利用GPGPU计算大规模群落仿真行为

前言

在今年6月的 Unite Europe 2017 大会上 Unity 的 CTO Joachim Ante 演示了未来 Unity 新的编程特性—— C# Job 系统，它提供了编写多线程代码的一种既简单又安全的方法。Joachim 通过一个大规模群落行为仿真的演示，向我们展现了最新的 Job 系统是如何充分利用 CPU 多核架构的优势来提升性能的。
但是吸引我的并非是 C# Job 如何利用多线程实现性能的提升，相反，吸引我的是如何在现在还没有 C# Job 系统的 Unity 中实现类似的效果。

在 Ante 的 session 中，他的演示主要是利用多核 CPU 提高计算效率来实现大群体行为。那么我就来演示一下，如何利用 GPU 来实现类似的目标吧。利用GPU做一些非渲染的计算也被称为GPGPU——General-purpose computing on graphics processing units，图形处理器通用计算。

CPU的限制

为何 Joachim 要用这种大规模群落行为的仿真来宣传 Unity 的新系统呢？

其实相对来说复杂的并非逻辑，这里的关键词是“大规模”——在他的演示中，实现了20,000个 boid 的群体效果，而更牛逼的是帧率保持在了 40fps 上下。
事实上自然界中的这种群体行为并不罕见，例如大规模的鸟群，大规模的鱼群。

在搜集资料的时候，我还发现了一位优秀的水下摄影师、加利福尼亚海湾海洋计划总监octavio aburto的个人网站上的一些让人惊叹的作品。

图片来自Octavio Aburto

而要在计算机上模拟出这种自然界的现象，乍看上去似乎十分复杂，但实际上却并非如此。
查阅资料，可以发现早在1986年就由Craig Reynolds提出了一个逻辑简单，而效果很赞的群体仿真模型——而作为这个群体内的个体的专有名词boid（bird-oid object，类鸟物）也是他提出的。
简单来说，一个群体内的个体包括3种基本的行为：

Separation：顾名思义，该个体用来规避周围个体的行为。

Alignment：作为一个群体，要有一个大致统一的前进方向。因此作为群体中的某个个体，可以根据自己周围的同伴的前进方向获取一个前进方向。

Cohesion：同样，作为一个群体肯定要有一个向心力。否则队伍四散奔走就不好玩了，因此每个个体就可以根据自己周围同伴的位置信息获取一个向中心聚拢的方向。

以上三种行为需要同时加以考虑，才有可能模拟出一个接近真实的效果。

Vector3 direction = separation+ alignment + (cohesion - boid.position).normalized;

可以看出，这里的逻辑并不复杂，但是麻烦的问题在于实现这套逻辑的前提是每个个体 boid 都需要获取自己周围的同伴信息。
因此最简单也最通用的方式就是每个 boid 都要和群落中的所有boid比较位置信息，获取二者之间的距离，如果小于阈值则判定是自己周围的同伴。而这种比较的时间复杂度显然是 O(n2)。因此，当群体是由几百个个体组成时，直接在 cpu 上计算时的表现还是可以接受的。但是数量一旦继续上升，效果就很难保证了。

当然，在 Unity 中我们还可以利用它的物理组件来获取一个boid个体周围的同伴信息：

Physics.OverlapSphere(Vector3 position, float radius, int layerMask);

这个方法会返回和自己重叠的对象列表，由于 unity 使用了空间划分的机制，所以这种方式的性能要好于直接比较n个boid之间的距离。

但是即便如此，cpu 的计算能力仍然是一个瓶颈。随着群体个体数量的上升，性能也会快速的下降。

GPU的优势

既然限制的瓶颈在于 CPU 面对大规模个体时的计算能力的不足，那么一个自然的想法就是将这部分计算转移到更擅长大规模计算的 GPU 上来进行。
CPU 的结构复杂，主要完成逻辑控制和缓存功能，运算单元较少。与CPU相比，GPU的设计目的是尽可能的快速完成图像处理，通过简化逻辑控制并增加运算单元实现了高性能的并行计算。

利用 GPU 的超强计算能力来实现一些渲染之外的功能并非一个新的概念，早在十年前nvidia就为GPU引入了一个易用的编程接口，即CUDA统一计算架构，之后微软推出了 DirectCompute ——它随 DirectX 11 一同发布。
和常见的 vertex shader 和 fragment shader 类似，要在 GPU 运行我们自己设定的逻辑也需要通过 shader，不过和传统的 shader 的不同之处在于，compute shader 并非传统的渲染流水线中的一个阶段，相反它主要用来计算原本由 CPU 处理的通用计算任务，这些通用计算常常与图形处理没有任何关系，因此这种方式也被称为 GPGPU——General-purpose computing on graphics processing units，图形处理器通用计算。
利用这些功能，之前由CPU来实现的计算就可以转移到计算能力更强大的 GPU 上来进行了，比如物理计算、AI 等等。
而 Unity 的 Compute Shader 十分接近 DirectCompute，最初 Unity 引入 Compute Shader 时仅仅支持 DirectX 11，不过目前的版本已经支持别的图形 API 了。详情可以参考：Unity - Manual: Compute shaders。

在 Unity 中我们可以很方便的创建一个 Compute Shader，一个 Unity 创建的默认 Compute Shader 如下所示：

// Each #kernel tells which function to compile; you can have many kernels
#pragma kernel CSMain

// Create a RenderTexture with enableRandomWrite flag and set it
// with cs.SetTexture
RWTexture2D Result;

[numthreads(8,8,1)]
void CSMain (uint3 id : SV_DispatchThreadID)
{
    // TODO: insert actual code here!

    Result[id.xy] = float4(id.x & id.y, (id.x & 15)/15.0, (id.y & 15)/15.0, 0.0);
}

这里我先简单的介绍一下这个 Compute Shader 中的相关概念，首先在这里我们指明了这个 shader 的入口函数。

#pragma kernel CSMain

之后，声明了在 compute shader 中操作的数据。

RWTexture2D Result;

这里使用的是 RWTexture2D，而我们更常用的是 RWStructuredBuffer（RW 在这里表示可读写）。
之后是很关键的一行：

[numthreads(8,8,1)]

这里首先要说一下 Compute Shader 执行的线程模型。DirectCompute 将并行计算的问题分解成了多个线程组，每个线程组内又包含了多个线程。

[numthreads(8,8,1)]的意思是在这个线程组中分配了 8x8x1=64 个线程，当然我们也可以直接使用：

[numthreads(64,1,1)]

因为三维线程模型主要是为了方便某些使用情景，和性能关系不大，硬件在执行时仍然是把所有线程当做一维的。
至此，我们已经在 shader 中确定了每个线程组内包括几个线程，但是我们还没有分配线程组，也没有开始执行这个 shader。
和一般的 shader 不同，compute shader 和图形无关，因此在使用 compute shader 时不会涉及到 mesh、material 这些内容。相反，compute shader 的设置和执行要在 c# 脚本中进行。

this.kernelHandle = cshader.FindKernel("CSMain");
 ......
 cshader.SetBuffer(this.kernelHandle, "boidBuffer", buffer);
 ......
 cshader.Dispatch(this.kernelHandle, this.boidsCount, 1, 1);
 buffer.GetData(this.boidsData);
 ......

在 c# 脚本中准备、传送数据，分配线程组并执行 compute shader，最后数据再从 GPU 传递回 CPU。
不过，这里有一个问题需要说明。虽然现在将计算转移到 GPU 后计算能力已经不再是瓶颈，但是数据的转移此时变成了首要的限制因素。而且在 Dispatch 之后直接调用 GetData 可能会造成 CPU 的阻塞。因为CPU此时需要等待 GPU 计算完毕并将数据传递回 CPU，所以希望日后 Unity 能够提供一个异步版本的 GetData。

最后将行为模拟的逻辑从 CPU 转移到 GPU 之后，模拟 10，000 个 boid 组成的大群组在我的笔记本上已经能跑在 30FPS 上下了。