面向异构多核系统的并行计算模型和调度算法研究

发布时间：2018-01-13 21:38

本文关键词：面向异构多核系统的并行计算模型和调度算法研究　出处：《湖南大学》2012年硕士论文　论文类型：学位论文

【摘要】：随着异构多核并行编程的难度不断增大，人们迫切希望并行编程模型可以处理并能生成超大规模(TB级)数据集，以减少并行编程难度，提高异构多核系统开发速度。 MapReduce是近些年新兴的并行编程模型，该模型主要用于实现并行计算中子任务划分、资源的调度、计算结构归约等，其为异构并行系统的大规模数据处理提供一个简单、有效的解决方案。然而传统的MapReduce调度算法存在任务响应时间过长，系统吞吐量大幅度下降的情况，从而影响整个系统的效率的提高。本文在对MapReduce并行编程模型深入研究的基础上，提出了一种适应于Hadoop平台的异构多核的MapReduce调度改进算法。主要工作如下： (1)针对MapReduce模型的调度问题，研究了影响MapReduce调度性能的三个主要因素：本地化、同步开销及公平性约束，并对处理这三个因素的调度方法进行分析。对MapReduce模型中同步开销问题的两种解决方法：异步处理和推测执行进行了探究。对于公平性约束，讨论了Hadoop的本地提升和延迟调度，以及Dryad的Quincy调度器。 (2)结合异构多核环境的特性，针对基于典型MapReduce调度算法——LATE算法的不足，提出了一种MapReduce异构多核调度的改进算法，该算法通过在系统上添加使系统获得自动学习的能力——机器学习中的监管学习，随机提取部分工作任务作为测试任务，以获得处理节点的处理信息，进而得到任务处理的各个阶段的实际时间比，并调整程序的运行方式，从而启动备份任务，以提高任务响应时间。为了验证本文算法的有效性，本文在Hadoop平台基础上，对本文算法进行了实验，实验结果表明本文算法在任务响应时间上，，优于LATE算法和Hadoop平台原有调度算法，有利于整个系统处理效率的提高，对异构多核并行计算具有一定的推动意义。
[Abstract]:With the increasing difficulty of heterogeneous multi-core parallel programming, people urgently hope that the parallel programming model can process and generate large scale / terabyte (TB) data sets, so as to reduce the difficulty of parallel programming. Improve the development speed of heterogeneous multi-core system. MapReduce is a new parallel programming model in recent years. This model is mainly used to realize the parallel computing neutron task partition, resource scheduling, computing structure reduction and so on. It provides a simple and effective solution for large-scale data processing in heterogeneous parallel systems. However, the task response time of traditional MapReduce scheduling algorithm is too long. The throughput of the system is greatly reduced, which affects the efficiency of the whole system. This paper deeply studies the parallel programming model of MapReduce. In this paper, an improved MapReduce scheduling algorithm based on heterogeneous multicore for Hadoop platform is proposed. The main work is as follows: 1) aiming at the scheduling problem of MapReduce model, three main factors affecting the scheduling performance of MapReduce are studied: localization, synchronization overhead and fairness constraints. This paper also analyzes the scheduling methods to deal with these three factors, and explores two solutions to the synchronous overhead problem in the MapReduce model: asynchronous processing and speculative execution. The local promotion and delay scheduling of Hadoop and the Quincy scheduler of Dryad are discussed. 2) considering the characteristics of heterogeneous multi-core environment, aiming at the shortcomings of the typical MapReduce scheduling algorithm, path algorithm. In this paper, an improved algorithm for heterogeneous multi-core scheduling of MapReduce is proposed. The algorithm adds the ability of automatic learning to the system, which is the supervised learning in machine learning. A part of the task is randomly extracted as a test task to obtain the processing information of the processing node, and then the actual time ratio of each stage of the task processing is obtained, and the operation mode of the program is adjusted to start the backup task. To increase task response time. In order to verify the effectiveness of this algorithm, this paper based on the Hadoop platform, the experimental results show that the algorithm in the task response time. It is superior to the LATE algorithm and the original scheduling algorithm of Hadoop platform, which is beneficial to the improvement of the processing efficiency of the whole system, and has a certain significance to promote the heterogeneous multi-core parallel computing.
【学位授予单位】：湖南大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP338.6

【参考文献】