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 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 l1 benchmark circuits for k-way (2 ≦ k ≦ 10) partitioning shows that the proposed algorithm yields an average of 10.6% im-provement over MELO [2] for the k-way scaled cost partitioning.key words: netlist partitioning spectral Method linear ordering
社団法人電子情報通信学会の論文
1996-12-25