DROPS

Document

Artifact

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

Authors: Raffaele Zippo, Paul Nikolaus, and Giovanni Stea

Published in: DARTS, Volume 9, Issue 1, Special Issue of the 35th Euromicro Conference on Real-Time Systems (ECRTS 2023)

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.

Cite as

Raffaele Zippo, Paul Nikolaus, and Giovanni Stea. Isospeed: Improving (min,+) Convolution by Exploiting (min,+)/(max,+) Isomorphism (Artifact). In Special Issue of the 35th Euromicro Conference on Real-Time Systems (ECRTS 2023). Dagstuhl Artifacts Series (DARTS), Volume 9, Issue 1, pp. 3:1-3:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/DARTS.9.1.3},
  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}
}

Document

DOI: 10.4230/LIPIcs.ECRTS.2023.12

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

Authors: Raffaele Zippo, Paul Nikolaus, and Giovanni Stea

Published in: LIPIcs, Volume 262, 35th Euromicro Conference on Real-Time Systems (ECRTS 2023)

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.

Cite as

Raffaele Zippo, Paul Nikolaus, and Giovanni Stea. Isospeed: Improving (min,+) Convolution by Exploiting (min,+)/(max,+) Isomorphism. In 35th Euromicro Conference on Real-Time Systems (ECRTS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 262, pp. 12:1-12:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ECRTS.2023.12},
  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}
}

Search Results

Documents authored by Zippo, Raffaele

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

Abstract

Cite as

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

Abstract

Cite as

Thanks for your feedback!

Could not send message