Title :
Crossing distribution [circuit layout CAD]
Author :
Wang, Deborah C. ; Shung, C. Bernard
Author_Institution :
LSI Logic Corp., Milpitas, CA, USA
Abstract :
The problem of distributing the set of crossings between two regions is studied. A crossing is defined as the intersection of two nets. Three types of crossing-distribution problems are considered: (1) the quota problem, (2) the membership problem, and (3) the combination problem, which is a combination of the quota and membership problems. The objective is to find a net ordering at the boundary between two regions such that the quota and membership problems are resolved, and the total number of crossings is minimized. The authors propose the use of computational geometry techniques for the solution of the quota problem in O(n log n) time, the use of a depth-first search to solve the membership in O(n2) time, and the use of a breadth-first search to solve the combination problem in O(n2 ) time, where n is the number of tests
Keywords :
circuit layout CAD; computational geometry; circuit layout CAD; combination problem; computational geometry; crossing distribution; depth-first search; membership problem; net ordering; quota problem; Circuits; Computational geometry; Large scale integration; Logic; Macrocell networks; Routing; Sorting; Wire; Wiring;
Conference_Titel :
Design Automation Conference, 1992., EURO-VHDL '92, EURO-DAC '92. European
Conference_Location :
Hamburg
Print_ISBN :
0-8186-2780-8
DOI :
10.1109/EURDAC.1992.246219
