Modular reasoning for deterministic parallelism
Modular reasoning for deterministic parallelism
复制标题
确定性并行的模块化推理
DOI：
10.1145/1925844.1926416
复制
发表时间：
2011
影响因子：
--
通讯作者：
Dodds M
中科院分区：
文献类型：
--
作者：
Dodds M
将并发控制协议编织到程序中是困难且容易出错的。减轻这种负担的一种方法是确定性并行。在这种研究方法并行化，顺序程序注释的部分，可以同时执行，自动注入控制结构，用于确保可观察到的行为与原始program.This一致的形式规范和验证这些结构。我们的高级规范定义了正确执行所必需的条件;这些条件反映了确保确定性行为所必需的程序依赖性。我们连接高层次的规范所使用的客户端的图书馆与低层次的图书馆实施，以证明客户端的要求，确定性的强制执行。值得注意的是，我们可以在不打破抽象边界的情况下推理程序和库的正确性。为了实现这一点，我们使用基于分离逻辑的并发抽象谓词来封装库实现中的行为。为了允许通用规范的库，可以实例化的客户端程序，我们扩展了逻辑与高阶参数和量化。我们表明，我们的高级别规范抽象的细节，确定性并行验证两个不同的低级别实现的库。
Weaving a concurrency control protocol into a program is difficult and error-prone. One way to alleviate this burden isdeterministic parallelism. In this well-studied approach to parallelisation, a sequential program is annotated with sections that can execute concurrently, with automatically injected control constructs used to ensure observable behaviour consistent with the original program.This paper examines the formal specification and verification of these constructs. Our high-level specification defines the conditions necessary for correct execution; these conditions reflect program dependencies necessary to ensure deterministic behaviour. We connect the high-level specification used by clients of the library with the low-level library implementation, to prove that a client's requirements for determinism are enforced. Significantly, we can reason about program and library correctness without breaking abstraction boundaries.To achieve this, we useconcurrent abstract predicates, based on separation logic, to encapsulate racy behaviour in the library's implementation. To allow generic specifications of libraries that can be instantiated by client programs, we extend the logic with higher-order parameters and quantification. We show that our high-level specification abstracts the details of deterministic parallelism by verifying two different low-level implementations of the library.
登录
查看更多内容
使用 Heap-Hop 跟踪跳跃的堆
DOI：
10.1007/978-3-642-12002-2_23
发表时间：
2010
期刊：
Proceedings of the 7th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering
影响因子：
--
作者：
Jules Villard;É. Lozes;Cristiano Calcagno
通讯作者：
Cristiano Calcagno
DOI：
10.1145/1275497.1275499
发表时间：
2007-01-01
影响因子：
1.3
作者：
Biering, Bodil;Birkedal, Lars;Torp-Smith, Noah
通讯作者：
Torp-Smith, Noah
使用分支帧属性验证事件驱动程序
DOI：
10.1145/1708016.1708025
发表时间：
2010
期刊：
Rehabilitation Counselors and Educators Journal
影响因子：
--
作者：
N. Krishnaswami;L. Birkedal;Jonathan Aldrich
通讯作者：
Jonathan Aldrich
无死锁通道和锁
影响因子：
2.8
作者：
K. R. M. Leino;Peter Müller;Jan Smans
通讯作者：
Jan Smans