CROSS POINT ASSIGNMENT WITH GLOBAL REROUTING FOR GENERAL-ARCHITECTUREDESIGNS

Cross point assignment (CPA) for designs of general architecture is a layout problem that has not been well addressed so far. It is done bef ore detailed routing and is to decide for each net the exact crossing locations on the boundaries of global routing cells (GRC's). To comple te the CPA for a whole chip, an order of GRC boundaries needs to be de cided, then a sequence of single boundary cross point assignment (SBCP A) 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 em ploys the well-known linear assignment algorithm to solve the SBCPA pr oblem. For the algorithm we develop a novel and comprehensive cost fun ction that can, in addition to minimizing wire length and via count, r educe the effects of horizontal/vertical constraints, and consider glo bally the wire topologies in a GRC row or column. Moreover, by perform ing global rerouting based on accurate congestion status after each CP A iteration, the tool can produce, with a well-improved global wire ro uting, the final CPA result of each GRC. The result can usually be dir ectly input to detailed routing with much higher completion rate and t hus can relieve the efforts of past-routing clean up. This tool has be en tested on several gate-array and sea-of-gates chips. In particular, the benchmark chips, Primary1 and Primary2 have been successfully rou ted with about 17% track usage improvement.