SPLASH 2021
Sun 17 - Fri 22 October 2021 Chicago, Illinois, United States
Thu 21 Oct 2021 14:05 - 14:20 at Zurich F - PLDI 2020 Papers 2 Chair(s): Tyler Sorensen

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 Oct

Displayed 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
13:50
15m
Talk
Automated Derivation of Parametric Data Movement Lower Bounds for Affine Programs
SIGPLAN Papers
Auguste Olivry Inria, France, Julien Langou , Louis-Noël Pouchet Colorado State University, USA, Saday Sadayappan University of Utah, USA, Fabrice Rastello Inria, France
14:05
15m
Talk
Responsive Parallelism with Futures and State
SIGPLAN Papers
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
14:20
15m
Talk
The Essence of Bluespec: A Core Language for Rule-Based Hardware Design
SIGPLAN Papers
Thomas Bourgeat , Clément Pit-Claudel MIT CSAIL, Adam Chlipala Massachusetts Institute of Technology, Arvind Massachusetts Institute of Technology, USA
14:35
15m
Paper
Semantic Code Search via Equational Reasoning
SIGPLAN Papers
Varot Premtoon Massachusetts Institute of Technology, USA, James Koppel Massachusetts Institute of Technology, USA, Armando Solar-Lezama Massachusetts Institute of Technology
Link to publication
14:50
20m
Live Q&A
Discussion, Questions and Answers
SIGPLAN Papers