Task modules Partitioning, Scheduling and Floorplanning for Partially Dynamically Reconfigurable Systems Based on Modern Heterogeneous FPGAs

The design automation of partially dynamically reconfigurable systems involves the problems of task modules partitioning, scheduling, and floorplanning on heterogeneous resources. The analysis of these problems is described in Section 2.3. Many previous works have been committed to designing algorithms to implement the automation of partially dynamically reconfigurable systems. However, these works are more or less impaired. And Table 1 lists part representative works.

Some works have focused on partition and floorplan of PDRS to decrease wire length and improve resources utilization. Bolchini et al. (bolchini2011automated, ) proposed a floorplanner to place reconfigure regions(RRs). This work is based on the SA algorithm, and the objective is to improve the utilization of heterogeneous resources of the PDRS with optimizing wire length. However, this work only considers the floorplan of reconfigurable regions and only solves part problems of the design automation of PDRS. P. Banerjee et al.(banerjee2010floorplanning, ) proposed a three-stages heuristic method to partition and floorplan task modules on heterogeneous resources of PDRS. This work limits that each reconfigurable region deploys one task module in each partition. However, on a modern FPGA chip with PDR technology, each reconfigurable region can deploy multiple task modules, thus reducing control and communication costs and avoiding congestion. Yao et al. (yao2022fast, ) proposed the fast search and efficient algorithm for the floorplan of task modules on modern heterogeneous FPGAs with increasing both floorplan speed and success rate. However, this work only considers the cost of resource utilization and ignores other costs, such as the cost of wire length. These works (bolchini2011automated, ; banerjee2010floorplanning, ; yao2022fast, ) do not consider the task modules scheduling that affects the performance of PDRS. Besides, some other excellent works also only consider the partition and floorplan in PDRS but don’t consider schedule. (rabozzi2015floorplanning, ; liu2013resource, ; montone2010placement, ; singhal2006multi, ).

And some other works have focused on partition and schedule. Ganesan et al. (ganesan2000integrated, ) proposed a reconfigurable processor system with two reconfigurable regions for performance acceleration. This work exploits the characteristics of PDR to hide the configuration overhead and improve the parallelism to speed up. However, modern FPGA chips with PDR technology can support multiple reconfigurable regions, and thus this problem is more complicated. Rana et al.(rana2009minimization, ) proposed a reconfigurable overhead minimization method based on the analysis of the communication graph. This work tries to group task modules that require simultaneous reconfguration into the same reconfigurable region. However, the designer must appoint the number of the reconfigurable regions manually. R. Cordone et al. (cordone2009partitioning, ) proposed an integer linear programming (ILP) model and a heuristic method for task graph partitioning and scheduling. They exploit the characteristics of task module reuse and configuration prefetching to minimize reconfiguration overhead. (jiang2007temporal, ; purgato2016resource, ; tang2020partitioning, ) also contribute to task module partitioning and scheduling in PDRS.

However, task modules partitioning affects schedule and floorplan, and these three factors significantly impact the performance, resources utilization, and energy consumption of PDRS. And some works have focused on solving the problems of task modules partitioning, scheduling, and floorplanning of PDRS integrated. P. Yuh et al. (yuh2004temporal, ; yuh2007temporal, ) modeled the task modules as three-dimensional (3D) boxes and proposed an SA-based 3D floorplanner to floorplan and schedule task modules. However, assuming task modules can be reconfigured at any time and in any region may not match practically reconfigurable architectures. E. A. Deiana et al.(deiana2015multiobjective, ) proposed a scheduler based on mixed-integer linear programming (MILP). The scheduler can schedule and deploy applications on PDRS based on FPGA. And if the scheduler cannot successfully perform, the scheduler will be re-executed until a feasible floorplan is determined. However, the time consumption of the MILP-based approach is impractical for large-scale applications. Chen et al. (chen2018integrated, ) proposed the partitoned sequence triple P-ST to express partition, schedule, and floorplan of task modules for PDRS and used an SA-based search engine with a perturbation method to achieve a higher success rate of floorplan with optimizing schedule time. However, this work models the process of PDRS by modeling homogeneous resource, CLB, and thus simplifies these problems.

These works mentioned above either solve the three problems sequentially or solve only two of the three problems in an integrated framework, or model the process of PDRS by modeling homogeneous resources, thus simplifying these problems.

In this paper, we propose a complete workflow to find the optimal solution of task modules partitioning, scheduling, and floorplanning on heterogeneous resources based on FPGA-PDRS. This workflow includes pre-processing, the exploration of task modules partitioning, scheduling, floorplanning, and post-optimization. The main contributions of this paper are outlined as follows.

1. 1)

   In this pre-processing process, we propose the strategy of generating the list of task modules candidate shapes according to resources requirements of each task module. This strategy is based on the enumeration of task module shapes.

2. 2)

   We change our previous algorithm(chen2018integrated, ) by changing the process of exploring solution space and adding the cost of heterogeneous resource utilization to generate the solution of task modules partitioning, scheduling and floorplanning. Then we integrate the changed algorithm into the complete workflow.

3. 3)

   After given the partition, schedule, and floorplan of task modules, we build the ILP model to reselect task modules shape from the candidate shapes list to improve the success rate of floorplan.

The experimental results demonstrate the efficiency and effectiveness of the proposed algorithms. The remainder of the paper is organized as follows. Section 2 not only describes the hardware architecture and the process of FPGA-PDRS but also describes the definition and analysis of problems. Section 3 discusses the overall design workflow of generating the partition, schedule, and floorplan of task modules for FPGA-PDRS. Section 4 describes the proposed algorithms of pre-processing and post-optimization. The experimental results and conclusions are shown in Section 5 and Section 6, respectively.

To deploy a large-scale computing application to a partially dynamically reconfigurable system based on FPGA, we need to divide the application into several task modules and then partition, schedule and floorplan these task modules. We define the set of $n$ task modules as $M=\{m_{i}|1\leq i\leq n\}$.

Implementing the reconfiguration process requires synthesizing task modules. The synthesizing results will provide the resources requirements of task modules, which mainly include the demand for Lookup Table(LUT), Flip-Flop(FF), BRAM, and DSP. While CLB is composed of LUT and FF, we can regard the synthesizing results as the demand for CLB, BRAM, and DSP. The synthesizing and simulation results will also provide the execution time of each task module. In addition, to model the deployment of task modules in FPGA-PDRS, we add configuration time and shape to the task module. These notations and meaning related to the factors of task module and the chip are shown in Table 2.

There are data dependencies among these task modules, which are defined by a task graph $TG=(V_{TG},E_{TG})$ $V_{TG}$ represents the set of task modules $(=M)$. $E_{TG}$ represents data dependencies among task modules. The definition of $E_{TG}$ is as follows:

To ensure that the floorplan on heterogeneous resources is feasible, we consider the following constraints:

1. (1)

   The region occupied by the task module on the chip must meet the resources requirements of CLB, BRAM, and DSP.

2. (2)

   The task modules in the same time layer must be nonoverlapped and placed within their corresponding reconfigurable region. And the reconfigurable regions must be placed without overlapping each other.

3. (3)

   The whole part of the PDRS needs to meet the boundary constraints, the width and the height of PDRS cannot exceed the width and the height of the chip, respectively.

In summary, we define the input, output, and objective of this study as follows:

Input: The graph of data dependency among task modules and related information of task modules.

Output: The solution of task modules partitioning, scheduling, and floorplanning in FPGA-PDRS.

Objective: Maximize the performance with improving the utilization of heterogeneous resources and reducing the communication cost.

Each task module has the demands for heterogeneous resources CLB, BRAM, and DSP on the chip. For the task module $m_{i}$, the demand is denoted as $[CLB_{i},BRAM_{i},DSP_{i}]$. The irregular column structure on the chip and undetermined position of task modules make generating the width and height of task module $m_{i}$, which are denoted as $width_{i}$ and $height_{i}$, respectively, a tough problem.

The shape of the task module $m_{i}$ is larger will reduce heterogeneous resources utilization. In contrast, the smaller shape of the task module $m_{i}$ may not meet the resource requirements in a certain position, thus inducing infeasible floorplan. To make the shape of task module $m_{i}$ meet the resource requirements at each position on the chip, the shape needs to move along the x-axis and meet the resource requirements in each movement.

Since the irregular column structure on the chip is continuous, we adopt an enumeration strategy. The pseudo code for generating the candidate shape list is shown in Algorithm. 1. We traverse all task modules and all the possible widths of each task module on the chip. And for each width of task module $m_{i}$, we find a height that can let the task module meet the resource requirements at all positions on the chip. Specifically, under each width of task module $m_{i}$, if the maximum height can meet the resource requirements at each position on the chip, we reduce the height one by one until it cannot meet this condition. Since we use the enumeration strategy of increasing the width and determining the minimum height under each width, some shapes with the same height but different widths may appear. Those shapes with smaller widths are better shapes. Thus, we remove those shapes with the same height but larger width from the list. Then if the aspect ratio of the shape is less than $\gamma$, we add this shape to the candidate shape list. Since (chen2008fixed, ) interpret intuitively and show by experiments that an aspect ratio close to one is beneficial to wirelength, we set $\gamma$ to 1.5 for optimization of communication cost and ensure a certain solution space margin.

Finally, according to area, we choose the top $n$ shapes from this list as the final candidate shape list. The value of $n$ is related to the complexity of the exploration process and the process of post-optimization. A relatively larger value of $n$ means that the exploration process can explore more floorplan solutions and better optimize schedule time and communication cost. Also, the larger value of $n$ provides a larger solution space of reselecting task modules shapes for the process of post-optimization and can better improve the floorplan success rate of the solution. And in this work, we empirically set $n$ to 10.

After generating the candidate shape list for each task module, we initialize the shape of each task module from the corresponding list. In this paper, we use the shape with minimum area as the temporary shape of the task module. Then we use these initialized task modules shape as the input of the exploration process to generate the solution of task modules partitioning, scheduling, and floorplanning of PDRS.

The process of exploring the solution space reduces the total cost in each iteration. And to ensure the performance of PDRS, the floorplan of the generated solution may exceed the boundary, which is like the left figure of Fig. 6(b). As described in Section 2.3.3, there are no direct relationships between the task module shapes and the shape of the whole PDRS, and the shape of the task module affects the shape of its time layer and thus affects the shape of the reconfigurable region. To make the floorplan of this solution feasible, we can reselect the task modules’ shapes from the candidate shape lists, and then change the shape of reconfigurable regions thus generating the feasible floorplan like the right figure of Fig. 6(b).

As shown in Fig. 6(a), assuming there are $m$ task modules, and there are $n$ shapes in the list of each task module. Then the solution space size is $n^{m}$. Therefore we establish a ILP model to solve it and try to find feasible floorplan of the solution through the solver Gurobi. The ILP model involves three-part constraints, one is the constraint of task modules shape, one is the constraint of the position relationship among task modules, and one is the boundary constraint of the whole design of PDRS.

We use a matrix to represent the shape selection of task modules, which likes Fig. 6(a) and denoted as $MS$. If task module $m_{i}$ use shape $s_{j}$, then we denote this by $MS[i,j]=1$. A task module can only have one shape, so we have the following constraint for selecting the shape of each task module. This constraint is shown by Equation (5), and in Equation (5), $m$ is the number of task modules.

Then, the width and height of task module $m_{i}$ can be expresented by linear expression Equation (6) and Equation (7), respectively.

After adding constraints to the shape of task modules, we then add constraints to the positional relationship among task modules and finally get the boundary of the whole design of PDRS. In this work, we use P-ST that is proposed in our previous work (chen2018integrated, ) to represent the solution information. P-ST includes the Sequence Pair(SP)(murata1996vlsi, ) to represent floorplan, and the information of reconfigurable regions and time layers are added to SP to express partition.

All constraints of calculating coordinates are added to these two matrices. By traversing SP and adding constraints to each row of the two matrices, we can get the linear expression of the constraints coordinate of the task modules floorplan. And for the boundary of floorplan of PDRS, we have the following constraints Equation (8) and Equation (9) to limit $X_{max}$ and $Y_{max}$, respectively.

The feasible floorplan means that the whole PDRS should be placed within the chip boundary, therefore we add the constraints to the boundary of PDRS. The constraints are shown by Equation (10), and in Equation (10), $Width$ and $Height$ are the boundaries of the chip.

Finally, we set the objective function of this model as to maximize the value of subtracting between chip boundary and the boundary of the whole design PDRS. This objective is shown by Equation (11).

In this study, all proposed methods were implemented in C/C++ language on a 64-bit Linux workstation (Intel(R) Xeon(R) Gold 6254 CPU @ 3.10 GHz, 125 GB RAM). Since there are no standard benchmarks for the discussed problems, we constructed the benchmarks by using the tool Task Graphs For Free (TGFF)  (1998TGFF, ) to generate a directed acyclic graph(DAG) to represent the task modules and the data dependencies among task modules. We denote this graph as task graph(TG). The information of nodes and edges, which represent task modules and data dependencies, respectively, in TG, is shown in Table 3.

We also generate two benchmarks from two popular convolutional neural network models, AlexNet(krizhevsky2017imagenet, ) and VGG(simonyan2014very, ). The two benchmarks respectively include all the convolution layers, pooling layers, and full connection layers of the two neural networks. The convolution layer and full connection layer mainly include the multiply-add computing unit, and the pooling layer mainly includes the comparator. Therefore, we synthesize the heterogeneous resources usage of the multiply-add computing unit and the comparator, respectively. We use several multiply-add computing units as a convolution kernel and several comparators as a pooling kernel. For the convolution layer and full connection layer with larger computation, we use several convolution cores to perform convolution operation over these feature maps by channel parallel, and for the pooling layer, we use a specified pooling core to perform pooling operations over all the output feature maps. The execution times of task modules are estimated based on a frequency of 200MHz.

In Table 3, each benchmark has three different implementations and these implementations has the same number of task modules but different task dependencies. And $\#V$ and $\#E$ denote the number of nodes and edges in TG, respectively. The column $VMR$ represents the range of random values of execution time for task modules, the column $EWR$ means the range of random values of communication among task modules, and the column $CPT$ represents the critical paths of the task graphs, in which the task modules are weighted by execution time. The column $CLB$, $BRAM$, and $DSP$ represent the range of random values of task modules’ resources requirements for CLB, BRAM, and DSP. And in this work, we use one of the most widely used Xilinx Virtex-7 series FPGA chips, XC7VX485T, as the target chip.

In this section, we show and analyze the experimental results of the comparison. The complete workflow in this paper includes three parts, pre-processing, the exploration of task modules partitioning, scheduling, floorplanning, and post-optimization. To demonstrate the efficiency and effectiveness of the three processes, we accomplish three comparative experiments.

Firstly, we compare the effect of our method of generating task modules shapes on heterogeneous resources usage with (banerjee2009fast, ). Secondly, we compare the solution generated by our complete workflow with the solution generated by the method $Int\_PSF$ in previous work(chen2018integrated, ) on schedule time, communication cost, floorplan success rate, and heterogeneous resources reuse rate. Thirdly, We compare the improvement of the floorplan success rate through the ILP model in post-optimization with the solution generated by the exploration process.