A fast router and placement algorithm for wafer scale integration and wafer scale hybrid packaging

The authors describe an algorithm developed for discretionary wafer routing needed for wafer scale integration (WSI) or multichip packaging. A very fast multilayer line probe router has been developed and implemented. The router uses a collection of depth-first heuristics to provide an extremely fast route with exceptional wiring quality and very high completion rate. The search algorithms and data structures are significantly different from those of D. Hightower (1969). These differences make it possible to route the special kinds of wiring needed for WSI in under a minute of VAX 6410 CPU time in many cases. Such a high-speed router will be necessary when line routing is to proceed at wafer throughput rates for fabrication