Multiprocessor Scheduling with Communication Delays

摘要

It is important, when programming a parallel computer, to assign the tasks toprocessors while respecting the information dependencies inbetween the tasks. The purpose of the work is to investigate the allocation of program modules or tasks to parallel processors in the context of deterministic machine scheduling theory. An extension of an already applied scheduling model is proposed. A model allowing for communication delays is discussed. The tradeoff between the optimal makespan of schedules with and without duplicated tasks is investigated. The computational complexity of scheduling multiprocessor tasks with prespecified processor allocations is studied. The hybrid invariant, in which some tasks are to be allocated to either of two processors and others have a prespecified allocation to a single processor, is considered. A detailed description of Tosca's method and its implementation are given.