COLLOQUIUM LECTURE - Parallelizing Inherently Sequential Computations by Breaking Dependences Precisely

Speaker:
Madan Musuvathi
Date:
Tuesday, 18.12.2018, 14:30
Place:
Room 337 Taub Bld.
Affiliation:
Microsoft Research
Host:
Roy Schwartz

Large-scale data processing requires large-scale parallelism. Data-processing systems from traditional databases to Hadoop and Spark rely on embarrassingly-parallel relational primitives (e.g. map, reduce, filter, and join) to extract parallelism from input programs. But many important applications, such as machine learning and log processing, iterate over large data sets with true loop-carried dependences across iterations. As such, these applications are not readily parallelizable in current data-processing systems. In this talk, I will challenge the premise that parallelism requires independent computations. In particular, I will describe a general methodology for extracting parallelism from dependent computations. The basic idea is replace dependences with symbolic unknowns and execute the dependent computations symbolically in parallel. The challenge of parallelization now becomes a, hopefully mechanizable, task of performing the resulting symbolic execution efficiently. This methodology opens up the possibility of designing new languages for data-processing computations, compilers that automatically parallelize such computations, and runtimes that exploit the additional parallelism. I will describe our initial successes with this approach and the research challenges that lie ahead. Short Bio: Madas Musuvathi is a Principal Researcher in the Research in Software Engineering group at Microsoft Research. His research focus is on scalable analysis of concurrent systems. More broadly, his interests include systems, program analysis, model checking, verification, and theorem proving. He spend a lot of time at Microsoft building analysis tools to improve the productivity of software developers and testers. His current research projects include: Efficient Parallel Algorithms, End to End Sequential Consistency, Concurrency Fuzzing, Memory Models, CHESS. He obtained his M.S. and Ph.D. at Stanford University, where he worked under the guidance of Prof. David L. Dill and Prof. Dawson Engler. Before that, He got his B.Tech. in Computer Science from the Indian Institute of Technology (IIT), Chennai (which was then called Madras).

Back to the index of events