Title :
The modular orientation of VLSI layout
Author :
Cheng, Chung-Kuan ; Hu, T.C. ; Yao, So-Zen
Author_Institution :
Dept. of Comput. Sci. & Eng., California Univ., San Diego, CA, USA
Abstract :
After all (rectangular) circuit modules are placed, it may still be possible to flip the modules so as to reduce the total net length. The orientation of modules is formulated as a graph problem and proved to be NP-complete. The orientation problem is shown to be equivalent to finding a minimum cut of a graph with some arcs of negative capacities. In many cases, it is possible to decompose the graph into subgraphs and reduce the search space for optimum orientation. Experiments with real cases show that an optimum orientation reduces the total net length and improves the routability
Keywords :
VLSI; circuit layout; graph theory; modules; network topology; NP-complete; VLSI layout; graph problem; minimum cut; modular orientation; negative capacities; orientation problem; routability; search space; subgraphs; total net length; Algorithm design and analysis; Computer science; Integrated circuit layout; Merging; Pins; Very large scale integration;
Conference_Titel :
Circuits and Systems, 1990., IEEE International Symposium on
Conference_Location :
New Orleans, LA
DOI :
10.1109/ISCAS.1990.112442
