## 5 Adaptive Core Distribution Optimization Algorithm
### ACTR Algorithm
Therefore, the sliding window mechanism not only enhances the search efficiency of the algorithm but also, as demonstrated by comparative experiments, generates a set of optimal solutions. Experimental results demonstrate that the algorithm has good robustness and reliability. Based on the mechanisms mentioned above for NoC-based embedded multiprocessor systems, we propose the optimized core distribution adaptive topology reconfiguration algorithm (ACTR). The general ideas of ACTR are listed as follows:  
1. Initialize the physical array H, the router frame generated for the solution S.
2. Locate all faulty cores in S and count the number of faulty core PEs. 3. Calculate the normalized Euclidean distance between the faulty core PEs, generate the core distribution factor Q, and set a dynamic threshold to determine whether special treatment is needed. 4. Based on the distribution of faulty core PEs, decide the final traversal order, which may involve comparing the number of faulty core PEs in different regions. 5. Output the processed solution S as the final target array T.  
The pseudo-code of this core algorithm is shown below (Algorithm 1). In order to analyze the time complexity of the ACTR algorithm, we have taken an example of the reconfiguration of a target topology of size \(n\times(n+k)\). In this algorithm, the generation of the router framework involves traversing an \(n\times n\) grid, resulting in a complexity of \(O\big{(}n^{2}\big{)}\). Identifying faulty cores requires iterating through the physical array \(S\) of size \(n\times(n+k)\), leading to a complexity of \(O(n(n+k))=O\big{(}n^{2}+nk\big{)}\). The calculation of normalized Euclidean distances among faulty processing elements (PEs) involves nested loops, yielding a worst-case complexity of \(O\big{(}t^{2}\big{)}\), which can also be approximated as \(O\big{(}n^{2}\big{)}\) under maximum fault conditions. Additionally, generating the core distribution factor and calculating the dynamic threshold are \(O(1)\) operations. The final counting of faulty PEs contributes \(O(n(n+k))\). In summary, the total time complexity of the entire ACTRalgorithm is approximated as \(O\big{(}n^{2}+nk\big{)}\), emphasizing the significant impact of both \(n\) and \(k\) on performance. ```
0: An \(n\times(n+k)\) physical array H
0: An \(n\times n\) target array T
1: \(S:=H\);
2: Initialize \(t:=0\);
3:for\(i:=0\) to \(n-1\)do
4:for\(j:=0\) to \(n-1\)do
5: Pan the routers to generate a new \(n\times n\) router framework for solution S;
6:endfor
7:endfor
8:for\(i:=0\) to \(n-1\)do
9:for\(j:=0\) to \(n+k-1\)do
10: Find all faulty cores depending on the coordinates in \(S_{ij}\)
11: Record the number of faulty PEs;
12:if\(S_{ij}\) is faulty then
13:\(t:=t+1\);
14:endif
15:endfor
16:endfor
17:for\(i:=0\) to \(t-1\)do
18:for\(j:=i+1\) to \(t-1\)do /*t representing the number of faulty PEs;*/
19: Calculate the normalized Euclidean distance of faulty PEs;
20:endfor
21:endfor
22: Generate the core distribution factor for Q;
23:Dynamic_threshold := \(log_{10}n\);
24:if Dynamic_threshold >= Q then
25: T := ACTR-SDC(S);
26:return T;
27:endif
28:for\(i:=0\) to \(t-1\)do
29: Calculate the upper right numbers of faulty PEs in \(count1\);
30: Calculate the lower left numbers of faulty PEs in \(count2\);
31:endfor
32:if\(count1\geq count2\)then
33: T := ACTR-URC(S);
34:else
35: T := ACTR-DLC(S);
36:endif
37:return T;
```  
**Algorithm 1** ACTR Algorithm. ACTR involves the ACTR-URC procedure, ACTR-DLC procedure, and ACTR-SDC procedure to determine and locate the distribution of faulty cores. The general framework of these three procedures is basically the same, but the order of their search is different. The SDW procedure is invoked to perform the search. It is designed to receive an initial solution from the ACTR algorithm and eventually generate the optimal solution for the search. The pseudo-code for one of the derived algorithms will be given below (Algorithm 2).