A formal analysis of space filling curves for parallel domain decomposition

Space filling curves (SFCs) are widely used for parallel domain decomposition in scientific computing applications. The proximity preserving properties of SFCs are expected to keep most accesses local in applications that require effi-cient access to spatial neighborhoods. While experimental results are used to confirm this behavior, a rigorous math-ematical analysis of SFCs turns out to be rather hard and rarely attempted. In this paper, we analyze SFC based par-allel domain decomposition for a uniform random spatial distribution in three dimensions. Let n denote the expected number of points and P denote the number of processors. We show that the expected distance along an SFC to a near-est neighbor is O(n2/3). We then consider the problem of answering nearest neighbor and spherical region queries for each point. For P = nα (0 < α ≤ 1) processors, we show that the total number of remote accesses grows as O(n3/4+α/4). This analysis shows that the expected num-ber of total remote accesses is sublinear for any sublinear number of processors. We view the analysis presented here as a step towards the goal of understanding the utility of SFCs in scientific applications and the analysis of more complex spatial distributions. Key words: domain decomposition, parallel algorithms, probabilistic analysis, space filling curves