## 3 Proposed HT Mitigation Method
### Optimization of Evolvable Regions  
EA is usually time-consuming for generating optimal target circuit structures, especially when the circuits are complex and/or oversized. To reduce the evolution time, we propose an algorithm to optimize the evolvable region. While retaining the original circuit occupying the on-chip region, the evolvable region is expanded step by step until it stops when the number of redundant PEs in the current region is satisfied to be greater than HT-I PEs. Figure 4 shows the method and the effect of optimizing the evolvable region.  
Algorithm 1 describes the pseudo-code for optimizing the evolvable region. The algorithm's input is all PEs on the CGRA architecture, and the output is the optimized evolvable region. First, we assign coordinate values to the positions of all PEs with the purpose of quantifying the distance and area (lines 2-4). Based on this, we traverse to find the coordinates of the leftmost, topmost, rightmost and bottommost (\(X_{t}\), \(Y_{t}\), \(X_{r}\), \(Y_{b}\)) PEs of the current circuit to be evolved (lines 6-8). Once these four coordinates are obtained, the area of the rectangle in which the circuit to be evolved is located is calculated (line 10). If the number of free PEs (\(F_{p}\)) contained in this rectangular area is greater than the number of PEs inserted by the HTs (\(H_{p}\)), then this area is the evolvable area. Otherwise, the clustering solves for the center coordinates (\(CP\)) of the circuit to be evolved (line 17). Afterward, an attempt is made to expand the original region with rectangular cells (line 19) and calculate the Euclidean distance (lines 21-23) of all the newly added PEs from the \(CP\). After that, the Euclidean distances are sorted in ascending order (line 25), and the relationship between the number of \(F_{p}\) and the number of \(H_{p}\) in the current region is compared in order (lines 27-29). If there are joined rectangular regions in which \(F_{p}\) is greater than \(H_{p}\), the current region is an evolvable region; otherwise, lines 18-31 are repeated until the PE requirement for evolution is satisfied. The time complexity of this algorithm is \(O(n)\).  
Figure 4: The effect of optimizing the evolvable region. (Red Color: the HT-I PEs; Blue Color: the coordinates of the leftmost, topmost, rightmost and bottommost PEs; [PERSON] and Pink Color: the effect of optimizing evolvable region).  
Figure 3: Proposed structure for protection of FPGA against HTs.  
```
1:All PEs on the CGRA
2:Optimized Evolvable Region (OER);
3:List_PEsall PEs; ListC_PEs:PEs used in the current evolutionary circuit.
4:
5:
6:
7:
8:end for
9:/* Calculate the initial area (\(Ira\)) occupied by the current evolutionary circuit */
10:\(Ira=(X_{l}-X_{r})\times(Y_{t}-Y_{b})\)
11:/* Compare the number of free-PEs (\(Fp\)) in the Ira with the number of HT-I PEs (\(Hp\)) */
12:if\(F_{p}>=Hp\)then
13:Output\(Ira\to Ora\)
14: break
15:else
16: /* Clustering to solve the center point (\(CP\)) of the current evolutionary circuit */
17:\(CP\to Clustering(ListC\_PEs.cv)\)
18: /* Expand the evolution area (\(era\)) horizontally or vertically
19:\(List\_Era\to Expend(Ira)\)
20: /* Calculate Euclidean_distance between the added coordinates (\(a\_cv\)) and \(CP\) in turn */
21:for\(i\)in\(length(List\_Era)\):do
22:\(Euclidean\_distance\to Calculate(CP,a\_cv)\)
23:endfor
24: /* Sort the Euclidean distance in ascending order */
25:\(List\_Era\to Sort(Euclidean\_distance)\);
26: /* Compare sequentially in ascending order of Euclidean distance \(Fp\) and \(Hp\) */
27:if\(List\_Era.Fp>=Hp\)then
28:Output\(List\_Era\to Ora\)
29: break
30:else
31:repeat (18)-(31);
32:endif
33:endif
```  
**Algorithm 1** Optimization of Evolvable Region Algorithm