PARALLEL COMPACT HASH ALGORITHMS FOR COMPUTATIONAL MESHES

We employ compact hashing and the discrete properties of computational meshes to optimize spatial operations in scientific computing applications. Our target is to develop highly parallel compact hashing methods suitable for the fine-grained parallelism of GPU and MIC architectures that will scale to the next generation of computing systems. As a model, we apply spatial hashing methods to the problem of determining neighbor elements in adaptive mesh refinement (AMR) schemes. By applying memory savings techniques, we extend the perfect spatial hash algorithm to a compact hash by compressing the resulting sparse data structures. Using compact hashing and specific memory optimizations, we increase the range of problems that can benefit from our ideal $O(n)$ algorithms. The spatial hash methods are tested and compared across a variety of architectures on both a randomly generated sample mesh and an existing cell-based AMR shallow-water hydrodynamics scheme. We demonstrate consistent speed-up and increased per...