CN105468439A - 在cpu-gpu异构框架下遍历固定半径内邻居的自适应并行算法 - Google Patents

Abstract

本发明公开了一种在CPU-GPU异构框架下遍历固定半径内邻居的自适应并行算法，该算法中使用了一个新的并行模型从而让GPU的各种特性能够和问题本身的性质相契合。该算法首先引入自适应并行的概念来对GPU中各个线程进行重组，从而让物理上相邻的线程能够处理逻辑上相似的工作，这样GPU中的很多局部性特征能够得到利用。其次，使用了CPU-GPU异构框架，让CPU协同处理一些由于使用自适应并行产生的一些对于GPU来说低效率的事务。为了显示出本发明的特点，其被运用到光滑了粒子流体动力学方法（SPH）上并跟现有方法进行了对比，并在处理大规模高密度粒子的问题上体现出了很大的优势。

Description

在CPU-GPU异构框架下遍历固定半径内邻居的自适应并行算法

技术领域

本发明属于高性能计算领域，具体地说是一种基于自适应并行方法在CPU-GPU异构框架下的新的遍历固定半径内邻居的并行算法，涉及到SIMD架构，GPU硬件特性，异构平台下的任务调度与负载均衡，数据交互策略，计算机图形学以及仿真等。

背景技术

FNN问题是处理在多维度欧几里德空间中，所有在给定距离内的点与点之间的交互的问题。而固定网格算法是其中最被广泛使用的方法，特别是在数值方法中。这个算法广泛应用于自然环境的模拟，生物仿真，行为模拟以及三维重建。通过这个算法，可以将构建邻居信息的时间复杂度降到O(wn)(如果使用不基于比较的排序算法)，而遍历邻居的时间复杂度降为O(3^kwnN)，其中w是排序关键字长度，n是空间中点的数量，k是空间维度，N是每一个单元格中点的数量的上限。

为了提升上述算法的性能，一个可行的方案是在多核处理器，特别是诸如GPU这种SIMD加速器上来实现上述算法。由于这个算法非常适合并行化，因此在GPU上已经有了一些针对这个算法比较成熟的并行模型。并且这些传统的并行模型能够在点密度比较低的情况下得到非常好的性能。在传统并行模型中，GPU内核程序的线程网格中所包含的线程数量是和空间中点的数量是相同的。然后这些线程被直接划分为包含线程数量相同的几个线程块，然后在GPU中以这些线程块为单位进行调度运算。每个线程所作的工作就是读取它们所负责的那一个点的一个邻居点的信息然后做一些运算，如此循环直到所有邻居都访问到了。每个线程块的工作就是读取其所负责的所有点的所有邻居，并做相应的运算。

然而，随着点密度的提升，传统的并行模型的性能下降得非常厉害。这是由于传统方法会带来一个线程块中的不同线程的负载不均衡以及内存访问的不一致。这是由于这种简单的线程划分策略导致的：一个线程块内的线程所负责的点往往会分布在几个不同的单元格中，而不同单元格中的点的邻居以及邻接单元格中点的数量都是不一致的，从而导致串行化的内存访问以和分支的产生。并且由于这种不一致性，很难利用GPU中的层次线程和存储单元的特性。图1就展示了传统并行模式下的状况，其中网格块是代表了在当前循环中有点正在被访问的单元格，虚线方块是已经被访问过的单元格，c是一个线程块所负责点所分布的单元格的数量，这个迭代循环会持续1次，其中nc是邻接单元格的数量，np_ij是线程块内第j个单元格的第i个邻接单元格中点的数量。

另一方面，随着GPGPU技术的不断发展，在一些诸如CUDA和OpenCL这些主流的GPGPU平台上，自适应并行技术(在这些主流平台上被称为动态并行)被逐渐得到支持。而这个技术能够使得计算资源按需分配。从而避免了上一段所说的对计算和存储资源的浪费，从而增加了系统的并行效率。

同时，目前主流的主机往往配备有CPU和GPU。传统的并行模型往往会利用主机中最适合的处理器(CPU或GPU)来计算某个指定问题，而其他设备则闲置了，这是对计算资源的浪费。而针对固定网格算法来处理固定半径内的邻居问题，特别是在GPGPU的出现开始，往往只交给GPU来处理。尽管CPU在处理这个问题方面性能不及GPU，但是合理利用CPU的计算资源来协助GPU还是一项非常有意义的工作。

发明內容

本发明的目的是提供一种在CPU-GPU异构框架下遍历固定半径内邻居的自适应并行算法，该算法在于充分利用主流单节点主机的所有计算能力，来更快速地用基于固定网格算法来处理FNN问题。

本发明的目的是这样实现的：

一种在CPU-GPU异构框架下遍历固定半径内邻居的自适应并行算法，它包括以下步骤：a)基于固定网格法将空间划分为互不相交的单元格，通过遍历邻接单元格中的点来寻找所有在固定范围内的其他点；

b)GPU自适应并行模型

ⅰ)大量GPU内核程序的组织与调度

1)从CPU上发射GPU父内核程序，该内核程序中每一个线程负责空间中一个单元格的计算；

2)每个父内核程序线程计算其所负责的单元格内的点的数量、点在内存中的存储范围、计算这些点所需要的线程及内存资源；

3)每个父内核程序线程根据所需要的线程以及内存资源，使用GPU动态并行快速地为其所负责的单元格发射一个GPU子内核程序来负责该单元格中点的计算；子内核程序中的线程数量依赖于单元格中点的数量；

ⅱ)GPU内存访问优化

1)为每个子内核程序中的线程块在共享内存中开辟足够存放W个点的必要数据的空间；其中，W是SIMD硬件能够同时执行的指令数量；在时下主流的GPU中这个值为32；

2)每个子内核程序中的线程块中的前W个线程读取W个邻居点的数据到共享内存中；通过GPU全局内存的合并访问从而在一次全局内存访问中读取多个点的数据；

3)每个子内核程序中的线程读取在共享内存中的W个邻居信息并做相应的处理；

4)重复本步骤2)和3)直到对于该子内核程序所负责的单元格的所有邻接点的数据都被访问过；

c)CPU-GPU协同计算模型：

根据GPU自适应并行模型的缺陷，让CPU协同计算

ⅰ)CPU-GPU数据传输优化

CPU和GPU使用不同的存储空间，当需要进行数据同步时，两者进行频繁的数据交换，优化步骤具体包括：

1)任务分配策略：将包含点少的单元格交给CPU处理，其余的给GPU处理；

2)将计算工作进行分组：将整个计算区域分成几个子区域，点根据其在空间中的位置信息来确定其所在的子区域；计算将以子区域为单位计算，为了区域间的负载均衡，每个子区域所包含的点的个数是相近的；

3)重叠计算与数据传输：以本步骤2)中所分的子区域为单位进行计算；当一个子区域中的点计算完毕后，马上将结果传到对端即CPU计算完毕后将结果传到GPU的存储空间中，反之亦然；

4)新的数据组织方式：将给CPU和GPU处理的点的数据集中在一起，得以较小的成本调度大量的数据，并减少大量的冗余计算；

5)根据上述要求，建立一套新的空间中点的排序规则，将点的数据在计算之前进行排序，能够高效访问和快速定位；使用以上信息构成一个用于对点的数据进行排序的哈希值，并根据该值使用基数排序或者计数排序对点的数据进行排序；

ⅱ)负载均衡策略

使用动态负载均衡策略，以保证CPU和GPU能根据自己的计算能力的特性，分配到适合的工作以及合理的工作量；

1)一组指代单元格中点的数量的阀值来决定某个点是由CPU还是GPU来计算；为每一个计算工作分组设定一个阀值；

2)如果CPU和GPU的运算时间之比在[α,β](0<α<β<1)范围之内，则不调整两者的工作量；

3)如果GPU的耗时较低，则直接调整一组阀值中的其中一个来增加GPU的工作量；

4)如果CPU耗时较低，将使用如下方法增加CPU的工作量：

a)预测更改了阀值之后的CPU计算量w_f＝w_o+w_△，其中w_f为预测工作量，w_o为原有工作量，w_△为工作增加量；

b)预测计算时间其中，t_cpu为上一次计算CPU的耗时，为预测耗时；

c)判断其中，t_gpu为上一次计算GPU的耗时，如果是真，则修改阀值以增加CPU的计算量。

本发明的有益效果：

本发明被运用于SPH方法模拟流体，并以此来检测其性能，SPH方法中有密度计算和力计算两个部分涉及到FNN问题。GPGPU平台使用的是CUDA，并且使用自己开发的CPU-GPU异构框架，CPU方面的多线程框架是基于生产者消费者模型开发，这个模型被广泛运用于处理大规模并发事务的多线程服务器中。

附图说明

图1为传统并行模式中GPU全局内存的串行访问过程图；

图2为只适用GPU动态并行而没有CPU协同计算的范例图；

图3为使用了CPU协同处理的范例图；

图4为从CPU和GPU分别发射32768个子内核程序的耗时对比图；

图5为发射不同数量子内核程序的耗时对比图；

图6为本发明中提出的基于点的空间信息的哈希值位结构图；

图7为405,224粒子的情况下，前500个时间步的采样图；

图8为本发明未包含CPU-GPU协同计算和现有方法在10个测试样例中的对比图；

图9为本发明是否利用CPU协同计算的耗时比例图；

图10为CPU与GPU在405224个粒子下前500个时间步下耗时对比图。

具体实施方式

以下结合附图对本发明作详细说明。

概要设计

和传统方法一样，在本发明中，模拟空间被视为一个网格，由很多不相交的单元格组成。每一个空间中的点必定落在其中一个单元格中。并且单元格的边长就是查找半径的长度。于是，每个点只需要遍历其所在的单元格以及这个单元格周围的单元格中的点就能找到所有距离其指定距离内的所有的点。通过这种算法，可以将原先时间复杂度为O(n²)的暴力求解方法下降到O(3^kwnN)。

为了克服传统方法中一个线程块中的不同线程的负载不均衡以及内存访问的不一致问题，本发明提出了自适应并行的方法，让一个线程块内的线程所负责的点处在同一个单元格中。应用程序可以动态地使用高分辨率的子线程网格来处理一些需要大量计算的区域，而不用浪费任何资源在那些不需要计算的区域上，如图2所示，其中Kernel_1中的波浪线代表那些处理对GPU来说比较棘手的工作的线程，Kernel_3包含了相对而言比较少的线程。

但是使用这种自适应并行技术是有代价的。当决定使用这种技术的时候，必须要保证其所带来的利益至少能抵消使用其所带来的成本。所以，使用了CPU-GPU异构架构，让CPU去处理那些对于GPU来说处理成本比较高、不能充分利用自适应并行技术的部分，如图3所示，可以看到图2中Kernel_1和Kernel_3中的线程的任务交给了CPU处理。

GPU上的自适应并行

⑴大规模任务规划与调度

在GPU中，由于一个线程网格中每个线程块的数量是相同的，所以最好的方法是为每个单元格发射一个GPU内核程序。假设计算空间是三维欧几里德空间，并且整个空间被划分为32×32×32＝32768个单元格，那么就需要发射32768个内核程序。比较直接简单的方式是通过CPU发射这么多内核程序。尽管CPU调用GPU内核程序是异步的，但是这还是会导致大量CPU与GPU的通信，会严重影响性能，因此，使用动态并行技术，在GPU中发射内核程序是比较好的方式，图4是两种方式的对比，所以使用的测试样例一共发射32768个子内核程序，每个内核程序包含了256个线程做向量加法运算。于是，最好的方法是由CPU发射的父内核程序，其线程网格包含的线程数量和单元格数量相同；然后在GPU中，其中每个父内核程序中的线程根据自己所负责的单元格所包含的点的个数发射子内核程序。

⑵内存访问优化

在这里，本发明提出了一个新的共享内存的使用方案。共享内存是GPU中芯片内存储单元，和L1缓存公用一块存储介质，速度快但是容量小，过多的使用会导致每个多处理器同时处理更少的线程块，从而降低并发度。本发明使用的方案能够同时到达对共享内存的高效利用并非常节省资源。并且这种方式还能充分利用全局内存的统一读取机制，使得耗时的全局内存访问次数降低。在本发明中，让共享内存同时存储最多W个邻居点的数据，W取决于SIMD硬件同时执行的指令数量，在最新的GPU中一般这个值是32。每次线程块中前W个线程读取W个邻居的数据到共享内存，然后线程块中的所有线程从共享内存中读取这些邻居信息并进行计算。而这W个邻居是处于同一个邻接单元格中的，他们在物理内存上也是邻近的，因此全局内存的统一读取机制也会起作用，一次全局内存的访问可以同时读取多个邻居的数据。

随后，所有子内核程序中的线程从共享内存中依次获取邻居的数据。在每一次迭代中，每个线程所访问的数据是一致的，不会出现存储体冲突的问题，再加一次共享内存访问只需要1-2个时钟周期，这种数据访问方式是非常快且高效的。当每个线程获得一个邻居的数据之后，就能够进行相应的处理，然后再去共享内存中读取另一个邻居的数据，直到共享内存中的邻居都被遍历过一次。之后就是重复上一段所述的过程，再次从全局内存中读取其他邻居的数据到共享内存，然后从共享内存中读取邻居数据并做处理。

另外，每个单元格自己的点的数据被存放在寄存器中。SIMD处理器的寄存器往往非常多，一般都能容下一个单元格中的点的数据。

CPU--GPU协同计算

⑴任务分配策略

图5显示了动态并行发射不同数量子内核程序所需要的耗时，这些子内核程序没有任何计算，发射之后就马上返回。从图中可以看出动态并行所需要的代价，因此当选择用这个技术时，需要保证物有所值。在实际的应用中，某些单元格往往会包含比较少的点，而为这样的单元格去创建一个子内核程序去处理往往是不划算的。而另一方面，CPU则比较擅长处理这种比较独立的事务。因此本发明的CPU-GPU协同计算框架的设计主要是让CPU去处理那些对于之前所提的并不适合让GPU自适应并行模型所处理的问题。详细的讲，就是让CPU去处理那些所包含点比较少的单元格中的点。

⑵数据传输优化

在很多涉及到FNN问题的应用中，总是包含多个涉及到FNN的阶段以及多个需要完全在GPU或是CPU上处理的阶段。并且前一个阶段的结果往往要被后一个阶段所使用。又由于CPU和GPU使用不同的内存空间，所以频繁的数据交互是无法避免的。而大量数据的交互往往是比较耗时的，因此需要尽力缩短这方面的消耗。

让计算和数据传输重叠的做法往往是非常有效的并且切实可行的。如果CPU上用于存储数据的内存是非分页式的，那么可以通过DMA(DirectMemoryAccess)来异步高效地和PCI-E设备进行数据传输。而另一方面，一般现代GPU都至少包含一个计算引擎队列和一个数据拷贝引擎队列，所以重叠数据传输和计算也是可行的。

为了实现数据传输和计算的重叠，本发明还将整个空间划分为多个子区域，然后对每个子区域分别处理。这样，当一个区域的数据计算完毕后，便立刻进行数据传输，与此同时，另一个区域开始被计算，如同流水线一样。

传统并行模型中，点的数据是仅仅根据点所在的单元格来进行存放的，属于一个单元格的点是存放在一起的。由于本发明交给CPU计算的点往往分布在包含点比较少的单元格中，因此需要遍历所有的单元格来判断某个点属于哪个处理器负责，以及判断处理完的数据的传输方向(从CPU到GPU还是从GPU到CPU)。然后为每个单元格的数据进行一次CPU与GPU之间的数据传输。这个过程的计算量非常大，并且会产生大量的CPU与GPU之间的通信。如果能让CPU和GPU负责的数据分开存放，那么消耗会减少很多。因此本发明制定了更加复杂的点数据的排序规则：

●为了重叠数据传输和计算，处在不同子区域的点需要被分开

●为了降低数据传输次数，点的数据需要根据其所在的单元格中所包含的点数据进

●行排序

●为了高效的内存访问和定位，属于同一个单元格的点应该被放在一起

由于本发明中使用了较为复杂的排序规则，一般情况下使用基于比较的排序算法会比较简单，但是为了系统的性能，仍然决定改进方法使其能够使用不基于比较的排序算法，把这些比较信息浓缩到一个关键字中，图6就是本发明中所使用的新的空间哈希值的结构。通过这个，可以用不基于比较的排序算法高效地按照上述要求对数据进行排序。

另外，为了快速定位内存中的数据，在本发明中还需统计如下信息：

●每个单元格开始和结束的索引，这样就可以知道每个单元格在内存中的范围和点的数量

●每一个子区域开始的地方，这样可以知道每个子区域的内存范围

●单元格包含点个数的索引，记录了小于等于某个指定值的单元格在内存中的范围，这个指定值一般是这样可以快速定位到某个子区域中，包含小于等于某个指定值的点在内存中的存储范围。

注意的是，传统并行模型并不需要统计上述信息，因此本发明在这方面会花费更多的时间。

⑶负载均衡策略

由于CPU和GPU计算能力的差异，针对他们的负载均衡策略是必须的。本发明使用的是基于经验主义的动态负载均衡方法。在本发明中并没有考虑数据传输的消耗，这是因为总是大于1并且大多数数据传输都能被重叠掉，其中O为数据传输大小，Q为数据传输带宽。在本发明中并使用一个阀值来决定和调整任务在CPU和GPU之间的分配，如果某个单元格中的点的个数小于这个阀值，则交给CPU计算，反之交给GPU计算。CPU能够根据单元格包含点个数的索引来快速判断出那些点是它负责处理的；在GPU中，父内核程序中的每个线程会将其所负责的单元格中的点的数量和阀值进行比较，来决定是否发射一个子线程来处理单元格内点的计算。对于那些应用中有多个阶段涉及到FNN问题，可以使用多个不同的阀值，这是因为不同阶段的计算特性是不一样。

每当一个时间步结束的时候，CPU和GPU所消耗的时间会被统计下来，根据这个耗时来实时地对任务分配进行调整。本发明中设定了一对阀值α,β(0<α<β<1)，如果不在这对阀值范围内，则对任务分配阀值进行调整。当GPU所消耗时间比较少时，直接调整阀值给以为GPU添加任务。由于在相同的时间间隔内，GPU能够比CPU处理更多的任务，因此本发明中使用更加谨慎地添加CPU的任务，从而保证在让CPU协助运算的同时不降低整个系统的运行效率详细的方法如下：

1.预测更改了阀值之后的CPU计算量w_f＝w_o+w_△，其中w_f为预测工作量，w_o为原有工作量，w_△为工作增加量；

2.预测计算时间其中，t_cpu为上一次计算CPU的耗时，为预测耗时；

3.判断其中，t_gpu为上一次计算GPU的耗时，如果是真，则修改阀值以增加。

表1是测试案例的列表，每个样例之间的粒子数目相差100,000左右，图7是测试样例4的模拟状况。由于不同的粒子数被用来模拟相同质量和初始状态的液体，随着粒子数的上升，每个粒子的邻居粒子的数目也会快速上升，从而计算量大幅度上升。通过将本发明在SPH方法上的应用与Herault等人提出的传统并行模型以及Goswami等人提出的使用共享内存的方法来说明本发明的优势。

图8显示了本发明(只用GPU)和之前方法在10个测试样例中每一个时间步的平均耗时的对比。Herault等人的传统并行模型在低密度粒子的情况下表现最好，但是随着粒子密度的上升，性能下降得很厉害，而Goswami等人的方法和本发明随着粒子数量上升，性能下降并没有那么明显，这是这两者极大的减少了冗余的全局内存访问。由于GPU中各种层次内存访问方法的改进，本发明比起Goswami等人的方法要好得多。

图9是本发明在10个测试样例中是否利用CPU协同计算的对比图。CPU/GPU混合架构和只用GPU的耗时用实线表示。虚线表示在密度和力计算阶段，GPU所分别负责的粒子的比例。可以看到，由于CPU的协助所降低的时间比例比CPU从GPU那分配来的粒子数的比例更多，这说明在本发明中，成功地让CPU处理了那些对于GPU来说更加棘手的工作，从而说明本发明的任务分配策略是着实有效的。

图10是CPU-GPU系统计算下两者在500帧中所耗时间的对比，本发明中的负载均衡策略试图保证CPU的计算时间是GPU的60％～90％。从结果来看这个目标大致是达到的。

表1测试样例

。

Claims (1)

1.一种在CPU-GPU异构框架下遍历固定半径内邻居的自适应并行算法，其特征在于包括以下步骤：

a)基于固定网格法将空间划分为互不相交的单元格，通过遍历邻接单元格中的点来寻找所有在固定范围内的其他点；

b)GPU自适应并行模型

ⅰ)大量GPU内核程序的组织与调度

1)从CPU上发射GPU父内核程序，该内核程序中每一个线程负责空间中一个单元格的计算；

2)每个父内核程序线程计算其所负责的单元格内的点的数量、点在内存中的存储范围、计算这些点所需要的线程及内存资源；

3)每个父内核程序线程根据所需要的线程以及内存资源，使用GPU动态并行快速地为其所负责的单元格发射一个GPU子内核程序来负责该单元格中点的计算；子内核程序中的线程数量依赖于单元格中点的数量；

ⅱ)GPU内存访问优化

1)为每个子内核程序中的线程块在共享内存中开辟足够存放W个点的必要数据的空间；其中，W是SIMD硬件能够同时执行的指令数量；在时下主流的GPU中这个值为32；

2)每个子内核程序中的线程块中的前W个线程读取W个邻居点的数据到共享内存中；通过GPU全局内存的合并访问从而在一次全局内存访问中读取多个点的数据；

3)每个子内核程序中的线程读取在共享内存中的W个邻居信息并做相应的处理；

4)重复本步骤2)和3)直到对于该子内核程序所负责的单元格的所有邻接点的数据都被访问过；

c)CPU-GPU协同计算模型：

根据GPU自适应并行模型的缺陷，让CPU协同计算

ⅰ)CPU-GPU数据传输优化

CPU和GPU使用不同的存储空间，当需要进行数据同步时，两者进行频繁的数据交换，优化步骤具体包括：

1)任务分配策略：将包含点少的单元格交给CPU处理，其余的给GPU处理；

2)将计算工作进行分组：将整个计算区域分成几个子区域，点根据其在空间中的位置信息来确定其所在的子区域；计算将以子区域为单位计算，为了区域间的负载均衡，每个子区域所包含的点的个数是相近的；

3)重叠计算与数据传输：以本步骤2)中所分的子区域为单位进行计算；当一个子区域中的点计算完毕后，马上将结果传到对端即CPU计算完毕后将结果传到GPU的存储空间中，反之亦然；

4)新的数据组织方式：将给CPU和GPU处理的点的数据集中在一起，得以较小的成本调度大量的数据，并减少大量的冗余计算；

5)根据上述要求，建立一套新的空间中点的排序规则，将点的数据在计算之前进行排序，能够高效访问和快速定位；使用以上信息构成一个用于对点的数据进行排序的哈希值，并根据该值使用基数排序或者计数排序对点的数据进行排序；

ⅱ)负载均衡策略

使用动态负载均衡策略，以保证CPU和GPU能根据自己的计算能力的特性，分配到适合的工作以及合理的工作量；

1)一组指代单元格中点的数量的阀值来决定某个点是由CPU还是GPU来计算；为每一个计算工作分组设定一个阀值；

2)如果CPU和GPU的运算时间之比在[α,β](0<α<β<1)范围之内，则不调整两者的工作量；

3)如果GPU的耗时较低，则直接调整一组阀值中的其中一个来增加GPU的工作量；

4)如果CPU耗时较低，将使用如下方法增加CPU的工作量：

a)预测更改了阀值之后的CPU计算量w_f＝w_o+w_△，其中w_f为预测工作量，w_o为原有工作量，w_△为工作增加量；

b)预测计算时间其中，t_cpu为上一次计算CPU的耗时，为预测耗时；

c)判断t_wf<t_gpu×β，其中，t_gpu为上一次计算GPU的耗时，如果是真，则修改阀值以增加CPU的计算量。