Cross Point Assignment with Global Rerouting for General-Architecture Designs

Cross point assignment (CPA) for designs of general architecture is a layout problem that has not been well addressed so far. It is done before detailed routing and is to decide for each net the exact crossing locations on the boundaries of global routing cells (GRC's). To complete the CPA for a whole chip, an order of GRC boundaries needs to be decided, then a sequence of single boundary cross point assignment (SBCPA) tasks are performed. In this paper, we present a tool that performs iteratively the CPA process integrated with global rerouting. The CPA process applies a set of heuristic rules for boundary ordering and employs the well-known linear assignment algorithm to solve the SBCPA problem. For the algorithm we develop a novel and comprehensive cost function that can, in addition to minimizing wire length and via count, reduce the effects of horizontal/vertical constraints, and consider globally the wire topologies in a GRC row or column. Moreover, by performing global rerouting based on accurate congestion status after each CPA iteration, the tool can produce, with a well-improved global wire routing, the final CPA result of each GRC. The result can usually be directly input to detailed routing with much higher completion rate and thus can relieve the efforts of post-routing clean up. This tool has been tested on several gate-array and sea-of-gates chips. In particular, the benchmark chips, Primary1 and Primary2 have been successfully routed with about 17% track usage improvement.