Parallel and Distributed Systems
Possible semester projects
PROJECT PROPOSAL DUE (one page): March 22, 2016; In class 2-minute introduction: March 24, 2016
You are free to work together in
groups of 2 or 3 (with a commensurate increase in expectation) for your term
The proposal must be in PDF format and turned in using the electronic TURN-IN
In the proposal, you should describe the concrete goals for your project,
any related materials from papers and web resources, and anything else you
feel is relevant. Please provide sufficient detail in the project proposal to
demonstrate your preparation for the project. Please make sure to specify all
project participants in the proposal.
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.
- Application parallelization/parallel machine/parallel abstraction
- 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, TBB, OpenMP, UPC, X10, ... Alternatively,
explore abstractions such as Map-Reduce, or those provided by
Pregel or GraphLab. Analyze the behavior of different parallel
systems, including the BlueGene/Q at the Center for Integrated Research
We have several research groups associated with the CIRC
with compute-intensive codes that could benefit from
efficient parallelization, both on clusters and on the BlueGene rack at the
CIRC. As part of this project, you could work with one of these groups to
develop an efficient parallel implementation of their code.
Please send me a note if you are interested and I will forward you more information.
I can also put you in touch with the corresponding sponsor.
Here are some example projects:
- Flow cytometry data analysis(contact: Jeanne Holden-Wiltse, Max Qian, David Topham):
- Parallel data processing for directed automated filtering of high-dimensional flow cytometry data:
(From the developers) Data filtering is an essential preprocessing step for computational analysis of flow cytometry data. We have developed and
implemented software programs (in C and Matlab) that are able to
process and filter each flow cytometry data file in a sequential way.
In the end, all the resulting images will be assembled into one or
multiple large image composites for visual examination.
We are looking to parallelize the procedure in a MapReduce fashion
with software implementation that can be run on (and utilize) the
Bluehive parallel computing infrastructure. The goal is to accelerate
the filtering and image generation procedure so that results from
large sets of files with multiple configurations can be generated and
examined by the scientists in a timely fashion.
Code is available
for class use on request.
- Parallel conversion and transformation of flow cytometry data:
(From the developers) The existing R-based conversion and
transformation of flow cytometry data is slow and suboptimal in
memory management. We are looking to implement a scalable version
that can preprocess the flow cytometry data files in a more
efficient way. It can be accomplished through either
re-implementing the existing serial code with R parallel packages
(e.g., snow/parallel/RHadoop) or implementing wrapper software for
parallel execution across multiple compute cores/nodes.
Link to a paper on the subject
Link to the source code
- Parallel generation and organization of dot plots from flow cytometry data analysis results: (From the developers) The High-dimensional flow cytometry data analysis generates a huge number of 2D dot plots as part of the analysis results. We have developed a suite of software programs (primarily in Java, also in Perl and Python) for generating and managing these dot plots, including versions for multi-threading and data-parallel executions. We are looking to adapt these programs for their executions on the Bluehive compute cluster. Most importantly, we expect the adapted implementation can utilize a large number of compute cores across multiple compute nodes to provide a highly scalable solution for dot plot image generation and management.
Link to a paper
Link to the source code
Link to the code for generation of 2d plots
- Software Transactional Memory (sponsor: Michael Scott):
- Over the past decade, URCS has been one of the leading sites for
research in transactional memory (TM). We have multiple TM
implementations available, both hardware and software. Possible projects
- Implement or port your favorite application using TM instead of locks.
- Implement or re-implement standard library (e.g., container) classes using
STM, allowing their operations to compose with one another without fear of deadlock.
- Building on the work of Lingxiang Xiang (published at PPoPP
2015), build _partitioned_ library routines that combine manual
"pre-speculation" with composability.
- Nonblocking data structures (sponsor: Michael Scott):
- These are thread-safe concurrent data structures that work without
locks, and are immune to the performance hiccups caused by preemption.
Possible projects include:
- Dual data structures:
A decade ago, grad student Bill Scherer (now at HP) gained
considerable fame (including a "research highlights" publication in
CACM) 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. Recently, Joe Izraelevitz did similar
work on fast, fetch-and-increment-based queues. What else can be built in this
style? In particular, you might consider priority queues or other
- Hybrid transactional / non-blocking data structures: One of the
key advantages of nonblocking data structures is increased
concurrency. A major disadvantage is complexity. Can we get
(most of) the concurrency without (most of) the complexity by
using transactions for _sub-parts_ of each operation? Consider,
for example, a B-tree or 2-3 tree: can we capture rebalancing as
a _series_ of transactions, each of which transforms the tree
from a consistent but sub-optimal state to a "better" consistent
- Evaluate Sharing-Aware Mapping on Multicore Systems (sponsor: Sandhya Dwarkadas):
- Multicore systems share resources such as on-chip interconnects,
last-level caches, and off-chip bandwidth, and incur non-uniform
latencies of access. Users of parallel applications written for these
environments often have to understand the topology to get the best
stand-alone performance. In the presence of multiprogramming, which
dynamically changes the resources allocated to the parallel application,
extracting the best performance available from the system is next to
impossible. In a recent kernel-level implementation and corresponding
publication, we have developed a Sharing-Aware Mapper, which identifies
and reacts to both sharing and resource contention.
Your task will be to develop both microbenchmarks and real applications
to stress test the system.
- Large-scale graph-based computations (sponsor: Sandhya Dwarkadas):
An unprecedented increase in the volumes of data that can be
generated and stored has resulted in the need for data analysis
tools that can handle this volume. Systems such as MapReduce,
GraphLab, and Grappa have been developed to support analysis on both
structured and unstructured data in parallel. In this project, you
could experiment with the pros and cons of some of these frameworks
when developing classic machine learning algorithms to handle
data from different domains. One example project would consist
of implementing algorithms to determine the k-nearest neighbors
of a query data point.
Deterministic Parallel Ruby (DPR)
(sponsor: Michael Scott):
For the thesis he defended last year (and presented at
PLDI'14), graduate student Li Lu developed a parallel dialect of
Ruby (based primarily on parallel execution of independent code
blocks) and an innovative race detector (determinism checker) named
TARDIS, which verifies independence.
- Concurrent verification.
We think there is an opportunity to speed up the performance of
TARDIS by moving work onto the "sister" hyperthreads of program
threads on SMT machines. This would entail some interesting work
inside both the JRuby virtual machine and the Jikes JVM, to
"pin" computations to hardware threads.
Parallelize your favorite Ruby apps -- parts of the Rails
- Teaching concurrency.
The DPR/TARDIS implementation has been released as open source.
With some additional work, we believe it would make an ideal
teaching language. This project would entail a detailed
assessment of the implementation, itemization of the steps
needed to make it "freshman proof", and implementation of as
many steps as possible toward that goal.
- Thread wakeup (sponsor: Michael Scott):
- Fast "remote" operations are increasingly common on modern machines.
Examples of such operations include remote procedure call (RPC) and
requests to user-accessible devices and accelerators (network, hard
drive, GPU, or compression/encryption/transcoding engine). The costs
associated with invoking remote operations are poorly understood, yet
essential for good performance.
- Implement a simple RPC system and parameterized microbenchmark.
Using fine-grain timers and hardware performance counters, measure
the impact of protection boundary crossing, data copying, loss of
cache footprint, loss of TLB state, and processor power-saving
modes as a function of request size and timing, locations of
communicating partners, and concurrent activity in other cores and
- Implement techniques to mitigate the above impacts. Examples
might include co-location, deliberate slowing of polling rates,
and anticipatory cache/TLB/power-state warm-up.
Software coherence (sponsor: Sandhya Dwarkadas and/or Michael L. Scott):
- Around the turn of the century,
Michael Scott and I led a pair of projects known as
Cashmere and InterWeave. These explored techniques to implement
shared-memory programming models on distributed hardware.
There has been a recent resurgence of interest in this area.
As people design chips with ever larger numbers of cores, they are
beginning to question whether the hardware should guarantee
coherence across all cores.
Build a software shared-memory system
in the style of Cashmere that exploits hardware coherence within
subdomains of a multiprocessor, and fast but noncoherent access to
memory across subdomains.
Build a coherent memory system for a collection of devices with globally
accessible but scratchpad-style local memory (i.e., direct access to,
but without hardware support for coherent shared memory). In essence,
you could propose and evaluate an explicit cache management strategy
that is tailored to the latency and bandwidth constraints in multicores.
- Suggestion-based Parallelization Language (sponsor: Chen Ding)
- Below are some bullet points provided by Prof. Chen Ding. If you are
interested, please contact him for more details.
- Use BOP system to parallelize one or more programs.
- Evaluate the current implementation using current benchmarks.
- Apply or extend FastTrack, a suggestion-based optimization tool.
- Shared cache locality management (sponsor: Chen Ding)
- Shared cache locality modeling and improvement, in particular,
characterizing the shared cache locality in sequential and parallel
programs and examining possible solutions.
- 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
- Parallel architecture simulation and evaluation (sponsor: Sandhya Dwarkadas):
- 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, SIMICS, a full system
simulator, and GEM5.
- 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
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
26 April 2016 /