emmtrix Wiki - User contributions [en]

Logical Execution Time (LET)

2024-09-27T09:44:28Z

Michael.rueckauer:

==Logical Execution Time for Control Applications==
The most obvious approach for parallelization or porting control software to multi-core systems is based on a last is best model that relies on shared memory and global variables. However, jitter can occur when using this approach, which results in non-deterministic runtime behaviour. Additionally, the approach has poor scalability with the number of cores. This article discusses the use of logical execution time for parallelization of control software for multi-core systems that overcomes these limitations.

==Inter-Task Commuication Model==
{| class="wikitable"
![[File:Last Is Best.png|left|thumb]]
!
===Last Is Best (LIB)===
Currently, most control software uses the Last Is Best (LIB) inter-task communication model. The last available values are read and written from a shared memory. Data consistency is ensured at task level by synchronization mechanisms (such as spin locks), so that a component always reads the same age of values, e.g. temperature and speed. In parallel processing, different components are executed on different cores or tasks.<sup>1</sup>

One problem of the LIB model is sampling and response time jitter. In the event of jitter, a component either accesses obsolete data or control decisions are available too late. Both effects lead to a degradation in the performance of the control software.

Another disadvantage of jitter is that the system no longer behaves deterministically. Whether jitter occurs or not depends on the execution time of each task and the system load. Since utilization and execution times vary, it effectively depends on a random selection whether old or current data is used.

The problem of jitter increases with the number of cores since more components compete simultaneously for access to shared memory. This is one cause why the LIB model scales poorly with an increasing number of cores.
|-
|[[File:Logical Execution Time.png|thumb|left]]
|
===Last Is Best (LIB)===
Currently, most control software uses the Last Is Best (LIB) inter-task communication model. The last available values are read and written from a shared memory. Data consistency is ensured at task level by synchronization mechanisms (such as spin locks), so that a component always reads the same age of values, e.g. temperature and speed. In parallel processing, different components are executed on different cores or tasks.<sup>1</sup>

One problem of the LIB model is sampling and response time jitter. In the event of jitter, a component either accesses obsolete data or control decisions are available too late. Both effects lead to a degradation in the performance of the control software.

Another disadvantage of jitter is that the system no longer behaves deterministically. Whether jitter occurs or not depends on the execution time of each task and the system load. Since utilization and execution times vary, it effectively depends on a random selection whether old or current data is used.

The problem of jitter increases with the number of cores since more components compete simultaneously for access to shared memory. This is one cause why the LIB model scales poorly with an increasing number of cores.

|}

emmtrix Dependency Analyzer

2024-08-14T14:16:07Z

Michael.rueckauer: Fix

The emmtrix Dependency Analyzer (eDA) analyzes C source code to extract which output signals/variables depend on which input signals/variables.

== Dependency Analysis ==
The core dependency analysis of the eDA tool is using the C source code and an entry function (typically a runnable in an automotive application) as input. It calculates which global variables depend on each other when the function is executed. If a variable v1 depends on variable v2, the result of v1 (after function execution) is somehow influenced by the value of v2 (before function execution) when the function is executed.

The dependency analysis is not limited to programs using global variables for transporting information. By applying an automatic preprocessing and postprocessing step, more generic programs can be transformed into programs using global variables. This way we can e.g. detect dependencies between AUTOSAR signals, network communication function, etc.

=== Simple Case ===

In the following example, we have the global variables <code>in1</code>, <code>out1</code>, <code>out2</code> and <code>out3</code>.

* <code>in1</code> is assigned to out1, so the value of <code>out1</code> depend on <code>in1</code>.
* <code>in1</code> is not changed in the function, so it is not listed in the results.
* <code>out2</code> is assigned a constant value, so it has no dependency on any input value.
* <code>in1</code> is added to <code>out3</code>, so the value of <code>out3</code> depends both on <code>in1</code> and on <code>out3</code> itself (i.e. the value prior function execution).

{| class="wikitable"
|+
!Input Code
!Result
|-
|
<syntaxhighlight lang="c">
int in1;
int out1, out2, out3;

void func(void) {
out1 = in1;
out2 = 5;
out3 += in1;
}
</syntaxhighlight>
|<pre>out1: in1
out2: -
out3: out3 in1
</pre>
|}

=== Conditional ===

The eDA distinguish between two kinds of dependencies:

# '''Data dependencies''' are caused by assigning a value to variable.
# '''Control dependencies''' are caused by the control structure of the program e.g. if a variable changed conditionally. Control dependencies are indicated in the results by the <code>(c)</code> suffix.
The eDA restricts that one variable can be either control or data dependent on another variable. The data dependency is considered stronger that the control dependency. If both dependencies appear, only the data dependency will appear in the results.

In this example, the dependency of output variables on input variables is determined based on a conditional if statement. The function checks the value of in1 to decide which values to assign to out1 and out2. The result shows that out1 is control dependent on in1 and data dependent on in2. out2 is both control and data dependent on in1 but only the dominant data dependency is shown.

{| class="wikitable"
|+
!Input Code
!Result
|-
|
<syntaxhighlight lang="c">
int in1, in2;
int out1, out2;

void func(void) {
if (in1) {
out1 = in2;
out2 = in1;
} else {
out1 = 0;
out2 = 0;
}
}
</syntaxhighlight>
|<pre>out1: in1(c) in2
out2: in1
</pre>
|}

=== Delay Elements ===
In this example, a simple implementation of a delay element is shown. The output variable out1 is assigned the value of in1 from the previous function call. If the function is executed only one time, the output variable is not influenced by any input variable and thus would only have a dependency to the internal variable.

eDA considers this scenario by calculating the dependencies for multiple function calls. If one variable is dependent on a variable from a previous function call, it is considered as a delayed (data or control) dependency. Delayed dependencies are indicated in the results by a suffix of <code>^-N</code>, where N is the number of function calls the dependency is delayed. Internally non-delayed dependencies are modeled as delayed dependencies with N=0. One variable cannot have multiple delayed or non-delayed dependencies to the same variable. Dependencies with a smaller delay are considered stronger than dependencies with a larger delay.
{| class="wikitable"
|+
!Input Code
!Result
|-
|
<syntaxhighlight lang="c">
int in1;
int out1;
static int internal1;

void func(void) {
out1 = internal1;

internal1 = in1;
}
</syntaxhighlight>
|<pre>internal1: in1
out1: internal1 in1^-1
</pre>
|}

=== Local Variables ===
In this example, two local variables are used to store intermediate results. eDA considers the local variables and their dependencies to the global variables. The result shows that the output variable out1 is dependent on in1 and in2. The local variables are not listed in the results as their lifetime ends after the function execution.
{| class="wikitable"
|+
!Input Code
!Result
|-
|
<syntaxhighlight lang="c">
float in1, in2;
float out1;

void func(void) {
float local1;
float local2;

local1 = in1 * in1 + in2 * in2;
local2 = sqrt(local1);

out1 = local2 + 1.0f;
}
</syntaxhighlight>
|<pre>out1: in1 in2
</pre>
|}
=== Ignoring Name Dependencies===
In this example, the local variable local1 is reused to store two different intermediate results. Reusing (global or local) variables is common in C programming and also used by code generators like TargedLink. A name-based dependency analysis would consider the output variable out2 dependent on in1 and in2. However, eDA ignores the name of the variable and considers only the data flow. The result shows that out2 is only dependent on in2.
{| class="wikitable"
|+
!Input Code
!Result
|-
|<syntaxhighlight lang="c">
float in1, in2;
float out1, out2;

void func(void) {
float local1;

local1 = in1 * in1;
out1 = local1;

local1 = sqrt(in2);
out2 = local1;
}
</syntaxhighlight>
|<pre>out1: in1
out2: in2
</pre>
|}

=== Parametrized Dependency Analysis===
In automotive applications, it is common to use the same software across multiple car models with different configurations. eDA supports a parametrized dependency analysis where one or more input variables are considered as constant parameters. Code parts that are deactivated by the constant parameters are not considered during dependency analysis. This is useful to calculate the dependencies only for one active configuration and to reduce the number of dependencies.

eDA follows a two step approach for the parametrized dependency analysis. In the first step, the constant parameters are propagated through the code and inactive code parts are removed. In the second step, the dependency analysis is performed on the transformed code. Even the transformed code is available as intermediate code for transparency reasons. This is useful to understand the results and to verify the correctness of the transformation.

The following example is identical to the conditional example. Only the input variable in1 is considered as a constant parameter (indicated by the <code>static const</code> in the input code). The result shows the intermediate code after the transformation. The if statement is removed and the output variables are assigned the values of the else branch. In contrast to the conditional example, the output variables are not dependent on the input variable in1.
{| class="wikitable"
|+
!Input Code
!Intermediate Code
!Result
|-
|<syntaxhighlight lang="c">
static const int in1 = 0;
int in2;
int out1, out2;

void func(void) {
if (in1) {
out1 = in2;
out2 = in1;
} else {
out1 = 0;
out2 = 0;
}
}
</syntaxhighlight>
|<syntaxhighlight lang="c">
int in2;
int out1, out2;

void func(void) {
out1 = 0;
out2 = 0;
}
</syntaxhighlight>
|<pre>out1: -
out2: -
</pre>
|}

=== AUTOSAR Integration ===
In AUTOSAR, ports are accessed using IRead/IWrite function. By providing dummy implementations of these functions that simple read or write a dummy global variable, the AUTOSAR program is transformed into a program with global variables. This is used as input for the dependency analysis.

=== Undescribed Features ===

* Function calls to known functions
* Function calls to unknown functions
* Optimization for array with const access
* Loops
* Switch case
* Pointer function parameters
* Output
** C debug output
** XML output
** Reachability output
** Dependency path output
* Propagation of tags (e.g. OBD, ASIL-D)
* AUTOSAR integration

== See Also ==

* Official webpage - https://www.emmtrix.com/tools/emmtrix-dependency-analyzer

[[Category:emmtrix Tools]]

emmtrix Dependency Analyzer

2024-08-14T14:09:51Z

Michael.rueckauer: Fix

The emmtrix Dependency Analyzer (eDA) analyzes C source code to extract which output signals/variables depend on which input signals/variables.

== Dependency Analysis ==
The core dependency analysis of the eDA tool is using the C source code and an entry function (typically a runnable in an automotive application) as input. It calculates which global variables depend on each other when the function is executed. If a variable v1 depends on variable v2, the result of v1 (after function execution) is somehow influenced by the value of v2 (before function execution) when the function is executed.

The dependency analysis is not limited to programs using global variables for transporting information. By applying an automatic preprocessing and postprocessing step, more generic programs can be transformed into programs using global variables. This way we can e.g. detect dependencies between AUTOSAR signals, network communication function, etc.

=== Simple Case ===

In the following example, we have the global variables <code>in1</code>, <code>out1</code>, <code>out2</code> and <code>out3</code>.

* <code>in1</code> is assigned to out1, so the value of <code>out1</code> depend on <code>in1</code>.
* <code>in1</code> is not changed in the function, so it is not listed in the results.
* <code>out2</code> is assigned a constant value, so it has no dependency on any input value.
* <code>in1</code> is added to <code>out3</code>, so the value of <code>out3</code> depends both on <code>in1</code> and on <code>out3</code> itself (i.e. the value prior function execution).

{| class="wikitable"
|+
!Input Code
!Result
|-
|
<syntaxhighlight lang="c">
int in1;
int out1, out2, out3;

void func(void) {
out1 = in1;
out2 = 5;
out3 += in1;
}
</syntaxhighlight>
|<pre>out1: in1
out2: -
out3: out3 in1
</pre>
|}

=== Conditional ===

The eDA distinguish between two kinds of dependencies:

# '''Data dependencies''' are caused by assigning a value to variable.
# '''Control dependencies''' are caused by the control structure of the program e.g. if a variable changed conditionally. Control dependencies are indicated in the results by the <code>(c)</code> suffix.
The eDA restricts that one variable can be either control or data dependent on another variable. The data dependency is considered stronger that the control dependency. If both dependencies appear, only the data dependency will appear in the results.

In this example, the dependency of output variables on input variables is determined based on a conditional if statement. The function checks the value of in1 to decide which values to assign to out1 and out2. The result shows that out1 is control dependent on in1 and data dependent on in2. out2 is both control and data dependent on in1 but only the dominant data dependency is shown.

{| class="wikitable"
|+
!Input Code
!Result
|-
|
<syntaxhighlight lang="c">
int in1, in2;
int out1, out2;

void func(void) {
if (in1) {
out1 = in2;
out2 = in1;
} else {
out1 = 0;
out2 = 0;
}
}
</syntaxhighlight>
|<pre>out1: in1(c) in2
out2: in1
</pre>
|}

=== Delay Elements ===
In this example, a simple implementation of a delay element is shown. The output variable out1 is assigned the value of in1 from the previous function call. If the function is executed only one time, the output variable is not influenced by any input variable and thus would only have a dependency to the internal variable.

eDA considers this scenario by calculating the dependencies for multiple function calls. If one variable is dependent on a variable from a previous function call, it is considered as a delayed (data or control) dependency. Delayed dependencies are indicated in the results by a suffix of <code>^-N</code>, where N is the number of function calls the dependency is delayed. Internally non-delayed dependencies are modeled as delayed dependencies with N=0. One variable cannot have multiple delayed or non-delayed dependencies to the same variable. Dependencies with a smaller delay are considered stronger than dependencies with a larger delay.
{| class="wikitable"
|+
!Input Code
!Result
|-
|
<syntaxhighlight lang="c">
int in1;
int out1;
static int internal1;

void func(void) {
out1 = internal1;

internal1 = in1;
}
</syntaxhighlight>
|<pre>internal1: in1
out1: internal1 in1^-1
</pre>
|}

=== Local Variables ===
In this example, two local variables are used to store intermediate results. eDA considers the local variables and their dependencies to the global variables. The result shows that the output variable out1 is dependent on in1 and in2. The local variables are not listed in the results as their lifetime ends after the function execution.
{| class="wikitable"
|+
!Input Code
!Result
|-
|
<syntaxhighlight lang="c">
float in1, in2;
float out1;

void func(void) {
float local1;
float local2;

local1 = in1 * in1 + in2 * in2;
local2 = sqrt(local1);

out1 = local2 + 1.0f;
}
</syntaxhighlight>
|<pre>out1: in1 in2
</pre>
|}
=== Ignoring Name Dependencies===
In this example, the local variable local1 is reused to store two different intermediate results. Reusing (global or local) variables is common in C programming and also used by code generators like TargedLink. A name-based dependency analysis would consider the output variable out2 dependent on in1 and in2. However, eDA ignores the name of the variable and considers only the data flow. The result shows that out2 is only dependent on in2.
{| class="wikitable"
|+
!Input Code
!Result
|-
|<syntaxhighlight lang="c">
float in1, in2;
float out1, out2;

void func(void) {
float local1;

local1 = in1 * in1;
out1 = local1;

local1 = sqrt(in2);
out2 = local2;
}
</syntaxhighlight>
|<pre>out1: in1
out2: in2
</pre>
|}

=== Parametrized Dependency Analysis===
In automotive applications, it is common to use the same software across multiple car models with different configurations. eDA supports a parametrized dependency analysis where one or more input variables are considered as constant parameters. Code parts that are deactivated by the constant parameters are not considered during dependency analysis. This is useful to calculate the dependencies only for one active configuration and to reduce the number of dependencies.

eDA follows a two step approach for the parametrized dependency analysis. In the first step, the constant parameters are propagated through the code and inactive code parts are removed. In the second step, the dependency analysis is performed on the transformed code. Even the transformed code is available as intermediate code for transparency reasons. This is useful to understand the results and to verify the correctness of the transformation.

The following example is identical to the conditional example. Only the input variable in1 is considered as a constant parameter (indicated by the <code>static const</code> in the input code). The result shows the intermediate code after the transformation. The if statement is removed and the output variables are assigned the values of the else branch. In contrast to the conditional example, the output variables are not dependent on the input variable in1.
{| class="wikitable"
|+
!Input Code
!Intermediate Code
!Result
|-
|<syntaxhighlight lang="c">
static const int in1 = 0;
int in2;
int out1, out2;

void func(void) {
if (in1) {
out1 = in2;
out2 = in1;
} else {
out1 = 0;
out2 = 0;
}
}
</syntaxhighlight>
|<syntaxhighlight lang="c">
int in2;
int out1, out2;

void func(void) {
out1 = 0;
out2 = 0;
}
</syntaxhighlight>
|<pre>out1: -
out2: -
</pre>
|}

=== AUTOSAR Integration ===
In AUTOSAR, ports are accessed using IRead/IWrite function. By providing dummy implementations of these functions that simple read or write a dummy global variable, the AUTOSAR program is transformed into a program with global variables. This is used as input for the dependency analysis.

=== Undescribed Features ===

* Function calls to known functions
* Function calls to unknown functions
* Optimization for array with const access
* Loops
* Switch case
* Pointer function parameters
* Output
** C debug output
** XML output
** Reachability output
** Dependency path output
* Propagation of tags (e.g. OBD, ASIL-D)
* AUTOSAR integration

== See Also ==

* Official webpage - https://www.emmtrix.com/tools/emmtrix-dependency-analyzer

[[Category:emmtrix Tools]]