同构型多机系统多任务的连通性分配

The Connected Assignment of Multiple Tasks on Homogeneous Multiprocessor Systems

本文提出了同构型多机系统多任务并行处理的一种新的调度方式——连通性分配.采用连通性分配后,不需增加硬件和软件,系统的容错能力即可得以提高.文章对系统的可连通分配性给出了一些判定条件,并证明了任意连通分配的判定问题是NP完全的.对某些特殊类型的分配问题,给出了多项式复杂性的分配算法.

A new approach to task scheduling, connected assignment, is proposed for parallel processing of multiple tasks on homogeneous multiprocessor systems. The fault-tolerant capability of a system can be increased via connected assignment without any particular hardware or software. Certain criteria for connected assignability are presented while the decision of arbitary connected assignability is shown to fall into the class of NP-complete problems. Polynomial time algorithms are given for some special types of connected assignment.