Parallel VLSI-routing models for polymorphic processors array

This tutorial explores various parallel processing methods for concurrent multi-layer VLSI-routing. One approach is based on efficient execution of the maze algorithm on custom processing elements arranged in the form of a hexagonal array. The key features here are the mapping policy and the acceleration of three-dimensional search operations. Subsequently, parallel algorithms over a reconfigurable SIMD array will be discussed to handle a wider range of routing applications. A routing framework will be discussed that consolidates many of the existing specialized algorithms such as channel, switch-box and maze routers into one routing system. The concept of a total grid-graph will be used 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-2-node grid-graph. Based on these algorithms, the tutorial will develop 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, a parallel hill-climbing algorithm will be discussed 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.