Parallelizing Sequential Iterative Algorithms

This talk will delve into our decade-long research in parallelizing sequential iterative algorithms, such as greedy algorithms and dynamic programming that are covered in undergrad algorithm courses. The core concept here is to identify the inherent computational structures and develop general frameworks for their parallel execution. I will overview the key concepts and techniques proposed throughout this research process, including the dependence graphs, asynchronous execution, phase parallelism, and the cordon algorithm. Illustrative examples will include random permutation, maximal independent set (MIS), and dynamic programming applications. This talk will cover the results in several papers, including a JACM'20 paper, Outstanding Papers at SPAA'20 and SPAA'24, and a best paper at ESA'23.