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

发布时间：2018-11-05 20:34

【摘要】：针对传统的并行哈希划分算法不能高效地利用多核处理器的并行资源,且不能较好处理有倾斜的输入数据的问题,提出了一种在多核处理器中基于MapReduce的哈希划分算法,并且提出了存储结构优化、多步划分优化、数据倾斜优化3种优化策略。该算法将输入数据分成若干块后提交给各个线程并行处理,并选择合适的策略避免写冲突,使其能够高效地利用多核处理器的并行资源。文中提出的哈希表能够提高cache效率,从而提升算法的整体性能。引入MapReduce模型可使多步哈希划分在Map过程和Reduce过程中分别进行;数据倾斜优化策略能使算法适应有倾斜的输入数据,且具有较好的效果。实验结果表明:在多核处理器中,文中提出的算法能够适应各种分布的输入数据,并且使哈希划分的整体性能得到提升。
[Abstract]:Aiming at the problem that the traditional parallel hash partition algorithm can not efficiently utilize the parallel resources of the multi-core processor and can not handle the skewed input data, a hash partition algorithm based on MapReduce in the multi-core processor is proposed. Three optimization strategies, storage structure optimization, multi-step partition optimization and data skew optimization, are proposed. The algorithm divides the input data into several blocks and submits them to each thread for parallel processing, and selects appropriate strategies to avoid write conflicts, so that it can efficiently utilize the parallel resources of multi-core processors. The hash table proposed in this paper can improve the efficiency of cache and improve the overall performance of the algorithm. By introducing MapReduce model, the multi-step hash partition can be carried out in the Map process and the Reduce process, and the data skew optimization strategy can adapt the algorithm to the skewed input data, and it has a good effect. Experimental results show that the proposed algorithm can adapt to all kinds of distributed input data and improve the overall performance of hash partitioning in multi-core processors.
【作者单位】：西安电子科技大学计算机学院;
【基金】：国家科技支撑计划资助项目(2012BAH01B05) 陕西省科技统筹创新工程计划资助项目(2012KTZD-02-05-2)
【分类号】：TP332

【参考文献】