Schedulability Analysis of Multiprocessor RealTime Applications with Stochastic Task Execution Times
Int'l Conference on Computer Aided Design, ICCAD 02, San Jose, California, USA, November 1014, 2002, pp. 699706
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 semiMarkov 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 tradeoffs regarding the accuracy of generated results.
Related files: 
ICCAD02.pdf  Adobe Acrobat portable document 
[MEP02] Sorin Manolache, Petru Eles, Zebo Peng, "Schedulability Analysis of Multiprocessor RealTime Applications with Stochastic Task Execution Times", Int'l Conference on Computer Aided Design, ICCAD 02, San Jose, California, USA, November 1014, 2002, pp. 699706 
