Energy-efficient scheduling on multi-FPGA reconfigurable systems

Abstract

With the growing demand in high performance computing, reconfigurable computing systems built with Field Programmable Gate Array (FPGA) have become increasingly popular for its reconfigurability and adaptability to applications. Although such systems promise high processing performance, their energy efficiency has become a critical issue. This paper studies the crucial problem of energy-efficient scheduling for reconfigurable systems with multiple FPGAs. Several factors make the energy efficient scheduling particularly challenging, including spatial allocation constraint, reconfiguration overhead, limited reconfiguration ports, and deadline satisfaction. These unique characteristics make energy efficient scheduling in multi-FPGA reconfigurable systems particularly challenging and none of existing solutions can be directly applied. This paper takes on this challenge and proposes an energy-efficient scheduling algorithm called AEE based on ant colony optimization for multi-FPGA reconfigurable systems. A task placement scheme is devised which serves as the heuristic function that derives the minimum global makespan, which is important to the ant colony algorithm based proposed in the paper. The scheme takes into account reconfiguration overhead and places tasks for reducing the overall overhead. Then, based on AEE, an enhanced algorithm (eAEE) is devised to deal with the tasks with precedence and interdependencies. To evaluate the effectiveness of the two proposed algorithms, comprehensive trace-driven simulations have been conducted and compared with other state-of-art algorithms. Experimental results demonstrate that AEE can successfully complete tasks without violating deadline constraints and the energy dissipation is largely reduced, no more than 10.65% higher than the optimum when the problem scale is relatively small. Also, eAEE consumes energy 58.17% less than an improved simulated annealing algorithm (iSA) with a large problem scale.

Introduction

Recent years have witnessed the rapid development of Field Programmable Gate Array (FPGA) technology, which has been widely used in various application domains. Compared with Application Specific Integrated Circuit (ASIC), FPGA outperforms in terms of performance, cost, flexibility and reconfigurability. Today, some off-the-shelf commercial FPGA systems support partial runtime reconfiguration (PRTR). This allows part of logic blocks to be reconfigured on the runtime, without affecting the rest of logic blocks. FPGAs have been used to construct high performance systems that are dynamically reconfigurable. Compared with systems built with multiple general processors, such systems are advantageous. The processing speed is higher since a task is processed with a hardware implementation. Example of such systems include BEE2 [6] and TM-4 [11]. This paper considers multi-FPGA reconfigurable systems (as shown in Fig. 1), which have been adopted in a number of application domains [2], [6], [11].

Although multi-FPGA systems are capable of providing high performance computing, their energy dissipation is a serious issue. It is highly important to achieve energy efficiency. Firstly, less heat would be generated and the effort for releasing heat could be greatly saved. Secondly, the less energy dissipates in the system, the smaller the energy bill should be paid. Lastly, less heat results in a higher reliability of the whole system [1]. The increasing temperature leaves FPGA fabrics more vulnerable.

Fortunately, many contemporary reconfigurable platforms incorporate tuning mechanisms for energy efficient operations. For instance, Xilinx Vertiex-5 is designed based on CMOS circuitry [3] that allows adjustable power consumption rates.

It has become evident, however, that there is an intrinsic tradeoff between processing performance and energy consumption for multi-FPGA systems. To achieve lower power consumption rate, the system can decrease the operating frequency, which leads to longer processing time. In practice, it is highly desirable to complete tasks within given deadlines while minimizing the overall power consumption of the whole system. This paper studies the crucial problem of energy-efficient scheduling on multi-FPGA systems without missing deadline constraint.

To achieve energy efficiency, several great challenges have to be addressed. First, a task may use a number of logic blocks and it is required that these blocks be located together. We define this as integral allocation of contiguous logic blocks on a FPGA to a computing task. Second, the scheduling system needs to take into account reconfiguration overhead. It takes a non-eligible amount of time to reconfigure the logic blocks in order to execute a new type of task. Moreover, a FPGA has a limited number of loading ports. This suggests that a reconfigurable system faces the constraint that at one time a limited number of tasks can accepted simultaneously for which the logic blocks are being reconfigured for the new type of tasks. This kind of constraint can be considered simultaneous reconfiguration constraint. It should be noted that in a multi-FPGA system, multiple independent tasks are likely to be reconfigured simultaneously. Finally, the scheduling algorithm needs to minimize the overall energy consumption while meeting the deadline constraints of application tasks.

There have been a few studies on energy conversation in reconfigurable systems. Many of them are dedicated to designing hardware in the circuit level [7], [21] and the system level [20], [23]. In [21], the authors develop a dual V_DD/V_t voltage on an LUT-Based FPGA to tune the overall energy consumption. DVS (Dynamic Voltage Scaling) [7] is applied to adjust the voltage level in FPGAs embedded with a logic delay measurement circuit. The later methods apply scheduling techniques for reduction of energy consumption in dynamically reconfigurable systems. In [20], a post-placement leakage aware scheduler is invoked to reduce waste of leakage power, which can be measured from the delay between task reconfiguration and execution. One optimal algorithm is proposed for the case in which a task partition over contexts is given, and approximation algorithms are developed for the case in which no task partition is given [23]. In [4], [22], the methods either neglect the reconfiguration overhead or focus on single-FPGA systems. When there are multiple FPGA units, we should carefully allocate tasks to the FPGA units, maximizing simultaneous reconfiguration and minimizing reconfiguration overhead. Most existing work on multi-FPGA systems [2], [11], [24] has largely concentrated on computing performance only. In summary, few existing methods can be applied to energy-efficient scheduling on multi-FPGA systems.

Energy-efficient scheduling on multi-processor or multi-core systems [5], [14], [17], [19], [25], [27] has been extensively studied. But, energy efficient scheduling on multi-FPGA systems is different and more difficult. First, in a reconfigurable system, allocating tasks to FPGAs must conform to the spatial allocation constraint. A subset of contiguous logic blocks has to be allocated to one task. There is no such constraint for systems of general purpose processors. Second, a task to be executed on a reconfigurable system must first be mapped to a given set of logic blocks before it is run. Finally, scheduling on dynamically reconfigurable systems should explicitly take reconfiguration overhead into account [13]. Thus, existing scheduling algorithms for multi-processor systems can hardly be directly applied in multi-FPGA systems.

In this paper, we show that the optimal scheduling problem for energy minimization with deadline constraints is NP Complete (independent tasks). We propose an energy efficient scheduling algorithm called AEE based on Ant Colony Optimization (ACO). Also, we propose an enhanced AEE algorithm (eAEE) to deal with the tasks with precedence and interdependencies. These algorithms can achieve high energy efficiency and in the meanwhile meet the deadline requirement of computing tasks. The distinctive features of the algorithms are low complexity. Comprehensive trace-driven simulation experiments have been conducted to evaluate the algorithms and results show that the algorithms can process all tasks without violating deadline constraint and can considerably reduce energy consumption in the meantime.

The main technical contributions of the paper are listed as follows:

• We investigate the unique characteristics of multi-FPGA reconfigurable systems, and then accordingly formulate the energy-efficient scheduling problem as an optimization problem with deadline constraints.

• We analyze the complexity of the optimal scheduling problem and rigidly prove that it is a NP-Complete problem.

• We propose AEE and eAEE, two energy efficient scheduling algorithms based on Ant-Colony Optimization, are for tasks independent and dependent, respectively. In spite of low complexity, these algorithms dramatically reduce the overall energy consumption while meeting the deadline constraint.

• Comprehensive trace-driven simulations have been conducted and results show that the AEE algorithm dissipates power no more than 10.65% higher than the optimal solution, and eAEE consumes 58.17% less energy than that of iSA.

The remainder of paper is organized as follows. We introduce related work in Section 2. In Section 3, we present the system model and formally define the scheduling problem. In Section 4, we give the details of the proposed two scheduling algorithms. The performance evaluation methodology and evaluation results are presented in Section 5. We conclude the paper in Section 6.