Adaptive Computer Systems

Fall 1999 -- Vijay Karamcheti

General Information

Lectures: Tuesdays, 5:00pm-7:00pm,
101 CIWW
Office Hours: Mondays, 4:00pm-5:00pm and by appointment,
715 Broadway, Room 704
phone: (212) 998-3496
email: vijayk@cs.nyu.edu
Mailing List: To subscribe send email to majordomo@cs.nyu.edu.
In the body of the messge, simply write: subscribe g22_3033_003_fl99
To post to the mailing list, send email to g22_3033_003_fl99.


At least one graduate-level course each in Computer Architecture and Operating Systems.


Current-day computer systems exhibit increasing diversity in computing and networking environments ranging from powerful desktop processors connected with gigabit ethernet to relatively weak PDAs connected with ad hoc wireless networks. Such diversity is encountered even within a single computing node, with access costs for different levels of the storage hierarchy (cache, memory, disk) often differing by as much as six orders of magnitude. Despite these differences, there is a growing demand for applications that can interoperate across and sometimes even run on all of these platforms. This desire motivates a change in the traditionally inflexible structure of different system layers--hardware, operating systems, and applications. Guided by application requirements, the different system layers must now be able to "adapt" to the run-time environment, altering their functionality to improve overall performance.

This course will focus on the state-of-the-art of hardware and software approaches for adaptation (such as reconfigurability, extensible operating systems, etc.), as well as techniques for exploiting  application information to facilitate such adaptation. More emphasis will be given to software, user-level adaptation techniques.

The course is mainly targeted towards Ph.D. students with research interests in computer architecture, compilers, operating systems, and programming languages.

Course Structure

Researchers have started examining the various aspects of Adaptive Computer Systems only over the last few years. Consequently, readings for the course will be selected from a collection of recent research papers that address one or more of the issues surrounding this topic.

Instead of formal lectures, the course will emphasize an informal discussion format. Students will be expected to present a subset of the papers, participate in discussions, and submit writeups that summarize and critique these papers. The course grade will be primarily based upon these writeups and an extensive course project (which will be done in groups). There will be no exams.


09/07 Lecture 1 Introduction
Architectural Mechanisms
(Writeup 1 due 10/05/1999)
09/14 Lecture 2 Architectural Adaptation for Application-Specific Locality Optimizations,
Xingbin Zhang, Ali Dasdan, Martin Schulz, Rajesh Gupta, and Andrew Chien.
International Conference on Computer Design, 1997.
Presentation Slides (Hua Wang)
PipeRench: A Coprocessor for Streaming Multimedia Acceleration,
Seth Copen Goldstein, Herman Schmit, Matthew Moe, Mihai Budiu, Srihari Cadambi, R. Reed Taylor, Ronald Laufer.
International Symposium on Computer Architecture, 1999.
Presentation Slides (Ilya Lipkind)
09/21 Lecture 3 Impulse: Memory System Support for Scientific Applications,
John Carter, Wilson Hsieh, Leigh Stoller, Mark Swanson, Lixin Zhang.
To appear in a future issue of Scientific Programming, IOS Press.
Presentation Slides (Mauricio Plaza)
ISTORE: Introspective Storage for Data-Intensive Network Services,
Brown, A., D. Oppenheimer, K. Keeton, R. Thomas, J. Kubiatowicz, and D.A. Patterson
7th Workshop on Hot Topics in Operating Systems (HotOS-VII), 1999.
Presentation Slides (George Sikorjak)

A related paper that provides good technical background on Active Disks:
Active Disks: Programming Model, Algorithms, and Evaluation,
Anurag Acharya, Mustafa Uysal, and Joel Saltz
Eighth Internation Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-VIII), 1998.

09/28 Lecture 4 SPINE: An Operating System for Intelligent Network Adapters,
Marc E. Fiuczynski, Richard P. Martin, Brian N. Bershad, David E. Culler
Technical Report, University of Washington (UW TR-98-08-01).
Presentation Slides (Anca-Andreea Ivan)

A related paper that extends these ideas to internal network nodes:
Towards an Active Network Architecture,
David L. Tennenhouse and David J. Wetherall
Computer Communication Review, Vol. 26, No. 2, April 1996.

An Architecture for Differentiated Service,
S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, W. Weiss.
IETF Network Working Group, RFC 2475, December 1998.
Presentation Slides (Tao Zhao)
Operating System Mechanisms
(Writeup 2 due 10/19/1999)
10/05 Lecture 5 Continuous Profiling: Where Have All the Cycles Gone?
ennifer M. Anderson, Lance M. Berc, Jeffrey Dean, Sanjay Ghemawat, Monika R. Henzinger, Shun-Tak A. Leung, Richard L. Sites, Mark T. Vandevoorde, Carl A. Waldspurger, and William E. Weihl.
ACM Transactions on Computer Systems, Volume 15, Number 4, November 1997, pages 357-390.
Presentation Slides (Igor Pechtchanski)
The Performance of µ-Kernel-Based Systems
Hermann Härtig, Michael Hohmuth, Jochen Liedtke, Sebastian Schönberg, Jean Wolter
16th ACM Symposium on Operating Systems Principles (SOSP'97), 1997.
Presentation Slides (Xiaodong Fu)
10/12 Lecture 6 Extensibility, Safety and Performance in the SPIN Operating System
Brian Bershad, Stefan Savage, Przemyslaw Pardyak, Emin Gun Sirer, David Becker, Marc Fiuczynski, Craig Chambers, Susan Eggers
15th ACM Symposium on Operating System Principles (SOSP-15), 1995.
Presentation Slides (Anatoly Akkerman)
Application Performance and Flexibility on Exokernel Systems.
M. Frans Kaashoek, Dawson R. Engler, Gregory R. Ganger, Héctor M. Briceńo, Russell Hunt, David Mazičres, Thomas Pinckney, Robert Grimm, John Jannotti, and Kenneth Mackenzie.
16th ACM Symposium on Operating Systems Principles (SOSP'97), 1997.
Presentation Slides (Tatiana Kichkaylo)
Adaptation Frameworks
(Writeup 3 due 11/09/1999)
10/19 Lecture 7 An end-to-end QoS management architecture,
Mallikarjun Shankar, Miguel DeMiguel, and Jane W. S. Liu.
Real-Time Applications Symposium, June 1999.
Presentation Slides (Oleg Barshay)
Application Scheduling on the Information Power Grid,
Dmitrii Zagorodnov, Francine Berman, and Rich Wolski
submitted to International Journal of High-Performance Computing, 1998.
Presentation Slides (Niranjan Nilakantan)
10/26 Lecture 8 Exploiting Application Alternatives
Peter J. Keleher, Jeffrey K. Hollingsworth and Dejan Perkovic.
19th International Conference on Distributed Computing Systems, June 1999.
Presentation Slides (Aleksander Bukharovich)
Exploiting Application Tunability for Efficient, Predictable Parallel Resource Management,
F. Chang, V. Karamcheti, and Z. Kedem,
International Parallel Processing Symposium (IPPS/SPDP 1999), April 1999.
Presentation Slides (Fangzhe Chang)
11/02 Lecture 9 Darwin: Resource Management for Value-Added Customizable Network Service,
Prashant Chandra, Allan Fisher, Corey Kosak, T. S. Eugene Ng, Peter Steenkiste, Eduardo Takahashi, Hui Zhang
Sixth IEEE International Conference on Network Protocols (ICNP'98), 1998.
Presentation Slides (Vijay Karamcheti)
The MultiSpace: an Evolutionary Platform for Infrastructural Services,
Steven D. Gribble, Matt Welsh, Eric A. Brewer, and David Culler.
Usenix Annual Technical Conference, June 1999.
Presentation Slides (Mauricio Plaza)
Project: Design Meetings
11/09 Lecture 10 These design meetings should be used to discuss any design and/or implementation issues that might crop up while doing the project.
11/16 Lecture 11
11/23 Lecture 12
11/30 Lecture 13
12/07 Lecture 14 Project Presentations
Final report (no more than 20 pages) due December 21st, 1999.


The objective of the project (to be done in groups of 2-3 students) is to provide a concrete context for the research topics that we will discuss in the course. Each group will develop and implement an adaptation framework for applications running in a distributed environment with varying CPU and network load conditions. A good project will address several issues of adaptation: (1) specification of alternate behaviors, (2) run-time monitoring, (3) mechanisms for adaptation, and (4) adaptation policies.

The Application: A visualization application where a client process downloads images from a server. On the server side, images are uploaded from disk, processed as appropriate (e.g., compressed) and then sent to the client. The client process receives the data, processes as appropriate (e.g., decompresses it) and then displays it. Overall application performance is affected by client and server speeds, memory capacities, and disk, network, and display bandwidths.

The Platform: Two PCs running Windows NT, connected using the Myrinet network. The application components will execute in a virtual environment that can be used to control various application interactions with the underlying operating system (e.g., relative communication send/receive rates on different socket connections). Moreover, your adaptation techniques can take advantage of the Myrinet programmable network interface processor.

The Challenge: Design an adaptation strategy that delivers the best (with respect to other projects) performance over a range of system load scenarios.