%0 Journal Article %1 MaxtGraph1991 %A Puschner, Peter P. %A Schedl, Anton V. %D 1991 %J Kluwer Academic Publishers, Boston %K MAXT SPA graph mgr realtime %P 1-27 %T Computing Maximum Task Execution Times - A Graph-Based Approach. %U http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.52.8250&rep=rep1&type=pdf %X The knowledge of program execution times is crucial for the development and the verification of real-time software. Therefore, there is a need for methods and tools to predict the timing behavior of pieces of program code and entire programs. This paper presents a novel method for the analysis of program execution times. The computation of MAximum eXecution Times (MAXTs) is mapped onto a graph-theoretical problem that is a generalization of the computation of a maximum cost circulation in a directed graph. Programs are represented by T-graphs, timing graphs, which are similar to ow graphs. These graphs reflect the structure and the timing behavior of the code. Relative capacity constraints, a generalization of capacity constraints that bound the ow in the edges, express user-supplied information about infeasible paths. To compute MAXTs, T-graphs are searched for those execution paths which correspond to a maximum cost circulation. The search problem is transformed into an integer linear programming problem. The solution of the linear programming problem yields the MAXT. The special merits of the presented method are threefold: It uses a concise notation to characterize the static structure of a program and its possible execution paths. Furthermore, the notation allows for a description of the feasible paths through the program code that characterizes the behavior of the code sufficiently to compute the exact maximum execution time of the program - not just a bound thereof. Finally, linear program solving does not only yield maximum execution times, but also produces detailed information about the execution time and the number of executions of every single program construct in the worst case. This knowledge is valuable for a more comprehensive analysis of the timing of a program.

@article{MaxtGraph1991, abstract = {The knowledge of program execution times is crucial for the development and the verification of real-time software. Therefore, there is a need for methods and tools to predict the timing behavior of pieces of program code and entire programs. This paper presents a novel method for the analysis of program execution times. The computation of MAximum eXecution Times (MAXTs) is mapped onto a graph-theoretical problem that is a generalization of the computation of a maximum cost circulation in a directed graph. Programs are represented by T-graphs, timing graphs, which are similar to ow graphs. These graphs reflect the structure and the timing behavior of the code. Relative capacity constraints, a generalization of capacity constraints that bound the ow in the edges, express user-supplied information about infeasible paths. To compute MAXTs, T-graphs are searched for those execution paths which correspond to a maximum cost circulation. The search problem is transformed into an integer linear programming problem. The solution of the linear programming problem yields the MAXT. The special merits of the presented method are threefold: It uses a concise notation to characterize the static structure of a program and its possible execution paths. Furthermore, the notation allows for a description of the feasible paths through the program code that characterizes the behavior of the code sufficiently to compute the exact maximum execution time of the program - not just a bound thereof. Finally, linear program solving does not only yield maximum execution times, but also produces detailed information about the execution time and the number of executions of every single program construct in the worst case. This knowledge is valuable for a more comprehensive analysis of the timing of a program.}, added-at = {2009-07-08T20:08:09.000+0200}, author = {Puschner, Peter P. and Schedl, Anton V.}, biburl = {https://www.bibsonomy.org/bibtex/297fd24001169ad50b2d8226dc347d90d/gwpl}, description = {dblp}, interhash = {0665b5c08bb34fab0f437f3900753e9e}, intrahash = {97fd24001169ad50b2d8226dc347d90d}, journal = {Kluwer Academic Publishers, Boston}, keywords = {MAXT SPA graph mgr realtime}, month = May, note = {,,1-27() (C)Kluwer Academic Publishers, Boston. Manufactured in The Netherlands. PETER P. PUSCHNER AND ANTON V. SCHEDL Institut fur Technische Informatik, Technische Universitat Wien Institut fur Technische Informatik, TechnA-1040 Vienna, Austria}, pages = {1-27}, timestamp = {2009-07-09T09:11:46.000+0200}, title = {Computing Maximum Task Execution Times - A Graph-Based Approach.}, url = {http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.52.8250&rep=rep1&type=pdf}, year = 1991 }