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

Via-Aware Parallel Layer Assignment Algorithm for VLSI Physical Design

作　　者：刘耿耿[1] 李泽鹏 郭文忠[1] 陈国龙[1] 徐宁[2] LIU Geng-geng;LI Ze-peng;GUO Wen-zhong;CHEN Guo-long;XU Ning(College of Computer and Data Science,Fuzhou University,Fuzhou,Fujian 350116,China;School of Information Engineering,Wuhan University of Technology,Wuhan,Hubei 430070,China)

机构地区：[1]福州大学计算机与大数据学院,福建福州350116 [2]武汉理工大学信息工程学院,湖北武汉430070

出　　处：《电子学报》2022年第11期2575-2583,共9页Acta Electronica Sinica

基　　金：国家自然科学基金(No.61877010,No.11501114);国家重点基础研究发展计划(No.2011CB808000);计算机体系结构国家重点实验室开放课题(No.CARCHB202014);福建省自然科学基金(No.2019J01243)。

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

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

分 类 号：TP391.7[自动化与计算机技术—计算机应用技术]