Parallel H-Tree Based Data Cubing on Graphics Processors
    Download PDF
Baoyuan Wang,Yizhou Yu. Parallel H-Tree Based Data Cubing on Graphics Processors. International Journal of Software and Informatics, 2012,6(1):61~87
Hits: 3160
Download times: 1656
Fund:This work is sponsored by Institute of Software, the Chinese Academy of Sciences, China and partially supported by National Natural Science Foundation of China under Grant No. 60728204/F020404, National Science Foundation (IIS 09-14631).
Abstract:Graphics processing units (GPUs) have an SIMD architecture and have been widely used recently as powerful general-purpose co-processors for the CPU. In this paper, we investigate efficient GPU-based data cubing because the most frequent operation in data cube computation is aggregation, which is an expensive operation well suited for SIMD parallel processors. H-tree is a hyper-linked tree structure used in both top-k H-cubing and the stream cube. Fast H-tree construction, update and real-time query response are crucial in many OLAP applications. We design highly efficient GPU-based parallel algorithms for these H-tree based data cube operations. This has been made possible by taking effective methods, such as parallel primitives for segmented data and efficient memory access patterns, to achieve load balance on the GPU while hiding memory access latency. As a result, our GPU algorithms can often achieve more than an order of magnitude speedup when compared with their sequential counterparts on a single CPU. To the best of our knowledge, this is the first attempt to develop parallel data cubing algorithms on graphics processors.
keywords:SIMD  GPGPUs  data cubing  H-tree  OLAP
View Full Text  View/Add Comment  Download reader



Top Paper  |  FAQ  |  Guest Editors  |  Email Alert  |  Links  |  Copyright  |  Contact Us

© Copyright by Institute of Software, the Chinese Academy of Sciences
ICP: Jing ICP Bei No.10016592

京公网安备 11040202500065号