Via-Aware Parallel Layer Assignment Algorithm for VLSI Physical Design

LIU Geng-geng; LI Ze-peng; GUO Wen-zhong; CHEN Guo-long; XU Ning

doi:10.12263/DZXB.20211065

您当前的位置：

首页 >

文章列表页 >

Via-Aware Parallel Layer Assignment Algorithm for VLSI Physical Design

PAPERS | 更新时间：2025-12-08

- Via-Aware Parallel Layer Assignment Algorithm for VLSI Physical Design
- ACTA ELECTRONICA SINICA Vol. 50, Issue 11, Pages: 2575-2583(2022)
- 作者机构：
  
  1.福州大学计算机与大数据学院，福建福州 350116
  2.武汉理工大学信息工程学院，湖北武汉 430070
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20211065
  CLC： TP391.7
- Received：09 August 2021，
  
  Revised：2021-11-16，
  
  Published：25 November 2022
- 稿件说明：
移动端阅览
刘耿耿,李泽鹏,郭文忠等.面向超大规模集成电路物理设计的通孔感知的并行层分配算法[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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Optimization Study of the Load Balancing Algorithm in the Multi-Layer Lattice Boltzmann Method

Diverse User Service Requirement-Oriented Dynamic Resource Allocation Algorithm for Multi-Beam Satellite Systems

A Low Time Complexity Segment Routing Approach for Multi-Commodity Traffic Flow in Mega LEO Constellation

Research on Load Balancing of Distributed Control Plane in Polymorphic Network

Related Author

Geng-geng LIU

Ze-peng LI

Wen-zhong GUO

Guo-long CHEN

Ning XU

HE Peng

WANG Liang-jun

ZHANG Wu

Related Institution

College of Computer and Data Science， Fuzhou University

School of Information Engineering， Wuhan University of Technology

School of Computer Engineering and Science, Shanghai University

School of Mechanics and Engineering Science, Shanghai University

School of Communications and Information Engineering, Chongqing University of Posts and Telecommunications

⁰