CSC 2/458
Parallel and Distributed Systems
Spring 2026
Possible semester projects
The following are listed in no particular order.
Also note that this is in no way an exhaustive list;
suggestions here are just ideas to get you started.
Feel free to suggest a project of your own!
Many of these items are left over from 2019; they may be out of date.
Be sure to check with the instructor before investing much of your time.
- Parallelize something cool
-
Are you passionate about machine learning?
Computational linguistics?
On-line gaming?
Medical informatics?
Arguably the most compelling projects are those that involve
parallelizing some application in which you have a strong personal
interest.
Depending on personal interest and the characteristics of the
program, you might use C++, MPI, OpenMP, Rust, CUDA, or various
other options.
- Subgraph Isomorphism
(suggested by Prof. Sreepathi Pai)
-
While this problem is NP complete, given its importance, there are
now many implementations.
Read papers on the subject and implement at least two parallel
algorithms that solve subgraph isomorphism, comparing their
performance.
- Compiler parallelization
(suggested by Prof. Sreepathi Pai)
-
Compilers consume significant amounts of time and are mostly
serial. Characterize the performance behavior of a modern
compiler framework (GCC, LLVM) and identify opportunities for
parallelization. Implement and compare performance.
- Parallel sorting
(endorsed by Prof. Sreepathi Pai)
- This is a perennial favorite.
Andrea and Remzi Arpacci-Dusseau, now at UW-Madison, made a big
splash 30 years ago by improving on the best known techniques while
they were graduate students at UC-Berkeley. A good place to
start would be to read up on their work, re-implement it, explore
more recent improvements, and if possible implement your own.
Prof. Pai suggests a concrete formulation:
Given an array of (k, v) pairs, with both k and v being 64-bits, and
the number of elements being in the billions and not fitting in RAM,
sort them, ideally in-place.
- Parallelization of MCMC sampling
(suggested by Prof. Daniel Štefankovič)
-
Several approaches to this have been suggested in recent years
(1,
2,
3); try them out!
- Parallelization of Stochastic Gradient Descent (SGD)
(suggested by Prof. Daniel Štefankovič)
-
Experiment with the approach of Niu et al.
- Machine-checked proofs
(suggested by Prof. Chen Ding)
-
Build a machine-checked proof of correctness (Prof. Ding suggests
using Rocq) for your favorite
concurrent data structure.
- Can AI write parallel code?
- AI tools are increasingly being used to automate
“routine” coding tasks. Can AI write good
parallel code? Can it successfully parallelize nontrivial
sequential computation-intensive algorithms? Can it find
data races?&*nbsp; How would you go about answering these
questions?
- Transactional Memory (TM)
- While this area is not as “hot” as it was a decade
ago, interesting work continues to be done, and papers to be
published. Possible projects include
-
Learn about the original
and “lite”
proposals to incorporate TM into the C++
programming language.
Experiment with available implementations, including the one that
ships with
gcc.
Characterize its performance—both the software library and
(for x86 and Power) the support for hardware TM.
-
Develop a proposal for TM condition synchronization and build it into
gcc.
You might want to check out the retry
mechanism of Haskell and the work of Wang & Spear.
-
Develop a version of “smart pointers”
(
shared_ptr and weak_ptr in particular)
that “play nice” with transactions. In particular,
figure out how to ensure that nontransactional increments and
decrements of shared_ptr reference counts—and
invocations of
destructors when counts reach zero—always serialize with
respect to transactions that touch the same objects.
How much overhead is your mechanism forced to impose on
nontransactional code?
-
In a similar vein, develop an implementation of
atomic
variables that can safely be accessed inside
atomic blocks, in such a way that nontransactional
accesses serialize with respect to transactions that access the same
objects.
-
Port the instructor's Delaunay Mesh creation program
to use C++ TM. Extend it to perform mesh refinement, as in the
STAMP
YADA benchmark.
-
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.
-
Write your own favorite application using transactional
memory. Compare both ease of programming and performance to
what you get with locks.
- 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 state?
- Pure nonblocking structures
- New nonblocking data structures are constantly being developed,
and often lead to publications.
Develop a nonblocking version of something novel.
If you want a possible option, the instructor developed a design for
a nonblocking priority queue heap while taking long walks during the
COVID-19 pandemic. Try building this structure and
benchmarking it. Compare it to other options from the
literature.
- Dual data structures
- Bill Scherer gained considerable fame 20 years ago 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. A decade later, Joe
Izraelevitz showed how to
build dual versions of the LCRQ (FAI-based concurrent queue) of
Morrison & Afek. What else can be built in this
style? In particular, you might consider priority queues or
skip lists.
- Data race detection
- There has been a huge amoung of work in recent years on the
detection and correction of
data races (one of the principal categories of program bugs and
security vulnerabilities). Explore the literature and
implement/experiment with some of the leading options.
- Cluster-level shared memory
- Cashmere
was a locally-developed project to emulate shared
memory across clusters of multiprocessors connected by a fast
system-area network with support for remote reads and writes—a
predecessor to today’s Infiniband. HLRC was a similar
project developed at Princeton. Using the Infiniband
cluster here in the department, rebuild Cashmere or HLRC to
use this more modern network (and processors), and
re-evaluate the conclusions of the earlier project.
- Explore graph runtimes
-
Many packages for large-scale graph computation have been developed
over the years.
Example systems include Pregel, GraphLab, Grappa,
Giraph, and Hive. The article by McCune
et al. provides a good (but now decade-old) survey of these and
others.
Use some subset of these to build implementations of a few standard
graph algorithms (shortest paths, betweeness centrality, connected
components, page rank, etc.) and compare their functionality and
performance.
- Sparse linear solver
-
In some years, one of the whole-class projects has been to
parallelize Gaussian
elimination. The algorithm isn’t very efficient when
the coefficient matrix is sparse (mostly zeros). Create a better
version. (Kai Shen, formerly a
professor in our department, built a very good
version of this as a graduate student. He notes:
“Sparse matrix processing is the computational kernel in
applications ranging from scientific simulations to Google's
PageRank calculation. There is
a little bit of numerical analysis involved in this project, but
your main efforts will be centering around fine-grain
synchronization, work stealing/balancing, and cache-efficient
algorithms.”)
- Scalable try-locks for in-core databases
-
25 years ago, Bill Scherer and I developed a family of scalable
queue-based locks in which a process can “time out” and
stop waiting for the lock. Ten years ago, Chabbi et
al. published a variant on one of these schemes.
Bill and I conjectured that such locks would be particularly useful
for in-core user-level database systems. It would be
interesting to engineer them into MySQL or memcached and measure the
performance of the resulting code.
- Replication for availability
-
Consider a data repository—e.g., a key-value store—in
which lookups are much more common than updates.
For the sake of availability, such a repository may be replicated in
multiple locations, with replicas kept up to date via multicast
updates. Using memcached as the foundation, build a replicated
repository and experiment with alternative implementations of
ordered (consistent) multicast. Compare the performance of your
implementations to that of a (nonserializable) alternative that does
not enforce consistent orders.
- Automatic hardware benchmarking
-
As we have seen, performance on modern machines can depend on a wide
variety of system characteristics, including
the number of threads per core, cores per socket, and sockets per
machine; the number of levels of cache, their sizes, associativity,
and sharing across threads and cores;
the interconnection network topology; and the distribution of main
memory.
Build a tool that automatically explores the underlying
hardware and produces a detailed report of these and other
characteristics.
- Parallel game tree search
- Another perennial favorite.
Alpha-beta search with pruning is central to computerized versions of
many classic games, including chess, checkers, reversi (Othello),
and go. How many plies can you search per second using a
cluster-based combination of OpenMP and MPI?
- Shared memory v. message passing
-
Create a shared memory version of some existing MPI application, and
perform a detailed performance comparison.
- Data parallel programming
-
Create a GPU version of some existing data parallel application, and
perform a detailed performance comparison.
Alternatively, experiment with machine learning apps in TensorFlow.
Back to the course home page
Last Change:
26 February 2026