|
Abstract : |
Balanced partitioning of non-uniform data in a high dimensional space is much more difficult than partitioning the non-uniform data projected onto a line. For dynamic problems which require many such partitions, this partitioning time difference may be critical. For this reason, Recursive Coordinate Bisection (RCB) has grown in popularity since it repeatedly collapses d \Gamma 1 dimensions onto 1 dimension. As an alternative method, we introduce the Inverse Spacefilling Partition (ISP) which maps the higher dimensional space to a line in more fine-grained units. ISP is faster than RCB, and yields a more even load balance at the cost of slightly higher communication and irregularly partitioned regions. The general d-dimensional ISP algorithm is described, then analytical and empirical comparisons are made between ISP and RCB. 1, |
