A new approach to sea-of-gates global routing

The authors integrate the concepts and techniques of two existing complementary approaches, namely, the rerouting approach and the top-down hierarchical approach based on linear assignment. This combines and enhances the advantages of the two approaches and results in a fast and high-quality router which can handle large sea-of-gates designs. In addition, it solves the problems of routing interdependence and routing resource estimation which heretofore have not been well addressed yet. The method has been implemented and successfully tested on three real gate-arrays chips: Primary 1, Primary 2, and a channelless industrial example with 100 K gates.<>