high performance computing on graphics processing units: hgpu.org

Over the past years, the rise of General Purpose GPU (GPGPU) paradigm has become more evident in high-performance computing. The massive parallelism that GPUs offer at low cost is the catalyst for its adoption in numerous computational intensive applications, where tremendous speedup gains are reported due to the ease of parallelization of the algorithms they encapsulate. This thesis studied more advanced data management problems such as inequality and set similarity joins, along with the set intersection and containment operators on the GPGPU paradigm. Due to the inherent quadratic complexity of these problems, direct performance gains are unachievable. However, as shown in this thesis by designing co-processing techniques that take advantage of the different and complementary characteristics offered by CPUs and GPUs, tangible speedup gains are achieved over standalone implementations and other multi-threaded CPU solutions. More specifically, for the inequality or theta joins, efficient implementations on a GPU are provided along with several optimizations to further improve performance. The best performing technique adopts a sliding window approach, and by resource reuse and through memory hierarchy exploitation, manages to achieve speedups of an order of magnitude for the aggregation query and of 2.7X for the select query over other CPU alternatives. For the set similarity join, a co-processing CPU-GPU technique is proposed with the goal to utilize both processors. As a result, due to the execution overlap between the CPU and GPU tasks, significant speedups, which can reach up to 2.6X, are achieved over other alternatives in several cases. Furthermore, an empirical evaluation of the state-of-the-art GPU-enabled set similarity techniques is also presented, along with several key insights into under which circumstances each technique performs better. The main outcome is that there is no dominant solution; each technique has its own pros and cons based on specific dataset characteristics. Based on these findings, a hybrid framework for the set similarity join problem his proposed, which encapsulates the state-of-the-art CPU and GPU set similarity join techniques. By introducing two workload allocation strategies, the hybrid framework manages to utilize both the CPU and the GPU with high efficiency and achieves speedups of up to 3.25X over standalone techniques and of an order of magnitude over other parallel CPU solutions. Finally, by adapting techniques initially proposed for graph analytics and matrix multiplication on the GPU, several hybrid GPU techniques for the set intersection operator on large sets are proposed. In addition, the first known technique for the set containment operator in the GPGPU paradigm, which involves a co-processing scheme between the CPU and the GPU, is introduced. In a thorough experimental evaluation, the proposed techniques for both operators manage to achieve performance speedup of an order of magnitude over the respective multi-threaded CPU alternatives.