CPA-SEL: Collaborative Research: Trace-Driven Verification of Multithreaded Software

CCF-0811287/CCF-0810865协作研究：多线程软件的跟踪驱动验证杨子江和Karem Sakallah超线程的使用越来越多，廉价的多处理器硬件的可用性为软件开发人员带来了巨大的机遇和严峻的挑战。为了使软件应用程序受益于多核处理器中持续的指数吞吐量增长，应用程序必须是编写良好的多线程软件程序。不幸的是，编写能够释放当前和未来硬件系统全部潜力的多线程软件程序在今天仍然像30年前一样具有挑战性。本研究的目的是开发实用的工具和方法，可以降低测试/调试多线程程序的复杂性的水平相媲美的测试/调试顺序程序。为此，现有的调试工具必须增强强大的推理引擎，使他们能够隐式地分析所有可能的线程交织在指定的测试输入。在这个项目的过程中，各种方法来实现这一目标将进行调查，包括一些新的想法，似乎特别有前途的初步分析：（1）有效的符号编码的多线程程序，（2）跟踪驱动的抽象和细化其执行，（3）性能增强技术，使这种方法扩展到现实的程序大小。

CCF-0811287/CCF-0810865Collaborative Research: Trace-Driven Verification of Multithreaded SoftwareZijiang Yang and Karem SakallahThe ever increasing use of hyper-threading and the availability of inexpensive multiprocessor hardware present tremendous opportunities as well as serious challenges for software developers. In order for software applications to benefit from the continued exponential throughput advances in multicore processors, the applications must be well-written multithreaded software programs. Unfortunately, writing multithreaded software programs that can unleash the full potential of present and future hardware systems remains as challenging today as it was thirty years ago. This research aims to develop practical tools and methodologies that can bring down the complexity of testing/debugging multithreaded programs to a level comparable to that of testing/debugging sequential programs. To this end, existing debugging tools have to be enhanced with powerful reasoning engines that allow them to implicitly analyze all possible thread interleavings under the specified test inputs. During the course of this project a variety of approaches to achieve this objective will be investigated, including some novel ideas that seem particularly promising from a preliminary analysis: (1) efficient symbolic encoding of multithreaded programs, (2) trace-driven abstraction and refinement of their execution, and (3) performance enhancement techniques that allow this approach to scale to realistic program sizes.