| 摘要: |
| 在分布式内存多处理机DMM(distributed memory multiprocessor)系统中，不同处理机上运行的任务之间的通信开销仍然很大，有时甚至抵消了多处理机并行所带来的好处.为了使并行程序在DMM系统上能得以高效的执行，必须采用合理的调度技术将任务分配给处理机.文章首先分别给出了任务调度系统中的任务模型、处理机模型以及调度问题的形式化描述，然后在此基础上研究了任务调度中3个最重要的问题，即(1) 如何顺序选择参与调度的任务，(2) 如何选择路由，(3) 如何分配任务给处理机.其中，路由选择 |
| 关键词: 静态任务调度，任务模型，处理机模型，存储转发寻径，虫蚀寻径. |
| DOI： |
| 分类号: |
| 基金项目:本文研究得到国家自然科学基金和国家攀登计划项目基金资助. |
|
| Static Task Scheduling for Incompletely Interconnected Homogeneous Systems |
|
ZHANG Jun,ZHANG Li-sheng,HAN Cheng-de
|
| Abstract: |
| In the distributed memory multiprocessor (DMM) systems, communication overhead, involved among tasks run on different processors, is still large which even offsets the advantages brought by multiprocessor parallelism. In order to execute a parallel application efficiently, it is necessary to choose an appropriate scheduling technology to allocate processors to tasks. In this paper, formal description of general scheduling system including task model, processor model and schedule problem is presented. Three most important problems, 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 to tasks. In addition, the problem on how to choose a route is studied according to store-and-forward and wormhole routing respectively. In the end, a static scheduling algorithm for incompletely interconnected homogeneous systems is constructed according to the solutions to the above three problems. |
| Key words: Static task scheduling, task model, processor model, store－and－forward routing, wormhole routing. |
