# Extension of ACETONE C code generator for multi-core architectures

Yanis Aït-Aïssa, Thomas Carle, Sergei Chichin, Benjamin Lesage, Claire Pagetti

## ► To cite this version:

Yanis Aït-Aïssa, Thomas Carle, Sergei Chichin, Benjamin Lesage, Claire Pagetti. Extension of ACE-TONE C code generator for multi-core architectures. 13th European Congress of Embedded Real Time Systems (ERTS), Feb 2026, Toulouse, France. 10.82331/ERTS.2026.55. hal-05513962v2

HAL Id: hal-05513962

https://hal.science/hal-05513962v2

Submitted on 25 Feb 2026

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques 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.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Extension of ACETONE C code generator for multi-core architectures

Yanis Aït-Aïssa¹,², Thomas Carle³, Sergeï Chichin², Benjamin Lesage¹ and Claire Pagetti¹

¹ ONERA, ² Airbus, ³ Université de Toulouse – IRIT – all in Toulouse France

## ABSTRACT

Integrating Deep Neural Networks into safety-critical aeronautical systems remains a significant challenge, as it requires high predictability and adherence to precise certification standards. The ACETONE framework addresses this by generating certifiable C code for mono-core systems. We present an extension to the framework for the generation of predictable, parallel C code on multi-core architectures. By modeling the inference as a DAG scheduling problem and utilizing an optimized Constraint Programming approach, we enable efficient execution on multi-core CPUs without dedicated accelerators. Our solution is validated through both WCET analysis and experimental evaluation.

## 1. INTRODUCTION

The use of Machine Learning in industry has grown steadily in recent years. In the aeronautical sector, it is an appealing way forward for enabling new functionalities such as navigation assistance, runway detection, and trajectory optimization. However, integrating such advanced algorithms in safety-critical systems remains a significant challenge. This has led to the emergence of new development assurance processes, as outlined in the EASA guidance [4] and the yet to be published draft of the ED 324, with publicly available material [6, 10, 11]. In this work, we focus on the implementation and inference of deep neural networks (DNN) on multi-core architectures. Indeed, the aeronautical sector is currently moving from single core to multi-core and is not yet ready to embedded dedicated accelerators [5]. Thus, for a rapid solution, it makes sense to have a multi-core-based execution for small- and medium-sized networks.

### 1.1. Context

The framework ACETONE [3] tackles part of this problem by generating sequential C code from detailed descriptions of offline trained DNNs. The generated code is designed to be easily certifiable for being embedded in aeronautical safety-critical systems. Practically, the code preserves the semantics of the DNN model by 1) coding the operations described in the input's description and 2) assuring that the C output numerical values on data is very close to those computed by the training framework (in the range of the numerical error). The code is also predictable, which means that its worst-case execution time (WCET) can be estimated, and this was shown with the OTAWA [1] tool. However, the framework is limited to run

DNN inference on the same core, which quickly increases the computation time and in turn may breach the time constraints given by the application. Parallelizing the C code on multi-core architectures allows reducing the global inference time, and thus exploiting more time constrained or even larger models. However, the size of the board's memory remains a limiting factor with respect to the model size.

The transition from single-core to multi-core is far from trivial. In a theoretical perspective, parallelizing code on a multi-core platform requires dividing the application into independent computational blocks, each of which is assigned to a core for execution with the goal of minimizing the overall execution time. From an implementation perspective, programming for multi-core processors requires the use of synchronization mechanisms to coordinate the various cores. From ACETONE perspective, all the internal generation processes are optimized to produce sequential code.

### 1.2. Contributions

In this paper, we address both the theoretical and practical aspects of the generation of parallel C code in the field of embedded systems for aeronautics and propose an extension to ACETONE. Our contribution is threefold:

* We formalize the computation of an offline parallel schedule as a DAG scheduling problem. To this end, we define the embedded system, the application model representing the studied neural networks, and the expected schedule.

* To compute (optimal) schedules, we encode the search as a constraint programming problem, similar to Tang *et al.* [15]. Such encoding scales poorly, leading us to propose a much more efficient equivalent problem (by reducing the number of decision variables and improving some of the constraints). We then review efficient heuristics [12].

* We extend ACETONE to generate parallel code. As the experiments are deployed in a bare-metal setting, we integrate within ACETONE both the mapping of programs to cores and adequate synchronization mechanisms.

* We evaluate our predictable extension both by computing the WCET obtained with OTAWA [1] and by measuring the observed WCET for various neural networks.

The outline of the paper is as follows. Section 2 details the problem statement. Section 3 describes the offline DAG scheduling problem and some ways of computing (optimal) solutions. Section 4 presents the comparison of those solutions. Section 5 focuses on the extension of ACETONE. We finally conclude the paper and present some future work in Section 6.

<footnote>Yanis Aït-Aïssa et al. This is an open-access article distributed under the terms of the Creative Commons Attribution 4.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.</footnote>
## 2. PROBLEM STATEMENT

### 2.1. Platform model

The platform consists of a multi-core CPU with a finite number $m$ of identical cores operating under a unified memory architecture (UMA). The homogeneity of the cores ensures that the WCET of a task is independent of the core on which it is executed. As a result, the WCET of a sequential code can be computed on any core, with identical outcomes. The UMA allows each core to access the shared memory at the same speed and ensures that inter-core communication latency does not vary with the source and destination. However, such memory representation induces interference between the cores during concurrent memory access. The precise study of interference is considered out of scope for our study and is represented by a margin added to all computed WCET.

Parallelism is implemented using a shared memory strategy, meaning that each core can read from and write to a common memory space. These operations are not instantaneous and introduce latency. In particular, a source core writes a message to a predetermined memory location, and the destination core reads it once a synchronization mechanism permits.

### 2.2. Application model

An application is defined as a deep neural network (DNN). The framework extension relates to the code generated and not the type of input; the DNN is assumed to be compatible with ACETONE, meaning the network is an off-line pre-trained feed-forward network. In particular, the network is assumed to be either a convolutional neural network (CNN) – such as the LeNet-5 neural network presented in Figure 1 – or simply a multilayer perceptron (MLP), also referred to as a fully connected neural network.

<figure><img src="image_2.png" /><figcaption>Figure 1. LeNet-5 neural network</figcaption></figure>

In this work, we focus on the scheduling and code generation of a given neural network with a fixed architecture. Practically, each layer appearing in the DNN description is translated into a sequential C code. This allows to keep the code generated by ACETONE of each layer untouched and to preserve the good properties required by certification and offered by ACETONE.

If needed, the user can modify the initial neural network beforehand to obtain a more parallel architecture. For example, the LeNet-5 in Figure 1 has a purely sequential architecture and is not adapted for parallelization. It can be, for instance, transformed by splitting the first two layers, as done in [8] and shown in Figure 2, to create two separate parallel branches. Such preliminary off-line modifications to expose high parallelism are left to the user, and our work solely focuses on scheduling the input model without modifying its architecture.

The DNN architecture is modeled as a directed acyclic graph (DAG), where each layer of the network is associated with a node of the graph. A directed graph (DG) is defined by a quadruplet $(V, E, t, w)$, where:

<figure><img src="image_3.png" /><figcaption>Figure 2. Modified LeNet-5 neural network</figcaption></figure>

* $V$ is the set of the graph's nodes. Each node represents a layer from the network.

* $E \subset V \times V$ is the set of the graph's edges. For two distinct nodes $u$ and $v$ from $V$, the edge $e = (u, v) \in E$ if and only if there is an exchange of data from $u$ to $v$. $u$ is then said to be a parent of $v$, and $v$ is a child of $u$.

* $t: V \to \mathbb{R}$ is a function mapping to each node the WCET of the corresponding task on a core.

* $w: E \to \mathbb{R}$ is a function mapping to each edge the latency that would be induced by the transmission of data from the source of the edge to its destination, if both of them are not on the same core.

A DAG is said to be acyclic if and only if there is no succession of nodes linked by edges from a node to itself.

We assume that DAGs have only one sink node denoted subsequently $s$. It is easy to transform any DAG into an equivalent one sink DAG. The black nodes in Figure 3 illustrate an DAG with 9 nodes. Each node is identified by a unique label, while the WCET is indicated by the underlined values on its right. The transmission delay on an edge is indicated by the gray value next to it. The red part illustrates the transformation into a one sink DAG.

<figure><img src="image_4.png" /><figcaption>Figure 3. Example of a DAG. In black the original graph, and in red the new node and edges used to compute a one-sink graph.</figcaption></figure>

### 2.3. Model expression

We assimilate a node from the graph to the corresponding task in the schedule. The scheduling is done in ACETONE before generating the code and abides by the following properties:

1. The scheduling is done statically.

2. The tasks are non-preemptive, i.e. once they have started their execution, they do not stop until completion.

3. A task can be scheduled if and only if all of its predecessors have been entirely scheduled – the task is then said to be ready.
A schedule is a tuple $(Sc_1, ..., Sc_m)$, where each $Sc_i$ represents a sub-schedule for core $i$. A sub-schedule $Sc_i$ is defined as a list of tuples $(v, s)$, where $v \in V$ is a node of the graph and $s \in \mathbb{R}$ denotes the start time of $v$. This list is empty if no nodes are assigned to the corresponding core.

A schedule is said to be valid if the following properties hold:

* Two nodes cannot be executed at the same time on the same core.

* A node does not start before its inputs are available (the parents have been executed, and the communication is over).

* Each node can be duplicated on different cores. Indeed, such duplication can help minimize the makespan by removing the communication delay induced by data transfer between cores. A duplication providing no gain is called redundant and is to be removed.

* Each node must be present at least once in the schedule and at most once by sub-schedule.

The goal is to find valid schedules with the shortest makespan.

### 3. OPTIMAL SCHEDULE SEARCH

The problem was studied and proved to be NP-complete by Garey and Johnson [7]. As such, numerous studies have worked on exact and heuristic searches of the problem.

#### 3.1. State of the art ILP encoding

Tang et al. [15] proposed a constraints representation and used an ILP solver to find optimal solutions. The model is based on four decision variables:

* $s_{v_p}$: the start time of task $v \in V$ on core $p \in \mathbf{P}$.

* $f_{v_p}$: the completion time of task $v \in V$ on core $p \in \mathbf{P}$.

* $x_{v_p}$: a binary variable equal to 1 if node $v \in V$ is scheduled on core $p \in \mathbf{P}$ and is not redundant, and 0 otherwise.

* $d_{a_i, b_j}$: a binary variable equal to 1 if task $a \in V$ scheduled on core $i \in \mathbf{P}$ transfers data to node $b \in V$ scheduled on core $j \in \mathbf{P}$, and 0 otherwise.

The first constraint ensures that each node is scheduled at least once.

$$ \sum_{p \in \mathbf{P}} x_{v_p} \geq 1, \forall v \in V \quad (1) $$

Since the tasks are non-preemptive, the completion time equals the start time plus the WCET of the task.

$$ f_{v_p} = s_{v_p} + t(v) \times x_{v_p}, \forall v \in V, \forall p \in \mathbf{P} \quad (2) $$

When a task is not assigned to a core, its corresponding start time is set to 0.

$$ x_{v_p} = 0 \Rightarrow s_{v_p} = 0, \forall v \in V, \forall p \in \mathbf{P} \quad (3) $$

Thus, by applying 2 and 3, we can deduce that when a node is not assigned to a core, its start time and end time on that core are both equal to zero.

A core can execute at most one task at a given instant. When two tasks are scheduled on the same core, the start time of one

must necessarily be after the completion time of the other.

$$ x_{a_i} = x_{b_i} = 1 \Rightarrow (f_{a_i} \le s_{b_i}) \lor (f_{b_i} \le s_{a_i}), \quad (4) \\ \forall (a, b) \in V \times V \setminus \{a\}, \forall i \in \mathbf{P} $$

For each edge $e = (a, b) \in E$, if a is scheduled on core $i \in \mathbf{P}$ and b on $j \in \mathbf{P}$, the start time of b cannot be earlier than the completion time of a, plus the communication delay needed to transmit data from a to b (if applicable).

$$ d_{a_i, b_j} = 1 \Rightarrow f_{a_i} + (1 - \mathbf{1}_{i,j}) \times w(e) \le s_{b_j}, \quad (5) \\ \forall (a, b) \in E, \forall (i, j) \in \mathbf{P}^2 $$

where $\mathbf{1}_{i,j}$ is the indicator function equal to 1 if $i = j$, and 0 otherwise.

To limit the number of duplications, each node in the schedule must either produce or consume data. Indeed, duplicating tasks is of interest to avoid communicating time. Thus, sink nodes are never duplicated.

$$ \sum_{p \in \mathbf{P}} x_{s_p} = 1 \text{ with } s \text{ the sink node of the graph} \quad (6) $$

In addition, constraint 7 ensures that every source node of a communication sends data to at least one destination. In other words, for a node $a \in V$ on core $i \in \mathbf{P}$, there exists at least one non-zero variable $d_{a_i, b_j}$, with $b \in V$ and $j \in \mathbf{P}$.

$$ x_{a_i} = 1 \Rightarrow \sum_{b \in S(a)} \sum_{j \in \mathbf{P}} d_{a_i, b_j} \geq 1, \forall a \in V, \forall i \in \mathbf{P} \quad (7) $$

Constraint 8 ensures that each scheduled destination node of a communication receives all the required data from exactly one source. In other words, for a node $b \in V$ on core $j \in \mathbf{P}$, only one communication variable $d_{a_i, b_j}$ is nonzero for each of its parent nodes $a \in V$.

$$ x_{b_j} = 1 \Rightarrow \sum_{i \in \mathbf{P}} d_{a_i, b_j} = 1, \forall (a, b) \in E, \forall j \in \mathbf{P} \quad (8) $$

#### 3.2. Improved encoding

Tang's ILP representation can be quite time-consuming. Indeed, the communication variable $d_{a_i, b_j}$ is represented by a 4D tensor and can be complex for the solver to handle. To reduce this complexity, we introduce a new formulation which reworks all the constraints involving $d_{a_i, b_j}$ (constraints 5, 7, and 8), and uses only the other three decision variables. All other constraints remain untouched.

To replace constraints 7 and 8 and thereby limit the number of duplications, an upper bound, imposed by constraint 9, prevents a node from having more instances than child nodes.

$$ \sum_{i \in \mathbf{P}} x_{v_i} \leq \mathrm{card}(S(v)), \forall v \in V \setminus \{s\} \quad (9) $$

where $card(S(v))$ is the number of children of node $v$, and $s$ is the sink node of the graph. This upper bound on the number of duplications comes from the fact that, for each non-sink node of the graph, an assignment in the schedule is useful if and only if it sends data to another node. Moreover, each node
can receive data from only one instance of each parent. Thus, if a node is duplicated more times than it has children, some instances will not communicate with any node.

Constraint 5, which introduces the communication delay in the representation, is transformed into two new constraints: if both nodes of an edge $(a, b) \in E$ are assigned to the same core, then the end time of the source must be less than or equal to the start time of the destination (constraint 10). Otherwise, the start time of the destination must occur after the earliest finish time among all instances of the source, plus the communication latency (constraint 11).

$$x_{u_i} = x_{v_i} = 1 \Rightarrow f_{u_i} \le s_{v_i}, \forall (u, v) \in E, \forall (i, j) \in \mathbf{P} \quad (10)$$

$$(x_{u_i} = 0) \land (x_{v_i} = 1) \Rightarrow \begin{cases} \text{earliest}_{-f_u} + w(e) \le s_{v_i}, \\ \forall e = (u, v) \in E, \forall (i, j) \in \mathbf{P} \end{cases} \quad (11)$$

where $earliest_{-f_u} = \min_{i \in \mathbf{P}} f_{u_i}$ is the earliest end time of an assigned node $u$.

When determining the earliest end time of a node $u$, a conflict may arise with constraint 2: if the node is not assigned to a core $i$, the end time $f_{u_i}$ is set to 0, which is the lowest value it can attain and interferes with the earliest end time of the node. To resolve this issue, the constraint is split into two parts: if the node $v \in V$ is assigned to core $i \in \mathbf{P}$, the end time is equal to the start time plus the node's WCET (constraint 12); otherwise, the end time is set to the theoretical maximum, defined as the sum of all nodes' WCETs (constraint 13).

$$x_{v_i} = 1 \Rightarrow f_{v_i} = s_{v_i} + t(v), \forall v \in V, \forall i \in \mathbf{P} \quad (12)$$

$$x_{v_i} = 0 \Rightarrow f_{v_i} = \sum_{u \in V} t(u), \forall v \in V, \forall i \in \mathbf{P} \quad (13)$$

Such a representation is efficient up to several hundred nodes, which is more than enough to schedule the largest models we can encounter. However, this number can be reached and exceeded when we use finer parallelization. Indeed, the operation behind some layers, such as the convolution layer, can be divided into smaller operations, increasing the number of tasks to be scheduled. Heuristics may become necessary to schedule a finer representation of neural networks.

### 3.3. Scheduling heuristics

A first possible method is to use a list scheduling algorithm. This family of algorithms has been widely studied in the literature under various constraints and is known to offer high performance. Among them, the most effective are the critical path algorithms, which are based on assigning a level to each node—this level determines the order in which nodes are considered during the scheduling phase.

Kruatachue [12] extended these algorithms to a problem similar to ours: new scheduling heuristics applied to a DAG with non-unit tasks and non-zero transmission times. Those heuristics share the same framework: each node is assigned a level equal to the sum of all node execution times alongside the longest valid path from the node to the leaf; then the ready nodes are placed in an ordered list (sorted by level). As long as not all nodes in the DAG are scheduled, the algorithm updates the ready queue (by adding the newly ready tasks to the queue and ordering it by level), selects the node at the front of the queue, finds the core that minimizes the task's start time, and then assigns it accordingly.

In the first heuristic, Insertion Scheduling Heuristic (ISH), each node is assigned to the core that minimizes the task's start time. An insertion step then places the node on the selected core. If there is an idle period on the core between the previously scheduled task and the current one, the step checks the ready queue and attempts to schedule a node with a lower level in this idle time, while preserving the current task's start time.

Figure 4 illustrates this algorithm when trying to schedule the graph from Figure 3 on two cores. When scheduling node 7, the earliest start time possible is at time 6, due to the communication delay with node 5. This delay creates an idle time of the core — shown in gray in the figure — between times 5 and 6, as shown by the rightmost Gantt chart. This idle time, in turn, triggers an insertion step. Two nodes, 3 and 2, are in the ready queue. Node 3 is parsed first, but the idle time is shorter than its WCET, the second node is considered. Node 2's WCET is short enough, and since it has no communication delay (its only parent, node 1, is on the same core), it fits in this idle time and is inserted into the gap, as shown in the leftmost Gantt chart in Figure 4.

<figure><img src="image_5.png" /><figcaption>Figure 4. Scheduling of the node 7 using ISH. A "*" means that the node is not yet scheduled, a gray background is a delay induced by the communication between cores and a red background means the node has been scheduled during the insertion step.</figcaption></figure>

In the second heuristic, Duplication Scheduling Heuristic (DSH), most of the complexity lies in the first part. Instead of directly using the start time of a task on the core, the heuristic attempts to optimize that start time. Specifically, if idle time occurs when scheduling a task — most often due to a transmission delay — the function tries to duplicate the task's parent(s) on that core and checks whether the idle time is reduced. If not, it proceeds to duplicate the parents of those parents, and so on, until either no more predecessor(s) remain to duplicate, in which case the process is abandoned, or the original task's start time is improved, in which case a list of nodes to duplicate on the core is constructed. The second step is similar to that of the previous heuristic, with the additional action of scheduling the duplicated nodes on the appropriate core.

An example of this process is shown in Figure 5. During the scheduling of node 5 on P2, idle time occurs due to commu-
nication from node 1 on P1, as shown in the rightmost chart of the figure. To reduce it, a copy of node 5's parent is placed on P2. This duplication, as illustrated in the leftmost chart, reduces both the delay and the task's start time.

<figure><img src="image_6.png" /><figcaption>Figure 5. Scheduling of the node 5 using DSH. A "*" means that the node is not yet scheduled and a gray background is a delay induced by the communication between cores.</figcaption></figure>

### 3.4. Exploring the solution space

Another approach, proposed by Chou and Chung [2], explores the solution space directly using an algorithm tailored for scheduling. This method utilizes two relations between nodes in a graph $(V, E, t, w)$ to prune the search space:

* **Dominance ($u \mathcal{D} v$):** if $P(v) \supseteq P(u)$ and $S(u) \supseteq S(v)$.

* **Equivalence ($u \mathcal{E} v$):** if $P(v) = P(u)$ and $S(u) = S(v)$.

Similar to the pruning mechanisms in ILP solvers, these relations allow the algorithm to discard sub-optimal branches in a solution tree. Each S-node in this tree represents a schedule state containing at most *m* tasks (see Figure 6). Chou and Chung proved that if an S-node dominates or is equivalent to another, the latter can be pruned without losing optimality. The optimal schedule is then identified by finding the shortest path from the root to the leaves of the pruned tree.

<figure><img src="image_7.png" /><figcaption>Figure 6. Partial solution tree for scheduling the graph in Figure 3 on two cores</figcaption></figure>

## 4. EVALUATION OF THE OFFLINE SCHEDULES

We focus on the ILP representation and the scheduling heuristics. We use several sets of randomly generated DAGs and evaluate the methods on two main metrics: the speedup and the average computation time.

### 4.1. Setup

**Applications.** The evaluation uses three sets of randomly generated DAGs containing 20, 50, and 100 nodes, respectively.

Each node is assigned a Worst-Case Execution Time and each edge a communication weight, both uniformly sampled from [1, 10].

The generation follows a three-step process: (1) node instatement with unique indices; (2) edge creation by connecting lower-indexed nodes to higher-indexed ones to ensure acyclicity; and (3) a verification step to ensure a single sink node, as detailed in Section 2.2.

The connectivity of these graphs is defined by their density, representing the ratio of actual edges $|E|$ to the maximum possible edges in a DAG:

$$ \text{density} = \frac{|E|}{|V|(|V| - 1)/2} \quad (14) $$

All test sets were generated with a density of 10%, representing a moderately connected network.

**Metrics.** The performance is evaluated using speedup and average computation time. Speedup is defined as the ratio between the single-core and multi-core makespans:

$$ \text{speedup} = \frac{\text{makespan single-core}}{\text{makespan multi-core}} \quad (15) $$

where *C* represents the makespan. The average computation time is calculated as the arithmetic mean of the durations required by a method to reach a solution across all test cases.

### 4.2. ISH and DSH evaluation

This part evaluates the influence of the number of cores on both scheduling heuristics presented in subsection 3.3. Figure 7a (respectively 7b) represents the speedup provided by the ISH (respectively DSH) algorithm for a number of cores ranging from 2 to 20.

**Observation 1: maximal parallelism** In both figures, the speedup grows until it reaches a plateau. The plateau is induced by the maximal parallelization value equal to the maximum number of parallel branches. For example, in Figure 3, this value would be 5. Having more cores than this number will not provide any additional benefits for the speedup.

**Observation 2: highest speedup** Under similar conditions, the DSH algorithm provides a higher or equal speedup than the ISH. This behavior has been observed in ([15] and [12]): DSH is supposed to be slower but closer to the optimal solution, while ISH is faster but can only reach a near-optimal solution.

Finally, we can see that the higher the number of nodes, the greater the speedup; thus, the use of parallelization becomes more advantageous for the corresponding application.

**Observation 3: faster computation** The computation time results vary significantly between the two heuristics. As shown in Figures 7c and 7d, ISH is consistently faster and more stable, maintaining a steady order of magnitude for a given node count. Conversely, DSH execution time increases by one to two orders of magnitude as the number of cores grows, reaching nearly two minutes per graph. While still practical, DSH is significantly outperformed by ISH in terms of computational efficiency.

**Observation 4: memory footprint** By definition, DSH can
<figure><img src="image_8.png" /><figcaption>(a) Speedup ISH results</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>(b) Speedup DSH results</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(c) Computation time ISH results</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>(d) Computation time DSH results</figcaption></figure>

<caption>Figure 7. Metrics as a function of the number of cores</caption>

duplicate nodes, creating an overhead in the memory footprint.

## 4.3. ILP evaluation

To evaluate the ILP representation, we implemented the constraints using IBM's Optimization Programming Language (OPL) [16]. The problem is then solved using IBM's ILOG CP Optimizer [13], run on a 24-core Intel(R) Xeon(R) CPU E5-2420 0 @ 1.90 GHz with 12 GB of RAM. To accelerate the tests, a timeout of 1 hour is set for each run. When the solver reaches this timeout, it returns the best solution found during the allocated time but can not assure that it is the optimal one.

The results are presented in Figure 8, with the speedup evaluation on the right and the computation time on the left for a number of cores ranging from 2 to 20. Solely the datasets of size 20 and 50 are represented here, as the timeout was too tight for the solver to find coherent solutions with larger graphs.

**Observation 1: comparison between Tang et al. [15] and our optimized encoding** When testing Tang's representation under similar conditions, the solver was not able to find solutions before the timeout, while ours returns at least one solution in all tested configurations. When returned, the schedule produced by our method is at least as good as the one returned

by Tang's. Both representations yield similar performance in terms of speedup; but when the timeout is reached, ours allows the solver to explore the solution space further, and thus to produce better results in the same amount of time.

**Observation 2: optimal solution** As for the previous heuristics, the speedup reaches a plateau after a few cores. For both datasets, the plateau is at a similar value than the one of DSH. The plateau is reached around 5 cores, while DSH needed 7 cores. This confirms that DSH only returns a near-optimal solution.

**Observation 3: slower computation** The computation time quickly increases with the size of the evaluated graph. For 50-node graphs, the average computation time never goes below 54 minutes and often reaches the timeout.

For a higher number of cores, both DSH and the ILP solver have similar speedup performance, with the heuristic being significantly faster (up to 10 times in our evaluations). However, for a lower number of cores, the solver outperforms the heuristic by finding optimal solutions for our problem, albeit still with a longer computation time. It is important to note that the graphs evaluated here are quite small compared to some models found in the industry, where the number of nodes easily exceeds 50 for modern networks. To limit the explosion
<figure><img src="image_12.png" /><figcaption>Figure 8. Metrics evaluations of the modified ILP representation using OPL solver as a function of the number of core</figcaption></figure>

of computation time, a hybrid solution should be considered, where a call to DSH gives a first schedule, which is then used as a starting point by the solver to find an optimal solution.

# 5. IMPLEMENTATION IN ACETONE

## 5.1. Current state of the software

The ACETONE workflow is summarized in Figure 9. Starting from a model description (NNet, ONNX, H5, or JSON), a parser extracts the network layers and creates the corresponding objects in the ACETONE internal representation, capturing for each layer the underlying operation and its relation with other layers (producers of its operands, or consumers of its output). The scheduler arranges them topologically; the scheduler ensures each layer is visited after its parents have produced their output. This ordered list is passed to the code generator, which traverses it and produces the corresponding C implementation.

<figure><img src="image_13.png" /><figcaption>Figure 9. ACETONE’s workflow</figcaption></figure>

Each layer in ACETONE is represented by a *Layer* Python object associated with an implementation in C (a default template is provided to generate the implementation, with the possibility for the user to implement their own). These implementations are then printed sequentially in an *inference function*, following the ordered list, with glue code passing the output of a layer as inputs of its children. As an example, Algorithm 1 provides an extract of the code generated for the LeNet-5 described in Figure 2. The external input is loaded in a local variable using the *Input* layer at lines 3-4. From line 6 to 30, each layer is executed sequentially, the result being stored in statically allocated output variables, which are then referenced as inputs in the subsequent layer. Finally, an *Output* layer, lines 32-33, retrieves the value computed from the last layer

and puts it in the global output variable.

<table><caption>**Algorithm 1** Inference function of LeNet5 Figure 2</caption><thead><tr><th></th><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>Function: INFERENCE(float** inputs, float** outputs)</td><td></td></tr><tr><td>2</td><td>/* Input layer</td><td>*/</td></tr><tr><td>3</td><td>for int i=0; i&lt;nb_input_elements; ++i do</td><td></td></tr><tr><td>4</td><td>next layer in[i] = inputs[i];</td><td></td></tr><tr><td>5</td><td>/* Split layer</td><td>*/</td></tr><tr><td>6</td><td>layer out 1, layer out 2 = split(next layer in);</td><td></td></tr><tr><td>7</td><td>for int i=0; i&lt;nb layer elements; ++i do</td><td></td></tr><tr><td>8</td><td>next layer in top branch[i] = layer out 1[i];</td><td></td></tr><tr><td>9</td><td>next layer in bot branch[i] = layer out 2[i];</td><td></td></tr><tr><td>10</td><td>/* Top branch Conv1 layer</td><td>*/</td></tr><tr><td>11</td><td>layer out top = conv(next layer in top branch);</td><td></td></tr><tr><td>12</td><td>for int i=0; i&lt;nb layer elements; ++i do</td><td></td></tr><tr><td>13</td><td>next layer in top branch[i] = layer out top[i];</td><td></td></tr><tr><td>14</td><td>/* Bottom branch Conv1 layer</td><td>*/</td></tr><tr><td>15</td><td>layer out bot = conv(next layer in bot branch);</td><td></td></tr><tr><td>16</td><td>for int i=0; i&lt;nb layer elements; ++i do</td><td></td></tr><tr><td>17</td><td>next layer in bot branch[i] = layer out bot[i];</td><td></td></tr><tr><td>18</td><td>/* Concat layer</td><td>*/</td></tr><tr><td>19</td><td>layer out = concat( next layer in top branch, next layer in bot branch, )</td><td></td></tr><tr><td>20</td><td>for int i=0; i&lt;nb input elements; ++i do</td><td></td></tr><tr><td>21</td><td>next layer in[i] = layer out[i];</td><td></td></tr><tr><td>22</td><td>/* Dense3 layer</td><td>*/</td></tr><tr><td>23</td><td>layer out = dense(next layer in);</td><td></td></tr><tr><td>24</td><td>/* Output layer</td><td>*/</td></tr><tr><td>25</td><td>for int i=0; i&lt;nb layer elements; ++i do</td><td></td></tr><tr><td>26</td><td>next layer in[i] = layer out[i];</td><td></td></tr><tr><td>27</td><td>/* Dense3 layer</td><td>*/</td></tr><tr><td>28</td><td>layer out = dense(next layer in);</td><td></td></tr><tr><td>29</td><td>/* Output layer</td><td>*/</td></tr><tr><td>30</td><td>for int i=0; i&lt;nb layer elements; ++i do</td><td></td></tr><tr><td>31</td><td>outputs[i] = layer out[i];</td><td></td></tr></tbody></table>

## 5.2. Synchronization mechanisms

The communication between nodes executed on different cores must ensure precedence between the production of an output and its consumption is respected. The communication starts after the end of the producing layer and ends before the start of the consumer ones. Since we consider bare-metal setting, we implement the synchronization using the specificity of our
<figure><img src="image_14.png" /></figure>

independent branches.

<figure><img src="image_15.png" /><figcaption>Figure 10. Example of a Googlenet architecture</figcaption></figure>

We estimated the WCET of each layer and compiled the results in Table 1. The reshape operation impacts only the dimensions of the input without changing the order of its elements. In the generated code, each tensor is encoded with a 1D array and reshaping a 1D tensor does not modify anything, leading to a zero WCET.

Using Table 1, the network is scheduled on four cores by the DSH heuristic as shown in Figure 11. Each communication, highlighted in red in the figure, is named using the following norm: *source destination identifier*. For example, the communication 2_0_b is the data transfer named b going from core 2 to core 0.

To handle those communications, operators have been added to the program and need to be taken into account. We estimated the WCET of their data handling part and compiled it in Table 2. *Writing* and *Reading* operators having similar code,

<table><caption>Table 1. WCET bounds produced by OTAWA for each individual layer.</caption><thead><tr><th>Layer Name</th><th>WCET [cycles]</th></tr></thead><tbody><tr><td>Input Layer</td><td>5.27 × 10<sup>6</sup></td></tr><tr><td>conv_1</td><td>8.16 × 10<sup>9</sup></td></tr><tr><td>maxpool_1</td><td>1.22 × 10<sup>8</sup></td></tr><tr><td>conv_2</td><td>1.59 × 10<sup>10</sup></td></tr><tr><td>maxpool_2</td><td>2.71 × 10<sup>7</sup></td></tr><tr><td>inception_1/conv_a</td><td>4.57 × 10<sup>8</sup></td></tr><tr><td>inception_1/conv_b1</td><td>2.86 × 10<sup>8</sup></td></tr><tr><td>inception_1/conv_b2</td><td>7.92 × 10<sup>8</sup></td></tr><tr><td>inception_1/conv_c1</td><td>5.72 × 10<sup>7</sup></td></tr><tr><td>inception_1/conv_c2</td><td>1.63 × 10<sup>8</sup></td></tr><tr><td>inception_1/maxpool</td><td>2.49 × 10<sup>7</sup></td></tr><tr><td>inception_1/conv_d</td><td>2.29 × 10<sup>8</sup></td></tr><tr><td>inception_1/concat</td><td>6.06 × 10<sup>6</sup></td></tr><tr><td>inception_2/conv_a</td><td>6.86 × 10<sup>8</sup></td></tr><tr><td>inception_2/conv_b1</td><td>3.43 × 10<sup>8</sup></td></tr><tr><td>inception_2/conv_b2</td><td>1.14 × 10<sup>9</sup></td></tr><tr><td>inception_2/conv_c1</td><td>8.58 × 10<sup>7</sup></td></tr><tr><td>inception_2/conv_c2</td><td>2.53 × 10<sup>8</sup></td></tr><tr><td>inception_2/maxpool</td><td>2.49 × 10<sup>7</sup></td></tr><tr><td>inception_2/conv_d</td><td>2.29 × 10<sup>8</sup></td></tr><tr><td>inception_2/concat</td><td>7.49 × 10<sup>6</sup></td></tr><tr><td>avgpool</td><td>2.51 × 10<sup>6</sup></td></tr><tr><td>reshape</td><td>0</td></tr><tr><td>gemm</td><td>2.67 × 10<sup>7</sup></td></tr><tr><td>Output Layer</td><td>3.51 × 10<sup>4</sup></td></tr><tr><td>Total Sum</td><td>2.90 × 10<sup>10</sup></td></tr></tbody></table>

their WCET is the same at each end of a communication.

<table><caption>Table 2. WCET bounds produced by OTAWA for the synchronization layers (Y denotes any core and Z denotes any name).</caption><thead><tr><th>Communication Name</th><th>WCET [cycles]</th></tr></thead><tbody><tr><td>2_0_b</td><td>3.58 × 10<sup>5</sup></td></tr><tr><td>0_1_a</td><td>2.98 × 10<sup>5</sup></td></tr><tr><td>1_Y_a</td><td>2.38 × 10<sup>5</sup></td></tr><tr><td>0_2_a, 0_3_a</td><td>1.49 × 10<sup>5</sup></td></tr><tr><td>1_0_b, 2_Y_a, 3_Y_Z</td><td>1.19 × 10<sup>5</sup></td></tr></tbody></table>

The global WCET is constructed layer-by-layer using Table 1, synchronizing cores at each barrier by adopting the maximum accumulated WCET. The parallelized model achieves 2.68 × 10¹⁰ cycles, an 8% gain over the sequential 2.90 × 10¹⁰ cycles. This modest overall speedup is due to the large contributions of sequential layers conv_1 and conv_2 to the WCET. However, the parallelizable segment (maxpool_2 to inception_2/concat) shows a 46% gain, reducing execution from 4.81 × 10⁹ to 2.60 × 10⁹ cycles.

## 5.5. Evaluation on the target

The generated code is then run on a Texas Instruments Keystone II SoC [9], which is composed of a cluster of four ARM Cortex-A15 cores implementing the ARMv7 architecture. We evaluated the number of cycles taken by each layer's implementation to execute in both sequential and parallelized configurations, and compiled the results in Table 3. When several instances of the same layer exist on different cores, only the highest computation time is represented.

**Observation 1: Multi-core interference** For almost all lay-
<table><caption>Figure 11. Googlenet scheduling on four cores</caption><thead><tr><th>P0</th><th>P1</th><th>P2</th><th>P3</th></tr></thead><tbody><tr><td>Input Layer</td><td>Input Layer</td><td>Input Layer</td><td>Input Layer</td></tr><tr><td>conv_1</td><td>conv_1</td><td>conv_1</td><td>conv_1</td></tr><tr><td>maxpool_1</td><td>maxpool_1</td><td>maxpool_1</td><td>maxpool_1</td></tr><tr><td>conv_2</td><td>conv_2</td><td>conv_2</td><td>conv_2</td></tr><tr><td>maxpool_2</td><td>maxpool_2</td><td>maxpool_2</td><td>maxpool_2</td></tr><tr><td>inception_1/conv_b1</td><td>inception_1/conv_a</td><td>inception_1/maxpool</td><td>inception_1/conv_c1</td></tr><tr><td>Write 0_3_a</td><td>Write 1_3_a</td><td>inception_1/conv_d</td><td>inception_1/conv_c2</td></tr><tr><td>Write 0_2_a</td><td>Write 1_2_a</td><td>Write 2_3_a</td><td>Write 3_2_a</td></tr><tr><td>inception_1/conv_b2</td><td>Write 1_0_a</td><td>Write 2_1_a</td><td>Write 3_1_a</td></tr><tr><td>Write 0_1_a</td><td></td><td>Write 2_0_a</td><td>Write 3_0_a</td></tr><tr><td></td><td></td><td>Read 0_2_a</td><td>Read 0_3_a</td></tr><tr><td>Read 1_0_a</td><td>Read 0_1_a</td><td>inception_1/conv_b2</td><td>inception_1/conv_b2</td></tr><tr><td>Read 2_0_a</td><td>Read 3_1_a</td><td>Read 1_2_a</td><td>Read 1_3_a</td></tr><tr><td>Read 3_0_a</td><td>Read 2_1_a</td><td>Read 3_2_a</td><td>Read 2_3_a</td></tr><tr><td>inception_1/concat</td><td>inception_1/concat</td><td>inception_1/concat</td><td>inception_1/concat</td></tr><tr><td>inception_2/conv_b1</td><td>inception_2/maxpool</td><td>inception_2/conv_a</td><td>inception_2/conv_c1</td></tr><tr><td>inception_2/conv_b2</td><td>inception_2/conv_d</td><td>Write 2_0_b</td><td>inception_2/conv_c2</td></tr><tr><td>Read 2_0_b</td><td>Write 1_0_b</td><td></td><td>Write 3_0_b</td></tr><tr><td>Read 3_0_b</td><td></td><td></td><td></td></tr><tr><td>Read 1_0_b</td><td></td><td></td><td></td></tr><tr><td>inception_2/concat</td><td></td><td></td><td></td></tr><tr><td>avgpool</td><td></td><td></td><td></td></tr><tr><td>gemm</td><td></td><td></td><td></td></tr><tr><td>Ouput Layer</td><td></td><td></td><td></td></tr></tbody></table>

ers, the same order of magnitude for the number of cycles is found in both cases. The only exceptions are the Input layer, where the multiple cores heavily interfere with each other, and inception_2/concat. The measured WCET for the latter one is high, but this only occurred in one measure among the ten, with all the other ones being around 5.00e+5 cycles.

**Observation 2: Computation time distribution** We observe a similar distribution of computation time as with the estimated WCET, with conv_2 being the most demanding operation, closely followed by conv_1.

**Observation 3: Parallelism gain** We achieved a 8% gain in acceleration, which corresponds to the theoretical gain found in Section 5.4. When focusing only on the highly parallelizable part of the model—from the beginning of the maxpool_2 layer to the end of inception_2/concat—we observe a gain of 31% (2.72 × 10⁸ cycles in sequential execution versus 1.86 × 10⁸ cycles in the parallel code). This difference can be explained by the check before the *Writing* operation, which ensures that the data has been read before it is overwritten; this postpones the operation and increases the delay.

## 6. CONCLUSION

In this work, we have defined the scope of our problem and explored solutions from the literature to extend ACETONE in order to generate parallel code and fully exploit the multi-core architecture of our systems. After reviewing the state of the art on DAG scheduling, we identified several resolution methods, conducted a study on the scalability of the selected heuristics, and compared their output schedules using normalized metrics.

We also focused on extending ACETONE by creating new templates that allow the use of synchronization mechanisms and the repartition of tasks across several cores. These mechanisms are target-dependent, as they rely on specific interrupts that, when addressed to a given core, do not impact any other core, and on busy waiting by setting binary flags in shared memory and having the core stop until these flags are in the

<table><caption>Table 3. Measured WCET [cycles] for the different layers in both single-core and multi-core contexts.</caption><thead><tr><th>Layer name</th><th>Single-core</th><th>Multi-core</th></tr></thead><tbody><tr><td>Input Layer</td><td>9.75 × 10<sup>5</sup></td><td>3.34 × 10<sup>6</sup></td></tr><tr><td>conv_1</td><td>6.92 × 10<sup>8</sup></td><td>6.86 × 10<sup>8</sup></td></tr><tr><td>maxpool_1</td><td>1.26 × 10<sup>7</sup></td><td>1.32 × 10<sup>7</sup></td></tr><tr><td>conv_2</td><td>1.45 × 10<sup>9</sup></td><td>1.45 × 10<sup>9</sup></td></tr><tr><td>maxpool_2</td><td>2.61 × 10<sup>6</sup></td><td>2.62 × 10<sup>6</sup></td></tr><tr><td>inception_1/conv_a</td><td>1.36 × 10<sup>7</sup></td><td>1.37 × 10<sup>7</sup></td></tr><tr><td>inception_1/conv_b1</td><td>8.46 × 10<sup>6</sup></td><td>8.63 × 10<sup>6</sup></td></tr><tr><td>inception_1/conv_b2</td><td>6.29 × 10<sup>7</sup></td><td>7.60 × 10<sup>7</sup></td></tr><tr><td>inception_1/conv_c1</td><td>7.53 × 10<sup>6</sup></td><td>1.86 × 10<sup>6</sup></td></tr><tr><td>inception_1/conv_c2</td><td>1.16 × 10<sup>7</sup></td><td>1.19 × 10<sup>7</sup></td></tr><tr><td>inception_1/maxpool</td><td>2.55 × 10<sup>6</sup></td><td>2.49 × 10<sup>6</sup></td></tr><tr><td>inception_1/conv_d</td><td>6.96 × 10<sup>6</sup></td><td>6.94 × 10<sup>6</sup></td></tr><tr><td>inception_1/concat</td><td>4.37 × 10<sup>5</sup></td><td>4.56 × 10<sup>5</sup></td></tr><tr><td>inception_2/conv_a</td><td>2.03 × 10<sup>7</sup></td><td>2.04 × 10<sup>7</sup></td></tr><tr><td>inception_2/conv_b1</td><td>1.01 × 10<sup>7</sup></td><td>1.02 × 10<sup>7</sup></td></tr><tr><td>inception_2/conv_b2</td><td>9.48 × 10<sup>7</sup></td><td>9.53 × 10<sup>7</sup></td></tr><tr><td>inception_2/conv_c1</td><td>2.54 × 10<sup>6</sup></td><td>2.62 × 10<sup>6</sup></td></tr><tr><td>inception_2/conv_c2</td><td>1.76 × 10<sup>7</sup></td><td>1.92 × 10<sup>7</sup></td></tr><tr><td>inception_2/maxpool</td><td>2.55 × 10<sup>6</sup></td><td>2.62 × 10<sup>6</sup></td></tr><tr><td>inception_2/conv_d</td><td>6.90 × 10<sup>6</sup></td><td>6.94 × 10<sup>6</sup></td></tr><tr><td>inception_2/concat</td><td>1.02 × 10<sup>6</sup></td><td>5.29 × 10<sup>5</sup></td></tr><tr><td>avgpool</td><td>1.69 × 10<sup>5</sup></td><td>1.42 × 10<sup>5</sup></td></tr><tr><td>reshape</td><td>0</td><td>0</td></tr><tr><td>gemm</td><td>2.67 × 10<sup>6</sup></td><td>2.69 × 10<sup>6</sup></td></tr><tr><td>Output Layer</td><td>3.22 × 10<sup>3</sup></td><td>3.77 × 10<sup>3</sup></td></tr><tr><td>Total</td><td>2.42 × 10<sup>9</sup></td><td>2.22 × 10<sup>9</sup></td></tr></tbody></table>

passing state. These mechanisms are necessary both for enforcing precedence constraints—by ensuring that a node is computed after all its parents on other cores—and for preserving the integrity of data in shared memory, by preventing simultaneous writing.

This extension is then verified using both a static WCET analysis with the dedicated tool OTAWA and experimental measurements on a Texas Instruments KeyStone platform.

For future work, we identified limitations in the paper to address, such as the strong constraints on the target (UMA, homogeneous cores, ...). We plan to extend the theory to take into account the use of non-homogeneous cores or accelerators included in the target, and to adapt both the scheduling heuristics and the ILP representation to this new problem. We also plan to explore other parallelization methods to improve the current implementation in ACETONE.

**Acknowledgement** This work has benefited from the AI cluster ANITI2 and from the PATO project funded by the French government through the France Relance program, based on the funding from and by the European Union through the NextGenerationEU program.

## REFERENCES

[1] C. Ballabriga, H. Cassé, C. Rochange, and P. Sainrat. Otawa: An open toolbox for adaptive wcet analysis. In S. L. Min, R. Pettit, P. Puschner, and T. Ungerer, editors, *Software Technologies for Embedded and Ubiquitous Systems*, pages 35–46, Berlin, Heidelberg, 2010.
[2] H.-C. Chou and C.-P. Chung. Optimal multiprocessor task scheduling using dominance and equivalence relations. *Computers & Operations Research*, 21(4):463–475, 1994.

[3] I. De Albuquerque Silva, T. Carle, A. Gauffriau, and C. Pagetti. ACETONE: Predictable Programming Framework for ML Applications in Safety-Critical Systems. In *34th Euromicro Conference on Real-Time Systems (ECRTS 2022)*, Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1–3:19, 2022.

[4] EASA. Concept Paper: guidance for Level 1 & 2 machine learning applications - Proposed Issue 02, 2024.

[5] A. Faure-Gignoux, K. Delmas, A. Gauffriau, and C. Pagetti. Methodology for formal verification of hardware safety strategies using smt. *IEEE Embedded Systems Letters*, 16(4):381–384, 2024.

[6] C. Gabreau and et al. EUROCAE WG114 – SAE G34: a joint standardization initiative to support Artificial Intelligence revolution in aeronautics, 2023. Keynote of SafeAI.

[7] M. R. Garey and D. S. Johnson. *Computers and Intractability: A Guide to the Theory of NP-Completeness*. W. H. Freeman & Co., USA, 1979.

[8] A. Gauffriau, I. D. A. Silva, and C. Pagetti. Formal description of ml models for unambiguous implementation, 2024.

[9] T. Instruments. *TCI6630K2L Multicore DSP+ARM KeyStone II System-on-Chip*. Technical Report SPRS893E, Texas Instruments Incorporated, 2013.

[10] F. Kaakai and et al. Toward a machine learning development lifecycle for product certification and approval in aviation. *SAE International journal of aerospace*, 15, 2022.

[11] F. Kaakai and et al. Data-centric operational design domain characterization for machine learning-based aeronautical products, 2023.

[12] B. Kruatrachue. *Static task scheduling and grain packing in parallel-processing systems*. PhD thesis, Oregon State University, 01 1987.

[13] P. Laborie, J. Rogerie, P. Shaw, and P. Vilím. Ibm ilog cp optimizer for scheduling. *Constraints*, 23(2):210–250, Apr 2018.

[14] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich. Going deeper with convolutions, 2014.

[15] Q. Tang, L.-H. Zhu, L. Zhou, J. Xiong, and J.-B. Wei. Scheduling directed acyclic graphs with optimal duplication strategy on homogeneous multiprocessor systems. *Journal of Parallel and Distributed Computing*, 138:115–127, 2020.

[16] P. Van Hentenryck. *The OPL optimization programming language*. MIT Press, 1999.