Title :
A new performance driven placement algorithm
Author :
Gao, T. ; Vaidya, P.M. ; Liu, C.L.
Author_Institution :
Dept. of Comput. Sci., Illinois Univ., Urbana, IL, USA
Abstract :
The authors present a novel performance driven placement algorithm. They use a convex programming algorithm to compute a set of upper bounds on the net wire lengths. A modified min-cut algorithm is then used to generate a placement with the objective of minimizing the number of nets, the wire lengths of which exceed their corresponding upper bounds. The situation in which the modified min-cut algorithm fails to generate a placement that satisfies the timing requirements is addressed, and an iterative approach is used to modify the set of upper bounds making use of information from previous placements. The algorithm was implemented in C and tested on eight problems on a Sparc 2 workstation.<>
Keywords :
circuit layout CAD; computational complexity; convex programming; minimisation of switching nets; C language; Sparc 2 workstation; convex programming algorithm; min-cut algorithm; net minimisation; net wire lengths; performance driven placement algorithm; upper bounds; wire lengths; Algorithm design and analysis; Circuits; Computer science; Delay; Iterative algorithms; Iterative methods; Joining processes; Timing; Upper bound; Wire;
Conference_Titel :
Computer-Aided Design, 1991. ICCAD-91. Digest of Technical Papers., 1991 IEEE International Conference on
Conference_Location :
Santa Clara, CA, USA
Print_ISBN :
0-8186-2157-5
DOI :
10.1109/ICCAD.1991.185187