License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2019.9
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11421/
Kontogiannis, Spyros ;
Papadopoulos, Anastasios ;
Paraskevopoulos, Andreas ;
Zaroliagis, Christos
Exploiting Amorphous Data Parallelism to Speed-Up Massive Time-Dependent Shortest-Path Computations
Abstract
We aim at exploiting parallelism in shared-memory multiprocessing systems, in order to speed up the execution time with as small redundancy in work as possible, for an elementary task that comes up frequently as a subroutine in the daily maintenance of large-scale time-dependent graphs representing real-world relationships or technological networks: the many-to-all time-dependent shortest paths (MATDSP) problem. MATDSP requires the computation of one time-dependent shortest-path tree (TDSPT) per origin-vertex and departure-time, from an arbitrary collection of pairs of origins and departure-times, towards all reachable destinations in the graph.
Our goal is to explore the potential and highlight the limitations of amorphous data parallelism, when dealing with MATDSP in multicore computing environments with a given amount of processing elements and a shared memory to exploit. Apart from speeding-up execution time, consumption of resources (and energy) is also critical. Therefore, we aim at limiting the work overhead for solving a MATDSP instance, as measured by the overall number of arc relaxations in shortest-path computations, while trying to minimize the overall execution time. Towards this direction, we provide several algorithmic engineering interventions for solving MATDSP concerning: (i) the compact representation of the instance; (ii) the choice and the improvement of the time-dependent single-source shortest path algorithm that is used as a subroutine; (iii) the way according to which the overall work is allocated to the processing elements; (iv) the adoption of the amorphous data parallelism rationale, in order to avoid costly synchronization among the processing elements while doing their own part of the work.
Our experimental evaluations, both on real-world and on synthetic benchmark instances of time-dependent road networks, provide insight how one should organize heavy MATDSP computations, depending on the application scenario. This insight is in some cases rather unexpected. For instance, it is not always the case that pure data parallelism (among otherwise totally independent processors) is the best choice for minimizing execution times. In certain cases it may be worthwhile to limit the level of data parallelism in favor of algorithmic parallelism, in order to achieve more efficient MATDSP computations.
BibTeX - Entry
@InProceedings{kontogiannis_et_al:OASIcs:2019:11421,
author = {Spyros Kontogiannis and Anastasios Papadopoulos and Andreas Paraskevopoulos and Christos Zaroliagis},
title = {{Exploiting Amorphous Data Parallelism to Speed-Up Massive Time-Dependent Shortest-Path Computations}},
booktitle = {19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
pages = {9:1--9:18},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {978-3-95977-128-3},
ISSN = {2190-6807},
year = {2019},
volume = {75},
editor = {Valentina Cacchiani and Alberto Marchetti-Spaccamela},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11421},
doi = {10.4230/OASIcs.ATMOS.2019.9},
annote = {Keywords: amorphous data parallelism, delta-stepping algorithm, travel-time oracle, many-to-all shortest paths, time-dependent road networks}
}
|
Keywords: |
|
amorphous data parallelism, delta-stepping algorithm, travel-time oracle, many-to-all shortest paths, time-dependent road networks |
|
Collection: |
|
19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
15.11.2019 |
