CSR: SHF: Medium: Collaborative Research: New Horizons in Deterministic Execution

CSR：SHF：媒介：协作研究：确定性执行的新视野

• 批准号: 1703425
• 负责人: Jakob Eriksson
• 金额: $ 47.34万
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-07-01 至 2021-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1703425&HistoricalAwards=false
• 关键词: CSR; SHF; Medium; Collaborative; Research

If you have ever thought to yourself "huh, my computer didn't do that last time", you may have experienced what computer scientists call non-determinism. Today, most computer hardware executes programs in a non-deterministic fashion: a program may yield different output or behavior in different runs, given the exact same input, sometimes with disastrous consequences. Recent research enforces deterministic execution in inherently non-deterministic systems. Unfortunately, this often comes at a steep performance price. Also, until now determinism is only available for non-interactive programs. The goal of this project is to improve the efficiency of deterministic execution of concurrent programs, and to include a large class of interactive programs in the scope of deterministic execution. Longer term, the goal is to make deterministic computing a viable choice, where nondeterminism is the only option today. This would likely improve both the safety and quality of the vast number of multithreaded programs running on today's and tomorrow's multicore devices.To bring the benefits of deterministic execution to real-world programs, this project investigates algorithms, runtime systems, operating systems and hardware support to improve the performance and applicability of determinism. The project is organized along three major thrusts: combating the clock skew in deterministic logical clocks that imposes unnecessary waiting on threads, using speculation to break the serial bottleneck that current systems impose on synchronization operations, and extending the scope of determinism to encompass interactive applications. The researchers plan to openly distribute the systems built for this project to facilitate examination by other researchers and integration with computer systems education.

如果你曾经对自己说：“哈，我的电脑上次没有这样做”，你可能已经经历了计算机科学家所说的非决定论。今天，大多数计算机硬件以非确定性的方式执行程序：给定完全相同的输入，程序在不同的运行中可能会产生不同的输出或行为，有时会带来灾难性的后果。最近的研究在固有的非确定性系统中强制执行确定性执行。不幸的是，这往往是在一个陡峭的性能价格。此外，到目前为止，决定论只适用于非交互式程序。这个项目的目标是提高并发程序的确定性执行的效率，并将一大类交互式程序纳入确定性执行的范围。从长远来看，目标是使确定性计算成为一种可行的选择，而非确定性是当今唯一的选择。这可能会提高安全性和质量的大量多线程程序运行在今天和明天的多核设备。为了使确定性执行的好处，现实世界的程序，这个项目研究算法，运行时系统，操作系统和硬件支持，以提高性能和适用性的确定性。该项目的组织沿着三个主要的推力：打击时钟偏差确定性逻辑时钟，不必要的等待线程，使用投机打破串行瓶颈，目前的系统同步操作，并扩大范围的确定性，包括交互式应用程序。研究人员计划公开发布为该项目构建的系统，以方便其他研究人员进行检查，并与计算机系统教育相结合。

项目成果

Frequent background polling on a shared thread, using light-weight compiler interrupts

• DOI: 10.1145/3453483.3454107
• 发表时间: 2021-06
• 期刊: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation
• 作者: Nilanjana Basu;C. Montanari;Jakob Eriksson

Lazy Determinism for Faster Deterministic Multithreading

用于更快确定性多线程的惰性确定性

• DOI: 10.1145/3297858.3304047
• 发表时间: 2019
• 期刊: Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems
• 作者: Merrifield, Timothy;Roghanchi, Sepideh;Devietti, Joseph;Eriksson, Jakob
• 通讯作者: Eriksson, Jakob