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

• 作者: 吴振鹏 张健 范星奇 李翠平
• 来源期刊: 山东大学学报（工学版）
• 关键词: 联机分析处理 图形处理单元 整体型聚集函数 中位数
• 年，卷（期）: 2021,（3）
• 所属期刊栏目: 机器学习与数据挖掘|Machine Learning & Data Mining
• 页码范围: 7-14
• 页数: 8页
• 分类号: TP392
• 语种: 中文
• DOI: 10.6040/j.issn.1672-3961.0.2019.508

摘要

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