Description:
Tools and techniques for PE, Analytical and Simulation models, evaluation of multiprocessors, multicomputer and LANs, scheduling policies, case studies.
Prerequisites:
- C++ programming
- Probability
- Mathematical proofs
Required materials:
- Performance Modeling and Design of Computer Systems: Queueing Theory in Action (available in the bookstore)
- Network Calculus: A Theory of Deterministic Queuing Systems for the Internet (available online)
- Computer able to run a linux VM, run native linux, or ssh to a cloud VM
- Mobile device (laptop/phone) with Canvas access for in-lecture quizzes
Learning objectives:
By the end of the course,
- students will be able to utilize multiple types of analysis techniques to study the performance of systems (e.g., Queueing theory, Markov chains, Network calculus)
- students will be able to implement discrete event simulation code and apply it to simulating queueing systems
- students will be able to select and justify appropriate performance metrics and analysis techniques
- students will be able to utilize analysis techniques to compare system designs and decide which design is better for solving a problem
Preliminaries (must be done first):
- Academic Integrity module
- Programming assignment setup
Homework assignments:
- HW1 (Review)
- HW2 (Operational laws)
- HW3 (Discrete time Markov chains)
- HW4 (Continuous time Markov chains)
- HW5 (Queueing theory)
- HW6 (Scheduling)
- HW7 (Network calculus)
Programming assignments:
- Lab1 (Simulation Part1 – discrete event simulator core)
- Lab2 (Simulation Part2 – task dispatch and queueing networks)
- Lab3 (Simulation Part3 – scheduling)
Grading:
- 30% Homework assignments: equally weighted with lowest 1 dropped
- 30% Programming assignments: equally weighted
- 10% In-class midterm
- 25% Comprehensive final exam
- 5% In-class mini quizzes (during most lectures): lowest 5 dropped
Late policy:
Each assignment can be submitted at most 1 day late with a 15% penalty. 1 day refers to 11:59PM the day after the assignment is due, which may be more than 24 hours. Assignments are generally due before class starts. All times in the course are in local PA time (Eastern Time).
Class participation will be determined by answering a question during each lecture via a Canvas Quiz: Correct answer (2), Incorrect answer (1), No response (0). There will not be any makeup/excused absences for class participation, and instead, the lowest 5 participation scores will be dropped.
| Category | Topic | References |
|---|---|---|
| Intro | Basics/definitions | Ch2 |
| Intro | C++ review | None |
| Intro | C++ review | None |
| Simulation | Simulator architecture and design | None |
| Intro | Probability review | Ch3.1-3.15 |
| Simulation | Generating random variables | Ch4.1-4.2 |
| Simulation | Time average vs. ensemble average | Ch5.3 |
| Operational laws | Open/Closed systems | Ch2.3-2.7 |
| Operational laws | Little’s law | Ch6.1-6.7 |
| Operational laws | Other operational laws | Ch6.8-6.10 |
| Operational laws | Modification analysis | Ch7.1-7.5 |
| Markov chains | Discrete time Markov chain definition and modeling | Ch8.1-8.3 |
| Markov chains | Discrete time Markov chain solving | Ch8.4-8.7 |
| Markov chains | Discrete time Markov chain solving | Ch8.8-8.10,Ch9.6-9.7 |
| Markov chains | Ergodicity | Ch9.1-9.4 |
| Markov chains | Exponential distribution | Ch11.1-11.4 |
| Markov chains | Poisson Process | Ch11.5-11.8 |
| Markov chains | Continuous time Markov chain modeling | Ch12.1 |
| Markov chains | Continuous time Markov chain solving, M/M/1 | Ch12.2-12.3,Ch14.1,Ch13.1-13.2 |
| Queueing theory | PASTA | Ch13.3 |
| Queueing theory | M/M/k | Ch14.3-14.4 |
| Review | Midterm review | None |
| In-class midterm | In-class midterm | None |
| Queueing theory | M/M/k/k, M/M/∞, capacity provisioning | Ch14.2,Ch15.2-15.3 |
| Queueing theory | M/G/1, renewal-reward theory, Heavy tails: Pareto, Bounded Pareto | Ch23.1-23.6,Ch20.3-20.5 |
| Scheduling | Task dispatch | Ch24.1-24.2 |
| Scheduling | Non-preemptive, non-size based algorithms | Ch29.1 |
| Scheduling | Preemptive, non-size based algorithms | Ch30.1-30.2 |
| Scheduling | Preemptive, non-size based algorithms | Ch30.3 |
| Scheduling | Non-preemptive, size based algorithms | Ch31.1-31.4 |
| Scheduling | Preemptive, size based algorithms | Ch32.2-32.3 |
| Scheduling | Shortest remaining processing time first (SRPT) algorithm | Ch33.1-33.3 |
| Network calculus | Deterministic Network Calculus: arrival curves and rate limiters/shapers | DNC Ch1.1-1.2 |
| Network calculus | Deterministic Network Calculus: service curves and latency/buffer bounds | DNC Ch1.3-1.4 |
| Network calculus | Deterministic Network Calculus: network analysis | DNC Ch1.4 |
| Network calculus | Deterministic Network Calculus: effective bandwidth/equivalent capacity | DNC Ch1.8 |
| Review | Review | None |
Academic Integrity Statement:
In this course, all work (e.g., homework assignments, programming assignments, quizzes, exams, etc.) is to be done individually and independently. No outside help of any form is permitted. You are also responsible for securing your work so that you do not intentionally or unintentionally assist any other student in violating the academic integrity policy.
For example, the following are strictly forbidden:
- Looking online for proofs or solutions to problems
- Looking online for hints on how to solve an assignment
- Using any proof, solution, hints, or code from any online source
- Using any Artificial Intelligence tool (e.g., ChatGPT) for assignments
- Getting hints or any assistance from another student on how to solve an assignment
- Providing hints or any assistance to another student on how to solve an assignment
- Looking at another student’s code or work
- Debugging another student’s code
- Posting any course-related material to any online public location (e.g., public github repository, online forums, etc.)
- Using any other student’s account or allowing anyone else to use your account
- Assisting anyone in violating any academic integrity policy either intentionally or unintentionally (e.g., from not securing your work)
- Getting any help from any source other than the instructor
The above list is non-exhaustive, and it is your responsibility to ensure that you A) complete all the coursework individually and independently without any outside help of any form, and B) secure your work so that you do not intentionally or unintentionally assist any other student in violating the academic integrity policy.
Additionally, this course follows all the standards in the CSE Department’s Academic Integrity Policy, which includes using tools to identify similarities with submitted code and other code from online sources and any submission, prior or present.
Completing the department’s Academic Integrity module is required for the course.
Failure to comply by the academic integrity policy will result in a 0 for the assignment plus a 10% overall course grade reduction. Additional sanctions (e.g., F for course) may apply depending on the severity and for repeat offenders. Providing false or misleading information or failure to provide relevant information when addressing academic integrity could increase the severity of the offense — honesty is an important aspect of academic integrity.
Academic integrity is the pursuit of scholarly activity in an open, honest and responsible manner. Academic integrity is a basic guiding principle for all academic activity at The Pennsylvania State University, and all members of the University community are expected to act in accordance with this principle. Consistent with this expectation, the University’s Code of Conduct states that all students should act with personal integrity, respect other students’ dignity, rights and property, and help create and maintain an environment in which all can succeed through the fruits of their efforts.
Academic integrity includes a commitment by all members of the University community not to engage in or tolerate acts of falsification, misrepresentation or deception. Such acts of dishonesty violate the fundamental ethical principles of the University community and compromise the worth of work completed by others.
Lecture Recording Statement:
Video and audio recordings of class lectures will be part of the classroom activity. The video and audio recording is used for educational use/purposes and only may be made available to all students presently enrolled in the class. For purposes where the recordings will be used in future class session/lectures, any type of identifying information will be adequately removed.
Recordings can be found in the Media Gallery tab after processing is completed.
Disability Accommodation Statement:
Penn State welcomes students with disabilities into the University’s educational programs. Every Penn State campus has an office for students with disabilities. The Student Disability Resources website provides contact information for every Penn State campus. For further information, please visit the Student Disability Resources website.
In order to receive consideration for reasonable accommodations, you must contact the appropriate disability services office at the campus where you are officially enrolled, participate in an intake interview, and provide documentation. If the documentation supports your request for reasonable accommodations, your campus’s disability services office will provide you with an accommodation letter. Please share this letter with your instructors and discuss the accommodations with them as early in your courses as possible. You must follow this process for every semester that you request accommodations.
Counseling and Psychological Services (CAPS) Statement:
Many students at Penn State face personal challenges or have psychological needs that may interfere with their academic progress, social development, or emotional wellbeing. The university offers a variety of confidential services to help you through difficult times, including individual and group counseling, crisis intervention, consultations, online chats, and mental health screenings. These services are provided by staff who welcome all students and embrace a philosophy respectful of clients’ cultural and religious backgrounds, and sensitive to differences in race, ability, gender identity and sexual orientation.
Counseling and Psychological Services at University Park (CAPS) (http://studentaffairs.psu.edu/counseling/): 814-863-0395
Counseling and Psychological Services at Commonwealth Campuses (https://senate.psu.edu/faculty/counseling-services-at-commonwealth-campuses/)
Penn State Crisis Line (24 hours/7 days/week): 877-229-6400
Crisis Text Line (24 hours/7 days/week): Text LIONS to 741741
Education Equity and Reporting Bias:
Penn State takes great pride to foster a diverse and inclusive environment for students, faculty, and staff. Acts of intolerance, discrimination, or harassment due to age, ancestry, color, disability, gender, gender identity, national origin, race, religious belief, sexual orientation, or veteran status are not tolerated and can be reported through Educational Equity via the Report Bias webpage (http://equity.psu.edu/reportbias/).