| 【中文题名】 | 基于动态通信竞争的任意处理机网络表调度算法 |
| 【英文题名】 | Based on Dynamic Communication Contention List Scheduling Algorithm for Arbitrary Network System |
| 【学科专业】 | 计算机系统结构 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-9-27 |
| 【中关键词】 | 表调度,任意处理机网络,DAG,通信竞争,并行算法, |
| 【英关键词】 | list scheduling,arbitrary processors networks,DAG,communication contention,parallel algorithm, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>计算技术、计算机技术>计算机的应用>计算机网络>一般性问题 |
| 【论文摘要】 |
计算技术和网络技术的飞速发展,极大地促进了基于网络环境的科学应用研究。许多应用领域对计算能力的要求越来越高,单台计算机已很难满足计算需求。由多处理机构建的高性能计算系统已成为计算技术发展的必然,然而在这种系统环境下调度任意结构并行任务并获取最优解的问题仍然是NP完全难题。表调度算法是解决此类问题的一种经典启发式任务调度算法,具有调度性能较好,时间复杂度较低等优点。但经典表调度算法假定目标处理机全互连,以及调度节点时忽略节点之间的通信,显然不符合任意处理机网络计算环境的需求。因为对于任意处理机网络拓朴结构的异构系统,各任务之间的通信竞争不可忽略,这种任务通信对整个并行应用程序的执行有重要影响。因而,考虑通信竞争的调度算法是提高并行分布式计算系统实际性能的重要途径之一。
本文研究工作主要方法是在调度算法中考虑通信竞争,即调度任务时同时考虑节点和通信边的调度。为了实现调度目标,提出一个基于最短路径搜索算法的最早通信完成路径查找算法(EFCS),采用插入式链路实现策略,以达到通信边的动态调度;对于任意处理机网络环境下的任务优先级计算问题,受HEFT算法启发提出递归优先权计算公式,并且按非升序排列获得... |
| 【论文题纲】 |
|
摘要 |
7-8 |
|
ABSTRACT |
8-9 |
|
插图索引 |
9-10 |
|
附表索引 |
10-11 |
|
第1章 绪论 |
11-16 |
|
1.1 调度问题研究的背景和意义 |
11-12 |
|
1.2 调度问题 |
12-14 |
|
1.3 本文的主要工作 |
14 |
|
1.4 本文的组织结构 |
14-16 |
|
第2章 基于优先级的启发式表调度算法 |
16-28 |
|
2.1 DAG 调度模型 |
16-18 |
|
2.2 基于DAG 模型的启发式表调度算法相关专业术语 |
18-20 |
|
2.3 启发式表调度算法 |
20-27 |
|
2.4 小结 |
27-28 |
|
第3章 基于动态通信竞争的任意处理机网络表调度算法 |
28-36 |
|
3.1 考虑通信竞争表调度算法概述 |
28 |
|
3.2 任意处理机网络异构系统优先权计算问题 |
28-29 |
|
3.3 基于动态通信竞争的表调度算法 |
29-33 |
|
3.4 基于动态通信竞争的表调度算法实例 |
33-35 |
|
3.5 小结 |
35-36 |
|
第4章 模拟实验结果分析 |
36-43 |
|
4.1 随机应用程序任务图 |
36 |
|
4.2 任意处理机网络分布式计算系统 |
36-37 |
|
4.3 随机应用程序实验结果及性能分析 |
37-40 |
|
4.4 实际应用问题实验结果性能分析与比较 |
40-42 |
|
4.5 小结 |
42-43 |
|
第5章 基于动态通信竞争的并行表调度算法 |
43-51 |
|
5.1 并行表调度算法概述 |
43 |
|
5.2 OPENMP 简介 |
43-49 |
|
5.3 基于动态通信竞争的并行表调度算法 |
49-50 |
|
5.4 小结 |
50-51 |
|
结论 |
51-53 |
|
参考文献 |
53-57 |
|
致谢 |
57-58 |
|
附录 A（攻读硕士期间发表论文列表） |
58-59 |
|
附录 B（攻读硕士期间参与的项目列表） |
59 |
|
| 【DOI】 | LunWen.ID:2.2008.376138 |
