CSC 2/458

Parallel and Distributed Systems

Spring 2009.

Possible semester projects

The following are listed in no particular order. Also note that this is in no way an exhaustive list; feel free to suggest a project of your own.

Software Transactional Memory (from Michael Scott): Rochester currently distributes the largest, most highly tuned suite of software TM (STM) systems, collectively known as RSTM (R for Rochester).

Parallelize some interesting application using either traditional lock-based shared memory or message passing, or more interestingly, contrasting these approaches with the use of transactional memory or languages such as CILK.
Possibilities include

Compare shared memory and message passing
Create a shared memory version of some existing MPI application, and perform a detailed performance comparison.

Behavior-Oriented Parallelization (from Chen Ding)
Behavior-based programming is a new approach that allows a user or a profiling tool to parallelize or optimize a program based on *partial* information about the program code and the input. It uses modern parallel processors to reduce and hide the overhead of dynamic correctness checking and error recovery. The current system supports unsafe parallelization and optimization for C/C++/Fortran applications on x86 running Linux. A description of the basic design and the preliminary results can be found in the on-line URCS technical report TR-904 and TR-907. For this project, you can either study an interesting computation, e.g. dynamic programming, for speculative parallelism;adapt an existing application, e.g. one from SPEC integer benchmarks, touse multicore, multi-processors; or improve the design and expand the user interface of the current systems. You will need to work with Prof. Ding (who'll be in Seattle after February) remotely but can collaborate with his students here.

Dual data structures (from Michael Scott)
Bill Scherer gained considerable fame a few years back by rewriting classic queues, stacks, synchronous queues, and exchangers as lock-free "dual" data structures, in which an operation that has to wait for a precondition leaves an explicit reservation in the data structure. What else can be built in this style? In particular, you might consider priority queues or various search structures. This is definitely publishable.

Parallel I/O workload characterization (from Kai Shen)
Data-intensive parallel applications demand efficient I/O to achieve high performance. Many parallel applications use the MPI-I/O interface to access storage devices managed by parallel file systems. Some parallel file systems (like PVFS) manage a cluster of storage hosts (each with attached disks) on commodity storage and network hardware. In this project, you will experiment with several parallel applications on such platform; collect I/O workload characteristics on individual storage hosts and across the whole storage cluster; analyze such characteristics and speculate on possible operating system and distributed system enhancements. You should plan on a literature survey concerning previous work on parallel I/O workload characterization. Note that earlier results might have been produced on different parallel I/O platforms.

InterWeave
InterWeave is a system that allows distributed processes to share global variables. It keeps locally cached copies of these variables up-to-date efficiently, converting automatically among multiple languages and machine types. It was a very successful project, and has a high-quality implementation. We'd like to distribute it to the world. Rich Sarkis, a former URCS undergrad now on staff in Physics and Astronomy, made a start toward polishing and packaging the system for Open Source download. Get in touch with him, see where it stands, and push the project through to completion. This would involve nontrivial work with demo applications, performance tuning, and configuration and installation tools. It's an opportunity to have your name permanently associated with a widely-used code base.

Software distributed shared memory
Our group has done considerable work in this area. We have access to two state-of-the-art runtime systems (TreadMarks and Cashmere) that provide the illusion of shared memory on a network of workstations. You could enhance one of these systems to improve the communication behavior of some application class, either using a published protocol enhancement, or developing your own.

Parallel sorting
Andrea and Remzi Arpacci-Dusseau, now at UW-Madison, hold the record for the performance of a parallel external sort. Read up on their work, re-implement it, experiment with it, and if possible improve it.

Parallel Sparse LU Factorization Using Message Passing (from Kai Shen)
In project one of this course, you have implemented parallel Gaussian Elimination with partial pivoting (using pthreads and MPI). LU factorization is the core step of the Gaussian Elimination. In this project, you will work on *sparse* LU factorization in the sense that most elements in the matrix are zeros. Sparse matrix computations have applications in many scientific and engineering problems, including the computation for Google's PageRank algorithm. Parallel sparse LU factorization with partial pivoting is challenging because it requires fine-grain synchronization and large communication volume between computing nodes. Creating a new solver would probably require more than a semester's effort. Instead, you are asked to experiment with and analyze some existing solvers. Two MPI-based solvers are:
* SuperLU_DIST, available at http://crd.lbl.gov/~xiaoye/SuperL U/. The following paper explains its design.
* S+, available here . The following papers explain its design in version 1.0 and updates in version 1.1.
In your project, you can pick one of the solvers and study its behavior on different parallel platforms (e.g., a PC cluster and the IBM Regatta). You may also compare across the two solvers. Please pay attention to both performance as well as numerical stability. Analysis on good/bad behaviors and insights into any possible improvement are an important part of the project outcome.

Scalable try-locks for in-core databases (from Michael Scott)
Bill Scherer, Bijun He, and Michael Scott have developed a family of scalable queue-based locks in which a process can "time out" and stop waiting for the lock. They conjecture that these locks would be particularly useful for in-core user-level database systems. Try it out!

Parallel architecture simulation and evaluation
Implement a simulation model of your own or an existing shared memory multiprocessor design (e.g., TimeStamp Snooping) and evaluate its performance on a set of available benchmarks. Possible simulation tools include SimpleScalar extended to handle multithreaded applications, and SIMICS, a full system simulator.

Memory Hierarchy Design for Multi-Core Processors
As part of our research, we are exploring novel communication and synchronization mechanisms, as well as examining ways in which on-chip state resources can be partitioned/shared so as to improve both single and multi-threaded performance. We have working simulation designs for various communication mechanisms and cache designs. As part of this project, you could use the simulator to examine/evaluate the proposed cache designs, suggest improvements of your own, or find and experiment with new ways to utilize the proposed communication mechanisms. For more information, take a look at the CoSyn project.

Resource-Aware Scheduling for Multi-Threaded Processors
Multi-threaded processors (simultaneous multi-threaded or multi-core) have a unique opportunity to share resources at a fine grain. However, contention from conflicting resource requirements can result in reduced performance, especially in the memory hierarchy. As part of this project, you could attempt to identify a mechanism by which thread conflicts may be detected and implement a scheme to utilize the information at either the operating system or application level.

Automatic Component Placement in Distributed Systems
For the sake of modularity, flexibility, and reusability, distributed applications are increasingly implemented as collections of components, using CORBA, Java Beans, .NET, CCA, etc. Most components today are statically located, but several groups are working to extend this model, either via object mobility (allowing remote components to change location) or via shared state or object caching (allowing data or code to move transparently to where it is needed, so that local access replaces remote invocation). Your task as part of this project could be to take an existing benchmark or application (e.g., a distributed game) and determine how to componentize/distribute it so as to maximize performance.

Last Change: 01 May 2009 / Sandhya Dwarkadas