Modeling and Analysis of Data Flow Graphs Using the Digraph Real-Time Task Model

摘要

Data flow graphs are widely used for modeling and analysis of real-time streaming applications in which having a predictable and reliable implementation is an essential requirement. In this paper, we consider scheduling a set of data flow graphs such that liveness and boundedness properties are guaranteed, which leads to a predictable and correct behavior of the application. A formal translation method is proposed to map a given set of data flow graphs to a set of graph-based real-time tasks. Additionally, sufficient conditions are derived under which the obtained task set provides a semantically correct implementation of the given data flow graphs. It is shown that the proposed approach provides a higher level of design flexibility compared to the existing methods which use a simpler, i.e. periodic, task model.