基于NUMA的并行RTL仿真中的拓扑感知 admission control 动态负载均衡 黄欣、 李光荣、 杨帆、 毕赵蕊

《Electronics》：Topology-Aware Admission Control for Dynamic Load Balancing in NUMA-Based Parallel RTL Simulation Xin Huang, Guangrong Li, Fan Yang and Zhaori Bi

　　摘要
在多插槽NUMA平台上对寄存器传输级（RTL）设计进行并行离散事件模拟（PDES）时，需要动态负载均衡来减轻由屏障引起的尾部延迟。然而，RTL模拟的超细事件粒度使得迁移成本不可忽视，而NUMA的非均匀内存层次结构将迁移成本变成了一个与拓扑结构相关的变量，而不仅仅是常数。现有的方法要么忽略了这种拓扑依赖性，要么依赖于缺乏理论依据的启发式阈值。本文将NUMA感知的动态负载均衡构建为一个受限优化问题，在该问题中，迁移成本是源核心和目标核心之间插槽局部性的显式函数。我们引入了一个统一的净收益函数???(??,?? →??,??)，该函数综合考虑了将模块m从核心i迁移到核心j时的尾部延迟减少、迁移开销以及缓存预热成本。我们证明了G函数在迁移规模和频率上是联合凹函数，得出了两个分析结果：（i）一个闭合形式的准入不等式，用于判断何时迁移严格有益；（ii）一个保守的固定频率设计规则，用于指导基于时代的控制器的总体时长的选择。我们进一步证明了，当初始静态分区满足有界质量条件时，总迁移量是有界的，这证实了限制是最佳选择，而不仅仅是保守的。我们在基于事件的并行RTL模拟原型TACVS（Topology-Aware Admission Control Verilog Simulator）中实现了所提出的拓扑感知准入控制（TAC）框架。在2插槽NUMA平台上对四种开源RTL设计的实验表明，TAC平均可以将尾部延迟比率降低18.0%（最高可达28.5%），并将归一化吞吐量提高27.1%（最高可达34.1%），相比不考虑拓扑结构的基线而言。消融研究进一步表明，准入控制和冷却对于性能至关重要，分别移除它们时，吞吐量平均下降15.9%和22.8%（最高可达22.4%和32.5%）。

1. 引言
寄存器传输级（RTL）模拟仍然是现代VLSI设计流程中功能验证的主力方法。随着设计规模扩展到数十亿个门电路，模拟工作负载远远超过了单个核心的能力，从而需要在多核平台上进行并行离散事件模拟（PDES）。如今，高核数服务器普遍采用非均匀内存访问（NUMA）架构，其中核心被分组到插槽中，每个插槽具有本地内存；跨插槽访问会导致显著更高的延迟，并通过缓存一致性协议消耗插槽间带宽。
并行RTL模拟以Delta周期进行，在每个周期内，所有并发事件必须在周期继续之前被评估。这在每个Delta周期边界处引入了一个全局屏障：所有核心必须完成其分配的工作负载后，任何核心才能继续。因此，模拟吞吐量由每个屏障中最慢的核心决定，这就是所谓的尾部延迟问题。RTL模块在核心间的不均匀分布直接转化为在屏障处浪费的周期。
动态负载均衡通过在运行时将工作负载从负载过重的核心迁移到负载不足的核心来解决尾部延迟问题。然而，在NUMA平台上，迁移引入了三个问题：
- 局部性破坏：跨插槽迁移模块会使本地缓存失效，触发冷启动惩罚，并将后续内存访问重定向到远程节点。
- 不恒定的成本：与对称多处理器不同，NUMA上的迁移成本是源核心和目标核心之间插槽局部性的函数。插槽内的移动比跨插槽移动便宜得多。
- 细粒度：RTL事件持续时间极短（每个事件的模拟时间为纳秒级别），因此即使是一次不明智的迁移，其成本也无法在后续的有用工作中得到摊销。
这些观察结果激发了本工作的核心前提：在NUMA上的细粒度PDES中，动态负载均衡必须确定何时迁移是净有害的，而不仅仅是如何迁移。当迁移成本依赖于拓扑结构并且在事件粒度上不可忽视时，选择性限制比激进的重平衡表现更好。

1.1. 现有方法的局限性
现有工作在基于NUMA的RTL环境中留下了三个特别重要的空白：
- 忽视拓扑结构的动态方法，如工作窃取和基于扩散的平衡[1,2]，它们会对不平衡作出反应，但将处理元素视为等距离的。在NUMA平台上，这种假设可能会触发不必要的跨插槽迁移，破坏局部性，并放大一致性/互连流量。
- 静态分区和基于图的重新分区方法[3,4,5]在编译时很好地利用了结构连接性，但它们无法适应由数据依赖的信号活动引起的运行时不平衡。在RTL模拟中，这一限制尤为严重，因为在模拟的不同阶段，活跃的工作集可能会发生显著变化。
- 实用的并行HDL/RTL模拟器通常将静态分区与运行时调度或迁移结合使用[6,7,8]，但它们的迁移决策主要是启发式的。它们没有提供一个明确的标准，来同时权衡尾部延迟减少与NUMA系统上的拓扑依赖性迁移开销和缓存预热成本。
我们的工作重点关注这三个空白，同时也考虑了前两个问题。因此，核心问题不仅是如何迁移工作负载，还有在基于NUMA的并行RTL模拟中何时迁移也是净有益的。

1.2. 贡献
本文做出了以下贡献：
- 问题表述：我们将NUMA感知的动态负载均衡在并行RTL模拟中构建为一个受限优化问题，在该问题中，迁移成本被明确建模为NUMA拓扑距离的函数（第4节）。
- 统一的净收益模型和设计规则：我们引入了一个统一的净收益函数???(??,?? →??,??)，该函数综合考虑了尾部延迟减少、迁移开销和缓存预热成本。基于此模型，我们推导出了一个闭合形式的准入不等式，用于判断何时迁移有益，以及一个保守的固定频率设计规则，用于选择基于时代的控制器的总体时长（第5节）。
- 迁移量界限：我们证明了在初始分区质量有界的情况下，所有时段的总迁移字节数量受到初始分区质量比率和最小非零拓扑距离的函数限制。这一结果明确了动态平衡几乎静止的条件（第5节）。
- 系统实现和验证：我们在TACVS中实现了所提出的框架，包括一个轻量级的运行时分析器、一个拓扑感知的候选集构造器、一个准入控制器和一个分层调度器。在2插槽NUMA平台上的四个RTL基准测试上的实验验证了分析结果和所提出方法的端到端性能（第6节和第7节）。

2. 相关工作及其与最近最先进技术的定位
最近关于并行RTL模拟的工作在几个不同的方向上取得了进展。一项工作通过更积极的执行和分区重构来改进CPU侧的RTL模拟。例如，RepCut[7]针对全周期RTL模拟，并通过帮助分区的复制来提高并行性。BatchSim[9]也属于全周期模拟家族，但它通过将多个周期批量化为一个任务图并并行执行结果的多周期计算图来提高并行性。TaroRTL[8]通过使用基于协程的异构CPU–GPU任务图调度探索了设计空间的另一个点。
另一个重要趋势强调在现代硬件上特别是NUMA平台上进行局部性感知的执行。先前关于NUMA感知调度和内存放置的工作表明，保持局部性并减少不必要的远程访问对于可扩展性能至关重要[10,11,12]。更广泛地说，这些研究表明，拓扑感知调度正在成为并行运行时的一个重要最新技术原则。然而，这些机制通常在不同的运行时抽象或模拟器内核中实现，因此并不直接等同于事件驱动的RTL PDES中的屏障主导执行模型。
我们的工作关注一个互补的设置：具有Delta周期屏障和时代边界迁移的事件驱动并行RTL模拟。在这种设置中，关键挑战不仅仅是增加迁移的积极性，而且是在拓扑依赖成本下确定迁移何时是净有益的。这种关注与全周期重构方法和通用的NUMA感知运行时策略不同，因为它将尾部延迟减少、迁移开销和缓存预热成本明确结合到一个统一的决策模型中。因此，所提出的框架特别适合于多插槽NUMA服务器上的细粒度RTL PDES，在这种情况下，选择性限制通常比激进的运行时重平衡更有效。
为了将我们的评估与这种最近的拓扑感知研究趋势更直接地联系起来，我们在第7节中还引入了一个分层工作窃取（HWS）基线。HWS并不代表一个独立的模拟器家族；相反，它是一个受控的基线，捕捉了在同一事件驱动的RTL模拟堆栈内的局部性感知受害者选择的最新核心思想。具体来说，HWS保留了与经典工作窃取相同的执行模型和窃取粒度，但在NUMA平台上用局部优先的分层受害者探测替换了忽略拓扑的随机受害者选择。这使我们能够区分仅引入拓扑感知窃取的好处与包括准入控制、冷却和分层迁移调度在内的完整TAC框架带来的额外收益。

3. 预备知识和符号
3.1. 并行RTL模拟模型
我们考虑事件驱动的并行RTL模拟，其中待验证的设计被分解为N个模块??={为了分析的清晰性，我们在下一个Delta周期开始之前引入了一个全局同步屏障，以便可以将模拟器视为一系列由屏障分隔的Delta周期执行。这种抽象有两个来源：（i）标准的Verilog/systemVerilog事件调度语义[13,14,15]；（ii）先前关于并行RTL模拟的工作，这些工作强调同步/屏障成本是关键的可扩展性瓶颈[6,7,8]。因此，我们的模型并不是对任何单一模拟器实现的逐字重述；而是一个简化的执行模型，用于捕捉本文分析所需的屏障主导行为。
定义1（执行成本）：模块????在Delta周期t的执行成本表示为?????(??) ∈?>0。这种成本通常在编译时是未知的，因为它取决于数据依赖的控制流和信号活动。
设P表示核心的数量。一个分区?? :? →{1,…,??}将每个模块分配给一个核心。核心p在Delta周期t的负载表示为?????(??)=∑??:???(????)=???????(??)。（1）
核心p的屏障等待时间表示为?????(??) =??max?(??) ??????(??)，其中??max?(??) =max????????(??)。尾部延迟本身就是??max?(??)；最小化尾部延迟等同于最小化每个核心的最大负载。Delta周期t的平均每个核心负载表示为?????(??)=1?????∑??=1?????(??)。（2）这个瞬时量对于描述Delta周期级别的屏障不平衡很有用。其按时代聚合的对应量将在第3.4节中介绍。

3.2. NUMA架构模型
定义2（NUMA拓扑）：NUMA平台被建模为一组S个插槽，每个插槽包含??/??个核心，这些核心共享一个一级缓存（LLC）和本地内存。我们定义核心i和j之间的拓扑距离如下：
???(??,??)=?{ {?{ {?0??????=??,??intra??????≠????????????????????????????,??inter??????,??????????????????????????????????????,（3）
其中??inter ???intra >0。
在同一插槽内的核心访问保持局部性，通常会产生较低的延迟，而跨越插槽边界的访问会产生较高的延迟并消耗插槽间带宽。
方程（3）是本文采用的简化插槽级抽象。它受到之前NUMA研究中讨论的访问不对称性的启发[10,11]，但有意简化为两个非零距离级别，以揭示与迁移决策相关的关键区别：插槽内的移动比跨插槽的移动便宜得多。
将模块从核心i迁移到核心j的成本包括：（i）与模块工作集大小成比例的状态传输开销，以及（ii）目标处的缓存预热成本，这两者都随???(??,??)而变化。

3.3. 时代和屏障
在RTL事件粒度下，每个Delta周期或每个模拟周期的迁移都是非常昂贵的。因此，我们将连续的屏障分成长度为??epoch（以模拟周期计）的时代。迁移决策仅在时代边界进行。
定义3（时代）：一个时代e由模拟周期{(???1)???epoch +1,…,?? ·??epoch}组成。每个时代的负载统计数据被汇总，以指导下一个时代的迁移决策。

3.4. 时代级控制统计
设????表示时代e中发生的Delta周期屏障集合。我们定义核心p的按时代聚合负载以及时代e中所有核心的平均负载为^??(??)??=∑??∈?????????(??)，^ˉ??(??)=1?????∑??=1^??(??)??。（4）
运行时控制器使用时代级不平衡指标????=max???^??(??)??^ˉ??(??）（5）来判断是否应在时代e的边界激活迁移规划。这个控制量与第7.4节中报告的基于屏障的尾部延迟比率不同，后者用于性能评估。

4. 问题表述
我们现在正式定义了NUMA感知的动态负载均衡问题。设????表示时代e开始时的分区，Δ?????表示在时代e和?? +1之间边界应用的迁移操作集合。每个迁移操作?? =(????,??,??)将模块????从核心i迁移到核心j。

4.1. 迁移成本函数
定义4（迁移成本）：迁移?? =(????,??,??)的成本表示为???(??)=??·????·???(??,??)+??·???(??,??）（6），其中????是模块????的工作集大小，α表示按拓扑距离缩放的每个字节的状态传输开销，β表示与大小无关的固定开销。
注释1。在实践中，α和β被视为固定NUMA平台的机器特定校准系数。它们在目标机器上被近似为一次常数，但不假设它们在不同的平台上是通用的。与以往工作的关键区别在于，???(??)不是一个常数：它取决于模块的特性（????）以及源和目标之间的拓扑关系（???(??,??)）。4.2. 目标函数让????表示第e时代的delta-cycle障碍集合。我们定义ˉ??(??)max=1|????|3∑??∈??????max?(??)（7）作为时代级的平均障碍尾延迟。动态负载均衡问题旨在最小化E个时代内的累积尾延迟：min{Δ?????}????=12??∑??=1ˉ??(??)max?(????⊕Δ?????）（8），受限于∑??∈Δ????????(??)≤??(??)budget，???=1,…,??（9），其中??(??)budget是第e时代的迁移成本预算，⊕表示将迁移集合Δ?????应用于分区????。注2. 预算约束（9）反映了共享资源（插槽间互连带宽、缓存一致性协议）的有限容量。在NUMA上，超过这个预算会降低所有共享互连的模块的性能，而不仅仅是被迁移的模块。4.3. 一般问题的难度优化（8）和（9）通常都是NP难问题（通过从多处理器调度问题归约得到）。此外，????2(??)的精确值事先是未知的。因此，我们的方法寻求分析条件，以确定何时单次迁移是净受益的，从而能够做出贪婪的、短视的迁移决策，并有可证明的质量保证。5. 理论框架5.1. 净收益函数我们分析了单次迁移决策的边际效应。考虑在第e时代的边界将模块m从核心i（尾部核心）迁移到核心j，迁移每1/??时代执行一次（频率f，以??3??3??3??3??3??3??3??3??3??3??3??3??3??3??3???1为单位）。从频率和周期的定义来看，显然?? =1????3??3??3??3?。请注意，在实现的运行时中，f应该被解释为基于时代的控制器的全球控制节奏，而不是每次迁移的独立时钟。每次迁移的自适应节奏选择是可能的，但这超出了本工作的范围。我们现在定义第e时代模块k的每个模块的累计负载估计^??(??)??=∑??∈????????2(??)（10）。然后我们有定义5（净收益函数）。将模块m从核心i迁移到核心j的净收益为???(??,??→??,??)=Δ???2(??,??,??)?__?__?????????-????????????????????????????????????·???(??,??,??)?__?__????????????????????????????????????????????????·??2(??,??)?__?__?cache????????-????3??????????????（11），其中Δ???2(??,??,??) =^???? ?(????+^???????max)+是通过将m从当前的尾部核心i移动到核心j所实现的尾延迟减少量，(??)+ =max2(0,??)；???(??,??,??) =（??3????+??）·??2(??,??)是定义4中的单次迁移成本；??2(??,??)是在接收m后在核心j产生的缓存预热惩罚，与???? ·??2(??,??)成正比。由于??2(??,??)更依赖于运行时，它是根据最近的迁移后行为在线估计的。结合成本项，我们写???(??,??→??,??)=Δ???2(??,??,??)???·Γ2(??,??,??）（12），其中Γ2(??,??,??) =???(??,??,??) +??2(??,??)是每次迁移的总惩罚。5.2. 净收益函数的性质定理1（净收益的凹性）。对于固定的模块m和迁移路径?? →??：1. 对于?? >0，G是f的严格递减的、仿射函数。2. 对于一组候选迁移??，累积净收益^?? =∑??∈????2(??,????)在迁移规模|??|和频率向量（????）??∈??上是共同凹的。证明。第1部分直接来自（12）：G是f的仿射函数，斜率为负Γ <0。对于第2部分，观察到Δ???在从尾部核心移除的模块数量上是凹的（每次额外的迁移由于（??）+截断而减少了边际尾延迟增益），而成本项在|??|和f上是线性的。凹函数和线性函数的和是凹的。□ 5.3. 推论1：准入不等式推论1（准入不等式）。迁移?? =(??,?? →??)在频率f下是净受益的当且仅当Δ???2(??,??,??)>??·Γ2(??,??,??)+??（13），其中?? >0是一个防止振荡迁移的稳定裕度。证明。从（12）来看，?? >0要求Δ??? >?? ·Γ。引入稳定裕度??是为了确保即使在Δ???和Γ的估计误差下，G也保持严格正。我们设置?? =?? ·^ˉ??，其中^ˉ??在方程（4）中定义，?? >0是容忍参数（类似于有界负载算法[16]中的（1 +??）松弛）。注3. 准入不等式（13）明确了NUMA拓扑的影响：对于跨插槽迁移，??2(??,??) =??inter会产生较大的Γ，需要相应的较大Δ???来证明移动的合理性。在极限情况??inter →∞下，永远不会允许跨插槽迁移，恢复纯插槽内平衡策略。5.4. 推论2：固定频率设计规则推论2（固定频率控制器的全球时代长度可行性）。假设运行时使用决定频率f。那么任何在此固定节奏控制器下保持净受益的迁移?? =(??,?? →??)必须满足??<δ???2(??,??,??)???γ2(??,??,??）（14）。等价地，全球时代长度必须满足??epoch>Γ2(??,??,??)Δ???2(??,??,??)???（15）。因此，一个充分的全局选择是??epoch≥ΓmaxΔ???min???≥sup??∈??rep?Γ2(??)Δ???2(??)???（16），其中??rep表示目标平台上工作负载类的代表性候选/允许迁移集合，Γmax和Δ???min是在这个集合上取得的。注意对于（16），我们只是在选择一个适当的全局迁移频率。因此，做出一个充分的选择是更好的。这个结果应该被解释为选择一个单一系统级控制节奏的保守设计规则，而不是声称所有个别迁移或所有测试用例都共享一个精确的内在最优解。证明。根据推论1，迁移保持净受益仅当Δ???2(??)>??2Γ2(??,??)+??，这等同于（14）。重新排列得到（15）。因为实现的运行时对所有迁移决策使用一个全局节奏，所选择的??epoch必须满足控制器在该固定频率政策下打算保持可接受的每个迁移的这个条件。在对代表性候选集合??rep取最大值得到（16）。通过Γmax/(Δ???min???)的近似是保守的，因为它结合了不需要在单次迁移事件中同时发生的最坏情况。注4. 推论2并不断言所有迁移或所有测试用例都共享一个普遍的精确最优解。它的作用是为选择基于时代的全球控制器节奏提供一个保守的尺度设置规则。这是有意义的，因为在TAC中所有控制动作都在时代边界同步。在我们固定的2插槽NUMA平台上，拓扑距离只有两个非零值（??intra和??inter），而准入和分层调度进一步过滤极端候选者。这些效果共同使单个固定的??epoch成为一个实用且稳健的系统级控制旋钮，而不是针对每个测试用例调整的参数。5.5. 在质量分区下的迁移量限制我们现在确定，一个良好的初始静态分区限制了所需的动态迁移量。定义6（分区质量比率）。让^??(0)??表示在参考评估时代中，在初始分区??0下测量的核心p的累计负载。初始分区的质量比率为??0 =??2(??0)。一个完美的分区有??0 =1。定理2（迁移量限制）。让??0是具有质量比率??0 =??2(??0)的初始静态分区。在具有容忍度?的准入不等式下，E个时代内的总迁移量（所有迁移模块的工作集合大小之和）满足??total≤(??0?1???)·^ˉ??(0)·????·??intra（17），其中??total=∑??∈∪????=1Δ?????????（18）。特别是，当??0 ≤1 +??时，我们有??total ≤0，即没有触发迁移。证明。如果??0 ≤1 +??，那么^??(0)max?^ˉ??(0)≤??3^ˉ??(0）（19），因此不平衡保持在容忍带内，调度器不允许任何迁移。因此，??total =0。现在考虑??0 >1 +??。超出容忍带的负载过剩是^??(0)max?(1+??)?^ˉ??(0)=(??0?1???)?^ˉ??(0)（20）。因此，在E个时代内，可以移除的累积有用过剩量上限为（??0?1???)?^ˉ??(0)3??（21）。对于任何被允许的迁移??，迁移成本模型给出???(??)=??3???????2(??,??)+??3??2(??,??)≥??3???????intra（22）。因此，??3??intra3∑??????≤∑?????(??）（23）。由于允许的迁移只能在移除有用过剩量时消耗惩罚预算，因此所有允许的迁移在E个时代内的总惩罚不能超过累积可移除的过剩量：∑????2(??)≤(??0?1???)3^ˉ??(0)3??（24）。结合这两个不等式得到??total=∑??????≤(??0?1???)3^ˉ??(0)3????3??intra（25）。这证明了结果。注5. 定理2为“约束即最优”的设计原则提供了正式的证明：初始分区越好，动态均衡器需要做的工作就越少。当??0 ?1 ≤??时，系统可证明是静止的——没有迁移通过准入测试，动态均衡器保持空闲。6. 系统设计本节描述了如何在第5节的理论框架中实现一个实际的并行RTL仿真系统。图1提供了概述。图1. TACVS中的TAC运行时控制流。运行时分析器从仿真引擎收集时代级的负载统计信息，并为拓扑感知的候选构建推导出不平衡状态。然后准入控制器过滤候选迁移，分层调度器执行被允许的移动。6.1. 轻量级运行时分析器分析器以最小的开销收集时代级的运行时摘要。它不是在每个障碍边界对所有RTL模块进行单独的全局分析，而是利用仿真引擎中已有的障碍同步。每个核心在连续障碍之间累积其总活跃时间，而模块级的细分是通过正常任务执行路径上的轻量级软件计时器或等效的硬件计数器差值得到的。在每个时代边界，分析器输出两类运行时摘要。首先，它报告时代级的核心负载^??(??)??，控制器从中得出尾部核心??*=arg2max??2^??(??）（26）和时代级的不平衡指标????=^??(??)??*^ˉ??(??）（27）。其次，它报告在第e时代在尾部核心上执行的模块的每个模块的时代级累计负载估计^??(??)??。这些量被后续的热模块提取和迁移规划阶段所使用。6.2. 热模块提取只有当时代级的不平衡指标满足???? >1 +??时，才触发迁移规划。一旦满足这个条件，控制器就专注于当前尾部核心：模块按^??(??)??降序排列，前K个模块用于构建拓扑感知的（模块，目标）候选者。因此，????仅作为调用迁移规划的时代的门控，而候选模块的排名是由^??(??)??决定的，而不是由比率本身决定的。这一阶段的输出是热模块集??(??)hot。目标扩展、准入评估和冷却过滤被推迟到接下来的阶段。6.3. 检测和规划迁移对于每个属于??(??)hot的热模块??，运行时查询m的通信邻居的当前放置的核心级摘要，并构建一个受限的目标集??(??)2(??)。注意，我们是在相邻核心上扩展候选目标，而不是重新扫描所有相邻模块。这种限制结合了RTL的结构连接性和NUMA拓扑：根据频繁交互的模块的放置来选择候选目标核心，以便尽可能保持迁移的局部性。因此，得到的候选迁移集是??(??)={(??,??*→??)∣??∈??(??)hot,??∈??(??)2(??)}（28）。只有通过运行时的准入不等式形式时，候选者才会被接受：Δ3^??2(??,??*,??)>??current·^Γ2(??,??*,??)+??·^ˉ??然后，每个时期的控制平面开销满足以下公式：
$$
T(e)_{\text{ctrl}} = \mathcal{O}(A_e) + \mathcal{O}(U_e\mathbf{i} \cdot \log_{\mathbf{K}} + \mathcal{O}(\log_{\mathbf{K}}) + \mathcal{O}\left(\sum_{k \in \mathbf{M}(e)\text{hot}\mathbf{r}_k\right) + \mathcal{O}(|A_e^{\text{adm}}),
$$
（32）
其中，$\mathbf{K} = |\mathbf{M}(e)\text{hot}|$ 是固定的热模块预算。由于 $K$ 是固定的，这个公式简化为：
$$
T(e)_{\text{ctrl}} = \mathcal{O}(A_e) + \mathcal{O}(U_e\mathbf{i}) + \mathcal{O}\left(\sum_{k \in \mathbf{M}(e)\text{hot}\mathbf{r}_k\right) + \mathcal{O}(|A_e^{\text{adm}}).
$$
（33）
此外，因为 $U_e\mathbf{i} \leq A_e$ 且 $|A_e^{\text{adm}} \leq \sum_{k \in \mathbf{M}(e)\text{hot}\mathbf{r}_k$，我们有：
$$
T(e)_{\text{ctrl}} = \mathcal{O}\left(A_e + \sum_{k \in \mathbf{M}(e)\text{hot}\mathbf{r}_k\right).
$$
（34）
如果每个执行的任务至少产生 $\sigma > 0$ 单位的有用仿真工作量，那么 $T(e)\sim \sigma A_e$，并且存在依赖于实现的常数 $\mathcal{c}_1, \mathcal{c}_2 > 0$，使得：
$$
T(e)_{\text{ctrl}} \leq \mathcal{c}_1\sigma + \mathcal{c}_2\sum_{k \in \mathbf{M}(e)\text{hot}\mathbf{r}_k\sigma A_e.
$$
（35）
由于 $K$ 是固定的且 $\mathbf{r}_k \leq \mathbf{T}$，第二项被限制在 $\mathcal{c}_2\mathbf{K}\mathbf{T}/(\sigma A_e)$ 内，随着时期包含更多有用工作量，这个值会减小。

**证明：**
控制平面由四个组件组成：
1. **记录任务。**
?????（profiler）依赖于正常的任务执行路径。每次任务完成时，运行时（runtime）使用轻量级的定时器更新工作负载级别的活动时间累加器和相应的模块级别计数器。这是每个执行的任务的一次常数时间记账操作，因此在时期 $e$ 中的总成本是 $\mathcal{O}(A_e)$。

2. **计算热任务。**
在时期边界，运行时识别尾部核心 $\mathbf{i}$ 并仅从尾部核心中提取前 $K$ 个热模块。扫描尾部核心的稀疏活动表的成本是 $\mathcal{O}(U_e\mathbf{i})$；维护大小为 $K$ 的最小堆（min-heap）的成本是 $\mathcal{O}(U_e\mathbf{i}\cdot \log_{\mathbf{K})$；对保留的热模块进行排序的成本是 $\mathcal{O}(\log_{\mathbf{K})$。因此，这一阶段的总成本是 $\mathcal{O}(U_e\mathbf{i}\cdot \log_{\mathbf{K}} + \log_{\mathbf{K})$，由于 $K$ 是固定的，所以简化为 $\mathcal{O}(U_e\mathbf{i})$。

3. **检测和规划迁移。**
对于每个热模块 $\mathbf{k} \in \mathbf{M}(e)\text{hot}$，运行时查询当前通信的核心级别摘要，并在相邻核心上扩展候选目的地，而不是重新扫描所有相邻模块。如果 $\mathbf{r}_k$ 是保留的相邻核心的数量，这一阶段的成本是 $\mathcal{O}\left(\sum_{k \in \mathbf{M}(e)\text{hot}\mathbf{r}_k\right)$。（36）

4. **执行。**
对于每个被允许的迁移，运行时更新模块到核心的映射，并将受影响的未来事件重定向到目标核心。因此，这一阶段的成本是 $\mathcal{O}(|A_e^{\text{adm}})$。

将这四个部分的成本相加，得到上述的界限。由于 $U_e\mathbf{i} \leq A_e$ 且被允许的迁移数量不会超过构建的候选迁移数量，即 $|A_e^{\text{adm}} \leq \sum_{k \in \mathbf{M}(e)\text{hot}\mathbf{r}_k$，（37）简化后的界限随之得出。通过将两边都除以 $T(e)\sim \sigma A_e$，可以得到比率界限。□

**完整时期边界决策流程和系统伪代码**总结在算法 1 中。

**算法 1：时期边界迁移协议**

**要求：**
- 从 profiler 中加载统计信息；
- 分区 $\mathbf{\xi}_e$

**确保：**
- 更新分区 $\mathbf{\xi}_e + 1$

**步骤：**
1. 计算 $\mathbf{i}^* = \arg_{\max}\mathbf{p}^{\mathcal{L}(e)\mathbf{p}$ 和 $\mathbf{Q}_e = \mathcal{L}(e)\mathbf{i}^*/\mathcal{L}^{\text{bar}}(e)$；
2. 如果 $\mathbf{Q}_e \leq 1 + \epsilon$，则返回 $\mathbf{\xi}_e$（在容忍范围内；无需迁移）；
3. 否则：
- $\mathbf{M}(e)\text{hot} \leftarrow \text{SelectHotModules}(i^*)$；
- $\mathbf{A}(e)^{\text{adm}} \leftarrow \emptyset$；
- 对于每个 $\mathbf{m} \in \mathbf{M}(e)\text{hot}$：
- $\mathbf{R}(e)^2(\mathbf{m}) \leftarrow \text{ExpandDestinations}(\mathbf{m}, \pi_e)$；
- 对于每个 $\mathbf{j} \in \mathbf{R}(e)^2(\mathbf{m})$：
- $\mathbf{\Delta}^2(\mathbf{m}, \mathbf{i}^* \rightarrow \mathbf{j})$；
- 估计 $\Delta^2(\mathbf{m}), \Gamma^2(\mathbf{m}), \alpha^2(\mathbf{m})$；
- 如果 $\Delta^2(\mathbf{m}) > \mathcal{f}_{\text{current}}^2(\mathbf{m}} + \epsilon^{\text{bar}}\mathcal{L}(e)$，则：
- 如果 $\mathbf{m}$ 不在冷却期（cooldown）中，则
- $\mathbf{A}(e)^{\text{adm}} \leftarrow \mathbf{A}(e)^{\text{adm}} \cup \{\mathbf{m}\}$；
- 否则结束；
- 结束循环；
3. 在 $\mathbf{A}(e)^{\text{intra}}$ 中执行一级（socket 内）迁移；
4. 在 $\mathbf{A}(e)^{\text{intra}}$ 中执行二级（socket 间）迁移；
5. 返回 $\mathbf{\xi}_e + 1$。

**7. 实验评估**
本节描述了实验设置、基准测试、指标以及用于验证理论界限和端到端系统性能的实验。

**7.1. 实验设置**
**硬件平台。**
所有实验都在一台 2-socket 的 Intel Xeon Gold 6226R 服务器上进行，该服务器的基础频率为 2.90 GHz，每个 socket 有 16 个物理核心（32 个硬件线程），每个 socket 有 22 MB 的 LLC（内存），每个 NUMA 节点有 377.2 GB 的本地 DRAM。两个 socket 通过 Intel UPI 连接。启用了超线程。由于我们的基准测试规模较小，我们使用每个 socket 4 个核心（8 个线程），即总共 8 个核心（16 个线程）。

**仿真基础设施。**
我们在 TACVS（Topology-Aware Admission Control Verilog Simulator）中实现了所提出的拓扑感知准入控制（TAC）框架，这是一个事件驱动的并行 RTL 仿真器。在整篇论文中，TAC 指决策框架/策略，而 TACVS 表示实现 TAC 的仿真器。基线静态分区器使用 PaToH [3]（版本 3.2）根据 RTL 连通性图生成初始的模块到核心的分配。

**比较方法。**
我们比较了以下方法：
- **仅静态（Static-Only）：** 无运行时迁移的静态 Graph 分区。
- **工作窃取（Work-Stealing，WS）：** 典型的工作窃取方法，随机选择受害者。
- **分层工作窃取（Hierarchical Work-Stealing，HWS）：** 分层工作窃取方法，首先在同一个 socket 内探测受害者，只有在本地探测失败后才扩展到远程 socket。
- **启发式混合（Heuristic-Hybrid，HH）：** 使用固定经验阈值的静态分区与迁移相结合的方法。
- **提出的方法（TAC）：** 本文提出的拓扑感知准入控制框架。

**HWS** 作为相同事件驱动仿真器堆栈中的更强有力的 NUMA 感知基线。

**全局配置。**
除非另有说明，我们将时期长度设置为 $\mathcal{T}_e = 100$，$\epsilon = 0.1$。TAC 使用冷却期 $\mathcal{C}_d = 5$ 个时期。

**备注 6.** $\mathcal{T}_e = 100$ 的选择分为两步：**
首先，推论 2 为目标平台提供了 $\mathcal{T}_e$ 的保守下限规模。其次，我们使用第 7.3 节中的 turbo 8051 SoC 基准测试来识别该可行范围内的高吞吐量操作点。然后我们在其余实验中保持这个值不变，以确保一致性和可重现性。这并不意味着所有测试用例都具有完全相同的最优值；而是将 $\mathcal{T}_e = 100$ 视为所研究平台和 workload 类的稳健默认值。实验5：开销分析
在本部分中，我们报告了第6.5节介绍的四个控制平面组件（记录任务、计算热点任务、检测和计划迁移以及执行）的实际开销分解，并将这些测量结果与分析得出的轻量级性结果（表3）进行对比。表3显示了在turbo 8051 SoC上每个周期的控制平面开销分解情况。表中的数值来源于具体的turbo 8051 SoC运行时跟踪数据。CPU周期数值四舍五入到最接近的102个周期，运行时间份额数值则根据未经过四舍五入的测量结果计算得出，并保留两位小数。我们有意报告四舍五入后的数值，以便强调数量级的变化，而不是精确到每个周期的可重复性，因为缓存驻留时间、队列状态和其他微架构因素会导致 pequenas 波动。

从表格可以看出，主要开销来源于“记录任务”组件，这是每个模拟任务中唯一会被执行一次的组件，而其余的决策逻辑只带来了少量的额外开销。

8. 结论
本文提出了一种基于拓扑结构的 Admission Control (TAC) 框架，用于 NUMA 支持的并行 RTL 仿真中的动态负载平衡。通过将尾延迟减少、迁移开销和缓存重新加热成本建模为一个统一的净收益函数，我们推导出了一个准入测试（推论1）、一个保守的频率/周期规模可行性条件（推论2）以及在初始分区质量良好的情况下的迁移量上限（定理2）。该框架在 TACVS 中实现，并在2-socket NUMA平台上通过四个开源RTL基准测试进行了评估。与不考虑拓扑结构的基线相比，所提出的方法平均降低了18.0%的尾延迟比率（最高可达28.5%），同时平均提高了27.1%的标准化吞吐量（最高可达34.1%）。消融研究进一步表明，准入控制和冷却处理是两个最关键的组件。