电子学报 ›› 2022, Vol. 50 ›› Issue (11): 2575-2583.DOI: 10.12263/DZXB.20211065

• 学术论文 • 上一篇    下一篇

面向超大规模集成电路物理设计的通孔感知的并行层分配算法

刘耿耿1, 李泽鹏1, 郭文忠1, 陈国龙1, 徐宁2()   

  1. 1.福州大学计算机与大数据学院,福建 福州 350116
    2.武汉理工大学信息工程学院,湖北 武汉 430070
  • 收稿日期:2021-08-09 修回日期:2021-11-16 出版日期:2022-11-25
    • 通讯作者:
    • 徐宁
    • 作者简介:
    • 刘耿耿 男, 1988年生, 福建南安人, 博士,副教授, 博士生导师, 主要研究方向为EDA算法研究、 计算智能及其应用.E-mail: liugenggeng@fzu.edu.cn
      李泽鹏 男, 1998年生, 福建安溪人, 硕士研究生, 主要研究方向为EDA算法研究.E-mail: li_zepeng@yeah.net
      郭文忠 男, 1979年生, 福建惠安人, 博士, 教授, 主要研究方向为计算智能及其应用.E-mail: guowenzhong@fzu.edu.cn
      陈国龙 男, 1965年生, 福建莆田人, 博士,教授, 主要研究方向为人工智能、 网络信息安全.E-mail: cgl@fzu.edu.cn
      徐 宁(通讯作者) 男, 1968年生, 湖北武汉人, 博士, 教授, 主要研究方向为FPGA物理设计、 电子设计自动化、 大数据分析与人工智能、图像处理.
    • 基金资助:
    • 国家自然科学基金 (61877010); 国家重点基础研究发展计划 (2011CB808000); 计算机体系结构国家重点实验室开放课题 (CARCHB202014); 福建省自然科学基金 (2019J01243)

Via-Aware Parallel Layer Assignment Algorithm for VLSI Physical Design

LIU Geng-geng1, LI Ze-peng1, GUO Wen-zhong1, CHEN Guo-long1, XU Ning2()   

  1. 1.College of Computer and Data Science, Fuzhou University, Fuzhou, Fujian 350116, China
    2.School of Information Engineering, Wuhan University of Technology, Wuhan, Hubei 430070, China
  • Received:2021-08-09 Revised:2021-11-16 Online:2022-11-25 Published:2022-11-19
    • Corresponding author:
    • XU Ning

摘要:

随着集成电路规模的日益增长, 需要处理的线网数量显著增多, 层分配算法运行时间增大成为限制高效设计布线方案的重要因素; 此外在生产工艺中, 通孔的制造成本较高. 针对以上两个问题, 本文提出了两种新颖的策略分别用于优化算法运行时间和通孔数量: (1)一种高效的基于区域划分的并行策略, 实现各区域在并行布线阶段负载均衡, 以提高并行布线的效率; (2)基于线网等效布线方案感知的通孔优化策略, 决定各线网对布线资源使用的优先级, 进而减少层分配方案的通孔数量. 最终将上述两种策略相结合, 提出了一种面向超大规模集成电路物理设计的通孔感知的并行层分配算法. 实验结果表明该算法对通孔数量和运行时间均有良好的优化效果.

关键词: 并行算法, 层分配, 通孔, 区域划分, 负载均衡, 超大规模集成电路

Abstract:

As the scale of integrated circuits grows, the number of nets greatly increases, which makes the runtime of layer assignment algorithm increase and becomes an important limiting factor of efficient routing algorithm. Besides, in the manufacture, vias always take high cost. Accordingly, this paper presents two strategies to reduce runtime and the number of vias: (1) an efficient region-division based parallel strategy, which realizes load balancing of parallel routing to improve the efficiency of routing algorithm; (2) an equivalent routing solution aware via optimization strategy, which determines the priority of each net in using routing resource to reduce the number of vias of layer assignment. Furthermore, combining the above two strategies, this paper proposes a via-aware parallel layer assignment algorithm for very large scale integration (VLSI) physical design. The experimental results show that the proposed algorithm is able to optimize the number of vias significantly and reduce runtime simultaneously.

Key words: parallel algorithm, layer assignment, via, region-division, load balancing, VLSI

中图分类号: