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

刘耿耿; 李泽鹏; 郭文忠; 陈国龙; 徐宁

doi:10.12263/DZXB.20211065

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2025-12-08

- 面向超大规模集成电路物理设计的通孔感知的并行层分配算法
- Via-Aware Parallel Layer Assignment Algorithm for VLSI Physical Design
- 电子学报 2022年50卷第11期页码：2575-2583
- 作者机构：
  
  1.福州大学计算机与大数据学院，福建福州 350116
  2.武汉理工大学信息工程学院，湖北武汉 430070
- 作者简介：
  
  [ "刘耿耿男, 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;11501114);国家重点基础研究发展计划(2011CB808000);计算机体系结构国家重点实验室开放课题(CARCHB202014);福建省自然科学基金(2019J01243)
- DOI：10.12263/DZXB.20211065
  中图分类号： TP391.7
- 收稿：2021-08-09，
  
  修回：2021-11-16，
  
  纸质出版：2022-11-25
- 稿件说明：
移动端阅览
刘耿耿,李泽鹏,郭文忠等.面向超大规模集成电路物理设计的通孔感知的并行层分配算法[J].电子学报,2022,50(11):2575-2583.

LIU Geng-geng,LI Ze-peng,GUO Wen-zhong,et al.Via-Aware Parallel Layer Assignment Algorithm for VLSI Physical Design[J].ACTA ELECTRONICA SINICA,2022,50(11):2575-2583.
刘耿耿,李泽鹏,郭文忠等.面向超大规模集成电路物理设计的通孔感知的并行层分配算法[J].电子学报,2022,50(11):2575-2583. DOI： 10.12263/DZXB.20211065.

LIU Geng-geng,LI Ze-peng,GUO Wen-zhong,et al.Via-Aware Parallel Layer Assignment Algorithm for VLSI Physical Design[J].ACTA ELECTRONICA SINICA,2022,50(11):2575-2583. DOI： 10.12263/DZXB.20211065.

摘要

随着集成电路规模的日益增长

需要处理的线网数量显著增多

层分配算法运行时间增大成为限制高效设计布线方案的重要因素; 此外在生产工艺中

通孔的制造成本较高. 针对以上两个问题

本文提出了两种新颖的策略分别用于优化算法运行时间和通孔数量: (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.

关键词

Keywords

references

SHI D , TASHJIAN E , DAVOODI A . Dynamic planning of local congestion from varying-size vias for global routing layer assignment [J]. IEEE Transactions on Computer Aided Design of Integrated Circuits & Systems , 2017 , 36 ( 8 ): 1301 ‐ 1312 .

NACLERIO N J , MASUDA S , NAKAJIMA K . The via minimization problem is NP-complete [J]. IEEE Transactions on Computers , 1989 , 38 ( 11 ): 1604 ‐ 1608 .

MCMURCHIE L , EBELING C . Pathfinder: A negotiation-based performance-driven router for FPGAs [C]// Proceedings of the 1995 ACM Third International Symposium on Field-Programmable Gate Arrays . New York : ACM Press , 1995 : 111 ‐ 117 .

ZHANG X H , ZHUANG Z , LIU G G , HUANG X , LIU W H , GUO W Z , WANG T C . MiniDelay: Multi-strategy timing-aware layer assignment for advanced technology nodes [C]// 2020 Design , Automation & Test in Europe Conference & Exhibition . Los Alamitos : IEEE Computer Society Press , 2020 : 586 ‐ 591 .

LIU G G , ZHANG X H , GUO W Z , HUANG X , LIU W H , CHAO K Y , WANG T C . Timing-aware layer assignment for advanced process technologies considering via pillars [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. Los Alamitos: IEEE Computer Society Press , 2021 : 1 ‐ 14 .

DAI K R , LIU W H , LI Y L . NCTU-GR: Efficient simulated evolution-based rerouting and congestion-relaxed layer assignment on 3-D global routing [J]. IEEE Transactions on Very Large Scale Integration Systems , 2012 , 20 ( 3 ): 459 ‐ 472 .

LEE T H , WANG T C . Congestion-constrained layer assignment for via minimization in global routing [J]. IEEE Transactions on Computer Aided Design of Integrated Circuits & Systems , 2008 , 27 ( 9 ): 1643 ‐ 1656 .

LI Z , ALPERT C J , HU S , MUHMUD T , QUAY S T , VILLARRUBIA P G . Fast interconnect synthesis with layer assignment [C]// Proceedings of International Symposium on Physical Design . New York : ACM Press , 2008 : 71 ‐ 77 .

HU S , LI Z , ALPERT C J . A faster approximation scheme for timing driven minimum cost layer assignment [C]// Proceedings of International Symposium on Physical Design . New York : ACM Press , 2009 : 167 ‐ 174 .

LIU D , YU B , CHOWDHURY S , PAN D Z . TILA-S: Timing-driven incremental layer assignment avoiding slew violations [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2017 , 37 ( 1 ): 231 ‐ 244 .

HAN S Y , LIU W H , EWETZ R , KOH C K , CHAO K Y , WANG T C . Delay-driven layer assignment for advanced technology nodes [C]// Asia and South Pacific Design Automation Conference . Los Alamitos : IEEE Computer Society Press , 2017 : 456 ‐ 462 .

AO J C , DONG S Q , CHEN S , GOTO S . Delay-driven layer assignment in global routing under multi-tier interconnect structure [C]// Proceedings of the 2013 Acm International Symposium on International Symposium on Physical Design . New York : ACM Press , 2013 : 101 ‐ 107 .

WU T H , DAVOODI A , LINDEROTH J T . GRIP: scalable 3D global routing using integer programming [C]// 2009 46th ACM/IEEE Design Automation Conference . Los Alamitos : IEEE Computer Society Press , 2009 : 320 ‐ 325 .

LIU J W , PUI C W , WANG F Z , YOUNG E . CUGR: detailed-routability-driven 3D global routing with probabilistic resource model [C]// 2020 57th ACM/IEEE Design Automation Conference . Los Alamitos : IEEE Computer Society Press , 2020 : 1 ‐ 6 .

WU T H , DAVOODI A , LINDEROTH J T . A parallel integer programming approach to global routing [C]// IEEE Proceedings of Design Automation Conference . Los Alamitos : IEEE Computer Society Press , 2010 : 194 ‐ 199 .

JIANG Y J , FANG S Y . COALA: Concurrently assigning wire segments to layers for 2D global routing [C]// 2020 IEEE/ACM International Conference On Computer Aided Design . Los Alamitos : IEEE Computer Society Press , 2020 : 1 ‐ 8 .

LATHA N R , PRASAD G R . Performance and memory-efficient parallel computing framework for RSMT construction [C]//DAS H, PATTNAIK P K, RAUTARAY S S, LI K C. Progress in Computing , Analytics and Networking . Singapore : Springer , 2020 : 369 ‐ 381 .

SHYAMALA G , PRASAD G R . An efficient parallel computing framework for over the obstacle VLSI routing [C]//DAS H, PATTNAIK P K, RAUTARAY S S, LI K C. Progress in Computing , Analytics and Networking . Singapore : Springer , 2020 : 383 ‐ 395 .

HE J Y , BURTSCHER M , MANOHAR R , PINGALI K . SPRoute: A scalable parallel negotiation-based global router [C]// 2019 IEEE/ACM International Conference on Computer-Aided Design . Los Alamitos : IEEE Computer Society Press , 2019 : 1 ‐ 8 .

LIU W H , KAO W C , LI Y L , CHAO K Y . NCTU-GR 2.0: Multithreaded collision-aware global routing with bounded-length maze routing [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2013 , 32 ( 5 ): 709 ‐ 722 .

HAN Y D , ANCAJAS D M , CHAKRABORTY K , ROY S . Exploring high throughput computing paradigm for global routing [C]// 2011 IEEE/ACM International Conference on Computer-Aided Design . Los Alamitos : IEEE Computer Society Press , 2011 : 298 ‐ 305 .

VISWANATHAN N , ALPERT C , SZE C , LI Z , WEI Y G . The DAC 2012 routability-driven placement contest and benchmark suite [C]// Proceedings of the 2012 Design Automation Conference . Los Alamitos : IEEE Computer Society Press , 2012 : 774 ‐ 782 .

HSU M K , CHEN Y F , HUANG C C , CHEN T C , CHANG Y W . Routability-driven placement for hierarchical mixed-size circuit designs [C]// 2013 50th ACM/EDAC/IEEE Design Automation Conference . Los Alamitos : IEEE Computer Society Press , 2013 : 1 ‐ 6 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

格子Boltzmann方法多层网格负载均衡算法优化研究

面向用户多样化业务需求的多波束卫星系统动态资源分配算法

低轨巨星座多品类业务流低复杂度分段路由方法

多模态网络分布式控制平面负载均衡研究