The Galois Approach to Optimistic Parallelization

从现在开始，所有的处理器都将由大量的处理核心组成，只有当程序能够在这些核心上并行运行时，它们才能运行得很快。然而，在程序中寻找并行性是一项非常困难的工作，并且仅在科学计算等有限领域取得了成功。在操作大型指针数据结构（如图）的不规则程序的更一般领域中，很少有成功案例。Galois项目将实现并评估一种基于乐观并行化和库编写者提供的少量信息的新方法来并行化这种不规则程序。在Delaunay网格生成等问题上的初步结果是很有希望的。众所周知，操作基于指针的数据结构的不规则程序很难并行化。伽罗瓦项目实现了一种乐观并行执行这类程序的新方法。伽罗瓦编程模型是一种基于对象的共享内存模型。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.