Portal de Periódicos da CAPES

Voxel databases: A paradigm for parallelism with spatial structure

1992; Wiley; Volume: 4; Issue: 8 Linguagem: Inglês

10.1002/cpe.4330040804

1096-9128

Roy Williams,

Computer Graphics and Visualization Techniques

Abstract This paper concerns parallel, local computations with a data structure such as 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 an example we discuss the implementation of an unstructured finite‐element elliptic solver using a conjugate gradient method. We also discuss the implementations of a finite‐volume flux‐split fluid solver and of local adaptive refinement for meshes of simplices such as triangles or tetrahedra.