# Runtime task scheduling for FPGA-based embedded systems using just-in-time bitstream prefetching

Alexis Duhamel, Sébastien Pillement

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

## To cite this version:

Alexis Duhamel, Sébastien Pillement. Runtime task scheduling for FPGA-based embedded systems using just-in-time bitstream prefetching. IEEE Access, 2024, 12, pp.184303 - 184310. 10.1109/AC-CESS.2024.3507376. [https://doi.org/10.1109/ACCESS.2024.3507376](https://doi.org/10.1109/ACCESS.2024.3507376)

HAL Id: hal-04790732

https://hal.science/hal-04790732v1

Submitted on 6 Jun 2025

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Received 30 September 2024, accepted 14 November 2024, date of publication 27 November 2024, date of current version 16 December 2024.

Digital Object Identifier 10.1109/ACCESS.2024.3507376

RESEARCH ARTICLE

# Runtime Task Scheduling for FPGA-Based Embedded Systems Using Just-in-Time Bitstream Prefetching

ALEXIS DUHAMEL<sup>©</sup> AND SÉBASTIEN PILLEMENT<sup>©</sup>, (Member, IEEE)

CNRS, IETR UMR 6164, Nantes Université, 44000 Nantes, France

Corresponding author: Sébastien Pillement (sebastien.pillement@univ-nantes.fr)

This work was supported by Capgemini Engineering.

**ABSTRACT** Dynamically and partially reconfigurable Field Programmable Gate Arrays (FPGAs) offer high performances and flexibility. These platforms can hot-swap reconfigurable regions to change the hardware behavior at the cost of a reconfiguration process. The scheduling of applications and their reconfiguration processes are then essential to respect timing constraints. In this paper, we introduce PF-PEFT, a scheduling heuristic for dynamically reconfigurable FPGA architectures. Results show that our approach reduces schedules duration by up to 13% compared to a comparable state-of-the-art approach.

**INDEX TERMS** DPR, FPGA, just-in-time bitstream prefetch, reconfigurable computing, runtime scheduling.

## I. INTRODUCTION

FPGAs are mainstream in the industry for hardware acceleration of data flow applications, and their computing performance has been shown to compete with GPU architectures with better energy efficiency. However, the number of available resources in FPGA are limited, and while large circuit exist, industry has an interest in using small circuits to reduce production costs.

To mitigate this hardware limitation, the Dynamic Partial Reconfiguration (DPR) technique can be exploited. It consists in reconfiguring sections of an FPGA, called Reconfigurable Regions (RRs), while the remaining logic gates are still running. This technique enables hot-swapping of hardware blocks at runtime [1].

Applications are then partitioned in hardware tasks [2], introduced to benefit from DPR. To guarantee execution of such applications within a time window, these tasks need to be scheduled on the system's resources. This is done via real-time scheduling heuristic which purpose is to find a partition of the tasks on the available resources respecting

timing constraints, while ensuring there is no deadlock in execution.

Finding schedules that minimize application execution times, or makespan, is a key to maximize performance of DPR-capable FPGA. Additionally, the time overhead introduced by the scheduling algorithm and the reconfiguration process needs to be kept as low as possible.

The contributions of this paper are threefold:

* Just-in-time bitstream prefetching formulation for scheduling heuristics;

* An original runtime scheduling heuristic for DPR capable architectures supporting bitstream pre-fetching;

* A partial schedule computation technique to significantly reduce decision times at runtime.

Experiments conducted on benchmark applications show that our approach outperforms a state of the art [3] approach while remaining in the millisecond range of decision time. Finally, we demonstrate the impact of the reconfigurable architecture composition on the application makespan reduction and on the decision time of the scheduling heuristic.

The remainder of this paper is as follows. Section II introduces the runtime scheduling problem and related works. Section III describes the application and architecture

The associate editor coordinating the review of this manuscript and approving it for publication was Vincenzo Conti<sup>©</sup>.
models, while the proposed method is detailed in Section IV. Finally, experiments results are discussed in Section V before concluding in Section VI.

## II. RELATED WORKS

Classically, data flow applications can be represented by a directed acyclic graph (DAG). Scheduling DAGs is a known NP-Hard problem that consists in time-multiplexing tasks on the architecture resources to minimize makespan, while respecting task dependencies [4]. In comparison with multi/many-core scheduling, proper management of the reconfiguration processes for DPR-capable architectures is required. RRs need to be fully reconfigured before executing a task, using the FPGA's unique Internal Configuration Access Port (ICAP) controller. This is typically done via a dedicated hardware block implemented within the FPGA matrix, and although their bandwidth can reach from 400MBps [5] up to 1.433GBps [6], the duration of this process is non-negligible and scales with the RR size (in logic elements), regardless of its usage.

To mitigate this DPR overhead, partial bitstreams can be pre-fetched to pipeline the configuration process with the execution of other tasks [3], [4]. This way, a pre-fetched task can immediately start its execution after its parent tasks are completed if they do not share the same RR.

To perform runtime scheduling for FPGA-based architectures, heuristics propose acceptable trade-offs between performance (schedule makespan) and complexity (decision delay). In this regard, [3] proposed an ASAP scheduling policy with bitstream pre-fetch capabilities. This approach considers homogeneous RRs, i.e. with a fixed number of logic elements. However, while this approach yields low time complexity ($O(n \cdot p)$ for n tasks and p RRs), it may not account for complex workloads requiring diverse amount of resources.

In the field of heterogeneous MPSoC architectures, the authors of [7] have studied the trade-off between resulting schedule makespan reduction and decision time of heuristics. Results show that the Predict Earliest Finish Time (PEFT) heuristic [8] achieve good performance amongst popular scheduling heuristics. It has a $O(n^2p)$ time complexity for n tasks and p resources which makes for a good efficiency trade-off for runtime scheduling.

Other interesting approaches from the heterogeneous MPSoC field such as [9] offer good trade-off between schedule makespan reduction and complexity. In particular, this approach makes use of a realistic communication model using shared bus which could be abstracted for dynamically reconfigurable resources. However, while this approach tackles the energy consumption problem, it relies on the DVFS capabilities of the processors which cannot be used in our work.

While the heterogeneous MPSoC approaches show similarities with our problem, they do not target FPGA-based platforms. In this context, the authors of [10] have proposed a viable offline formal approach to schedule real-time

applications on FPGA. This work promises interesting results to benefit from the capabilities of dynamically reconfigurable systems, but lack the flexibility of online scheduling. The latter being critical for time-critical and environment-dependant applications, which is covered in this work.

The EFT scheduling heuristics family has been used in the past to schedule DAGs on DPR-capable FPGA architectures [11], [12]. However, and to the best of our knowledge, no other works intend to employ the pre-fetching technique to benefit from the efficiency of PEFT and mitigate DPR overhead. Furthermore, approaches that do employ pre-fetching [3] do not consider architectures with RRs of different sizes, which has proven to optimize resource usage [13].

## III. MODELS DEFINITION

### A. MODEL OF ARCHITECTURE

We target a FPGA-based system on chip which embeds a CPU, an FPGA, and on-chip memories. This type of platform is typical of those used in the industry, such as Zynq platforms which we employ in our experiments. Our DPR-capable architecture, shown in Figure 1, supports multiple heterogeneous (i.e. of different size) RRs to execute hardware tasks.

<figure><img src="image_3.png" /><figcaption>FIGURE 1. Overview of the targeted architecture. Dark blue arrows represent the reconfiguration process flow, Dashed red arrows the control flow, and light green arrows the application data flow.</figcaption></figure>

Dynamic reconfiguration of RRs is handled by the VR-ZYCAP DPR controller [5]. The RRs are heterogeneous in size which has a direct impact on the partial bitstream file sizes, and reconfiguration times [14]. Each RR has a dedicated local static memory. The latter is used as data buffer while the RR is being reconfigured to separate communication and reconfiguration operations.

In the FPGA, an AXI-Stream switch interface ensures the transfer of data between RRs and the shared DDR memory. We use this infrastructure for its communication efficiency [15] and its simple timing model, although its implementation is not optimal [16] and it imposes congestion problems. Communication optimizations are out of the scope of this work.

Without loss of generality, and to enable modifications we rely on the open-source Linux-based FPGA Operating
System (FOS) libraries [17]. These libraries offer an API to control the execution of hardware tasks on FPGA targets. The CPU execute the scheduling heuristic at runtime, and software tasks via the POSIX API.

We define a communication matrix C of size $p \times p$, with p the number of resources. Element $C(p_i; p_j)$ is the worst-case estimated time to transfer data from resource $p_i$ to $p_j$. When the data is stored in the local buffer, then $p_i = p_j$, and $C(p_i; p_j) = 0$. Finally, a reconfiguration vector R of size p denotes the reconfiguration latency of resources. In this work, a resource can denote either a RR or a software thread, with $R(p_i) = 0$ if $p_i$ is the CPU.

## B. MODEL OF APPLICATIONS

Data stream applications are represented by their Directed Acyclic Graph (DAG). They are composed of nodes which represent tasks to execute, and edges representing data dependencies. Tasks can be executed once all their predecessors have been executed and their input data stored in their local memory. Tasks are atomic, and hardware preemption is not considered in this work due to the cost of this approach.

By definition, DAGs are arranged in such a way that no loop occurs. Data-flow applications can typically be represented by such graphs [18]. These DAGs may possess bottlenecks, which are characterized by nodes having more parents than children nodes. Bottlenecks are typically in the critical path of the DAG. Therefore any delay in their execution has a direct impact on the overall schedule makespan. Bottleneck detection, as performed by the PEFT algorithm, is a desirable feature for our problem.

Formally, we define the adjacency matrix A of size $n \times n$, with n the number of tasks in the DAG. Elements $A(t_i; t_j)$ are equal to 0 or 1, respectively denoting absence or presence of a data dependency between tasks $t_i$ and $t_j$. The computation matrix W has size $n \times p$, and elements $W(t_i; p_j)$ are the profiled execution times of task $t_i$ on resource $p_j$. $W(t_i; p_j) = 0$ indicates that task $t_i$ cannot be executed on the resource $p_j$.

Table 1 summarizes the parameters used for the models.

<table><caption>TABLE 1. Architecture and application models parameters.</caption><thead><tr><td>Symbol</td><td>Name</td><td>Size</td></tr></thead><tbody><tr><td>n</td><td>Number of tasks</td><td>1</td></tr><tr><td>p</td><td>Number of resources</td><td>1</td></tr><tr><td>A</td><td>Adjacency matrix</td><td>n × n</td></tr><tr><td>C</td><td>Communication matrix</td><td>p × p</td></tr><tr><td>W</td><td>Computation matrix</td><td>n × p</td></tr><tr><td>R</td><td>Reconfiguration vector</td><td>p × 1</td></tr></tbody></table>

## IV. METHODOLOGY

We define the scheduling problem as the allocation of tasks to resources with objective to minimize the schedule length while satisfying the following set of constraints:

* All tasks from the task graph must be allocated exactly once, respecting the task execution dependencies;

* A task is atomic and may not be preempted;

* Any task $t_i$ can be allocated to any resource $p_j$ if $W(i; j) > 0$;

* A resource $p_j$ can only be assigned to one task at any given time;

* A task $t_i$ allocated on resource $p_j$ with $R(j) > 0$ is a hardware task and must be reconfigured by the DPR controller, abstracted as a unique resource dedicated to reconfiguration;

* Reconfiguration of a RR j is abstracted as a reconfiguration job $t_j^R$, and its reconfiguration time $R_j$ must be accounted for in the overall schedule;

* A hardware task $t_i$ must start after reconfiguration of the RR j (i.e. after job $t_j^R$);

* A task $t_i$ on resource $p_j$ must start after receiving data from its predecessor job, if any, and communication latency between tasks must be accounted for if they are scheduled on different resources;

Computing an optimal solution for the scheduling problem is NP-complete and even more would be too compute-intensive for runtime scheduling on the targeted embedded system (Fig. 1). Therefore, we propose a scheduling heuristic based on the PEFT algorithm [8] targeting heterogeneous multi CPUs platform.

### A. PEFT HEURISTIC

The PEFT heuristic is based on an Optimistic Cost Table (OCT) to predict the impact of assigning a task to a resource on the application makespan. This enables the heuristic to make decisions based on potential makespan reduction further down the task graph and to avoid task dependency bottlenecks.

The OCT table is a matrix of size $n \times p$ that captures the remaining schedule duration comprised of $t_i$'s children tasks when assigning $t_i$ to $p_j$ in Eq. (1). It is evaluated recursively by computing the maximum of shortest paths to the sink task of the application DAG using Eq. (2):

$$ \text{OCT}(t_i; p_j) = \max_{t_c \in \text{child}(t_i)} \left[ \min_{p_w \in \text{PE}} \{\omega(t_i; t_c; p_j; p_w)\} \right] \quad (1) $$

with the duration cost $\omega$ of a path to the sink node defined as:

$$ \omega(t_i; t_c; p_j; p_w) = \text{OCT}(t_c; p_w) + W(t_i; p_j) + C(p_j; p_w) \quad (2) $$

An OCT ranks vector, of size n, of average OCT values per resource, is then computed. The OCT rank of task $t_i$ is a representation of the remaining schedule duration after $t_i$'s termination. This vector is used to define a topological ordering from highest to lowest OCT rank, determining a priority list for tasks.

After having computed the OCT table and ranks, the heuristic enters its main loop and schedules tasks in the list of tasks ready for execution in a decreasing OCT rank order. The selected resource for the task implementation is the one that minimizes the Optimistic Earliest Finish Time ($O_{EFT}$). It is a runtime prediction indicator of the remaining workload
duration, defined by Eq. (3).

$$O_{EFT}(t_i; p_j) = OCT(t_i; p_j) + EFT(t_i; p_j) \quad (3)$$

with EFT(tᵢ; pⱼ) being the earliest time at which task tᵢ can be terminated on resource pⱼ given the DAG topology, assuming the resource is free. This prediction indicator helps PEFT schedule tasks in such a way that it minimizes the earliest finish time of the whole set of remaining tasks to schedule.

A task can be inserted in the existing schedule by insertion policy, illustrated in Fig. 2 for task t'₄, if there is enough idle time in a resource's schedule, known as the insertion window. This policy helps to maximize resource occupancy and to reduce schedule makespan. If the insertion is not feasible, the task is appended to the schedule (case t''₄ in Fig. 2).

<figure><img src="image_4.png" /><figcaption>FIGURE 2. Schedule of task t₄ from an example task graph on two software resources. t''₄ (in blue) is inserted in the schedule, while t''₄ (in red) is appended to the schedule.</figcaption></figure>

Once a task has been scheduled, some or all of its children may be ready for execution and are added to the ready list. PEFT repeats resource selection by O<sub>EFT</sub> minimization until all tasks are scheduled.

## B. PF-PEFT

To adapt the PEFT heuristic to DPR-capable architectures, we need to consider hardware tasks and RRs must be reconfigured before executing tasks. This reconfiguration process is decoupled from the task and can be seen as a setup cost to use the RR. When a RR is being reconfigured, it is considered busy during the process. This process is atomic and cannot be preempted.

As the ICAP controller is unique, it must be shared by all RR reconfigurations. Ignoring the inherent ICAP management problem can lead to unrealistic schedules with parallel DPR processes. As a consequence, the scheduling heuristic must check the availability of the resource, and potentially delay the reconfiguration process. In order to optimize the application execution time, the proposed heuristic thus supports bitstream pre-fetching.

Additional constraints must be considered in the scheduling heuristic if the next or previous reconfiguration task targets the same RR:

* **RR occupancy:** a RR cannot be reconfigured if it is currently executing a hardware task or is in a reconfiguration process.

* **Idle task residency:** a pre-fetched bitstream is implemented on the RR and is waiting for termination of its parent(s), preventing other tasks from being scheduled in the gap as it would overwrite the idle task in the RR.

PF-PEFT addresses these two constraints with an additional DPR resource schedule that contains exclusively reconfiguration tasks performed by the ICAP controller. In the scheduling heuristic, once an EFT for hardware task tᵢ has been selected, a corresponding reconfiguration task t''ᵢ must be handled first.

To reduce the idle task residency constraint, we introduce Just-In-Time (JIT) bitstream pre-fetching. The goal is to make the reconfiguration task t''ᵢ end as close as possible to the earliest start of tᵢ. To answer the RR occupancy constraint with JIT pre-fetching, we identified three cases presented in Figure 3.

<figure><img src="image_5.png" /><figcaption>FIGURE 3. The three cases of Just-In-Time (JIT) bitstream pre-fetching.</figcaption></figure>

When task tᵢ and its reconfiguration task t''ᵢ shares the same earliest start due to RR occupancy constraint, case one happens and tᵢ's start is delayed by the duration of t''ᵢ. This is the worst case scenario as pre-fetching isn't possible.

Case two happens when t''ᵢ's earliest start is sooner than tᵢ's, and the gap between these two times is longer than the duration of t''ᵢ. Then JIT pre-fetching is applied and tᵢ can start at its earliest evaluated start time. This is the best case to reduce tᵢ's EFT.

Case three happens when the time gap isn't long enough to fully fit t''ᵢ, and tᵢ's start is delayed by the overhead.

Because JIT pre-fetching is a decision made after the OCT table computation, we need to assume the worst case scenario when computing OCT(tᵢ; pⱼ) values. The shortest path evaluation needs to be modified to take reconfiguration times into account. The path cost formula of (2) then becomes:

$$ \begin{aligned} & \omega(t_i; t_c; p_j; p_w) \\ &= OCT(t_c; p_w) + W(t_c; p_w) + C(p_j; p_w) + R(p_w) \end{aligned} \quad (4) $$
**Algorithm 1 PF-PEFT Scheduling Heuristic**

**Input:** Matrices A, C, W and vector R

**Output:** Application schedule for DPR capable architecture

1. Compute OCT table recursively with (1) and (4)

2. Put source task in the list of tasks ready for execution (ready-list)

3. **while** ready-list not empty **do**

4. $t_i \leftarrow$ highest OCT ranked task from ready-list

5. **for each** $p_j \in$ set of resources **do**

6. Compute $EFT(t_i; p_j)$ using insertion policy

7. **if** $R(p_j) > 0$ **then** // If $p_j$ is a RR

8. Set reconf. task $t_i^R$ for resource $p_j$ with JIT pre-fetch

9. **if** delay > 0 **then** // JIT pre-fetch case 1 or 3

10. Update $EFT(t_i; p_j)$

11. $O_{EFT}(t_i; p_j) \leftarrow OCT(t_i; p_j) + EFT(t_i; p_j)$

12. Assign task $t_i$ to resource $p_j$ that minimizes $O_{EFT}$

13. Update ready-list with $t_i$'s children

14. **return** PF-PEFT schedule

The computational complexity of PF-PEFT can be analyzed. The computation of the OCT table requires recursive calculations based on the dependencies of each task and for each processor, resulting in a complexity of at most $O(n^2p)$. The main while-loop (lines 3-18) iterates $n$ times, corresponding to the number of tasks. In line 4, task selection from the ready-list causes a worst-case complexity of $O(n)$, given that the list contains at most $n$ tasks. The nested loop (line 5) iterates over the $p$ resources, and for each resource, the computation of the Earliest Finish Time (EFT) with insertion policy requires at most $O(n)$ operations, regardless of whether the task is hardware or software. Finally, after exiting the nested loop, identifying the task-resource pair that minimizes $O_{EFT}$ requires $p$ iterations.

Therefore, the nested loop line 5 has a computational complexity of $O(n.p)$ to compute the $O_{EFT}$. This in turns makes the main loop reach a complexity of $O(n^2p)$ to compute this for each task in the task graph. Finally, because the OCT table computation is out of the main loop, this gives a final computational complexity of $O(n^2p) + O(n^2p) = O(n^2p)$.

### C. PARTIAL AND COMPLETE PF-PEFT FOR RUNTIME SCHEDULING

Runtime schedule computation is desirable when the workload to execute changes dynamically, or when application constraints change [1], [19]. Statically defined schedules may not cover all runtime situations unless a sizable database of schedules is stored on-target, which can be impossible on embedded systems.

To compute a new schedule online, we execute the proposed PF-PEFT heuristic, presented in Algorithm 1. However, the OCT table is computed only (line 1), and is only used as reference for prediction. To reduce the scheduling

heuristic decision time, it is possible to store a statically computed OCT table instead of computing a new one for each new schedule.

We define *Partial* and *Complete* versions of PF-PEFT, which respectively denote the version that reuse a statically computed OCT table, and the one that computes a new OCT table each time. Because PF-PEFT is deterministic, their resulting schedule makespan are equal whether, and the two versions only differ in decision times.

## V. RESULTS

### A. EXPERIMENTAL SETUP

We evaluated a set of ten applications implemented on DPR-capable architectures [4], [20], including a in-house H264 implementation. We extrapolated task computations time from heterogeneous CPU-GPU architectures by assuming that the execution times on GPU are similar to those on FPGA [8], [21].

In addition, we generated random synthetic DAGs as in [3] to have results on a variety of DAG topologies. Synthetic DAG are generated by connecting a random number of nodes $n \in$ [20; 100]. Each node can be connected randomly with a number $m(X)$ of nodes from previous layers, with $X$ being a random uniform value in [0; 1] and $m(X) = \lceil \frac{n}{10}e^{-5X} \rceil$. This makes each DAG node capable of being connected with one to $\lceil \frac{n}{10} \rceil$ previous nodes.

The adjacency matrix $A$ can then be extracted, and the corresponding computation matrix $W$ values are generated uniformly in the [0.5; 50] range (in ms), which corresponds to computation times from the literature benchmark applications [4], [18], [22], [23].

We measure and compare the performance of PF-PEFT and of the prefetch-capable ASAP heuristic from [3]. To compare schedule makespans, we use the Schedule Length Ratio (SLR) [24], defined as the normalization of the resulting schedule duration, by the critical path CP of the architecture (Eq. 5).

$$SLR = \frac{\text{Makespan} + \text{Decision time}}{\sum_{n_i \in CP} \min [W(i; j)]} \quad (5)$$

The critical path is given for an ideal architecture with no reconfiguration nor communication times. SLR is dimensionless and cannot be less than one, and the lowest the SLR is, the better.

Results are obtained by running the heuristics on the ARM core of the platform, and decision times were measured using the time.h library. We included these times to the resulting schedule makespan. This provides the full picture of the performance of the heuristics as it considers both their inherent time complexity and makespan reduction performance.

We considered different application compositions with tasks using 1k up to 10k slices of a Xilinx ZCU9EG FPGA. The size of the resulting partial bitstreams range from 400 kB to 2 MB. Using the VR-Zycap 380 MBps ICAP
controller [5], profiled reconfiguration times are comprised between 1.23 ms and 5.24 ms.

We experiment with four resource compositions (Table 2) of “small” RRs (less than 2k slices) and “large” RRs (greater than 8k, up to 10k slices), as used in [2] and [17]. Fewer RRs in the FPGA matrix imply bigger regions, and as the number of RRs grows, a variety of RR sizes is defined to fill the FPGA matrix.

<table><caption>TABLE 2. Considered architecture resource compositions.</caption><thead><tr><td>Composition</td><td>RR sizes</td><td>Description</td></tr></thead><tbody><tr><td>4RR+1SW</td><td>4 large</td><td>Coarse-grain island style</td></tr><tr><td>8RR+2SW</td><td>3 large, 5 small</td><td>Balanced coarse-grain</td></tr><tr><td>12RR+3SW</td><td>2 large, 10 small</td><td>Fragmented</td></tr><tr><td>16RR+4SW</td><td>1 large, 15 small</td><td>Highly parallel</td></tr></tbody></table>

The communication matrices are extracted from measured worst-case communication time for 4 kB data chunks. Measured times are 0.96 ms between RRs, including AXI-Stream interconnect configuration, 0.26 ms between RRs and software threads via DMA on the shared memory, and 0.01 ms between software threads.

## B. EXPERIMENTS RESULTS

### 1) APPLICATION BENCHMARKS

Table 3 gives the obtained results on the benchmarks, with the SLR of ASAP as reference. Those results were obtained on the 8RR+2SW architecture.

<table><caption>TABLE 3. Comparative performance of heuristics measured in SLR for the 8RR+2SW architecture.</caption><thead><tr><th rowspan="2"></th><th rowspan="2">Task count</th><th rowspan="2">ASAP [3]</th><th colspan="2">PF-PEFT</th></tr><tr><th>Partial</th><th>Complete</th></tr></thead><tbody><tr><td>CryptoGraphy<fnref n="1" /> [22]</td><td>4</td><td>18.274</td><td>0.00%</td><td>0.01%</td></tr><tr><td>StereoVision [4]</td><td>7</td><td>1.329</td><td>-1.94%</td><td>-1.94%</td></tr><tr><td>Edge Detection Mix [20]</td><td>9</td><td>1.770</td><td>-6.52%</td><td>-6.51%</td></tr><tr><td>Canonical<fnref n="1" /> [8]</td><td>10</td><td>3.351</td><td>-13.23%</td><td>-13.22%</td></tr><tr><td>H264 (this work)</td><td>10</td><td>1.810</td><td>-19.26%</td><td>-19.23%</td></tr><tr><td>Traction Control<fnref n="1" /> [23]</td><td>10</td><td>2.254</td><td>-12.49%</td><td>-12.43%</td></tr><tr><td>Lane Detection<fnref n="1" /> [22]</td><td>14</td><td>4.280</td><td>-46.65%</td><td>-46.61%</td></tr><tr><td>Epigenomics<fnref n="1" /> [18]</td><td>20</td><td>1.775</td><td>-1.84%</td><td>-1.84%</td></tr><tr><td>CyberShake<fnref n="1" /> [18]</td><td>22</td><td>2.167</td><td>-26.75%</td><td>-26.74%</td></tr><tr><td>Montage<fnref n="1" /> [18]</td><td>26</td><td>1.946</td><td>-3.97%</td><td>-3.97%</td></tr></tbody></table>

PF-PEFT and ASAP yield similar schedules with less than 2% difference for applications with sequential topologies such as CryptoGraphy, StereoVision and Epigenomics, except for the Lane Detection, which has a DAG reconvergence that ASAP was unable to predict, whereas PF-PEFT was able to anticipate and therefore minimize makespan by -46%.

On average, the partial and complete PF-PEFT heuristics respectively yield 13.26% and 13.25% shorter schedules than ASAP. There is a small difference as decision times for applications with low task counts remain within a

hundred microseconds, noticeably shorter than hardware task computation times.

### 2) SYNTHETIC DAG BENCHMARKS

Figure 4 illustrates the resulting SLR evolution with the number of nodes in synthetic DAGs for both heuristics for a 8RR+2SW architecture. A total of one million synthetic DAGs were generated.

<figure><img src="image_6.png" /><figcaption>FIGURE 4. Resulting application SLR according to the number of nodes for synthetic DAGs on a 8RR+2SW architecture composition.</figcaption></figure>

The PF-PEFT heuristic outperforms ASAP on all evaluated synthetic benchmarks. SLRs are reduced by 23% over ASAP at the 20 nodes count on average, and up to 30% for higher node counts. This is due to the fact that DAG bottlenecks can be predicted early in the scheduling phase. As JIT pre-fetching minimizes the idle task residency, it enables PF-PEFT to fill gaps with the insertion policy in the RR schedules whenever possible.

The difference between partial and complete PF-PEFT grows up to 1.39% at higher task counts as the decision time increases significantly, which highlights how reusing the OCT table in the partial PF-PEFT can slightly improve performance.

### 3) RESOURCE COMPOSITION EVALUATION

In this last experiment, we evaluated the impact of resource composition on the PF-PEFT heuristic performance.

The impact of resource composition on the resulting SLR is shown in Figure 5.a. As expected, more resource lead to better schedules. However this relation gets diminishing returns, as synthetic DAGs are not specifically generated to be highly parallel.

Figure 5.b shows that decision times increases according to the platform size. This was expected as time complexity for PF-PEFT is $O(n^2p)$. The ASAP scheduling policy is consistently 10× faster than PF-PEFT. However, decision times are included in the SLR and makespan reductions offered by PF-PEFT outweigh the higher decision times.

Finally, Figure 5.c highlights the average part of decision times from (b) spent computing the OCT table. PF-PEFT typically spends half its decision time for the OCT table computation. This illustrate the potential benefit of partial PF-PEFT at the cost of not being able to modify the workload's properties at runtime.

<footnote n="1">¹ Task execution times extrapolated from heterogeneous CPU and GPU platforms.</footnote>
<figure><img src="image_7.png" /><figcaption>**FIGURE 5.** (a) SLR and (b) decision times by nodes and architecture composition for PF-PEFT, with average ASAP decision times on all considered architectures, and (c) impact of OCT computation on decision time.</figcaption></figure>

## 4) DAG COMPOSITION EVALUATION

In this section, we compare two topologies of task graphs: Wide and Tall. Wide task graphs have a higher level of parallelism (e.g.: Cybershake), versus Tall graphs which are more sequential (e.g.: Epigenomic). Wide synthetic task graphs were obtained by fixing the number of layers in the DAG generation to $h \in [1; 4]$ with a number of tasks in a layer $w \in [2; 50]$. Tall graphs were obtained with $h \in [1; 50]$ and $w \in [2; 4]$.

Figure 6 insets (a) and (b) show that task graph topology impacts the decision time mostly during the OCT table computation phase, as partial PF-PEFT decision times remain relatively identical between Wide and Tall, while Complete PF-PEFT increases significantly. This is due to the recursivity of the OCT table computation, which benefits from reusing OCT values from a common direct parent task, which is more commonly found in highly parallel applications than more sequential ones.

Insets (c) and (d) show PF-PEFT (both Partial and Complete) yields 29% shorter makespan on Wide task graphs than ASAP, and 41% shorter on Tall graphs. This is because task execution bottlenecks are more prevalent in more sequential graphs. This highlights PF-PEFT prediction capabilities. If Wide graphs have fewer of such bottlenecks,

<figure><img src="image_8.png" /><figcaption>**FIGURE 6.** Comparison of the impact of Wide and Tall task graph topologies on resulting SLR and decision times.</figcaption></figure>

PF-PEFT was still capable of finding better schedule than ASAP thanks to our reconfiguration task insertion policy, which reduced the reconfiguration overhead.

## VI. CONCLUSION

This paper introduce PF-PEFT, a runtime capable scheduling heuristic for DPR-capable FPGA. It is capable of scheduling scalable task graphs on FPGA RRs of different sizes, and implement Just-In-Time bitstream pre-fetch to reduce application makespan and respect hardware constraints. Compared to a state of the art algorithm with bitstream pre-fetch capabilities, experiments show our approach yields up to 13% shorter schedules including decision time.

Furthermore, it was shown that the scheduling decision times of our approach can be reduced by 40% to 60% by reusing a pre-computed OCT prediction table.

Finally, experiments show that the heuristic scale with resource composition in the architecture and that a trade-off exists between makespan reduction and scheduling decision times.

However, while the proposed scheme yields good results in terms of SLR on synthetic and the set of benchmark applications, workloads containing a higher number of tasks in their DAG will have to pay the increasing decision time. For future works, we believe mixed methodologies capable of delivering a first sub-optimal schedule fast and then refine it could help satisfy real-time application constraints and make a better use of processing resources.

## REFERENCES

[1] M. Nguyen, R. Tamburo, S. Narasimhan, and J. C. Hoe, "Quantifying the benefits of dynamic partial reconfiguration for embedded vision applications," in *Proc. 29th Int. Conf. Field Program. Log. Appl. (FPL)*, Sep. 2019, pp. 129–135.

[2] A. Agne, M. Platzner, C. Plessi, M. Happe, and E. Lübers, "ReconOS," in *FPGAs for Software Programmers*. Berlin, Germany: Springer, pp. 227–244, Oct. 2009.
[3] R. Ramezani, “A prefetch-aware scheduling for FPGA-based multi-task graph systems,” *J. Supercomput.*, vol. 76, no. 9, pp. 7140–7160, Sep. 2020.

[4] A. Dorflinger, M. Albers, J. Schlatow, B. Fiethe, H. Michalik, P. Keldenich, and S. P. Fekete, “Hardware and software task scheduling for ARM-FPGA platforms,” in *Proc. NASA/ESA Conf. Adapt. Hardw. Syst. (AHS)*, Aug. 2018, pp. 66–73.

[5] B. Sultana, A. Ullah, A. A. Malik, A. Zahir, P. Reviriego, F. B. Muslim, N. Ullah, and W. Ahmad, “VR-ZYCAP: A versatile resource-level ICAP controller for Zynq SOC,” *Electronics*, vol. 10, no. 8, p. 899, Apr. 2021.

[6] R. Bonamy, H.-M. Pham, S. Pillement, and D. Chillet, “UPaRC—Ultra-fast power-aware reconfiguration controller,” in *Proc. Design, Autom. Test Eur. Conf. Exhib. (DATE)*, Mar. 2012, pp. 1373–1378.

[7] A. K. Maurya and A. K. Tripathi, “On benchmarking task scheduling algorithms for heterogeneous computing systems,” *J. Supercomput.*, vol. 74, no. 7, pp. 3039–3070, Jul. 2018.

[8] H. Arabnejad and J. G. Barbosa, “List scheduling algorithm for heterogeneous systems by an optimistic cost table,” *IEEE Trans. Parallel Distrib. Syst.*, vol. 25, no. 3, pp. 682–694, Mar. 2013.

[9] S. K. Roy, R. Devaraj, and A. Sarkar, “SAFLA: Scheduling multiple real-time periodic task graphs on heterogeneous systems,” *IEEE Trans. Comput.*, vol. 72, no. 4, pp. 1067–1080, Apr. 2023.

[10] C. Kejela, R. Devaraj, A. Sarkar, and S. Saha, “A supervisory control approach for scheduling real-time periodic tasks on dynamically reconfigurable platforms,” in *Proc. 25th Euromicro Conf. Digit. Syst. Design (DSD)*, Aug. 2022, pp. 1–8.

[11] M. Bertolino, R. Pacalet, L. Apvrille, and A. Enrici, “Multi-resource scheduling for FPGA systems,” *Microprocessors Microsyst.*, vol. 87, Nov. 2021, Art. no. 104373.

[12] R. Ramezani, “Dynamic scheduling of task graphs in multi-FPGA systems using critical path,” *J. Supercomput.*, vol. 77, no. 1, pp. 597–618, Jan. 2021.

[13] Z. Sun, H. Zhang, and Z. Zhang, “Resource-aware task scheduling and placement in multi-FPGA system,” *IEEE Access*, vol. 7, pp. 163851–163863, 2019.

[14] K. Vipin and S. A. Fahmy, “FPGA dynamic and partial reconfiguration: A survey of architectures, methods, and applications,” *ACM Comput. Surveys*, vol. 51, no. 4, pp. 1–39, Jul. 2018.

[15] Y. Wang, X. Zhou, L. Wang, J. Yan, W. Luk, C. Peng, and J. Tong, “SPREAD: A streaming-based partially reconfigurable architecture and programming model,” *IEEE Trans. Very Large Scale Integr. (VLSI) Syst.*, vol. 21, no. 12, pp. 2179–2192, Dec. 2013.

[16] E. M. Abdali, M. Pelcat, F. Berry, J.-P. Diguet, and F. Palumbo, “Exploring the performance of partially reconfigurable point-to-point interconnects,” in *Proc. 12th Int. Symp. Reconfigurable Commun.-Centric Syst.-Chip (ReCoSoC)*, Jul. 2017, pp. 1–6.

[17] A. Vaishnav, K. D. Pham, J. Powell, and D. Koch, “FOS: A modular FPGA operating system for dynamic workloads,” *ACM Trans. Reconfigurable Technol. Syst.*, vol. 13, no. 4, pp. 1–28, Dec. 2020.

[18] G. Juve, A. Chervenak, E. Deelman, S. Bharathi, G. Mehta, and K. Vahi, “Characterizing and profiling scientific workflows,” *Future Gener. Comput. Syst.*, vol. 29, no. 3, pp. 682–692, Mar. 2013.

[19] C. Hireche, C. Dezan, S. Mocanu, D. Heller, and J.-P. Diguet, “Context/resource-aware mission planning based on BNs and concurrent MDPs for autonomous UAVs,” *Sensors*, vol. 18, no. 12, p. 4266, Dec. 2018.

[20] G. Charitopoulos, I. Koidis, K. Papadimitriou, and D. Pnevmatikatos, “Run-time management of systems with partially reconfigurable FPGAs,” *Integration*, vol. 57, pp. 34–44, Mar. 2017.

[21] E. Nurvitadhi, G. Venkatesh, J. Sim, D. Marr, R. Huang, J. O. G. Hock, Y. T. Liew, K. Srivatsan, D. Moss, S. Subhaschandra, and G. Boudoukh, “Can FPGAs beat GPUs in accelerating next-generation deep neural networks?” in *Proc. ACM/SIGDA Int. Symp. Field-Program. Gate Arrays*, Feb. 2017, pp. 5–14.

[22] D. Jeong, J. Kim, M.-L. Oldja, and S. Ha, “Parallel scheduling of multiple SDF graphs onto heterogeneous processors,” *IEEE Access*, vol. 9, pp. 20493–20507, 2021.

[23] S. K. Roy, R. Devaraj, A. Sarkar, and D. Senapati, “SLAQA: Quality-level aware scheduling of task graphs on heterogeneous distributed systems,” *ACM Trans. Embedded Comput. Syst.*, vol. 20, no. 5, pp. 1–31, Sep. 2021.

[24] H. Topcuoglu, S. Hariri, and M.-Y. Wu, “Performance-effective and low-complexity task scheduling for heterogeneous computing,” *IEEE Trans. Parallel Distrib. Syst.*, vol. 13, no. 3, pp. 260–274, Mar. 2002.

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

**ALEXIS DUHAMEL** received the Engineering degree in electronics and digital technologies engineering from Polytech Nantes, in 2018, and the Ph.D. degree in electronics engineering from Nantes Université, in 2022. From 2019 to 2022, he was part of the UCODEC Research and Development Team, Capgemini, France. Since 2022, he has been a Digital Design Engineer with Microchip. His research interests include dynamic partial reconfiguration of FPGA devices, architecture of self-reconfigurable systems, heterogeneous hardware-software workload scheduling, hardware preemption, SoC energy consumption, and runtime management methodologies.

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

**SÉBASTIEN PILLEMENT** (Member, IEEE) received the Ph.D. degree from the University of Montpellier II, in 1998, and the Habilitation degree in computer engineering from the University of Rennes 1, France, in 2010.

From 1999 to 2012, he was with IUT, Lannion, the subdivision of the University of Rennes 1, and was also a Research Member with the CAIRN INRIA Research Team, Research Institute of Computer Science and Random Systems (IRISA Laboratory). Since 2012, he has been a Full Professor with Polytech Nantes, Engineering School, Nantes University, and a member with UMR CNRS 6164, Research Institute of Electronics and Telecommunication (IETR Laboratory). He is currently the Deputy Director of the SoC2 National Research Group. He is the author or co-author of about 160 journals and conference papers and holds two patents. His research interests include dynamically reconfigurable architectures, smart systems on chips, design methodology, and network-on-chip (NoC)-based circuits. He focuses his research on designing intelligent, flexible, and efficient architectures managed in real-time and on the use of these architectures to increase the reliability of systems, with a focus on embedded AI.

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