Partial-order reduction for performance analysis of max-plus timed systems

Bram van der Sanden, Marc Geilen, Michel Reniers, Twan Basten

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)

Abstract

This paper presents a partial-order reduction method for performance analysis of max-plus timed systems. A max-plus timed system is a network of automata, where the timing behavior of deterministic system tasks (events in an automaton) is captured in (max, +) matrices. These tasks can be characterized in various formalisms like synchronous data flow, Petri nets, or real-time calculus. The timing behavior of the system is captured in a (max, +) state space, calculated from the composition of the automata. This state space may exhibit redundant interleaving with respect to performance aspects like throughput or latency. The goal of this work is to obtain a smaller state space to speed up performance analysis. To achieve this, we first formalize state-space equivalence with respect to throughput and latency analysis. Then, we present a way to compute a reduced composition directly from the specification. This yields a smaller equivalent state space. We perform the reduction on-the-fly, without first computing the full composition. Experiments show the effectiveness of the method on a set of realistic manufacturing system models.

Original languageEnglish
Title of host publicationProceedings - 18th International Conference on Application of Concurrency to System Design, ACSD 2018
Place of PublicationPiscataway
PublisherInstitute of Electrical and Electronics Engineers
Pages40-49
Number of pages10
ISBN (Electronic)978-1-5386-7013-2
DOIs
Publication statusPublished - 20 Nov 2018
Event18th International Conference on Application of Concurrency to System Design, ACSD 2018 - Bratislava, Slovakia
Duration: 24 Jun 201829 Jun 2018

Conference

Conference18th International Conference on Application of Concurrency to System Design, ACSD 2018
Country/TerritorySlovakia
CityBratislava
Period24/06/1829/06/18

Keywords

  • Latency
  • Max-plus
  • Max-plus algebra
  • Max-plus automata
  • Partial-order reduction
  • Performance
  • Performance analysis
  • Throughput

Fingerprint

Dive into the research topics of 'Partial-order reduction for performance analysis of max-plus timed systems'. Together they form a unique fingerprint.

Cite this