Parallel algorithms for multi-layer wire routing problems.

Abstract

In this thesis, we explore various parallel processing methods for concurrent multi-layer VLSI routing. One approach is based on efficient execution of the maze routing algorithm on custom processing elements arranged in the form of a hexagonal array. The key contributions here are the mapping policy and the acceleration of three-dimensional search operations. Subsequently, we extend the above work, using a reconfigurable SIMD array, to handle a wider range of routing applications. We do so by developing a routing framework that consolidates many of the existing specialized algorithms such as channel, switchbox and maze routers into one routing system. We employ the concept of a total grid-graph to capture the state of the routing region and propose new and efficient parallel algorithms for cycle detection, cycle elimination, and tree reduction on such graphs. The proposed algorithms scale well with increased problem sizes since they require only $O(\log(N))$ time given a $N\sp2$-node grid-graph. Based on these algorithms, we have developed two types of generalized detailed routers, each capable of finding paths concurrently spanning multiple layers. The first, called a parallel chord router, has the ability to compute various "useful" route patterns in close to constant time; the second is an adaptation of maze routing capable of simultaneously expanding from multiple pins. In addition, we have developed a parallel hill-climbing algorithm that can be used to improve a given route, if possible, by iteratively identifying and rewiring bends in the route. This process yields additional Steiner points and the average cost improvement of the resulting route over the corresponding minimum spanning tree is around 9.5%. In the presence of obstacles the method still yields up to a 4% improvement over a conventional maze router. All algorithms have been coded and tested on several examples and give good results. Some of the basic routines have been further investigated from an architectural viewpoint using trace-driven simulation experiments. The results suggest that the proposed methods can run on a variety of commercially available massively parallel processors (MPPs) providing excellent results at only a fraction of the time required by a conventional serial processor.