Torus网络中处理机分配策略的研究

摘要

网络技术与并行技术的高速发展，使得人们对计算能力的要求随之增加，而并行计算机是实现高性能计算的最有效的技术途径。20世纪80年代末以来，高性能商用微处理器技术取得了迅猛的发展，使高性能大规模并行计算机的实现成为可能。随着并行计算系统的应用和推广，人们不断增长的需求为科研工作者提出了一系列新的挑战课题。
　　 本文就Torus结构的多处理机系统中处理机的搜索与分配算法进行了较为深入的研究，在已有工作的基础上进行了探索和创新，并取得了一定的成果。具体内容体现在如下几个方面：
　　 1、系统阐述了网络技术与并行计算技术的发展，对并行计算中的任务调度和处理机分配的联系与区别进行了探讨。
　　 2、在系统分析已有的子网搜索与分配算法的基础上，以二维Torus结构的多处理机系统为例，提出了一种相对快速、高效的子网搜索分配算法，该算法通过简单的坐标运算和空间运算能够显著地缩小搜索范围，从而快速地找到满足要求的子网。
　　 3、随着系统中处理机数目的增加，处理机出现故障的情况是难以避免的，一旦出现故障结点，原有的搜索算法将受到限制，从而影响系统的性能；针对这种情况，本文对具有故障结点的Torus网络进行研究，给出了搜索由正常结点组成的最大子网的算法，并用实例验证了算法的可行性。
　　 4、在连续分配策略的基础上提出一种非连续分配策略，该策略能够进一步提高处理机的利用率，降低任务的等待时间，提高整个系统的效率。
　　 5、最后，提出需要进一步开展的研究工作。

目录

文摘

英文文摘

声明

第一章绪论

1.1选题背景和意义

1.2国内外研究概况

1.3主要工作介绍

1.4论文的组织结构

第二章预备知识

2.1并行计算与互连网络

2.2并行计算机体系结构

2.3互连网络分类

2.3.1共享介质网络

2.3.2直接网络

2.3.3间接网络

2.3.4混合网络

2.4任务调度

2.4.1任务调度的类型

2.4.2多处理机任务调度

2.5处理机分配

2.5.1常用的处理机分配方案

2.5.2连续的处理机分配方案

2.5.3非连续的处理机分配方案

第三章Torus多处理机中的子网分配算法研究

3.1引言

3.2基本概念

3.3高效的子网搜索算法

3.3.1 Torus网络中子网搜索算法的基本原理

3.3.2子网搜索算法的流程图及算法描述

3.4算法复杂度分析

4.5算法模拟

3.6小结

第四章故障Torus网络中的子网搜索方案设计

4.1引言

4.2相关概念及理论基础

4.2.1 Torus网络的相关概念

4.2.2 Torus网络的相关理论基础

4.3相关概念及理论基础

4.4子网的确定

4.4.1子网规模的确定

4.4.2信息的发送

4.5搜索最大子网的算法描述

4.6算法模拟

4.7小结

第五章Torus网络中非连续处理机分配策略的设计

5.1引言

5.2 Torus网络的相关概念

5.3相关理论基础

5.4非连续分配的基本思想

5.4.1处理机的区分

5.4.2处理机的分配

5.5非连续分配的算法描述

5.6算法模拟

5.7小结

第六章总结与展望

6.1工作总结

6.2未来的工作展望

参考文献

致谢

攻读硕士学位期间发表论文和参加科研情况