NDLI: Failure-Aware Task Scheduling of Synchronous Data Flow Graphs Under Real-Time Constraints

Content Provider	Springer Nature Link
Author	Lee, Chanhee Kim, Sungchan Oh, Hyuk Ha, Soonhoi
Copyright Year	2013
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.
Starting Page	201
Ending Page	212
Page Count	12
File Format	PDF
ISSN	19398018
Journal	Journal of Signal Processing Systems
Volume Number	73
Issue Number	2
e-ISSN	19398115
Language	English
Publisher	Springer US
Publisher Date	2013-05-08
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Failure-aware scheduling Task rescheduling Permanent fault Genetic algorithm Task migration Signal, Image and Speech Processing Circuits and Systems Electrical Engineering Image Processing and Computer Vision Pattern Recognition Computer Imaging, Vision, Pattern Recognition and Graphics
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Signal Processing Control and Systems Engineering Information Systems Modeling and Simulation Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Leakage-Aware Multiprocessor Scheduling

Power-Aware 3D Computer Graphics Rendering

Three-Phase Algorithms for Task Scheduling in Distributed Mobile DSP System with Lifetime Constraints

Implementation, Scheduling, and Adaptation of Partial Expansion Graphs on Multicore Platforms

Modeling Resolution of Resources Contention in Synchronous Data Flow Graphs

Performance Analysis of Weakly-Consistent Scenario-Aware Dataflow Graphs

Parameterized Scheduling of Topological Patterns in Signal Processing Dataflow Graphs

Instruction Scheduling for Low Power

Peak Temperature Minimization via Task Allocation and Splitting for Heterogeneous MPSoC Real-Time Systems

Failure-Aware Task Scheduling of Synchronous Data Flow Graphs Under Real-Time Constraints

Similar Documents

Leakage-Aware Multiprocessor Scheduling

Power-Aware 3D Computer Graphics Rendering

Three-Phase Algorithms for Task Scheduling in Distributed Mobile DSP System with Lifetime Constraints

Implementation, Scheduling, and Adaptation of Partial Expansion Graphs on Multicore Platforms

Modeling Resolution of Resources Contention in Synchronous Data Flow Graphs

Performance Analysis of Weakly-Consistent Scenario-Aware Dataflow Graphs

Parameterized Scheduling of Topological Patterns in Signal Processing Dataflow Graphs

Instruction Scheduling for Low Power

Peak Temperature Minimization via Task Allocation and Splitting for Heterogeneous MPSoC Real-Time Systems

Failure-Aware Task Scheduling of Synchronous Data Flow Graphs Under Real-Time Constraints