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.