Sequential/Parallel Global Routing Algorithms for VLSI Standard Cells
By Hao Sun, May 2004
Abstract:
Global routing is an important and time consuming step in VLSI physical design
automation. In order to effectively solve this problem, three standard cell global
routers are presented in the form of (i) a Sequential Heuristic Global Router
(SHGR) (ii) a Hierarchical Heuristic Global Router (HHGR) and (iii) an Integer
Linear Programming (ILP) based Global Router (ILP-GR). The objective of SHGR is to
find the minimum cost path for each net by enumerating a set of possible 2-bend
routes. It achieves 16% improvement over wirelength obtained by placement
based on Half Perimeter Wire Length (HPWL) method. HHGR is a pre-processing technique
that provides good routing estimations in reasonable time. It can predict the
routability of circuits and reduces CPU time on average by 82.5% compared with
SHGR. ILP-GR formulates the global routing problem as two Integer Linear Programming
(ILP) models. These ILP models are further relaxed tong (LP) models to reduce
computation time. ILP-GR overcomes the net-ordering problem and provides optimal
solutions which can be used as upper bounds for other global routers. It achieves on
average an improvement of 6.7% over wirelength solutions produced by the SHGR
technique.
