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

Abstract

Sorting and hashing are canonical index-based methods to perform searching, and are often sub-routines in many visualization and analysis algorithms. With the emergence of many-core architectures, these algorithms must be rethought to exploit the increased available thread-level parallelism and data-parallelism. Data-parallel primitives (DPP) provide an efficient way to design an algorithm for scalable, platform-portable parallelism. This dissertation considers the following question: What are the best index-based search techniques for visualization and analysis algorithms on diverse many-core systems? To answer this question, we develop new DPP-based techniques, and evaluate their performance against existing techniques for data-intensive visualization and analysis algorithms across different many-core platforms. Then, we synthesize our findings into a collection of best practices and recommended usage. As a result of these efforts, we were able to conclude that our techniques demonstrate viability and leading platform-portable performance for several different search-based use cases. This dissertation is a culmination of previously-published co-authored material.