  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.
