An interactive maze router with hints
- 6 January 2003
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 672-676
- https://doi.org/10.1109/dac.1988.14840
Abstract
This paper presents the Irouter, an interactive maze router for the Magic IC layout editor that takes hints. The Irouter is a flexible tool intended to be useful wherever tight or unusual constraints do not permit automatic routing. It has already been used in the layout of an 80,000 transistor CMOS chip developed by our group at LLNL, and is currently being used to route the control signals of a 100,000 transistor, high performance, FPU chip being developed by the Berkeley SPUR project.Several novel ideas for maze routing have been developed in the Irouter. Hint layers permit the user to map out the general path of a route and pull the route in desired directions, while leaving details, such as obeying the design rules, to the router. The gross structure of the layout is preprocessed to facilitate accurate estimates of cost to completion during routing and hence effective pruning of misdirected partial routes. A windowed search strategy slowly shifts the focus from the start point towards the goal. This permits the consideration of alternatives at all stages of routing without blowing up into an exhaustive search.Keywords
This publication has 9 references indexed in Scilit:
- A Tile-Expansion RouterIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- The Magic VLSI Layout SystemIEEE Design & Test of Computers, 1985
- Corner Stitching: A Data-Structuring Technique for VLSI Layout ToolsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1984
- Magic's Incremental Design-Rule CheckerPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1984
- Circuit layoutProceedings of the IEEE, 1981
- Fast Maze RouterPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- The Lee Path Connection AlgorithmIEEE Transactions on Computers, 1974
- An Algorithm for Path Connections and Its ApplicationsIEEE Transactions on Electronic Computers, 1961
- A note on two problems in connexion with graphsNumerische Mathematik, 1959