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: http://hdl.handle.net/10197/12201
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: http://bigdataieee.org/BigData2019/
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: https://creativecommons.org/licenses/by-nc-nd/3.0/ie/
Appears in Collections:Computer Science Research Collection
Insight Research Collection

Show full item record

Page view(s)

40
Last Week
5
Last month
checked on Jun 15, 2021

Download(s)

8
checked on Jun 15, 2021

Google ScholarTM

Check

Altmetric


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