Hash Partitioning Optimizations Based on MapReduce for Chip Multiprocessors

doi:10.7652/xjtuxb201411017

您当前的位置：

首页 >

文章列表页 >

Hash Partitioning Optimizations Based on MapReduce for Chip Multiprocessors

更新时间：2025-07-09

- Hash Partitioning Optimizations Based on MapReduce for Chip Multiprocessors
- Vol. 48, Issue 11, Pages: 97-102(2014)
- 作者机构：
  
  西安电子科技大学计算机学院,西安,710071
- 作者简介：
- 基金信息：
- DOI：10.7652/xjtuxb201411017
  CLC： TP392
- Online First：10 November 2014，
  
  Published：2014
- 稿件说明：
移动端阅览
Hash Partitioning Optimizations Based on MapReduce for Chip Multiprocessors[J]. 2014, 48(11): 97-102.
DOI：

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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Research on the Electrohydrodynamic Effects of Ionic Liquid-Modified Fuels

Study on the Thermodynamic Properties in the Anomalous Region of Supercritical Water

Electrothermal Coupling Research on the Evolutionary Law of Anti-Corona Performance for High-Altitude Air-Cooled Generators

Windage Loss and Flow Characteristics in Impeller Back Gaps of sCO2 Radial Inflow Turbines

Numerical Simulation of the Energy Conversion Process in Thermoacoustic Engines with Different Stack Materials

Related Author

No data

Related Institution

No data

⁰