A parallel integer programming approach to global routing

We propose a parallel global routing algorithm that con-currently processes routing subproblems corresponding to rectangular subregions covering the chip area. The algo-rithm uses at it core an existing integer programming (IP) formulation—both for routing each subproblem and for con-necting them. Concurrent processing of the routing sub-problems is desirable for effective parallelization. However, achieving no (or low) overflow global routing solutions with-out strong, coordinated algorithmic control is difficult. Our algorithm addresses this challenge via a patching phase that uses IP to connect partial routing solutions. Patching pro-vides feedback to each routing subproblem in order to avoid overflow, later when attempting to connect them. The end result is a flexible and highly scalable distributed algorithm for global routing. The method is able to accept as input tar-get runtimes for its various phases and produce high-quality solution within these limits. Computational results show that for a target runtime of 75 minutes, running on a com-putational grid of few hundred CPUs with 2GB memory, the algorithm generates higher quality solutions than competing methods in the open literature