id: 06097749
dt: j
an: 06097749
au: Saule, Erik; Baş, Erdeniz Ö.; Çatalyürek, Ümit V.
ti: Load-balancing spatially located computations using rectangular partitions.
so: J. Parallel Distrib. Comput. 72, No. 10, 1201-1214 (2012).
py: 2012
pu: Elsevier Science (Academic Press), San Diego, CA
la: EN
cc: 
ut: load balancing; spatial partitioning; optimal algorithms; heuristics;
    dynamic programming; particle-in-cell; mesh-based computation; jagged
    partitioning; rectilinear partitioning; hierarchical partitioning
ci: 
li: doi:10.1016/j.jpdc.2012.05.013
ab: Summary: 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.
rv: