Efficient Parallel Algorithm for BFS on Large Graphs

Gollepally, Yamini and Peri, Sathya (2017) Efficient Parallel Algorithm for BFS on Large Graphs. Masters thesis, Indian Institute of Technology Hyderabad.

Text
CS15MTECH11003.pdf - Submitted Version
Restricted to Registered users only until 2 July 2020.
Download (1MB) | Request a copy

Abstract

Breadth First Search Traversal algorithm is an important kernel for many real - time scientific and engineering applications. However, the scalability is limited in parallel shared sy stems due to memory latencies and synchronization problems. To alleviate these demerits it is proposed to develop an efficient implementation of parallelized BFS approach BFS, on shared memory systems by improving synchronization aiming fine grained parall elism using optimistic concurrency control mechanisms and devise a mechanism to prove the correctness of a parallel algorithm which is a challenging task. In this project, we present a multithreaded parallel breadth first traversal algorithm on shared memo ry architecture by applying two techniques Hand - over - Hand(HoH) locking method , which achieves coarse grained parallelism and List - of - List(LoL) optimistic algorithm which achieves fine - grained parallelism. Using real - world graph datasets, we compared and evaluate the performance of both the algorithms on Intel architecture with 8 cores. Obtained results shown that the speed of both the proposed methods in terms of time taken to traverse all the nodes of a graph is less compared to sequential breadth firs t search algorithm, also List - of - List(LoL) optimistic algorithm results better when compared to Hand - over - Hand locking(HoH) method

[error in script]

IITH Creators: