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

0动态依赖分析和分布式一致性的可见性算法0Michael BauerNVIDIAmbauer@nvidia.com0Elliott SlaughterSLAC国家加速器实验室eslaught@slac.stanford.edu0Sean TreichlerNVIDIAsean@nvidia.com0Wonchan Lee NVIDIAwonchanl@nvidia.com0Michael GarlandNVIDIAmgarland@nvidia.com0亚历克斯∙艾肯斯坦福大学aaiken@stanford.edu0摘要0隐式并行编程系统必须解决依赖分析和一致性的联合问题，以确保在分布式内存机器上运行的应用程序具有表面上的顺序语义。在数据相关的控制流和任意别名的情况下解决这些问题是一项挑战，大多数现有系统通过牺牲其编程模型的表达能力和/或实现性能来回避这些问题。我们通过将问题简化为计算机图形学中的可见性问题，展示了这些问题的一般类解决方案。0关键词：可见性，Legion，动态分析，一致性 1引言0对于需要超级计算机或云进行大规模计算但不熟悉或不愿开发显式并行和分布式应用程序的用户，隐式并行和分布式编程系统非常受欢迎[2, 3, 8, 14, 16, 19,29]。这些系统提供基于高生产力的编程模型，通过对隐式分布式集合数据类型（如数组和数据框）上的计算进行自动并行发现，实现了高生产效率。任何隐式并行和分布式编程模型的实现都有两个主要职责。首先，它必须通过执行对访问集合子集的区别计算（通常称为运算符或任务）进行依赖分析，从而发现并行性，我们称之为区域。访问不相交区域的任务，或以不会干扰其他任务的方式访问区域（例如，仅读取数据）的任务可以并行执行。其次，系统必须确保区域的一致性，以便任务观察到数据的最新更新，与原始程序的顺序共享内存语义一致。在本文中，我们介绍并评估了管理一致性和检测数据依赖的算法，这些算法适用于区域可以命名集合的任意子集的一般情况（因此区域可以重叠或别名），当区域是01 struct Node {02 up: float03 down: float05 6任务t1(p, g):07读写p.up，reduce::+ g.down;08任务t2(p, g):09读写p.down，reduce::+ g.up;010 11任务main(N):012读写N.up，N.down;013 P[1..3] = ... # 创建N的主要划分014 G[1..3] = ... # 创建N的幽灵划分015 while (*)016对于i = 1..3 t1(P[i],G[i])017对于i = 1..3 t2(P[i],G[i])0图1。使用集合的两个不同划分的任务的简化图计算。0当任务的顺序是由数据相关的控制流决定时，当任务的子区域的计算范围是动态计算的而不是静态指定时，我们需要执行实现并评估。Legion运行时[5]支持这三个特性，这对于具有数据相关行为的许多应用程序至关重要。这些问题的数据相关性要求解决方案是动态依赖和一致性分析。大多数现有的具有这种分析的系统都会施加限制以简化其实现，例如要求所有区域成对独立。我们将这种模型下的系统称为“基于名称的一致性”系统，因为每个数据元素必须始终具有唯一名称（即只能在一个区域中），而在“基于内容的一致性”系统中，数据元素可以同时属于多个区域。基于内容的一致性比基于名称的一致性更加通用：基于内容的一致性可以使用一个区域来轻松支持基于名称的一致性。我们在第9节进一步比较了基于内容和基于名称的系统。我们的主要技术贡献在于认识到在隐式并行任务分布式系统中的依赖分析和基于内容的一致性问题与计算机图形学中的可见性问题密切相关（第3节）。在提供一些背景和0PPoPP'23，2023年2月25日至3月1日，加拿大蒙特利尔，QC，加拿大。所有权/作者所有。ACM ISBN979-8-4007-0015-6/23/02。https://doi.org/10.1145/3572848.35775150本作品采用知识共享署名-非商业性使用-禁止演绎 4.0国际许可协议许可。0PPoPP'23，2023年2月25日至3月1日，加拿大蒙特利尔，QC，加拿大。Michael Bauer，Elliott Slaughter，Sean Treichler，Wonchan Lee，Michael Garland和Alex Aiken0（a）主要划分（b）幽灵划分（c）区域树0图2。图的节点的主要划分和幽灵划分以及相关的区域树。0本文中使用的示例程序（第2节）演示了如何将这些问题简化为可见性问题。然后，我们将逐步提升的三种众所周知的可见性算法（画家算法、沃诺克算法和射线投射）调整为解决基于内容的一致性问题（第4至7节）。我们评估了这三种算法在多个不同规模的机器上的实现情况（第8节）。结果显示，射线投射具有明显优于其他算法的整体性能，因此射线投射算法是Legion项目目前正在使用的算法。最后，我们讨论相关工作（第9节）并进行总结（第10节）。02 示例和背景0图2（a）的蓝色子区域的分割被省略；节点计算足以进行说明。0请注意，节点的虚拟划分不是数学划分：它不是完整的（某些节点不属于任何子区域），并且某些节点具有多个颜色，因为它们包含在多个子区域中。因此，虚拟子区域也不是不相交的，划分G被称为别名。图2（c）显示了此程序的区域和划分的排列，形成了一种称为区域树的分层结构，捕捉了它们之间的关系：所有节点的集合（根区域 N ）有两个划分（由标记为 P 和 G的三角形表示），每个划分都有三个子区域，表示 N中的数据子集。在构建节点的主要和虚拟划分之后，图1中的程序进入一个循环，反复在两个阶段 t1 和 t2之间交替。给出了这些任务的签名，包括它们对区域字段（structNode 的成员）的影响：t1读取和写入其主要子区域中每个节点的 up字段，并对其虚拟子区域中每个节点的 down字段执行约简（求和）操作。任务 t2 反转 up 和 down字段的角色。很容易检查线16上的所有三个任务调用可以并行执行。首先，在每个对 t1的调用中，通过主要划分和虚拟划分进行的访问是触及不同数据的，因为它们涉及不同的字段 up 和 down。t1任务读取和写入其主要子区域，这可以并行进行，因为主要子区域是不相交的。在对 t1的不同调用中，虚拟区域的访问可能触及同一节点的 down字段（因为某些节点包含在多个虚拟子区域中），但这些访问是约简操作，因此可以单独执行，并且稍后将三组结果合并（例如，当该字段被另一个任务读取时）。t2任务（第17行）可以并行运行的理由是对称的。现在考虑线16和线17之间发生的情况。第17行的任务 t2在主要划分中读取通过线16对虚拟划分的约简写入的 down字段的值。类似地，通过线17对虚拟划分的约简的结果必须应用于通过主要划分的最近版本的 up字段。当一个任务使用一个划分写入数据，另一个任务通过不同的划分读取该数据时，复杂的通信模式可能出现；在隐式并行模型中，程序员只需识别数据的所需划分，而无需显式管理通信，这是该模型的优势之一。系统的责任是保证一致性：任务 �的每次读取都能看到由在顺序程序中先于 �的任务产生的正确的、当前的数据版本，而不管任务在何处被调度。将这个顺序顺利地放松为并行调度需要分析任务之间的依赖关系。除非两个任务都读取同一数据或都使用相同的关联操作符进行约简，否则两个任务之间存在一个访问同一数据的依赖关系。0动态依赖分析和分布式一致性的可见性算法 PPoPP’23，2020年2月25日-3月1日，加拿大蒙特利尔0图3. 将3D场景渲染为2D图像。0从主要划分的线16写入的 up字段的值到线17的值之间，会发生类似的隐式通信。当一个任务使用一个划分写入数据，另一个任务通过不同的划分读取该数据时，可能会产生复杂的通信模式；隐式并行模型的优势之一是，程序员只需识别数据的所需划分，而无需显式地管理通信。系统的责任是保证一致性：任务 �的每次读取都能看到由在顺序程序中先于 �的任务产生的正确的、当前的数据版本，而不管任务在何处被调度。将这个顺序顺利地放松为并行调度需要分析任务之间的依赖关系。除非两个任务都读取同一数据或都使用相同的关联操作符进行约简，否则两个任务之间存在一个访问同一数据的依赖关系。0如前所述，虽然Legion支持基于内容的一致性，但大多数系统无法支持图1所示的程序，因为它们是基于名称的，只考虑区域的名称而不是其内容。因此，为了避免别名（数据元素不能有多个名称），所有子区域必须两两不相交，因此只支持对区域的单个不相交划分[2, 8, 14, 16, 19,29]。根据我们的经验，基于名称的一致性会在编写具有多个自然视图（划分）的程序时，强制至少两种妥协之一。图1中的程序可以只使用主要划分来编写。在这种方法中，通信虚拟节点需要通信整个图的一个部分，因为唯一可以通信的单位是具有名称的子区域；因此，一种妥协是在所需最粗粒度上命名区域，并接受一些任务将通信更多的数据。一种更高效的策略是创建一个单独的区域集，仅包含虚拟节点；显式副本管理虚拟节点区域与主要划分的一致性，但放弃了隐式通信的优势。03 可见性问题0计算机图形学中的可见性是确定场景中的哪些基本对象（通常是三角形）对相机可见，因此应该对像素的渲染值做出贡献的问题[10, 13, 20]。这会引起复杂性问题。0这是因为一个对象可能在相机的视角下位于另一个对象的前面或遮挡另一个对象，而某些对象可能部分或完全透明。图3描述了从3D场景渲染2D图像的常见情况。渲染算法解决可见性问题，根据场景中的基本对象和相机的位置，为输出图像的每个像素计算一个值。最终，只有最靠近相机的对象对像素的值有贡献，除非某些对象至少部分透明，如图3中的蓝色和红色三角形所示。对象的透明度程度称为其 alpha 值，0表示完全透明，1表示完全遮挡，介于两者之间的值表示分数透明度。将多个半透明基本对象的影响累积到一个像素中的过程称为 alpha混合。基本的可见性问题是计算沿一条线的可见性。假设基本对象是三角形，并忽略退化情况，场景中的每个三角形与该线相交的点要么是零个要么是一个。与该线共享点的三角形可以根据这些点在线上的出现顺序进行排序，如图3所示。这里，场景中的四个三角形与从相机到 � 4 的线相交，� 1最接近相机。由相机沿线视图定义的像素的值为 � = �(� 1 , � 1 ,�(�2 , � 2 ,�(� 3 , � 3 ,�(� 4 , � 4 , 0)))))，其中 � 是混合函数，� � 是第 �个三角形的 alpha 值，0 是 � 的单位元（即 �(�, �, 0) =��）。由于紫色三角形上的点 � 3 是遮挡的（� 3 =1），黑色三角形沿线不可见；即 � = �(� 1 , � 1 ,�(� 2 , � 2 ,�(� 3 , 1 ,0)))。03.1 一致性问题我们将（基于内容或基于名称的）一致性问题转化为计算机图形学中的可见性问题。考虑一个区域的单个元素 �，例如 �维数组或数据帧中的一个点。我们假设存在一个全局时钟，为� 上的任何任务执行的每个操作 � 分配一个时间 �。� �的增序排列的操作序列为 � � 1 ,� 1 � , . . . ,  � � � ,� ��。可能的三个操作是写操作 � � ，将 � 分配给 � ，约简操作 � � �，将约简操作符 �  � 应用于 � 的当前值和 � ，以及读操作 � ，读取� 的当前值。我们在该序列上定义了一个混合函数 �。0�(� � 1 ,� 1 � , . . . ,  � � � ,� � � , � ) = �(� � 2 ,� 2 � , . . .  � � � ,� � � ,�( � 1 , � ))0� ( � � , � ) = �0� ( � � � , � ) = � � ( �, � )0� ( �, � ) = �0考虑一个读取  � �,� � � 。那么  � (� � 1 ,� 1 � , . . . ,  � � � − 1 ,� � − 1 � ,  0 )是时间  � � 上  �  的值，它在时间向后沿着  �的线上是可见的。视觉透明度在一致性中有一个直接的类比：读取是完全透明的，降低是部分透明的。0PPoPP ’23，2月25日至3月1日，加拿大蒙特利尔 Michael Bauer，Elliott Slaughter，Sean Treichler，Wonchan Lee，Michael Garland和Alex Aiken0(a) 任务时间线 (b) 任务更新0图 4.  基于内容的一致性可视化。0（“透明度”的“程度”取决于降低运算符），并且写操作是完全不透明的。使用这些操作对任务的程序在区域的任意子集上引发了一个时空体积，必须对其进行一致性分析。我们的研究结果显示了图形中可见性和任务为基础的系统中的一致性之间的直接对应关系：一个计算空间维度中的可见性，另一个计算时间维度中的可见性。图  4 (a)显示了六个任务的时间线，图  4 (b)显示了每个任务与更新的数组对应部分，最近的更新在顶部。所有的更新都是写操作（以实心框表示），除了任务  T4  和T6 ，它们执行降低操作（部分透明框）。当任务  T6执行时，将从最近的任务中汇编出任务  T6的输入数据以进行更新。图  4 (b) 显示任务  T6 需要任务  T5、  T4 、  T3  和  T2 写入的一些数据，但不需要任务  T1写入的数据，因为任务  T1 的更新被任务  T2 遮挡。在图  4(a)中，虚线箭头显示了这种“朝后看”的过程，以找到写入任务 T6  所需数据的任务。03.2 依赖分析0上述降低使用全局时间概念，对应于任务的顺序执行顺序。需要依赖分析来将这个顺序顺序放松为任务执行的部分（并行）顺序，以保证读取的一致性仍然得到保证。请记住，我们区分基于内容的一致性和基于名称的一致性。在基于名称的方案中，区域必须不相交，只有两个具有相同特权的任务  � ( � )  和  � ( � )  之间才能存在依赖关系，其中  �  =  。在基于内容的一致性中，区域可以重叠，并且只有在  �  ∩ �  ≠  �时才能存在依赖关系。基于内容的一致性还轻松支持不规则和稀疏区域；区域中的元素集合不需要是元素的连续子范围。基于内容的一致性的主要成本是发现哪些区域对具有非空交集。仅因为两个任务  � ( � )  和  � ( � )共享数据并不意味着它们之间存在依赖关系；仅当任务执行顺序的反转可能导致错误结果时，才存在依赖关系。每个任务声明其是否进行读取、读取和写入，或者对其区域参数执行特定降低运算符（例如求和）。Legion运行时使用任务的特权[ 5]保守地估计两个任务之间是否存在依赖关系；我们省略了详细信息。图  5  显示了图1  中  main任务执行的前九个任务。由于我们的分析是动态的，运行时系统观察到它要分析的任务启动序列的依赖关系和一致性。考虑图  5  中第 7 行的任务  � 6 ，即图  1  中第 16行的循环第二次进入时调用的任务。为了计算任务  � 6  依赖的任务并计算  � 6参数的一致版本，运行时系统“向后”观察先前任务对  � 6引用的数据区域的影响。在这种情况下，� 6  依赖于任务  � 3 ，  � 4 和  � 5 ，因为  � 6读取主分区中可能与这些先前任务对鬼分区进行的降低操作重叠的子区域。相应地，� 3 依赖于  � 0 ，  � 1 和  � 2 ，因为  � 3  为这些任务写入的值添加了降低操作。任务  � 4  和� 5  也出于同样的原因依赖于  � 0 ，  � 1 和  � 2。通过这个例子，我们可以看到依赖分析是一致性问题的一个子集。依赖分析仅需要系统证明哪些任务触及了另一个任务可能访问的数据，但它不需要知道元素的实际值，只需知道可能存在共同元素。例如，在图  5  的任务流中，系统将发现任务  � 0 − 2 ，  � 3− 5  和  � 6 − 8之间没有依赖关系，允许这些任务组并行执行。对于一致性，我们必须再进一步计算共同元素的当前值。因此，我们的一致性算法也将为依赖分析提供解决方案。01 t1(P[1],G[1]) #  � 003 t1(P[3],G[3]) #  � 205 t2(P[2],G[2]) #  � 407 t1(P[1],G[1]) #  � 609 t1(P[3],G[3]) #  � 801 # S 是运行时系统的状态03 对于每个  P i  R i05 R 1 , . . . ,  R n  : =  T ( R 1 , . . . ,  R n07 S  : =  提交 ( P i ,  R i ,  S )0图 6.  任务执行。04 准备工作0在介绍可见性算法之前，我们首先为它们的介绍定义一个共同的框架。图  6  定义了一个函数  run_task，该函数接受一个任务调用  T ( P 1  R 1 , . . . ,  P n  R n ) 和运行时系统的当前状态  S 。这里  P i  是任务  T对区域  R i  的特权（见下文）。每个可见性算法必须提供两个函数  materialize  和  commit ，以及  S的实现。为了解释 materialize  和  commit ，我们需要任务的其他细节：0动态依赖分析和分布式一致性的可见性算法 PPoPP ’23，2月25日至3月1日，加拿大蒙特利尔0•  程序使用一个单独的区域  A。（实际系统允许任意数量的区域以及每个区域的多个字段，但这个更简单的设置足以说明重要的思想。）域  dom ( A )= { i | � i ,  v � ∈  A }  是  A  的第一个组成部分的集合。0•  区域  R  是一组对  {� �, � �}  形式的集合，其中  �  是一- 维点的集合，而  �是该点上的区域的值。注意，此定义将区域限制为单个字段。集合中的每个第一组成部分  �  最多只能出现一次。0•  任务调用中的每个特权  P i  都是读取、读写或降低 f，其中  f  是降低运算符（例如，求和具有降低特权  reduce+）。两个特权干扰，如果具有这些特权的两个任务可能存在依赖关系。唯一不干扰的特权组合是 read/read  和  reduce0•  降低运算符  f  必须具有一个身份  0 f来支持部分累积。 1 例如，  +=  是一个具有身份 0的降低运算符。0• 任务的任何区域参数R和R'必须具有不相交的域dom(R) ∩dom(R') =�，除非任务只读取这两个区域或者只对这两个区域使用相同的归约运算符2。任务的区域参数Ri只是指定所需数据的区域：dom(Ri)是索引的集合，运行时系统负责填充正确的值。函数materialize接受一个区域、其特权和当前运行时状态，并返回一个具有相同域和当前值的区域；materialize还可能更新状态（图6中的第5行）。运行任务时，会对区域参数调用该函数，可能会更新这些区域（第6行）。函数commit记录了为将来的任务调用所需的正确区域参数的信息（第8行）。05画家算法在接下来的三节中，我们将介绍三种基于计算机图形的可见性算法的一致性算法。每个算法都对前一个算法进行了改进，因此最成熟和性能最好的方法，即射线投射，重用了为其他两种方法开发的概念。在计算机图形学中，画家算法通过从后面渲染场景中的对象来解决可见性问题。01当关于区域参数的减少运算符是可交换和/或可结合时，存在一些有趣的优化方法，但它们超出了本文的范围。2处理干扰特权具有交集的情况需要超出本文范围的任务内一致性。01 # S是一个历史记录：特权，区域对的列表02 paint(R,S)03 # 历史记录从旧到新遍历05 如果 P ′ =  read  - write ，那么07 否则，如果 P ′ =  reduce f ，那么08 R  : =  R  ⊕  f ( R / R ′ ,  R ′ / R ) .09 # 如果 P ′ =  read ，则不执行任何操作010 返回 R, S011 12 materialize(P,R,S)013 # 对于所有i∈dom(R)，R[i]最初未定义014 如果 P  =  reduce f ，那么015 返回 {� i, 0 f �|  i  ∈  dom ( R ′ ) }016 否则017 返回 paint(R,S)018 19 commit(P,R,S)020 返回 S ++ � P, R �0图7。画家算法。0将其添加到前面[17]。对于给定的像素�，渲染一个半透明对象（在已经渲染的所有对象的前面）会累积到�上，并且渲染一个完全遮挡的对象会覆盖�。内容一致性的画家算法在图7中。该代码使用了三个辅助函数：0� / � = {� �, � � ∈  �  |  �  ∈  dom ( � )}0� \ � = {� �, � � ∈  �  |  �  �  dom ( � )}0�  ⊕  � = � \ �  ∪  �0简而言之，� / � 是与�共享点的�的子集，� \ � 是与�不共享点的�的子集，� ⊕ �是使用�的值对�和�求并集，其中 dom(�) ∩ dom(�)。图7中的状态S是特权区域对� P, R�的列表。初始状态是一个包含一个对� read-write, A�的对的列表，这是A的初始值。当任务完成时，commit将其区域参数的最终状态附加到S。因此，该状态是操作结果的历史记录，按照时间的递增顺序排列 -程序顺序中第�个任务调用的所有结果对在� + 1的任务和� - 1的任务结果之前列出。30paint函数通过按照顺序应用操作来计算区域R的最新状态。对于每个特权区域对（第3行），如果特权为read-write，则替换R的被覆盖部分，而保留未更新的部分（第5行）。reducef类似，只是将更新的部分使用归约运算符折叠到R中（第7行）。注意，我们将归约运算符�逐点地提升到区域对：�(�,�) = {� �, � �|��, � � � ∈  �  ∧ � �, � � � ∈  �  ∧  �  ( � � , � � )  =  �}。对于读操作，不需要对R进行任何修改。materialize函数的行为取决于对R执行的操作的特权。对于归约，不需要检查历史记录，区域会初始化为归约运算符的标识 -仅在未来应用归约。03 由于区域参数别名的限制，对于单个任务调用的区域参数的顺序无关紧要。0PPoPP ’23，2023年2月25日至3月1日，加拿大蒙特利尔 Michael Bauer, Elliott Slaughter, Sean Treichler, Wonchan Lee, Michael Garland, and Alex Aiken0(a) 任务 t 0 − 2 (b) 任务 t 3 − 5 (c) 任务 t 6 − 80图8。处理图5中的任务启动后的区域树状态。0对于 materialize的调用。这种延迟应用降低了数据移动的量：急切执行归约需要将区域的当前值实例化，这将在任务开始执行之前将数据复制到任务的位置，而积累部分归约只在结果需要时移动数据[ 24 ]。相反，对于 read 或 read-write操作，系统必须实例化区域的当前值。05.1优化和实现图7中的算法简单但效率低下。当实例化子区域R时，简单的画家算法需要测试历史记录中的每个操作是否与R重叠。一种更高效的方法是使用区域树作为加速数据结构：我们将历史记录存储在区域树中，以便可以沿着从区域树根到R的路径找到与R相关的历史记录。更具体地说，区域树的每个节点R维护一个子历史R.h，并且我们保证实例化R所需的路径历史（按顺序从根到R的路径连接）产生与简单的画家算法相同的结果。当启动任务t并具有区域参数R和特权p时：01. 将 � t ,  p � 附加到 R . h . 2. 找到 R 的祖先 R ′ ，并且 R′ 有一个子区域 C 。如果 C ∩ R  ≠  � ，那么在 C ′的子树中已经记录的任何任务必须在路径历史中的 � t ,  p �之前。我们将 C的任务历史的快照，称为复合视图，附加到 R ′ . h。我们删除 C 中的任务历史，因为它们现在已经记录在 C的父节点 R ′ 中。0在遍历路径历史时，首先遍历复合视图（包括任何嵌套的复合视图），然后继续下一个路径元素。我们可以通过在每个节点R上记录它是“打开的”（R的子树中存在非空历史记录）还是“关闭的”（R的子树中的所有历史记录都为空）来减少复合视图的数量。另一个改进是在R处记录R的子树中使用的特权。当执行上述步骤（2）时，我们可以跳过为具有关闭或仅具有不干扰� t ,  p�的特权的历史记录的子树创建复合视图。最后，经常一个复合视图会遮挡先前的复合视图�'，从而允许�'被删除。0从历史记录中删除；由于篇幅有限，我们省略了用于识别这种屏蔽的保守测试的细节。0图8给出了使用图5中的任务序列的示例。图中的索引表示将任务或复合视图添加到区域树的步骤。当启动t0时，没有先前的任务，因此任务记录在P.up[1]的历史记录中。当启动t1时，我们在P.up[2]处记录t1。因为P是一个不相交的分区，所以不创建复合视图，因此P.up[1] ∩ P.up[2] =�。t2的启动类似；图8（a）显示了在记录t0-2之后的区域树状态。任务t3使用了G.up[1]子区域，因此通过区域树以不同的路径通过并具有不同的归约特权。因为P.up和G.up重叠，并且P.up中使用的read-write特权与t使用的归约特权干扰，所以将P.up的子树的复合视图V0附加到根的历史记录中。即使G.up是别名分区，t4和t5与t3使用相同的归约特权，因此这些任务只是分别添加到G.up[2]和G.up[3]的历史记录中。启动t0-5后的区域树状态如图8（b）所示。当启动t6时，将G.up的另一个复合视图V1附加到根。图8（c）显示了分析任务t0-8后的区域树状态。0区域树和复合视图都是具有部分组件分布在不同节点上的分布式数据结构，出于可扩展性的原因。区域树和复合视图中的子区域数量通常与机器中的节点数量成正比，因此在单个节点上存储任何此类数据结构可能会非常昂贵。我们自下而上构建复合视图，节点之间的通信最小化，以捕获最上层的状态。由于复合视图在构建后是不可变的，因此我们可以根据需要安全地复制复合视图的节点到整个机器上。06 Warnock算法画家算法的一个缺点是，即使经过优化，材质化区域R可能会导致对许多（特别是复合视图）由于后续更新而不再可见的历史记录条目进行测试。Warnock算法在Figure9中给出，通过进行空间分解来解决材质化区域时不考虑的更新。0动态依赖分析和分布一致性的可见性算法 PPoPP ’23，2月25日至3月1日，加拿大蒙特利尔，魁北克01# S是一组等价集。0等价集是一对（区域，历史）的数据结构。03 refine(R,S)0S' := �05对于�R'，H�在S中07S' := S'∪{�R'，H�}09S' := S'∪{�R'，H�}011S' := S'∪{�R'/R，H�，�R'\R，H�}0返回S'013 14材质化(P，R，S)0S' := refine(R, S)016Es := {�X，H�∈S' | dom(X)�dom(R)}0R:=�018对于�R'，H�在Es中0如果P = 减少f，则020X := {�i，0f�| i ∈ dom(R')}0否则022X := paint(R'，H)0R:=R∪X024返回R，S'0commit(P,R,S)027S' := �029如果R'/R = R'则031S' := S'∪�R'，�P，R/R'��033S' := S'∪�R'，H++�P，R/R'��035S' := S'∪�R'，H�0返回S'0图9. Warnock算法。0问题[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的材质化。历史的空间分隔可以在commit函数中看到，该函数仅将任务对区域R的操作附加到构成R的等价集。如果任务是写入，则可以清除先前的历史记录0图10. Warnock算法对图5中的任务启动创建的等价集树。0等价集，然后将自身作为新历史中唯一的条目存储，从而确保历史记录是精确的，并且只包含最近“可见”的任务（第30-31行）。0图10展示了Warnock算法为图5中的任务启动序列创建的等价集树的示例。我们仅展示了与up字段相关的等价集细化的序列。每个等价集�都标有�所代表的N.up的子集，以及导致�添加到细化树中的任务�。实线轮廓表示任务的区域参数来自P分区，虚线表示来自G分区的区域参数（参见图2）。最初，N.up是唯一的等价集。任务t0对P[1].up具有特权，这导致将根节点细化为N.up/P[1].up=P[1].up和N.up\P[1].up。任务t1对P[2].up具有特权，与P[1].up不相交，因此只有节点N.up\P[1].up被细化为N.up\P[1].up/P[2].up=P[2].up和N.up\P[1].up\P[2].up=P[3].up。在任务t1和t2之后，Warnock算法发现了P分区的子区域，因此任务t2对P[3].up没有添加额外的等价集节点。任务t3-5处理幽灵分区的子区域G[1-3]。任务t3以G[1].up作为参数。回想一下，G[1].up是P[1].up的幽灵节点集，这意味着G[1].up可能与P[2].up和P[3].up共享节点（再次参见图2）。因此，t3导致将P[2].up和P[3].up分割为在G[1].up中是幽灵单元格和不是幽灵单元格的元素。任务t4以G[2].up作为参数，这导致在P[1].up和P[3].up的子树中的叶节点进一步细化。最后，任务t5以G[3].up作为参数，这导致在P[1].up和P[2].up的子树中进行最后的细化。请注意，不显示P[1].up子树下计算的所有等价集，因为P[1].up/G[2]/G[3]和P[1].up/G[2]\G[3]为空。任务t5是循环的第一次迭代的最后一个任务。后续的每次迭代都使用相同的区域，因此不需要对图10中的树进行进一步的细化。0PPoPP ’23， 2月25日至3月1日，加拿大蒙特利尔，魁北克，迈克尔∙鲍尔，艾略特∙斯劳特，肖恩∙特里奇勒，Wonchan Lee，迈克尔∙加兰和Alex Aiken06.1优化和实现与前一节类似，我们可以通过一些优化大大提高Warnock算法的性能。最重要的挑战是加速确定哪些等价集表示给定区域（Figure9的第16行）。由于每个等价集总是被细化为覆盖原始等价集的新等价集，所以细化历史定义了一个搜索树，它是一个边界体积层次结构（BVH）[9]。对于任何新的子区域R，为了发现其组成的等价集，它从等价集BVH的根节点开始，测试与任何子节点的交集，并递归遍历任何重叠的子节点。到达的叶节点集合恰好是在程序执行的那一点上用于执行R的依赖性和一致性分析的最新的等价集。在执行此初始遍历后，我们可以记忆化组成R的等价集。由于Warnock算法仅细化等价集，因此在程序中稍后使用R的下一个任务可以从每个记忆化的等价集开始搜索R的当前组成等价集。等价集BVH是一个分布式数据结构。BVH中唯一的可变状态是存储在叶节点上的历史记录，因此我们可以安全地在整个机器上复制BVH中的中间节点，因为在细化等价集后，任何子节点的名称都是不可变的。在规模上，当许多节点尝试执行需要遍历BVH的上层来识别其子区域的组成等价集的任务时，复制是避免顺序瓶颈的关键。0光线投射0从历史中精确修剪遮挡元素的能力，因此随后开发了我们对Warnock算法的改进版。当创建太多等价集时，Warnock算法也会导致不同的可伸缩性问题（参见第8节）。我们认识到这些算法与计算机图形学中的可见性相关，这在以前不明显，这促使我们调查光线投射是否比其他方法更好，光线投射是现代渲染中的首选方法[28]。光线投射从图像的每个像素向场景投射光线，记录它所穿过的对象（如果是半透明的）和最终阻挡它的对象。然后累积这些相交的效果以计算像素的最终值4（参见图3）。基于光线投射和Warnock算法的基于内容的协同的区别在于处理方式0在图形学中，当对表面进行着色的递归“阴影”光线也会被投射以对表面点的照明进行采样。在我们的情况下没有阴影光线的类似物；我们只需要确定可见的任务。01 dominating_write(R,S) 2 S' := {�R, [�read-write, ��]�} ∪ {�R', H� ∈ S | dom(R) ∩0返回S'04 5  materialize(P,R,S) 6 R', S' :=warnock::materialize (P, R, S)08 S' := dominating_write(R', S')0返回R'，S'010 11  commit(P,R,S) 12 returnwarnock::commit (P, R, S)0图11.光线投射算法。0对于Warnock算法，等价集仅被细化为更小的等价集。虽然这使得很容易发现哪些等价集表示一个子区域，但在执行写操作之后，它经常导致许多具有相同历史的等价集。在光线投射方法中，每个对区域R执行写操作的任务t创建一个表示具有初始历史�read-write,R�的R的新等价集。在为写操作创建新的等价集R之后，我们修剪所有被R遮挡的等价集。图11使用了Warnock算法的materialize和commit例程。新函数dominating-write为R创建了一个新的等价集，并修剪了被R遮挡的等价集（图11的第2行）。对写操作的新处理意味着等价集既可以合并也可以细化。光线投射作为解决这些由于等价集的收集与Warnock算法相比现在的非单调变化引起的两个问题的主要机制。为了在dominating-write函数中修剪等价集，我们使用光线投射来发现被区域R遮挡的等价集（图11的第2行）。此外，我们使用光线投射来发现每次调用materialize函数（图9的第16行通过图11的第6行）时区域R的组成等价集，因为在每个任务的materialize函数调用之后，等价集的集合可能会发生变化。0光线投射产生与图5中的任务t1-t5显示的等价集相同的等价集，但请注意这些等价集存储在P分区的叶子节点中，P是示例中唯一的不相交-完整分区。每个循环的第一个任务对P [1].up具有读写权限。写权限会导致P[1]的所有细化及其历史被丢弃，从而减少等价集的数量并简化历史，直到再次调用操作幽灵区域的任务。对P [2] .up和P[3] .up具有读写权限的任务也会合并等价集并简化历史。07.1 优化和实现0为了加速光线投射，在计算机图形学中的实际实现依赖于场景的BVH分解，以高效地检测光线与对象的相交[9]。由于等价集通过写操作合并，因此不再有0动态依