核内调度问题的分层优化：缓存管理与性能均衡策略 问题 3 的模型建立与求解 问题分析

5 问题 3 的模型建立与求解5.1 问题分析在 NPU 的核内调度问题中问题 1 和问题 2 分别聚焦于最小化缓存驻留容量和总额 外数据搬运量从而构建了一个基础的调度框架如图4所示。问题 1 通过优化调度顺序 降低了计算图执行过程中对缓存空间的最大需求即 max(Vstay)而问题 2 在硬件缓存容 量限制下通过地址分配和 Spill 操作进一步减少了因空间不足导致的额外数据搬运开 销。然而这一框架可能未能充分优化总执行时间——即计算图在硬件上完成所有任务所 需的时钟周期数。原因在于问题 1 和问题 2 的优化目标主要围绕缓存资源管理而未显 式考虑如何最大化硬件执行单元的并行性、减少指令间的空闲等待时间。因此问题 3 要 求在总额外数据搬运量不显著增加的前提下设计性能优化策略以最小化总执行时间 或对数据搬运量和执行时间进行联合优化。总执行时间表示在硬件上执行完计算图需要的总时钟周期数直接决定了神经网络算 子在边缘设备上的推理延迟是衡量调度算法实际效能的关键指标。SIMD 架构的硬件特 性如多执行单元并行、多级缓存层次为优化提供了空间但也引入了复杂性调度顺 序和缓存分配不仅影响资源使用效率还决定了指令流水线的连贯性和单元利用率。问题 3 的本质是在满足数据依赖和硬件约束的条件下通过调度和资源分配的精细调整实现 计算密集型任务的高效并行执行。硬件上各个不同单元虽然可以同时工作但由于指令间存在依赖关系某条指令要能 在某个单元上执行必须等待其前序指令在其他单元上执行完毕。两种依赖关系可能 导致节点执行时需要等待一是计算图中节点间已有的依赖边二是缓存物理地址复用带 来的执行依赖。优良的调度方案能使得各执行单元交替工作并行地流水化处理计算图各 节点最小化各执行单元等待时间从而减少总执行时间提升运行效率。总执行时间的计算是一个多阶段的过程需依次考虑缓存换入换出操作、地址复用依 赖以及硬件单元的并行执行约束。具体而言可分为以下三个主要步骤步骤一Spill 操作节点插入若调度方案中包含缓存换入换出操作则需在原计算图中插入相应的 Spill_OUT 与 Spill_IN 节点。同时需根据 Spill 操作在调度序列中的位置建立新的依赖边若调度方案中未引入 Spill 操作则可跳过本步骤。同时考虑到插入 Spill_OUT 与 Spill_IN 节点会 引入额外的时间消耗有和步骤二缓存复用依赖分析在缓存分配方案中若多个缓冲区分时复用同一片物理地址空间则其生命周期不得 重叠且后续缓冲区的分配操作必须等待前一缓冲区释放之后才能执行。为此需遍历所 有缓冲区的 ALLOC 节点检查其是否复用了先前已分配缓冲区的地址空间。若是则需 在图中添加一条从前一缓冲区的 FREE 节点到当前缓冲区 ALLOC 节点的依赖边。此类依 赖边反映了硬件缓存资源的时序约束是确保数据一致性的必要条件。步骤三基于约束的流水线时序排布在完成前述两步对计算图的扩展与依赖边补充后即可进行流水线时序排布。设扩展 后的计算图为 G ′ {V ′ , E ′}其中 V ′ 为节点集合E ′ 为依赖边集合。每个节点 vi ∈ V ′ 的 起始时间 St(vi) 和结束时间 E(vi) 需满足以下约束条件 1非负性约束任一节点的起始时间不得为负即2资源独占约束同一执行单元在任意时刻最多只能执行一个节点。从单个执行单 元的视角来看它严格遵循调度序列中节点的排列顺序依次执行不具备乱序执行能力。 也就是说如果节点 b 排在节点 a 之后且两者属于同一执行单元那么该单元必然先执 行完节点 a才会开始执行节点 b。3执行依赖约束对于任意依赖边 (ui , vi) ∈ E ′节点 vi 必须在其所有前驱节点 ui 执行结束后才能开始执行即4执行耗时约束节点的结束时间等于其起始时间加上该节点在其执行单元上所需 的时钟周期数。对于非缓存管理节点即实际操作节点有对于缓存管理节点其执行耗时视为零即 Cycles(vi) 0故 E(vi) St(vi)。在满足上述所有约束的前提下总执行时间即为所有节点结束时间的最大值。为更直观地展示各硬件单元在时序上的工作状态可采用流水图进行可视化。流水图 以时间为横轴以不同的执行单元为纵轴图中每一条水平线段表示一个节点在相应单元 上的执行区间。例如在图5所示的 Exp 计算图中若按调度序列 0 → 1 → 2 → 3 → 4 → 5 → 6 执行其流水图如图9所示。其中缓存管理节点ID 为 0、2、4、6因执行周期 为零而未予显示操作节点 1、3、5 因存在依赖关系而串行执行总执行时间为 60 个时钟 周期。值得注意的是不同硬件单元之间具备并行执行能力。如图7所示当计算图中存在 多个独立子图时通过将后续子图的 COPY_IN 操作提前执行可与当前子图的计算阶段 重叠形成流水线并行从而有效压缩总执行时间。这种并行能力的挖掘是优化总执行时 间的关键途径。问题 3 的复杂性在于优化执行时间往往需要更激进的并行调度如提前执行独立指 令但这可能导致缓存访问冲突、生命周期重叠增加从而触发更多 Spill 操作抬高数 据搬运量。因此优化策略必须在时空资源分配上做出精细权衡。