CAREER: Making Threads More Deterministic by Memoizing Schedules

职业生涯：通过记忆时间表使线程更具确定性

• 批准号: 1054906
• 负责人: Junfeng Yang
• 金额: $ 64.16万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-02-01 至 2017-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1054906&HistoricalAwards=false
• 关键词: CAREER; Making; Threads; More; Deterministic

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.

多核硬件的兴起和即将到来的云计算风暴的推动下，多线程程序变得越来越重要。不幸的是，这些程序仍然难以编写、测试和调试。造成这种困难的一个关键原因是不确定性：多线程程序的不同运行可能会显示不同的行为，这取决于线程如何交织。 非确定性使多线程程序的几乎每一个开发步骤都变得复杂。 例如，它削弱了测试，因为测试的时间表可能不是在现场运行的时间表;它使调试复杂化，因为复制一个错误的时间表是困难的。在过去的三十年里，研究人员已经开发了许多技术来解决不确定性。 尽管有这些努力，它仍然是一个开放的挑战，以实现通用多线程程序在商品多处理器的效率和确定性。 它的核心思想是可以重用少量的调度来处理大量的输入。 基于这一认识，它采用了一种名为schedule memoization的方法，这种方法可以记住过去的计划，并在可能的情况下在将来的运行中重用它们。 这种方法分摊了在多次重用中使一个调度具有确定性的高开销，并使程序尽可能重复熟悉的行为。 这一方法的一个现实类比是动物遵循熟悉路线的自然倾向，以避免危险和发现未知路线的开销。该项目的最大影响将是一种新颖的方法和新的，有效的系统和技术，以提高软件的可靠性，从而使每一个企业，政府和个人受益。