Finitary Real-Time Calculus: Efficient Performance Analysis of Distributed Embedded Systems
2013 (English)In: Proc. Real-Time Systems Symposium: RTSS 2013, IEEE Computer Society, 2013Conference paper (Refereed)
Real-Time Calculus (RTC) is a powerful framework to analyzereal-time performance of distributed embedded systems. However,RTC may run into serious analysis efficiency problems when appliedto systems of large scale and/or with complex timing parameter characteristics.The main reason is that many RTC operations generatecurves with periods equal to the hyper-period of the input curves.Therefore, the analysis in RTC has exponential complexity. In practisethe curve periods may explode rapidly when several componentsare serially connected, which leads to low analysis efficiency.In this work, we propose Finitary RTC to solve the above problem.Finitary RTC only maintains and operates on a limited part ofeach curve that is relevant to the final analysis results, which resultsin pseudo-polynomial computational complexity. Experiments showthat Finitary RTC can drastically improve the analysis efficiency overthe original RTC. The original RTC may take hours or even days toanalyze systems with complex timing characteristics, but FinitaryRTC typically can complete the analysis in seconds. Even for simplesystems, Finitary RTC also typically speeds up the analysis procedureby hundreds of times. While getting better efficiency, FinitaryRTC does not introduce any extra pessimism, i.e., it yields analysisresults as precise as the original RTC.
Place, publisher, year, edition, pages
IEEE Computer Society, 2013.
Research subject Computer Science with specialization in Real Time Systems
IdentifiersURN: urn:nbn:se:uu:diva-209549OAI: oai:DiVA.org:uu-209549DiVA: diva2:658400