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

doi:10.3778/j.issn.1673-9418.1208036

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

• 学术研究 • 上一篇

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

周国亮1，2+，王桂兰3，朱永利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. 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

摘要/Abstract

摘要： 近年来，计算机硬件技术获得了很大发展，尤其是大内存和多核，但算法效率并没有随着硬件技术的发展而提高，根本原因是没有充分利用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

周国亮，王桂兰，朱永利. 多核处理器上的并行联机分析处理算法研究[J]. 计算机科学与探索, 2013, 7(2): 180-190.

ZHOU Guoliang, WANG Guilan, ZHU Yongli. Parallel On-Line Analysis Processing Algorithms Research on Multi-Core CPUs[J]. Journal of Frontiers of Computer Science and Technology, 2013, 7(2): 180-190.

[1]	李佩琦，郁龚健，华夏，刘家航，柴志雷. PEST：由PYNQ集群实现的高能效NEST类脑仿真器[J]. 计算机科学与探索, 2021, 15(11): 2127-2141.
[2]	廖芸，张骁，廖士中. 统一框架下在线核选择的竞争性分析[J]. 计算机科学与探索, 2020, 14(7): 1126-1132.
[3]	王丰，张俊. KRust:Rust形式化可执行语义[J]. 计算机科学与探索, 2019, 13(12): 2008-2014.
[4]	耿璐，李艳娟. 结合JADE和CoDE差分算子的人工蜂群算法[J]. 计算机科学与探索, 2019, 13(12): 2103-2116.
[5]	田家源，杨东华，王宏志. 面向互联网资源的医学命名实体识别研究[J]. 计算机科学与探索, 2018, 12(6): 898-907.
[6]	景翠萍，廖丽，王伟. 面向非结构网格应用并行程序的编程工具[J]. 计算机科学与探索, 2018, 12(2): 252-262.
[7]	李吟，方建勇，江梦. 面向需求覆盖的Web服务自动化测试框架[J]. 计算机科学与探索, 2017, 11(11): 1747-1763.
[8]	吕小玲，王鑫，冯志勇，饶国政，张小旺，许光全. MPPIE：基于消息传递的RDFS并行推理框架[J]. 计算机科学与探索, 2016, 10(4): 451-465.
[9]	苏群，杨隆浩，傅仰耿，余瑞银. 基于BK树的扩展置信规则库结构优化框架[J]. 计算机科学与探索, 2016, 10(2): 257-267.
[10]	周作建，林文敏，王斌斌，潘金贵. 基于海量医疗数据的症状自查服务云框架设计[J]. 计算机科学与探索, 2015, 9(9): 1056-1065.
[11]	王虹旭，吴斌，刘旸. 基于Spark的并行图数据分析系统[J]. 计算机科学与探索, 2015, 9(9): 1066-1074.
[12]	陈军. 微波源器件模拟中的并行FDTD建模[J]. 计算机科学与探索, 2015, 9(11): 1295-1300.
[13]	李国红，汪东升，刘振宇，李崇民，刘根贤，郭三川. 核分组的多核处理器优化方法[J]. 计算机科学与探索, 2014, 8(4): 385-396.
[14]	李瑞轩，廖东杰，辜希武，文坤梅，赵铄乂，董新华. YARN平台上的并行主题标引算法[J]. 计算机科学与探索, 2014, 8(12): 1409-1421.
[15]	李玉坤，任标，赵喜燕，刘里，肖迎元. 个人数据管理技术研究[J]. 计算机科学与探索, 2014, 8(11): 1281-1295.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics