Finitary real-time calculus: Efficient performance analysis of distributed embedded systems

Nan Guan, Wang Yi

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

14 Citations (Scopus)

Abstract

Real-Time Calculus (RTC) is a powerful framework to analyze real-time performance of distributed embedded systems. However, RTC may run into serious analysis efficiency problems when applied to systems of large scale and/or with complex timing parameter characteristics. The main reason is that many RTC operations generate curves with periods equal to the hyper-period of the input curves. Therefore, the analysis in RTC has exponential complexity. In practise the curve periods may explode rapidly when several components are 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 of each curve that is relevant to the final analysis results, which results in pseudo-polynomial computational complexity. Experiments show that Finitary RTC can drastically improve the analysis efficiency over the original RTC. The original RTC may take hours or even days to analyze systems with complex timing characteristics, but Finitary RTC typically can complete the analysis in seconds. Even for simple systems, Finitary RTC also typically speeds up the analysis procedure by hundreds of times. While getting better efficiency, Finitary RTC does not introduce any extra pessimism, i.e., it yields analysis results as precise as the original RTC.
Original languageEnglish
Title of host publicationProceedings - IEEE 34th Real-Time Systems Symposium, RTSS 2013
Pages330-339
Number of pages10
DOIs
Publication statusPublished - 1 Dec 2013
Externally publishedYes
EventIEEE 34th Real-Time Systems Symposium, RTSS 2013 - Vancouver, BC, Canada
Duration: 3 Dec 20136 Dec 2013

Conference

ConferenceIEEE 34th Real-Time Systems Symposium, RTSS 2013
CountryCanada
CityVancouver, BC
Period3/12/136/12/13

Keywords

  • Performance analysis
  • Real-time calculus
  • Real-time systems
  • Scalability

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this