Title :
A Two-Step Heuristic Algorithm for Minimum-Crosstalk Routing Resource Assignment
Author :
Cai, Yici ; Liu, Bin ; Zhou, Qiang ; Hong, Xianlong
Author_Institution :
Dept. of Comput. Sci. & Technol., Tsinghua Univ., Beijing
Abstract :
This brief deals with the crosstalk minimization problem in an integrated routing resource assignment stage containing several operations between global routing and detailed routing. A two-step heuristic algorithm consisting of coarse assignment and detailed assignment is proposed. In coarse assignment, shield lines are planned based on the chromatic number of a light coarse coupling graph, and the assignment of segments that are longer than a predefined threshold is solved with semidefinite programming. In detailed assignment, a strategy based on a dynamic priority queue is introduced to mitigate common problems caused by sequential routing. Experimental results on a set of benchmarks show significant reduction in coupling length between sensitive segments compared to a prevalent bipartite-matching-based algorithm
Keywords :
circuit optimisation; crosstalk; minimisation; network routing; bipartite matching; coarse assignment; crosstalk minimization; detailed assignment; detailed routing; dynamic priority queue; global routing; heuristic algorithm; integrated routing resource assignment; light coarse coupling graph; sequential routing; Crosstalk; Delay effects; Electronic design automation and methodology; Heuristic algorithms; Logic; Optical coupling; Research and development; Routing; Wire; Yield estimation; Crosstalk; layout; routing; shield insertion; track assignment;
Journal_Title :
Circuits and Systems II: Express Briefs, IEEE Transactions on
DOI :
10.1109/TCSII.2006.882353
