We use cookies to improve your experience with our site.
Xiao-Tong Cui, Kai-Jie Wu, Tong-Quan Wei, Edwin Hsing-Mean Sha. Worst-Case Finish Time Analysis for DAG-Based Applications in the Presence of Transient Faults[J]. Journal of Computer Science and Technology, 2016, 31(2): 267-283. DOI: 10.1007/s11390-016-1626-6
Citation: Xiao-Tong Cui, Kai-Jie Wu, Tong-Quan Wei, Edwin Hsing-Mean Sha. Worst-Case Finish Time Analysis for DAG-Based Applications in the Presence of Transient Faults[J]. Journal of Computer Science and Technology, 2016, 31(2): 267-283. DOI: 10.1007/s11390-016-1626-6

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

  • 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.
  • loading

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return