We consider in this talk a general and intuitive communication model between multi-periodic real-time tasks following hypothesis of Liu and Layland. We recall that the system can then be directly expressed using a ”Synchronous Data-flow Graph”. The question tackled is the development of efficient algorithms to evaluate the worst-case latency of this system (ie. the maximum time elapsed between the activation of an input and an output of the system).

We first develop an exact pseudo-polynomial evaluation method to calculate the worst case latency of a system from a given input to a connected outcome. Then, we present several efficient (polynomial or pseudo-polynomial) strategies to roughly frame this value by computing upper and lower bounds. In paticular, we show that bounds can be computed using a polynomial amount of computation time, while the time required to compute the exact value increases linearly according to the average repetition factor. Furthermore, the gap between the exact result and its upper (resp. lower) bound is evaluated between 10 and 15% (resp. 20 and 30%).