NDLI: Worst-Case Finish Time Analysis for DAG-Based Applications in the Presence of Transient Faults

Content Provider	Springer Nature Link
Author	Cui, Xiao Tong Wu, Kai Jie Wei, Tong Quan Sha, Edwin Hsing Mean
Copyright Year	2016
Abstract	Tasks in hard real-time systems are required to meet preset deadlines, even in the presence of transient faults, and hence the analysis of worst-case finish time (WCFT) must consider the extra time incurred by re-executing tasks that were faulty. Existing solutions can only estimate WCFT and usually result in significant under- or over-estimation. In this work, we conclude that a sufficient and necessary condition of a task set experiencing its WCFT is that its critical task incurs all expected transient faults. A method is presented to identify the critical task and WCFT in O(\|V \| + \|E\|) where \|V \| and \|E\| are the number of tasks and dependencies between tasks, respectively. This method finds its application in testing the feasibility of directed acyclic graph (DAG) based task sets scheduled in a wide variety of fault-prone multi-processor systems, where the processors could be either homogeneous or heterogeneous, DVS-capable or DVS-incapable, etc. The common practices, which require the same time complexity as the proposed critical-task method, could either underestimate the worst case by up to 25%, or overestimate by 13%. Based on the proposed critical-task method, a simulated-annealing scheduling algorithm is developed to find the energy efficient fault-tolerant schedule for a given DAG task set. Experimental results show that the proposed critical-task method wins over a common practice by up to 40% in terms of energy saving.
Starting Page	267
Ending Page	283
Page Count	17
File Format	PDF
ISSN	10009000
Journal	Journal of Computer Science and Technology
Volume Number	31
Issue Number	2
e-ISSN	18604749
Language	English
Publisher	Springer US
Publisher Date	2016-03-07
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	fault tolerance worst-case analysis simulated annealing energy conservation dynamic voltage scaling (DVS) Computer Science Software Engineering Theory of Computation Data Structures, Cryptology and Information Theory Artificial Intelligence (incl. Robotics) Information Systems Applications (incl. Internet)
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Computer Science Applications Software 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

Tolerating Permanent State Transition Faults in Asynchronous Sequential Machines

Better-Than-Worst-Case Design: Progress and Opportunities

Fault Tolerance and Recovery for Group Communication Services in Distributed Networks

A new classification of path-delay fault testability in terms of stuck-at faults

PartialRC: A Partial Recomputing Method for Efficient Fault Recovery on GPGPUs

Constructing Edge-Colored Graph for Heterogeneous Networks

UiLog: Improving Log-Based Fault Diagnosis by Log Analysis

Worst-Case Nash Equilibria in Restricted Routing

Effectiveness Analysis of DVFS and DPM in Mobile Devices

Worst-Case Finish Time Analysis for DAG-Based Applications in the Presence of Transient Faults

Similar Documents

Tolerating Permanent State Transition Faults in Asynchronous Sequential Machines

Better-Than-Worst-Case Design: Progress and Opportunities

Fault Tolerance and Recovery for Group Communication Services in Distributed Networks

A new classification of path-delay fault testability in terms of stuck-at faults

PartialRC: A Partial Recomputing Method for Efficient Fault Recovery on GPGPUs

Constructing Edge-Colored Graph for Heterogeneous Networks

UiLog: Improving Log-Based Fault Diagnosis by Log Analysis

Worst-Case Nash Equilibria in Restricted Routing

Effectiveness Analysis of DVFS and DPM in Mobile Devices

Worst-Case Finish Time Analysis for DAG-Based Applications in the Presence of Transient Faults