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)
- Port one or more benchmarks (e.g. SPLASH) to RSTM.
- Port RSTM to the Power4. Assess the extent to which the relaxed
memory model complicates the implementation.
- Implement and benchmark closed nesting in RSTM.
- Implement support for condition synchronization using the 'retry'
mechanism described by Harris et al. [PPoPP'05]
- Implement the transaction synchronizers of Luchangco and Marathe
[SCOOL'05]
- Implement support for irreversible operations like I/O. Michael
says, "I have some
ideas on this; I'm sure there's a paper in it.", so please see him
if you're interested.
- 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
- MiniSAT, an open source SAT solver (see Virendra Marathe for more
on this)
SAT is an NP-complete and extremely important problem with applications
varying from proving the theoretical hardness of algorithms to the
verification of complex microprocessor architectures. MINISAT is a
publicly available SAT solver that employs several state-of-the-art
techniques and heuristics in single-threaded SAT solvers. The code size is
a managable 1500 lines.
-
ICED, a bioinformatics gene expression program, developed in part
by Yinhe Chen and Mitsu Ogihara
- Dana Ballard's neural simulator
- 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