Colloquia Series-Stefan Muller

Sep 28, 2018
10:00 a.m.
Lopata Hall, Room 101

Cost Models for Parallel Programs


If a program takes time T to run on one processor, how long will it take to run on P processors? This is a fundamental question when designing parallel algorithms, programs and languages, and answering it has been the subject of decades of work. The program of bounded implementations pioneered by Blelloch and Greiner in the 1990s gives a framework for relating parallel programs to abstract dependency graphs, using existing results about such graphs to give reasonable bounds on time and space cost, and then showing that an implementation of the program or language can realize these bounds.

In this talk, I will argue that the framework of bounded implementations should be seen not as a historical artifact but as a blueprint for exploring new problems in parallel computing and for designing new parallel languages. I will then describe how we are applying this blueprint to reason about a new and important class of parallel programs: interactive programs for which a suitable notion of cost must account for responsiveness and not just throughput. We have extended the dependency graph-based cost models to account for responsiveness. In turn, these models have influenced the development of our languages and techniques by helping us reason about and eliminate performance pitfalls, such as priority inversions, that arise in this new setting.


Stefan earned his PhD at Carnegie Mellon University in September 2018. His thesis work, advised by Prof. Umut Acar, focused on the design of languages and cost analysis techniques for parallel interactive programs. He is continuing to study cost semantics and how they can be used to analyze the responsiveness of software as a postdoctoral fellow under Prof. Jan Hoffmann at CMU.

Organizer / Host: Angelina Lee