An adaptation of the interior point method for solving the global routing problem

A linear-programming (LP) solution technique is applied to solve the global routing problem. Minimal spanning trees that were found in the subgrid by generating vertical and horizontal lines about the points of a given net and a modified interior point approach that reduces the number of arc constraints which were considered in the routing problem were used to reduce the problem site. An interior point algorithm approach is developed to solve the resulting LP problem. A FORTRAN code ROUTFAST is tested on several problems of varying arc capacities. ROUTFAST is compared with MINOS 5.0 which is a Simplex-based code on the same set of problems. ROUTFAST is at least 8-20 times faster than MINOS on the largest problems tested and seems to be getting faster as the problem size and arc capacity increases. Using a modification (ROUTLP) to solve four benchmark gate-array layout problems, ROUTFAST yielded competitive global routing results to TimberWolfSC Version 5.4 and in a fraction of TimberWolfSC´s running time