A Global Routing Algorithm for General Cells
- 1 January 1984
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. c 18, 45-51
- https://doi.org/10.1109/dac.1984.1585771
Abstract
An algorithm is presented which accomplishes the global routing for a building block or general cell routing problem. A line search technique is employed and therefore no grid is assumed either for the module placements or the pin locations. Instead of breaking the routing surface up into channels, a maze search finds acceptable global routes while avoiding the blocks. Both multi-pin terminals and multi-terminal nets are accomodated. It is shown that the Lee-Moore grid-based approach is actually a special case of the general search algorithm presented. This algorithm is borrowed from the field of artificial intelligence where it has been applied to many state-space search problems.Keywords
This publication has 5 references indexed in Scilit:
- Automated Layout in ASHLAR: An Approach to the Problems of "General Cell" Layout for VLSIPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- The interconnection problem: A tutorialComputer, 1974
- A Method for Solving Arbitrary-Wall Mazes by ComputerIEEE Transactions on Computers, 1969
- A solution to line-routing problems on the continuous planePublished by Association for Computing Machinery (ACM) ,1969
- An Algorithm for Path Connections and Its ApplicationsIEEE Transactions on Electronic Computers, 1961