high performance computing on graphics processing units: hgpu.org

General purpose computing on graphics processor units (GPGPU) has attained widespread acceptance in the high-performance computing community. This has largely been at- tributed to the rise of programming models and large peak performance to cost ratio of the GPU. The peak throughput of modern GPUs are typically 5 TFLOPS at a cost of 600 US $. These upper limits are found only for applications that have a regular and low frequency memory access. Many algorithms which have a computational model orthogo- nal to the GPU model, especially in the domain of graph theory, have been traditionally not known to be well suited for the GPU model. Graph theoretical algorithms are considered as one of the fundamental building blocks for Computer Science in general. They are considered impractical on many of the current high performance platforms because of the large dependence on irregular data movement, which in the GPU context is a major performance bottleneck. In this context, we focus on fundamental primitives with applications for graph theory, with a large number of immediate applications Typical primitives related to graph theory, can be divided into: Graph primitives: Graph primitives include traversal, connectivity algorithms, path based algorithms etc.. In this thesis, we have dealt with connectivity algorithms such as connected components, spanning tree and spanning forest; Generic Primitives: Graph theory applications rely not just on domain specific primitives, but primitives from other domains play a significant role especially in large graph operations on parallel machines. One such primitive is the Range Query Primitive (esp Minima and Maxima). We present a GPU specific implementation of range queries and use it to answer queries such as LCA, minimum/maximum element in a subtree etc.. All the primitives rely on an array based representation, and focus on reducing the dependence on the hierarchical structure of the graph. Problems such as minimum key in a subtree are converted into equivalent problems (Range Query) that have a solution more suited to the GPU model. Also, solutions presented here try to reduce data movement by exploiting data level as well as functional data movement redundancies. Thus the focus is on handling data movement judiciously. We show that the results we have obtained on data sizes fitting the GPU are faster than results on any hardware currently present in literature.