Timing Analysis of Process Graphs with Finite Communication Buffers
Chung-Wei Lin, Marco Di Natale, Haibo Zeng, Linh Thi Xuan Phan, Alberto Sangiovanni-Vincentelli

Citation
Chung-Wei Lin, Marco Di Natale, Haibo Zeng, Linh Thi Xuan Phan, Alberto Sangiovanni-Vincentelli. "Timing Analysis of Process Graphs with Finite Communication Buffers". Prodeedings of IEEE Real-Time and Embedded Technology and Applications Symposium, 227-236, April, 2013; The publication does not specifically credit TerraSwarm, but is nonetheless of interest to TerraSwarm researchers in Task 4 (Methodologies, Models and Tools).

Abstract
Real-Time Calculus (RTC) is a modular performance analysis framework for real-time embedded systems. It can be used to compute the worst-case and best-case response times of tasks with general activation patterns and configurations, such as pipelines of tasks that are connected via finite buffers. In this paper, we extend the existing RTC framework to analyze arbitrary graph configurations of tasks and messages, with mixed periodic and event-based activation models and finite buffers between any pair of nodes. Our extension also improves upon several sources of pessimism in the existing analysis. We present an application of the extended RTC to the Loosely Time-Triggered Architecture (LTTA) implementation of synchronous models, commonly used in the development of embedded automotive, avionics and control systems. We show how our method can be used to model scheduling and communication delays in an LTTA mapping, which gives tighter analysis bounds on the output rate and the latency compared to existing techniques. The evaluation on automotive workloads shows that our approach is scalable and outperforms existing techniques in terms of analysis accuracy.

Electronic downloads

Citation formats  
  • HTML
    Chung-Wei Lin, Marco Di Natale, Haibo Zeng, Linh Thi Xuan
    Phan, Alberto Sangiovanni-Vincentelli. <a
    href="http://www.terraswarm.org/pubs/66.html"
    >Timing Analysis of Process Graphs with Finite
    Communication Buffers</a>, Prodeedings of IEEE
    Real-Time and Embedded Technology and Applications
    Symposium, 227-236, April, 2013; The publication does not
    specifically credit TerraSwarm, but is nonetheless of
    interest to TerraSwarm researchers in Task 4 (Methodologies,
    Models and Tools).
  • Plain text
    Chung-Wei Lin, Marco Di Natale, Haibo Zeng, Linh Thi Xuan
    Phan, Alberto Sangiovanni-Vincentelli. "Timing Analysis
    of Process Graphs with Finite Communication Buffers".
    Prodeedings of IEEE Real-Time and Embedded Technology and
    Applications Symposium, 227-236, April, 2013; The
    publication does not specifically credit TerraSwarm, but is
    nonetheless of interest to TerraSwarm researchers in Task 4
    (Methodologies, Models and Tools).
  • BibTeX
    @inproceedings{LinDiNataleZengThiXuanPhanSangiovanniVincentelli13_TimingAnalysisOfProcessGraphsWithFiniteCommunication,
        author = {Chung-Wei Lin and Marco Di Natale and Haibo Zeng
                  and Linh Thi Xuan Phan and Alberto
                  Sangiovanni-Vincentelli},
        title = {Timing Analysis of Process Graphs with Finite
                  Communication Buffers},
        booktitle = {Prodeedings of IEEE Real-Time and Embedded
                  Technology and Applications Symposium},
        pages = {227-236},
        month = {April},
        year = {2013},
        note = {The publication does not specifically credit
                  TerraSwarm, but is nonetheless of interest to
                  TerraSwarm researchers in Task 4 (Methodologies,
                  Models and Tools).},
        abstract = {Real-Time Calculus (RTC) is a modular performance
                  analysis framework for real-time embedded systems.
                  It can be used to compute the worst-case and
                  best-case response times of tasks with general
                  activation patterns and configurations, such as
                  pipelines of tasks that are connected via finite
                  buffers. In this paper, we extend the existing RTC
                  framework to analyze arbitrary graph
                  configurations of tasks and messages, with mixed
                  periodic and event-based activation models and
                  finite buffers between any pair of nodes. Our
                  extension also improves upon several sources of
                  pessimism in the existing analysis. We present an
                  application of the extended RTC to the Loosely
                  Time-Triggered Architecture (LTTA) implementation
                  of synchronous models, commonly used in the
                  development of embedded automotive, avionics and
                  control systems. We show how our method can be
                  used to model scheduling and communication delays
                  in an LTTA mapping, which gives tighter analysis
                  bounds on the output rate and the latency compared
                  to existing techniques. The evaluation on
                  automotive workloads shows that our approach is
                  scalable and outperforms existing techniques in
                  terms of analysis accuracy.},
        URL = {http://terraswarm.org/pubs/66.html}
    }
    

Posted by Chung-Wei Lin on 13 May 2013.
Groups: tools

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.