Title :
Timing-driven bipartitioning with replication using iterative quadratic programming
Author :
Ou, Shihliang ; Pedram, Massoud
Author_Institution :
Dept. of Electr. Eng., Univ. of Southern California, Los Angeles, CA, USA
Abstract :
We present an algorithm for solving a general min-cut, two-way partitioning problem subject to timing constraints. The problem is formulated as a constrained programming problem and solved in two phases: cut-set minimization and timing satisfaction. A mathematical programming technique based on iterative quadratic programming (TPIQ) is used to find an approximate solution to the constrained problem. When the timing constraints are too strict to have a feasible solution, node replication is used to satisfy the constraints. Experimental results on the ISCAS89 benchmark suite show that TPIQ can solve the timing-driven bipartitioning problem with little impact on the chip size
Keywords :
VLSI; circuit layout CAD; delay estimation; integrated circuit layout; iterative methods; quadratic programming; timing; TPIQ algorithm; VLSI design; constrained programming problem; cut-set minimization; iterative quadratic programming; mathematical programming technique; min-cut two-way partitioning problem; node replication; timing constraints; timing satisfaction; timing-driven bipartitioning; CMOS process; Circuit optimization; Delay; Iterative algorithms; Mathematical programming; Minimization; Partitioning algorithms; Quadratic programming; Timing; Very large scale integration;
Conference_Titel :
Design Automation Conference, 1999. Proceedings of the ASP-DAC '99. Asia and South Pacific
Conference_Location :
Wanchai
Print_ISBN :
0-7803-5012-X
DOI :
10.1109/ASPDAC.1999.759724
