Failure-Aware Task Scheduling of Synchronous Data Flow Graphs Under Real-Time Constraints
- Title
- Failure-Aware Task Scheduling of Synchronous Data Flow Graphs Under Real-Time Constraints
- Author
- 오현옥
- Keywords
- Failure-aware scheduling; Task rescheduling; Permanent fault; Genetic algorithm; Task migration
- Issue Date
- 2013-05
- Publisher
- Springer
- Citation
- JOURNAL OF SIGNAL PROCESSING SYSTEMS FOR SIGNAL IMAGE AND VIDEO TECHNOLOGY 권: 73 호: 2 페이지: 201-212
- 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.
- URI
- https://link.springer.com/article/10.1007%2Fs11265-013-0753-3
- ISSN
- 1939-8018
- DOI
- 10.1007/s11265-013-0753-3
- Appears in Collections:
- COLLEGE OF ENGINEERING[S](공과대학) > INFORMATION SYSTEMS(정보시스템학과) > Articles
- Files in This Item:
There are no files associated with this item.
- Export
- RIS (EndNote)
- XLS (Excel)
- XML