Optimal Circuit Clustering for Delay Minimization Under a More General Delay Model

Abstract— This paper considers the area-constrained clustering ofcombinational circuits for delay minimization under a more general delaymodel, which practically takes variable interconnect delay into account.notation of actual delay information to drive the clustering process. Wepresent a vertex grouping technique and integrate it with the algorithm(Rajaraman and Wong, 1995) such that our algorithm can be proved tosolve the problem optimally in polynomial time.Index Terms— Partitioning, performance optimization, physical design,timing optimization, very large scale integration (VLSI). I. I NTRODUCTION Circuit clustering is to assign circuit elements into a number of clus-ters under different design constraints, such as area and/or pin con- Manuscript received May 20, 2002; revised November 3, 2002. This paperwas recommended by Associate Editor M. D. F. Wong.C. N. Sze is with the Department of Electrical Engineering, Texas A&M Uni-versity, College Station, TX 77843-3259 USA (e-mail: cnsze@ee.tamu.edu).T.-C. Wang is with the Department of Computer Science, National Tsing HuaUniversity, Hsinchu 300, Taiwan, R.O.C. (e-mail: tcwang@cs.nthu.edu.tw).Digital Object Identifier 10.1109/TCAD.2003.8107460278-0070/03$17.00 © 2003 IEEE