基于PVM的任务分配及调度策略研究

论文摘要

网络并行计算是一种分布式处理系统，它利用现有高速网络互联的处理机、工作站的软硬件资源，实现以前只有专用且昂贵的大规模并行计算机系统才能完成的高性能计算。与专用的大型机、超级并行计算机相比，网络并行计算具有投资小，灵活性强，应用软件开发速度快和可移植性好的优点。正是由于其简洁、高效以及广泛的适用性和易用性，网络并行计算成为当今并行处理技术研究的热点。任务的分配与调度是网络并行计算中最基本、最关键，也是最具挑战性的问题之一，是影响并行计算执行效率的一个关键因素。任务分配与调度是计算机研究领域的一个经典问题，其许多子问题尚未彻底解决，对它们进行研究具有重要的理论和实际价值。论文详细分析了PVM网络并行计算平台的系统结构和通信机制，对网络并行计算的模型和实现进行了深入的探讨，研究了各种任务分配及调度的相关策略。针对网络并行计算的任务分配与调度存在的问题，通过对PVM网络并行环境的特点及各种任务分配策略进行详细的对比研究，综合考虑任务执行时间，任务间的通信时间以及处理机的计算能力等因素，本文提出了任务预分配与动态调度相结合的任务分配与调度策略。基于PVM网络并行计算平台的并行程序比较适合一些中、大粒度的任务，任务间的通信时间和通信延迟开销都比较大，本文提出的任务分配与调度策略能较好地解决了该问题。根据任务之间的通信关系，在任务的预分配中，对任务模型进行了并行簇的划分，并把处理机按并行簇进行分组。每个处理机组有一个组调度主机，对并行簇进行任务的动态调度，避免了使用单一调度主机产生的瓶颈问题。使用的任务预分配策略比一般的静态任务分配大大减小了任务分配的时间，又避免了完全依靠动态分配策略进行任务调度而带来的抖动现象的发生；每个处理机组采用动态任务调度又能根据系统的信息负载情况进行合理地调度，减小任务分配的开销和任务间的通信开销，从而使并行计算的效率得到提高。通过详细地分析与研究，本文设计了一个基于windows环境下PVM平台的任务分配与调度模型。该任务模型包括系统负载的获取、任务的预分配与动态任务调度。最后总结了本文的研究工作，指出了下一步的研究方向。

论文目录

• 摘要
• Abstract
• 目录
• Contents
• 第一章 绪论
• 1.1 课题的研究意义与研究现状
• 1.1.1 研究意义
• 1.1.2 课题研究的现状
• 1.2 研究内容
• 1.3 论文的组织
• 第二章 PVM并行计算平台的分析
• 2.1 网络并行计算
• 2.2 PVM概述
• 2.2.1 PVM系统的特点
• 2.2.2 WPVM
• 2.3 PVM系统的组成与结构
• 2.3.1 PVM系统的组成
• 2.3.2 PVM系统结构
• 2.4 PVM通信机制
• 2.4.1 PVM的通信方式
• 2.4.2 PVM的通信函数
• 2.5 PVM的并行程序模式
• 第三章 任务分配与调度理论分析
• 3.1 基本概念
• 3.2 任务的划分
• 3.3 基本的任务调度技术
• 3.3.1 基于表的任务调度算法
• 3.3.2 基于任务复制的调度
• 3.3.3 基于任务集群（Cluster）或聚类的调度
• 3.3.4 非确定性调度
• 3.4 任务分配模型
• 3.4.1 任务模型
• 3.4.2 处理机模型
• 3.5 任务分配与调度的性能
• 3.5.1 总体完成时间
• 3.5.2 提高任务执行性能的途径
• 第四章 基于PVM的任务分配与调度
• 4.1 PVM系统的原始任务分配方法
• 4.1.1 轮询法任务分配
• 4.1.2 二次均分法任务分配
• 4.1.3 PVM系统的负载不平衡问题
• 4.2 静态任务分配
• 4.3 动态任务调度
• 4.3.1 集中式的调度策略
• 4.3.2 分布式的调度策略
• 4.4 任务预分配与动态调度结合的调度策略
• 4.4.1 调度方案选择的分析
• 4.4.2 基于PVM系统的任务分配及调度方案
• 4.4.3 任务预分配
• 4.4.4 任务调度
• 4.4.5 任务预分配与动态调度结合的优势
• 4.5 预分配与动态调度列表
• 第五章 任务分配与调度的设计与分析
• 5.1 任务的描述
• 5.1.1 任务描述的数据结构
• 5.1.2 处理机描述的数据结构
• 5.2 系统信息收集模块
• 5.2.1 处理机计算能力
• 5.2.2 负载指标
• 5.2.3 系统信息的获取
• 5.2.4 消息的处理
• 5.3 任务调度模块
• 总结与展望
• 全文总结
• 未来研究的展望
• 参考文献
• 攻读硕士学位期间发表的论文
• 致谢