Journal of Shandong University(Engineering Science) ›› 2021, Vol. 51 ›› Issue (3): 7-14.doi: 10.6040/j.issn.1672-3961.0.2019.508

Previous Articles     Next Articles

Median calculation algorithms based on GPU in OLAP

WU Zhenpeng1, ZHANG Jian2, FAN Xingqi3, LI Cuiping4   

  1. 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-20 Published:2021-06-24

PDF (PC)

253

Abstract: 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(n2)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.

Key words: OLAP, GPU, holistic aggregate functions, median

CLC Number: 

  • TP392
[1] CODD E F, CODD S B, SALLEY C T. Providing OLAP(on-line analytical processing)to user-analysts: an IT mandate[J]. White Paper of Arbor Software Corporation, 1993: 125-129.
[2] CODD E F, CODD S B. Beyond decision support[J]. Computer World, 1993, 27(30): 87-89.
[3] CUZZOCREA A, BELLATRECHE L, SONG I, et al. Data warehousing and OLAP over big data: current challenges and future research directions[C] // Proceedings of the Sixteenth International Workshop on Data Warehousing and OLAP. New York, USA: Association for Computing Machinery, 2013: 67-70.
[4] CUZZOCREA A. Data warehousing and OLAP over big data: a survey of the state-of-the-art, open problems and future challenges[J]. International Journal of Business Process Integration and Management, 2015, 7(4): 372-377.
[5] 孙婷婷, 黄皓, 王嘉伦, 等. 面向 CPU-GPU 异构系统的数据分析负载均衡策略[J]. 计算机工程与科学, 2019(3): 417-423. SUN Tingting, HUANG Hao, WANG Jialun, et al. A load balancing strategy on heterogeneous CPU-GPU data analytic systems[J]. Computer Engineering and Science, 2019(3): 417-423.
[6] NVIDIAC. CUDA C++programming guide PG-02829-001_v11.0[EB/OL].(2020-06-01)[2020-06-08]. https://docs.nvidia.com/pdf/CUDA_C_Programming_Guide.pdf.
[7] HARRIS M. Optimizing CUDA. SC07: high performance computing with CUDA[EB/OL].(2009-01-21)[2020-06-08]. http://www.enseignement.polytechnique.fr/profs/informatique/Eric.Goubault/Cours09/CUDA/SC07_CUDA_5_Optimization_Harris.pdf.
[8] YUAN Y, LEE R, ZHANG X. The Yin and Yang of processing data warehousing queries on GPU devices[J]. Proceedings of the VLDB Endowment, 2013, 6(10): 817-828.
[9] SITARIDI E A, ROSS K A. A meliorating memory contention of OLAP operators on GPU processors[C] //Proceedings of the Eighth International Workshop on Data Management on New Hardware. New York, USA: Association for Computing Machinery, 2012: 39-47.
[10] LAUER T, DATTA A, KHADIKOV Z, et al. Exploring graphics processing units as parallel coprocessors for online aggregation[C] //Proceedings of the ACM 13th international workshop on Data warehousing and OLAP. New York, USA: Association for Computing Machinery, 2010: 77-84.
[11] WU H, DIAMOS G, WANG J, et al. Optimizing data warehousing applications for GPUs using kernel fusion/fission[C] //2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum. Piscataway: IEEE, 2012: 2433-2442.
[12] ZHOU G, CHEN H. Parallel cube computation on modern CPUs and GPUs[J]. The Journal of Supercomputing, 2012, 61(3): 394-417.
[13] DORAISWAMY H, VO H T, SILVA C T, et al. A GPU-based index to support interactive spatio-temporal queries over historical data[C] //2016 IEEE 32nd International Conference on Data Engineering(ICDE). Piscataway: IEEE, 2016: 1086-1097.
[14] PAPADIAS D, KALNIS P, ZHANG J, et al. Efficient OLAP operations in spatial data warehouses[C] //International Symposium on Spatial and Temporal Databases. Berlin, Germany: Springer, 2001: 443-459.
[15] ZHANG Y, WANG S, HUANG W. ParaCube: a scalable OLAP model based on distributed aggregate computing with sibling cubes[C] //2010 12th International Asia-Pacific Web Conference. Piscataway, USA: IEEE, 2010: 323-329.
[16] 焦敏,张延松,王珊,等.内存OLAP多核并行查询优化技术研究[J].计算机学报,2014,37(9):1895-1910. JIAO Min, ZHANG Yansong, WANG Shan, et al. Research on multicore parallel query processing techniques for main-memory OLAP[J]. Chinese Journal of Computers, 2014, 37(9): 1895-1910.
[17] 张延松, 肖艳芹,王珊, 等. 主存 OLAP 系统中 what-if 查询处理策略[J]. 软件学报, 2010(10): 2494-2512. ZHANG Yansong, XIAO Yanqin, WANG Shan, et al. What-if query processing policy of main-memory OLAP system[J]. Journal of Software, 2010(10): 2494-2512.
[18] BRESS S, FUNKE H, TEUBNER J. Robust query processing in co-processor-accelerated databases[C] //Proceedings of the 2016 International Conference on Management of Data. New York, USA: Association for Computing Machinery, 2016: 1891-1906.
[19] ALABI T, BLANCHARD J D, GORDON B, et al. Fast k-selection algorithms for graphics processing units[J]. ACM Journal of Experimental Algorithms, 2012, 17(4): 1-29.
[20] SHANBHAG A, PIRK H, MADDEN S. Efficient top-k query processing on massively parallel hardware[C] //Proceedings of the 2018 International Conference on Management of Data. New York, USA: Association for Computing Machinery, 2018: 1557-1570.
[1] LIU Chen, CAI Ting. A localization algorithm based on RSSI vector for wireless sensor networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(3): 23-30.
[2] MI Gang1, WANG Hao2*. Research on a subsurface drip irrigation system of a highway median strip [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(3): 138-142.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] ZHANG Yong-hua,WANG An-ling,LIU Fu-ping . The reflected phase angle of low frequent inhomogeneous[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 22 -25 .
[2] SHI Lai-shun,WAN Zhong-yi . Synthesis and performance evaluation of a novel betaine-type asphalt emulsifier[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(4): 112 -115 .
[3] LI Liang, LUO Qiming, CHEN Enhong. Graph-based ranking model for object-level search
[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 15 -21 .
[4] CHEN Rui, LI Hongwei, TIAN Jing. The relationship between the number of magnetic poles and the bearing capacity of radial magnetic bearing[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(2): 81 -85 .
[5] LI Ke,LIU Chang-chun,LI Tong-lei . Medical registration approach using improved maximization of mutual information[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 107 -110 .
[6] QIN Tong, SUN Fengrong*, WANG Limei, WANG Qinghao, LI Xincai. 3D surface reconstruction using the shape based interpolation guided by maximal discs[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(3): 1 -5 .
[7] ZHANG Ying,LANG Yongmei,ZHAO Yuxiao,ZHANG Jianda,QIAO Peng,LI Shanping . Research on technique of aerobic granular sludge cultivationby seeding EGSB anaerobic granular sludge[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(4): 56 -59 .
[8] WANG Li-ju,HUANG Qi-cheng,WANG Zhao-xu . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(6): 51 -56 .
[9] LIU Zhongguo,ZHANG Xiaojing,LIU Boqiang,LIU Changchun, . The development of ultrasonic characterization of the biological tissue elasticity[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(3): 34 -38 .
[10] . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 92 -95 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd