Previous [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ]

@

Journal of Information Science and Engineering, Vol. 20 No. 1, pp. 1-25 (January 2004)

On the Crossing Distribution Problem in Two Regions

T. K. Yu+ and D. T. Lee*+
+Department of Computer Science and Information Engineering
National Taiwan University
Taipei, 106 Taiwan
E-mail: tkyu@ntu.edu.tw
*Institute of Information Science
Academia Sinica
Taipei, 115 Taiwan
E-mail: dtlee@iis.sinica.edu.tw

VLSI layout design is typically decomposed into four steps: placement, global routing, routing region definition and ordering, and detailed routing. The crossing distribution problem occurs prior to detailed routing, in which crossings of nets are distributed according to design constraints. In this paper, we propose an O(nlog n) time algorithm for the crossing distribution problem for two-terminal nets in two regions, where n is the number of nets. This algorithm improves a previously known result that runs in O(n2) time [6]. We also give an O(n2) time algorithm for the crossing distribution problem for three-terminal nets under some assumption.

Keywords: VLSI, crossing distribution problem, crossing minimization problem, detailed routing, two-terminal net, multi-terminal net

Full Text () Retrieve PDF document (200401_01.pdf)

Received January 31, 2003; accepted July 4, 2003.
Communicated by Shiuh-Pyng Shieh
*A preliminary version of this paper has been presented at the 2002 International Computer Symposium, 2002.