POST GLOBAL ROUTING CROSSTALK SYNTHESIS

For the generation of a risk-free layout solution of a chip, crosstalk synthesis should be pursued at various stages in the routing process. This paper proposes a post global routing crosstalk optimization appr oach, which to our knowledge, is the first to estimate and reduce cros stalk risk at the global routing level, It consists of two parts: regi on-based crosstalk risk estimation and crosstalk risk I eduction at th e global routing level, In Part One, crosstalk risk graphs are first i ntroduced for each routing region representing its current crosstalk s ituation. The crosstalk risk of each region, which indicates whether a risk-free routing solution of the region is possible, is then quantit atively defined and estimated using a graph-based approach. In Part Tw o, the risk tolerance bound of each net is partitioned appropriately a mong its routing regions via integer linear programming for accurate ( minimized) crosstalk risk estimation. If high risk regions still exist after bound partitioning, net ripping-up and rerouting is applied to reduce their crosstalk risks. At the end of the entire optimization pr ocess, a risk-free global routing solution is obtained together with p artitions of nets' risk tolerance hounds which reflect the current cro sstalk situation of the chip, These can greatly facilitate the generat ion of a risk-free final solution at later stages in the layout proces s. The proposed approach has been implemented and tested on CBL/NCSU b enchmarks and the experimental results are very promising.