A versatile cost modelling approach for multicomputer task scheduling
In general, scheduling models only consider the message delay or latency as the dominant communication parameter. However, in many of the current generation of parallel systems, latency is negligible compared to the CPU penalties for the communication-related activities that are incurred whenever pairs of dependent tasks on distinct processors need to communicate. This work considers a model where the CPU penalty, which is associated with sending and receiving, communication events, is an additional (potentially dominant) communication parameter. A multi-stage scheduling approach (MSA) is proposed which takes both of these types communication parameters into account. This scheduling approach can be customised to classes of parallel systems according to their communication performance characteristics by varying the order in which the rules (which guide the strategy) are applied.
task scheduling latency communication overheads multi-stage scheduling heuristic clustering task replication