Document Open Access Logo

Exploiting Amorphous Data Parallelism to Speed-Up Massive Time-Dependent Shortest-Path Computations

Authors Spyros Kontogiannis, Anastasios Papadopoulos, Andreas Paraskevopoulos, Christos Zaroliagis

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2019.9.pdf
  • Filesize: 1.58 MB
  • 18 pages

Document Identifiers

Author Details

Spyros Kontogiannis
  • University of Ioannina, Greece
  • Computer Technology Institute & Press, Rion, Greece
Anastasios Papadopoulos
  • University of Patras, Greece
Andreas Paraskevopoulos
  • University of Patras, Greece
Christos Zaroliagis
  • University of Patras, Greece
  • Computer Technology Institute & Press, Rion, Greece

Funding

S. Kontogiannis, A. Papadopoulos, C. Zaroliagis: Partially supported by the INTERREG V-A GR-IT programme 2014-2020 (project INVESTMENT). A. Paraskevopoulos: Supported by the Hellenic Foundation for Research and Innovation, and the General Secretariat for Research and Technology of Greece (project 10110).

Cite AsGet BibTex

Spyros Kontogiannis, Anastasios Papadopoulos, Andreas Paraskevopoulos, and Christos Zaroliagis. Exploiting Amorphous Data Parallelism to Speed-Up Massive Time-Dependent Shortest-Path Computations. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/OASIcs.ATMOS.2019.9

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shared memory algorithms
Keywords
  • amorphous data parallelism
  • delta-stepping algorithm
  • travel-time oracle
  • many-to-all shortest paths
  • time-dependent road networks

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory Algorithms and Applications. Prentice Hall, Englewood Cliffs, 1993. Google Scholar
  2. M. Amber-Hassaan, M. Burtscher, and K. Pingali. Ordered vs. unordered: Acomparison of parallelism and work-efficiency in irregular algorithms. Sigplan Notices - SIGPLAN, 46:3-12, 2011. Google Scholar
  3. G. V. Batz, R. Geisberger, P. Sanders, and C. Vetter. Minimum Time-Dependent Travel Times with Contraction Hierarchies. ACM Journal of Experimental Algorithmics, 18(1):1-43, 2013. URL: https://github.com/GVeitBatz/KaTCH.
  4. R. Bellman. On a Routing Problem. Quarterly of Applied Mathematics, 16, 1958. Google Scholar
  5. V. T. Chakaravarthy, F. Checconiy, P. Murali, F. Petriniy, and Y. Sabharwal. Scalable Single Source Shortest Path Algorithms for Massively Parallel Systems. IEEE Transactions on Parallel &Distributed Systems, 28:2031-2045, 2017. Google Scholar
  6. D. Delling, A. V. Goldberg, A. Nowatzyk, and R. F. Werneck. PHAST: Hardware-accelerated shortest path trees. IEEE International Parallel Distributed Processing Symposium (IPDPS), pages 921-931, 2011. Google Scholar
  7. E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269-271, 1959. Google Scholar
  8. S. E. Dreyfus. An appraisal of some shortest-path algorithms. Operations Research, 17(3):395-412, 1969. Google Scholar
  9. M. L. Fredman, R. Sedgewick, D. D. Sleator, and R. E. Tarjan. The pairing heap - A new form of self-adjusting heap. Algorithmica, 1:111-119, 1986. Google Scholar
  10. L. R. Ford Jr. Network flow theory. Technical report, RAND CORP SANTA MONICA CA, 1956. Google Scholar
  11. S. Kontogiannis, G. Papastavrou, A. Paraskevopoulos, D. Wagner, and C. Zaroliagis. Improved Oracles for Time-Dependent Road Networks. Algorithmic Approaches for Transportation Modeling Optimization, and Systems (ATMOS), 2017. Google Scholar
  12. D. Larkin, S. Sen, and R. E. Tarjan. A Back-to-basics Empirical Study of Priority Queues. Algorithm Engineering &Experiments (ALENEX), pages 61-72, 2014. Google Scholar
  13. G. Mali, P. Michail, A. Paraskevopoulos, and C. Zaroliagis. A new dynamic graph structure for large-scale transportation networks. Conference on Algorithms and Complexity (CIAC), pages 312-323, 2013. LNCS 7878. Google Scholar
  14. U. Meyer and P. Sanders. Δ-stepping: a parallelizable shortest path algorithm. Journal of Algorithms, 49(1):114-152, 2003. Google Scholar
  15. G. Nannicini, D. Delling, D. Schultes, and L. Liberti. Bidirectional A* search on time-dependent road networks. Networks, 59:240-251, 2012. Google Scholar
  16. D. Nguyen, A. Lenharth, and K. Pingali. A lightweight infrastructure for graph analytics. ACM Symposium on Operating Systems Principles (SOSP), pages 456-471, 2013. Google Scholar
  17. D. Nguyen, A. Lenharth, and K. Pingali. Deterministic Galois: On-demand Portable and Parameterless. International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 499-512, 2014. Google Scholar
  18. A. Orda and R. Rom. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. Journal of the ACM, 37(3):607-625, 1990. Google Scholar
  19. K. Pingali, D. Nguyen, M. Kulkarni, M. Burtscher, M. Amber-Hassaan, R. Kaleem, T.-H. Lee, A. Lenharth, R. Manevich, M. Méndez-Lojo, D. Prountzos, and X. Sui. The tao of parallelism in algorithms. ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 12-25, 2011. Google Scholar
  20. P. Sanders. Fast Priority Queues for Cached Memory. Journal of Experimental Algorithmics, 5(7), 2000. ACM, New York, NY, USA. Google Scholar
  21. P. Sanders, D. Schultes, and C. Vetter: Mobile route planning. Mobile route planning. European symposium on Algorithms (ESA), pages 732-743, 2008. Google Scholar
  22. E. Strubell, A. Ganesh, and A. McCallum. Energy and Policy Considerations for Deep Learning in NLP. Annual Meeting of the Association for Computational Linguistics (ACL), 2019. URL: http://arxiv.org/abs/1906.02243.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact