摘  要

随着异构多核并行编程的难度不断增大，人们迫切希望并行编程模型可以处理并能生成超大规模(TB级)数据集，以减少并行编程难度，提高异构多核系统开发速度。

MapReduce是近些年新兴的并行编程模型，该模型主要用于实现并行计算中子任务划分、资源的调度、计算结构归约等，其为异构并行系统的大规模数据处理提供一个简单、有效的解决方案。然而传统的MapReduce调度算法存在任务响应时间过长，系统吞吐量大幅度下降的情况，从而影响整个系统的效率的提高。本文在对MapReduce并行编程模型深入研究的基础上，提出了一种适应于Hadoop平台的异构多核的MapReduce调度改进算法。主要工作如下：

(1) 针对MapReduce模型的调度问题，研究了影响MapReduce调度性能的三个主要因素：本地化、同步开销及公平性约束，并对处理这三个因素的调度方法进行分析。对MapReduce模型中同步开销问题的两种解决方法：异步处理和推测执行进行了探究。对于公平性约束，讨论了Hadoop的本地提升和延迟调度，以及Dryad的Quincy调度器。

(2) 结合异构多核环境的特性，针对基于典型MapReduce调度算法——LATE算法的不足，提出了一种MapReduce异构多核调度的改进算法，该算法通过在系统上添加使系统获得自动学习的能力——机器学习中的监管学习，随机提取部分工作任务作为测试任务，以获得处理节点的处理信息，进而得到任务处理的各个阶段的实际时间比，并调整程序的运行方式，从而启动备份任务，以提高任务响应时间。

    为了验证本文算法的有效性，本文在Hadoop平台基础上，对本文算法进行了实验，实验结果表明本文算法在任务响应时间上，优于LATE算法和Hadoop平台原有调度算法，有利于整个系统处理效率的提高，对异构多核并行计算具有一定的推动意义。

关键词：异构多核系统；并行编程模型；MapReduce；推测执行；调度算法

论文报告