摘要
本文讨论了多机相关任务的调度问题，从时间和空间两方面考虑，提出了一种新的多机相关任务的调度算法──多机相关任务的相关矩阵调度算法（RMSA）．利用可变的相关矩阵Mu，表示任务的空间需求与处理机的局部存储空间的关系以及任务分配的状态．实验表明此算法具有较短的调度长度，并且具有较好的时间均衡性和空间协调性．
This paper discusses the scheduling problem of dependent tasks in mul-tiprocessors and presents a haw scheduling algorithm- the relation matrixscheduling algorithm (RMSA) of dependent tasks in multiprocessors consideringtime and space. In this paper, a cost function is constructed according to the featureof dependent task in multiprocessors and scheduling strategy is drawn up based onthe cost function. The cost function ensure the minimum of scheduling length, andthe balance of tasks assignment in condition of the minimum of scheduling length.In order to scheduling dependent tasks, this paper constructs variable relation ma-trix M0,M1, Mm Variable relation matrix indicates the relationship of space re-quirement of tasks and local memory of processors, and the state of aSSigned tasks.The initial variable relation matrix M, indicates the relationship of space require-ment of tasks and local memory of processors. relation matrix M0,M1, , Mm-1 arechanged after a task is assigned. All tasks are assigned when Mm=0. Finally, ascheduling example is given. The experimental result shows that scheduling deppen-dbnt tasks in multiprocessors using RMSA can achieve the minimum of scheduling.length, balance in time and coordination in space.
出处
《计算机学报》
EI
CSCD
北大核心
1998年第10期933-938,共6页
Chinese Journal of Computers
关键词
多处理机系统
调度算法
任务分配
Multiprocessor system, scheduling algorithm, task allocation
