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

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

• 批准号: 1703541
• 负责人: Joseph Devietti
• 金额: $ 42.34万
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-07-01 至 2021-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1703541&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.

如果您曾经想过“嗯，我的计算机上次没有这样做”，那么您可能已经经历了计算机科学家所说的非确定性。如今，大多数计算机硬件以非确定性的方式执行程序：一个程序可能会在不同的运行中产生不同的输出或行为，给定完全相同的输入，有时会带来灾难性的后果。最近的研究在固有的非确定性系统中执行确定性执行。不幸的是，这通常以陡峭的性能价格出现。同样，到目前为止，确定性仅适用于非交互式程序。该项目的目的是提高并发程序确定性执行的效率，并在确定性执行的范围内包括大量的交互式程序。从长远来看，目标是使确定性计算成为可行的选择，而无确定性是当今唯一的选择。这可能会提高在当今和明天的多核心设备上运行的大量多线程程序的安全性和质量。为了将确定性执行的好处带入现实世界程序，该项目研究了算法，运行时系统，操作系统，操作系统和硬件支持，以提高确定症的性能和适用性。该项目沿三个主要的力量组织：打击时钟以确定性的逻辑时钟偏斜，这些时钟施加了不必要的等待线程，使用猜测来打破当前系统对同步操作施加的串行瓶颈，并扩展确定性的范围，以包含交互式应用程序。研究人员计划公开分发为该项目构建的系统，以促进其他研究人员的检查，并与计算机系统教育相结合。

项目成果

Monadic composition for deterministic, parallel batch processing

• DOI: 10.1145/3133897
• 发表时间: 2017-10
• 期刊: Proceedings of the ACM on Programming Languages
• 作者: Ryan G. Scott;O. N. Leija;Joseph Devietti;Ryan Newton

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

Deterministic Atomic Buffering

确定性原子缓冲

• DOI: 10.1109/micro50266.2020.00083
• 发表时间: 2020
• 期刊: 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO
• 作者: Chou, Yuan Hsi;Ng, Christopher;Cattell, Shaylin;Intan, Jeremy;Sinclair, Matthew D.;Devietti, Joseph;Rogers, Timothy G.;Aamodt, Tor M.
• 通讯作者: Aamodt, Tor M.