research-article

LHNN: lattice hypergraph neural network for VLSI congestion prediction

Authors:

Guangyong Chen,

Pheng Ann HengAuthors Info & Claims

DAC '22: Proceedings of the 59th ACM/IEEE Design Automation Conference

Pages 1297 - 1302

https://doi.org/10.1145/3489517.3530675

Published: 23 August 2022 Publication History

Abstract

Precise congestion prediction from a placement solution plays a crucial role in circuit placement. This work proposes the lattice hypergraph (LH-graph), a novel graph formulation for circuits, which preserves netlist data during the whole learning process, and enables the congestion information propagated geometrically and topologically. Based on the formulation, we further developed a heterogeneous graph neural network architecture LHNN, jointing the routing demand regression to support the congestion spot classification. LHNN constantly achieves more than 35% improvements compared with U-nets and Pix2Pix on the F1 score. We expect our work shall highlight essential procedures using machine learning for congestion prediction.

References

[1]

M.-K. Hsu et al., "NTUplace4h: A novel routability-driven placement algorithm for hierarchical mixed-size circuit designs," TCAD, vol. 33, no. 12, pp. 1914--1927, 2014.

[2]

W.-H. Liu et al., "NCTU-GR 2.0: Multithreaded collision-aware global routing with bounded-length maze routing," IEEE TCAD, vol. 32, no. 5, pp. 709--722, 2013.

Digital Library

[3]

P. Spindler et al., "Fast and accurate routing demand estimation for efficient routability-driven placement," in DATE, pp. 1--6, IEEE, 2007.

[4]

A. F. Tabrizi et al., "A machine learning framework to identify detailed routing short violations from a placed netlist," in DAC, pp. 1--6, IEEE, 2018.

[5]

J. Chen et al., "PROS: A plug-in for routability optimization applied in the state-of-the-art commercial eda tool using deep learning," in ICCAD, pp. 1--8, IEEE, 2020.

Digital Library

[6]

M. B. Alawieh et al., "High-definition routing congestion prediction for large-scale FPGAs," in ASP-DAC, pp. 26--31, IEEE, 2020.

[7]

Z. Xie et al., "RouteNet: Routability prediction for mixed-size designs using convolutional neural network," in ICCAD, pp. 1--8, IEEE, 2018.

Digital Library

[8]

A. Al-Hyari et al., "A deep learning framework to predict routability for FPGA circuit placement," TRETS, vol. 14, no. 3, pp. 1--28, 2021.

Digital Library

[9]

R. Liang et al., "Drc hotspot prediction at sub-10nm process nodes using customized convolutional network," in ISPD, pp. 135--142, 2020.

[10]

R. Kirby et al., "CongestionNet: Routing congestion prediction using deep graph neural networks," in VLSI-SoC, pp. 217--222, IEEE, 2019.

[11]

X. Chen et al., "Detailed routing short violation prediction using graph-based deep learning model," IEEE Trans. Circuits Syst. II Express Briefs, 2021.

[12]

M. Schlichtkrull et al., "Modeling relational data with graph convolutional networks," in ESWC, pp. 593--607, Springer, 2018.

[13]

N. Yadati et al., "HyperGCN: A new method of training graph convolutional networks on hypergraphs," NeurIPS, vol. 32, 2019.

[14]

J. Gilmer et al., "Neural message passing for quantum chemistry," in ICML, pp. 1263--1272, PMLR, 2017.

[15]

Z. Hu et al., "Heterogeneous graph transformer," in Proceedings of The Web Conference 2020, pp. 2704--2710, 2020.

Digital Library

[16]

N. Viswanathan et al., "The ispd-2011 routability-driven placement contest and benchmark suite," in Proc. ISPD, pp. 141--146, 2011.

[17]

N. Viswanathan et al., "The dac 2012 routability-driven placement contest and benchmark suite," in DAC, pp. 774--782, IEEE, 2012.

[18]

Y. Lin et al., "Dreamplace: Deep learning toolkit-enabled gpu acceleration for modern vlsi placement," IEEE TCAD, vol. 40, no. 4, pp. 748--761, 2020.

[19]

M. Wang et al., "Deep graph library: Towards efficient and scalable deep learning on graphs.," 2019.

[20]

O. Ronneberger et al., "U-net: Convolutional networks for biomedical image segmentation," in MICCAI, pp. 234--241, Springer, 2015.

[21]

P. Isola et al., "Image-to-image translation with conditional adversarial networks," in Proc. CVPR, pp. 1125--1134, 2017.

Cited By

Wang ZChen LWang JBai YLi XLi XYuan MHao JZhang YWu FSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)A circuit domain generalization framework for efficient logic synthesis in chip designProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3694123(50163-50207)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3694123
Zhong RYe JTang ZKai SYuan MHao JYan JWooldridge MDy JNatarajan S(2024)PreRoutGNN for timing prediction with order preserving partitionProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i15.29653(17087-17095)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i15.29653
Hou YYe HZhang YXu SSong GBaeza-Yates RBonchi F(2024)RoutePlacer: An End-to-End Routability-Aware Placer with Graph Neural NetworkProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671895(1085-1095)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671895
Show More Cited By

Recommendations

Evaluating TCP-friendliness in light of Concurrent Multipath Transfer

In prior work, a CMT protocol using SCTP multihoming (termed SCTP-based CMT) was proposed and investigated for improving application throughput. SCTP-based CMT was studied in (bottleneck-independent) wired networking scenarios with ns-2 simulations. ...
TCP CERL: congestion control enhancement over wireless networks

In this paper, we propose and verify a modified version of TCP Reno that we call TCP Congestion Control Enhancement for Random Loss (CERL). We compare the performance of TCP CERL, using simulations conducted in ns-2, to the following other TCP variants: ...
The incremental deployability of RTT-based congestion avoidance for high speed TCP Internet connections
SIGMETRICS '00: Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

Our research focuses on end-to-end congestion avoidance algorithms that use round trip time (RTT) fluctuations as an indicator of the level of network congestion. The algorithms are referred to as delay-based congestion avoidance or DCA. Due to the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '22: Proceedings of the 59th ACM/IEEE Design Automation Conference

July 2022

1462 pages

ISBN:9781450391429

DOI:10.1145/3489517

General Chair:
Rob Oshana
NXP

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE CEDA

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 August 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Guangdong Provincial Basic and Applied Basic Research Fund - Regional Joint Fund
National Key Research and Development Program of China
Key Fundamental Research Program of Shenzhen
National Natural Science Foundation of China

Conference

DAC '22

Sponsor:

SIGDA

DAC '22: 59th ACM/IEEE Design Automation Conference

July 10 - 14, 2022

California, San Francisco

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
518
Total Downloads

Downloads (Last 12 months)169
Downloads (Last 6 weeks)16

Reflects downloads up to 15 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang ZChen LWang JBai YLi XLi XYuan MHao JZhang YWu FSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)A circuit domain generalization framework for efficient logic synthesis in chip designProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3694123(50163-50207)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3694123
Zhong RYe JTang ZKai SYuan MHao JYan JWooldridge MDy JNatarajan S(2024)PreRoutGNN for timing prediction with order preserving partitionProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i15.29653(17087-17095)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i15.29653
Hou YYe HZhang YXu SSong GBaeza-Yates RBonchi F(2024)RoutePlacer: An End-to-End Routability-Aware Placer with Graph Neural NetworkProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671895(1085-1095)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671895
Yu HZhang YHe LZhao YLi XXin RZhao JLiao XLiu HHe BJin H(2024)RAHP: A Redundancy-aware Accelerator for High-performance Hypergraph Neural Network2024 57th IEEE/ACM International Symposium on Microarchitecture (MICRO)10.1109/MICRO61859.2024.00094(1264-1277)Online publication date: 2-Nov-2024
https://doi.org/10.1109/MICRO61859.2024.00094
Liu RLiu GLei X(2024)MSANet: Congestion Prediction for Chip Routing Based on Multi-Scale Attention Network2024 3rd International Symposium on Semiconductor and Electronic Technology (ISSET)10.1109/ISSET62871.2024.10779655(587-592)Online publication date: 23-Aug-2024
https://doi.org/10.1109/ISSET62871.2024.10779655
Li HHuo YWang YYang XHao MWang X(2024)A Lightweight Inception Boosted U-Net Neural Network for Routability Prediction2024 2nd International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA62518.2024.10617987(648-653)Online publication date: 10-May-2024
https://doi.org/10.1109/ISEDA62518.2024.10617987
Qi ZPeng QHu SYou H(2024)Effective Heterogeneous Graph Neural Network for Routing Congestion Prediction2024 2nd International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA62518.2024.10617734(369-373)Online publication date: 10-May-2024
https://doi.org/10.1109/ISEDA62518.2024.10617734
Liu BQiao CXu NGeng XZhu ZYang JKim T(2024)Variational Label-Correlation Enhancement for Congestion PredictionProceedings of the 29th Asia and South Pacific Design Automation Conference10.1109/ASP-DAC58780.2024.10473930(466-471)Online publication date: 22-Jan-2024
https://dl.acm.org/doi/10.1109/ASP-DAC58780.2024.10473930
Zou JWang XGuo JLiu WZhang QHuang COh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Circuit as set of pointsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667532(32468-32480)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667532
Verma ASaxena RJadeja MBhateja VLin J(2023)Bet-GAT: An Efficient Centrality-Based Graph Attention Model for Semi-Supervised Node ClassificationApplied Sciences10.3390/app1302084713:2(847)Online publication date: 7-Jan-2023
https://doi.org/10.3390/app13020847
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten