PAGR: Accelerating Global Routing for VLSI Design Flow

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Roman A. Solovyev, Ilya A. Mkrtchan, Dmitry V. Telpukhov, Ilya I. Shafeev, Aleksandr Y. Romanov, Yevgeniy V. Stolbikov, Alexander L. Stempkovsky
Format: Article
Language:English
Published: IEEE 2025-01-01
Series:IEEE Access
Subjects:
Design flow
global routing
ISPD contest
matrix reduction
Steiner tree
VLSI
Online Access:https://ieeexplore.ieee.org/document/10829948/
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2169-3536

Similar Items