2022, Vol. 33
2. 国家超级计算长沙中心, 湖南 长沙 410082
2. National Supercomputing Center in Changsha, Changsha 410082, China
在进行电路设计时, 为了保证设计电路的正确性需要对电路进行功能验证. 常用的功能验证有两种方法, 一种是基于软件工具对电路逻辑进行验证, 另一种则是借助硬件加速器[1,2]实现. 硬件加速器提供的性能比软件工具要多几个数量级. 通常情况下基于软件工具的模拟验证周期需要数月, 而使用硬件加速器的验证周期则可被缩短至几天甚至几个小时[3], 极大降低了验证环节的时间成本. 同时, 随着电路设计中门原语规模的不断扩大, 需要将一个大型电路划分成多个小规模子电路, 以便能够放置在多个加速处理器或芯片上. 但是不同芯片(处理器)之间的高延迟和带宽限制, 应该最大化电路层次结构中每一层的连接, 确保对每个单元的评估可以路由到它的下游, 而尽可能少的在任何一条路径上造成过多的延迟. 虽然在学术界和工业界, 类似的电路划分问题被建模为图划分问题. 但是用于硬件加速功能验证的划分问题不同于传统的图划分问题, 如用于电路布局的图划分问题[4,5]. 在传统的图划分问题中, 通常以最小边割[5-7]为划分目标. 但是在不同电路分区之间并行的进行功能验证, 还应考虑电路门间信号的时序依赖性, 切边引起的通信时延和划分后模拟调度的并行性. 通过划分算法解决硬件加速功能验证问题是为了缩小问题规模, 使划分后的子集能在不同的硬件加速器上并行的进行调度, 以大幅缩小电路验证环节的验证周期. 因此, 硬件加速功能验证的划分是一个需要将图划分思想和调度思想相结合的复杂问题.
应用在电路设计领域的传统图划分问题总以最小边割为划分目标, 追求划分后各个分区间的低通信时延. 与其他划分算法相比, 多级图划分策略具有更高的效率和更好的划分结果. 多级图划分模式将整个划分过程分成3个阶段, 首先通过合并顶点来减少顶点数直至图的规模达到最小, 再对规模最小的图执行初始划分; 然后不断移动调整各分区边界的顶点来优化划分质量. 而硬件加速功能验证问题在追求分区间通信时延较小的基础上, 需要保证划分结果的可调度性以及调度的并行性. 因此为了有效的解决VLSI物理设计中硬件加速功能验证的划分问题, 本文提出一种基于调度思想的有向无环图(directed acyclic graph, DAG)多级划分算法. 该算法在传统多级划分模式基础上, 以DAG为划分模型, 使用电路的拓扑时序信息和关键路径信息对边权进行预处理, 使边权对关键路径敏感, 从而更易选择符合调度需求的切边; 并提出了基于rankDown策略的粗化算法, 并实现了对关键路径敏感的匹配模式, 以更有效地处理电路划分的时序依赖, 提高模拟调度的并行性.同时本文提出算法不会导致切边数的恶化, 减少了由于切边引入的通信时延.
本文第1节进行相关工作的总结. 第2节简单介绍硬件加速功能验证问题并对其进行问题建模. 第3节详细介绍本文提出算法的构造过程, 重点阐述如何使用关键路径信息和电路时序信息对边权进行预处理, 以及基于rankDown策略改进的粗化方法. 第4节介绍实验所需环境和数据集以及对实验结果的详细分析. 第5节给出结论以及进一步的研究方向.
1 相关工作最早VLSI领域中提出的划分问题是为了解决电路布局的规模巨大, 芯片制造工艺以及电路设计工具的局限性等设计问题. 通用的解决方案是采用分治思想, 将电路划分成规模均等的子集, 从而将对大规模电路的复杂处理转化为对子电路的设计. 因此传统的电路划分问题都是以最小边割为划分目标, 尽可能地减少划分后的通信时延. Allam等人[8]使用贪婪的聚类算法进行电路划分, 该算法首先生成一个好的初始划分, 然后使用模块交换方法来提高初始划分效果; Kolar等人[9]提出使用模拟退火算法解决图划分问题; Sipakoulis等人[10]为电路划分提出了改进的遗传算法, 该算法可以在搜索过程中通过评估算法表现迭代的动态更新交叉速率, 变异速率等算法参数, 不断的提高算法能力; Guo等人[11]提出了一种基于遗传操作的混合粒子群优化算法对电路进行划分, 并使用FM策略[12]提高算法的局部搜索能力, 同时采用多样性变异策略来避免算法陷入局部最优; Karypis等人[13,14]比较了多级划分模式的多个阶段, 提出了改进的粗化方案和KL算法[15]并对多级划分算法的能力做出了理论分析. 但是硬件加速功能验证的划分问题与传统的电路划分问题的划分目标并不相同. 硬件加速功能验证问题相较于切边引入的通信时延更关注划分结果的调度性. 因此, 以最小边割为划分目标的多级图划分策略并不能较好的解决硬件加速功能验证的划分问题.
Moffitt等人[16]在多级图划分策略的基础上, 考虑电路的时序依赖进行了超图建模; 并通过优化关键路径和有向切边来进一步降低模拟执行的指令深度, 最大化机器指令内存限制下的并行性. 同时, 在真实电路环境中的实验结果中证明了该算法的有效性. 该算法的不足之处在于其划分性能. 和传统图划分算法的划分结果相比, 尽管该算法有效的减少了模拟深度, 但切边数却数倍增加. 并且该算法的实现较为复杂, 也并未在划分阶段考虑由于切边引入的时延.
因此, 我们所在课题组为了进一步构造硬件加速功能验证问题的优化解法, 重新对硬件加速功能验证问题进行了调研建模, 提出了一种有向图的划分算法. 该算法以多级图划分模式为基础, 以减少关键路径长度为划分目标; 将电路网表建模成带权的有向无环图, 并利用路径信息和电路时序信息进行边权预处理使其对关键路径敏感; 同时也构造了一种基于rankDown策略的粗化算法, 来更好的处理图划分模型的有向性和时序性. 基于随机网表的划分实验结果证明了本文提出算法在有效降低关键路径长度的同时能保证切边数不会恶化, 验证了算法的有效性和鲁棒性. 后文将详细介绍问题的描述和算法的具体构造.
2 问题建模电路设计中的功能验证环节目的是确保芯片或系统的逻辑符合执行规范. 而对功能验证实行硬件加速可以解决电路设计验证环节中时间成本较高的问题. 硬件加速功能验证的划分问题就是将待验证电路划分成多个子集, 然后在硬件加速器上并行的执行调度, 以此缩短验证周期, 提高验证效率. 图1(a)是一个待验证的电路网表, 其中模块a–j表示电路的标准执行单元. 图1(b)表示对电路网表进行划分后的调度情况, 其中黑色圆点表示当前时刻处理器处于空闲状态. 在网表的执行逻辑中, 单元的顺利执行往往依赖于前一单元的输出, 例如单元e的执行依赖于单元b, c的执行输出. 因此在逻辑时序关系上, 单元e的执行往往晚于单元b, c. 对于任意给定的逻辑顺序, 都可以构建一个模拟调度序列. 这里假设将待验证的电路划分至两个支持并行处理的处理器上进行模拟调度. 其中处理器 P1模拟调度的最大指令深度为5, 处理器 P2的最大指令深度为6. 图1(b)中由于执行单元a, b, c, e不依赖于单元的d, f, h的输出, 因此a, b, c, e和d, f, h可以被划分至P1, P2两个处理器上并行执行. 由于单元g依赖于单元e的输出, 当单元e在处理器P1上执行时, 处理器P2此时刻就会出现空闲等待. 将图划分模型中的每个顶点视作一个消耗单位时间的执行指令, 模拟深度表示的是多个处理器并行调度划分结果的最大指令长度. 模拟深度也可反映处理器进行并行调度的最大执行时间. 针对同一个图模型的不同划分结果, 划分后的模拟深度越小, 表示处理器并行处理的时间越少, 划分结果的调度并行性越高. 因此, 针对硬件加速功能验证的划分问题, 需要在划分过程中降低模拟深度, 尽量减少处理器空闲等待时间, 来提高模拟调度并行性.
|
图 1 电路网表划分调度实例 |
硬件加速功能验证问题与DAG调度问题类似. 在DAG调度中, 任务被抽象成DAG中的顶点, 任务之间的依赖被抽象成DAG中的有向边. DAG调度的基本目标是把不同且独立的任务分配到不同的处理器中, 使所有任务的处理时间总和最短. DAG调度问题同样是一个完全NP问题. 已存在的启发式算法有基于表的算法, 例如HEFT调度算法[17], HSV调度算法[18]; 基于聚类的DAG调度算法, 例如CMWSL[19]. 然而, DAG调度算法的复杂性普遍较高且很难处理硬件加速功能验证等大规模调度问题[17,20,21]. 本文将结合DAG调度思想使用多级图划分策略来解决硬件加速功能验证问题.
2.1 划分目标图2展示了使用不同的划分方式将同一个图模型划分至两个处理器上时处理器调度的差异. 其中不同顶点之间的传输时延均设置为1, 顶点自身处理时延忽略不计, 切边引入的通信时延设置为2. 图2中有向图的关键路径为
|
图 2 不同划分方式在调度方面的区别 |
2.2 DAG建模
在传统图划分算法中, 一些划分算法使用简单无向图作为划分模型[13], 部分划分算法使用无向超图或者有向超图进行建模[16,22,23], 也有部分研究[24,25]基于DAG提出了多级划分算法. 文献[24]提出一种DAG的多级无环划分算法, 并提出一种直接k-way划分模式. 文献[26]为了提高多级划分算法的划分质量, 提出了一种基于最大流-最小边割和FM算法的局部改进算法以及基于多网格线性解的全局搜索策略. 但诸多划分算法的划分目标通常为最小边割, 旨在减少切边引入的通信时延, 且并未在划分算法中考虑划分结果的可调度性以及关键路径在划分算法中的影响. 文献[16]在解决硬件加速功能验证问题时, 将电路建模成有向无环超图(directed acyclic hypergraph, DAH), 其中每个顶点代表电路的一个标准单元, 每条有向超边代表电路中上游单元至下游单元的连接. 对于超图模型, 一条超边被切割对应着电路中多条连接被切割. 图3展示了在DAG和DAH模型中切割电路中同一条连接的情况. 从图3可知, 当切割单元f到单元i之间的连接时, DAG模型中顶点f到顶点i的有向边会被切割; 而在DAH模型中, 单元f和单元h, j, i中任意一个之间的连接被切割时, 对应着的都是DAH中的同一条超边被切割. 第2.1节中分析了关键路径对于提高划分结果调度并行性的重要性. 当使用DAH作为划分模型时, 切割多条连接对应的都是关键路径上同一条边被切割, 从而导致DAH划分结果的关键路径长度不能准确表示划分结果被模拟调度的情况. 显然, 关键路径思想并不能很好的和DAH划分结合. 本文第3.1节介绍的边权预处理策略需要计算每条边的路径信息, 而DAH划分模型同样不能很好的表达电路的有向路径信息. 因此, 本文基于DAG划分模型, 将电路转换成DAG 型并对其进行拓扑时序分析, 从而得到每个顶点的拓扑时序信息和每条边的路径信息. 同时, 本文提出的边权预处理策略和改进的粗化方法也将结合DAG模型进一步, 降低模拟深度, 提升调度并行性.
|
图 3 DAG和DAH中切割同一条连接的情况 |
2.3 问题形式化定义
定义
硬件加速功能验证的划分问题就是将V中的顶点划分到数量均等的K个子集
| $ {\rm{min}}\left\{ {{\max_{e \in E}}\{ path(e)\} } \right\} $ | (1) |
| $ {\rm{s.t.}}\left\{ {\begin{array}{*{20}{l}} {\max\left\{ ({\rm{max}}\left\{ {{r_{ij}}} \right\} - {\rm{avg}}\left\{\displaystyle \sum\nolimits_{i = 1}^k {{r_{ij}}} \right\} )/{\rm{avg}}\left\{ {\displaystyle\sum\nolimits_{i = 1}^k {{r_{ij}}} } \right\},({\rm{avg}}\left\{ {\displaystyle\sum\nolimits_{i = 1}^k {{r_{ij}}} } \right\} - {\rm{min}}\left\{ {{r_{ij}}} \right\})/{\rm{avg}}\left\{ {\displaystyle\sum\nolimits_{i = 1}^k {{r_{ij}}} } \right\}\right\} \leqslant imbalance}\\ {\displaystyle\sum\nolimits_{i = 1}^k {{r_{ij}}} \leqslant {R_j},{R_j} \in \{ {R_1},{R_2},{R_3}, \ldots ,{R_m}\} }\\ {{V_1} + {V_2} + \ldots + {V_k} = V,{V_a} \cap {V_b} = \mathrm{\varnothing } ,a,b \in 1, \ldots ,k} \end{array}} \right. $ | (2) |
其中,
本文构造的算法基于传统多级图划分模式, 以减少关键路径长度为划分目标, 注重提高对划分结果执行调度的并行性. 同时, 电路中各单元间存在的通信时延是影响电路功能验证效率的重要因素. 而切边会破坏电路单元间的时序关系, 引入不必要的通信时延. 因此切边数也是划分过程中的重要考量因素. 针对时延问题, 本文在计算关键路径敏感的新边权时将考虑电路单元本身的处理时延, 以及在计算划分结果的关键路径长度时考虑切边引入的通信时延, 同时使用DAG对电路进行建模. DAG和DAH在划分时的差异见本文第2.2节. 图4为本文构造算法的基本框架图. 在该算法中, 首先通过对整个电路模型进行拓扑时序分析计算顶点的时序信息和路径信息, 再结合顶点的时序信息重新计算边权, 使每条边的边权对关键路径敏感; 然后根据顶点的拓扑时序信息计算出粗化阶段的待访问顶点队列, 对待访问顶点执行约束判断并合并满足约束条件的顶点对(即匹配)直至粗化图的顶点数足够小; 再对最小的粗化图执行初始划分; 最后在细化阶段使用增益调整策略对分区边界的顶点进行调整, 直至图恢复至原始图. 本节将详细介绍算法的构造过程.
|
Fig. 4 The framework of the algorithm in this paper 图 4 本文构造算法框架图 |
3.1 权重预处理
文中第2.1节介绍了不同的划分方式对划分结果可调度性的影响. 在划分过程中, 减少对关键路径的破坏可以更少地破坏电路单元间的时序关系, 提高划分结果的调度并行性. 因此, 如何将关键路径信息融入到划分过程中成为关键. 为此, 首先定义表示顶点拓扑时序信息的rankDown值和rankUp值, 计算见公式(3)和公式(4). 顶点p的rankDown信息描述的是沿着有向边的方向由入度为0的顶点开始到顶点p的最长路径长度, 顶点p的rankUp信息描述的是沿着有向边的反方向由出度为0的顶点开始到顶点p的最长路径长度.
| $ \textit{rankDown}\left( p \right) = {\max_{{p_i} \in inputs\left( p \right)}}\left( {\textit{rankDown}\left( {{p_i}} \right) + {W_d}({p_i}) + {W_e}\left( {\left\langle {{p_i},p} \right\rangle } \right)} \right) $ | (3) |
| $ \textit{rankUp}\left( p \right) ={\max_{{p_i} \in outputs\left( p \right)}} (\textit{rankUp}( {{p_j}} ) + {W_d}({p_j}) + {W_e}(\langle {{p_j},p} \rangle ))) $ | (4) |
其中,
然后, 根据公式(5)使用拓扑时序信息定义DAG中包含有向边e的所有路径中最大的路径长度.
| $ path\left(e\right)=\mathit{rank}\mathit{Down}\left(source\right(e\left)\right)+{W}_{e}\left(e\right)+\textit{rankUp}\left(sink\right(e\left)\right)$ | (5) |
其中,
最后, 为了充分利用多级划分过程中的关键路径信息, 重新定义了新边权
| $ {path}_{\min}=\underset{e\in E}{\mathrm{min}}\left(path\right(e\left)\right) $ | (6) |
| $ {W}_{e}'\left(e\right)=path\left(e\right)-{path}_{\min} $ | (7) |
在对电路进行DAG建模时, 初始边权代表着电路中该边连接的上游单元和下游单元之间的传输时延. 为了构造关键路径敏感的划分策略, 基于DAG划分模型的初始边权再利用公式(3)–公式(7)计算出新边权
多级划分算法中的粗化阶段可大致分为3个步骤: (1)构造随机待匹配序列, 选择未被匹配顶点作为待匹配顶点; (2)待匹配顶点与其未匹配邻接顶点执行匹配模式, 构造全局匹配映射; (3)根据匹配映射构造下一级图结构. 在多级划分的粗化中, 随机匹配模式[13]中合并顶点对的选择随机性较强, 而最大边权匹配模式[13]对于顶点的匹配只简单进行边权的比较而不考虑路径信息对调度的影响. 因而简单的多级划分算法不足以满足硬件加速功能验证的划分问题对于调度并行性的需求. 为此, 本节基于顶点的rankDown值重新设计了粗化方法并改进了两种匹配模式.
基于rankDown策略的随机匹配模式: 按照顶点rankDown值递增的顺序构造待匹配序列. 首先遍历待匹配访问序列, 为当前未匹配顶点随机选择一个未匹配邻接顶点进行匹配; 然后判断这两个顶点合并后是否满足资源负载均衡; 并将匹配过的两个顶点均标记为已匹配状态. 在这个过程中, 将边权按照加权取和的规则进行动态更新. 如果有多个顶点可与待匹配顶点进行匹配, 则选择具有较低rankDown值的顶点进行匹配.
基于rankDown策略的最大边权匹配模式: 按照顶点rankDown值递增的顺序构造待匹配序列. 首先遍历待匹配访问序列, 在其邻接边列表中找到具有最大边权的有向边, 同时判断这两个顶点合并后是否满足资源负载均衡; 然后合并由最大边连接的两个顶点. 由于更新后的边权是关键路径敏感的, 较大边权的边位于关键路径上的可能性更高. 此时顶点的匹配可避免后续划分过程中该有向边被切割, 从而更好地保护关键路径不被切割, 保证调度的并行性. 同时, 边权进行加权取和的更新. 如果存在多个顶点可以与当前待匹配顶点进行匹配, 将rankDown值较低的顶点作为与之匹配的顶点. 此时, 若有多个顶点具有相同的rankDown值, 则取序列号较低的顶点进行匹配.
由于顶点的rankDown值和rankUp值只是从不同的方向性描述DAG的拓扑时序信息, 因此在改进的两种匹配模式中仅选用顶点的rankDown值作为构造访问序列和匹配的影响因子. 在本文算法实现中, 粗化阶段将混合使用这两种改进后的匹配模式. 改进后的粗化步骤如下.
(1)按照顶点rankDown值递增的顺序构造待匹配序列, 选择未匹配顶点作为待匹配顶点;
(2)执行改进的随机匹配模式或者最大边权匹配模式, 构造顶点匹配映射;
(3)根据顶点匹配结果构造下一级粗化图结构并维持顶点点权以及rankDown值和rankUp值的动态更新.
3.3 算法步骤本文所构造的多级划分算法伪代码如下. 在本文构造算法中, 首先使用转换函数
算法1. 以关键路径为目标的多级划分算法.
输入: 电路网表数据data;
输出: 划分结果partition.
1. 图结构graph, 顶点集合P, 有向边集合E, 待访问顶点序列perm, 分区结果partition, 匹配映射match, 粗化比例COARSEN_FRACTION;
2.
3. for p in P
4.
5.
6. for e in E
7.
8.
9. for e in E
10.
11.
12. while
13. match =
14.
15.
16. end while
17.
18.
针对电路硬件加速功能验证的划分问题, 本文仅考虑以减少划分结果的关键路径长度为划分目标的情况. 算法采用划分目标作为主要评估函数, 以划分后产生的切边数作为辅助评估函数, 具体定义如下:
| $ f1={\max _{e \in E}}\left\{path\right(e\left)\right\} $ | (8) |
| $ f2=\sum\nolimits _{i=1}^{k}\sum\nolimits _{j=i+1}^{k}{L}_{ij} $ | (9) |
其中, E表示有向图模型的有向边集合,
本文算法使用编程语言C++进行实现, 本文涉及的所有实验均在主频为2.5 GHz的Intel(R) Xeon(R) Gold 5118处理器, 内存为264 GB, 操作系统为Ubuntu的服务器环境下进行测试. 为了尽可能避免实验测试结果的偶然性, 本文将使用GNL随机网表生成工具(官方网址:
|
Table 1 Specification of the benchmark dataset 表 1 测试数据集说明 |
GNL是一种生成逻辑电平基准电路的工具. GNL的电路生成是基于自上而下的递归聚类, 将子模块(电路)合成更大规模的模块直至生成完整的电路; 同时模块的生成遵循一定的电路生成准则, 该准则可以防止逻辑环的形成, 并且可以在模块生成过程中控制其最长路径长度. 由于GNL生成工具是按照递归聚类的方式将子模块组合成最终电路网表, 导致其生成较大规模的电路数据时效率较低. 为了提高随机网表数据的生成效率, 我们使用了一种拼接方案; 该方案将GNL工具生成的多个小规模电路网表拼接成较大规模的网表数据, 以此来提高网表数据生成效率. 同时, 在GNL工具生成随机网表数据后, 利用电路单元输入输出端口之间的映射关系将整个网表转换成将带权的有向无环图. 转换后有向图的无环性依赖于GNL生成网表的无环性.
4.2 算法有效性分析为了分析本文构造算法的有效性, 对METIS划分算法、使用原有粗化方法和边权预处理策略的METIS算法(METIS only with preprocessing edge-weigh, METISPW)、结合
|
|
Table 2 Experimental resuslts 表 2 实验结果 |
4.2.1 算法的有效性
本文从分区数, 切边权重和点权以及边权多个变化维度来对数据集进行综合划分测试, 并取平均关键路径长度和平均切边数作为实验结果来进行算法对比. 表2为本文不同策略下划分数量不同时对实验数据集的测试结果, 同时指定切边权重为常数40再测试划分后的关键路径长度. 从表2 的实验结果可以看出, 多种算法不可避免都会导致划分之后的关键路径长度较原始图有所增加. METISPW算法划分后的关键路径长度相比于METIS算法有显著减少, 且切边数仅微弱幅度的增加. 结合边权预处理策略和改进粗化策略的METISRP算法较METISPW算法的划分结果有了进一步的提升. 虽然METISRP算法的实验结果并未全部优于METISPW算法, 但是METISRP算法对各数据集进行划分后的平均关键路径长度小于METISPW算法, METISPW算法较原始METIS划分结果的平均关键路径优化幅度为15%左右, METISRP算法的平均关键路径长度优化幅度为17%左右. 但由于边权预处理策略和改进粗化策略的加入, METISRP算法和METISPW算法产生的切边数相较于METISPW算法的划分结果呈现了微弱的增长趋势, METISRP算法和METISPW算法的平均切边数增长幅度均在9%左右.
表2中同样展示了hMETIS的实验结果. 除了在分区数量为5时的实验结果稍劣于hMETIS算法, 在其余划分情况下, METISRP算法和METISPW算法的划分结果均优于hMETIS算法. 针对算法的整体执行时间, METISRP算法较原始METIS算法仅增加了维护
以上实验结果反映出, 仅基于METIS算法对输入图进行边权预处理形成的METISPW算法, 其实验结果与METIS算法相比实验结果上有明显提升. 并且再加入
但是由于多级划分算法的启发式性质, 划分算法的划分结果并不总是较优的; 且粗化方法, 初始划分和细化方法都有随机选择访问顶点的操作, 多级划分算法的划分结果会在合理的范围内波动; 同时最大边权匹配不能一直保持高效的顶点合并效率, 在某些划分分数时划分算法会由于粗化阶段顶点合并不充分降低划分质量; 以上多种因素都可能会导致本文提出算法的划分结果发生波动, 导致划分结果的关键路径长度出现逆增长的现象. 文献[27]为了解决粗化过程中顶点匹配不充分而导致划分质量下降的情况, 基于最大边权匹配模式提出brotherly matching模式, adoption matching模式和community matching模式来提高顶点匹配效率, 优化粗化质量. 与METIS算法和hMETIS算法的实验结果对比, 可以验证本文提出算法的有效性. 在以关键路径长度为主要划分目标的划分问题上, 本文提出的算法思想行之有效.
4.2.2 算法的鲁棒性在划分实验中存在许多因子会影响算法的整体划分结果, 例如待划分的图规模, 分区数, 计算关键路径长度时赋予切边的权重值以及点权和边权等. 为了探究在一些划分因素发生变化时本文提出算法是否可以继续保持划分结果的有效, 本文分别进行了分区数不同和切边权重不同时的划分实验. 图5展示了在切边权重等其他因素一定时, 不同的划分算法对同一数据集gnl100w划分后的关键路径长度的平均减少幅度. 图6展示了在切边权重等其他因素一定时, 算法对数据集gnl500w划分后的关键路径长度的平均减少幅度. 图5和图6展示的实验结果均以METIS算法的划分结果为对比基准. 从图5可以看出, 对于不同的划分分区数, METISPW算法和METISRP算法划分后关键路径长度的平均减少幅度基本上能稳定维持在10%左右; 从图6可以看出, 对于不同的划分分区数, METISPW算法和METISRP算法划分后关键路径长度的平均减少幅度也可稳定维持在15%~18%范围内. 而hMETIS算法对数据集gnl100w和数据集gnl500w进行划分得到的实验结果相差较大; 从图5可以看出, hMETIS算法划分后的关键路径长度的平均减少幅度仅在3%~4%左右; 从图6可知, 在对数据集gnl500w进行划分时, hMETIS算法划分后的关键路径长度又出现大量逆增长的情况, 平均减少幅度为−2%左右. 同时, 虽然用于本文实验的数据集的点数和边数均在数百万级别, 但是随着图规模的增大, 本文提出的METISRP算法仍能有效减少关键路径长度并保证切边数不出现恶化情况, 仍然保持着较优的划分结果.
|
Fig. 5 Partition result of gnl100w with different partitions 图 5 分区数不同时, 对数据集gnl100w的划分结果 |
|
Fig. 6 Partition result of gnl500w with different partitions 图 6 分区数不同时, 对数据集gnl500w的划分结果 |
在硬件加速器对划分结果的模拟调度中, 切边权重值表示由于不同分区间存在依赖关系从而引入的通信时延, 此时切边权重值越大, 则调度过程中分区之间通信代价越大. 而划分后关键路径长度的计算依赖于切边的权重值, 所以不同的切边权重也会导致不同的划分结果. 图7展示了当分区数固定为200, 切边的权重值不同时, 各个算法对数据集gnl500w划分后关键路径长度的减少幅度. 从图7可以看出, 在设置不同的切边权重后, METISRP算法和METISPW算法划分后的关键路径长度几乎均能保持6%~16%左右的有效减少. 而当切边权重值不同时, hMETIS算法的实验结果波动较为明显, 并且出现了关键路径长度大幅增加的情况. 从以上实验结果可知, 当某些划分因素变化时, 本文提出的METISRP算法可一直保持着关键路径长度的有效减少, 实验结果较其他划分算法鲁棒性更强.
|
Fig. 7 Partitioning result for gnl500w when the weight of cutting edge is different 图 7 切边权重不同时, 对数据集gnl500w的划分结果 |
5 结束语
为了解决VLSI领域硬件加速功能验证的划分问题, 针对已有算法[16]在降低模拟深度的同时切边数急剧增长的性能缺陷, 本文提出一种有效且鲁棒的图划分算法, 该算法基于传统多级图划分模式并结合调度思想, 对DAG模型进行划分. 已有实验可以证明该算法在有效减少模拟深度的同时切边数只会小幅增加, 不会出现切边数恶化的情况, 减少了不必要引入的通信时延, 同时维持了分区结果的资源负载平衡. 本文下一步工作方向是探索多级划分中细化算法的改进以及其他启发式算法是否会进一步优化关键路径指标, 并探究功能验证时的多维权重约束问题, 以及探究强化学习在该问题上的应用.
致谢 在此, 我们向为本文工作提供修改意见的匿名审稿人表示衷心的感谢.
| [1] |
Mammo BW. Reining in the functional verification of complex processor designs with automation, prioritization, and approximation [Ph.D. Thesis]. Ann Arbor: The University of Michigan, 2017.
|
| [2] |
Blank T. A survey of hardware accelerators used in computer-aided design. IEEE Design & Test of Computers, 1984, 1(3): 21-39.
[doi:10.1109/MDT.1984.5005647] |
| [3] |
Schubert KD. POWER7: Verification challenge of a multi-core processor. In: Proc. of the 2009 Int’l Conf. on Computer-Aided Design. San Jose: ACM, 2009. 809–812.
|
| [4] |
Chandy JA, Banerjee P. A parallel circuit-partitioned algorithm for timing driven cell placement. In: Proc. of the Int’l Conf. on Computer Design VLSI in Computers and Processors. Austin: IEEE, 1997. 621–627.
|
| [5] |
Gao T, Vaidya PM, Liu CL. A new performance driven placement algorithm. In: Proc. of the 1991 IEEE Int’l Conf. on Computer-Aided Design Digest of Technical Papers. Santa Clara: IEEE, 1991. 44–47.
|
| [6] |
Hill D. Alternative strategies for applying min-cut to VLSI placement. In: Proc. of the 1988 IEEE Int’l Conf. on Computer Design: VLSI. Rye Brook: IEEE, 1988. 440–444.
|
| [7] |
Mak WK. Faster min-cut computation in unweighted hypergraphs/circuit netlists. In: Proc. of the 2005 IEEE VLSI-TSA Int’l Symp. on VLSI Design, Automation and Test, 2005. (VLSI-TSA-DAT). Hsinchu: IEEE, 2005. 67–70.
|
| [8] |
Allam MW, Vannelli A, Elmasry MI. A clustering algorithm for circuit partitioning. In: Proc. of the CCECE1997. Canadian Conf. on Electrical and Computer Engineering. Engineering Innovation: Voyage of Discovery. Conf. Proc. St. John’s: IEEE, 1997. 12–14.
|
| [9] |
Kolar D, Puksec JD, Branica I. VLSI circuit partition using simulated annealing algorithm. In: Proc. of the 12th IEEE Mediterranean Electrotechnical Conf. (IEEE Cat. No. 04CH37521). Dubrovnik: IEEE, 2004. 205–208.
|
| [10] |
Sipakoulis GC, Karafyllidis I, Thanailakis A. Genetic partitioning and placement for VLSI circuits. In: Proc. of the 6th IEEE Int’l Conf. on Electronics, Circuits and Systems (Cat. No. 99EX357). Paphos: IEEE, 1999. 1647–1650.
|
| [11] |
Guo WZ, Chen GL, Xiong NX, Peng SJ. Hybrid particle swarm optimization algorithm for VLSI circuit partitioning. Ruan Jian Xue Bao/Journal of Software, 2011, 22(5): 833−842 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3980.htm
|
| [12] |
Fiduccia CM, Mattheyses BM. A linear-time heuristic for improving network partitions. In: Proc. of the 19th Design Automation Conf. Las Vegas: IEEE, 1982. 175−181.
|
| [13] |
Karypis G, Kumar V. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal of Scientific Computing, 1998, 20(1): 359-392.
[doi:10.1137/S1064827595287997] |
| [14] |
Karypis G, Kumar V. Analysis of multilevel graph partitioning. In: Proc. of the 1995 ACM/IEEE Conf. on Supercomputing. San Diego: IEEE, 1995. 29.
|
| [15] |
Kernighan BW, Lin S. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 1970, 49(2): 291-307.
[doi:10.1002/j.1538-7305.1970.tb01770.x] |
| [16] |
Moffitt MD, Sustik MA, Villarrubia PG. Robust partitioning for hardware-accelerated functional verification. In: Proc. of the 48th Design Automation Conf. San Diego: ACM, 2011. 854–859.
|
| [17] |
Topcuoglu H, Hariri S, Wu MY. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans. on Parallel and Distributed Systems, 2002, 13(3): 260-274.
[doi:10.1109/71.993206] |
| [18] |
Xie GQ, Li RF, Li KQ. Heterogeneity-driven end-to-end synchronized scheduling for precedence constrained tasks and messages on networked embedded systems. Journal of Parallel and Distributed Computing, 2015, 83: 1-12.
[doi:10.1016/j.jpdc.2015.04.005] |
| [19] |
Kanemitsu H, Hanada M, Nakazato H. Clustering-based task scheduling in a large number of heterogeneous processors. IEEE Trans. on Parallel and Distributed Systems, 2016, 27(11): 3144-3157.
[doi:10.1109/TPDS.2016.2526682] |
| [20] |
Liu CB, Li KL, Liang J, Li KQ. COOPER-SCHED: A cooperative scheduling framework for mobile edge computing with expected deadline guarantee. IEEE Trans. on Parallel and Distributed Systems, 2019.
|
| [21] |
Zhao S, Dai XT, Bate I, Burns A, Chang WL. DAG scheduling and analysis on multiprocessor systems: Exploitation of parallelism and dependency. In: Proc. of 2020 IEEE Real-time Systems Symp. Houston: IEEE, 2020. 128–140.
|
| [22] |
Karypis G, Aggarwal R, Kumar V, Shekhar S. Multilevel hypergraph partitioning: Applications in VLSI domain. IEEE Trans. on Very Large Scale Integration (VLSI) Systems, 1999, 7(1): 69-79.
[doi:10.1109/92.748202] |
| [23] |
Karypis G, Kumar V. Multilevel k-way hypergraph partitioning. In: Proc. 1999 Design Automation Conf. (Cat. No. 99CH36361). New Orleans: IEEE, 1999. 343–348.
|
| [24] |
Herrmann J, Kho J, Uçar B, Kaya K, Çatalyürek ÜV. Acyclic partitioning of large directed acyclic graphs. In: Proc. of the 17th IEEE/ACM Int’l Symp. on Cluster, Cloud and Grid Computing (CCGRID). Madrid: IEEE, 2017. 371–380.
|
| [25] |
Herrmann J, Özkaya MY, Uçar B, Kaya K, Çatalyürek ÜV. Multilevel algorithms for acyclic partitioning of directed acyclic graphs. SIAM Journal on Scientific Computing, 2019, 41(4): A2117-A2145.
[doi:10.1137/18M1176865] |
| [26] |
Sanders P, Schulz C. Engineering multilevel graph partitioning algorithms. In: Proc. of the 19th European Symp. on Algorithms. Saarbrücken: Springer, 2011. 469–480.
|
| [27] |
Davis TA, Hager WW, Kolodziej SP, et al. Algorithm 1003: Mongoose, a graph coarsening and partitioning library. ACM Trans. on Mathematical Software, 2020, 46(1): 7.
[doi:10.1145/3337792] |
| [11] |
郭文忠, 陈国龙, Xiong NX, 彭少君. 求解VLSI电路划分问题的混合粒子群优化算法. 软件学报, 2011, 22(5): 833−842. http://www.jos.org.cn/1000-9825/3980.htm
|