Multilevel routing for 3-dimensional circuits
James Haralambides · Annual Conference on Computers · 2006
We present a multilevel routing algorithm for circuits modeled on the 3-Dimensional grid. The algorithm repeatedly contracts the grid by coalescing nodes until a small manageable size has been obtained. Routing is performed on the smaller size grid based on a modified shortest path technique. In the reverse process, the grid and subsequently all pre-routed paths are expanded. Additional routing of emergent nodes is performed at intermediate levels. Final routing concludes at the original level. When compared to single level routing, the algorithm dramatically improves execution time while preserving the quality of routing delays and routing lengths.