This handout gives a brief overview of the research projects going on in the systems group at Rice, and then goes on to suggest some possible Comp 520 projects. I suggest you read this document, think about some of the research projects, think about possible Comp 520 projects, and start talking to other people about shared interests. You are not restricted to the suggested topics, but, of course, more help will be available if you choose a topic of local interest. I would also encourage you to see the suggested topics as beginnings of ideas, not as finalized ideas. You should try to develop your own topic to the extent possible.
Given the size of the class, projects should be done in groups of at least 2 and preferably 3 students. A title for your project and the composition of the group is due by September 18. Your project proposal is due by September 25.
TreadMarks: Shared Memory on Networks of Workstations
Treadmarks supports parallel computing on networks of workstations. Its main novel feature is that it provides a global shared address space across the different machines on a cluster. The shared address space distinguishes it from other well-known packages such as MPI that provide a message passing interface between machines. There is growing consensus in the parallel computing community that a shared memory interface is more desirable from the application programmer's viewpoint, allowing him or her to focus on algorithmic development rather than on managing communication. The challenge in providing a shared memory interface is to do so efficiently. To this end, TreadMarks incorporates several innovative features, including release consistency and multiple-writer protocols.
The most successful application of TreadMarks occurred at the NIH, where it was used to parallelize FASTLINK, a software package to support disease gene location. The resulting parallel version was instrumental in the widely-reported discovery of the gene responsible for Parkinson's disease. Other applications using TreadMarks include work on constructing evolutionary trees at the Pasteur Institute, Paris, France, and the work on mixed integer programming (MIP).
Current research going on in the TreadMarks project includes the integration of compiler and runtime techniques, the use of multithreading, in particular on multiprocessor nodes, support for scalability, and support for modern languages like Java. TreadMarks runs on IBM, DEC, SUN, HP, x86 (running FreeBSD, Linux, or Windows NT) and SGI hardware.
OpenMP on NOWs: A Standard for Shared Memory NOW Computing
The OpenMP Application Programming Interface (API) is an emerging standard for parallel programming on shared-memory multiprocessors. It defines a set of program directives and a library for run-time support that augment standard C, C++ and Fortran. In contrast to MPI, a message-passing API, OpenMP facilitates an incremental approach to the parallelization of sequential programs: the programmer can add a parallelization directive to one loop or subroutine of the program at a time. Unlike POSIX threads, OpenMP specifically addresses the needs of scientific programming, such as support for Fortran and data parallelism. An earlier proposal for a standard, shared-memory API for scientific programming, ANSI X3H5, was never formally adopted, leading vendors to create their own similar but subtlely different programming models. OpenMP consolidates these different models into a single syntax and semantics, and finally delivers the long-awaited promise of single-source portability for shared-memory parallelism. Early experience with applications using OpenMP has been encouraging. Together, all these attributes have created great demand for OpenMP among users and rapid deployment of it by vendors.
At the same time, driven by economics, parallel computing is moving from special-purpose to commodity hardware, so called ``networks of workstations''. One problem has prevented the use of OpenMP implementations on these systems: the networks connecting the workstations only support message passing, but existing OpenMP implementations require shared memory. This has put OpenMP at a disadvantage in terms of portability to MPI, which is available on all platforms. Our objective is to develop a portable, robust, high-performance implementation of the OpenMP API for a network of shared-memory multiprocessors. This system will enable a programmer to rely on a single, standard, shared-memory API for parallelization both within a multiprocessor and between multiprocessors. Currently, the only standard APIs with implementations supporting parallelization at both levels are message-passing standards. Consequently, a programmer must either forego the use of shared memory within each multiprocessor or use two distinct APIs, one for each form of parallelization. We have demonstrated satisfactory performance on a number of benchmarks, including the Sweep3D benchmark from the DOE ASCI program. Our implementation uses the TreadMarks software distributed shared-memory system to provide an efficient emulation of shared memory on a network of workstations.
ScalaServer: Servers for a Scalable Information Infrastructure
The ScalaServer project focuses on operating systems and middleware support for constructing high-performance, highly available, and scalable cluster based Web servers.
Traditional operating systems were designed with a focus on computation as the main task of the computer. Today, communication is in many applications the dominant and most performance critical task. Many operating system facilities, however, have not kept pace with this change in the nature of the applications. Among the novel operating systems facilities we have developed are the IO-Lite unified buffering and caching system, which eliminates redundant copying and multiple buffering of I/O data; resource containers, a new abstraction that enables accurate resource accounting, fine-grained scheduling and differentiated quality-of-service in server applications; and, a new API for scalable event handling. Cluster level innovations include new mechanisms for scalable request distribution and new policies for distributing requests to cluster nodes that improve locality while maintaining load balance. Finally, our Flash Web server uses a novel multi-process structure that achieves superior performance both on in-memory and disk-bound workloads.
In addition to scalability, availability, and performance, Web services increasingly demand effective resource management in the server in order to provide differentiated and predictable levels of service to clients. In its simplest form, sites may want to prioritize requests, for instance, depending on whether they originate from within or from outside the organization. Beyond giving different priorities to different requests, sites may want to guarantee an upper bound on response time to paying clients, while providing best efforts to others. Finally, Web servers that host multiple Web sites or services often need to set appropriate resource limits (in terms of CPU, memory, disk, and network bandwidth) for each site and/or service. To enable the enforcement of such policies, we are developing a cluster wide resource management scheme that controls multiple resources (CPU, memory, disk and network bandwidth) in an integrated fashion.
Another current focus of interest in the ScalaServer project is how to build geographically distributed services.
EDT: Engineering Design Tutor
The goal of the Engineering Design Tutor (EDT) project is to move much of the rote training in engineering design courses out of the classroom and on to computers. By doing so, we hope to free up class time for creative design, and allow self-paced instruction and distance education.
Developing a student's intuition for a particular aspect of engineering design requires exposing the student to numerous sample problems. Instructors in engineering design courses spend a vast amount of class time trying to develop this intuition by working through selected problem instances in class.
In the Web-based Engineering Design Tutor (EDT), all student interactions with the design problem sets will be electronic via computer. Students using a World Wide Web (WWW) browser will be able to access the problem sets and the associated software residing on an Internet-based server. By adopting standard Internet technology, the Tutor can be used at other institutions or to support distance learning. In addition, an Internet-based tutor provides 24-hour access from a large variety of locations that support Internet access. This flexibility allows the students to explore design problems at their own pace.
The EDT will direct the student through the design problems and monitor his or her performance. In its current initial development phase, the server offers a number of fixed problem instances. It monitors the student's ability to follow the correct design procedure, checks for errors committed, and redirects the student after an error. In a second phase, we will log the students' interactions with the server, providing the instructor with feedback about the students' performance. Finally, in a third phase, we will dynamically generate new problem sets, according to the success or failure of the individual student in solving earlier problems.
Puppeteer: Adaptation in Mobile Environments
A mobile computing platform must be able to gracefully adapt to the network resource changes that are inherent in mobile computing. Future wireless networks will provide high bandwidth while indoors and lower bandwidth outdoors. Our goal is to add network-adaptivity to existing applications without modifying them. Some previous systems have required applications to be modified while others have changed the system beneath the applications. However, both approaches have limited the effectiveness of the network adaptivity. Either a small number of applications can be supported well, or a large number of applications can be supported poorly.
Modern applications, from popular tools like Microsoft's Office 2000 to open source efforts including KDE's KOffice, are built using components. A component might be a bar chart or a bitmap image inserted in a spreadsheet document, or a paragraph within a word processing document. These components have standardized interfaces for manipulating them while they are running and they have well-defined and structured data representations whether they are stored in memory or on disk.
Puppeteer takes advantage of this component structure. Without modifying an application, we will break down a document to its internal components on the server, transmit those components independently across the network to the mobile platform, and rebuild the document on the mobile platform on the fly. This allows documents to be read, edited, and even written before they have completed loading. Our system will use the components' external interfaces to dynamically load data into a running application and to monitor how an application is being used, dynamically prioritizing the order in which components might be loaded. Our system will also monitor the network conditions, adapting the system's behavior to provide good user-perceived response time. Our system is called Puppeteer, because it controls the application from behind the scenes.
Safkasi: Resource-management in Type-safe Language Environments
Type-safe language runtime systems are increasingly being used as mechanisms for evaluating untrusted computations within a trusted host. We call these computations codelets, and they are used in a wide range of computer systems including databases, operating system kernels, network routers, Web browsers, proxy servers, multi-user virtual reality systems, agent systems, and more. While the traditional operating system ``process'' could be used to separate codelets from their host and manage the resources they use, language-based systems allow the host and codelets to run within the same address space, avoiding context-switching and communication overhead. While language-based systems can provide good access controls, limiting codelets' access to resources like files and the network, most general-purpose language-based systems do not provide resource management controls to manage codelets' aggregate use of memory, CPU, network bandwidth, and so forth. Today's language-based systems are vulnerable to simple resource exhaustion attacks such as infinite loops.
The goals of this research are to design and implement resource management support for language-based systems. In particular, we wish to be able to accurately account for and schedule memory and CPU usage. We want to connect these language-level mechanisms to kernel-level mechanisms so kernel resources used indirectly by codelets can be properly accounted for. Language runtime mechanisms must be designed that allow misbehaving codelets to be safely terminated and to help the system maintain a consistent state after the termination. Finally, we are also interested in creating formal models for our system's behavior, allowing us to make mathematically rigorous statements about our system. In particular, we wish to prove that our systems will enforce its security and resource management policies.
Some Suggested Projects