Please use this identifier to cite or link to this item: https://doi.org/10.1109/SYNASC.2007.53
Title: Path-constrained relaxed schedulability analysis
Authors: Andrei, Ş.
Chakraborty, S. 
Keywords: Computational and structural complexity
Feasibility analysis
SAT problem
Scheduling
Issue Date: 2007
Source: Andrei, Ş., Chakraborty, S. (2007). Path-constrained relaxed schedulability analysis. Proceedings - 9th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2007 : 474-481. ScholarBank@NUS Repository. https://doi.org/10.1109/SYNASC.2007.53
Abstract: The schedulability analysis problem for many realistic task models is known to be hard (NP or coNP). As this severely restricts the application of these task models, recently there has been a considerable amount of interest in relaxed or approximate notions of schedulability, with the hope that they can be checked more efficiently. In this paper we introduce yet another natural notion of relaxed schedulability, which is parameterized in terms of the number of paths in a task set. In the model we consider, each task is represented by a directed acyclic graph where the nodes of such a graph are annotated with execution times and deadlines. Our proposed notion of schedulability allows a certain number of paths from each task graph to be non-schedulable. For describing the relaxed schedulability analysis, we formally define a measure called pseudo-K-schedulability, which corresponds to the situation when the task set has exactly K schedulable paths. At one extreme is the classical notion of schedulability analysis, where the problem is NP hard in our and many other task models. At the other extreme of this spectrum we have the trivial notion of schedidability analysis, where no path needs to be schedulable. Problems in between allow for a flexible notion of schedulability. This paper studies the relaxed schedulability because not all paths in a code are executed. This paper shows a fundamental result, namely the membership of the pseudoschedulability problem to the class of #P-hard problems. © 2008 IEEE.
Source Title: Proceedings - 9th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2007
URI: http://scholarbank.nus.edu.sg/handle/10635/41963
ISBN: 0769530788
DOI: 10.1109/SYNASC.2007.53
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

49
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.