论文部分内容阅读
21世纪人们迎来了大数据时代,随着互联网与云计算的兴起,特别是移动设备和互联网结合的越来越紧密,每个人每时每刻都在产生与消费大量的数据。对于服务供应商而言,如何处理这些数据并从这些数据中得到有价值的信息成为了棘手的难题。为了解决这一难题,在数据处理方面人们开发了许多大数据处理框架,然而由于数据量过大,传统的基于CPU的计算模型已经无法满足海量数据的计算需求;另一方面,GPU由于其结构天生适合并行运算逐渐引起了人们的关注,并且越来越多的计算框架专门开发了基于GPU的版本来提高性能。尽管GPU天生适合并行计算,但它由于数据容量有限且和内存数据交换性能开销大,并且由于GPU本身具有的逻辑控制单元很少,这些因素造成了单独的G PU只能处理较小规模的数据并且只能进行易于分解的计算任务而不能像CPU一样执行复杂的逻辑判断。特别地,在执行图计算任务方面,由于warp内线程负载不均衡而导致的同步开销以及图的不规则性导致的访存不连续形成了GPU性能的瓶颈。为了更加清晰地探索GPU性能优化的方向以及其可行性,本文由一种基础的想法到几种过渡的模型,最后得出性能提升较优的基于二分查找/插值查找的两阶段负载调度算法。在二分查找中,每个线程通过前缀求和数组找到自身负责的工作单元。在最好情况下一次就能找到目标值,而最坏情况下需要2logN次访存操作。实际上每次迭代中每个线程需要执行两次访存操作分别访问左端和右端的元素比较大小以更新m的值。同时,由于每个线程并发进行搜寻时需要等待barrier的数据同步,而至少有一个线程需要执行2logN次操作,因此一次完整的二分查找复杂度就是2logN。之后为了印证该算法对于GPU性能的提升设计了多个实验,GPU将会通过执行四种常见的图计算算法测试性能提升。为了使得我们对于GPU的性能有一个更为清晰的认识,还设计了多个对照组,分别会使用CPU与GPU配合其他几种调度模型执行相同的算法。更进一步,我们还采用了不同的数据集以及多个迭代次数与样本容量来探究该方案对于性能优化的优劣势。经过实验,根据平均每次迭代w arp使用情况以及执行时间论证了该算法的有效性。并且还得出了最优的block大小以获取最优的性能。