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

(西安电子科技大学计算机学院, 710071, 西安)

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

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

(西安电子科技大学计算机学院, 710071, 西安)

针对传统的并行哈希划分算法不能高效地利用多核处理器的并行资源,且不能较好处理有倾斜的输入数据的问题,提出了一种在多核处理器中基于MapReduce的哈希划分算法,并且提出了存储结构优化、多步划分优化、数据倾斜优化3种优化策略。该算法将输入数据分成若干块后提交给各个线程并行处理,并选择合适的策略避免写冲突,使其能够高效地利用多核处理器的并行资源。文中提出的哈希表能够提高cache效率,从而提升算法的整体性能。引入MapReduce模型可使多步哈希划分在Map过程和Reduce过程中分别进行;数据倾斜优化策略能使算法适应有倾斜的输入数据,且具有较好的效果。实验结果表明:在多核处理器中,文中提出的算法能够适应各种分布的输入数据,并且使哈希划分的整体性能得到提升。

数据划分;哈希处理;多核处理器;MapReduce模型

划分是数据库中的重要操作,同时也是其他数据库操作(如连接、聚集、排序等)的基本操作。划分是将一个较大的任务分成若干个较小的子任务,而处理若干个子任务所用的时间常常少于处理一个较大任务所用的时间,这是因为较小的任务能够高效地利用cache和内存。哈希划分是使用范围最广的划分算法。

当今的硬件发展十分迅速,CPU拥有更多的核心,每个核心拥有更多的线程。……