A Global Routing Algorithm for General Cells

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.