More Like this

1. GPU LSM: A Dynamic Dictionary Data Structure for the GPU

   https://doi.org/10.1109/IPDPS.2018.00053  

   Ashkiani, Saman; Li, Shengren; Farach-Colton, Martin; Amenta, Nina; Owens, John D. (May 2018, Proceedings of the 31st IEEE International Parallel and Distributed Processing Symposium)

   We develop a dynamic dictionary data structure for the GPU, supporting fast insertions and deletions, based on the Log Structured Merge tree (LSM). Our implementation on an NVIDIA K40c GPU has an average update (insertion or deletion) rate of 225 M elements/s, 13.5x faster than merging items into a sorted array. The GPU LSM supports the retrieval operations of lookup, count, and range query operations with an average rate of 75 M, 32 M and 23 M queries/s respectively. The trade-off for the dynamic updates is that the sorted array is almost twice as fast on retrievals. We believe that our GPU LSM is the first dynamic general-purpose dictionary data structure for the GPU. 

   more » « less
2. GPU LSM: A Dynamic Dictionary Data Structure for the GPU

   Ashkiani, S.; Li, S.; Farach-Colton, M; Amenta, N.; Owens, J (January 2018, IPDPS .... [proceedings])

   We develop a dynamic dictionary data structure for the GPU, supporting fast insertions and deletions, based on the Log Structured Merge tree (LSM). Our implementation on an NVIDIA K40c GPU has an average update (insertion or deletion) rate of 225 M elements/s, 13.5x faster than merging items into a sorted array. The GPU LSM supports the retrieval operations of lookup, count, and range query operations with an average rate of 75 M, 32 M and 23 M queries/s respectively. The trade-off for the dynamic updates is that the sorted array is almost twice as fast on retrievals. We believe that our GPU LSM is the first dynamic general-purpose dictionary data structure for the GPU. 

   more » « less
3. RXMesh: a GPU mesh data structure

   https://doi.org/10.1145/3450626.3459748  

   Mahmoud, Ahmed_H; Porumbescu, Serban_D; Owens, John_D (July 2021, ACM Transactions on Graphics)

   We propose a new static high-performance mesh data structure for triangle surface meshes on the GPU. Our data structure is carefully designed for parallel execution while capturing mesh locality and confining data access, as much as possible, within the GPU's fast shared memory. We achieve this by subdividing the mesh intopatchesand representing these patches compactly using a matrix-based representation. Our patching technique is decorated withribbons, thin mesh strips around patches that eliminate the need to communicate between different computation thread blocks, resulting in consistent high throughput. We call our data structureRXMesh: Ribbon-matriX Mesh. We hide the complexity of our data structure behind a flexible but powerful programming model that helps deliver high performance by inducing load balance even in highly irregular input meshes. We show the efficacy of our programming model on common geometry processing applications---mesh smoothing and filtering, geodesic distance, and vertex normal computation. For evaluation, we benchmark our data structure against well-optimized GPU and (single and multi-core) CPU data structures and show significant speedups. 

   more » « less
4. Swizzle Inventor: Data Movement Synthesis for GPU Kernels

   https://doi.org/10.1145/3297858.3304059  

   Phothilimthana, Phitchaya Mangpo; Bodik, Rastislav; Elliott, Archibald Samuel; Wang, An; Jangda, Abhinav; Hagedorn, Bastian; Barthels, Henrik; Kaufman, Samuel J.; Grover, Vinod; Torlak, Emina (April 2019, ASPLOS)

   Utilizing memory and register bandwidth in modern architectures may require swizzles — non-trivial mappings of data and computations onto hardware resources — such as shuffles. We develop Swizzle Inventor to help programmers implement swizzle programs, by writing program sketches that omit swizzles and delegating their creation to an automatic synthesizer. Our synthesis algorithm scales to real-world programs, allowing us to invent new GPU kernels for stencil computations, matrix transposition, and a finite field multiplication algorithm (used in cryptographic applications). The synthesized 2D convolution and finite field multiplication kernels are on average 1.5–3.2x and 1.1–1.7x faster, respectively, than expert-optimized CUDA kernels. 

   more » « less
5. GPU-DFC: A GPU-Based Parallel Algorithm for Computing Dynamic-Functional Connectivity of Big fMRI Data

   https://doi.org/10.1109/BigDataService.2019.00022  

   Eslami, Taban; Saeed, Fahad (April 2019, Proceedings of IEEE Fifth International Conference on Big Data Computing Service and Applications (BigDataService))

   Studying dynamic-functional connectivity (DFC) using fMRI data of the brain gives much richer information to neuroscientists than studying the brain as a static entity. Mining of dynamic connectivity graphs from these brain studies can be used to classify diseased versus healthy brains. However, constructing and mining dynamic-functional connectivity graphs of the brain can be time consuming due to size of fMRI data. In this paper, we propose a highly scalable GPU-based parallel algorithm called GPU-DFC for computing dynamic-functional connectivity of fMRI data both at region and voxel level. Our algorithm exploits sparsification of correlation matrix and stores them in CSR format. Further reduction in the correlation matrix is achieved by parallel decomposition techniques. Our GPU-DFC algorithm achieves 2 times speed-up for computing dynamic correlations compared to state-of-the-art GPU-based techniques and more than 40 times compared to a sequential CPU version. In terms of storage, our proposed matrix decomposition technique reduces the size of correlation matrices more than 100 times. Reconstructed values from decomposed matrices show comparable results as compared to the correlations with original data. The implemented code is available as GPL license on GitHub portal of our lab (https://github.com/pcdslab/GPU-DFC). 

   more » « less