PAGR: Accelerating Global Routing for VLSI Design Flow

IEEE Access. 2025. Vol. 13. P. 6440–6450.

Roman A. Solovyev, Mkrtchan I., Telpukhov D., Shafeev I., Romanov A. Y., Stolbikov Y., Stempkovsky A.

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.

Keywords: VLSI, Steiner tree, global routing, ISPD contest, Design flow, matrix reduction

Publication based on the results of: Methods and tools for the development and implementation of digital twins for electronic engineering (2025)