License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DARTS.9.1.3
URN: urn:nbn:de:0030-drops-180247
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18024/
Go back to Dagstuhl Artifacts Series

Zippo, Raffaele ; Nikolaus, Paul ; Stea, Giovanni

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

pdf-format:
DARTS-9-1-3.pdf (0.6 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 abate the computation times of (min,+) convolution by orders of magnitude.

BibTeX - Entry

@Article{zippo_et_al:DARTS.9.1.3,
  author =	{Zippo, Raffaele and Nikolaus, Paul and Stea, Giovanni},
  title =	{{Isospeed: Improving (min,+) Convolution by Exploiting (min,+)/(max,+) Isomorphism (Artifact)}},
  pages =	{3:1--3:4},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2023},
  volume =	{9},
  number =	{1},
  editor =	{Zippo, Raffaele and Nikolaus, Paul and Stea, Giovanni},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18024},
  URN =		{urn:nbn:de:0030-drops-180247},
  doi =		{10.4230/DARTS.9.1.3},
  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: DARTS, Volume 9, Issue 1, Special Issue of the 35th Euromicro Conference on Real-Time Systems (ECRTS 2023)
Issue Date: 2023
Date of publication: 03.07.2023

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