Static prediction of parallel computation graphs
Static prediction of parallel computation graphs
复制标题
并行计算图的静态预测
DOI：
10.1145/3498708
复制
发表时间：
2022
影响因子：
--
通讯作者：
Muller, Stefan K.
中科院分区：
文献类型：
--
作者：
Muller, Stefan K.
许多用于分析并行程序的算法，例如检测死锁或数据竞争或计算执行成本，都是基于一种模型，该模型被不同地称为成本图、计算图或依赖图，该模型捕获程序中线程的并行结构。在现代并行程序中，计算图是高度动态的，并且在很大程度上依赖于程序输入和执行细节。因此，大多数使用这些图的分析要么是动态分析，要么是专门的静态分析，为特定目的收集依赖关系信息的子集。图类型是利用图类型系统和推理算法从并行程序中推断出来的，我们借鉴了Hindley-Milner类型推理、仿射逻辑和区域类型系统的思想。我们已经在OCaml的一个子集上实现了推理算法，并用并行原语进行了扩展，并演示了如何通过为死锁检测和代价分析提供概念验证分析来使用图类型来加速新的基于图的静态分析的开发。
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.This paper introduces graph types, which compactly represent all of the graphs that could arise from program execution. Graph types are inferred from a parallel program using a graph type system and inference algorithm, which we present drawing on ideas from Hindley-Milner type inference, affine logic and region type systems. We have implemented the inference algorithm over a subset of OCaml, extended with parallelism primitives, and we demonstrate how graph types can be used to accelerate the development of new graph-based static analyses by presenting proof-of-concept analyses for deadlock detection and cost analysis.
登录
查看更多内容
已证明良好且实用高效的 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
带有 future 的并行程序中的死锁避免：为什么并行任务不应该等待陌生人
影响因子：
--
作者：
Tiago Cogumbreiro;R. Surendran;F. Martins;Vivek Sarkar;V. Vasconcelos;M. Grossman
通讯作者：
M. Grossman
关于具有控制效应的连续性的推理
DOI：
10.1145/73141.74837
发表时间：
1989
期刊：
Proceedings of 1993 IEEE 17th International Computer Software and Applications Conference COMPSAC '93
影响因子：
--
作者：
P. Jouvelot;D. Gifford
通讯作者：
D. Gifford
与 future 和 state 的响应式并行
DOI：
10.1145/3385412.3386013
发表时间：
2020
期刊：
Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation
影响因子：
--
作者：
Muller, Stefan K.;Singer, Kyle;Goldstein, Noah;Acar, Umut A.;Agrawal, Kunal;Lee, I-Ting Angelina
通讯作者：
Lee, I-Ting Angelina
NESL 的可证明时间和空间高效的实现
DOI：
10.1145/232627.232650
发表时间：
1996
期刊：
Proceedings of the 19th International Symposium on Principles and Practice of Declarative Programming
影响因子：
--
作者：
G. Blelloch;John Greiner
通讯作者：
John Greiner