CSC 2/458

Parallel and Distributed Systems

Spring 2007.

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)

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 last year 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 may be 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. MPI programs are very portable since they can run on both shared-memory machines and distributed-memory machines. However, most existing parallel sparse LU solvers were only evaluated on tightly coupled parallel computing platforms, such as the IBM Regatta, SP2, and Cray T3E. This is because parallel sparse LU factorization with partial pivoting requires fine-grain synchronization and large communication volume between computing nodes. This project examines the effectiveness of existing solvers on platforms with relative poor message passing performance (e.g., the PC cluster). Specifically, you are asked to compare the performance of two MPI-based solvers: SuperLU_DIST (version 2.0) and S+ (version 1.1) on the IBM Regatta and a Linux cluster. Please analyze the results and explain the algorithmic features that contribute to good/bad performance. Suggest improvements that can enhance the application performance on the Linux cluster. This project is suggested by Professor Kai Shen, who would be a good point of contact for advice.
* SuperLU_DIST can be found at http://crd.lbl.gov/~xiaoye/SuperLU/. The following paper explains its design.
* S+ 1.1 can be found here . The following papers explain it design in version 1.0 and updates in version 1.1

Lock-free MPI (from Michael Scott and Kai Shen)
MPI implementations for shared-memory machines are highly threaded, and make heavy use of locks. Take an existing implementation and make it lock-free. Could potentially see significant performance improvements, akin to Maged Michael's results (reported at PLDI 2004) with malloc. The following paper titled Program Transformation and Runtime Support for Threaded MPI Execution on Shared Memory Machines will provide you with a good headstart. Both Professors Kai Shen and Michael Scott have offered to be available for advice and useful tips.

Scalable try-locks for in-core databases (from Michael Scott)
Bill Scherer 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.

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 in Multi-Threaded/Chip Multiprocessors
As part of our research, we are examining ways in which on-chip resources can be partitioned/clustered so as to improve both single and multi-threaded performance. The clustered architecture directly exposes the trade-off between communication and parallelism. We have a working simulator that implements this architecture. As part of this project, you could use the simulator to examine/evaluate ways in which the cache may be partitioned or shared among simultaneously executing threads. For more information on the project, take a look at cs.rochester.edu/research/dt-cmt

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: 05 May 2007 / Sandhya Dwarkadas