.png){kind=icon}
.png){kind=icon}
Return
Load-balancing spatially located computations using rectangular partitions
.png){kind=icon}
OA
AI
DOI：10.1016/j.jpdc.2012.05.013.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Distributing spatially located heterogeneous workloads is an important problem in parallel scientific computing. We investigate the problem of partitioning such workloads (represented as a matrix of non-negative integers) into rectangles, such that the load of the most loaded rectangle (processor) is minimized. Since finding the optimal arbitrary rectangle-based partition is an NP-hard problem, we investigate particular classes of solutions: rectilinear, jagged and hierarchical. We present a new class of solutions called m-way jagged partitions, propose new optimal algorithms for m-way jagged partitions and hierarchical partitions, propose new heuristic algorithms, and provide worst case performance analyses for some existing and new heuristics. Moreover, the algorithms are tested in simulation on a wide set of instances. Results show that two of the algorithms we introduce lead to a much better load balance than the state-of-the-art algorithms. We also show how to design a two-phase algorithm that reaches different time/quality tradeoffs. (C) 2012 Elsevier Inc. All rights reserved.
Keywords:
Load balancing
Spatial partitioning
Optimal algorithms
Heuristics
Dynamic programming
Particle-in-cell
Mesh-based computation
Jagged partitioning
Rectilinear partitioning
Hierarchical partitioning
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