Title :
Parallel algorithms for physical design
Author :
Lee, Jong ; Won, Youngju ; Sahni, Sartaj ; Shragowitz, Eugene
Author_Institution :
Minnesota Univ., Minneapolis, MN, USA
Abstract :
Parallel algorithms are developed for three problems that are commonly encountered in the physical design of VLSI circuits. These are maze routing using Lee´s router, the 0/1 knapsack problems, and linear assignment. The latter two problems are frequently encountered in the placement and routing phases of standard cell and sea of gates chip design. The algorithms presented here have been programmed on the NCUBE hypercube multicomputer. Experimental results indicating the amount of speedup achieved are also presented.<>
Keywords :
VLSI; circuit CAD; parallel algorithms; 0/1 knapsack problems; Lee´s router; NCUBE hypercube multicomputer; VLSI; linear assignment; maze routing; physical design; placement; routing phases; sea of gates; standard cell; Algorithm design and analysis; Chip scale packaging; Computer architecture; Hypercubes; Parallel algorithms; Physics computing; Programming profession; Routing; Topology; Very large scale integration;
Conference_Titel :
Circuits and Systems, 1988., IEEE International Symposium on
Conference_Location :
Espoo, Finland
DOI :
10.1109/ISCAS.1988.14931
