An Algorithm Producing Balanced Partitionings of Data Arrays
Lawrence Snyder, David Socha · 2005
We present a new polynomial time algorithm for allocating array elements to the processor memories of parallel computers. The algorithm produces, for sufficiently large arrays, partitionings that are balanced, near-rectangular and near-bulky. Balanced means each allocation is assigned the minimal number of elements. Near-rectangular means that each allocation is at most two off from the optimal aspect ratio in each dimension and has at most two jogs along each edge. A jog is where the boundary deviates from a straight line. Near-bulky means that each allocation has a near maximal ratio of interior/exterior points. For an I x J array of points and a K x K array of processors the algorithm produces balanced nearbulky partitionings when I, J 2 4K and produces balanced, near-bulky and near-rectangular allocations when I, J 2 8K. These bounds are not tight. A variant of the algorithm produces allocations with at most six neighbors per allocation for arbitrary stencils. Using these near-rectangular allocations incurs little additional cost for compilers for distributed memory parallel computers, and the extra run-time cost usually is offset by the advantage of balanced allocations.