License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECRTS.2023.12
URN: urn:nbn:de:0030-drops-180415
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18041/
Go to the corresponding LIPIcs Volume Portal

Zippo, Raffaele ; Nikolaus, Paul ; Stea, Giovanni

Isospeed: Improving (min,+) Convolution by Exploiting (min,+)/(max,+) Isomorphism

pdf-format:
LIPIcs-ECRTS-2023-12.pdf (2 MB)

Abstract

(min,+) convolution is the key operation in (min,+) algebra, a theory often used to compute performance bounds in real-time systems. As already observed in many works, its algorithm can be computationally expensive, due to the fact that: i) its complexity is superquadratic with respect to the size of the operands; ii) operands must be extended before starting its computation, and iii) said extension is tied to the least common multiple of the operand periods.
In this paper, we leverage the isomorphism between (min,+) and (max,+) algebras to devise a new algorithm for (min,+) convolution, in which the need for operand extension is minimized. This algorithm is considerably faster than the ones known so far, and it allows us to reduce the computation times of (min,+) convolution by orders of magnitude.

BibTeX - Entry

@InProceedings{zippo_et_al:LIPIcs.ECRTS.2023.12,
  author =	{Zippo, Raffaele and Nikolaus, Paul and Stea, Giovanni},
  title =	{{Isospeed: Improving (min,+) Convolution by Exploiting (min,+)/(max,+) Isomorphism}},
  booktitle =	{35th Euromicro Conference on Real-Time Systems (ECRTS 2023)},
  pages =	{12:1--12:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-280-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{262},
  editor =	{Papadopoulos, Alessandro V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18041},
  URN =		{urn:nbn:de:0030-drops-180415},
  doi =		{10.4230/LIPIcs.ECRTS.2023.12},
  annote =	{Keywords: Deterministic Network Calculus, min-plus algebra, max-plus algebra, performance, algorithms}
}

Keywords: Deterministic Network Calculus, min-plus algebra, max-plus algebra, performance, algorithms
Collection: 35th Euromicro Conference on Real-Time Systems (ECRTS 2023)
Issue Date: 2023
Date of publication: 03.07.2023
Supplementary Material: Software (ECRTS 2023 Artifact Evaluation approved artifact): https://doi.org/10.4230/DARTS.9.1.3

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI