The Galois Approach to Optimistic Parallelization

从现在起，所有处理器都将由大量的处理核心组成，只有在这些核心上能够并行运行的程序才能快速运行。然而，在程序中找到并行性是一项非常困难的工作，而且只在科学计算等有限的领域取得了成功。在更一般的不规则程序领域，操纵大型基于指针的数据结构(如图形)的成功还很少。Galois项目将实施和评估一种基于乐观并行化和来自库作者的少量信息来并行化这种不规则程序的新方法。在Delaunay网格生成等问题上的初步结果是非常有希望的。众所周知，操纵基于指针的数据结构的不规则程序很难并行化。Galois项目正在为这类程序的乐观并行执行实现一种新的方法。Galois编程模型是一种基于对象的共享内存模型。Galois有三个主要方面：(I)用于将乐观并行化打包为数据结构操作的少量语法构造，(Ii)关于类库中的方法的断言，以及(Iii)用于检测乐观计算对共享内存进行的不安全访问并从中恢复的运行时系统。该项目的资金将用于开发验证类库断言的技术，并继续实施Galois系统。

From now on, all processors will consist of a large number of processing cores, and programs will run fast only if they can run in parallel on these cores. However, finding parallelism in programs is a very difficult job, and has succeeded only in limited domains like scientific computing. There have been few successes in the more general domain of irregular programs that manipulate large pointer-based data structures like graphs. The Galois project will implement and evaluate a new approach to parallelizing such irregular programs based on optimistic parallelization and a small amount of information from library writers. Preliminary results on problems like Delaunay mesh generation are very promising.Irregular programs that manipulate pointer-based data structures are known to be difficult to parallelize. The Galois project is implementing a novel approach for optimistic parallel execution of such programs. The Galois programming model is an object-based shared-memory model. There are three main aspects to Galois: (i) a small number of syntactic constructs for packaging optimistic parallelization as data structure manipulations, (ii) assertions about methods in class libraries, and (iii) a runtime system for detecting and recovering from unsafe accesses made by an optimistic computation to shared memory. The funding for this project will be used to develop techniques for verifying class library assertions, and continuing the implementation of the Galois system.