A clustering based linear ordering algorithm for netlist partitioning

Abstract

In this paper, we propose a clustering based linear ordering algorithm which consists of global ordering and local ordering. In the global ordering, the algorithm forms clusters from n given vertices and orders the clusters. In the local ordering, the elements in each cluster are linearly ordered. The linear order, thus produced, is used to obtain optimal k-way partitioning based on scaled cost objective function. When the number of cluster is one, the proposed algorithm is exactly the same as MELO [2]. But the proposed algorithm has more global partitioning information than MELO by clustering. Experiment with 11 benchmark circuits for k-way (2 less than or equal to k less than or equal to 10) partitioning shows that the proposed algorithm yields an average of 10.6% improvement over MELO [2] for the k-way scaled cost partitioning.