1. 项目概述当芯片设计遇上“不可信”的第三方组件在今天的芯片设计领域尤其是复杂异构多处理器片上系统MPSoC的开发中有一个既普遍又棘手的问题我们几乎不可避免地要使用第三方知识产权核3PIP。这就像盖一栋摩天大楼你不可能从烧砖、炼钢开始所有工序都自己来。为了追赶市场节奏、控制成本设计师们会大量采购现成的“功能模块”比如某个特定算法的硬件加速器、标准的内存控制器或者通信接口。然而这些“采购”来的模块其内部对我们而言是一个黑盒。你无法百分之百信任提供这些模块的供应商——不是质疑他们的商业信誉而是在复杂的全球供应链中任何一个环节都可能被植入恶意逻辑也就是我们常说的“硬件木马”。硬件木马的威胁是真实且严重的。想象一下在一个处理金融交易或控制关键基础设施的芯片里某个来自第三方供应商的计时器模块可能在特定条件下通过一个隐秘的通信通道激活另一个来自同一供应商的总线控制器中的恶意代码导致整个系统总线瘫痪。这种协同攻击单靠检测单个模块的输出是否正确是很难发现的。传统的“任务复制”安全策略让同一个任务在不同供应商的核上运行并比对结果可以应对输出篡改却无法切断这种模块间的秘密通信。因此安全感知的任务调度技术应运而生。它的核心思想非常巧妙既然无法确保每个3PIP都是干净的那就在系统架构层面通过智能的任务编排将来自同一供应商的、可能“串通”的组件隔离开。具体来说就是在高层次综合HLS阶段将一个应用程序分解成多个任务Task并在将这些任务映射到具体的硬件处理核Core上执行时施加两类安全约束任务复制同一任务需在不同供应商的核上执行和供应商多样性有数据依赖关系的相邻任务必须分配到不同供应商的核上执行。前者用于结果校验后者用于隔离风险。但安全不是免费的午餐。这些约束会带来显著的性能开销调度长度变长和成本开销需要更多不同供应商的核即设计成本需要更多硬件核即面积成本。我们面临的是一个典型的多目标优化难题如何在给定的资源核的数量约束或性能最晚完成时间约束下设计出安全违规最少、调度效率最高的任务调度方案这正是本文要深入探讨的核心。我将结合论文中的思路为你拆解其中的算法逻辑、实现难点并分享在实际工程化中可能遇到的“坑”和应对技巧。2. 核心安全威胁与防御架构解析在深入调度算法之前我们必须彻底理解我们防御的敌人是什么以及我们构建的“城墙”是如何工作的。这有助于理解后续所有优化决策背后的根本原因。2.1 硬件木马的攻击模式从单点失效到协同作案早期的硬件安全威胁模型相对简单主要关注单个IP核内部可能存在的、独立激活的恶意逻辑。例如一个被植入木马的加密协处理器可能在遇到特定输入模式时泄露密钥。针对这种威胁任务复制Task Duplication是一种有效的防御手段。其原理是将同一个计算任务例如一个FFT运算分配给两个来自不同供应商的、功能相同的IP核例如供应商A的DSP核和供应商B的DSP核并行执行。由于不同供应商的实现方式、内部状态机乃至晶体管级电路都不同同一个硬件木马被同时植入两个独立设计核的概率极低。因此通过一个可信的比较器通常由设计方自己实现比对两个核的输出结果一旦不一致就能触发安全警报从而检测到输出篡改类攻击。然而攻击者的手段也在进化。更隐蔽、危害更大的是一种分布式、协同式的攻击。攻击者可能将木马的“触发器”和“负载”分别植入两个来自同一供应商的不同IP核中。在系统正常运行时这两个核通过设计者未知的、隐秘的通信路径例如利用共享总线上的特定时序、预留的测试接口或未公开的寄存器进行通信。当承载“触发器”的核满足某个罕见条件时它会通过秘密通道发送一个激活信号唤醒另一个核中的“负载”木马从而发起拒绝服务、信息泄露或更复杂的攻击。注意这种协同攻击之所以危险是因为单个核在独立测试或执行“任务复制”校验时其行为可能是完全正常的。只有当他们被部署在同一个系统中并且按照特定的顺序和依赖关系执行时攻击链才会被触发。这使得传统的、针对单个IP的检测方法如形式化验证、代码覆盖率分析几乎失效。2.2 安全约束构建系统级的动态隔离区为了应对协同攻击论文引入了供应商多样性Vendor Diversity约束。其规则直观而有力任何两个在任务图中直接相连即存在数据依赖关系的任务不能被调度到来自同一供应商的硬件核上执行。这个约束的威力在于它从数据流的角度切断了潜在恶意IP核之间建立稳定、可预测通信路径的可能性。回到之前的例子如果任务A父任务和任务B子任务必须由不同供应商的核执行那么即使供应商X的核A中包含了“触发器”供应商X的核B中包含了“负载”由于任务调度结果强制它们不能相邻执行那个隐秘的、依赖于特定执行顺序和上下文的激活通道就被物理或至少是逻辑隔离了。任务复制和供应商多样性共同构成了一个立体的防御架构纵向任务层面通过复制与比对确保单个任务计算结果的正确性。横向数据流层面通过供应商隔离防止恶意逻辑沿任务依赖链传播和协同激活。这个架构将安全考量从被动的“检测与响应”前置到了主动的“设计与隔离”阶段是高层次综合中实现“设计即安全”理念的关键实践。2.3 安全开销的量化我们为安全付出了什么引入安全约束的直接代价体现在三个维度这也是我们优化算法的优化目标调度长度Schedule Length, SL即整个任务图完成所有计算所需的时间。供应商多样性约束限制了任务调度的灵活性。例如即使有两个空闲的核如果它们来自同一供应商而待调度的两个任务存在依赖关系它们也无法并行执行必须串行从而拉长整体时间。设计成本Design Cost这里模型化为所需IP供应商的数量。为了满足供应商多样性尤其是当任务图复杂、并行度高时我们可能需要采购来自多家供应商的同类IP核这增加了采购、验证和集成成本。面积/资源成本Area/Resource Cost模型化为所需硬件处理核的总数。任务复制本身就需要至少两倍的核来执行同一任务。此外为了满足多样性和并行性可能还需要更多的核来弥补因约束导致的效率下降这直接增加了芯片的硅片面积和功耗。论文中定义的两个核心优化问题正是针对资源核数固定或性能时间固定这两种最常见的工程约束场景寻求安全与效率的最优平衡点。3. 资源约束下的安全感知任务调度第一种场景是资源受限调度我们手头可用的硬件核总数是固定的面积/功耗预算已定目标是在满足供应商数量约束的前提下找到一个调度方案使得最终完成时间调度长度最短同时尽可能减少安全约束违反如果无法完全满足。3.1 问题建模与核心挑战输入包括任务图TG、供应商约束最多能用λ个不同供应商、资源约束总共只有R个核。输出是一个任务到核的映射以及执行时间表。核心矛盾在于供应商多样性要求相邻任务用不同供应商的核这倾向于使用更多供应商但资源约束限制了核的总数而每个供应商能提供的核可能也是有限的在论文的扩展问题中考虑。这可能导致“死锁”可用的核不少但因为供应商类型不合适任务无法被调度造成资源闲置和调度延迟。论文指出先前的研究如Liu等人的工作将任务调度和供应商分配分成了两个独立的步骤。先不管供应商按最快速度调度任务然后再尝试给每个任务分配供应商。这种方法忽略了“供应商分配”对“调度可行性”的实时影响可能导致如图3(b)所示的糟糕结果任务V3和V4本可并行但因都被分配到供应商3且该供应商只有一个可用核被迫串行。因此本文算法的第一个关键改进是将供应商分配与任务调度过程深度融合在决定一个任务何时在哪个核上执行的同时就为其决定由哪个供应商的核来执行。3.2 算法核心供应商冲突图与最大团计算为了实现上述融合调度算法需要一种方法来快速评估如果给某个任务分配了某个供应商会不会导致后续无法满足供应商约束这里引入了供应商冲突图Vendor Violation Graph, VVG的概念。VVG的构建VVG中的每个节点代表任务图TG中的一个任务簇。初始时每个任务自成一个簇。如果两个任务簇中的任务在原任务图中是相邻的存在数据依赖那么在VVG中这两个节点之间就有一条边。这条边代表一条供应商多样性约束这两个簇必须被分配到不同的供应商。理解“团”与“供应商数量”的关系 在VVG中一个“团”指的是一组节点其中任意两个节点之间都有边相连即两两互斥。这意味着这个团里的所有任务簇彼此之间都存在直接的依赖关系根据供应商多样性约束它们必须全部来自不同的供应商。 因此VVG中最大团的大小ω(VVG)就等于满足当前任务图所有多样性约束所至少需要的供应商数量。例如如果VVG中有一个包含4个节点的团那么你至少需要4家不同的供应商才能给这个团里的每个簇分配一个互不相同的供应商。算法的巧妙之处在于快速更新 当我们将两个任务簇合并即违反一次多样性约束让两个有依赖的任务共享同一个供应商的核VVG中的两个节点会收缩为一个。这可能会减少最大团的大小从而降低对供应商数量的最低要求。 论文提出不需要每次合并后都重新计算整个VVG的最大团这是一个NP难问题。由于任务图的连接通常比较稀疏每个任务只与少数任务相邻因此受一次合并操作影响的只是局部子图。算法通过计算诱导子图VVG_I(ci)包含节点ci及其所有邻居的最大团来高效更新全局最大团的估计值从而在调度过程中动态评估供应商约束的满足情况。3.3 调度流程详解与实操要点整个资源约束调度流程如图4所示是一个迭代优化过程供应商约束下的任务聚类Vendor-Constrained Task Clustering 如果初始VVG的最大团大小ω(VVG)超过了允许的供应商数量λ说明约束无法被完全满足必须违反一些多样性约束。此时需要智能地选择将哪些相邻任务聚类即分配到同一供应商的核上以最小化安全违规数scyv。算法会构建一个供应商团图VCG只包含那些位于最大团中的节点和边。然后它计算每条边的“收缩优先级”优先收缩那些能消除最多最大团、同时引入最少安全违规的边。这个过程循环直到ω(VVG) ≤ λ。候选供应商集合确定Candidate Color Set Determination 在调度每个任务时我们需要知道当前可以给它分配哪些供应商而不违反约束。这被建模为一个图着色问题每个颜色代表一个供应商。算法为每个任务簇维护一个“候选颜色集合”。当尝试给一个簇分配某种颜色时它会快速检查这个操作是否会在局部子图中产生一个大小为(λ1)的团即需要λ1个供应商。如果会则这个颜色从该簇的候选集中移除。这个检查同样利用了局部诱导子图的性质避免了全局重算效率很高。任务着色与调度Task Coloring and Scheduling 这是调度器的核心循环。采用类似列表调度的策略每次从就绪任务所有前驱任务已调度完成中选择一个任务。对于这个任务遍历其所有可用的核考虑资源和供应商候选集。对于每个核计算该任务最早可开始执行的时间。选择能使该任务最早完成的那个核并为其分配对应的供应商。这个过程实现了供应商分配与调度决策的实时联动。实操心得与注意事项优先级函数的设计在列表调度中如何对就绪任务排序论文可能使用了诸如“向上排名”等启发式方法。在实践中可以结合任务的关键路径长度、子任务数量等因素来定义优先级这对最终调度长度影响很大。“最早完成时间”计算这不仅仅是任务在某个核上的开始时间执行时间。还需要考虑核间通信开销。如果该任务的前驱任务在另一个核上执行数据需要传输时间。调度器必须维护每个核的时间线Timeline和核间通信链路的状态准确计算数据传输完成的时间。处理核资源限制每个供应商的核数量可能有限。在“候选供应商集合确定”阶段除了检查团约束还需要检查该供应商是否还有可用的核。如果没有则该供应商颜色也应从候选集中移除。4. 性能约束下的安全感知任务调度第二种场景是性能受限调度我们有一个最后期限Deadline即调度长度不能超过某个值D。目标是在满足这个性能要求的前提下最小化所需硬件核的总数同时尽可能减少安全约束违反。4.1 问题转化与核心思路当性能是硬约束时我们的思路要从“如何排布任务使时间最短”转变为“如何在给定时间内用最少的资源跑完所有任务”。一个直接的想法是将更多的任务“打包”到同一个核上执行即任务聚类这样可以节省核的数量。但聚类意味着让有依赖关系的任务在同一个核上运行这必然违反供应商多样性约束因为相邻任务用了同一个供应商的核。因此性能约束调度问题本质上是一个安全与资源的权衡我们愿意承受少安全风险违反多少条多样性约束来换取资源的节省论文的目标是在满足时间要求的前提下找到那个违反约束最少的调度方案。4.2 基于最大流最小割的关键路径聚类算法这是本算法最精彩的部分。它的直觉是想要缩短总时间必须压缩关键路径即任务图中最长的路径的长度。将关键路径上的任务聚类到同一个核上可以消除它们之间的核间通信延迟是缩短调度长度最有效的方法。但关键路径可能有多条且聚类操作会引入安全违规。如何选择聚类哪些边才能用最少的安全违规代价换取最大的时间收益论文将此建模为一个网络流问题构建流网络以任务图为蓝本构建一个流网络。其中边的容量Capacity被设置为一个与“如果收缩这条边即聚类其两端任务所能减少的调度长度估计值”相关的权重。减少时间越多的边容量越大。同时节点的容量或通过引入额外节点实现的边容量可以映射为违反安全约束的代价。求解最小割在流网络中寻找最小割。根据最大流最小割定理最小割的容量等于从源点到汇点的最大流。在这个建模下最小割所对应的边集恰恰代表了那些以最小总“代价”此处代价是安全违规的加权和将网络分割成能显著影响关键路径的两部分的边。换句话说割掉这些边在调度中即聚类这些边连接的任务能以最小的安全代价最有效地缩短整个任务图的调度长度。迭代收缩根据最小割的结果收缩相应的边进行任务聚类。然后更新任务图因为聚类产生了新的复合任务和流网络重复上述过程直到估算的调度长度满足性能约束D为止。这个方法的优势在于它通过严谨的数学规划方法系统性地在全局范围内寻找“性价比”最高的聚类操作而不是贪婪地处理单条关键路径。4.3 聚类后的供应商分配与调度完成满足性能要求的聚类后我们得到了一个“粗粒度”的任务簇集合。接下来需要解决两个问题供应商分配为每个任务簇分配一个供应商。这又回到了一个图着色问题但此时的图是聚类后的冲突图一个簇是一个节点。目标是用最少的颜色供应商使得相邻簇颜色不同满足未因聚类而消除的多样性约束。这是一个经典的图着色优化问题可以使用DSATUR等启发式算法高效求解。最终调度在确定了每个簇的供应商后问题退化为一个在资源核数已最小化和供应商约束下的普通列表调度问题。由于聚类已经大大减少了任务数量和通信开销这个调度步骤会相对快速。常见问题与排查技巧实录问题一性能约束过于严苛即使完全违反所有安全约束也无法满足。排查首先检查不考虑任何安全约束时的最短可能调度长度即无限资源、无限供应商下的理想情况。如果这个理想长度都大于D那么问题本身无解。需要与系统架构师协商放宽性能要求或考虑使用更高性能的IP核。问题二算法迭代多次后调度长度下降缓慢无法达到目标D。技巧检查流网络中边的容量权重设计。容量权重应准确反映收缩该边对全局关键路径的缩短潜力而不仅仅是局部通信延迟。一个改进方法是使用更精确的调度长度估算器如基于关键路径的静态列表调度在每次迭代后重新评估并动态更新流网络中的容量。问题三供应商分配阶段所需供应商数量仍然过多。技巧当图着色结果需要的颜色数超过可用供应商数时说明前期聚类程度不够。可以反馈到聚类阶段以“减少所需供应商数”为附加目标优先考虑收缩那些连接高度数节点的边因为给高度数节点着色需要更多颜色即使它们对缩短时间的贡献不是最大。这需要在安全违规、时间缩短和供应商数量之间进行更复杂的三方权衡。5. 工程实现考量与扩展讨论将学术算法转化为实际可用的EDA工具或设计流程的一部分还需要考虑许多工程细节。5.1 输入建模的准确性算法的有效性高度依赖于输入模型的质量任务执行时间是固定值还是范围是否考虑缓存、总线争用带来的波动在实际HLS中这通常通过综合后的静态时序分析或仿真来获取。通信延迟核间通信开销的建模至关重要。它是固定的还是与数据量、网络拓扑、拥塞情况相关论文中假设了固定值但实际中可能需要更精细的片上网络NoC模型。供应商可信度模型论文假设所有第三方供应商同等不可信。现实中我们可能对某些经过认证的供应商有更高的信任度或者知道某些供应商的IP核存在特定类型的已知漏洞。这可以引入“供应商风险权重”在优化目标中违反涉及高风险供应商的约束代价更高。5.2 多目标优化的权衡系数论文的目标函数如公式1中的 α1 * scyv SL中α1是一个很大的常数确保优先最小化安全违规。但在实际工程中这个系数需要仔细设定。如果α1设置得过大算法会不惜一切代价避免违规可能导致调度长度急剧恶化即使只违反一条无关紧要的约束就能换来显著性能提升。如果α1设置得过小算法可能会为了微小的性能提升而引入大量安全违规。 一个更实用的方法是采用帕累托前沿Pareto Front分析。运行算法多次每次调整安全与性能的权重得到一组“非支配”解即无法在不让另一个目标变差的情况下改进一个目标。让设计师从这个解集中根据项目具体需求进行选择。5.3 与现有HLS/MPSoC设计流程的集成安全感知调度不应是一个孤立的工具而应嵌入现有设计流程输入阶段从高级别语言如C/C或模型如Simulink编译得到任务图TG。调度阶段集成本文算法接受资源、性能、供应商约束作为设计约束。输出阶段生成的任务-核-供应商绑定关系以及调度表应能向下传递到硬件综合指导每个处理核的RTL生成或选择从对应的供应商IP库中。通信综合根据任务间的数据依赖和调度时序生成片上网络NoC或总线架构。软件生成生成在目标MPSoC上运行的操作系统任务或裸机代码框架实现调度表。5.4 应对动态与不确定性论文研究的是静态调度。在实际系统中任务执行时间可能因输入数据而异或者系统需要处理动态到达的任务。静态调度基础本文的算法可以作为基线静态调度方案为每个任务分配固定的核和供应商。动态调整在此基础上可以设计一个轻量级的运行时管理器。当监测到任务执行严重偏离预期如超时时管理器可以在一个预先计算好的、有限的“安全调度模式”集合中进行切换例如将某个任务迁移到另一个供应商的备用核上这些备用模式都经过离线验证满足基本的安全约束。安全监控集成调度系统应与硬件安全监控模块如用于比较复制任务结果的信任比较器紧密耦合。当比较器检测到不一致时不仅能触发警报还应能通知调度器将相关任务标为“可疑”并将其后续调度到经过特殊验证的“安全岛”核上执行。安全感知的任务调度是在芯片设计源头构筑安全防线的一次有力尝试。它不再把安全视为事后附加的检测模块而是将其作为设计空间探索的一个核心维度。尽管引入约束带来了优化复杂度但通过文中的图论建模冲突图、最大团和组合优化方法最大流最小割、图着色我们能够在安全、性能、成本这个“不可能三角”中找到有价值的折衷点。对于设计金融、汽车、工业控制等安全关键型芯片的工程师而言理解和应用这类方法意味着能在激烈的市场竞争中为自己的产品增加一道至关重要的差异化壁垒。
芯片设计中的安全感知任务调度：应对第三方IP硬件木马威胁
1. 项目概述当芯片设计遇上“不可信”的第三方组件在今天的芯片设计领域尤其是复杂异构多处理器片上系统MPSoC的开发中有一个既普遍又棘手的问题我们几乎不可避免地要使用第三方知识产权核3PIP。这就像盖一栋摩天大楼你不可能从烧砖、炼钢开始所有工序都自己来。为了追赶市场节奏、控制成本设计师们会大量采购现成的“功能模块”比如某个特定算法的硬件加速器、标准的内存控制器或者通信接口。然而这些“采购”来的模块其内部对我们而言是一个黑盒。你无法百分之百信任提供这些模块的供应商——不是质疑他们的商业信誉而是在复杂的全球供应链中任何一个环节都可能被植入恶意逻辑也就是我们常说的“硬件木马”。硬件木马的威胁是真实且严重的。想象一下在一个处理金融交易或控制关键基础设施的芯片里某个来自第三方供应商的计时器模块可能在特定条件下通过一个隐秘的通信通道激活另一个来自同一供应商的总线控制器中的恶意代码导致整个系统总线瘫痪。这种协同攻击单靠检测单个模块的输出是否正确是很难发现的。传统的“任务复制”安全策略让同一个任务在不同供应商的核上运行并比对结果可以应对输出篡改却无法切断这种模块间的秘密通信。因此安全感知的任务调度技术应运而生。它的核心思想非常巧妙既然无法确保每个3PIP都是干净的那就在系统架构层面通过智能的任务编排将来自同一供应商的、可能“串通”的组件隔离开。具体来说就是在高层次综合HLS阶段将一个应用程序分解成多个任务Task并在将这些任务映射到具体的硬件处理核Core上执行时施加两类安全约束任务复制同一任务需在不同供应商的核上执行和供应商多样性有数据依赖关系的相邻任务必须分配到不同供应商的核上执行。前者用于结果校验后者用于隔离风险。但安全不是免费的午餐。这些约束会带来显著的性能开销调度长度变长和成本开销需要更多不同供应商的核即设计成本需要更多硬件核即面积成本。我们面临的是一个典型的多目标优化难题如何在给定的资源核的数量约束或性能最晚完成时间约束下设计出安全违规最少、调度效率最高的任务调度方案这正是本文要深入探讨的核心。我将结合论文中的思路为你拆解其中的算法逻辑、实现难点并分享在实际工程化中可能遇到的“坑”和应对技巧。2. 核心安全威胁与防御架构解析在深入调度算法之前我们必须彻底理解我们防御的敌人是什么以及我们构建的“城墙”是如何工作的。这有助于理解后续所有优化决策背后的根本原因。2.1 硬件木马的攻击模式从单点失效到协同作案早期的硬件安全威胁模型相对简单主要关注单个IP核内部可能存在的、独立激活的恶意逻辑。例如一个被植入木马的加密协处理器可能在遇到特定输入模式时泄露密钥。针对这种威胁任务复制Task Duplication是一种有效的防御手段。其原理是将同一个计算任务例如一个FFT运算分配给两个来自不同供应商的、功能相同的IP核例如供应商A的DSP核和供应商B的DSP核并行执行。由于不同供应商的实现方式、内部状态机乃至晶体管级电路都不同同一个硬件木马被同时植入两个独立设计核的概率极低。因此通过一个可信的比较器通常由设计方自己实现比对两个核的输出结果一旦不一致就能触发安全警报从而检测到输出篡改类攻击。然而攻击者的手段也在进化。更隐蔽、危害更大的是一种分布式、协同式的攻击。攻击者可能将木马的“触发器”和“负载”分别植入两个来自同一供应商的不同IP核中。在系统正常运行时这两个核通过设计者未知的、隐秘的通信路径例如利用共享总线上的特定时序、预留的测试接口或未公开的寄存器进行通信。当承载“触发器”的核满足某个罕见条件时它会通过秘密通道发送一个激活信号唤醒另一个核中的“负载”木马从而发起拒绝服务、信息泄露或更复杂的攻击。注意这种协同攻击之所以危险是因为单个核在独立测试或执行“任务复制”校验时其行为可能是完全正常的。只有当他们被部署在同一个系统中并且按照特定的顺序和依赖关系执行时攻击链才会被触发。这使得传统的、针对单个IP的检测方法如形式化验证、代码覆盖率分析几乎失效。2.2 安全约束构建系统级的动态隔离区为了应对协同攻击论文引入了供应商多样性Vendor Diversity约束。其规则直观而有力任何两个在任务图中直接相连即存在数据依赖关系的任务不能被调度到来自同一供应商的硬件核上执行。这个约束的威力在于它从数据流的角度切断了潜在恶意IP核之间建立稳定、可预测通信路径的可能性。回到之前的例子如果任务A父任务和任务B子任务必须由不同供应商的核执行那么即使供应商X的核A中包含了“触发器”供应商X的核B中包含了“负载”由于任务调度结果强制它们不能相邻执行那个隐秘的、依赖于特定执行顺序和上下文的激活通道就被物理或至少是逻辑隔离了。任务复制和供应商多样性共同构成了一个立体的防御架构纵向任务层面通过复制与比对确保单个任务计算结果的正确性。横向数据流层面通过供应商隔离防止恶意逻辑沿任务依赖链传播和协同激活。这个架构将安全考量从被动的“检测与响应”前置到了主动的“设计与隔离”阶段是高层次综合中实现“设计即安全”理念的关键实践。2.3 安全开销的量化我们为安全付出了什么引入安全约束的直接代价体现在三个维度这也是我们优化算法的优化目标调度长度Schedule Length, SL即整个任务图完成所有计算所需的时间。供应商多样性约束限制了任务调度的灵活性。例如即使有两个空闲的核如果它们来自同一供应商而待调度的两个任务存在依赖关系它们也无法并行执行必须串行从而拉长整体时间。设计成本Design Cost这里模型化为所需IP供应商的数量。为了满足供应商多样性尤其是当任务图复杂、并行度高时我们可能需要采购来自多家供应商的同类IP核这增加了采购、验证和集成成本。面积/资源成本Area/Resource Cost模型化为所需硬件处理核的总数。任务复制本身就需要至少两倍的核来执行同一任务。此外为了满足多样性和并行性可能还需要更多的核来弥补因约束导致的效率下降这直接增加了芯片的硅片面积和功耗。论文中定义的两个核心优化问题正是针对资源核数固定或性能时间固定这两种最常见的工程约束场景寻求安全与效率的最优平衡点。3. 资源约束下的安全感知任务调度第一种场景是资源受限调度我们手头可用的硬件核总数是固定的面积/功耗预算已定目标是在满足供应商数量约束的前提下找到一个调度方案使得最终完成时间调度长度最短同时尽可能减少安全约束违反如果无法完全满足。3.1 问题建模与核心挑战输入包括任务图TG、供应商约束最多能用λ个不同供应商、资源约束总共只有R个核。输出是一个任务到核的映射以及执行时间表。核心矛盾在于供应商多样性要求相邻任务用不同供应商的核这倾向于使用更多供应商但资源约束限制了核的总数而每个供应商能提供的核可能也是有限的在论文的扩展问题中考虑。这可能导致“死锁”可用的核不少但因为供应商类型不合适任务无法被调度造成资源闲置和调度延迟。论文指出先前的研究如Liu等人的工作将任务调度和供应商分配分成了两个独立的步骤。先不管供应商按最快速度调度任务然后再尝试给每个任务分配供应商。这种方法忽略了“供应商分配”对“调度可行性”的实时影响可能导致如图3(b)所示的糟糕结果任务V3和V4本可并行但因都被分配到供应商3且该供应商只有一个可用核被迫串行。因此本文算法的第一个关键改进是将供应商分配与任务调度过程深度融合在决定一个任务何时在哪个核上执行的同时就为其决定由哪个供应商的核来执行。3.2 算法核心供应商冲突图与最大团计算为了实现上述融合调度算法需要一种方法来快速评估如果给某个任务分配了某个供应商会不会导致后续无法满足供应商约束这里引入了供应商冲突图Vendor Violation Graph, VVG的概念。VVG的构建VVG中的每个节点代表任务图TG中的一个任务簇。初始时每个任务自成一个簇。如果两个任务簇中的任务在原任务图中是相邻的存在数据依赖那么在VVG中这两个节点之间就有一条边。这条边代表一条供应商多样性约束这两个簇必须被分配到不同的供应商。理解“团”与“供应商数量”的关系 在VVG中一个“团”指的是一组节点其中任意两个节点之间都有边相连即两两互斥。这意味着这个团里的所有任务簇彼此之间都存在直接的依赖关系根据供应商多样性约束它们必须全部来自不同的供应商。 因此VVG中最大团的大小ω(VVG)就等于满足当前任务图所有多样性约束所至少需要的供应商数量。例如如果VVG中有一个包含4个节点的团那么你至少需要4家不同的供应商才能给这个团里的每个簇分配一个互不相同的供应商。算法的巧妙之处在于快速更新 当我们将两个任务簇合并即违反一次多样性约束让两个有依赖的任务共享同一个供应商的核VVG中的两个节点会收缩为一个。这可能会减少最大团的大小从而降低对供应商数量的最低要求。 论文提出不需要每次合并后都重新计算整个VVG的最大团这是一个NP难问题。由于任务图的连接通常比较稀疏每个任务只与少数任务相邻因此受一次合并操作影响的只是局部子图。算法通过计算诱导子图VVG_I(ci)包含节点ci及其所有邻居的最大团来高效更新全局最大团的估计值从而在调度过程中动态评估供应商约束的满足情况。3.3 调度流程详解与实操要点整个资源约束调度流程如图4所示是一个迭代优化过程供应商约束下的任务聚类Vendor-Constrained Task Clustering 如果初始VVG的最大团大小ω(VVG)超过了允许的供应商数量λ说明约束无法被完全满足必须违反一些多样性约束。此时需要智能地选择将哪些相邻任务聚类即分配到同一供应商的核上以最小化安全违规数scyv。算法会构建一个供应商团图VCG只包含那些位于最大团中的节点和边。然后它计算每条边的“收缩优先级”优先收缩那些能消除最多最大团、同时引入最少安全违规的边。这个过程循环直到ω(VVG) ≤ λ。候选供应商集合确定Candidate Color Set Determination 在调度每个任务时我们需要知道当前可以给它分配哪些供应商而不违反约束。这被建模为一个图着色问题每个颜色代表一个供应商。算法为每个任务簇维护一个“候选颜色集合”。当尝试给一个簇分配某种颜色时它会快速检查这个操作是否会在局部子图中产生一个大小为(λ1)的团即需要λ1个供应商。如果会则这个颜色从该簇的候选集中移除。这个检查同样利用了局部诱导子图的性质避免了全局重算效率很高。任务着色与调度Task Coloring and Scheduling 这是调度器的核心循环。采用类似列表调度的策略每次从就绪任务所有前驱任务已调度完成中选择一个任务。对于这个任务遍历其所有可用的核考虑资源和供应商候选集。对于每个核计算该任务最早可开始执行的时间。选择能使该任务最早完成的那个核并为其分配对应的供应商。这个过程实现了供应商分配与调度决策的实时联动。实操心得与注意事项优先级函数的设计在列表调度中如何对就绪任务排序论文可能使用了诸如“向上排名”等启发式方法。在实践中可以结合任务的关键路径长度、子任务数量等因素来定义优先级这对最终调度长度影响很大。“最早完成时间”计算这不仅仅是任务在某个核上的开始时间执行时间。还需要考虑核间通信开销。如果该任务的前驱任务在另一个核上执行数据需要传输时间。调度器必须维护每个核的时间线Timeline和核间通信链路的状态准确计算数据传输完成的时间。处理核资源限制每个供应商的核数量可能有限。在“候选供应商集合确定”阶段除了检查团约束还需要检查该供应商是否还有可用的核。如果没有则该供应商颜色也应从候选集中移除。4. 性能约束下的安全感知任务调度第二种场景是性能受限调度我们有一个最后期限Deadline即调度长度不能超过某个值D。目标是在满足这个性能要求的前提下最小化所需硬件核的总数同时尽可能减少安全约束违反。4.1 问题转化与核心思路当性能是硬约束时我们的思路要从“如何排布任务使时间最短”转变为“如何在给定时间内用最少的资源跑完所有任务”。一个直接的想法是将更多的任务“打包”到同一个核上执行即任务聚类这样可以节省核的数量。但聚类意味着让有依赖关系的任务在同一个核上运行这必然违反供应商多样性约束因为相邻任务用了同一个供应商的核。因此性能约束调度问题本质上是一个安全与资源的权衡我们愿意承受少安全风险违反多少条多样性约束来换取资源的节省论文的目标是在满足时间要求的前提下找到那个违反约束最少的调度方案。4.2 基于最大流最小割的关键路径聚类算法这是本算法最精彩的部分。它的直觉是想要缩短总时间必须压缩关键路径即任务图中最长的路径的长度。将关键路径上的任务聚类到同一个核上可以消除它们之间的核间通信延迟是缩短调度长度最有效的方法。但关键路径可能有多条且聚类操作会引入安全违规。如何选择聚类哪些边才能用最少的安全违规代价换取最大的时间收益论文将此建模为一个网络流问题构建流网络以任务图为蓝本构建一个流网络。其中边的容量Capacity被设置为一个与“如果收缩这条边即聚类其两端任务所能减少的调度长度估计值”相关的权重。减少时间越多的边容量越大。同时节点的容量或通过引入额外节点实现的边容量可以映射为违反安全约束的代价。求解最小割在流网络中寻找最小割。根据最大流最小割定理最小割的容量等于从源点到汇点的最大流。在这个建模下最小割所对应的边集恰恰代表了那些以最小总“代价”此处代价是安全违规的加权和将网络分割成能显著影响关键路径的两部分的边。换句话说割掉这些边在调度中即聚类这些边连接的任务能以最小的安全代价最有效地缩短整个任务图的调度长度。迭代收缩根据最小割的结果收缩相应的边进行任务聚类。然后更新任务图因为聚类产生了新的复合任务和流网络重复上述过程直到估算的调度长度满足性能约束D为止。这个方法的优势在于它通过严谨的数学规划方法系统性地在全局范围内寻找“性价比”最高的聚类操作而不是贪婪地处理单条关键路径。4.3 聚类后的供应商分配与调度完成满足性能要求的聚类后我们得到了一个“粗粒度”的任务簇集合。接下来需要解决两个问题供应商分配为每个任务簇分配一个供应商。这又回到了一个图着色问题但此时的图是聚类后的冲突图一个簇是一个节点。目标是用最少的颜色供应商使得相邻簇颜色不同满足未因聚类而消除的多样性约束。这是一个经典的图着色优化问题可以使用DSATUR等启发式算法高效求解。最终调度在确定了每个簇的供应商后问题退化为一个在资源核数已最小化和供应商约束下的普通列表调度问题。由于聚类已经大大减少了任务数量和通信开销这个调度步骤会相对快速。常见问题与排查技巧实录问题一性能约束过于严苛即使完全违反所有安全约束也无法满足。排查首先检查不考虑任何安全约束时的最短可能调度长度即无限资源、无限供应商下的理想情况。如果这个理想长度都大于D那么问题本身无解。需要与系统架构师协商放宽性能要求或考虑使用更高性能的IP核。问题二算法迭代多次后调度长度下降缓慢无法达到目标D。技巧检查流网络中边的容量权重设计。容量权重应准确反映收缩该边对全局关键路径的缩短潜力而不仅仅是局部通信延迟。一个改进方法是使用更精确的调度长度估算器如基于关键路径的静态列表调度在每次迭代后重新评估并动态更新流网络中的容量。问题三供应商分配阶段所需供应商数量仍然过多。技巧当图着色结果需要的颜色数超过可用供应商数时说明前期聚类程度不够。可以反馈到聚类阶段以“减少所需供应商数”为附加目标优先考虑收缩那些连接高度数节点的边因为给高度数节点着色需要更多颜色即使它们对缩短时间的贡献不是最大。这需要在安全违规、时间缩短和供应商数量之间进行更复杂的三方权衡。5. 工程实现考量与扩展讨论将学术算法转化为实际可用的EDA工具或设计流程的一部分还需要考虑许多工程细节。5.1 输入建模的准确性算法的有效性高度依赖于输入模型的质量任务执行时间是固定值还是范围是否考虑缓存、总线争用带来的波动在实际HLS中这通常通过综合后的静态时序分析或仿真来获取。通信延迟核间通信开销的建模至关重要。它是固定的还是与数据量、网络拓扑、拥塞情况相关论文中假设了固定值但实际中可能需要更精细的片上网络NoC模型。供应商可信度模型论文假设所有第三方供应商同等不可信。现实中我们可能对某些经过认证的供应商有更高的信任度或者知道某些供应商的IP核存在特定类型的已知漏洞。这可以引入“供应商风险权重”在优化目标中违反涉及高风险供应商的约束代价更高。5.2 多目标优化的权衡系数论文的目标函数如公式1中的 α1 * scyv SL中α1是一个很大的常数确保优先最小化安全违规。但在实际工程中这个系数需要仔细设定。如果α1设置得过大算法会不惜一切代价避免违规可能导致调度长度急剧恶化即使只违反一条无关紧要的约束就能换来显著性能提升。如果α1设置得过小算法可能会为了微小的性能提升而引入大量安全违规。 一个更实用的方法是采用帕累托前沿Pareto Front分析。运行算法多次每次调整安全与性能的权重得到一组“非支配”解即无法在不让另一个目标变差的情况下改进一个目标。让设计师从这个解集中根据项目具体需求进行选择。5.3 与现有HLS/MPSoC设计流程的集成安全感知调度不应是一个孤立的工具而应嵌入现有设计流程输入阶段从高级别语言如C/C或模型如Simulink编译得到任务图TG。调度阶段集成本文算法接受资源、性能、供应商约束作为设计约束。输出阶段生成的任务-核-供应商绑定关系以及调度表应能向下传递到硬件综合指导每个处理核的RTL生成或选择从对应的供应商IP库中。通信综合根据任务间的数据依赖和调度时序生成片上网络NoC或总线架构。软件生成生成在目标MPSoC上运行的操作系统任务或裸机代码框架实现调度表。5.4 应对动态与不确定性论文研究的是静态调度。在实际系统中任务执行时间可能因输入数据而异或者系统需要处理动态到达的任务。静态调度基础本文的算法可以作为基线静态调度方案为每个任务分配固定的核和供应商。动态调整在此基础上可以设计一个轻量级的运行时管理器。当监测到任务执行严重偏离预期如超时时管理器可以在一个预先计算好的、有限的“安全调度模式”集合中进行切换例如将某个任务迁移到另一个供应商的备用核上这些备用模式都经过离线验证满足基本的安全约束。安全监控集成调度系统应与硬件安全监控模块如用于比较复制任务结果的信任比较器紧密耦合。当比较器检测到不一致时不仅能触发警报还应能通知调度器将相关任务标为“可疑”并将其后续调度到经过特殊验证的“安全岛”核上执行。安全感知的任务调度是在芯片设计源头构筑安全防线的一次有力尝试。它不再把安全视为事后附加的检测模块而是将其作为设计空间探索的一个核心维度。尽管引入约束带来了优化复杂度但通过文中的图论建模冲突图、最大团和组合优化方法最大流最小割、图着色我们能够在安全、性能、成本这个“不可能三角”中找到有价值的折衷点。对于设计金融、汽车、工业控制等安全关键型芯片的工程师而言理解和应用这类方法意味着能在激烈的市场竞争中为自己的产品增加一道至关重要的差异化壁垒。
