skip to main content
10.1145/1118299.1118480acmconferencesArticle/Chapter ViewAbstractPublication PagesaspdacConference Proceedingsconference-collections
Article

SAT-based optimal hypergraph partitioning with replication

Published: 24 January 2006 Publication History

Abstract

We propose a methodology for optimal k-way partitioning with replication of directed hypergraphs via Boolean satisfiability. We begin by leveraging the power of existing and emerging SAT solvers to attack traditional logic bipartitioning and show good scaling behavior. We continue to present the first optimal partitioning results that admit generation and assignment of replicated nodes concurrently. Our framework is general enough that we also give the first published optimal results for partitioning with respect to the maximum subdomain degree metric and the sum of external degrees metric.We show that for the bipartitioning case we can feasibly solve problems of up to 150 nodes with simultaneous replication in hundreds of seconds. For other partitioning metrics, we are able to solve problems up to 40 nodes in hundreds of seconds.

References

[1]
F. M. Johannes, "Partitioning of VLSI Circuits and Systems," presented at ACM/IEEE Design Automation Conference, 1996.
[2]
A. E. Caldwell, A. B. Kahng, and I. L. Markov, "Optimal Partitioners and End-case Placers for Standard-cell Layout," IEEE Transactions on Computer-Aided Design, vol. 19, pp. 1304--1313, 2000.
[3]
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness: W. H. Freeman, 1979.
[4]
S. Devadas, "Optimal Layout via Boolean Satisfiability," presented at International Conference on Computer-Aided Design, 1989.
[5]
L. Zhang and S. Malik, "The Quest for Efficient Boolean Satisfiability Solvers," presented at International Conference on Computer Aided Verification, Copenhagen, 2002.
[6]
V. Betz and J. Rose, "Cluster-Based Logic Blocks for FPGAs: Area-Efficiency vs. Input Sharing and Size," presented at IEEE Custom Integrated Circuits Conference, 1997.
[7]
G. Karypis and V. Kumar, "Multilevel K-way Hypergraph Partitioning," presented at Design Automation Conference, 1999.
[8]
N. Selvakkumaran and G. Karypis, "Multi-Objective Hypergraph Partitioning Algorithms for Cut and Maximum Subdomain Degree Minimization," presented at International Conference on Computer-Aided Design, 2003.
[9]
W.-K. Mak and D. F. Wong, "Minimum Replication Min-Cut Partitioning," IEEE Transactions on Computed-Aided Design for Integrated Circuits and Systems, vol. 16, pp. 1221--1227, 1997.
[10]
L. J. Hwang and A. E. Gamal, "Min-Cut Replication in Partitioned Networks," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 14, pp. 96--106, 1995.
[11]
M. Wallace and A. Veron, "Two Problems - Two Solutions: One System - Eclipse," presented at IEE Colloquium on Advanced Software Technologies for Scheduling, 1993.
[12]
O. Bailleux and Y. Boufkhad, "Full CNF-Encoding: The Counting Constraints Case," presented at International Conference on Theory and Applications of Satisfiability Testing, 2004.
[13]
L. Ryan, Efficient Algorithms for Clause-Learning SAT Solvers. Masters thesis: Simon Fraser University, 2004.
[14]
O. Bailleux and Y. Boufkhad, "Efficient CNF Encodings of Boolean Cardinality Constraints," presented at International Conference on the Principles and Practice of Constraint Programming, 2003.
[15]
J. M. Silva, Personal Website. http://sat.inesc-id.pt/~jpms/scripts/.
[16]
J. Cong and Y. Ding, "FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs," IEEE Transactions on Computer-Aided Design, vol. 13, pp. 1--12, 1994.
[17]
A. Nadel, Backtrack Search Algorithms for Propositional Logic Satisfiability. Masters thesis: Tel-Aviv University, 2002.
[18]
N. Eén and N. Sörensson, "An Extensible SAT-solver," presented at International Conference on Theory and Applications of Satisfiability Testing, 2003.

Cited By

View all
  • (2019)SIP shakerProceedings of the 35th Annual Computer Security Applications Conference10.1145/3359789.3359848(203-214)Online publication date: 9-Dec-2019

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ASP-DAC '06: Proceedings of the 2006 Asia and South Pacific Design Automation Conference
January 2006
998 pages
ISBN:0780394518

Sponsors

  • IEEE Circuits and Systems Society
  • SIGDA: ACM Special Interest Group on Design Automation
  • IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
  • IPSJ SIG-SLDM: Information Processing Society of Japan, SIG System LSI Design Methodology

Publisher

IEEE Press

Publication History

Published: 24 January 2006

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Upcoming Conference

ASPDAC '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)12
  • Downloads (Last 6 weeks)8
Reflects downloads up to 07 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2019)SIP shakerProceedings of the 35th Annual Computer Security Applications Conference10.1145/3359789.3359848(203-214)Online publication date: 9-Dec-2019

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media