异构环境中并行计算模型与任务调度的研究

论文摘要

计算机硬件成本的不断降低、微处理器处理能力的快速提升和网络技术的高速发展,为用普通微机建立并行计算系统提供了条件。通常这类并行计算系统都具有异构性,而且异构并行计算系统已经广泛应用于科学领域和商业领域,对异构计算系统的研究也成为近年来的研究重点。因此研究异构并行环境下的并行计算模型和任务调度有着重要的意义。本文介绍了并行计算的概念和并行计算系统的分类,重点论述了异构并行计算系统,并详细阐述已经提出的并行计算模型。并行计算模型在并行计算系统硬件与软件之间起着桥梁作用,对各种并行计算系统的特征进行抽象,得到并行计算模型。对于一个并行应用问题,在并行计算模型上设计和分析算法,高级语言被有效编译,并通过硬件来实现算法。然而并行计算发展到今天,还没有个一个通用的计算模型,已经提出的并行计算模型或者过于抽象简单或者只适用于专门的环境。通过对现有的模型进行研究,本文提出了非独占异构的异步并行计算模型—NHA-BSP模型。通过理论分析可知,NHA-BSP模型更加准确的描述系统的性能参数,详细刻画系统非独占性,异构性对并行算法执行效率的影响,允许程序异步执行,提高系统的吞吐量,改进并行程序的执行效率。最后通过实验验证了该模型的可用性,并给出了程序优化的方法。异构并行计算系统包含多个异构处理器,处理器之间通过不同的通信链路相连。并行任务调度算法对整个系统的计算效率起着重要作用。因此,优化任务调度策略是本文的另一研究内容。本文详细阐述了异构环境下任务调度的相关内容,包括异构计算的四个步骤以及任务调度的分类,重点研究了静态任务调度中的启发式调度策略。对异构并行计算环境下基于关键路径任务调度算法CPOP算法做出改进,在此基础上提出了一个异构并行环境下基于复制的任务调度算法。通过实例分析和仿真实验证明,在具有相同时间复杂度的前提下,此算法取得比CPOP算法更高的效率,体现算法的优越性。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景和意义
• 1.2 研究现状
• 1.3 本文组织结构
• 第二章 并行计算系统
• 2.1 并行计算
• 2.2 并行计算机的分类
• 2.3 异构并行计算系统
• 2.4 总结
• 第三章 并行计算模型
• 3.1 传统的并行计算模型
• 3.2 基于BSP模型扩展的并行计算模型
• 3.3 并行计算模型的比较
• 3.3.1 传统并行计算模型的比较
• 3.3.2 基于BSP模型的扩展并行计算模型的比较
• 3.4 总结
• 第四章 一种改进的BSP模型
• 4.1 NHA-BSP模型
• 4.2 实例分析
• 4.2.1 MPI基本介绍
• 4.2.2 实验环境介绍
• 4.2.3 实验算法描述
• 4.2.4 实验结果及分析
• 4.3 总结
• 第五章 异构计算环境中的调度算法
• 5.1 任务调度概述
• 5.2 任务调度的分类
• 5.3 静态任务调度
• 5.4 问题描述和算法设计
• 5.4.1 任务模型和异构并行计算系统模型
• 5.4.2 相关术语介绍
• 5.4.3 算法设计及其复杂度分析
• 5.5 实例分析和仿真实验
• 5.5.1 实例分析
• 5.5.2 仿真实验
• 5.6 总结
• 第六章 总结和展望
• 参考文献
• 在校期间发表的学术论文
• 致谢