Article

Free access

New algorithms for min-cut replication in partitioned circuits

Authors:

Hannah Honghua Yang,

D. F. WongAuthors Info & Claims

ICCAD '95: Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design

Pages 216 - 222

Published: 01 December 1995 Publication History

PDF eReader Publisher Site

Abstract

Abstract: Hwang and El Gamal (1992, 1995) formulated the min-cut replication problem, which is to determine min-cut replication sets for the components of a k-way partition such that the cut size of the partition is minimized after the replication. They gave an optimal algorithm for finding min-cut replication sets for a k-way partitioned digraph. However, their optimal min-cut replication algorithm does not guarantee min-cut replication sets of minimum sizes. Furthermore, their algorithm is not optimal for hypergraphs. In this paper, we optimally solve the min-area min-cut replication problem on digraphs, which is to find min-cut replication sets with the minimum sizes. More importantly, we give an optimal solution to the hypergraph min-area min-cut replication problem using a much smaller flow network model. We implemented our algorithms in a package called Hyper-MAMC, and interfaced Hyper-MAMC to the TAPIR package. On average, Hyper-MAMC produces 57.3% fewer cut nets and runs much faster than MO-Rep in the TAPIR package, on the same initial partitions of a set of MCNC Partition93 benchmark circuits.

References

[1]

J. Cong, L. Hagen, and A. Kahng. Net Partitions Yield Better Module Partitions. In Proc. of the 29th A CM/IEEE Design Automation Conf., pages 47-52, 1992.

Digital Library

[2]

J.R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.

[3]

C.M. Fiduccia and R. M. Mattheyses. A Linear Time Heuristic for Improving Network Partitions. In Proc. of the AUM/IEEE Design A utomation Conf., pages 175-181, 1982.

Digital Library

[4]

J. Hwang and A. E1 Gamal. Optimal Replication for Min-Cut Partitioning. In Proc. of the IEEE Int'l Conf. on Computer-Aided Design, pages 432-435, Nov. 1992.

Digital Library

[5]

J. Hwang and A. E1 Gamal. Min-Cut Replication in Partitioned Networks. IEEE Trans. on CAD, 14(1):96-106, Jan. 1995.

Digital Library

[6]

L. Hagen and A. B. Kahng. Fast Spectral Methods for Ratio Cut Partitioning and Clustering. In Proc. of the IEEE Int'l Conf. on Computer- Aided Design, pages 10-13, Nov. 1991.

[7]

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by Simulated Annealing. Science, pages 671-680, May 1983.

[8]

B. Kernighan and S. Lin. An Efficient Heuristic Procedure for Partitioning of Electrical Circuits. Bell System Technical Journal, pages 291-307, Feb. 1970.

[9]

C. Kring and A. R. Newton. A Cell-Replicating Approach to Mincut-Based Circuit Partitioning. In Proc. of the IEEE Int'l Conf. on Computer- Aided Design, pages 2-5, Nov. 1991.

[10]

L.-T. Liu, M.-T. Kuo, C.-K. Cheng, and T. C. Hu. A Replication Cut for Two-Way Partitioning. IEEE Trans. on CAD, 14(5):623-630, May 1995.

Digital Library

[11]

R. Murgai, R. K. Brayton, and A. Sangiovanni- Vincentelli. On Clustering for Minimum Delay/Area. In Proc. of the IEEE Int'l Conf. on Computer-Aided Design, pages 6-9, 1991.

[12]

B. Preas and M. Lorenzetti. Physical Design Automation of VLSI Systems. Benjamin/Cummings, 1988.

[13]

R. Rajaraman and D. F. Wong. Optimal Cluetering for Delay Minimization. In Proc. 30th A CM/IEEE Design Automation Conf., pages 309-314, 1993.

Digital Library

[14]

Y.C. Wei and C. K. Cheng. Towards Efficient Hierarchical Designs by Ratio Cut Partitioning. In Proc. of the IEEE Int'l Conf. on Computer- Aided Design, pages 298-301, Nov. 1989.

[15]

H. Yang and D. F. Wong. Efficient Network Flow Based Min-Cut Balanced Partitioning. In Proc. of the IEEE Int'l Conf. on Computer-Aided Design, pages 50-55, Nov. 1994.

Digital Library

Cited By

Chaudhary AChen DWhitton KNiemier MRavichandran R(2005)Eliminating wire crossings for molecular quantum-dot cellular automata implementationProceedings of the 2005 IEEE/ACM International conference on Computer-aided design10.5555/1129601.1129681(565-571)Online publication date: 31-May-2005
https://dl.acm.org/doi/10.5555/1129601.1129681
Wong EYoung EMak WStan MGarrett DNakajima K(2003)Clustering based acyclic multi-way partitioningProceedings of the 13th ACM Great Lakes symposium on VLSI10.1145/764808.764860(203-206)Online publication date: 28-Apr-2003
https://dl.acm.org/doi/10.1145/764808.764860
Mak WYoung ESapatnekar SPedram M(2002)Temporal logic replication for dynamically reconfigurable FPGA partitioningProceedings of the 2002 international symposium on Physical design10.1145/505388.505434(190-195)Online publication date: 7-Apr-2002
https://dl.acm.org/doi/10.1145/505388.505434
Show More Cited By

Index Terms

New algorithms for min-cut replication in partitioned circuits

Recommendations

Optimal min-area min-cut replication in partitioned circuits

Previous results show that node replication can be used to reduce the number of cut edges substantially in a partitioned circuit. The node replication approach is particularly useful for fully utilizing pin-limited devices such as multiple field-...
Cluster-aware iterative improvement techniques for partitioning large VLSI circuits

Move-based iterative improvement partitioning (IIP) methods, such as the Fiduccia-Mattheyses (FM) algorithm [Fidducia and Mattheyses 1982] and Krishnamurthy's Look-Ahead (LA) algorithm [Krishnamurthy 1984], are widely used in VLSI CAD applications, ...
VLSI circuit partitioning by cluster-removal using iterative improvement techniques
ICCAD '96: Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design

Move-based iterative improvement partitioning methods such as the Fiduccia-Mattheyses (FM) algorithm and Krishnamurthy's Look-Ahead (LA) algorithm are widely used in VLSI CAD applications largely due to their time efficiency and ease of implementation. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '95: Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design

December 1995

748 pages

ISBN:0818672137

Chairman:
Richard Rudell
Synopsys, Inc., Mountain View, CA

Copyright © Copyright (c) 1995 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS: Computer Society

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 December 1995

Check for updates

Author Tags

Qualifiers

Article

Conference

ICCAD '95

Sponsor:

SIGDA
IEEE-CS

ICCAD '95: International Conference on Computer Aided Design

November 5 - 9, 1995

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
424
Total Downloads

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

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chaudhary AChen DWhitton KNiemier MRavichandran R(2005)Eliminating wire crossings for molecular quantum-dot cellular automata implementationProceedings of the 2005 IEEE/ACM International conference on Computer-aided design10.5555/1129601.1129681(565-571)Online publication date: 31-May-2005
https://dl.acm.org/doi/10.5555/1129601.1129681
Wong EYoung EMak WStan MGarrett DNakajima K(2003)Clustering based acyclic multi-way partitioningProceedings of the 13th ACM Great Lakes symposium on VLSI10.1145/764808.764860(203-206)Online publication date: 28-Apr-2003
https://dl.acm.org/doi/10.1145/764808.764860
Mak WYoung ESapatnekar SPedram M(2002)Temporal logic replication for dynamically reconfigurable FPGA partitioningProceedings of the 2002 international symposium on Physical design10.1145/505388.505434(190-195)Online publication date: 7-Apr-2002
https://dl.acm.org/doi/10.1145/505388.505434
Mak WSapatnekar SWiesel M(2001)Min-cut partitioning with functional replication for technology mapped circuits using minimum area overheadProceedings of the 2001 international symposium on Physical design10.1145/369691.369746(100-105)Online publication date: 1-Apr-2001
https://dl.acm.org/doi/10.1145/369691.369746
Enos MHauck SSarrafzadeh MOtten RYasuura H(1997)Replication for logic bipartitioningProceedings of the 1997 IEEE/ACM international conference on Computer-aided design10.5555/266388.266504(342-349)Online publication date: 13-Nov-1997
https://dl.acm.org/doi/10.5555/266388.266504
Mak WWong DRutenbar ROtten R(1997)Minimum replication min-cut partitioningProceedings of the 1996 IEEE/ACM international conference on Computer-aided design10.5555/244522.244557(205-210)Online publication date: 1-Jan-1997
https://dl.acm.org/doi/10.5555/244522.244557
Johannes FPennino TYoffa E(1996)Partitioning of VLSI circuits and systemsProceedings of the 33rd annual Design Automation Conference10.1145/240518.240535(83-87)Online publication date: 1-Jun-1996
https://dl.acm.org/doi/10.1145/240518.240535

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents