Modular Performance Analysis with Real-Time Calculus

Ernesto Wandeler, Lothar Thiele
© 2008 Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Switzerland

Table of Contents

  1. Modular Performance Analysis with Real-Time Calculus
    1. Table of Contents
    2. Overview
    3. RTC Toolbox
      1. Overview
      2. Download
      3. Setup
        1. Option A: Loading of the Real-Time Calculus (RTC) Toolbox
        2. Option B: Installation of the Real-Time Calculus (RTC) Toolbox
        3. Uninstalling the Real-Time Calculus (RTC) Toolbox
      4. License
      5. RTC Toolbox User Guide
    4. Real-Time Simulation Toolbox
      1. Overview
      2. Download
      3. Setup
        1. Installation of the Real-Time Simulation (RTS) Toolbox
        2. Uninstalling the Real-Time Simulation (RTS) Toolbox:
      4. License
    5. PESMIDES
      1. Overview
      2. Modeling Scope
      3. Download and Setup
      4. License
      5. User Guide
    6. Multicore
      1. Overview
      2. Tutorial



Overview

This web page serves as a central resource to the research on Modular Performance Analysis, Real-Time Calculus, and Real-Time Simulation. All results are based on our publications in the area, see for example Google Scholar. For more comprehensive coverage, the following PhD theses are recommended:




RTC Toolbox

Overview

The Real-Time Calculus (RTC) Toolbox is a free Matlab toolbox for system-level performance analysis of distributed real-time and embedded system. It is based on an efficient representation of Variability Characterization Curves (VCC's) and implements most min-plus and max-plus algebra operators for these curves. On top of the min-plus and max-plus algebra operators, the RTC Toolbox provides a library of functions for Modular Performance Analysis with Real-Time Calculus.

Download

The latest release of the toolbox: RTC Toolbox

Setup

The RTC Toolbox requires a MATLAB version R14SP3, 7.1 or later.

There are two alternatives for the use of the RTC Toolbox:

  1.     load the toolbox each time you need it
  2.     installation of the toolbox

You can try out the toolbox using the first option and install the toolbox later on.

Option 1 requires that every time you want to use the RTC Toolbox you need to perform the steps 3 and 4 below.

Option 2 will install the RTC Toolbox, such that it is loaded automatically on startup of Matlab. This requires to go only once through the installation routine, but will slightly increase the time for starting Matlab. Installation makes use of Matlab's savepath function, which may not work for users with limited write permissions.

Option A: Loading of the Real-Time Calculus (RTC) Toolbox

  1. Extract the downloaded zip package. The extracted directory will contain a directory called rtc.
  2. Copy or move the directory rtc to some directory, e.g. to /home/user/my_tools/rtc

Each time you want to use the toolbox, do the following

  1. Open Matlab and change to the rtc directory:
    >> cd /home/user/my_tools/rtc
  2. Run:
    >> rtc_load

Option B: Installation of the Real-Time Calculus (RTC) Toolbox

  1. Extract the downloaded zip package. The extracted directory will contain a directory called rtc.
  2. Copy or move the directory rtc to its final installation destination, e.g. to $MATLAB$/toolbox/rtc
  3. Open Matlab and change to the rtc directory:
    >> cd $MATLAB$/toolbox/rtc
  4. Run:
    >> rtc_install

Now you can start using the RTC Toolbox. To explore the functionality of the RTC Toolbox, try the following:
 >> help rtc

Uninstalling the Real-Time Calculus (RTC) Toolbox

  1. Run:
    >> rtc_uninstall
  2. You may now delete the directory $MATLAB$/toolbox/rtc

License

Copyright (c) 2004-2008 Computer Engineering and Networks Laboratory (TIK) ETH Zurich, Switzerland. All rights reserved.

Real-Time Calculus (RTC) Toolbox

Redistribution and use in source and binary forms, with or without modi- fication, are permitted provided that the following conditions are met:

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

RTC Toolbox User Guide

The RTC Toolbox Tutorial introduces the RTC Toolbox in four parts:




Real-Time Simulation Toolbox

Overview

The Real-Time Simulation (RTS) Toolbox is a free Matlab toolbox for system-level discrete-event simulation of distributed real-time and embedded systems.

The RTS Toolbox uses the component-based design approach of the MPA/RTC Toolbox however, instead of using abstract representations of event arrivals and resource availabilities (such as Variability Characterization Curves (VCC)), it uses traces. It provides facilities for random generation of traces of finite length given the VCC specification, and computation of the VCCs given the traces.

The library of components in the toolbox at the moment supports:

This is a preliminary version of the simulator and there is no User Guide available at the moment. There are several examples included in the release that can be used as a reference.

Download

The latest release of the toolbox: RTS Toolbox

Setup

The RTS Toolbox requires a MATLAB version R14SP3, 7.1 or later.

You can try out the toolbox by using the following setup steps. You need to repeat them each time you want to use the toolbox.

Installation of the Real-Time Simulation (RTS) Toolbox

  1. Extract the downloaded zip package. The extracted directory will contain a directory called rts.
  2. Copy or move the directory rts to its final installation destination, e.g. to $MATLAB$/toolbox/rts
  3. Open Matlab and change to the rts directory:
    >> cd $MATLAB$/toolbox/rts
  4. Run:
    >> rts_install

Now you can start using the RTS Toolbox with exploring the example systems in the $MATLAB$/toolbox/rts/rtsdemos directory.

Uninstalling the Real-Time Simulation (RTS) Toolbox:

  1. Run:
    >> rts_uninstall
  2. You may now delete the directory $MATLAB$/toolbox/rts

License

Copyright (c) 2004-2009 Computer Engineering and Networks Laboratory (TIK) ETH Zurich, Switzerland. All rights reserved.

Real-Time Simulation (RTS) Toolbox

Redistribution and use in source and binary forms, with or without modi- fication, are permitted provided that the following conditions are met:

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.




PESMIDES

Overview

PESIMDES (Performance Simulation of Distributed Embedded Systems) is an extendible open-source library for performance simulation of distributed embedded systems based on SystemC.

SystemC, a widespread platform for system-level modeling and simulation, can be used to estimate the performance of distributed embedded systems modeled on a high level of abstraction, i.e. as an aggregation of event generators, processing resources and tasks with BCET/WCET. However, this requires a substantial set-up effort, as all the necessary components of the system model must be implemented from scratch. Because on a high level of abstraction all distributed embedded systems are composed of the same basic components, we have decided to collect a number of such components in a common repository in order to reduce the set-up effort required for a SystemC performance simulation. The result is PESIMDES, a library for performance estimations of distributed embedded systems build on top of SystemC. PESIMDES is intended to be a pool of reusable modules which are designed to facilitate the system-level modeling and simulation of large distributed embedded systems in early design stages.

BibTeX entry for citation:

 @MISC{pesimdes,
     author  = {Simon Perathoner},
     title   = {{PESIMDES}},
     url     = {http://www.mpa.ethz.ch/PESIMDES},
     howpublished = {\\{\tt http://www.mpa.ethz.ch/PESIMDES}}
     year    = {2006},
 }

Modeling Scope

PESIMDES provides estimations for two important performance metrics of a distributed embedded system: latencies and memory requirements. On the one hand the simulation allows to record the maximum observed end-to-end delay for the processing of event streams. On the other hand the maximum observed activation backlog of every single task can be monitored.

These results can be compared to the timing/memory requirements of the system and possible deadline misses or buffer overflows may be detected. The sequence of events leading to such a requirement violation can easily be traced back as all generated input stimuli are stored into trace-files which can be used to replicate the simulation.

Like any other simulation based approach, PESIMDES can only analyze single input instances out of all possible system inputs. Thus the tool itself cannot provide hard bounds for the worst-case performance of a system. It is up to the designer to provide a set of appropriate simulation stimuli which cover all relevant corner cases.

PESIMDES offers various components to model the environment, the computation and communication resources, the tasks and the buffers of a distributed embedded system. To create a new system model, it is suffcient to select the proper components, instantiate them and link them together. The following table gives an overview of the current modeling power of PESIMDES.

Input event models periodic
periodic with jitter
periodic with burst
sporadic
sporadic with jitter
sporadic with burst
input from tracefile
Resource models & Scheduling FP resource (preemptive/non-preemptive)
EDF resource (preemptive/non-preemptive)
TDMA resource (preemptive/non-preemptive)*
Processing Components task with single activation
task with multiple activation (AND)
task with multiple activation (OR)

The modeling scope can easily be extended by adding new components to the library.

Download and Setup

The latest release of the PESIMDES SystemC library: PESIMDES

PESIMDES is built on top of the SystemC 2.1 C++ class library provided by the Open SystemC Initiative (http://www.systemc.org). In oder to use PESIMDES it is necessary to download, compile and install the SystemC library (v2.1 or above). Please refer to http://www.systemc.org/ for more information about the setup of SystemC.

Installing the PESIMDES library:

Make sure that your compiler and linker can find the corresponding files of the PESIMDES library.

License

Copyright (c) 2004-2006 Computer Engineering and Networks Laboratory (TIK) ETH Zurich, Switzerland. All rights reserved.

PESIMDES library

Redistribution and use in source and binary forms, with or without modi- fication, are permitted provided that the following conditions are met:

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

User Guide

Modeling

To model a distributed embedded system with PESIMDES for performance analysis, it is sufficient to write a simple SystemC program that instantiates and connects proper modules of the PESIMDES library. In particular it is necessary to:

In the following we demonstrate the modeling procedure for the example system depicted in the figure below:


The following listing reports the SystemC code that models the depicted system using components of the PESIMDES library.

  1 #include "pesimdes.h"

  3 #define MAXBUFFER 1000

  5 bool verbose = false;


  8 int sc_main (int argc , char *argv[]) {

 10    // initialize the random number generator
 11    srand(-24);


 14    // Module instantiations

 16    // Event stream generators
 17    input_periodic_with_burst_uwj input_generator_1 ("I1",sc_time(20,SC_MS),sc_time(55,SC_MS),
                                                        sc_time(2,SC_MS),"input_trace_1.tra");
 18    input_periodic input_generator_2 ("I2",sc_time(10,SC_MS),"input_trace_2.tra");

 20    // Tasks
 21    task t1("T1",2,"AND",1);
 22    task t2("T2");
 23    task t3("T3");
 24    task t4("T4",2);
 25    task t5("T5");

 27    // Resources
 28    resource_n_tasks_fixed_priority_preemptive cpu_1("CPU1",2);
 29    resource_n_tasks_EDF_preemptive cpu_2("CPU2",2);
 30    resource_n_tasks_fixed_priority_preemptive cpu_3("CPU3",1);

 32    // Event sinks
 33    output_display display_1("O1");
 34    output_display display_2("O2");


 37    // Task mapping
 38    cpu_1.assign_task(t1,0,sc_time(2,SC_MS),1);
 39    cpu_1.assign_task(t2,1,sc_time(1,SC_MS),2);
 40    cpu_2.assign_task(t3,0,sc_time(7,SC_MS),sc_time(18,SC_MS));
 41    cpu_2.assign_task(t4,1,sc_time(3,SC_MS),sc_time(35,SC_MS));
 42    cpu_3.assign_task(t5,0,sc_time(8,SC_MS),1);


 45   // Channel instantiations

 47    // Task activation buffers
 48    my_sc_fifo<event_token> buffer_T1_1(MAXBUFFER);
 49    my_sc_fifo<event_token> buffer_T1_2(MAXBUFFER);
 50    my_sc_fifo<event_token> buffer_T2(MAXBUFFER);
 51    my_sc_fifo<event_token> buffer_T3(MAXBUFFER);
 52    my_sc_fifo<event_token> buffer_T4(MAXBUFFER);
 53    my_sc_fifo<event_token> buffer_T5(MAXBUFFER);

 55    // Dummy buffers for event sinks
 56    sc_fifo<event_token> dummy_buffer_display_1(1);
 57    sc_fifo<event_token> dummy_buffer_display_2(1);


 60    // Port binding

 62    // Stream I1-O1
 63    input_generator_1.out(buffer_T3);
 64    t3.in[0](buffer_T3);
 65    t3.out[0](dummy_buffer_display_1);
 66    display_1.in(dummy_buffer_display_1);

 68    // Stream I2-O2
 69    input_generator_2.out(buffer_T1_1);
 70    t1.in[0](buffer_T1_1);
 71    t1.out[0](buffer_T4);
 72    t4.in[0](buffer_T4);
 73    t4.out[0](buffer_T5);
 74    t4.out[1](buffer_T1_2);
 75    t1.in[1](buffer_T1_2);
 76    t5.in[0](buffer_T5);
 77    t5.out[0](buffer_T2);
 78    t2.in[0](buffer_T2);
 79    t2.out[0](dummy_buffer_display_2);
 80    display_2.in(dummy_buffer_display_2);


 83    // Initial state
 84    set_initial_token(buffer_T1_2,2);


 87    // Start simulation
 88    sc_start(100000,SC_MS);


 91    // Print performance results
 92    cout << "\n Max. observed End-to-End Delay from I2 to O2: " <<
            sc_time_output(display_2.getmaxlatency("I2")) << " (event no. " <<
            display_2.getseqnoofmaxlatency("I2") << ")\n";
 93    cout << "Max. observed Backlog T2: " << buffer_T2.getmaxbacklog() << "\n";

 95    return 0;
 96 }

The instantiation and connection of the various components is straightforward. More documentation about the single constructor calls can be found in the corresponding header files of the library.

Simulation

Once the topology of the system is modeled by instantiating and connecting proper PESIMDES modules, it is necessary to configure the simulation. In particular the following simulation parameters must be set:

Maximum Buffersize

A maximum size for the task activation buffers must be specified (see line 3 of above listing). Note that the buffer size does not influence the behavior of the system, i.e. a full buffer does not block a writing task. In case of a buffer overflow an appropriate exception is raised and the simulation is stopped.

Simulation length

The length of the simulation must be specified as parameter of the sc_start call (see line 88 of above listing), which determines the duration of the SystemC simulation. Note that by this parameter you specify the amount of time to simulate and not the running time of the simulation.

Simulation outputs

In order to obtain the estimations for the requested performance characteristics of the system it is necessary to output the return values of the functions getmaxlatency and getmaxbacklog called on the corresponding components (see lines 92 and 93 of above listing)

Random number generator

Various event generators make use of a random number generator. The corresponding seed value can be set explicitly (see line 11 of above listing). By choosing twice the same seed number the results of a simulation can be reproduced.

Verbose option

It is possible to instruct the PESIMDES components to print to standard output a detailed simulation log. This is done by setting the verbose flag (see line 5 of above listing). The log traces generation, processing and propagation of every single event in the system. Note that the use of the verbose feature may significantly increase the running time of the simulation.



Multicore

Overview

he Multicore extension to the RTC Toolbox is a free Matlab toolbox to

The Toolbox has been developed in the course of the Predator Project http://www.predator-project.eu.


Consider a Multicore Platform as in the picture below. This toolbox allows to derive


Tutorial

Part 1 - Representing Interference as Arrival Curves

We implemented a MATLAB toolbox to derive the access pattern of a set of superblocks, that executes periodically, onto a shared resource. The definition of the set of superblocks that executes on a particular core is done in an ASCII file, which is the input to the analysis. The file has the following format:

%number of superblocks
%period
%minimum number of access requests
%maximum number of access requests
%communication time per access request
%minimum computation time
%maximum computation time
10
10000
39 7 195 81 182 252 259 180 57 10
39 7 195 81 182 252 259 180 57 10
2
0 2 54 23 61 75 80 56 17 0
0 2 54 23 61 75 80 56 17 0

The derivation of the arrival curves, is then performed by calling the function:

RTCcurve_upper = interference_single_periodic_task(config_file, output, delta, debug)

The first argument to this function is config_file, representing the MATLAB file handle to the configuration file. The argument output, defines whether a plot representing the curves should be plotted output=1, or not output=0, while argument delta specifies the maximum value on the x-axis, in case a plot is produced. Argument debug=1 allows to produce a plot with all the intermediate data that is produces during the derivation of the arrival curve. The function returns the parameters RTCcurve_upper representing the resulting arrival curve.

This results in the following output:


Part 2 - Worst-Case Analysis for hybrid arbitration on the shared resource

In order to perform WCRT analysis for the set of superblocks that executes on the processing element under analysis, we consider all the other processing elements in the multicore platform as interferers. Their interference is represented as arrival curve for each core, and thus we represent their overall interference as the sum the corresponding arrival curves. As an example, consider a system with 4 cores, where Core 1 is the processing element under analysis. Then we compute the overall interference as follows:

alpha_2 = interference_single_periodic_task(config_file_core2, output, delta, debug);
alpha_3 = interference_single_periodic_task(config_file_core3, output, delta, debug);
alpha_4 = interference_single_periodic_task(config_file_core4, output, delta, debug);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%produces the overall interference, considering that core1
%is the core under analysis
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpha_23 = rtcplus(alpha_2, alpha_3);
alpha_interference = rtcplus(alpha_23, alpha_4);

As a result, the overall interference is now stored in alpha_interference.

Following that, the set of superblocks that have to be analyzed and the arbiter have to be defined. Consider a configuration file as described above for each core. Then, the configuration for the processing element under analysis (Core 1 in our example), is performed as follows:

[A D H] = importdata(config_file_core1_opt, ' ',7);
number_of_blocks = A.data(1);
S_opt = zeros(number_of_blocks, 5);
%the upper bound on the execution time
S_opt(1:number_of_blocks, 1) = A.data(3+2*number_of_blocks+1:3+3*number_of_blocks),
%the upper bound on access requests
S_opt(1:number_of_blocks, 2) = A.data(3+number_of_blocks:3+2*number_of_blocks-1);
%the slot assignment, e.g., Slot 1 is assigned to this core
S_opt(1:number_of_blocks, 3) = 1;
%the execution model: 0 = sequential, x \in R = the starting time for time-triggered execution
S_opt(1:number_of_blocks, 4) = 0;
%the period
S_opt(1:number_of_blocks, 5) = 2.5;

Then, the arbiter has to be defined:

%communication time per access request
C = 0.5;

%the arbiter
%the static segment
theta.assignments = [ 2 1 3];
%the starting times of the static slots
theta.starting_times = [0 11 15];
%the length of the static segment
theta.L = 17
%the length of the dynamic segment
theta.dyn_length = 7;
%note: the arbitration length is L+dyn_length

%the worst-case number of interferers and 
%pending access requests at the beginning
%of the dynamic segment
Ltot = 2
Lpre = 2;

%the length of a minislot in the dynamic
%segment
ml = 0.5;

Eventually, the WCRT can be computed by the following command:

[schedulable, wcct] = analyzeTask(S, alpha_interference, theta, Ltot, C, ml, Lpre);



!!! Dieses Dokument stammt aus dem ETH Web-Archiv und wird nicht mehr gepflegt !!!
!!! This document is stored in the ETH Web archive and is no longer maintained !!!