Coursera
Explore
  • Browse
  • Search
  • For Enterprise
  • Log In
  • Sign Up

Quantitative Formal Modeling and Worst-Case Performance Analysis

OverviewSyllabusFAQsCreatorsRatings and Reviews

HomeComputer ScienceSoftware Development

Quantitative Formal Modeling and Worst-Case Performance Analysis

EIT Digital

About this course: Welcome to Quantitative Formal Modeling and Worst-Case Performance Analysis. In this course, you will learn about modeling and solving performance problems in a fashion popular in theoretical computer science, and generally train your abstract thinking skills. After finishing this course, you have learned to think about the behavior of systems in terms of token production and consumption, and you are able to formalize this thinking mathematically in terms of prefix orders and counting functions. You have learned about Petri-nets, about timing, and about scheduling of token consumption/production systems, and for the special class of Petri-nets known as single-rate dataflow graphs, you will know how to perform a worst-case analysis of basic performance metrics, like throughput, latency and buffering. Disclaimer: As you will notice, there is an abundance of small examples in this course, but at first sight there are not many industrial size systems being discussed. The reason for this is two-fold. Firstly, it is not my intention to teach you performance analysis skills up to the level of what you will need in industry. Rather, I would like to teach you to think about modeling and performance analysis in general and abstract terms, because that is what you will need to do whenever you encounter any performance analysis problem in the future. After all, abstract thinking is the most revered skill required for any academic-level job in any engineering discipline, and if you are able to phrase your problems mathematically, it will become easier for you to spot mistakes, to communicate your ideas with others, and you have already made a big step towards actually solving the problem. Secondly, although dataflow techniques are applicable and being used in industry, the subclass of single-rate dataflow is too restrictive to be of practical use in large modeling examples. The analysis principles of other dataflow techniques, however, are all based on single-rate dataflow. So this course is a good primer for any more advanced course on the topic. This course is part of the university course on Quantitative Evaluation of Embedded Systems (QEES) as given in the Embedded Systems master curriculum of the EIT-Digital university, and of the Dutch 3TU consortium consisting of TU/e (Eindhoven), TUD (Delft) and UT (Twente). The course material is exactly the same as the first three weeks of QEES, but the examination of QEES is at a slightly higher level of difficulty, which cannot (yet) be obtained in an online course.

Who is this class for: This course is aiming for first year Master students in Electrical Engineering or Computer Science. Note that as a consequence, quiz questions are more like exam questions where you have to construct the answer based on the principles that are taught in the web lectures, rather than to recall the literal text of the teacher.


Created by:  EIT Digital
EIT Digital

  • Dr.ir. Pieter Cuijpers

    Taught by:  Dr.ir. Pieter Cuijpers, Assistant Professor

    Mathematics and Computer Science

  • Anne Remke

    Taught by:  Anne Remke, Prof. dr.

    Computer Science
Commitment5 weeks of study, 1-2 hours/week
Language
English
How To PassPass all graded assignments to complete the course.
User Ratings
4.4 stars
Average User Rating 4.4See what learners said
Syllabus
WEEK 1
Introduction
This course is part of a Blended Master Programme in Embedded Systems.
1 video, 1 reading
  1. Video: Introduction
  2. 읽기 자료: Some suggested reading material
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.
11 videos, 3 readings, 2 practice quizzes
  1. Video: A single picture tells more than a thousand words
  2. Video: Consumption and production of tokens
  3. 읽기 자료: Always ask yourself...
  4. Video: Modeling an intensive care unit
  5. Video: Modeling a wireless LAN radio
  6. Video: Modeling and refining an industrial robot
  7. 연습 문제: Modeling Warehouse 13
  8. Video: Pick your own system
  9. Video: Classes of Petri-nets
  10. Video: Causality, choice and concurrency (modeling patterns)
  11. Video: Refinement of consumption/production systems
  12. 읽기 자료: The refinement of the robot.
  13. 연습 문제: Definition of refinement
  14. Video: Interpreting pictures for performance analysis
  15. Video: Draw your own model
  16. 읽기 자료: Tooling
Graded: Basic modeling ideas
Graded: Modeling features
Graded: Which is a refinement of which?
Graded: Draw your own model
WEEK 2
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.
14 videos, 5 readings, 4 practice quizzes
  1. Video: Warning: prepare for some set theory!
  2. 읽기 자료: Flags and Fitch style proofs
  3. Video: Syntax and semantics
  4. Video: The basics
  5. Video: Extensions
  6. Video: Prefix orders
  7. Video: Exercise on prefix orders
  8. Video: Proof that flows form a prefix order
  9. 읽기 자료: Slides of the proof
  10. Video: Formalizing interpretations as functions
  11. Video: Counting is order preserving
  12. 연습 문제: Thinking about observation functions
  13. 연습 문제: Isomorphism
  14. Video: Formalizing the Petri-net interpretation
  15. Video: Proof that the number of tokens in a single-rate dataflow cycle is constant
  16. 읽기 자료: Slides of the proof
  17. 연습 문제: Summarize!
  18. Video: Formalizing timing
  19. 읽기 자료: Exercise: Formalize best-case response times
  20. Video: Formalizing eager scheduling
  21. Video: Formalizing periodic scheduling
  22. 읽기 자료: About the next quiz.
  23. 연습 문제: Formalizing performance properties
Graded: Bipartite graphs
WEEK 3
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.
20 videos, 2 readings, 1 practice quiz
  1. Video: Running example
  2. Video: Throughput is bounded by 1/MCM
  3. Video: Proof - a
  4. Video: Proof - b
  5. Video: Proof - c
  6. Video: Proof - d
  7. Video: Proof - e
  8. Video: Proof - f
  9. Video: Proof - g
  10. Video: Proof - h
  11. Video: Proof - i
  12. Video: Proof - j
  13. 읽기 자료: Slides of the proof
  14. 연습 문제: Summarize!
  15. Video: The throughput bound is tight
  16. 읽기 자료: Alternative proof in synchronization and linearity
  17. Video: Periodic scheduling of a dataflow graph
  18. Video: Latency analysis of a periodic schedule
  19. Video: Latency analysis of an eager schedule
  20. Video: The formal definition of latency
  21. Video: The boot-up time of a dataflow graph
  22. Video: Optimizing latency estimates w.r.t. boot-up time
  23. Video: Buffering and backpressure
Graded: Calculating the MCM and worst-case throughput
Graded: Calculate some periodic schedules
Graded: Calculating optimal periodic schedules and their latencies
Graded: Calculating suitable buffer sizes
WEEK 4
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.
1 video, 5 readings
  1. Video: One final example
  2. 읽기 자료: 2015 Assignment on dataflow modeling.
  3. 읽기 자료: Additional dataflow exercises
  4. 읽기 자료: Example of an exam at masters level (without solutions)
  5. 읽기 자료: Another example of an exam (with solutions)
  6. 읽기 자료: Material created by fellow students

FAQs
How It Works
수업 활동
수업 활동

각 강좌는 대화형 교과서 형식으로 이루어지며, 사전 녹화된 비디오, 테스트, 프로젝트를 포함합니다.

동료로부터의 도움
동료로부터의 도움

수천 명의 다른 동료 학습자와 함께 논의하고, 강좌 자료에 대하여 토론하고, 개념 습득을 위해 서로 도움을 받으십시오.

수료증
수료증

귀하의 성과를 공식적으로 인정받아 친구, 동료, 회사에 성과를 공유해 보세요.

Creators
EIT Digital
EIT Digital is a pan-European education and research-based open innovation organization founded on excellence. Its mission is to foster digital technology innovation and entrepreneurial talent for economic growth and quality of life. By linking education, research and business, EIT Digital empowers digital top talents for the future. EIT Digital provides online "blended" Innovation and Entrepreneurship education to raise quality, increase diversity and availability of the top-level content provided by 20 reputable universities of technology around Europe. The universities all together deliver a unique blend of the best of technical excellence and entrepreneurial skills and mindset to digital engineers and entrepreneurs at all stages of their careers. The academic partners support Coursera’s bold vision to enable anyone, anywhere, to transform their lives by accessing the world’s best learning experience. This means that EIT Digital gradually shares parts of its entrepreneurial and academic education programmes to demonstrate its excellence and make it accessible to a much wider audience. EIT Digital’s online education portfolio can be used as part of blended education settings, in both Master and Doctorate programmes, and for professionals as a way to update their knowledge. EIT Digital offers an online programme in 'Internet of Things through Embedded Systems'. Achieving all certificates of the online courses and the specialization provides an opportunity to enroll in the on campus program and get a double degree. These are the courses in the online programme:
Ratings and Reviews
Rated 4.4 out of 5 of 35 ratings
Michael Blonsky

Great lectures and format. The content was quiet complicated, especially the math proofs, but they make it easy to skip over the tough parts. It's a great way to learn how to think critically and logically about all sorts of systems.

Kuei-Ti Lu

The videos are sometimes interesting, but explanations would have been clearer if there are documents provided as visual aids.



You May Also Like
EIT Digital
System Validation (2): Model process behaviour
1 course
EIT Digital
System Validation (2): Model process behaviour
View course
EIT Digital
System Validation (3): Requirements by modal formulas
1 course
EIT Digital
System Validation (3): Requirements by modal formulas
View course
EIT Digital
System Validation (4): Modelling Software, Protocols, and other behaviour
1 course
EIT Digital
System Validation (4): Modelling Software, Protocols, and other behaviour
View course
EIT Digital
System Validation: Automata and behavioural equivalences
1 course
EIT Digital
System Validation: Automata and behavioural equivalences
View course
EIT Digital
Quantitative Model Checking
1 course
EIT Digital
Quantitative Model Checking
View course
Coursera
Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
Download on the App StoreGet it on Google Play
  • Coursera
  • About
  • Leadership
  • Careers
  • Catalog
  • Certificates
  • Degrees
  • For Business
  • For Government
  • Community
  • Partners
  • Mentors
  • Translators
  • Developers
  • Beta Testers
  • Connect
  • Blog
  • Facebook
  • LinkedIn
  • Twitter
  • Google+
  • Tech Blog
  • More
  • Terms
  • Privacy
  • Help
  • Accessibility
  • Press
  • Contact
  • Directory
  • Affiliates