A two-step heuristic algorithm for minimum-crosstalk routing resource assignment

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. Index Terms--Crosstalk, layout, routing, shield insertion, track assignment.