硬件加速功能验证问题的DAG划分算法
作者:
作者单位:

作者简介:

何天祥(1998-), 男, 硕士生, 主要研究领域为图计算, 图划分;肖正(1981-), 男, 博士, 副教授, 博士生导师, CCF专业会员, 主要研究领域为协同优化, 并行分布式系统, 高性能计算, 智能信息处理, 大数据;陈岑(1985-), 男, 博士, 主要研究领域为并行与分布式计算, 机器学习, 深度学习;刘楚波(1988-), 男, 博士, 副教授, 博士生导师, CCF专业会员, 主要研究领域为并行分布式计算, 博弈论, 体系结构, 人工智能;李肯立(1971-), 男, 博士, 教授, 博士生导师, CCF会士, 主要研究领域为并行分布式处理, 超级计算与云计算, 面向大数据和人工智能的高效能计算

通讯作者:

李肯立, E-mail: lkl@hnu.edu.cn

中图分类号:

TP301

基金项目:

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


DAG Partition Algorithm for Hardware Accelerated Function Verification
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    功能验证是超大规模集成电路(very large scale integration, VLSI)设计的一个基本环节. 随着超大规模电路的普及与发展, 在单处理器上对整个电路进行功能验证在可行性和效率上都存在较大的缺陷. 基于硬件加速器的功能验证是将整个电路划分成若干个规模更小的子电路; 然后在多个硬件处理器上并行的执行功能验证. 当电路划分结果的并行性较优时可提高功能验证的效率, 缩短时间周期. 类似电路设计中的其他划分问题, 用于硬件加速功能验证的电路划分问题可以被抽象成图划分问题. 相较于传统图划分问题, 硬件加速功能验证的划分问题还需要保证较小的模拟深度和较高的调度并行性. 为了满足硬件加速功能验证的划分需求, 提出了一种基于传统多级图划分策略的有效算法. 该算法结合调度思想, 利用电路的关键路径信息和时序信息, 将硬件加速功能验证问题转化为有向无环图的多级划分问题. 随机电路网表数据的实验结果表明, 所构造的算法可以有效的减少关键路径长度并且不会引起切边数的增长恶化.

    Abstract:

    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.

    参考文献
    相似文献
    引证文献
引用本文

何天祥,肖正,陈岑,刘楚波,李肯立.硬件加速功能验证问题的DAG划分算法.软件学报,2022,33(9):3236-3248

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-03-12
  • 最后修改日期:2021-04-12
  • 录用日期:
  • 在线发布日期: 2022-06-15
  • 出版日期: 2022-09-06
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号