TY - GEN

T1 - Interactive schedulability analysis

AU - Bordoloi, Unmesh D.

AU - Chakraborty, Samarjit

PY - 2006

Y1 - 2006

N2 - A typical design process for real-time embedded systems involves choosing the values of certain system parameters and performing a schedulability analysis to determine whether all deadline constraints can be satisfied. If such an analysis returns a negative answer, then some of the parameters are modified and the analysis is invoked once again. This iteration is repeated till a schedulable design is obtained. However, the schedulability analysis problem for most task models is intractable (usually co-NP hard) and hence such an iterative design process is often very expensive. To get around this problem, we introduce the concept of "interactive" schedulability analysis. It is based on the observation that if only a small number of system parameters are changed, then it is not necessary to rerun the full schedulability analysis algorithm, thereby making the iterative design process considerably faster. We refer to this analysis as being "interactive" because it is supposed to be run in an interactive mode. This concept is fairly general and can be applied to a wide variety of task models. In this paper we have chosen the recurring real-time task model because it can be used to represent realistic applications from the embedded systems domain (containing conditional branches and fine-grained deadline constraints). Our experimental results show that using our scheme can lead to more than 20 x speedup for each invocation of the schedulability analysis algorithm, compared to the case where the full algorithm is run.

AB - A typical design process for real-time embedded systems involves choosing the values of certain system parameters and performing a schedulability analysis to determine whether all deadline constraints can be satisfied. If such an analysis returns a negative answer, then some of the parameters are modified and the analysis is invoked once again. This iteration is repeated till a schedulable design is obtained. However, the schedulability analysis problem for most task models is intractable (usually co-NP hard) and hence such an iterative design process is often very expensive. To get around this problem, we introduce the concept of "interactive" schedulability analysis. It is based on the observation that if only a small number of system parameters are changed, then it is not necessary to rerun the full schedulability analysis algorithm, thereby making the iterative design process considerably faster. We refer to this analysis as being "interactive" because it is supposed to be run in an interactive mode. This concept is fairly general and can be applied to a wide variety of task models. In this paper we have chosen the recurring real-time task model because it can be used to represent realistic applications from the embedded systems domain (containing conditional branches and fine-grained deadline constraints). Our experimental results show that using our scheme can lead to more than 20 x speedup for each invocation of the schedulability analysis algorithm, compared to the case where the full algorithm is run.

UR - http://www.scopus.com/inward/record.url?scp=33749610823&partnerID=8YFLogxK

U2 - 10.1109/RTAS.2006.22

DO - 10.1109/RTAS.2006.22

M3 - Conference contribution

AN - SCOPUS:33749610823

SN - 0769525164

SN - 9780769525167

T3 - Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS

SP - 147

EP - 156

BT - Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium

T2 - 12th IEEE Real-Time and Embedded Technology and Applications Symposium

Y2 - 4 April 2006 through 7 April 2006

ER -