In our system, tasks can be dynamically activated and terminated based on environmental changes and mission objectives. As such, the load on the system varies. When the system is not under heavy load, all tasks with a HW configuration will be run in hardware as it offers improved performance. If the load on the system increases and the reconfigurable area is filled, some tasks will have to be moved to SW. We assume that each application in the system can specify a set of possibly several different execution modes, which tradeoff resource requirements vs provided QoS. The goal of the task management system is then to select a mode for each running application is such a way as to maximize the overall system QoS. Several tasks might have to be moved from HW to SW or viceversa each time an application changes mode. To preserve real-time requirements, it is essential that no task is stopped while migration takes place.

Note that reconfiguring a HW tasks takes a non negligible amount of time. As such, we do not allow HW tasks to be preepted; they execute for the entirety of their periods. SW tasks are executed on the CPU according to Earliest Deadline First (EDF) scheduling. To migrate a task from SW the HW, we use the following strategy: while the SW task is executing, we reconfigure the FPGA to accomodate the HW task. At the end of the next period, we then migrate the task.

A new application mode configuration is achieved by "swapping" groups of tasks executing in SW with tasks executing in HW. In the figure below, assuming the management goal is simply to maximize utilization of FPGA area, tasks 4 and 7 must be swapped (task width represents area used on the FPGA, task height represents utilization on the CPU). This is achieved by first moving task 4 to the CPU and then moving task 7 to the now free FPGA area. Note that during the transition, both tasks 4 and 7 are scheduled on the CPU, resulting in a transitory overhead. If the overhead is too large, then the CPU schedulability bound can be violated and the reconfiguration is unfeasible since it can lead to deadline violations.

We have developed a comprehensive relocation algorithm that efficiently computes bounds on the reconfiguration overhead by building a series of swapping groups of equal area. We further proved the following [Pel07a]:

• the overhead is equal to the minimum CPU utilization of any swapping group;
  
• it is possible to construct a swapping group with minimum utilization in quadratic time in the number of tasks;
  
• it is possible to defragment the device without introducing additional overhead.