关于webgl:如何玩转-WebGL-并行计算

简介：现在在 Web 端应用 WebGL 进行高性能计算已有不少实际，例如在端智能畛域中的 tensorflow.js，再比方可视化畛域中的 Stardust.js。

作者 | 沧东
起源 | 阿里技术公众号

现在在 Web 端应用 WebGL 进行高性能计算已有不少实际，例如在端智能畛域中的 tensorflow.js，再比方可视化畛域中的 Stardust.js。在本文中，咱们将介绍以下内容：

• 应用 GPU 进行通用计算（GPGPU）的历史
• 以后在 Web 端应用图形 API 实现 GPGPU 的技术原理，以及前端开发者可能遇到的难点
• 相干业界实际，包含布局计算、动画插值等
• 局限性与将来瞻望

一 什么是 GPGPU

因为硬件构造不同，GPU 与 CPU 善于执行不同类型的计算工作。CPU 通过简单的 Cache 设计实现低提早，蕴含简单的管制逻辑（分支预测），ALU 只占一小部分。而 GPU 为高吞吐量而生，蕴含大量 ALU。因而在单指令流多数据流（SIMD）场景下，GPU 的运算速度远超 CPU，并且这种差距还在一直拉大。

而一些古代 GPU 上甚至有专门负责张量计算、光线追踪的硬件（Tensor/RT Core），例如 Nvidia 的图灵架构。这使得在解决这些计算复杂度极高的工作时能取得更大的性能晋升。

这里就须要引出一个概念，用 GPU 进行除渲染外的通用计算：General-Purpose computation on Graphics Processing Units，即 GPGPU。

自 2002 年提出以来，在实时加解密、图片压缩、随机数生成等计算畛域都能看到它的身影，GPU Gems/Pro 上也有专门的章节介绍。经由 Nvidia 提出的 CUDA(Compute Unified Device Architecture) 这一对立计算架构，开发者能够应用 C、Java、Python 等语言编写本人的并行计算工作代码。

那么在 Web 端咱们应该如何应用 GPU 的计算能力呢？

二 用 WebGL 实现并行计算的原理

在现代化的图形 API（Vulkan/Metal/Direct3D）中提供了 Compute Shader 供开发者编写计算逻辑。思考到 WebGPU 仍在开发中，目前在 Web 端能应用的图形渲染 API 只有 WebGL1/2，它们都不反对 Compute Shader（WebGL 2.0 Compute 已废除），因而只能“曲线救国”。在本文的最初一节咱们将展望未来的技术手段。

咱们先疏忽具体的 API 用法，从 CPU 和 GPU 的角度看两者在并行计算过程中是如何合作的，前者也常被称作 host，后者为 device。第一步为数据初始化，须要从 CPU 内存中拷贝数据到 GPU 内存中，在 WebGL 中会通过纹理绑定实现。第二步 CPU 须要筹备提交给 GPU 的指令和数据，实现计算程序的编译，在 WebGL 中通过调用一系列 API 实现。在第三步中将计算逻辑调配给 GPU 各个外围执行，因而这段逻辑也叫做“核函数”。最初把计算结果从 GPU 内存中拷贝回 CPU 内存，在 WebGL1 中通过读取纹理中像素值实现。

上面咱们从 GPU 编程模型和执行模型动手，顺便引出线程和线程组的概念，这也是 GPU 可数据并行的要害。下图展现了网格与线程组的档次关系，并不局限于 DirectCompute。

• 通过 dispatch(x, y, z) 调配一个 3 维的线程网格（Grid），其中的线程共享全局内存空间；
• 网格中蕴含了许多线程组（Work Group、Thread Group、Thread Block、本地工作组不同叫法），每一个线程组中又蕴含了许多线程，线程组也是 3 维的，个别在 Shader 中通过 numthreads(x, y, z) 指定。它们能够通过共享内存或同步原语进行通信；
• Shader 程序最终会运行在每一个线程上。对于每一个线程，能够获取本人在线程组中的 3 维坐标，也能够获取线程组在整个线程网格中的 3 维坐标，以此映射到不同的数据上，实现数据并行的成果；

再回到硬件视角，线程对应 GPU 中的 CUDA 外围，线程组对应 SM（Streaming Multiprocessor），网格就是 GPU。

1 WebGL1 纹理映射

下图来自「GPGPU 编程技术 – 从 GLSL、CUDA 到 OpenCL」，这也是经典的 GPGPU 计算流程。

通常来说图形渲染 API 最终的输入指标就是屏幕，显示渲染后果。然而在 GPGPU 场景中咱们只是心愿在 CPU 侧读取最终的计算结果。因而会应用到渲染 API 提供的离屏渲染性能，即渲染到纹理，其中的关键技术就是应用帧缓存对象（Framebuffer Object/FBO）作为渲染对象。纹理用来存储输出参数和计算结果，因而在创立时咱们通常须要开启浮点数扩大 OES_texture_float，该扩大在 WebGL2 中曾经内置。

并行计算产生在光栅化阶段，咱们将计算逻辑（核函数）写在 Fragment Shader 中，Vertex Shader 仅负责映射纹理坐标，因而 Geometry 能够应用一个 Quad（4 个顶点）或者全屏三角形（3 个顶点）。对于每一个像素点来说，它的工作并无变动，平时执行的渲染逻辑此时成了一种计算过程，像素值也成了计算结果。

但这种形式存在一个显著的限度，对于所有线程，纹理缓存要么是只读的，要么就是只写的，没法实现一个线程在读纹理，另一个在写纹理。实质上是由 GPU 的硬件设计决定的，如果想要实现多个线程同时对同一个纹理进行读 / 写操作，须要设计简单的同步机制防止读写抵触，势必会影响到线程并行执行的效率。因而在经典 GPGPU 的实现中，通常咱们会筹备两个纹理，一个用来保留输出数据，一个用来保留输入数据。

除此之外，该办法并不反对线程间同步和共享内存这些个性，因而一些并行算法无奈实现，例如 Bellman-Ford 单源最短门路算法。

上图中也提到了乒乓技术，很多算法须要间断运行屡次，例如 G6 中应用的布局算法须要迭代屡次达到稳固状态。上一次迭代中输入的计算结果，须要作为下一次迭代的输出。在理论实现中，咱们会调配两张纹理缓存，每次迭代后对输出和输入纹理进行替换，实现相似乒乓的成果。

值得注意的是，因为 readPixels（在 CPU 侧读取纹理中的数据）十分慢，除了获取最终后果，过程中该当尽可能减少对它的调用，尽可能让数据留在 GPU 中。

这里咱们不再开展 WebGL1 API 的理论用法，具体应用形式能够参考相干教程。

2 WebGL2 Transform Feedback

首先不得不提到已废除的 WebGL 2.0 Compute（底层为 OpenGL ES 3.1），在草案中能看到例如用于线程间同步的 memoryBarrier 和 shared memory 这些高级个性，但最终工作组还是转向了 WebGPU。

WebGL2 中提供了另一种在 Vertex Shader 中进行并行计算的伎俩，即 Transform Feedback，它会跳过光栅化管线因而也不须要 Fragment Shader 参加（理论实现中提供一个空 Shader 即可）。

该计划和 WebGL1 的纹理映射办法有以下不同点：

• 不须要 Fragment Shader 参加，因而能够通过全局变量开启 gl.enable(gl.RASTERIZER_DISCARD)；
• 计算逻辑写在 Vertex Shader 中，不再须要艰涩的纹理映射，能够间接应用 Buffer 读写数据；
• 读取后果时能够间接应用 getBufferSubData。不过不变的是，该办法仍然很慢；

尽管相比 WebGL1 曾经有了不小提高，但仍旧缺失 Compute Shader 中的一些重要个性。

同样，这里咱们也不开展 WebGL2 API 的理论用法，具体应用形式能够参考相干教程。

三 实现中的难点

即便把握了以上原理，前端开发者在具体实际中还是会遇到很大艰难。除了图形 API 和 Shader 自身的学习老本，前端对于 GPU 编程模型自身也是比拟生疏的。

咱们遇到的第一个问题是一个算法是否可并行。有些计算工作十分耗时简单，但并不能交给 GPU 来做，例如代码编译，因而可并行和复杂度并没有间接关系。对于是否可并行的判断并无严格规范，更多来自教训以及业界已有的实际（例如后文会提到的图布局 / 剖析算法），通常遇到一个 “for every X do Y” 这样的工作就能够思考是否能进行数据并行。例如下图展现了一种单源最短门路算法，不难发现外面有遍历每一个节点，针对每一条边的“松弛”操作，此时咱们就能够思考并行化，让一个线程解决一个节点。

当咱们想把一个已有的可并行算法迁徙到 GPU 中时，面临的第一个问题就是数据结构的设计。GPU 内存是线性的，也不存在相似对象这样构造，因而在迁徙算法时不可避免的须要从新设计，如果再思考到对 GPU 内存敌对，设计难度会进一步加大。在上面利用示例「对于图布局 / 剖析算法」一节中将看到对于图的线形示意。

下一个问题是无论 WebGL1 还是 WebGL2，都缺失了 Compute Shader 中的一些重要个性，因而一些在 CUDA 中曾经实现的算法也无奈间接移植。对于这个问题在本文最初一节中有具体的阐明。

咱们曾经重复提到了共享内存和同步，这里举一个 Reduce 求和的例子帮忙读者理解它们的含意。下图展现调配 16 个线程解决一个长度为 16 的数组，最终由 0 号线程将最终后果输入到共享内存的第一个元素中。该过程可分解为以下步骤：

1. 各个线程从全局内存中将数据装载到共享内存内。
2. 进行同步(barrier)，确保对于线程组内的所有线程，共享内存数据都是最新的。
3. 在共享内存中进行累加，每个线程实现后都须要进行同步。
4. 最初所有线程计算实现后，在第一个线程中把共享内存中第一个元素写入全局输入内存中。

试想如果没有共享内存和同步机制，最终的后果显然不会是正确的，有点相似并发编程中的 mutex，如果没有读写锁会失去意想不到的凌乱后果。

最初，GPU 编程中的优化空间很大水平依赖开发者对硬件自身的理解，还是以下面 Reduce 求和为例，在 DirectCompute Optimizations and Best Practices 中能找到基于该版本 5 个以上的优化版本。

另外，GPU 在执行 Shader 时无奈中断，这也带来了代码难以调试的问题，很多渲染引擎也同样面临这样的问题，Unity 有 RenderDoc 这样的工具，WebGL 暂无。

四 利用示例介绍

上面咱们着重介绍一些 GPGPU 在可视化畛域的利用，它们别离来自图算法、高性能动画以及海量数据并行处理场景。

既然是通用计算，咱们必然无奈笼罩所有畛域的计算场景，咱们尝试剖析以下计算工作的设计实现思路，心愿能给读者一些启发，当遇到特定场景的可并行算法时，能够尝试应用 GPU 减速这个过程。

1 图算法

布局和剖析是图场景中常见的两类算法。CUDA 有 nvGRAPH 这样的高性能图剖析算法库，蕴含相似最短门路、PageRank 等，反对多达 20 亿条边的规模。

在实现具体算法前，咱们首先须要思考一个问题，即如何用线性构造示意一个图。最直观的数据结构是邻接矩阵，如下图所示。如果咱们有 6 个节点，就能够用一个 6 x 6 的矩阵示意，有连贯关系的就在对应元素上 + 1。下图来自维基百科对于邻接矩阵的展现。

但这样的数据结构存在一个显著的问题，过于稠密导致空间节约，尤其当节点数增多时。邻接表是更好的抉择，该线性构造分成节点和边两局部，充分考虑 GPU 内存的程序读，尽可能压缩（例如每一个 Edge 的 rgba 重量都存储了临接节点的 index）。以斥力计算（G6 的实现）为例，须要遍历除本身外的全副其余节点，这全部都是程序读操作。同样的，在计算吸引力时，遍历一个节点的所有边也都是程序读。随机读只会呈现在获取端点坐标时才会呈现。

这里不开展具体算法实现，迁徙 G6 已有布局算法的过程详见。最终成果依不同算法实现差距很大，成果最好的是 Fruchterman 布局，节点数过千后 GPU 版本有百倍以上的晋升，但 GForce 布局在大量节点的状况下甚至不如 CPU 版本。

2 SandDance

SandDance 提供了多维数据在多种布局下晦涩切换的成果，它扩大了 Vega 标准，在 2D 场景中减少了深度信息，同时应用 Deck.gl 做渲染。具体到布局切换应用的技术，Luma.gl（Deck.gl 的底层渲染引擎）提供了基于 WebGL2 Transform Feedback 的高级封装，用于在 GPU 中实现动画和数据变换的插值。比照传统的在 CPU 中做插值动画性能要高很多。在通用渲染引擎中，该技术也罕用于粒子特效的实现。

3 P4: Portable Parallel Processing Pipelines

P4 致力于海量数据的解决和渲染，在运行时生成数据聚合和渲染的 Shader 代码，前者有点相似 tfjs 中的一些 op。值得一提的是通过 WebGL 的 Blending 操作实现了一些 Reduce 操作（例如最大最小值、计数、求和、平均值）。例如在实现 Reduce 求和时应用到的 blendEquation 为 gl.ADD。

五 以后局限性与将来瞻望

咱们能够看出 WebGL 受限于底层 API 能力，在很多计算相干的个性上有不同水平的缺失，导致很多可并行算法无奈实现。另一方面，可视化畛域又缺失有不少适宜的场景，咱们迫切需要下一代能力更强的 Web API。

WebGPU 作为 WebGL 的继任者，底层依赖各个操作系统上更现代化的图形 API，提供了更低级的接口，这意味着开发者对 GPU 有更多间接管制以及更少的驱动资源耗费，渲染计算厚此薄彼。目前曾经能够在 Chrome/Edge/Safari 的预览版本中应用它。

WebGPU 在 Shader 语言的抉择上摈弃了 WebGL 应用的 GLSL，转向新的 WGSL。在咱们关怀的计算相干个性上，它提供了 storage/workgroupBarrier 同步办法。有了这些个性，一些算法就能够移植到 Web 端了，例如单源最短门路等其余图算法的 CUDA 开源实现，笔者尝试用 WGSL 实现它。

目前一个更成熟的实际是，Apache TVM 社区退出了 WebAssembly 和 WebGPU 后端反对。在 MacOS 上能够取得和间接本地运行 native metal 简直一样的效率。

总之在可预感的将来，这无疑是 Web 端 GPGPU 的最佳抉择。

原文链接
本文为阿里云原创内容，未经容许不得转载。