Engineering a Parallel ∆-stepping Algorithm

Files in This Item:
File Description SizeFormat 
insight_publication.pdf705 kBAdobe PDFDownload
Title: Engineering a Parallel ∆-stepping Algorithm
Authors: Duriakova, ErikaAjwani, DeepakHurley, Neil J.
Permanent link:
Date: 12-Dec-2019
Online since: 2021-05-26T10:19:11Z
Abstract: Computation of the single-source shortest path (SSSP) is a fundamental primitive in many network analytics tasks. With the increasing size of networks to beanalysed, there is a need for effcient tools to compute shortest paths, especiallyon the widely adopted shared-memory multicore architectures. The ∆-steppingalgorithm, that trades-off the work effciency of Dijkstra’s algorithm with theparallelism offered by the Bellman-Ford algorithm, has been found to be among thefastest implementations on various parallel architectures. Despite its widespread popularity, the different design choices in implementing the parallel∆-steppingalgorithm are not properly understood and these design choices can have a significant impact on the final performance. In this paper, we carefully comparetwo different implementations of the∆-stepping algorithm for shared-memorymulticore architectures: (i) a static workload assignment where the nodes areassigned to threads at the beginning of the algorithm and only the assigned thread can relax edges leading to a node and (ii) a dynamic workload assignment wherethe nodes are dynamically allocated to threads at the time of bucket relaxation. Based on an extensive empirical study on a range of graph classes, edge density and weight distributions, we show that while the more intuitive and widely used approach of dynamically balanced workload suits dense power-law graphs well,the static partitioning approach outperforms this more intuitive approach on awide range of graph classes. Our findings can guide a network analyst in selecting the best parallel implementation of the ∆-stepping algorithm for a given analytics task and a given graph class.
Funding Details: Science Foundation Ireland
Funding Details: Insight Research Centre
Type of material: Conference Publication
Publisher: IEEE
Copyright (published version): 2019 IEEE
Keywords: Recommender systemsHeuristic algorithmsPartitioning algorithmsMulticore processingInstruction setsData analysisComputer scienceTask analysis
DOI: 10.1109/BigData47090.2019.9006237
Other versions:
Language: en
Status of Item: Peer reviewed
Is part of: Baru, C., Huan, J., Khan, L., Hu, X., AK, R., Tian, Y., Barga, R., Zaniolo, C., Lee, K., Ye, Y.F. 2019 IEEE International Conference on Big Data: Proceedings, Dec 9- Dec 12 2019, Los Angeles, CA, USA
Conference Details: The IEEE Big Data 2019, Los Angeles, United States of America, December 9-12 2019
This item is made available under a Creative Commons License:
Appears in Collections:Computer Science Research Collection
Insight Research Collection

Show full item record

Page view(s)

Last Week
Last month
checked on Jun 15, 2021


checked on Jun 15, 2021

Google ScholarTM



If you are a publisher or author and have copyright concerns for any item, please email and the item will be withdrawn immediately. The author or person responsible for depositing the article will be contacted within one business day.