67812 – Seminar on Computer Systems and Performance Evaluation

67812 – Spring 2010
Seminar on Computer Systems and Performance Evaluation

Instructor:Prof. Dror Feitelson
Time and place:Wednesdays 4:15-5:45, Ross 201

In the first part of the semester, we'll cover a number of classic papers. Everyone has to read these papers, write a short report, and we'll discuss them in class.

During the remaining weeks, we'll review a selection of recent research papers. A list is given below, but you are also allowed to initiate your own. Each student is expected to make a detailed presentation of a chosen topic during a 90-minute session. This is typically based on one or two main papers, possibly with some additional background material as well. You are also encouraged to form groups that work together to present several related papers for an in-depth coverage of the topic.

Contact me if you have trouble downloading the papers.

Part I: Classics

Read these papers in advance. At the beginning of class, submit your report. This is strictly limited to one page maximum, and can also be much shorter than a full page.

The report should include the following:

Note that some of these papers are rather long. Part of your task is to figure out what are the core ideas and what are details that can be skimmed or even skipped because they are only of interest to someone who is doing closely related research. If you have spent many hours reading a paper and are still nowhere near the end then stop!

3/3/10 B.P. Miller, L. Fredriksen, and B. So, “An empirical study of the reliability of UNIX utilities”. Comm. ACM 33(12), pp. 32-44, Dec 1990.
Somewhat related read:
A. Bessey et al., “A few billion lines of code later: using static analysis to find bugs in the real world”. Comm. ACM 53(2), pp. 66-75, Feb 2010.
10/3/10 Mor Harchol-Balter and Allen B. Downey, “Exploiting process lifetime distributions for dynamic load balancing”. In SIGMETRICS Conf. Measurement & Modeling of Comput. Syst., pp. 13-24, May 1996.
Presentation about structure of papers and writing abstracts
17/3/10 William J. Dally and Charles L. Seitz, “Deadlock-free message routing in multiprocessor interconnection networks”. IEEE Trans. Comput. C-36(5) pp. 547-553, May 1987.
24/3/10 Mohit Aron and Peter Druschel “Soft timers: efficient microsecond software timer support for network processing”. ACM Trans. Comput. Syst. 18(3) pp. 197-228, Aug 2000.

Part II: Current Topics

Chose your topic during the initial week of the semester and get my approval. Read the papers and start working on the presentation at least two weeks in advance; feel free to come over and discuss it if you need any advice. Submit a report like those we did above one week in advance of your talk, listing all the papers you used. Show or send me the presentation 3 days in advance.
21 Apr 2010
Elliot

File System Workloads

Nitin Agrawal, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau, “Generating Realistic Impressions for File-System Benchmarking”. 7th USENIX Conf. File and Storage Technologies, Jan 2009.

Eric Anderson, “Capture, Conversion, and Analysis of an Intense NFS Workload”. 7th USENIX Conf. File and Storage Technologies, Jan 2009.

Avishay Traeger, Erez Zadok, Nikolai Joukov, and Charles P. Wright, “A Nine Year Study of File System and Storage Benchmarking”. ACM Trans. Storage 4(2), pp. 5:1--5:56, May 2008.

28 Apr 2010
Netanell

Control Theory and Performance

Cheng-Zhong Xu, Bojin Liu, and Jianbin Wei, “Model Predictive Feedback Control for QoS Assurance in Webservers”. Computer 41(3), pp. 66-72, Mar 2008.

Joseph L. Hellerstein, Vance Morrison, and Eric Eilebrecht, “Applying Control Theory in the Real World: Experience with Building a Controller for the .NET Thread Pool”. In 2nd HotMetrics, Jun 2009.

5 May 2010
David

Timing and Timers

Simon Peter, Andrew Baumann, Timothy Roscoe, Paul Barham, Rebecca Isaacs, “30 seconds is not enough!: a study of operating system timer usage”. In 3rd EuroSys, pp. 205--218, Apr 2008.

George Varghese and Anthony Lauck, “Hashed and hierarchical timing wheels: efficient data structures for implementing a timer facility”. IEEE/ACM Trans. Networking 5(6), pp. 824--834, Dec 1997.

2 Jun 2010
Tamar

Monitoring, Testing, and Debugging

Sapan Bhatia, Abhishek Kumar, Marc E. Fiuczynski, and Larry Peterson, “Lightweight, High-Resolution Monitoring for Troubleshooting Production Systems”. In 8th USENIX Symp. Operating Systems Design and Implementation, Dec 2008.

Cristian Cadar, Daniel Dunbar, and Dawson Engler, “KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs”. In 8th USENIX Symp. Operating Systems Design and Implementation, Dec 2008.

T.Y. Chen, F.-C. Kuo, R.G. Merkel, and T.H. Tse, “Adaptive random testing: The ART of test case diversity”. J. Syst. Soft. 83(1) pp. 60-66, Jan 2010.

9 Jun 2010
Amnon

Virtualization Performance Impact

Omesh Tickoo, Ravishankar Iyer, Ramesh Illikkal, and Don Newell, “Modeling Virtual Machine Performance: Challenges and Approaches”. In 2nd HotMetrics, Jun 2009.

Keith Adams and Ole Agesen, A comparison of software and hardware techniques for x86 virtualization. In 12th Intl. Conf. Architectural Support for Programming Languages and Operating Systems, pp. 2-13, Oct 2006.

Bryan Clark at al., “Xen and the art of repeated research”. In USENIX 2004 Annual Technical Conf., FREENIX Track, pp. 135-144, Jun 2004.
background reading:
Paul Barham et al., Xen and the art of virtualization. In 19th Symp. Operating Systems Principles, pp. 164-177, Oct 2003.

16 Jun 2010
Oron

Scheduling and Fairness

A. Mancina, G. Lipari, J. N. Herder, B. Gras, and A. S. Tanenbaum, “Enhancing a dependable multiserver operating system with temporal protection via resource reservations”. In 16th Intl. Conf. Real-Time and Network Syst., Oct 2008.

C. S. Wong, I. Tan, R. Deena, and F. Wey, “Towards achieving fairness in the Linux scheduler”. Operating Systems Review 42(5), pp. 34-43, Jul 2008.

Lisa A. Torrey, Joyce Coleman, and Barton P. Miller, “A Comparison of Interactivity in the Linux 2.6 Scheduler and an MLFQ Scheduler”. Software—Practice & Experience 37(4), pp. 347-364, Apr 2007.

Matei Zaharia, Andy Konwinski, Anthony D. Joseph, Randy Katz, and Ion Stoica, “Improving MapReduce Performance in Heterogeneous Environments”. In 8th USENIX Symp. Operating Systems Design and Implementation, Dec 2008.

Y. Etsion, T. Ben-Nun, and D. G. Feitelson, “A global scheduling framework for virtualization environments”. In 5th Intl. Workshop System Management Techniques, Processes, and Services, May 2009.
and
T. Ben-Nun, Y. Etsion, and D. G. Feitelson, “Design and Implementation of a Generic Resource Sharing Virtual Time Dispatcher”. Technical Report, Oct 2009.

16 Jun 2010
Avnit

The New Parallel: Multicore and MapReduce

Guanying Wang, Ali R. Butt, Prashant Pandey, and Karan Gupta, “A simulation approach to evaluating design decisions in MapReduce setups”. In 17th Conf. Modeling, Analysis, & Simulation of Comput. & Telecomm. Syst., Oct 2009.
background reading:
Jeffrey Dean and Sanjay Ghemawat, “MapReduce: simplified data processing on large clusters”. Comm. ACM 51(1), pp. 107-113, 2008.

Silas Boyd-Wickizer, Haibo Chen, Rong Chen, Yandong Mao, Frans Kaashoek, Robert Morris, Aleksey Pesterev, Lex Stein, Ming Wu, Yuehua Dai, Yang Zhang, and Zheng Zhang, “Corey: An Operating System for Many Cores”. In 8th USENIX Symp. Operating Systems Design and Implementation, Dec 2008.