Engineering a Parallel ∆-stepping Algorithm
|Title:||Engineering a Parallel ∆-stepping Algorithm||Authors:||Duriakova, Erika; Ajwani, Deepak; Hurley, 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 systems; Heuristic algorithms; Partitioning algorithms; Multicore processing; Instruction sets; Data analysis; Computer science; Task 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
If you are a publisher or author and have copyright concerns for any item, please email email@example.com and the item will be withdrawn immediately. The author or person responsible for depositing the article will be contacted within one business day.