Search Results

Documents authored by Stea, Giovanni

Document
Artifact
DOI: 10.4230/DARTS.9.1.3
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}
}
Document
DOI: 10.4230/DagRep.9.3.1
Analysis, Design, and Control of Predictable Interconnected Systems (Dagstuhl Seminar 19101)

Authors: Kunal Agrawal, Enrico Bini, and Giovanni Stea

Published in: Dagstuhl Reports, Volume 9, Issue 3 (2019)

Abstract
We call "Interconnected Systems" any collection of systems distributed over a metric space whose behavior is influenced by its neighborhood. Examples of interconnected systems exist at very different scales: different cores over the same silicon, different sub-systems in vehicles, communicating nodes over either a physical (e.g., optical) network, or - more recently - virtualized network. Examples also exist in contexts which are not related to computing or communication. Smart Grids (of energy production, distribution, and consumption) and Intelligent Transportation Systems are just two notable examples. The common characteristic among all these examples is the presence of a spatially distributed demand of resources (energy, computing, communication bandwidth, etc.) which needs to be matched with a spatially distributed supply. Often times demands and availability of resources of different types (e.g., computing and link bandwidth in virtualized network environments) need to be matched simultaneously. Time predictability is a key requirement for above systems. Despite this, the strong market pressure has often led to ``quick and dirty'' best-effort solutions, which make it extremely challenging to predict the behavior of such systems. Research communities have developed formal theories for predictability which are specialized to each application domain or type of resource (e.g., schedulability analysis for real-time systems or network calculus for communication systems). However, the emerging application domains (virtualized networks, cyber-physical systems, etc.) clearly require a unified, holistic approach. By leveraging the expertise, vision and interactions of scientists that have addressed predictability in different areas, the proposed seminar aims at constructing a common ground for the theory supporting the analysis, the design, and the control of predictable interconnected systems.
Cite as

Kunal Agrawal, Enrico Bini, and Giovanni Stea. Analysis, Design, and Control of Predictable Interconnected Systems (Dagstuhl Seminar 19101). In Dagstuhl Reports, Volume 9, Issue 3, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{agrawal_et_al:DagRep.9.3.1,
  author =	{Agrawal, Kunal and Bini, Enrico and Stea, Giovanni},
  title =	{{Analysis, Design, and Control of Predictable Interconnected Systems (Dagstuhl Seminar 19101)}},
  pages =	{1--15},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{3},
  editor =	{Agrawal, Kunal and Bini, Enrico and Stea, Giovanni},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.3.1},
  URN =		{urn:nbn:de:0030-drops-112882},
  doi =		{10.4230/DagRep.9.3.1},
  annote =	{Keywords: distributed resource management, network calculus, real-time systems}
}
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