Comparison of Single Source Shortest Path Algorithms on Two Recent Asynchronous Many-task Runtime Systems

With the advent of the exascale era, new runtimes and algorithm design techniques need to be explored. In this paper, we investigate performance of three different single-source shortest path algorithms in two relatively recent asynchronous many-task runtime systems AM++ and HPX-5. We identify the u...

Full description

Saved in:
Bibliographic Details
Main Authors: Firoz, Jesun Sahariar, Barnas, Martina, Zalewski, Marcin, Lumsdaine, Andrew
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Approximation algorithms
Computational modeling
Computer networks
Conferences
Decentralized control
Design engineering
Feasibility
Graphs
Libraries
Run time (computers)
Runtime
Shortest-path problems
Synchronization
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:With the advent of the exascale era, new runtimes and algorithm design techniques need to be explored. In this paper, we investigate performance of three different single-source shortest path algorithms in two relatively recent asynchronous many-task runtime systems AM++ and HPX-5. We identify the underlying set of differential features for these runtimes, and we compare and contrast the performance of Δ-stepping algorithm, Distributed Control based algorithm, K-level Asynchronous algorithm in AM++ and in HPX-5, for which we also include chaotic implementation. We observe that specific runtime characteristics or lack thereoff and different graph inputs can impact the feasibility of an algorithmic approach.
ISSN:2690-5965
1521-9097
DOI:10.1109/ICPADS.2015.90