Document Open Access Logo

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

Authors Raffaele Zippo , Paul Nikolaus , Giovanni Stea

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2023.12.pdf
  • Filesize: 1.78 MB
  • 24 pages

Document Identifiers

Author Details

Raffaele Zippo
  • Dipartimento di Ingegneria dell'Informazione, University of Firenze, Italy
  • Dipartimento di Ingegneria dell'Informazione, University of Pisa, Italy
  • Distributed Computer Systems Lab (DISCO), TU Kaiserslautern, Germany
Paul Nikolaus
  • Distributed Computer Systems Lab (DISCO), TU Kaiserslautern, Germany
Giovanni Stea
  • Dipartimento di Ingegneria dell'Informazione, University of Pisa, Italy

Funding

This work was supported in part by the Italian Ministry of Education and Research (MIUR) in the framework of the FoReLab project (Departments of Excellence).

Acknowledgements

This work is inspired by the results in [Pollex et al., 2011] - we wish to thank Steffen Bondorf for pointing out this paper to us, as well as Raul-Paul Epure for suggestions with respect to some proofs.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.ECRTS.2023.12

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.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
  • Networks → Network performance analysis
  • Mathematics of computing → Mathematical software performance
Keywords
  • Deterministic Network Calculus
  • min-plus algebra
  • max-plus algebra
  • performance
  • algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Luis Almeida and Paulo Pedreiras. Scheduling within temporal partitions: response-time analysis and server design. In Proceedings of the 4th ACM international conference on Embedded software, pages 95-103, 2004. Google Scholar
  2. François Baccelli, Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat. Synchronization and linearity: an algebra for discrete event systems. John Wiley & Sons Ltd, 1992. Google Scholar
  3. Mahmoud Bazzal, Lukas Krawczyk, and Carsten Wolff. RTCAnalysis: Practical Modular Performance Analysis of Automotive Systems with RTC. In Audrius Lopata, Daina Gudonienė, and Rita Butkienė, editors, Information and Software Technologies, pages 209-223, Cham, 2021. Springer International Publishing. Google Scholar
  4. Anne Bouillard, Marc Boyer, and Euriell Le Corronc. Deterministic Network Calculus: From Theory to Practical Implementation. Wiley, Hoboken, NJ, 2018. Google Scholar
  5. Anne Bouillard, Bertrand Cottenceau, Bruno Gaujal, Laurent Hardouin, Sébastien Lagrange, Mehdi Lhommeau, and Éric Thierry. COINC library: a toolbox for the Network Calculus. In VALUETOOLS'09, 2009. Google Scholar
  6. Anne Bouillard and Éric Thierry. An algorithmic toolbox for network calculus. Discrete Event Dynamic Systems, 18(1):3-49, 2008. Google Scholar
  7. Marc Boyer, Amaury Graillat, Benoît Dupont de Dinechin, and Jörn Migge. Bounding the delays of the MPPA network-on-chip with network calculus: Models and benchmarks. Performance Evaluation, 143:102124, 2020. URL: https://doi.org/10.1016/j.peva.2020.102124.
  8. Cheng-Shang Chang. Performance guarantees in communication networks. Springer-Verlang, New York, USA, 2000. Google Scholar
  9. Rene L Cruz. A calculus for network delay, part II: Network analysis. IEEE Transactions on information theory, 37(1):132-141, 1991. Google Scholar
  10. Rene L Cruz et al. A calculus for network delay, part I: Network elements in isolation. IEEE Transactions on information theory, 37(1):114-131, 1991. Google Scholar
  11. Xiang Feng and Aloysius K Mok. A model of hierarchical real-time virtual resources. In 23rd IEEE Real-Time Systems Symposium, 2002. RTSS 2002., pages 26-35. IEEE, 2002. Google Scholar
  12. Nan Guan and Wang Yi. Finitary real-time calculus: Efficient performance analysis of distributed embedded systems. In 2013 IEEE 34th Real-Time Systems Symposium, pages 330-339, 2013. Google Scholar
  13. Kai Lampka, Steffen Bondorf, and Jens Schmitt. Achieving efficiency without sacrificing model accuracy: Network calculus on compact domains. In 2016 IEEE 24th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS), pages 313-318. IEEE, 2016. Google Scholar
  14. Kai Lampka, Steffen Bondorf, Jens B. Schmitt, Nan Guan, and Wang Yi. Generalized finitary Real-Time calculus. In Proc. of the 36th IEEE International Conference on Computer Communications (INFOCOM 2017), 2017. Google Scholar
  15. Jean-Yves Le Boudec and Patrick Thiran. Network calculus: a theory of deterministic queuing systems for the internet. Springer Science & Business Media, Berlin, Germany, 2001. Google Scholar
  16. Euriell Le Corronc, Bertrand Cottenceau, and Laurent Hardouin. Container of (min,+)-linear systems. Discrete Event Dynamic Systems, 24(1):15-52, 2014. Google Scholar
  17. Jörg Liebeherr. Duality of the Max-Plus and Min-Plus Network Calculus. Foundations and Trends in Networking, 11(3-4):139-282, 2017. URL: https://doi.org/10.1561/1300000059.
  18. Giuseppe Lipari and Enrico Bini. Resource partitioning among real-time applications. In 15th Euromicro Conference on Real-Time Systems, 2003. Proceedings., pages 151-158. IEEE, 2003. Google Scholar
  19. David A. Nascimento, Steffen Bondorf, and Divanilson R. Campelo. Modeling and Analysis of Time-Aware Shaper on Half-Duplex Ethernet PLCA Multidrop. IEEE Transactions on Communications, 71(4):2216-2229, 2023. URL: https://doi.org/10.1109/TCOMM.2023.3246080.
  20. Victor Pollex, Henrik Lipskoch, Frank Slomka, and Steffen Kollmann. Runtime Improved Computation of Path Latencies with the Real-Time Calculus. In Proceedings of the 1st International Workshop on Worst-Case Traversal Time, pages 58-65, 2011. Google Scholar
  21. RealTime-at-Work. RTaW-Pegase (min,+) library. https://www.realtimeatwork.com/rtaw-pegase-libraries/. Accessed: 2022-04-05.
  22. Insik Shin and Insup Lee. Periodic resource model for compositional real-time guarantees. In RTSS 2003. 24th IEEE Real-Time Systems Symposium, 2003, pages 2-13. IEEE, 2003. Google Scholar
  23. Martin Stigge, Pontus Ekberg, Nan Guan, and Wang Yi. The digraph real-time task model. In 2011 17th IEEE real-time and embedded technology and applications symposium, pages 71-80. IEEE, 2011. Google Scholar
  24. Deepak Vedha Raj Sudhakar, Karsten Albers, and Frank Slomka. Generalized and scalable offset-based response time analysis of fixed priority systems. Journal of Systems Architecture, 112:101856, 2021. URL: https://doi.org/10.1016/j.sysarc.2020.101856.
  25. L. Thiele, S. Chakraborty, and M. Naedele. Real-time calculus for scheduling hard real-time systems. In 2000 IEEE International Symposium on Circuits and Systems (ISCAS), volume 4, pages 101-104 vol.4, 2000. URL: https://doi.org/10.1109/ISCAS.2000.858698.
  26. Ernesto Wandeler and Lothar Thiele. Real-Time Calculus (RTC) Toolbox. URL: http://www.mpa.ethz.ch/Rtctoolbox.
  27. Raffaele Zippo, Paul Nikolaus, and Giovanni Stea. Extending the Network Calculus Algorithmic Toolbox for Ultimately Pseudo-Periodic Functions: Pseudo-Inverse and Composition, 2022. URL: https://doi.org/10.48550/arXiv.2205.12139.
  28. Raffaele Zippo and Giovanni Stea. Nancy: An efficient parallel Network Calculus library. SoftwareX, 19:101178, 2022. URL: https://doi.org/10.1016/j.softx.2022.101178.
  29. Raffaele Zippo and Giovanni Stea. Computationally efficient worst-case analysis of flow-controlled networks with Network Calculus. IEEE Transactions on Information Theory, 2023. URL: https://doi.org/10.1109/TIT.2023.3244276.
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