CAREER: Making Threads More Deterministic by Memoizing Schedules

在多核硬件的兴起和即将到来的云计算风暴的推动下，多线程程序正变得越来越重要。不幸的是，这些程序仍然难以编写、测试和调试。造成这种困难的一个关键原因是不确定性：多线程程序的不同运行可能显示不同的行为，这取决于线程的交错方式。不确定性使多线程程序的每个开发步骤都变得复杂。例如，它削弱了测试，因为测试的时间表可能不是在现场运行的时间表；它使调试变得复杂，因为再现一个有缺陷的时间表是困难的。在过去的三十年里，研究人员开发了许多技术来解决不确定性问题。尽管做出了这些努力，但在商用多处理器上实现通用多线程程序的效率和确定性仍然是一个开放的挑战。本项目旨在解决这一根本性的挑战。它的关键观点是可以重用少量的调度来处理大量的输入。基于这种见解，它采用了一种称为计划记忆的方法，该方法可以记住过去的计划，并在可能的情况下为未来的运行重用它们。这种方法平摊了将一个调度确定为多个重用的高开销，并使程序尽可能重复熟悉的行为。与这种方法类似的现实世界是，动物的自然倾向是遵循熟悉的路线，以避免危险和发现未知路线的额外费用。这个项目最大的影响将是一种新颖的方法和新的、有效的系统和技术，以提高软件的可靠性，从而使每个企业、政府和个人受益。

Multithreaded programs are becoming increasingly critical driven by therise of multicore hardware and the coming storm of cloud computing.Unfortunately, these programs remain difficult to write, test, and debug.A key reason for this difficulty is nondeterminism: different runs of amultithreaded program may show different behaviors depending on how thethreads interleave. Nondeterminism complicates almost every developmentstep of multithreaded programs. For instance, it weakens testing becausethe schedules tested may not be the ones run in the field; it complicatesdebugging because reproducing a buggy schedule is hard.In the past three decades, researchers have developed many techniques toaddress nondeterminism. Despite these efforts, it remains an openchallenge to achieve both efficiency and determinism for generalmultithreaded programs on commodity multiprocessors.This project aims to address this fundamental challenge. Its key insightis that one can reuse a small number of schedules to process a largenumber of inputs. Based on this insight, it takes an approach calledschedule memoization that memoizes past schedules and, when possible,reuses them for future runs. This approach amortizes the high overhead ofmaking one schedule deterministic over many reuses and makes a programrepeat familiar behaviors whenever possible. A real-world analogy to thisapproach is animals' natural tendencies to follow familiar routes to avoidhazards and discovery overhead of unknown routes.The greatest impact of this project will be a novel approach and new,effective systems and technologies to improving software reliability, thusbenefiting every business, government, and individual.