ACM通信
研究突出了
乐观并行需要抽象
如果我们能够自动并行顺序程序，为多核处理器编写软件的问题将大大简化。虽然对自动并行化的研究已经有几十年了，但它只在稠密矩阵计算等少数应用领域取得了成功。特别是不规则程序的自动并行化，这些程序是围绕大型的、基于指针的数据结构(如图表)组织起来的，这似乎很难解决。
伽罗瓦项目正在重新审视自平行化。我们不是试图并行化所有程序，不管它们写得多么晦涩，而是设计编程抽象，使程序员能够突出利用顺序程序中的并行性的机会，并构建一个使用这些提示并行执行程序的运行时系统。在本文中，我们描述了一个基于这些思想的系统的设计和实现。在两个实际的不规则应用中，Delaunay网格细化应用和一个执行聚集聚类的图形应用的实验结果表明，该方法是有前景的。
1.简介
悲观主义者在每个机会中看到困难;乐观者在困难中看到机会。
温斯顿·丘吉尔爵士
不规则应用程序是围绕基于指针的数据结构(如图和树)组织起来的，在一些重要的应用领域(如有限元素、SAT求解器、maxflow计算和编译器)中普遍存在。原则上，可以使用线程库(如pthreads)或编译器指令和库的组合(如OpenMP)来为不规则的应用程序编写并行代码，但众所周知，由于内存一致性模型、同步、数据竞争等的复杂性，编写显式并行代码可能非常棘手。多线程游戏引擎Unreal 3的设计者Tim Sweeney估计，Epic Games编写多线程代码的成本是软件成本的三倍3.)．
从并行计算的早期开始，人们就认识到，避免编写显式并行代码的一种方法是auto-parallelization．10在这种方法中，应用程序程序员编写顺序程序，把它留给编译器或运行时系统来提取和利用程序中的潜在并行性。关于自动并行化的算法和机制，有大量的文献，但就像皮兰德娄戏剧中的角色一样《六个寻找作者的角色，他们中的大多数都在寻找可以并行化的程序。它们可以分为两类:编译时技术和运行时技术。编译时技术使用静态分析来找到程序中的独立计算，并成功地并行化了有限类不规则程序，如n体方法。1，5，20.运行时技术使用乐观并行化:计算被推测地并行化，运行时系统检测并发计算之间的冲突，并根据需要回滚它们，以保持程序的顺序语义。乐观并行性是用于并行事件驱动模拟的流行Timewarp算法的基础，9但是建立基于乐观并行化的通用系统的努力，例如线程级猜测(TLS)，19，22，24取得了有限的成功。由于这些问题，近年来对自平行化的兴趣减弱。
我们对自动并行化有了新的认识，但是从一个不同于该领域以前工作的角度。Galois项目没有试图并行所有的应用程序，不管它们写得多么晦涩，而是专注于以下问题。
- 我们能否设计出能够捕获程序中最常见的并行模式的顺序编程抽象?
- 如果是这样，需要什么系统支持来自动并行化使用这些抽象的程序?
一个有用的类比是关系数据库编程。SQL程序员将数据视为扁平的表(关系)，并使用联接和投影等高级操作对数据进行操作。在数据库系统内部，使用b -树、索引结构等以非常复杂的方式实现关系，并且使用锁和事务并行执行高级操作，但是关系抽象使这些复杂的操作对SQL程序员隐藏起来。
对于不定期的申请，我们可以进行类似的项目吗?虽然我们还远远没有一个完整的解决方案，但是并行性的重要模式的解决方案的轮廓正在从迷雾中浮现出来。在本文中，我们着重于理解和利用并行性迭代不规则的应用程序。在第2节中，我们描述了两个这样的应用程序中的并行模式:一个Delaunay网格细化代码2以及图形应用程序23执行聚集集群。17在第3节中，我们讨论了利用这种并行性的伽罗瓦编程模型和运行时系统。在第4节中，我们将评估系统在两个应用程序上的性能。最后，在第5节中，我们讨论了结论和正在进行的工作。
2.两个不规则的应用程序
在本节中，我们将描述在两个不规则应用中利用并行性的机会:Delaunay网格细化，2和烧结的集群17在图形应用程序中使用。23这些应用程序分别执行细化和粗化，这可以说是批量修改不规则数据结构最常见的两种操作。
2.1.德劳内网格细化
二维Delaunay网格细化算法的输入是平面内某一区域的三角剖分，其中所有三角形都满足一种称为Delaunay条件的几何性质。2根据某些几何标准，这些三角形的形状可能很糟糕;例如，过大的三角形可能会导致不可接受的离散化误差在有限元解决方案。网格细化的目标是通过用更小的三角形替换这些形状不好的三角形来消除网格中的这些三角形。然而，在一个坏的三角形上执行这个操作可能会违反相邻三角形的Delauanay条件，因此有必要找到所有受影响的三角形(这被称为腔然后重新测量整个洞的角度。图1左边显示初始网格(形状不好的三角形为黑色，空腔为灰色)，右边显示精制网格。优化可能会产生新的形状不好的三角形，但至少在2D中，有一个数学上的保证，如果重复这个过程，最终会产生一个没有坏三角形的网格。最终网格的结构可能取决于消除坏三角形的顺序，但由这个过程产生的任何网格都是可以接受的。
图2显示网格细化的伪代码。可以很自然地围绕包含坏三角形的工作列表组织程序，如第3行和第4行所示。该工作列表是网格细化的两种关键数据结构之一。另一种是表示网格结构的图;网格中的每个三角形都表示为一个节点，图中的边表示网格中的三角形邻接。
利用并行的机会Delaunay网格细化是一个相对复杂的代码，因为中心数据结构是一个图，在算法执行过程中反复修改。尽管如此，由于不重叠的空腔可以并行处理，因此在算法中可能会有很多并行性图1．如果两个腔重叠，就必须按某种顺序依次处理。网格细分的并行度有多大?我们的研究11已经表明，对于一个包含10万个三角形的网格，其中大约一半的初始三角形形状不好，有超过256个三角形可以并行处理，直到几乎执行结束。
2.2.烧结的集群
第二个问题是烧结的集群，一个著名的数据挖掘算法。17该算法用于处理大量光源的图形应用。23
聚类算法的输入是(1)数据集和(2)数据集中项目之间相似性的度量。聚类的目标是构造一棵二叉树系统树图其层次结构暴露了数据集中项之间的相似性。图3(一个)显示了一个包含平面上点的数据集，数据点之间的相似性度量是欧氏距离。该数据集的树状图显示在图3 (b)而且(c)．
聚类可以通过迭代算法进行:在每一步中，数据集中最近的两个点聚在一起，并由代表新聚类的单个新点替换数据集中的两个新点。这个新点的位置可以用启发式方法确定。17当数据集中只剩下一个点时，算法终止。算法的伪代码如图4．该算法在优先队列上迭代，其条目是点<的有序对。x, y>,这样y最近的邻居是x(我们称之为最近的(x))．在每次while循环的迭代中，优先级队列最前面的点(最接近的点对)被聚集在一起。这两个点被一个新的、有代表性的点所取代。确定该点的最近邻居，并进入优先队列。
为了找到一个点的最近邻居，我们可以在每一步扫描整个数据集，但这太低效了。相反，我们使用一种空间加速度结构，称为kdtree寻找最近的邻居。kd-树在算法开始时构建，并随着空间中点的移除和添加而保持更新，如图4．
利用并行的机会:由于每次迭代聚类在当前数据集中的两个最近的点，它可能看起来是固有的顺序算法。然而，如果我们考虑中的数据集图3(一个)，我们看到它指向一个而且b,点c而且d可以并发集群，因为两个集群都不影响另一个集群。直观地说，如果树形图是一棵又长又细的树，那么独立的迭代可能很少，而如果树形图是一棵茂密的树，那么可以利用并行性，因为树可以自底向上并行地构建。在Delaunay网格细化的情况下，并行性是非常依赖数据的。在两万盏灯的图形场景实验中，我们发现平均可以同时构建约100个簇11；因此，可以利用大量的并行性。
2.3.讨论
现有的不规则程序编译时并行化技术是基于形状分析，20.它确定数据结构中的结构不变量。网格细分中的图没有特定的结构，在循环的每次迭代中也会进行修改图2，因此编译时并行化不适用于此应用程序。半静态方法使用inspector-executor模型18将计算划分为两个阶段:检查阶段确定工作单元之间的依赖关系，并构建计算进度，执行阶段并行执行结果进度。这种方法不能用于网格细化，因为当底层图被算法修改时，依赖结构会发生变化。
这些考虑表明，在运行时检测依赖关系的完全动态方法需要并行化代码，如网格细化和聚集聚类。Hudson等人提出了一种并行网格细化的方法，8它的步骤如下:(1)在不修改图的情况下计算所有坏三角形的空腔;(2)构建干涉图，其中节点表示空腔，边表示重叠的空腔;(3)在干涉图中找到一个最大的独立节点集;(4)并行地重新排列这些节点对应的空腔，不需要任何同步。这些步骤在新的网格中重复，直到收敛。这种方法可以看作是一种扩展的检查器-执行器方法，其中检查器和执行器的执行是交错的。然而，这种方法对于Delaunay网格细化是非常特殊的。例如，不清楚它是否可以用于类似于在优先级队列上执行迭代的聚合集群的应用程序。
3.伽罗瓦的方法
第2节的分析表明，乐观并行是在不规则应用程序中利用并行的唯一通用方法，在这种方法中，计算将推测地并行执行，并在运行时系统检测到依赖冲突时有选择地回滚。在本节中，我们讨论乐观并行化需要与适当的编程抽象相结合，我们将描述这些思想在伽罗瓦系统中的实现。
如果我们考虑中的网格细化代码，对编程抽象的需求就变得很明显图2．坏三角形的工作列表决定了顺序程序处理坏三角形的特定顺序，该代码的任何自动并行版本都将被迫以相同的顺序处理坏三角形。实际上，坏三角形可以以任何顺序处理，这对并行化很重要，但在这段代码中没有这一点。抽象地说，我们可以把每个坏三角形的处理看作是对图的一个操作，用于修改图的一小块区域;坏三角形可以以任何顺序处理的事实，相当于断言这个算子对图的应用程序彼此“交换”。由于最终的图的结构实际上可能会因运算符的不同排序而不同，我们称其为特定于应用程序的交换性原因很明显。
利用交换性的机会也可能出现在抽象数据类型(ADT)实现中。考虑使用链表实现的一组ADT。对于集合的语义，插入操作相互转换，因为所有的插入顺序都会产生相同的集合，即使对于不同的插入顺序，ADT内部的链表表示可能不同。在这种情况下，交换性源于这样一个事实:可能有几个具体(记忆)状态代表一个抽象状态。利用这种ADT交换性显然需要面向对象的语言。
我们将具体应用程序和ADT交换性称为语义交换性．相比之下，传统的编译时并行化技术，如依赖性分析10以及迪尼兹和里纳尔的交换性分析4专注于具体的交换性其中所有执行操作的顺序都导致相同的具体状态。语义交换性更为普遍，它允许更多的操作交错。
本节介绍的编程抽象允许程序员强调利用语义交换的机会。它们可以添加到任何顺序的面向对象语言中(本文的结果来自于c++的实现)。图5(一个)是伽罗瓦系统的概念图。应用程序使用两个被称为伽罗瓦setiterators，以强调利用并行性的机会。第3.2节描述了数据结构库。有机会利用ADT交换性的数据结构被实现国类，而其他类则在catch-and-keep类。运行时系统实现了乐观并行化，并从可能不安全的共享对象访问中检测和恢复，如3.3节所述。
3.1.伽罗瓦集迭代器
伽罗瓦编程模型是顺序的、面向对象的;程序是用面向对象的语言(如c++或Java)编写的，使用两个称为伽罗瓦集迭代器的结构进行扩展。
- 无序集迭代器:对集合S中的每一个e执行B(e)
对于集合s中的每个元素e执行循环体B(e)，因为集合元素是没有顺序的，这个构造函数断言在循环的串行执行中，迭代可以以任何顺序执行。迭代之间可能存在依赖关系，例如在Delaunay网格细化的情况下，但任何执行迭代的串行顺序都是允许的。当一次迭代执行时，它可以向S添加元素。 - 有序集迭代器:对Poset S中的每一个e做B(e)
该构造函数在部分有序集(Poset) S上迭代。它与上面的集合迭代器类似，不同的是，任何执行顺序都必须遵守Poset S施加的部分顺序。
注意，在遍历集合时可能会向其添加新元素，这在SETL或Java等语言中的传统集合迭代器中是不允许的。图6展示了Delaunay网格生成的客户端代码。这段代码没有使用坏三角形的工作列表，而是使用了一组坏三角形和一个集合迭代器。因为集合元素是没有顺序的，所以允许迭代器以任何顺序遍历集合。因此，伽罗瓦版本证明了一个事实:坏三角形是可以处理的任何秩序，这个事实在更传统的规则中是不存在的图2．由于篇幅不足，我们没有展示聚类的伽罗瓦版本，但它以明显的方式使用了有序集迭代器。
并行执行模型如图5 (b)．主线程执行伽罗瓦集迭代器之外的所有代码。当它遇到伽罗瓦集迭代器时，它会使用工作线程来帮助并发地执行迭代。对线程的迭代赋值是动态完成的，但是这个策略可以由专业的程序员更改。12线程通过迭代器末尾的barrier同步进行同步。
对于这种执行模型，主要的技术问题是确保并行执行遵循迭代器的顺序语义。对于无序集迭代器，这可以通过确保每次迭代的执行具有事务性语义．这些语义保证可串行性；并行执行的行为就好像迭代是按某种顺序连续执行的。对于有序集迭代器，还必须确保迭代按照集合元素的顺序所规定的顺序执行。保证顺序语义是一个非常重要的问题，因为每次迭代都可能读写共享内存中的对象，因此我们必须确保这些读写是适当协调的。接下来，我们将描述这是如何实现的。
3.2.伽罗瓦库类
标准库有两种类:catch-and-keep和catch-and-release。在Java中，锁与每个对象自动关联，但这两种类的锁策略是不同的。
Catch-and-Keep类: Catch-and-keep类是默认的，它们是在伽罗瓦中使用著名的两阶段锁定策略的变体实现的。要在catch-and-keep对象上调用方法，迭代必须首先获得与其关联的锁。这个锁一直保持到迭代结束，此时迭代释放它的所有锁。如果一个迭代无法获得对象上的锁，这意味着第二个迭代当前正在访问该对象，并且必须回滚这两个迭代中的一个。回滚是通过在修改对象之前复制对象，并在回滚时从该副本恢复来完成的。因此，在所有对象都使用catch-and-keep策略的系统中，很容易确保迭代的序列化。获取和释放锁，创建对象的备份副本，等等，都由我们的运行时系统自动执行，如3.3节所述。也可以使用硬件事务内存(TM)。7
虽然catch-and-keep类很容易实现，但它们可能无法提供足够的并发性。工作集本身就是数据结构，它们是使用伽罗瓦库中的类来实现的。由于每个迭代在开始时从工作集获得一个元素，并可能在结束时向其添加元素，所以工作集类的catch-and-keep实现一次只允许执行一个迭代。
国类:为了解决这个问题，Galois系统支持对并发访问的对象(如网格细化中的图和工作集，或聚集聚类中的kd-tree)的捕获和释放策略。要访问捕获-释放对象，迭代必须获得该对象上的锁。然而，与catch-and-keep不同的是，只要方法完成，锁就会被释放。释放锁允许从不同迭代中交叉调用方法，从而提高了并发性。
catch-and-release的关键问题是确保方法交错不违反迭代的可序列化性。中的程序证明了这一点图7，它显示了对支持的集合进行的迭代操作添加，删除,包含，使用标准语义。在图7 (a)，我们可以看到在任何顺序执行中，调用包含(x)将返回false。但是，对于图中所示的交错，调用将返回true。另一方面，对于在图7 (b)，所有可能的方法交错匹配串行执行。对于“捕获-释放”对象，我们如何确定哪些交错是合法的，哪些应该被禁止?
关键是语义交换，这在本节的开始部分已经描述过。通过两个迭代对给定对象的方法调用可以安全地交叉，只要最终的抽象状态与迭代执行的某些串行顺序一致。在图7 (a),调用包含(x)不与来自其他线程的操作交换，因此来自两个迭代的调用不能交叉。在图7 (b)，包含(y)与其他操作交换，这样迭代就可以并行执行。注意交换性可能取决于方法的参数或返回值。
因为迭代是并行执行的，所以交换性冲突可能会导致迭代无法完成，从而需要回滚迭代。因为语义交换性不跟踪对象的具体状态，简单地创建具体状态的副本(如catch-and-keep类)是不够的。相反，catch-and-release对象的每个可以修改该对象状态的方法都必须有一个关联的逆方法，该方法可以消除该方法调用的副作用。例如，对于不包含x，与添加元素的方法调用相反x到集合的方法调用是从该集合中删除它。在交换性的情况下，与我们的目的有关的是逆语义有意义;连续调用一个方法及其逆函数可能无法恢复具体的数据结构。
请注意，当一个迭代回滚时，它在回滚期间调用的所有方法都必须成功。因此，在调用逆方法时绝不能遇到冲突。当伽罗瓦系统检验交换性时，它也用相关的逆方法检验交换性。把它们放在一起: ADT交换性和撤销必须由类设计者指定。图8说明如何在Galois中为实现集合的类指定此信息。对于每个方法，实现者指定如下:
- 通勤:该部分指定当前方法在哪些条件下与其他哪些方法进行通信。例如,
删除(x)通勤与添加(y)，只要元素不同。 - 逆:该部分指定当前方法的逆函数。
请注意,添加(x)通勤时不带添加(x)根据这个规范。这是因为回滚添加(x)需要调用删除(x)，这将与其他调用的添加(x)．这种选择简化了实现。
3.3.运行时系统
Galois运行时系统有两个组件:(1)全局结构，称为提交池它负责创建、中止和提交迭代和(2)结构冲突日志它检测当交换性条件被违反的捕获和释放对象。
提交池维护一个迭代记录所示,图9，用于系统中每个正在进行的迭代。迭代的状态可以是运行,清债信托公司(准备好提交),或流产．线程进入提交池以获得一次迭代。提交池创建一个新的迭代记录，从迭代器中获取下一个元素，根据元素的优先级给迭代记录分配一个优先级(对于set迭代器，所有元素都具有相同的优先级)，并将迭代记录的状态字段设置为运行．当一个迭代调用一个共享对象的一个方法时，(1)该对象的冲突日志被更新，如下所述;(2)关联的逆方法的回调被推到迭代记录的撤销日志上。如果检测到交换性冲突，提交池将在冲突的迭代之间进行仲裁，并中止迭代，以允许优先级最高的迭代继续执行。在取消迭代的撤消日志中执行回调，以撤消它们对共享对象的影响。一旦线程完成了一次迭代，该迭代的状态字段就被更改为清债信托公司，线程被允许开始一个新的迭代。当完成的迭代在系统中具有最高的优先级时，它被允许提交。可以看到，提交池的角色类似于无序处理器中的重新排序缓冲区。
冲突日志:冲突日志是检测交换性冲突的机制。每个捕获和释放对象都有一个冲突日志。对象冲突日志的一个简单实现是一个列表，其中包含当前执行迭代(称为“未完成调用”)对该对象进行的所有调用的方法签名(包括输入和输出参数的值)。当迭代我尝试调用一个方法米1在对象上，将方法签名与冲突日志中所有未完成的调用进行比较。如果日志中的条目没有与米1，然后检测交换性冲突，并开始仲裁过程，以确定应该终止哪些迭代，如下所述。如果米1的签名与日志中的所有条目进行转换米1追加到日志中。当我终止或提交冲突日志中的所有条目我从冲突日志中删除。
考虑呼叫的影响包含(x)中所示接口的集合图8．冲突日志包含集合上所有未完成的方法调用。因为包含只能与添加或删除，运行时系统将扫描日志，以确保没有调用其他迭代添加(x)或删除(x)．
请注意，为了提高效率，运行时系统可能使用冲突日志的优化实现，它不需要对所有未执行的方法调用进行完整扫描来检测冲突。本文的完整版本更详细地描述了其中一些优化。14
提交池:当一个迭代尝试提交时，提交池会检查两件事:(1)该迭代在提交队列的最前面，(2)该迭代的优先级高于正在被迭代的集合/Poset中的所有剩余元素。如果两个条件都满足，迭代就可以成功提交。如果条件不满足，迭代必须等待，直到它在系统中具有最高优先级;状态设置为清债信托公司，线程被允许开始另一个迭代。
当一个迭代成功提交时，运行该迭代的线程还检查提交队列，以查看是否有更多的迭代清债信托公司状态可以提交。如果是这样，它在开始执行新的迭代之前提交那些迭代。当一个迭代必须中止时，它的记录的状态被更改为流产，但是提交池没有采取进一步的行动。当这些迭代对象到达头部时，将惰性地从提交队列中删除。
冲突仲裁:提交池的另一个职责是仲裁迭代之间的冲突。在无序集上迭代时，在发生冲突时选择回滚哪个迭代是无关紧要的。为了简单起见，我们总是选择检测到冲突的迭代。然而，当在有序集上迭代时，低优先级迭代必须回滚，而高优先级迭代必须继续。如果不这样做，就可能出现死锁。因此,当迭代我1调用共享对象上的方法，并通过迭代检测到冲突我2，提交池根据两次迭代的优先级进行仲裁。如果我1优先级较低，它只执行标准的回滚操作。正在执行的线程我1然后开始一个新的迭代。
这种情况是复杂的我2是必须回滚的迭代。因为Galois运行时函数在用户级，所以无法回滚在另一个线程上运行的迭代。相反,我1解除的影响我2没有显式回滚执行。接下来,我1设置一个标志我2告诉它回滚。当线程运行时我2调用共享方法或尝试提交时，它检查此标志并完成回滚。
当一个迭代必须中止时，撤销日志中的回调将按照后进先出的顺序执行。注意，回调函数使用的参数在创建回调函数时必须有相应的值。这是由于撤消日志的后进先出顺序而确保的，因为以后对参数的任何更改将首先撤消。
3.4.讨论
在当前TLS系统中没有类似的无序集迭代器或捕获-释放对象22，24(事实上，这些系统中的大多数自动并行化了FORTRAN和C语言的程序，它们没有数据抽象的概念)。这可能是这些系统性能有限的原因。
Herlihy and Moss的TM纸7激发了大量关于交易和TM的文献(参见Larus和Rajwar15更重要的结果的调查)。事务性方法的起点是显式并行程序，重点是通过使用事务性模型来降低同步的复杂性和开销。相反，我们的起点是一个顺序程序，重点是自动并行化。Galois运行时系统利用乐观并行性，就像TM利用乐观同步一样。可以使用硬件TM以较低的开销实现catch-and-keep类，但必须在软件中支持catch-and-release类。Herlihy和Koskinen最近在TM to软件中引入了捕获和释放对象提高它的性能。6
镍等。16提出用开放嵌套事务和抽象锁定扩展传统事务模型，以允许更抽象的冲突检查。开放式嵌套是机制，它没有指定应该如何使用抽象锁。语义交换为数据结构的语义冲突提供了合适的定义，而开放嵌套是实现语义交换的一种可能的方法。
4.评价
我们最初的伽罗瓦系统是用c++实现的。我们的评估平台是一个4处理器，1.5 GHz的Itanium 2，每个处理器有16KB的L1、256KB的L2和3MB的L3缓存。线程库是pthreads。
4.1.德劳内网格细化
我们首先编写了一个没有锁、线程等的顺序Delaunay网格细化程序参考实现。然后我们实现了一个Galois版本(我们称之为meshgen)，以及一个显式并行的细粒度锁程序(备受)，在单个三角形上使用锁。伽罗瓦版本使用set迭代器和3.3节描述的运行时系统。在这三种实现中，网格都是由一个图形表示的，该图形被实现为一组三角形，其中每个三角形维护其邻居的一组。对于meshgen，交换性检查的代码被手工添加到这个图类中;最终，我们希望从高级交换性规范中自动生成这些代码图8．我们使用STL队列来实现工作集。我们将这些meshgen和FGL的默认实现称为meshgen (d)而且备受(d)．
为了了解调度策略对性能的影响，我们实现了另外两个版本，备受(右)而且meshgen(右)，其中工作集由返回工作集随机元素的数据结构实现。
输入数据集是使用Jonathan Shewchuk的三角程序自动生成的。21它有10156个三角形和边界段，其中4837个三角形是坏的。
执行时间和加速:五种实现在安腾电脑上的执行时间见图10 (a)．参考版本是单处理器上最快的。在四个处理器上，FGL(d)和FGL(r)的性能差别很小。Meshgen(r)的表现几乎和FGL一样好，尽管令人惊讶的是，Meshgen(d)的速度是FGL的两倍。
提交和中止迭代的统计信息:为了更好地理解这些问题，我们确定了不同版本meshgen的提交和中止迭代的总次数，如下所示图10 (b)．在一个处理器上，meshgen执行和提交了21918次迭代。由于set迭代器固有的不确定性，meshgen并行执行的迭代次数每次运行都不同(如果调度策略不同，在一个处理器上也会出现相同的效果)。因此，我们运行了大量的代码，并确定了提交和中止迭代的数量分布。图10 (b)在四个处理器上，meshgen(d)执行的迭代次数与在一个处理器上执行的迭代次数大致相同，但由于空腔冲突而中止的迭代次数也几乎相同。meshgen(r)的中止率要低得多，因为调度策略减少了处理器之间发生冲突的可能性。meshgen(d)和meshgen(r)的性能差异主要是由于中止比较低。因为FGL代码是精心手工调优的，所以迭代失败的成本大大低于mesh - gen的相应成本，所以FGL(r)的性能只比FGL(d)好一点。
随机调度策略可能是有益的，这似乎有悖直觉，但对腔冲突来源的深入调查表明，这个问题可能归因于我们使用STL队列来实现工作集。当一个坏三角形被算法细化时，一个更小的坏三角形簇可能会在空腔内产生。在队列数据结构中，这些新的坏三角形彼此相邻，因此它们很可能被安排在一起在不同的处理器上细化，从而导致空腔冲突。从这些实验得出的一个结论是，领域知识对于实现一个好的调度策略是无价的。
开销崩溃:伽罗瓦系统在引用代码上引入了一些开销，即使运行在一个处理器上;Meshgen (r)在相同的输入上执行引用代码要多花58%的时间。为了理解Galois实现的开销，我们使用PAPI对代码进行了插装。我们将伽罗瓦开销分成四类:(1)提交开销，(2)中止开销，(3)调度开销，包括仲裁冲突的时间，以及(4)交换性检查开销。结果，如所见图10 (c)，表明大约四分之三的伽罗瓦开销用于执行交换性检查。很明显，减少这种开销是减少Galois运行时总体开销的关键。
4.2.烧结的集群
对于聚集性聚类问题，两种主要的数据结构是kd树和优先队列。kd-tree接口本质上与set相同，但加入了最近邻居(最近的)方法。优先队列是Poset的一个实例。由于优先级队列用于排序迭代，因此删除和插入操作(得到而且添加，分别)由提交池编排。
为了评估聚合聚类算法，我们修改了一个名为lightcuts的现有图形应用程序，它提供了一种可伸缩的照明方法。23该代码基于考虑欧几里得距离、光强度和光方向的距离度量来构建一个光层次结构。我们修改了轻量级集群代码中使用的对象，使用Galois接口和Posetiterator来构建树。结果代码的整体结构在图4．我们将这个伽罗瓦版本称为treebuild．的运行时间进行了比较treebuild针对顺序参考的版本。
图11给出性能结果。这些结果与第4.1节中讨论的Delaunay网格生成结果相似，因此我们只描述需要注意的地方。中的执行时间图11 (a)表明尽管优先级队列的顺序依赖，伽罗瓦系统仍然能够暴露大量的并行性。允许我们这样做的机制是提交池，它允许线程开始执行迭代，即使较早的迭代还没有提交。在单处理器上，伽罗瓦系统带来的开销是44%。我们看到，由于管理提交池的开销，调度程序占了总体伽罗瓦开销的很大一部分，如图11 (c)．
4.3.正在进行的工作
在最近的工作中，我们引入了逻辑的概念数据分区进入伽罗瓦体系。13对于网格细化，图的每个分区都映射到一个核心，每个核心在自己的分区中处理坏三角形。这种映射减少了冲突的可能性，因为不同的核心工作在图的不同区域;与第4节中讨论的随机调度不同，这种方法还促进了引用的局部性。此外，可以用锁定分区来替换代价昂贵的交换性检查。图的过度分解增加了一个核心需要工作的可能性，即使它的一些分区被其他处理跨多个分区的空腔的核心锁定了。然而，负载平衡比基线方法更成问题。我们还开发了一个调度框架，使程序员能够控制Galois运行时使用的调度策略。12
我们用Java生成了一个新的伽罗瓦系统的实现，它包含了这些更改。然后，我们评估了网格细化的实现，使用100,000个三角形的输入网格。图12展示了该实现在128核Sunfire系统上的性能，规范化为普通Java的顺序实现。我们可以看到，Galois系统能够实现64核的显著加速，超过64核，负载不平衡和通信延迟开始主导性能。
5.结论
本文介绍了一种新的不规则应用程序自动并行化方法——伽罗瓦系统。无论程序写得多么晦涩，我们的系统都没有试图并行化所有的程序，而是提供了编程抽象，程序员使用这些抽象来突出利用并行性的机会。运行时系统使用乐观并行化来利用程序员强调的并行执行机会。它检测并发计算之间的冲突，并适当地回滚计算，以保留程序的顺序语义。在两个实际的不规则应用中，Delaunay网格细化应用和一个执行聚集聚类的图形应用的实验结果表明，该方法是有前景的。
应该将伽罗瓦方法视为不规则应用程序的基线并行实现。许多不规则应用程序的手写并行版本利用这些应用程序中的特定类型的结构来减少并行开销。我们如何识别在非常规项目中利用结构的机会?编译器能自动执行相关的优化吗?如何减少运行时开销?这些都是一些令人兴奋的研究机会。
这项工作部分得到了美国国家科学基金会0833162、0719966、0702353、0724966、0739601和0615240的资助，以及IBM和英特尔公司的资助。
参考文献
1.伯克，M.，卡里尼，P.，崔，j . d。过程间指针别名分析．技术报告IBM RC 21055, IBM约克敦高地，1997。
2.保证曲面的网格生成质量。在SCG’93:第九届计算几何年会论文集(1993), 274280。
3.对更强处理能力的追求:单核CPU注定要失败吗?http://www.anandtech.com/cpuchipsets/showdoc.aspx?I=2377, 2005年2月。
4.交换性分析:并行化编译器的一种新的分析技术。ACM反式。掠夺。朗。系统。19， 6(1997)， 942991。
5.Ghiya, R.， Hendren, L.它是树、dag还是循环图?堆指向指针的形状分析POPL,1996年。
6.事务促进:一种用于高并发事务对象的方法。在并行编程原理与实践(PPoPP), 2008年。
7.事务性内存:无锁数据结构的架构支持。在第20届计算机体系结构国际年会论文集(1993)。
8.Hudson, B.， Miller, g.l.， Phillips, T.稀疏并行Delaunay网格优化。在SPAA(2007)。
9.杰斐逊，dr。虚拟时间。ACM反式。掠夺。朗。7系统。， 3(1985)， 404425。
10.Kennedy, K.， Allen, J.编辑。为现代架构优化编译器:基于依赖的方法．2001年摩根考夫曼。
11.Kulkarni, M.， Burtscher, M.， Inkulu, R.， Pingali, K.， Cascaval, C.在不规则应用中有多少并行性?在并行编程原理与实践(PPoPP), 2009年。
12.Kulkarni, M.， Carribault, P.， Pingali, K.， Ramanarayanan, G.， Walter, B.， Bala, K.， Chew, L.P.不规则程序乐观并行执行的调度策略。在并行架构与算法研讨会(2008)。
13.Kulkarni M.， Pingali, K.， Ramanarayanan, G.， Walter, B.， Bala, K.， Chew, L.P.乐观并行得益于数据分区。SIGARCH第一版。Archit。新闻36， 1(2008)， 233243。
14.Kulkarni, M.， Pingali, K.， Walter, B.， Ramanarayanan, G.， Bala, K.， Chew, L.P.乐观并行需要抽象。42 . SIGPLAN Not (PLDI论文集2007， 6(2007)， 211222。
15.J. Larus, R. Rajwar。事务性存储器(计算机体系结构综合讲座)．Morgan & Claypool出版社，2007年。
16.Ni, Y.， Menon, V.， Adl-Tabatabai, A.-R。，Hosking, A.L., Hudson, R., Moss, J.E.B., Saha, B., Shpeisman, T. Open nesting in software transactional memory. In并行编程原理与实践(PPoPP), 2007年。
17.谭庞宁，m.s.，库马尔，V.编辑。数据挖掘概论．Pearson Addison Wesley, 2005年。
18.Ponnusamy, R.， Saltz, J.， Choudhary, A.，数据分区和通信调度复用的运行时编译技术。在1993年ACM/IEEE超级计算会议论文集(1993)。
19.LRPD测试:用私有化和缩减并行化来推测循环的运行时并行化。IEEE反式。Distrib平行。系统。， 2(1999)， 160180。
20.刘志强，刘志强，刘志强。用破坏性更新法求解语言中的形状分析问题。在第23届美国计算机学会程序设计语言原理年会论文集(圣彼得堡海滩，佛罗里达，1996年1月)。
21.shwchuk, J.R. Triangle:设计一个2D高质量网格生成器和Delaunay三角测量器。在《应用计算几何:走向几何工程的第1148卷计算机科学课堂讲稿．1996年5月,203222年。
22.Steffan, j.g.， colhan, c.b.， Zhai, A.， Mowry, T.C.线程级推测的可扩展方法。在ISCA '00:第27届计算机体系结构国际年会论文集(2000)。
23.Walter, B.， Fernandez, S.， Arbree, A.， Bala, K.， Donikian, M.， Greenberg, D. Lightcuts:一种可扩展的照明方法。ACM反式。图形(SIGGRAPH) 24， 3(2005年7月)，10981107。
24.张荣勇，张志强，张志强，等。分布式共享内存多处理器中推测运行时并行化的硬件。在第4届国际高性能计算机体系结构研讨会论文集(1998)。
©2009 acm 0001-0782/09/0900 $10.00
允许制作本作品的全部或部分的数字或硬拷贝用于个人或课堂使用，但前提是该拷贝不是为了盈利或商业利益而制作或分发，并且该拷贝在第一页上带有本通知和完整引用。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定的许可和/或付费。
数字图书馆是由计算机协会出版的。版权所有©2009 ACM有限公司
没有发现记录