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

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