并行处理系统中任务调度算法及模型的研究

摘要

论文首先阐述了并行处理系统及并行处理系统中的任务调度问题,之后对其中有代表性的网络流量算法和启发式调度算法进行了比较深入的研究,阐述算法原理,进行综合分析,并对一类启发式群聚算法进行了改进,在开发完成的一个任务调度算法仿真系统上进行了实现.论文还对基于Stone典型模型基础之上的一些算法模型,尤其是近年来的最具一般性,最有效的解决了处理机数目上限制问题的几个算法及模型进行了比较,分析和讨论.在此基础上,提出了一个新的算法及模型.该算法弥补了以前算法的一些不足,将改进的启发式算法,网络流量算法和贪心算法有机的结合在一起,很好地解决了处理机数目上的限制问题.

目录

文摘

英文文摘

第一章序言

1.1课题背景介绍

1.2论文主要内容

1.3本人的主要工作

第二章并行处理系统

2.1并行处理的发展及趋势

2.2并行体系结构

2.2.1向量处理计算机

2.2.2共享主存处理机系统

2.2.3分布主存大规模并行机

2.2.4群机并行系统

2.3并行程序设计基础

2.3.1并行模式

2.3.2程序并行执行的基本概念

2.3.3并行程序性能描述

2.4并行计算模型

2.4.1 PRAM模型

2.4.2 BSP模型

2.4.3 LogP模型

2.4.4 C3模型

2.5小结

第三章并行处理系统中的任务调度

3.1引言

3.2任务调度的分类

3.2.1一般的任务调度分类

3.2.2任务调度的一个典型分类

3.3任务调度的基本模型

3.3.1任务图

3.3.2目标机器

3.3.3调度

3.4任务调度算法

3.4.1传统的任务调度算法

3.4.2比较新的任务调度算法

3.5小结

第四章网络流量调度算法和启发式任务调度算法

4.1网络流量调度算法

4.1.1背景知识

4.1.2 Ford-Fulkerson算法

4.1.3 Edmonds-Karp算法

4.1.4 Dinic算法

4.1.5 Karzanov算法

4.1.6 Push-Relabel算法

4.1.7算法比较分析

4.2启发式任务调度算法

4.2.1基于队列结构的启发式任务调度算法

4.2.2基于任务群聚的启发式任务调度算法

4.2.3任意目标机器上的启发式任务调度算法

4.3算法仿真

4.4小结

第五章调度算法模型和应用

5.1 Stone的典型模型

5.1.1 2个处理机的情况

5.1.2 n个处理机的情况

5.2 VIRGINIA MARY-LO的改进算法及模型

5.3 VIRGINIA MARY-LO对Stone模型的改进

5.4同构系统的图形理论模型

5.4.1模型基础及思想

5.4.2 n维阵列的情况

5.4.3 n个处理机的树的情况

5.5异构系统的启发式算法模型

5.5.1算法模型的基础思想

5.5.2启发式匹配算法

5.5.3启发式最大边算法

5.6算法比较分析

5.7算法仿真与说明

5.8小结

第六章一个改进的调度算法模型

6.1MARY-LO的算法模型的不足

6.2算法模型的改进思想

6.3一个改进的启发式群聚算法

6.3.1算法的改进

6.3.2算法的仿真和说明

6.4新的任务调度算法的组成

6.4.1改进的启发式群聚算法

6.4.2MARY-LO启发式算法

6.5新的算法及模型的详细描述

6.5.1第一阶段

6.5.2第二阶段

6.5.3第三阶段

6.5.4第四阶段

6.6算法分析

6.7小结

结束语

致谢

参考文献