Fault tolerance in scheduling through interval ordered tasks for multiprocessors

Mohana Desiraju; Hesham H. Ali

Fault tolerance in scheduling through interval ordered tasks for multiprocessors

Mohana Desiraju, Hesham H. Ali

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

While precedence constrained scheduling is NP-hard in general, it is known that optimal scheduling algorithms exist for special cases such as for trees, Interval Orders or when number of processors is limited to two. In this paper, we employ these optimal algorithms to address the important issue of fault tolerance for scheduling general graphs. The input precedence graphs are augmented into Interval Orders and then scheduled optimally while incorporating fault tolerance measures. It is proved that for the case where the graph is already an Interval Order, the fault tolerant schedule generated is optimal. For general precedence graphs, the obtained schedules are shown to be near optimal by comparing them with a standard list scheduling algorithm.

Original language	English (US)
Title of host publication	Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems
Editors	T. Gonzalez
Pages	467-472
Number of pages	6
Volume	16
State	Published - 2004
Event	Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems - Cambridge, MA, United States Duration: Nov 9 2004 → Nov 11 2004

Other

Other	Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems
Country/Territory	United States
City	Cambridge, MA
Period	11/9/04 → 11/11/04

Keywords

Augmented Graph
Backup task
Fault Tolerant Scheduling
Predecessor
Primary task
Successor

ASJC Scopus subject areas

Engineering(all)

Cite this

Desiraju, M & Ali, HH 2004, Fault tolerance in scheduling through interval ordered tasks for multiprocessors. in T Gonzalez (ed.), Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems. vol. 16, 439-122, pp. 467-472, Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems, Cambridge, MA, United States, 11/9/04.

@inproceedings{7dea198d6b424a45935e2017e46b62cc,

title = "Fault tolerance in scheduling through interval ordered tasks for multiprocessors",

abstract = "While precedence constrained scheduling is NP-hard in general, it is known that optimal scheduling algorithms exist for special cases such as for trees, Interval Orders or when number of processors is limited to two. In this paper, we employ these optimal algorithms to address the important issue of fault tolerance for scheduling general graphs. The input precedence graphs are augmented into Interval Orders and then scheduled optimally while incorporating fault tolerance measures. It is proved that for the case where the graph is already an Interval Order, the fault tolerant schedule generated is optimal. For general precedence graphs, the obtained schedules are shown to be near optimal by comparing them with a standard list scheduling algorithm.",

keywords = "Augmented Graph, Backup task, Fault Tolerant Scheduling, Predecessor, Primary task, Successor",

author = "Mohana Desiraju and Ali, {Hesham H.}",

year = "2004",

language = "English (US)",

volume = "16",

pages = "467--472",

editor = "T. Gonzalez",

booktitle = "Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems",

note = "Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems ; Conference date: 09-11-2004 Through 11-11-2004",

}

TY - GEN

T1 - Fault tolerance in scheduling through interval ordered tasks for multiprocessors

AU - Desiraju, Mohana

AU - Ali, Hesham H.

PY - 2004

Y1 - 2004

N2 - While precedence constrained scheduling is NP-hard in general, it is known that optimal scheduling algorithms exist for special cases such as for trees, Interval Orders or when number of processors is limited to two. In this paper, we employ these optimal algorithms to address the important issue of fault tolerance for scheduling general graphs. The input precedence graphs are augmented into Interval Orders and then scheduled optimally while incorporating fault tolerance measures. It is proved that for the case where the graph is already an Interval Order, the fault tolerant schedule generated is optimal. For general precedence graphs, the obtained schedules are shown to be near optimal by comparing them with a standard list scheduling algorithm.

AB - While precedence constrained scheduling is NP-hard in general, it is known that optimal scheduling algorithms exist for special cases such as for trees, Interval Orders or when number of processors is limited to two. In this paper, we employ these optimal algorithms to address the important issue of fault tolerance for scheduling general graphs. The input precedence graphs are augmented into Interval Orders and then scheduled optimally while incorporating fault tolerance measures. It is proved that for the case where the graph is already an Interval Order, the fault tolerant schedule generated is optimal. For general precedence graphs, the obtained schedules are shown to be near optimal by comparing them with a standard list scheduling algorithm.

KW - Augmented Graph

KW - Backup task

KW - Fault Tolerant Scheduling

KW - Predecessor

KW - Primary task

KW - Successor

UR - http://www.scopus.com/inward/record.url?scp=11844294892&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=11844294892&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:11844294892

VL - 16

SP - 467

EP - 472

BT - Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems

A2 - Gonzalez, T.

T2 - Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems

Y2 - 9 November 2004 through 11 November 2004

ER -

Fault tolerance in scheduling through interval ordered tasks for multiprocessors

Abstract

Other

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this