1. 项目概述当调度遇见绑定一场硬件映射的“双向奔赴”在硬件加速器和高性能计算的世界里我们总在追求一个看似矛盾的目标既要马儿跑得快高性能、低延迟又要马儿吃得少低功耗、小面积。尤其是在粗粒度可重构阵列CGRA这类灵活又高效的平台上将一个用高级语言比如Matlab或C描述的算法高效地“翻译”并“安放”到具体的硬件资源上这个过程被称为高层次综合HLS中的映射。而映射问题的核心就是调度和绑定这两个相爱相杀的兄弟。你可以把CGRA想象成一个现代化的、可灵活布置的工厂车间。调度就像是给生产线上的每一道工序排定时间表先做A再做BC和D可以并行……目标是让整个产品计算结果的出厂时间总执行周期最短。绑定则是决定哪台机器功能单元如ALU、乘法器执行哪道工序以及原材料和半成品数据变量存放在哪个仓库寄存器文件或内存里。目标是让物料搬运路径最短减少车间内的交通拥堵和能耗。传统做法往往是串行的先不管三七二十一把工序固定到机器上绑定然后再去排时间表调度或者反过来。这就好比先强行把零件分配到各个工位再发现有些工位忙死、有些闲死流水线根本流畅不起来。因为绑定决策会极大地影响调度的灵活性反之亦然。它们本质上是深度耦合的。于是我们决定让它们“牵手”——进行调度与绑定的联合优化。而促成这场“联姻”的数学红娘就是整数线性规划。ILP允许我们将所有约束比如一个机器同一时间只能干一件事、数据依赖关系、存储空间限制和目标最小化总周期数、最小化数据搬运距离用一堆线性方程和不等式严谨地描述出来然后丢给求解器去找到一个全局最优或近似最优的解决方案。本文聚焦的SiLago框架正是一个需要这种“精细手术”的舞台。它包含DRRA动态可重构资源阵列和DiMArch分布式内存架构两种可重构硬件织物。之前的Vesyla编译器采用先绑定、后调度的串行策略效果难免打折扣。我们的工作就是为SiLago量身打造一套基于ILP的联合优化方法让调度和绑定同时进行协同决策最终在延迟和功耗上获得显著提升。2. 核心思路拆解ILP如何为硬件映射建模要把一个具体的工程问题转化为ILP模型关键在于如何用数学语言精准地描述它。这就像为一场复杂的多目标调度任务编写一份毫无歧义的“宪法”。我们的“宪法”主要包含以下几个部分决策变量、目标函数和约束条件。2.1 决策变量定义用0和1描述所有可能性在ILP的世界里一切选择都用二进制变量0或1来表示。对于我们的调度与绑定问题我们定义了几类核心变量操作调度变量ost_ijk和oend_ijk。这是一个三维变量。i代表第i个操作j代表第j个时钟周期k代表第k个DPU数据处理单元。如果ost_ijk 1就意味着操作i在周期j于DPUk上开始执行。同理oend_ijk表示操作i在周期j于DPUk上结束。通过这类变量我们精确刻画了每个操作在何时、何地开始和结束。资源绑定变量x_ijk和y_ijk。x_ijk表示寄存器文件变量i在周期j是否被绑定到第k个寄存器文件。y_ijk则表示SRAM变量i在周期j是否被绑定到第k个SRAM宏。这些变量决定了数据住在哪个“房间”。辅助变量为了简化约束或计算目标我们还需要一些辅助变量比如操作i的开始时间T_i^st、结束时间T_i^end以及操作i在周期j是否正在执行oP_ij。实操心得定义变量是建模的第一步也是最容易出错的一步。一定要确保变量定义能无歧义地覆盖所有需要做出的决策。例如用独立的开始和结束变量而不是一个持续时间变量能更自然地表达“一个操作必须在某个资源上连续执行”的约束。2.2 双目标权衡时间与空间的博弈我们的优化目标不是单一的需要在两个关键维度上取得平衡目标一最小化执行时间。这直接对应着系统的性能。我们希望所有操作完成的总时钟周期数T尽可能小。目标二最小化数据转移互连长度。在硬件中数据搬运从SRAM到寄存器从寄存器到DPU是需要消耗能量和时间的。互连长度越长动态功耗通常越高信号延迟也可能越大。我们通过计算资源DPU、寄存器文件、SRAM之间的曼哈顿距离坐标差的绝对值之和来量化这个长度。如何将两个目标合并我们引入了权重因子α和β构成一个加权和的目标函数最小化 [ α * (总执行时间相关项) β * (总互连长度相关项) ]α和β的魔力α1 β0这就是“性能至上”模式。ILP求解器将不惜一切代价压缩执行周期哪怕数据需要跨越大半个芯片去搬运。适合对延迟极度敏感的应用。α0 β1这是“功耗优先”模式。求解器会尽量把通信频繁的操作和数据绑定到彼此相邻的资源上形成紧凑的局部计算簇哪怕这可能会拉长整个任务的执行时间。适合能量受限的移动或嵌入式场景。α和β取中间值在性能和功耗之间进行折衷。我们通过实验为不同类型的计算任务如BLAS例程、图像处理找到了一组经验性的最优权重α_opt和β_opt使得在两者间取得最佳平衡。核心原理这个加权和的方法在优化理论中非常常见它将一个多目标优化问题转化为单目标问题。其物理意义在于它允许设计者根据应用场景是服务器加速卡还是物联网传感器来设定优化优先级提供了宝贵的设计空间探索能力。2.3 约束条件硬件世界的“物理法则”目标函数指明了方向约束条件则划定了可行的道路。我们的ILP模型包含了四大类约束确保解是物理可实现的调度约束唯一性每个操作必须恰好开始一次、结束一次。起止时间关系操作的结束时间 开始时间 执行延迟 - 1。数据依赖如果操作B依赖于操作A的结果那么B的开始时间必须晚于A的结束时间。这是保证程序正确性的基石。时间上界所有操作的结束时间都不能超过总执行时间T。DPU绑定约束资源独占同一个DPU在同一个时钟周期内最多只能执行一个操作。这避免了硬件冲突。位置一致性一个操作必须在其开始和结束的整个时间段内被绑定到同一个DPU上。不能中途“跳车”。寄存器文件绑定约束容量限制一个寄存器文件里存储的所有变量总大小不能超过其深度可存储的单词数。这是最容易被忽略的约束之一尤其在变量生命周期重叠时。端口限制寄存器文件的读写端口数量有限同一周期内进行读或写的变量数不能超过端口数。这模拟了实际的硬件访问瓶颈。滑动窗口通信这是DRRA架构的一个特色。一个寄存器文件只能和处于其“滑动窗口”例如左右各两列范围内的DPU或其他寄存器文件直接通信。这个约束极大地缩小了搜索空间也体现了架构特性对映射的决定性影响。SRAM绑定约束类似于寄存器文件也有容量和通信距离滑动窗口的约束。避坑指南约束条件的编写必须极其严谨。例如“滑动窗口”约束如果写错求解器可能会给出一个无法在真实硬件上路由的绑定方案。在模型验证阶段除了看结果是否最优一定要将解“翻译”回具体的调度表和绑定图人工检查是否违反任何硬件限制。一个技巧是先用小规模、已知最优解的问题来测试你的约束集是否正确。3. 从模型到实践在SiLago框架中的实现流程有了完美的数学模型下一步就是将其集成到实际的编译框架中并让它高效地运转起来。下图清晰地展示了我们方法的完整工作流程graph TD A[输入: Matlab风格代码] -- B[Vesyla前端解析]; B -- C[生成CADFGbr/控制地址数据流图]; C -- D[提取ILP模型参数br/操作数/变量数/依赖关系等]; D -- E[定义决策变量与目标函数]; E -- F[构建约束条件体系br/调度/DPU绑定/RF绑定/SRAM绑定]; F -- G[调用IBM CPLEX求解器]; G -- H{获得最优解?}; H -- 是 -- I[输出: 调度表与绑定方案]; I -- J[生成DRRA/DiMArch配置码]; H -- 否 -- K[调整模型参数/权重]; K -- F;3.1 输入与中间表示CADFG的核心作用我们的流程始于用特定风格带有编译指示编写的Matlab代码。Vesyla编译器首先会将其解析并转换为一个名为CADFG的中间表示。CADFG全称控制地址数据流图它比传统的数据流图DFG更丰富不仅包含了操作之间的数据依赖关系还包含了地址计算、控制流和存储访问信息。为什么是CADFG而不是DFG因为SiLago的DRRA架构具有独特的地址生成单元。数据在SRAM和寄存器文件之间的搬运不是简单的读写而是需要AGU产生地址序列。CADFG能捕获这些地址计算操作这对于生成正确的配置码至关重要。我们的ILP模型中的许多参数如操作类型、变量生命周期、依赖关系都是从CADFG中自动提取的这实现了从高级语言到优化问题的无缝衔接。3.2 模型求解与配置生成参数齐备后我们按照前文所述的公式构建完整的ILP模型并调用业界成熟的IBM ILOG CPLEX求解器进行计算。CPLEX内部采用分支定界、割平面等高级算法在这个由0-1变量构成的巨大组合空间中进行搜索。求解成功后我们得到的是所有决策变量的赋值。我们需要将这些“0”和“1”解码成人类和硬件可理解的信息调度表每个操作在哪个时钟周期、在哪个DPU上执行。绑定表每个寄存器变量绑定到哪个寄存器文件每个SRAM变量绑定到哪个SRAM宏。最后Vesyla的后端会根据这份详细的“施工蓝图”生成针对DRRA每个单元的配置码以及整个SiLago块SiLago Block的布局。这些配置码被加载到硬件上即可正确执行目标应用。实操心得ILP求解可能非常耗时尤其对于大规模问题。在实践中我们并非总是追求数学上的绝对最优解。CPLEX可以在达到一定时间限制或找到满足特定间隙的最优解时停止。对于快速设计空间探索我们可以先设置一个较短的超时时间比较不同α/β配置下的解质量快速锁定有潜力的方向再对重点配置进行更长时间的精确求解。4. 实验验证与深度分析数字会说话理论再优美也需要实验的检验。我们在SiLago框架上针对一系列标准计算内核进行了全面的测试。4.1 基准测试与实验设置我们选用了两类典型的计算负载基础线性代数子程序包括矩阵-向量乘法、矩阵-矩阵乘法等。这是科学计算和机器学习的基石。图像处理任务包括2D卷积、图像平均和Sobel边缘检测。这类任务具有规则的数据并行性非常适合CGRA加速。硬件参数基于真实的DRRA/DiMArch设计采用28nm工艺时钟频率200MHz。我们使用Synopsys Design Compiler进行逻辑综合Cadence Innovus进行物理综合和功耗分析并通过仿真获取开关活动性数据。4.2 权重因子的影响一个三维权衡案例为了直观展示α和β如何影响结果我们以blas3gemv矩阵-向量乘法为例展示三种典型配置下的调度与绑定结果配置案例α (调度权重)β (绑定权重)总执行周期DPU绑定位置RF变量绑定列分布互连长度趋势优化倾向Case 110最少集中如[0,0]可能分散在两列长极端追求性能忽略通信开销Case 201最多集中高度集中在一列最短极端追求低功耗允许时间增加Case 3α_optβ_opt接近最少平衡分布平衡分布较短性能与功耗的平衡点结果解读Case 1求解器全力压缩周期数它可能会把操作调度得非常紧凑甚至采用更多的并行。但这可能导致产生的中间变量被“随意”放置到还有空间的寄存器文件中而不管它们之间的距离从而增加了数据搬运的路径长度和功耗。Case 2求解器全力缩短通信距离它会尽量将同时使用的操作和数据绑定到物理上相邻的资源上形成一个紧凑簇。但这可能限制了操作的并行度因为相邻区域的资源是有限的从而拉长了总执行时间。Case 3通过精心选择的α_opt和β_opt例如通过公式α_opt x2/(x1x2),β_opt x1/(x1x2)其中x1, x2为Case1和Case2的目标函数值我们找到了一个帕累托最优点。在这个点上既获得了接近Case 1的高性能又保持了接近Case 2的低通信开销实现了整体最优。4.3 与现有方法的对比联合优化的威力我们将提出的联合优化方法ILP-SSB与Vesyla原有的串行方法先手动/启发式绑定再列表调度进行了对比。对比指标是延迟和功耗。实验结果令人振奋对于测试的所有基准程序ILP-SSB方法均取得了显著优势。延迟降低由于调度时能充分考虑绑定带来的资源竞争和通信延迟联合优化可以找到更优的调度序列平均延迟降低了约15%-25%。功耗降低由于绑定时能前瞻性地考虑调度带来的数据生命周期和访问模式联合优化可以将通信频繁的数据放置在更近的位置平均动态功耗降低了约20%-30%。深度分析这个提升从何而来串行方法的根本问题在于“目光短浅”。先绑定就等于提前把操作钉死在了某些资源上后续调度只能在这个僵化的资源布局上做文章失去了全局优化的机会。而联合优化如同一位高明的棋手每一步调度或绑定都考虑了对后续十步的影响从而能走出更妙的棋局。4.4 可扩展性与编译时间分析ILP方法的经典挑战是可扩展性。随着问题规模操作数、变量数、硬件阵列大小增大变量和约束数量会呈组合级增长求解时间可能爆炸。我们的实验也印证了这一点问题规模增大当图像处理核的窗口尺寸变大或DRRA阵列的列数增加时编译时间明显上升。矩阵维度增大对于BLAS例程当输入矩阵从16x16增大到64x64时编译时间从几十秒增长到上千秒。然而这并非致命伤原因如下实际应用场景许多嵌入式和加速场景中映射的目标是计算密集的内核或循环体其规模通常是可控的几十到几百个操作。对于这类问题ILP可以在可接受的时间内几分钟到几十分钟求得优质解。设计流程定位HLS通常用于设计固化的加速器。编译时间即使是数小时相对于长达数周或数月的芯片设计周期来说是可以接受的。一次性的编译开销换来的是硬件在整个生命周期内更优的性能和能效。混合策略对于超大规模问题可以采用分层或分治策略。例如先用启发式方法如模拟退火、遗传算法得到一个较好的初始解再用ILP对关键子图进行局部优化。经验之谈在实际项目中使用ILP时一定要设置合理的求解时间上限和最优间隙容忍度。不要追求“绝对最优”而是追求“在合理时间内足够好”。同时ILP模型本身如本文的模型具有良好的参数化特性。当硬件架构参数如寄存器文件深度、滑动窗口大小改变时只需调整模型中的相应常数而无需重写整个模型这为架构探索提供了极大便利。5. 超越SiLago方法的通用性思考虽然本文工作是基于SiLago框架及其DRRA/DiMArch架构但所提出的ILP方法具有相当的通用性。其核心思想——将调度和绑定的约束与目标联合建模——可以迁移到其他CGRA甚至更通用的硬件架构上。如何适配其他架构关键在于约束的调整资源类型如果目标架构有乘法器、加法器、移位器等异构功能单元只需在DPU绑定约束中增加单元类型匹配的限制。互连拓扑DRRA采用滑动窗口近邻连接。如果目标架构是网格状总线或基于NoC则需要修改通信约束用路由跳数或链路带宽来替代曼哈顿距离。存储层次如果有多级缓存或共享内存需要在模型中引入相应的存储变量和访问延迟约束。本方法的独特优势在于其“白盒”特性它明确地建模了所有重要的硬件限制和优化目标。与一些黑盒启发式方法相比ILP模型本身就是一个清晰、可验证的架构规约文档。通过调整模型参数可以快速评估不同架构设计选择对映射结果的影响从而在硬件设计早期就提供有价值的反馈。6. 总结与展望通过这项研究我们成功地将整数线性规划这一强大的数学工具应用于解决CGRA映射中的调度与绑定联合优化这一NP难问题。实验证明在SiLago框架上相较于传统的串行方法我们的ILP-SSB方法能够同时降低关键路径延迟和动态功耗为高效能、低功耗的硬件加速器设计提供了一条有效路径。回顾整个工作有几点深刻的体会首先对问题本质的深刻理解是建模的前提。必须吃透硬件架构的每一个细节如滑动窗口、AGU、端口限制才能将其转化为正确的线性约束差之毫厘解就可能谬以千里。 其次多目标优化中的权重设置是一门艺术。α和β不是随便给的需要结合具体应用场景和对性能/功耗的权衡偏好。我们提供的基于极端情况归一化的经验公式是一个不错的起点。 最后ILP并非银弹但它是一把精准的手术刀。在问题规模适中、对解质量要求极高的场景下它无可替代。对于更大规模的问题未来可以探索将其与启发式方法结合例如用ILP优化关键子图或用启发式结果为ILP提供优质初始解以加速求解。这项工作也为未来打开了多扇门如何将路由问题也纳入联合优化如何支持动态可重构场景下的在线映射如何为更复杂的控制流和数据流建模这些都是值得继续探索的方向。但无论如何将调度与绑定这对“孪生兄弟”置于统一的优化框架下协同考虑无疑是通往更高效硬件映射的必由之路。
基于整数线性规划的CGRA调度与绑定联合优化方法
1. 项目概述当调度遇见绑定一场硬件映射的“双向奔赴”在硬件加速器和高性能计算的世界里我们总在追求一个看似矛盾的目标既要马儿跑得快高性能、低延迟又要马儿吃得少低功耗、小面积。尤其是在粗粒度可重构阵列CGRA这类灵活又高效的平台上将一个用高级语言比如Matlab或C描述的算法高效地“翻译”并“安放”到具体的硬件资源上这个过程被称为高层次综合HLS中的映射。而映射问题的核心就是调度和绑定这两个相爱相杀的兄弟。你可以把CGRA想象成一个现代化的、可灵活布置的工厂车间。调度就像是给生产线上的每一道工序排定时间表先做A再做BC和D可以并行……目标是让整个产品计算结果的出厂时间总执行周期最短。绑定则是决定哪台机器功能单元如ALU、乘法器执行哪道工序以及原材料和半成品数据变量存放在哪个仓库寄存器文件或内存里。目标是让物料搬运路径最短减少车间内的交通拥堵和能耗。传统做法往往是串行的先不管三七二十一把工序固定到机器上绑定然后再去排时间表调度或者反过来。这就好比先强行把零件分配到各个工位再发现有些工位忙死、有些闲死流水线根本流畅不起来。因为绑定决策会极大地影响调度的灵活性反之亦然。它们本质上是深度耦合的。于是我们决定让它们“牵手”——进行调度与绑定的联合优化。而促成这场“联姻”的数学红娘就是整数线性规划。ILP允许我们将所有约束比如一个机器同一时间只能干一件事、数据依赖关系、存储空间限制和目标最小化总周期数、最小化数据搬运距离用一堆线性方程和不等式严谨地描述出来然后丢给求解器去找到一个全局最优或近似最优的解决方案。本文聚焦的SiLago框架正是一个需要这种“精细手术”的舞台。它包含DRRA动态可重构资源阵列和DiMArch分布式内存架构两种可重构硬件织物。之前的Vesyla编译器采用先绑定、后调度的串行策略效果难免打折扣。我们的工作就是为SiLago量身打造一套基于ILP的联合优化方法让调度和绑定同时进行协同决策最终在延迟和功耗上获得显著提升。2. 核心思路拆解ILP如何为硬件映射建模要把一个具体的工程问题转化为ILP模型关键在于如何用数学语言精准地描述它。这就像为一场复杂的多目标调度任务编写一份毫无歧义的“宪法”。我们的“宪法”主要包含以下几个部分决策变量、目标函数和约束条件。2.1 决策变量定义用0和1描述所有可能性在ILP的世界里一切选择都用二进制变量0或1来表示。对于我们的调度与绑定问题我们定义了几类核心变量操作调度变量ost_ijk和oend_ijk。这是一个三维变量。i代表第i个操作j代表第j个时钟周期k代表第k个DPU数据处理单元。如果ost_ijk 1就意味着操作i在周期j于DPUk上开始执行。同理oend_ijk表示操作i在周期j于DPUk上结束。通过这类变量我们精确刻画了每个操作在何时、何地开始和结束。资源绑定变量x_ijk和y_ijk。x_ijk表示寄存器文件变量i在周期j是否被绑定到第k个寄存器文件。y_ijk则表示SRAM变量i在周期j是否被绑定到第k个SRAM宏。这些变量决定了数据住在哪个“房间”。辅助变量为了简化约束或计算目标我们还需要一些辅助变量比如操作i的开始时间T_i^st、结束时间T_i^end以及操作i在周期j是否正在执行oP_ij。实操心得定义变量是建模的第一步也是最容易出错的一步。一定要确保变量定义能无歧义地覆盖所有需要做出的决策。例如用独立的开始和结束变量而不是一个持续时间变量能更自然地表达“一个操作必须在某个资源上连续执行”的约束。2.2 双目标权衡时间与空间的博弈我们的优化目标不是单一的需要在两个关键维度上取得平衡目标一最小化执行时间。这直接对应着系统的性能。我们希望所有操作完成的总时钟周期数T尽可能小。目标二最小化数据转移互连长度。在硬件中数据搬运从SRAM到寄存器从寄存器到DPU是需要消耗能量和时间的。互连长度越长动态功耗通常越高信号延迟也可能越大。我们通过计算资源DPU、寄存器文件、SRAM之间的曼哈顿距离坐标差的绝对值之和来量化这个长度。如何将两个目标合并我们引入了权重因子α和β构成一个加权和的目标函数最小化 [ α * (总执行时间相关项) β * (总互连长度相关项) ]α和β的魔力α1 β0这就是“性能至上”模式。ILP求解器将不惜一切代价压缩执行周期哪怕数据需要跨越大半个芯片去搬运。适合对延迟极度敏感的应用。α0 β1这是“功耗优先”模式。求解器会尽量把通信频繁的操作和数据绑定到彼此相邻的资源上形成紧凑的局部计算簇哪怕这可能会拉长整个任务的执行时间。适合能量受限的移动或嵌入式场景。α和β取中间值在性能和功耗之间进行折衷。我们通过实验为不同类型的计算任务如BLAS例程、图像处理找到了一组经验性的最优权重α_opt和β_opt使得在两者间取得最佳平衡。核心原理这个加权和的方法在优化理论中非常常见它将一个多目标优化问题转化为单目标问题。其物理意义在于它允许设计者根据应用场景是服务器加速卡还是物联网传感器来设定优化优先级提供了宝贵的设计空间探索能力。2.3 约束条件硬件世界的“物理法则”目标函数指明了方向约束条件则划定了可行的道路。我们的ILP模型包含了四大类约束确保解是物理可实现的调度约束唯一性每个操作必须恰好开始一次、结束一次。起止时间关系操作的结束时间 开始时间 执行延迟 - 1。数据依赖如果操作B依赖于操作A的结果那么B的开始时间必须晚于A的结束时间。这是保证程序正确性的基石。时间上界所有操作的结束时间都不能超过总执行时间T。DPU绑定约束资源独占同一个DPU在同一个时钟周期内最多只能执行一个操作。这避免了硬件冲突。位置一致性一个操作必须在其开始和结束的整个时间段内被绑定到同一个DPU上。不能中途“跳车”。寄存器文件绑定约束容量限制一个寄存器文件里存储的所有变量总大小不能超过其深度可存储的单词数。这是最容易被忽略的约束之一尤其在变量生命周期重叠时。端口限制寄存器文件的读写端口数量有限同一周期内进行读或写的变量数不能超过端口数。这模拟了实际的硬件访问瓶颈。滑动窗口通信这是DRRA架构的一个特色。一个寄存器文件只能和处于其“滑动窗口”例如左右各两列范围内的DPU或其他寄存器文件直接通信。这个约束极大地缩小了搜索空间也体现了架构特性对映射的决定性影响。SRAM绑定约束类似于寄存器文件也有容量和通信距离滑动窗口的约束。避坑指南约束条件的编写必须极其严谨。例如“滑动窗口”约束如果写错求解器可能会给出一个无法在真实硬件上路由的绑定方案。在模型验证阶段除了看结果是否最优一定要将解“翻译”回具体的调度表和绑定图人工检查是否违反任何硬件限制。一个技巧是先用小规模、已知最优解的问题来测试你的约束集是否正确。3. 从模型到实践在SiLago框架中的实现流程有了完美的数学模型下一步就是将其集成到实际的编译框架中并让它高效地运转起来。下图清晰地展示了我们方法的完整工作流程graph TD A[输入: Matlab风格代码] -- B[Vesyla前端解析]; B -- C[生成CADFGbr/控制地址数据流图]; C -- D[提取ILP模型参数br/操作数/变量数/依赖关系等]; D -- E[定义决策变量与目标函数]; E -- F[构建约束条件体系br/调度/DPU绑定/RF绑定/SRAM绑定]; F -- G[调用IBM CPLEX求解器]; G -- H{获得最优解?}; H -- 是 -- I[输出: 调度表与绑定方案]; I -- J[生成DRRA/DiMArch配置码]; H -- 否 -- K[调整模型参数/权重]; K -- F;3.1 输入与中间表示CADFG的核心作用我们的流程始于用特定风格带有编译指示编写的Matlab代码。Vesyla编译器首先会将其解析并转换为一个名为CADFG的中间表示。CADFG全称控制地址数据流图它比传统的数据流图DFG更丰富不仅包含了操作之间的数据依赖关系还包含了地址计算、控制流和存储访问信息。为什么是CADFG而不是DFG因为SiLago的DRRA架构具有独特的地址生成单元。数据在SRAM和寄存器文件之间的搬运不是简单的读写而是需要AGU产生地址序列。CADFG能捕获这些地址计算操作这对于生成正确的配置码至关重要。我们的ILP模型中的许多参数如操作类型、变量生命周期、依赖关系都是从CADFG中自动提取的这实现了从高级语言到优化问题的无缝衔接。3.2 模型求解与配置生成参数齐备后我们按照前文所述的公式构建完整的ILP模型并调用业界成熟的IBM ILOG CPLEX求解器进行计算。CPLEX内部采用分支定界、割平面等高级算法在这个由0-1变量构成的巨大组合空间中进行搜索。求解成功后我们得到的是所有决策变量的赋值。我们需要将这些“0”和“1”解码成人类和硬件可理解的信息调度表每个操作在哪个时钟周期、在哪个DPU上执行。绑定表每个寄存器变量绑定到哪个寄存器文件每个SRAM变量绑定到哪个SRAM宏。最后Vesyla的后端会根据这份详细的“施工蓝图”生成针对DRRA每个单元的配置码以及整个SiLago块SiLago Block的布局。这些配置码被加载到硬件上即可正确执行目标应用。实操心得ILP求解可能非常耗时尤其对于大规模问题。在实践中我们并非总是追求数学上的绝对最优解。CPLEX可以在达到一定时间限制或找到满足特定间隙的最优解时停止。对于快速设计空间探索我们可以先设置一个较短的超时时间比较不同α/β配置下的解质量快速锁定有潜力的方向再对重点配置进行更长时间的精确求解。4. 实验验证与深度分析数字会说话理论再优美也需要实验的检验。我们在SiLago框架上针对一系列标准计算内核进行了全面的测试。4.1 基准测试与实验设置我们选用了两类典型的计算负载基础线性代数子程序包括矩阵-向量乘法、矩阵-矩阵乘法等。这是科学计算和机器学习的基石。图像处理任务包括2D卷积、图像平均和Sobel边缘检测。这类任务具有规则的数据并行性非常适合CGRA加速。硬件参数基于真实的DRRA/DiMArch设计采用28nm工艺时钟频率200MHz。我们使用Synopsys Design Compiler进行逻辑综合Cadence Innovus进行物理综合和功耗分析并通过仿真获取开关活动性数据。4.2 权重因子的影响一个三维权衡案例为了直观展示α和β如何影响结果我们以blas3gemv矩阵-向量乘法为例展示三种典型配置下的调度与绑定结果配置案例α (调度权重)β (绑定权重)总执行周期DPU绑定位置RF变量绑定列分布互连长度趋势优化倾向Case 110最少集中如[0,0]可能分散在两列长极端追求性能忽略通信开销Case 201最多集中高度集中在一列最短极端追求低功耗允许时间增加Case 3α_optβ_opt接近最少平衡分布平衡分布较短性能与功耗的平衡点结果解读Case 1求解器全力压缩周期数它可能会把操作调度得非常紧凑甚至采用更多的并行。但这可能导致产生的中间变量被“随意”放置到还有空间的寄存器文件中而不管它们之间的距离从而增加了数据搬运的路径长度和功耗。Case 2求解器全力缩短通信距离它会尽量将同时使用的操作和数据绑定到物理上相邻的资源上形成一个紧凑簇。但这可能限制了操作的并行度因为相邻区域的资源是有限的从而拉长了总执行时间。Case 3通过精心选择的α_opt和β_opt例如通过公式α_opt x2/(x1x2),β_opt x1/(x1x2)其中x1, x2为Case1和Case2的目标函数值我们找到了一个帕累托最优点。在这个点上既获得了接近Case 1的高性能又保持了接近Case 2的低通信开销实现了整体最优。4.3 与现有方法的对比联合优化的威力我们将提出的联合优化方法ILP-SSB与Vesyla原有的串行方法先手动/启发式绑定再列表调度进行了对比。对比指标是延迟和功耗。实验结果令人振奋对于测试的所有基准程序ILP-SSB方法均取得了显著优势。延迟降低由于调度时能充分考虑绑定带来的资源竞争和通信延迟联合优化可以找到更优的调度序列平均延迟降低了约15%-25%。功耗降低由于绑定时能前瞻性地考虑调度带来的数据生命周期和访问模式联合优化可以将通信频繁的数据放置在更近的位置平均动态功耗降低了约20%-30%。深度分析这个提升从何而来串行方法的根本问题在于“目光短浅”。先绑定就等于提前把操作钉死在了某些资源上后续调度只能在这个僵化的资源布局上做文章失去了全局优化的机会。而联合优化如同一位高明的棋手每一步调度或绑定都考虑了对后续十步的影响从而能走出更妙的棋局。4.4 可扩展性与编译时间分析ILP方法的经典挑战是可扩展性。随着问题规模操作数、变量数、硬件阵列大小增大变量和约束数量会呈组合级增长求解时间可能爆炸。我们的实验也印证了这一点问题规模增大当图像处理核的窗口尺寸变大或DRRA阵列的列数增加时编译时间明显上升。矩阵维度增大对于BLAS例程当输入矩阵从16x16增大到64x64时编译时间从几十秒增长到上千秒。然而这并非致命伤原因如下实际应用场景许多嵌入式和加速场景中映射的目标是计算密集的内核或循环体其规模通常是可控的几十到几百个操作。对于这类问题ILP可以在可接受的时间内几分钟到几十分钟求得优质解。设计流程定位HLS通常用于设计固化的加速器。编译时间即使是数小时相对于长达数周或数月的芯片设计周期来说是可以接受的。一次性的编译开销换来的是硬件在整个生命周期内更优的性能和能效。混合策略对于超大规模问题可以采用分层或分治策略。例如先用启发式方法如模拟退火、遗传算法得到一个较好的初始解再用ILP对关键子图进行局部优化。经验之谈在实际项目中使用ILP时一定要设置合理的求解时间上限和最优间隙容忍度。不要追求“绝对最优”而是追求“在合理时间内足够好”。同时ILP模型本身如本文的模型具有良好的参数化特性。当硬件架构参数如寄存器文件深度、滑动窗口大小改变时只需调整模型中的相应常数而无需重写整个模型这为架构探索提供了极大便利。5. 超越SiLago方法的通用性思考虽然本文工作是基于SiLago框架及其DRRA/DiMArch架构但所提出的ILP方法具有相当的通用性。其核心思想——将调度和绑定的约束与目标联合建模——可以迁移到其他CGRA甚至更通用的硬件架构上。如何适配其他架构关键在于约束的调整资源类型如果目标架构有乘法器、加法器、移位器等异构功能单元只需在DPU绑定约束中增加单元类型匹配的限制。互连拓扑DRRA采用滑动窗口近邻连接。如果目标架构是网格状总线或基于NoC则需要修改通信约束用路由跳数或链路带宽来替代曼哈顿距离。存储层次如果有多级缓存或共享内存需要在模型中引入相应的存储变量和访问延迟约束。本方法的独特优势在于其“白盒”特性它明确地建模了所有重要的硬件限制和优化目标。与一些黑盒启发式方法相比ILP模型本身就是一个清晰、可验证的架构规约文档。通过调整模型参数可以快速评估不同架构设计选择对映射结果的影响从而在硬件设计早期就提供有价值的反馈。6. 总结与展望通过这项研究我们成功地将整数线性规划这一强大的数学工具应用于解决CGRA映射中的调度与绑定联合优化这一NP难问题。实验证明在SiLago框架上相较于传统的串行方法我们的ILP-SSB方法能够同时降低关键路径延迟和动态功耗为高效能、低功耗的硬件加速器设计提供了一条有效路径。回顾整个工作有几点深刻的体会首先对问题本质的深刻理解是建模的前提。必须吃透硬件架构的每一个细节如滑动窗口、AGU、端口限制才能将其转化为正确的线性约束差之毫厘解就可能谬以千里。 其次多目标优化中的权重设置是一门艺术。α和β不是随便给的需要结合具体应用场景和对性能/功耗的权衡偏好。我们提供的基于极端情况归一化的经验公式是一个不错的起点。 最后ILP并非银弹但它是一把精准的手术刀。在问题规模适中、对解质量要求极高的场景下它无可替代。对于更大规模的问题未来可以探索将其与启发式方法结合例如用ILP优化关键子图或用启发式结果为ILP提供优质初始解以加速求解。这项工作也为未来打开了多扇门如何将路由问题也纳入联合优化如何支持动态可重构场景下的在线映射如何为更复杂的控制流和数据流建模这些都是值得继续探索的方向。但无论如何将调度与绑定这对“孪生兄弟”置于统一的优化框架下协同考虑无疑是通往更高效硬件映射的必由之路。
