BILKENT
UNIVERSITY
CS 511 Introduction to Performance Modelling, Fall '96
(8:40-10:30 M, 10:40-11:30 Th, EA-502)
Dr. Tugrul Dayar
Department of Computer Engineering and Information Science (521 Engineering
Building)
e-mail: tugrul@bilkent.edu.tr
Office Hours: 15:40-16:30 T, 13:40-14:30 Th (or if this is not possible,
by appointment from 1981) Course Description: Introduction to modelling, review of probability theory, transforms
in probability theory, programming simulations, analyzing simulation results,
stochastic processes and Markov chains, discrete vs continuous time MCs,
state classification, numerical solution techniques (direct, iterative)
Little's result, M/M/1, M/M/infinity, M/M/1/L/M queues, non-birth-death
systems (M/E_{r}/1), non-Markovian systems (M/G/1), routing chain, M =>
M property, local balance, solving open networks, solving closed networks,
convolution, mean value analysis, stochastic automata networks, case studies.
Prerequisites: See me.
References:
Gelenbe, E. and Mitrani, I., Analysis and Synthesis of Computer
Systems,
Academic Press, New York, 1980. QA76.9.E94G281 1980
Gelenbe, E. and Pujolle, G., Introduction to Queueing Networks,
Wiley, New York, 1987. T57.9.G4513 1987
Jain, R., The Art of Computer Systems Performance Analysis: Techniques
for Experimental Design, Measurement, Simulation, and Modeling ,
Wiley, New York, 1991. QA76.9.E94J32 1991
King, P. J. B., Computer and Communication Systems Performance Modelling,
Prentice-Hall, New York, 1990. QA76.9.E94K56 1990
Kleinrock, L., Queueing Systems Vols. I and II,
Wiley, New York, 1975. T57.9K6 1975
Lavenberg, S. S., Ed., Computer Performance Modeling Handbook,
Academic Press, New York, 1983. QA76.9.E94C66 1983
Lazowska, E. D., Zahorjan, D., Graham, G. S., and Sevcik, K. C., Quantitative
System Performance: Computer System Analysis Using Queueing Network Models,
Prentice-Hall, Englewood Cliffs, N.J., 1984. QA76.9.E94Q36 1984
Mitrani, I., Modelling of Computer and Communication Systems,
Cambridge University Press, New York, 1987. QA76.9.C65M56 1987
Molloy, M. K., Fundamentals of Performance Modeling,
Macmillan, New York, 1989.
Sahner, R., Trivedi, K. S., and Puliafito, A., Performance and Reliability
Analysis of Computer Systems: An Example-Based Approach Using the SHARPE
Software Package, Kluwer, Boston, 1996. QA76.9.E94S23 1996
Stewart, W. J., Introduction to the Numerical Solution of Markov
Chains,
Princeton University Press, Princeton, N.J., 1994. QA274.7.S74 1994
Course Outline:
Overview of probability theory (Ch.2 in [9])
Transform theory (Ch.3 in [9])
Simulation (Ch.4 in [9])
Markov models, numerical solution techniques (Ch. 5 in [9]; Chs. 1-3
in [11])
Single queues (Ch.6 in [9])
Network of queues (Ch. 7 in [9])
Stochastic Automata Networks (Ch. 9 in [11])
Case studies (Ch. 8 in [9]; [3])
Note: In order to use matlab, which is available in the bcc domain,
please check the CS 471 course home page.
Also there is a wealth of software at netlib (especially the directory random may be of interest).
Grading:
Homework (20%)
Homework 1 (due 17/10/96): Solutions 1.
Homework 2 (due 4/11/96): Solutions 2.
Homework 3 (due 21/11/96): Solutions 3
Homework 4 (due 16/12/96): Solutions 4.
Midterm (25%, November 25, 9:00-10:30, EA502).
Project(s) (25%)
Project 1 (due 28/11/96) (You may want to check this paper in the US.)
Project 2 (due 10/1/97 by 5:30 pm, DON'T ASK FOR ANOTHER EXTENSION!!!)
A list of papers to read:
The Numerical Solution of Stochastic Automata Networks. European Journal
of Operational Research. Volume 86, Number 3, pp. 503 -- 525, 1995.
(W. J. Stewart, K. Atif, B. Plateau)
gzipped postscript.
Efficient Descriptor-Vector Multiplication in Stochastic Automata
Networks. (P. Fernandes, B. Plateau, W. J. Stewart) to be published,
gzipped postscript.
Numerical Issues for Stochastic Automata Networks.
(P. Fernandes, B. Plateau, and W. J. Stewart) to be published,
gzipped postscript.
Stochastic Automata Networks. (B. Plateau, W. J. Stewart) to be published,
gzipped postscript.