A Global Routing Algorithm for General Cells

Gary W. Clow

CaltechAUTHORS (California Institute of Technology) · 1984 · 49 citations · 7 references

Concepts

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. 
\n
\nIt 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.

References

7