动态依赖分析与分布式一致性的可见性算法

动态依赖分析和分布式一致性的可见性算法迈克尔·鲍尔Nvidiambauer@nvidia.com李元灿Nvidiaonchanl@nvidia.com摘要埃利奥特·斯劳特SLAC国家加速器实验室eslaught@slac.stanford.edu迈克尔·加兰Nvidiamgarland@nvidia.com肖恩·特赖克勒Nvidiasean@nvidia.comAlex Aiken斯坦福大学aaiken@stanford.edu隐式并行程序设计系统必须解决依赖分析和一致性的联合问题，以保证在分布存储机器上运行的应用程序具有表观顺序语义。 在存在数据依赖控制流和任意别名的情况下解决这些问题是大多数现有系统通过妥协其编程模型的表达性和/或其实现的性能而回避的挑战。 我们demonstrate一般类的解决方案，这些问题通过减少从计算机图形的可见性问题。关键词：可视性，军团，动态分析，一致性1介绍隐式并行和分布式编程系统受到需要超级计算机或云进行大规模计算的用户的欢迎，但不熟悉或不愿意开发显式并行和分布式应用程序[2，3，8，14，16，19，29]。 这些系统提供了高生产力的编程模型，基于从隐式分布的集合数据类型（例如数组和嵌套结构）上的计算中自动发现并行性。隐式并行和分布式编程模型的任何实现都有两个主要职责。首先，它必须通过对访问集合子集（我们称之为区域）的特殊计算序列（通常称为运算符或任务）执行依赖分析来发现并行性。访问不相交区域的任务，或以不干扰其他任务的方式访问区域的任务（例如，仅读取数据）可以并行执行第二，系统必须确保区域的一致性，以便任务观察数据的最新更新，与原始程序的顺序共享内存语义一致。在本文中，我们提出并评估了在一般情况下，当区域可以命名集合的任意子集（因此区域可以重叠或别名），当区域本作品采用知识共享署名-非商业性使用-禁止演绎国际4.0许可协议进行许可。PPoPP©2023版权归所有者/作者所有。ACM ISBN979-8-4007-0015-6/23/02。https://doi.org/10.1145/3572848.3577515图1.一种程式化的图计算，任务使用图中节点集合的两个不同分区。动态计算而不是静态指定，并且任务序列由数据相关控制流确定。由于这些要求，我们使用Legion运行时[5]执行我们的实现和评估，因为它支持所有三个特性，这对于许多具有数据依赖行为的应用程序来说这些问题的数据依赖性要求解决方案是动态依赖和一致性分析。大多数现有的系统与这样的分析施加限制，以简化其实现，如要求所有区域是成对独立的。我们将具有此模型的系统称为使用基于名称的一致性，因为每个数据元素必须始终具有唯一的名称（即， 可以仅在一个区域中）;相反，在基于内容的相干系统中，数据元素可以同时是多个区域的一部分。基于内容的一致性比基于名称的一致性更一般：基于内容的一致性可以对每个名称使用单个区域来支持基于名称的一致性。 我们将在第9节中进一步对比基于内容和基于名称的系统。我们的主要技术贡献是，在隐式并行的基于任务的分布式系统中的依赖分析和基于内容的相干性问题与计算机图形学中的可见性问题密切相关（第3节）。在提供了一些背景和1234567891011121314151617struct节点{起来：floatdown：float}任务t1（p Node >，g Node>）：read-writep .up，reduce：：+g.down;任务t2（p Node >，g Node>）：read-writep .down，reduce：：+g.up;任务main（N Node>）：read-writeN .up，N.down;P [1.. 3]- - #创建N的主分区G [1.. 3]- - # createghost partition of Nwhile（*）对于i = 1..3 t1（P[i]，G[i]）对于i = 1..3 t2（P[i]，G[i]）PPoPP(a)主分区（b）幽灵分区（c）区域树图2.图的节点和关联区域树的主分区和幽灵分区。示例程序，我们使用的文件（第2节）的持续时间，我们演示了如何减少这些问题的可见性问题。然后，我们适应三个著名的可见性算法的日益复杂，以解决基于内容的一致性：画家的算法，Warnock的算法，光线投射（第4 - 7节）。 我们评估了所有三种算法在几个不同的应用程序跨机器规模（第8节）。结果表明，光线投射具有最佳的整体性能，具有显著的优势，因此，光线投射算法是Legion项目目前使用的算法最后，我们讨论了相关的工作（第9节），并得出结论（第10节）。2示例和背景在本节中，我们将给出更多关于Legion编程模型[5]的背景，并介绍一个程序，我们将在整篇论文中使用该程序作为运行示例图1中的程序概述了无向图上的典型模拟，说明了支持基于内容的一致性的价值。每个任务访问两个不同的数据子区域：一组形成图的一部分的节点和一组与该部分相邻的幽灵节点。子区域只是区域元素的子集（而不是副本）Legion允许程序通过创建区域的分区来命名子区域，而不是在每次任务启动时计算这些子集[23，25]，在这种情况下，图的节点区域N的P（主要）和G（幽灵）分区是子区域的图2（a）中示出了将图的节点划分为三个不相交的子区域的示例主分区P，其中一种颜色的所有节点属于同一子区域。 主分区可以跨机器映射（例如， 每个子区域被分配给不同的GPU），以使得能够通过子区域上的任务进行并行计算。主分区的每个子区域���的幽灵节点是外部的节点������，至少有一条边连接到这些节点;这些节点表示在模拟过程中必须在图的各个部分之间交换信息的地方。 图2（b）显示了对应于图2（a）中的主分区的幽灵分区。例如，图2（b）中的所有蓝色节点形成了蓝色亚区2（a）。 我们省略了边的划分;节点计算足以说明。请注意，节点的幽灵分区不是一个抽象分区：它是不完整的（一些节点不包括在任何子区域中），一些节点具有多种颜色，因为它们包括在一个以上的子区域中。因此，重影子区域也不是不相交的，并且分区G被称为是混叠的。图2（c）显示了这个程序的区域和分区的安排，它被称为区域树，可以捕捉它们之间的关系：所有节点的集合（根区域N）有两个分区（由标记为P和G的三角形表示），每个分区有三个子区域，代表N中的数据子集。在构建了节点的主分区和幽灵分区之后，图1中的程序进入一个循环，在这个循环中，它在两个阶段t1和t2之间反复交替。给出了这些任务的签名，包括它们对区域字段（结构节点的成员）的影响：t1读取和写入其主要子区域中每个节点的up字段，并对其ghost子区域中每个节点的down字段执行约简（求和）。 任务t2颠倒了up和down字段的角色。很容易检查第16行上的所有三个任务调用是否可以并行执行。首先，在对t1的每次调用中，通过主分区和幽灵分区的访问涉及不同的数据，因为它们向上和向下引用不同的字段。t1任务读取和写入它们的主子区域，这可以并行进行，因为主子区域是不相交的。在t1的不同调用中的重影区域访问可以触及相同节点的down字段（因为一些节点被包括在多于一个重影子区域中），但是访问是归约，因此可以单独执行，并且稍后组合三组结果（例如，当该字段被另一个任务读取时 t2任务（第17行）可以并行运行的理由是对称的。现在想想第16行和第17行之间发生了什么任务第17行上的T2读取通过归约写入第16行上的虚分区的主分区中的下场的值类似地，通过第17行上的幽灵分区的减少动态依赖分析和分布式一致性的可见性算法PPoPP（）⟨ ⟩ ⟨⟩（）⟨ ⟩ (⟨ ⟩ ⟨ ⟩)−−图3.将三维场景渲染为二维图像。通过第16行上的主分区写入的up字段的值。 类似的隐式通信发生在下一次循环迭代的第17行到第16行。 当一个任务使用一个分区写入数据，而另一个任务通过不同的分区读取该数据时，可能会出现复杂的通信模式;隐式并行模型的优势之一是程序员只需要识别数据的所需分区，而不需要显式地管理通信。 这是系统������的责任，guarantee一致性：每个任务的读取看到正确的，当前版本的数据所产生的任务之前，在连续的程序顺序，无论任务安排。正确地将这种顺序放松为并行调度需要分析任务之间的依赖关系。访问相同数据的两个任务之间存在依赖关系，除非这两个任务都读取该数据或都使用相同的关联运算符执行归约。如前所述，虽然Legion支持基于内容的一致性，但大多数系统都不能支持图1中的程序，因为它们是基于名称的，只推理区域的名称而不是它们的内容。因此，所有子区域必须成对不相交以避免别名（没有数据元素可以有一个以上的名称），因此仅支持区域的单个不相交分区[2，8，14，16，19，29]。根据我们的经验，在编写具有数据的多个自然视图（分区）的程序时，基于名称的一致性将迫使至少两种妥协之一图1中的程序可以只使用主分区来编写。在这种方法中，传递幽灵节点需要传递整个图，因为可以传递的唯一单元是命名的子区域;因此，一个折衷方案是以所需的粗粒度命名区域，并接受某些任务将传递比必要更多的数据。一个更有效的策略是创建一组单独的区域，只保存幽灵节点;显式副本管理幽灵节点区域与主分区的一致性，这放弃了隐式通信的优势。3的可见性问题计算机图形学中的可见性是确定场景中哪些图元对象（通常是三角形）对相机可见的问题，因此应该有助于像素的渲染值[10，13，20]。出现并发症因为从照相机的角度来看，一个对象可能在另一个对象的前面或遮挡另一个对象，并且一些对象可能是部分或全部透明的。 图3描绘了从3D场景渲染2D图像的图形中的常见情况。渲染算法解决可见性问题，以计算输出图像中每个像素的值作为场景中的图元和相机位置的函数。只有离相机最近的对象最终才对像素值有贡献，除非某些对象至少部分透明，如图3中的蓝色和红色三角形所示。对象的透明度是其Alpha值，0表示完全透明，1表示完全遮挡，中间的值表示部分透明度。将多个半透明基元的效果累积到像素的过程被称为阿尔法混合。基本的可见性问题是计算沿直线可见的东西假设基本对象是三角形，并且忽略退化情况，场景中的每个三角形与线在零点或一点处相交。与直线共享一个点的三角形可以按照这些点在直线上出现的位置进行排序，如图3所示。在这里，场景中的四个三角形与摄像机的一条线相交于点101到104，其中101最靠近摄像机。由视图沿摄像机的直线定义的像素值为=1，1，2，2，3，3，，4，0，在哪里是混合函数 ，三角形，并且0是用于m的恒等式（即，, ,0=).由于紫色三角形上的点3被遮挡（3=1），因此黑色三角形沿直线不可见;即， =（3.1一致性我们将一致性问题（基于内容或基于名称）归结为计算机图形学中的可见性问题 考虑一个区域的单个元素 ，例如多维数组中的一个点 . 我们假设有一个全局时钟，它为上的任何任务执行的每个操作分配一个时间 。设1，1，. . .，是按递增顺序排列的操作序列。这三种可能的操作是：写操作，它将写赋值给写，其将归约运算符应用于和的当前值，以及读取 ，其读取当前值 。我们在这个序列上定义一个混合函数���������（- 是的- 是的， ） =（2，2，.���������������- 是的- 是的⟨������,������⟩,���(1, ))���（（（考虑一个阅读，阅读。然后1，1，. . .，1，1，0是at time的值，其是沿时间向后延伸的线上的可见性 。视觉透明度在连贯性方面有直接的类比：读取是完全透明的，减少是部分透明的PPoPP∩∅（）（）（）（）–123456789t1（P[1]，G [1]）#0t1（P[2]，G [2]）#1t1（P[3]，G [3]）#2t2（P[1]，G [1]）#3t2（P[2]，G [2]）#4t2（P[3]，G [3]）#5t1（P[1]，G [1]）#6t1（P[2]，G [2]）#7t1（P[3]，G [3]）#8(a) （b）任务更新图4.基于内容的连贯性的可视化。（透明度的在区域的任意子集上使用这些操作的任务程序的执行引起必须分析相干性的时空体积。 我们的约简显示了图形中的可见性和基于任务的系统中的一致性之间的直接对应关系：一个计算空间维度中的可见性，另一个计算时间维度中的可见性。图4（a）示出了六个任务的时间轴，图4（b）示出了每个任务所涉及的阵列的相应部分，其中更新按时间顺序堆叠，最新的更新在顶部。所有更新都是写入（描绘为实心 框） ， 除了执 行减少 的任务 T4和 T6（部分透明框）。当任务T6执行时，T6 图4（b）显示T6需要T5、T4、T3和T2写入的一些数据，但不需要T1，T1的更新被T2遮挡。 在图4（a）中，虚线箭头显示了这种“回顾时间”，以找到写入T6所需的每一段数据的任务。3.2相关解析上面介绍的缩减使用了一个全局时间概念，它对应于任务的顺序执行顺序。需要依赖性分析来将这种顺序次序为执行任务的部分（并行）次序，使得读取的一致性仍然得到保证。回想一下，我们区分了基于内容的连贯和基于名称的连贯。在基于名称的方案中，区域必须是不相交的，并且只有在两个任务之间存在依赖关系，即，如果=，则和之间存在依赖关系。������������在基于内容的一致性中，区域可以重叠，并且只有在重叠���时才可能存在依赖性。基于内容的一致性也很容易支持不规则和稀疏的区域;区域中的元素集不需要是元素的连续子范围。基于内容的一致性的主要成本是发现哪些区域对具有非空交集。仅仅因为两个任务和共享数据并不意味着它们之间存在依赖关系;只有当颠倒任务的执行顺序可能导致错误的结果时，才存在依赖关系。每个任务都声明它是否图5. 图1中main中的初始任务序列。12345678# S是运行时系统的状态run_task（T（P1R1，. . .，P n Rn），S）foreachPi RiR1，. - 是的- 是的 ，Rn：= T（R1，. - 是的-Ri，S：=物化（Pi，Ri，S）foreachPi Ri返回SS：=commit（Pi，Ri，S）图6. 任务执行。读、读和写，或者用特定的归约运算符（例如求和）对其区域参数执行归约Legion运行时使用任务的特权保守地估计两个任务之间是否存在依赖关系[ 5 ];我们省略了细节。图5显示了图1中的主任务执行的前九个任务。 因为我们的分析是动态的，所以运行时系统观察一系列任务启动，并分析其相关性和一致性。 考虑图5第7行的任务6，第一个任务在第二次进入图1第16行的循环时被调用。为了计算B2B6依赖于哪些任务，的参数时，运行库会及时“查看”以前的任务对数据区域的影响。66篇参考文献。在这种情况下，由于任务103、104和105从主分区中读取子分区，所以任务106依赖于任务103、104和105，该子分区可能与这些先前任务对幽灵分区的缩减重叠。 反过来，103依赖于100、101和102，因为103将减少添加到由 这些任务写入的值。出于同样的原因，任务E14和E15也依赖于E10、E11和E12从这个例子中我们可以看出，相关性分析是一致性问题的一个子集。依赖性分析只需要系统证明哪些任务接触了另一个任务可能访问的数据，但它不需要知道元素的实际值，只是可能有共同的元素。例如，在图5中的任务流中，系统将发现在任务02、35和68之间不存在依赖性，从而允许这些任务组并行执行。 对于相干性，我们必须更进一步，计算共同元素的当前值。因此，我们的一致性算法也将提供相关性分析的解决方案4预赛在介绍我们的可见性算法之前，我们首先为它们的表示定义一个通用框架图6定义了动态依赖分析和分布式一致性的可见性算法PPoPP（）•关于我们+（）（）（）−+（）（）⊕/\电子邮件[emailprotected]（） {|⟨⟩ ∈∧ ⟨⟩ ∈∧ （）}（）（）函数run_task接受任务调用T P1R1，. - 是的- 是的、PnRn和运行时系统的当前状态S。这里Pi是T在区域Ri上的特权（见下文）。每个可见性算法都必须提供两个函数物化和提交以及S的实现。为了解释实现和提交，我们需要任务的更多细节一个区域R是一组对 ， 其中 是一个 多维点，是该区域在该点的值。请注意，此定义将区域限制为单个字段。 每个第一组件 可以在集合中最多出现一次。程序使用单个区域A。（实际系统允许任何数量的区域以及每个区域的多个字段，但这种更简单的设置足以说明重要的思想。）域dom（A）={我|<$i，v<$∈ A}是A的第一个分支的集合。• 归约运算符f必须有一个恒等式0f，1234567891011121314151617181920# S是一个历史：（特权，区域）对的列表paint（R，S）#历史从最古老到最新对于P′，R′nS如果P′=read-writethenelseifP′=redue ftenR：=（R<$R′）/R# do nothing if P′= read返回R、 SR：= R f（R/R′，R′/R）.实现（P，R，S）# R [i]对于dom（R）如果P =减少f，则else返回{i，0f|i ∈ dom（R′）}返回油漆（R，S）commit（P，R，S）returnS ++ P， R图7. 画家前[17]。对于一个给定的像素，渲染一个半透明的对象（在所有已经渲染的对象之前支持部分积累。1例如，+=是一个具有标识0的归约运算符并渲染完全遮挡的对象覆盖 。任务调用中的每个特权Pi是读、读写或归约f中的一个，其中f是归约运算符（例如， 求和具有reduce特权）。如果两个具有特权的任务之间存在依赖关系，那么这两个特权会相互干扰唯一不干扰的特权组合是read/read和reducef/reducef，用同一个算子进行两次约简任务的任何区域参数R和R′都必须有不相交的域dom R dom R′=，除非任务只读取两个区域或只使用相同的归约运算符2归约到两个区域。任务的区域参数Ri只指定需要什么数据：dom Ri是索引 的 集 合 ， 由 运 行 时 系 统 填 写 正 确 的 值 。 函 数materialize接受一个区域、它的权限和当前运行时状态，并返回一个具有相同域和当前值的区域; materialize还可以更新状态（图6的第5行）。 运行一个任务会调用region参数上的函数，这可能会更新这些region（第6行）。函数commit记录了为将来的任务调用具体化正确的区域参数所需的信息（第8行）。5画家在接下来的三节中，我们将介绍三种基于计算机图形学可见性算法的相干算法每一种算法都是对前一种算法的改进，因此最先进、性能最好的方法，光线投射，重用了为其他两种算法开发的概念。在计算机图形学中，画家算法通过从后面渲染场景中的对象来1当约简算子是commu时，有一些有趣的优化，画家代码使用三个辅助函数：���/={���，���∈���|{���search（ ）}���\={���，���∈���|���boundary（ ）}���⊕ =���\���∪���换句话说，是与共享点的子集，是与不共享点的子集，是和的并集，使用���������������������图7中的状态S是一个存储区-区域对列表P，R. 初始状态是一个具有一对读写的列表，A是A的初始值。当任务完成时，commit将其区域参数的最终状态附加到S。因此，状态是按时间增加的顺序的操作结果的历史-按程序顺序的第���th个任务调用的所有结果对被列在任务1的结果之前和任务1的结果之后。3paint函数通过遍历历史并对R应用操作来计算区域R的最新状态。对于每个缓存-区域对（第3行），如果特权是读-写，则R的重写部分被替换，而未更新的部分被保留（第5行）。reducef是类似的，除了更新的部分使用归约运算符折叠成R（第7行）。注意，我们将约简算子逐点提升到区域对，=，，，，= . 读操作不需要修改Rmaterialize函数的行为取决于要在R上执行的操作的特权。 对于约简，根本不检查历史，并且将区域初始化为约简运算符的标识-约简在本地累积并且仅在将来应用它们是抽象的和/或联想的，但它们超出了这项工作的范围2处理带有干扰特权的dom Rdom R′的情况需要任务内的一致性，这超出了本文的范围。3.由于区域参数别名的限制，因此对于单个任务调用，区域参数的顺序并不重要。···PPoPP⟨⟩∩∅⟨⟩⟨⟩−−[]−[][][][][][](a)任务t0−2（b）任务t3−5（c）任务t6−8图8.处理任务后的区域树状态如图5所示。呼吁实现。这种懒惰的归约应用很重要，因为它最大限度地减少了数据移动：急切地执行归约需要具体化区域的当前值，在开始执行之前将数据复制到任务的位置，而累积部分归约仅在需要结果时移动数据。相反，对于读或读写操作，系统必须具体化区域的当前值5.1优化和实施图7中的算法简单但效率低。当具体化子区域R时，朴素画家一种更有效的方法是使用区域树作为加速数据结构：我们将历史存储在区域树中，使得可以沿着从区域树的根到R的路径找到与区域R相关的历史更具体地，区域树的每个节点R维护子历史R。h，并且我们保证为了具体化R，具体化路径历史，其是从根到R的路径上的所有历史的串联，以该顺序，产生与朴素画家算法相同的结果。当启动具有区域参数R和特权p的任务t时1.t，p附加到R。H.2. 设R′是R的一个祖先，其子节点为C。如果C是R，则在路径历史中，已经记录在C的子树中的任何任务必须在t，p我们将C的任务历史子树的快照（称为复合视图）附加到R ′。H. 我们删除C中的任务历史，因为它们现在记录在C当遍历路径历史时，复合视图在继续路径的下一个元素之前被遍历（包括任何嵌套的我们可以通过在每个节点R上记录-ing来减少复合视图的数量，无论它是开放的（R的子树中有非空的历史）还是封闭的（R的子树中的所有历史都是空的）。另一个改进是在R处记录R的子树中使用的特权。当执行上面的步骤（2）时，我们可以跳过为关闭的子树或仅具有不干扰t，p的特权的历史的子树创建复合视图。最后，复合视图通常会遮挡较早的复合视图“”，从而允许“”从历史记录中删除由于空间不足，我们省略了识别这种遮挡的保守测试图8给出了一个使用图5中的任务序列的示例。图中的索引指示将任务或复合视图添加到区域树的步骤 当t0被启动时，没有先前的任务，因此该任务被记录在历史中的P处。上升1. 当t1被发射时，我们在P处记录t1. 上涨2没有创建复合视图，因为P是一个不相交的分区，所以P。上升1个百分点。上2=. t2的启动是类似的;图8（a）显示了记录t02之后的区域树状态任务t3使用G. UP1子区域，因此采用具有不同归约特权的区域树的不同路径。 因为P. 上和G。up重叠并且P.up中使用的读写特权干扰t使用的归约特权，则P.up处的子树的复合视图V0被附加到根的历史。尽管G。up是别名分区，t4和t5使用与t3相同的归约特权，因此这些任务被简单地添加到G的历史中。上2和G. 分别为3图8（b）显示了t05启动后的区域树状态。 当 t6启动时，G的另一个合成视图V1up被附加在根上。图8（c）显示了任务t08被分析后区域树的状态区域树和复合视图都是分布式数据结构，由于可伸缩性的原因，部分组件位于不同的节点上。区域树和复合视图中的子区域的数量通常与机器中的节点的数量成正比，因此在单个节点上存储任何这样的数据结构可能非常昂贵。我们自下而上构建复合视图，节点之间的通信最少，以捕获最高级别的状态 由于复合视图在构建后是不可变的，因此我们可以根据需要在机器上安全地复制复合视图的节点。6Warnock画家算法的缺点是，即使进行了优化，具体化区域R也可能导致针对许多历史条目（特别是复合视图）测试R，这些历史条目由于后续更新而不再可见。Warnock它通过执行空间分解来解决可见性问题动态依赖分析和分布式一致性的可见性算法PPoPP123456789101112131415161718192021222324252627282930313233343536# S是一组等价集。#等价集是一个（区域，历史）对。精炼（R，S）S′：= S′对于R，H，N，S如果dom（R ′）≠ dom（R）=然后elseifdom（R）=dom（R）thenS′：=S′{<$R′，H<$}elseS′：=S′{<$R′，H<$}′返回S′S′：=S′{<$R′/R，H，<$R′\R，H}实现（P， R、 S）S′：=finish（R，S）Es：={<$X，H <$∈S′|dom（X）{dom（R）}R：= 0′为您提供最佳使用体验，出于技术、分析及推广目的，如果P =减少f，则elseX：={\displaystyle {\pi，0}}|i ∈dom（R′）}R：返回R、S=RXX：=paint（R′，H）′commit（P，R，S）S′：=S′对于R，H， 在S如果R/ R= R′，则如果P=reead-writeten，elseS′：=S′R′，P，R/R′else#精炼保证sdom（R）dom（R）=S′：=S′R′，H ++P，R/R′′返回S′S′：=S′R′，H\/[编辑]（）（）⟨ ⟩ ∈[][][][][][][][][][][][][−][]−/[][]\ [][]\[]\[][]\[]\[]/ [][]/ [ ]/[]/ [ ] \[][][][]图9. Warnock算法问题[27]。 该算法将场景划分为多个部分，然后确定每个子场景中可见图元的数量。分而治之的方法递归地继续，直到每个子场景中可见的基元的数量是微不足道的（一个或一个小的数字），或者子场景已经被细化到单个像素。 一旦场景被分割成简单的子场景，每个子场景就可以很容易地独立渲染。状态S现在是一组等价集，由一对区域R和历史H组成，具有H中的每个操作都与R的每个元素相关的性质：如果P′，R′H，则dom R dom R′。最初有一个等价集，全局集合A，具有历史读写A。任何两个等价集总是不相交的，所有等价集的并集总是覆盖A。当任务启动时，函数refine根据需要分割等价集，以保持相关的不变量，即每个等价集表示具有相同历史的点集 如果一个任务在一个区域R上工作，该区域与现有的等价集R′有 非 平 凡 的 重 叠，那么R′被分成两个等价集，由R′R和R′R组成（第11行）。然后，我们将画家算法应用于每个等价集（第18-24行），以构建R的物化。在提交函数中可以看到历史的空间分离在任务是写入的情况下，它可以清除任务的先前历史。图10. Warnock算法为任务启动创建的等价集如图5所示等价集，然后将其自身存储为新历史中的唯一条目，从而确保历史是精确的，并且仅包含最近“可见”的任务（第30-31行）。图10给出了Warnock我们只展示了上域的等价集加细序列。 每个等价集���都标记有N.up的子集，该子集���表示以及���导致���被添加到细化树的任务。节点的实线轮廓表示任务一个来自G分区的区域参数（回想图2）。最初，N.up是唯一的等价集。任务t0具有优先级-在P[1]上的ileges. up导致根被细化为N。上P1。上= P1。上，N。上P1。起来 任务t1对P[2].up具有权限，它与P[1].up不相交，因此只有节点N。上P1。up被细化为N。上P1。上P2。上=P 2。上，N。上P1。上 P2。上=P 3。起来在任务t1和t2之后，Warnock任务t3.5在幻影分区子区域G 1.3上工作。 任务t3取G1。作为一个论点。 回想一下G1。up是P1的幽灵节点的集合。上，这意味着G1。up可以与P2共享节点。上，P3。向上（再次参见图2）。因此，t3导致P2。上，P3。在G1中被分裂成幽灵细胞和非幽灵细胞。起来任务t4取G2。up作为参数，这导致子树中的then-leaf节点在P1下。上，P3。有待进一步完善。最后，任务t5需要G3。up作为一个参数，这将导致在P1下的子树中的最终细化。上，P2。起来注意，不是所有的等价集都在P1下的子树中计算. 因为P1。G2、G3和P1。上G2G3是空的。任务t5是图1中循环的第一次迭代的最后一个任务. 每个后续迭代都使用相同的区域，因此不需要对图10中的树进行进一步的细化。PPoPP⟨⟩−[][][][]6.1 优化和实施与 前 一 节 一 样 ， 我 们 可 以 通 过 一 些 优 化 来 大 大 提 高Warnock算法的性能最重要的挑战是加快确定哪些等价集代表给定区域（图9的第16行）。 由于每个等价集总是被细化为覆盖原始等价集的新等价集，因此细化的历史定义了一个搜索树，即包围体层次结构（BVH）[9]。 对于要发现其组成等价集的任何新的子区域R，其在等价集BVH的根节点处开始，测试与任何子节点的交叉，并且递归地遍历任何重叠的子节点。到达的叶节点的集合是例如在程序执行中的该点处执行R的依赖性和一致性分析所需的最近的等价集合。 在执行这个初始遍历之后，我们可以记住组成R. 由于Warnock在程序中稍后使用R的下一个任务可以开始在每个记忆化等价集合处搜索R等价集BVH是一种分布式数据结构。BVH中唯一可变的状态是存储在叶子节点的历史，因此我们可以在整个机器中安全地复制BVH中的中间节点，因为在等价集被细化之后，任何子节点的名称都是不可变的。复制是至关重要的，以避免连续的瓶颈规模时，许多节点试图执行的任务都需要遍历上层的BVH，以确定其子区域的组成等价集7光线投射从历史上看，画家算法是我们实现的第一个相干算法，但由于无法精确地修剪历史的遮挡元素，它具有可扩展性问题，因此随后开发了我们对Warnock算法的适应。 Warnock算法在创建过多等价集时也会导致不同的可伸缩性问题（参见第8节）。我们意识到这些al-tax与计算机图形中的可见性有关，这在早期并不明显，这促使我们研究光线投射（现代渲染中的首选方法）[28]是否比其他方法更好。在光线投射中，光线从图像的每个像素投射到场景中，记录它穿过的对象（如果是半透明的）和最终阻挡它的对象然后将这些交叉点的影响累积起来，以计算像素4的最终值（请参阅图3）。使用光线投射的基于内容的一致性与Warnock4在图形学中，当给表面着色时，递归的“阴影”射线也被投射到表面点处的照明采样。在我们的例子中没有阴影光线的模拟;我们只需要确定可见的任务。1 dominating_write（R，S）2S3返回S'：={ R，[read-write，]}{���R，H ∈ S |dom（R′（R）{\displaystyle\mathbb{ R}′4′5实现（P，R，S）6R′，S′：=Warnock：：materialize（P，R，S）789如果P=reead-writeten，S′：=dominating_write（R′，S′）10returnR′，S′11 commit（P，R，S）12returnwarnock：：commit（ P， R， S）图11. 光线投射算法。的写作。使用Warnock虽然这使得很容易发现哪些等价集代表一个子区域，但它通常会导致在执行写入后具有相同历史的许多等价集。在光线投射方法中，对区域R执行写入的每个任务t创建表示R中的点的新等价集，其中历史最初仅包含读写R。在为写入创建新的等价集R之后，我们修剪被R遮挡的所有等价集。 图11使用了Warnock算法中的物化和提交例程。新函数dominating-write为R创建了一个新的等价集，并修剪了被R遮挡的等价集（第2行）。新的写操作意味着等价集可以被合并和细化。射线投射作为解决两个问题所造成的这些现在的非单调变化的等价集的集合相比，Warnock的算法的主要机制。 为了在支配写函数中修剪等价集，我们使用光线投射来发现被区域R遮挡的等价集（图11的第2行）。此外，我们使用光线投射来发现在物化函数的每次调用中区域R的组成等价集（图9的第16行到图11的第6行），因为等价集的集合在调用之后可能会改变。为每个任务实现物化功能光线投射为图5的任务t1t5产生图10中所示的相同等价集，但是注意，这些等价集被存储在P分区的叶子处，P分区是图1中的示例中唯一不相交且完整的分区。每个循环的第一个任务在P1上具有读写特权。起来 写特权导致P1的任何细化及其历史被丢弃，减少等价集的数量并简化历史，直到再次调用在幽灵区域上操作的任务。P2上具有读写权限的任务。上，P3。类似地合并等价集并简化历史。7.1 优化和实施为了加速光线投射，计算机图形中的实际实现依赖于场景的BVH分解来有效地检测光线相交的对象[9]。由于等价集是通过写入合并的动态依赖分析和分布式一致性的可见性算法PPoPP基于等价集的稳定BVH 相反，我们使用一种启发式方法，根据任务使用的分区来选择根区域的子树，该子树仅具有不相交和完整的分区，这自然定义了BVH。如果应用程序切换到使用具有不相交完全分区的不同子树，则运行库将等价集转移到新的子树。 在极少数情况下，当不存在具有不相交完全分区的子树时，运行时创建K-d树[6]。虽然基于区域子树的BVH数据结构的构造是不同的，但是光线投射的实现的其余部分与Warnock的算法非常相似8绩效评价十多年来，我们已经在Legion运行时中实现和调优了所有三种算法。在开发时，每个实现都在世界上许多顶级超级计算机上进行了测试。 为了进行实验比较不同方法的性能，我们将Regent的最新版本[21]（一种针对Legion的编程语言）反向移植到Legion运行时的所有三个版本。同样，我们使用后端移植的最新版本的Realm [24]运行所有实验，这是位于Legion之下的低级可移植性层，以确保尽可能统一的行为目前没有其他基于任务的运行时系统完全支持基于内容的一致性，因此我们不可能与其他运行时系统进行比较（参见第9节）。另一方面，在一个共同的平台上实现和调优所有三种方法也消除了潜在的显著但正交的性能差异，我们对算法的评价是直接可比的。我们考虑三个基准代码。 第一种是2-D模板计算，它在结构化的规则网格上计算9点5模板，并与数据并行计算混合[26]。第二个基准是基于图形的电路仿真，其迭代地将电路元件的行为建模为具有不同电压的节点之间的边缘[22]。图的结构是不规则的，并且在图的每个子集之间引起不同的通信模式。图形计算还利用归约来描述对来自不同电路元件的电压的并行更新，所述不同电路元件对相同电压节点有贡献。图1中的框架程序就是从这个基准程序派生出来的。 最终基准是Pennant迷你应用程序[12]。Pennant是一个用于非结构网格的二维拉格朗日流体动力学程序。 Pennant还执行归约以并行处理更新，并有几个不同的归约运算符用于代码的不同部分。在之前的工作中，每个基准测试都已经过调优和可伸缩性测试。实验在Piz Daint超级计算机[1]上运行，每个节点有一个Legion进程所有任务都映射到每个节点上的单个GPU我们没有使用Legion5从中心向每个方向各两个单元格，不包括连贯性分析。因此，这些实验并不测量Legion的峰值性能，而是测量不同相干算法的性能。 对 于 光 线 投 射 和Warnock算法的实现，我们还使用Legion的新型动态控制复制（DCR）进行实验[ 4 ]。（不幸的是，画家DCR的目的是将单个任务的工作分割到多个节点上，这对于启动大量子任务的任务来说非常重要。 考虑图1中的while循环，它重复地启动与机器大小成比例的子任务。 由于任务是内部顺序的（并行性是在任务之间，而不是在任务内部），这样的任务在规模上成为顺序瓶颈;将DCR应用于任务本质上将其转换为SPMD风格的执行，任务的每个分片处理任务启动的子集。DCR通过将一致性和依赖性分析的源分布在节点上来强调我们的对于每个基准测试，我们测量了两个执行阶段第一个阶段是初始化时间，这是从应用程序启动到应用程序顶层循环的第一次迭代结束的全部时间初始化阶段的性能衡量Legion发现和分析应用程序的一致性要求的能力，无论是为画家算法制作初始复合视图，还是为Warnock算法和光线投射构建BVH和等价集数据结构。 分区和通信模式越复杂，可能需要的初始化时间就越多。第二个阶段是计算剩余部分的稳态性能;由于所有基准测试都执行重复循环，而不改变分区或任务依赖关系的结构，因此一旦