A CLUSTERING BASED LINEAR ORDERING ALGORITHM FOR NETLIST PARTITIONING

In this paper, we propose a clustering based linear ordering algorithm which consists of global ordering and local ordering. In the global o rdering, 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. Wh en the number of cluster is one, the proposed algorithm is exactly the same as MELO [2]. But the proposed algorithm has more global partitio ning 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 1 0) partitioning shows that the proposed algorithm yields an average of 10.6% improvement over MELO [2] for the k-way scaled cost partitionin g.