Keynote talk III

III- “Parallelizing Seemingly Sequential Algorithms“

Madan Musuvathi Microsoft Research, USA

Biography of Madan Musuvathi:
Madan Musuvathi is a Principal Researcher at Microsoft Research. His research focusses on concurrency and parallelism at the intersection of systems, programming languages, formal verification, and theory. He received his Ph.D. from Stanford University in 2004.

Abstract:
Exploiting parallelism has almost always been synonymous with identifying independent computations. At the same time, it is well known that computations with associative dependences can be parallelized. In this talk, I will generalize this idea and show how symbolic computation can be used to break dependences in computation. Doing so makes parallelization more mechanizable – the fact that a computation is efficiently parallelizable or not reduces to whether its symbolic computation can be optimized statically and/or dynamically. This presents a new and exciting application for program analysis techniques developed over the past few decades. I will present initial successes of this idea by demonstrating new parallel algorithms for finite-state machines and dynamic programming.