Article

Clustering based acyclic multi-way partitioning

Authors:

Eric S. H. Wong,

Evangeline F. Y. Young,

W. K. MakAuthors Info & Claims

GLSVLSI '03: Proceedings of the 13th ACM Great Lakes symposium on VLSI

Pages 203 - 206

https://doi.org/10.1145/764808.764860

Published: 28 April 2003 Publication History

Get Access

Abstract

In this paper, we present a clustering based algorithm for acyclic multi-way partitioning. Many existing partitioning algorithms have shown that clustering can effectively improve the solution quality. However, most of them do not consider the signal direction and thus cannot maintain the acyclic property. Our algorithm is based on clustering by computing the modified fan-out free cones. Fan-out free cone clustering can reduce a graph to a smaller and sparser one, and maintain the acyclic property at the same time. Experimental results showed that our algorithm compares favorably with the previous best acyclic multi-way partitioning algorithm in cut-size.

References

[1]

C. J. Alpert, J. H. Huang, and A. B. Kahng. Multilevel circuit partitioning. DAC, pages 530--533, 1997.

Digital Library

Google Scholar

[2]

J. Cong, Z. Li, and R. Bagrodia. Acyclic multi-way partitioning of boolean networks. Proceeding ACM/IEEE 31st Design Automation Conference, pages 670--675, June 1994.

Digital Library

Google Scholar

[3]

C. M. Fiduccia and R. M. Mattheyses. A linear-time heuristic for improving network partitions. Design Automation Conference, pages 241--247, 1982.

Digital Library

Google Scholar

[4]

G. Karypis and V. Kumar. Multilevel k-way hypergraph partitioning. ACM/IEEE Design Automation Conference, pages 343--348, 1999.

Digital Library

Google Scholar

[5]

B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, pages 291--307, 1970.

Google Scholar

[6]

H. Liu and D. F. Wong. Network flow based circuit partitioning for time-multiplexed fpga. ICCAD, pages 497--504, 1998.

Digital Library

Google Scholar

[7]

H. Yang and D. F. Wong. Efficient network flow based min-cut balanced partitioning. IEEE ICCAD, pages 50--55, November 1994.

Digital Library

Google Scholar

[8]

H. Yang and D. F. Wong. New algorithms for min-cut replication in partitioned circuits. ICCAD, pages 216--222, 1995.

Digital Library

Google Scholar

[9]

R. Boppana. Eigenvalues and Graph Bisection: An Average-Case Analysis. IEEE Symp. on Foundations of Computer Science, pages 280--285, 1987.

Google Scholar

[10]

P. K. Chan and D. F. Schlag and J. Zien. Spectral K-way Ratio-Cut Partitioning and Clustering. Proceeding ACM/IEEE Design Automation Conference, pages 749--754, 1993.

Digital Library

Google Scholar

Cited By

View all

Herrmann JKho JUçar BKaya KÇatalyürek Ü(2017)Acyclic Partitioning of Large Directed Acyclic GraphsProceedings of the 17th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing10.1109/CCGRID.2017.101(371-380)Online publication date: 14-May-2017
https://dl.acm.org/doi/10.1109/CCGRID.2017.101
Tai TLai Y(2011)A Performance-Oriented Algorithm with Consideration on Communication Cost for Dynamically Reconfigurable FPGA PartitioningACM Transactions on Reconfigurable Technology and Systems10.1145/1968502.19685074:2(1-18)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1145/1968502.1968507
Kerkiz NElchouemi ABouldin D(2010)Multi-FPGA partitioning method based on topological levelizationJournal of Electrical and Computer Engineering10.1155/2010/7094872010(1-7)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1155/2010/709487
Show More Cited By

Index Terms

Clustering based acyclic multi-way partitioning
1. Applied computing
  1. Arts and humanities
    1. Architecture (buildings)
      1. Computer-aided design
  2. Physical sciences and engineering
    1. Engineering
      1. Computer-aided design

Recommendations

On the Impact of Post-clustering Phase in Multi-way Spectral Partitioning
MIKE 2015: Proceedings of the Third International Conference on Mining Intelligence and Knowledge Exploration - Volume 9468

Spectral clustering is one of the most popular modern graph clustering techniques in machine learning. By using the eigenvalue analysis, spectral methods partition the given set of points into number of disjoint groups. Spectral methods are very useful ...
A new hybrid method based on partitioning-based DBSCAN and ant clustering

Clustering problem is an unsupervised learning problem. It is a procedure that partition data objects into matching clusters. The data objects in the same cluster are quite similar to each other and dissimilar in the other clusters. Density-based ...
Global clustering-based performance-driven circuit partitioning
ISPD '02: Proceedings of the 2002 international symposium on Physical design

In this paper, we propose a new global clustering based multi-level partitioning algorithm for performance optimization. Our algorithm computes a delay minimal K-way partition first, then gradually reduces the cutsize while keeping the circuit delay by ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GLSVLSI '03: Proceedings of the 13th ACM Great Lakes symposium on VLSI

April 2003

320 pages

ISBN:1581136773

DOI:10.1145/764808

General Chair:
Mircea Stan
University of Virginia
,
Program Chairs:
David Garrett
Bell Labs Research, Lucent Technologies
,
Kazuo Nakajima
University of Maryland

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 April 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GLSVLSI03

Sponsor:

GLSVLSI03: Great Lakes Symposium on VLSI 2003

April 28 - 29, 2003

D. C., Washington, USA

Acceptance Rates

Overall Acceptance Rate 312 of 1,156 submissions, 27%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
170
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Herrmann JKho JUçar BKaya KÇatalyürek Ü(2017)Acyclic Partitioning of Large Directed Acyclic GraphsProceedings of the 17th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing10.1109/CCGRID.2017.101(371-380)Online publication date: 14-May-2017
https://dl.acm.org/doi/10.1109/CCGRID.2017.101
Tai TLai Y(2011)A Performance-Oriented Algorithm with Consideration on Communication Cost for Dynamically Reconfigurable FPGA PartitioningACM Transactions on Reconfigurable Technology and Systems10.1145/1968502.19685074:2(1-18)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1145/1968502.1968507
Kerkiz NElchouemi ABouldin D(2010)Multi-FPGA partitioning method based on topological levelizationJournal of Electrical and Computer Engineering10.1155/2010/7094872010(1-7)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1155/2010/709487
Rung-Bin Lin Tsung-Han Lin Shin-An Wu (2009)Circuit acyclic clustering with input/output constraints and applications2009 International Symposium on VLSI Design, Automation and Test10.1109/VDAT.2009.5158107(110-113)Online publication date: Apr-2009
https://doi.org/10.1109/VDAT.2009.5158107
Yan Gu Wei Tsang Ooi (2005)Packetization of 3D progressive meshes for streaming over lossy networksProceedings. 14th International Conference on Computer Communications and Networks, 2005. ICCCN 2005.10.1109/ICCCN.2005.1523900(415-420)Online publication date: 2005
https://doi.org/10.1109/ICCCN.2005.1523900
Kocan FGunes M(2005)Acyclic circuit partitioning for path delay fault emulationThe 3rd ACS/IEEE International Conference onComputer Systems and Applications, 2005.10.1109/AICCSA.2005.1387021(76-80)Online publication date: 2005
https://doi.org/10.1109/AICCSA.2005.1387021

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

On the Impact of Post-clustering Phase in Multi-way Spectral Partitioning

A new hybrid method based on partitioning-based DBSCAN and ant clustering

Global clustering-based performance-driven circuit partitioning