电脑没有图形处理器(基于图形处理器的球面Voronoi图生成算法优化)

基于四元三角格网距离计算和比较的球面Voronoi图生成算法比对展开算法具有更高的精度，但该算法效率较低，因为需要计算和比较每个格网点与所有种子点之间的距离。针对对，问题，对算法在GPU上通过并行计算实现，然后从GPU共享内存、常量内存和寄存器的访问进行优化。最后，用C语言和CUDA开发了实验系统，并将对优化前后的算法效率与对进行了比较，实验结果表明，合理使用不同的内存可以大大提高算法的效率，并且数据规模越大，加速比越高。

关键词：球体沃罗诺伊图；统一计算设备架构；共享内存；永恒的记忆；注册

随着数字地球的发展，球面Voronoi图(以下简称v图)已广泛应用于全球空间索引[1-2]和球面动力学模拟[3]。与对算法和扩展算法相比，基于四元三角格网单元间距离计算和比较的球面三角图生成算法具有更高的精度。然而，由于需要计算和比较每个格网和所有种子点之间的距离，该算法效率低，不能满足实时应用的需要。

近年来，随着图形处理器技术的飞速发展，其浮点计算能力和内存带宽已经远远超过了中央处理器[6]。英伟达公司开发的统一计算设备架构(CUDA)为GPU增加了一个易用的编程接口，使得GPU并行计算广泛应用于群体行为模拟、三维数据并行可视化、地表测绘等领域。本文通过距离计算和比较，利用CUDA对生成球面v形图。然后，从GPU共享内存、常量内存和寄存器的访问三个方面对对算法进行了优化。最后，利用c和cuda开发了一个实验系统，并将对优化前后的算法效率与对算法进行了比较

1基于qtm的球面Voronoi图并行生成算法如果公式(1)中的定义为QTM，格网，定义为球面上所有QTM 格网的集合，距离函数d定义为球面弧的距离，则公式(1)表示基于QTM的球面v图。

基于QTM 格网[5]之间距离的计算和比较的球形V图生成算法通过计算和比较从每个格网到所有种子点的距离来确定格网单元所属的沃罗诺伊区域。该算法具有计算密集、指令一致、相互独立的特点。本文采用GPU单指令多数据(SIMD)并行计算模型来完成这些运算，算法实现的核函数伪代码如下(Kernel_1)。算法2的优化

CUDA体系结构中有多种可用的内存，如全局内存、局部内存、共享内存、常量内存、寄存器等。每种内存都有不同的空间大小、范围和访问速度。因此，在实现算法时使用不同的内存和不同的访问方法将对对程序的性能产生很大的影响。本文介绍了图形处理器的内存访问(包括共享内存、常量内存和寄存器等)。)由对算法优化。2.1共享内存优化

GPU全局内存位于视频内存中，存储空间大，可以被内核调用的所有线程访问，但是全局内存的访问有很高的内存访问延迟(一次访问需要400 ~ 600个时钟周期)。共享内存是图形处理器芯片中的高速内存，其缓冲区驻留在物理图形处理器上，而不是图形处理器外部的系统内存中。因此，共享内存的内存访问延迟远低于全局内存(仅占全局内存的1%左右)[11-12]。共享内存可以被线程块内，中的所有线程访问，这是以最小的延迟实现线程间通信的方法[11]。但是，共享内存存储空间很小，每个线程块可用的共享内存只有16KB(计算能力为1.1的设备)。在Kernel_1描述的算法中，格网中心点的坐标数据和种子点的坐标数据存储在全局存储器中。当计算从每个QTM 格网到所有种子点的距离时，有必要频繁地从全局存储器获得种子点数据。假设种子点的数量为n，球上QTM 格网的总数为G，生成球形V-图所需的计算和比较的总数为2NG，所需的全局内存访问的数量为(G NG)，比例为2NGG21。也就是说，每两次计算(或比较)都需要访问全局内存，这将严重影响算法的效率。

共享内存阶段对比全局内存具有更高的内存访问速度，因此种子点数据可以从全局内存中取出并存储在线程块内的所有线程的共享内存中(每个线程处理一个格网)，并且每次计算只需要从共享内存中读取数据。但是，由于每个线程块可用的共享内存只有16KB，当种子点的数量很大时，它不能一次放入共享内存。这需要分成几次。每次，种子点数据的一部分被放入共享存储器。当使用这部分数据时，取出一部分种子点数据进行计算，该计算顺序进行，直到计算完所有种子点。算法的伪代码如下(内核2)。如果每个线程块中的线程数为B，则每个线程块内的计算和比较的总数为2NB，全局存储器访问的次数为(B=N)(包括从全局存储器中获取B个QTM 格网数据和N个种子点数据)，则计算(或比较)次数与全局存储器访问次数的比率为2NB:(B=N)=2n:(1N/B)。如果N=1024，B=256，计算与内存访问时间的比率为2048: 5 400: 1。与原算法相比，该对算法大大减少了全局内存访问次数，提高了算法效率。