Simulation and Performance Evaluation - aa 2016-17

Past academic year courses: bottom page

Welcome to the 2016-17 web site of Simulation and Performance Evaluation. This is the second year of the course and we have some major changes on the course management. We use Google Classroom for a more dynamic and agile on-line interaction and for the assignment of personal projects. This site remains the main entry point of the course, but it is a one-way communication channel, and its access is public, thus here you only find public information and official information.

Google Classroom works instead by invitation. You have to send me an e-mail (via your official @unitn.it account) and I will invite you to participate. In Classroom you will find the course material that is not available here, and also an on-line course I registered as rehearsal of Probability Theory ... useful for those who have never taken a good course on the subject or ... have forgotten it.

You can interact (with some parsimony, please!) both with the Classroom socials and sending me e-mails. You will generally be answered NBD. Please, use e-mails for personal communications only, and Classroom for topics (e.g., clarification requests) that are of general interest and may sparkle discussions also among you. Remember that he best place to take questions and answers remains the (physical) classroom.

The billboard below is used to convey messages and announcements also to those that cannot be in class, so please check it regularly, though "urgent" matters will be sent via Classroom mailing list.

Slides and other teaching material (including assignments) will be posted in Classroom in due time. Remember that:
1) Classroom does not substitute lessons;
2) Those not registered in Classroom will not be assigned the ... assignments, so they will not be able to take the exam.

Timetable

Monday 11-13, Room B104; Thursday 17-19, Room A205

Bill board

  • Nov. 17, Assignment 2: The assignment details are available and topologies are in Classroom.
  • Oct. 26, Final Assignment 1 Traces: The definitive traces for Assignment 1 are available on Classroom.
  • Oct. 24, Lesson Suspension: We suspend the lessons on Thursday Oct 27 so you can dedicate time to the first assignemnt; lessons will resume regularly on Thursday Nov 3.
  • Course Opening: The course starts Thursday Sept. 15, 17-19 room A221.

Program and Methodology

Please, refer to ESSE3 and the syllabus relative to Simulation and Performance Evaluation for the official course content.

This said, let's try to understand a bit better the course goals and the course content, which, up to some point, will also be twisted and tweked based on how we came to know each other during the first few lessons. As mentioned in the general page of the course site, Performance Evaluation (PE for short) is central to all systems design, and ICT systems are no exception. Event driven simulations of just Simulations to be brief, are one of the means to evaluate performance, but since very often the term "simulation" is used with different meanings, and since it is unfortunately widespread to think about simulations in bery different terms, we explicit it in the title that Simulation techniques and methodology are part of this course.

The main objective of the course is defining what PE means, what are the applications areas, and why it is (or should be) a centerpiece of any system design ... including computers, software, the Internet, and applications in general. Very often performance is just seen as speed ("how fast is your system"?), but it is not a great intellectual feat to understand that speed alone is not sufficient: even a racing car can be the fastest of the lot, but if it breaks down it does not win the race! So reliability is part of performance, availability too, and dependability even more, specially for mission-critical systems.

One of the major issues we will have to clarify is that performance is rarely (if ever) a simple number, but it has to be expressed in stochastic terms, and often as complex vectors of time-dependent variables, and this explain why the starting point of our course is some reasonable knowledge of Probability and Statistics (which in turn imply some reasonable knowledge of Analysis). And we give for granted that, as you all are graduate students of Computer Science, you are all much better than me in programming techniques and software engineering, so that the implementation of simple algorthms, drawting some graphs and manipulating matrices and programs outputs is not a problem.

We will try to make a logical path that starts from systems, simple or complex as they are, understand, given the system, what are the relevant metrics that define their perfromance, and what are the dependencies between different metrics and different subsystems. Once we have understood what are the metrics of interest and their relationships, we have to take a tough decision to evaluate performance: shall we measure them on the real system, simulate the system, or build an analytical model?

We will start from measures, or better, from the interpretation of measure points and from the design of a correct experimental setup do do the measures. We will use a simulator as if it were a real system, because this gives us more flexibility ... and makes experiments much, much cheaper!

Next we will introduce simulations, understand what they really are from a mathematical point of view, and learn the basics to design a simulator.

Finally we will make some examples of systems that are prone to an analytical modeling and how these models can be solved to yield results that are otherwise impossible to obtain.

Textbooks

We do not have an official textbook, because the course covers the enormously vast topic of Perfroamcne Evaluation with a "breadth first" approach, so that we would end up using chapters of many different books, and it is not worth buying them. However, I report here some selected books that for one reason or another are relevant for the course ... and try to explain why.

Book No. 1:
K.S. Trivedi,
"Probability and Statistics with Reliability, Queuing, and Computer Science Applications",
Wiley-Interscience; 2001
ISBN: 0-471-33341-7
can be bought on-line at Amazon or directly from the Wiley Web Site .
2-3 copies are available in the University Libraries;
The first five Chapters plus Chapter 10 of this book contain all the background in probability and statistics we need for the course. Indeed, I think there is much more than what you already know, but I do not have control on the courses you took at the Bachelor, thus I cannot be more precise. In conclusion: don't be too scared if some of the material looks new or if some details are beyond your knowledge, we'll rehearse these more advanced parts. If instead you have problems with Bayes rule, feel uncomfortable with percentiles and find difficult to compute the probability that an exponential RV with mean μ is larger than 2μ, then it is probably better to devote some time to study these Chapters.

Book No. 2:
R. Jain,
"The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling,"
Wiley- Interscience, 1991,
ISBN:0471503361
This book is very old, so I do not advise to buy it, but it is still the only one I'm aware of that tackles the entire range of Performance Analysis techniques in the context of Computer Science, thus it is a good reference for the subject as a whole, while taking examples are "real cases" is today a bit outdated.

Book No. 3:
G. Bolch, S. Greiner, H. de Meer, K.S. Trivedi,
"Queueing Networks and Markov Chains: Modeling and Performance Evaluation With Computer Science Applications",
Wiley-Interscience; 1998
ISBN: 0-471-19366-6
(can be bought on-line AT Amazon or directly from the Wiley Web Site).
This is a very good and advanced book on the use of Markov Chains and Queueing Networks for performance evaluation, but it is definitely not needed for our course, where analytical modeling will be at most 1/3 of the course: this book covers all what we do in just a few pages.

Exams

The exam is composed of the assignments we give you during the course through the Google Classroom platform, plus an oral discussion and colloquium. All assignments are individual, meaning that each of you have to deliver a report (often limited in length, to avoid that you write too much). There will be 3 assignments during the course, each of which should not take more than 8-10 hours to complete. Further details will be given later on.

The oral discussion can include exercises, clarifications on the assignements and reports and theoretical, open questions as well. The outcome is a blend of the quality of your reports and the oral discussion, with "more weight" on the assignments if the oral confirms the result; however, you cannot come with assignments perfectly done to the oral, and then be unable to even discuss what is their meaning, in this case the oral dominates, and you may even fail the exam.

All reports must be written in English and also the clarity of the language is part of the evaluation, while the oral can be taken both in English or in Italian as you prefer.

Michele Segata will help me with assignments and their evaluation.

Forthcoming Dates

  • January - February 2016

Refer to ESSE3 for the remaining burocracy.

Please remember to register for the exam before delivering your material and reserve for the oral discussion!

Teaching Material

The slides are provided to help taking notes. "Reading" the slides is definitely not enough to study the course. Additional material, if present, normally refers to somthing we discussed in class, but may have different notation or cover more than we actually did.

Here you only find the course presentation (slides and a short video) and introduction, the rest of the material is available in Google Classroom once you logged in.

Google Classroom works by invitation. You have to send me an e-mail (via your official @unitn.it account) and I will invite you to participate.

  • Course introduction: a short video, mainly for students coming from other Universities ... but not only.
  • Course presentation, rules, exams, and the program at large.
  • The systems we consider for performance evaluation, the need for a model, an example of possible systems with many facets, common concetual mistakes in PE, the three methodologies for PE: Measures, Simulations, Analysis.
  • Overview of Stochastic Processes. At this point we must be familiar (very familiar!) with probabilities. The key concepts we rely upon are presented in the five videos in Classroom. As stochatic processes are time functions of random variables, lack of understanding of probabilities or weaknesses in manipulating RVs, distributions, and key concepts as moments, means, mode value, median, percentiles may hamper further understanding.
  • Measures as outcomes of an SP: Population and Sample. Plotting data, finding model parameters through functions (moments) of the data, point estimates and bias, data correlation, confidence intervals and examples of distribution models.
  • Presentation of the first Exam Assignment.
  • Some basic notions on MLE and Regression; it is a very fast excursus to have the fundamental notion on when to use and when not to use MLE.
  • The art of modeling: how do we build a mathematical model starting from a system? How good is a model? Examples from different areas.
  • Foundation of discrete event simulations and DES design principles. You can find the simulator and R scripts used to present the queueing network simulator on Classroom.
  • A "primer" on trivial MAC protocols we'll use to understand DES programming.
  • Solving and Using Markov Chains: the theory that allows finding closed form solutions for the steady state distribution of MC (both DT and CT), and how to use this to predict performance.
  • Single station queueing systems: Solution of Makovian queues and beyond.
    • PDF Slides. New version with corrected typos and more derivation passages for some formulas.
  • Queueing Networks: Systems of Interconnected queues, form Jackson queues to the BCMP theorem

Assignments

The assignments are parte of the exam, indeed a large part of it. We have three different assignemnts, each requiring 10-20 hours of work ... provided you have already studied the relative theory! There are three assignemnts, one on measures, one on simulation, and one on modeling. Each one assignes up to 11 points, so that overall you can "collect" 33 points, that then you have to confirm with the oral discussion.

  • A template in LaTex explaining how to write a decent (if not good) report. You are free to use any word processor you like, but don't complain or blame it on us if the result is bad and/or the format requested difficult to achieve.
Assignments will be done through Google Classroom.

Google Classroom works by invitation. You have to send me an e-mail (via your official @unitn.it account) and I will invite you to participate.


Past Academic Years