总线互连机群系统上的静态任务调度

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.