Index-Based Search Techniques for Visualization and Data Analysis Algorithms on Many-Core Systems

Date and time: 
Friday, February 22, 2019 - 10:00
220 Deschutes
Brenton Lessley
University of Oregon
  • Hank Childs (chair)
  • Boyana Norris
  • Chris Wilson
  • Eric Torrence (Physics)

Sorting and hashing are canonical index-based methods to perform searching, and are prevalent sub-routines in many scientific visualization and data analysis algorithms. With the emergence of highly-parallel, many-core architectures, these algorithms must be reformulated to exploit the increased available data-parallelism and instruction-level parallelism. Data-parallel primitives (DPP) provide an efficient way to design an algorithm for scalable, platform-portable parallelism. This dissertation proposes the design of platform-portable, index-based search techniques using DPP. In particular, we introduce new sort- and hashing-based techniques for the search of duplicate elements, and then design a new data-parallel hash table data structure that builds upon these techniques. We then apply these methods to the data-parallel reformulation of select data-intensive visualization and data analysis algorithms, all of which are non-trivial to implement with DPP. Finally, we synthesize the dissertation findings into a collection of best practices and recommended usage for achieving suitable platform-portable performance with our search techniques. This dissertation is a culmination of previously-published co-authored material.