A challenging aspect of performing scientific visualization in a parallel environment with many threads is finding common topology elements generated concurrently by parallel threads. When parallel threads work on coarse regions of topology (such as in an MPI environment) it is feasible (and common) to simply allow coincident topology to be duplicated. When working with a processor that requires many threads (such as a GPU), there is too much overlap to make duplication feasible. In our reasearch we developed techniques that built unique keys to simplify the identification of common elements.
"Finely-Threaded History-Based Topology Computation." Robert Miller, Kenneth Moreland, and Kwan-Liu Ma. In Eurographics Symposium on Parallel Graphics and Visualization (EGPGV), June 2014. pp. 41–48. DOI 10.2312/pgv.20141083.
In our initial research we explored the idea of defining a unique integer-based identifier for each topological element. The key insight is that new topologies are typically based on an input topology in visualization, and we can use the indices of the source topology to formulate unique keys.
Graphics and visualization pipelines often make use of highly parallelized algorithms which transform an input mesh into an output mesh. One example is Marching Cubes, which transforms a voxel grid into a triangle mesh approximation of an isosurface. These techniques often discard the topological connectivity of the output mesh, and instead produce a ‘soup’ of disconnected geometric elements. Calculations that require local neighborhood, such as surface curvature, cannot be performed on such outputs without first reconstructing its topology. We present a novel method for reconstructing topological information across several kinds of mesh transformations, which we demonstrate with GPU and OpenMP implementations. Our approach makes use of input topological elements for efficient location of coincident elements in the output. We provide performance data for the technique for isosurface generation, tetrahedralization, subdivision, and dual mesh generation, and demonstrate its use in visualization pipelines containing further computations of local curvature and mesh coarsening.
"Techniques for Data-Parallel Searching for Duplicate Elements." Brenton Lessley, Kenneth Moreland, Matthew Larsen, and Hank Childs. In IEEE Symposium on Large Data Analysis and Visualization (LDAV), October 2017. DOI 10.1109/LDAV.2017.8231845.
In this work, we explored the use of imperfect hashes as keys to identify common topological elements. Although this results in key collisions, the correction for collisions takes less time than the benefit of faster hash grouping. We also explore a "hash-fight" algorithm for external faces that uses a different technique for finding duplicate hashes.
We study effective shared-memory, data-parallel techniques for searching for duplicate elements. We consider several data-parallel approaches, and how hash function, machine architecture, and data set can affect performance. We conclude that most choices of algorithm and hash function are problematic for general usage. However, we demonstrate that the choice of the Hash-Fight algorithm with the FNV1a hash function has consistently good performance over all configurations.
Use the following link to download the benchmarking program that we used to take the measurements provided by the paper.
We also post here the raw files generated by our benchmarking runs. In the table below, the left links are to the raw log file (either in YAML or CSV format). The associated link to the right is a Jupyter/IPython file we used to process the log files and generate the figures seen in the paper.
|Log File||Jupyter Python Script|