The Galois Approach to Optimistic Parallelization

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

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.