hMETIS

hMETIS is a set of programs for partitioning hypergraphs such as those corresponding to VLSI circuits. The algorithms implemented by hMETIS are based on the multilevel hypergraph partitioning schemes developed in our lab. The advantages of hMETIS are the following: Provides high quality partitions! On a wide range of hypergraphs arising in the VLSI domain hMETIS produces bisections that cut 10% to 300% fewer hyperedges than those cut by other popular algorithms such as PARABOLI, PROP, and CLIP-PROP, especially for circuits with over 100,000 cells, and circuits with non-unit cell area. It is extremely fast! A single run of hMETIS is faster than a single run of simpler schemes such as FM, KL, or CLIP. Furthermore, because of its very good average cut characteristics, it produces high quality partitionings in significantly fewer runs. It can bisect circuits with over 100,000 vertices in a couple of minutes on Pentium-class workstations.


References in zbMATH (referenced in 13 articles )

Showing results 1 to 13 of 13.
Sorted by year (citations)

  1. Bergner, Martin; Caprara, Alberto; Ceselli, Alberto; Furini, Fabio; Lübbecke, Marco E.; Malaguti, Enrico; Traversi, Emiliano: Automatic Dantzig-Wolfe reformulation of mixed integer programs (2015)
  2. Akbudak, Kadir; Kayaaslan, Enver; Aykanat, Cevdet: Hypergraph partitioning based models and methods for exploiting cache locality in sparse matrix-vector multiplication (2013)
  3. Ding, Zuohua; Shen, Hui; Kandel, Abraham: Hypergraph partitioning for the parallel computing of fuzzy differential equations (2013)
  4. Kayaaslan, Enver; Pinar, Ali; Çatalyürek, Ümit; Aykanat, Cevdet: Partitioning hypergraphs in scientific computing applications through vertex separators on graphs (2012)
  5. Liang, Zhen; Chi, Zheru; Fu, Hong; Feng, Dagan: Salient object detection using content-sensitive hypergraph representation and partitioning (2012)
  6. Demir, Engin; Aykanat, Cevdet; Cambazoglu, B.Barla: A link-based storage scheme for efficient aggregate query processing on clustered road networks (2010)
  7. de Paulo, Vitor; Ababei, Cristinel: 3D network-on-chip architectures using homogeneous meshes and heterogeneous floorplans (2010)
  8. Uçar, Bora; Çatalyürek, Ümit V.; Aykanat, Cevdet: A Matrix Partitioning Interface to PaToH in MATLAB (2010)
  9. Ababei, Cristinel: Speeding up FPGA placement via partitioning and multithreading (2009)
  10. Li, Jinfeng; Wang, Kanliang; Xu, Lida: Chameleon based on clustering feature tree and its application in customer segmentation (2009)
  11. Aykanat, Cevdet; Cambazoglu, B.Barla; Uçar, Bora: Multi-level direct $K$-way hypergraph partitioning with multiple constraints and fixed vertices (2008)
  12. Trifunović, Aleksandar; Knottenbelt, William J.: Parallel multilevel algorithms for hypergraph partitioning (2008)
  13. Knottenbelt, William J.; Bradley, Jeremy T.: Tackling large state spaces in performance modelling (2007)


Further publications can be found at: http://glaros.dtc.umn.edu/gkhome/metis/hmetis/publications