## 4 Algorithm Flow
### Basic Flow
```
0: path collection \(C\), static power consumption \(P\), timing arcs, the OCV derate \(\alpha\)
0: sub cell swap list
1: Initialize each path \(i\)'s \(t_{slack}\), \(t_{repairable_{i}}\) and \(R_{i}\) from collection C
2: Collect the replaceable cells on each path \(i\) as collection \(CIP_{i}\)
3: Collect the paths through each cell \(j\) as collection \(PTC_{j}\)
4: Initialize each cell \(j\)'s weight \(WS_{j}\) (HVT-to-SVT) and \(WL_{j}\) (SVT-to-LVT)
5: Initialize the state of all cells to 0
6: When cell \(j\)'s state is 0, \(W_{j}=WS_{j}\); when state is 1, \(W_{j}=WL_{j}\); when state is 2, \(W_{j}=0\)
7:repeat
8: Select the path \(m\) with the largest \(R_{m}\) value
9: Select the cell \(n\) with the largest \(W_{n}\) value in \(CIP_{m}\)
10:if cell's state = 0 then
11: Swap cell \(n\) from HVT to SVT, remark cell's state as 1
12:elseif cell's state = 1 then
13: Swap cell \(n\) from SVT to LVT, remark cell's state as 2
14:endif
15:for each path \(x\) in \(PTC_{n}\)do
16: Update \(t_{slack}\), \(t_{repairable_{x}}\), \(R_{x}\) with Equations (3), (4) and (6)
17:for each cell \(y\) in \(CIP_{x}\)do
18: Update \(WS_{y}\), \(WL_{y}\) with Equation (8)
19:endfor
20:endfor
21:until all paths' \(t_{slack}\geq 0\)
22:Return sub cell swap list
```  
**Algorithm 1** Sub triple-threshold voltage distribution algorithm ```
0: Static timing analysis results
0: Final cell-swapping list
1: Initialize the circuit state to all-HVT
2: Initialize the path collection \(C\)
3:repeat
4: Provide path collection \(C\) to Algorithm 1
5: Obtain the sub cell-swapping list from Algorithm 1
6: Obtain the new path collection \(C^{{}^{\prime}}\) after applying the sub cell swapping list in STA tools
7: Add the new path collection \(C^{{}^{\prime}}\) to the original path collection \(C\)
8: Restore the circuit state to all-HVT
9:until STA results meet the timing constraints
10:Return Final cell-swapping list
```

**Algorithm 2** Top triple-threshold voltage distribution algorithm

### Optimize the Sub Algorithm

We then will discuss the time feasibility of Algorithm 1. Calculate the time complexity of Algorithm 1. Assume that the number of swapped cells is \(A\), the number of paths in path collection is \(B\), and the maximum number of cells on a path is \(C\). The time complexity of the initialization phase is \(O(B*C)\). In the algorithm, we need to retrieve the most critical path before each cell replacement, i.e., find the path with the worst timing among all the paths that have not yet met the timing constraints. With the execution of the algorithm, the number of paths that do not meet the timing constraints gradually decreases. Therefore, the number of paths that need to be traversed per replacement is also decreasing. Figure 6 shows the relationship between the number of paths to be traversed and the current number of replaced cells. The experimental circuit in this figure is the same as that in Section 5. In this figure, the experiment was performed on a CPU circuit containing 385781 cells and triple-threshold voltage. The experiment was to execute Algorithm 1 once based on the initial path collection. The experimental results show that the number of paths to be traversed decreases approximately linearly as the number of replaced cells increases, so the time complexity of finding the worst path is \(O(A*B)\). The time complexity of finding the cell with the highest weight in the worst path is \(O(A*C)\), while that of swapping cells is \(O(A)\). The worst case is that every cell of every path is replaced. Thus the time complexity of updating the path weights is \(O(B*C)\)

Figure 6: The relationship between the number of traversed paths and the times of swapping cells. A change in each path causes the weights of the \(C\) cells to be updated. Thus the time complexity of updating the cell weights is \(O(B*C^{2})\).