CAREER: Making Threads More Deterministic by Memoizing Schedules

在多核硬件和云计算风暴的驱动下，多线程程序变得越来越关键。不幸的是，这些程序仍然很难编写、测试和调试。这种困难的一个关键原因是不确定性：多线程程序的不同运行可能会显示不同的行为，这取决于线程的交织方式。不确定性使多线程程序的几乎每一个开发步骤都变得复杂。例如，它削弱了测试，因为测试的时间表可能不是在现场运行的时间表；它使调试变得复杂，因为复制有错误的时间表很难。在过去的30年里，研究人员开发了许多技术来解决不确定性。尽管做出了这些努力，但在商品多处理器上实现通用多线程程序的效率和确定性仍然是一个开放的挑战。本项目旨在解决这一根本挑战。它的关键洞察力在于，人们可以重复使用少量的时间表来处理大量的输入。基于这一认识，它采取了一种称为日程备忘录的方法，即记录过去的日程安排，并在可能的情况下，在未来的跑步中重复使用它们。这种方法消除了在多次重用上确定一个时间表所带来的高开销，并使程序尽可能重复熟悉的行为。与这种方法在现实世界中的类比是，动物的自然倾向是遵循熟悉的路线来避免未知路线的危险和发现开销。该项目最大的影响将是一种新的方法和新的、有效的系统和技术来提高软件可靠性，从而使每个企业、政府和个人受益。

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.