ULT TOLERANT SCHEDULING OF INTERVAL ORDERED TASKS WITH COMMUNICATION IN A MULTIPROCESSOR SYSTEM

摘要

This work is intended to present an efficient technique to produce a fault tolerant schedule for a task graph while considering communication costs. It is well known that when communication costs are considered, optimal algorithms exist for special cases like Interval Ordered graphs and Tree structured graphs on two processors. Following this fact, this paper provides an optimal Fault Tolerant schedule for the Interval Graphs and a near optimal Fault Tolerant schedule for the non-Interval Order graphs by converting them into Interval Orders. The importance of this algorithm is that the communication costs are not ignored.