Summary: Scheduling of precedence-constrained communicating tasks onto a multiprocessor system depends on many factors. Although many scheduling policies have been presented in the literature, the results vary according to different assumptions, especially for the communication network. Inter-processor communication has become the major performance limitation due to the transmission/synchronization delays and conflicts for shared communication resources.
In this paper we examine the effect of the type of the interconnection network (bus, hypercube) on a nonpreemptive, static, list scheduling algorithm that allocates interrelated computational tasks of a single job to a multiprocessor system. The computational tasks and their interdependence are represented by a directed acyclic task graph, in which the weights on the nodes represent the execution time while the weights on the edges represent the amount of data to be transferred between the tasks. Then, the scheduler is tested with two different types of interconnection networks, estimating their effect to the completion time and to the overall speedup of the multiprocessor system.
For the entire collection see [Zbl 0927.00039].