STATIC TASK SCHEDULING FOR CLUSTERS INTERCONNECTED BY BUS

Compared with massively parallel processing（MPP） systems, a cluster, which consists of several computers interconnected by a bus, is a very cheap parallel computing environment. This paper proposes a novel scheduling algorithm for clusters interconnected by bus. In general, the algorithm has three main features: （1） Shared bus is treated as a resource being allocated to messages just like processors to tasks; （2） Broadcast is considered which can decrease communication times greatly in some cases, and （3） The earliest idle time slot is exploited when determining the start time of a task on a processor and that of a message on the bus. Finally, the schedule results of the Gauss Jordan elimination method and LU decomposition are given and analyzed.