Hybrid Multicore Algorithms for Some Semi Numerical Applications and Graphs

Abstract

In this thesis we work towards the development of hybrid multicore computing. Hybrid multicore computing is developing algorithms and optimization strategies for popular computing primitives on an hybrid platform. A hybrid platform is one which contains two or more multicore or many-core devices. There are several challenges towards the efficient algorithm design on hybrid platforms such as that of communication bottlenecks, load balance and synchronization. In this thesis we work towards developing algorithms for some computing primitives such as that of list ranking, sorting and pseudo-randomness and some graph algorithms. We experiment on a hybrid platform consisting of a 6-core Intel CPU and Nvidia GPUs of broadly two generations. In our first work we work towards the development of hybrid algorithms for List Ranking. The main contribution of this work is to address the issues related to the design of hybrid solutions. We show our hybrid algorithm for list ranking is faster by 50% compared to the best known implementation [Wei et. al.IPDPS 2010]. newline newlineThe ability to use randomness in computation is known to help in several situations. For such computations to be made possible on a general purpose computer, a source of randomness, or in general a pseudo random generator (PRNG), is essential. However, most of the PRNGs currently available on GPUs suffer from some basic drawbacks. Our approach produces 0.07 GNumbers per second. newline newlineThe quality of our generator is tested with industry standard tests. In the second part of the thesis, we work towards hybrid graph connected components and breadth first search. We achieve almost 25% improvement over the best known implementation in. For performing breadth first search (BFS), we employ a graph pruning strategy to reduce the size of large graphs which is often composed of a large percentage of pendant nodes. We apply a hybrid BFS on the remainder graph and is followed by a re-insertion phase. We achieve a 35% improvement over the current best know solution.