A Clustering Based Linear Ordering Algorithm for Netlist Partitioning

Kwang-Su SEONG; Chong-Min KYUNG

A Clustering Based Linear Ordering Algorithm for Netlist Partitioning

Kwang-Su SEONG, Chong-Min KYUNG

Full Text Views

0

Cite this

Summary :

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 κ-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 κ-way (2 κ 10) partitioning shows that the proposed algorithm yields an average of 10.6% improvement over MELO [2] for the κ-way scaled cost partitioning.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E79-A No.12 pp.2185-2191

Publication Date: 1996/12/25

Publicized

Online ISSN

DOI

Type of Manuscript: LETTER

Category: VLSI Design Technology and CAD

Cite this

Copy

Kwang-Su SEONG, Chong-Min KYUNG, "A Clustering Based Linear Ordering Algorithm for Netlist Partitioning" in IEICE TRANSACTIONS on Fundamentals, vol. E79-A, no. 12, pp. 2185-2191, December 1996, doi: .
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 κ-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 κ-way (2 κ 10) partitioning shows that the proposed algorithm yields an average of 10.6% improvement over MELO [2] for the κ-way scaled cost partitioning.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e79-a_12_2185/_p

Copy

@ARTICLE{e79-a_12_2185,
author={Kwang-Su SEONG, Chong-Min KYUNG, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Clustering Based Linear Ordering Algorithm for Netlist Partitioning},
year={1996},
volume={E79-A},
number={12},
pages={2185-2191},
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 κ-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 κ-way (2 κ 10) partitioning shows that the proposed algorithm yields an average of 10.6% improvement over MELO [2] for the κ-way scaled cost partitioning.},
keywords={},
doi={},
ISSN={},
month={December},}

Copy

TY - JOUR
TI - A Clustering Based Linear Ordering Algorithm for Netlist Partitioning
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2185
EP - 2191
AU - Kwang-Su SEONG
AU - Chong-Min KYUNG
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E79-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 1996
AB - 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 κ-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 κ-way (2 κ 10) partitioning shows that the proposed algorithm yields an average of 10.6% improvement over MELO [2] for the κ-way scaled cost partitioning.
ER -