Title :
On the design of a parallel algorithm for VLSI layout compaction
Author :
Thulasiraman, K. ; Comeau, M.A. ; Chalasani, R.P. ; Das, A. ; Atwood, J.W.
Author_Institution :
Concordia Univ., Montreal, Que., Canada
Abstract :
The essential features of an approach to the design of a parallel algorithm for the layout compaction problem are presented. A previously presented formulation of the problem is given in terms of the dual transshipment problem. The approach to the solution of the dual transshipment problem involves repeated applications of three basic steps: testing feasibility, shortest-path computations, and performing concurrent pivot operations. A discussion in terms of market graph concepts and previously presented results is given. The approach can also be used in the study of the relative placement problem
Keywords :
VLSI; circuit layout CAD; parallel algorithms; VLSI layout compaction; dual transshipment problem; layout compaction problem; market graph concepts; parallel algorithm design; performing concurrent pivot operations; relative placement problem; repeated applications; shortest-path computations; testing feasibility; Algorithm design and analysis; Compaction; Computer science; Concurrent computing; Design engineering; Parallel algorithms; Performance evaluation; Testing; Topology; Very large scale integration;
Conference_Titel :
Circuits and Systems, 1990., IEEE International Symposium on
Conference_Location :
New Orleans, LA
DOI :
10.1109/ISCAS.1990.112038
