## 4 Algorithm Flow
### Basic Flow
In the actual circuit design, the logical depth \(C\) of the path is much lesser in order of magnitude than the number of replaced cells \(A\) and the number of traversed paths \(B\), which can be considered as a constant when calculating the time complexity. Moreover, \(A\) and \(B\) can be considered in the same order of magnitude. Thus, the worst time complexity obtained is \(O(B^{2})\) of finding the worst path. Then we update the sub-algorithm, which improves the running time in two ways while guaranteeing the same execution results. #### 4.2.1 Optimize the Way to Update Cells' Weight

Weighting aims to find the most critical cell in a given path. The original approach was to replace a cell and update the weights of all associated cells. Therefore, we propose a new updating strategy that can effectively reduce the number of updating weights. First, we do not update the cell weight immediately after the cell is replaced. At this point, the weights of all the cells in the given path are not updated. Moreover, there is a fact that the weight of the updated cell will not exceed what it was when it was not updated. Therefore, we only need to obtain a cell that satisfies the following conditions: (1) its weight has been updated; (2) its weight is greater than the weight of all other cells in the path (regardless of whether the weight of other cells is updated). To this end, the following update operations are taken: (1) to obtain the cell with the highest weight in the path. (2) If the weight of this cell is not updated, update it and return to step (1); otherwise, output this cell. Figure 7 shows an example. In step (a), we obtain cell A with the highest weight in the path. In step (b), we judge that the weight of cell A needs to be updated, so we update it and find a new cell F with the largest weight. In step (c), we judge that the weight of cell F still needs to be updated; after updating it, we find that cell F has met the abovementioned conditions, so we output it. The above operations effectively reduce the number of operations to update the cell's weight and the algorithm's running time. #### 4.2.2 Optimize the Way to Find the Path

Updating path weight is the operation with the highest time complexity in Algorithm 1. Therefore, the following method is proposed to reduce the time complexity. We set a range according to path weight R, obtain the paths with the worst timing in the path collection, and set it as the subpath collection. There is a fact that for each path, the path weight only decreases as the cells are swapped to a lower threshold voltage. As long as the following operations are performed, the path with the worst timing must be in the subpath collection: (1) replace and update the path's weight in the subpath collection

Figure 7: An example of the new way to update the cell weights. every time and remove the path that no longer belongs to the range. (2) When the subpath collection is empty, give a new range to obtain a new subpath collection. Therefore, we can only traverse the collection of subpaths when looking for the worst path, avoiding traversing all paths. We obtain the subpath collection in the following way: set a parameter \(D\) (\(D>1\)) and set the initial range of the subpath set as \((1-1/D)<R<1\). When a new range is needed, reduce the left and correct bounds by \(1/D\) each. We compared the experiment shown in Figure 6 based on the same circuit condition. Set \(D=B^{0.5}=655\). The relationship between the number of traversed paths and the times of swapping cells are shown in Figure 8. Observe that the number of traversed paths is always less than the value of \(B/D\). According to the experiment results, the number of operations for extracting the sub-collection and traversing path is less than \((A*B/D+B*D)\). We take \(D=B^{0.5}\) in the experiment. Thus the time complexity in the experimental results of the new approach is \(O(B^{1.5})\). #### 4.2.3 The Update Algorithm

After applying the above two methods, the update algorithm for Algorithm 1 is shown in Algorithm 3.