Search

We explore the potential uses of hash-based algorithms in the remap operation, mapping one computational mesh onto another. We implement and test optimizations designed to reduce memory operations ...

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...

We explore the idea that all mesh operations in numerical methods can be implemented with efficient hash-based algorithms. The hash-based methods are presented with a view toward highly parallel implementations on both the CPU and GPU. A general set of applications, including sorting, neighbor calculation, remapping, and table look-up, demonstrate the practical value and several orders of magnitude speed-up of hash-based implementations.