Title :
A graphtheoretic approach to the relative placement problem
Author :
Weis, Bernd X. ; Mlynski, Dieter A.
Author_Institution :
Karlsruhe Univ., West Germany
fDate :
3/1/1988 12:00:00 AM
Abstract :
The problem of placing components on a carrier is usually divided into two steps: computation of relative positions of cells; and the final placement so that the cells do not overlap and sufficient area is provided for routing. Using circumscribed rectangles as netmodels, the two-dimensional relative placement problem is translated into two one-dimensional graph-theoretic optimization problems, each of which is a constrained minimization of weighted arc lengths in a placement graph. These optimization problems are solved independently by an exact graph-theoretic algorithm with exponential complexity in the worst case and quadratic in realistic cases. Gate arrays are used as examples
Keywords :
cellular arrays; computational complexity; graph theory; logic design; minimisation of switching nets; network topology; circumscribed rectangles; constrained minimization; exponential complexity; gate arrays; logic design; netmodels; one-dimensional graph-theoretic optimization; placement graph; quadratic complexity; relative placement problem; weighted arc lengths; Bipartite graph; Chip scale packaging; Chromium; Constraint optimization; Equations; Integrated circuit interconnections; Minimization; Pins; Routing; Very large scale integration;
Journal_Title :
Circuits and Systems, IEEE Transactions on
