Parallel partitioning with Zoltan: is hypergraph partitioning worth it? Graph partitioning is an important and well studied problem in combinatorial scientific computing, and is commonly used to reduce communication in parallel computing. Different models (graph, hypergraph) and objectives (edge cut, boundary vertices) have been proposed. Hypergraph partitioning has become increasingly popular over the last decade. Its main strength is that it accurately captures communication volume, but it is slower to compute than graph partitioning. par We present an empirical study of the Zoltan parallel hypergraph and graph (PHG) partitioner on graphs from the 10th DIMACS implementation challenge and some directed (nonsymmetric) graphs. We show that hypergraph partitioning is superior to graph partitioning on directed graphs (nonsymmetric matrices), where the communication volume is reduced in several cases by over an order of magnitude, but has no significant benefit on undirected graphs (symmetric matrices) using current parallel software tools.

References in zbMATH (referenced in 26 articles , 1 standard article )

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

1 2 next

  1. Lee, J.; Cookson, A.; Roy, I.; Kerfoot, E.; Asner, L.; Vigueras, G.; Sochi, T.; Deparis, S.; Michler, C.; Smith, N.P.; Nordsletten, D.A.: Multiphysics computational modeling in $\mathcalC\boldHeart$ (2016)
  2. Isaac, Tobin; Burstedde, Carsten; Wilcox, Lucas C.; Ghattas, Omar: Recursive algorithms for distributed forests of octrees (2015)
  3. Nejadmalayeri, Alireza; Vezolainen, Alexei; Brown-Dymkoski, Eric; Vasilyev, Oleg V.: Parallel adaptive wavelet collocation method for pdes (2015)
  4. Wang, Kun; Liu, Hui; Chen, Zhangxin: A scalable parallel black oil simulator on distributed memory parallel computers (2015)
  5. Brandfass, B.; Alrutz, T.; Gerhold, T.: Rank reordering for MPI communication optimization (2013)
  6. Espinha, Rodrigo; Park, Kyoungsoo; Paulino, Glaucio H.; Celes, Waldemar: Scalable parallel dynamic fracture simulation using an extrinsic cohesive zone model (2013)
  7. Kuhlemann, Verena; Vassilevski, Panayot S.: Improving the communication pattern in matrix-vector operations for large scale-free graphs by disaggregation (2013)
  8. Rajamanickam, Sivasankaran; Boman, Erik G.: Parallel partitioning with Zoltan: is hypergraph partitioning worth it? (2013)
  9. Camata, J.J.; Rossa, A.L.; Valli, Andrea M.P.; Catabriga, Lucia; Carey, Graham F.; Coutinho, Alvaro L.G.A.: Reordering and incomplete preconditioning in serial and parallel adaptive mesh refinement and coarsening flow solutions (2012)
  10. Selvitopi, R.Oguz; Turk, Ata; Aykanat, Cevdet: Replicated partitioning for undirected hypergraphs (2012)
  11. Burstedde, Carsten; Wilcox, Lucas C.; Ghattas, Omar: p4est: scalable algorithms for parallel adaptive mesh refinement on forests of octrees (2011)
  12. Lin, Lin; Yang, Chao; Lu, Jianfeng; Ying, Lexing; E, Weinan: A fast parallel algorithm for selected inversion of structured sparse matrices with application to 2D electronic structure calculations (2011)
  13. Bozdağ, Doruk; Çatalyürek, Ümit V.; Gebremedhin, Assefaw H.; Manne, Fredrik; Boman, Erik G.; Özgüner, Füsun: Distributed-memory parallel algorithms for distance-2 coloring and related problems in derivative computation (2010)
  14. Shadid, J.N.; Pawlowski, R.P.; Banks, J.W.; Chacón, L.; Lin, P.T.; Tuminaro, R.S.: Towards a scalable fully-implicit fully-coupled resistive MHD formulation with stabilized FE methods (2010)
  15. Zhou, Min; Sahni, Onkar; Devine, Karen D.; Shephard, Mark S.; Jansen, Kenneth E.: Controlling unstructured mesh partitions for massively parallel simulations (2010)
  16. Espinha, Rodrigo; Celes, Waldemar; Rodriguez, Noemi; Paulino, Glaucio H.: ParTopS: compact topological framework for parallel fragmentation simulations (2009)
  17. Aykanat, Cevdet; Cambazoglu, B.Barla; Uçar, Bora: Multi-level direct $K$-way hypergraph partitioning with multiple constraints and fixed vertices (2008)
  18. Bozdağ, Doruk; Gebremedhin, Assefaw H.; Manne, Fredrik; Boman, Erik G.; Catalyurek, Umit V.: A framework for scalable greedy coloring on distributed-memory parallel computers (2008)
  19. Pınar, Ali; Tabak, E.Kartal; Aykanat, Cevdet: One-dimensional partitioning for heterogeneous systems: theory and practice (2008)
  20. To, Albert C.; Liu, Wing Kam; Olson, Gregory B.; Belytschko, Ted; Chen, Wei; Shephard, Mark S.; Chung, Yip-Wah; Ghanem, Roger; Voorhees, Peter W.; Seidman, David N.; Wolverton, Chris; Chen, J.S.; Moran, Brian; Freeman, Arthur J.; Tian, Rong; Luo, Xiaojuan; Lautenschlager, Eric; Challoner, A.Dorian: Materials integrity in microsystems: a framework for a petascale predictive-science-based multiscale modeling and simulation system (2008)

1 2 next

Further publications can be found at: http://www.cs.sandia.gov/zoltan/Zoltan_pubs.html