Multilevel Circuit Clustering for Delay Minimization

Abstract—In this paper, an effective algorithm is presented for multilevel circuit clustering for delay minimization, and is appli-cable to hierarchical field programmable gate arrays. With a novel graph contraction technique, which allows some crucial delay in-formation of a lower-level clustering to be maintained in the con-tracted graph, our algorithm recursively divides the lower-level clustering into the next higher-level one in a way that each recur-sive clustering step is accomplished by applying a modified single-level circuit clustering algorithm based on [1]. We test our algo-rithm on the two-level clustering problem and compare it with the latest algorithm in [2]. Experimental results show that our algo-rithm achieves, on average, 12 % more delay reduction when com-pared to the best results (from TLC with full node-duplication) in [2]. In fact, our algorithm is the first one for the general multilevel circuit clustering problem with more than two levels. Index Terms—Partitioning, performance optimization, physical design, timing optimization, very large scale integration (VLSI). I