多核处理器中基于MapReduce的哈希划分优化

袁通; 刘志镜; 刘慧; 王梓

doi:10.7652/xjtuxb201411017

您当前的位置：

首页 >

文章列表页 >

多核处理器中基于MapReduce的哈希划分优化

更新时间：2025-07-09

- 多核处理器中基于MapReduce的哈希划分优化
- Hash Partitioning Optimizations Based on MapReduce for Chip Multiprocessors
- 西安交通大学学报 2014年48卷第11期页码：97-102
- 作者机构：
  
  西安电子科技大学计算机学院,西安,710071
- 作者简介：
- 基金信息：
  
  : 2014-04-09。作者简介: 袁通(1987—),男,博士生;刘志镜(通信作者),男,教授,博士生导师。基金项目: 国家科技支撑计划资助项目(2012BAH01B05);陕西省科技统筹创新工程计划资助项目(2012KTZD-02-05-2
- DOI：10.7652/xjtuxb201411017
  中图分类号： TP392
- 网络首发：2014-11-10，
  
  纸质出版：2014
- 稿件说明：
移动端阅览
袁通, 刘志镜, 刘慧, 等. 多核处理器中基于MapReduce的哈希划分优化[J]. 西安交通大学学报, 2014,48(11):97-102.

Hash Partitioning Optimizations Based on MapReduce for Chip Multiprocessors[J]. 2014, 48(11): 97-102.
袁通, 刘志镜, 刘慧, 等. 多核处理器中基于MapReduce的哈希划分优化[J]. 西安交通大学学报, 2014,48(11):97-102. DOI： 10.7652/xjtuxb201411017.

Hash Partitioning Optimizations Based on MapReduce for Chip Multiprocessors[J]. 2014, 48(11): 97-102. DOI： 10.7652/xjtuxb201411017.

摘要

针对传统的并行哈希划分算法不能高效地利用多核处理器的并行资源

且不能较好处理有倾斜的输入数据的问题

提出了一种在多核处理器中基于MapReduce的哈希划分算法

并且提出了存储结构优化、多步划分优化、数据倾斜优化3种优化策略。该算法将输入数据分成若干块后提交给各个线程并行处理

并选择合适的策略避免写冲突

使其能够高效地利用多核处理器的并行资源。文中提出的哈希表能够提高cache效率

从而提升算法的整体性能。引入MapReduce模型可使多步哈希划分在Map过程和Reduce过程中分别进行; 数据倾斜优化策略能使算法适应有倾斜的输入数据

且具有较好的效果。实验结果表明:在多核处理器中

文中提出的算法能够适应各种分布的输入数据

并且使哈希划分的整体性能得到提升。

Abstract

A hash partitioning method based on MapReduce framework and three efficient optimizations including storage structure optimization

multi-pass partitioning optimization and skew data optimization on chip multiprocessor(CMP)are proposed to address the problems that conventional hash partitioning method cannot take full advantage of CMP's parallel execution resources and properly process the skew input data. The input data are split into several units which are later processed by all threads simultaneously

and suitable strategy is adopted to avoid writing collision hence CMP's parallel execution resources could be fully unitized. The new hash table proposed in this paper can improve the overall performance by increasing the cache efficiency. The introduction of MapReduce framework makes it possible to multiply partition the data in Map phase and Reduce phase

respectively. In addition

the skew data optimization can make the proposed method suitable for processing various skew input data. Experiments have testified these advantages displayed by the proposed hash partitioning method.

关键词

Keywords

references

邓亚丹, 景宁, 熊伟. 基于共享Cache多核处理器的Hash连接优化[J]. 软件学报, 2010, 21(6): 1220-1232.

DENG Yadan, JING Ning, XIONG Wei. Hash join query optimization based on shared-cache chip multi-processor[J]. Journal of Software, 2010, 21(6): 1220-1232.

YE Y, ROSS K, VESDAPUNT N. Scalable aggregation on multicore processors[C]∥Proceedings of the Seventh International Workshop on Data Management on New Hardware. New York, USA: ACM, 2011: 1-9.

BALKESEN C, TEUBNER J, ALONSO G, et al. Main-memory hash join on multi-core CPUs: tuning to the underlying hardware[C]∥Proceedings of the 29th International Conference on Data Engineering. Piscataway, NJ, USA: IEEE, 2013: 362-373.

MANEGOLD S, BONCZ P, KERSTEN M. Optimizing main-memory join on modern hardware[J]. IEEE Transactions on Knowledge and Data Engineering, 2002, 14(4): 709-730.

CIESLEWICZ J, ROSS K. Data partitioning on chip multiprocessors[C]∥Proceedings of the Fourth International Workshop on Data Management on New Hardware. New York, USA: ACM, 2008: 25-34.

WU L, BARKER R, KIM M, et al. Navigating big data with high-throughput, energy-efficient data partitioning[C]∥Proceedings of the 40th Annual International Symposium on Computer Architecture. New York, USA: ACM, 2013: 249-260.

DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters[C]∥Proceedings of the Sixth Symposium on Operating Systems Design and Implementation. Berkeley, USA: USENIX, 2004: 137-150.

TALBOT J, YOO R, KOZYRAKIS C. Phoenix++: modular MapReduce for shared-memory systems[C]∥Proceedings of the Second International Workshop on MapReduce and Its Applications. New York, USA: ACM, 2011: 9-16.

FANG Wenbin, HE Bingsheng, LUO Qiong, et al. Mars: accelerating MapReduce with graphics processors[J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 22(4): 608-620.

CIESLEWICZ J, ROSS K, GIANNAKAKIS I. Parallel buffers for chip multiprocessors[C]∥Proceedings of the Third International Workshop on Data Management on New Hardware. New York, USA: ACM, 2007: 1-10.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

三塔合一间接空冷系统结构参数对夏季运行特性的影响研究

结构-语义-残差协同的图像压缩框架：面向隐私保护与高保真重建

超临界水异常区域热力学特性研究

电子级超纯氮深冷空分流程节能优化研究

扇贝仿生密封腔室内超临界二氧化碳泄漏流湍动能耗散机理研究