Lectures:
  Thursday, 14:00, S10 (Petr Tůma)
Labs:
  Thursday, 9:00, SU2 (even weeks) (Vojtěch Horký)
Information in SIS: NSWI131
Term: Credit and exam

About

Are efficient algorithms enough for writing fast code ? And if not, what else ?

The speed of a program is as important as its function. However, unlike function, speed is the result of often surprising interactions across the entire system stack. This course helps understand what influences program speed and the speed should be measured, evaluated and presented. Apart from general guidelines, the course will visit many system details relevant to performance and introduce tools that help in software performance evaluation.

Why Take the Course

The goal is to provide an overview of methods used for performance evaluation of software. We will focus on experimental methods.

The course can teach you:

You can find another benefit of the course in research, where it is required to verify properties of proposed solutions. Various performance experiments are essential for such verification. This course will teach you how to do that and you can use the knowledge in your Master thesis, for example.

Your MFF studies provided you with good basics in mathematics and statistics. You are also well-versed in computer system internals (architecture, operating system, etc). For computer systems performance evaluatation, both fields are necessary. This course will help you take advantage of your previous knowledge.

The course covers one part of the Master State Exams requirements - topic 2 (Embedded and Realtime Systems) of the plan Dependeble Systems for Software Systems, in particular “metrics of computer system performance and their statistical evaluation (metriky výkonnosti počitačových systémů a jejich statistické vyhodnocování)“. It also extends the information on requirements “simulation and modelling of performance (simulace a modelování výkonnosti)” and “QPN (Queuing Petri Nets)“, but these are covered by different courses in more detail.

Prerequisites

There are no formal prerequisites. However, you should be familiar with basics of probability and statistics, the knowledge of operating systems, computer architecture and compiler principles is also advantageous. If you have passed the Operating Systems (NSWI004) and Methods of Mathematical Statistics (NMAI061), you are fine. If you have missed those courses, you should be at least a little interested in more system aspects of computers and programs and be willing to study the statistical methods we use along with the R system.

The course aims at Master program students, but the students of Bachelor program are also welcome. If you like the topic, you will be probably fine.

Labs

In the labs you will exercise the knowledge from lectures in a practical manner.

To get the credit (zápočet) you need to finish tasks given during the labs.

Date Title Downloads
March 14th Agenda, timers Materials
March 28th Hardware counters Materials
April 11th Big benchmarks Materials
April 25th Instrumentation (Pin, DiSL) Pin DocPin OS-APIDiSL APIMaterials
On lab blade, use Java from /usr/lib/jvm/java-8-openjdk/
May 9th Statistics Materials
May 23rd Complete performance experiment TBBconcurrent_unordered_mapCollectionsHashMapMaterials

Grading

The exam will have two parts: practical and theoretical. In the practical one, you will be required to design and execute a performance evaluation experiment similar (but more complex) to one from the last lab assignment. You will be able to choose from several languages (at least C and Java will be available) and a framework or library to collect the data. During the exam you will explain your experiment and results.

The theoretical part will be testing your understanding and ability to use various methods and systems presented in the lectures.

Preliminary Syllabus

This is a preliminary syllabus of the course. Minor changes are possible. From the following list, each point will be usually covered in a single lecture:

  1. General information. Goals and means we can use for performance evaluation.
  2. What to measure. Metrics.
  3. How to measure I - Theory. Clock, profiling, tracing, events.
  4. How to measure II - Practical 1. Timers, Counters.
  5. How to measure III - Practical 2. Instrumentation. Frameworks overview.
  6. How to process data I - Statistical tools. Means, distributions, …
  7. How to process data II - Alternatives, confidence intervals, tests, ANOVA
  8. Graphical presentations - How to do good plots.
  9. What is going on? Data analysis, reading plots.
  10. Simulation. Modeling.

Literature

The slides presented in the lectures will be available here. You can also use many online resources, we will provide links in the lectures.

Most topics are covered to the detail in these great books: