EECS 298-11: CAD Seminar Wednesday, February 5, 1997, 5pm Cory Hall--Hogan Room Parallel Algorithms for Multi-layer Wire Routing Problems Pinaki Mazumder University of Michigan Routing is one of the significant problems in designing VLSI chips. It can also be very time and memory-space consuming, esp. for large areas with multiple interconnection layers. As hardware costs plummet and massively parallel processing gains maturity and commercialization, it becomes appropriate to consider how this computational power can be efficiently harnessed to actually have the machines deliver all those MFLOPS and MIPS in solving complex routing problems. A new data-parallel heuristic will be presented in this talk to demonstrate how a quasi-optimal multi-layer rectilinear Steiner tree (RST) for a given set of points can be efficiently constructed. Unlike most other RST models, this algorithm can handle both complete as well as partial grid-graphs and so forms a basis for fast general-area routing. Starting from an initial route, the algorithm works by iteratively identifying and rewiring bends in the route. This process yields additional Steiner points and the average cost improvement of the resulting routes over the corresponding minimum spanning tree is around 9\% when there are no obstacles. In the presence of obstacles the method yields up to 4\% improvement over a conventional maze router. For purpose of initial routing, the talk will discuss two models (i) a parallel maze routing algorithm which is computationally superior to the more conventional version in that it requires on the average 4 times fewer propagation and backtrace cycles, and (ii) a parallel chord-based algorithm based on rapid solutions to the twin problems of cycle-detection and cycle-elimination within rectilinear grid-graphs that in practice, yield routes within a factor of 1.56 of the optimal Steiner trees in the absence of obstacles and within a factor of 2 in the presence of obstacles. The latter algorithm is also interesting in that it can be simply tuned towards comb-tree, single-trunk Steiner tree or contour routing which is useful in performing detailed routing. Finally, some of the implementation results will be discussed in the form of several routed examples (both general areas as well as channels and switchboxes) and they will be compared to those obtained using constraint-graph based methods.