A Sequential Detailed Router for Huge Grid Graphs

Sequential routing algorithms using maze-running are very suitable for general Over-the-Cell-Routing but su#er often from the high memory or runtime requirements of the underlying path search routine. A new algorithm for this subproblem is presented that computes shortest paths in a rectangular grid with respect to euclidean distance. It achieves performance and memory requirements similar to fast line-search algorithms while still being optimal. An additional application for the computation of minimal rip-up sets will be presented. Computational results are shown for a detailed router based on these algorithms that is used for the design of high performance CMOS processors at IBM