A Benchmark Set For Multilevel Hypergraph Partitioning Algorithms

DESCRIPTION<br>
-------------------------------------------------------------------------------------------------------<br>
This archive contains a large benchmark set for hypergraph partitioning algorithms.<br>
All hypergraphs are unweighted (i.e., have unit edge and vertex weights) and use<br>
the hMetis hypergraph input file format [1].

BENCHMARK SETS<br>
-------------------------------------------------------------------------------------------------------<br>
Hypergraphs are derived from the following benchmark sets:<br>
- The ISPD98 Circuit Benchmark Suite [2]<br>
- The DAC 2012 Routability-Driven Placement Contest [3]<br>
- The international SAT Competition 2014 [4]<br>
- The University of Florida Sparse Matrix Collection (UF-SPM) [5]

The benchmark set contains all ISPD98 and DAC2012 instances. Furthermore,<br>
it contains 92 randomly selected instances from the application track of the SAT Competition 2014.<br>
The Sparse Matrix Collection is organized into 172 groups and each group contains<br>
matrices of different application areas. From each group, we chose one matrix for each application <br>
area that has between 10 000 and 10.000.000 columns. In case multiple matrices fulfill<br>
our criteria, we randomly selected one. In total, we include 192 matrices.

<br>
HYPERGRAPH REPRESENTATION<br>
-------------------------------------------------------------------------------------------------------<br>
VLSI instances [2,3] are transformed into hypergraphs by converting the netlist into a<br>
set of hyperedges. Sparse Matrices are translated into hypergraphs using the row-net model [6],<br>
i.e. each row is treated as a net and each column as a vertex. SAT instances are converted into<br>
three different hypergraph representations: In the literal model, each boolean literal is mapped to one<br>
vertex and each clause constitutes a net [7]. In the primal model each variable is represented by a vertex<br>
and each clause is represented by a net, whereas in the dual model the opposite is the case [8].

FILE NAMES<br>
-------------------------------------------------------------------------------------------------------<br>
The origin of each hypergraph (and for SAT instances the hypergraph model) is encoded<br>
into the file names as follows:<br>
- Sparse Matrices : *.mtx.hgr<br>
- DAC2012 : dac2012_superblue*.hgr<br>
- ISPD98 : ISPD98_ibm*.hgr<br>
- SAT-14 primal : sat14_*.cnf.primal.hgr<br>
- SAT-14 dual : sat14_*.cnf.dual.hgr<br>
- SAT-14 literal : sat14_*.cnf.hgr

REFERENCES<br>
-------------------------------------------------------------------------------------------------------<br>
[1] http://glaros.dtc.umn.edu/gkhome/fetch/sw/hmetis/manual.pdf<br>
[2] C. J. Alpert. The ISPD98 Circuit Benchmark Suite. In Proc. of the 1998 Int. Symp. on Physical Design, pages 80–85, New York, 1998. ACM.<br>
[3] N. Viswanathan, C. Alpert, C. Sze, Z. Li, and Y/ Wei. The dac 2012 routability-driven placement contest and benchmark suite. In Proceedings of the 49th Annual Design Automation Conference, DAC ’12, pages 774–782<br>
[4] A. Belov, D. Diepold, M. Heule, and M. Järvisalo. The SAT Competition 2014. http://www.satcompetition.org/2014/, 2014.<br>
[5] T. A. Davis and Y. Hu. The University of Florida Sparse Matrix Collection. ACM Trans. Math. Softw.,38(1):1:1–1:25, 2011.<br>
[6] Ü. V. Catalyürek and C. Aykanat. Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication. IEEE Transactions on Parallel and Distributed Systems, 10(7):673–693, Jul 1999.<br>
[7] D. A. Papa and I. L. Markov. Hypergraph Partitioning and Clustering. In T. F. Gonzalez, editor, Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall/CRC, 2007.<br>
[8] Zoltan Mann and Pal Papp. Formula partitioning revisited. In Daniel Le Berre, editor, POS-14. Fifth Pragmatics of SAT workshop, volume 27 of EPiC Series in Computing, pages 41–56. EasyChair, 2014.