Responsive Parallelism with Futures and State
Motivated by the increasing shift to multicore computers, recent work has developed language support for responsive parallel applications that mix compute-intensive tasks with latency-sensitive, usually interactive, tasks. These developments include calculi that allow assigning priorities to threads, type systems that can rule out priority inversions, and accompanying cost models for predicting responsiveness. These advances share one important limitation: all of this work assumes purely functional programming. This is a significant restriction, because many realistic interactive applications, from games to robots to web servers, use mutable state, e.g., for communication between threads.
In this paper, we lift the restriction concerning the use of state. We present $\lambda_i^4$, a calculus with implicit parallelism in the form of prioritized futures and mutable state in the form of references. Because both futures and references are first-class values, $\lambda_i^4$ programs can exhibit complex dependencies, including interaction between threads and with the external world (users, network, etc). To reason about the responsiveness of $\lambda_i^4$ programs, we extend traditional graph-based cost models for parallelism to account for dependencies created via mutable state, and we present a type system to outlaw priority inversions that can lead to unbounded blocking. We show that these techniques are practical by implementing them in C++ and present an empirical evaluation.
Thu 21 OctDisplayed time zone: Central Time (US & Canada) change
13:50 - 15:10
PLDI 2020 Papers 2SIGPLAN Papers at Zurich F
Chair(s): Tyler Sorensen University of California at Santa Cruz
|Automated Derivation of Parametric Data Movement Lower Bounds for Affine Programs|
Auguste Olivry Inria, France, Julien Langou , Louis-Noël Pouchet Colorado State University, USA, Saday Sadayappan University of Utah, USA, Fabrice Rastello Inria, France
|Responsive Parallelism with Futures and State|
Stefan K. Muller Illinois Institute of Technology, Kyle Singer Washington University in St. Louis, USA, Noah Goldstein Washington University in St. Louis, USA, Umut A. Acar Carnegie Mellon University, Kunal Agrawal Washington University in St. Louis, USA, I-Ting Angelina Lee Washington University in St. Louis, USA
|The Essence of Bluespec: A Core Language for Rule-Based Hardware Design|
Thomas Bourgeat , Clément Pit-Claudel MIT CSAIL, Adam Chlipala Massachusetts Institute of Technology, Arvind Massachusetts Institute of Technology, USA
|Semantic Code Search via Equational Reasoning|
Varot Premtoon Massachusetts Institute of Technology, USA, James Koppel Massachusetts Institute of Technology, USA, Armando Solar-Lezama Massachusetts Institute of TechnologyLink to publication
|Discussion, Questions and Answers|