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

doi:10.12263/DZXB.20211065

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

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

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

^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-geng¹, LI Ze-peng¹, GUO Wen-zhong¹, CHEN Guo-long¹, XU Ning²()

^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

摘要/Abstract

摘要：

随着集成电路规模的日益增长, 需要处理的线网数量显著增多, 层分配算法运行时间增大成为限制高效设计布线方案的重要因素; 此外在生产工艺中, 通孔的制造成本较高. 针对以上两个问题, 本文提出了两种新颖的策略分别用于优化算法运行时间和通孔数量: (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

中图分类号:

TP391.7

刘耿耿, 李泽鹏, 郭文忠, 陈国龙, 徐宁. 面向超大规模集成电路物理设计的通孔感知的并行层分配算法[J]. 电子学报, 2022, 50(11): 2575-2583.

LIU Geng-geng, LI Ze-peng, GUO Wen-zhong, CHEN Guo-long, XU Ning. Via-Aware Parallel Layer Assignment Algorithm for VLSI Physical Design[J]. Acta Electronica Sinica, 2022, 50(11): 2575-2583.

图/表 13

参考文献 23

1	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.
2	NACLERIO N J, MASUDA S, NAKAJIMA K. The via minimization problem is NP-complete[J]. IEEE Transactions on Computers, 1989, 38(11): 1604‐1608.
3	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.
4	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.
5	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.
6	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.
7	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.
8	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.
9	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.
10	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.
11	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.
12	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.
13	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.
14	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.
15	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.
16	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.
17	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.
18	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.
19	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.
20	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.
21	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.
22	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.
23	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.

benchmark	#grid	#layer	#net
superblue2	770×891	9	990899
superblue3	800×415	9	898001
superblue6	649×495	9	1006629
superblue7	499×713	9	1340418
superblue9	426×570	9	833808
superblue11	631×878	9	935731
superblue12	444×518	9	1293436
superblue14	406×473	9	619815
superblue16	465×404	9	697458
superblue19	321×518	9	511685

benchmark	#grid	#layer	#net
superblue2	770×891	9	990899
superblue3	800×415	9	898001
superblue6	649×495	9	1006629
superblue7	499×713	9	1340418
superblue9	426×570	9	833808
superblue11	631×878	9	935731
superblue12	444×518	9	1293436
superblue14	406×473	9	619815
superblue16	465×404	9	697458
superblue19	321×518	9	511685

benchmark	VLA_runtime		SUP
benchmark	VR	PVR	SUP
superblue2	46.407	17.438	2.66
superblue3	24.558	11.913	2.06
superblue6	22.903	11.770	1.95
superblue7	30.187	11.690	2.58
superblue9	16.459	8.159	2.02
superblue11	25.200	9.544	2.64
superblue12	26.055	11.109	2.35
superblue14	14.041	7.130	1.97
superblue16	16.737	9.407	1.78
superblue19	9.226	4.513	2.04
average			2.20

benchmark	VLA_runtime		SUP
benchmark	VR	PVR	SUP
superblue2	46.407	17.438	2.66
superblue3	24.558	11.913	2.06
superblue6	22.903	11.770	1.95
superblue7	30.187	11.690	2.58
superblue9	16.459	8.159	2.02
superblue11	25.200	9.544	2.64
superblue12	26.055	11.109	2.35
superblue14	14.041	7.130	1.97
superblue16	16.737	9.407	1.78
superblue19	9.226	4.513	2.04
average			2.20

benchmark	NVLA_runtime		SUP
benchmark	VR	PVR	SUP
superblue2	240.144	100.979	2.38
superblue3	167.022	86.836	1.92
superblue6	137.432	67.692	2.03
superblue7	177.883	74.700	2.38
superblue9	96.693	46.674	2.07
superblue11	103.781	43.040	2.41
superblue12	164.388	78.414	2.10
superblue14	85.886	40.345	2.13
superblue16	108.72	70.933	1.53
superblue19	44.396	23.626	1.88
average			2.08

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

Via-Aware Parallel Layer Assignment Algorithm for VLSI Physical Design

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 23

相关文章 15

编辑推荐

Metrics

benchmark	VRO_runtime		SUP
benchmark	VR	PVR	SUP
superblue2	67.037	24.493	2.74
superblue3	39.515	16.427	2.41
superblue6	37.739	15.853	2.38
superblue7	48.160	16.991	2.83
superblue9	26.944	11.225	2.40
superblue11	37.795	13.195	2.86
superblue12	40.811	17.307	2.36
superblue14	23.018	9.983	2.31
superblue16	27.575	12.868	2.14
superblue19	13.725	6.088	2.25
average			2.47

benchmark	total_runtime			SUP
benchmark	VR	文献［10］	PVR	文献［10］	PVR
superblue2	353.588	161.582	142.910	2.19	2.47
superblue3	231.095	126.879	115.175	1.82	2.01
superblue6	198.074	110.927	95.315	1.79	2.08
superblue7	256.230	104.435	103.381	2.45	2.48
superblue9	140.096	85.728	66.058	1.63	2.12
superblue11	166.766	55.983	65.799	2.98	2.54
superblue12	231.254	107.340	106.830	2.15	2.16
superblue14	122.945	119.577	57.458	1.03	2.14
superblue16	153.032	81.969	93.208	1.87	1.64
superblue19	67.347	34.430	34.227	1.96	1.97
average				1.99	2.16

benchmark	via_count			ratio
benchmark	DDR^［11］	DLA^［12］	VR	DDR^［11］	DLA^［12］
superblue2	7129655	6794969	5703736	20.00%	16.06%
superblue3	6382992	6094468	5276904	17.33%	13.41%
superblue6	6202333	5993170	5316640	14.28%	11.29%
superblue7	9335272	9008199	7785024	16.61%	13.58%
superblue9	5120143	4928392	4248455	17.02%	13.80%
superblue11	5592279	5463358	4692009	16.10%	14.12%
superblue12	8500960	8180039	7321668	13.87%	10.49%
superblue14	4038943	3917782	3539881	12.36%	9.65%
superblue16	4122687	3899307	3371064	18.23%	13.55%
superblue19	3038941	2960095	2614623	13.96%	11.67%
average				15.98%	12.76%

[1]	赵夫群, 耿国华. 基于特征区域划分的文物碎片自动匹配算法[J]. 电子学报, 2022, 50(6): 1436-1443.
[2]	刘焕淋, 胡俊岭, 任杰, 胡会霞, 唐畅, 陈浩楠. 基于光路负载均衡和邻域匹配的串扰感知资源分配方法[J]. 电子学报, 2022, 50(11): 2746-2753.
[3]	左小寒, 梁华国, 倪天明, 杨兆, 束月, 蒋翠云, 鲁迎春. 基于间隔分组的TSV聚簇故障冗余结构[J]. 电子学报, 2021, 49(4): 805-811.
[4]	崔子熙, 胡宇翔, 兰巨龙, 王雨. 基于流分类的数据中心网络负载均衡机制[J]. 电子学报, 2021, 49(3): 559-565.
[5]	王宁远, 刘亮, 陈东, 刘欢, 郝时光. 低轨巨星座多品类业务流低复杂度分段路由方法[J]. 电子学报, 2021, 49(11): 2124-2132.
[6]	江小玉, 李贵洋, 周悦, 胡金平, 李慧. 基于负载均衡的纠删码修复流水线[J]. 电子学报, 2020, 48(5): 930-936.
[7]	蹇强, 张培勇, 王雪洁. 一种可配置的CNN协加速器的FPGA实现方法[J]. 电子学报, 2019, 47(7): 1525-1531.
[8]	刘焕淋, 胡浩, 陈勇, 杜君丹, 向敏. 联合能耗与负载均衡的虚拟网络映射方法[J]. 电子学报, 2019, 47(12): 2488-2494.
[9]	倪天明, 常郝, 卞景昌, 易茂祥, 梁华国, 黄正峰. 基于边沿延时翻转的绑定前硅通孔测试方法[J]. 电子学报, 2019, 47(11): 2278-2283.
[10]	黄建洋, 兰巨龙, 胡宇翔, 马腾. 一种基于分段路由的多路径流传输机制[J]. 电子学报, 2018, 46(6): 1488-1495.
[11]	胡涛, 张建辉, 邬江, 何为伟, 江逸茗, 赵伟. SDN中基于分布式决策的控制器负载均衡机制[J]. 电子学报, 2018, 46(10): 2316-2324.
[12]	方馨蔚, 陈庶樵, 江逸茗, 任泽荣. 一种内容中心网络中的热区控制及内容调度缓存算法[J]. 电子学报, 2017, 45(5): 1182-1188.
[13]	陶晓玲, 韦毅, 王勇. 一种基于分层多代理的云计算负载均衡方法[J]. 电子学报, 2016, 44(9): 2106-2113.
[14]	盛洁, 马冬. 异构无线网络业务接入多目标优化控制算法[J]. 电子学报, 2016, 44(2): 282-288.
[15]	刘书勇, 吴艳霞, 张博为, 张国印, 戴葵. 基于可重构计算系统的矩阵三角化分解硬件并行结构研究[J]. 电子学报, 2015, 43(8): 1642-1650.