Keynote talk III

III- Parallelizing Seemingly Sequential Algorithms

Madan 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.

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.

Dates [No Extensions]

January 9, 2015

Abstract submission deadline

January 18, 2015

Paper submission deadline

March 16, 2015

Acceptance notification

April 13, 2015

Camera ready copy due



The proceedings of the conference will be published in Springer’s Lecture Notes in Computer Science