DocumentCode :
1406238
Title :
On crossing minimization problem
Author :
Chen, Hsiao-Feng Steven ; Lee, D.T.
Author_Institution :
Avant Corp., Fremont, CA, USA
Volume :
17
Issue :
5
fYear :
1998
fDate :
5/1/1998 12:00:00 AM
Firstpage :
406
Lastpage :
418
Abstract :
In this paper, we consider a problem related to global routing postoptimization: the crossing minimization problem (CMP). Given a global routing representation, the CMP is to minimize redundant crossings between every pair of nets. In particular, there are two kinds of CMP: constrained CMP (CCMP) and unconstrained CMP (UCMP). These problems have been studied previously where an O(m2n) algorithm was proposed for CCMP, and where an (mn22 ) algorithm was proposed for UCMP where m is the total number of modules, n is the number of nets, and ξ is the number of crossings defined by an initial global routing topology. We present a simpler and faster O(mn) algorithm for CCMP and an O[n(m+ξ)] time algorithm for UCMP. Both algorithms improve over the time bounds of the previously proposed algorithms. The novel part of our algorithm is that it uses the plane embedding information of globally routed nets in the routing area to construct a graph-based framework and obtain a good junction terminal assignment that minimizes the number of crossings
Keywords :
VLSI; circuit layout CAD; circuit optimisation; graph theory; integrated circuit layout; network routing; redundancy; VLSI; constrained CMP; crossing minimization problem; global routing postoptimization; graph-based framework; junction terminal assignment; plane embedding information; redundant crossings; time bounds; unconstrained CMP; Circuits; Data structures; Manufacturing processes; Minimization; Multichip modules; Routing; Topology; Very large scale integration; Wire; Wiring;
fLanguage :
English
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
0278-0070
Type :
jour
DOI :
10.1109/43.703928
Filename :
703928
Link To Document :
بازگشت