The complexity and size of integrated circuit designs has increased dramatically in recent years. Accordingly, there is a need for design automation tools that can handle ever larger and more complex routing problems. The problems of interest have evolved from simple channels to switchboxes to general areas. Currently, there is great interest in solving general area routing problems because of the rising popularity of new design methodologies and the emergence of new manufacturing technologies. For example, the Sea-of-Gates design style with many layers of high-quality interconnect requires over-the-cell routing to achieve high circuit densities. The structure of such routing problems on the channelless gate array is clearly in the domain of general area routers. Similarly, the next generation PC board technology using silicon-on-silicon modules will also require a general area router. Because these complex routing problems are a manifestation of an overall increase in design complexity, routers must not only handle these general area problems but also interact with other design tools in a more sophisticated manner. In particular, the feedback between routing programs and placement programs must become more explicit and any approach developed for general area problems must take this interaction into consideration. In this report, hierarchical decomposition is examined as a way to attack the general area routing problem. This divide and conquer method is a useful technique for managing complexity and in recent years has been applied to various routing problems. In particular, there are examples of this concept in channel routers [BP82, BP83a, HM85, HM89], switchbox routers [BP83b], and global routers [M584, LTW86, M586, Lau87]. This work describes a set of experiments that outlines the extension of these applications to general area routing problems.




Download Full History