## 3 Problem Formulation
### Insight of the Studied Problem  
In order to facilitate the description of the target problem, the concepts of module merging and reconfiguration node need to be introduced first. The module merging technique combines several tasks to a reconfiguration node which is the minimum reconfiguration unit. Those tasks contained in a single reconfiguration node are reconfigured as a whole. A reconfiguration node is be denoted as \(\textbf{RN}=\{...,n_{p},\,...,\,n_{q},...\}(p\
eq q)\), each element represents a task in the node. Reconfiguration node has multiple attributes, including reconfiguration start time \(Rs\), reconfiguration end time \(Re\), and execution start time \(Es\), execution end time \(Ee\). First, we discuss how to determine the size and the number of a reconfigurable region. Generally, the number of region is set to an upper limit, and the optimal solution for partitioning and scheduling is determined within the upper limit. The size of a region must meets the maximum resource requirement of the set of tasks mapped to a region. Besides, the task is mapped to a region and is related with a reconfiguration node. The life cycle of each reconfiguration node is divided into three phases, i.e., the reconfiguration phase, the execution phase and the waiting phase. Each phase has a start time and an end time. The reconfiguration end time is the sum of the reconfiguration start time and the reconfiguration time of the reconfiguration node, which can be expressed as:  
\[Re_{i}=Rs_{i}+RT_{i} \tag{2}\] \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Task Name** & **ET** & **CLB Num** & **PN** & **CN** \\ \hline \(n_{0}\) & 243 & 231 & - & \(\{n_{3}\}\) \\ \(n_{1}\) & 175 & 532 & - & \(\{n_{3},n_{4}\}\) \\ \(n_{2}\) & 154 & 287 & - & \(\{n_{4}\}\) \\ \(n_{3}\) & 146 & 357 & \(\{n_{0},n_{1}\}\) & \(\{n_{5},n_{6}\}\) \\ \(n_{4}\) & 139 & 532 & \(\{n_{1},n_{2}\}\) & \(\{n_{5}\}\) \\ \(n_{5}\) & 199 & 91 & \(\{n_{3}\}\) & \(\{n_{7}\}\) \\ \(n_{6}\) & 256 & 406 & \(\{n_{3},n_{4}\}\) & \(\{n_{7}\}\) \\ \(n_{7}\) & 17 & 14 & \(\{n_{5},n_{6}\}\) & \(\{n_{5}\}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: DAG parameter. Figure 2: A sample directed acyclic graph (DAG). The execution end time is the sum of the execution start time and the execution time \(ET\):  
\[Ee_{i}=Es_{i}+ET_{i} \tag{3}\]  
The FPGA resource is finite in actual scenarios, it is impossible to divide logic resources indefinitely. Hence, there are constraints between supply and demand of resources. The resources of the region and the resource requirement of the task need to meet the following constraints:  
Constraint 1. The type and amount of resources in a reconfigurable region must meet the resource requirements of the largest reconfiguration node in this region, which can be modeled as:  
\[\left|h_{i}^{\mathbf{PR_{k}}}\right|\geq\left|h_{i}^{\mathbf{RN_{m}}}\right|, \forall h_{i}\in\mathbf{H},\mathbf{RN_{m}}\in\mathbf{PR_{k}},\mathbf{PR_{k}} \in\mathbf{PR} \tag{4}\]  
Constraint 2. The total amount of resources of all regions does not exceed the total amount of FPGA resources. \[\sum_{k=0}^{\left|\mathbf{PR}\right|}\left|h_{i}^{\mathbf{PR_{k}}}\right|\leq \left|h_{i}^{FPGA}\right|,\forall h_{i}\in\mathbf{H} \tag{5}\]  
Then, for the problem of scheduling order of the set of tasks, we need to set a reconfiguration order value for each reconfiguration node, which represents the reconfiguration order of the corresponding reconfiguration node in the entire scheduling process. We use \(\mathbf{O}=\left\{\mathbf{RN_{0}},\mathbf{RN_{1}},\,...,\,\mathbf{RN_{i}}\right\}\) to denote the reconfiguration order of all nodes. Each node \(\mathbf{RN_{i}}\) and the tasks it share the same unique reconfiguration order value (ROV), and ROV increases from left to right in \(\mathbf{O}\). Due to the physical constraints of the existing FPGA architecture, the partitioning and scheduling process of DPR system needs to satisfy the following constraints:  
Constraint 3.