a
Tool for Performance Analysis
of
Complex Real Time Systems
Content
Introduction
Example
CyNC - a Graphical Tool for Modelling and Performance Analysis of Real Time Systems.
Installing CyNC
Disclaimer
Using service elements
Specifying external bounds
Specifying Processing Resources
Backlog and Delay Calculation
Aggregating and Packetizing flows
Running the Analysis
Introduction
Example
CyNC - a Graphical Tool for Modelling and Performance Analysis of Real Time Systems.
Installing CyNC
Disclaimer
Using service elements
Specifying external bounds
Specifying Processing Resources
Backlog and Delay Calculation
Aggregating and Packetizing flows
Running the Analysis
Introduction
CyNC is short for Cyclic Network Calculus and denotes a method for applying Network Calculus to real time systems with cyclic dependencies. Such systems include router networks providing real time services such as IntServ or DiffServ as well as embedded systems with complex dependencies between processes.
More information on Network Calculus is found in various papers and books by J.Y. Le Boudec as well as the seminal paper by R. Cruz. Recent advancements in the theory are given by L. Thiele [link to paper]. The latest developments allowing cyclic dependencies are given by H. Schioler in [1] and [2].
The basic objects in network calculus are upper and lower bounds on ingess traffic or recieved workload as well as on the service assigned to various processes. Workload and service bounds are given as functions of time t and formally bound the workload and service within time intervals of length t .
Provided bounds on the workload recieved by some server as well as the associated processing capabilities associated bounds on the egress flow as well as remaining processing resources are obtained along with bounds on delay and backlog in the server. Bounds on egress flow is forwarded to the next service unit in line or passed across system boundaries. Remaining processing resources are forwarded to lower priority units in a prioritized system.
Example
Consider two processes tC and tN in a prioritized real time system recieving workload from the system exterior and exhanging workload as well. (The example and its practical relevance is discussed further in H. Schioler)
For such a system the following work flow diagram is given
To illustrate the use of various elements a SimuLink/CyNC diagram of the above work flow diagram is shown below.
Installing CyNC
CyNC is implemented as a number of MATLAB m-files along with SimuLink mdl-files.
All files may be downloaded to any location from
http://www.control.auc.dk/~henrik/CyNC
A running installation and valid license of MATLAB and SimuLink are required.
The CyNC library is developed and tested for MATLAB 6.5 and MATLAB 7.0 but it should be firmly stated that
Disclaimer
CyNC 0.1 is still on an experimental stage and no responsibilities a taken w.r.t. correctness of the tool.
Any errors may be reported to henrik@control.auc.dk
Using service elements
So far CyNC includes only two types of service elements FPrio, which adopts a fixed priority service discipline among ingress flows and FIFO where a FIFO flows are merged in a single ingress queue and served in FIFO order.
Generally processing resources should be fed into the first input terminal In1 of service elements, whereas remaining resources are taken from the first output terminal Out1. This is illustrated in the above CyNC diagram where external processing resources are fed into In1 of FIFO and forwarded through Out1 of FIFO to In1 of FIFO1 (naming is default SimuLink name assignment and may be modified as wished).
Flows are fed into the remaining input terminal In2 .. In10 and corresponding output flows are given on corresponding output terminals Out2 .. Out10. More precisely; if flow bounds are given to In3 on some service element then corresponding output flow bounds are found at Out3 on the same service element.
Specifying external bounds
External flow and service bounds are specified in CyNC by elements Generator, Affine, and Periodic, all of which must be connected to a standard SimuLink constant block as shown below.
The examples in this section you may find as running models in "manual1.mdl" in your CyNC install directory.
CyNC is short for Cyclic Network Calculus and denotes a method for applying Network Calculus to real time systems with cyclic dependencies. Such systems include router networks providing real time services such as IntServ or DiffServ as well as embedded systems with complex dependencies between processes.
More information on Network Calculus is found in various papers and books by J.Y. Le Boudec as well as the seminal paper by R. Cruz. Recent advancements in the theory are given by L. Thiele [link to paper]. The latest developments allowing cyclic dependencies are given by H. Schioler in [1] and [2].
The basic objects in network calculus are upper and lower bounds on ingess traffic or recieved workload as well as on the service assigned to various processes. Workload and service bounds are given as functions of time t and formally bound the workload and service within time intervals of length t .
Provided bounds on the workload recieved by some server as well as the associated processing capabilities associated bounds on the egress flow as well as remaining processing resources are obtained along with bounds on delay and backlog in the server. Bounds on egress flow is forwarded to the next service unit in line or passed across system boundaries. Remaining processing resources are forwarded to lower priority units in a prioritized system.
Example
Consider two processes tC and tN in a prioritized real time system recieving workload from the system exterior and exhanging workload as well. (The example and its practical relevance is discussed further in H. Schioler)
For such a system the following work flow diagram is given
Bounds and external flows f1C and f3N are assumed given along with
bounds on processing resources SC.
From externally given bounds CyNC provides bounds for internal flows as
well as delays and backlogs in server queues. As a final result delays
for complete transactions such as the transaction indicated by flows f3N, g1N, f2C, g2C, f2N and g3N may be found.
CyNC - a Graphical Tool for Modelling and Performance Analysis of Real Time Systems.
To facilitate CyNC for practical use a graphical modelling and analysis tool is developed as a library for the MATLAB/SimuLink environment. A screenshot of the elements in the library is shown below.
CyNC - a Graphical Tool for Modelling and Performance Analysis of Real Time Systems.
To facilitate CyNC for practical use a graphical modelling and analysis tool is developed as a library for the MATLAB/SimuLink environment. A screenshot of the elements in the library is shown below.
- Elements FIFO and FPrio are service elements.
- Generator, Affine, and Periodic are used to specify external flow bounds.
- Resource is used for specifying externally bounded processing resources.
- Aggregate merges flows by adding flow bounds.
- Packetize accounts for burst effects of packetizing.
- Delay and Queue calculates bounds for delay and queue given flow and service bounds.
- SConv concatenates service elements in series by computing the so called inf/plus convolution of service bounds.
- Curveplot plots bounds.
To illustrate the use of various elements a SimuLink/CyNC diagram of the above work flow diagram is shown below.
Installing CyNC
CyNC is implemented as a number of MATLAB m-files along with SimuLink mdl-files.
All files may be downloaded to any location from
http://www.control.auc.dk/~henrik/CyNC
A running installation and valid license of MATLAB and SimuLink are required.
The CyNC library is developed and tested for MATLAB 6.5 and MATLAB 7.0 but it should be firmly stated that
Disclaimer
CyNC 0.1 is still on an experimental stage and no responsibilities a taken w.r.t. correctness of the tool.
Any errors may be reported to henrik@control.auc.dk
Using service elements
So far CyNC includes only two types of service elements FPrio, which adopts a fixed priority service discipline among ingress flows and FIFO where a FIFO flows are merged in a single ingress queue and served in FIFO order.
Generally processing resources should be fed into the first input terminal In1 of service elements, whereas remaining resources are taken from the first output terminal Out1. This is illustrated in the above CyNC diagram where external processing resources are fed into In1 of FIFO and forwarded through Out1 of FIFO to In1 of FIFO1 (naming is default SimuLink name assignment and may be modified as wished).
Flows are fed into the remaining input terminal In2 .. In10 and corresponding output flows are given on corresponding output terminals Out2 .. Out10. More precisely; if flow bounds are given to In3 on some service element then corresponding output flow bounds are found at Out3 on the same service element.
Specifying external bounds
External flow and service bounds are specified in CyNC by elements Generator, Affine, and Periodic, all of which must be connected to a standard SimuLink constant block as shown below.
The examples in this section you may find as running models in "manual1.mdl" in your CyNC install directory.
For each of the element types Generator,
Affine, and Periodic the connected constant blocks have particular
interpretation.
For generator the constant block Constant4 upper and lower bounds are given as a vector of en even number of elements, of which the first half specifies the upper bound and the second half the lower bound. For upper and lower bounds separately the final number specifies the slope of the bound for large time values, whereas the previous parameters specifies the bound numerically.
Considering the settings below
For generator the constant block Constant4 upper and lower bounds are given as a vector of en even number of elements, of which the first half specifies the upper bound and the second half the lower bound. For upper and lower bounds separately the final number specifies the slope of the bound for large time values, whereas the previous parameters specifies the bound numerically.
Considering the settings below
In this case the upper bound is
specified numerically by points (0,5),(1,10),(2,15),(3,20) and a
straight line with slope 5 going through the point (3,20). The
corresponding lower bound is given numerically by points
(0,0),(1,0),(2,0),(3,0) and a straight line with slope 3 passing
through
(3,0). The bounds so specified are shown graphically in the figure below
The Periodic element takes 4 input parameters in the following order: period, packet size, tolerance and time limit. The element specifies flow bounds for a periodic source with constant packet length where reception times may be jittered a certain amount given by the tolerance. The time limit indicates the time bound after which an affine approximation is used. Consider the settings below
The Periodic element takes 4 input parameters in the following order: period, packet size, tolerance and time limit. The element specifies flow bounds for a periodic source with constant packet length where reception times may be jittered a certain amount given by the tolerance. The time limit indicates the time bound after which an affine approximation is used. Consider the settings below
Packets of size 5 are recieved with a
period of 10 time units. Packet reception may be jittered 2 time units
from the periodic time instants and after 40 time units and affine
approximation with a slope computed as the ratio PacketSize/Period is
used. The above settings correspond to the bounds shown
graphically below.
The Affine element is used for
specifying affine flow bounds. The element takes two input parameters:
rate and burst. Upper and lower bounds are given as functions r t + b
and [r t - b]+ respectively, where []+ denotes positive parts.
Settings
Settings
specify a rate of 0.5 workload units per
time unit and a burst of 5 workload units. Corresponding bounds are
shown below
and the MATLAB simulation should be started.
The analysis uses iteration to obtain its result. The first part of the iteration establishes so called fluid results, i.e. it solves the flow rate equations. When a stationary value is found CYNCEVENT should be set to 1 giving the following MATLAB command window
Specifying Processing
Resources
External processing resources are provided in real life systems by raw CPU capabilities. A processing unit typically provides 1 unit of processing time per time unit. In such a case upper and lower bounds on processing resource would be the function 1* t. Frequently more than one CPU is associated to the system under analysis. In this case different slopes may be used to model CPUs of different speed, e.g. one CPU may have a bound 1* t whereas another may have 2* t indicating the latter to be twice as fast as the former. In other cases, for example when CPUs are used for other external purposes, upper and lower bounds are no longer identical and may not be linear.
Bounds on processing resources are specified in CyNC with the Resource element connected to a SimuLink constant block as shown below.
The examples in this section you may find as running models in "manual2.mdl" and "manual3.mdl" in your CyNC install directory.
External processing resources are provided in real life systems by raw CPU capabilities. A processing unit typically provides 1 unit of processing time per time unit. In such a case upper and lower bounds on processing resource would be the function 1* t. Frequently more than one CPU is associated to the system under analysis. In this case different slopes may be used to model CPUs of different speed, e.g. one CPU may have a bound 1* t whereas another may have 2* t indicating the latter to be twice as fast as the former. In other cases, for example when CPUs are used for other external purposes, upper and lower bounds are no longer identical and may not be linear.
Bounds on processing resources are specified in CyNC with the Resource element connected to a SimuLink constant block as shown below.
The examples in this section you may find as running models in "manual2.mdl" and "manual3.mdl" in your CyNC install directory.
The constant block specifies resource
bounds as was explained above for the Generator element. Thus the
settings
Specify upper and lower resource bound
by the function 1*t.
As shown in the example diagram above the output of the resource block should be connected to the 1st. input terminal In1 of the service element to which the processing resources are associated as shown below
As shown in the example diagram above the output of the resource block should be connected to the 1st. input terminal In1 of the service element to which the processing resources are associated as shown below
Backlog and Delay Calculation
Backlog and delay of particular flows in service elements is computed with the Queue and Delay elements in the CyNC library. Both elements take one set of flow bounds and one set of resource bounds as inputs and computes maximum backlog and delay as results. The output is presented as a positive real number and may be shown using the standard SimuLink display element as shown below. (The figure shows resources and flows fed directly from external specifications, which is not the typical situation)
The examples in this section you may find as running models in "manual4.mdl" and "manual5.mdl" in your CyNC install directory.
Backlog and delay of particular flows in service elements is computed with the Queue and Delay elements in the CyNC library. Both elements take one set of flow bounds and one set of resource bounds as inputs and computes maximum backlog and delay as results. The output is presented as a positive real number and may be shown using the standard SimuLink display element as shown below. (The figure shows resources and flows fed directly from external specifications, which is not the typical situation)
The examples in this section you may find as running models in "manual4.mdl" and "manual5.mdl" in your CyNC install directory.
In the above backlog calculation a
maximum backlog of 5 workload units is obtained, which corresponds to
the computational inputs of a lower resource bound 1*t and an upper flow bound of 0.5*t + 5.
This
gives a stable situation w.r.t. rates (processing rate is higher than
inflow rate). Since service is specified to be fluid, the maximum
backlog is identical to the burst of the inflow; namely 5 units.
When using Queue and Delay elements in larger configurations with service elements serive bounds may be taken from output terminal of the latter. An inflow to some terminal, e.g. In2 of a service element produces corresponding output bounds on the terminal Out2. On this terminal the separate service bounds for this particular flow are also found. Hence to compute the backlog or delay experienced by a particular flow passing through some service element, this specific service bound should be used. In that case a configuration as shown below is obtained
When using Queue and Delay elements in larger configurations with service elements serive bounds may be taken from output terminal of the latter. An inflow to some terminal, e.g. In2 of a service element produces corresponding output bounds on the terminal Out2. On this terminal the separate service bounds for this particular flow are also found. Hence to compute the backlog or delay experienced by a particular flow passing through some service element, this specific service bound should be used. In that case a configuration as shown below is obtained
The use of the Delay element is identical.
Aggregating and Packetizing flows
Flows may in CyNC be aggregated i.e. merged, in which case bounds are simply added. The Aggregate element is used for this purpose. The Aggregate element takes two flows in arbitrary order and add their corresponding bounds.
The examples in this section you may find as running models in "manual6.mdl" and "manual7.mdl" in your CyNC install directory.
The effect of packetizing flows may be accounted for by using the Packetize element. Packetize takes two input parameters: mult and add. When presented to upper and lower flow bounds U and L respectively Packetize responds with bounds mult*U+add and [mult*L-add]+. Parameters for Packetize are given by opening the block with a double-click and obtaining the following diagram
Aggregating and Packetizing flows
Flows may in CyNC be aggregated i.e. merged, in which case bounds are simply added. The Aggregate element is used for this purpose. The Aggregate element takes two flows in arbitrary order and add their corresponding bounds.
The examples in this section you may find as running models in "manual6.mdl" and "manual7.mdl" in your CyNC install directory.
The SConv
element is used for computing the overall affect to some flow of
passing
through a number of service elements. Up to 4 separate lower service
bounds may be concatened in this element. The particular concatenation
takes plce by performing so called inf/plus convolution of the
lower service bounds presented as inputs. A typical example is shown
below where particular service bounds are taken from two service
elements and concatenated in an SConv
element.
which also illustrates the use of the Curveplot element, that plots flow
and service bounds.
The effect of packetizing flows may be accounted for by using the Packetize element. Packetize takes two input parameters: mult and add. When presented to upper and lower flow bounds U and L respectively Packetize responds with bounds mult*U+add and [mult*L-add]+. Parameters for Packetize are given by opening the block with a double-click and obtaining the following diagram
where mult is set to 2 and add to 5.
As an example consider the diagram below
As an example consider the diagram below
with affine parameters [0.5 10] . Bounds
before and after packetizing with parameters 2 and 5 are shown in the
table below.
 |
 |
Running
the Analysis
Before running the analysis a MATLAB script: globals.m should be run. Then the command window should be prepaired to set the global variable CYNCEVENT to1. This gives the following MATLAB command window
Before running the analysis a MATLAB script: globals.m should be run. Then the command window should be prepaired to set the global variable CYNCEVENT to1. This gives the following MATLAB command window
Herafter the MATLAB simulation
parameters should be set as follows
and the MATLAB simulation should be started.
The analysis uses iteration to obtain its result. The first part of the iteration establishes so called fluid results, i.e. it solves the flow rate equations. When a stationary value is found CYNCEVENT should be set to 1 giving the following MATLAB command window
and the iteration starts solving for non
fluid effects.
There is so far no assistance in CyNC to determine when to move from fluid iteration to non-fluid. It is suggested to inspect running results with the Curveplot element to determine when a stationary fluid solution is found. This method may be used to determine the overall number of iterations. Automatic determination of iteration length is currently investigated.
There is so far no assistance in CyNC to determine when to move from fluid iteration to non-fluid. It is suggested to inspect running results with the Curveplot element to determine when a stationary fluid solution is found. This method may be used to determine the overall number of iterations. Automatic determination of iteration length is currently investigated.