Paper Info
Title
Failure-Aware Task Scheduling of Synchronous Data Flow Graphs Under Real-Time Constraints
Abstract
As more processors are integrated into Multiprocessor System-on-Chips (MPSoCs) via relentless technology scaling, the mean-time-to-failure (MTTF) is reduced to the extent that unexpected processor failures are considered during design time. A popular approach to tolerate processor failures is to migrate tasks on the faulty processor to live processors. This approach, however, is not suitable for real-time digital signal processing (DSP) applications since it may not guarantee real-time constraints. In this paper, we propose the re-scheduling of the entire application to minimize throughput degradation under a latency constraint, given that the application is specified by a Synchronous Data Flow (SDF) graph. We obtain sub-optimal re-scheduling results using a genetic algorithm for each scenario of processor failures at compile-time. If a failure is detected at run-time, the live processors obtain the saved schedule, perform task transfer, and execute the remaining tasks of the current iteration. We compare preemptive and non-preemptive migration policies and propose a hybrid policy to obtain better performance. We demonstrate the viability of the proposed technique through experiments with real-life DSP applications as well as randomly generated graphs under timing constraints and random fault scenarios.
Year
DOI
Venue
2013
10.1007/s11265-013-0753-3
Signal Processing Systems
Keywords
Field
DocType
Failure-aware scheduling,Task rescheduling,Permanent fault,Genetic algorithm,Task migration
Digital signal processing,Computer science,Scheduling (computing),Latency (engineering),Real-time computing,Genetic algorithm,Distributed computing,Mean time between failures,Graph,Parallel computing,Multiprocessing,Synchronous Data Flow,Embedded system
Journal
Volume
Issue
ISSN
73
2
1939-8018
Citations 
PageRank 
References 
4
0.43
22
Authors
4
Name
Order
Citations
PageRank
Chanhee Lee11168.33
Sungchan Kim238726.65
Hyunok Oh345740.49
Soonhoi Ha41684174.65