DocumentCode :
3002255
Title :
Evaluating iterative improvement heuristics for bigraph crossing minimization
Author :
Stallmann, Matthias ; Brglez, Franc ; Ghosh, Debabrata
Author_Institution :
Dept. of Comput. Sci., North Carolina State Univ., Raleigh, NC, USA
Volume :
6
fYear :
1999
fDate :
36342
Firstpage :
444
Abstract :
The bigraph crossing problem, embedding the two node sets of a bipartite graph G=(V0, V1, E) along two parallel lines so that edge crossings are minimized, has application to placement optimization for standard cells and other technologies. Iterative improvement heuristics involve repeated application of some transformation on an existing feasible solution to obtain better feasible solutions. Typically an increase in the number of iterations, and therefore execution time, implies an improvement in solution quality. We investigate tradeoffs between execution time and solution quality in order to establish the best heuristic for any given time budget. Our experiments show some clear trends for a scalable class of graphs based on actual circuits. These trends, based on statistically significant samples of each of several graph sizes, suggest promising directions for development of better heuristics
Keywords :
VLSI; cellular arrays; circuit layout CAD; circuit optimisation; crosstalk; graph theory; integrated circuit layout; iterative methods; logic CAD; network routing; wiring; bigraph crossing minimization; execution time; iterative improvement heuristics; node sets; placement optimization; routing; scalable class; solution quality; standard cells; wire length; Bipartite graph; Circuits; Collaboration; Computer science; Crosstalk; Minimization; Routing; Very large scale integration; Wire; Wiring;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Circuits and Systems, 1999. ISCAS '99. Proceedings of the 1999 IEEE International Symposium on
Conference_Location :
Orlando, FL
Print_ISBN :
0-7803-5471-0
Type :
conf
DOI :
10.1109/ISCAS.1999.780190
Filename :
780190
Link To Document :
بازگشت