PARALLEL 3D RECTILINEAR STEINER TREE CONSTRUCTION BASED ON SPANNING GRAPHS

Abstract

Steiner tree construction is a fundamental problem in VLSI physical design. Given a set of pins in 3D space, the objective is to connect all pins with minimum total wirelength, possibly using additional Steiner points. This problem becomes particularly important in modern 3D integrated circuits, where vertical connections are realized through Through-Silicon Vias (TSVs). Since TSVs occupy valuable silicon area, their positions must be carefully determined and tracked to avoid conflicts between different nets. Building upon the 3D rectilinear spanning graph presented in prior work, this paper proposes a parallel algorithm for 3D rectilinear Steiner tree construction. The main contributions are as follows. First, the pair-generation process is decoupled from Kruskal's algorithm. Second, Tarjan's sequential lowest-common-ancestor (LCA) computation is replaced with the Euler tour technique combined with a range-minimum-query (RMQ) data structure, enabling fast and independent parallel LCA queries. In addition, a centroid-based tree partitioning scheme is introduced, which allows edge substitutions to be computed concurrently and independently. The proposed algorithm achieves up to $15\times$ speedup with 16 threads compared to the sequential version while maintaining solution quality. As an application, a TSV-aware multi-net routing framework is demonstrated, where dies are modeled as layers in 3D space, and TSV positions are dynamically determined during Steiner tree construction and tracked to prevent conflicts between nets.