硬件加速功能验证问题的DAG划分算法  

DAG Partition Algorithm for Hardware Accelerated Function Verification

作　　者：何天祥 肖正 陈岑 刘楚波 李肯立 HE Tian-Xiang;XIAO Zheng;CHEN Cen;LIU Chu-Bo;LI Ken-Li(College of Computer Science and Electronic Engineering,Hunan University,Changsha 410082,China;National Supercomputing Center in Changsha,Changsha 410082,China)

机构地区：[1]湖南大学信息科学与工程学院,湖南长沙410082 [2]国家超级计算长沙中心,湖南长沙410082

出　　处：《软件学报》2022年第9期3236-3248,共13页Journal of Software

基　　金：国家自然科学基金(61772182,61802032)。

摘　　要：功能验证是超大规模集成电路(very large scale integration,VLSI)设计的一个基本环节.随着超大规模电路的普及与发展,在单处理器上对整个电路进行功能验证在可行性和效率上都存在较大的缺陷.基于硬件加速器的功能验证是将整个电路划分成若干个规模更小的子电路;然后在多个硬件处理器上并行的执行功能验证.当电路划分结果的并行性较优时可提高功能验证的效率,缩短时间周期.类似电路设计中的其他划分问题,用于硬件加速功能验证的电路划分问题可以被抽象成图划分问题.相较于传统图划分问题,硬件加速功能验证的划分问题还需要保证较小的模拟深度和较高的调度并行性.为了满足硬件加速功能验证的划分需求,提出了一种基于传统多级图划分策略的有效算法.该算法结合调度思想,利用电路的关键路径信息和时序信息,将硬件加速功能验证问题转化为有向无环图的多级划分问题.随机电路网表数据的实验结果表明,所构造的算法可以有效的减少关键路径长度并且不会引起切边数的增长恶化.Functional verification is a basic step in VLSI design. With the popularity and development of VLSI, the feasibility and efficiency of functional verification of the whole circuit on a single processor are greatly deficient. The functional verification based on hardware accelerator divides the whole circuit into several smaller sub circuits. When the parallelism of circuit partitioning is better, the time cycle of function verification can be accelerated. Similar to other partitioning problems in circuit design, the circuit partitioning problem for hardware accelerated function verification can be abstracted into graph partitioning problem. In order to meet the requirements of hardware accelerated functional verification, an effective algorithm based on traditional multi-level graph partition strategy is proposed.The algorithm combines the idea of scheduling, and uses the critical path information and timing information of the circuit. The problem of hardware accelerated function verification is transformed into the problem of multi-level partition of directed acyclic graph. The experimental results of random circuit netlist data show that the proposed algorithm can effectively reduce the critical path length and does not cause the growth and deterioration of the number of cut edges.

关 键 词：超大规模集成电路(VLSI) 硬件功能加速验证 有向无环图 多级图划分 关键路径 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]