Hardware task scheduling algorithm related to power consumption of reconfigurable system

introduction

A reconfigurable system refers to a computing platform that uses software to change the hardware structure to achieve specific applications. It is generally composed of a non-flexible but programmable processor and a flexible digital logic device that can be reconfigured by program control. At present, the reconfigurable hardware used in the research of reconfigurable systems at home and abroad is mainly the Field Programming Gate Array (FPGA). Reconfigurable systems are very suitable for applications that have strict requirements on power consumption or are computationally intensive, because the power consumption of such applications implemented on FPGAs is much lower than that implemented on processors. Treating tasks running on FPGAs as "hardware tasks" and incorporating them into the unified management scope of the real-time operating system (RTOS) can simplify the design and management of the system. Therefore, it is necessary to introduce a hardware task manager in the traditional RTOS to achieve the management and scheduling of hardware tasks.

At present, this research has made some progress. For example, the commercial reconfigurable system OS4RS proposed in reference [1] includes the main functions of task creation/destruction, dynamic migration of heterogeneous tasks, and communication between tasks. Supporting software/hardware task debugging and allowing tracking and monitoring of operating system modules and user tasks are important features of reconfigurable hardware operating systems. In reference [2], a real-time operating system SHUM-μCOS based on a unified software/hardware multi-task model was designed, which implements unified task management, independent scheduling of software/hardware tasks based on static priorities, management of hardware resources, and communication between software/hardware tasks based on the software layer.

However, the software/hardware scheduling algorithms considered by most researchers are generally difficult to implement on existing FPGA hardware platforms, such as the 2D FPGA resource model used by the FORS algorithm in reference [2]. This is because current FPGA technology only allows all tasks to occupy the same "height", and the above work rarely takes power consumption into consideration. Therefore, similar to the dynamic voltage scaling (DVS) technology widely used in embedded microprocessors to reduce system power consumption, this paper proposes an algorithm for dynamically adjusting the FPGA operating frequency to achieve a balance between the performance requirements and power requirements of reconfigurable systems, and it can be implemented under current FPGA technology conditions.

1 Scheduling Model

1.1 Reconfigurable System Architecture

This paper only considers the reconfigurable system structure under the current FPGA technology conditions, as shown in Figure 1. FPGA is divided into two parts: dynamic and static. The dynamic part includes many reconfigurable modules (RM). Each hardware task runs on one RM. The FPGA width occupied by each RM may not be equal. It is generally composed of several CLBs (Configurable Logic Blocks, reconfigurable units) in the same column. The static part is responsible for data interaction between the CPU and RM.

Assume that the FPGA is composed of many CLBs arranged in an array. Each CLB can be regarded as a 1×1 unit square, and an FPGA is a rectangle with an area of ​​ω×h. Where ω is the width of the rectangle, h is the height of the rectangle, and ω×h is the total number of CLBs contained in the FPGA (i.e., the area). Figure 2 shows a 5×4 FPGA. In the implementation, because each RM uses the same FPGA height, i.e., h, the area of ​​the smallest RM is ωmm×h, where the size of ωmin depends on the number of CLBs required for the hardware task. Therefore, the maximum number of RMs on an FPGA can be:

When configuring an FPGA, its dynamic part can be divided into RMs with different widths, so that multiple hardware tasks with different CLB requirements can run on the FPGA at the same time. In addition, when configuring one of the RMs, it has no effect on other running parts, so reconfigurable hardware allows hardware tasks to run in a true dynamic multitasking manner.

1.2 Task Definition

① Hardware task: A hardware task refers to a functional module implemented based on FPGA in a reconfigurable system. Once a hardware task is configured, it can start executing. Before completion, the reconfigurable resources it occupies are generally not released, that is, it cannot be preempted by other hardware tasks.

② A hardware task can be expressed as Ti(fi, max, ai, ci, ti, ei, fworking). Among them, fi, max is the maximum clock frequency at which the hardware task can run on the RM. This frequency is determined by the timing conditions of each specific hardware task design, so fi, max for each task may be different. ωi is the width resource of the reconfigurable hardware occupied by the task, ai represents the arrival time of the hardware task, ci represents the final completion time of the hardware task, and ti is the running time when the hardware task works at fi, max. In this paper, the configuration time of the hardware task on the FPGA is not considered separately, but it is incorporated into the running time. e is the power consumption of the hardware task when it works at fi, max, which can be estimated by the power consumption model established in reference [4]. fworking is the actual frequency of the FPGA when the task is running.

In reference [4], the power consumption of a hardware task is directly related to the operating frequency of the hardware. Therefore, the actual running time and power consumption of a hardware task can be estimated using the following two formulas:

Where f is the actual running frequency of the hardware task. [page]

2 Power consumption related hardware task scheduling algorithm EEHTS

2.1 Hardware Task Scheduler Design

The target system is shown in Figure 3. The user program is divided into two parts, where the software task runs on the CPU and the hardware task runs on the FPGA. This paper only considers the scheduling of power-related hardware tasks. The goal is to unify the software/hardware tasks and reduce the overall power consumption of the system while meeting the task deadline requirements, that is:

2.2 Scheduling and placement principles

In embedded systems, the correctness of tasks depends not only on their functional correctness but also on the timeliness of their execution. Therefore, ensuring that tasks do not miss their deadlines is the most important scheduling basis. Under the premise of meeting the task deadline, the latest starting time (Last: Starting time, LST) of a newly arrived hardware task Ti is LST(Ti)=ci-ti. If Ti does not find a suitable location when it is placed, the scheduler does not immediately reject Ti, because as long as resources that meet Ti's requirements are released before LST(Ti), Ti can still meet its deadline requirements. In the EEHTS algorithm, it is necessary to maintain the arrival task list Alist, which stores all tasks that have arrived and failed to be successfully assigned. The tasks in the arrival list are arranged in ascending order according to the LST of the task, that is, they are scheduled according to the principle of Earliest Last Starting time First (ELST). The core of the hardware task scheduler is to perform positioning allocation, that is, to find a suitable location on the FPGA to configure the FPGA according to the size of the FPGA resources occupied by the hardware task, such as the MER algorithm proposed in reference [5]. However, the FPGA area models used by such algorithms are all 2D resource models, which cannot be implemented under the current FPGA technology conditions. Therefore, this paper adopts a method similar to the traditional operating system to manage memory resources, namely the FirstFit algorithm. In the EEHTS algorithm, it is necessary to maintain a blank resource list B, which stores all the currently unused blank areas on the FPGA. Once a hardware task is successfully placed, the configuration and operation can begin. Therefore, it is necessary to maintain a running task list Elist in the EEHTS algorithm. The execution list Elist contains all the running hardware tasks Ti, and the tasks are arranged in increasing order of the execution completion time.

Before a hardware task is completed, it cannot be preempted by other tasks; when a hardware task is completed, the occupied FPGA resources can be released, and the completed task is inserted into the completed task list Flist. This feature is a significant difference between hardware tasks and software tasks.

2.3 Power consumption related hardware task scheduling algorithm EEHTS

(1) Algorithm 1: EEHTS algorithm

At any time t, the EEHTS algorithm first checks the first task Ti in the Alist queue. The function has three possible return results: ACCEPT, REJECT, and NULL. In line 2, if there is a suitable position to place task Ti in the FPGA blank area list B, then Ti is added to Elist, and then line 6 recalculates a more optimized FPGA frequency fe. If fe is less than the current FPGA running frequency fworking, and all tasks in Elist can be completed within their deadlines under fe, it means that the overall power consumption of the hardware task can be reduced by reducing the frequency while ensuring the task deadline, so the algorithm returns ACCEPT at this time; in line 13, if the task is about to or has missed the latest start time, then the function returns REJECT at this time, indicating that the task is rejected; in line 15, if there is no suitable position at the current moment, but the task has not yet reached its latest start time, it means that the resources required for the task may still be obtained in the future, so the function returns the result NULL.

The algorithm for recalculating the FPGA operating frequency in line 6 of Algorithm 1 is shown in Algorithm 2, where F is the set of operating frequency values ​​of all hardware tasks. It should be noted that the operating frequency values ​​of hardware tasks running on the FPGA at the same time must be the same, and choosing 5 as the increment of FPGA frequency is also in line with the actual FPGA technology situation. [page]

(2) Algorithm 2: Select the optimal frequency value as the operating frequency of the FPGA

Step 1: fscheduled,max=min(fi,min|Ti∈Elist)

Step 2: For each value of f in the set F that satisfies fmin≤f≤fscheduled, max, calculate:

The value that minimizes the result in calculation step 2 is selected as the operating frequency value of the FPGA, thereby minimizing the overall power consumption of the FPGA.

3Simulation Experiment and analysis

Since there is no unified benchmark for evaluating scheduling algorithms related to power consumption in reconfigurable systems, a discrete clock simulator was designed using a simulation model similar to that in reference [2] to simulate the clock ticks in real-time systems to check task deadlines. A random task generator was then designed to generate task sets containing 1,000, 2,000, 3,009, 4,000, 5,000, and 6,000 Ti(fi,max,ωi,ai,ci,ti,ei,fworking) respectively. The width and execution time of the hardware tasks were also randomly generated.

Assume that the target device is Xilinx Virtex XCV1000, with a total of 96 columns × 64 rows, of which 80 columns are used to configure the dynamic part of the hardware task, and the rest are used for communication and I/O of the operating system. The parameters used in the simulation experiment are as follows: the minimum width of the task ωmin=1, Nmax=80, and the width range of the task ωi is 1~80; fmin=20 MHz, fmax=100MHz, so the maximum frequency fi,max∈[20, 25, …, 1 000] that each task can run; the running time ti of the task at the frequency fi,max ranges from 100 to 1 000 ms. ei ranges from 20 to 200 mJ, and the size of ei is related to the task width. The arrival time ranges from 01.5 to 500 ms, and the clock tick of the simulator is set to 500 μs. The overall running time and overall power consumption of the task set using the ELST algorithm and the EEHTS algorithm are simulated respectively, as shown in Figures 4 and 5. As can be seen from Figure 4, the task running time curve using the ELST algorithm is lower than that using the EEHTS algorithm. This is because the FPGA's operating frequency is not changed when only the ELST algorithm is used. The FPGA always runs at the highest frequency. Obviously, the power consumption of this method will be greater than that of the EEHTS algorithm, and the experimental results also prove this. As shown in Figure 5, although the EEHTs algorithm sacrifices some time performance, the hardware task can still be completed within its deadline, and the power consumption of the hardware task is reduced by about 32% compared to the ELST algorithm.

Conclusion

In embedded systems, low power consumption is a very important goal. This paper studies the hardware task scheduling algorithm in reconfigurable systems, takes power consumption into consideration when scheduling hardware tasks, and dynamically changes the frequency of hardware task operation, thereby reducing the overall power consumption of the system.