Parallel Algorithms for Several VLSI Routing Problems.

We consider several basic problems in VLSI routing such as river routing between rectangles, routing within a rectilinear polygon, wiring module pins to frame pads and channel routing in the knock-knee model. The known strategies to handle these problems seem to be inherently sequential. We develop new techniques that lead to efficient parallel algorithms. Our basic model of parallel processing is the CREWPRAM. All our algorithms use p processors, where 1 < p < n, n is the input length, and run in time O( n/p +log n) or O((n log n)/p +log^2 n). Our algorithms have fast implementations on other parallel models such as the mesh and the hypercube. For the river routing problem between rectangles, we have derived O(n/p + log n) algorithms to determine the characteristic bendpoints and the minimum separation, and O((n log n)/p + log^2 n) algorithm to solve the offset problem. To solve the routing problem within a rectilinear polygon, we convert the layout problem into a geometric problem of finding the union of rectilinear polygons and develop O( n/p + log n) algorithms for both the detailed routing and routability testing problems For the problem of wiring module pins to frame pads, we develop a new strategy that leads to an O(np + log n) algorithm. We have also developed 0 ((n log n)/p + log^2 n) algorithms to detect routability and to minimize the total wire length. To solve the channel routing problem in the knock-knee model, we have developed an O (n/p + log n) parallel algorithm to partition the n input nets into d chains, where d is the density of the problem. This new technique could replace the left edge or the greedy strategy for channel routing. Then we have developed O(n/p + log n) algorithms to modify the above chains and to generate the optimal wiring. For the three layer assignment problem, we have developed O(n/p + log n) algorithms to modify the above layout and do the layer assignment such that the layout is three layer wirable