Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2011-04-13
Computer Science
Distributed, Parallel, and Cluster Computing
Scientific paper
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 tradeoff.
Baş Erdeniz Ö.
Çatalyürek Ümit V.
Saule Erik
No associations
LandOfFree
Load-Balancing Spatially Located Computations using Rectangular Partitions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Load-Balancing Spatially Located Computations using Rectangular Partitions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Load-Balancing Spatially Located Computations using Rectangular Partitions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-219786