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

如果你曾经想过“嗯，我的计算机上次没有做到这一点”，你可能经历过计算机科学家所说的非决定论。今天，大多数计算机硬件以非确定性的方式执行程序：给定完全相同的输入，程序在不同的运行中可能产生不同的输出或行为，有时会带来灾难性的后果。最近的研究在固有的非确定性系统中加强了确定性执行。不幸的是，这往往是以高昂的性能代价为代价的。此外，到目前为止，决定论仅适用于非交互式程序。该项目的目标是提高并发程序的确定性执行效率，并将大量交互式程序纳入确定性执行范围。从长远来看，目标是使确定性计算成为一种可行的选择，而非确定性是目前唯一的选择。这可能会提高当前和未来多核设备上运行的大量多线程程序的安全性和质量。为了将确定性执行的好处带到现实世界的程序中，该项目研究了算法、运行时系统、操作系统和硬件支持，以提高确定性的性能和适用性。该项目主要围绕三个重点进行组织：对抗确定性逻辑时钟中的时钟倾斜，这种时钟倾斜会给线程带来不必要的等待；使用推测来打破当前系统对同步操作施加的串行瓶颈；将确定性的范围扩展到交互式应用程序。研究人员计划公开发布为这个项目建立的系统，以方便其他研究人员的考试，并与计算机系统教育集成。

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.