General Language Mechanisms for Deterministic Parallel Programming

0702724 Vikram S.AdveUniversity of Illinois@Urbana如今大多数新的消费者电脑至少有两个内核，高端电脑多达八个，主要供应商的路线图预计会有数百个内核。要利用这种处理能力，并行计算，曾经是一种狭隘的专业，必须成为主流。然而，并行编程是出了名的困难。为了避免程序员生产力的昂贵下降，编程语言、库和工具必须使并行编程几乎与顺序编程一样容易。实现这一目标的一种有效方法是启用确定性风格的并行编程，这意味着无论何时使用特定的输入运行程序，都可以保证生成相同的输出。决定论消除了并行编程中最困难的问题，如数据竞争和死锁。最重要的是，它使质量保证更容易，因为每个输入只需要测试一次执行，而且错误更容易重现。虽然存在确定性编程模型，但它们的表达能力有限，不能处理大多数用Java和C#等广泛使用的语言编写的程序。这项研究正在开发简单、富有表现力的语言和运行时机制，用于确定性并行，使用带有可变对象别名的线程并行风格。该设计结合了类型系统中用于声明和检查内存区域和效果的最新进展，在使用类型系统难以表达或无法表达的情况下依靠运行时推测。该项目还在开发各种机制，以允许“局部非确定性”构造，如联合约简和互换数据结构更新。最后，该项目将发展以确定性风格编写现实的并行程序的经验，以回答许多关于确定性语言特性的表现力、易用性和性能影响的实际问题。

0702724Vikram S. AdveUniversity of Illinois @ UrbanaMost new consumer computers today contain at least two cores, high-end ones have as many as eight, and major vendor road-maps foresee hundreds of cores. To exploit this processing power, parallel computing, once a narrow specialty, must become mainstream. Parallel programming, however, is notoriously difficult. To avoid an expensive decline in programmer productivity, programming languages, libraries, and tools must make parallel programming nearly as easy as sequential programming. One powerful way to achieve this goal will be to enable a deterministic style of parallel programming, meaning that a program is guaranteed to produce the same output whenever it is run with a particular input. Determinism eliminates the hardest problems of parallel programming such as data races and deadlocks. Most importantly, it makes quality assurance easier because only one execution for each input must be tested and because errors are easier to reproduce. While deterministic programming models exist, they have limited expressivity and do not handle most programs written in widely-used languages such as Java and C#.This research is developing simple, expressive language and runtime mechanisms for deterministic parallelism, using a thread-parallel style with aliasing of mutable objects. The design combines recent advances in type systems for declaring and checking memory regions and effects, falling back on runtime speculation in cases that are burdensome or impossible to express using the type system. The project is also developing mechanisms to allow ``locally non-deterministic'' constructs such as associative reductions and commutative data structure updates. Finally, the project will develop experience with writing realistic parallel programs in a deterministic style, to answer many practical questions about the expressivity, ease-of-use, and performance implications of the deterministic language features.