Ernesto Wandeler, Lothar Thiele
© 2008 Computer Engineering and Networks Laboratory (TIK), ETH Zurich,
Switzerland
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:
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.
The latest release of the toolbox: RTC Toolbox
The RTC Toolbox requires a MATLAB version R14SP3, 7.1 or later.
There are two alternatives for the use of the RTC 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.
Each time you want to use the toolbox, do the following
>> cd /home/user/my_tools/rtc
>> rtc_load
>> cd $MATLAB$/toolbox/rtc
>> rtc_install
Now you can start using the RTC Toolbox. To explore the functionality of
the RTC Toolbox, try the following:
>> help rtc
>> rtc_uninstall
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.
The RTC Toolbox Tutorial introduces the RTC Toolbox in four parts:
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.
The latest release of the toolbox: RTS Toolbox
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.
>> cd $MATLAB$/toolbox/rts
>> rts_install
Now you can start using the RTS Toolbox with exploring the example systems in the $MATLAB$/toolbox/rts/rtsdemos directory.
>> rts_uninstall
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.
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},
}
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.
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:
#include <pesimdes.h>
Make sure that your compiler and linker can find the corresponding files of the PESIMDES library.
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.
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
Simulation length
Simulation outputs
Random number generator
Verbose option
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.
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);