SAAP: An Efficient Spatial-Aware Analytic Partitioning Algorithm of VLSI Netlists for Parallel Routing
This work solves the problem of inefficient parallel routing in VLSI design for chip designers, offering a significant improvement over existing methods but is incremental as it builds on spatial-aware partitioning.
The paper tackles the problem of partitioning VLSI netlists for parallel routing by addressing performance degradation from spatial constraints in 2D layouts, proposing SAAP, which enforces hard spatial constraints to minimize cut sizes, resulting in several to dozens of times smaller spatial cut sizes compared to previous state-of-the-art methods.
As VLSI designs grow in complexity, partitioning is widely adopted to accelerate physical design through parallel computing. However, traditional hypergraph partitioning methods often degrade in performance when applied to 2D layouts due to spatial constraints. For routers with post-placement locations, a spatial-aware partitioning method fully utilizing placement data is preferable. Existing works can only consider soft spatial constraints, leading to a scattered distribution in one partition. We propose SAAP, an analytic partitioning algorithm enforcing hard spatial constraints while efficiently minimizing cut sizes. It includes analytic boundary modeling with regularity-guided simulated annealing and region embedding. Given placed netlists, it generates timing-friendly k-way spatially continuous partitions for parallel routing. Experiments show that it can quickly provide several to dozens of times smaller spatial cut sizes than previous state-of-the-art, with better spatial continuity.