Please use this identifier to cite or link to this item:
DC FieldValue
dc.titlePath-constrained relaxed schedulability analysis
dc.contributor.authorAndrei, Ş.
dc.contributor.authorChakraborty, S.
dc.identifier.citationAndrei, Ş., 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.
dc.description.abstractThe 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.
dc.subjectComputational and structural complexity
dc.subjectFeasibility analysis
dc.subjectSAT problem
dc.typeConference Paper
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.sourcetitleProceedings - 9th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2007
Appears in Collections:Staff Publications

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

Google ScholarTM



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