1. 项目概述当任务调度遇上硬件安全在芯片设计尤其是异构多处理器系统MPSoC设计领域我们一直在性能、功耗和面积这个“铁三角”之间做权衡。但随着供应链全球化一个过去被相对忽视的维度——硬件安全正变得前所未有的重要。你设计的芯片可能性能卓越、能效出众但如果其中某个由第三方提供的处理器核心3PIP被植入了硬件木马Hardware Trojan那么整个系统在特定条件下就可能被触发导致功能错误、信息泄露甚至完全失效。这不是危言耸听而是摆在所有系统架构师和芯片设计者面前的现实挑战。传统的“信任但验证”思路在复杂的第三方IP核面前往往力不从心。于是学术界和工业界提出了“供应商多样性”Vendor Diversity和“任务复制”Task Duplication这两种架构级的安全增强策略。简单来说就是不把鸡蛋放在一个篮子里关键的计算任务被复制成两份并由来自不同供应商的、功能等效但实现不同的处理器核心来执行只有两份结果一致时才被采纳。这能有效防范针对单一供应商的特定硬件木马攻击。然而安全不是免费的午餐。引入供应商多样性和任务复制相当于给原本的任务调度问题套上了一层复杂的“紧箍咒”。调度器不仅要考虑任务间的依赖关系、通信开销和资源竞争还必须遵守一系列安全约束比如两个存在数据依赖的敏感任务不能分配给同一个供应商以防该供应商的硬件木马同时污染这两个任务。这直接导致调度问题的解空间爆炸式增长传统的列表调度List Scheduling或力导向调度Force-Directed Scheduling算法难以直接应用。我最近深入研究了N. Wang等人在2018年发表的一篇论文《Security-Aware Task Scheduling Using Untrusted Components in High-Level Synthesis》并基于其核心思想进行了一系列的算法实现与工程化探索。这篇博文我将以一个一线工程师的视角为你拆解这个“基于安全约束的高层次综合任务调度算法”的核心原理、实现细节以及在实际应用中可能遇到的坑和应对技巧。无论你是正在研究安全关键系统设计的学者还是面临如何将安全需求落地的芯片开发者相信这些从论文到代码的实战经验都能给你带来启发。2. 核心安全约束与问题建模在深入算法之前我们必须先把问题定义清楚。安全感知调度不是在传统调度目标上简单加个“安全标签”而是从根本上改变了问题的约束条件和优化目标。2.1 安全约束的形式化从直觉到图论供应商多样性和任务复制带来的核心安全约束可以这样理解系统中有多个来自不同供应商的处理器核心。每个计算任务Task都有一个原始的“主版本”和一个用于比对的“复制版本”。这两个版本必须被调度到来自不同供应商的核心上执行。更进一步如果两个任务之间存在数据依赖即一个任务的输出是另一个任务的输入并且它们都被判定为“敏感任务”那么这两个任务包括它们的主版本和复制版本也不能被分配到同一个供应商的核心上。这是为了防止一个“恶意”供应商的核心通过数据流连续污染多个敏感任务从而绕过基于结果比对的检测机制。如何形式化地描述这些约束论文引入了供应商违规图Vendor Violation Graph, VVG这一核心概念。这是一个无向图其中每个节点代表一个任务簇Cluster由多个可合并的任务组成。如果两个任务簇不能被分配到同一个供应商即违反供应商多样性约束那么它们之间就存在一条边称为“敏感边”。这里的关键是“团”Clique的概念。在图论中团是一个图的完全子图即其中任意两个节点之间都有边相连。在VVG中如果一个团的大小即包含的节点数为 λ那么这意味着这个团里所有的 λ 个任务簇都两两不能共用供应商。因此要满足安全约束我们至少需要 λ 个不同的供应商来为这个团中的任务簇提供服务。这个 λ 就被定义为该任务簇的团大小它是调度算法中一个至关重要的动态属性。2.2 两类核心调度问题基于上述模型论文主要解决了两类问题这也是我们工程实践中常遇到的两类场景1. 资源约束下的任务调度给定固定数量的处理器核心资源和供应商数量λ目标是找到一个任务调度方案在满足所有安全约束的前提下最小化整个应用的调度长度Schedule Length也就是总的执行时间。这对应着成本核心数量固定的情况我们要尽可能跑得快。2. 性能约束下的任务调度给定一个性能目标即最大的允许调度长度和供应商数量约束λ目标是找到一个任务调度方案在满足性能目标的前提下最小化所需的核心数量同时尽可能少地违反安全约束因为有时在严格约束下可能无解。这对应着工期固定的情况我们要用最少的资源完成任务并权衡安全损失。无论是哪类问题其核心难点都在于安全约束体现在VVG的团结构上与调度决策任务在何时、何核心上执行强烈耦合。为一个任务分配供应商着色会改变其邻居任务在VVG中的团大小进而影响它们未来的可分配供应商集合。这是一个典型的NP难问题需要精巧的启发式算法。3. 算法基石供应商违规图VVG的动态维护整个调度算法的智能很大程度上体现在对VVG的实时、动态维护上。这不是一个静态的图而是一个随着调度决策不断演化的结构。3.1 团大小的计算与更新计算一个任务簇ci的团大小ω(ci)并不是简单地计算它在VVG中的最大团。论文的核心洞见在于我们只关心与ci通过敏感边相连的那些“敏感节点”构成的子图VVG‘_s(ci)。ci的团大小等于在VVG‘_s(ci)中能找到的最大团的大小。算法2Candidate Color Set Determination是动态维护的关键。它的目的是确定当前可以分配给任务簇ci的候选供应商集合clr(ci)。其逻辑是遍历所有可能的供应商颜色。对于每个供应商colork我们检查如果将ci分配给colork是否会违反安全约束。检查的方法是在VVG‘_s(ci)中移除所有当前团大小已经小于 λ 的节点因为它们不构成约束然后检查剩下的子图中是否存在至少 λ 个节点它们的度数都大于等于 λ-1。如果存在说明这个子图包含一个大小为 λ 的团那么当前供应商colork就不能分配给ci需要从候选集中移除。这个过程我最初实现时在“检查是否存在 λ-clique”这里遇到了性能瓶颈。穷举所有子图找最大团是指数级的。论文巧妙地用了度数条件作为启发式判断在一个包含 n 个节点的图中如果存在一个大小为 k 的团那么这 k 个节点的度数至少是 k-1。这是一个必要但不充分条件。在实际编码中我采用了一种更保守但更高效的方法维护一个“潜在团大小”的估计值并结合贪心搜索来验证。虽然可能略微多排除一些本可用的供应商但换来了算法运行时间的大幅下降在工程上是值得的。实操心得度数的动态更新VVG节点的度数是动态变化的。当两个任务簇因为调度决策被合并聚类时它们对应的节点在VVG中也会合并其度数需要重新计算。这里极易出错。我的经验是为VVG维护一个邻接表并在每次图结构变更节点删除、合并、边添加/删除时增量式地更新受影响节点的度数而不是全量重新计算。这能有效提升算法在迭代调度过程中的效率。3.2 任务聚类平衡安全与性能直接对原始任务图进行调度复杂度太高。因此算法先进行任务聚类将多个任务合并成一个更大的“超级任务”即任务簇从而减少调度实体的数量。这里有两条聚类路径面向供应商约束的聚类目标是减少最终VVG中的节点数从而降低满足供应商多样性所需的供应商数量。其核心是合并那些在任务图中相连但在VVG中不相连即可以共享供应商的任务。这通常使用基于最大流最小割的算法寻找那些合并后能最大程度减少“敏感边”数量的边进行收缩。面向性能约束的聚类目标是减少任务间的通信开销因为簇内通信变为零开销的片内通信以满足性能 deadline。这里引入了“时序违规图”TVG的概念它只包含那些在关键路径上或松弛时间为负的任务。同样使用最大流最小割算法但边的容量capacity定义为将这条边对应的通信从“核间通信”变为“核内通信”所能节省的延迟。算法会迭代地切割TVG直到预估的调度长度满足虚拟性能约束。我实现时最大的体会是这两种聚类目标经常是冲突的。为了性能而合并任务可能会意外地在VVG中创建新的敏感边加剧供应商约束的满足难度反之为了安全而拆分任务簇又会增加通信开销损害性能。论文的算法7TSP采用了一个外层的迭代循环来调和这个矛盾先按性能目标聚类再检查供应商约束如果违反则收紧性能约束让虚拟 deadline 更紧重新聚类如此往复。这实际上是一个在“安全-性能”帕累托前沿上的搜索过程。4. 资源约束下的调度算法实现与调优资源约束调度TSR是基础。它的输入是任务图、每个供应商可用的核心数CORE以及供应商数量约束λ。目标是输出一个满足安全约束的调度表且调度长度最短。4.1 算法流程拆解算法4TSR是一个列表调度框架但每个调度决策都渗透着安全考量初始化进行供应商约束的任务聚类构建初始的VVG。为每个任务簇ci初始化候选供应商集合clr(ci)为所有供应商。调度循环当存在未调度的任务时 a.确定候选供应商对于当前待调度任务vj所在簇ci调用clr_dtm算法即前述的算法2根据最新的VVG状态计算出ci当前真正可用的供应商集合clr(ci)。 b.确定可用核心core(vj)是来自clr(ci)中所有供应商的、当前空闲的核心集合。 c.选择核心采用最早完成时间优先EFT策略将vj调度到core(vj)中能使vj最早完成的核心上。其复制任务v‘j以同样方式调度但必须从不同于vj供应商的核心中选择。 d.更新图状态任务被调度后其所在簇ci被正式分配给某个供应商colork。调用CQ_Update算法算法3更新VVG中所有与ci有敏感边相连的节点的团大小。4.2 关键实现细节与坑1. 核心选择策略的陷阱单纯的EFT策略在安全约束下可能不是最优。比如有两个核心都能让任务最早完成一个来自供应商A一个来自供应商B。如果选择A可能会导致后续某个关键任务因为供应商约束无法使用A而被迫推迟选择B则不会。因此我改进了核心选择函数引入了一个简单的“前瞻代价”估计。在选择核心时不仅看当前任务的完成时间还快速评估一下这个选择对后续直接后继任务的候选供应商集合的影响选择一个“代价”较小的。这虽然增加了单次调度的计算量但整体上能得到更短的调度长度。2. 团大小更新的优化算法3CQ_Update是串行更新每个敏感节点cj的团大小。在最坏情况下一个任务簇可能与许多敏感节点相连导致更新成本高。我观察到团大小的增加具有“局部性”。一个节点团大小的增加通常只发生在其邻居节点也被分配了相同供应商从而形成了一个更大的团。因此在实现中我维护了一个“待更新队列”。当ci被着色后我只将其直接邻居中的敏感节点加入队列。然后处理队列如果一个节点cj的团大小更新了我再将cj的邻居且与ci也相邻加入队列。这种类似BFS的传播方式在大多数情况下比遍历所有敏感节点要快得多。3. 处理无解情况在严格资源约束下可能不存在满足所有安全约束的调度方案。算法需要能优雅地处理这种情况。我的实现中当clr_dtm算法发现某个任务簇ci的候选供应商集合为空时不会直接报错退出而是触发一个“松弛”机制。例如可以记录下这个冲突暂时允许ci与其冲突最少的邻居共享供应商即违反一条安全约束并记录这次违规的代价。然后继续调度。最终算法可以输出一个调度方案以及所违反的安全约束列表和总代价供设计者权衡。这比直接失败更有实用价值。5. 性能约束下的调度算法实现与折衷性能约束调度TSP更复杂它是一个迭代优化过程目标是在满足给定调度长度pc的前提下最小化核心使用量和安全约束违反数量。5.1 迭代优化框架解析算法7TSP的流程体现了典型的约束驱动设计思想设定虚拟性能约束初始的虚拟性能约束pc_v设为实际约束pc。迭代聚类与供应商分配 a. 基于当前的pc_v执行性能约束聚类Task_Clusterp合并任务以减少通信开销。 b. 执行供应商约束聚类Task_Clusterv合并任务以减少所需供应商数量。 c. 执行供应商分配Vendor算法6将任务簇分配给具体供应商。此时每个任务的实际执行时间因供应商核心速度不同才能确定。 d. 计算实际调度长度sl。如果sl pc违反实际性能约束则计算超出量σ令pc_v pc_v - σ进入下一轮迭代。这意味着上一轮为了性能而做的聚类还不够“激进”需要设定更紧的虚拟约束来驱动更多的任务合并。最终调度当实际调度长度满足约束后使用力导向调度Force-Directed Scheduling将任务分配到具体的时间段和核心上以实现资源的均衡利用。5.2 供应商分配策略的精髓算法6Vendor Assignment是性能约束调度的核心之一。它的巧妙之处在于区分了“关键任务簇”和“非关键任务簇”。对于包含时序关键任务的簇将其分配给当前“关键计算量”colork.cri最大的供应商。里的cri累计了分配给该供应商的所有关键任务的计算量。这实际上是一种贪心策略试图让最快的核心去承担最紧急的任务从而有利于满足性能约束。对于不包含时序关键任务的簇将其分配给当前总计算负载colork.sum最小的供应商。这是一种负载均衡策略避免某些供应商过早被占满。在实现中“时序关键任务”的判断基于任务在 ASAP 和 ALAP 调度下的松弛时间slack。我将松弛时间小于某个阈值例如总调度长度的5%的任务标记为关键。这个阈值是个可调参数设置得太小可能无法有效区分设置得太大则会导致太多任务被标记为关键削弱了负载均衡的效果需要根据具体任务图进行微调。5.3 力导向调度的安全适配传统的力导向调度用于平衡资源利用率将操作均匀分布到各个控制步骤。在安全感知的语境下我们需要为每个供应商单独维护一个资源分布图。因为不同供应商的核心是独立的资源池。调度时对于一个任务vi及其副本v‘i我们需要分别从它们所属供应商的资源分布图中寻找“力”最小的那个时间周期进行绑定。这里的“力”可以理解为该时间段内该供应商核心的拥挤程度。这保证了调度结果在时间维度上是均衡的同时严格遵守了供应商隔离约束。避坑指南迭代收敛与初始值TSP算法的外层迭代可能不收敛或者在收敛前需要很多轮迭代。我遇到的主要问题是pc_v的调整步长。如果直接将σ实际超出量作为减少量有时会过于激进导致虚拟约束pc_v一下子变得太紧下一轮聚类过度反而损害了安全性需要更多轮次来回调。一个更稳定的策略是使用比例-积分PI控制器思想pc_v pc_v - α * σ - β * Σσ其中α和β是小的正系数Σσ是历史超出量的累积。这能 smoother 地调整虚拟约束加快收敛。通常设置α0.8,β0.05能取得不错的效果。6. 实验验证、参数影响与工程化思考任何算法的价值都需要通过实验来验证。我参照论文的思路使用标准任务图基准如Robot Control, Sparse Matrix Solver等进行了测试同时也生成了一些随机任务图以测试算法的可扩展性。6.1 核心发现与数据解读资源约束调度TSR的优势与将供应商分配和任务调度分步进行的朴素方法相比TSR通过联合优化平均能减少28%左右的调度长度。这印证了安全约束与调度决策耦合优化的必要性。代价是运行时间增加了约一个数量级但对于设计空间探索DSE阶段来说这个时间是完全可以接受的。供应商约束聚类的有效性当供应商数量λ被限制为2时即只能使用两个供应商论文提出的供应商约束聚类方法TCv相比简单的基于团的聚类方法能将安全约束违反率从平均1.99%降低到1.34%。这意味着在严格的成本限制下我们的方法能以更小的安全代价满足设计需求。性能约束调度TSP的权衡在满足给定性能和供应商约束的前提下TSP方法平均只需要违反约3.21%的安全约束同时比对比方法节省了18%的核心数量。这完美体现了其在“性能-安全-面积成本”三维空间中进行有效折衷的能力。6.2 关键参数的影响与调参经验通信计算比CCR这是任务图固有的一个关键参数。CCR越高通信开销占比越大。实验表明CCR越高性能约束聚类TCp带来的收益减少的安全约束违反越明显。因为高CCR下通过聚类减少通信对满足性能目标至关重要。供应商核心速度差异论文假设不同供应商核心速度呈阶梯差异如10%。在实际中这个差异可能更大或不规则。我的测试发现核心速度差异越大供应商分配算法Algorithm 6中“将关键任务分配给最快核心”的策略效果越显著。如果所有核心速度相同该策略则退化为随机分配。虚拟性能约束pc_v的初始值不要简单地设为实际约束pc。一个更好的策略是先用一个不考虑安全约束的快速调度算法如简单的列表调度得到一个粗略的调度长度sl_init然后设pc_v γ * min(pc, sl_init)其中γ是一个略小于1的因子如0.9。这为迭代优化提供了一个更好的起点能减少迭代次数。6.3 从算法到工程的挑战将论文算法转化为实际可用的工具还面临一些工程挑战可扩展性对于超大规模任务图数千个节点VVG的构建和团大小的动态维护会成为瓶颈。我采用的方法是层次化聚类先对任务进行粗粒度聚类在簇间应用安全约束调度算法然后在每个簇内部再进行细粒度的、不考虑安全约束的调度因为簇内任务共享供应商。这大大降低了问题规模。与现有HLS流程集成安全感知调度应该作为高层次综合HLS前端的一个优化pass。这意味着需要从C/C/SystemC代码中提取任务图包含计算量、通信量估计。我通常借助LLVM/Clang的编译器中间表示IR来分析控制流和数据流自动生成任务图并将最终的调度和绑定结果反馈回HLS工具指导RTL生成。多目标优化安全、性能、面积核心数、功耗都是需要权衡的目标。本文算法主要关注安全-性能-面积的权衡。在实际项目中我通常将其扩展为一个多目标优化问题使用诸如NSGA-II之类的进化算法在外层驱动调度算法产生一组帕累托最优解供架构师选择。7. 总结与展望安全感知的任务调度不再是学术上的概念而是构建可信赖异构计算系统的必由之路。通过供应商多样性和任务复制引入的硬件安全约束彻底改变了传统调度问题的格局。N. Wang等人的这项工作通过引入供应商违规图VVG和团大小这一核心概念将复杂的安全约束转化为可计算的图属性并巧妙地与最大流最小割、列表调度、力导向调度等经典算法结合给出了一个系统性的解决方案。从我实际的实现和应用经验来看这套算法的优势在于其坚实的理论基础和良好的可扩展性。它没有试图用一个超级复杂的模型一次性解决所有问题而是通过分解问题先聚类再调度迭代优化、动态维护关键信息团大小、以及巧妙的启发式策略如区分关键任务进行供应商分配在可接受的时间内找到了高质量的次优解。当然没有银弹。这套方法假设硬件木马的触发依赖于特定的供应商并且任务复制和比对机制是完美的。在实际系统中还需要考虑比较器本身的可信度、侧信道攻击等更广泛的安全威胁。此外算法目前主要处理静态任务图对于动态负载变化的情景还需要研究运行时Runtime的调度和迁移策略。对我而言实现这个算法的过程是一次将形式化安全模型与经典EDA算法深度融合的宝贵实践。它让我深刻体会到在“后摩尔时代”芯片设计的挑战不仅来自物理和工艺更来自系统与安全。作为工程师我们需要不断吸收像这样的跨领域研究成果并将其打磨成稳定、高效的工程实现才能真正为设计出既高性能又高可靠的芯片贡献力量。如果你正在面临类似的设计挑战不妨从构建你的第一个VVG开始亲手实现一下团大小的动态更新算法相信你会对“安全约束”更具体、更深刻的认识。
安全感知任务调度：基于供应商违规图与团大小动态更新的异构系统设计
发布时间：2026/5/27 14:05:13
1. 项目概述当任务调度遇上硬件安全在芯片设计尤其是异构多处理器系统MPSoC设计领域我们一直在性能、功耗和面积这个“铁三角”之间做权衡。但随着供应链全球化一个过去被相对忽视的维度——硬件安全正变得前所未有的重要。你设计的芯片可能性能卓越、能效出众但如果其中某个由第三方提供的处理器核心3PIP被植入了硬件木马Hardware Trojan那么整个系统在特定条件下就可能被触发导致功能错误、信息泄露甚至完全失效。这不是危言耸听而是摆在所有系统架构师和芯片设计者面前的现实挑战。传统的“信任但验证”思路在复杂的第三方IP核面前往往力不从心。于是学术界和工业界提出了“供应商多样性”Vendor Diversity和“任务复制”Task Duplication这两种架构级的安全增强策略。简单来说就是不把鸡蛋放在一个篮子里关键的计算任务被复制成两份并由来自不同供应商的、功能等效但实现不同的处理器核心来执行只有两份结果一致时才被采纳。这能有效防范针对单一供应商的特定硬件木马攻击。然而安全不是免费的午餐。引入供应商多样性和任务复制相当于给原本的任务调度问题套上了一层复杂的“紧箍咒”。调度器不仅要考虑任务间的依赖关系、通信开销和资源竞争还必须遵守一系列安全约束比如两个存在数据依赖的敏感任务不能分配给同一个供应商以防该供应商的硬件木马同时污染这两个任务。这直接导致调度问题的解空间爆炸式增长传统的列表调度List Scheduling或力导向调度Force-Directed Scheduling算法难以直接应用。我最近深入研究了N. Wang等人在2018年发表的一篇论文《Security-Aware Task Scheduling Using Untrusted Components in High-Level Synthesis》并基于其核心思想进行了一系列的算法实现与工程化探索。这篇博文我将以一个一线工程师的视角为你拆解这个“基于安全约束的高层次综合任务调度算法”的核心原理、实现细节以及在实际应用中可能遇到的坑和应对技巧。无论你是正在研究安全关键系统设计的学者还是面临如何将安全需求落地的芯片开发者相信这些从论文到代码的实战经验都能给你带来启发。2. 核心安全约束与问题建模在深入算法之前我们必须先把问题定义清楚。安全感知调度不是在传统调度目标上简单加个“安全标签”而是从根本上改变了问题的约束条件和优化目标。2.1 安全约束的形式化从直觉到图论供应商多样性和任务复制带来的核心安全约束可以这样理解系统中有多个来自不同供应商的处理器核心。每个计算任务Task都有一个原始的“主版本”和一个用于比对的“复制版本”。这两个版本必须被调度到来自不同供应商的核心上执行。更进一步如果两个任务之间存在数据依赖即一个任务的输出是另一个任务的输入并且它们都被判定为“敏感任务”那么这两个任务包括它们的主版本和复制版本也不能被分配到同一个供应商的核心上。这是为了防止一个“恶意”供应商的核心通过数据流连续污染多个敏感任务从而绕过基于结果比对的检测机制。如何形式化地描述这些约束论文引入了供应商违规图Vendor Violation Graph, VVG这一核心概念。这是一个无向图其中每个节点代表一个任务簇Cluster由多个可合并的任务组成。如果两个任务簇不能被分配到同一个供应商即违反供应商多样性约束那么它们之间就存在一条边称为“敏感边”。这里的关键是“团”Clique的概念。在图论中团是一个图的完全子图即其中任意两个节点之间都有边相连。在VVG中如果一个团的大小即包含的节点数为 λ那么这意味着这个团里所有的 λ 个任务簇都两两不能共用供应商。因此要满足安全约束我们至少需要 λ 个不同的供应商来为这个团中的任务簇提供服务。这个 λ 就被定义为该任务簇的团大小它是调度算法中一个至关重要的动态属性。2.2 两类核心调度问题基于上述模型论文主要解决了两类问题这也是我们工程实践中常遇到的两类场景1. 资源约束下的任务调度给定固定数量的处理器核心资源和供应商数量λ目标是找到一个任务调度方案在满足所有安全约束的前提下最小化整个应用的调度长度Schedule Length也就是总的执行时间。这对应着成本核心数量固定的情况我们要尽可能跑得快。2. 性能约束下的任务调度给定一个性能目标即最大的允许调度长度和供应商数量约束λ目标是找到一个任务调度方案在满足性能目标的前提下最小化所需的核心数量同时尽可能少地违反安全约束因为有时在严格约束下可能无解。这对应着工期固定的情况我们要用最少的资源完成任务并权衡安全损失。无论是哪类问题其核心难点都在于安全约束体现在VVG的团结构上与调度决策任务在何时、何核心上执行强烈耦合。为一个任务分配供应商着色会改变其邻居任务在VVG中的团大小进而影响它们未来的可分配供应商集合。这是一个典型的NP难问题需要精巧的启发式算法。3. 算法基石供应商违规图VVG的动态维护整个调度算法的智能很大程度上体现在对VVG的实时、动态维护上。这不是一个静态的图而是一个随着调度决策不断演化的结构。3.1 团大小的计算与更新计算一个任务簇ci的团大小ω(ci)并不是简单地计算它在VVG中的最大团。论文的核心洞见在于我们只关心与ci通过敏感边相连的那些“敏感节点”构成的子图VVG‘_s(ci)。ci的团大小等于在VVG‘_s(ci)中能找到的最大团的大小。算法2Candidate Color Set Determination是动态维护的关键。它的目的是确定当前可以分配给任务簇ci的候选供应商集合clr(ci)。其逻辑是遍历所有可能的供应商颜色。对于每个供应商colork我们检查如果将ci分配给colork是否会违反安全约束。检查的方法是在VVG‘_s(ci)中移除所有当前团大小已经小于 λ 的节点因为它们不构成约束然后检查剩下的子图中是否存在至少 λ 个节点它们的度数都大于等于 λ-1。如果存在说明这个子图包含一个大小为 λ 的团那么当前供应商colork就不能分配给ci需要从候选集中移除。这个过程我最初实现时在“检查是否存在 λ-clique”这里遇到了性能瓶颈。穷举所有子图找最大团是指数级的。论文巧妙地用了度数条件作为启发式判断在一个包含 n 个节点的图中如果存在一个大小为 k 的团那么这 k 个节点的度数至少是 k-1。这是一个必要但不充分条件。在实际编码中我采用了一种更保守但更高效的方法维护一个“潜在团大小”的估计值并结合贪心搜索来验证。虽然可能略微多排除一些本可用的供应商但换来了算法运行时间的大幅下降在工程上是值得的。实操心得度数的动态更新VVG节点的度数是动态变化的。当两个任务簇因为调度决策被合并聚类时它们对应的节点在VVG中也会合并其度数需要重新计算。这里极易出错。我的经验是为VVG维护一个邻接表并在每次图结构变更节点删除、合并、边添加/删除时增量式地更新受影响节点的度数而不是全量重新计算。这能有效提升算法在迭代调度过程中的效率。3.2 任务聚类平衡安全与性能直接对原始任务图进行调度复杂度太高。因此算法先进行任务聚类将多个任务合并成一个更大的“超级任务”即任务簇从而减少调度实体的数量。这里有两条聚类路径面向供应商约束的聚类目标是减少最终VVG中的节点数从而降低满足供应商多样性所需的供应商数量。其核心是合并那些在任务图中相连但在VVG中不相连即可以共享供应商的任务。这通常使用基于最大流最小割的算法寻找那些合并后能最大程度减少“敏感边”数量的边进行收缩。面向性能约束的聚类目标是减少任务间的通信开销因为簇内通信变为零开销的片内通信以满足性能 deadline。这里引入了“时序违规图”TVG的概念它只包含那些在关键路径上或松弛时间为负的任务。同样使用最大流最小割算法但边的容量capacity定义为将这条边对应的通信从“核间通信”变为“核内通信”所能节省的延迟。算法会迭代地切割TVG直到预估的调度长度满足虚拟性能约束。我实现时最大的体会是这两种聚类目标经常是冲突的。为了性能而合并任务可能会意外地在VVG中创建新的敏感边加剧供应商约束的满足难度反之为了安全而拆分任务簇又会增加通信开销损害性能。论文的算法7TSP采用了一个外层的迭代循环来调和这个矛盾先按性能目标聚类再检查供应商约束如果违反则收紧性能约束让虚拟 deadline 更紧重新聚类如此往复。这实际上是一个在“安全-性能”帕累托前沿上的搜索过程。4. 资源约束下的调度算法实现与调优资源约束调度TSR是基础。它的输入是任务图、每个供应商可用的核心数CORE以及供应商数量约束λ。目标是输出一个满足安全约束的调度表且调度长度最短。4.1 算法流程拆解算法4TSR是一个列表调度框架但每个调度决策都渗透着安全考量初始化进行供应商约束的任务聚类构建初始的VVG。为每个任务簇ci初始化候选供应商集合clr(ci)为所有供应商。调度循环当存在未调度的任务时 a.确定候选供应商对于当前待调度任务vj所在簇ci调用clr_dtm算法即前述的算法2根据最新的VVG状态计算出ci当前真正可用的供应商集合clr(ci)。 b.确定可用核心core(vj)是来自clr(ci)中所有供应商的、当前空闲的核心集合。 c.选择核心采用最早完成时间优先EFT策略将vj调度到core(vj)中能使vj最早完成的核心上。其复制任务v‘j以同样方式调度但必须从不同于vj供应商的核心中选择。 d.更新图状态任务被调度后其所在簇ci被正式分配给某个供应商colork。调用CQ_Update算法算法3更新VVG中所有与ci有敏感边相连的节点的团大小。4.2 关键实现细节与坑1. 核心选择策略的陷阱单纯的EFT策略在安全约束下可能不是最优。比如有两个核心都能让任务最早完成一个来自供应商A一个来自供应商B。如果选择A可能会导致后续某个关键任务因为供应商约束无法使用A而被迫推迟选择B则不会。因此我改进了核心选择函数引入了一个简单的“前瞻代价”估计。在选择核心时不仅看当前任务的完成时间还快速评估一下这个选择对后续直接后继任务的候选供应商集合的影响选择一个“代价”较小的。这虽然增加了单次调度的计算量但整体上能得到更短的调度长度。2. 团大小更新的优化算法3CQ_Update是串行更新每个敏感节点cj的团大小。在最坏情况下一个任务簇可能与许多敏感节点相连导致更新成本高。我观察到团大小的增加具有“局部性”。一个节点团大小的增加通常只发生在其邻居节点也被分配了相同供应商从而形成了一个更大的团。因此在实现中我维护了一个“待更新队列”。当ci被着色后我只将其直接邻居中的敏感节点加入队列。然后处理队列如果一个节点cj的团大小更新了我再将cj的邻居且与ci也相邻加入队列。这种类似BFS的传播方式在大多数情况下比遍历所有敏感节点要快得多。3. 处理无解情况在严格资源约束下可能不存在满足所有安全约束的调度方案。算法需要能优雅地处理这种情况。我的实现中当clr_dtm算法发现某个任务簇ci的候选供应商集合为空时不会直接报错退出而是触发一个“松弛”机制。例如可以记录下这个冲突暂时允许ci与其冲突最少的邻居共享供应商即违反一条安全约束并记录这次违规的代价。然后继续调度。最终算法可以输出一个调度方案以及所违反的安全约束列表和总代价供设计者权衡。这比直接失败更有实用价值。5. 性能约束下的调度算法实现与折衷性能约束调度TSP更复杂它是一个迭代优化过程目标是在满足给定调度长度pc的前提下最小化核心使用量和安全约束违反数量。5.1 迭代优化框架解析算法7TSP的流程体现了典型的约束驱动设计思想设定虚拟性能约束初始的虚拟性能约束pc_v设为实际约束pc。迭代聚类与供应商分配 a. 基于当前的pc_v执行性能约束聚类Task_Clusterp合并任务以减少通信开销。 b. 执行供应商约束聚类Task_Clusterv合并任务以减少所需供应商数量。 c. 执行供应商分配Vendor算法6将任务簇分配给具体供应商。此时每个任务的实际执行时间因供应商核心速度不同才能确定。 d. 计算实际调度长度sl。如果sl pc违反实际性能约束则计算超出量σ令pc_v pc_v - σ进入下一轮迭代。这意味着上一轮为了性能而做的聚类还不够“激进”需要设定更紧的虚拟约束来驱动更多的任务合并。最终调度当实际调度长度满足约束后使用力导向调度Force-Directed Scheduling将任务分配到具体的时间段和核心上以实现资源的均衡利用。5.2 供应商分配策略的精髓算法6Vendor Assignment是性能约束调度的核心之一。它的巧妙之处在于区分了“关键任务簇”和“非关键任务簇”。对于包含时序关键任务的簇将其分配给当前“关键计算量”colork.cri最大的供应商。里的cri累计了分配给该供应商的所有关键任务的计算量。这实际上是一种贪心策略试图让最快的核心去承担最紧急的任务从而有利于满足性能约束。对于不包含时序关键任务的簇将其分配给当前总计算负载colork.sum最小的供应商。这是一种负载均衡策略避免某些供应商过早被占满。在实现中“时序关键任务”的判断基于任务在 ASAP 和 ALAP 调度下的松弛时间slack。我将松弛时间小于某个阈值例如总调度长度的5%的任务标记为关键。这个阈值是个可调参数设置得太小可能无法有效区分设置得太大则会导致太多任务被标记为关键削弱了负载均衡的效果需要根据具体任务图进行微调。5.3 力导向调度的安全适配传统的力导向调度用于平衡资源利用率将操作均匀分布到各个控制步骤。在安全感知的语境下我们需要为每个供应商单独维护一个资源分布图。因为不同供应商的核心是独立的资源池。调度时对于一个任务vi及其副本v‘i我们需要分别从它们所属供应商的资源分布图中寻找“力”最小的那个时间周期进行绑定。这里的“力”可以理解为该时间段内该供应商核心的拥挤程度。这保证了调度结果在时间维度上是均衡的同时严格遵守了供应商隔离约束。避坑指南迭代收敛与初始值TSP算法的外层迭代可能不收敛或者在收敛前需要很多轮迭代。我遇到的主要问题是pc_v的调整步长。如果直接将σ实际超出量作为减少量有时会过于激进导致虚拟约束pc_v一下子变得太紧下一轮聚类过度反而损害了安全性需要更多轮次来回调。一个更稳定的策略是使用比例-积分PI控制器思想pc_v pc_v - α * σ - β * Σσ其中α和β是小的正系数Σσ是历史超出量的累积。这能 smoother 地调整虚拟约束加快收敛。通常设置α0.8,β0.05能取得不错的效果。6. 实验验证、参数影响与工程化思考任何算法的价值都需要通过实验来验证。我参照论文的思路使用标准任务图基准如Robot Control, Sparse Matrix Solver等进行了测试同时也生成了一些随机任务图以测试算法的可扩展性。6.1 核心发现与数据解读资源约束调度TSR的优势与将供应商分配和任务调度分步进行的朴素方法相比TSR通过联合优化平均能减少28%左右的调度长度。这印证了安全约束与调度决策耦合优化的必要性。代价是运行时间增加了约一个数量级但对于设计空间探索DSE阶段来说这个时间是完全可以接受的。供应商约束聚类的有效性当供应商数量λ被限制为2时即只能使用两个供应商论文提出的供应商约束聚类方法TCv相比简单的基于团的聚类方法能将安全约束违反率从平均1.99%降低到1.34%。这意味着在严格的成本限制下我们的方法能以更小的安全代价满足设计需求。性能约束调度TSP的权衡在满足给定性能和供应商约束的前提下TSP方法平均只需要违反约3.21%的安全约束同时比对比方法节省了18%的核心数量。这完美体现了其在“性能-安全-面积成本”三维空间中进行有效折衷的能力。6.2 关键参数的影响与调参经验通信计算比CCR这是任务图固有的一个关键参数。CCR越高通信开销占比越大。实验表明CCR越高性能约束聚类TCp带来的收益减少的安全约束违反越明显。因为高CCR下通过聚类减少通信对满足性能目标至关重要。供应商核心速度差异论文假设不同供应商核心速度呈阶梯差异如10%。在实际中这个差异可能更大或不规则。我的测试发现核心速度差异越大供应商分配算法Algorithm 6中“将关键任务分配给最快核心”的策略效果越显著。如果所有核心速度相同该策略则退化为随机分配。虚拟性能约束pc_v的初始值不要简单地设为实际约束pc。一个更好的策略是先用一个不考虑安全约束的快速调度算法如简单的列表调度得到一个粗略的调度长度sl_init然后设pc_v γ * min(pc, sl_init)其中γ是一个略小于1的因子如0.9。这为迭代优化提供了一个更好的起点能减少迭代次数。6.3 从算法到工程的挑战将论文算法转化为实际可用的工具还面临一些工程挑战可扩展性对于超大规模任务图数千个节点VVG的构建和团大小的动态维护会成为瓶颈。我采用的方法是层次化聚类先对任务进行粗粒度聚类在簇间应用安全约束调度算法然后在每个簇内部再进行细粒度的、不考虑安全约束的调度因为簇内任务共享供应商。这大大降低了问题规模。与现有HLS流程集成安全感知调度应该作为高层次综合HLS前端的一个优化pass。这意味着需要从C/C/SystemC代码中提取任务图包含计算量、通信量估计。我通常借助LLVM/Clang的编译器中间表示IR来分析控制流和数据流自动生成任务图并将最终的调度和绑定结果反馈回HLS工具指导RTL生成。多目标优化安全、性能、面积核心数、功耗都是需要权衡的目标。本文算法主要关注安全-性能-面积的权衡。在实际项目中我通常将其扩展为一个多目标优化问题使用诸如NSGA-II之类的进化算法在外层驱动调度算法产生一组帕累托最优解供架构师选择。7. 总结与展望安全感知的任务调度不再是学术上的概念而是构建可信赖异构计算系统的必由之路。通过供应商多样性和任务复制引入的硬件安全约束彻底改变了传统调度问题的格局。N. Wang等人的这项工作通过引入供应商违规图VVG和团大小这一核心概念将复杂的安全约束转化为可计算的图属性并巧妙地与最大流最小割、列表调度、力导向调度等经典算法结合给出了一个系统性的解决方案。从我实际的实现和应用经验来看这套算法的优势在于其坚实的理论基础和良好的可扩展性。它没有试图用一个超级复杂的模型一次性解决所有问题而是通过分解问题先聚类再调度迭代优化、动态维护关键信息团大小、以及巧妙的启发式策略如区分关键任务进行供应商分配在可接受的时间内找到了高质量的次优解。当然没有银弹。这套方法假设硬件木马的触发依赖于特定的供应商并且任务复制和比对机制是完美的。在实际系统中还需要考虑比较器本身的可信度、侧信道攻击等更广泛的安全威胁。此外算法目前主要处理静态任务图对于动态负载变化的情景还需要研究运行时Runtime的调度和迁移策略。对我而言实现这个算法的过程是一次将形式化安全模型与经典EDA算法深度融合的宝贵实践。它让我深刻体会到在“后摩尔时代”芯片设计的挑战不仅来自物理和工艺更来自系统与安全。作为工程师我们需要不断吸收像这样的跨领域研究成果并将其打磨成稳定、高效的工程实现才能真正为设计出既高性能又高可靠的芯片贡献力量。如果你正在面临类似的设计挑战不妨从构建你的第一个VVG开始亲手实现一下团大小的动态更新算法相信你会对“安全约束”更具体、更深刻的认识。
