DocumentCode
1651466
Title
Parallel algorithms for physical design
Author
Lee, Jong ; Won, Youngju ; Sahni, Sartaj ; Shragowitz, Eugene
Author_Institution
Minnesota Univ., Minneapolis, MN, USA
fYear
1988
Firstpage
325
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Circuits and Systems, 1988., IEEE International Symposium on
Conference_Location
Espoo, Finland
Type
conf
DOI
10.1109/ISCAS.1988.14931
Filename
14931
Link To Document