非完全互连同构系统上的静态任务调度

Static Task Scheduling for Incompletely Interconnected Homogeneous Systems

在分布式内存多处理机DMM（distributedmemorymultiprocessor）系统中，不同处理机上运行的任务之间的通信开销仍然很大，有时甚至抵消了多处理机并行所带来的好处．为了使并行程序在DMM系统上能得以高效的执行，必须采用合理的调度技术将任务分配给处理机．文章首先分别给出了任务调度系统中的任务模型、处理机模型以及调度问题的形式化描述，然后在此基础上研究了任务调度中3个最重要的问题，即（l）如何顺序选择参与调度的任务，（2）如何选择路由，（3）如何分配任务给处理机．其中，路由选择是按存储转发寻径与虫蚀寻径两种不同的方式来讨论的．最后，根据上述3个问题的解决策略，构造了一个非完全互连同构系统上的静态任务调度算法．

In the distributed memory multiprocessor (DMM) systems, communication overhead, involvedamong tasks run on different processors, is still large which even offsets the advantages brought by multiproces-sor parallelism; In order to execute a parallel application efficiently, it is necessary to choose an appropriatescheduling technology to allocate processors to tasks. In this paper, formal description of general schedulingsystem including task model, processor model and schedule problem is presented. Three most important prob-lems , concerning schedule in incompletely interconnected homogeneous systems, are studied, which are: (1 )How to choose scheduling tasks in sequence, (2) How to choose a route, (3) How to allocate processors totasks. In addition, the problem on how to choose a route is studied according to store-and-forward and worm-hole routing respectively. In the end, a static scheduling algorithm for incompletely interconnected homogeneoussystems is constructed according to the solutions to the above three problems.