Electronic Control Units (ECUs), such as for automotive engine control, execute highly interdependent software units. These software units and their interaction are optimized for single-cores and need to be parallelized for upcoming multi-core processors. In this paper we investigate how to leverage the parallelism of the physical environment for the parallelization of legacy control software. Key for e cient parallelization is the knowledge of the physically required data ow timing which is often more relaxed than the timing of the single-core implementation. As this knowledge is often not documented, a domain expert needs to be involved. We propose an iterative model-based approach that minimizes the evaluation e ort of the domain expert when parallelizing. In our case study, using a real-world automotive engine control software, we show that the presented approach can exploit parallelism while guaranteeing a correct data ow timing.
Future automotive control algorithms become more and more sophisticated due to
increasing comfort, safety, and power-train functionalities. The resulting complex
functionality is implemented in embedded real-time control software with an
increasing demand for computing power. Multi-core processors are the most
promising solution to cope with the computational demand. Though, decades of
ECU software development for single-core processors have left a huge amount of
legacy software, structured in cyclically activated tasks. Using the concept of Logical
Execution Time (LET) [
Our solution approach thus suggests to leverage domain knowledge of experts to identify where a dependency can be relaxed in terms of its timing. This may lead to a behavior which is di erent from the legacy implementation. A domain expert has r1 r2 to evaluate if this behavior is still correct. Though, evaluating all dependencies is unfeasible due to time and cost reasons. In contrast, a small number of dependencies, as depicted in Fig. 1 on the right side, can be evaluated. The main thesis of this paper is that there are dependencies which are more relevant and probable to ease the partitioning challenge and thus more promising candidates for evaluation than others. The main contribution is a model-based work ow to determine these evaluation candidates through a machine-assisted iterative approach. In our case study, we have evaluated a real-world gasoline Engine Management System (EMS), which is one of the most complex control software applications in the automotive domain. Our approach allows to nd a correct and suitable degree of parallelism with reduced evaluation e ort.
The rest of this paper is organized as follows: In the next section we present the background related to the used models in our approach. Section 3 explains our work ow and its algorithms in detail. Experimental results are presented in Section 4. We discuss related work in Section 5 and conclude in Section 6. 2
In this section we introduce the system model and its graph representation used
for our approach. We use Amalthea [
Amalthea is a model and tool platform for automotive embedded-system engineering and provides integration into established industrial development processes. In Amalthea, a software unit is called runnable and a set of communicating runnables provides a desired functionality. A runnable r 2 R is an encapsulated portion of sequential code, i.e., a void-void function. The runnables communicate indirectly via labels. A label d 2 D can be of di erent data type, e.g. bit, array, or characteristic map and is stored in shared memory. Large data types such as a map are typically read-only and only segments are accessed. Each read-write and write-read relation between two runnables via a label is a dependency q 2 Q (R R). A dependency between two runnables ri; rj 2 R is denoted as qi;j and distinct through the corresponding label dk. The unit of scheduling for the underlying operating system is a task ti 2 T that manages the execution of runnables. Runnables are mapped to a task by the function m : R ! T. Let ti be a task, then the order of execution of runnables is de ned as the totally ordered set P(Rti ; ). If ra rb (ra precedes rb), then runnable ra terminates its execution before rb is executed. A task is cyclically activated with a period Pti , has a relative deadline Dti that is typically equal to Pti , and releases an in nite number of jobs Jti;k; k 2 N. Each job Jti;k of task ti is activated at ati;k+1 = ati;k + Pti with ati;0 = 0. The execution time of a task ti is denoted as Iti . It is the sum of the execution time3 of all runnables managed by task ti. A task ti can be split into multiple task partitions ti;k; k 2 N. Nti;k is hereby the ratio of execution time of partition Iti;k to execution time of task Iti .
We represent the Amalthea model as a graph. The runnable graph is a cyclic multigraph GR = (V; E) that describes the communication dependencies between runnables. It consists of nodes V = R and the multiset of edges E = Q. 2.2
For the communication between tasks, we use the concept of Logical Execution
Time (LET) [
Pti
ati;1 (b) Split task ti into ti;1 and ti;2.
t
It represents the timing constraint for the communication between the producer ra and consumer rb when data is produced in job Jti;k for a mapping m, such that m(ra) = ti and m(rb) = tj . A dependency qa;b is considered uncritical if the communication allows additional latencies through LET, i.e., pub(qa;b) = ati;k+1. Otherwise they are considered critical, i.e., pub(qa;b) is instantly. Relaxing the criticality of a dependency is the veri ed transformation from critical to uncritical.
The cluster graph GC is the transformed graph of GR such that all uncritical dependencies are removed. Each subgraph in GC represents a task cluster c 2 C. Task clusters are the graph representation of task partitions. All runnables inside a cluster have critical dependencies and are thus functionally (in respect to timing) dependent on each other. 3
Our expert-in-the-loop work ow determines the criticality of dependencies in which the expert and the machine are in an interactive loop. The input is an Amalthea task with communication based on LET and a parallel target scenario. Initially, all dependencies of this task are critical. During the work ow, the expert is guided toward a parallel target scenario by evaluating one dependency for its criticality on every iteration. One iteration in our work ow consists of ve steps, cf. Fig. 3: 1. Every unevaluated dependency is analyzed according to a number of criteria. 2. The criteria results of each dependency are aggregated. A dependency becomes a candidate if it has a potential impact toward the given parallel target scenario and has a high probability to be uncritical. 3. The analysis proposes the dependency candidate that is most suitable and probable for evaluation to the domain expert. 4. The domain expert evaluates whether the criticality of the dependency candidate can be relaxed. 5. The resulting, potentially relaxed, criticality is re ned in the model.
The parallel scenario is computed via a bin-packing approach on every work ow iteration. A parallel scenario s 2 S is de ned as the execution time ratios of all task partitions Nti;k. E.g. a scenario with two equally sized task partitions is denoted as s = (Nti;1; Nti;2) = (0:5; 0:5). The parallel target scenario st allows a variation Vti of the task partitions to the target. For example, if two equally sized task 1. infer criteria Model 3. propose candidate Domain Expert 4. evaluate candidate automatic manual partitions with a variation of 10 % are allowed, we denote the target scenario as st = ((Nti;1 ; Nti;2 ); Vti ) = ((0:5; 0:5); 10 %). The work ow is nished as soon as the st is reached. The work ow also respects more ne-grained partitions because partitions can always be merged. E.g. the work ow halts if it nds a scenario with (0:45; 0:24; 0:31). In the following, we present steps 1{5 of our work ow. In the rst step of our work ow, the dependencies are quanti ed according to certain criteria which evaluate these properties. There are two types of criteria: 1) An impact criterion indicates the bene t toward the parallel target scenario if the criticality is relaxed. It is the normalized function impact : Q ! [0; 1] 2 R. The bene t is relative to the impact: an impact of ]0; 1] is bene cial, an impact of 0 indicates no bene t. 2) A probability criterion indicates the probability of the criticality. It is the function prob : Q ! [0; 1] 2 R, i.e., if a dependency is likely critical it is in [0; 0:5[ or if it is likely uncritical it is in ]0:5; 1]. If the criterion cannot be decided to either criticality, it is 0:5. We present ve criteria in the following subsections.
Minimum Feedback Arc Set (MFAS). For a correct execution, dependency cycles of the task have to be resolved. Such cycles can be resolved by relaxing the criticality of at least one dependency in the cycle. To reduce the evaluation e ort, it is important to nd the smallest set of dependencies (MFAS) to resolve. As shown in (1), the criterion impactMFAS is 1 for dependencies that are part of this set as they reduce the evaluation e ort.
impactMFAS (qi;j ) =
(1; if qi;j 2 MFAS
0; otherwise
(1)
Strongly Connected Component (SCC). Even if a dependency is not part
of MFAS, it can be a member of a cycle. To nd cycles, i.e., SCCs in our graph we
use the algorithm by K. A. Hawick and H. A. James [
After evaluating the criteria of each dependency, the results are aggregated in this second step. Each dependency is hereby analyzed for candidacy which is represented by a score. The score(qa;b) of a dependency is the product of the total impact times the total probability:
n n score (qa;b) = Y probi(qa;b) X wi impacti(qa;b) (6) i=0 i=0
To evaluate the total impact of a dependency, the impact criteria are weighted.
During the work ow these weights change and thus control the analysis. For
example, in the beginning of the work ow the main objective besides the target
scenario is to resolve cycles. For that purpose, the analysis adjusts the weights wi to
favor the MFAS and SCC criteria. As soon as all cycles are resolved, the two
criteria will yield no further impact. The product of all probability criteria estimates
how likely it is that a dependency is evaluated as uncritical. For example, if a
dependency originally was critical based on the RI criterion, but the DC criterion
yields a probability of 0:8, the dependency is a more probable candidate. Depending
on the score, a criticality is proposed. The score and the dependency create an
evaluation candidate. These candidates are inserted into a prioritized queue. The
evaluation candidate with the highest score is proposed to the domain expert in
step three of our work ow. For the current iteration, the candidate with the highest
score represents the most suitable and probable dependency for an evaluation.
In step four, the domain expert evaluates if the proposed dependency candidate allows
a relaxed timing. The dependency candidate is part of a controller with a certain
functionality. When relaxing the timing of this dependency, the communicated
data is delayed (as shown in Section 2.2). This delay increases the reaction
time of the controller that potentially alters the functionality: Depending on the
controller design, the delay may violate latency or stability requirements, and
other performance criteria. But a complete speci cation of these requirements for
each single controller and their interactions is not available, such that a manual
evaluation by an expert in this domain is mandatory. For the evaluation, our
work ow presents the dependency candidate together with the criteria values to the
expert. The criteria values give hints why this dependency candidate is the most
suitable and probable one among the others. This may in uence how the expert
evaluates the dependency candidate. There are various techniques to evaluate
the execution timing impact on the functionality of the controller such as formal
veri cation or simulation [
We have implemented the presented approach as an Amalthea [
The results in Fig. 4a and 4b show how our approach partitioned the task te. Note that 128 clusters with a size of one runnable are left out for illustration reasons. On average, after 9.4 (min: 8, max: 24) iterations, our approach nds a partitioning that satis es the parallel target scenario. In comparison, when (a) Iteration #0
(b) Iteration #9 dependencies were selected randomly, it took approximately 72 (min: 17, max: 123) iterations with the expert on average to reach the target scenario. Note that one dependency is evaluated by the expert in one iteration. This shows that our approach successfully guides the selection of dependencies for evaluation and signi cantly reduces the number of iterations and thus the amount of manual work for reaching the parallelization goal. 5
Based on the abstraction level of tasks, the problem of partitioning has been
studied in the following contributions. Using the Amalthea platform, Hottger
et al. [
In contrast to the above related approaches that maintain dependencies through synchronization, our approach relaxes the timing of dependencies to increase parallelizability. The relaxed dependencies could then be used as input for the discussed approaches and yield improved results.
In this paper, we have presented an approach to ease the partitioning challenge of control software by relaxing the timing constraints of dependencies. Relaxed timing constraints increase the e ciency of partitioning techniques and reduce synchronization overhead. Our main contribution is the semi-automatic and iterative work ow to nd the most bene cial and probable dependencies for evaluation by a domain expert. Our analysis leverages domain knowledge and thus the parallelism of the physical environment. We have demonstrated our approach by partitioning a heavy task of a real-world Engine Management System (EMS) by selecting and evaluating only 3:6 % of the dependencies through an expert.
As a future work, we plan to include additional criteria such as end-to-end latency constraints over chains of runnables. We also consider a possible propagation of criticality along dependency chains based on static code analysis.