Towards Efficient Graph Traversal using a Multi-GPU Cluster

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

Performance Comparison of DCT and Walsh Transforms for Watermarking using DWT-SVD

This paper presents a DWT-DCT-SVD based hybrid watermarking method for color images. Robustness is achieved by applying DCT to specific wavelet sub-bands and then factorizing each quadrant of frequency sub-band using sin...

Enhancing Elasticity of SaaS Applications using Queuing Theory

Elasticity is one of key features of cloud computing. Elasticity allows Software as a Service (SaaS) applications’ provider to reduce cost of running applications. In large SaaS applications that are developed using serv...

SME Cloud Adoption in Botswana: Its Challenges and Successes

The standard office or business in Botswana hosts their resources in-house. This means that a company will have their hardware, software and support staff as part of their daily work operations. Technology has brought a...

  Improved Face Recognition with Multilevel BTC using Kekre’s LUV Color Space

 The theme of the work presented in the paper is Multilevel Block Truncation Coding based Face Recognition using the Kekre’s LUV (K’LUV) color space. In [1], Multilevel Block Truncation Coding was applied on the RGB...

LeafPopDown: Leaf Popular Down Caching Strategy for Information-Centric Networking

Information-Centric Networking is a name based internet architecture and is considered as an alternate of IP base internet architecture. The in-network caching feature used in ICN has attracted research interests as it r...

Download PDF file
  • EP ID EP259649
  • DOI 10.14569/IJACSA.2017.080644
  • Views 103
  • Downloads 0

How To Cite

Hina Hameed, Nouman M Durrani, Sehrish Hina, Jawwad A. Shamsi (2017). Towards Efficient Graph Traversal using a Multi-GPU Cluster. International Journal of Advanced Computer Science & Applications, 8(6), 338-346. https://europub.co.uk/articles/-A-259649