Search

This paper proposes the Makespan and Reliability Cost Driven (MRCD) heuristic, a static scheduling strategy for heterogeneous distributed systems that not only minimizes the makespan, but also maximizes the reliability of the application. The MRCD scheduling decisions are guided by a weighted function that considers both objectives simultaneously, instead of prioritizing one of them. This work also introduces a classification of the solutions produced by weighted bi-objective schedulers to aid users to tune the weighting function such that an appropriate solution can be selected in accordance with their needs. In comparison with the related work, MRCD produced schedules with makespans that were significantly better then those produced by the other strategies at expense of an insignificant deterioration in reliability.

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.