## 4 The Reconfiguration-Dependency Non-Consistent Algorithm Based on Simulated Annealing (RDNC-SA)
### Solution Feasibility Evaluation
#### 4.4.2 Execution Infeasible Condition  
In a solution, if the task cannot get the data of the parent tasks according to the dependency relationship during the execution of the task, we call this solution the execution infeasible solution. To clearly describe this condition, several definitions are introduced to describe the relationship between different tasks of the application. **Definition 1**. : _If the ROV of a certain task is greater than any ancestor task or less than any descendant task, we call this case the reverse order._  
**Definition 2**. : _If the ROV of a certain task is less than or equal to all ancestor tasks and greater than all descendant tasks, we call this case the positive order._  
**Definition 3**. : _The reconfiguration-adjacent node of \(n_{i}\) is the reconfiguration node that is rightly reconfigured after \(n_{i}\) on the same region. The tasks in the node are called reconfiguration-adjacent tasks. Noting that \(n_{i}\) and its reconfiguration-adjacent node \(\mathbf{RN_{j}}\) should be mapped to the same region, and no other node is reconfigured between \(n_{i}\) and \(\mathbf{RN_{j}}\)._Based on the above definitions and the previous analysis of the solution structure, we give a lemma to indicate under what conditions the solution is a feasible solution. **Lemma 1**. : _For a task \(n_{i}\), \(n_{i}\) and its ancestor tasks cannot be in reverse order relationship in the same region, and if the reconfiguration-adjacent task of \(n_{i}\) exists, it cannot be reconfigured before any ancestor task of \(n_{i}\)._  
For any two different tasks \(n_{i}\) and \(n_{j}\), we assumed that \(n_{i}\) is an ancestor task of \(n_{j}\). As we know, a sufficient and necessary condition for an execution feasible solution is that the task can obtain the data it needs in a limited time. Hence, when a task can be executed, it must have obtained the data of all parent tasks. And when its parent tasks can be executed, they must have obtained the data of all grandparent tasks, and so on. We conclude that \(n_{j}\) must not be executed if any ancestor task \(n_{i}\) is not executed. As the previous analysis, a solution consisted of reconfiguration order and task-to-region allocation. For two tasks, the reconfiguration order relationship can be divided into reverse order and positive order and task-to-region allocation relationship can be grouped into in the same region and in the different region. For positive order, regardless of whether the task is in the same region, its corresponding solution must be a feasible solution. When \(n_{i}\) and \(n_{j}\) belong to the same region because of positive order, it is obvious that \(n_{i}\) carried out execution phase before \(n_{j}\). In different region, \(n_{j}\) must obtain its parents data before its reconfiguration-adjacent tasks start to reconfigured. Because execution must be feasible when the reconfiguration order is positive order. So, there must be feasible solutions. For reverse order, we assume that the tasks are in the same region and the reconfiguration-adjacent node of \(n_{j}\) exists. Before reconfiguration phase of the reconfiguration node which \(n_{j}\) belong starts, since \(n_{i}\) has not started the reconfiguration and execution, at least one parent task of \(n_{j}\) cannot be executed, which leads to \(n_{j}\) unable to execute. Therefore, the region where \(n_{j}\) is located will be in the waiting state after \(n_{j}\) reconfiguration. Since the reconfiguration of \(n_{i}\) is latter than \(n_{j}\) in the same region, the region will reconfigured before \(n_{j}\) starts the execution phase. Hence, the descendant task \(n_{j}\) will never wait for its parent data. For the different region situation, as mentioned earlier, \(n_{j}\) needs to wait for the data of the parent tasks after reconfiguration because the parent tasks of \(n_{j}\) is not fully executed. However, the reconfiguration-adjacent node reconfigures before \(n_{i}\). When \(n_{j}\) does not get \(n_{i}\) data, its reconfiguration region has been reconfigured.