On partitioning problems with complex objectives

Abstract : Hypergraph and graph partitioning tools are used to partition work for efficient parallelization of many sparse matrix computations. Most of the time, the objective function that is reduced by these tools relates to reducing the communication requirements, and the balancing constraints satisfied by these tools relate to balancing the work or memory requirements. Sometimes, the objective sought for having balance is a complex function of the partition. We describe some important class of parallel sparse matrix computations that have such balance objectives. For these cases, the current state of the art partitioning tools fall short of being adequate. To the best of our knowledge, there is only a single algorithmic framework in the literature to address such balance objectives. We propose another algorithmic framework to tackle complex objectives and experimentally investigate the proposed framework.
Complete list of metadatas

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/inria-00567129
Contributor : Bora Uçar <>
Submitted on : Friday, February 18, 2011 - 1:13:29 PM
Last modification on : Thursday, June 27, 2019 - 4:27:48 PM
Long-term archiving on : Tuesday, November 6, 2012 - 2:16:19 PM

File

RR-7546.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00567129, version 1

Citation

Kamer Kaya, François-Henry Rouet, Bora Uçar. On partitioning problems with complex objectives. [Research Report] RR-7546, INRIA. 2011. ⟨inria-00567129⟩

Share

Metrics

Record views

387

Files downloads

273