计算机科学与探索 ›› 2013, Vol. 7 ›› Issue (2): 180-190.DOI: 10.3778/j.issn.1673-9418.1208036

• 学术研究 • 上一篇    

多核处理器上的并行联机分析处理算法研究

周国亮1,2+,王桂兰3,朱永利1   

  1. 1. 华北电力大学 控制与计算机学院,河北 保定 071003
    2. 冀北电力有限公司 技能培训中心,河北 保定 071051
    3. 华北电力大学 信息与网络管理中心,河北 保定 071003
  • 出版日期:2013-02-01 发布日期:2013-02-01

Parallel On-Line Analysis Processing Algorithms Research on Multi-Core CPUs

ZHOU Guoliang1,2+, WANG Guilan3, ZHU Yongli1   

  1. 1. College of Control and Computer Engineering, North China Electric Power University, Baoding, Hebei 071003, China
    2. Skill Training Center, Jibei Electric Power Company Limited, Baoding, Hebei 071051, China
    3. Center of Information and Network Management, North China Electric Power University, Baoding, Hebei 071003, China
  • Online:2013-02-01 Published:2013-02-01

摘要: 近年来,计算机硬件技术获得了很大发展,尤其是大内存和多核,但算法效率并没有随着硬件技术的发展而提高,根本原因是没有充分利用CPU缓存以及单线程程序设计的局限性。在联机分析处理领域,数据方体计算是一个重要而又耗时的操作,因此如何提高数据方体的计算效率是该领域的一个研究难点。探讨了基于多核CPU特征的并行立方体算法, 提出了MT-Multi-Way(multi-threading multi-way)和MT-BUC(multi-
threading bottom-up computation)算法。该算法通过有效的数据划分和多线程协作,避免了Cache竞争,并确保了负载均衡,获得了近似线性加速比。以上述算法为基础,提出了处理立方体算法的多核框架,包括数据划分策略及递归算法的多核处理,指导立方体算法的并行化。

关键词: 多核处理器, 并行算法, 立方体计算, 框架

Abstract:  Computer hardware technology has greatly developed, especially large memory and multi-core, but the algorithm efficiency dose not improve with the development of hardware. The fundamental reason is the insufficient utilization of CPU cache and the limitation of single-thread programming. In the field of OLAP (on-line analysis processing), data cube computation is an important and time-consuming operation, so how to improve the performance of data cube computation is a difficult research point in this field. Based on the characteristics of multi-core CPUs, this paper proposes two parallel algorithms, MT-Multi-Way (multi-threading multi-way) and MT-BUC (multi-threading bottom-up computation), which utilize data partition and multi-thread cooperation. All these algorithms avoid cache contentions between threads and keep loading balance, so obtain near-linear speedup. Based on these algorithms, this paper suggests one unified framework for cube computation on multi-core CPUs, including how to partition data and resolve recursive program on multi-core CPUs for guiding cube computation parallelization.

Key words: multi-core CPU, parallel algorithm, cube computation, unified framework