AF: Small: Shared-Memory Parallel Algorithms: Theory and Practice

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

With the advent in recent years of multicore processors ranging from fifty dollar hobby kits to multi-million dollar supercomputers, shared-memory parallel algorithms have increasingly significant practical and theoretical relevance. This project is developing new algorithmic approaches and results relevant to today's shared-memory parallel machines. The impact of this project will be felt in applications being able to make better use of the computational power of modern multi-core architectures. The project seeks to develop library implementations of many of these algorithms which will be made available to the public. On the educational side, the project will result in coursework that will help undergraduate students learn about parallel algorithms and their implementation. The project focuses on three areas. The first is research on developing results in a model, the binary forking model, that is more relevant to today's machines than some previous models. In particular the model matches the software platforms that are available on most parallel machines, and supports an asynchronous form of parallelism that are most relevant to the machines they run on. The second area is to better understand the parallelism already available in many sequential algorithms. The goal is to derive algorithms that are simpler and more efficient. The third area is to develop algorithms that allow the user to efficiently make batches of updates to underlying data structures. This is referred to as batch parallel dynamic algorithms, and follows significant prior work on sequential single update dynamic updates. In the binary forking model each task can only fork into two child tasks, but can do so recursively and asynchronously. At present no tight performance bounds for the binary forking model are known even for some basic problems such as sorting and graph connectivity, which this project seeks to remedy. For the thrust on understanding parallelism in sequential algorithms, the project will study the dependencies among sub-computations in iterative sequential algorithms. In the thrust on parallel batched algorithms the project is looking at applying the ideas to graph connectivity and related problems. The goal is to achieve algorithms that are work-efficient relative to the best (or near best) sequential algorithms---and in particular for graph connectivity to achieve O(log^2 n) amortized work per update, while allowing batches of updates. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.