.png){kind=icon}
.png){kind=icon}
Return
Fast optimal load balancing algorithms for 1D partitioning
.png){kind=icon}
OA
AI
DOI：10.1016/j.jpdc.2004.05.003.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The one-dimensional decomposition of nonuniform workload arrays with optimal load balancing is investigated. The problem has been studied in the literature as the chains-on-chains partitioning problem. Despite the rich literature on exact algorithms, heuristics. are still used in parallel computing community with the hope of good decompositions and the myth of exact algorithms being hard to implement and not runtime efficient. We show that exact algorithms yield significant improvements in load balance over heuristics with negligible overhead. Detailed pseudocodes of the proposed algorithms are provided for reproducibility. We start with a literature review and propose improvements and efficient implementation tips for these algorithms. We also introduce novel algorithms that are asymptotically and runtime efficient. Our experiments on sparse matrix and direct volume rendering datasets verify that balance can be significantly improved by using exact algorithms. The proposed exact algorithms are 100 times faster than a single sparse-matrix vector multiplication for 64-way decompositions on the average. We conclude that exact algorithms with proposed efficient implementations can effectively replace heuristics. (C) 2004 Elsevier Inc. All rights reserved.
Keywords:
one-dimensional partitioning-
optimal load balancing
chains-on-chains partitioning
dynamic programming
iterative refinement
parametric search
parallel sparse matrix vector multiplication
image-space parallel volume rendering
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K
Organization
No organization information available