Bin-Hash Indexing: A Parallel Method For Fast Query Processing
This work presents a new indexing data structure for query processing, called the Bin-Hash index that effectively utilizes the parallel processing power of the Graphics Processing Unit (GPU). Our approach concentrates on reducing both the amount of bandwidth and memory required to evaluate a query. We achieve this goal by integrating two key strategies: we use encoded data tables to help overcome the limitations imposed by limited GPU memory, and a technique known as perfect spatial hashing to accelerate the retrieval of raw data necessary for candidate checks. We support our candidate checks with a flexible dual cache (one for the GPU and one for the CPU) that uses independent replacement polices. To this end, the CPU serves as a host to the GPU, only supplying the raw data needed for candidate checks; all query evaluations are performed on the GPU by executing kernels written in NVIDIA’s data-parallel programming language CUDA. In our timing measurements, our new query processing method can be an order of magnitude faster than current state-of-the-art indexing technologies such as the compressed bitmap index.
The contributions of this work greatly extend the utility of Query-Driven Visualization strategies; our GPU-based query-processing strategy accelerates both query answering and rendering tasks, and also implements a compression scheme to efficiently utilize available GPU-memory resources. Authors: Luke J. Gosink, Kesheng Wu, E. Wes Bethel, John D. Owens, Kenneth I. Joy
Query-Driven Visualization of Time-Varying Adaptive Mesh Refinement Data
We present a new approach that enables query-driven analysis and multitemporal visualization of time-varying AMR data. Previously, such analysis and visualization efforts were hindered by the dynamic temporal and spatial properties of AMR grid hierarchies. We present a two-step method for compositing and synchronizing AMR data from a series of time steps. We first generate a composite template from the AMR grid hierarchies of these time steps; the composite template preserves the finest level of grid cell refinement from each grid hierarchy. We then synchronize each time steps grid hierarchy to the composite template. This approach enables our method to process queries on a common AMR grid hierarchy. Using this data structure, we move the work of query processing to the GPU to realize the benefit of greatly accelerated QDV analysis. On the GPU side, we integrate our new method with a GPU-based query engine, called the Bin-Hash index.
Our method facilitates query-driven analysis of time-varying AMR data, and generates two types of time-dependent visualization: temporally sequential and temporally concurrent. In temporally sequential visualizations, features from each time step are analyzed and visualized individually in sequential frames as an animation. Comparatively, in temporally concurrent visualizations, a single multitemporal image conveys how queries characterizing important features evolve over time. In temporally sequential visualizations, our GPU-based QDV engine enables accelerated analysis; users can process queries over multiple time steps and view the results in real-time as an animation. Authors: Luke J. Gosink, John C. Anderson, E. Wes Bethel, and Kenneth I. Joy