电子学报 ›› 2022, Vol. 50 ›› Issue (11): 2575-2583.DOI: 10.12263/DZXB.20211065
收稿日期:
2021-08-09
修回日期:
2021-11-16
出版日期:
2022-11-25
通讯作者:
作者简介:
基金资助:
LIU Geng-geng1, LI Ze-peng1, GUO Wen-zhong1, CHEN Guo-long1, XU Ning2()
Received:
2021-08-09
Revised:
2021-11-16
Online:
2022-11-25
Published:
2022-11-19
Corresponding author:
摘要:
随着集成电路规模的日益增长, 需要处理的线网数量显著增多, 层分配算法运行时间增大成为限制高效设计布线方案的重要因素; 此外在生产工艺中, 通孔的制造成本较高. 针对以上两个问题, 本文提出了两种新颖的策略分别用于优化算法运行时间和通孔数量: (1)一种高效的基于区域划分的并行策略, 实现各区域在并行布线阶段负载均衡, 以提高并行布线的效率; (2)基于线网等效布线方案感知的通孔优化策略, 决定各线网对布线资源使用的优先级, 进而减少层分配方案的通孔数量. 最终将上述两种策略相结合, 提出了一种面向超大规模集成电路物理设计的通孔感知的并行层分配算法. 实验结果表明该算法对通孔数量和运行时间均有良好的优化效果.
中图分类号:
刘耿耿, 李泽鹏, 郭文忠, 陈国龙, 徐宁. 面向超大规模集成电路物理设计的通孔感知的并行层分配算法[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.
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 |
表1 测试用例特征表
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 | |
---|---|---|---|
VR | PVR | ||
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 |
表2 通孔主导的层分配阶段串行算法与基于区域划分的并行算法的运行时间对比
benchmark | VLA_runtime | SUP | |
---|---|---|---|
VR | PVR | ||
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 | |
---|---|---|---|
VR | PVR | ||
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 |
表3 基于协商的通孔感知层分配阶段串行算法与基于区域划分的并行算法的运行时间对比
benchmark | NVLA_runtime | SUP | |
---|---|---|---|
VR | PVR | ||
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 |
benchmark | VRO_runtime | SUP | |
---|---|---|---|
VR | PVR | ||
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 |
表4 通孔精炼阶段串行算法与基于区域划分的并行算法的运行时间对比
benchmark | VRO_runtime | SUP | |
---|---|---|---|
VR | PVR | ||
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 | |||
---|---|---|---|---|---|
VR | 文献[ | PVR | 文献[ | 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 |
表5 基于通孔感知的并行层分配算法整体运行时间对比
benchmark | total_runtime | SUP | |||
---|---|---|---|---|---|
VR | 文献[ | PVR | 文献[ | 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 | |||
---|---|---|---|---|---|
DDR[ | DLA[ | VR | DDR[ | DLA[ | |
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% |
表6 基于线网等效布线方案感知的通孔优化策略验证
benchmark | via_count | ratio | |||
---|---|---|---|---|---|
DDR[ | DLA[ | VR | DDR[ | DLA[ | |
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% |
benchmark | via_count | ratio | |||
---|---|---|---|---|---|
DDR[ | DLA[ | PVR | DDR[ | DLA[ | |
superblue2 | 7129655 | 6794969 | 5885709 | 17.45% | 13.38% |
superblue3 | 6382992 | 6094468 | 5494079 | 13.93% | 9.85% |
superblue6 | 6202333 | 5993170 | 5532920 | 10.79% | 7.68% |
superblue7 | 9335272 | 9008199 | 7884639 | 15.54% | 12.47% |
superblue9 | 5120143 | 4928392 | 4268805 | 16.63% | 13.38% |
superblue11 | 5592279 | 5463358 | 4909798 | 12.20% | 10.13% |
superblue12 | 8500960 | 8180039 | 7807668 | 8.16% | 4.55% |
superblue14 | 4038943 | 3917782 | 3688443 | 8.68% | 5.85% |
superblue16 | 4122687 | 3899307 | 4105378 | 0.42% | -5.28% |
superblue19 | 3038941 | 2960095 | 2668770 | 12.18% | 9.84% |
average | 11.60% | 8.19% |
表7 本文算法的有效性验证
benchmark | via_count | ratio | |||
---|---|---|---|---|---|
DDR[ | DLA[ | PVR | DDR[ | DLA[ | |
superblue2 | 7129655 | 6794969 | 5885709 | 17.45% | 13.38% |
superblue3 | 6382992 | 6094468 | 5494079 | 13.93% | 9.85% |
superblue6 | 6202333 | 5993170 | 5532920 | 10.79% | 7.68% |
superblue7 | 9335272 | 9008199 | 7884639 | 15.54% | 12.47% |
superblue9 | 5120143 | 4928392 | 4268805 | 16.63% | 13.38% |
superblue11 | 5592279 | 5463358 | 4909798 | 12.20% | 10.13% |
superblue12 | 8500960 | 8180039 | 7807668 | 8.16% | 4.55% |
superblue14 | 4038943 | 3917782 | 3688443 | 8.68% | 5.85% |
superblue16 | 4122687 | 3899307 | 4105378 | 0.42% | -5.28% |
superblue19 | 3038941 | 2960095 | 2668770 | 12.18% | 9.84% |
average | 11.60% | 8.19% |
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. |
[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. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||