DESCRIPTION ------------------------------------------------------------------------------------------------------- This archive contains a large benchmark set for hypergraph partitioning algorithms. All hypergraphs are unweighted (i.e., have unit edge and vertex weights) and use the hMetis hypergraph input file format [1]. BENCHMARK SETS ------------------------------------------------------------------------------------------------------- Hypergraphs are derived from the following benchmark sets: - The ISPD98 Circuit Benchmark Suite [2] - The DAC 2012 Routability-Driven Placement Contest [3] - The international SAT Competition 2014 [4] - The University of Florida Sparse Matrix Collection (UF-SPM) [5] The benchmark set contains all ISPD98 and DAC2012 instances. Furthermore, it contains 92 randomly selected instances from the application track of the SAT Competition 2014. The Sparse Matrix Collection is organized into 172 groups and each group contains matrices of different application areas. From each group, we chose one matrix for each application area that has between 10 000 and 10.000.000 columns. In case multiple matrices fulfill our criteria, we randomly selected one. In total, we include 192 matrices. HYPERGRAPH REPRESENTATION ------------------------------------------------------------------------------------------------------- VLSI instances [2,3] are transformed into hypergraphs by converting the netlist into a set of hyperedges. Sparse Matrices are translated into hypergraphs using the row-net model [6], i.e. each row is treated as a net and each column as a vertex. SAT instances are converted into three different hypergraph representations: In the literal model, each boolean literal is mapped to one vertex and each clause constitutes a net [7]. In the primal model each variable is represented by a vertex and each clause is represented by a net, whereas in the dual model the opposite is the case [8]. FILE NAMES ------------------------------------------------------------------------------------------------------- The origin of each hypergraph (and for SAT instances the hypergraph model) is encoded into the file names as follows: - Sparse Matrices : *.mtx.hgr - DAC2012 : dac2012_superblue*.hgr - ISPD98 : ISPD98_ibm*.hgr - SAT-14 primal : sat14_*.cnf.primal.hgr - SAT-14 dual : sat14_*.cnf.dual.hgr - SAT-14 literal : sat14_*.cnf.hgr REFERENCES ------------------------------------------------------------------------------------------------------- [1] http://glaros.dtc.umn.edu/gkhome/fetch/sw/hmetis/manual.pdf [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. [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 [4] A. Belov, D. Diepold, M. Heule, and M. Järvisalo. The SAT Competition 2014. http://www.satcompetition.org/2014/, 2014. [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. [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. [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. [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.