Journal of Frontiers of Computer Science and Technology ›› 2011, Vol. 5 ›› Issue (12): 1057-1075.

• 综述·探索 • Previous Articles     Next Articles

Optimization Strategies of Data Processing Algorithms under Multi-Core Architecture

CHEN Wei, DU Lingxia, CHEN Hong   

  1. 1. Key Laboratory of Data Engineering and Knowledge Engineering, Ministry of Education, Renmin University of China, Beijing 100872, China 2. School of Information, Renmin University of China, Beijing 100872, China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-12-01 Published:2011-12-01

多核架构下的数据处理算法优化策略综述

陈 伟, 杜凌霞, 陈 红   

  1. 1. 中国人民大学 数据工程与知识工程教育部重点实验室, 北京 100872
    2. 中国人民大学 信息学院, 北京 100872

Abstract: Multi-core processors, especially the single chip multi-processors (CMP), can provide strong parallel resources of sharing memory. However, the majority of programs and algorithms from single-core processors can not make full use of computing resources of multi-core architecture. Therefore, according to some characteristics of multi-core architecture, researchers should optimize those algorithms and substantially increase the performance of algorithms. This paper reviews related optimization strategies of data processing algorithms on multi-core processors around several aspects, including improving the locality of programs, decreasing cache access conflict, enhancing the thread parallelism, taking advantage of single instruction multiple data (SIMD) parallelism and optimizing bandwidth usage. In addtion, it summarizes and comments on the algorithms on multi-core processors. Finally, it introduces several interesting issues that people should address and predicts the prospect of the research on multi-core processors in future.

Key words: multi-core, chip multi-processor (CMP), data level parallelism (DLP), thread level parallelism (TLP), single instruction multiple data (SIMD)

摘要:

多核处理器, 尤其是单芯片多处理器(chip multi-processor, CMP)能够提供强大的共享内存的并行资源, 然而单核处理器上的程序和算法并不能充分利用多核架构提供的并行计算资源, 因此必须针对多核体系架构特点, 对算法进行改进优化, 提高算法的执行性能。以优化程序局部性、减少cache访问冲突、提高线程并行度、充分利用单指令多数据流(single instruction multiple data, SIMD)并行和带宽优化等几方面为出发点, 归纳和分析了多核处理器上数据处理算法的相关优化策略, 并对多核算法进行了总结评述。最后阐述了该领域亟待解决的诸多问题, 展望了未来的研究发展方向。

关键词: 多核, 单芯片多处理器(CMP), 数据级别并行(DLP), 线程级别并行( TLP), 单指令多数据流(SIMD)