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

吴振鹏¹,张健²,范星奇³,李翠平⁴

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

出版日期:2021-06-20发布日期:2021-06-24

作者简介:吴振鹏(1988— ),男,山东潍坊人,工学硕士,助理工程师,主要研究方向为数据仓库与基于GPU的高性能计算. E-mail:wzpcapf0502@ruc.edu.cn

Median calculation algorithms based on GPU in OLAP

WU Zhenpeng¹, ZHANG Jian², FAN Xingqi³, LI Cuiping⁴

1. Shandong Provincial Corps, Chinese People's Armed Police Force, Jinan 250116, Shandong, China;
2. Liaoning Provincial Corps, Chinese People's Armed Police Force, Shenyang 110000, Liaoning, China;
3. School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China;
4. School of Information, Renmin University of China, Beijing 100872, China

Online:2021-06-20Published:2021-06-24

摘要/Abstract

摘要： 针对联机分析处理(online analytical processing, OLAP)中的整体型聚集函数中位数,提出基于图形处理单元(graphics processing unit, GPU)的GPU-Median算法,通过对数据进行划分,分段排序,不断裁剪全局中位数之前的数据,对未裁剪的数据进行合并,得到最终的中位数,避免了全局的排序时间。提出GPU-Median+算法,对GPU-Median算法进行优化和扩展,使用CPU与GPU协同作业实现聚集操作,利用GPU处理每个队列的数据,CPU处理全局数据。试验和分析证明,相比CPU算法,GPU-Median+算法将中位数计算的时间复杂度从O(n²)降低到了O(n);相比GPU上的基数排序算法,GPU-Median+算法的计算时间减少了三分之一。该算法的应用使得GPU计算OLAP中的整体型聚集函数时,发挥出更加优良的并行计算能力,为提升OLAP的查询性能提供了新的思路。


PDF全文下载地址:

http://gxbwk.njournal.sdu.edu.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=2032