Towards Efficient Graph Traversal using a Multi-GPU Cluster
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2017, Vol 8, Issue 6
Abstract
Graph processing has always been a challenge, as there are inherent complexities in it. These include scalability to larger data sets and clusters, dependencies between vertices in the graph, irregular memory accesses during processing and traversals, minimal locality of reference, etc. In literature, there are several implementations for parallel graph processing on single GPU systems but only few for single and multi-node multi-GPU systems. In this paper, the prospects of improvement in large graph traversals by utilizing multi-GPU cluster for Breadth First Search algorithm has been studied. In this regard, a DiGPU, a CUDA-based implementation for graph traversal in shared memory multi-GPU and distributed memory multi-GPU systems has been proposed. In this work, an open source software module has also been developed and verified through set of experiments. Further, evaluations have been demonstrated on local cluster as well as on CDER cluster. Finally, experimental analysis has been performed on several graph data sets using different system configurations to study the impact of load distribution with respect to GPU specification on performance of our implementation.
Authors and Affiliations
Hina Hameed, Nouman M Durrani, Sehrish Hina, Jawwad A. Shamsi
Keywords
Related Articles
- EP ID EP259649
- DOI 10.14569/IJACSA.2017.080644
- Views 89
- Downloads 0
Mining Opinion in Online Messages
The number of messages that can be mined from online entries increases as the number of online application users increases. In Malaysia, online messages are written in mixed languages known as ‘Bahasa Rojak’. Therefore,...
Detection and Identification System of Bacteria and Bacterial Endotoxin Based on Raman Spectroscopy
Sepsis is a global health problem that causes risk of death. In the developing world, about 60 to 80 % of death cases are caused by Sepsis. Rapid methods for detecting its causes, represent one of the major factors that...
Eye Detection Based-on Color and Shape Features
This paper presents an eye detection technique based-on color and shape features. The approach consists of three steps: a rough eye localization using projection technique, a white color thresholding to extract whi...
Efficient Algorithm for Maximal Clique Size Evaluation
A large dataset network is considered for computation of maximal clique size (MC). Additionally, its link with popular centrality metrics to decrease uncertainty and complexity and for finding influential points of any n...
Position-based Selective Neighbors
In this paper, we propose a routing protocol, named Position-based Selective Neighbors (PSN), for controlling the Route Request (RREQ) propagation in Mobile Ad-hoc Networks (MANETs). PSN relies on the Residual Energy (RE...