21st Design Automation Conference Proceedings · 1984 · 42 citations · 6 references
ComputingComputer ScienceAlgorithmsInterconnection NetworksOptimizationHeuristic SearchLayout OptimizationRoutingRouting AlgorithmsSearching AlgorithmsCellular RoutingGlobal RoutingGrid SearchHeuristic Routing AlgorithmsMaze RoutingMulti-terminal RoutingPlacement AlgorithmsState Space Search
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.
6
An Algorithm for Path Connections and Its Applications
C. Y. Lee · IEEE Transactions on Electronic Computers · 1961 · 1.6K citations
The interconnection problem: A tutorial
David W. Hightower · Computer · 1974 · 51 citations