Analytical Performance Modeling & Design of Computer Systems Course ID 15857 Description In designing computer systems one is usually constrained by certain performance requirements and limitations. For example, one might need to guarantee a response time SLA or certain throughput requirement, while at the same time staying within a power budget or cost budget. On the other hand, one often has many choices: One fast disk, or two slow ones? More memory, or a faster processor? A fair scheduler or one that minimizes mean response time? For multi-server systems, one can choose from a wide array of load balancing policies, a wide array of migration policies, capacity provisioning schemes, power management policies ... The possibilities are endless. The best choices are often counter-intuitive. Ideally, one would like to have answers to these questions before investing the time and money to build a system. This class will introduce students to analytic stochastic modeling with the aim of answering the above questions. Key Topics Operational Laws: Little's Law, response-time law, asymptotic bounds, modification analysis, performance metrics. Markov Chain Theory: discrete-time Markov chains, continuous-time Markov chains, renewal theory, time-reversibility. Poisson Process: memorylessness, Bernoulli splitting, uniformity, PASTA. Queueing Theory: open systems, closed systems, M/M/1, M/M/k, M/M/k/k, M/G/1 full analysis, M/G/k, G/G/1, transform analysis (Laplace and z-transforms). Simulations: time averages versus ensemble averages, generating random variables for simulation, Inspection Paradox. Modeling Empirical Workloads: heavy-tailed property, Pareto distributions, heavy-tailed distributions, understanding variability and tail behavior. Management of Server Farms: capacity provisioning, dynamic power management, routing policies. Analysis of Scheduling: FCFS, non-preemptive priorities, preemptive priorities, PS, LCFS, FB, SJF, PSJF, SRPT, plus the latest scheduling research: SOAP. Applications to Today's Datacenters: Scheduling for multiserver system, resource allocation for multi-dimensional jobs, c-mu rule for maximizing value, parallel jobs with different speedup functions. Required Background Knowledge We assume a reasonable background in probability, such as that covered in an Undergraduate Probability class. Specifically, we assume a knowledge of continuous and discrete distributions, conditional probability, conditional expectation, and higher moments. Chapter 3 of our textbook summarizes most of the assumed material. Alternatively, you can get a much better feel for the assumed material by reading Chapters 1 through 9 of the Undergraduate PnC Probability Book: "Introduction to Probability for Compuing" textbook that was mailed to you. We also expect you to know basic calculus and nested integrals (3D integration). There is an assessment provided on the first day of class to make it clear to you if you have the prerequisites with respect to undergraduate probability and calculus. Course Relevance CSD star (*) course (fullfills curriculum breadth requirement). Appropriate for doctoral, master's and advanced undergraduate. Please note prereq knowledge to be successful in the course. Course Goals The techniques studied in this class are useful to students in Computer Science, ECE, Mathematics, ACO, Tepper, Statistics, MLD, and Engineering. This course is packed with open problems -- problems which if solved are not just interesting theoretically, but which have huge applicability to the design of computer systems today. Learning Resources We will closely follow the textbook: Performance Modeling and Design of Computer Systems: https://www.cs.cmu.edu/~harchol/PerformanceModeling/book.html Assessment Structure Weekly Homeworks -- worth 40% total. (We drop the lowest homework score) Midterm 1 -- 25% (somewhere after Chpt 14) Midterm 2 -- 25% (near the very end -- instead of a "final exam") ONE mandatory grading meeting during semester -- 5%. Will take place Friday or Saturday. Includes free dinner! Participation -- 5%. Standard grading scale: 90%- 100% is A; 80% - 89% is B; 70%- 79% is C; and so on, typically with curve at end. Note the large emphasis on homework. Homeworks are due Friday at the start of recitation and are graded over the weekend. It is your responsibility to get the homework to the TAs on time! If you cannot be in recitation, then email the homework to the TAs by the start of recitation. Any further issues should be handled through the TAs. Keep in mind that your TAs are busy. Your TAs will not grade your homework if they don't have it by the time they start grading. Course Link http://www.cs.cmu.edu/~harchol/Perfclass/class23fall.html
