【IT168 技术】
注：本文为IT168&NVIDIA联合举办的“如何并行化我的应用”方案征集活动参赛作品。本次方案征集活动详情见：http://cuda.itpub.net/thread-1299715-1-1.html。近期活动的大部分方案，将会逐步与大家分享，不可错过哦!
CUDA ZONE专区：http://cuda.it168.com/
CUDA技术论坛：http://cuda.itpub.net
1. 前言
人是现实世界中最重要和最基本的组成元素之一，虚拟角色对于虚拟世界来说具有同样重要的意义。利用群体模拟技术，在计算机生成空间中创建并模拟现实世界中的群体及其运动，能够极大地提高虚拟世界的真实感和沉浸感。近年来，随着计算机群体模拟技术的不断发展，其应用也越来越广泛，涉及的领域包括模拟训练、计算机游戏动画、影视特效和公共安全辅助设计等。比如，影视画面中可以将包含大量人群活动的场景通过计算机模拟实现，从而提高特效制作的效率并降低制作成本;通过对日常人流或紧急情况下人群的运动过程进行模拟与分析，为建筑物结构设计、大型活动客流管理、公共场所应急预案制定起到很好的指导作用。
目前，计算机群体行为模拟方法主要以基于个体的(agent-based)局部控制方法为主，其思想主要源于现实生活中人群的运动特点：人群中的每个个体都有独立的目标并具有不同的运动特性。虽然这类方法比较灵活且能够方便地定制个体的行为，但是计算量也会随着模拟的人群数量的增加而增加。因此，我们设计了一种基于CUDA的大规模人群快速模拟计算方法。
2. 方法基本流程
为了满足GPU计算的需要，我们定义了一种新的人群运动计算模型，可以充分利用现有GPU计算单元高度并行化的特点，同时又能满足较好的模拟真实性。
根据影响人群运动的因素，我们通过一组代价函数计算个体的局部运动代价并驱动个体运动，该算法主要包括两个步骤：1. 将环境状态信息映射到全局状态场;2. 局部运动代价求解并驱动个体运动。如图1所示，人群和障碍物状态将映射到二维网格面上，计算个体运动时，每个个体只考虑其局部的环境信息，并估计不同运动方向的运动代价，从中选择代价最小的方向运动。
图1. 模拟方法示意图
3. 方法的计算求解
3.1CPU/GPU计算任务划分
由上面提到的人群模拟方法可知，环境状态的映射是在整个二维网格面上的全局操作，而每个个体的计算又是部分网格上的局部操作，根据这样的计算特点，我们将整个方法分解为在CPU和GPU上的计算任务。
如图2所示，环境信息的映射将在CPU中计算，在每个计算周期，我们将得到的二维环境场送到GPU的只读存储器中，每个个体从中取出部分网格上的信息然后计算运动代价，并随后统一将更新完毕的人群状态信息从GPU中拷回到内存中，提供给下一周期计算使用。
图2. 任务划分
3.2GPU部分的实现
对于GPU部分有三个主要步骤：
1. 初始化全局环境场;
2. 计算每个个体的运动代价;
3. 更新人群状态并返回到内存。
我们利用cudaMemcpy和cudaMemcpy2D函数将全局环境场从内存中拷贝到GPU的设备存储器，作为全局变量存放。由于环境场占用的存储器空间和场景规模相关，我们一般模拟的场景较大，需占用的空间较多，所以选择设备存储器存放全局环境场。
对于kernel函数，我们将每个个体的运动计算看作一个原子任务，一个线程计算一个个体当前Step的运动，在这个函数中，个体估计不同运动方向的运动代价，从中选择代价最小的方向运动，如图3所示。
我们知道，由于设备存储器比芯片存储器的延迟更高、带宽更低，因此应尽量减少设备存储器访问，所以在每个线程初期，我们将每个个体的局部环境场从设备存储器拷贝到线程的共享存储器中，提高操作效率，而且这样也能保证线程间不存在存储体冲突，能进一步保证访问速度。
所有线程计算完毕之后，又通过cudaMemcpy函数将计算结果拷贝回内存中。
图3. GPU部分实现示意图
4. 实验及结果
我们已经将上述算法用于开发群体模拟系统，并以该系统为基础完成我们的实验，下面介绍模拟的三维效果和效率测试结果。
4.1模拟结果
测试场景中既有大量人群的，又有动态障碍物的，如图4所示，我们的方法可以得到较逼真的人群运动轨迹。
图4. 模拟的三维效果
4.2效率测试
测试用机器的配置如下：Intel Core2 Duo E8300 (2.83GHz), 3.5G RAM, NVIDIA GeForce 8800GT (512MB video Memory)。
(a) 2,000人规模 (b) 10,000人规模
图5. 算法计算效率测试结果
如图5所示，与CPU上的计算相比，通过GPU并行计算可以达到二十倍左右的加速比，而且随着模拟人群规模的增大，提升的效果越明显。
5. 小结
在本文中，我们提出一种基于CUDA的大规模人群模拟计算方法，该方法是一种基于个体的计算模型，能比较真实的反映虚拟人群的运动行为，通过CUDA在GPU上实现并行计算，可以达到一定的计算效率。
我们的方法只是使用了CUDA比较基本的特性，也没有为性能的提升做更多的优化，因此，我们也只是希望介绍一些不为人所熟知的应用，借此扩展CUDA的应用领域，同时也为这个方向的研究者提供一些参考。
