# Static Scheduling of Periodic Hardware Tasks with Precedence and Deadline Constraints on Reconfigurable Hardware Devices

Authors: Ikbel Belaid; Fabrice Muller; Maher Benjemaa
Journal: International Journal of Reconfigurable Computing
 (2011)

---

## Abstract

Task graph scheduling for reconfigurable hardware devices can be defined as finding a schedule for a set of periodic tasks with precedence, dependence, and deadline constraints as well as their optimal allocations on the available heterogeneous hardware resources. This paper proposes a new methodology comprising three main stages. Using these three main stages, dynamic partial reconfiguration and mixed integer programming, pipelined scheduling and efficient placement are achieved and enable parallel computing of the task graph on the reconfigurable devices by optimizing placement/scheduling quality. Experiments on an application of heterogeneous hardware tasks demonstrate an improvement of resource utilization of 12.45% of the available reconfigurable resources corresponding to a resource gain of 17.3% compared to a static design. The configuration overhead is reduced to 2% of the total running time. Due to pipelined scheduling, the task graph spanning is minimized by 4% compared to sequential execution of the graph.


---

## Body

## 1. Introduction

An important trend in real-time applications implemented in reconfigurable computing systems consists in using reconfigurable hardware devices to increase performances and to guarantee temporal constraints. These reconfigurable devices provide a high density of heterogeneous resources in order to satisfy application requirements and especially to enable parallel computing. Furthermore, the devices employ the pertinent concept of run-time partial reconfiguration which allows reconfiguration of a portion of available resources without interrupting the remainder parts running in the same device. Consequently, the concept increases resource utilization and application performance.Periodic partially ordered activities represent the major computational demand in real-time systems such as real-time control and digital signal processing. This category of repetitive computation is described by directed acyclic graphs (DAGs). Implementation of these DAGs in reconfigurable hardware devices consists in scheduling tasks to a limited number of nonidentical units shaped on the area of reconfigurable resources, while respecting the four constraints described as follows. (1) The periodicity constraint: each task is repeated periodically according to its ready times in the graph. Thus, if taskA has a period PA, then for all i∈ℕ, (rAi+1-rAi)=PA, where Ai and Ai+1 are the ith and the (i+1)th repetitions of task A, and rAi and rAi+1 are their start times. (2) The precedence constraint: to maintain the rightness of task precedences, in each iteration, a task can be executed only if all its predecessors in the graph have finished their executions. Therefore, each task A must start execution after the completion of executions of its predecessors defined by the subset ΠA, thus for all i∈ℕ, sAi≥sBi+CB, for all B∈ΠA, where sAi, sBi are the start times of task A and task B, respectively, during their ith iteration, and CB is the execution time of task B. (3) The dependence constraint: the execution of each task in DAG is launched when all the data resulting from all its predecessors are available. This constraint guides the choice of task periods as detailed in Section 3. (4) The deadline constraint: as this paper focuses on hard real-time systems, each task in the DAG must finish its execution before its hard deadline. Thus, within iteration i, if task A has an execution time CA and an absolute deadline dAi, then sAi+CA≤dAi.Figure1 illustrates an example of the targeting task graph. As can be seen in Figure 1, the tasks are repeated according to their fixed periods. Each task with precedence link launches its execution only when its predecessors achieve their executions and only when it is required. For example, the third iterations of T2 and T3 of periods 8 do not need a third execution of their predecessor T1 as it is less repetitive than T2 and T3 (period of T1 is equal to 12). At each repetition, to enable the task execution, the dotted lines ensure the data transfer between interdependent tasks. The issue of data dependence is detailed later in the paper. Finally, at each iteration, the real-time tasks must respect their hard deadlines.Figure 1
The targeted acyclic task graph.As shown in Figure2, this paper proposes a new methodology comprising three main stages to achieve the scheduling of these DAGs with the predefined constraints on reconfigurable devices.Figure 2
The proposed methodology.Task Clustering
This stage is technology dependent. It targets the partitioning of tasks requiring the same types of resources into the same cluster.Mapping/Scheduling of Tasks in Clusters
This stage starts by performing spatial and temporal analyses mentioned in Figure2 by DAG validity, Ready Times, and a set of heuristics. Subsequently, based on a predefined preemption model, it deals with simultaneous resolution of mapping tasks to the obtained clusters and global scheduling of tasks in clusters respecting the periodicity, precedence, dependence, and deadline constraints. This stage aims at optimizing scheduling quality.Cluster Placement on the Reconfigurable Device
This stage is also technology dependent. It involves searching for the most suitable physical location partitioned on the reconfigurable device for each cluster obtained at the second stage. This stage aims at optimizing placement quality.The resolution of these three stages results in static scheduling of tasks in the DAGs into a limited number of reconfigurable units partitioned on the device, respecting the periodicity, precedence, dependence, and deadline constraints. This is a fundamental problem in parallel computation, equivalent to determining static multiprocessor scheduling for DAGs in a software context. As is well known, static multiprocessor task graph scheduling is a combinatorial optimization problem, and it is formulated in this paper through mixed integer programming and solved by means of powerful solvers.The paper details the spatial and temporal analyses required to check scheduling task graph feasibility and aims at determining the optimal solution in terms of schedule length, waiting time, parallel efficiency, resource efficiency, and configuration overhead. Schedulability analysis is not the focus of the present paper. However, before dealing with DAG scheduling on reconfigurable device, the rightness of the precedences and dependences between tasks within the graph and the accuracy of real-time functioning are analyzed, and a set of heuristics are performed to provide the number of reconfigurable physical units needed to ensure the existence of valid DAG scheduling. The analyses are expressed by some constraints to ensure the validity of the chosen task graph.The paper is organized as follows: Section2 presents related works of the DAG scheduling problem. Section 3 details the methodology we propose to achieve the placement and scheduling of DAGs on reconfigurable devices. Section 4 describes an illustration of our proposed methodology on a given DAG and evaluates the obtained enhancements by metric measuring of placement and scheduling quality. The conclusion and future works are presented in Section 5.


## 2. Related Works

Static multiprocessor scheduling techniques using task graphs have matured over the last years, and many powerful scheduling strategies have emerged. As this problem is known to be NP-hard [1], the main research efforts in this area focus on heuristic methods and few of them propose analytic resolutions. We have studied static and dynamic multiprocessor scheduling using DAGs in both the software and hardware contexts.In [2], Clemente et al. implement a static hardware scheduler employing efficient techniques which greatly reduce reconfiguration latencies and schedule length. Taking into account that configuration latency drastically reduces the efficiency of hardware multitasking systems, they introduce a new hardware scheduler communicating directly with the reconfigurable units and using optimization techniques: prefetch, reuse and replace while guaranteeing the precedence constraints. The prefetch technique manages in advance the reconfigurations and replacements required to improve task reuse. Reference [2] presents three algorithms for the replace technique, that is, the Least  Recently  Used, Longest  Forward  Distance, and Look  Forward+Critical(LF+C) algorithms. The paper focuses especially on LF+C to schedule graph tasks on several reconfigurable units. In order to maximize the task reuse that reduces reconfiguration latency, LF+C classifies tasks from the most critical ones in terms of required reconfiguration to the least critical ones and tries to replace the latter tasks, so that their reconfiguration does not generate any overhead during task graph execution. This advantage is ensured by the prefetch technique which reconfigures a given task during execution of its predecessors.Static multiprocessor scheduling is a very difficult problem, but genetic algorithms have successfully been applied to the search for acceptable solutions. In [3], the authors investigate scheduling for cyclic task graphs using genetic algorithms by transforming the cyclic graph into several alternate DAGs. To create an efficient schedule, the paper considers both the intracycle dependencies and the dependencies across different cycles. After unfolding the cyclic task graph for two cycles by incorporating the intercycle dependencies, the paper presents an algorithm investigating all the subgraphs extracted from a two-cycle task graph. Based on measurements such as the height and the width of the task graph, connection degree, degree of simultaneousness, and independent parts in the graph, the method evaluates the resulting subgraphs to select the configuration that best suits a chosen application and the available hardware configuration. Suitable allocation to processors is obtained by the earliest  start  time heuristic where tasks are assigned to the processor that offers the earliest start time. The employed genetic algorithm tries to optimize the schedule length which is expressed by the finishing time on all processors.In [4], Abdeddaim et al. describe a method based on a timed automaton model for solving the problem of scheduling partially ordered tasks on parallel identical machines. The proposed method formulates for each task in the graph a 3-state automaton consisting of the waiting, active, and finish states. Therefore, by searching the tasks related by a partial order in the graph, the possible disjoint chains in the graph are extracted. The automaton of every chain is constructed using the individual task-specific automaton. The global automaton is then composed by the chain-specific automata and takes care that the transitions do not violate the precedence, and resource constraints. Thus, optimal scheduling consists in finding the shortest path in the timed automaton. The proposed methodology is also extended to include two additional features in the task-specific automaton which are the release and the deadline times.Integer linear programming (ILP) formulation is exploited in some works of static multiprocessor scheduling using task graphs. The authors of paper [5] propose an exact ILP formulation to perform task graph scheduling on dynamically and partially reconfigurable architectures and that minimizes schedule length. In addition, this work proposes a dynamic reconfiguration-aware heuristic scheduler called NAPOLEON, which adopts an ALAP (as late as possible) order of tasks and exploits configuration prefetching, module reuse, and antifragmentation techniques. Both methods are extended to the Hw/Sw codesign. The ILP formulation is based on nonpreemptive tasks, allows the execution of tasks on software processors or on the FPGA, and respects the FPGA physical constraints as well as the precedence and temporal constraints in the graph. Both methods provide a solution for the complete scheduling of the DAG and determine for each task its Sw or Hw execution unit, its time of reconfiguration start, its position on FPGA, and its execution starting time.Another exact ILP formulation for performing task mapping and scheduling on multicore architectures is presented in [6]. The technique of these authors incorporates loop level task partitioning, task transformations by using loop fusion and loop splitting, and it aims at reducing system execution time. The paper focuses on an ILP-based approach for task partitioning, task mapping, and pipelined scheduling while taking data communication between processors into consideration for DSP applications on the multicore platform. The authors in [6] divide the problem into two parts. The first assigns and schedules tasks on processors by including the task merging on the same batch and the replication of batches to several processors. The second step conducts a mapping of data to memory architecture by minimizing memory access latencies.In [7], Sandnes and Sinnen consider the scheduling of iterative computing that can be represented by cyclic task graphs. In order to avoid costly classic graph unfolding and to shorten the makespan during scheduling, the authors propose a new strategy for transforming cyclic task graphs into acyclic task graphs; an efficient scheduling from the literature named Critical  Path/Most  Immediate  Successor  First (CP-MISF), proposed by Kasahara and Narita in 1985, is then applied to the transformed graph. The strategy is based on a decyclification step involving three parts: (1) a decyclification algorithm for transforming the cyclic graph into an acyclic graph based on a given start node and depth first search (DFS) strategy, (2) by assuming that the critical path in the graph is a good estimator for its schedule length, it searches the start node that yields the shortest critical path in the transformed graphs, and (3) quantifying the acyclic graph quality in terms of makespan. In addition, based on an adjacency matrix representing the graph dependencies and simplifying the unfolding formulation, the paper presents a new intuitive graph unfolding formulation which decomposes the adjacency matrix into two matrices, one for intraiteration dependences and another for interiteration dependences. The unfolded graph is then scheduled using a genetic algorithm approach.In [1], Djordjević and Tošić propose a new compile-time single-pass scheduling technique applied for task graphs onto fully connected multiprocessor architectures called chaining and which takes into account communication delays. The proposed technique consists in a generalized list scheduling with no preconditions concerning the order in which tasks are selected for scheduling. The main idea is to build an heuristic providing a trade-off between maximizing parallelism on processors, minimizing communication overheads, and minimizing overall execution time of the task graph. Chaining technique uses nonpreemptive tasks and constructs a scheduled task graph incrementally by scheduling one task at each step. The intermediate partially scheduled task graphs are obtained by selecting a nonscheduled task at each step and by placing it on the most appropriate precedence edge. The policy of selection of tasks to be scheduled is based on a Task  Selection  First heuristic, and the selection of the most suitable valid edge where the task will be placed is guided by the critical path and edge width criteria. The tasks encompassed within the same chain are scheduled on the same processor.In [8], the authors aim at improving the performance of hardware tasks on the FPGA. Intertask communication and data dependences between tasks are analyzed in order to reduce configuration overhead, to minimize communication latency, and to shorten the overall execution of tasks. The work exploits the proposed works in reconfigurable computing and addressing resource efficiency to present three algorithms. Reduced  Data  Movement  Scheduling (RDMS) is the most efficient dynamic algorithm for reducing configuration and communication overheads and provides the optimal performance for scheduling tasks in DAGs on the FPGA. RDMS uses the total reconfiguration of the FPGA and tries to minimize the number of reconfigurations by grouping communicating tasks in the same configuration. By conducting a width search, RDMS schedules tasks while respecting their data dependences. RDMS is based on dynamic programming algorithm and ensures that each configuration includes the combination of tasks that exploits the hardware resources to the maximum and that encompasses the highest possible number of task dependences.In [9], Fekete et al. consider the optimal placement of hardware tasks in space and in time on the FPGA. Tasks are presented as three-dimensional boxes in space and time. The authors integrate intertask communication expressing data dependence and use a graph-theoretical characterization of the feasible packing determined by means of a decision of an orthogonal packing problem with precedence constraints. By searching the transitive orientations and by performing projections, the authors of paper [9] transform the 3D boxes representing tasks into 3×1D arrangements and then verify whether the three obtained arrangements referred to as packing classes satisfy the conditions of the feasible packing and determine the optimal spatial and temporal packing. This work enhances the makespan of the graph and optimizes the used reconfigurable space on the FPGA.The major contribution in [10] is the development of a multitasking microarchitecture to perform a dynamic task scheduling algorithm on reconfigurable hardware for nondeterministic applications with intertask dependences which are not known until runtime. The task system is modeled as a modified directed acyclic graph which contains directed data edges and directed control edges labeled with scalar values indicating the probability of occurrence of the corresponding sink task in multiple task graph iterations [10]. Based on dynamic priority assignment for nonpreemptive tasks, the dynamic scheduler assigns each task to a software or hardware processing element, schedules the contexts (bitstreams) and the data, and the fetch and the prefetch reconfigurations, and activates task execution. In order to minimize reconfiguration overhead, the dynamic scheduler uses the configuration prefetching technique to prefetch the task bitstream ahead of time or exploits the previous context configured in the logic cell. In addition, it aims to minimize application execution time by employing a local optimization technique.In [11], Kohler defines a new heuristic to schedule DAGs on a system of independent identical processors. The author describes a simple critical path priority method which is shown to be optimal or near optimal in the most randomly generated computation graphs compared to the Branch and Bound method. This heuristic aims to minimize the finishing time of the computation graph. Critical path scheduling is based on a list (L) containing permutation of the tasks. Any time a processor is idle, it instantaneously scans the list L from the beginning and begins to execute the first free task which may validly be executed because all its predecessors have been completed [11]. The construction of the list is based on the critical path of tasks which is defined by the longest path from a given task to a terminal node. The paper also presents the exact Branch and Bound method used to obtain optimal scheduling, and the results obtained are compared to the critical path heuristic to prove the high quality of the latter method.Table1 provides a summary of the optimization parameters and employed techniques described in the cited works.Table 1
Optimization parameters and techniques for scheduling works.
ReferencesMakespan/Speedup/Parallel efficiencyResource efficiencyConfiguration overheadTechniques[2]xxPrefetch/replace/reuse of reconfigurations[3]xGraph unfolding/genetic algorithm/earliest  start  time heuristic[4]xTimed automaton model/shortest path[5]xx(1) ILP/reuse(2)NAPOLEAN/ALAP/prefetch/reuse/antifragmentation[6]xILP/loop level task partitioning/task transformation (loop fusion + loop splitting)/task mapping and scheduling (task merging on batches + batch replication)/data mapping[7]x(1) Graph decyclification (DFS + shortest critical path)/CP-MISF(2) Graph unfolding/genetic algorithm[1]xChaining/task selection first heuristic/critical path/edge width/communication latencies[8]xxxDynamic programming algorithm/FPGA total configuration[9]xxOrthogonal packing problem/packing classes[10]xxPrefetch/local optimization/reuse[11]xCritical path heuristic/Branch and BoundThe major common drawback of most described techniques is that they do not address real-time constraints. Furthermore, as shown in Table1, most of them seek to optimize the makespan of the graph and neglect reconfiguration overhead and resource inefficiency or do not optimize the three parameters simultaneously. The works described in [8, 9] that conduct scheduling of DAGs on FPGA devices are based on successive total configurations of the device. Their resource efficiency consists only in the packing the maximum of tasks in the DAG on the FPGA in order to efficiently exploit the reconfigurable resources as well as to perform the minimum of total configurations. These works therefore do not consider the internal fragmentation caused by task placement on the FPGA which represents resource efficiency in our work.In the context of hardware task scheduling, in the proposed works, the placement of scheduled tasks is not considered. Either the placement of the task is allowed in whatever position in the device (in this case, they do not take into account device heterogeneity) or the task is fixed to a unique reconfigurable unit which will reduce application flexibility. Contrary to these works, our strategy may be generalized for all types of devices, that is, both homogeneous and heterogeneous devices; the placement problem is considered an important stage, that is, highly interlinked with the scheduling of task graphs on the reconfigurable device. With our strategy, the task may be executed on several reconfigurable units according to its resources and according to the analyses conducted during the clustering stage.Moreover, some of the described works do not exploit the relevant concept of run-time partial reconfiguration afforded by recent reconfigurable devices and employ the total configuration of FPGAs.Based on these observations, our challenge is to utilize the benefits of the run-time partial reconfiguration concept for recent heterogeneous devices. The concept opens up the possibility of developing a hardware multitasking system by dividing the reconfigurable area into smaller reconfigurable units and by customizing them as required by the running application.Considering multitasking, scheduling of task graphs on reconfigurable hardware devices is similar to heterogeneous multiprocessor scheduling in the software context. With full knowledge of the characteristics of DAG tasks and technology features, our methodology targets constrained applications and endeavors to provide pipelined scheduling in multi-reconfigurable-unit system while optimizing schedule length, waiting time, parallel efficiency, resource efficiency, and configuration overhead.


## 3. Proposed Methodology for Placement and Scheduling of Dags on Reconfigurable Devices

Our methodology can be viewed as two separate subproblems: (i) the mapping and scheduling of hardware tasks on predefined clusters by satisfying periodicity, precedence, dependence, and deadline constraints and (ii) the placement of obtained clusters on reconfigurable device taking into account its heterogeneity. Our resource and task management is essentially based on features of hardware tasks and reconfigurable hardware devices. The most recent Xilinx’s Virtex FPGA was used as a reference for the reconfigurable hardware device to perform the placement and scheduling of the DAGs. Virtex SRAM-based FPGAs are characterized by a column-based architecture, a high density of heterogeneous resources, and several parallel configuration ports functioning at a high speed.


### 3.1. Terminology and Definitions

Throughout the paper,NT refers to the number of tasks in the graph, NZ the number of clusters, and NP the number of resource types in the chosen technology. The directed acyclic task graph is denoted by the pair (N,E). N is the set of nodes representing tasks in the DAG, and E is the set of edges linking the dependent tasks, E⊆N×N.As shown in Figure3, on each edge, the outgoing value (xA,B) from the source node A to the sink node B depicts the amount of data that A must produce at each repetition for B. The incoming value (yB,A) represents the amount of data that must be consumed by the sink node B at each execution iteration after completion of the repetition of its predecessor A.Figure 3
Directed acyclic graph.Each task in the graph has three models as follows.


#### 3.1.1. Functional Model

Each hardware task(A) is represented by a set of parameters fixed at compile time and which are kept static throughout the DAG execution. A is characterized by its worst-case execution time (CA), its period (PA), which is equal to its relative deadline (DA), and a set of preemption points (PreempA,l). The preemption points are instants of the time taken throughout the worst-case execution time as shown in Figure 4. The number of preemption points of task A is denoted by NbrPreempA. This number also includes the first point of execution of the task. The set of preemption points is determined by the designer according to the known states in the behavioral model and according to possible data dependences between these states. The predefinition of preemption points gives rise to the execution sections within the hardware task. Our methodology is based on preemptive modeling to create a reactive system, to increase flexibility towards application needs, and consequently to enhance the respect of real-time constraints.Figure 4
Predefined preemption points in TaskA.


#### 3.1.2. Behavioral Model

This includes the finite state machine controlling each task and which handles a set of registers or a small memory bank useful for context switching during preemption. The latency required to preempt and to resume the execution of tasks is disregarded as in the worst case; the time to access the system bus and memory is negligible. With the preemptive model, we do not use the classical method of readback and load modified bitstream since latency with this method is significant; it complicates preemption and requires a large space memory. With the classical method, a new readback bitstream must be saved at each preemption. With our model, the number of preemptions within tasks is limited by specifying the possible preemption points according to task states outside of which preemption is not allowed. Thus, we resort to saving/loading the current state of the finite state machine with an acceptable amount of data by maintaining the same bitstream for each task within a given reconfigurable unit when the task needs to be preempted or resumed. Preemption points of hardware tasks are set in a way that reduces the data dependences that could exist between two states. In fact, maintaining a preemption point between two states processing the same data must be avoided because these data need to be saved into an external memory which might increase the preemption overhead at runtime. Otherwise, it is recommended to insert a preemption point when the task is in a blocked state, waiting to receive an external resource to enable the ready tasks to be executed in the reconfigurable unit. In the finite state machine, the longest execution time between two states must be considered in order to deduct the worst-case execution time.


#### 3.1.3. RB-Model

At the physical level, tasks are presented as a set of reconfigurable resources called reconfigurable blocs (RB). RBs correspond to the physical resources in the reconfigurable hardware device required to achieve execution of the hardware task, and they define the RB model of the task as expressed by (1). Determination of the RB-model of hardware tasks is well detailed in our work described in [12]. The number of RB types is equal to the number of resource types in the chosen technology. The RBs are the smallest reconfigurable units in the hardware device. They are determined according to the available reconfigurable resources in the device, and they closely match its reconfiguration granularity. Each type of RB is characterized by a specified cost, RBCostk, defined according to its frequency in the device, its power consumption, and the importance of its functionality,(1)A_RB={αA,kRBk},αA,k∈N,1≤A≤NT,1≤k≤NP.The reconfigurable device is also characterized by its RB model as shown in our work described in [12] to enable the placement of hardware task clusters at a later stage.The three main stages of the methodology used for static scheduling of DAGs on multi-reconfigurable-unit system with predefined constraints are described below.


### 3.2. Hardware Task Clustering

This stage comprises two steps that are performed consecutively: (i) reconfigurable zone type search and (ii) costD computing. Bearing in mind that the concept of run-time partial reconfiguration had to be used, our main objective at this first stage was to partition tasks constituting the graph into cluster types determined according to their required RB types in order to enhance resource utilization.


#### 3.2.1. Reconfigurable Zones Types Search

This step takes as input the RB model of each task in the DAG, and by performing Algorithm1 of the worst-case complexity O(NT2*NP), it groups tasks sharing the same types of RBs under the same type of cluster by taking the maximum number of RBs between these tasks. With our methodology, the obtained types of clusters are denoted as reconfigurable zones (RZs). The upper bound of the possible RZs is NT. Thus, RZs are virtual units customized by Algorithm 1 to model the classes of hardware tasks in terms of RB types. RZs separate hardware tasks from their execution units on the reconfigurable device. In the last stage of our proposed methodology, RZs will be placed on their suitable reconfigurable units respecting the heterogeneity of the device and optimizing resource efficiency as well as configuration overhead. After the completion of Algorithm 1, each RZ is represented by its RB model as expressed by (2)RZj_RB={βj,kRBk},βj,k∈N,1≤j≤NZ,1≤k≤NP.
Algorithm 1 processes the tasks of the DAG as follows. It scans the RB model of each hardware task and checks whether an already inserted type of RZ that closely matches the required types of RBs in the task exists in the RZ types list, list-RZ (line 6). Should this be the case, Algorithm 1 updates the number of RBs within this type of RZ by the maximum between the number of RBs in the task and that in the RZ (line 9).Algorithm 1:RZ types search or hardware task classes search.
(1)RZ-type=0 // RZ types(2)List-RZ // list of RZ types(3)n // natural(4)for  all  tasks A  do(5)   //A_RB=αA,kRBk(6)if  ((RZ-type≠0)  and  (∃n,1≤n≤RZ-type)/∀k((αA,k≠0andβn,k≠0)  or  (αA,k=0andβn,k=0)))then(7)    // this test checks whether the task matches with an RZ type that already exists inlist-RZ(8)for  all  k  do(9)βn,k=max(αA,k,βn,k) // update RB number of RZn(10)end  for(11)else(12)    IncrementRZ-type(13)RZRZ-type=CreatenewRZ(αA,k) // new type of RZ, RZRZ-type={αA,kRBk}(14)    Insert (list-RZ, RZRZ-type)(15)end  if(16)end  forIf the required types of RBs in the task do not match any type of RZ included in thelist-RZ, the algorithm of the search of RZ types decides on the creation of a new type of RZ as required by the task (lines 12, 13) and inserts it in list-RZ (line 14).Figure5 is an example of the execution of Algorithm 1 for the RZ types search for DAG comprising five tasks. Figure 5 illustrates the search for RZ types resulting from five tasks in a technology including four types of RBs (RB1, RB2, RB3 and RB4). A and C are grouped in the same type of RZ (RZ1) as both need RB1 and RB2, and the number of each RB type within RZ1 is adjusted by the maximum number of RBs between A and C. Similarly, RZ2 is created by B and D, and E defines the third type of RZ (RZ3).Figure 5
Example of the search for RZ types.After searching for the set of RZs, the configuration overhead for each obtained RZ is computed and denoted byConfigj. Configj corresponds to the configuration overhead to fit RZj in the target technology. This configuration overhead is computed by the floorplanning of each RZj on the chosen device and by conducting the whole partial reconfiguration flowup to the creation of the partial bitstream. Configj is determined by (3) according to configuration frequency and configuration port,(3)Configj=sizeofbitstream(Configuration frequency×configuration port width).


#### 3.2.2. CostD Computing

This step commences by computing costD between tasks and each RZ type resulting from the first step. Cost D represents the differences in RBs between tasks and RZs; consequently, it expresses resource wastage when a task is mapped to an RZ. Based on RB models of task A and RZ RZj, cost D is computed according to two cases as follows. Firstly, we define by (4)dA,j,k=αA,k-βj,k,1≤A≤NT,1≤j≤NZ,1≤k≤NP.Case 1.
For allk, dA,j,k≤0, RZj contains a sufficient number of each type of RB (RBk) required by A, and cost D is equal to the sum of the differences in the numbers of each RB type between A and RZj weighted by RBCostk as expressed in
(5)D(A,RZj)=∑1≤k≤NPRBCostk×|dA,j,k|.Case 2.
There existsk, dA,j,k>0, the number of RBs required by A exceeds the number of RBs in RZj or A needs RBk which is not included in RZj. In this case, cost D is infinite,
(6)D(A,RZj)=∞.
CostD is exploited during the stage of task mapping and scheduling on RZs and the RZ placement stage to optimize the utilization of costly resources to the device. The execution of a given task in an RZ is allowed only when the cost D between them is finite. Figure 6 illustrates the computing of costs D between the five tasks and RZ3 described in Figure 5.Figure 6
Example of computing costD with RZ3.


### 3.3. Mapping and Scheduling of Hardware Tasks on RZs

It is well known that task mapping and scheduling are highly interdependent. The two issues therefore need to be addressed together for mapping and scheduling to be efficient. In order to analyze the scheduling of a given DAG of periodic tasks, it is sufficient to study its behavior for a time interval equal to the least common multiple of all the task periods, called the hyperperiod (HP). Consequently, the possible iterations of execution of each taskA during the HP may be determined according to its period PA, which is equal to ⌊HP/PA⌋. To resolve the subproblem of mapping and scheduling of hardware tasks on RZs, our methodology conducts three steps of spatial and temporal analyses. The first one checks the rightness of task precedences, dependences, and real-time functioning in the DAG by means of three essential constraints. Consequently, the DAG will be validated to launch the following analyses. The second analysis determines the lists of ready times of each task for each possible iteration during the hyperperiod. These lists take into account the periodicity, precedence, dependence, and deadline constraints. The third straightforward analysis takes as input the lists of ready times, searches at each iteration the possible execution intervals for each task, and therefore detects possible conflicts due to overlapping between execution intervals of parallel tasks on the same RZ. The third analysis pursues its processing to solve the detected overloads within RZs by performing either the migration of execution sections of some tasks respecting their predefined preemption points or by increasing the number of overloaded RZs.


#### 3.3.1. Checking of Precedence, Dependence, and Real-Time Rightness in DAG

The first temporal analysis does not take into account spatial constraints and considers that there is an available RZ for each task. It also considers the periodicity of tasks. The main objective of this analysis is only to validate the correctness of task precedence and dependences and real-time constraints in the studied DAG. It is conducted by means of three essential constraints.(a) Dependence Checking
More than precedence, we consider that the tasks related by an edge of precedence are also dependent. This means that the execution of a given task requires the data resulting from the execution of all its predecessors. This dependence is expressed by (7). Equation (7) focuses on periods and the amount of interchanged data between dependent tasks. It guarantees, when PA≥PB and A∈ΠB, that each data (xA,B) produced by task A in its repetition Ai is consumed by its successor B during its iterations of execution Bi or Bj>i. When PA≤PB and A∈ΠB, at each iteration of execution of B, it ensures that there are the sufficient data (yB,A) for B to be executed. 											(7)yB,A×⌊HPPB⌋=xA,B×⌊HPPA⌋,∀B,A∈πB.The previous equation eliminates the problem of data wastage and ensures that the data produced by all the iterations of each task are consumed by all the iterations of its successors. In this work, we focus on the case where PA≥PB, for all B,A∈πB.(b) Precedence Checking
As we work in the case ofPA≥PB, for all B,A∈πB, considering the periodicity constraint, this constraint claims that each iteration of execution Ai of a given task A may include only the iterations Bi or {Bj<i} of its successors {B} to ensure the correctness of the precedence constraint. During repetition Ai of a given task A, this constraint prohibits that Bi and {Bj>i} repetitions of its successors {B} coexist. In this way, during the HP, each ith execution of any task is preceded by the ith execution iterations of all its predecessors. To guarantee these rules, the following constraint expressed by (8) was developed to guide the selection of execution times and periods for tasks in the DAG:
(8)TreadyB+k×PB>TreadyA+(k-1)×PA,∀B,A∈πB,k∈N,1≤k≤NbrIterA.NbrIterA depicts the possible number of execution iterations of A during the HP. TreadyA and TreadyB are the ready times for tasks A and B without considering the spatial constraints. They are determined by searching the critical path corresponding to the task in the graph by using the ASAP (as soon as possible) technique. For each task B having a set of predecessors {A}, its ready time TreadyB is computed as follows
(9)TreadyB=max⁡{A∈πB}⁡(TreadyA+CA),TreadyB=0,ifπB=∅.(c) Real-Time Checking
Considering the periodicity constraint, this constraint analyses the respect of real-time constraints in the best case of spatial conditions in terms of number of RZs. By respecting the precedence and dependence constraints, (10) checks at each iteration whether each task may complete its execution before its strict absolute deadline. If the absolute deadline of the task for its last iteration exceeds the HP, the deadline then turns into the HP. As we work in the case PA≥PB, for all A∈πB, the second expression of (10) satisfies the deadline constraint for the remaining repetitions of task B when its predecessors {A} achieve all their execution iterations
(10)max⁡(TreadyA+k×PA+CA,TreadyB+k×PB)+CB≤min⁡⁡(TreadyB+(k+1)×PB,HP),∀B,A∈πB,k∈N,0≤k≤NbrIterA-1,TreadyB+k×PB⁡+CB≤min⁡⁡(TreadyB+(k+1)×PB,HP)∀B,k∈N,max⁡A∈πB⁡(NbrIterA)≤k≤NbrIterB-1.
Respect of the three previous constraints validates the selection of periods and execution times for periodic tasks in the graph for the scheduling with precedence, dependence constraints, and under strict real-time constraints on an unlimited number of reconfigurable units. Nevertheless, the following temporal and spatial analyses will extract the corresponding number of RZs that will satisfy these constraints. When the previous constraints are unreal, the DAG is considered invalid and consequently it will be rejected or the features of its tasks will be modified and evaluated again till it respects the constraints expressed by (7), (8), and (10).
Consequently, with our methodology, we depart from the temporal analysis to construct a suitable physical architecture allowing a feasible schedule. As a final step at this stage, after fixing the physical architecture of the multi-reconfigurable-unit system, analytic resolution of mapping/scheduling provides the optimal scheduling of DAGs on target technology.


#### 3.3.2. Determination of Lists of Ready Times

The temporal analysis does not consider the physical constraints and searches all the ready times in each execution iteration for all tasks in the graph by respecting the precedence, dependence, periodicity, and real-time constraints. This analysis yields, by means of (11), the lists {TreadyminBi,…,TreadymaxBi} during which task B may start execution, where Bi denotes the ith iteration of task B within the HP. Outside this list, task B might not respect the predefined constraints, which would lead to unfeasible scheduling.For each taskB, TreadyminBi is the lower bound time to start task execution at its iteration i in order to respect its precedence, dependence, and periodicity constraints. TreadymaxBi is the upper bound time from which the task can no longer start execution if its strict deadline and the data dependency and precedence of its successors are to be respected. To compute the Treadymin of tasks, we start computing from the top of the DAG. For the Treadymax calculation, we start from the bottom of the DAG, and for both, we proceed using the breadth-first search strategy(11)TreadyminB1=0ifπB=∅,TreadyminBi=max⁡(max⁡A∈πB⁡(TreadyminAi+CA),rminBi),TreadymaxB1=min⁡(min⁡A∈φB⁡(TreadymaxA1),PB)-CB,φBisthesetofsuccessorsofB,TreadymaxBi/i>1=min⁡(min⁡A∈φB⁡(TreadymaxAi),rmaxBi+1,HP)-CB.rminBi and rmaxBi are the start times of the ith repetition of B according to its first ready times (TreadyminB1 and TreadymaxB1). Hence, they are determined by incrementing TreadyminB1 and TreadymaxB1 by PB. For example, if we have a task B with a period = 8, a hyperperiod HP=24, and we consider TreadyminB1=3 and TreadymaxB1=4, then rminB1=TreadyminB1=3, rminB2=3+8=11, rminB3=11+8=19, rmaxB1=TreadymaxB1=4, rmaxB2=4+8=12, rmaxB3=12+8=20.


#### 3.3.3. Determination of Task Execution Intervals and the Number of RZs

This temporal and spatial analysis considers the RZ types resulting from the task clustering stage and searches the possible parallelism between tasks to study execution conflicts on the RZs. When an overload is detected in some RZs, the analysis starts by solving this problem through a migration mechanism; if migration does not produce a solution, it increments the number of overloaded RZs as required. This analysis searches first, by means of Algorithm2, the execution intervals of each task for each possible iteration during the HP, then, using Algorithm 3, it deals with the overlapping execution intervals on the RZs to search the possible overloads, and finally, it uses Algorithm 4 to try to solve the found overloads by the migration mechanism; when this latter mechanism fails, additional RZs are inserted in the architecture of the multi-reconfigurable-unit system to solve the persisting overloads.Algorithm 2:Search of execution intervals.
(1)A,B // Tasks(2)i // Natural, iterations of execution of task A(3)List-TreadyAi // the list of ready times for task A during ith iteration(4)TreadyAi // the ready times for task A during ith iteration(5)TreadyA // the ready times for task A from the current TreadyAi(6)Execution-IntervalAi=⊘ // the set of execution intervals for task A during ith iteration(7)for  all  tasks A  do(8)for  all  execution iterations i of task A  do(9)List-TreadyAi={TreadyminAi,…,TreadymaxAi}(10)if  i=1  then(11)Execution-IntervalAi = {[TreadyAi,min(TreadyAi+PA,minB∈φA(TreadymaxBi),HP)],∀TreadyAi∈List-TreadyAi}(12)else(13)for  all  TreadyA1∈List-TreadyA1  do(14)TreadyAi = First (List-TreadyAi)(15)for  all  TreadyA∈{TreadyAi,…,TreadymaxAi}  do(16)Execution-IntervalAi=Execution-IntervalAi⋃{[TreadyA,min(TreadyA1+i*PA,minB∈φA(TreadymaxBi),HP)], if TreadyA1+i*PA is chosen as upperbound for this interval then it must respect: TreadyA+CA≤TreadyA1+i*PA, if HP is chosen then it must respect: TreadyA+CA≤HP}(17)end  for(18)List-TreadyAi = next (List-TreadyAi)(19)end  for(20)end  if(21)end  for(22)end  forAlgorithm 3:Search of overlapping execution intervals and RZ loads.
(1)A,B,D // Tasks(2)i, j, k, m // Natural, iterations of execution of tasks(3)Execution-IntervalAi // The set of execution intervals for task A during ith iteration(4)Crossing-Combination // All the possible combinations of sets Execution-IntervalAi of distinct tasks that giveoverlapping execution intervals on a given RZ, duringHP(5)Comb // Combination of overlapping execution intervals depicted by [A-min, A-max](6)CDr // The remaining execution time within task D(7)PDr The remaining period within task D(8)Pmax // The period of conflict for a combination of overlapping execution intervals(9)for  all  iteration i  do(10)for  all  RZ  do(11)Crossing-Combination = {{Execution-IntervalAj}/⋂j≤iExecution-IntervalAj≠⊘}(12)Comb = one combination of overlapping execution intervals extracted from sets in Crossing-Combination.(13)for  all  Comb in Crossing-Combination  do(14)    InComb, search the latest tasks {B} in starting execution(15)    InComb, search all the remaining tasks {D} that are ready or start execution before {B} and determinetheir remaining execution times:CDr and their remaining periods: PDr(16)CDr=CD-(B-min-D-min)(17)PDr=PD-(B-min-D-min)(18)if  (∀D-min, D-min = TreadyD1+(k-1)*PD, ∀D-max, D-max=TreadyD1+k*PD, ∀B-min,B-min = TreadyB1+(m-1)*PB and ∀B-max, B-max = TreadyB1+m*PB/TreadyD1∈{TreadyminD1,…,TreadymaxD1}, TreadyB1∈{TreadyminB1,…,TreadymaxB1}, and k and m are theiterations from which the execution  intervals are taken respectively for tasks{D} and {B})  then(19)RZ-Load = ∑DCDr/PDr + ∑BCB/PB(20)else(21)Pmax=maxD(D-max-B-min)(22)RZ-Load = ∑DCDr/Pmax + ∑BCB/Pmax(23)end  if(24)end  for(25)end  for(26)end  forAlgorithm 4:Total and partial migration or addition of RZs.
(1)Comb // Combination of overlapping execution intervals(2)Non-overload-comb // Boolean controlling after migration whether RZ is no longer overloaded by Comb(3)RZ-Load// Load of the RZ corresponding to Comb(4)RZ-migration // The set of RZs helpful for partial migration(5)Task-migration // The set of tasks that might perform partial migration(6)for  all  Comb giving overloaded RZ  do(7)Non-overload-comb= False(8)while  (Non-overload-comb = False) and (Comb≠⊘)  do(9)    // Total migration of tasks(10)Select the interval from Comb that gives the most heavy occupation rate and discard it from Comb.(11)Check whether the iteration, corresponding to the execution interval of the selected task, is studied on anothernon-overload RZ and update the load of the overloaded RZ after the elimination of the selected task.(12)if  RZ-Load≤1  then(13)Non-overload-comb= True(14)end  if(15)end  while(16)if  Non-overload-comb=False  then(17)   ReinitializeRZ-Load and Comb with its tasks(18)Task-migration=⊘(19)RZ-migration=⊘(20)   // Partial migration of tasks(21)   Omit the tasks from the overloaded RZ, corresponding toComb, that are also acceptable by another RZs (D≠∞) andreduce their occupation rates from the loads of these RZs. These latter RZs with the overloaded RZ corresponding toComb are included in the set RZ-migration. The omitted tasks are included in Task-migration(22)while  Task-migration≠⊘  do(23)    InTask-migration set, start by the task that gives the best trade-off between least number of RZs in RZ-migrationwhere it could migrate and heaviest occupation rate in the overloaded RZ.(24)    DuringComb, within the selected task, choose the biggest execution sections that could be placed in RZs from thesetRZ-migration without overloading them.(25)    Update the load of RZs receiving execution sections from the selected task(26)if  Some execution sections of the selected task are not placed  then(27)     Reinitialize the loads of RZs inRZ-migration to values before processing Comb(28)     Increment the number of RZ corresponding toComb up to ⌈RZ-Load⌉, go to 6(29)else(30)     Discard the selected task fromTask-migration.(31)end  if(32)end  while(33)   // All the execution sections of tasks are placed(34)Non-overload-comb=True(35)end  if(36)end  for(a) Search of Execution Intervals
This step uses the functional model of tasks and determines their execution intervals by means of Algorithm2 of worst-case temporal complexity equal to O(NT*HP3). An execution interval for a given task at a given iteration is an interval during which the task can be executed while satisfying all the predefined constraints.
For each taskA in the DAG, Algorithm 2 produces the set of its possible execution intervals expressed by Execution-IntervalAi at each possible iteration i during the HP. When this algorithm processes the first iteration of task A, the set of its possible execution intervals is determined directly (line 11) considering the precalculated ready times in List-TreadyA1, and the periodicity and dependence constraints. For the next iterations, considering each possible TreadyA1 for the purpose of respecting the periodicity constraint (line 13), at each iteration i, Algorithm 2 searches all the corresponding execution intervals starting with each possible TreadyAi (line 14, line 15), and considering the dependence and the deadline constraints, and the HP to determine the upper bound for each execution interval (line 16). In line 18, in order to guarantee the periodicity and dependence constraints, progressing from a TreadyA1 to another in list List-TreadyA1, Algorithm 2 must shift the list List-TreadyAi by omitting its first element, since ready times in each iteration i are also linked to the ready times of the first iteration.(b) Search of Overlapping between Execution Intervals of Tasks in the Same RZ
For the first iteration, the parallel tasks on a given RZ are extracted directly from the DAG; hence, there is no parallel execution between a given task and its successors. However, in the next iterationsi, searching parallel tasks must respect some rules. For the next iterations i, for parallel efficiency, a given task could overlap with its successors during their iterations j(j<i) on the same RZ. Moreover, this step must also consider the execution conflicts on the same RZ for a given task in its iteration i and other tasks that are in the iterations j(j≤i) when there are no dependence constraints between them. This step prohibits simultaneous execution of several iterations of the same task.
The step defines for each task the possible RZs allowing its execution in terms of types and number of RBs based on computed costD and then searches the execution conflicts on the RZs using Algorithm 3. Algorithm 3 has a worst-case temporal complexity equal to O(NZ*2NT*HP).
During each iterationi, for each RZ, in order to find the parallel tasks with a finite cost D with the RZ, Algorithm 3 searches all the possible combinations of sets of execution intervals {Execution-IntervalAj} of all the tasks that can be executed on the current RZ and produce overlapping execution intervals respecting the rules described above (line 11). Then, from the resulting sets of execution intervals, Algorithm 3 extracts the execution intervals causing the conflicts in the current RZ which will result in Comb (line 12). Comb may contain two or more tasks. Each obtained Comb is processed individually to study the load of the RZ (line 13–line 24). For each Comb, we start the study only at the time at which all the tasks coexist to check for possible conflict and its consequence on the current RZ. Thus, Algorithm 3 searches the latest tasks {B} in Comb (line 14) and for tasks {D} that either have already started their executions and still running after {B} arriving or have been ready before {B} arriving; it searches their remaining execution times and periods (line 15–line 17) by promoting the tasks with the earliest deadlines and using the ASAP technique, especially in the case there are more than two tasks within the Comb. Finally, Algorithm 3 computes the load of the current RZ for this current Comb according to two cases. In the first case (Case 1, line 18-line 19), the remaining tasks with their new execution time values and periods are considered as virtual new tasks, and if their execution intervals in Comb corresponds to their total periods, Algorithm 3 intuitively computes the load of the RZ as mentioned in line 19 by considering the occupation rate (CA/PA) of each virtual new task A and each latest task {B} in Comb on the current RZ.
In the second case (Case2), the longest period of time (Pmax) that could be shared by the tasks in Comb is determined in line 21 and the load of the RZ is studied during Pmax (line 22).
This step deals with all possible cases of execution conflicts on all the RZs. At the end of this step, we obtain at each iteration during the HP, the loads of each RZ produced by each combination of tasks giving overlapping execution intervals. Consequently, we can detect the possible overloads in the RZs(RZ-load>1). Some combinations might be included within other ones. When overloads are detected on some RZs, the next step resolves the problem either by performing migration of tasks respecting their preemption points or by incrementing the number of overloaded RZs until the overloads are covered.(c) Task Migration or Addition of RZs
Migration of tasks causing an overload on a given RZ during a combination of simultaneous executions might be total or partial. Total migration consists in replacing the entire execution of one or many tasks on another RZs. Partial migration consists in the reallocation of some execution sections within tasks predefined by their preemption points to nonoverloaded RZs. The migration is performed as explained by Algorithm4. The worst-case temporal complexity of Algorithm 4 is O(2NT*HP*NT*NZ). Algorithm 4 searches the combinations producing overloaded RZs obtained by Algorithm 3 (line 6). Firstly, Algorithm 4 starts by total migration (line 8–line 15) to avoid the preemption of tasks resulting in difficulties related to context switches. During each Comb causing overload, the algorithm extracts the execution interval of the task that provides the largest occupation rate in the current Comb (line 10). In the case of equality between tasks, the task producing the fewest RZs for total migration during the Comb should be selected. The algorithm then determines the execution iteration of the task corresponding to this extracted interval and checks whether the iteration is also studied in another nonoverloaded RZs. Should this be the case, total migration of the task is allowed, and the task is eliminated from the overloaded RZ (line 11). If there are several RZs accepting total migration of the selected task, the RZ which is least required by tasks in the Comb is chosen. In cases of equality, the least loaded RZ is kept. After each total migration of a task, Algorithm 4 updates the load of the RZ corresponding to Comb and checks whether it is no longer overloaded (line 12–line 14). When total migration fails to resolve the overload in the RZ, partial migration takes place (line 16–line 35). Partial migration reinitializes the load of the current RZ corresponding to Comb. It searches the tasks in Comb that give finite D with other RZs and omits their occupation rates from the combinations on these latter RZs and from the current overloaded RZ considering the iteration of each task in Comb and includes the omitted tasks in the set Task-migration. The RZs accepting the tasks of Comb and the RZ corresponding to Comb are inserted within the set RZ-migration (line 21). Algorithm 4 attributes weights to tasks within Task-migration according to their occupation rates in Comb and according to the numbers of RZs in RZ-migration producing finite D with them. The task yielding the best trade-off between the two parameters is selected (line 23). Within the selected task, partial migration tries to reallocate its predefined execution sections in RZs from RZ-migration without causing an overload (line 24). Partial migration promotes the biggest execution sections respecting this rule. It starts by placing the selected execution section on the RZ which is least required by the other tasks in Task-migration waiting for partial migration. In cases of equality, it starts with the least loaded RZ in RZ-migration. Algorithm 4 pursues the processing of these partial migrations until the set Task-migration is empty. If partial migration does not successfully map all the execution sections of a given task in Task-migration (line 26), Algorithm 4 reinitializes the loads of the RZs to their initial values before processing the Comb (line 27), stops its processing for the current Comb, and increments the number of the corresponding RZ to ⌈RZ-Load⌉ (line 28). When a given overloaded Comb is resolved by partial migration, Algorithm 4 takes into account the update of loads of all altered RZs (line 25) to be considered for the next Comb. Although migration might resolve many overloads for several combinations, it is still very difficult to perform as it is exhaustive and depends on the initial choices of tasks and RZs. One could consider the best case of studied migrations to minimize the number of added RZs. After each increment of RZ, the step must consider the added RZs to deal with the overloads of the remaining Comb not yet processed to avoid an excessive number of unusable RZs. As the proposed algorithm of migration is not exact, it might lead to an excessive number of RZs. This problem will be covered during resolution of mapping/scheduling which also optimizes the number of used RZs for the purpose of resource efficiency. However, an excess of RZs is very useful as it guarantees elimination of the infeasibility of analytic resolution and consequently, and it guarantees the feasibility of scheduling of the DAG.
At the end of this step, the number of RZs required to perform the scheduling of the chosen DAG on the FPGA is obtained. The resulting RZs constitute the target multi-reconfigurable-unit system where the scheduling of DAG will be conducted. The next step focuses essentially on determining the optimal valid scheduling that respects the predefined constraints.


#### 3.3.4. Mapping and Scheduling Resolution

In the last step of the current stage, we concentrate on the resolution of mapping and scheduling tasks in the DAG on the resulting multi-reconfigurable-unit system. Mapping and scheduling are highly interlinked. It is well known that static multiprocessor scheduling of DAGs is performed by means of two actions: (i) assignment of an execution order expressed by temporal scheduling and (ii) assignment of processors expressed by mapping, for a set of tasks characterized by precedence and real-time constraints. With our methodology, based on a preemptive model, mapping consists in assigning each task to the most suitable RZs in terms of utilization of costly resources. Mapping is considered as spatial scheduling to a limited number of heterogeneous RZs. The scheduling searches the optimal scenario for task execution on RZs during the HP. At each execution iteration for a given task, it assigns for its execution sections specific times to launch their executions on the corresponding RZs. This scheduling is valid only when it satisfies predefined temporal constraints, and it should optimize the makespan of the graph, parallel efficiency, waiting time, and schedule response time. The proposed resolution leads to global static pipelined scheduling on a heterogeneous multi-reconfigurable-unit system because it is constructed at compile time, and it allows overlapping between execution iterations of distinct tasks on distinct RZs. Moreover, the problem of mapping/scheduling is a combinatorial optimization problem as it uses a discrete solution set and chooses the best combination of feasible assignments by optimizing a multiobjective function.In this paper, resolution of mapping/scheduling is performed by mixed integer nonlinear programming solver as it is well adapted for this kind of problem. The mapping/scheduling problem is modeled by the quadruplet (constants, variables, constraints, and objective function).ConstantsNT:Number of tasks constituting the DAGNZ:Number of RZs resulting from the taskmigration or addition of RZs analysisNP:Number of RB types existing in thetarget technologyi, o:The references of iterations ofexecutions during the HPj:The references of RZsA, B:The references of tasksk:The references of RB typesl, e:The references of preemption pointsin taskst:The references of times values,t∈{0,…,∞}D(A,RZj):The costD between task A and RZ RZjRBCostk:The cost of each RB typeHP:The hyperperiod in the DAGCA:The worst case execution time of taskAPA:The period of taskA which is equal toits relative deadlineNbrPreempA:The number of possible preemptionpoints within taskAPreempA,l:The set of possible preemption pointsof taskA. The first preemption pointfor all tasks is equal to 0SectionA,l:The execution section within taskAprovided by the predefinedpreemption pointlNbrIterA:The number of execution iterationsof taskA during the HPTimesValuest:The set of possible times assigned topreemption points during the HP.It is equal to{0,…,∞}PredA,B:Binary constant takes 1 when taskAhas a precedence constraint withtaskB in the DAGDependA:Binary constant takes 1 when taskAhas data dependence constraintswith tasks in the DAGConfigj:The configuration overhead ofRZjCom:The maximum value of time fortransmitting a data of unit lengthbetween two dependent tasksyA,B:The amount of data sent byB for Aexecution.Variables
TUnicityj,A,l,t,i
Binary variable takes 1 when the preemption pointl of task A is mapped to RZj at time t at iteration i. This variable ensures the link between mapping and scheduling. In our resolution, the mapping/scheduling problem is solved when binary values are assigned to all these variables.PTimeRZj,A,l,i
This variable represents the time value assigned to preemption pointl of task A on RZj at iteration i during the HP. This variable is not defined when RZj gives infinite D with task A. It is obtained as expressed by
(12)PTimeRZj,A,l,i=∑t0≤TimeValuest≤HPTUnicityj,A,l,t,i×TimeValuest,∀1≤j≤NZ,1≤A≤NT,1≤l≤NbrPreempA,1≤i≤NbrIterA,D(A,RZj)≠∞.PTimeA,l,i
This variable provides the time value assigned to preemption pointl of task A at iteration i during the HP and is calculated by means of
(13)PTimeA,l,i=∑1≤j≤NZD(A,RZj)≠∞⁡PTimeRZj,A,l,i,∀1≤A≤NT,1≤l≤NbrPreempA,1≤i≤NbrIterA.Occupationj,A
The total duration of execution of taskA on RZj, after achievement of mapping/scheduling; it is computed by summing up all the execution sections of A mapped to RZj. This variable is not defined when RZj gives infinite D with task A. It is obtained using
(14)Occupationj,A=∑l,i1≤l≤NbrPreempA1≤i≤NbrIterA⁡∑t0≤TimeValuest≤HP(TUnicityj,A,l,t,i×SectionA,l)∀1≤j≤NZ,1≤A≤NT,D(A,RZj)≠∞.Existj,A,l,i
This Binary variable tests whether the preemption pointl of task A during its execution iteration i is mapped to RZj. This variable is not defined when RZj gives infinite D with task A. It is obtained by means of
(15)Existj,A,l,i=∑t0≤TimeValuest≤HP⁡TUnicityj,A,l,t,i,∀1≤j≤NZ,1≤A≤NT,1≤l≤NbrPreempA,1≤i≤NbrIterA,D(A,RZj)≠∞.Constraints
Infeasibility of Mapping for Preemption Points
The constraint expressed by (16) prohibits the mapping of preemption points of task A to RZj giving infinite D with the task. Indeed, as explained in the second step of the task clustering stage, infinite D between a task and an RZ means that there is a lack of RBs in the RZ preventing task execution or an absence of RB types which are required by the task in the RZ. In addition, this constraint asserts that the time values chosen during mapping/scheduling for preemption points of tasks must be within the set of integers {0,…,HP},
(16)TUnicityj,A,l,t,i=0,whenD(A,RZj)=∞orTimeValuest>HP,∀1≤j≤NZ,1≤A≤NT,1≤l≤NbrPreempA,1≤i≤NbrIterA,0≤t≤∞.Uniqueness of Mapping/Scheduling Preemption Points on RZs
As expressed by (17), at each possible execution iteration i, if some tasks {A} need to be scheduled on RZj at a time referred to as t, one task can be executed on this RZ at this time,
(17)∑A,l,i1≤A≤NT1≤l≤NbrPreempA1≤i≤NbrIterAD(A,RZj)≠∞⁡TUnicityj,A,l,t,i≤1,∀1≤j≤NZ,0≤TimeValuest≤HP,0≤t≤∞.Uniqueness of RZs for Preemption Points
This constraint asserts that at each execution iterationi, each preemption point l of A must exist on a unique RZj (see (18)) and must be scheduled at a unique time referred to as t. This constraint also guarantees the achievement of task execution at each repetition, as all the preemption points delimiting the execution sections of the task are fitted on RZs at specified time values,
(18)∑j,t1≤j≤NZ0≤TimeValuest≤HPD(A,RZj)≠∞⁡TUnicityj,A,l,t,i=1,∀1≤A≤NT,1≤l≤NbrPreempA,1≤i≤NbrIterA.Order of Preemption Points of a Task
At each execution iterationi for a task A, the preemption points must be scheduled in order, that is, the time value assigned to a preemption point l+1 must be superior to the completion of execution section specified by the preemption point l. Equation (19) guarantees a consistent order of scheduling of preemption points for a given task and the completion of their corresponding execution sections,
(19)PTimeA,l+1,i≥PTimeA,l,i+SectionA,l,∀1≤A≤NT,1≤l≤NbrPreempA-1,1≤i≤NbrIterA.Order between Iterations
Based on (19), the constraint expressed by (20) requires that during each execution iteration i for a task A, the scheduling of tasks must lead to the completion of each execution section within A before the beginning of its next iteration (i+1). Simultaneous executions of distinct iterations for the same task are not permitted,
(20)PTimeA,NbrPreempA,i+SectionA,NbrPreempA≤PTimeA,1,i+1,∀1≤A≤NT,1≤i≤NbrIterA-1.Upper Bound of Task Execution
Based on (19) and (20), (21) indicates that for each scheduled preemption point for a given task A, at each execution iteration i, its execution section must be completed before the HP. Otherwise, the resulting scenario is not considered a feasible scheduling,
(21)PTimeA,NbrPreempA,NbrIterA+SectionA,NbrPreempA≤HP∀1≤A≤NT.Nonoverlapping Execution
This constraint eliminates task conflicts on a given RZ. For all execution iterations, when several tasks are scheduled on the same RZ, their predefined execution sections must not overlap (see (22)). This constraint is also applicable within the same task, that is, overlapping running between execution sections is not allowed either during the same iteration, which is implicitly expressed by (19) by the imposed order for preemption point scheduling, or between distinct iterations, which is implicitly expressed by the imposed order for execution iterations of a given task in (20). Equation (22) describes this constraint between two tasks A and B existing on the same RZj,
(22)Existj,A,l,i×Existj,B,e,o×(PTimeRZj,A,l,i+SectionA,l)≤PTimeRZj,B,e,o,orExistj,A,l,i×Existj,B,e,o×(PTimeRZj,B,e,o+SectionB,e)≤PTimeRZj,A,l,i,∀1≤A,B≤NT,1≤j≤NZ,1≤l≤NbrPreempA,1≤e≤NbrPreempB,1≤i≤NbrIterA,1≤o≤NbrIterB.Precedence and Dependence Constraints
Equation (23) defines the precedence and dependence constraints. At each possible execution iteration i of task A, if A has dependence links with tasks {B}, its execution for this iteration can be launched only if the running within ith execution iterations of all its predecessors {B} has been completed and the required data for A execution have been received,
(23)PTimeA,1,i≥PTimeB,NbrPreempB,i+SectionB,NbrPreempB+Com×yA,B∀1≤A,B≤NT,1≤i≤NbrIterB,PredB,A=1.Periodicity Constraint without Dependence Constraints
This constraint focuses on the periodic execution of tasks without predecessors in the DAG. Each taskA is repeated periodically according to its specified period PA in its functional model. Each repetition defines an execution iteration for the task. Equation (24) imposes constraints only on the first preemption point of the task as (19) defines an order for scheduling the preemption points in the same iteration which consequently will take into account the periodicity constraint for the other remaining preemption points,
(24)PTimeA,1,i≥(i-1)×PA∀1≤A≤NT,1≤i≤NbrIterA,DependA=0.Periodicity Constraint with Dependence Constraints
Equation (25) addresses tasks with predecessors in the DAG. These predecessors assert a dependence of execution on their successors at each repetition. Like for tasks without predecessors, tasks having dependence constraints with other tasks in the DAG must be repeated periodically as specified by their functional model and especially taking into consideration the first instants of completion of their predecessors. Indeed, a task with dependence constraints begins its first iteration after the execution achievement of all its predecessors and their data sending. Consequently, the periodicity constraint must consider the beginning time of these tasks with dependence constraints. Similarly, by means of (19), this constraint will be considered for all the preemption points,
(25)PTimeA,1,i≥max⁡BB≠APredB,A=1⁡(PTimeB,NbrPreempB,1+SectionB,NbrPreempB+Com×yA,BPTimeB,NbrPreempB,1)+(i-1)×PA,∀1≤A≤NT,1≤i≤NbrIterA,DependA=1.Deadline Constraint without Dependence Constraints
The key idea behind the constraint explained by (26) is to respect the strict real-time constraints in the case of the absence of dependence constraints. At each given execution iteration i for a task A without predecessors, the running of task A must be completed before its absolute deadline,
(26)PTimeA,NbrPreempA,i+SectionA,NbrPreempA≤i×PA∀1≤A≤NT,1≤i≤NbrIterA,DependA=0.Deadline Constraint with Dependence Constraints
Equation (27) adheres to the deadline constraint in the case of the existence of dependence constraints between tasks in the DAG. Knowing that the beginning of a given task A with predecessors {B} in the DAG is considered since the end of running of all its predecessors within their first execution iterations and the receipt of required data, the absolute deadline of A at each execution iteration i must be met as follows:
(27)PTimeA,NbrPreempA,i+SectionA,NbrPreempA≤max⁡BB≠APredB,A=1⁡(PTimeB,NbrPreempB,1+SectionB,NbrPreempB+Com×yA,BPTimeB,NbrPreempB,1)+i×PA,∀1≤A≤NT,1≤i≤NbrIterA,DependA=1.Objective Function(F)
The objective function guides resolution and helps to converge to the optimal solution. The minimization objective functionF in (28) defines the optimal solution for the mapping/scheduling sub-problem by means of six parameters. F promotes the solution that provides the best trade-off of lowest values for these parameters. The parameters are all considered important for our methodology and are weighted according to their ranges of values. However, F gives priority to the number of occupied RZs more than other parameters. In fact, F increases exponentially with the minimum growth of the number of used RZs. Preference for this parameter is explained by the fact that our methodology is strongly dependent on physical architecture; hence, the minimum number of RZs enabling scheduling and satisfying the strict predefined constraints must be determined in order to avoid resource wastage and its consequences,
(28)F=ln⁡(Param)+exp⁡⁡(NumberOfOccupiedRZs),Param=δ1×MakeSpan+δ2×WaitingTime+δ3×ResourceOptimization+δ4×MigrationNumber+δ5×ConfigurationOverhead.
MakeSpan
It is determined by the length of the obtained scheduling. This parameter is considered the most pertinent factor in multiprocessor scheduling of DAGs as it evaluates the efficiency of the performed scheduling in terms of parallelism on processors and execution speed. Equation (29) reduces the MakeSpan of the DAG by minimizing the time of finishing execution within the last execution iterations for all tasks as they are linked by precedence and dependence constraints. Consequently, as the execution iterations are also highly dependent, it is necessary to start the execution of a given task for each iteration as soon as possible in order to minimize the makespan of the DAG,
(29)MakeSpan=max⁡A1≤A≤NT⁡(PTimeA,NbrPreempA,NbrIterA+SectionA,NbrPreempA).WaitingTime
It is determined by the response time of the scheduling for task execution. By means of (30), WaitingTime is computed as the sum of differences between the obtained runtimes of the tasks during the scheduling span and their effective execution times. WaitingTime includes the waiting time of tasks in the ready queue of the scheduler waiting for execution when their dependence and periodicity constraints are satisfied and the blocking time when the task is preempted,
(30)WaitingTime=∑A1≤A≤NT(RunTimeA-NbrIterA×CA),RunTimeA=∑i1≤i≤NbrIterA((PTimeA,NbrPreempA,i+SectionA,NbrPreempA)-(i-1)×PAPTimeA,NbrPreempA,i)ifDependA=0,RunTimeA=∑i1≤i≤NbrIterA(max⁡BB≠APredB,A=1(PTimeA,NbrPreempA,i+SectionA,NbrPreempA)-max⁡(max⁡BB≠APredB,A=1⁡(PTimeB,NbrPreempB,1+SectionB,NbrPreempB+Com×yA,BPTimeB,NbrPreempB,1)+(i-1)×PA,max⁡BB≠APredB,A=1⁡(PTimeB,NbrPreempB,i+SectionB,NbrPreempB+Com×yA,BPTimeB,NbrPreempB,i)max⁡BB≠APredB,A=1)),elseResourceOptimization
It is related to the physical features of the chosen technology. The parameter considers resource wastage and the utilization of costly resources. Both issues are involved in costD computation in the first stage. Thus, resource optimization, using (31), targets mapping tasks with high occupation rates to the RZs providing the lowest cost D with them,
(31)ResourceOptimization=∑1≤A≤NT1≤j≤NZ⁡(D(A,RZj)2×Occupationj,A24-D(A,RZj)×Occupationj,AD(A,RZj)2×Occupationj,A24).MigrationNumber
Although the migration concept optimizes scheduling length, it helps to guarantee real-time constraints and to increase resource efficiency; it also raises configuration overhead. Bearing this in mind, we constructed (32) that aims at minimizing the number of migrations required. For a given task A, the first expression of (32), on the left of the summation, searches the number of migrations within the same execution iteration, and the second part of the summation calculates the performed migrations between iterations,
(32)MigrationNumber=∑1≤A≤NT1≤j≤NZ1≤i≤NbrIterA⁡∑1≤l<NbrPreempAExistj,A,l,i≠0,Existj,A,l+1,i=0⁡1+∑1≤A≤NT1≤j≤NZ⁡∑1≤i<NbrIterAExistj,A,NbrPreempA,i≠0,Existj,A,1,i+1=0⁡1.ConfigurationOverhead
During the scheduling span, we do not consider the configuration overhead before the task execution on the RZ. This configuration overhead is negligible, that is, according to several experimentations performed with Virtex 5 technology, which uses parallel high-speed configuration ports, it represents less than 10% of the computation time of the task and does not impact the real-time functioning. However, after scheduling has been achieved, the configuration overhead, that impacts scheduling performance and power consumption, is evaluated using (33). The configuration overhead parameter should be reduced during resolution of mapping/scheduling. Equation (33) includes four expressions in the summation. The first expression, Exp1, is the initial configuration when tasks are launched by the scheduler for their first execution iteration as they did not exist on the RZs. The second expression, Exp2, represents the configuration overhead required to configure a task that migrates from one RZ to another within the same iteration i; the third expression, Exp3, depicts the configuration overhead required by a task that has finished its execution on a given RZ for an iteration i and started its (i+1)th iteration by migrating to another RZ. The fourth expression, Exp4, computes the configuration overhead resulting from intermediate tasks preempting a given task running on the same RZ. The first part of Exp4 considers the configuration overhead required in cases where a task A, during iteration i, finishes its execution section delimited by preemption point l, then it is preempted by other tasks to perform execution sections, which is then followed by task A performing its l+1 execution section at a later stage on the same RZ. This event is detected by the binary variable CurrentIterj,A,l,i. This binary variable takes 1 if two successive execution sections for the same task at the same iteration are separated by one or more tasks on the same RZ. By means of variable InterIterj,A,NbrPreempA,i, the second part of Exp4 deals with situations during which a task finishes its last execution section for a given iteration i on an RZ and starts the first execution section of (i+1)th iteration on the same RZ after the execution of other execution sections of other tasks on the same RZ. This variable takes 1 when at least one other task runs on the same RZ between two successive execution iterations of the same task,
(33)ConfigurationOverhead=Exp1+Exp2+Exp3+Exp4Exp1=∑1≤A≤NT1≤j≤NZ0≤TimeValuest≤HP⁡TUnicityj,A,1,t,1×ConfigjExp2=∑1≤A≤NT1≤j≤NZ1≤i≤NbrIterA⁡∑1≤l<NbrPreempAExistj,A,l,i≠0,Existj,A,l+1,i=0⁡ConfigjExp3=∑1≤A≤NT1≤j≤NZ⁡∑1≤i<NbrIterAExistj,A,NbrPreempA,i≠0,Existj,A,1,i+1=0⁡ConfigjExp4=∑1≤A≤NT1≤j≤NZ1≤i≤NbrIterA1≤l<NbrPreempA⁡Configj×CurrentIterj,A,l,i+∑1≤A≤NT1≤j≤NZ1≤i<NbrIterA⁡Configj×InterIterj,A,NbrPreempA,i.NumberOfOccupiedRZs
As explained in the previous step (determination of task execution intervals and the number of RZs), the obtained number of RZs ensures the feasibility of scheduling but is not necessarily the optimal number for valid scheduling. Thus, for the purpose of resource efficiency, (34) searches the lowest possible number of RZs required for feasible real-time scheduling for the chosen DAG on a multi-reconfigurable-unit system,
(34)NumberOfOccupiedRZs=∑1≤j≤NZRZOccupationj≠0⁡1,RZOccupationj=∑A1≤A≤NT⁡Occupationj,A.
Other optimization parameters are also integrated in objective functionF, but they are not mentioned in the formulation above as they implicitly impact the makespan. These parameters optimize the solutions that launch the execution of tasks as soon as their predecessors terminate their computations. In addition, they aim to bring the beginning of the tasks closer to the start time of each repetition.
After resolution of the first sub-problem of mapping/scheduling tasks on RZs, the resulting RZs must be placed on the target device. The second sub-problem of task cluster placement is a well-known problem in reconfigurable computing systems, and it differentiates our problem of scheduling on reconfigurable devices from that on software multiprocessors, generally not constrained by the physical architecture of the homogeneous processors. The second sub-problem of RZ placement is described in the next and last stage of our proposed methodology and like mapping/scheduling; it is solved by means of mixed integer programming as it is considered to be a combinatorial optimization problem.


### 3.4. Partitioning of Reconfigurable Device and Fitting of RZs

In general, the problem of hardware task placement includes two primary subfunctions: (i)partitioning, which handles free resource space on the reconfigurable device to identify potential sites enabling hardware task execution and (ii) fitting, which, according to the chosen criteria, selects a feasible placement solution among sites provided by the partitioning to fit the hardware task on a suitable physical location. Several research works have been proposed for the placement of hardware tasks on reconfigurable devices, and placement can be divided into on-line and off-line placement. For on-line placement, most scenarios propose as a partitioning technique to search for the maximal empty physical rectangles in the free space to avoid the resource wastage. For example, the two techniques proposed by Bazargan et al. in [13], one referred to as “Keeping  All  Maximal  Empty  Rectangles” searches all overlapping maximal empty rectangles and the other referred to as “Keeping  Nonoverlapping  Empty  Rectangles” keeps only the distinct holes in the free space. In [14], Walder et al. describe efficient partitioning algorithms, the main one being the On-The-Fly (OTF) partitioner which resizes empty rectangles only if the new arrived task overlaps them. Handa and Vemuri introduce staircase partitioning in [15]. Marconi et al. extend in [16] Bazargan’s partitioner by means of an Intelligent  Merging (IM) algorithm that dynamically combines three techniques for managing free resources. In [17], Ahmadinia et al. present a new method of on-line partitioning which manages occupied space on devices rather than free space, given the difficulty of managing empty space and the resulting vast increase in empty rectangles. Regarding the fitting subfunction, the works are essentially based on bin-packing rules, such as in [13] which describes the First  Fit, Best  Fit, and Bottom  left bin-packing algorithms. In [14], Walder et al. employ a hash matrix to perform fitting based on Best  Fit, Worst  Fit, Best  Fit  with  Exact  Fit, and Worst  Fit  with  Exact  Fit algorithms. In [17], Ahmadinia et al. fit tasks on sites, reducing communication costs, by means of the Nearest  Possible  Position algorithm. For off-line placement, many research works deal with metaheuristics such as simulated annealing, greedy research, and Keeping  All  Maximal  Empty  Rectangle-Best  Fit as described in [13]. In [18], ElGindy et al. describe task rearrangement by using a genetic algorithm approach with the First  Fit strategy. Considering task placement as a 2D packing problem, researchers propose off-line heuristics such as Lodi et al. who describe the Next-Fit  Decreasing  Height, First-Fit  Decreasing  Height, and Best-Fit  Decreasing  height algorithms in [19], as well as the Floor-Ceiling and Knapsack  packing algorithms in [20]. Integer linear programming is also proposed by Panainte et al. in [21] to model the problem of hardware task placement by minimizing the resources area that is reconfigured at runtime.With our methodology, we focus on off-line placement of RZs on reconfigurable devices. As the reconfigurable devices afford a limited number of reconfigurable resources and DAG includes bounded numbers of tasks, analytic resolution of the placement sub-problem is the recommended method as it guarantees the optimal solution to perform efficient allocation of tasks on FPGA. The placement of RZs is a combinatorial mono-objective problem. It consists in searching for suitable coordinates for each RZ in the FPGA among all the possible combinations of discrete coordinates. In this section, similarly to the mapping/scheduling sub-problem, the resolution of RZ placement on the reconfigurable device is accomplished through mixed integer programming and optimizes resource efficiency. The achievement of RZ placement results in a 2D physical locations for each task cluster. These physical locations are depicted by reconfigurable physical blocs (RPBs) and are represented by their RB model as described in (35). RZs are abstractions of hardware task clusters, and RPBs are the final reconfigurable units where tasks may be executed. With the concept of run-time partial reconfiguration, after the mapping/scheduling results are obtained respecting the strict predefined constraints and optimizing several criteria, task execution sections are reconfigured and executed on RPBs as restricted by the schedule scenario. Thus, the task bitstreams on their associated RPBs are created at compile time. These bitstreams are used during the DAG running as indicated by scheduling which specifies the corresponding state for each task on each RPB,(35)RPBj_RB={γj,kRBk},γj,k∈N,1≤j≤NZ,1≤k≤NP.As shown in Figure7, the partitioned RPBs on a reconfigurable device for a given RZ must include all its required RB types to ensure the execution of the tasks. The partitioned RPBs for a given RZ might contain some RBs that are not required by the RZ. For instance, RB4 is inserted within RPB3 but is not used by the corresponding RZ. This resource inefficiency is explained by the rectangular shape of the RPBs. Thus, the number of RBs included in the RPB could exceed the required RBs in the RZ. Resource inefficiency is also due to the heterogeneity of the device; partitioning could book some RBs which are not used by the RZ. RB utilization efficiency is an important metric parameter for evaluating placement quality. During RZ placement resolution, we focus on fitting RZs as closely as possible to RPBs in terms of number and types of RBs.Figure 7
Example of RPBs for RZ.By means of mixed integer linear programming solver, both the partitioning and fitting subfunctions are solved simultaneously. The RZ placement sub-problem is modeled by the quadruplets (Constants, Variables, Constraints, and Objective Function).ConstantsNZ:Number of RZs resulting frommapping/scheduling resolutionNP:Number of RB types existing inthe target technology RZfeatures, RB featuresDevice featuresDevice_Width:The width of the deviceDevice_Height:The height of the deviceDevice_RB:The RB model of the device.Variables
Placement resolution consists in assigning discrete values for the four coordinates specifying theRPBj for each RZj. Each RPBj is constructed by four coordinates:Xj:The abscissa of the upper left vertex ofRPBjYj:The ordinate of the upper left vertex ofRPBjWRPBj:The abscissa of the upper right vertex ofRPBjHRPBj:The ordinate of the bottom left vertex ofRPBj.Constraints
Heterogeneity Constraint
As RZs are fitted on RPBs, during RPB partitioning, the number of each RB type within the RPBs (Xj, WRPBj, Yj, HRPBj) must be greater than or equal to those in the RZs (βj,k) as formulated by (36) in order to satisfy the RB requirements of the RZs. Because of the heterogeneity of RBs in the device and the rectangular shape of RPBs, the partitioned RPBs could include some RB types not required by the RZs. Moreover, the number of RB types in the RPBs and included in the RZs might exceed that required by the RZs. This resource inefficiency is minimized by means of the objective function,
(36)βj,k≤∑Xj≤m≤WRPBjYj≤n≤HRPBj⁡∑device_RB[m][n]=RBk1,∀1≤j≤NZ,1≤k≤NP,RZj_RB={βj,kRBk},RPBj(Xj,WRPBj,Yj,HRPBj).Nonoverlapping between RPBs
As expressed by (37), this constraint restricts the fitting of RZs on nonoverlapping RPBs
(37)Xq>WRPBjorXj>WRPBqorYq>HRPBjorYj>HRPBq,∀j≠q,1≤j,q≤NZ.Objective Function(F)
Objective functionF comprises one parameter which is ResourceEfficiency. This primordial parameter focuses on finding the closest RPB partitioned on the FPGA to fit each RZ in terms of number and types of RBs. By respecting both previous constraints, (38) assesses placement quality after RZ insertion on the selected RPBs in order to achieve the optimal solution. Increasing resource efficiency reduces configuration overhead,
(38)ResourceEfficiency=∑1≤j≤NZ1≤k≤NP⁡RBCostk×(γj,k-βj,k),RPBjRB={γj,kRBk},RZj_RB={βj,kRBk},1≤j≤NZ,1≤k≤NP.
Both subproblems, that is, (i) mapping/scheduling tasks on RZs and (ii) partitioning/fitting RZs on the FPGA, are successively solved by means of powerful solvers dedicated by the AIMMS [22] environment. The chosen solvers for mixed integer programming satisfy predefined constraints and provide an optimal solution in an acceptable time frame. The following section shows how our proposed methodology may be applied to an example of DAG on Virtex 5 technology; the section also evaluates scheduling and placement quality.


## 3.1. Terminology and Definitions

Throughout the paper,NT refers to the number of tasks in the graph, NZ the number of clusters, and NP the number of resource types in the chosen technology. The directed acyclic task graph is denoted by the pair (N,E). N is the set of nodes representing tasks in the DAG, and E is the set of edges linking the dependent tasks, E⊆N×N.As shown in Figure3, on each edge, the outgoing value (xA,B) from the source node A to the sink node B depicts the amount of data that A must produce at each repetition for B. The incoming value (yB,A) represents the amount of data that must be consumed by the sink node B at each execution iteration after completion of the repetition of its predecessor A.Figure 3
Directed acyclic graph.Each task in the graph has three models as follows.


### 3.1.1. Functional Model

Each hardware task(A) is represented by a set of parameters fixed at compile time and which are kept static throughout the DAG execution. A is characterized by its worst-case execution time (CA), its period (PA), which is equal to its relative deadline (DA), and a set of preemption points (PreempA,l). The preemption points are instants of the time taken throughout the worst-case execution time as shown in Figure 4. The number of preemption points of task A is denoted by NbrPreempA. This number also includes the first point of execution of the task. The set of preemption points is determined by the designer according to the known states in the behavioral model and according to possible data dependences between these states. The predefinition of preemption points gives rise to the execution sections within the hardware task. Our methodology is based on preemptive modeling to create a reactive system, to increase flexibility towards application needs, and consequently to enhance the respect of real-time constraints.Figure 4
Predefined preemption points in TaskA.


### 3.1.2. Behavioral Model

This includes the finite state machine controlling each task and which handles a set of registers or a small memory bank useful for context switching during preemption. The latency required to preempt and to resume the execution of tasks is disregarded as in the worst case; the time to access the system bus and memory is negligible. With the preemptive model, we do not use the classical method of readback and load modified bitstream since latency with this method is significant; it complicates preemption and requires a large space memory. With the classical method, a new readback bitstream must be saved at each preemption. With our model, the number of preemptions within tasks is limited by specifying the possible preemption points according to task states outside of which preemption is not allowed. Thus, we resort to saving/loading the current state of the finite state machine with an acceptable amount of data by maintaining the same bitstream for each task within a given reconfigurable unit when the task needs to be preempted or resumed. Preemption points of hardware tasks are set in a way that reduces the data dependences that could exist between two states. In fact, maintaining a preemption point between two states processing the same data must be avoided because these data need to be saved into an external memory which might increase the preemption overhead at runtime. Otherwise, it is recommended to insert a preemption point when the task is in a blocked state, waiting to receive an external resource to enable the ready tasks to be executed in the reconfigurable unit. In the finite state machine, the longest execution time between two states must be considered in order to deduct the worst-case execution time.


### 3.1.3. RB-Model

At the physical level, tasks are presented as a set of reconfigurable resources called reconfigurable blocs (RB). RBs correspond to the physical resources in the reconfigurable hardware device required to achieve execution of the hardware task, and they define the RB model of the task as expressed by (1). Determination of the RB-model of hardware tasks is well detailed in our work described in [12]. The number of RB types is equal to the number of resource types in the chosen technology. The RBs are the smallest reconfigurable units in the hardware device. They are determined according to the available reconfigurable resources in the device, and they closely match its reconfiguration granularity. Each type of RB is characterized by a specified cost, RBCostk, defined according to its frequency in the device, its power consumption, and the importance of its functionality,(1)A_RB={αA,kRBk},αA,k∈N,1≤A≤NT,1≤k≤NP.The reconfigurable device is also characterized by its RB model as shown in our work described in [12] to enable the placement of hardware task clusters at a later stage.The three main stages of the methodology used for static scheduling of DAGs on multi-reconfigurable-unit system with predefined constraints are described below.


## 3.1.1. Functional Model

Each hardware task(A) is represented by a set of parameters fixed at compile time and which are kept static throughout the DAG execution. A is characterized by its worst-case execution time (CA), its period (PA), which is equal to its relative deadline (DA), and a set of preemption points (PreempA,l). The preemption points are instants of the time taken throughout the worst-case execution time as shown in Figure 4. The number of preemption points of task A is denoted by NbrPreempA. This number also includes the first point of execution of the task. The set of preemption points is determined by the designer according to the known states in the behavioral model and according to possible data dependences between these states. The predefinition of preemption points gives rise to the execution sections within the hardware task. Our methodology is based on preemptive modeling to create a reactive system, to increase flexibility towards application needs, and consequently to enhance the respect of real-time constraints.Figure 4
Predefined preemption points in TaskA.


## 3.1.2. Behavioral Model

This includes the finite state machine controlling each task and which handles a set of registers or a small memory bank useful for context switching during preemption. The latency required to preempt and to resume the execution of tasks is disregarded as in the worst case; the time to access the system bus and memory is negligible. With the preemptive model, we do not use the classical method of readback and load modified bitstream since latency with this method is significant; it complicates preemption and requires a large space memory. With the classical method, a new readback bitstream must be saved at each preemption. With our model, the number of preemptions within tasks is limited by specifying the possible preemption points according to task states outside of which preemption is not allowed. Thus, we resort to saving/loading the current state of the finite state machine with an acceptable amount of data by maintaining the same bitstream for each task within a given reconfigurable unit when the task needs to be preempted or resumed. Preemption points of hardware tasks are set in a way that reduces the data dependences that could exist between two states. In fact, maintaining a preemption point between two states processing the same data must be avoided because these data need to be saved into an external memory which might increase the preemption overhead at runtime. Otherwise, it is recommended to insert a preemption point when the task is in a blocked state, waiting to receive an external resource to enable the ready tasks to be executed in the reconfigurable unit. In the finite state machine, the longest execution time between two states must be considered in order to deduct the worst-case execution time.


## 3.1.3. RB-Model

At the physical level, tasks are presented as a set of reconfigurable resources called reconfigurable blocs (RB). RBs correspond to the physical resources in the reconfigurable hardware device required to achieve execution of the hardware task, and they define the RB model of the task as expressed by (1). Determination of the RB-model of hardware tasks is well detailed in our work described in [12]. The number of RB types is equal to the number of resource types in the chosen technology. The RBs are the smallest reconfigurable units in the hardware device. They are determined according to the available reconfigurable resources in the device, and they closely match its reconfiguration granularity. Each type of RB is characterized by a specified cost, RBCostk, defined according to its frequency in the device, its power consumption, and the importance of its functionality,(1)A_RB={αA,kRBk},αA,k∈N,1≤A≤NT,1≤k≤NP.The reconfigurable device is also characterized by its RB model as shown in our work described in [12] to enable the placement of hardware task clusters at a later stage.The three main stages of the methodology used for static scheduling of DAGs on multi-reconfigurable-unit system with predefined constraints are described below.


## 3.2. Hardware Task Clustering

This stage comprises two steps that are performed consecutively: (i) reconfigurable zone type search and (ii) costD computing. Bearing in mind that the concept of run-time partial reconfiguration had to be used, our main objective at this first stage was to partition tasks constituting the graph into cluster types determined according to their required RB types in order to enhance resource utilization.


### 3.2.1. Reconfigurable Zones Types Search

This step takes as input the RB model of each task in the DAG, and by performing Algorithm1 of the worst-case complexity O(NT2*NP), it groups tasks sharing the same types of RBs under the same type of cluster by taking the maximum number of RBs between these tasks. With our methodology, the obtained types of clusters are denoted as reconfigurable zones (RZs). The upper bound of the possible RZs is NT. Thus, RZs are virtual units customized by Algorithm 1 to model the classes of hardware tasks in terms of RB types. RZs separate hardware tasks from their execution units on the reconfigurable device. In the last stage of our proposed methodology, RZs will be placed on their suitable reconfigurable units respecting the heterogeneity of the device and optimizing resource efficiency as well as configuration overhead. After the completion of Algorithm 1, each RZ is represented by its RB model as expressed by (2)RZj_RB={βj,kRBk},βj,k∈N,1≤j≤NZ,1≤k≤NP.
Algorithm 1 processes the tasks of the DAG as follows. It scans the RB model of each hardware task and checks whether an already inserted type of RZ that closely matches the required types of RBs in the task exists in the RZ types list, list-RZ (line 6). Should this be the case, Algorithm 1 updates the number of RBs within this type of RZ by the maximum between the number of RBs in the task and that in the RZ (line 9).Algorithm 1:RZ types search or hardware task classes search.
(1)RZ-type=0 // RZ types(2)List-RZ // list of RZ types(3)n // natural(4)for  all  tasks A  do(5)   //A_RB=αA,kRBk(6)if  ((RZ-type≠0)  and  (∃n,1≤n≤RZ-type)/∀k((αA,k≠0andβn,k≠0)  or  (αA,k=0andβn,k=0)))then(7)    // this test checks whether the task matches with an RZ type that already exists inlist-RZ(8)for  all  k  do(9)βn,k=max(αA,k,βn,k) // update RB number of RZn(10)end  for(11)else(12)    IncrementRZ-type(13)RZRZ-type=CreatenewRZ(αA,k) // new type of RZ, RZRZ-type={αA,kRBk}(14)    Insert (list-RZ, RZRZ-type)(15)end  if(16)end  forIf the required types of RBs in the task do not match any type of RZ included in thelist-RZ, the algorithm of the search of RZ types decides on the creation of a new type of RZ as required by the task (lines 12, 13) and inserts it in list-RZ (line 14).Figure5 is an example of the execution of Algorithm 1 for the RZ types search for DAG comprising five tasks. Figure 5 illustrates the search for RZ types resulting from five tasks in a technology including four types of RBs (RB1, RB2, RB3 and RB4). A and C are grouped in the same type of RZ (RZ1) as both need RB1 and RB2, and the number of each RB type within RZ1 is adjusted by the maximum number of RBs between A and C. Similarly, RZ2 is created by B and D, and E defines the third type of RZ (RZ3).Figure 5
Example of the search for RZ types.After searching for the set of RZs, the configuration overhead for each obtained RZ is computed and denoted byConfigj. Configj corresponds to the configuration overhead to fit RZj in the target technology. This configuration overhead is computed by the floorplanning of each RZj on the chosen device and by conducting the whole partial reconfiguration flowup to the creation of the partial bitstream. Configj is determined by (3) according to configuration frequency and configuration port,(3)Configj=sizeofbitstream(Configuration frequency×configuration port width).


### 3.2.2. CostD Computing

This step commences by computing costD between tasks and each RZ type resulting from the first step. Cost D represents the differences in RBs between tasks and RZs; consequently, it expresses resource wastage when a task is mapped to an RZ. Based on RB models of task A and RZ RZj, cost D is computed according to two cases as follows. Firstly, we define by (4)dA,j,k=αA,k-βj,k,1≤A≤NT,1≤j≤NZ,1≤k≤NP.Case 1.
For allk, dA,j,k≤0, RZj contains a sufficient number of each type of RB (RBk) required by A, and cost D is equal to the sum of the differences in the numbers of each RB type between A and RZj weighted by RBCostk as expressed in
(5)D(A,RZj)=∑1≤k≤NPRBCostk×|dA,j,k|.Case 2.
There existsk, dA,j,k>0, the number of RBs required by A exceeds the number of RBs in RZj or A needs RBk which is not included in RZj. In this case, cost D is infinite,
(6)D(A,RZj)=∞.
CostD is exploited during the stage of task mapping and scheduling on RZs and the RZ placement stage to optimize the utilization of costly resources to the device. The execution of a given task in an RZ is allowed only when the cost D between them is finite. Figure 6 illustrates the computing of costs D between the five tasks and RZ3 described in Figure 5.Figure 6
Example of computing costD with RZ3.


## 3.2.1. Reconfigurable Zones Types Search

This step takes as input the RB model of each task in the DAG, and by performing Algorithm1 of the worst-case complexity O(NT2*NP), it groups tasks sharing the same types of RBs under the same type of cluster by taking the maximum number of RBs between these tasks. With our methodology, the obtained types of clusters are denoted as reconfigurable zones (RZs). The upper bound of the possible RZs is NT. Thus, RZs are virtual units customized by Algorithm 1 to model the classes of hardware tasks in terms of RB types. RZs separate hardware tasks from their execution units on the reconfigurable device. In the last stage of our proposed methodology, RZs will be placed on their suitable reconfigurable units respecting the heterogeneity of the device and optimizing resource efficiency as well as configuration overhead. After the completion of Algorithm 1, each RZ is represented by its RB model as expressed by (2)RZj_RB={βj,kRBk},βj,k∈N,1≤j≤NZ,1≤k≤NP.
Algorithm 1 processes the tasks of the DAG as follows. It scans the RB model of each hardware task and checks whether an already inserted type of RZ that closely matches the required types of RBs in the task exists in the RZ types list, list-RZ (line 6). Should this be the case, Algorithm 1 updates the number of RBs within this type of RZ by the maximum between the number of RBs in the task and that in the RZ (line 9).Algorithm 1:RZ types search or hardware task classes search.
(1)RZ-type=0 // RZ types(2)List-RZ // list of RZ types(3)n // natural(4)for  all  tasks A  do(5)   //A_RB=αA,kRBk(6)if  ((RZ-type≠0)  and  (∃n,1≤n≤RZ-type)/∀k((αA,k≠0andβn,k≠0)  or  (αA,k=0andβn,k=0)))then(7)    // this test checks whether the task matches with an RZ type that already exists inlist-RZ(8)for  all  k  do(9)βn,k=max(αA,k,βn,k) // update RB number of RZn(10)end  for(11)else(12)    IncrementRZ-type(13)RZRZ-type=CreatenewRZ(αA,k) // new type of RZ, RZRZ-type={αA,kRBk}(14)    Insert (list-RZ, RZRZ-type)(15)end  if(16)end  forIf the required types of RBs in the task do not match any type of RZ included in thelist-RZ, the algorithm of the search of RZ types decides on the creation of a new type of RZ as required by the task (lines 12, 13) and inserts it in list-RZ (line 14).Figure5 is an example of the execution of Algorithm 1 for the RZ types search for DAG comprising five tasks. Figure 5 illustrates the search for RZ types resulting from five tasks in a technology including four types of RBs (RB1, RB2, RB3 and RB4). A and C are grouped in the same type of RZ (RZ1) as both need RB1 and RB2, and the number of each RB type within RZ1 is adjusted by the maximum number of RBs between A and C. Similarly, RZ2 is created by B and D, and E defines the third type of RZ (RZ3).Figure 5
Example of the search for RZ types.After searching for the set of RZs, the configuration overhead for each obtained RZ is computed and denoted byConfigj. Configj corresponds to the configuration overhead to fit RZj in the target technology. This configuration overhead is computed by the floorplanning of each RZj on the chosen device and by conducting the whole partial reconfiguration flowup to the creation of the partial bitstream. Configj is determined by (3) according to configuration frequency and configuration port,(3)Configj=sizeofbitstream(Configuration frequency×configuration port width).


## 3.2.2. CostD Computing

This step commences by computing costD between tasks and each RZ type resulting from the first step. Cost D represents the differences in RBs between tasks and RZs; consequently, it expresses resource wastage when a task is mapped to an RZ. Based on RB models of task A and RZ RZj, cost D is computed according to two cases as follows. Firstly, we define by (4)dA,j,k=αA,k-βj,k,1≤A≤NT,1≤j≤NZ,1≤k≤NP.Case 1.
For allk, dA,j,k≤0, RZj contains a sufficient number of each type of RB (RBk) required by A, and cost D is equal to the sum of the differences in the numbers of each RB type between A and RZj weighted by RBCostk as expressed in
(5)D(A,RZj)=∑1≤k≤NPRBCostk×|dA,j,k|.Case 2.
There existsk, dA,j,k>0, the number of RBs required by A exceeds the number of RBs in RZj or A needs RBk which is not included in RZj. In this case, cost D is infinite,
(6)D(A,RZj)=∞.
CostD is exploited during the stage of task mapping and scheduling on RZs and the RZ placement stage to optimize the utilization of costly resources to the device. The execution of a given task in an RZ is allowed only when the cost D between them is finite. Figure 6 illustrates the computing of costs D between the five tasks and RZ3 described in Figure 5.Figure 6
Example of computing costD with RZ3.


## 3.3. Mapping and Scheduling of Hardware Tasks on RZs

It is well known that task mapping and scheduling are highly interdependent. The two issues therefore need to be addressed together for mapping and scheduling to be efficient. In order to analyze the scheduling of a given DAG of periodic tasks, it is sufficient to study its behavior for a time interval equal to the least common multiple of all the task periods, called the hyperperiod (HP). Consequently, the possible iterations of execution of each taskA during the HP may be determined according to its period PA, which is equal to ⌊HP/PA⌋. To resolve the subproblem of mapping and scheduling of hardware tasks on RZs, our methodology conducts three steps of spatial and temporal analyses. The first one checks the rightness of task precedences, dependences, and real-time functioning in the DAG by means of three essential constraints. Consequently, the DAG will be validated to launch the following analyses. The second analysis determines the lists of ready times of each task for each possible iteration during the hyperperiod. These lists take into account the periodicity, precedence, dependence, and deadline constraints. The third straightforward analysis takes as input the lists of ready times, searches at each iteration the possible execution intervals for each task, and therefore detects possible conflicts due to overlapping between execution intervals of parallel tasks on the same RZ. The third analysis pursues its processing to solve the detected overloads within RZs by performing either the migration of execution sections of some tasks respecting their predefined preemption points or by increasing the number of overloaded RZs.


### 3.3.1. Checking of Precedence, Dependence, and Real-Time Rightness in DAG

The first temporal analysis does not take into account spatial constraints and considers that there is an available RZ for each task. It also considers the periodicity of tasks. The main objective of this analysis is only to validate the correctness of task precedence and dependences and real-time constraints in the studied DAG. It is conducted by means of three essential constraints.(a) Dependence Checking
More than precedence, we consider that the tasks related by an edge of precedence are also dependent. This means that the execution of a given task requires the data resulting from the execution of all its predecessors. This dependence is expressed by (7). Equation (7) focuses on periods and the amount of interchanged data between dependent tasks. It guarantees, when PA≥PB and A∈ΠB, that each data (xA,B) produced by task A in its repetition Ai is consumed by its successor B during its iterations of execution Bi or Bj>i. When PA≤PB and A∈ΠB, at each iteration of execution of B, it ensures that there are the sufficient data (yB,A) for B to be executed. 											(7)yB,A×⌊HPPB⌋=xA,B×⌊HPPA⌋,∀B,A∈πB.The previous equation eliminates the problem of data wastage and ensures that the data produced by all the iterations of each task are consumed by all the iterations of its successors. In this work, we focus on the case where PA≥PB, for all B,A∈πB.(b) Precedence Checking
As we work in the case ofPA≥PB, for all B,A∈πB, considering the periodicity constraint, this constraint claims that each iteration of execution Ai of a given task A may include only the iterations Bi or {Bj<i} of its successors {B} to ensure the correctness of the precedence constraint. During repetition Ai of a given task A, this constraint prohibits that Bi and {Bj>i} repetitions of its successors {B} coexist. In this way, during the HP, each ith execution of any task is preceded by the ith execution iterations of all its predecessors. To guarantee these rules, the following constraint expressed by (8) was developed to guide the selection of execution times and periods for tasks in the DAG:
(8)TreadyB+k×PB>TreadyA+(k-1)×PA,∀B,A∈πB,k∈N,1≤k≤NbrIterA.NbrIterA depicts the possible number of execution iterations of A during the HP. TreadyA and TreadyB are the ready times for tasks A and B without considering the spatial constraints. They are determined by searching the critical path corresponding to the task in the graph by using the ASAP (as soon as possible) technique. For each task B having a set of predecessors {A}, its ready time TreadyB is computed as follows
(9)TreadyB=max⁡{A∈πB}⁡(TreadyA+CA),TreadyB=0,ifπB=∅.(c) Real-Time Checking
Considering the periodicity constraint, this constraint analyses the respect of real-time constraints in the best case of spatial conditions in terms of number of RZs. By respecting the precedence and dependence constraints, (10) checks at each iteration whether each task may complete its execution before its strict absolute deadline. If the absolute deadline of the task for its last iteration exceeds the HP, the deadline then turns into the HP. As we work in the case PA≥PB, for all A∈πB, the second expression of (10) satisfies the deadline constraint for the remaining repetitions of task B when its predecessors {A} achieve all their execution iterations
(10)max⁡(TreadyA+k×PA+CA,TreadyB+k×PB)+CB≤min⁡⁡(TreadyB+(k+1)×PB,HP),∀B,A∈πB,k∈N,0≤k≤NbrIterA-1,TreadyB+k×PB⁡+CB≤min⁡⁡(TreadyB+(k+1)×PB,HP)∀B,k∈N,max⁡A∈πB⁡(NbrIterA)≤k≤NbrIterB-1.
Respect of the three previous constraints validates the selection of periods and execution times for periodic tasks in the graph for the scheduling with precedence, dependence constraints, and under strict real-time constraints on an unlimited number of reconfigurable units. Nevertheless, the following temporal and spatial analyses will extract the corresponding number of RZs that will satisfy these constraints. When the previous constraints are unreal, the DAG is considered invalid and consequently it will be rejected or the features of its tasks will be modified and evaluated again till it respects the constraints expressed by (7), (8), and (10).
Consequently, with our methodology, we depart from the temporal analysis to construct a suitable physical architecture allowing a feasible schedule. As a final step at this stage, after fixing the physical architecture of the multi-reconfigurable-unit system, analytic resolution of mapping/scheduling provides the optimal scheduling of DAGs on target technology.


### 3.3.2. Determination of Lists of Ready Times

The temporal analysis does not consider the physical constraints and searches all the ready times in each execution iteration for all tasks in the graph by respecting the precedence, dependence, periodicity, and real-time constraints. This analysis yields, by means of (11), the lists {TreadyminBi,…,TreadymaxBi} during which task B may start execution, where Bi denotes the ith iteration of task B within the HP. Outside this list, task B might not respect the predefined constraints, which would lead to unfeasible scheduling.For each taskB, TreadyminBi is the lower bound time to start task execution at its iteration i in order to respect its precedence, dependence, and periodicity constraints. TreadymaxBi is the upper bound time from which the task can no longer start execution if its strict deadline and the data dependency and precedence of its successors are to be respected. To compute the Treadymin of tasks, we start computing from the top of the DAG. For the Treadymax calculation, we start from the bottom of the DAG, and for both, we proceed using the breadth-first search strategy(11)TreadyminB1=0ifπB=∅,TreadyminBi=max⁡(max⁡A∈πB⁡(TreadyminAi+CA),rminBi),TreadymaxB1=min⁡(min⁡A∈φB⁡(TreadymaxA1),PB)-CB,φBisthesetofsuccessorsofB,TreadymaxBi/i>1=min⁡(min⁡A∈φB⁡(TreadymaxAi),rmaxBi+1,HP)-CB.rminBi and rmaxBi are the start times of the ith repetition of B according to its first ready times (TreadyminB1 and TreadymaxB1). Hence, they are determined by incrementing TreadyminB1 and TreadymaxB1 by PB. For example, if we have a task B with a period = 8, a hyperperiod HP=24, and we consider TreadyminB1=3 and TreadymaxB1=4, then rminB1=TreadyminB1=3, rminB2=3+8=11, rminB3=11+8=19, rmaxB1=TreadymaxB1=4, rmaxB2=4+8=12, rmaxB3=12+8=20.


### 3.3.3. Determination of Task Execution Intervals and the Number of RZs

This temporal and spatial analysis considers the RZ types resulting from the task clustering stage and searches the possible parallelism between tasks to study execution conflicts on the RZs. When an overload is detected in some RZs, the analysis starts by solving this problem through a migration mechanism; if migration does not produce a solution, it increments the number of overloaded RZs as required. This analysis searches first, by means of Algorithm2, the execution intervals of each task for each possible iteration during the HP, then, using Algorithm 3, it deals with the overlapping execution intervals on the RZs to search the possible overloads, and finally, it uses Algorithm 4 to try to solve the found overloads by the migration mechanism; when this latter mechanism fails, additional RZs are inserted in the architecture of the multi-reconfigurable-unit system to solve the persisting overloads.Algorithm 2:Search of execution intervals.
(1)A,B // Tasks(2)i // Natural, iterations of execution of task A(3)List-TreadyAi // the list of ready times for task A during ith iteration(4)TreadyAi // the ready times for task A during ith iteration(5)TreadyA // the ready times for task A from the current TreadyAi(6)Execution-IntervalAi=⊘ // the set of execution intervals for task A during ith iteration(7)for  all  tasks A  do(8)for  all  execution iterations i of task A  do(9)List-TreadyAi={TreadyminAi,…,TreadymaxAi}(10)if  i=1  then(11)Execution-IntervalAi = {[TreadyAi,min(TreadyAi+PA,minB∈φA(TreadymaxBi),HP)],∀TreadyAi∈List-TreadyAi}(12)else(13)for  all  TreadyA1∈List-TreadyA1  do(14)TreadyAi = First (List-TreadyAi)(15)for  all  TreadyA∈{TreadyAi,…,TreadymaxAi}  do(16)Execution-IntervalAi=Execution-IntervalAi⋃{[TreadyA,min(TreadyA1+i*PA,minB∈φA(TreadymaxBi),HP)], if TreadyA1+i*PA is chosen as upperbound for this interval then it must respect: TreadyA+CA≤TreadyA1+i*PA, if HP is chosen then it must respect: TreadyA+CA≤HP}(17)end  for(18)List-TreadyAi = next (List-TreadyAi)(19)end  for(20)end  if(21)end  for(22)end  forAlgorithm 3:Search of overlapping execution intervals and RZ loads.
(1)A,B,D // Tasks(2)i, j, k, m // Natural, iterations of execution of tasks(3)Execution-IntervalAi // The set of execution intervals for task A during ith iteration(4)Crossing-Combination // All the possible combinations of sets Execution-IntervalAi of distinct tasks that giveoverlapping execution intervals on a given RZ, duringHP(5)Comb // Combination of overlapping execution intervals depicted by [A-min, A-max](6)CDr // The remaining execution time within task D(7)PDr The remaining period within task D(8)Pmax // The period of conflict for a combination of overlapping execution intervals(9)for  all  iteration i  do(10)for  all  RZ  do(11)Crossing-Combination = {{Execution-IntervalAj}/⋂j≤iExecution-IntervalAj≠⊘}(12)Comb = one combination of overlapping execution intervals extracted from sets in Crossing-Combination.(13)for  all  Comb in Crossing-Combination  do(14)    InComb, search the latest tasks {B} in starting execution(15)    InComb, search all the remaining tasks {D} that are ready or start execution before {B} and determinetheir remaining execution times:CDr and their remaining periods: PDr(16)CDr=CD-(B-min-D-min)(17)PDr=PD-(B-min-D-min)(18)if  (∀D-min, D-min = TreadyD1+(k-1)*PD, ∀D-max, D-max=TreadyD1+k*PD, ∀B-min,B-min = TreadyB1+(m-1)*PB and ∀B-max, B-max = TreadyB1+m*PB/TreadyD1∈{TreadyminD1,…,TreadymaxD1}, TreadyB1∈{TreadyminB1,…,TreadymaxB1}, and k and m are theiterations from which the execution  intervals are taken respectively for tasks{D} and {B})  then(19)RZ-Load = ∑DCDr/PDr + ∑BCB/PB(20)else(21)Pmax=maxD(D-max-B-min)(22)RZ-Load = ∑DCDr/Pmax + ∑BCB/Pmax(23)end  if(24)end  for(25)end  for(26)end  forAlgorithm 4:Total and partial migration or addition of RZs.
(1)Comb // Combination of overlapping execution intervals(2)Non-overload-comb // Boolean controlling after migration whether RZ is no longer overloaded by Comb(3)RZ-Load// Load of the RZ corresponding to Comb(4)RZ-migration // The set of RZs helpful for partial migration(5)Task-migration // The set of tasks that might perform partial migration(6)for  all  Comb giving overloaded RZ  do(7)Non-overload-comb= False(8)while  (Non-overload-comb = False) and (Comb≠⊘)  do(9)    // Total migration of tasks(10)Select the interval from Comb that gives the most heavy occupation rate and discard it from Comb.(11)Check whether the iteration, corresponding to the execution interval of the selected task, is studied on anothernon-overload RZ and update the load of the overloaded RZ after the elimination of the selected task.(12)if  RZ-Load≤1  then(13)Non-overload-comb= True(14)end  if(15)end  while(16)if  Non-overload-comb=False  then(17)   ReinitializeRZ-Load and Comb with its tasks(18)Task-migration=⊘(19)RZ-migration=⊘(20)   // Partial migration of tasks(21)   Omit the tasks from the overloaded RZ, corresponding toComb, that are also acceptable by another RZs (D≠∞) andreduce their occupation rates from the loads of these RZs. These latter RZs with the overloaded RZ corresponding toComb are included in the set RZ-migration. The omitted tasks are included in Task-migration(22)while  Task-migration≠⊘  do(23)    InTask-migration set, start by the task that gives the best trade-off between least number of RZs in RZ-migrationwhere it could migrate and heaviest occupation rate in the overloaded RZ.(24)    DuringComb, within the selected task, choose the biggest execution sections that could be placed in RZs from thesetRZ-migration without overloading them.(25)    Update the load of RZs receiving execution sections from the selected task(26)if  Some execution sections of the selected task are not placed  then(27)     Reinitialize the loads of RZs inRZ-migration to values before processing Comb(28)     Increment the number of RZ corresponding toComb up to ⌈RZ-Load⌉, go to 6(29)else(30)     Discard the selected task fromTask-migration.(31)end  if(32)end  while(33)   // All the execution sections of tasks are placed(34)Non-overload-comb=True(35)end  if(36)end  for(a) Search of Execution Intervals
This step uses the functional model of tasks and determines their execution intervals by means of Algorithm2 of worst-case temporal complexity equal to O(NT*HP3). An execution interval for a given task at a given iteration is an interval during which the task can be executed while satisfying all the predefined constraints.
For each taskA in the DAG, Algorithm 2 produces the set of its possible execution intervals expressed by Execution-IntervalAi at each possible iteration i during the HP. When this algorithm processes the first iteration of task A, the set of its possible execution intervals is determined directly (line 11) considering the precalculated ready times in List-TreadyA1, and the periodicity and dependence constraints. For the next iterations, considering each possible TreadyA1 for the purpose of respecting the periodicity constraint (line 13), at each iteration i, Algorithm 2 searches all the corresponding execution intervals starting with each possible TreadyAi (line 14, line 15), and considering the dependence and the deadline constraints, and the HP to determine the upper bound for each execution interval (line 16). In line 18, in order to guarantee the periodicity and dependence constraints, progressing from a TreadyA1 to another in list List-TreadyA1, Algorithm 2 must shift the list List-TreadyAi by omitting its first element, since ready times in each iteration i are also linked to the ready times of the first iteration.(b) Search of Overlapping between Execution Intervals of Tasks in the Same RZ
For the first iteration, the parallel tasks on a given RZ are extracted directly from the DAG; hence, there is no parallel execution between a given task and its successors. However, in the next iterationsi, searching parallel tasks must respect some rules. For the next iterations i, for parallel efficiency, a given task could overlap with its successors during their iterations j(j<i) on the same RZ. Moreover, this step must also consider the execution conflicts on the same RZ for a given task in its iteration i and other tasks that are in the iterations j(j≤i) when there are no dependence constraints between them. This step prohibits simultaneous execution of several iterations of the same task.
The step defines for each task the possible RZs allowing its execution in terms of types and number of RBs based on computed costD and then searches the execution conflicts on the RZs using Algorithm 3. Algorithm 3 has a worst-case temporal complexity equal to O(NZ*2NT*HP).
During each iterationi, for each RZ, in order to find the parallel tasks with a finite cost D with the RZ, Algorithm 3 searches all the possible combinations of sets of execution intervals {Execution-IntervalAj} of all the tasks that can be executed on the current RZ and produce overlapping execution intervals respecting the rules described above (line 11). Then, from the resulting sets of execution intervals, Algorithm 3 extracts the execution intervals causing the conflicts in the current RZ which will result in Comb (line 12). Comb may contain two or more tasks. Each obtained Comb is processed individually to study the load of the RZ (line 13–line 24). For each Comb, we start the study only at the time at which all the tasks coexist to check for possible conflict and its consequence on the current RZ. Thus, Algorithm 3 searches the latest tasks {B} in Comb (line 14) and for tasks {D} that either have already started their executions and still running after {B} arriving or have been ready before {B} arriving; it searches their remaining execution times and periods (line 15–line 17) by promoting the tasks with the earliest deadlines and using the ASAP technique, especially in the case there are more than two tasks within the Comb. Finally, Algorithm 3 computes the load of the current RZ for this current Comb according to two cases. In the first case (Case 1, line 18-line 19), the remaining tasks with their new execution time values and periods are considered as virtual new tasks, and if their execution intervals in Comb corresponds to their total periods, Algorithm 3 intuitively computes the load of the RZ as mentioned in line 19 by considering the occupation rate (CA/PA) of each virtual new task A and each latest task {B} in Comb on the current RZ.
In the second case (Case2), the longest period of time (Pmax) that could be shared by the tasks in Comb is determined in line 21 and the load of the RZ is studied during Pmax (line 22).
This step deals with all possible cases of execution conflicts on all the RZs. At the end of this step, we obtain at each iteration during the HP, the loads of each RZ produced by each combination of tasks giving overlapping execution intervals. Consequently, we can detect the possible overloads in the RZs(RZ-load>1). Some combinations might be included within other ones. When overloads are detected on some RZs, the next step resolves the problem either by performing migration of tasks respecting their preemption points or by incrementing the number of overloaded RZs until the overloads are covered.(c) Task Migration or Addition of RZs
Migration of tasks causing an overload on a given RZ during a combination of simultaneous executions might be total or partial. Total migration consists in replacing the entire execution of one or many tasks on another RZs. Partial migration consists in the reallocation of some execution sections within tasks predefined by their preemption points to nonoverloaded RZs. The migration is performed as explained by Algorithm4. The worst-case temporal complexity of Algorithm 4 is O(2NT*HP*NT*NZ). Algorithm 4 searches the combinations producing overloaded RZs obtained by Algorithm 3 (line 6). Firstly, Algorithm 4 starts by total migration (line 8–line 15) to avoid the preemption of tasks resulting in difficulties related to context switches. During each Comb causing overload, the algorithm extracts the execution interval of the task that provides the largest occupation rate in the current Comb (line 10). In the case of equality between tasks, the task producing the fewest RZs for total migration during the Comb should be selected. The algorithm then determines the execution iteration of the task corresponding to this extracted interval and checks whether the iteration is also studied in another nonoverloaded RZs. Should this be the case, total migration of the task is allowed, and the task is eliminated from the overloaded RZ (line 11). If there are several RZs accepting total migration of the selected task, the RZ which is least required by tasks in the Comb is chosen. In cases of equality, the least loaded RZ is kept. After each total migration of a task, Algorithm 4 updates the load of the RZ corresponding to Comb and checks whether it is no longer overloaded (line 12–line 14). When total migration fails to resolve the overload in the RZ, partial migration takes place (line 16–line 35). Partial migration reinitializes the load of the current RZ corresponding to Comb. It searches the tasks in Comb that give finite D with other RZs and omits their occupation rates from the combinations on these latter RZs and from the current overloaded RZ considering the iteration of each task in Comb and includes the omitted tasks in the set Task-migration. The RZs accepting the tasks of Comb and the RZ corresponding to Comb are inserted within the set RZ-migration (line 21). Algorithm 4 attributes weights to tasks within Task-migration according to their occupation rates in Comb and according to the numbers of RZs in RZ-migration producing finite D with them. The task yielding the best trade-off between the two parameters is selected (line 23). Within the selected task, partial migration tries to reallocate its predefined execution sections in RZs from RZ-migration without causing an overload (line 24). Partial migration promotes the biggest execution sections respecting this rule. It starts by placing the selected execution section on the RZ which is least required by the other tasks in Task-migration waiting for partial migration. In cases of equality, it starts with the least loaded RZ in RZ-migration. Algorithm 4 pursues the processing of these partial migrations until the set Task-migration is empty. If partial migration does not successfully map all the execution sections of a given task in Task-migration (line 26), Algorithm 4 reinitializes the loads of the RZs to their initial values before processing the Comb (line 27), stops its processing for the current Comb, and increments the number of the corresponding RZ to ⌈RZ-Load⌉ (line 28). When a given overloaded Comb is resolved by partial migration, Algorithm 4 takes into account the update of loads of all altered RZs (line 25) to be considered for the next Comb. Although migration might resolve many overloads for several combinations, it is still very difficult to perform as it is exhaustive and depends on the initial choices of tasks and RZs. One could consider the best case of studied migrations to minimize the number of added RZs. After each increment of RZ, the step must consider the added RZs to deal with the overloads of the remaining Comb not yet processed to avoid an excessive number of unusable RZs. As the proposed algorithm of migration is not exact, it might lead to an excessive number of RZs. This problem will be covered during resolution of mapping/scheduling which also optimizes the number of used RZs for the purpose of resource efficiency. However, an excess of RZs is very useful as it guarantees elimination of the infeasibility of analytic resolution and consequently, and it guarantees the feasibility of scheduling of the DAG.
At the end of this step, the number of RZs required to perform the scheduling of the chosen DAG on the FPGA is obtained. The resulting RZs constitute the target multi-reconfigurable-unit system where the scheduling of DAG will be conducted. The next step focuses essentially on determining the optimal valid scheduling that respects the predefined constraints.


### 3.3.4. Mapping and Scheduling Resolution

In the last step of the current stage, we concentrate on the resolution of mapping and scheduling tasks in the DAG on the resulting multi-reconfigurable-unit system. Mapping and scheduling are highly interlinked. It is well known that static multiprocessor scheduling of DAGs is performed by means of two actions: (i) assignment of an execution order expressed by temporal scheduling and (ii) assignment of processors expressed by mapping, for a set of tasks characterized by precedence and real-time constraints. With our methodology, based on a preemptive model, mapping consists in assigning each task to the most suitable RZs in terms of utilization of costly resources. Mapping is considered as spatial scheduling to a limited number of heterogeneous RZs. The scheduling searches the optimal scenario for task execution on RZs during the HP. At each execution iteration for a given task, it assigns for its execution sections specific times to launch their executions on the corresponding RZs. This scheduling is valid only when it satisfies predefined temporal constraints, and it should optimize the makespan of the graph, parallel efficiency, waiting time, and schedule response time. The proposed resolution leads to global static pipelined scheduling on a heterogeneous multi-reconfigurable-unit system because it is constructed at compile time, and it allows overlapping between execution iterations of distinct tasks on distinct RZs. Moreover, the problem of mapping/scheduling is a combinatorial optimization problem as it uses a discrete solution set and chooses the best combination of feasible assignments by optimizing a multiobjective function.In this paper, resolution of mapping/scheduling is performed by mixed integer nonlinear programming solver as it is well adapted for this kind of problem. The mapping/scheduling problem is modeled by the quadruplet (constants, variables, constraints, and objective function).ConstantsNT:Number of tasks constituting the DAGNZ:Number of RZs resulting from the taskmigration or addition of RZs analysisNP:Number of RB types existing in thetarget technologyi, o:The references of iterations ofexecutions during the HPj:The references of RZsA, B:The references of tasksk:The references of RB typesl, e:The references of preemption pointsin taskst:The references of times values,t∈{0,…,∞}D(A,RZj):The costD between task A and RZ RZjRBCostk:The cost of each RB typeHP:The hyperperiod in the DAGCA:The worst case execution time of taskAPA:The period of taskA which is equal toits relative deadlineNbrPreempA:The number of possible preemptionpoints within taskAPreempA,l:The set of possible preemption pointsof taskA. The first preemption pointfor all tasks is equal to 0SectionA,l:The execution section within taskAprovided by the predefinedpreemption pointlNbrIterA:The number of execution iterationsof taskA during the HPTimesValuest:The set of possible times assigned topreemption points during the HP.It is equal to{0,…,∞}PredA,B:Binary constant takes 1 when taskAhas a precedence constraint withtaskB in the DAGDependA:Binary constant takes 1 when taskAhas data dependence constraintswith tasks in the DAGConfigj:The configuration overhead ofRZjCom:The maximum value of time fortransmitting a data of unit lengthbetween two dependent tasksyA,B:The amount of data sent byB for Aexecution.Variables
TUnicityj,A,l,t,i
Binary variable takes 1 when the preemption pointl of task A is mapped to RZj at time t at iteration i. This variable ensures the link between mapping and scheduling. In our resolution, the mapping/scheduling problem is solved when binary values are assigned to all these variables.PTimeRZj,A,l,i
This variable represents the time value assigned to preemption pointl of task A on RZj at iteration i during the HP. This variable is not defined when RZj gives infinite D with task A. It is obtained as expressed by
(12)PTimeRZj,A,l,i=∑t0≤TimeValuest≤HPTUnicityj,A,l,t,i×TimeValuest,∀1≤j≤NZ,1≤A≤NT,1≤l≤NbrPreempA,1≤i≤NbrIterA,D(A,RZj)≠∞.PTimeA,l,i
This variable provides the time value assigned to preemption pointl of task A at iteration i during the HP and is calculated by means of
(13)PTimeA,l,i=∑1≤j≤NZD(A,RZj)≠∞⁡PTimeRZj,A,l,i,∀1≤A≤NT,1≤l≤NbrPreempA,1≤i≤NbrIterA.Occupationj,A
The total duration of execution of taskA on RZj, after achievement of mapping/scheduling; it is computed by summing up all the execution sections of A mapped to RZj. This variable is not defined when RZj gives infinite D with task A. It is obtained using
(14)Occupationj,A=∑l,i1≤l≤NbrPreempA1≤i≤NbrIterA⁡∑t0≤TimeValuest≤HP(TUnicityj,A,l,t,i×SectionA,l)∀1≤j≤NZ,1≤A≤NT,D(A,RZj)≠∞.Existj,A,l,i
This Binary variable tests whether the preemption pointl of task A during its execution iteration i is mapped to RZj. This variable is not defined when RZj gives infinite D with task A. It is obtained by means of
(15)Existj,A,l,i=∑t0≤TimeValuest≤HP⁡TUnicityj,A,l,t,i,∀1≤j≤NZ,1≤A≤NT,1≤l≤NbrPreempA,1≤i≤NbrIterA,D(A,RZj)≠∞.Constraints
Infeasibility of Mapping for Preemption Points
The constraint expressed by (16) prohibits the mapping of preemption points of task A to RZj giving infinite D with the task. Indeed, as explained in the second step of the task clustering stage, infinite D between a task and an RZ means that there is a lack of RBs in the RZ preventing task execution or an absence of RB types which are required by the task in the RZ. In addition, this constraint asserts that the time values chosen during mapping/scheduling for preemption points of tasks must be within the set of integers {0,…,HP},
(16)TUnicityj,A,l,t,i=0,whenD(A,RZj)=∞orTimeValuest>HP,∀1≤j≤NZ,1≤A≤NT,1≤l≤NbrPreempA,1≤i≤NbrIterA,0≤t≤∞.Uniqueness of Mapping/Scheduling Preemption Points on RZs
As expressed by (17), at each possible execution iteration i, if some tasks {A} need to be scheduled on RZj at a time referred to as t, one task can be executed on this RZ at this time,
(17)∑A,l,i1≤A≤NT1≤l≤NbrPreempA1≤i≤NbrIterAD(A,RZj)≠∞⁡TUnicityj,A,l,t,i≤1,∀1≤j≤NZ,0≤TimeValuest≤HP,0≤t≤∞.Uniqueness of RZs for Preemption Points
This constraint asserts that at each execution iterationi, each preemption point l of A must exist on a unique RZj (see (18)) and must be scheduled at a unique time referred to as t. This constraint also guarantees the achievement of task execution at each repetition, as all the preemption points delimiting the execution sections of the task are fitted on RZs at specified time values,
(18)∑j,t1≤j≤NZ0≤TimeValuest≤HPD(A,RZj)≠∞⁡TUnicityj,A,l,t,i=1,∀1≤A≤NT,1≤l≤NbrPreempA,1≤i≤NbrIterA.Order of Preemption Points of a Task
At each execution iterationi for a task A, the preemption points must be scheduled in order, that is, the time value assigned to a preemption point l+1 must be superior to the completion of execution section specified by the preemption point l. Equation (19) guarantees a consistent order of scheduling of preemption points for a given task and the completion of their corresponding execution sections,
(19)PTimeA,l+1,i≥PTimeA,l,i+SectionA,l,∀1≤A≤NT,1≤l≤NbrPreempA-1,1≤i≤NbrIterA.Order between Iterations
Based on (19), the constraint expressed by (20) requires that during each execution iteration i for a task A, the scheduling of tasks must lead to the completion of each execution section within A before the beginning of its next iteration (i+1). Simultaneous executions of distinct iterations for the same task are not permitted,
(20)PTimeA,NbrPreempA,i+SectionA,NbrPreempA≤PTimeA,1,i+1,∀1≤A≤NT,1≤i≤NbrIterA-1.Upper Bound of Task Execution
Based on (19) and (20), (21) indicates that for each scheduled preemption point for a given task A, at each execution iteration i, its execution section must be completed before the HP. Otherwise, the resulting scenario is not considered a feasible scheduling,
(21)PTimeA,NbrPreempA,NbrIterA+SectionA,NbrPreempA≤HP∀1≤A≤NT.Nonoverlapping Execution
This constraint eliminates task conflicts on a given RZ. For all execution iterations, when several tasks are scheduled on the same RZ, their predefined execution sections must not overlap (see (22)). This constraint is also applicable within the same task, that is, overlapping running between execution sections is not allowed either during the same iteration, which is implicitly expressed by (19) by the imposed order for preemption point scheduling, or between distinct iterations, which is implicitly expressed by the imposed order for execution iterations of a given task in (20). Equation (22) describes this constraint between two tasks A and B existing on the same RZj,
(22)Existj,A,l,i×Existj,B,e,o×(PTimeRZj,A,l,i+SectionA,l)≤PTimeRZj,B,e,o,orExistj,A,l,i×Existj,B,e,o×(PTimeRZj,B,e,o+SectionB,e)≤PTimeRZj,A,l,i,∀1≤A,B≤NT,1≤j≤NZ,1≤l≤NbrPreempA,1≤e≤NbrPreempB,1≤i≤NbrIterA,1≤o≤NbrIterB.Precedence and Dependence Constraints
Equation (23) defines the precedence and dependence constraints. At each possible execution iteration i of task A, if A has dependence links with tasks {B}, its execution for this iteration can be launched only if the running within ith execution iterations of all its predecessors {B} has been completed and the required data for A execution have been received,
(23)PTimeA,1,i≥PTimeB,NbrPreempB,i+SectionB,NbrPreempB+Com×yA,B∀1≤A,B≤NT,1≤i≤NbrIterB,PredB,A=1.Periodicity Constraint without Dependence Constraints
This constraint focuses on the periodic execution of tasks without predecessors in the DAG. Each taskA is repeated periodically according to its specified period PA in its functional model. Each repetition defines an execution iteration for the task. Equation (24) imposes constraints only on the first preemption point of the task as (19) defines an order for scheduling the preemption points in the same iteration which consequently will take into account the periodicity constraint for the other remaining preemption points,
(24)PTimeA,1,i≥(i-1)×PA∀1≤A≤NT,1≤i≤NbrIterA,DependA=0.Periodicity Constraint with Dependence Constraints
Equation (25) addresses tasks with predecessors in the DAG. These predecessors assert a dependence of execution on their successors at each repetition. Like for tasks without predecessors, tasks having dependence constraints with other tasks in the DAG must be repeated periodically as specified by their functional model and especially taking into consideration the first instants of completion of their predecessors. Indeed, a task with dependence constraints begins its first iteration after the execution achievement of all its predecessors and their data sending. Consequently, the periodicity constraint must consider the beginning time of these tasks with dependence constraints. Similarly, by means of (19), this constraint will be considered for all the preemption points,
(25)PTimeA,1,i≥max⁡BB≠APredB,A=1⁡(PTimeB,NbrPreempB,1+SectionB,NbrPreempB+Com×yA,BPTimeB,NbrPreempB,1)+(i-1)×PA,∀1≤A≤NT,1≤i≤NbrIterA,DependA=1.Deadline Constraint without Dependence Constraints
The key idea behind the constraint explained by (26) is to respect the strict real-time constraints in the case of the absence of dependence constraints. At each given execution iteration i for a task A without predecessors, the running of task A must be completed before its absolute deadline,
(26)PTimeA,NbrPreempA,i+SectionA,NbrPreempA≤i×PA∀1≤A≤NT,1≤i≤NbrIterA,DependA=0.Deadline Constraint with Dependence Constraints
Equation (27) adheres to the deadline constraint in the case of the existence of dependence constraints between tasks in the DAG. Knowing that the beginning of a given task A with predecessors {B} in the DAG is considered since the end of running of all its predecessors within their first execution iterations and the receipt of required data, the absolute deadline of A at each execution iteration i must be met as follows:
(27)PTimeA,NbrPreempA,i+SectionA,NbrPreempA≤max⁡BB≠APredB,A=1⁡(PTimeB,NbrPreempB,1+SectionB,NbrPreempB+Com×yA,BPTimeB,NbrPreempB,1)+i×PA,∀1≤A≤NT,1≤i≤NbrIterA,DependA=1.Objective Function(F)
The objective function guides resolution and helps to converge to the optimal solution. The minimization objective functionF in (28) defines the optimal solution for the mapping/scheduling sub-problem by means of six parameters. F promotes the solution that provides the best trade-off of lowest values for these parameters. The parameters are all considered important for our methodology and are weighted according to their ranges of values. However, F gives priority to the number of occupied RZs more than other parameters. In fact, F increases exponentially with the minimum growth of the number of used RZs. Preference for this parameter is explained by the fact that our methodology is strongly dependent on physical architecture; hence, the minimum number of RZs enabling scheduling and satisfying the strict predefined constraints must be determined in order to avoid resource wastage and its consequences,
(28)F=ln⁡(Param)+exp⁡⁡(NumberOfOccupiedRZs),Param=δ1×MakeSpan+δ2×WaitingTime+δ3×ResourceOptimization+δ4×MigrationNumber+δ5×ConfigurationOverhead.
MakeSpan
It is determined by the length of the obtained scheduling. This parameter is considered the most pertinent factor in multiprocessor scheduling of DAGs as it evaluates the efficiency of the performed scheduling in terms of parallelism on processors and execution speed. Equation (29) reduces the MakeSpan of the DAG by minimizing the time of finishing execution within the last execution iterations for all tasks as they are linked by precedence and dependence constraints. Consequently, as the execution iterations are also highly dependent, it is necessary to start the execution of a given task for each iteration as soon as possible in order to minimize the makespan of the DAG,
(29)MakeSpan=max⁡A1≤A≤NT⁡(PTimeA,NbrPreempA,NbrIterA+SectionA,NbrPreempA).WaitingTime
It is determined by the response time of the scheduling for task execution. By means of (30), WaitingTime is computed as the sum of differences between the obtained runtimes of the tasks during the scheduling span and their effective execution times. WaitingTime includes the waiting time of tasks in the ready queue of the scheduler waiting for execution when their dependence and periodicity constraints are satisfied and the blocking time when the task is preempted,
(30)WaitingTime=∑A1≤A≤NT(RunTimeA-NbrIterA×CA),RunTimeA=∑i1≤i≤NbrIterA((PTimeA,NbrPreempA,i+SectionA,NbrPreempA)-(i-1)×PAPTimeA,NbrPreempA,i)ifDependA=0,RunTimeA=∑i1≤i≤NbrIterA(max⁡BB≠APredB,A=1(PTimeA,NbrPreempA,i+SectionA,NbrPreempA)-max⁡(max⁡BB≠APredB,A=1⁡(PTimeB,NbrPreempB,1+SectionB,NbrPreempB+Com×yA,BPTimeB,NbrPreempB,1)+(i-1)×PA,max⁡BB≠APredB,A=1⁡(PTimeB,NbrPreempB,i+SectionB,NbrPreempB+Com×yA,BPTimeB,NbrPreempB,i)max⁡BB≠APredB,A=1)),elseResourceOptimization
It is related to the physical features of the chosen technology. The parameter considers resource wastage and the utilization of costly resources. Both issues are involved in costD computation in the first stage. Thus, resource optimization, using (31), targets mapping tasks with high occupation rates to the RZs providing the lowest cost D with them,
(31)ResourceOptimization=∑1≤A≤NT1≤j≤NZ⁡(D(A,RZj)2×Occupationj,A24-D(A,RZj)×Occupationj,AD(A,RZj)2×Occupationj,A24).MigrationNumber
Although the migration concept optimizes scheduling length, it helps to guarantee real-time constraints and to increase resource efficiency; it also raises configuration overhead. Bearing this in mind, we constructed (32) that aims at minimizing the number of migrations required. For a given task A, the first expression of (32), on the left of the summation, searches the number of migrations within the same execution iteration, and the second part of the summation calculates the performed migrations between iterations,
(32)MigrationNumber=∑1≤A≤NT1≤j≤NZ1≤i≤NbrIterA⁡∑1≤l<NbrPreempAExistj,A,l,i≠0,Existj,A,l+1,i=0⁡1+∑1≤A≤NT1≤j≤NZ⁡∑1≤i<NbrIterAExistj,A,NbrPreempA,i≠0,Existj,A,1,i+1=0⁡1.ConfigurationOverhead
During the scheduling span, we do not consider the configuration overhead before the task execution on the RZ. This configuration overhead is negligible, that is, according to several experimentations performed with Virtex 5 technology, which uses parallel high-speed configuration ports, it represents less than 10% of the computation time of the task and does not impact the real-time functioning. However, after scheduling has been achieved, the configuration overhead, that impacts scheduling performance and power consumption, is evaluated using (33). The configuration overhead parameter should be reduced during resolution of mapping/scheduling. Equation (33) includes four expressions in the summation. The first expression, Exp1, is the initial configuration when tasks are launched by the scheduler for their first execution iteration as they did not exist on the RZs. The second expression, Exp2, represents the configuration overhead required to configure a task that migrates from one RZ to another within the same iteration i; the third expression, Exp3, depicts the configuration overhead required by a task that has finished its execution on a given RZ for an iteration i and started its (i+1)th iteration by migrating to another RZ. The fourth expression, Exp4, computes the configuration overhead resulting from intermediate tasks preempting a given task running on the same RZ. The first part of Exp4 considers the configuration overhead required in cases where a task A, during iteration i, finishes its execution section delimited by preemption point l, then it is preempted by other tasks to perform execution sections, which is then followed by task A performing its l+1 execution section at a later stage on the same RZ. This event is detected by the binary variable CurrentIterj,A,l,i. This binary variable takes 1 if two successive execution sections for the same task at the same iteration are separated by one or more tasks on the same RZ. By means of variable InterIterj,A,NbrPreempA,i, the second part of Exp4 deals with situations during which a task finishes its last execution section for a given iteration i on an RZ and starts the first execution section of (i+1)th iteration on the same RZ after the execution of other execution sections of other tasks on the same RZ. This variable takes 1 when at least one other task runs on the same RZ between two successive execution iterations of the same task,
(33)ConfigurationOverhead=Exp1+Exp2+Exp3+Exp4Exp1=∑1≤A≤NT1≤j≤NZ0≤TimeValuest≤HP⁡TUnicityj,A,1,t,1×ConfigjExp2=∑1≤A≤NT1≤j≤NZ1≤i≤NbrIterA⁡∑1≤l<NbrPreempAExistj,A,l,i≠0,Existj,A,l+1,i=0⁡ConfigjExp3=∑1≤A≤NT1≤j≤NZ⁡∑1≤i<NbrIterAExistj,A,NbrPreempA,i≠0,Existj,A,1,i+1=0⁡ConfigjExp4=∑1≤A≤NT1≤j≤NZ1≤i≤NbrIterA1≤l<NbrPreempA⁡Configj×CurrentIterj,A,l,i+∑1≤A≤NT1≤j≤NZ1≤i<NbrIterA⁡Configj×InterIterj,A,NbrPreempA,i.NumberOfOccupiedRZs
As explained in the previous step (determination of task execution intervals and the number of RZs), the obtained number of RZs ensures the feasibility of scheduling but is not necessarily the optimal number for valid scheduling. Thus, for the purpose of resource efficiency, (34) searches the lowest possible number of RZs required for feasible real-time scheduling for the chosen DAG on a multi-reconfigurable-unit system,
(34)NumberOfOccupiedRZs=∑1≤j≤NZRZOccupationj≠0⁡1,RZOccupationj=∑A1≤A≤NT⁡Occupationj,A.
Other optimization parameters are also integrated in objective functionF, but they are not mentioned in the formulation above as they implicitly impact the makespan. These parameters optimize the solutions that launch the execution of tasks as soon as their predecessors terminate their computations. In addition, they aim to bring the beginning of the tasks closer to the start time of each repetition.
After resolution of the first sub-problem of mapping/scheduling tasks on RZs, the resulting RZs must be placed on the target device. The second sub-problem of task cluster placement is a well-known problem in reconfigurable computing systems, and it differentiates our problem of scheduling on reconfigurable devices from that on software multiprocessors, generally not constrained by the physical architecture of the homogeneous processors. The second sub-problem of RZ placement is described in the next and last stage of our proposed methodology and like mapping/scheduling; it is solved by means of mixed integer programming as it is considered to be a combinatorial optimization problem.


## 3.3.1. Checking of Precedence, Dependence, and Real-Time Rightness in DAG

The first temporal analysis does not take into account spatial constraints and considers that there is an available RZ for each task. It also considers the periodicity of tasks. The main objective of this analysis is only to validate the correctness of task precedence and dependences and real-time constraints in the studied DAG. It is conducted by means of three essential constraints.(a) Dependence Checking
More than precedence, we consider that the tasks related by an edge of precedence are also dependent. This means that the execution of a given task requires the data resulting from the execution of all its predecessors. This dependence is expressed by (7). Equation (7) focuses on periods and the amount of interchanged data between dependent tasks. It guarantees, when PA≥PB and A∈ΠB, that each data (xA,B) produced by task A in its repetition Ai is consumed by its successor B during its iterations of execution Bi or Bj>i. When PA≤PB and A∈ΠB, at each iteration of execution of B, it ensures that there are the sufficient data (yB,A) for B to be executed. 											(7)yB,A×⌊HPPB⌋=xA,B×⌊HPPA⌋,∀B,A∈πB.The previous equation eliminates the problem of data wastage and ensures that the data produced by all the iterations of each task are consumed by all the iterations of its successors. In this work, we focus on the case where PA≥PB, for all B,A∈πB.(b) Precedence Checking
As we work in the case ofPA≥PB, for all B,A∈πB, considering the periodicity constraint, this constraint claims that each iteration of execution Ai of a given task A may include only the iterations Bi or {Bj<i} of its successors {B} to ensure the correctness of the precedence constraint. During repetition Ai of a given task A, this constraint prohibits that Bi and {Bj>i} repetitions of its successors {B} coexist. In this way, during the HP, each ith execution of any task is preceded by the ith execution iterations of all its predecessors. To guarantee these rules, the following constraint expressed by (8) was developed to guide the selection of execution times and periods for tasks in the DAG:
(8)TreadyB+k×PB>TreadyA+(k-1)×PA,∀B,A∈πB,k∈N,1≤k≤NbrIterA.NbrIterA depicts the possible number of execution iterations of A during the HP. TreadyA and TreadyB are the ready times for tasks A and B without considering the spatial constraints. They are determined by searching the critical path corresponding to the task in the graph by using the ASAP (as soon as possible) technique. For each task B having a set of predecessors {A}, its ready time TreadyB is computed as follows
(9)TreadyB=max⁡{A∈πB}⁡(TreadyA+CA),TreadyB=0,ifπB=∅.(c) Real-Time Checking
Considering the periodicity constraint, this constraint analyses the respect of real-time constraints in the best case of spatial conditions in terms of number of RZs. By respecting the precedence and dependence constraints, (10) checks at each iteration whether each task may complete its execution before its strict absolute deadline. If the absolute deadline of the task for its last iteration exceeds the HP, the deadline then turns into the HP. As we work in the case PA≥PB, for all A∈πB, the second expression of (10) satisfies the deadline constraint for the remaining repetitions of task B when its predecessors {A} achieve all their execution iterations
(10)max⁡(TreadyA+k×PA+CA,TreadyB+k×PB)+CB≤min⁡⁡(TreadyB+(k+1)×PB,HP),∀B,A∈πB,k∈N,0≤k≤NbrIterA-1,TreadyB+k×PB⁡+CB≤min⁡⁡(TreadyB+(k+1)×PB,HP)∀B,k∈N,max⁡A∈πB⁡(NbrIterA)≤k≤NbrIterB-1.
Respect of the three previous constraints validates the selection of periods and execution times for periodic tasks in the graph for the scheduling with precedence, dependence constraints, and under strict real-time constraints on an unlimited number of reconfigurable units. Nevertheless, the following temporal and spatial analyses will extract the corresponding number of RZs that will satisfy these constraints. When the previous constraints are unreal, the DAG is considered invalid and consequently it will be rejected or the features of its tasks will be modified and evaluated again till it respects the constraints expressed by (7), (8), and (10).
Consequently, with our methodology, we depart from the temporal analysis to construct a suitable physical architecture allowing a feasible schedule. As a final step at this stage, after fixing the physical architecture of the multi-reconfigurable-unit system, analytic resolution of mapping/scheduling provides the optimal scheduling of DAGs on target technology.


## 3.3.2. Determination of Lists of Ready Times

The temporal analysis does not consider the physical constraints and searches all the ready times in each execution iteration for all tasks in the graph by respecting the precedence, dependence, periodicity, and real-time constraints. This analysis yields, by means of (11), the lists {TreadyminBi,…,TreadymaxBi} during which task B may start execution, where Bi denotes the ith iteration of task B within the HP. Outside this list, task B might not respect the predefined constraints, which would lead to unfeasible scheduling.For each taskB, TreadyminBi is the lower bound time to start task execution at its iteration i in order to respect its precedence, dependence, and periodicity constraints. TreadymaxBi is the upper bound time from which the task can no longer start execution if its strict deadline and the data dependency and precedence of its successors are to be respected. To compute the Treadymin of tasks, we start computing from the top of the DAG. For the Treadymax calculation, we start from the bottom of the DAG, and for both, we proceed using the breadth-first search strategy(11)TreadyminB1=0ifπB=∅,TreadyminBi=max⁡(max⁡A∈πB⁡(TreadyminAi+CA),rminBi),TreadymaxB1=min⁡(min⁡A∈φB⁡(TreadymaxA1),PB)-CB,φBisthesetofsuccessorsofB,TreadymaxBi/i>1=min⁡(min⁡A∈φB⁡(TreadymaxAi),rmaxBi+1,HP)-CB.rminBi and rmaxBi are the start times of the ith repetition of B according to its first ready times (TreadyminB1 and TreadymaxB1). Hence, they are determined by incrementing TreadyminB1 and TreadymaxB1 by PB. For example, if we have a task B with a period = 8, a hyperperiod HP=24, and we consider TreadyminB1=3 and TreadymaxB1=4, then rminB1=TreadyminB1=3, rminB2=3+8=11, rminB3=11+8=19, rmaxB1=TreadymaxB1=4, rmaxB2=4+8=12, rmaxB3=12+8=20.


## 3.3.3. Determination of Task Execution Intervals and the Number of RZs

This temporal and spatial analysis considers the RZ types resulting from the task clustering stage and searches the possible parallelism between tasks to study execution conflicts on the RZs. When an overload is detected in some RZs, the analysis starts by solving this problem through a migration mechanism; if migration does not produce a solution, it increments the number of overloaded RZs as required. This analysis searches first, by means of Algorithm2, the execution intervals of each task for each possible iteration during the HP, then, using Algorithm 3, it deals with the overlapping execution intervals on the RZs to search the possible overloads, and finally, it uses Algorithm 4 to try to solve the found overloads by the migration mechanism; when this latter mechanism fails, additional RZs are inserted in the architecture of the multi-reconfigurable-unit system to solve the persisting overloads.Algorithm 2:Search of execution intervals.
(1)A,B // Tasks(2)i // Natural, iterations of execution of task A(3)List-TreadyAi // the list of ready times for task A during ith iteration(4)TreadyAi // the ready times for task A during ith iteration(5)TreadyA // the ready times for task A from the current TreadyAi(6)Execution-IntervalAi=⊘ // the set of execution intervals for task A during ith iteration(7)for  all  tasks A  do(8)for  all  execution iterations i of task A  do(9)List-TreadyAi={TreadyminAi,…,TreadymaxAi}(10)if  i=1  then(11)Execution-IntervalAi = {[TreadyAi,min(TreadyAi+PA,minB∈φA(TreadymaxBi),HP)],∀TreadyAi∈List-TreadyAi}(12)else(13)for  all  TreadyA1∈List-TreadyA1  do(14)TreadyAi = First (List-TreadyAi)(15)for  all  TreadyA∈{TreadyAi,…,TreadymaxAi}  do(16)Execution-IntervalAi=Execution-IntervalAi⋃{[TreadyA,min(TreadyA1+i*PA,minB∈φA(TreadymaxBi),HP)], if TreadyA1+i*PA is chosen as upperbound for this interval then it must respect: TreadyA+CA≤TreadyA1+i*PA, if HP is chosen then it must respect: TreadyA+CA≤HP}(17)end  for(18)List-TreadyAi = next (List-TreadyAi)(19)end  for(20)end  if(21)end  for(22)end  forAlgorithm 3:Search of overlapping execution intervals and RZ loads.
(1)A,B,D // Tasks(2)i, j, k, m // Natural, iterations of execution of tasks(3)Execution-IntervalAi // The set of execution intervals for task A during ith iteration(4)Crossing-Combination // All the possible combinations of sets Execution-IntervalAi of distinct tasks that giveoverlapping execution intervals on a given RZ, duringHP(5)Comb // Combination of overlapping execution intervals depicted by [A-min, A-max](6)CDr // The remaining execution time within task D(7)PDr The remaining period within task D(8)Pmax // The period of conflict for a combination of overlapping execution intervals(9)for  all  iteration i  do(10)for  all  RZ  do(11)Crossing-Combination = {{Execution-IntervalAj}/⋂j≤iExecution-IntervalAj≠⊘}(12)Comb = one combination of overlapping execution intervals extracted from sets in Crossing-Combination.(13)for  all  Comb in Crossing-Combination  do(14)    InComb, search the latest tasks {B} in starting execution(15)    InComb, search all the remaining tasks {D} that are ready or start execution before {B} and determinetheir remaining execution times:CDr and their remaining periods: PDr(16)CDr=CD-(B-min-D-min)(17)PDr=PD-(B-min-D-min)(18)if  (∀D-min, D-min = TreadyD1+(k-1)*PD, ∀D-max, D-max=TreadyD1+k*PD, ∀B-min,B-min = TreadyB1+(m-1)*PB and ∀B-max, B-max = TreadyB1+m*PB/TreadyD1∈{TreadyminD1,…,TreadymaxD1}, TreadyB1∈{TreadyminB1,…,TreadymaxB1}, and k and m are theiterations from which the execution  intervals are taken respectively for tasks{D} and {B})  then(19)RZ-Load = ∑DCDr/PDr + ∑BCB/PB(20)else(21)Pmax=maxD(D-max-B-min)(22)RZ-Load = ∑DCDr/Pmax + ∑BCB/Pmax(23)end  if(24)end  for(25)end  for(26)end  forAlgorithm 4:Total and partial migration or addition of RZs.
(1)Comb // Combination of overlapping execution intervals(2)Non-overload-comb // Boolean controlling after migration whether RZ is no longer overloaded by Comb(3)RZ-Load// Load of the RZ corresponding to Comb(4)RZ-migration // The set of RZs helpful for partial migration(5)Task-migration // The set of tasks that might perform partial migration(6)for  all  Comb giving overloaded RZ  do(7)Non-overload-comb= False(8)while  (Non-overload-comb = False) and (Comb≠⊘)  do(9)    // Total migration of tasks(10)Select the interval from Comb that gives the most heavy occupation rate and discard it from Comb.(11)Check whether the iteration, corresponding to the execution interval of the selected task, is studied on anothernon-overload RZ and update the load of the overloaded RZ after the elimination of the selected task.(12)if  RZ-Load≤1  then(13)Non-overload-comb= True(14)end  if(15)end  while(16)if  Non-overload-comb=False  then(17)   ReinitializeRZ-Load and Comb with its tasks(18)Task-migration=⊘(19)RZ-migration=⊘(20)   // Partial migration of tasks(21)   Omit the tasks from the overloaded RZ, corresponding toComb, that are also acceptable by another RZs (D≠∞) andreduce their occupation rates from the loads of these RZs. These latter RZs with the overloaded RZ corresponding toComb are included in the set RZ-migration. The omitted tasks are included in Task-migration(22)while  Task-migration≠⊘  do(23)    InTask-migration set, start by the task that gives the best trade-off between least number of RZs in RZ-migrationwhere it could migrate and heaviest occupation rate in the overloaded RZ.(24)    DuringComb, within the selected task, choose the biggest execution sections that could be placed in RZs from thesetRZ-migration without overloading them.(25)    Update the load of RZs receiving execution sections from the selected task(26)if  Some execution sections of the selected task are not placed  then(27)     Reinitialize the loads of RZs inRZ-migration to values before processing Comb(28)     Increment the number of RZ corresponding toComb up to ⌈RZ-Load⌉, go to 6(29)else(30)     Discard the selected task fromTask-migration.(31)end  if(32)end  while(33)   // All the execution sections of tasks are placed(34)Non-overload-comb=True(35)end  if(36)end  for(a) Search of Execution Intervals
This step uses the functional model of tasks and determines their execution intervals by means of Algorithm2 of worst-case temporal complexity equal to O(NT*HP3). An execution interval for a given task at a given iteration is an interval during which the task can be executed while satisfying all the predefined constraints.
For each taskA in the DAG, Algorithm 2 produces the set of its possible execution intervals expressed by Execution-IntervalAi at each possible iteration i during the HP. When this algorithm processes the first iteration of task A, the set of its possible execution intervals is determined directly (line 11) considering the precalculated ready times in List-TreadyA1, and the periodicity and dependence constraints. For the next iterations, considering each possible TreadyA1 for the purpose of respecting the periodicity constraint (line 13), at each iteration i, Algorithm 2 searches all the corresponding execution intervals starting with each possible TreadyAi (line 14, line 15), and considering the dependence and the deadline constraints, and the HP to determine the upper bound for each execution interval (line 16). In line 18, in order to guarantee the periodicity and dependence constraints, progressing from a TreadyA1 to another in list List-TreadyA1, Algorithm 2 must shift the list List-TreadyAi by omitting its first element, since ready times in each iteration i are also linked to the ready times of the first iteration.(b) Search of Overlapping between Execution Intervals of Tasks in the Same RZ
For the first iteration, the parallel tasks on a given RZ are extracted directly from the DAG; hence, there is no parallel execution between a given task and its successors. However, in the next iterationsi, searching parallel tasks must respect some rules. For the next iterations i, for parallel efficiency, a given task could overlap with its successors during their iterations j(j<i) on the same RZ. Moreover, this step must also consider the execution conflicts on the same RZ for a given task in its iteration i and other tasks that are in the iterations j(j≤i) when there are no dependence constraints between them. This step prohibits simultaneous execution of several iterations of the same task.
The step defines for each task the possible RZs allowing its execution in terms of types and number of RBs based on computed costD and then searches the execution conflicts on the RZs using Algorithm 3. Algorithm 3 has a worst-case temporal complexity equal to O(NZ*2NT*HP).
During each iterationi, for each RZ, in order to find the parallel tasks with a finite cost D with the RZ, Algorithm 3 searches all the possible combinations of sets of execution intervals {Execution-IntervalAj} of all the tasks that can be executed on the current RZ and produce overlapping execution intervals respecting the rules described above (line 11). Then, from the resulting sets of execution intervals, Algorithm 3 extracts the execution intervals causing the conflicts in the current RZ which will result in Comb (line 12). Comb may contain two or more tasks. Each obtained Comb is processed individually to study the load of the RZ (line 13–line 24). For each Comb, we start the study only at the time at which all the tasks coexist to check for possible conflict and its consequence on the current RZ. Thus, Algorithm 3 searches the latest tasks {B} in Comb (line 14) and for tasks {D} that either have already started their executions and still running after {B} arriving or have been ready before {B} arriving; it searches their remaining execution times and periods (line 15–line 17) by promoting the tasks with the earliest deadlines and using the ASAP technique, especially in the case there are more than two tasks within the Comb. Finally, Algorithm 3 computes the load of the current RZ for this current Comb according to two cases. In the first case (Case 1, line 18-line 19), the remaining tasks with their new execution time values and periods are considered as virtual new tasks, and if their execution intervals in Comb corresponds to their total periods, Algorithm 3 intuitively computes the load of the RZ as mentioned in line 19 by considering the occupation rate (CA/PA) of each virtual new task A and each latest task {B} in Comb on the current RZ.
In the second case (Case2), the longest period of time (Pmax) that could be shared by the tasks in Comb is determined in line 21 and the load of the RZ is studied during Pmax (line 22).
This step deals with all possible cases of execution conflicts on all the RZs. At the end of this step, we obtain at each iteration during the HP, the loads of each RZ produced by each combination of tasks giving overlapping execution intervals. Consequently, we can detect the possible overloads in the RZs(RZ-load>1). Some combinations might be included within other ones. When overloads are detected on some RZs, the next step resolves the problem either by performing migration of tasks respecting their preemption points or by incrementing the number of overloaded RZs until the overloads are covered.(c) Task Migration or Addition of RZs
Migration of tasks causing an overload on a given RZ during a combination of simultaneous executions might be total or partial. Total migration consists in replacing the entire execution of one or many tasks on another RZs. Partial migration consists in the reallocation of some execution sections within tasks predefined by their preemption points to nonoverloaded RZs. The migration is performed as explained by Algorithm4. The worst-case temporal complexity of Algorithm 4 is O(2NT*HP*NT*NZ). Algorithm 4 searches the combinations producing overloaded RZs obtained by Algorithm 3 (line 6). Firstly, Algorithm 4 starts by total migration (line 8–line 15) to avoid the preemption of tasks resulting in difficulties related to context switches. During each Comb causing overload, the algorithm extracts the execution interval of the task that provides the largest occupation rate in the current Comb (line 10). In the case of equality between tasks, the task producing the fewest RZs for total migration during the Comb should be selected. The algorithm then determines the execution iteration of the task corresponding to this extracted interval and checks whether the iteration is also studied in another nonoverloaded RZs. Should this be the case, total migration of the task is allowed, and the task is eliminated from the overloaded RZ (line 11). If there are several RZs accepting total migration of the selected task, the RZ which is least required by tasks in the Comb is chosen. In cases of equality, the least loaded RZ is kept. After each total migration of a task, Algorithm 4 updates the load of the RZ corresponding to Comb and checks whether it is no longer overloaded (line 12–line 14). When total migration fails to resolve the overload in the RZ, partial migration takes place (line 16–line 35). Partial migration reinitializes the load of the current RZ corresponding to Comb. It searches the tasks in Comb that give finite D with other RZs and omits their occupation rates from the combinations on these latter RZs and from the current overloaded RZ considering the iteration of each task in Comb and includes the omitted tasks in the set Task-migration. The RZs accepting the tasks of Comb and the RZ corresponding to Comb are inserted within the set RZ-migration (line 21). Algorithm 4 attributes weights to tasks within Task-migration according to their occupation rates in Comb and according to the numbers of RZs in RZ-migration producing finite D with them. The task yielding the best trade-off between the two parameters is selected (line 23). Within the selected task, partial migration tries to reallocate its predefined execution sections in RZs from RZ-migration without causing an overload (line 24). Partial migration promotes the biggest execution sections respecting this rule. It starts by placing the selected execution section on the RZ which is least required by the other tasks in Task-migration waiting for partial migration. In cases of equality, it starts with the least loaded RZ in RZ-migration. Algorithm 4 pursues the processing of these partial migrations until the set Task-migration is empty. If partial migration does not successfully map all the execution sections of a given task in Task-migration (line 26), Algorithm 4 reinitializes the loads of the RZs to their initial values before processing the Comb (line 27), stops its processing for the current Comb, and increments the number of the corresponding RZ to ⌈RZ-Load⌉ (line 28). When a given overloaded Comb is resolved by partial migration, Algorithm 4 takes into account the update of loads of all altered RZs (line 25) to be considered for the next Comb. Although migration might resolve many overloads for several combinations, it is still very difficult to perform as it is exhaustive and depends on the initial choices of tasks and RZs. One could consider the best case of studied migrations to minimize the number of added RZs. After each increment of RZ, the step must consider the added RZs to deal with the overloads of the remaining Comb not yet processed to avoid an excessive number of unusable RZs. As the proposed algorithm of migration is not exact, it might lead to an excessive number of RZs. This problem will be covered during resolution of mapping/scheduling which also optimizes the number of used RZs for the purpose of resource efficiency. However, an excess of RZs is very useful as it guarantees elimination of the infeasibility of analytic resolution and consequently, and it guarantees the feasibility of scheduling of the DAG.
At the end of this step, the number of RZs required to perform the scheduling of the chosen DAG on the FPGA is obtained. The resulting RZs constitute the target multi-reconfigurable-unit system where the scheduling of DAG will be conducted. The next step focuses essentially on determining the optimal valid scheduling that respects the predefined constraints.


## 3.3.4. Mapping and Scheduling Resolution

In the last step of the current stage, we concentrate on the resolution of mapping and scheduling tasks in the DAG on the resulting multi-reconfigurable-unit system. Mapping and scheduling are highly interlinked. It is well known that static multiprocessor scheduling of DAGs is performed by means of two actions: (i) assignment of an execution order expressed by temporal scheduling and (ii) assignment of processors expressed by mapping, for a set of tasks characterized by precedence and real-time constraints. With our methodology, based on a preemptive model, mapping consists in assigning each task to the most suitable RZs in terms of utilization of costly resources. Mapping is considered as spatial scheduling to a limited number of heterogeneous RZs. The scheduling searches the optimal scenario for task execution on RZs during the HP. At each execution iteration for a given task, it assigns for its execution sections specific times to launch their executions on the corresponding RZs. This scheduling is valid only when it satisfies predefined temporal constraints, and it should optimize the makespan of the graph, parallel efficiency, waiting time, and schedule response time. The proposed resolution leads to global static pipelined scheduling on a heterogeneous multi-reconfigurable-unit system because it is constructed at compile time, and it allows overlapping between execution iterations of distinct tasks on distinct RZs. Moreover, the problem of mapping/scheduling is a combinatorial optimization problem as it uses a discrete solution set and chooses the best combination of feasible assignments by optimizing a multiobjective function.In this paper, resolution of mapping/scheduling is performed by mixed integer nonlinear programming solver as it is well adapted for this kind of problem. The mapping/scheduling problem is modeled by the quadruplet (constants, variables, constraints, and objective function).ConstantsNT:Number of tasks constituting the DAGNZ:Number of RZs resulting from the taskmigration or addition of RZs analysisNP:Number of RB types existing in thetarget technologyi, o:The references of iterations ofexecutions during the HPj:The references of RZsA, B:The references of tasksk:The references of RB typesl, e:The references of preemption pointsin taskst:The references of times values,t∈{0,…,∞}D(A,RZj):The costD between task A and RZ RZjRBCostk:The cost of each RB typeHP:The hyperperiod in the DAGCA:The worst case execution time of taskAPA:The period of taskA which is equal toits relative deadlineNbrPreempA:The number of possible preemptionpoints within taskAPreempA,l:The set of possible preemption pointsof taskA. The first preemption pointfor all tasks is equal to 0SectionA,l:The execution section within taskAprovided by the predefinedpreemption pointlNbrIterA:The number of execution iterationsof taskA during the HPTimesValuest:The set of possible times assigned topreemption points during the HP.It is equal to{0,…,∞}PredA,B:Binary constant takes 1 when taskAhas a precedence constraint withtaskB in the DAGDependA:Binary constant takes 1 when taskAhas data dependence constraintswith tasks in the DAGConfigj:The configuration overhead ofRZjCom:The maximum value of time fortransmitting a data of unit lengthbetween two dependent tasksyA,B:The amount of data sent byB for Aexecution.Variables
TUnicityj,A,l,t,i
Binary variable takes 1 when the preemption pointl of task A is mapped to RZj at time t at iteration i. This variable ensures the link between mapping and scheduling. In our resolution, the mapping/scheduling problem is solved when binary values are assigned to all these variables.PTimeRZj,A,l,i
This variable represents the time value assigned to preemption pointl of task A on RZj at iteration i during the HP. This variable is not defined when RZj gives infinite D with task A. It is obtained as expressed by
(12)PTimeRZj,A,l,i=∑t0≤TimeValuest≤HPTUnicityj,A,l,t,i×TimeValuest,∀1≤j≤NZ,1≤A≤NT,1≤l≤NbrPreempA,1≤i≤NbrIterA,D(A,RZj)≠∞.PTimeA,l,i
This variable provides the time value assigned to preemption pointl of task A at iteration i during the HP and is calculated by means of
(13)PTimeA,l,i=∑1≤j≤NZD(A,RZj)≠∞⁡PTimeRZj,A,l,i,∀1≤A≤NT,1≤l≤NbrPreempA,1≤i≤NbrIterA.Occupationj,A
The total duration of execution of taskA on RZj, after achievement of mapping/scheduling; it is computed by summing up all the execution sections of A mapped to RZj. This variable is not defined when RZj gives infinite D with task A. It is obtained using
(14)Occupationj,A=∑l,i1≤l≤NbrPreempA1≤i≤NbrIterA⁡∑t0≤TimeValuest≤HP(TUnicityj,A,l,t,i×SectionA,l)∀1≤j≤NZ,1≤A≤NT,D(A,RZj)≠∞.Existj,A,l,i
This Binary variable tests whether the preemption pointl of task A during its execution iteration i is mapped to RZj. This variable is not defined when RZj gives infinite D with task A. It is obtained by means of
(15)Existj,A,l,i=∑t0≤TimeValuest≤HP⁡TUnicityj,A,l,t,i,∀1≤j≤NZ,1≤A≤NT,1≤l≤NbrPreempA,1≤i≤NbrIterA,D(A,RZj)≠∞.Constraints
Infeasibility of Mapping for Preemption Points
The constraint expressed by (16) prohibits the mapping of preemption points of task A to RZj giving infinite D with the task. Indeed, as explained in the second step of the task clustering stage, infinite D between a task and an RZ means that there is a lack of RBs in the RZ preventing task execution or an absence of RB types which are required by the task in the RZ. In addition, this constraint asserts that the time values chosen during mapping/scheduling for preemption points of tasks must be within the set of integers {0,…,HP},
(16)TUnicityj,A,l,t,i=0,whenD(A,RZj)=∞orTimeValuest>HP,∀1≤j≤NZ,1≤A≤NT,1≤l≤NbrPreempA,1≤i≤NbrIterA,0≤t≤∞.Uniqueness of Mapping/Scheduling Preemption Points on RZs
As expressed by (17), at each possible execution iteration i, if some tasks {A} need to be scheduled on RZj at a time referred to as t, one task can be executed on this RZ at this time,
(17)∑A,l,i1≤A≤NT1≤l≤NbrPreempA1≤i≤NbrIterAD(A,RZj)≠∞⁡TUnicityj,A,l,t,i≤1,∀1≤j≤NZ,0≤TimeValuest≤HP,0≤t≤∞.Uniqueness of RZs for Preemption Points
This constraint asserts that at each execution iterationi, each preemption point l of A must exist on a unique RZj (see (18)) and must be scheduled at a unique time referred to as t. This constraint also guarantees the achievement of task execution at each repetition, as all the preemption points delimiting the execution sections of the task are fitted on RZs at specified time values,
(18)∑j,t1≤j≤NZ0≤TimeValuest≤HPD(A,RZj)≠∞⁡TUnicityj,A,l,t,i=1,∀1≤A≤NT,1≤l≤NbrPreempA,1≤i≤NbrIterA.Order of Preemption Points of a Task
At each execution iterationi for a task A, the preemption points must be scheduled in order, that is, the time value assigned to a preemption point l+1 must be superior to the completion of execution section specified by the preemption point l. Equation (19) guarantees a consistent order of scheduling of preemption points for a given task and the completion of their corresponding execution sections,
(19)PTimeA,l+1,i≥PTimeA,l,i+SectionA,l,∀1≤A≤NT,1≤l≤NbrPreempA-1,1≤i≤NbrIterA.Order between Iterations
Based on (19), the constraint expressed by (20) requires that during each execution iteration i for a task A, the scheduling of tasks must lead to the completion of each execution section within A before the beginning of its next iteration (i+1). Simultaneous executions of distinct iterations for the same task are not permitted,
(20)PTimeA,NbrPreempA,i+SectionA,NbrPreempA≤PTimeA,1,i+1,∀1≤A≤NT,1≤i≤NbrIterA-1.Upper Bound of Task Execution
Based on (19) and (20), (21) indicates that for each scheduled preemption point for a given task A, at each execution iteration i, its execution section must be completed before the HP. Otherwise, the resulting scenario is not considered a feasible scheduling,
(21)PTimeA,NbrPreempA,NbrIterA+SectionA,NbrPreempA≤HP∀1≤A≤NT.Nonoverlapping Execution
This constraint eliminates task conflicts on a given RZ. For all execution iterations, when several tasks are scheduled on the same RZ, their predefined execution sections must not overlap (see (22)). This constraint is also applicable within the same task, that is, overlapping running between execution sections is not allowed either during the same iteration, which is implicitly expressed by (19) by the imposed order for preemption point scheduling, or between distinct iterations, which is implicitly expressed by the imposed order for execution iterations of a given task in (20). Equation (22) describes this constraint between two tasks A and B existing on the same RZj,
(22)Existj,A,l,i×Existj,B,e,o×(PTimeRZj,A,l,i+SectionA,l)≤PTimeRZj,B,e,o,orExistj,A,l,i×Existj,B,e,o×(PTimeRZj,B,e,o+SectionB,e)≤PTimeRZj,A,l,i,∀1≤A,B≤NT,1≤j≤NZ,1≤l≤NbrPreempA,1≤e≤NbrPreempB,1≤i≤NbrIterA,1≤o≤NbrIterB.Precedence and Dependence Constraints
Equation (23) defines the precedence and dependence constraints. At each possible execution iteration i of task A, if A has dependence links with tasks {B}, its execution for this iteration can be launched only if the running within ith execution iterations of all its predecessors {B} has been completed and the required data for A execution have been received,
(23)PTimeA,1,i≥PTimeB,NbrPreempB,i+SectionB,NbrPreempB+Com×yA,B∀1≤A,B≤NT,1≤i≤NbrIterB,PredB,A=1.Periodicity Constraint without Dependence Constraints
This constraint focuses on the periodic execution of tasks without predecessors in the DAG. Each taskA is repeated periodically according to its specified period PA in its functional model. Each repetition defines an execution iteration for the task. Equation (24) imposes constraints only on the first preemption point of the task as (19) defines an order for scheduling the preemption points in the same iteration which consequently will take into account the periodicity constraint for the other remaining preemption points,
(24)PTimeA,1,i≥(i-1)×PA∀1≤A≤NT,1≤i≤NbrIterA,DependA=0.Periodicity Constraint with Dependence Constraints
Equation (25) addresses tasks with predecessors in the DAG. These predecessors assert a dependence of execution on their successors at each repetition. Like for tasks without predecessors, tasks having dependence constraints with other tasks in the DAG must be repeated periodically as specified by their functional model and especially taking into consideration the first instants of completion of their predecessors. Indeed, a task with dependence constraints begins its first iteration after the execution achievement of all its predecessors and their data sending. Consequently, the periodicity constraint must consider the beginning time of these tasks with dependence constraints. Similarly, by means of (19), this constraint will be considered for all the preemption points,
(25)PTimeA,1,i≥max⁡BB≠APredB,A=1⁡(PTimeB,NbrPreempB,1+SectionB,NbrPreempB+Com×yA,BPTimeB,NbrPreempB,1)+(i-1)×PA,∀1≤A≤NT,1≤i≤NbrIterA,DependA=1.Deadline Constraint without Dependence Constraints
The key idea behind the constraint explained by (26) is to respect the strict real-time constraints in the case of the absence of dependence constraints. At each given execution iteration i for a task A without predecessors, the running of task A must be completed before its absolute deadline,
(26)PTimeA,NbrPreempA,i+SectionA,NbrPreempA≤i×PA∀1≤A≤NT,1≤i≤NbrIterA,DependA=0.Deadline Constraint with Dependence Constraints
Equation (27) adheres to the deadline constraint in the case of the existence of dependence constraints between tasks in the DAG. Knowing that the beginning of a given task A with predecessors {B} in the DAG is considered since the end of running of all its predecessors within their first execution iterations and the receipt of required data, the absolute deadline of A at each execution iteration i must be met as follows:
(27)PTimeA,NbrPreempA,i+SectionA,NbrPreempA≤max⁡BB≠APredB,A=1⁡(PTimeB,NbrPreempB,1+SectionB,NbrPreempB+Com×yA,BPTimeB,NbrPreempB,1)+i×PA,∀1≤A≤NT,1≤i≤NbrIterA,DependA=1.Objective Function(F)
The objective function guides resolution and helps to converge to the optimal solution. The minimization objective functionF in (28) defines the optimal solution for the mapping/scheduling sub-problem by means of six parameters. F promotes the solution that provides the best trade-off of lowest values for these parameters. The parameters are all considered important for our methodology and are weighted according to their ranges of values. However, F gives priority to the number of occupied RZs more than other parameters. In fact, F increases exponentially with the minimum growth of the number of used RZs. Preference for this parameter is explained by the fact that our methodology is strongly dependent on physical architecture; hence, the minimum number of RZs enabling scheduling and satisfying the strict predefined constraints must be determined in order to avoid resource wastage and its consequences,
(28)F=ln⁡(Param)+exp⁡⁡(NumberOfOccupiedRZs),Param=δ1×MakeSpan+δ2×WaitingTime+δ3×ResourceOptimization+δ4×MigrationNumber+δ5×ConfigurationOverhead.
MakeSpan
It is determined by the length of the obtained scheduling. This parameter is considered the most pertinent factor in multiprocessor scheduling of DAGs as it evaluates the efficiency of the performed scheduling in terms of parallelism on processors and execution speed. Equation (29) reduces the MakeSpan of the DAG by minimizing the time of finishing execution within the last execution iterations for all tasks as they are linked by precedence and dependence constraints. Consequently, as the execution iterations are also highly dependent, it is necessary to start the execution of a given task for each iteration as soon as possible in order to minimize the makespan of the DAG,
(29)MakeSpan=max⁡A1≤A≤NT⁡(PTimeA,NbrPreempA,NbrIterA+SectionA,NbrPreempA).WaitingTime
It is determined by the response time of the scheduling for task execution. By means of (30), WaitingTime is computed as the sum of differences between the obtained runtimes of the tasks during the scheduling span and their effective execution times. WaitingTime includes the waiting time of tasks in the ready queue of the scheduler waiting for execution when their dependence and periodicity constraints are satisfied and the blocking time when the task is preempted,
(30)WaitingTime=∑A1≤A≤NT(RunTimeA-NbrIterA×CA),RunTimeA=∑i1≤i≤NbrIterA((PTimeA,NbrPreempA,i+SectionA,NbrPreempA)-(i-1)×PAPTimeA,NbrPreempA,i)ifDependA=0,RunTimeA=∑i1≤i≤NbrIterA(max⁡BB≠APredB,A=1(PTimeA,NbrPreempA,i+SectionA,NbrPreempA)-max⁡(max⁡BB≠APredB,A=1⁡(PTimeB,NbrPreempB,1+SectionB,NbrPreempB+Com×yA,BPTimeB,NbrPreempB,1)+(i-1)×PA,max⁡BB≠APredB,A=1⁡(PTimeB,NbrPreempB,i+SectionB,NbrPreempB+Com×yA,BPTimeB,NbrPreempB,i)max⁡BB≠APredB,A=1)),elseResourceOptimization
It is related to the physical features of the chosen technology. The parameter considers resource wastage and the utilization of costly resources. Both issues are involved in costD computation in the first stage. Thus, resource optimization, using (31), targets mapping tasks with high occupation rates to the RZs providing the lowest cost D with them,
(31)ResourceOptimization=∑1≤A≤NT1≤j≤NZ⁡(D(A,RZj)2×Occupationj,A24-D(A,RZj)×Occupationj,AD(A,RZj)2×Occupationj,A24).MigrationNumber
Although the migration concept optimizes scheduling length, it helps to guarantee real-time constraints and to increase resource efficiency; it also raises configuration overhead. Bearing this in mind, we constructed (32) that aims at minimizing the number of migrations required. For a given task A, the first expression of (32), on the left of the summation, searches the number of migrations within the same execution iteration, and the second part of the summation calculates the performed migrations between iterations,
(32)MigrationNumber=∑1≤A≤NT1≤j≤NZ1≤i≤NbrIterA⁡∑1≤l<NbrPreempAExistj,A,l,i≠0,Existj,A,l+1,i=0⁡1+∑1≤A≤NT1≤j≤NZ⁡∑1≤i<NbrIterAExistj,A,NbrPreempA,i≠0,Existj,A,1,i+1=0⁡1.ConfigurationOverhead
During the scheduling span, we do not consider the configuration overhead before the task execution on the RZ. This configuration overhead is negligible, that is, according to several experimentations performed with Virtex 5 technology, which uses parallel high-speed configuration ports, it represents less than 10% of the computation time of the task and does not impact the real-time functioning. However, after scheduling has been achieved, the configuration overhead, that impacts scheduling performance and power consumption, is evaluated using (33). The configuration overhead parameter should be reduced during resolution of mapping/scheduling. Equation (33) includes four expressions in the summation. The first expression, Exp1, is the initial configuration when tasks are launched by the scheduler for their first execution iteration as they did not exist on the RZs. The second expression, Exp2, represents the configuration overhead required to configure a task that migrates from one RZ to another within the same iteration i; the third expression, Exp3, depicts the configuration overhead required by a task that has finished its execution on a given RZ for an iteration i and started its (i+1)th iteration by migrating to another RZ. The fourth expression, Exp4, computes the configuration overhead resulting from intermediate tasks preempting a given task running on the same RZ. The first part of Exp4 considers the configuration overhead required in cases where a task A, during iteration i, finishes its execution section delimited by preemption point l, then it is preempted by other tasks to perform execution sections, which is then followed by task A performing its l+1 execution section at a later stage on the same RZ. This event is detected by the binary variable CurrentIterj,A,l,i. This binary variable takes 1 if two successive execution sections for the same task at the same iteration are separated by one or more tasks on the same RZ. By means of variable InterIterj,A,NbrPreempA,i, the second part of Exp4 deals with situations during which a task finishes its last execution section for a given iteration i on an RZ and starts the first execution section of (i+1)th iteration on the same RZ after the execution of other execution sections of other tasks on the same RZ. This variable takes 1 when at least one other task runs on the same RZ between two successive execution iterations of the same task,
(33)ConfigurationOverhead=Exp1+Exp2+Exp3+Exp4Exp1=∑1≤A≤NT1≤j≤NZ0≤TimeValuest≤HP⁡TUnicityj,A,1,t,1×ConfigjExp2=∑1≤A≤NT1≤j≤NZ1≤i≤NbrIterA⁡∑1≤l<NbrPreempAExistj,A,l,i≠0,Existj,A,l+1,i=0⁡ConfigjExp3=∑1≤A≤NT1≤j≤NZ⁡∑1≤i<NbrIterAExistj,A,NbrPreempA,i≠0,Existj,A,1,i+1=0⁡ConfigjExp4=∑1≤A≤NT1≤j≤NZ1≤i≤NbrIterA1≤l<NbrPreempA⁡Configj×CurrentIterj,A,l,i+∑1≤A≤NT1≤j≤NZ1≤i<NbrIterA⁡Configj×InterIterj,A,NbrPreempA,i.NumberOfOccupiedRZs
As explained in the previous step (determination of task execution intervals and the number of RZs), the obtained number of RZs ensures the feasibility of scheduling but is not necessarily the optimal number for valid scheduling. Thus, for the purpose of resource efficiency, (34) searches the lowest possible number of RZs required for feasible real-time scheduling for the chosen DAG on a multi-reconfigurable-unit system,
(34)NumberOfOccupiedRZs=∑1≤j≤NZRZOccupationj≠0⁡1,RZOccupationj=∑A1≤A≤NT⁡Occupationj,A.
Other optimization parameters are also integrated in objective functionF, but they are not mentioned in the formulation above as they implicitly impact the makespan. These parameters optimize the solutions that launch the execution of tasks as soon as their predecessors terminate their computations. In addition, they aim to bring the beginning of the tasks closer to the start time of each repetition.
After resolution of the first sub-problem of mapping/scheduling tasks on RZs, the resulting RZs must be placed on the target device. The second sub-problem of task cluster placement is a well-known problem in reconfigurable computing systems, and it differentiates our problem of scheduling on reconfigurable devices from that on software multiprocessors, generally not constrained by the physical architecture of the homogeneous processors. The second sub-problem of RZ placement is described in the next and last stage of our proposed methodology and like mapping/scheduling; it is solved by means of mixed integer programming as it is considered to be a combinatorial optimization problem.


## 3.4. Partitioning of Reconfigurable Device and Fitting of RZs

In general, the problem of hardware task placement includes two primary subfunctions: (i)partitioning, which handles free resource space on the reconfigurable device to identify potential sites enabling hardware task execution and (ii) fitting, which, according to the chosen criteria, selects a feasible placement solution among sites provided by the partitioning to fit the hardware task on a suitable physical location. Several research works have been proposed for the placement of hardware tasks on reconfigurable devices, and placement can be divided into on-line and off-line placement. For on-line placement, most scenarios propose as a partitioning technique to search for the maximal empty physical rectangles in the free space to avoid the resource wastage. For example, the two techniques proposed by Bazargan et al. in [13], one referred to as “Keeping  All  Maximal  Empty  Rectangles” searches all overlapping maximal empty rectangles and the other referred to as “Keeping  Nonoverlapping  Empty  Rectangles” keeps only the distinct holes in the free space. In [14], Walder et al. describe efficient partitioning algorithms, the main one being the On-The-Fly (OTF) partitioner which resizes empty rectangles only if the new arrived task overlaps them. Handa and Vemuri introduce staircase partitioning in [15]. Marconi et al. extend in [16] Bazargan’s partitioner by means of an Intelligent  Merging (IM) algorithm that dynamically combines three techniques for managing free resources. In [17], Ahmadinia et al. present a new method of on-line partitioning which manages occupied space on devices rather than free space, given the difficulty of managing empty space and the resulting vast increase in empty rectangles. Regarding the fitting subfunction, the works are essentially based on bin-packing rules, such as in [13] which describes the First  Fit, Best  Fit, and Bottom  left bin-packing algorithms. In [14], Walder et al. employ a hash matrix to perform fitting based on Best  Fit, Worst  Fit, Best  Fit  with  Exact  Fit, and Worst  Fit  with  Exact  Fit algorithms. In [17], Ahmadinia et al. fit tasks on sites, reducing communication costs, by means of the Nearest  Possible  Position algorithm. For off-line placement, many research works deal with metaheuristics such as simulated annealing, greedy research, and Keeping  All  Maximal  Empty  Rectangle-Best  Fit as described in [13]. In [18], ElGindy et al. describe task rearrangement by using a genetic algorithm approach with the First  Fit strategy. Considering task placement as a 2D packing problem, researchers propose off-line heuristics such as Lodi et al. who describe the Next-Fit  Decreasing  Height, First-Fit  Decreasing  Height, and Best-Fit  Decreasing  height algorithms in [19], as well as the Floor-Ceiling and Knapsack  packing algorithms in [20]. Integer linear programming is also proposed by Panainte et al. in [21] to model the problem of hardware task placement by minimizing the resources area that is reconfigured at runtime.With our methodology, we focus on off-line placement of RZs on reconfigurable devices. As the reconfigurable devices afford a limited number of reconfigurable resources and DAG includes bounded numbers of tasks, analytic resolution of the placement sub-problem is the recommended method as it guarantees the optimal solution to perform efficient allocation of tasks on FPGA. The placement of RZs is a combinatorial mono-objective problem. It consists in searching for suitable coordinates for each RZ in the FPGA among all the possible combinations of discrete coordinates. In this section, similarly to the mapping/scheduling sub-problem, the resolution of RZ placement on the reconfigurable device is accomplished through mixed integer programming and optimizes resource efficiency. The achievement of RZ placement results in a 2D physical locations for each task cluster. These physical locations are depicted by reconfigurable physical blocs (RPBs) and are represented by their RB model as described in (35). RZs are abstractions of hardware task clusters, and RPBs are the final reconfigurable units where tasks may be executed. With the concept of run-time partial reconfiguration, after the mapping/scheduling results are obtained respecting the strict predefined constraints and optimizing several criteria, task execution sections are reconfigured and executed on RPBs as restricted by the schedule scenario. Thus, the task bitstreams on their associated RPBs are created at compile time. These bitstreams are used during the DAG running as indicated by scheduling which specifies the corresponding state for each task on each RPB,(35)RPBj_RB={γj,kRBk},γj,k∈N,1≤j≤NZ,1≤k≤NP.As shown in Figure7, the partitioned RPBs on a reconfigurable device for a given RZ must include all its required RB types to ensure the execution of the tasks. The partitioned RPBs for a given RZ might contain some RBs that are not required by the RZ. For instance, RB4 is inserted within RPB3 but is not used by the corresponding RZ. This resource inefficiency is explained by the rectangular shape of the RPBs. Thus, the number of RBs included in the RPB could exceed the required RBs in the RZ. Resource inefficiency is also due to the heterogeneity of the device; partitioning could book some RBs which are not used by the RZ. RB utilization efficiency is an important metric parameter for evaluating placement quality. During RZ placement resolution, we focus on fitting RZs as closely as possible to RPBs in terms of number and types of RBs.Figure 7
Example of RPBs for RZ.By means of mixed integer linear programming solver, both the partitioning and fitting subfunctions are solved simultaneously. The RZ placement sub-problem is modeled by the quadruplets (Constants, Variables, Constraints, and Objective Function).ConstantsNZ:Number of RZs resulting frommapping/scheduling resolutionNP:Number of RB types existing inthe target technology RZfeatures, RB featuresDevice featuresDevice_Width:The width of the deviceDevice_Height:The height of the deviceDevice_RB:The RB model of the device.Variables
Placement resolution consists in assigning discrete values for the four coordinates specifying theRPBj for each RZj. Each RPBj is constructed by four coordinates:Xj:The abscissa of the upper left vertex ofRPBjYj:The ordinate of the upper left vertex ofRPBjWRPBj:The abscissa of the upper right vertex ofRPBjHRPBj:The ordinate of the bottom left vertex ofRPBj.Constraints
Heterogeneity Constraint
As RZs are fitted on RPBs, during RPB partitioning, the number of each RB type within the RPBs (Xj, WRPBj, Yj, HRPBj) must be greater than or equal to those in the RZs (βj,k) as formulated by (36) in order to satisfy the RB requirements of the RZs. Because of the heterogeneity of RBs in the device and the rectangular shape of RPBs, the partitioned RPBs could include some RB types not required by the RZs. Moreover, the number of RB types in the RPBs and included in the RZs might exceed that required by the RZs. This resource inefficiency is minimized by means of the objective function,
(36)βj,k≤∑Xj≤m≤WRPBjYj≤n≤HRPBj⁡∑device_RB[m][n]=RBk1,∀1≤j≤NZ,1≤k≤NP,RZj_RB={βj,kRBk},RPBj(Xj,WRPBj,Yj,HRPBj).Nonoverlapping between RPBs
As expressed by (37), this constraint restricts the fitting of RZs on nonoverlapping RPBs
(37)Xq>WRPBjorXj>WRPBqorYq>HRPBjorYj>HRPBq,∀j≠q,1≤j,q≤NZ.Objective Function(F)
Objective functionF comprises one parameter which is ResourceEfficiency. This primordial parameter focuses on finding the closest RPB partitioned on the FPGA to fit each RZ in terms of number and types of RBs. By respecting both previous constraints, (38) assesses placement quality after RZ insertion on the selected RPBs in order to achieve the optimal solution. Increasing resource efficiency reduces configuration overhead,
(38)ResourceEfficiency=∑1≤j≤NZ1≤k≤NP⁡RBCostk×(γj,k-βj,k),RPBjRB={γj,kRBk},RZj_RB={βj,kRBk},1≤j≤NZ,1≤k≤NP.
Both subproblems, that is, (i) mapping/scheduling tasks on RZs and (ii) partitioning/fitting RZs on the FPGA, are successively solved by means of powerful solvers dedicated by the AIMMS [22] environment. The chosen solvers for mixed integer programming satisfy predefined constraints and provide an optimal solution in an acceptable time frame. The following section shows how our proposed methodology may be applied to an example of DAG on Virtex 5 technology; the section also evaluates scheduling and placement quality.


## 4. Application and Results

The experiments were separated into two parts. The first part focuses on constructing the DAG as restricted by the rules of the mapping/scheduling stage, detailing the performed analysis and showing the results of task mapping/scheduling on the resulting RZs with a performance evaluation. The second part demonstrates placement resolution of the RZs on the reconfigurable device, Virtex 5 FX70T (ML507 board), and describes the metrics used to measure placement quality.To illustrate the methodology proposed for static scheduling of DAGs on multi-reconfigurable-unit systems with precedence and deadline constraints, we designed the fully connected DAG shown in Figure8. Tasks were selected from opencores (http://www.opencores.org/).Figure 8
Tasks in the DAG.Each task is characterized by its worst-case execution time (WCET) which also integrates the communication latency for data sending to task successors, its period (relative deadline), and the set of preemption points. The number of needed slices is also synthesized for each task. In the slices, either only LUTs are used or only registers are used or both of them are used. The number of slices used by the task for LUTs and those for registers are mentioned in the third column of Table2.Table 2
Task features.
ReferenceNameSlices (LUTs/registers)WCET (μs)Period (ms)Configuration overhead (μs)Preemption points (μs)RB modelAReed-Solomon2234/122426576500111614770, 20200{8RB1, 7RB2, 1RB3, 1RB4}BAES1150/507427335006755000, 11000, 23000, 30000{5RB1, 5RB2, 1RB3, 1RB4}CIIR678/565118052505243334, 10000{4RB1, 1RB2, 0RB3, 1RB4}DFFT2333/20101180625011995000, 11667{9RB1, 7RB2, 0RB3, 1RB4}EBasic DES387/192222802501887500, 15000, 19000{2RB1, 2RB2, 0RB3, 0RB4}The configuration overheads were computed by (3) and by using our own IP based on the ICAP reconfiguration port having a width of 32 bits and a frequency of 100 MHz. Values on the DAG edges represent the average number of packets of 16 words of 32 bits for communication between tasks.With the Virtex 5 technology [23], there are four main resource types, that is, CLBL, CLBM, BRAM, and DSP. Considering reconfiguration granularity, the RBs in Virtex 5 are vertical stacks composed of the same type of resources: RB1 (20 CLBMs), RB2 (20 CLBLs), RB3 (4 BRAMs), and RB4 (8 DSPs). In our application, for Virtex 5 FX70T, we considered that the lower the number of the RB types on the device and the higher its functioning speed, the more its cost would increase. We, respectively, assigned 16, 10, 168, and 194 as the RBCost for RB1, RB2, RB3, and RB4. We modeled the Virtex 5 FPGA and the hardware tasks with their RB-models. The task features are shown in Table 2.The overview functioning of selected tasks is described below.Reed-Solomon(A)
It is an error correcting code that works by oversampling the Galouee’s field polynomial constructed from the data to be coded. It is widely used to recover data from possible errors that occur during disk reading.AES(B)
Advanced encryption standard can decrypt input data using 256-bit key.IIR(C)
It performs infinite impulse response low-pass filter which cut off frequency in the range of 0.1 to 0.4 of the sampling frequency.FFT(D)
It performs 64 points Fast Fourier Transform where the data and coefficients are adjustable in the range 8 to 16 bits.Basic DES(E)
It performs single Data Encryption Standard by processing 16 identical rounds. Each round encrypts 32-bit block using 64-bit key to provide 32-bit output block.We applied the proposed methodology for placement and scheduling of DAGs on reconfigurable devices and obtained the following results.


### 4.1. Task Clustering Results

This stage executes Algorithm1 which results in RZ types (RZ1, RZ2, RZ3) represented by their RB models in the first column of Table 3. RZ1 is inserted by A and B, RZ2 is provided by C and D, and task E creates RZ3.Table 3
RZ types andD costs.
ABCDERZ1{8RB1, 7RB2, 1RB3, 1RB4}068292∞448RZ2{9RB1, 7RB2, 0RB3, 1RB4}∞∞1400356RZ3{2RB1, 2RB2, 0RB3, 0RB4}∞∞∞∞0When the maximal numbers of RBs within a constructed RZ are provided by several tasks, the configuration overhead of the RZ must be recomputed as described by (3). In our application, the maximum numbers of RBs within RZs are created by the same task. Thus, the RZ configuration overheads are provided by the predefined task features shown in Table 2. The second step of this stage computes the costs D between the DAG tasks and the resulting RZs. In Table 3, the bold numbers are the lowest costs D for tasks with the most suitable RZs.The resolution of scheduling of the chosen DAG on Virtex 5 FX70T is detailed in Sections4.2 and 4.3.


### 4.2. Mapping/Scheduling Results and Scheduling Quality Evaluation

DAG behavior is studied within the time interval (HP) of a period equal to the least common multiple of the periods of its tasks which is equal to 500 ms. Consequently, the execution iterations of tasks during the HP are deducted as follows:(39)NbrIterA=⌊HPPA⌋=⌊500500⌋=1,NbrIterB=1,NbrIterC=2,NbrIterD=2,NbrIterE=2.The three steps preceding mapping/scheduling resolution are detailed hereunder. In the remaining sections of the paper, the values are expressed inμs.


#### 4.2.1. Checking of Precedence, Dependence, and Real-Time Rightness in the DAG

The constraints for checking precedence, dependence, and real-time rightness in the proposed DAG are detailed below.Dependence Checking
In Figure8, it is obvious that the periods of tasks between the levels are guarded or dubbed. Thus, the successors are more repetitive than the predecessors.
In this case, all the data produced on an edge linking a source task and its successor must be sufficient and consumed by the latter task. As can be seen in Figure8, the constraint expressed by (7) is satisfied for all the edges. For example, task B produces at its unique execution iteration a data of size xB,C equal to 7812.5 packets on its outgoing edge. These data are consumed totally by its first successor C during its two iterations where it consumes yC,B (3906.25 packets) data at each iteration. A similar remark can be made for data interchanged on the edge linking B and D.Precedence Checking
This constraint is satisfied by all the interdependent tasks in the DAG and is checked by means of (8) and (9). TreadyA=0, TreadyB=0, TreadyC=max(CA,CB)=42733, TreadyD=CB=42733, TreadyE=max(TreadyC+CC,TreadyD+CD)=max(42733+11805,42733+11806)=54539.
TaskC and Task B Precedence:
(40)K=1:42733+250000=292733>0.TaskC and Task A Precedence:
(41)K=1:42733+250000=292733>0.TaskD and Task B Precedence:
(42)K=1:42733+250000=292733>0.TaskC and Task E Precedence:
(43)K=1:54539+250000=304539>42733,K=2:54539+2*250000=554539>42733+250000=292733.TaskD and Task E Precedence:
(44)K=1:54539+250000=304539>42733,K=2:54539+2*250000=554539>42733+250000=292733.
The above tests prove that each execution iterationAi of a given task A includes only execution iteration Bi or iterations preceding Bi of each successor B. Consequently, the precedences between tasks in the chosen DAG are correct.Real-Time Checking
For the purpose of real-time functioning, (10) considers dependence constraints between tasks and makes it possible to verify, in the best case of spatial conditions and by providing an RZ for each task, the rightness of real-time functioning according to computation times and periods assigned to tasks in the DAG.
An example of testing real-time constraints for taskC is shown hereunder.TaskC
(45)ΠC={A,B},K=0:max⁡(0+26576,42733+0)+11805=54538≤min⁡(42733+250000,500000)=292733(A),max⁡(0+42733,42733+0)+11805=54538≤min⁡(42733+250000,500000)=292733(B)K=1:(42733+250000)+11805=304538≤min⁡(42733+2*250000,500000)=500000.
By providing an RZ for each task, the deadlines of the tasks are met taking into consideration the dependence and precedence constraints.The above three tests validate the chosen graph in terms of dependence, precedence, and real-time constraints and in the following section; spatial/temporal analyses are performed in order to determine the required number of RZs allowing valid scheduling for the DAG.


#### 4.2.2. Determination of Lists of Ready Times

The first temporal analysis uses (11) to search the ready times of tasks which are helpful to limit execution intervals. Without considering the number of available reconfigurable units and taking into account precedence, dependence, periodicity, and real-time constraints, the ready times are determined as shown in Figure 9.Figure 9
Treadymin and Treadymax of tasks in the DAG.


#### 4.2.3. Determination of Task Execution Intervals and the Number of RZs

The first step of this spatial/temporal analysis uses Algorithm2 to determine the possible execution intervals of tasks based on lists of ready times and respecting specified constraints. The possible execution intervals for tasks in the DAG are shown below(46)Execution-IntervalA1={[0,215915],[1,215915],…,[i,215915],…,[189339,215915]},Execution-IntervalB1={[0,215914],[1,215914],…,[i,215914],…[173181,215914]},Execution-IntervalC1={[42733,227720],[42734,227720],…,[215915,227720]},Execution-IntervalC2={[292733,477720],[292734,477720],…,[465915,477720]},Execution-IntervalD1={[42733,227720],[42734,227720],…,[215914,227720]},Execution-IntervalD2={[292733,477720],[292734,477720],…,[465914,477720]},Execution-IntervalE1={[54539,304539],[54540,304540],…,[i,i+PE],…,[227720,477720]},Execution-IntervalE2={[304539,HP],[304540,HP],…,[477720,HP]}.
Using Algorithm 3, the analysis therefore integrates the spatial aspect and studies possible conflicts between tasks in shared RZs to detect possible overloads. Algorithm 3 must respect the rules explained in Section 3.3.3(b) to search the possible overlapping execution intervals. At each iteration, for each RZ, Algorithm 3 searches all the combinations of tasks causing overlapping execution intervals and inserts them in Crossing-Combination and computes the loads of RZs according to two cases as detailed as follows.Iteration 1
RZ1.   Crossing-Combination={{Execution-IntervalA1, Execution-IntervalB1}}. This Crossing-Combination contains several combinations of overlapping execution intervals between A and B. In the worst case of overlapping, such as the overlapping between [0,215915] from Execution-IntervalA1 and [0,215914] from Execution-IntervalB1, the load of RZ1 obtained by Case 2 is 32% satisfying the predefined constraints. RZ2.  Crossing-Combination={{Execution-IntervalC1, Execution-IntervalD1}}. Similarly, this Crossing-Combination provides several combinations of overlapping execution intervals between C and D. In the worst case of overlapping, such as when both tasks have confused execution intervals equal to [42733,227720], the load of RZ2 obtained in Case 2 is 12%. Another possible solution consists in total migration, as expressed by Algorithm 4, of task C to the RZ RZ1 to improve execution parallelism and to minimize the makespan of the DAG. Thus, as soon as tasks A, B computations are achieved, tasks C and D may be launched, respectively, on RZ1 and RZ2.
During the first iteration, no combination of detected overlapping execution intervals causes an overload on RZs.Iteration 2
RZ2.   Crossing-Combination={{Execution-IntervalC2, Execution-IntervalD2},{Execution-IntervalC2,Execution-IntervalD2,Execution-IntervalE1},{Execution-IntervalE1,Execution-IntervalD2},{Execution-IntervalE1, Execution-IntervalC2}}{Execution-IntervalC2, Execution-IntervalD2}: As with the first iteration, all the combinations of overlapping execution intervals between tasks C and D do not cause an overload on RZ2. The load of RZ2, in the worst case of confused execution intervals, is equal to 12%. Hence, in the worst case, tasks C and D could be executed consequently on RZ2 respecting all the predefined constraints.
As expressed by the rules set out in Section3.3.3(b), detection of conflicting tasks must consider current and preceding iterations.
{Execution-IntervalC2, Execution-IntervalD2, Execution-IntervalE1}: This set provides many combinations of overlapping execution intervals between tasks C, D, and E. However, following Algorithm 3 and the optimization parameters for reducing the makespan as explained at the end of mapping/scheduling resolution, task E starts its first iteration immediately after the achievement of its predecessors C and D which is equal, in the worst case, to 227720 μs, and RZ2 is idle at this time. Consequently, according to this start time of the first repetition, task E finishes its execution at 250 ms which is not attainable by the least start time of the second iterations of C and D, equal to 292733 μs. Thus, this set leads to no overlapping of execution between C, D, and E and becomes equivalent to the Crossing-Combination set: {Execution-IntervalC2,Execution-IntervalD2}. Another possible solution for this set is total migration of C to RZ1 and E to RZ3. This solution guarantees efficient parallelism between task computations.
{Execution-IntervalE1, Execution-IntervalD2}, {Execution-IntervalE1, Execution-IntervalC2}: As explained for the previous set, these sets of overlapping execution intervals do not cause an overload on RZ2.RZ1
Crossing-Combination={{Execution-IntervalE1, Execution-IntervalC2}}. As described for RZ2 with the last three sets, tasks C and E do not cause overloads on RZ1 during this Crossing-Combination. In fact, application of Algorithm 3 and the optimization parameters results in no remaining execution of the first repetition of E when C starts its second execution iteration.
After these spatial and temporal analyses, one can conclude there is no need to perform migration or to add other RZs. The three RZs resulting from the clustering stage are sufficient to perform valid scheduling of the chosen DAG. Thus, RZ1, RZ2, and RZ3 represent the multi-reconfigurable-unit system for DAG scheduling. Based on powerful solvers dedicated by the AIMMS environment, we obtained the following mapping/scheduling which is evaluated in the next section.


#### 4.2.4. Mapping and Scheduling Resolution

Figure10 describes the mapping/scheduling obtained for five tasks in the DAG on three RZs. As the number of RZs is the highest priority parameter in the objective function, the resolution concludes that for scheduling this DAG, only two RZs are required. RZ3 is not used, and hence it will not be placed on Virtex 5 FX70T in the third stage. The elimination of RZ3 enhances resource efficiency and enables the DAG to be extended and performed on the FPGA for future needs. RZ1 and RZ2 are selected by the solver to remain in the multi-reconfigurable-unit system since A and B can execute only on RZ1, task D can execute only on RZ2, and tasks C and E can run on both RZs.Figure 10
Mapping/scheduling resolution.The obtained mapping/scheduling takes into account all the optimization parameters described in the sub-problem formulation and satisfies the specified constraints. TasksA and B launch their computations first as they have no predecessors, and both can only execute on RZ1. To reduce the makespan of the DAG, the scheduler decides the preemption of A at its second preemption point (14770 μs) to enable the execution of task B, the termination of which permits the execution of task D on RZ2. The scheduler decides the execution of A before B in order to reduce the span between the executions of dependent tasks expressed by the dependence between C, D, and E. Hence, the scheduler promotes the solution that starts C immediately after completion of A and begins the execution of E once its predecessors C and D complete execution as reinforced by the optimization parameters explained at the end of mapping/scheduling resolution. These parameters aim at bringing closer the execution start of each task to the completion of its predecessors. C and E can execute on RZ1 and RZ2. The mapping assigns their executions to RZ2 as this RZ provides the best utilization of costly resources guided by their costs D. For the purpose of fully exploiting the multi-reconfigurable-unit system and to increase parallel efficiency, task A resumes its execution simultaneously with the start time of the first repetition of task D at 57503 μs. In their second execution iterations, respecting the periodicity and precedence constraints tasks C, D, and E are performed on their optimal RZ, that is, RZ2, to optimize resource utilization.The resulting scheduling respects all the predefined constraints and during task running generates a small waiting time, equal to 42733μs for task A when it is preempted and 14770 μs for task B in the ready queue. This waiting time represents only 16% of the overall running time. For the other tasks, the scheduler response is immediate, and the tasks are performed without preemption or migrations that substantially decrease the configuration overhead estimated in the following stage of resolution. The short response time of the scheduler is also reinforced by parallel computation.Thanks to parallel computation and the optimization parameters, especially the launching of tasks whenever the start times of their repetitions are valid, the makespan is optimal and equal to 353394μs. Compared to sequential execution of the DAG, the achieved speedup is 1.03.This speedup refers to the amount by which the pipelined scheduling speeds up the sequential execution of the DAG. Consequently, the parallel efficiency of this scheduling indicates how efficiently the RZs are exploited to perform DAG execution and is obtained by dividing the achieved speedup by the number of used RZs in the multi-reconfigurable-unit system. In our resolution, the parallel efficiency is about 0.5 which is considered acceptable as tasks are heterogeneous and are not allowed to be executed in all the RZs. The resolution of this first sub-problem is conducted on a CPU of 2 GHz with 2 GB of RAM and lasts 6280 seconds.


### 4.3. Partitioning/Fitting RZs Results and Placement Quality Evaluation

Based on powerful solvers, RZ1 and RZ2 are fitted on their most suitable RPBs defined by the following coordinates after 80.63 seconds on Virtex 5 FX70T (8×47RBs):(i)
RPB1 for RZ1: X1=14, Y1=6, WRPB1=32, HRPB1=6,(ii)
RPB2 for RZ2: X2=14, Y2=3, WRPB2=33, HRPB2=3.Table4 shows the comparison between the RBs of the obtained RPBs and their RZs expressed in the last column by cost Δ. The not null differences in RBs (Δ) are due to the rectangular shape of the RPBs and the heterogeneity of the device. Δ gives RB3 in excess. In fact, both RPBs include RB4, and in Virtex 5 FX70T there is no way to book RBs in a given RPB requiring DSP resources (RB4) with CLBL and CLBM resources (RB1 and RB2) without crossing BRAM (RB3) columns. Costs Δ also demonstrate how much the resulting placement of required RZs ensures resource efficiency. The low values found in Δ (1 RB3 and 2 RB3) show that the obtained RPBs are very close to their corresponding RZs, and consequently, resource efficiency is maintained during the conducted resolution.Table 4
Resource efficiency.
RB1RB2RB3RB4ΔRPB187211 RB3RPB297212 RB3Figure11 depicts the floorplanning of RPB1 and RPB2 on Virtex 5 FX70T as obtained by their coordinates. Figure 11 also represents the placing/routing of tasks A and D named, respectively, Reed-Solomon and FFT, which are running, respectively, on RZ1 and RZ2 during DAG execution in the time interval [57503,69309]. The obtained results show an average resource utilization of 12.46% of the available resources on the reconfigurable device. This average is computed according to the number and the cost of each RB type. Optimization in the utilization of resources minimizes the area of the FPGA which is reconfigured at runtime. Due to dynamic partial reconfiguration, resource efficiency is improved by 17.3% compared to the static design of the chosen DAG. The static design is created by floorplanning each task in the DAG on its unique corresponding RPB without sharing any RPBs between different tasks. Once the RPBs are allocated on the reconfigurable device, their bitstreams are created, and their real configuration overheads are computed. The incurred reconfiguration overhead obtained after mapping/scheduling is 6729 μs and represents only 2% of the total running time of the DAG.Figure 11
Floorplanning of RPBs and placing/routing of tasksA and D on Virtex 5 FX70T.Although the experimental conditions are not the same in terms of DAG size and used architecture, we compared our results to attainable improvements in previous works of multiprocessor scheduling. Speedup in our resolution is modest and is about 1.03, compared to [6] which achieves 5.01 for FIR implementation and [3], which reaches a speedup of up to 2. Similarly, regarding parallel efficiency on processors, the results of [6] show a parallel efficiency of 1.3, [3] improves this parameter to 1, and the highest parallelism system is obtained in the work described in [10] which produces 9.3 degrees of parallelism. Nevertheless, our methodology ensures a parallel efficiency of 0.5. The modest improvement in speedup and parallelism results obtained with our methodology can be explained by the heterogeneity of the tasks, the non suitability of all the provided RZs to execute the tasks, and the small number of provided RZs in order to increase resource efficiency in reconfigurable devices. The highest improvement in speedup and parallel efficiency reached in previous works of multiprocessor scheduling does not take into account the resource efficiency and the processor heterogeneity. Effectively, the processors are considered homogeneous as they have identical features, and tasks are allowed to be executed on whatever processor whenever is idle.However, compared to [18] where 80% of available resources are utilized, our methodology increases resource efficiency in heterogeneous devices by up to 17% compared to a static design and optimizes reconfigurable resource utilization by up to 12.46%. In contrast to [2] that targets an application of two or three tasks and attains a configuration overhead of 8% of total execution time, we immensely reduced the configuration overhead to 2% of the running time for a given DAG of five tasks. Similarly, in [24], Resano et al. attain 18% of configuration overhead to schedule only a JPEG decoder.Concerning computational complexity, compared to the proposed heuristics to perform multiprocessor scheduling, the worst case temporal complexity isO(n*(n+e)), where n is the number of nodes, and e is the number of edges in the graph. We are aware that the efficiency and the optimality of our proposed methodology may be impaired by its temporal complexity in finding the optimal solution and which grows exponentially with the number of tasks in the DAG. It is estimated by: O(2NT*NZ*NbrPreemp*HP*NbrIter)+O((Devicewidth2×Deviceheight2)NZ), where NbrPreemp and NbrIter are, respectively, the maximum number of preemption points and the maximum number of execution iterations for a given task.Thanks to the pertinent results obtained by the studied DAG, the efficiency of our proposed methodology in performing the placement and scheduling of small DAGs with few tasks is reinforced. However, due to the large size of search space containing the candidate solutions which will be checked for admission by constraints and evaluated for optimality by the objective function, our proposed approach is not capable to deal efficiently with intensive paralleled applications with hundreds of repetitive tasks. Effectively, using our approach in this class of application burdens the resolution time and the memory space, required for the computing of the several constraints and the different objective functions, and for searching the high number of assignments of possible values to the variables, parameters, and indexes. Currently, in our research project FOSFOR (Flexible Operating System FOr Reconfigurable platforms), the proposed methodology is efficiently employed as the target application is of type dataflow and contains small number of tasks.


## 4.1. Task Clustering Results

This stage executes Algorithm1 which results in RZ types (RZ1, RZ2, RZ3) represented by their RB models in the first column of Table 3. RZ1 is inserted by A and B, RZ2 is provided by C and D, and task E creates RZ3.Table 3
RZ types andD costs.
ABCDERZ1{8RB1, 7RB2, 1RB3, 1RB4}068292∞448RZ2{9RB1, 7RB2, 0RB3, 1RB4}∞∞1400356RZ3{2RB1, 2RB2, 0RB3, 0RB4}∞∞∞∞0When the maximal numbers of RBs within a constructed RZ are provided by several tasks, the configuration overhead of the RZ must be recomputed as described by (3). In our application, the maximum numbers of RBs within RZs are created by the same task. Thus, the RZ configuration overheads are provided by the predefined task features shown in Table 2. The second step of this stage computes the costs D between the DAG tasks and the resulting RZs. In Table 3, the bold numbers are the lowest costs D for tasks with the most suitable RZs.The resolution of scheduling of the chosen DAG on Virtex 5 FX70T is detailed in Sections4.2 and 4.3.


## 4.2. Mapping/Scheduling Results and Scheduling Quality Evaluation

DAG behavior is studied within the time interval (HP) of a period equal to the least common multiple of the periods of its tasks which is equal to 500 ms. Consequently, the execution iterations of tasks during the HP are deducted as follows:(39)NbrIterA=⌊HPPA⌋=⌊500500⌋=1,NbrIterB=1,NbrIterC=2,NbrIterD=2,NbrIterE=2.The three steps preceding mapping/scheduling resolution are detailed hereunder. In the remaining sections of the paper, the values are expressed inμs.


### 4.2.1. Checking of Precedence, Dependence, and Real-Time Rightness in the DAG

The constraints for checking precedence, dependence, and real-time rightness in the proposed DAG are detailed below.Dependence Checking
In Figure8, it is obvious that the periods of tasks between the levels are guarded or dubbed. Thus, the successors are more repetitive than the predecessors.
In this case, all the data produced on an edge linking a source task and its successor must be sufficient and consumed by the latter task. As can be seen in Figure8, the constraint expressed by (7) is satisfied for all the edges. For example, task B produces at its unique execution iteration a data of size xB,C equal to 7812.5 packets on its outgoing edge. These data are consumed totally by its first successor C during its two iterations where it consumes yC,B (3906.25 packets) data at each iteration. A similar remark can be made for data interchanged on the edge linking B and D.Precedence Checking
This constraint is satisfied by all the interdependent tasks in the DAG and is checked by means of (8) and (9). TreadyA=0, TreadyB=0, TreadyC=max(CA,CB)=42733, TreadyD=CB=42733, TreadyE=max(TreadyC+CC,TreadyD+CD)=max(42733+11805,42733+11806)=54539.
TaskC and Task B Precedence:
(40)K=1:42733+250000=292733>0.TaskC and Task A Precedence:
(41)K=1:42733+250000=292733>0.TaskD and Task B Precedence:
(42)K=1:42733+250000=292733>0.TaskC and Task E Precedence:
(43)K=1:54539+250000=304539>42733,K=2:54539+2*250000=554539>42733+250000=292733.TaskD and Task E Precedence:
(44)K=1:54539+250000=304539>42733,K=2:54539+2*250000=554539>42733+250000=292733.
The above tests prove that each execution iterationAi of a given task A includes only execution iteration Bi or iterations preceding Bi of each successor B. Consequently, the precedences between tasks in the chosen DAG are correct.Real-Time Checking
For the purpose of real-time functioning, (10) considers dependence constraints between tasks and makes it possible to verify, in the best case of spatial conditions and by providing an RZ for each task, the rightness of real-time functioning according to computation times and periods assigned to tasks in the DAG.
An example of testing real-time constraints for taskC is shown hereunder.TaskC
(45)ΠC={A,B},K=0:max⁡(0+26576,42733+0)+11805=54538≤min⁡(42733+250000,500000)=292733(A),max⁡(0+42733,42733+0)+11805=54538≤min⁡(42733+250000,500000)=292733(B)K=1:(42733+250000)+11805=304538≤min⁡(42733+2*250000,500000)=500000.
By providing an RZ for each task, the deadlines of the tasks are met taking into consideration the dependence and precedence constraints.The above three tests validate the chosen graph in terms of dependence, precedence, and real-time constraints and in the following section; spatial/temporal analyses are performed in order to determine the required number of RZs allowing valid scheduling for the DAG.


### 4.2.2. Determination of Lists of Ready Times

The first temporal analysis uses (11) to search the ready times of tasks which are helpful to limit execution intervals. Without considering the number of available reconfigurable units and taking into account precedence, dependence, periodicity, and real-time constraints, the ready times are determined as shown in Figure 9.Figure 9
Treadymin and Treadymax of tasks in the DAG.


### 4.2.3. Determination of Task Execution Intervals and the Number of RZs

The first step of this spatial/temporal analysis uses Algorithm2 to determine the possible execution intervals of tasks based on lists of ready times and respecting specified constraints. The possible execution intervals for tasks in the DAG are shown below(46)Execution-IntervalA1={[0,215915],[1,215915],…,[i,215915],…,[189339,215915]},Execution-IntervalB1={[0,215914],[1,215914],…,[i,215914],…[173181,215914]},Execution-IntervalC1={[42733,227720],[42734,227720],…,[215915,227720]},Execution-IntervalC2={[292733,477720],[292734,477720],…,[465915,477720]},Execution-IntervalD1={[42733,227720],[42734,227720],…,[215914,227720]},Execution-IntervalD2={[292733,477720],[292734,477720],…,[465914,477720]},Execution-IntervalE1={[54539,304539],[54540,304540],…,[i,i+PE],…,[227720,477720]},Execution-IntervalE2={[304539,HP],[304540,HP],…,[477720,HP]}.
Using Algorithm 3, the analysis therefore integrates the spatial aspect and studies possible conflicts between tasks in shared RZs to detect possible overloads. Algorithm 3 must respect the rules explained in Section 3.3.3(b) to search the possible overlapping execution intervals. At each iteration, for each RZ, Algorithm 3 searches all the combinations of tasks causing overlapping execution intervals and inserts them in Crossing-Combination and computes the loads of RZs according to two cases as detailed as follows.Iteration 1
RZ1.   Crossing-Combination={{Execution-IntervalA1, Execution-IntervalB1}}. This Crossing-Combination contains several combinations of overlapping execution intervals between A and B. In the worst case of overlapping, such as the overlapping between [0,215915] from Execution-IntervalA1 and [0,215914] from Execution-IntervalB1, the load of RZ1 obtained by Case 2 is 32% satisfying the predefined constraints. RZ2.  Crossing-Combination={{Execution-IntervalC1, Execution-IntervalD1}}. Similarly, this Crossing-Combination provides several combinations of overlapping execution intervals between C and D. In the worst case of overlapping, such as when both tasks have confused execution intervals equal to [42733,227720], the load of RZ2 obtained in Case 2 is 12%. Another possible solution consists in total migration, as expressed by Algorithm 4, of task C to the RZ RZ1 to improve execution parallelism and to minimize the makespan of the DAG. Thus, as soon as tasks A, B computations are achieved, tasks C and D may be launched, respectively, on RZ1 and RZ2.
During the first iteration, no combination of detected overlapping execution intervals causes an overload on RZs.Iteration 2
RZ2.   Crossing-Combination={{Execution-IntervalC2, Execution-IntervalD2},{Execution-IntervalC2,Execution-IntervalD2,Execution-IntervalE1},{Execution-IntervalE1,Execution-IntervalD2},{Execution-IntervalE1, Execution-IntervalC2}}{Execution-IntervalC2, Execution-IntervalD2}: As with the first iteration, all the combinations of overlapping execution intervals between tasks C and D do not cause an overload on RZ2. The load of RZ2, in the worst case of confused execution intervals, is equal to 12%. Hence, in the worst case, tasks C and D could be executed consequently on RZ2 respecting all the predefined constraints.
As expressed by the rules set out in Section3.3.3(b), detection of conflicting tasks must consider current and preceding iterations.
{Execution-IntervalC2, Execution-IntervalD2, Execution-IntervalE1}: This set provides many combinations of overlapping execution intervals between tasks C, D, and E. However, following Algorithm 3 and the optimization parameters for reducing the makespan as explained at the end of mapping/scheduling resolution, task E starts its first iteration immediately after the achievement of its predecessors C and D which is equal, in the worst case, to 227720 μs, and RZ2 is idle at this time. Consequently, according to this start time of the first repetition, task E finishes its execution at 250 ms which is not attainable by the least start time of the second iterations of C and D, equal to 292733 μs. Thus, this set leads to no overlapping of execution between C, D, and E and becomes equivalent to the Crossing-Combination set: {Execution-IntervalC2,Execution-IntervalD2}. Another possible solution for this set is total migration of C to RZ1 and E to RZ3. This solution guarantees efficient parallelism between task computations.
{Execution-IntervalE1, Execution-IntervalD2}, {Execution-IntervalE1, Execution-IntervalC2}: As explained for the previous set, these sets of overlapping execution intervals do not cause an overload on RZ2.RZ1
Crossing-Combination={{Execution-IntervalE1, Execution-IntervalC2}}. As described for RZ2 with the last three sets, tasks C and E do not cause overloads on RZ1 during this Crossing-Combination. In fact, application of Algorithm 3 and the optimization parameters results in no remaining execution of the first repetition of E when C starts its second execution iteration.
After these spatial and temporal analyses, one can conclude there is no need to perform migration or to add other RZs. The three RZs resulting from the clustering stage are sufficient to perform valid scheduling of the chosen DAG. Thus, RZ1, RZ2, and RZ3 represent the multi-reconfigurable-unit system for DAG scheduling. Based on powerful solvers dedicated by the AIMMS environment, we obtained the following mapping/scheduling which is evaluated in the next section.


### 4.2.4. Mapping and Scheduling Resolution

Figure10 describes the mapping/scheduling obtained for five tasks in the DAG on three RZs. As the number of RZs is the highest priority parameter in the objective function, the resolution concludes that for scheduling this DAG, only two RZs are required. RZ3 is not used, and hence it will not be placed on Virtex 5 FX70T in the third stage. The elimination of RZ3 enhances resource efficiency and enables the DAG to be extended and performed on the FPGA for future needs. RZ1 and RZ2 are selected by the solver to remain in the multi-reconfigurable-unit system since A and B can execute only on RZ1, task D can execute only on RZ2, and tasks C and E can run on both RZs.Figure 10
Mapping/scheduling resolution.The obtained mapping/scheduling takes into account all the optimization parameters described in the sub-problem formulation and satisfies the specified constraints. TasksA and B launch their computations first as they have no predecessors, and both can only execute on RZ1. To reduce the makespan of the DAG, the scheduler decides the preemption of A at its second preemption point (14770 μs) to enable the execution of task B, the termination of which permits the execution of task D on RZ2. The scheduler decides the execution of A before B in order to reduce the span between the executions of dependent tasks expressed by the dependence between C, D, and E. Hence, the scheduler promotes the solution that starts C immediately after completion of A and begins the execution of E once its predecessors C and D complete execution as reinforced by the optimization parameters explained at the end of mapping/scheduling resolution. These parameters aim at bringing closer the execution start of each task to the completion of its predecessors. C and E can execute on RZ1 and RZ2. The mapping assigns their executions to RZ2 as this RZ provides the best utilization of costly resources guided by their costs D. For the purpose of fully exploiting the multi-reconfigurable-unit system and to increase parallel efficiency, task A resumes its execution simultaneously with the start time of the first repetition of task D at 57503 μs. In their second execution iterations, respecting the periodicity and precedence constraints tasks C, D, and E are performed on their optimal RZ, that is, RZ2, to optimize resource utilization.The resulting scheduling respects all the predefined constraints and during task running generates a small waiting time, equal to 42733μs for task A when it is preempted and 14770 μs for task B in the ready queue. This waiting time represents only 16% of the overall running time. For the other tasks, the scheduler response is immediate, and the tasks are performed without preemption or migrations that substantially decrease the configuration overhead estimated in the following stage of resolution. The short response time of the scheduler is also reinforced by parallel computation.Thanks to parallel computation and the optimization parameters, especially the launching of tasks whenever the start times of their repetitions are valid, the makespan is optimal and equal to 353394μs. Compared to sequential execution of the DAG, the achieved speedup is 1.03.This speedup refers to the amount by which the pipelined scheduling speeds up the sequential execution of the DAG. Consequently, the parallel efficiency of this scheduling indicates how efficiently the RZs are exploited to perform DAG execution and is obtained by dividing the achieved speedup by the number of used RZs in the multi-reconfigurable-unit system. In our resolution, the parallel efficiency is about 0.5 which is considered acceptable as tasks are heterogeneous and are not allowed to be executed in all the RZs. The resolution of this first sub-problem is conducted on a CPU of 2 GHz with 2 GB of RAM and lasts 6280 seconds.


## 4.2.1. Checking of Precedence, Dependence, and Real-Time Rightness in the DAG

The constraints for checking precedence, dependence, and real-time rightness in the proposed DAG are detailed below.Dependence Checking
In Figure8, it is obvious that the periods of tasks between the levels are guarded or dubbed. Thus, the successors are more repetitive than the predecessors.
In this case, all the data produced on an edge linking a source task and its successor must be sufficient and consumed by the latter task. As can be seen in Figure8, the constraint expressed by (7) is satisfied for all the edges. For example, task B produces at its unique execution iteration a data of size xB,C equal to 7812.5 packets on its outgoing edge. These data are consumed totally by its first successor C during its two iterations where it consumes yC,B (3906.25 packets) data at each iteration. A similar remark can be made for data interchanged on the edge linking B and D.Precedence Checking
This constraint is satisfied by all the interdependent tasks in the DAG and is checked by means of (8) and (9). TreadyA=0, TreadyB=0, TreadyC=max(CA,CB)=42733, TreadyD=CB=42733, TreadyE=max(TreadyC+CC,TreadyD+CD)=max(42733+11805,42733+11806)=54539.
TaskC and Task B Precedence:
(40)K=1:42733+250000=292733>0.TaskC and Task A Precedence:
(41)K=1:42733+250000=292733>0.TaskD and Task B Precedence:
(42)K=1:42733+250000=292733>0.TaskC and Task E Precedence:
(43)K=1:54539+250000=304539>42733,K=2:54539+2*250000=554539>42733+250000=292733.TaskD and Task E Precedence:
(44)K=1:54539+250000=304539>42733,K=2:54539+2*250000=554539>42733+250000=292733.
The above tests prove that each execution iterationAi of a given task A includes only execution iteration Bi or iterations preceding Bi of each successor B. Consequently, the precedences between tasks in the chosen DAG are correct.Real-Time Checking
For the purpose of real-time functioning, (10) considers dependence constraints between tasks and makes it possible to verify, in the best case of spatial conditions and by providing an RZ for each task, the rightness of real-time functioning according to computation times and periods assigned to tasks in the DAG.
An example of testing real-time constraints for taskC is shown hereunder.TaskC
(45)ΠC={A,B},K=0:max⁡(0+26576,42733+0)+11805=54538≤min⁡(42733+250000,500000)=292733(A),max⁡(0+42733,42733+0)+11805=54538≤min⁡(42733+250000,500000)=292733(B)K=1:(42733+250000)+11805=304538≤min⁡(42733+2*250000,500000)=500000.
By providing an RZ for each task, the deadlines of the tasks are met taking into consideration the dependence and precedence constraints.The above three tests validate the chosen graph in terms of dependence, precedence, and real-time constraints and in the following section; spatial/temporal analyses are performed in order to determine the required number of RZs allowing valid scheduling for the DAG.


## 4.2.2. Determination of Lists of Ready Times

The first temporal analysis uses (11) to search the ready times of tasks which are helpful to limit execution intervals. Without considering the number of available reconfigurable units and taking into account precedence, dependence, periodicity, and real-time constraints, the ready times are determined as shown in Figure 9.Figure 9
Treadymin and Treadymax of tasks in the DAG.


## 4.2.3. Determination of Task Execution Intervals and the Number of RZs

The first step of this spatial/temporal analysis uses Algorithm2 to determine the possible execution intervals of tasks based on lists of ready times and respecting specified constraints. The possible execution intervals for tasks in the DAG are shown below(46)Execution-IntervalA1={[0,215915],[1,215915],…,[i,215915],…,[189339,215915]},Execution-IntervalB1={[0,215914],[1,215914],…,[i,215914],…[173181,215914]},Execution-IntervalC1={[42733,227720],[42734,227720],…,[215915,227720]},Execution-IntervalC2={[292733,477720],[292734,477720],…,[465915,477720]},Execution-IntervalD1={[42733,227720],[42734,227720],…,[215914,227720]},Execution-IntervalD2={[292733,477720],[292734,477720],…,[465914,477720]},Execution-IntervalE1={[54539,304539],[54540,304540],…,[i,i+PE],…,[227720,477720]},Execution-IntervalE2={[304539,HP],[304540,HP],…,[477720,HP]}.
Using Algorithm 3, the analysis therefore integrates the spatial aspect and studies possible conflicts between tasks in shared RZs to detect possible overloads. Algorithm 3 must respect the rules explained in Section 3.3.3(b) to search the possible overlapping execution intervals. At each iteration, for each RZ, Algorithm 3 searches all the combinations of tasks causing overlapping execution intervals and inserts them in Crossing-Combination and computes the loads of RZs according to two cases as detailed as follows.Iteration 1
RZ1.   Crossing-Combination={{Execution-IntervalA1, Execution-IntervalB1}}. This Crossing-Combination contains several combinations of overlapping execution intervals between A and B. In the worst case of overlapping, such as the overlapping between [0,215915] from Execution-IntervalA1 and [0,215914] from Execution-IntervalB1, the load of RZ1 obtained by Case 2 is 32% satisfying the predefined constraints. RZ2.  Crossing-Combination={{Execution-IntervalC1, Execution-IntervalD1}}. Similarly, this Crossing-Combination provides several combinations of overlapping execution intervals between C and D. In the worst case of overlapping, such as when both tasks have confused execution intervals equal to [42733,227720], the load of RZ2 obtained in Case 2 is 12%. Another possible solution consists in total migration, as expressed by Algorithm 4, of task C to the RZ RZ1 to improve execution parallelism and to minimize the makespan of the DAG. Thus, as soon as tasks A, B computations are achieved, tasks C and D may be launched, respectively, on RZ1 and RZ2.
During the first iteration, no combination of detected overlapping execution intervals causes an overload on RZs.Iteration 2
RZ2.   Crossing-Combination={{Execution-IntervalC2, Execution-IntervalD2},{Execution-IntervalC2,Execution-IntervalD2,Execution-IntervalE1},{Execution-IntervalE1,Execution-IntervalD2},{Execution-IntervalE1, Execution-IntervalC2}}{Execution-IntervalC2, Execution-IntervalD2}: As with the first iteration, all the combinations of overlapping execution intervals between tasks C and D do not cause an overload on RZ2. The load of RZ2, in the worst case of confused execution intervals, is equal to 12%. Hence, in the worst case, tasks C and D could be executed consequently on RZ2 respecting all the predefined constraints.
As expressed by the rules set out in Section3.3.3(b), detection of conflicting tasks must consider current and preceding iterations.
{Execution-IntervalC2, Execution-IntervalD2, Execution-IntervalE1}: This set provides many combinations of overlapping execution intervals between tasks C, D, and E. However, following Algorithm 3 and the optimization parameters for reducing the makespan as explained at the end of mapping/scheduling resolution, task E starts its first iteration immediately after the achievement of its predecessors C and D which is equal, in the worst case, to 227720 μs, and RZ2 is idle at this time. Consequently, according to this start time of the first repetition, task E finishes its execution at 250 ms which is not attainable by the least start time of the second iterations of C and D, equal to 292733 μs. Thus, this set leads to no overlapping of execution between C, D, and E and becomes equivalent to the Crossing-Combination set: {Execution-IntervalC2,Execution-IntervalD2}. Another possible solution for this set is total migration of C to RZ1 and E to RZ3. This solution guarantees efficient parallelism between task computations.
{Execution-IntervalE1, Execution-IntervalD2}, {Execution-IntervalE1, Execution-IntervalC2}: As explained for the previous set, these sets of overlapping execution intervals do not cause an overload on RZ2.RZ1
Crossing-Combination={{Execution-IntervalE1, Execution-IntervalC2}}. As described for RZ2 with the last three sets, tasks C and E do not cause overloads on RZ1 during this Crossing-Combination. In fact, application of Algorithm 3 and the optimization parameters results in no remaining execution of the first repetition of E when C starts its second execution iteration.
After these spatial and temporal analyses, one can conclude there is no need to perform migration or to add other RZs. The three RZs resulting from the clustering stage are sufficient to perform valid scheduling of the chosen DAG. Thus, RZ1, RZ2, and RZ3 represent the multi-reconfigurable-unit system for DAG scheduling. Based on powerful solvers dedicated by the AIMMS environment, we obtained the following mapping/scheduling which is evaluated in the next section.


## 4.2.4. Mapping and Scheduling Resolution

Figure10 describes the mapping/scheduling obtained for five tasks in the DAG on three RZs. As the number of RZs is the highest priority parameter in the objective function, the resolution concludes that for scheduling this DAG, only two RZs are required. RZ3 is not used, and hence it will not be placed on Virtex 5 FX70T in the third stage. The elimination of RZ3 enhances resource efficiency and enables the DAG to be extended and performed on the FPGA for future needs. RZ1 and RZ2 are selected by the solver to remain in the multi-reconfigurable-unit system since A and B can execute only on RZ1, task D can execute only on RZ2, and tasks C and E can run on both RZs.Figure 10
Mapping/scheduling resolution.The obtained mapping/scheduling takes into account all the optimization parameters described in the sub-problem formulation and satisfies the specified constraints. TasksA and B launch their computations first as they have no predecessors, and both can only execute on RZ1. To reduce the makespan of the DAG, the scheduler decides the preemption of A at its second preemption point (14770 μs) to enable the execution of task B, the termination of which permits the execution of task D on RZ2. The scheduler decides the execution of A before B in order to reduce the span between the executions of dependent tasks expressed by the dependence between C, D, and E. Hence, the scheduler promotes the solution that starts C immediately after completion of A and begins the execution of E once its predecessors C and D complete execution as reinforced by the optimization parameters explained at the end of mapping/scheduling resolution. These parameters aim at bringing closer the execution start of each task to the completion of its predecessors. C and E can execute on RZ1 and RZ2. The mapping assigns their executions to RZ2 as this RZ provides the best utilization of costly resources guided by their costs D. For the purpose of fully exploiting the multi-reconfigurable-unit system and to increase parallel efficiency, task A resumes its execution simultaneously with the start time of the first repetition of task D at 57503 μs. In their second execution iterations, respecting the periodicity and precedence constraints tasks C, D, and E are performed on their optimal RZ, that is, RZ2, to optimize resource utilization.The resulting scheduling respects all the predefined constraints and during task running generates a small waiting time, equal to 42733μs for task A when it is preempted and 14770 μs for task B in the ready queue. This waiting time represents only 16% of the overall running time. For the other tasks, the scheduler response is immediate, and the tasks are performed without preemption or migrations that substantially decrease the configuration overhead estimated in the following stage of resolution. The short response time of the scheduler is also reinforced by parallel computation.Thanks to parallel computation and the optimization parameters, especially the launching of tasks whenever the start times of their repetitions are valid, the makespan is optimal and equal to 353394μs. Compared to sequential execution of the DAG, the achieved speedup is 1.03.This speedup refers to the amount by which the pipelined scheduling speeds up the sequential execution of the DAG. Consequently, the parallel efficiency of this scheduling indicates how efficiently the RZs are exploited to perform DAG execution and is obtained by dividing the achieved speedup by the number of used RZs in the multi-reconfigurable-unit system. In our resolution, the parallel efficiency is about 0.5 which is considered acceptable as tasks are heterogeneous and are not allowed to be executed in all the RZs. The resolution of this first sub-problem is conducted on a CPU of 2 GHz with 2 GB of RAM and lasts 6280 seconds.


## 4.3. Partitioning/Fitting RZs Results and Placement Quality Evaluation

Based on powerful solvers, RZ1 and RZ2 are fitted on their most suitable RPBs defined by the following coordinates after 80.63 seconds on Virtex 5 FX70T (8×47RBs):(i)
RPB1 for RZ1: X1=14, Y1=6, WRPB1=32, HRPB1=6,(ii)
RPB2 for RZ2: X2=14, Y2=3, WRPB2=33, HRPB2=3.Table4 shows the comparison between the RBs of the obtained RPBs and their RZs expressed in the last column by cost Δ. The not null differences in RBs (Δ) are due to the rectangular shape of the RPBs and the heterogeneity of the device. Δ gives RB3 in excess. In fact, both RPBs include RB4, and in Virtex 5 FX70T there is no way to book RBs in a given RPB requiring DSP resources (RB4) with CLBL and CLBM resources (RB1 and RB2) without crossing BRAM (RB3) columns. Costs Δ also demonstrate how much the resulting placement of required RZs ensures resource efficiency. The low values found in Δ (1 RB3 and 2 RB3) show that the obtained RPBs are very close to their corresponding RZs, and consequently, resource efficiency is maintained during the conducted resolution.Table 4
Resource efficiency.
RB1RB2RB3RB4ΔRPB187211 RB3RPB297212 RB3Figure11 depicts the floorplanning of RPB1 and RPB2 on Virtex 5 FX70T as obtained by their coordinates. Figure 11 also represents the placing/routing of tasks A and D named, respectively, Reed-Solomon and FFT, which are running, respectively, on RZ1 and RZ2 during DAG execution in the time interval [57503,69309]. The obtained results show an average resource utilization of 12.46% of the available resources on the reconfigurable device. This average is computed according to the number and the cost of each RB type. Optimization in the utilization of resources minimizes the area of the FPGA which is reconfigured at runtime. Due to dynamic partial reconfiguration, resource efficiency is improved by 17.3% compared to the static design of the chosen DAG. The static design is created by floorplanning each task in the DAG on its unique corresponding RPB without sharing any RPBs between different tasks. Once the RPBs are allocated on the reconfigurable device, their bitstreams are created, and their real configuration overheads are computed. The incurred reconfiguration overhead obtained after mapping/scheduling is 6729 μs and represents only 2% of the total running time of the DAG.Figure 11
Floorplanning of RPBs and placing/routing of tasksA and D on Virtex 5 FX70T.Although the experimental conditions are not the same in terms of DAG size and used architecture, we compared our results to attainable improvements in previous works of multiprocessor scheduling. Speedup in our resolution is modest and is about 1.03, compared to [6] which achieves 5.01 for FIR implementation and [3], which reaches a speedup of up to 2. Similarly, regarding parallel efficiency on processors, the results of [6] show a parallel efficiency of 1.3, [3] improves this parameter to 1, and the highest parallelism system is obtained in the work described in [10] which produces 9.3 degrees of parallelism. Nevertheless, our methodology ensures a parallel efficiency of 0.5. The modest improvement in speedup and parallelism results obtained with our methodology can be explained by the heterogeneity of the tasks, the non suitability of all the provided RZs to execute the tasks, and the small number of provided RZs in order to increase resource efficiency in reconfigurable devices. The highest improvement in speedup and parallel efficiency reached in previous works of multiprocessor scheduling does not take into account the resource efficiency and the processor heterogeneity. Effectively, the processors are considered homogeneous as they have identical features, and tasks are allowed to be executed on whatever processor whenever is idle.However, compared to [18] where 80% of available resources are utilized, our methodology increases resource efficiency in heterogeneous devices by up to 17% compared to a static design and optimizes reconfigurable resource utilization by up to 12.46%. In contrast to [2] that targets an application of two or three tasks and attains a configuration overhead of 8% of total execution time, we immensely reduced the configuration overhead to 2% of the running time for a given DAG of five tasks. Similarly, in [24], Resano et al. attain 18% of configuration overhead to schedule only a JPEG decoder.Concerning computational complexity, compared to the proposed heuristics to perform multiprocessor scheduling, the worst case temporal complexity isO(n*(n+e)), where n is the number of nodes, and e is the number of edges in the graph. We are aware that the efficiency and the optimality of our proposed methodology may be impaired by its temporal complexity in finding the optimal solution and which grows exponentially with the number of tasks in the DAG. It is estimated by: O(2NT*NZ*NbrPreemp*HP*NbrIter)+O((Devicewidth2×Deviceheight2)NZ), where NbrPreemp and NbrIter are, respectively, the maximum number of preemption points and the maximum number of execution iterations for a given task.Thanks to the pertinent results obtained by the studied DAG, the efficiency of our proposed methodology in performing the placement and scheduling of small DAGs with few tasks is reinforced. However, due to the large size of search space containing the candidate solutions which will be checked for admission by constraints and evaluated for optimality by the objective function, our proposed approach is not capable to deal efficiently with intensive paralleled applications with hundreds of repetitive tasks. Effectively, using our approach in this class of application burdens the resolution time and the memory space, required for the computing of the several constraints and the different objective functions, and for searching the high number of assignments of possible values to the variables, parameters, and indexes. Currently, in our research project FOSFOR (Flexible Operating System FOr Reconfigurable platforms), the proposed methodology is efficiently employed as the target application is of type dataflow and contains small number of tasks.


## 5. Conclusion and Future Work

Under strict real-time constraints and from a parallel processing perspective, our paper deals with the problem of static scheduling of DAGs on multi-reconfigurable-unit system. In our opinion, most of the works proposed in this field do not consider resource efficiency or configuration overhead, and they are not applied to new heterogeneous technology. The approaches focus only on improving computation speedup and parallel efficiency for DAGs on homogeneous execution units. By means of a new methodology comprising three main stages and by selecting a preemptive model, we take into account periodicity, precedence, dependence, and real-time constraints, and we employ rigorous efficient analytic resolution in order to enhance quality of placement and scheduling in the most recent heterogeneous reconfigurable devices. Our methodology is illustrated in a realistic application, and the results obtained are encouraging. The resolution tries to find the trade-off between all the cited criteria since the performance of the DAG on reconfigurable devices is mainly defined by the degree of parallelism, the resource efficiency, and the amount of incurred reconfiguration. Our proposed approach is largely dependent on the physical features of tasks and technology as well as on temporal characteristics. During our tests, we concluded that our proposed methodology is efficient for small DAGs rather than for larger ones. In fact, solver processing is immensely delayed when the number of tasks in DAG exceeds five.Static multiprocessor scheduling is a well-understood problem, and many efficient heuristics have been proposed to create compile-time scheduler scenarios. However, the approaches face difficulties in dealing with nondeterministic systems with run-time characteristics that are not well known before the DAG running. Thus, our future challenge is to define dynamic scheduling in heterogeneous reconfigurable devices to be applied for several DAGs of different sizes with nondeterministic behavior. We aim to consider intertask communication, all the specified constraints detailed throughout this paper, as well as to optimize all the cited criteria, especially degree of parallelism, resource efficiency, and configuration overheads.



---

*Source: 591983-2011-05-12.xml*