论文部分内容阅读
网络计算技术与并行计算技术的高速发展，导致了网络并行计算系统的产生，并以其范围之广泛、性能之高超、造价之低廉等卓越特性迅速发展壮大起来。目前最为典型的实例有基于局域网的集群（Cluster）和基于广域网的网格（Grid），它们把分布在不同地理位置的计算资源包括CPU、存储器、数据库等，通过高速网络组成充分共享的资源集成，从而提供一种高性能计算、管理及服务的资源能力。网络并行计算（Network parallel computing，本文简称NPC）已成为并行计算领域的一个重要发展方向，随着NPC系统的应用和推广，人们不断增长的需求和异构环境的复杂性，为科研工作者提出了一系列新的挑战课题。 本文就NPC系统的任务调度策略与调度算法进行了较为深入的研究。首先介绍了NPC系统中的基于多处理机任务的调度模型，并在已有工作的基础上进行了探索和创新，并取得了一定的成果。具体内容体现在如下几个方面： （1）在全局调度上把NPC系统当成一个异构的多处理机系统来考虑。根据处理机本身的处理能力、处理机之间的通信能力及任务对处理机的不同需求，定义具有多模式的多处理机任务，从而建立NPC系统中的多处理机任务调度模型Pm|set|Cmax。并从理论上探讨了该调度模型的近似优化问题的难度，在强NP-难的基础上证明了不存在一个多项式时间的常数近似比的调度算法。同时，通过对多处理机任务之间的并行关系的分析，得到了一般最优调度的下界。 （2）研究了3-处理机系统中的规则调度（Normal schedule），通过比较6个规则任务之间的时间长度关系，构造了一个最简单的调度算法，使得其调度时间跨度不超过最优调度的5/4倍，并通过一个实例说明该算法得到的是最优规则调度。然后在规则调度的基础上进行改进，利用拆分（Partition）和半规则调度（Semi-normal schedule）方法，将3-处理机系统中由Goemans’保持了数年之久的世界最好结果7/6改进到了9/8。 （3）研究了4一处理机系统中的规则调度。在组调度（GrouP及人召d公le）的基础上，改善各处理机的间隙搭配方式，并引入部分调度（尸‘尹tial:ched公le）以便充分利用间隙，构造了一系列线性算法。先后得到了近似比为2、5/3、3/2直至4/3的近似调度，而且4/3是规则调度中最优的，这些结果都经过了严格的证明。 （4）研究了多处理机（妻5）的刀尸C系统中的基于多处理机任务的调度问题。首次改进表调度算法并给出了简单可行的处理机指派方法和3种O（矛）时间的调度算法:最大长度优先调度忆五尸)方法、最大宽度优先调度（L环华，）方法和最大面积优先调度（LAF）方法，并通过实验模拟，验证了它们的算法效率和近似调度性能，分析了这些算法的优势和不足。