Theory Lunch Seminar

  • Ph.D. Student
  • Computer Science Department
  • Carnegie Mellon University

Two Recent Results in Parallel Computing

In this talk, I will discuss two recent results in parallel computing - a practical linear-work, polylogarithmic depth parallel algorithm for graph connectivity and a deterministic phase-concurrent hash table.

In the first part of the talk, I will discuss my recent work on a parallel algorithm for graph connectivity. Graph connectivity is a fundamental problem in computer science with many applications. Sequentially, connectivity can be done easily using a simple breadth-first search or depth-first search in linear work. There have been many parallel algorithms for connectivity. However the simpler parallel algorithms require superlinear work, and the linear-work polylogarithmic-depth parallel algorithms are very complicated and not amenable to implementation. In this talk, I will describe a simple and practical expected linear-work, polylogarithmic depth parallel algorithm for graph connectivity, thereby addressing this gap. The algorithm is based on a recent parallel algorithm for generating low-diameter graph decompositions by Miller et al. which uses parallel breadth-first searches. I discuss a (modest) variant of their decomposition algorithm which preserves the theoretical complexity of the algorithm while leading to a simpler and faster implementation.

In the second part of the talk, I will discuss my recent work on a phase-concurrent hash table. Many parallel programs use hash tables, however existing concurrent hash tables have non-deterministic state when operations are applied concurrently, even when restricted to only one type of operation. In this talk, I discuss a deterministic phase-concurrent hash table in which operations of the same type are allowed to proceed concurrently, but operations of different types are not. In general, inserts, deletes, finds and listing the contents of a hash table do not commute with each other. Phase-concurrency guarantees that all concurrent operations commute, giving a deterministic hash table state, guaranteeing that the state of the table at any quiescent point is independent of the ordering of operations. Furthermore, by restricting the hash table to be phase-concurrent, it can support operations more efficiently than previous concurrent hash tables. The hash table is based on linear probing, and relies on history-independence for determinism.

For More Information, Please Contact: