Robustness against Relaxed Memory Models (R2M2)
Robustness against Relaxed Memory Models (R2M2)
批准号:
241337241
负责人:
Professor Dr. Roland Meyer
金额:
$0.0万
依托单位国家:
德国
项目类别:
Research Grants
财政年份:
2013
资助国家:
德国
项目状态:
已结题
起止时间:
2012-12-31 至 2016-12-31
中文摘要
出于性能方面的原因,现代多处理器实现了宽松的内存模型,允许程序顺序超序和非存储原子执行。虽然数据竞争自由程序对这些放松并不敏感,但它们对底层并发库的开发构成了一个严重的问题。在顺序一致性下正常工作的例程在松弛的内存模型上运行时会显示出不希望看到的效果。例如,如果程序顺序稍微放松,互斥锁算法就会失败。我们说,这些程序对处理器支持的松弛不是很健壮。为了加强健壮性,程序员必须在控制硬件的代码中添加安全网指令,这项任务已被证明是困难的,即使对专家来说也是如此。随着多处理器的广泛使用,并发库在日常编程中变得越来越重要,健壮性开始成为一个关键问题。我们建议开发算法来检查和加强程序在放松内存模型下的健壮性。假设有一个记忆模型和一个给定的程序,我们的过程决定松弛的行为是否符合顺序一致性语义。如果不是这样,他们就会合成加强健壮性的安全网指令。当构建到编译器中时,我们的算法因此对程序员隐藏了放松的内存模型,并提供了顺序一致的错觉。由于问题中的两个无界性来源,检查健壮性是具有挑战性的。首先,为了确保分析独立于体系结构参数(如写缓冲区的大小),我们不能假定程序顺序松弛的界限。其次,基于类似的论点,我们不能假设一个库的客户端数量是有限的,尽管这个数字在实际处理器中是有限的。该项目努力为健壮性分析做出理论和实践贡献。从理论上讲,我们的目标是开发一种证明健壮性的可计算性和复杂性结果的方法。其思想是将关于宽松计算的组合推理与语言理论方法相结合。发展这样一个普遍的理论是有充分理由的。未来几代处理器将带来新的内存模型,我们在这里开发的技术应该会延续到这些体系结构中。事实上,我们的第二个目标是将证明方法应用于实践。我们解决了针对流行的POWER处理器的健壮性问题,这些处理器具有高度宽松的内存模型。此外,我们还研究了在未知环境中工作的并行库的健壮性。研究违反健壮性的计算的组合性质。在此基础上,发展语言理论技术来判定健壮性。将该方法应用于针对功率处理器的健壮性检验。扩展该方法以检查并发库的健壮性。
英文摘要
For performance reasons, modern multiprocessors implement relaxed memory models that admit out~of~program~order and non~store atomic executions. While data race free programs are not sensitive to these relaxations, they pose a serious problem to the development of the underlying concurrency libraries. Routines that work correctly under sequential consistency show undesirable effects when run on relaxed memory models. Mutex algorithms, for example, fail if the program~order is relaxed slightly. We say that these programs are not robust against the relaxations that the processor supports. To enforce robustness, the programmer has to add safety net instructions to the code that control the hardware ~ a task that has proven to be difficult, even for experts. With the widespread use of multiprocessors, concurrency libraries become increasingly important in everyday programming and robustness is starting to be a key concern.We propose to develop algorithms that check and enforce robustness of programsagainst relaxed memory models. Assuming a memory model and given a program, ourprocedures decide whether the relaxed behaviour coincides with the sequential consistency semantics. If this is not the case, they synthesize safety net instructions that enforce robustness. When built into a compiler, our algorithms thus hide the relaxed memory model from the programmer and provide the illusion of sequential consistency.Checking robustness is challenging due to two sources of unboundedness in the problem. First, to ensure the analysis is independent from architectural parameters (like the size of write buffers), we cannot assume a bound on the program~order relaxations. Second, and with a similar argument, we cannot assume a bound on the number of clients to a library ~ although this number is finite in actual processors.The project strives for theoretical as well as practical contributions to robustness analysis. From a theoretical point of view, our goal is to develop a proof method for computability and complexity results about robustness. The idea is to combine combinatorial reasoning about relaxed computations with language~theoretic methods. Developing such a general theory is well justified. Future processor generations will come with new memory models, and the techniques we develop here should carry over to these architectures. Indeed, our second goal is to apply the proof method in practice. We address robustness against the popular POWER processors that have a highly relaxed memory model. Moreover, we study robustness for concurrency libraries that act in an unknown environment.To sum up, the central goals of our project are the following.1. Investigate combinatorial properties of computations that violate robustness.2. Based on this, develop language~theoretic techniques to decide robustness.3. Apply the method to check robustness against POWER processors.4. Extend the method to check robustness of concurrency libraries.
期刊论文(5)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
Effect Summaries for Thread-Modular Analysis
线程模块化分析的效果摘要
DOI:
10.1007/978-3-319-66706-5_9
发表时间:
2017
期刊:
影响因子:
--
作者:
[L. Holík, R. Meyer, T. Vojnar, S. Wolff]
通讯作者:
S. Wolff
Pointer Race Freedom
指针竞赛自由
DOI:
10.1007/978-3-662-49122-5_19
发表时间:
2016
期刊:
影响因子:
--
作者:
[F. Haziza, L. Holík, R. Meyer, S. Wolff]
通讯作者:
S. Wolff
DOI:
10.4230/lipics.fsttcs.2013.127
发表时间:
2013
期刊:
ArXiv
影响因子:
--
作者:
[G. Călin, E. Derevenetc, R. Majumdar, R. Meyer]
通讯作者:
R. Meyer
Robustness against Power is PSpace-complete
抗功率鲁棒性是 PSpace 完备的
DOI:
10.1007/978-3-662-43951-7_14
发表时间:
2014
期刊:
影响因子:
--
作者:
[E. Derevenetc, R. Meyer]
通讯作者:
R. Meyer
Lazy TSO Reachability
惰性 TSO 可达性
DOI:
10.1007/978-3-662-46675-9_18
发表时间:
2015
期刊:
ArXiv
影响因子:
--
作者:
[A. Bouajjani, G. Călin, E. Derevenetc, R. Meyer]
通讯作者:
R. Meyer
Effective Denotational Semantics for Synthesis
-
批准号:417532197
-
项目类别:Research Grants
-
资助金额:$0.0万
-
财政年份:2018
-
负责人:Professor Dr. Roland Meyer
-
依托单位:
The Polish Dative as a test case for linguistic theory
-
批准号:277311979
-
项目类别:Research Grants
-
资助金额:$0.0万
-
财政年份:2015
-
负责人:Professor Dr. Roland Meyer
-
依托单位:
The history of pronominal subjects in the languages of northern Europe
-
批准号:448476652
-
项目类别:Research Grants
-
资助金额:$0.0万
-
财政年份:--
-
负责人:Professor Dr. Roland Meyer
-
依托单位:
Modelling the question-statement opposition in Slavic languages (QueSlav)
-
批准号:452148050
-
项目类别:Research Grants
-
资助金额:$0.0万
-
财政年份:--
-
负责人:Professor Dr. Roland Meyer
-
依托单位:
海外基金