Switching Max-Plus-Linear Systems

Many systems have deterministic concurrent behavior. Tasks or operations are executed in fixed patterns and with fixed dependencies. Examples are software task graphs, or operations of a manufacturing system.

If we are interested in performance related questions about such systems, e.g., “what is the average throughput?”, or “What is the makespan or latency?”, then max-plus algebra is often a very suitable model to study such systems.

Max-Plus Linear Systems

Max-plus algebra [1, 2, 3, 4] is a linear algebra and therefore has strong analysis possibilities.

It captures concurrency in a very different way than state-based models, which allow one to escape the state-space explosion problem in some cases.

Switching Max-Plus-Linear Systems

A strong prerequisite to the use of plain max-plus-linear modeling is the requirement that systems behave deterministically, i.e., alwyas execute the same operations in the same order.

Many systems in practice do not always behave deteministically. Some operations may or not be included in the task, may be interrupted by sporadic maintenance or startup-up actions.

This challenge may be addressed by considering switched max-plus-linear systems. These are systems that may switch between different max-plus-linear modes of operations.

The possible orders in which such modes can occur can restricted by a separate specification, typically using some form of automata.

See also

  • SADF
  • LSAT
  • xCPS

Related Publications

  • F. Siyoum, M. Geilen, J. Eker, C. von Platen, and H. Corporaal, “Automated extraction of scenario sequences from disciplined dataflow networks,” in Formal methods and models for codesign (memocode), 2013 eleventh ieee/acm international conference on, 2013, pp. 47-56.
    [Bibtex]
    @InProceedings{Siyoum2013,
    Title = {Automated extraction of scenario sequences from disciplined dataflow networks},
    Author = {F. Siyoum and M. Geilen and J. Eker and C. von Platen and H. Corporaal},
    Booktitle = {Formal Methods and Models for Codesign (MEMOCODE), 2013 Eleventh IEEE/ACM International Conference on},
    Year = {2013},
    Month = {Oct},
    Pages = {47-56},
    Abstract = {Analysing deadlock-freedom, boundedness and realtime constraints are crucial steps in the design of embedded streaming applications. Dataflow models of computation are often used to analyse such properties at design-time. To that end, scenario-based dataflow techniques isolate the individual operating scenarios of a dynamic application and analyse the executions of the possible scenario sequences. These techniques have rigorous analytical methods to verify consistency and realtime constraints. To exploit these benefits, identification of all scenarios and scenario sequences is required. This is challenging because of the large number of possible scenarios in modern-day dynamic applications. Manual construction is generally time-consuming and error-prone. In this paper, we address this challenge with an automated approach that extracts a scenario-based analysis model for a class of parallel implementations, which we call Disciplined Dataflow Network (DDN). DDN always guarantees construction of a scenario-based analysis model and enables automating the extraction process. The extraction process identifies all possible scenarios of a DDN and employs state-space enumeration to determine all possible sequences of executions of these scenarios. The approach is demonstrated for the CAL actor language and has been implemented in an openly available CAL compiler. Case studies are presented for the RVC-MPEG video decoder and WLAN 802.11a baseband processing. The case studies show the benefits of automated scenario extraction for efficient design-time analysis of dynamic streaming applications.},
    Keywords = {concurrency control;data flow analysis;data flow computing;embedded systems;media streaming;parallel languages;parallel programming;program compilers;program verification;CAL actor language;CAL compiler;DDN;RVC-MPEG video decoder;WLAN 802.11a baseband processing;automated scenario sequence extraction;boundedness;consistency verification;deadlock freedom;design time analysis;disciplined dataflow network;dynamic application;dynamic streaming;embedded streaming application;real time constraint;scenario-based dataflow technique;state-space enumeration;Analytical models;Detectors;Firing;Kernel;Ports (Computers);Schedules;System recovery;CAL;SDF;actor language;design-time analysis;dynamism;process network;real-time;scenario},
    Owner = {rvkampenhout},
    Timestamp = {2016.11.16}
    }

  • [DOI] M. Geilen, J. Falk, C. Haubelt, T. Basten, B. Theelen, and S. Stuijk, “Performance analysis of weakly-consistent scenario-aware dataflow graphs,” Journal of signal processing systems, vol. 87, iss. 1, p. 157–175, 2017.
    [Bibtex]
    @Article{GFHea16,
    author = {Geilen, Marc and Falk, Joachim and Haubelt, Christian and Basten, Twan and Theelen, Bart and Stuijk, Sander},
    title = {Performance Analysis of Weakly-Consistent Scenario-Aware Dataflow Graphs},
    journal = {Journal of Signal Processing Systems},
    year = {2017},
    volume = {87},
    number = {1},
    pages = {157--175},
    issn = {1939-8115},
    abstract = {The timed dataflow model of computation is a useful performance analysis tool for electronic system level design automation and embedded software synthesis. Its determinism gives it strong analyzability properties. Its monotonic temporal behavior provides hard real-time guarantees on throughput and latency. It is expressive enough to cover a large class of applications and platforms. The trend however, in both embedded applications and their platforms is to become more dynamic, reaching the limits of what the model can express and analyze with tight performance guarantees. Scenario-aware dataflow (SADF) allows more dynamism to be expressed, introducing a controlled amount of non-determinism into the model to represent different scenarios of behavior. We investigate so-called weakly consistent graphs in which the scenario changes are not tightly coupled with periods of repetitive behavior of the static dataflow behavior in scenarios as in previous methods. We define the semantics of such graphs in terms of ( max , + ) {\$}({\backslash}max , +){\$} -algebra and we introduce a method to analyze throughput using a generalization of ( max , + ) {\$}({\backslash}max , +){\$} -automata. We show that weakly-consistent SADF generalizes many of the existing analyzable dynamic dataflow models, such as CSDF, PDF and CFDF and we present an algorithm to convert CSDF graphs to SADF.},
    doi = {10.1007/s11265-016-1193-7},
    url = {http://dx.doi.org/10.1007/s11265-016-1193-7},
    }

  • M. C. W. Geilen and S. Stuijk, “Worst-case performance analysis of synchronous dataflow scenarios,” in International conference on hardware-software codesign and system synthesis, codes+isss 10, proc., scottsdale, az, usa, 24-29 october, 2010, 2010, pp. 125-134.
    [Bibtex]
    @InProceedings{GS10,
    author = {M.C.W. Geilen and S. Stuijk},
    title = {Worst-case Performance Analysis of Synchronous Dataflow Scenarios},
    booktitle = {International Conference on Hardware-Software Codesign and System Synthesis, CODES+ISSS 10, Proc., Scottsdale, Az, USA, 24-29 October, 2010},
    year = {2010},
    pages = {125-134},
    owner = {mgeilen},
    timestamp = {2011.04.08},
    }

  • [DOI] B. van der Sanden, J. Bastos, J. Voeten, M. Geilen, M. A. Reniers, T. Basten, J. Jacobs, and R. R. H. Schiffelers, “Compositional specification of functionality and timing of manufacturing systems,” in 2016 forum on specification and design languages, FDL 2016, bremen, germany, september 14-16, 2016, 2016, p. 1–8.
    [Bibtex]
    @InProceedings{SBVea16,
    author = {Bram van der Sanden and Jo{\~{a}}o Bastos and Jeroen Voeten and Marc Geilen and Michel A. Reniers and Twan Basten and Johan Jacobs and Ramon R. H. Schiffelers},
    title = {Compositional specification of functionality and timing of manufacturing systems},
    booktitle = {2016 Forum on Specification and Design Languages, {FDL} 2016, Bremen, Germany, September 14-16, 2016},
    year = {2016},
    pages = {1--8},
    doi = {10.1109/FDL.2016.7880372},
    timestamp = {Wed, 24 May 2017 08:31:17 +0200},
    url = {https://doi.org/10.1109/FDL.2016.7880372},
    }

  • B. van der Sanden, “Performance analysis and optimization of supervisory controllers,” PhD Thesis, 2018.
    [Bibtex]
    @PhdThesis{San18,
    author = {Bram van der Sanden},
    title = {performance analysis and optimization of supervisory controllers},
    school = {Eindhoven University of Technology},
    year = {2018},
    }

References

[1] B. Heidergott, G. J. Olsder, and J. van der Woude, Max plus at work, Princeton university press, 2006.
[Bibtex]
@Book{HOW06,
title = {Max Plus at Work},
publisher = {Princeton University Press},
year = {2006},
author = {Bernd Heidergott and Geert Jan Olsder and Jacob van der Woude},
owner = {mgeilen},
timestamp = {2009.07.06},
}
[2] [doi] T. J. J. van den Boom and B. De Schutter, “Modelling and control of discrete event systems using switching max-plus-linear systems,” Control engineering practice, vol. 14, iss. 10, p. 1199–1211, 2006.
[Bibtex]
@Article{BD06,
author = {T.J.J. {van den Boom} and B. {De Schutter}},
title = {Modelling and control of discrete event systems using switching max-plus-linear systems},
journal = {Control Engineering Practice},
year = {2006},
volume = {14},
number = {10},
pages = {1199--1211},
month = oct,
doi = {10.1016/j.conengprac.2006.02.006},
}
[3] S. Gaubert, “Performance evaluation of (max, +) automata,” Ieee trans. automatic control, vol. 40, iss. 12, pp. 2014-2025, 1995.
[Bibtex]
@Article{Gau95,
author = {S. Gaubert},
title = {Performance Evaluation of (max, +) automata},
journal = {IEEE Trans. Automatic Control},
year = {1995},
volume = {40},
number = {12},
pages = {2014-2025},
owner = {mgeilen},
timestamp = {2010.04.10},
}
[4] F. Baccelli, G. Cohen, G. J. Olsder, and J.P.Quadrat, Synchronization and linearity, John wiley & sons, 1992.
[Bibtex]
@Book{BCO92,
title = {Synchronization and Linearity},
publisher = {John Wiley \& Sons},
year = {1992},
author = {F. Baccelli and G. Cohen and G.J. Olsder and J.P.Quadrat},
owner = {mgeilen},
timestamp = {2009.04.22},
}