Parallel domain decomposition and load balancing usingspace-filling curves

摘要

Partitioning techniques based on space filling curves havereceived much recent attention due to their low running time and goodload balance characteristics. The basic idea underlying these methods isto order the multidimensional data according to a space filling curveand partition the resulting one dimensional order. However, spacefilling curves are defined for points that lie on a uniform grid of aparticular resolution. It is typically assumed that the coordinates ofthe points are representable using a fixed number of bits, and the runtimes of the algorithms depend upon the number of bits used. We presenta simple and efficient technique for ordering arbitrary and dynamicmultidimensional data using space filling curves and its application toparallel domain decomposition and load balancing. Our technique is basedon a comparison routine that determines the relative position of twopoints in the order induced by a space filling curve. The comparisonroutine could then be used in conjunction with any parallel sortingalgorithm to effect parallel domain decomposition