Hypergraph partitioning for multiple communication cost metrics: model and methods

Warning The system is temporarily closed to updates for reporting purpose.

Deveci, Mehmet and Kaya, Kamer and Uçar, Bora and Çatalyürek, Ümit V. (2015) Hypergraph partitioning for multiple communication cost metrics: model and methods. Journal of Parallel and Distributed Computing, 77 . pp. 69-83. ISSN 0743-7315 (Print) 1096-0848 (Onilne)

[img]PDF (This is a RoMEO green journal -- author can archive pre-print (ie pre-refereeing)) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dx.doi.org/10.1016/j.jpdc.2014.12.002


We investigate hypergraph partitioning-based methods for efficient parallelization of communicating tasks. A good partitioning method should divide the load among the processors as evenly as possible and minimize the inter-processor communication overhead. The total communication volume is the most popular communication overhead metric which is reduced by the existing state-of-the-art hypergraph partitioners. However, other metrics such as the total number of messages, the maximum amount of data transferred by a processor, or a combination of them are equally, if not more, important. Existing hypergraph-based solutions use a two phase approach to minimize such metrics where in each phase, they minimize a different metric, sometimes at the expense of others. We propose a one-phase approach where all the communication cost metrics can be effectively minimized in a multi-objective setting and reductions can be achieved for all metrics together. For an accurate modeling of the maximum volume and the number of messages sent and received by a processor, we propose the use of directed hypergraphs. The directions on hyperedges necessitate revisiting the standard partitioning heuristics. We do so and propose a multi-objective, multi-level hypergraph partitioner called UMPa. The partitioner takes various prioritized communication metrics into account, and optimizes all of them together in the same phase. Compared to the state-of-the-art methods which only minimize the total communication volume, we show on a large number of problem instances that UMPa produces better partitions in terms of several communication metrics.

Item Type:Article
Uncontrolled Keywords:Hypergraph; Graph; Partitioning; Load balancing
Subjects:Q Science > QA Mathematics > QA075 Electronic computers. Computer science
ID Code:27693
Deposited By:Kamer Kaya
Deposited On:09 Dec 2015 15:57
Last Modified:23 Aug 2019 12:09

Repository Staff Only: item control page