Performance-driven multi-level clustering for combinational circuits

In this paper, an effective algorithm is presented for performance driven multi-level clustering for combinational circuits, and is applicable to hierarchical FPGAs. With a novel graph contraction technique, which allows some crucial delay information of a lower-level clustering to be maintained in the contracted graph, our algorithm recursively divides the lower-level clustering into the next higher-level one in a way that each recursive clustering step is accomplished by applying a modified single-level circuit clustering algorithm based on (R. Rajaraman et al, CAD of ICs and Systems, vol. 14, no. 12, pp. 1490-1495, 1995). We test our algorithm on the two-level clustering problem and compare it with the latest algorithm in (J. Cong et al, ACM/IEEE Design Automation Conf., pp. 389-394, 2001). Experimental results show that our algorithm achieves, on average, 12% more delay reduction when compared to the best results (from TLC with full node-duplication) of the aforementioned algorithm. In fact, our algorithm is the first one for the general multi-level circuit clustering problem with more than two levels.