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).
- Port one or more benchmarks (e.g. Atomic Quake, RMS-TM) to RSTM.
- Port all of RSTM to the Power4 (parts of it run there already).
Assess the extent to which the relaxed
memory model complicates the implementation.
- Implement and benchmark closed nesting in RSTM.
- Adapt RSTM to provide the ABI (library interface) recently published
for the Intel and gcc TM projects.
- Implement and extend the transaction synchronizers of Luchangco and
Marathe [SCOOL'05].
- Kostas Menychtas recently built an RSTM version of Mike Spear's
RingSTM system. There are several RingSTM variants that we'd like
to add to the implementation. Code these up, and experiment with
the performance tradeoffs.
- Several aspects of STM could be aided by simple architectural features.
In RingSTM, for example, hardware support for Bloom filters could be
a major win. Implement one or more of these features in the
Simics/GEMS framework and evaluate its performance.
- Use TM infrastructure for speculative parallelization of sequential
programs. (Michael and Chen's groups are collaborating on this;
there's plenty of work to go around.)
- Use speculative parallelization to build a parallel discrete event
simulation system -- sort of a shared-memory version of the
classic TimeWarp system.
- Transactional mutex locks in systems software (suggested by Michael
Spear): Use transactional mutex locks to replace reader/writer locks and
mutex locks in gnu libstdc++ and/or the Linux kernel, and evaluate the
performance impact on benchmarks that stress those
portions of the code you touched.
- 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 (Henry Kautz or
recent grads Virendra Marathe or Ashwin Lal could provide more
guidance 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 manageable 1500 lines.
-
bioinformatics gene expression programs being developed in the UR
biostatistics department
- machine translation applications being developed in-house
- 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