Title :
Recursive and flat partitioning for VLSI circuit design
Author_Institution :
Sch. of Eng., Guelph Univ., Ont., Canada
Abstract :
Circuit partitioning is a subproblem of the physical design phase and considered to be a very important tool for circuit layout. Recent work of Cong and Lim (1998) suggests that multi-way bi-partitioning is more effective than hierarchical bi-partitioning based on a recursive scheme, in addition to the limitation of recursive multi-way partitioners to minimize absorption cost metrics but not hyper-edge cost metrics. In this paper, we use a modified recursive multi-way partitioner to prove that hierarchical bi-partitioning is more effective than multi-way partitioning for both cost metrics. Results obtained indicate that hierarchical bi-partitioning obtains cutsize results that are on average 25% and 55% better than a multiway flat partitioning based on the hyper-edge and absorption costs, respectively. In addition, a combined hierarchical bi-partitioning followed by a multiway flat partitioning scheme improves results on average by 42% for the hyper-edge cost metric.
Keywords :
VLSI; integrated circuit layout; logic partitioning; VLSI design cycle; absorption cost metrics; circuit layout; cutsize results; flat partitioning; hierarchical bi-partitioning; hyper-edge cost metrics; logic element interconnections; multi-way bi-partitioning; physical design phase; recursive multi-way partitioner; recursive multi-way partitioners; recursive partitioning; Absorption; Circuit synthesis; Clustering algorithms; Cost function; Design engineering; Iterative algorithms; Iterative methods; Partitioning algorithms; Power engineering and energy; Very large scale integration;
Conference_Titel :
Microelectronics, 2001. ICM 2001 Proceedings. The 13th International Conference on
Print_ISBN :
0-7803-7522-X
DOI :
10.1109/ICM.2001.997654