2D mesh处理机陈列上多处理分配策略研究

摘要

随着网络和并行计算的发展，人们对计算能力的要求越来越高，而并行计算机成为实现高性能计算最有效的技术途径之一。为了提高性能，在空间共享的并行计算机中，一种有效的处理机分配算法至关重要。一个好的处理机分配算法应该在尽可能小的开销下，为到来的任务找到合适的处理机结点进行分配。
　　 在mesh连接的多处理机结构上，已经提出了许多的连续分配和非连续分配算法。连续分配算法要求分配给一个并行任务的结点是连续的并且和多处理机系统中的拓扑结构相同，因此产生的外部碎片较高;在非连续分配中提高邻接性的目的是为了降低处理机碎片，但是由于结点之间消息传递的距离变长了，通信开销也随之增大。本文就2Dmesh结构的多处理机系统中处理机的搜索和分配算法进行了较深入的研究，提出了一种不同于以往的非连续分配算法，该算法是基于系统中当前可用的空闲子网进行分配的。
　　 首先，本文系统阐述了并行计算和互联网络的发展，对并行计算中的任务调度和处理机分配的联系与区别进行了探讨;其次，在系统分析了已有的连续分配和非连续分配算法的基础上，提出了一种相对简单高效的最大空闲子网搜索方法，根据系统中已分配子网的列表，利用空闲子网和已分配子网的空间相减运算，找到当前可利用的最大空闲子网;接下来，在基于空闲列表的非连续分配方法中，提出了一种支持紧凑机制的非连续分配算法CNA，当有若干候选子网或者选中的子网大于任务需要的规模时，实际上分配的是边界值最大的子网，即优先从mesh边界上和已分配子网的周边位置进行分配;最后，论文通过C编程实现了改进算法CNA，仿真实验表明，该算法能有效降低通信开销并提高性能。

目录

声明

学位论文的主要创新点

摘要

第一章 绪论

1．1 问题的提出

1．2 国内外研究概况

1．3 研究目的和意义

1．4 本文的组织结构

1．5 本文的主要创新点

1．6 本章小结

第二章 并行计算及互连网络

2．1 并行计算与互连网络

2．2 多处理机结构

2．3 互连网络

2．3．1 互连网络基本概念

2．3．2 互连网络分类

2．4 直接网络

2．4．1 结点结构

2．4．2 性能参数

2．4．3 流行的直接网络拓扑

2．5 任务调度

2．5．1 并行计算中任务调度分类

2．5．2 多处理机任务和调度

2．6 本章小结

第三章 高效的空闲子网列表更新

3．1 引言

3．2 常用多处理机分配方法

3．2．1 处理机连续分配方法

3．2．2 处理机非连续分配方法

3．3 最大空闲子网搜索

3．3．1 基本概念

3．3．2 空闲子网列表更新方法

3．4 空闲列表更新的扩展

3．5 本章小结

第四章 CNA算法原理及仿真

4．1 引言

4．2 支持紧凑机制

4．2．1 基本概念

4．2．2 结点边界值维护

4．2．3 紧凑机制

4．3 CNA算法

4．3．1 CNA算法的基本原理

4．3．2 CNA算法实例说明

4．3．3 CNA算法形式化描述

4．3．4 CNA算法流程图

4．4 仿真结果

4．4．1 CNA算法实验

4．4．2 结果分析

4．5 本章小结

第五章 总结和展望

5．1 回顾和总结

5．2 未来展望

参考文献

研究生期间发表学术论文及参加科研情况说明

致谢