分布式任务调度与并行算法设计
文献类型：学位论文
| 作者 | 康一梅 |
| 学位类别 | 工学博士 |
| 答辩日期 | 1994-06-01 |
| 授予单位 | 中国科学院自动化研究所 |
| 授予地点 | 中国科学院自动化研究所 |
| 导师 | 郑应平 |
| 学位专业 | 控制理论与控制工程 |
| 中文摘要 | 近年来，由于微处理器技术和网络技术突飞猛进的发展，计算机体系结构在设计 上产生了明显的倾向性变化，分布式计算机系统成为计算机界中引人注目的研究课 题。任务调度是提高分布处理系统效率的—个关键技术。 分布式计算系统的任务调度是确定性调度问题中的一个重要专题，这类问题基 本上都是NP难题，因此很难找到多项式时间最优算法。因此，许多人尝试用不同的 方法寻找次优解。启发式方法是一种用的很多的次优求解方法．启发式算法不一定 能找到最优的任务调度方案，但算法本身的效率很高。所以在分布式系统的任务调度 问题上，启发式算法应用价值很高。本文所提出的任务调度算法都是启发式算法． 全文内容共分六个部分。 第一章是综述，阐述了分布式调度的重要性，介绍了对现有分布式调度算法的分 类与评估方法，以及分布式调度的发展及现有成果，为理解以后各章作一引子。 文中对四种不同的分布式计算系统模型分别提出了其任务调度的启发式算法。 即从第二章到第五章分别探讨了四类调度问题： 第一类调度问题n个独立任务在m个同等处理机上处理，使完成时间最小的非 抢先调度问题。第二章提出一种启发式方法一BF算法，证明了它的最坏情况性能为 1．20OPT，与目前性能最好的MULTIFIT算法一样甚至更好，时间复杂性为O(nlogn +／knlogm)。BF算法是一种迭代算法，我们证明了它的收敛性及最坏情况性能与迭代 次数七无关，并通过大量仿真说明其：迭代次数比算法的迭代次数少，即时间复杂性较 小。 在实际应用中，绝大多数问题并不能分解成足够多的相互独立的任务，一般情况 下，任务间都有或多或少的优先约束。因此，在第三章中讨论了这类问题。 第二类调度问题：有优先约束的n个任务在m个同等处理机上处理，使完成时间 最小的调度问题。第三章中分别讨论了这类问题不考虑负载平衡与考虑负载平衡的 情况，提出几种算法。算法1分别求出各任务级的调度，然后以这些调度顺序排列所得 的调度为整个问题的解。文中分别证明了对星形优先结构和一般优先结构的情况的 最坏情况性能。算法2使处理机的空闲时间最小，文中证明了它得到最优调度的充分 条件。算法3考虑了负载平衡，最后通过实例比较三种算法的性能。 任务间优先约束都是由数据相依关系决定的，即有优先约束的任务间必有数据 通讯．第三章中假定数据通讯所需的时间可忽略不计，这在许多时侯是可以的．但当 通讯时间的平均值与处理时间的 |
| 英文摘要 | With the development of microprocessor techniques and network techniques, distributed computer systems become an important research field because of their high speed. Task scheduling is very important to raise the efficiency of the distributed computer systems. The task scheduling of distributed computer systems is an important special topic of deterministic sheduling problems. Almost all of these problems are NP--hard, it is very difficult to find a polynomial optimal solution. Hence, many people try to solve such problems through various methods to find suboptimal solutions instead. Heuristic methods are widely used to find subopthnal solutions. In this paper, all methods presented are heuristic. This paper contains six chapters. Chapter 1 is an introduction. The importance of distributed computer systems task scheduling will be shown. The classifications and evaluation methods of scheduling problems will be introduced. The development and existed results will also be introduced. For four different models, several heuristic scheduling methods will be presented from chapter 2 to chapter 5, respectively. The first problem: the nonpremptive problem of assigning n independent tasks to m identical processors in order to minimizing the total finishing time. In chapter 2, a heuristic algorithm BF algorithm is presented. It is shown that the worst case performance of BF algorithm is 1.20OPT. The performance is better than, at least as good as the worst case perfor mace of MULTIFIT methods, which is the method with the best error bound so far. It is also shown that the time complexity of BF is O(nlogn + knlogm). BF method is an iterative algorithm, the convergence is proved, it is also proved that the worst case performance is unrelated to the iteration number k. Through a lot of simulations, the conclusion is obtained that BF algorithm needs fewer iterations than MULTIFIT algorithm, that is the BF algorithm needs less run time. In pratical applications, most problems can not be discomposed into many enough independent tasks. Generally, there exists some precedence constraints among tasks. Such problems will be considered in chapter 3. The second problem: the problem of assigning n tasks with precedence constraints to m identical processors in order to minimizing the total finishing time. In chapter 2, algorithms without and with the consideration of load-balancing ate presented respectively. The worst case performances of algorithm 1 will be proved. Algorithm 2 finds schedules which minimizing the idle times, and a sufficient condition to find optimal shedule will be shown. Algorithm 3 can obtain a solution balancing the loads on each processors. At last, an example is analyzed to compare the performances of the three algorithms. The data dependence determines the precedence relationship among the tasks. In chapter 3, it is assumed that the communication cost |
| 语种 | 中文 |
| 其他标识符 | 295 |
| 源URL | [http://ir.ia.ac.cn/handle/173211/5642]  |
| 专题 | 毕业生_博士学位论文 |
| 推荐引用方式 GB/T 7714 | 康一梅. 分布式任务调度与并行算法设计[D]. 中国科学院自动化研究所. 中国科学院自动化研究所. 1994. |
入库方式： OAI收割
来源：自动化研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。