Title :
A circuit partitioning algorithm under path delay constraints
Author :
Minami, Jun´ Ichiro ; Koide, Tetsushi ; Wakabayashi, Shin´ Ichi
Author_Institution :
Fac. of Eng., Hiroshima Univ., Japan
Abstract :
This paper presents a timing-driven circuit partitioning algorithm for the general delay model. The proposed algorithm consists of the clustering and iterative improvement phases. In the first phase, we reduce the problem size, that is the size of a given graph, with a new clustering algorithm to obtain a partition in a short computation time. Next, the iterative improvement phase based on the Fiduccia and Mattheyses algorithm is applied and then a new path-based timing violation removal algorithm is also performed so as to remove all the timing violations. From experimental results for ISCAS89 benchmarks, we have demonstrated that the proposed algorithm can produce the partitions which mostly satisfy the timing constraints
Keywords :
VLSI; circuit layout CAD; delays; integrated circuit layout; iterative methods; timing; circuit partitioning algorithm; clustering algorithm; general delay model; iterative improvement phase; path delay constraints; path-based timing violation removal algorithm; timing-driven partitioning algorithm; Circuits; Clustering algorithms; Delay; Iterative algorithms; Iterative methods; Partitioning algorithms; Size control; Timing; Very large scale integration; Wire;
Conference_Titel :
Circuits and Systems, 1998. IEEE APCCAS 1998. The 1998 IEEE Asia-Pacific Conference on
Conference_Location :
Chiangmai
Print_ISBN :
0-7803-5146-0
DOI :
10.1109/APCCAS.1998.743671