A checkpointing scheme for relevant distributed real-time tasks which can be scheduled as a DAG is proposed. A typical algorithm, OSA, is selected for DAG scheduling. A new methods based a new structure, Scheduled Clu...A checkpointing scheme for relevant distributed real-time tasks which can be scheduled as a DAG is proposed. A typical algorithm, OSA, is selected for DAG scheduling. A new methods based a new structure, Scheduled Cluster Tree, is presented to calculate the slack time of each task in the task cluster. In the checkpointing scheme, the optimal checkpoint intervals which minimize the approximated failure probability are derived formally and validated experimentally. The complexity of approximated failure probability is quite small compared with that of the exact probability. Meanwhile, the consistency of the checkpointing is discussed also.展开更多
Optimized task scheduling is one of the most important challenges to achieve high performance in multiprocessor environments such as parallel and distributed systems. Most introduced task-scheduling algorithms are bas...Optimized task scheduling is one of the most important challenges to achieve high performance in multiprocessor environments such as parallel and distributed systems. Most introduced task-scheduling algorithms are based on the so-called list scheduling technique. The basic idea behind list scheduling is to prepare a sequence of nodes in the form of a list for scheduling by assigning them some priority measurements, and then repeatedly removing the node with the highest priority from the list and allocating it to the processor providing the earliest start time （EST）. Therefore, it can be inferred that the makespans obtained are dominated by two major factors： （1） which order of tasks should be selected （sequence subproblem）; （2） how the selected order should be assigned to the processors （assignment subproblem）. A number of good approaches for overcoming the task sequence dilemma have been proposed in the literature, while the task assignment problem has not been studied much. The results of this study prove that assigning tasks to the processors using the traditional EST method is not optimum; in addition, a novel approach based on the ant colony optimization algorithm is introduced, which can find far better solutions.展开更多
文摘A checkpointing scheme for relevant distributed real-time tasks which can be scheduled as a DAG is proposed. A typical algorithm, OSA, is selected for DAG scheduling. A new methods based a new structure, Scheduled Cluster Tree, is presented to calculate the slack time of each task in the task cluster. In the checkpointing scheme, the optimal checkpoint intervals which minimize the approximated failure probability are derived formally and validated experimentally. The complexity of approximated failure probability is quite small compared with that of the exact probability. Meanwhile, the consistency of the checkpointing is discussed also.
基金Project supported by Sama Technical and Vocational Training College,Islamic Azad University,Shoushtar Branch,Shoushtar,Iran
文摘Optimized task scheduling is one of the most important challenges to achieve high performance in multiprocessor environments such as parallel and distributed systems. Most introduced task-scheduling algorithms are based on the so-called list scheduling technique. The basic idea behind list scheduling is to prepare a sequence of nodes in the form of a list for scheduling by assigning them some priority measurements, and then repeatedly removing the node with the highest priority from the list and allocating it to the processor providing the earliest start time （EST）. Therefore, it can be inferred that the makespans obtained are dominated by two major factors： （1） which order of tasks should be selected （sequence subproblem）; （2） how the selected order should be assigned to the processors （assignment subproblem）. A number of good approaches for overcoming the task sequence dilemma have been proposed in the literature, while the task assignment problem has not been studied much. The results of this study prove that assigning tasks to the processors using the traditional EST method is not optimum; in addition, a novel approach based on the ant colony optimization algorithm is introduced, which can find far better solutions.
