先进通孔柱技术下高性能层分配算法

doi:10.19678/j.issn.1000-3428.0069463

摘要/Abstract

摘要：

通孔柱是先进制程下的一项新技术, 该技术对于优化布线方案中通孔的时延具有显著的效果, 但是需要占据更多的布线资源。因此, 如何在不影响可布线性的情况下, 合理地分配有限的布线资源, 充分地发挥通孔柱技术对时延的优化能力, 是先进制程下层分配算法的一大挑战。围绕先进通孔柱技术下高性能层分配问题展开研究, 提出3项改进策略: 1)提出初始布线顺序优先级定义策略, 综合考虑线网的总路径长度和接收器数量为线网确定优先级, 为后续阶段建立良好的布线基础; 2)提出考虑不溢出情况下历史代价计算策略, 有效地对所有的边进行使用优先级的划分, 减少拥塞的边的使用; 3)提出规范违规线网的重新分配顺序策略, 对迭代布线阶段中的违规线网重新分配顺序进行规范, 综合考虑线网的总路径长度、接收器数量以及线网上一次迭代后的时延, 使布线顺序具有更大的确定性和保障性。实验结果表明, 经上述策略改进, 算法的有效性、平均时延、通孔数、溢出和运行速度均得到了优化。

关键词: 层分配, 通孔柱, 超大规模集成电路, 布线优先级, 时延

Abstract:

The via pillar is a new technology using advanced technology nodes, which has a significant effect on optimizing the delay of via in routing solution; however, it requires increased routing resources. Therefore, reasonable assignment of the limited routing resources without affecting the routability is challenging. Additionally, fully using the delay optimization ability of the via pillar technology for the layer assignment algorithm in advanced technology nodes is difficult. This study focuses on high-performance layer assignment problem under advanced via pillar technology and proposes three improvement strategies. Here, an initial routing order priority definition strategy is proposed. This strategy comprehensively considers the number of sinks and the total length of the nets to determine the priority of the nets and establish a good routing foundation for the subsequent stage. Moreover, a calculation strategy without overflow is proposed considering historical cost. This strategy effectively prioritizes all the edges for use and reduces the use of congested edges. Additionally, a redistribution order strategy for illegal nets is proposed. This strategy comprehensively considers the total length of the nets, number of sinks, and delay of the last iteration to increase the security of the routing order at this stage. The experimental results demonstrate that the effectiveness, the number of vias, the overflow and delay of the timing-critical net of the proposed algorithm are optimized through the aforementioned strategies improments.

Key words: layer assignment, via pillar, Very Large Scale Integration Circuit (VLSI), routing priority, delay

林紫晴, 李泽鹏, 刘耿耿. 先进通孔柱技术下高性能层分配算法[J]. 计算机工程, 2025, 51(11): 204-214.

LIN Ziqing, LI Zepeng, LIU Genggeng. High-Performance Layer Assignment Algorithm Under Advanced Via Pillar Technology[J]. Computer Engineering, 2025, 51(11): 204-214.

https://www.ecice06.com/CN/Y2025/V51/I11/204

图/表 15

图1 多层布线模型

Fig.1 Multi-layer routing model

图2 网格单元示意图

Fig.2 Schematic diagram of grid cell

图3 不同层导线的不同宽度和间距

Fig.3 Different widths and spacings of wires in different layers

图4 默认规则导线、平行线和宽线

Fig.4 Default rule wire, parallel wires, and wide wire

图5 通孔柱类型

Fig.5 Type of via pillar

图6 层分配算法流程图

Fig.6 Flowchart of the layer assignment algorithm

图7 总路径相同时延不同的情况

Fig.7 The situation where the total path is the same but the delay is different

图8 不溢出的边拥塞程度不同的情况

Fig.8 The situation where non-overflow edge have different levels of congestion

图9 各项策略有效性验证

Fig.9 Effectiveness validation of each strategy

参考文献 29

1	LIU G G , ZHANG X H , GUO W Z , et al. Timing-aware layer assignment for advanced process technologies considering via pillars. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 41 (6): 1957- 1970. doi: 10.1109/TCAD.2021.3100296
2	MANTIK S, POSSER G, CHOW W K, et al. ISPD 2018 initial detailed routing contest and benchmarks[C]//Proceedings of the 2018 International Symposium on Physical Design. New York, USA: ACM Press, 2018: 140-143.
3	LIU W H, MANTIK S, CHOW W K, et al. ISPD 2019 initial detailed routing contest and benchmark with advanced routing rules[C]//Proceedings of the 2019 International Symposium on Physical Design. New York, USA: ACM Press, 2019: 147-151.
4	吕丽华, 张红. 基于分段时延凸函数的最小斯坦纳树方法. 计算机工程, 2010, 36 (6): 64- 66. doi: 10.3969/j.issn.1000-3428.2010.06.021
	LÜ L H , ZHANG H . Method of minimum steiner tree based on piecewise concavity of delay function. Computer Engineering, 2010, 36 (6): 64- 66. doi: 10.3969/j.issn.1000-3428.2010.06.021
5	廖海涛, 史峥, 张腾. 基于边界扩张的点对点布线新算法. 计算机工程, 2014, 40 (5): 299- 303. doi: 10.3969/j.issn.1000-3428.2014.05.062
	LIAO H T , SHI Z , ZHANG T . New algorithm for point-to-point wiring based on boundary expansion. Computer Engineering, 2014, 40 (5): 299- 303. doi: 10.3969/j.issn.1000-3428.2014.05.062
6	XU S J , WEI L , LIU G G , et al. A high-quality global routing algorithm based on hybrid topology optimization and heuristic search for data processing in MEC. The Journal of Supercomputing, 2022, 78 (5): 7133- 7157. doi: 10.1007/s11227-021-04147-y
7	LIU G G , CHEN X H , ZHOU R P , et al. Social learning discrete particle swarm optimization based two-stage X-routing for IC design under Intelligent Edge Computing architecture. Applied Soft Computing, 2021, 104, 107215. doi: 10.1016/j.asoc.2021.107215
8	LIU G G , ZHU Y H , XU S J , et al. PSO-based power-driven X-routing algorithm in semiconductor design for predictive intelligence of IoT applications. Applied Soft Computing, 2022, 114, 108114. doi: 10.1016/j.asoc.2021.108114
9	贾艳明, 蔡懿慈, 洪先龙. 考虑通孔电阻和耦合电容的时延驱动的层分配算法. 计算机辅助设计与图形学学报, 2009, 21 (2): 196- 202.
	JIA Y M , CAI Y C , HONG X L . Timing driven layer assignment considering via resistance and coupling capacitance. Journal of Computer-Aided Design[WT《Times New Roman》]& Computer Graphics, 2009, 21 (2): 196- 202.
10	周强, 周毅, 蔡懿慈, 等. 拥挤度驱动的总体布线层分配算法. 计算机辅助设计与图形学学报, 2004, 16 (7): 1005- 1009.
	ZHOU Q , ZHOU Y , CAI Y C , et al. Congestion driven global routing layer assignment algorithm. Journal of Computer-Aided Design and Computer Graphics, 2004, 16 (7): 1005- 1009.
11	洪先龙, 潘立, 王尔乾. 一种用于VLSI的统一通孔最少化和线长最小化层分配算法. 计算机学报, 1997, 20 (4): 335- 341.
	HONG X L , PAN L , WANG E Q . A layer assignment algorithm for unified via minimization and wire length minimization on the specified layer in VLSI. Chinese Journal of Computers, 1997, 20 (4): 335- 341.
12	LEE T H , WANG T C . Congestion-constrained layer assignment for via minimization in global routing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27 (9): 1643- 1656. doi: 10.1109/TCAD.2008.927733
13	SHI D H, TASHJIAN E, DAVOODI A. Dynamic planning of local congestion from varying-size vias for global routing layer assignment[C]//Proceedings of the 21st Asia and South Pacific Design Automation Conference (ASP-DAC). New York, USA: ACM Press, 2016: 372-377.
14	SHI D H , TASHJIAN E , DAVOODI A . Dynamic planning of local congestion from varying-size vias for global routing layer assignment. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017, 36 (8): 1301- 1312. doi: 10.1109/TCAD.2017.2695889
15	SUN J , LU Y H , ZHOU H , et al. Post-routing layer assignment for double patterning with timing critical paths consideration. Integration, 2013, 46 (2): 153- 164. doi: 10.1016/j.vlsi.2012.02.003
16	HU S Y, LI Z, ALPERT C J. A faster approximation scheme for timing driven minimum cost layer assignment[C]//Proceedings of the 2009 International Symposium on Physical Design. New York, USA: ACM Press, 2009: 167-174.
17	刘耿耿, 鲍晨鹏, 王鑫, 等. 非默认规则线技术下基于多策略的时延驱动层分配算法. 计算机学报, 2023, 46 (4): 743- 760.
	LIU G G , BAO C P , WANG X , et al. Multi-strategy delay-driven layer assignment for non-default-rule wiring techniques. Chinese Journal of Computers, 2023, 46 (4): 743- 760.
18	DONG S Q , AO J C , LUO F Q . Delay-driven and antenna-aware layer assignment in global routing under multitier interconnect structure. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2015, 34 (5): 740- 752. doi: 10.1109/TCAD.2015.2404871
19	LIU D R, YU B, CHOWDHURY S, et al. Incremental layer assignment for critical path timing[C]//Proceedings of the 53rd Annual Design Automation Conference. New York, USA: ACM Press, 2016: 1-6.
20	LIU D R , YU B , CHOWDHURY S , et al. Incremental layer assignment for timing optimization. ACM Transactions on Design Automation of Electronic Systems, 2017, 22 (4): 1- 25.
21	LIU D R , YU B , CHOWDHURY S , et al. TILA-S: timing-driven incremental layer assignment avoiding slew violations. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37 (1): 231- 244. doi: 10.1109/TCAD.2017.2652221
22	刘耿耿, 魏凌, 徐宁. 考虑总线时序匹配的多策略层分配算法. 计算机辅助设计与图形学学报, 2022, 34 (4): 545- 551.
	LIU G G , WEI L , XU N . Multi-strategy layer assignment algorithm considering bus timing matching. Journal of Computer-Aided Design[WT《Times New Roman》]& Computer Graphics, 2022, 34 (4): 545- 551.
23	ZHANG X H, ZHUANG Z, LIU G G, et al. MiniDelay: multi-strategy timing-aware layer assignment for advanced technology nodes[C]//Proceedings of the Design, Automation and Test in Europe Conference (DATE). Grenoble, France: IEEE Press, 2020: 586-591.
24	HSU M K, KATTA N, LIN H Y, et al. Design and manufacturing process co-optimization in nano-technology (designer track paper)[C]//Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD). San Jose, USA: IEEE Press, 2014: 574-581.
25	HAN S Y, LIU W H, EWETZ R, et al. Delay-driven layer assignment for advanced technology nodes[C]//Proceedings of the 22nd Asia and South Pacific Design Automation Conference. Makuhari Messe, Japan: [s. n. ], 2017: 456-462.
26	ELMORE W C . The transient response of damped linear networks with particular regard to wideband amplifiers. Journal of Applied Physics, 1948, 19 (1): 55- 63. doi: 10.1063/1.1697872
27	LU L C. Physical design challenges and innovations to meet power, speed, and area scaling trend[C]//Proceedings of the 2017 ACM on International Symposium on Physical Design. New York, USA: ACM Press, 2017: 63.
28	ZHONG Y, YU T C, YANG K C, et al. Via pillar-aware detailed placement[C]//Proceedings of the 2020 International Symposium on Physical Design. New York, USA: ACM Press, 2020: 17-24.
29	VISWANATHAN N, ALPERT C, SZE C, et al. The DAC 2012 routability-driven placement contest and benchmark suite[C]//Proceedings of the 49th Annual Design Automation Conference. New York, USA: ACM Press, 2012: 774-782.

[1]	李世超. 具有时延约束的高速铁路云无线接入网络资源分配研究[J]. 计算机工程, 2025, 51(9): 213-219.
[2]	王景熠, 朱予涵, 周茹平, 刘耿耿. 基于动态粒子群优化的X结构Steiner最小树算法[J]. 计算机工程, 2024, 50(9): 226-234.
[3]	杨志军, 黄文洁, 丁洪伟. 连续时间完全-限定(K=2)两级轮询系统性能分析[J]. 计算机工程, 2024, 50(1): 191-197.
[4]	彭世明, 林士飏, 贾硕, 杨苗会. 基于负载预测的多目标优化任务卸载策略[J]. 计算机工程, 2024, 50(1): 206-215.
[5]	罗华峰, 沈奕菲, 阮黎翔, 杜奇伟, 郑翔, 陈智麒, 张胜. 边缘环境下面向实时目标检测的帧卸载调度算法[J]. 计算机工程, 2023, 49(5): 295-301,309.
[6]	石小容, 李爱萍, 牛保宁, 段利国, 赵菊敏. 兼顾个性化需求的云边协作两级内容缓存研究[J]. 计算机工程, 2023, 49(5): 223-230.
[7]	谷允捷, 吴长禾, 吴庆, 张伟, 吕天航, 胡琪, 宋晓斌, 闫吉宇. 面向时延优化的级联漏洞扫描引擎部署策略[J]. 计算机工程, 2023, 49(3): 161-167,176.
[8]	李江和, 王玫. 一种用于因果式语音增强的门控循环神经网络[J]. 计算机工程, 2022, 48(11): 77-82.
[9]	罗菲莹, 李新民, 李强, 邓惠云. 面向URLLC业务的MIMO上行系统线性接收机性能分析[J]. 计算机工程, 2022, 48(11): 177-183.
[10]	杨志军, 寇倩兰, 丁洪伟. 5G切片架构下具有重传机制的轮询系统研究[J]. 计算机工程, 2022, 48(10): 202-211.
[11]	杨天, 杨军. MEC中卸载决策与资源分配的深度强化学习方法[J]. 计算机工程, 2021, 47(8): 37-44.
[12]	梁秋玲, 张向利, 张红梅, 闫坤. 基于多核处理器的关联任务并行感知调度算法[J]. 计算机工程, 2021, 47(7): 212-217.
[13]	吴晓彤, 柳平增. 基于备选投票机制的低时延PBFT改进研究[J]. 计算机工程, 2021, 47(7): 117-125,134.
[14]	赵兴兵, 赵一帆, 李波, 陈春, 丁洪伟. 基于时延与能量感知的边缘服务器放置方法[J]. 计算机工程, 2021, 47(11): 37-43.
[15]	曹乐, 胡晓辉, 乔钰. 一种车载自组织网络连通性维护方法[J]. 计算机工程, 2021, 47(10): 153-159.

选择文件类型/文献管理软件名称

选择包含的内容