Marcus Mikulcak
email: marcus.mikulcak@tu-berlin.de

Paula Herber

Thomas Göthel

Sabine Glesner

Timed Path Conditions in MATLAB/Simulink

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In the area of safety-critical embedded software, such as in the automotive and aerospace domain, programming errors can lead to disastrous and, if occurring, often fatal accidents. At the same time, the complexity of such systems has increased dramatically over recent years. To cope with the steadily increasing complexity, current design processes rely more and more on models. One of the most widely-used tools for model-based design is MATLAB/Simulink [START_REF]MathWorks: MATLAB/Simulink[END_REF] by MathWorks, which supports the graphical design and simulation of timecontinuous as well as time-discrete systems using block diagrams. Simulink is very well-suited to grasp the structure of a design on high abstraction levels and to visualize its behavior by simulation. However, due to the complexity and the dynamic character of the developed models, the analysis of a given model is a difficult challenge, in particular if timing aspects are considered. At the same time, knowledge about the existence of certain paths and the conditions under which they are executed is highly desirable. In particular, if a Simulink model becomes the main artifact in a model-based design process, the analysis of its properties becomes crucial for the correctness and reliability of the whole development process. With the help of (timed) path conditions, it is possible to identify interference and non-interference between model parts and, thus, to reason about compliance with security policies. Furthermore, (timed) path conditions can be used to compute areas of low dynamic coupling for subsequent model separation. With that, they have the potential to reduce the complexity of Simulink models and thus to improve verifiability and testability. Finally, they provide a basis for generating feasible, efficient test cases for quality assurance.

In this paper, we present an approach for the construction of timed path conditions in Simulink. The main challenge we face is that all dependencies in a given design must be considered. Thereby, dependencies might be indirectly introduced via control flow, or delayed, which introduces dependencies between signals from different time slices. In our approach, we start with a static overapproximation of all potential dependencies on a path between a timed output signal and a timed input signals and collect all control flow conditions. Then, for each path, we compute a set of constraints on all input signals by performing a backward propagation of control flow conditions, which also takes timing dependencies into account. The result of our analysis is a precise description of the timed dependencies between input and output signals, represented by timed path conditions that solely depend on model-wide input variables. We demonstrate the applicability of our approach by computing timed path conditions for a case study containing a shared buffer for public as well as confidential data.

Preliminaries

In this section, we describe the basic concepts and tools employed by our approach.

Path Conditions

In general, path conditions [START_REF] King | Symbolic execution and program testing[END_REF] describe sufficient conditions for paths to be executed. In [START_REF] Hammer | Information Flow Control for Java based on Path Conditions in Dependence Graphs[END_REF][START_REF] Hammer | Static path conditions for Java[END_REF], path conditions are used to capture all paths where information might flow from a source to a target. In contrast to static analyses, which consider all syntactically possible dependencies, path conditions take data and control flow conditions into account. With that, they exclude, for example, information flow which is only possible if disjoint control flow conditions are satisfied. Thus, a path condition based analysis is more precise than classical static analyses.

MATLAB/Simulink

MATLAB/Simulink [START_REF]MathWorks: MATLAB/Simulink[END_REF] is an add-on to the MATLAB IDE by MathWorks that enables graphical modeling and simulation of reactive systems. In its data-flow oriented notation, Simulink employs blocks which are connected using signals.

Additionally, each block and signal is assigned a set of parameters.

Simulation of Simulink models is performed using solvers which compute the output of each block according to its semantics. Variable step solvers aim at automatically finding a simulation step size for each block in the model to achieve a level of precision set by the model developer. Fixed step solvers use a fixed simulation step size at the expense of precision while increasing performance. The former class of solvers is commonly used for hybrid or purely time-continuous systems, while the latter is used for time-discrete models.

Information Flow Analysis

The protection of confidentiality of information inside a software system is a longstanding and increasingly important problem in the areas of general computing as well as embedded systems. Protecting not only the data itself but also the integrity of the functionality that produces and handles data is a goal of software non-interference policies [START_REF] Goguen | Security policies and security models[END_REF]. Such policies, based on the assignment of security levels to data elements, describe rules between which levels information flow is allowed or forbidden [START_REF] Sabelfeld | Language-based information-flow security. Selected Areas in Communications[END_REF]. When aiming at assuring confidentiality, data is prohibited to flow to inappropriate locations, while in the context of integrity, data is prohibited to flow from inappropriate sources. As non-interference refers to the absence of information flow, it ensures both confidentiality and integrity.

Related Work

Path conditions [START_REF] King | Symbolic execution and program testing[END_REF] are heavily used in the area of symbolic execution and automatic test generation. The use of path conditions to increase granularity of information flow analysis has first been proposed in [START_REF] Krinke | Validation of measurement software as an application of slicing and constraint solving[END_REF]. In this work, the authors describe the combination of program slicing and Constraint Logic Programming (CLP) to increase the precision of slicing for C programs, implemented in the VALSOFT Slicing System. They consider purely static slicing as too conservative and propose the extraction of conditions on the edges of the generated Program Dependence Graphs (PDGs). Subsequently, the concatenation of these conditions along paths of interest are analyzed by a constraint solver. However, due to the inherent differences between C and MATLAB/Simulink, their approach cannot directly be transferred to Simulink. For example, their work does not take timing behavior into account. They report that the precision of slicing operations can be considerably raised by the use of path conditions.

In [START_REF] Reicherdt | Slicing MATLAB/Simulink Models[END_REF], the authors present an approach for slicing of Simulink models. Their algorithm identifies model parts that influence the computation of a given block. However, as their approach does not have the characteristics of an Information Flow Analysis (IFA), i. e., does neither consider conditions nor timing along model paths, it only provides a coarse-grained dependency analysis.

In [START_REF] Whalen | Model Checking Information Flow[END_REF], the authors present an adaptation of the concept of path conditions to MATLAB/Simulink. The authors describe the translation of Simulink models into Lustre, a synchronous data-flow programming language [START_REF] Halbwachs | The synchronous data flow programming language lustre[END_REF]. On this basis, they define an IFA notation and calculate path conditions on the translated models. Their approach has been implemented in the Gryphon tool suite and tested using the example shown in Figure 1, which we adapted from their publication. With their approach, they are able to show non-interference between confidential and public data paths using path conditions. However, they assume that the timing dependencies do not influence the information flow. Although they discuss that this assumptions is violated in their own case study, they provide no solution that takes timing dependencies into account. Possible solutions to this problem have been presented in [START_REF] Tripakis | Translating discrete-time Simulink to Lustre[END_REF], [START_REF] Messaoud | Translating Discrete Time Simulink to SIGNAL[END_REF] and [START_REF] Herber | Bit-precise formal verification of discrete-time MATLAB/Simulink Models using SMT solving[END_REF] via further translations of Simulink models into Lustre, SIGNAL and UCLID, respectively. However, as these approaches rely on a translation of models into a target language using different functional and timing semantics, properties of the original systems are lost. For example, the translation to Lustre maps Simulink signals onto mathematical data types, thereby losing the possibility to perform bit-precise analyses of data.

Timed Path Conditions in MATLAB/Simulink

In this section, we present our approach for the computation of timed path condition in MATLAB/Simulink. The main idea is to transfer the concept of path conditions from sequential programming languages like C to the Simulink modeling language. The main challenges are to take both data and control dependencies into account and to cope with timing dependencies. Data dependencies can simply be resolved by following signal lines where each connection corresponds to a direct dependency. Control dependencies are more difficult to compute as they introduce conditional dependencies which are locally resolved. To overcome this problem, we propagate control flow dependencies backwards through the model to the input signals. With that, we can decide whether a certain path actually exists on a very fine-grained level. For both data and control dependencies, we have to take timing dependencies into account. An output might only depend on an input at certain points of time, and sophisticated routing policies might even take advantage of timing delays to make sure that two signals can never interfere. A motivating example for this case is given in the following subsection and used as a running example throughout this paper.

In order to take timing dependencies into account, we introduce the concept of time slices, and incorporate timing dependencies into our approach for the computation of timed path conditions by expressing all dependencies with respect to relative time slices. For the computation of timed path conditions, we use a two-step approach: (1) We (statically) identify all paths in a given Simulink model and collect all path conditions on each path. (2) For each path, we propagate all local control flow conditions backwards through the model in order to compute timed path conditions that solely depend on input variables.

In the following subsections, we first present our running example. Then, we introduce assumptions that define a Simulink subset our approach is currently able to safely analyze. In Section 4.3, we present our notations. Then, we present the computation of path conditions in Section 4.4.

Running Example

To illustrate our approach, we use a simplified version of the shared buffer presented in [START_REF] Whalen | Model Checking Information Flow[END_REF] (see Figure 1). 1 In this model, information of two different security levels (public and confidential ) is fed into a shared buffer, which is implemented as a Mem block. According to the current operation mode, confidential (mode 1) or public (mode 2) information is saved in the buffer and passed to the corresponding output, or the contents of the buffer are erased (mode 0).

The most interesting aspect of this example is that it makes use of a sophisticated routing scheme to avoid security violations. Although confidential and public data share the same memory block as buffer, the routing conditions are intended to ensure that confidential input data can never flow to the public output. To this end, the operation mode defines which input should be routed to the output. The designer did, however, not take the timing behavior of the Mem block into account. When examining the timing of the output signals we discover that if the operation mode switches from confidential to public, the outputs register a spike of the data previously stored in Mem: the confidential contents are sent to the public output. By computing path conditions without taking timing dependencies into account, one would falsely assume that information flow is impossible, as the control flow conditions along the path from confidential input to public output are disjoint. This shows that we can only safely use path conditions for Simulink models if we take timing behavior into account.

Assumptions

In order to apply our approach for the computation of timed path conditions, a given Simulink model has to fulfill the following assumptions: The first two assumptions are acceptable as we target Simulink models from the field of discrete embedded controller design, where time-continuous solvers, loop subsystems, and algebraic loops are rarely used. Assumptions 3 to 5 are imposed due to the current state of our implementation, we are confident that our approach can easily be extended to vector or matrix signals, varying sample times, and other conditional subsystems. Assumption 6 is the most serious restriction regarding typical Simulink models of interest. However, many practical Simulink models only use simple control logics. An extension of our approach to support more complex blocks and subsystems is subject to future work. In order to take timing dependencies into account, we denote the dependency of an output signal to the set of input variables at a certain point of time as (note that t max designates the maximum time slice depth over all paths):

o t n = d(i t 1 , . . . i t-tmax
C p(b 0 , b n ) = n-1 i=1 c(b i , b i-1 , b i+1 ) t-ti
As described above, each atomic path condition applies to the connecting signals between two neighboring blocks and not to the complete set of input and output signals. Intersecting paths through the same routing block therefore create different sets of conditions.

Computation of Timed Path Conditions

In this section, we describe our approach to compute timed path conditions for Simulink models. As mentioned above, we propose a two-step approach where we first identify all paths and collect all path conditions on each path, and then propagate all local control flow conditions backwards through the model in order to compute timed path conditions that solely depend on input variables. In the following, we first describe how we compute the set of all (potential) paths using a backwards depth-first search. Then, we explain how we determine timing dependencies and how we extract (local) path conditions for each path. Finally, we present our approach for the backward propagation of the local path conditions to achieve the final timed path conditions that solely depend on input variables. We illustrate each step using our running example from Section 4.1.

Finding Paths In the first step, we identify all potential paths between the model inports I and outports O. This is a first step to make it possible to analyze confidentiality of data as well as integrity of the model functionality, as data flowing to and from inappropriate sources can be detected (see Section 2.3). In order to find all paths P (i k , o l ), we traverse the model from o l recursively.

Our path detection starts the model traversal with a given outport block o l and implements a depth-first recursive search for all paths i k to o l while marking already visited blocks. This makes it possible to detect cycles along paths throughout the model. After completion of the path detection, the sets P (i, o) i ∈ I, o ∈ O contain all paths from all input and output ports and can be analyzed further.

Running Example

The results of the first step of our algorithm, the sets P (i, o) of our example, are shown in Figure 2. To compute the timing dependencies for a given set of paths, we iterate over each path and analyze it regarding time-dependent model elements and their parameters. If no timed element is found and the path is not part of a feedback loop, the untimed dependency relation

P (i1, o1) = ⟨i1, o1⟩ P (i2, o1) = P (i3, o1) = ∅ P (i1, o2) = ⟨i1, comp_conf, conf_out, o2⟩,
o t l = d(i t k ) is established.
If the path is not part of a feedback loop but time-dependent model elements are encountered along the path during the iteration, a fixed-delay relation can be established and type and parameters of the blocks decide its magnitude. As explained above, we only consider discretely timed models with a fixed simulation step size so far. The behavior of a Delay, UnitDelay and a Mem block is therefore similar. Each time a Mem block is encountered, the magnitude of the fixed delay for the current path is increased by 1. When encountering a Delay block, after confirming the correct sampling time, its DelayLength parameter is read and added to the delay magnitude m of the current path, which yields

o t l = d(i t-m k
). A path that is part of a feedback loop presents an infinite delay relation.

Running Example

The result of the application of this step to our running example is shown in Table 1. As illustrated, information from the data inputs does never arrive at the outputs in the same time slice, as there are no paths between i 2t , i 3t and o 2t , o 3t . Only information from the previous time slice arrives at the outports. This also presents an indicator for the existence of a security violation between the confidential data input and the public data output. At each time t, confidential information from the previous time slice t -1 is still held inside the system and is released in case of a change in mode of operation in the form of a spike. Note that we use the index c to denote indirect information flow through the control signal of routing blocks [START_REF] Denning | Certification of programs for secure information flow[END_REF].

Table 1: Timing relations between ports of our shared buffer example

i t 1 i t-1 1 i t 2 i t-1 2 i t 3 i t-1 3 o t 1 p(i t 1 , o t 1 ) ∅ ∅ ∅ ∅ ∅ o t 2 p(i t 1 , o t 2 ) c p(i t-1 1 , o t 2 ) c ∅ p(i t-1 2 , o t 2 ) ∅ p(i t-1 3 , o t 2 ) o t 3 p(i t 1 , o t 3 ) c p(i t-1 1 , o t 3 ) c ∅ p(i t-1 2 , o t 3 ) ∅ p(i t-1 3 , o t 3 )
Extracting Path Conditions After the identification of timing dependencies, in the next step of our analysis, we extract the conditions necessary for information to flow along paths. These conditions are dependent on the type of the block and its semantics. While it is true for blocks from the functionality and timing categories, routing blocks are analyzed further to extract their behavior. Thus, we iterate over each path in P (I, O) to check for the existence of routing blocks and create a set C p(i t-c k , o t l ) that holds the extracted conditions. If a routing block b r in time slice t-d with inputs s ctrl , s 1 , . . . , s n , output s out and neighboring blocks b l and b o is found, the necessary condition for the current path is extracted and saved for later analysis by the constraint solving tool. The condition is formed depending on the type of the encountered routing block.

Running Example

The goal of our running example, presented in Section 4.1, is to prove whether there is information flow between the confidential inport and the public outport. In the face of multiple routing blocks and a time-dependent model element, we will only consider one path in this example application of our approach: p(i t-1 2 , o t 3 ). After this step, the set of path conditions on this path is:

C p(i t-1 2 , o t 3 ) = s ctrl (pub_out) t ̸ = 0, s ctrl (mode_switch) t-1 == 1
Backward Propagation of Path Conditions As shown above, a single condition is extracted for each routing block on each path. However, as these individual conditions only contain local information about a single control signal, we propagate these control flow signals backwards to the inports of the model. This requires to take the functionalities of each block between the control signal and the inports into account. It elevates the local information about control signals in path conditions to model-wide conditions for information flow, which solely depend on input signals.

To accomplish this, we analyze each control signal separately and iterate over each path from the signal to its drivers while collecting the functionality of each block. We denote the resulting dependencies as:

s ctrl (b r ) = d(i t 1 , . . . , i t-tmax 1 , . . . , i t-tmax j , . . . , i t-tmax j )
For a single block b l , we define its functionality as s o (b l ) = f b l (s i1 , . . . , s in ). When considering a complete path p(b 1 , b n ), the resulting function f p is formed by the composition of each output function along the path according to its structural connections. For example, a linear chain of blocks yields:

f p := f b1 • f b2 • . . . • f bn
Note that for each block type, a specific set of parameters is extracted and its resulting functionality is recorded. We currently support the following block types on control paths: Bias, Gain, Abs, Compare, Add, Product.

While we support untimed and fixed-delay timing relations over control paths, i. e., the existence of multiple time slices along these paths, we presently do not support feedback loops inside control flow paths, as no conclusion can be drawn under these circumstances. We plan to extend our approach with feedback loops and support for additional block types in control flow paths in future work.

Running Example Using the previously created set of path conditions C(i t-1 2 , o t 3 ) as an input, this step of our analysis propagates the local path conditions of the routing blocks backwards and collects the functionality of each block along these paths. The model inports driving the control signals in C can be found in the first row of Table 1. There, untimed dependencies between i 1 , the mode of operation and o t 2 as well as o t 3 leading through the control signals of the routing blocks can be found and the paths between the control signal and the inport i 1 are identified:

p(i t 1 , s ctrl (mode_switch)) = {i t-1 1 } p(i t
1 , s ctrl (pub_out)) = {compare_public, i t 1 } Subsequently, we need to record the functionality of each block along these paths. The first path presents the trivial case that the control signal is directly connected to the inport of the model, we can therefore note its function as:

s ctrl (mode_switch) = f Inport (i t-1 1 ) = i t-1 1
When collecting the functionality of the second path, we encounter a Compare block with a Const value of 2, which we translate into the following function:

s ctrl (pub_out) = f Compare • f Inport (i t 1 ) = i t 1 == 2
With both extracted control flow relations, we have raised the scope of the path conditions from routing block-local to model-wide as path conditions are now presented as directly depending on a set of model inputs instead of local signals.

C p(o t 3 , i t-1 2 ) = (i t 1 == 2) ̸ = 0, i t-1 1 == 1
Translating and Solving Path Conditions We can analyze our timed path conditions, which are expressed by sets of constraints, using a constraint solver.

We chose a format that resembles a set of constraints on signals. To translate this representation into a set of constraints, we first declare all encountered signals as decision variables, then to extract each condition as a constraint on the signals.

Finally, the solver is instructed to find an assignment to the decision variables that does not violate any constraints. If such an assignment can be found, we can conclude that the extracted conditions along the path overlap and there is indeed the possibility for information flow. If the constraint system is unsatisfiable, the path conditions prohibit information flow.

Running Example

The result from translating the path conditions extracted in the previous step into a constraint system is shown in Listing 1.1. Decision variables are declared first, then the two conditions extracted from the routing blocks along the path are shown. When solving the constraint system, we conclude that it is in fact satisfiable due to the timing annotation at the input signal i 1 , allowing for information to flow from confidential to public signals.

1 var int : i_1_t ; 2 var int : i_1_t_sub_1 ; 3 constraint ( i_1_t == 2) != false ; 4 constraint i_1_t_sub_1 == 1; 5 solve satisfy ;

Listing 1.1: The translated constraint system

Evaluation

To evaluate our approach, we have implemented the analysis described above in Java. Our implementation uses an existing Simulink model parser originally developed for the Methods of Model Quality (MeMo) project [START_REF] Hu | MeMo -Methods of Model Quality[END_REF]. We made our computation and implementation accessible via an Eclipse plug-in. While in its current state, our backward propagation algorithm only supports a small subset of simple blocks, we are confident that it still can be applied to a broad range of practical examples as this part of our approach must only be applied to the part of the design that models control signals. As a CLP language, we chose MiniZinc [13] for its simplicity and the possibility to be translated into multiple solver back ends. As a back end, we utilize the Gecode [16] constraint solver.

Table 2 shows the results of our analysis of the running example. With a complexity linear to the size of the model, our algorithm extracts the timed path conditions and passes them to the constraint solver. As can be seen in the table, both the extraction of path conditions as well as the solving of each constraint file by Gecode is performed in under 100 ms.

For the two paths p(i t-1 2 , o t 2 ) and p(i t-1 3 , o t 3 ) connecting the confidential and public inputs with their respective outputs, the satisfiable constraint system shows that their path conditions overlap and information flow is therefore possible. Additionally, their timing relation shows that information fed into the system at time t exits the corresponding output in the next time slice.

The constraint systems created for the two paths p(i t-1 2 , o t 3 ) and t-1 3 , o t 2 ), on which confidential information crosses to the public output and vice versa, are satisfiable and therefore show that although the designer intended to use the operation mode to ensure non-interference, information flow does indeed occur whenever the operation mode is changed. The security policy of non-interference between the confidential and public data flows is therefore violated.

Conclusion

In this paper, we have presented an approach to extract timed path conditions from Simulink models. These conditions can be used to reduce model complexity and as an IFA tool to argue about the existence of paths between arbitrary blocks in a model. We have shown how we find paths between inputs and outputs to the model and how we determine timing dependencies of signals along these paths. Further, we have demonstrated how we extract conditions from routing blocks on paths and how we identify control flow relations between blocks to be able to draw conclusions about the existence of paths using a constraint solving tool. Using the example of a shared buffer for confidential as well as public data, we have demonstrated the usability of our approach in the context of an IFA. Thereby, we have shown how timed path conditions can be used to both detect as well as rule out security policy violations.

To increase the precision of our approach, we are planning to extend its functionality to include more parts of the Simulink design library, such as IndexVector and Selector blocks to support non-scalar signals. Furthermore, we see high potential to increase the width of our approach by supporting Stateflow [START_REF]MathWorks: MATLAB/Simulink[END_REF], an extension to Simulink with functionality and semantics similar to state machines. Stateflow is widely-used to model control logic within Simulink, i.e., to drive the control signals of routing blocks within the model. Finally, we aim at extending our approach to support more Simulink-specific features used in industrial applications, such as bit-precise variable modifications and the TargetLink block set [START_REF]dSpace: TargetLink Embedded Code Generator[END_REF] used in the development of implementation-level Simulink models.

Figure 1 :

 1 Figure 1: A shared buffer for public as well as confidential data

1 .

 1 It uses a time-discrete, fixed-step solver. 2. It does not contain algebraic loops or loop subsystems. 3. Only scalar signals are used. 4. So far, all blocks have to use the same sample time. 1 Our simplified version does not contain the Stateflow controller used to set the operation mode present in the original.

5 .

 5 For conditional execution, we support Enabled and routing blocks so far. 6. Control signals only pass through simple arithmetic blocks without feedback.

4. 3

 3 Notations We use the following notations: B denotes the set of blocks and S the set of signals in a given model. In addition, we use I and O as the sets of incoming and outgoing ports of a model, respectively. To describe paths, we use the set P (b l , b k ) that contains all paths between blocks b l and b k . On a path b l to b k , we denote the condition for information to flow through a block b m as c(b m , b l , b k ). While arithmetic blocks always establish a connection between all input and output signals (c(b i , * , * ) = true), routing blocks and conditional subsystems only establish a connection under certain conditions.

1 ,)

 1 . . . , i t k , . . . i t-tmax k If a path starts at source block b 0 and passes through b 1 , . . . , b n-1 to the target b n , the timed condition for the complete path p(b 0 , b n ) is denoted by:

  ⟨i1, mode_switch, Mem, conf_out, o2⟩ P (i2, o2) = ⟨i2, mode_switch, Mem, conf_out, o2⟩ P (i3, o2) = ⟨i3, conf_out, Mem, mode_switch, o2⟩ P (i1, o3) = ⟨i1, compare_public, pub_out, o3⟩, ⟨i1, mode_switch, Mem, pub_out, o3⟩ P (i2, o3) = ⟨i2, mode_switch, Mem, pub_out, o3⟩ P (i3, o3) = ⟨i3, mode_switch, Mem, pub_out, o3⟩

Figure 2 :

 2 Figure 2: Detected paths through the model

Table 2 :

 2 Evaluation results

	Path	Constraints	Sat	Time Extraction Solver
	p(i t 1 , o t 1 ) ∅		-		-
	p(i t-1 2	, o t 2 ) {i t-1 1	== 1, (i t 1 == 1) ̸ = 0} ✓		38 ms
	p(i t-1 2	, o t 3 ) {i t-1 1	== 1, (i t 1 == 2) ̸ = 0} ✓		29 ms
	p(i t-1 3	, o t 2 ) {i t-1 1	== 2, (i t 1 == 1) ̸ = 0} ✓	73 ms	27 ms
	p(i t-1 3	, o t 3 ) {i t-1 1	== 2, (i t 1 == 2) ̸ = 0} ✓		33 ms

* Funded by the German Federal Ministry of Education and Research as part of the research project CISMo


Vitor V Bandeira
email: vvbandeira@inf.ufrgs.br

Vivianne L Costa
email: vlcosta@ufpr.br

Guilherme Bontorin
email: gbontorin@inf.ufrgs.br

Ricardo A L Reis
email: reis@inf.ufrgs.br

Low Latency FPGA Implementation of Izhikevich-Neuron Model

The Izhikevich's simple model (ISM) for neural activity presents a good compromise between waveform quality and computational cost. FPGAs (Field Programmable Gate Array) are powerful, flexible, and inexpensive digital hardware that can implement such model. In this paper, we present a highly combinational, low latency implementation of ISM for FPGA. In the absence of official benchmark to compare different implementations, we propose two different metrics to compare the technical literature with our implementation. In this benchmark, we can implement a system that, when compared to the literature, has almost 1.5 times the number of digital neurons (DN), and latency more than 56 times smaller. This shows that our implementation is best suited for hybrid network systems and presents a fair performance for only-artificial networks.

Introduction

The human brain has about 10 11 neurons, and each one can have more than 10 4 synaptic connections with others neurons [START_REF] Izhikevich | Neural Excitability, Spiking and Bursting[END_REF]. As the most inspiring and powerful computing machine we know at present, it is normal to try breaking the code and understand how it works. We believe its computer capacity comes from a three level complexity: (a) the number of adaptable cells, the neurons; (b) the capability of configurable connections, the synapses; and (c) the waveform that is at the same time robust against noise and capable of encoding information, the spike or action potential.

In terms of the waveform, the literature presents various spike models, each one with a respective biological plausibility and computational complexity. The Izhikevich's Simple Model (ISM) [START_REF] Izhikevich | Simple model of spiking neurons[END_REF] presents one of the best compromises between waveform quality and computational cost at the moment. It is composed of a system of two ordinary differential equations of the first order that can be easily digitalized. In terms of capability of configuration connections and the number of cells, it is important to find a hardware that can at the same time be powerful, flexible, and inexpensive. FPGAs (Field Programmable Gate Array) seem to fill all these requirements as reprogrammable digital circuits. Some papers describe different implementations of ISM in FPGA [1, 4-6, 10, 11]. They differ from how serial or parallel the computations are implemented and the number of pipeline stages used. Our implementation is highly combinational and present low latency.

No other paper before has proposed any benchmark. To compare our work with others, we propose two different metrics. The first one is neural lattice network. It estimates the maximum number of cells we can simulate in a single hardware.

The second metric we propose is the latency of one neuron. It is the time a variation on the input takes to propagate to the output. This metric has a direct correlation to how parallel an implementation is. Depending on the application, this performance can or cannot be important. Hybrid neural networks, like [START_REF] Bontorin | A real-time closed-loop setup for hybrid neural networks[END_REF], are an example of systems where such a performance is fundamental. These are systems where the whole network is composed of the real-time communication between an artificial and a living part. Low and reliable latency is fundamental to ensure the real-time communication integrity between networks. As biological neurons have latency slower than digital ones, we expect to reuse the hardware, virtualizing a greater number of neurons.

In Section 2, we review the simple model proposed by Izhikevich and adapt its equation for digital computing. Section 3 presents the hardware implementation of the neuron and shows a lattice network for comparison reasons. Section 4 shows the hardware results of the implementation to compare it to current literature. Section 5 concludes on the potential of this work and comments about future projects.

Izhikevich's Simple Model

Equations Model

Ensuring some biological plausibility, the ISM reduces the Hodgkin-Huxley model in two-dimensional system of ordinary differential equations [START_REF] Izhikevich | Simple model of spiking neurons[END_REF]:

dv dt = 0.04v 2 + 5v + 140 -u + I (1)
du dt = a(bv -u) (2)
with the auxiliary after-spike resetting:

v ≥ 30mV =⇒ v ← c u ← u + d ( 3
)
where v is the membrane potential of the neuron and u is the membrane recovery variable, both in millivolts (mV); t is the time in milliseconds (ms); I is the total injected currents in nanoamperes (nA); a, b, c, and d are parameters to set the desired waveform or the neuronal activity. The parameter a describes the time scale of the recovery variable u. The parameter b represents a sensitivity of the recovery variable u to the subthreshold fluctuations of the membrane potential v. The parameter c describes the afterspike reset value of the membrane potential v. The parameter d represents afterspike reset of the recovery variable u. Different choices of the parameters a, b, c, and d result in different intrinsic firing patterns.

Change of Variables

In order to facilitate the model implementation in a digital circuit, it is possible to rewrite Equations (1) to (3) as:

h dv dt = 1 32 v 2 + 3.90625v + 109.375 -u * + I * (4)
h du * dt = a * (b * v -u * ) (5) v ≥ 30mV =⇒ v ← c u * ← u * + d (6)
where h = 0.78125, u * = hu, and I * = hI; the parameters a, b, and d are replaced by a*, b*, and d*, respectively, each one also multiplied by h. This transformation is suggested in [START_REF] Cassidy | Dynamical digital silicon neurons[END_REF] and [START_REF] Ambroise | Biorealistic spiking neural network on fpga[END_REF], but both neglect the factor h.

The new system of differential Equations ( 4) to (6) ensures the same behavior of Equations ( 1) to [START_REF] Burden | Numerical Analysis[END_REF]. We can solve by Euler's Method [START_REF] Burden | Numerical Analysis[END_REF], a numerical method of the first order, which produces accurate results. This approach results on:

v n+1 = v n + ∆t 1 32 v 2 n + 3.90625v n + 109.375 -u * n + I * n = v n + ∆t.kv (7) u * n+1 = u * n + ∆t [a * (b * v n -u * n )] = u * n + ∆t.ku (8)
where ∆t is the time increment of the Euler's Method. Moreover, in Equation ( 7) we also approximate 3.90625v ≈ 4v [START_REF] Cassidy | Dynamical digital silicon neurons[END_REF]. kv and ku are used further in the implementation and they represent the variation for each iteration.

The parameters in Table 1 are adapted from the original publication [START_REF] Izhikevich | Simple model of spiking neurons[END_REF] considering the factor h, and it depends on the type of the simulated neuron. The choice of parameters is beyond the scope of this paper, as it is a current research topic. The input current is set to an appropriated input to reveal a realistic behavior.

In the next section, we show the methodology for ISM implementation on FPGA.

3 Neuron Implementation

One Neuron

For our implementation, we use combinational logic for the most of the circuit. The circuitry is as parallel as possible, optimized for latency rather than the area with no reuse of any adder or multiplier. Figure 1 presents a single neuron, and Figure 2 the computation for the new value of v, u* as well as the activity log. For the calculation of the next v and u*, we opted for two parallel operations, one for the case with a spike and other without a spike and select between them afterward. We use an 18-bit fixed point two's complement representation: 1 sign bit, 9 bits for the integer part and 8 bits for the fractionary part. This representation is better suited for digital implementations than floating point, and 18 bits uses more efficiently the available hardware without compromising the accuracy as presented on [START_REF] Ambroise | Biorealistic spiking neural network on fpga[END_REF]. The initial values of v and u* are, respectively -70 mV and -15.63 mV. The time incremental is ∆t = h = 0.78125 ms (milliseconds). The parameters and injected currents are exhibited in Table 1.

Network for Tests and Metrics

We have chosen a lattice network: one neuron is directly connected to the next, by I [N ] and I [N +1] , Figure 3. Even though this has low biological meaning, it can be used estimate the maximal number of neurons that can be implemented on a single FPGA chip. We use an Altera's DE4 Board (EP4SGX230KF40C2) to estimate the number of cells that we could implement, and measure latency. Figures 4 and5 represent about 200 ms in biological time and about 1.8 microseconds in FPGA with a 250-MHz clock. The maximum and minimum tensions are, respectively, +32 mV and -70 mV. Table 1 contains the parameters used for the implementa-tion as well as the input current. These results were obtained with the SignalTap II, provided in the Quartus II software, and will be presented in the next section. Figure 4 shows the simulation of our Verilog description of lattice network using ModelSim TM . Figure 5 shows the measurement of the lattice network on the FPGA, with only the first and last neuron being presented. The data for Figure 5 was obtained using the SignalTap II tool from Quartus II Software. This tool implements a circuit on the FPGA that acquires data directly on the logic circuits and then send it through a JTAG connection to the computer. The data can be displayed and handled on SignalTap II or exported to other software. Only one neuron activity is shown, but we have tested the activity of the six neurons presented on Table 1.

With a lattice network, we can fit 364 digital neurons (DN) on an FPGA. This is 1.5 times more than previous from the literature, [START_REF] Thomas | Fpga accelerated simulation of biologically plausible spiking neural networks[END_REF], which presented 256 DN (Table 2). Our estimative is from a lattice network, but this number alone is expressive. And it is important to estimate how many realistic DN we can implement in a realistic physical network.

We consider that there is no coherence of network implementations and available data in the literature, since each paper implements a different network. Therefore, we do not compare values for virtual neurons at the network level. Indeed, we have not found any paper comparing it either.

There is much evidence of biological data from experiments indicating that the information in brain structures can be coded, among other ways, in the time interval between spikes [START_REF] Wennberg | Coordinated Activity in the Brain : Measurements and Relevance to Brain Function and Behavior[END_REF]. Because of this we have considered paramount to our implementation to have a high precision on the spike timestamp, which is the instant that the spike occurred. That is achieved with low latency and reliable system.

The latency is the time that the cell takes to provide a valid output from a variation on the input. We have shown that our latency (8 ns) is more than 56 times smaller than the literature, the best comparison being with [START_REF] Thomas | Fpga accelerated simulation of biologically plausible spiking neural networks[END_REF] (453.27 ns), Table 2.

The pipelines presented in the literature do not show a parallel load, causing to have a bigger latency. And also it implies an approximation of the spike timestamp as high as the pipeline extension. We suppose that such an approximation do not interfere with their applications [START_REF] Ambroise | Biorealistic spiking neural network on fpga[END_REF][START_REF] Cassidy | Dynamical digital silicon neurons[END_REF][START_REF] Cheung | A parallel spiking neural network simulator[END_REF][START_REF] Rice | Fpga implementation of izhikevich spiking neural networks for character recognition[END_REF][START_REF] Thomas | Fpga accelerated simulation of biologically plausible spiking neural networks[END_REF], but the same cannot be said to all applications.

Conclusion

In this paper, we presented a highly-combinational low-latency implementation for Izhikevich's Neuron Model in FPGA. This approach is better suited for hybrid network applications as it has the best latency in the literature, Table 2. Some other implementations can be better suited for emulation of networks purely artificial with less precision in spike timestamp, as they use fewer resources than ours.

We could also implement more DN in a single FPGA board than the literature when we consider our lattice network. Although as in many cases with bioinspired circuits, these implementations are very particular, and a fair comparison between two different networks is near impossible.

Future works include: (a) to implement a network with more biological meaning; (b) to reuse logic blocks and to implement a pipeline for some calculations to achieve a better speed without compromising latency; (c) to use precomputed values in auxiliary shared memory to reduce computation time and latency; and (d) to explore the parallelism technique for multiple virtual neurons, increasing the maximum size of a network in a single FPGA chip.

As our application is to study and interface with natural living neural networks, the FPGA implementation is preferable for it has easier configurability, reconfigurability, and test. Other implementations such as artificial networks implemented on a full-custom analog [START_REF] Indiveri | Frontiers in neuromorphic engineering[END_REF], or digital integrated circuits may be interesting to implement the short-term objectives (a) through (d) are achieved. Such long-term implementation can improve power consumption, timing performance, and area occupation at the expense of configurability.

Fig. 1 .

 1 Fig. 1. Implementation of One Neuron

Fig. 2 .

 2 Fig.2. Schematics of one neuron, the operations to compute Equations (4) to[START_REF] Cheung | A parallel spiking neural network simulator[END_REF]. All variables and parameters in this figure already account for the variable change presented in Section 2.

Fig. 3 .

 3 Fig. 3. Schematics of the lattice network used.

Fig. 4 .

 4 Fig. 4. Simulation results of the lattice network used.

Fig. 5 .

 5 Fig. 5. Measurement of the lattice network used.

Table 1

 1

	. PARAMETERS FOR EACH NEUROCOMPUTATIONAL FEATURE
	AND INJECTED CURRENT USED IN THE IMPLEMENTATION
			Neural Behaviour
	Tonic	Phasic	Tonic	Phasic	Mixed Spike-frequency
	spiking spiking bursting bursting	mode	adaptation

Table 2 .

 2 COMPARISON OF OUR IMPLEMENTATION WITH LITERATURE

	Ref	HW Use Neurons FF LUT Digital	Time Performance Clock Pipeline Latency Total Integer Vendor Family Representation FPGA (bits) (MHz) Stages (ns) Decimal
	[5] [4] [1] [10]	32 1 25	28% 44% 50 64% 78% 40 1% 1,5% 84.81 79% 198	0 5 7 23	320 150 94.33 121.21 44 18	-32.12 10.8	Xilinx	Spartan Virtex-4
	[6]	32	32% 36% 110.47	6	63.37	18	9.8
	[11] 256	3.39% 7.04%	307 214	96 147	315.96 32 453.27 64	-	Virtex-5
	This 364	93%	250	0	8	18	10.8	Altera Stratix IV

Acknowledgement

This work is funded by the following agencies: Federal Agency for Support and Evaluation of Higher Education of Brazil (CAPES), the National Council for Technological and Scientific Development (CNPq), and the Foundation for Research of the State of Rio Grande do Sul (FAPERGS). The authors thank the Macnica-DHW Ltda for the FPGAs boards and technical support.


Jan Jatzkowski
email: jan.jatzkowski@c-lab.de

Marcio Kreutz
email: kreutz@dimap.ufrn.br

Achim Rettberg
email: achim.rettberg@iess.org

Hierarchical Multicore-Scheduling for Virtualization of Dependent Real-Time Systems

Keywords: Embedded Systems, Dependent Real-time Systems, Realtime Virtualization, Multicore Scheduling, Hierarchical Scheduling

Hypervisor-based virtualization is a promising technology to concurrently run various embedded real-time applications on a single multicore hardware. It provides spatial as well as temporal separation of different applications allocated to one hardware platform. In this paper, we propose a concept for hierarchical scheduling of dependent real-time software on multicore systems using hypervisor-based virualization. For this purpose, we decompose offline schedules of singlecore systems based on their release times, deadlines, and precedence constraints. Resulting schedule fragments are allocated to time partitions such that task deadlines as well as precedence constraints are met while local scheduling order of tasks is preserved. This concept, e.g., enables consolidation of various dependent singlecore applications on a multicore platform using full virtualization. Finally, we demonstrate functionality of our concept by an automotive use case from literature.

Introduction

Nowadays, there is a raising interest in multicore technology for embedded realtime systems. Using multicore hardware promises not only more computational power but also reduced system size, weight, and power consumptions. However, many embedded applications require sequential interaction between different components. Increasing system performance is not reached by parallelization of dedicated software but rather by running various applications on one multicore platform concurrently [START_REF] Main | Virtualization on multicore for industrial real-time operating systems [from mind to market[END_REF]. Virtualization provides means to separate various applications. Multicore architectures and virtualization are therefore known as symbiotic technologies [START_REF] Kleidermacher | System virtualization in multicore systems[END_REF].

Hypervisor-based Virtualization

In this paper we focus on type-1 hypervisor-based virtualization, i.e. an additional software layer -the hypervisor -is placed between hardware and oper-ating system (OS) respectively application software. As type-1 hypervisor run bare-metal, they must provide, e.g., device drivers either by their own (monolithic) or by means of some special guest system (console-guest). Hypervisor provide virtual machines (VM) that represent duplicates of the real hardware. These VMs allow to run various systems spatial and temporal separated on a single hardware platform. Literature distinguishes full and para-virtualization [START_REF] Kleidermacher | System virtualization in multicore systems[END_REF]. While guest systems running at full virtualization are not aware of the hypervisor, para-virtualized systems are adapted to run in VMs. Consequently, para-virtualization allows information exchange between guest system and hypervisor, but full virtualization does not.

Problem Statement

Temporal isolation is an important property of hypervisor-based virtualization for embedded real-time systems. Current real-time hypervisor ensure temporal isolation of various VMs by some cyclic scheduling on hypervisor-level (cf. Sect. 2.2). These approaches provide each VM a guaranteed share of processing time during a predefined period, but dependencies between VMs remain an open issue.

Dependencies between tasks hosted by the same VM must be solved by its local scheduler. But dependencies between VMs must be solved by hypervisor scheduler. Using para-virtualization, local schedulers could notify the hypervisor when tasks are finished. This may enable solutions based on servers to schedule VMs with precedence constraints. In contrast, full virtualization implies that local and hypervisor scheduler cannot actively exchange information. Hence, apriori knowledge of local schedules and VM-dependencies are required to get an appropriate global scheduling.

Contribution

In this paper, we focus on hierarchical real-time scheduling of dependent VMs to enable full virtualization of singlecore systems deployed to multicore hardware. Here, dedendencies are given by precedence constraints. The challenge is to share execution time of p > 1 cores to m > p VMs such that deadlines as well as precedence constraints are met. Each VM encapsulates a periodic real-time system driven by its separate local singlecore schedule. Time sharing shall be realized by a fixed cyclic scheduling that guarantees holding task deadlines and precedence constraints. We consider task sets with acyclic dependencies, because cyclic task dependencies imply non-deterministic behavior. Nevertheless, resulting VM dependency graph may contain cycles. To meet deadlines as well as precedence constraints of the overall system, hypervisor scheduler has to preempt execution of VMs. For this purpose, first we decompose local schedules and then allocate time partitions of various length to those parts of VM schedules. The result of our approach is an offline multicore schedule for VMs that provides not only sufficient execution time for each VM but also considers precedence constraints.

Related Work

In this paper, we address hierarchical scheduling of periodic tasks with precedence constraints on a multicore platform. We therefore divide related work into approaches related to multicore scheduling and hierarchical scheduling.

Multicore Scheduling

Multicore scheduling approaches are classified as partitioned or global [START_REF] Baruah | Multiprocessor Scheduling for Real-Time Systems[END_REF]. Davis and Burns [START_REF] Davis | A survey of hard real-time scheduling for multiprocessor systems[END_REF] state that i) most published research addresses independent tasks and ii) main advantage of partitioned multicore scheduling is reuse of results from singlecore scheduling theory after allocation of tasks to cores has been achieved. Considering periodic task sets with precedence constraints, partitioned scheduling allows to apply, e.g., adapted Earliest Deadline First (EDF*) presented by Chetto et al. [START_REF] Chetto | Dynamic scheduling of real-time tasks under precedence constraints[END_REF] or Deadline Monotonic (DM) based scheduling proposed by Forget et al. [START_REF] Forget | Scheduling dependent periodic tasks without synchronization mechanisms[END_REF]. Both approaches adapt deadlines to solve dependencies between tasks allocated to a singlecore and thus enable deadline-based scheduling as for independent task sets. But dependencies between tasks allocated to different cores are not considered. For global multicore scheduling, e.g., some scheduling policies from singlecore scheduling were adapted. For independent tasks, global EDF schedules p tasks with earliest absolute deadline at each time, where p is number of cores. Lee [START_REF] Lee | On-line multiprocessor scheduling algorithms for real-time tasks[END_REF] extended global EDF to Earliest Deadline Zero Laxity (EDZL) that was proven to dominate global EDF [START_REF] Baruah | Multiprocessor Scheduling for Real-Time Systems[END_REF]. Cho et al. [START_REF] Cho | An optimal real-time scheduling algorithm for multiprocessors[END_REF] presented Largest Local Remaining Execution time First (LLREF). It is an optimal offline real-time scheduling approach for independent periodic tasks with implicit deadlines (d = T ) and it performs non-work-conserving scheduling, i.e. cores can be idle even in case of ready tasks. Rönngren and Shirazi [START_REF] Rönngren | Static multiprocessor scheduling of periodic real-time tasks with precedence constraints and communication costs[END_REF] proposed static scheduling of periodic tasks with precedence constraints for multiprocessor systems connected by a time division multiple access (TDMA) bus network. They adapt task deadlines -similar to [START_REF] Chetto | Dynamic scheduling of real-time tasks under precedence constraints[END_REF], [START_REF] Forget | Scheduling dependent periodic tasks without synchronization mechanisms[END_REF] -and apply a heuristic that schedules tasks w.r.t. earliest starting time, laxity, etc. In contrast to these approaches, our work aims at global offline scheduling that does not adapt local schedules, i.e. task parameters as well as local execution order keep untouched.

Hierarchical Scheduling

Most approaches for hierarchical scheduling at virtualization focus on independent sub-systems, while our work allows dependencies between those systems. In [START_REF] Groesbrink | A criticality-aware mapping of real-time virtual machines to multi-core processors[END_REF], Grösbrink and Almeida present hierarchical scheduling for hypervisor-based real-time virtualization of mixed-criticality systems. They address independent periodic VMs and apply partitioned hierarchical scheduling, i.e. VMs are allocated as periodic servers to cores and each core schedules its servers according to Rate Monotonic (RM). Masmano et al. [START_REF] Masmano | Xtratum: A hypervisor for safety critical embedded systems[END_REF] present the monolithic hypervisor XtratuM that provides para-virtualization. It schedules VMs -called partitions -globally by a static cyclic schedule and locally by a preemptive fixed prioritybased policy [START_REF] Crespo | Partitioned embedded architecture based on hypervisor: The xtratum approach[END_REF]. Xi et al. [START_REF] Xi | Real-time multicore virtual machine scheduling in xen[END_REF] present the console-guest hypervisor RT-Xen. It enables scheduling VMs as periodic or deferrable servers by EDF or DM priority schemes. Masrur et al. [START_REF] Masrur | Vm-based real-time services for automotive control applications[END_REF] proposed the priority-based scheduling plus simple EDF (PSEDF) to apply XEN hypervisor for mixed-criticality systems in automotive domain. But in contrast to our work, none of these approaches allows precedence constraints between VMs.

System Model

This paper focuses on hierarchical scheduling of periodic dependent real-time systems on a multicore platform. Usually, periodic embedded real-time systems get input from some sensors and compute output to control some acutators. But resources are limited to get input respectively set output via direct I/O access or network interfaces. To take this into account, we consider a periodic task model that allows asynchronous release of tasks:

Γ = {τ i = (C i , T i , D i , O i ) | 1 ≤ i ≤ n}. (1)
Each task τ i ∈ Γ is characterized by its worst case execution time (WCET) C i , period T i , constrained deadline D i ≤ T i , and offset O i . By means of constrained deadlines and offsets, we are able to cover systems where the multicore platform is connected to a time-triggered network. We denote j th instance of task τ i by τ ij and its absolute deadline by d ij . Task dependencies are given by precedence constraints τ i ≺ τ j meaning that τ i must finish before τ j can start execution. This corresponds to implicit communication between tasks, i.e. tasks require input just when they start and provide output when finished. To keep software behavior deterministic, we assume acylic task graphs. Consequently, task dependencies can be described by directed acyclic graphs (DAG). We define the set of source respectively sink nodes as

source = {τ i ∈ Γ | ∃τ j ∈ Γ : τ j ≺ τ i }, (2)
sink = {τ i ∈ Γ | ∃τ j ∈ Γ : τ i ≺ τ j }. (3)
While tasks τ i ∈ source make progress as soon as they are scheduled, tasks with predecessors (τ ∈ Γ \source) can only progress when required input has been delivered. Using hypervisor-based virtualization, task set Γ is mapped to a set of virtual machines (VM)

Υ = {υ k = (γ k , σ k ) | 1 ≤ j ≤ m} (4)
where VM υ k is given by a task set γ k ⊂ Γ and a scheduling σ k . In general, σ k can be an online or offline scheduling. In this paper, however, we assume offline singlecore scheduler running within VMs, i.e. σ k represents a fix order how tasks τ i ∈ γ k are scheduled. We denote worst case start time of task instance τ ij scheduled by σ k with σ s k (τ ij ) and its worst case finishing time with σ f k (τ ij ). The hypervisor scheduler is a fix cyclic schedule, i.e. VMs are scheduled by means of time partitions to keep temporal isolation. Each time partition represents a time interval I h = [a h , a h + l h [ defined by its start time a h and length (duration) l h . A VM υ k mapped to a time partition I h will be scheduled at time a h for l h time units. During this time, VM υ k can progress according to its schedule σ k . The hypervisor schedule finally provides for each core a set of time partitions where each partition I h is associated to a dedicated VM υ k . We note this association by I υ k h .

Hierarchical Scheduling with Precedence Constraints

Hierarchical scheduling comprises scheduling of schedules and thus introduces different levels of scheduling. We consider hierarchical scheduling for hypervisorbased virtualization that implies two levels: Global scheduling of VMs by hypervisor and local scheduling of tasks within each VM. We restrict local schedulers to offline singlecore schedules, i.e. execution order of tasks is fix within each VM. This restriction simplifies handling a-priori knowledge of local schedules that we require to cover full virtualization.

The main idea of our approach is to combine knowledge of local schedulers' task execution order with a-priori knowledge of tasks' WCETs and dependencies to compute worst case time partitions (WCTP) for VMs. That is, we calculate worst case VM execution time required to guarantee that a dedicated task τ has finished (cf. Sect. 4.2). In Section 4.3, we schedule these time partitions, which represent activation slots of the corresponding VMs, on a multicore system. In case of success, assigning execution time to VMs according to the resulting schedule ensures that task dependencies as well as tasks' deadlines are met.

Necessary Condition for Schedulability

To our best knowledge, literature provides no schedulability test that is neccessary as well as sufficient for periodic tasks with precedence constraints on multicore systems. For multicore scheduling, there are also no approaches known that convert precedence constraints to real-time constraints -as proposed by Chetto et al. [START_REF] Chetto | Dynamic scheduling of real-time tasks under precedence constraints[END_REF] for singlecore scheduling. This makes transferring results of multicore scheduling theory from independent to dependent task sets challenging. However, some results from multicore scheduling theory of independent tasks can be transferred to task sets with precedence contraints at least as necessary conditions. For instance, a trivial fact from scheduling theory is that a task set Γ with computation demand higher than computation supply provided by some hardware with p cores is not schedulable. Consequently, for multicore hardware with p identical cores, utilization of feasible task set Γ cannot be higher than available number of cores, i.e.

n i=1 C i T i ≤ p (5)
Although Eq. 5 is just a necessary condition, it allows to exclude at least some non-feasible task sets.

Decomposition of Local Schedules

Here, we consider local schedules that result from offline singlecore scheduling. Precedence constraints of tasks which are mapped to the same VM are solved by the corresponding local scheduler:

∀ τ i , τ j ∈ υ k : τ i ≺ τ j =⇒ σ f k (τ il ) ≤ σ s k (τ jl ) ∀l ∈ N (6)
Hence, two challenges remain to be solved by hypervisor during VM scheduling: it has to schedule VMs such that (i) deadlines of tasks running within VMs are met and (ii) dependencies between tasks hosted by different VMs are taken into account. For this purpose, we decompose local schedules of VMs based on 1. deadlines of tasks that are sink nodes of dependency graphs (τ ∈ sink) 2. release times of tasks that are source nodes of dependency graphs (τ ∈ source) 3. dependencies between tasks that are hosted by different VMs A first step towards enabling hypervisor to keep deadlines of tasks is done by splitting local schedules at worst case finishing time of sink nodes τ ∈ sink. This eases handling of different periods within task set Γ . Since execution order of tasks is static within a local schedule σ, fulfilling an absolute deadline d requires to run each local schedule until all task instances with absolute deadline d are finished. Therefore, we split local schedule σ at worst case finishing time of a sink node that is scheduled by σ last amongst all other sink nodes of equal absolute deadline:

max σ f (τ ij ) | τ i ∈ sink, d ij j ∈ N (7)
Note, that each resulting fragment of a local schedule is associated with the earliest absolute deadline d of all its tasks. Hypervisor must also consider release time of task instances because VMs with offline schedules cannot progress as long as the currently scheduled task is not ready. To avoid that hypervisor schedules VMs that cannot progress because of unrelased tasks, we apply another decomposition step onto local schedules based on release times. We split local schedule σ at the beginning of a source node that is scheduled first amongst all other source nodes of equal release time by σ:

min {σ s (τ ij ) | τ i ∈ source, r ij } j ∈ N (8)
Our last decomposition step is based on precedence constraints of tasks hosted by different VMs. As tasks with precedence constraints are just released when all predecessors have finished execution, we split local schedules based on inter-VM dependencies as follows: if a task τ allocated to VM υ k has predecessors hosted by another VM υ l , l = k, we just split schedule σ k at beginning of τ .

The result of the described decomposition is a totally ordered set Φ k of scheduling fragments ϕ h for each VM υ k . The order within Φ k is such that composing all scheduling fragments ϕ h ∈ Φ k w.r.t. this order results in the original local singlecore schedule σ k . Finally, we compute worst case time partitions (WCTP) based on these scheduling fragments and WCETs. For each local schedule fragment ϕ h , we sum up WCET of task instances covered by this fragment and define a time partition I h of this length. As this time partition is associated with the VM that hosts these task instances, we note:

l υ k h = τij ∈ϕ h C i ∀ϕ h ∈ Φ k . ( 9
)

Multicore Scheduling of Time Partitions

Our approach for hierarchical multicore scheduling is based on time partitions I h that were introduced in Sect. 3. While length of time partitions is set according to the WCTP resulting from decomposition of local schedules (cf. Eq. 9), starting time a h of time partitions as well as a core must be determined by hypervisor scheduler. So, the challenge addressed by our multicore scheduling approach is to allocate time partitions I υ k h to cores C j and set their starting time a υ k h such that all precedence constraints are met and tasks finish before their deadlines even in worst case.

We have to make scheduling decisions each time that a scheduling fragment is released or finished. As we decomposed local schedules based on precedence constraints, finishing one scheduling fragment usually implies that one or more other scheduling fragments were released during this execution. Therefore, we also make scheduling decisions when worst case finishing of a task τ i ∈ γ l with successor task τ j hosted by another VM is passed. However, we just need to consider worst case finishing of the task τ i ∈ γ l that is scheduled by υ l last amongst all other predecessors of τ . Keeping order of local schedules guarantees that all other predecessors hosted by VM υ l are then finished, too.

As multicore decisions are not only based on deadlines but have to consider dependencies as well, we define two sets of scheduling fragments that are updated at each scheduling decision:

R ⊂ m k=1 Φ k , N ⊂ m k=1 Φ k (10)
R covers those scheduling fragments ϕ V M k h that are ready, i.e. predecessors required to execute ϕ V M k h are finished and ϕ V M k h is due according to local schedule σ k . In fact, R is similar to a ready queue known from common task scheduling. Analogous, N covers those scheduling fragments ϕ V M k h that are next to become ready w.r.t. order of local schedule. Both, R and N , contain at most one scheduling fragment ϕ υ k h of a VM υ k . Scheduling decisions are based on the following rules with decreasing priority:

1. Schedule the fragment ϕ h ∈ R with earliest deadline (EDF)

Note: Here, we use deadlines associated to scheduling fragments during first decomposition step (cf. 4.2) 2. Schedule the fragment that has most successor fragments ϕ ∈ N While first scheduling rule aims at keeping deadlines, second rule addresses dependencies between different VMs.

Application Example

We will use an application example to demonstrate how our approach presented in Sect. 4 works. Based on the problem definition given in Sect. 1.2, we apply our approach to a minimal system that consists of p = 2 cores and m = 3 VMs. The task set Γ deployed to VMs is taken from Kandasamy et al. [START_REF] Kandasamy | Dependable communication synthesis for distributed embedded systems[END_REF]. It covers three applications from automotive domain: Adaptive cruise control (ACC), traction control (TC), and electric power steering (EPS). Figure 1 shows the corresponding direct acyclic task dependency graphs. In Table 1, we provide original task parameters of these applications given in [START_REF] Kandasamy | Dependable communication synthesis for distributed embedded systems[END_REF]. In addition, we adapted WCETs of tasks by some reduction. This represents a scenario where singlecore applications are consolidated on a multicore hardware with increased computational power related to original singlecore hardware. Task set Γ is deployed to VMs according to an approach presented by Klobedanz et al.( [START_REF] Klobedanz | Fault-tolerant deployment of real-time software in autosar ecu networks[END_REF], "Algorithm 1: Initial Mapping"). This deployment originally addresses singlecore ECU-networks and thus fits to the indicated scenario of consolidating singlecore systems on a multicore platform. Figure 2 shows the resulting local offline schedules based on original WCETs. These local schedules define execution order of tasks within VMs.

Decomposition of Local Schedules

Now, we use schedule σ 2 to demonstrate decomposition of local schedules. VM υ 2 hosts tasks of two example applications: EPS and TC. Tasks of EPS have deadline D = 1500 while deadline of TC-tasks is D = 3000. Our first decomposition step -splitting based on deadlines -therefore splits schedule σ 2 after finishing of τ 6,1 and associates first fragment with absolute deadline d = 1500 and second fragment with d = 3000.

Next decomposition step -splitting based on release times -is driven by second release of EPS system at host time t = 1500. According to our description in Sect. 4.2, we split σ 2 before beginning of τ 2,2 . Thus, second fragment resulting from first step is splitted again. Note, that both fragments resulting from this step keep associated with absolute deadline d = 3000.

Last decomposition step -splitting based on precedence constraints -requires to consider dependencies to other VMs. In particular, we split σ 2 at the beginning of tasks that require input from other VMs. In case of σ 2 , this results in splits at the beginning of τ 4,1 , τ 20,1 , and τ 22,1 .

Applying these decomposition steps to the other local schedules of our application scenario results in the scheduling fragments depicted in Fig. 3. Rectangles clustering tasks correspond to the results of our decomposition steps: outmost rectangles result from deadline-based decomposition, middle rectangles from splitting based on release times, and innermost rectangles result from splitting based on dependencies.

Next, we compute length of these scheduling fragments using Eq. 9. Due to adaptation of tasks' WCETs, handling of preemptions -e.g., task τ 14,1 in schedule V M schedule 1 -is challenging. Here, we just split WCET to execution parts of τ 14,1 in the same proportion as it was in case of original WCET. Results are summerized in Tab. 2.

ϕ υ 1 1 ϕ υ 1 2 ϕ υ 1 3 ϕ υ 1 4 ϕ υ 2 1 ϕ υ 2 2 ϕ υ 2 3 ϕ υ 2 4 ϕ υ 2 5 ϕ υ 2 6 ϕ υ 2 7 ϕ υ 3 1 ϕ υ 3 2 ϕ υ 3 3 ϕ υ 3 4 l υ k h 300

Multicore Scheduling by Time Partitions

Having local schedules decomposed into fragments, we now can allocate time partitions to dedicated cores of a multicore platform. In this example, we consider m = 3 VMs given by example applications introduced in this Section and p = 2 cores. Table 3 shows for each point in time -when the hypervisor can make scheduling decisions -why scheduling point occurs, what the current host time of hypervisor system is, which scheduling fragments are within sets R and N , and which scheduling fragments are scheduled next on cores C 1 and C 2 . For instance, applying rules defined in Sect. 4.3, hypervisor scheduling makes first decision based on deadlines of scheduling fragments. That is, ϕ υ1 1 and ϕ υ2 1 get higher priority than ϕ υ3 1 . Another interesting circumstance for making scheduling decision is at line 7 where "reason for scheduling" is ϕ υ1

2 . This is the first time, R does not contain scheduling fragments of all VMs because ϕ υ1 3 ∈ N requires input from ϕ υ3 2 that in worst case has not finished yet. Therefore, ϕ υ1 3 ∈ N is not passed to R and thus is not considered by hypervisor. Finally, mapping of scheduling fragments to cores is used to define time partitions I h resulting, e.g., for core C 1 in

I υ1 1 = [0, 540[ (11)

Conclusion

In this paper, we presented an approach for hierarchical scheduling of periodic dependent singelcore real-time systems on a multicore hardware. We introduced a system model that covers tasks with precedence constraints as well as VMs that host subsets of these tasks. To schedule the set of VMs on a multicore hardware with full hypervisor-based virtualization, we first proposed a concept to decompose local singlecore schedules into fragments based on deadlines, release times and inter-VM dependencies. Afterwards, we presented our approach for offline scheduling of these fragments on a multicore platform. Finally, we applied our approach to an automotive use case from literature to demonstrate functionality of the proposed concept. Future work aims at taking overhead induced by virualization as well as communication costs between VMs into account.

Fig. 1 .

 1 Fig. 1. Three application examples from automotive domain [8]: electric power steering (EPS), adaptive cruise control (ACC), and traction control (TC).

  240 125 375 90 175 175 150 160 130 175 465 150 200 175

2 ϕ υ 1 3 , ϕ υ 3 3 ϕ υ 2 5 ϕ υ 3 2 ϕ υ 3 2 880 ϕ υ 1 3 , ϕ υ 2 5 , ϕ υ 3 3 ϕ υ 3 4 ϕ υ 2 5 ϕ υ 3 3 ϕ υ 2 5 1025 ϕ υ 1 3 , ϕ υ 3 3 ϕ υ 3 4 ϕ υ 1 3 ϕ υ 3 3 ϕ υ 3 3 1080 ϕ υ 1 3 , ϕ υ 3 4 ϕ υ 1 3 ϕ υ 3 4 ϕ υ 1 3 1150 ϕ υ 3 4 ϕ υ 3 4ϕ υ 1 4 , ϕ υ 2 6 ϕ υ 2 7 ϕ υ 1 4 ϕ υ 2 6 ϕ υ 2 6 1630 ϕ υ 1 4 , ϕ υ 2 7 ϕ υ 1 4 ϕ υ 2 7 ϕ υ 2 7 1805 ϕ υ 1 4 ϕ υ 1 4 ϕ υ 1 4 1875

 332323533235333133331333342212642127114

Table 1 .

 1 Task parameters (original WCET C O i , adapted WCET Ci, period Ti, and relative deadline Di) of example applications shown in Fig. 1, cf. [8]. 2 τ 4 τ 6 τ 18 τ 19 τ 20 τ 22 τ 2 τ 22 τ 4 τ 6 τ 15 τ 16 τ 17 τ 8 τ 21 τ 10 τ 11 τ 13 τ 23 τ 24 Fig. 2. Local schedules resulting from deployment of example applications to three separate singlecore schedules σi, 1 ≤ i ≤ 3.

			EPS System					ACC System
	Task τi	τ1	τ2	τ3	τ4	τ5	τ6	τ7	τ8	τ9 τ10 τ11 τ12 τ13 τ14
	C O i	150 175 300 250 150 100 300 150 175 300 250 200 150 200
	Ci	75 90 150 125 75 50 150 75 90 150 125 100 75 100
	Ti = Di 1500 1500 1500 1500 1500 1500 3000 3000 3000 3000 3000 3000 3000 3000
					TC System
	Task τi τ15 τ16 τ17 τ18 τ19 τ20 τ21 τ22 τ23 τ24
	C O i	200 200 200 200 150 300 175 400 150 200
	Ci	100 100 100 100 75 150 90 200 75 100
	Ti = Di 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000

τ

Table 2 .

 2 Fig. 3. Scheduling fragments resulting from decomposition of local schedules σi, 1 ≤ i ≤ 3. Worst case time partition length for local scheduling fragments.

	τ 15,1	τ 16,1	τ 17,1	τ 8,1	τ 21,1	τ 10,1	τ 11,1	τ 13,1	τ 23,1	τ 24,1
	τ 2,1	τ 4,1	τ 6,1	τ 18,1	τ 19,1	τ 20,1	τ 22,1	τ 2,2	τ 22,1	τ 4,2	τ 6,2
		τ 3,1	τ 5,1	τ 7,1	τ 9,1	τ 12,1	τ 14,1	τ 1,2	τ 3,2	τ 14,1	τ 5,2

Table 3 .

 3 Offline multicore scheduling of time partitions (scheduling fragments).

	Reason for	Host time	R	N	Core C1 Core C2
	scheduling
		0	ϕ υ 1 1 , ϕ υ 2 1 , ϕ υ 3 1 ϕ υ 1 2 , ϕ υ 2 2 , ϕ υ 3 2	ϕ υ 1 1	ϕ υ 2 1
	σ f 1 (τ1,1)	75	ϕ υ 1 1 , ϕ υ 2 1 , ϕ υ 3 1 ϕ υ 1 2 , ϕ υ 2 2 , ϕ υ 3
		865	ϕ υ 2 5 , ϕ υ 3

Acknowledgment

This work was partly funded by German Ministry of Education and Research (BMBF) through project "it's OWL Intelligente Technische Systeme OstWest-falenLippe" (02PQ1021) and ITEA2 project AMALTHEA4public (01IS14029J).