Probabilistic State-Based RT-Analysis of SDFGs on MPSoCs with Shared Memory Communication

Ralf Stemmer and Henning Schlender and Maher Fakih and Kim Grüttner and Wolfgang Nebel
2019 Design, Automation & Test in Europe Conference & Exhibition (DATE)
This paper extends a state-based timing analysis for Synchronous Dataflow Applications on an MPSoC with shared memory.The existing approach transforms a mapped and timing annotated SDF graph into a timed automata representationfor the analysis of timing properties. One major drawback of the existing timing annotation approach is the usage of best- and worst-case execution time intervals,resulting in an overestimation of the actual timing behavior.Furthermore, those intervals can have a high impact on the timed automata state space and possibly slow down the analysis process. This paper proposes to replace the timing bound annotation with a Probability Density Function.For the overall timing analysis we use a stochastic timed automata model.We demonstrate and evaluate our approach on a Sobel filter, which is used in many image and video processing algorithms.As a reference, we compare our stochastic execution time model against a fixed best-/worst-case execution time model and against the measured execution time on an FPGA prototype.The results are promising and clearly indicate that our probabilistic approach provides tighter timing analysis results in comparison to the best-/worst-case execution analysis model.
3 / 2019