2 Search Results for "Gr�nbaum, Alberto F."

Document
DOI: 10.4230/OASIcs.ATMOS.2019.9
Exploiting Amorphous Data Parallelism to Speed-Up Massive Time-Dependent Shortest-Path Computations

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

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:OASIcs.ATMOS.2019.9,
  author =	{Kontogiannis, Spyros and Papadopoulos, Anastasios and Paraskevopoulos, Andreas and Zaroliagis, Christos},
  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 =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.9},
  URN =		{urn:nbn:de:0030-drops-114210},
  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}
}
Document
DOI: 10.4230/DagSemProc.07461.14
QBD processes and matrix orthogonal polynomilas: somw new explicit examples

Authors: Alberto F. Grünbaum

Published in: Dagstuhl Seminar Proceedings, Volume 7461, Numerical Methods for Structured Markov Chains (2008)

Abstract
In the case of birth-and-death processes there are a few exactly solvable situations where the n-step transition matrix can be written down using the Karlin-McGregor formula. A few of these come from group representation theory. I plan to show how this can be extended to some instances of QBD processes with an arbitrary finite number of phases. The group involved is the set of all unitary matrices of size N. For a fixed N one gets examples where the number of phases is a free parameter, and there are a few extra parameters to play with. By tunning these parameters one can exhibit examples where states are recurrent or transient. The rather surprising fact that for these examples one can compute everything explicitly raises the issue of finding a possible network application for this piece of mathematics that involves matrix valued orthogonal polynomials. I will give an ab-initio discussion of the examples starting with the case of one phase.
Cite as

Alberto F. Grünbaum. QBD processes and matrix orthogonal polynomilas: somw new explicit examples. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{grunbaum:DagSemProc.07461.14,
  author =	{Gr\"{u}nbaum, Alberto F.},
  title =	{{QBD processes and matrix orthogonal polynomilas: somw new explicit examples}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.14},
  URN =		{urn:nbn:de:0030-drops-13922},
  doi =		{10.4230/DagSemProc.07461.14},
  annote =	{Keywords: QBD, orthogonal polynomials, Karlin-McGregor formula, representation theory}
}
  • Refine by Author
  • 1 Grünbaum, Alberto F.
  • 1 Kontogiannis, Spyros
  • 1 Papadopoulos, Anastasios
  • 1 Paraskevopoulos, Andreas
  • 1 Zaroliagis, Christos

  • Refine by Classification
  • 1 Theory of computation → Shared memory algorithms

  • Refine by Keyword
  • 1 Karlin-McGregor formula
  • 1 QBD
  • 1 amorphous data parallelism
  • 1 delta-stepping algorithm
  • 1 many-to-all shortest paths
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2008
  • 1 2019

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