OLAP中基于GPU的中位数计算算法  

Median calculation algorithms based on GPU in OLAP

作　　者：吴振鹏 张健 范星奇 李翠平[4] WU Zhenpeng;ZHANG Jian;FAN Xingqi;LI Cuiping(Shandong Provincial Corps,Chinese People's Armed Police Force,Jinan 250116,Shandong,China;Liaoning Provincial Corps,Chinese People's Armed Police Force,Shenyang 110000,Liaoning,China;School of Mechanical Engineering,Shanghai Jiao Tong University,Shanghai 200240,China;School of Information,Renmin University of China,Beijing 100872,China)

机构地区：[1]中国人民武装警察部队山东省总队,山东济南250116 [2]中国人民武装警察部队辽宁省总队,辽宁沈阳110000 [3]上海交通大学机械与动力工程学院,上海200240 [4]中国人民大学信息学院,北京100872

出　　处：《山东大学学报（工学版）》2021年第3期7-14,共8页Journal of Shandong University（Engineering Science）

摘　　要：针对联机分析处理(online analytical processing, OLAP)中的整体型聚集函数中位数,提出基于图形处理单元(graphics processing unit, GPU)的GPU-Median算法,通过对数据进行划分,分段排序,不断裁剪全局中位数之前的数据,对未裁剪的数据进行合并,得到最终的中位数,避免了全局的排序时间。提出GPU-Median+算法,对GPU-Median算法进行优化和扩展,使用CPU与GPU协同作业实现聚集操作,利用GPU处理每个队列的数据,CPU处理全局数据。试验和分析证明,相比CPU算法,GPU-Median+算法将中位数计算的时间复杂度从O(n^(2))降低到了O(n);相比GPU上的基数排序算法,GPU-Median+算法的计算时间减少了三分之一。该算法的应用使得GPU计算OLAP中的整体型聚集函数时,发挥出更加优良的并行计算能力,为提升OLAP的查询性能提供了新的思路。An algorithm for one of the holistic aggregate operations in online analytical processing(OLAP) called Median was proposed based on graphics processing unit(GPU), which was named GPU-Median algorithm. This algorithm obtained the median of a series of data by segmenting the data, sorting the data by segments, cutting the data preceding the global median, and finally merging the uncut data. Through the algorithm above much time spent on global sorting was saved. Then an algorithm called GPU-Median+was presented in order to optimize and extend the GPU-Median algorithm. This algorithm implemented the aggregate operations through the collaboration of CPU and GPU, which used GPU to deal with segments of data and CPU to deal with global data. Experiments and analysis proved that the GPU-Median + algorithm reduced the time complexity of the median calculation from O(n^(2)) to O(n) compared to the CPU algorithm, and that the GPU-Median + algorithm reduced a third of the calculation time compared to the radix sort algorithm on the GPU. The application of this algorithm enabled the GPU to improve its ability of parallel calculations when calculating the holistic aggregate function in OLAP, thus providing a new idea for improving the query performance of OLAP.

关 键 词：联机分析处理 图形处理单元 整体型聚集函数 中位数 

分 类 号：TP392[自动化与计算机技术—计算机应用技术]