Models for performance analysis of concurrent programs HT'10, 7.5p

Will run Tuesdays 13.15- 15.00 Starting October 26.

Objectives

The objective of this course is to gain insight, through the use of simple models, into the performance and dimensioning of computer systems, in particular concurrent multithreaded programs. To that aim, basic performance models are studied and used for the analysis and evaluation of programs, to understand the impact of resource sharing, conflicts, scheduling, tex. Differen modelling approaches are considered, such as Markov chains, queuing networks, stochastic Petri Nets, and simulation. Various solution methods (such as analytical, numerical and simulation) and approximations are used to evaluate these models and to understand the behaviour of the systems being investigated.

The course material is not completely fixed, but may adapted (even dynamically) to the interest and importance.

Contents

Major sequence of topics will be

Schedule

W DateTimePlaceWhat
43 Tue26/1013-151146Basic probability theory
44 Tue2/1113-151146stochastic processes, Markov chains slides
45 Tue9/1115-171146Markov Processes, Birth-death-processes, M/M/1 queues slides
46 Tue16/1115-171146general queues (M/G/1), Little's law, PASTA slides
47 Tue23/1113-151146, Queueing Networks, Jackson Networks, Closed Networks, Mean Value Analysisslides, Example (by Pan Xiaoyue)
48 Tue30/1113-151146Problem solving session
49 Tue7/1213-152344Stochastic Petri Nets slides (by Jonathan Linden) (see the paper M. Ajmone Marsan: Stochastic Petri Nets: an Elementary Introduction, which is referenced below)
50 Tue14/1213-15noCancelled (no meeting)
51 Tue21/1213-15noCancelled

Lectures

Here is more detail about what will be/has been covered in each lecture (each bullet should be approximately one lecture).

  1. Basic probability theory, including: Probability spaces, Conditional probability and independence, Random variables (discrete and continuous), pdf (probability mass/density function), cdf (cumulative distribution function), Conditional random variables, Independence of random variable, Expected Value, Variance, laws for addition and multiplication, SOME COMMON Distributions: Bernoulli Distribution, Binomial Distribution, Negative Binomial distribution, Geometric Distribution, Possion Distribution, Exponential Distribution.
    Material: I will use the structure of the first lecture from Hillston's course, extended with the slides of Virtamo (first 3 lectures), but skip the material on generating functions.
  2. Stochastic processes, Markov Chains, transient and stable properties of Markov chains, balance equations, birth-death-processes,

Exercises

Here are some random exercises, which you can do (or find others)

  1. Homework 1
  2. Homework 2
  3. Homework 3
  4. Homework 4
  5. Homework 5
  6. Homework 6 (on Stochastic Petri Nets)

Course Material

There are several different possible sources: Books include There are several on-line monographs, including There are several sequences of lectures on the net, including

Schedule

The course will start in Week 41 (11-15 october), and thereafter meet once a week (possibly not in Week 42, when Bengt is on travel).

Sign Up

To sign up, add your times of availability in the week in the following doodle after which we will find a suitable time slot for the course. Please note that the doodle (for concreteness) asks for the week of oct. 11-15, but you should consider it a representative week for the autumn.