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

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

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