Welcome to "Quantitative Formal Modeling and Worst-Case Performance Analysis," an intellectually stimulating course designed to hone your abstract thinking skills in the realm of theoretical computer science.
This course invites you to dive deep into the world of token production and consumption, a foundational approach to system behaviour. Master the art of mathematically formalizing these concepts through prefix orders and counting functions. Get hands-on with Petri-nets, explore the nuances of timing, and delve into the scheduling intricacies of token systems. You'll even learn to conduct worst-case performance analysis on single-rate dataflow graphs, examining key metrics like throughput, latency, and buffering.
Why the focus on small examples rather than industrial-size systems? The aim here is twofold: First, we strive to cultivate your ability to think abstractly and mathematically about modelling and performance—a vital skill for tackling any future challenges in this field. Second, while dataflow techniques are indeed industry-applicable, this course serves as an essential primer that focuses on single-rate dataflow, the cornerstone of more advanced dataflow techniques.
And here's a bonus: this course forms part of the esteemed Quantitative Evaluation of Embedded Systems (QEES) curriculum offered under the aegis of the EIT-Digital University and the Dutch 3TU consortium. While the examination for QEES is more advanced, this course perfectly mirrors its initial three-week content, offering you a robust academic experience online.
Ready to sharpen your abstract thinking and delve into the fascinating world of formal modelling? Enroll now to secure your spot.
Overview
Syllabus
- Introduction
- This course is part of a Blended Master Programme in Embedded Systems.
- Modeling systems as token consumption/production systems
- In this module/week you will learn to draw a model of a token consumption/production system, and communicate your interpretation of this model with others in an informal manner. At the end of this model, you will be able to draw your own models, and explain your interpretation of them in general terms. Also, you will know about the standard Petri-net interpretation of consumption/production systems, and will be able to point out particular patterns in Petri-net models. Finally, you will be able to refine a consumption/production model into a model that contains sufficient information to allow worst-case performance analysis. This is all tested using a peer-reviewed assignment.
- Syntax and semantics
- In this module/week, you will be really training your abstract thinking skills. After finishing this module, you will have learned how to formalize the behavior of any dynamical system as a prefix order, and how to formalize the interpretation of a consumption/production system as a counting function on such a prefix order. You understand how the Petri-net interpretation puts certain restrictions on these counting functions, and how you can exploit those restrictions to prove properties about Petri-net interpretations, without knowing the actual interpretation itself. At the end of the module, you will practice the formalization of performance metrics as logical properties of counting functions, by recognizing right and wrong examples of formalization. Those who are already familiar with Petri-net theory, may find that the prefix order semantics that I introduce in this course is slightly different from what they are used to. Traditional Petri-net semantics is usually based on markings, transition systems, or the execution trees thereoff. Execution trees are a particular example of a prefix order, but in general prefix orders offer the added flexibility that they do not restrict the user to discrete interpretations of behavior only. This is particularly suitable when seeking connection between theoretical computer science and an application field like embedded systems, from which this course originates, where also the continuous behavior of physical systems has to be taken into account.
- Performance analysis
- In this module/week you will learn to exploit the structure of single-rate dataflow graphs to perform worst-case analysis of performance metrics like throughput, latency and buffering. After this week, you know how to calculate the maximum cycle mean of a dataflow graph, how to construct a periodic schedule for it, how to optimize this schedule for latency analysis, and how to determine the size of buffers with back-pressure such that the worst-case analysis remains valid. If you understood the material of the previous module/week, the proofs presented in this week will give you a deeper understanding of the mathematical underpinning of these methods.
- One final example
- In this last week, we just discuss one more example, following the outline of the peer-reviewed assignment of the first module/week. It's just a little summary, combining everything we have learned so far, and there is some additional reading material to trigger an appetite for further discovery.
Taught by
Dr.ir. Pieter Cuijpers
Tags
Related articles
Reviews
3.0 rating, based on 3 Class Central reviews
4.4 rating at Coursera based on 44 ratings
-
Excellent course. Both challenging and interesting at the same time. Also the teacher has a very clear and engaging style. I would thoroughly recommend this course.
-
Alex Ivanov
