Voxel Databases: A Paradigm for Parallelism with Spatial Structure

This paper concerns parallel, local computations with a data structure such a graph or mesh, which may be structured or unstructured. The target machine is a distributed-memory parallel processor with vector or pipeline hardware on the processors, but software based on voxel databases also runs efficiently on shared-memory and uniprocessor machines with and without vector hardware. A voxel database (VDB) is a distributed shared memory, where entities which share memory are those at the same geometric position. A VDB may be thought of as a dictionary of position-subscript pairs, so that data may be associated with points in space by using the subscript of that point as an index into data arrays. The use of subscripts allows ease of programming and vectorization. The shared memory at each point is weakly coherent and may be either single-writer, multiple reader, also known as the ghost node method; or multiple-combiner, multiple-reader memory. The VDB may be sorted to put special points at the beginning or end of the subscript list, and also to reduce cache-miss inefficiencies. Support is also provided for arbitrary distribution of data entities between processors for load-balancing. The idea of VDBs and the corresponding software tool provide a clear and efficient way to program a large variety of mesh computations in Fortran or C, such that the execution of the program is independent of the distribution of data to processors, and the mesh may be topologically adapted and load balanced. As a