Responsive parallelism with futures and state
Responsive parallelism with futures and state
复制标题
与 future 和 state 的响应式并行
DOI：
10.1145/3385412.3386013
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Lee, I-Ting Angelina
中科院分区：
文献类型：
--
作者：
Muller, Stefan K.;Singer, Kyle;Goldstein, Noah;Acar, Umut A.;Agrawal, Kunal;Lee, I-Ting Angelina
受多核计算机的日益发展的推动，最近的工作已经开发出了对响应并行应用程序的语言支持，这些应用程序将计算密集型任务与延迟敏感的，通常是交互式的任务混合在一起。这些发展包括允许为线程分配优先级的演算，可以排除优先级反转的类型系统，以及用于预测响应性的附带成本模型。这些进步都有一个重要的局限性：所有这些工作都假设纯函数式编程。这是一个重要的限制，因为许多现实的交互式应用程序，从游戏到机器人到Web服务器，都使用可变状态，例如，在本文中，我们解除了关于使用状态的限制。我们提出了λi4，一个以优先化的未来形式和以引用形式的可变状态形式的隐式并行性的演算。由于future和reference都是一流的值，因此λ i4程序可以表现出复杂的依赖关系，包括线程之间以及与外部世界（用户、网络等）的交互。为了解释λ i4程序的响应性，我们扩展了传统的基于图的并行性成本模型，以考虑通过可变状态创建的依赖关系，并且我们提出了一个类型系统来禁止可能导致无限阻塞的优先级反转。我们表明，这些技术是实用的，通过在C++中实现它们，并提出了实证评估。
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 λi4, 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, λi4programs can exhibit complex dependencies, including interaction between threads and with the external world (users, network, etc). To reason about the responsiveness of λi4programs, 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.
登录
查看更多内容
已证明良好且实用高效的 Fork-Join 程序并行竞争检测
DOI：
10.1145/2935764.2935801
发表时间：
2016
期刊：
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Utterback, Robert;Agrawal, Kunal;Fineman, Jeremy T.;Lee, I-Ting Angelina
通讯作者：
Lee, I-Ting Angelina
DOI：
--
发表时间：
2009
期刊：
ACM-SIGACT Symposium on Principles of Programming Languages
影响因子：
--
作者：
Ruy Ley;Umut A. Acar;M. Fluet
通讯作者：
M. Fluet
Dag-calculus：并行计算的微积分
DOI：
--
发表时间：
2016
期刊：
ACM SIGPLAN International Conference on Functional Programming
影响因子：
--
作者：
Umut A. Acar;A. Charguéraud;Mike Rainey;Filip Sieczkowski
通讯作者：
Filip Sieczkowski
带有 future 的并行程序中的死锁避免：为什么并行任务不应该等待陌生人
影响因子：
--
作者：
Tiago Cogumbreiro;R. Surendran;F. Martins;Vivek Sarkar;V. Vasconcelos;M. Grossman
通讯作者：
M. Grossman
响应式并行计算：桥接竞争线程和协作线程
DOI：
10.1145/3062341.3062370
发表时间：
2017
期刊：
Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation
影响因子：
--
作者：
Stefan K. Muller;Umut A. Acar;R. Harper
通讯作者：
R. Harper