PoP Seminar Talk

Static prediction of parallel computation graph

Stefan Muller, Gladwin Development Chair Assistant Professor
Thursday, 02 November, 2023; 3:30pm
NSH 4305
Host: Jan Hoffmann


Many algorithms for analyzing parallel programs, for example to detect deadlocks or data races or to calculate the execution cost, are based on a model variously known as a cost graph, computation graph, or dependency graph, which captures the parallel structure of threads in a program. In modern parallel programs, computation graphs are highly dynamic and depend greatly on the program inputs and execution details. As such, most analyses that use these graphs are either dynamic analyses or are specialized static analyses that gather a subset of dependency information for a specific purpose.

In this talk, I’ll briefly discuss my work on graph types, which compactly represent all of the graphs that could arise from program execution and can be inferred from a parallel program using a graph type system. The graph type system introduces unique names for vertices in the graph; uniqueness is ensured using an affine type system. I will also discuss recent work on extending the graph type system to handle data structures containing, or built using, futures, which requires indexing types in the graph type system with corecursive structures of vertex names


Stefan Muller is an Assistant Professor at the Illinois Institute of Technology working on the design of type systems and static analysis for safe and efficient parallel programming. Before joining Illinois Tech in 2020, he completed a PhD and postdoc at Carnegie Mellon University, working under Umut Acar and Jan Hoffmann.