1. Independent Circuit Structures

For any target node $\textit{i}$ of the circuit, the error probability can be regarded as the accumulation of error effects of the upstream circuit of the node (the circuit contained in the input cone of $\textit{i}$, denoted as INC$_{i}$). In COSEA, the circuit block is divided into two types. In INC$_{i}$, the output is the fanout node, while the input is the fanout node or the gate node of the original input. The circuit combination is called Fanout-Relevant Circuits (C$_{\mathrm{FR}}$). Its Failure Probability of C$_{\mathrm{FR}}$ (PFR) fans out to other circuits through the fanout source node, as shown in Fig. 1(a); some circuit module errors do not affect the fanout source node in INC$_{i}$. The output is the desired target node (non-fanout node), while the input is the fanout node or the original input. This circuit combination is called Fanout-Irrelevant Circuits (C$_{\mathrm{FI}}$). Its Failure Probability of C$_{\mathrm{FI}}$ (PFI) is as shown in Fig. 1(b).

Fig. 1. (a) Fanout-relevant circuits, (b) Fanout-irrelevant circuits.

2. Algorithm Flow

The method first extracts the circuit information from the netlist file, determines the logic value of the input signal and the failure probability of the gate, then stores and updates three pieces of information at each node: the logic value LV of the node, the failure probability PFI of the C$_{\mathrm{FI}}$, and the set U of the C$_{\mathrm{FR}}$. Based on the information at each node, we can calculate the failure probability of the node as follows:

where EPN$_{i}$ denotes the failure probability of node $\textit{i}$, n denotes the number of elements in the set of C$_{\mathrm{FR}}$, PFR$_{j}$ denotes the failure probability of fanout-relevant circuits C$_{\mathrm{FR}}$$_{j}$, and PFI$_{i}$ denotes the failure probability of fanout-irrelevant circuits C$_{\mathrm{FI}}$$_{i}$.

For node $\textit{i}$, the logical value of its input signal determines which C$_{\mathrm{FR}}$ and C$_{\mathrm{FI}}$ on the input signal can affect the output result; thus, the C$_{\mathrm{FR}}$, C$_{\mathrm{FI}}$ and logical values of the input signal need to be determined in order to calculate the node failure probability. There may be more than one C$_{\mathrm{FR}}$ affecting a node, and the set of all C$_{\mathrm{FR}}$ affecting a node is denoted by U. Moreover, the is at most one C$_{\mathrm{FI}}$ affecting a node; thus, we only need to calculate the PFI of the failure probability of the C$_{\mathrm{FI}}$ corresponding to each node. The failure probability of C$_{\mathrm{FR}}$ is not calculated directly, but is instead obtained by converting C$_{\mathrm{FI}}$ to C$_{\mathrm{FR}}$, as illustrated in Fig. 2.

Here, nodes $\textit{a}$, $\textit{b}$ and $\textit{c}$ represent the logic gates in the circuit, while the lines represent the connections in the circuit. When calculating the failure probability at point $\textit{a}$, C$_{\mathrm{FI(}}$$_{a}$$_{\mathrm{)}}$ is the C$_{\mathrm{FI}}$ with point $\textit{a}$ as the output; when the calculation reaches point $\textit{b}$, the range of C$_{\mathrm{FI(}}$$_{b}$$_{\mathrm{)}}$ includes C$_{\mathrm{FI(}}$$_{a}$$_{\mathrm{)}}$ and point $\textit{b}$. As point $\textit{b}$ is $\textit{a}$ fanout node, we calculate the failure probability of C$_{\mathrm{FI(}}$$_{b}$$_{\mathrm{)}}$ fanout at point $\textit{b}$, at which point C$_{\mathrm{FI(}}$$_{b}$$_{\mathrm{)}}$ is converted to C$_{\mathrm{FR(}}$$_{b}$$_{\mathrm{)}}$. As shown in Fig. 2(c), the failure probability PFR of the converted C$_{\mathrm{FR}}$ is equal to the failure probability of the PFI before conversion, while the PFI indicated by this node is set to 0.

The new C$_{\mathrm{FI(}}$$_{b}$$_{\mathrm{)}}$ no longer represents the range of the original C$_{\mathrm{FI(}}$$_{b}$$_{\mathrm{)}}$, but rather the C$_{\mathrm{FI}}$ circuit starting with the output of $\textit{b}$, without including any nodes. Thus, the new C$_{\mathrm{FI(}}$$_{b}$$_{\mathrm{)}}$ is the empty set, which corresponds to the failure probability PFI$_{\mathrm{(}}$$_{b}$$_{\mathrm{)}}$ = 0.

Fig. 2. The process of converting C$_{\mathrm{FI}}$ to C$_{\mathrm{FR}}$.

The failure probability of the circuit is accurately calculated based on the failure probability of the fanout-irrelevant node, the failure probability of each parent node and the logic value of the parent node iterated through to the output of the circuit. If the circuit under evaluation circuit is a single-output circuit, then the FPC is the original output node error rate. Otherwise, we first assume that the circuit contains $\textit{m}$ original outputs; since the error rate of each output node is composed of PFI and PFR, and the PFIs of any two output nodes are independent of each other while the different PFRs are also independent of each other, the failure probability of a multi-output circuit can be expressed as follows:

where $\textit{n}$ denotes the number of elements contained in the concatenated set of all original output nodes that fanout to the source set.

The algorithm about the calculation of COSEA are presented in Fig. 3.

Fig. 3. Pseudo-code of the COSEA algorithm.

1. Adaptive Strategies

In the basic cuckoo algorithm, parameters such as the power law exponent ${\beta}$, discovery probability $\textit{P}$$_{a}$ and scaling factor $\textit{r}$ are introduced. The settings of these parameters will have a great impact on the convergence of the global search and local search of the algorithm; thus, the parameter setting needs to balance the global search and convergence. In the basic CS algorithm, these parameters are fixed values, which is not a situation conducive to striking a balance between the algorithm's global and local random search. To overcome these shortcomings, we introduce an adaptive strategy to adjust these parameters with the goal of improving the solution search accuracy.

(1) Adaptive strategy with power-law exponent ${\beta}$

Fig. 5 and 6 show the fluctuation of the step at different values of ${\beta}$. From the figures, it can be seen that when ${\beta}$ is small, the fluctuation range of the step size is too large, which is not conducive to the convergence of the solution; when ${\beta}$ is large, moreover, the fluctuation range of the step size is too small, which is not conducive to the global search for the solution. Therefore, we set ${\beta}$ to fall within the range of [0.8,1.8] and use the adaptive strategy.

The values of ${\beta}$ are shown in Eqs. (9) and (10) below:

In Eq. (9), $\textit{n}$$_{i}$ denotes the current nest position, $\textit{n}$$_{best}$ denotes the optimal nest position at this time, and $\textit{l}$$_{max}$ denotes the maximum distance between the optimal position and the remainder of the nest positions. In Eq. (10), ${\beta}$$_{max}$ denotes the maximum value of ${\beta}$ (${\beta}$$_{max}$=1.8), while ${\beta}$$_{min}$ denotes the minimum value of ${\beta}$ (${\beta}$$_{min}$=0.8). This adaptive strategy indicates that if the current nest is close to the optimal nest position, the fluctuation of its step size will be reduced; conversely, if the current nest is far from the optimal nest position, the fluctuation of its step size will be increased to facilitate a better search for the optimal solution.

(2) Discovering adaptive strategies for probabilistic $\textit{P}$$_{a}$

A fixed value of $\textit{P}$$_{a}$ is not conducive to maintaining a balance between global and local search. To address this problem, it is necessary to adaptively adjust the $\textit{P}$$_{a}$ size according to different search results. In order to verify the performance of the cuckoo algorithm at different $\textit{P}$$_{a}$ values, three typical benchmark functions were selected for simulation, and the algorithm was used to search for function minima; their 3D surface graphs are presented in Fig. 7-9, and the experimentally selected test functions are shown in Eqs. (11)-(13).

Fig. 5. Step size fluctuations for different ${\beta}$ values.

Fig. 6. Fluctuation of step size when ${\beta}$ values are taken as 1.4, 1.8 and 2.

Fig. 7. 3D image of the Sphere function.

Fig. 8. 3D image of the Rosenbrock function.

Fig. 9. 3D image of the Rastrigrin function.

The parameters of the cuckoo algorithm were set as follows: number of nests $\textit{n}$=10, power law exponent ${\beta}$=1.5, scaling factor ${\alpha}$=0.8, number of iterations $\textit{iter}$=100, $\textit{P}$$_{a}$=0-1 (0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9 and 1), and each program was run 80 times independently for different values of $\textit{P}$$_{a}$. The performance of the algorithm was evaluated by observing the average of the results of each test function.

The experimental results are shown in Table 2. As can be seen from the table, the average value of the algorithm function is smaller in the range of [0.2, 0.8] for Pa. In summary, the probability of discovery Pa is chosen to be [0.2, 0.8].

The $\textit{P}$$_{a}$ adaptive strategy is as follows:

In Eq. (14), $P_{a\_ i}^{t}$ denotes the probability that the $\textit{i}$th individual in the population of generation $\textit{t}$ is found, $\textit{P}$$_{a\_max}$ and $\textit{P}$$_{a\_min}$ denote the upper and lower bounds of the probability of finding $\textit{P}$$_{a}$, and $f_{i}^{t}$ and $f_{best}^{t}$ denote the fitness of the $\textit{i}$th individual and the optimal individual respectively in the population of generation $\textit{t}$. This means that the further the nest is from the optimal nest, the higher the $\textit{P}$$_{a}$ value and the higher the probability of abandoning the nest; conversely, the closer the nest is to the optimal location, the lower the $\textit{P}$$_{a}$ value and the lower the probability of abandoning the nest.

(3) Adaptive strategy for scaling factor $\textit{r}$

In the basic cuckoo algorithm, the scaling factor $\textit{r}$ is a uniformly distributed random number in the interval [0, 1]. Its randomness does not guarantee a large variety of the worse individuals. If the scaling factor $\textit{r}$ can be better controlled to produce a large variety of the worse individuals and thus improve the algorithm's solution accuracy, this paper uses an adaptive mechanism to control the scaling factor r with the value interval [0, 1].

The scaling factor $\textit{r'}$s adaptive strategy can be expressed as follows:

In Eq. (15), $r_{i}^{t}$ denotes the scaling factor of the $\textit{i}$th individual in the $\textit{t}$th generation population, $\textit{r}$$_{\mathrm{max}}$ and $\textit{r}$$_{\mathrm{min}}$ denote the upper and lower bounds of the scaling factor, and $f_{i}^{t}$, $f_{best}^{t}$ and $f_{\textit{worst}}^{t}$ denote the fitness of the $\textit{i}$th, best and worst individuals in the $\textit{t}$th generation population, respectively. This means that the further the current nest is from the optimal nest, the larger the $\textit{r}$-value, and the further farther the updated nest is from the current nest; conversely, the closer the optimal nest location, the smaller the $\textit{r}$-value, and the closer the updated nest is to the current nest.

2. Improving Initial Population Quality through Hill Climbing Algorithms

In the basic cuckoo algorithm, the initial population is randomly selected, meaning that the initial population is of poor quality. To solve this problem, we replace the randomly selected initial population with a new population that has been optimized using the hill-climbing algorithm. The quality of the new population is superior to the quality of the randomly selected initial population used to optimize the cuckoo algorithm. We introduce the concept of adjacency, where input vectors that differ by one bit are considered to be adjacent. The climbing algorithm works by finding the vectors adjacent to the input vector, comparing them, saving the adjacent vector if it is better, and repeating the process until the iteration condition is met. The final better solution is found by taking the first $\textit{n}$ better solutions as the initial population according to the number of nests $\textit{n}$.

The algorithm for initializing population calculation of HC algorithm is presented in Fig. 10.

Fig. 10. Pseudo-code of the Hill Climbing (HC) algorithm initialization population.

3. Input Vector Segmentation

The input vector to the logic circuit is a sequence of consecutive binary codes. To facilitate the calculation, we convert the binary to decimal numbers, which are then used as input to the cuckoo algorithm. However, as the number of inputs to the circuit increases, any binary numbers that are too long cannot be converted to decimal numbers. We therefore propose a vector partitioning method to improve the cuckoo algorithm's search capability by dividing the longer binary numbers into several segments and reducing the vector space to be searched in each segment.

1.Determine the number of bits of the input vector $\textit{num}$;

2.Divide the input vector into equal segments, such that the number of bits in each segment is $\textit{c}$;

3.Convert each segment of the partitioned binary number to a decimal number;

4.Organize the converted decimal numbers into a mapping set $\textit{T}$;

5.Determine the upper and lower bounds as $[0,\sum _{j=0}^{c-1}2^{j}]$.

The conversion equations are presented in Eqs. (16)-(18):

Here, $\left\lceil \right\rceil $ represents rounding up, $\textit{b}$$_{i}$ stands for the $\textit{i}$th fragment, and Int($\textit{b}$$_{i}$) denotes mapping binary $\textit{b}$$_{i}$ to decimal.

In the vector partitioning method, $\textit{num}$ may not be an integer multiple of $\textit{c}$; this results in the last segment of the vector being of length $\textit{r}$(0<$\textit{r}$<$\textit{c}$), where the vector of length $\textit{r}$ is still converted to decimal, corresponding to its range bound of $[0,\sum _{j=0}^{r-1}2^{j}]$.

For example, suppose that the input vectors of circuit 1 and circuit 2 are '100010001111' (12 bits) and '10001000111' (11 bits) respectively, and that $\textit{c}$=3. In this case, the above analysis shows that the mapping set $\textit{T}$ of vector 1 is [4, 2, 1, 7], the mapping set $\textit{T}$ of vector 2 is [4, 2, 1, 3], the lower bound of circuit 1 is [0, 0, 0, 0] and the upper bound is [7, 7, 7, 7], while the lower bound of circuit 2 is [0, 0, 0, 0] and the upper bound is [7, 7, 7, 3].

Based on the above analysis, the IACS algorithm searches for sensitive vectors as shown in Fig. 11.

Fig. 11. Pseudo-code of the IACS algorithm.

1. COSEA vs. MC and CSA

In order to assess the accuracy of COSEA when calculating the failure probability of large circuits, a comparison with the MC method and the CSA method was conducted. The accuracy of the MC method is related to the number of simulations and requires a large number of simulation runs to be executed in order to obtain stable results. Here, we have 5*10e5 simulations for each vector using the MC method. The input vectors chosen for comparison are all zeros and all ones, and 85 series were chosen. The results of the tests are presented in Table 3.

The CSA method can only calculate the failure probability of a single output circuit. Here, the maximum number (10) of sub-circuits of C7552 are chosen (in the below, C7552\_i represents the $\textit{i}$th output containing the C7552 circuit). We here set FPG=10e-4 and the input vectors to full 0 and full 1. Table 4 provides the specific information for these ten experimental circuits. Fig. 12 plots the relative errors of COSEA and CSA against MC simulations.

As can be seen from Table 3, the average error is only 0.7318\%, while the time consumption of COSEA is several orders of magnitude higher than MC. Fig. 12 shows that the CSA algorithm has a maximum error of 118\% and an average error of 34\%; this is largely due to the fact that the CSA method does not take the effect of fanout reconvergence in the logic circuit into account, and is moreover less accurate. The COSEA algorithm has a maximum error of 1.59\% and an average error of 0.8429\%. Our experimental results show that the accuracy of the proposed COSEA algorithm is much higher than that of CSA.

Fig. 12. Failure probability relative error of COSEA and CSA compared with MC simulation of 10 sub-circuits of C7552.

2. Discussion of the Vector Partitioning Strategy Parameter c

We split the long input vector into several segments, then convert each segment to decimal in order to form a new input feature. The value of parameter $\textit{c}$ is too large, which is not conducive to the global search of the algorithm; moreover, due to computational performance limitations, the long binary data cannot be converted into decimal data, meaning that the parameter $\textit{c}$ cannot take too large a value. In summary, the value range of $\textit{c}$ is set from 1 to 5. Experimental results are shown in Table 5.

The results are summarized in Table 5, with the best values in bold and the worst values in italics for each row. As the data shows, the results are worse for $\textit{c}$ values of 1 and 5, and better for $\textit{c}$ values of 3 compared to the other values. The results improve when $\textit{c}$ is set to between 1 and 3, while they deteriorate when $\textit{c}$ is set from 3 to 5. In conclusion, setting $\textit{c}$ to 3 produces the best effect in this experiment.

3. Comparison Between the Method Proposed in This Paper and Other Algorithms

In this experiment, each algorithm was run 10 times independently when FPG=10e-4, and the maximum failure probability and running time of the algorithm run results were selected. From the above experimental analysis, we can determine that the number of IACS fixed evolution iterations is 500, the number of hill climbing algorithm iterations is 1000, the number of nests is 5, the upper and lower bounds of probability $\textit{P}$$_{a}$ are be 0.2 and 0.8, the upper and lower bounds of the scaling factor $\textit{r}$ are 0 and 1, and the upper and lower bounds of the power law exponent ${\beta}$ are 0.8 and 1.8. We measure the performance of the algorithm by the two indexes of maximum failure probability and time performance. The comparison between the cuckoo algorithm and other algorithms is analyzed below.

In our experiments, the parameters of the hill climbing algorithm, simulated annealing algorithm and genetic algorithm are a crucial element of algorithm effectiveness. For reasons related to time and efficiency, we set the algorithmic parameters as follows; The hill climbing algorithm is a simple local meritocratic method, using heuristics, which is essentially a gradient descent algorithm; the hill climbing algorithm is set to a fixed number of iterations, namely 10000; the simulated annealing algorithm is an optimization algorithm designed based on the concept of the Monte Carlo simulation, which is also essentially a greedy algorithm; the parameters of the simulated annealing algorithm are set to an initial temperature of 1000 and an end temperature of 10e-4. The genetic algorithm is a computational model of biological evolution that simulates the natural selection and genetic mechanism of Darwin's theory of biological evolution, and is widely used in various optimization problems; the parameters of the genetic algorithm are set to 500 for the initial population, 200 for the fixed number of iterations, 0.8 for the crossover rate and 0.1 for the mutation rate; the Randomized Algorithm (RA) randomly selects 100000 input vectors in each circuit, then selects the largest failure probability result among them. The results are presented in Table 6, with the best value marked in bold and the worst value in italics for each row, while "\textemdash{}" indicates that the search time was too long to calculate the results.

From the test results in Table 6, it can be seen that the cuckoo algorithm is significantly better at finding the maximum failure probability than the other four algorithms.

To compare the time performance of the algorithms, the parameters of the algorithm were designed as described above. The time of maximum failure probability was determined from Table 6 and shown in Table 7.

The main time consuming aspect of the algorithms is the calculation of the failure probability of the circuits with different input vectors, and the number of vectors calculated is mainly related to the number of iterations of the algorithm and the size of the population. The number of vectors needed to be calculated by the cuckoo algorithm is much lower than that of the three compared algorithms without losing accuracy. Assuming that the circuit failure probability time is calculated as $\textit{t}$($\textit{pf}$) for a single input vector, the time to optimize the population of the hill-climbing algorithm is $\textit{t}$($\textit{hc}$), the population size is $\textit{N}$, and the maximum number of iterations is $\textit{iter}$, then the complexity of the cuckoo algorithm is $\textit{O}$($\textit{iter}$*$\textit{N}$*$\textit{t}$($\textit{pf}$)+ $\textit{N*t(hc}$)).

Due to the limitations of the brute force search algorithm, we selected some small-scale circuits with less than 20 inputs for the test circuit. Moreover, due to the small size of the test circuit, we set the number of fixed iterations of the hill-climbing algorithm to the same number of nests and left the rest of the parameters unchanged.

The following table presents a comparison of the time performance of the two methods when finding the maximum failure probability of the tested circuit for FPG=10e-4. Table 8 shows the superiority of the cuckoo algorithm in terms of time efficiency for a larger number of circuit inputs.