Responsive Parallelism with Futures and State
| Autor: | Noah Goldstein, I-Ting Angelina Lee, Kunal Agrawal, Umut A. Acar, Stefan K. Muller, Kyle Singer |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
020203 distributed computing Theoretical computer science Computer Science - Programming Languages Computer science Purely functional programming Concurrency 020207 software engineering 02 engineering and technology Cilk Blocking (computing) Shared memory 0202 electrical engineering electronic engineering information engineering Parallelism (grammar) Graph (abstract data type) Implicit parallelism computer computer.programming_language Programming Languages (cs.PL) |
| Zdroj: | PLDI |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|