第14章 N-体问题

N-体（N-body）计算是一类并行计算模型，该模型由一组粒子（每个粒子称为一个个体）组成，在每个个体的计算中，必须考虑其他所有个体对它的影响。N-体计算的应用例子有如下一些（但是N-体计算并不局限于此）：

• 恒星引力场中的重力模拟。

• 离子静电场中的分子模拟。

• 计算机图形学中用于模拟水和火的粒子系统。
  ·“类鸟群”，一种用来模拟鸟群行为的计算机动画技术。

通常情况下，个体行为的模拟按时间步长进行，因此，对N个个体而言，每个时间步长的计算复杂度为 $O(N^{2})$ 。在大多数模型中，个体间的影响随着距离的增加快速减小，因此需要使用（例如）分层算法，以利用一组个体质心中个体的质量和位置来避免复杂度为 $O(N^{2})$ 的全部计算。Barnes-Hut算法通过引入一个空间层次，来近似计算两组对象之间的作用力，将计算的复杂度减小到 $O(N1gN)$ 。在实际应用中，叶子节点包含K个个体，对于给定的叶子节点必须进行复杂度为

0（K²）的计算。而复杂度为0（K²）的这部分计算是GPU最擅长的。

N-体负载已经被证实为能让GPU达到理论处理能力极限的最有效方式。在Harris等人的《GPU精粹》的“基于CUDA的快速N-体模拟”一章[1]中，频繁引用这个理论极限来解释为什么进一步提高计算性能是不可能的。所使用的英伟达公司的GeForce 8800 GTX GPU在N-体计算任务上是如此的高效，甚至超过了专门设计用来执行天体运算的GRAPE-6硬件。

我们希望读者能够将GPU引入自己的计算中，并且找到运行最快速的方法。本章将展示使用CUDA技术进行N-体及其相关计算的几种不同方式。

·简单的实现方法来说明技术本身，并强调使用高速缓存和循环展开的有效性。
·采用共享内存的实现方法（对于引力计算速度最快的方法），借鉴Harris等人的结果，在最内层循环使用线程块大小的个体集合对计算任务进行分块，以减小访问内存带来的延时。
·采用常量内存的实现方法，这种设计灵感来自于Stone等人的直接库伦求和（Direct Coulomb Summation，DCS）[2]计算，使用常量内存存储个体信息，可以释放共享内存供其他用途使用。

因为读者的应用也许不是N-体之间引力计算，呈现这些不同的实现方法的目的不是单纯地为了针对特定计算进行优化。它们能够根据目标SM构架、问题规模以及核心计算的具体细节改写为不同的实现方法。

既然N-体引力计算已经被作为GPU理论计算能力的典型代表（它能达到400倍的加速比），本章最后一节将提出CPU的优化策略。通过使用SSE指令集和多线程技术重新编写计算代码，可以得到超过300倍的加速比。根据第14-9小节报告的结果，一个GK104构架的GPU，性能显著优于两个英特尔的至强E2670高端服务器CPU。CUDA实现方案相对于优化过的CPU应用，具有运行速度更快、代码可读性强和维护性更好等优点。

贯穿于本章的性能评价，使用的是服务器级的机器，它有2个至强E2670“沙桥”CPU和多达4个GK104构架的GPU，为了减少散热和能耗，这4个GPU被降低了主频。我们报告的性能结果是根据每秒可以计算的个体之间相互作用的次数，而不是GFLOPS结果。