SHF: Small: Adapting Dataflow Analysis for Efficient and Precise Parallel Program Monitoring

由于整个行业都在转向多核处理，未来的应用程序只有以并行软件的形式编写才能运行得更快(即，单个程序的工作是通过在不同的处理器上同时执行该工作的不同部分来完成的)。不幸的是，历史告诉我们，编写并行软件对程序员来说是一项非常容易出错的任务。为了应对这一挑战，该研究项目正在创建一种强大的新机制来识别并有望修复大规模生产系统上的并行软件中的错误。希望得到的框架不仅将支持现有监控工具的并行执行，还将催生新的强大工具类别，这些工具可以识别并行软件中的细微错误。这样的工具可以帮助程序员继续获得未来微处理器的性能优势，从而继续实现越来越快的计算对经济、科学和技术以及我们在互联网连接的世界中的日常生活所带来的所有好处。更具体地说，这个项目的重点是复杂的在线程序监控工具，它以逐条指令的粒度模拟编程正确性的各个方面。为了在性能、精度和方便性之间取得实际的平衡，本研究开发了一个新的框架，该框架引入了显式的“不确定性窗口”，并结合了一种新的方法来避免分析中的状态空间爆炸(灵感来自Tarjan的数据流分析的区间分析方法)。

Due to the industry-wide shift to multi-core processing, futureapplications will only run faster if they are written as parallelsoftware (i.e. where the work for a single program is accomplished bysimultaneously performing different parts of that work on differentprocessors). Unfortunately history has taught us that writingparallel software is a very error-prone task for programmers. Toaddress this challenge, this research project is creating a powerfulnew mechanism for identifying and hopefully fixing bugs in parallelsoftware on large-scale production systems. Hopefully the resultingframework will not only support the parallel execution of existingmonitoring tools, but it will also spawn the creation of new classesof powerful tools that can recognize subtle bugs in parallel software.Such tools can help programmers continue to reap the performancebenefits of future microprocessors, thereby continuing to enable allof the benefits that increasingly-faster computation has had on theeconomy, science and technology, and our everyday lives in anInternet-connected world.More specifically, the focus of this project is on sophisticatedonline program monitoring tools that model various aspects of programcorrectness at an instruction-by-instruction granularity. To strike apractical balance between performance, precision, and convenience forthe tool developer, this research has developed a novel framework thatintroduces explicit "windows of uncertainty" combined with a newapproach for avoiding a state space explosion in the analysis(inspired by Tarjan's interval analysis approach to dataflow analysis).