PAGR: Accelerating Global Routing for VLSI Design Flow
In this paper, we present PAGR (Python Alpha Global Routing) – a solution to the global routing problem in physical synthesis based on data from the ISPD 2024 contest. Our solution constructs a weighted graph and builds a Steiner tree. To accelerate the Steiner tree search, we propose a t...
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10829948/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832088044420726784 |
|---|---|
| author | Roman A. Solovyev Ilya A. Mkrtchan Dmitry V. Telpukhov Ilya I. Shafeev Aleksandr Y. Romanov Yevgeniy V. Stolbikov Alexander L. Stempkovsky |
| author_facet | Roman A. Solovyev Ilya A. Mkrtchan Dmitry V. Telpukhov Ilya I. Shafeev Aleksandr Y. Romanov Yevgeniy V. Stolbikov Alexander L. Stempkovsky |
| author_sort | Roman A. Solovyev |
| collection | DOAJ |
| description | In this paper, we present PAGR (Python Alpha Global Routing) – a solution to the global routing problem in physical synthesis based on data from the ISPD 2024 contest. Our solution constructs a weighted graph and builds a Steiner tree. To accelerate the Steiner tree search, we propose a technique for the graph size minimization by reducing the input 3D matrix. This method slightly decreases result quality but finds solutions 2–10 times faster. We also detail our methods for parallel calculations and computing graph edge weights. Experimental results show that while the current Python implementation does not achieve high routing speeds, the solution’s quality measured in contest metrics (wire length, via, overflow) is comparable to top contestants. Implementing the algorithm in C/C++ will significantly improve runtime. The algorithm’s description can benefit future research, and the source code with detailed comments is available online. |
| format | Article |
| id | doaj-art-9c48a0d825554887b3f1295ffca80736 |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-9c48a0d825554887b3f1295ffca807362025-02-06T00:00:56ZengIEEEIEEE Access2169-35362025-01-01136440645010.1109/ACCESS.2025.352672210829948PAGR: Accelerating Global Routing for VLSI Design FlowRoman A. Solovyev0https://orcid.org/0000-0003-0312-452XIlya A. Mkrtchan1Dmitry V. Telpukhov2Ilya I. Shafeev3https://orcid.org/0009-0005-2323-3725Aleksandr Y. Romanov4https://orcid.org/0000-0002-9410-9431Yevgeniy V. Stolbikov5Alexander L. Stempkovsky6AlphaChip LLC, Moscow, RussiaAlphaChip LLC, Moscow, RussiaAlphaChip LLC, Moscow, RussiaNational Research University of Electronic Technology (MIET), Moscow, RussiaHSE University, Moscow, RussiaAlphaChip LLC, Moscow, RussiaAlphaChip LLC, Moscow, RussiaIn this paper, we present PAGR (Python Alpha Global Routing) – a solution to the global routing problem in physical synthesis based on data from the ISPD 2024 contest. Our solution constructs a weighted graph and builds a Steiner tree. To accelerate the Steiner tree search, we propose a technique for the graph size minimization by reducing the input 3D matrix. This method slightly decreases result quality but finds solutions 2–10 times faster. We also detail our methods for parallel calculations and computing graph edge weights. Experimental results show that while the current Python implementation does not achieve high routing speeds, the solution’s quality measured in contest metrics (wire length, via, overflow) is comparable to top contestants. Implementing the algorithm in C/C++ will significantly improve runtime. The algorithm’s description can benefit future research, and the source code with detailed comments is available online.https://ieeexplore.ieee.org/document/10829948/Design flowglobal routingISPD contestmatrix reductionSteiner treeVLSI |
| spellingShingle | Roman A. Solovyev Ilya A. Mkrtchan Dmitry V. Telpukhov Ilya I. Shafeev Aleksandr Y. Romanov Yevgeniy V. Stolbikov Alexander L. Stempkovsky PAGR: Accelerating Global Routing for VLSI Design Flow IEEE Access Design flow global routing ISPD contest matrix reduction Steiner tree VLSI |
| title | PAGR: Accelerating Global Routing for VLSI Design Flow |
| title_full | PAGR: Accelerating Global Routing for VLSI Design Flow |
| title_fullStr | PAGR: Accelerating Global Routing for VLSI Design Flow |
| title_full_unstemmed | PAGR: Accelerating Global Routing for VLSI Design Flow |
| title_short | PAGR: Accelerating Global Routing for VLSI Design Flow |
| title_sort | pagr accelerating global routing for vlsi design flow |
| topic | Design flow global routing ISPD contest matrix reduction Steiner tree VLSI |
| url | https://ieeexplore.ieee.org/document/10829948/ |
| work_keys_str_mv | AT romanasolovyev pagracceleratingglobalroutingforvlsidesignflow AT ilyaamkrtchan pagracceleratingglobalroutingforvlsidesignflow AT dmitryvtelpukhov pagracceleratingglobalroutingforvlsidesignflow AT ilyaishafeev pagracceleratingglobalroutingforvlsidesignflow AT aleksandryromanov pagracceleratingglobalroutingforvlsidesignflow AT yevgeniyvstolbikov pagracceleratingglobalroutingforvlsidesignflow AT alexanderlstempkovsky pagracceleratingglobalroutingforvlsidesignflow |