Linköping University: Students Alumni Trade and Industry/Society Internal Search
ICCAD02

Schedulability Analysis of Multiprocessor Real-Time Applications with Stochastic Task Execution Times

Sorin Manolache
 
Petru Eles Author homepage
Zebo Peng Author homepage

Int'l Conference on Computer Aided Design, ICCAD 02, San Jose, California, USA, November 10-14, 2002, pp. 699-706

ABSTRACT
This paper presents an approach to the analysis of task sets implemented on multiprocessor systems, when the task execution times are specified as generalized probability distributions. Because of the extreme complexity of the problem, an exact solution is practically impossible to be obtained even for toy examples. Therefore, our methodology is based on approximating the generalized probability distributions of execution times by Coxian distributions of exponentials. Thus, we transform the generalized semi-Markov process, corresponding to the initial problem, into a continuous Markov chain (CTMC) which, however, is extremely large and, hence, most often is impossible to be stored in memory. We have elaborated a solution which allows to generate and analyze the CTMC in an efficient way, such that only a small part has to be stored at a given time. Several experiments investigate the impact of various parameters on complexity, in terms of time and memory, as well as the trade-offs regarding the accuracy of generated results.


Related files:
ICCAD02.pdfAdobe Acrobat portable document


[MEP02] Sorin Manolache, Petru Eles, Zebo Peng, "Schedulability Analysis of Multiprocessor Real-Time Applications with Stochastic Task Execution Times", Int'l Conference on Computer Aided Design, ICCAD 02, San Jose, California, USA, November 10-14, 2002, pp. 699-706
( ! ) perl script by Giovanni Squillero with modifications from Gert Jervan   (v3.1, p5.2, September-2002-)