一种面向二维图形的排序中间体系结构

2020-06-16 00:06:21

在我最近的Piet-GPU更新中,我写道我对性能不满意,并调侃了一种新的方法。我正在寻求系统地找出如何获得一流性能的方法,这是我经过的一个电台的报告。

综上所述,Piet-GPU是一种新的高性能2D渲染引擎,目前正处于研究原型阶段。虽然大多数2D渲染器将矢量图元放入GPU的光栅化流水线中,但Piet-GPU的主要任务是充分利用现代GPU的计算能力。简而言之,它是一个软件渲染器,可以在高度并行的计算机上高效运行。即使对于复杂的3D场景,软件渲染也得到了更多的关注,因为传统的以三角形为中心的管道越来越不适合高端渲染。作为一个引人注目的例子,新的虚幻5引擎严重依赖于计算着色器进行软件光栅化。

Piet-GPU的新架构在很大程度上借鉴了Laine和Karras在2011年发表的论文“GPU上的高性能软件栅格化”(High Performance Software Rasterization On GPU)。该文描述了一种适用于传统3D三角形工作负载的全计算机渲染流水线。该体系结构要求在流水线中间进行排序,以便在流水线的早期阶段,可以按任意顺序处理三角形,以最大限度地利用并行性,但输出渲染器仍会按顺序正确地应用三角形。在3D渲染中,您几乎可以使用未排序的渲染,依靠Z缓冲来决定获胜的片段,但这会导致“Z-Fighting”瑕疵,还会给半透明的片段带来问题。

最初的Piet-Metal体系结构试图避免显式排序步骤,每次都是从根开始遍历场景图。简单性很吸引人,但它也需要重复的工作,并且限制了可以利用的并行性。新的架构采用了与Laine和Karras纸类似的管道结构,但用2D图形“元素”代替了三角形。

作为新Piet-GPU架构的核心,场景被表示为这些元素的连续序列,每个元素都有固定大小的表示。当前元素是“拼接仿射变换”、“设置线宽”、“用于笔划的线段”、“描边先前的线段”、“用于填充的线段”和“填充先前的线段”,当然,随着渲染器能力的增长,计划有更多的元素。

虽然除了混合光栅化片段的顺序之外,三角形或多或少彼此独立,但这些2D图形元素是一个不同的野兽:它们影响图形状态,而图形状态传统上是并行性的敌人。填充轮廓是另一个挑战:效果是非局部的,因为填充形状的内部取决于缠绕数,而缠绕数受可能非常远的轮廓分段的影响。为或多或少独立的三角形设计的管道如何适应这样的有状态模型并不明显。这篇文章将解释它是如何做到的。

通常,必须按顺序计算操作序列,每个操作序列都以某种方式操作状态。一个极端的例子是加密散列,例如SHA-256。用并行的方法计算这样的函数会颠覆我们对计算的理解。

但是,在某些情况下,并行计算非常实用,特别是当状态更改可以建模为关联操作时。最简单、最重要的示例是计数;只需将输入划分为多个分区,对每个分区进行计数,然后对这些分区求和即可。

我们是否可以设计一个关联操作来对场景表示的元素所做的状态更改进行建模?差不多了,正如我们将看到的,它已经足够近了。

在管道的这个阶段,我们的状态有三个组件:笔划宽度、当前仿射变换和边界框。编写为顺序伪代码时,我们所需的状态操作如下所示:

输入元素。如果上一个元素是";填充";或";笔划";,请重置边界框。如果元素是:";设置线宽";,请将线宽设置为该值。";合并变换";,将变换设置为当前变换的时间。";用于填充的线段,计算边界框并累计。笔划的线段,计算边界框,按线宽展开,然后累加。";填充";,输出累计边界框";笔划";,输出累计边界框。

请注意,大多数图形API都有一个“保存”操作,该操作将状态推送到堆栈上,而“恢复”操作则将其弹出。因为我们希望我们的州是固定大小的,所以我们会避免这些。相反,为了模拟“恢复”操作,如果转换在前一次“保存”后发生了更改,则CPU会对逆转换进行编码(这要求转换是非退化的,但这似乎是一个合理的限制)。

作为这种处理的结果,输入中的每个元素都用边界框进行注释,该边界框将在稍后的流水线阶段用于装箱。线段的边界框就是该线段(如果是笔触,则扩展线宽),但对于笔触或填充,它是其前面的线段的并集。

考虑到状态修改的相对简单性质,我们可以设计一个具有几乎结合的二元算子的“几乎么半群”。我不会在这里给出整个结构(它在代码中作为[element.comp]),但将概述重点。

在对这样的状态操作进行建模时,考虑由输入的某个连续切片执行的状态更改,然后考虑两个连续切片的效果的组合,会有所帮助。例如,任意一个切片或两个切片都可以设置线宽。如果第二个切片是这样,则无论第一个切片做什么,最后的线宽都是该值。如果没有,则总体效果与第一个切片相同。

变换上的效果甚至更简单,它只是仿射变换的乘法,众所周知,仿射变换是可结合的(但不是可交换的)。

事情变得稍微棘手的是边界框的积累。边界框的并集是一个关联(和交换)运算符,但是我们还需要几个标志来跟踪边界框是否重置。但是,一般而言,仿射变换和边界框不会完全分布;由边界框的仿射变换产生的边界框可能比变换单个元素的边界框大。

出于我们的目的,边界框可以保守,因为它只用于装箱。如果我们将变换限制到轴对齐,或者如果我们使用凸壳而不是边界矩形,那么变换将完全分布,我们就会得到真正的么半群。但是足够接近了。

当我写我的前缀和博客文章时,我有一些想法,它在2D中可能会有用,但当时不知道它会有多重要。令人高兴的是,该实现可以调整为处理转换和边界框计算,只需稍作更改,而且速度非常快,我们将在下面的性能讨论中看到这一点。

请注意,以前版本的Piet-GPU(以及之前的Piet-Metal)需要CPU计算每个“项”的边界框。新工作的部分主题是将尽可能多的负载卸载到GPU,包括边界框。

虽然在Laine和Karras纸中,元素处理与三角形处理完全不同,但装箱基本上是相同的。入库的目的相当简单:基于上面确定的边界框,将呈现目标表面区域划分为“箱”(在该实现中为256×256像素),并且对于每个箱输出接触到箱的元素的列表。

如果您查看代码,您会发现很多关于right_edge的问题,它用于背景计算,我们将在下面更详细地介绍。

装仓阶段一般与cudaraster相似,不过我确实对其进行了改进。在cudaraster启动固定数量的工作组(旨在匹配硬件中的流式多处理器数量)并输出段的链接列表(每个工作组和分区一个段)的情况下,我发现这在后续的合并步骤中产生了相当大的开销。因此,我的设计为每个bin和分区输出一个连续的段,这允许在合并步骤中进行更多的并行读取,尽管它潜在地输出空段的开销很小(我怀疑这就是Laine和Karras没有采用这种方法的原因)。在这两种情况下,工作组不需要彼此同步,并且输出段中的元素保持排序,这减轻了后续合并步骤中的负担。

装箱阶段也相当快,对总渲染时间没有太大影响。

为什么会有这么大的垃圾桶,或者换句话说,为什么这么少呢?如果入库速度如此之快,那么向下一直到单个瓷砖的入库可能会很吸引人。但是设计要求每个线程有一个bin,因此这将超过工作组的大小(工作组大小通常限制在1024个线程左右,非常大的工作组可能会有其他性能问题)。当然,仍然可以通过调优这些因素来提高性能;通常我使用的是整数。

到目前为止,这个流水线阶段的实现是最具挑战性的,这既是因为令人精疲力竭的性能要求,也是因为它需要结合太多的逻辑。

粗光栅化器的核心与cudaraster非常相似。在内部,它分阶段工作,每个周期消耗存储箱中的256个元素,直到处理完存储箱中的所有元素。

第一阶段合并箱输出,将元素恢复到排序的顺序。此阶段重复读取在入库阶段中生成的块,直到读取了256个元素(或到达输入末尾)。

接下来是输入阶段,每个线程读取一个元素。它还计算该元素的覆盖率,从而有效地绘制16x16位图。还有特殊的背景处理,见下文。

计算线段的总数,并使用原子加法分配输出中的空间。

与在cudaraster中一样,段以高度并行的方案输出,所有输出段在线程之间平均分配,因此每个线程必须执行一个较小的阶段才能找到它的工作项。

然后按顺序写入平铺命令,每个线程一个平铺。这使我们可以跟踪每个平铺的状态,并且命令的数量往往比分段少得多。

这被称为“粗光栅化”,因为它对路径段的几何形状很敏感。具体地说,线段的平铺覆盖是使用“粗线条光栅化”算法来完成的:

2D矢量图形的粗栅格化的一个特殊功能是填充形状的内部。常规方法类似于RAVG;当边缘穿过瓷砖的上边缘时,“背景”将传播到右侧的所有瓷砖,直到填充边界框的右边缘。

虽然在概念上相当简单,但有效实现此功能的代码涵盖了管道中的多个阶段。例如,填充的右边缘必须传播回填充内的线段,即使在早期阶段(如装箱)也是如此。

在元素处理中,每个分区的第一右边缘被记录在每个分区的集合中。

将为入库中的每个段计算右边缘,并将其记录在入库输出中。当线段穿过平铺的顶边时,此逻辑还会将线段添加到条柱中。

在粗略光栅化的输入阶段,横跨瓷砖上边缘的线段会将1“绘制”到所有瓷砖右侧的位图中,也就是直到填充的右边缘。交叉点的符号也在单独的位图中注明,但这不需要同时针对每个元素和每个平铺,因为它对所有平铺都是一致的。

在粗光栅化的输出阶段,使用位计数操作对背景进行求和。然后,如果拼贴中有任何路径段,则在PATH命令中记录背景。否则,如果背景非零,则输出纯色命令。

基本上,正确的缠绕数是三条规则的组合。在平铺内,线段会导致线右侧区域的缠绕编号更改为+1(翻转方向时翻转符号)。如果该线与垂直平铺边缘相交,则会向交叉点下方的半平铺中添加额外的-1。如果线条与水平平铺边缘相交,则右侧的所有平铺都会添加+1;这称为“背景”,也是完全位于形状内部的平铺可以被填充的方式。几乎就像变魔术一样,这三个规则的组合产生了正确的缠绕数,瓷砖边界被擦除。RAVG的论文中给出了这一观点的另一种表述。

精细光栅化阶段几乎没有受到之前Piet-GPU迭代的影响。我对它的表现非常满意;我们试图解决的问题是为粗略的光栅化有效地准备瓷砖。

Piet-GPU(和Piet-Metal)最初的梦想是编码过程尽可能轻,CPU实际上只是上传场景的表示,然后GPU将其处理成渲染的纹理。新的设计离这个梦想更近了一步;在最初的设计中,CPU负责计算边界框,但现在GPU负责这一点。

更令人兴奋的是,与原始Piet-Metal体系结构相比,字符串表示开辟了一种更简单的层方法:只需保留字节表示,然后将它们组合在一起即可。在最简单的实现中,这只是上传场景缓冲区之前的memcpy CPU端,但是可以使用用于非连续字符串表示的全部技术。以前的想法是将场景存储为图形,这需要复杂的内存管理。

一个重要的特例是字体呈现。字形的轮廓可以被编码成字节序列一次(通常在几百字节左右),然后可以通过将这些保留的编码与变换命令交织来组装文本串。从长远来看,即使是这种参考分辨率也可能想要迁移到GPU上,特别是为了启用纹理缓存,但这种更简单的方法也应该是可行的。

请注意,在当前的代码检查点,这一愿景还没有完全实现,因为扁平化仍然是CPU端的。因此,保留的子图(特别是字体字形)不能在大范围的缩放中重复使用。但我有信心这是可以做到的。

最初的设计对于某些工作负载非常有效,但总体性能(对我而言)令人失望。现在是深入了解更多细节的好时机。

简单地说,最初的设计是一系列的四个内核:图形遍历(和绑定到512x32的“tileggroup”),我现在称之为路径段的粗略光栅化,每平铺命令列表的生成(粗略光栅化的其余部分),以及精细光栅化。主要区别在于场景表示;否则舞台会有相当程度的重叠。在旧的设计中,CPU负责编码图形结构,填充/描边路径中的两个路径段,以及将项目分组在一起的能力。

总体而言,当节点的子节点数量既不大也不小时,较旧的设计是有效的。但是,如果超出了这一令人满意的中间值,性能将会下降,我们将研究其中的原因。前三个内核都有潜在的性能问题。

从内核1(图形遍历)开始,基本问题是该内核的每个工作组(负责512x512区域)都执行自己的输入图遍历。对于2048x1536目标,这意味着12个工作组。实际上,这突出了另一个问题;这一阶段可能会缺乏并行性,这在离散图形上是一个比集成图形更大的相对问题。因此,读取输入场景的成本乘以12。在某些情况下,这实际上不是一个严重的问题;如果这些节点有很多子节点(例如,每个节点都是具有很多路径段的路径),则只接触父节点。更好的是,如果节点以良好的空间局部性进行分组(这对于UI工作负载可能是现实的),则通过边界框剔除可以消除大量重复工作。但是对于大量小对象的特定情况(例如,在散点图可视化中可能发生的情况),功系数不是很好。

第二个内核有不同的问题,这取决于子代的数量是小还是大。在前一种情况下,因为工作组中的每个线程都读取一个子节点,所以利用率很低,因为没有足够的工作让线程保持忙碌(我有一个“奇特的K2”分支,它试图将多个节点打包在一起,但由于分歧较大,这是一种回归)。在后一种情况下,问题是每个工作组(负责512x32组)必须读取与该组相交的每条路径中的所有路径段。因此,对于一条涉及许多报道组的大型复杂路径,存在大量重复的作业阅读路径片段,然后这些片段将被丢弃。最重要的是,由于难以进行负载平衡,利用率很低;平铺的复杂性差异很大,因此一些线程会闲置,等待tileggroup中的其他线程完成。

第三个内核也需要相当多的时间,通常与精细光栅化大致相同。同样,最大的问题之一是利用率低,在本例中,因为所有线程都会考虑与tileggroup相交的所有项。在通常情况下,项目只触及TILEGROUP内的一小部分瓷砖,这会浪费大量的工作。

新的设计避免了许多这样的问题,在早期阶段大幅增加了并行性,在中间阶段采用了更多的并行、负载平衡的阶段。然而,它更复杂,通常也更重量级。因此,对于避免了上面概述的性能陷阱的工作负载,旧的设计仍然可以击败它。

与前一版本相比,性能好坏参半。这在某些方面是令人鼓舞的,但不是一刀切的,其中一项测试实际上是一种倒退。我们先来看一下GTX 1060:

这里的计时是成对给出的,旧的设计在左边,中间排序在右边。这些结果令人鼓舞,其中包括巴黎30k测试非常吸引人的加速。(同样,我应该指出,此测试不是完全准确的呈现,因为未应用笔划样式。然而,作为对旧架构和新架构的测试,这是一个公平的测试)。

简而言之,没有。加速比要小得多,事实上,对于Paris-30k的例子,它已经倒退了。不同的GPU具有不同的性能特征,在某些情况下非常重要,这是编写GPU代码的难点之一。我没有深入分析性能(我发现很难做到这一点,经常希望有更好的工具),但我怀疑这可能与Intel上线程组共享内存的相对较慢的性能有关。

在所有情况下,粗栅格化的成本都很高,而元素处理和入库都相当快。

性能总体上比上一版本的Piet-GPU有所提高,但不如我所希望的那么多。为什么?

我的分析是,这是概念的可靠实现,但在管道中完全按完全排序的顺序运输元素需要付出不小的成本。一种观察结果是,路径内的段根本不需要排序,简单地归因于正确的(路径、平铺位置)元组。我将在即将发布的一篇博客文章中探讨这一点。

另一件重要的东西从流通领域遗失了。

..