Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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: Frank M. Johannes, Partitioning of VLSI circuits and systems, Proceedings of the 33rd annual conference on Design automation, p.83-87, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240535]
• 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: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 4: S. Devadas, "Optimal Layout via Boolean Satisfiability," presented at International Conference on Computer-Aided Design, 1989.
• 5: Lintao Zhang , Sharad Malik, The Quest for Efficient Boolean Satisfiability Solvers, Proceedings of the 14th International Conference on Computer Aided Verification, p.17-36, July 27-31, 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: George Karypis , Vipin Kumar, Multilevel k-way hypergraph partitioning, Proceedings of the 36th ACM/IEEE conference on Design automation, p.343-348, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309954]
• 8: Navaratnasothie Selvakkumaran , George Karypis, Multi.Objective Hypergraph Partitioning Algorithms for Cut and Maximum Subdomain Degree Minimization, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.726, November 09-13, 2003 [doi>10.1109/ICCAD.2003.102]
• 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.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids
  B.m MISCELLANEOUS
      Subjects: Design management

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Hypergraphs

General Terms:
Algorithms, Design, Performance