Smita Krishnaswamy

George F Viamontes
email: gviamont@eecs.umich.edu

Igor L Markov
email: imarkov@eecs.umich.edu

John P Hayes
email: jhayes@eecs.umich.edu

Accurate Reliability Evaluation and Enhancement via Probabilistic Transfer Matrices

Soft errors are an increasingly serious problem for logic circuits. To estimate the effects of soft errors on such circuits, we develop a general computational framework based on probabilistic transfer matrices (PTMs). In particular, we apply them to evaluate circuit reliability in the presence of soft errors, which involves combining the PTMs of gates to form an overall circuit PTM. Information such as output probabilities, the overall probability of error, and signal observability can then be extracted from the circuit PTM. We employ algebraic decision diagrams (ADDs) to improve the efficiency of PTM operations. A particularly challenging technical problem, solved in our work, is to simultaneously extend tensor products and matrix multiplication in terms of ADDs to non-square matrices. Our PTM-based method enables accurate evaluation of reliability for moderately large circuits and can be extended by circuit partitioning. To demonstrate the power of the PTM approach, we apply it to several problems in fault-tolerant design and reliability improvement.

Introduction

Transient (probabilistic) errors have been a major source of system crashes for years. Traditional sources of transient errors include power supply instability and mismatches between components. As transistor sizes decrease, it becomes important to consider transient errors in logic circuits caused by cosmic rays [START_REF] Shivakumar | Modeling the Effect of Technology Trends on Soft Error Rate of Combinational Logic[END_REF]. When a primary particle strikes the atmosphere, neutrons and other secondary particles can be emitted. Neutrons can strike a critical node in a circuit, leaving behind an ionized track in silicon possibly causing a bit flip error to be latched. This necessitates methods to model and analyze circuits with probabilistic errors.

We model circuits at the logic level using a matrix representation for gates, an idea that goes back to [START_REF] Levin | Probability Analysis of Combination Systems and their Reliability[END_REF]. We use the form given in [START_REF] Patel | Evaluating Circuit Reliability Under Probabilistic Gate-Level Fault Models[END_REF] known as the probabilistic transfer matrix (PTM) formulation which represents parallel composition of gates with tensor products. Matrix representations of gates are illustrated in Figure 1, where the probability of each output value is explicit for each input combination.

Given individual gate error probabilities, we can compute output probabilities for the entire circuit and the overall probability of correctness, i.e., reliability of the circuit. This requires calculating the PTM for the whole circuit by combining gate PTMs. The process of combining gate PTMs implicitly takes into account signal dependencies between gates by considering the underlying joint and conditional probabilities within the circuit. Once the circuit PTM is calculated, accurate information about output probabilities, reliability and signal observabilities can be extracted from it.

Specific applications of interest include comparing the reliability of various circuits for a Boolean function and choosing critical components for partial duplication [START_REF] Mohanram | Cost-Effective Approach for Reducing Soft Error Failure Rate in Logic Circuits[END_REF]. The exactness of the calculations can be used to make small, incremental enhancements to a circuit. While approximate methods exist, higher precision may be required to evaluate sensitivities to changes in the circuit structure. Exact techniques are also needed to automate the evaluation of fault-tolerant constructs such as NAND-multiplexing and cascaded triple modular redundancy (TMR) [START_REF] Neumann | Probabilistic Logics & Synthesis of Reliable Organisms from Unreliable Components[END_REF].

The PTM evaluation method has several advantages over existing methods of soft error modeling. It performs simultaneous computation over all possible input combinations. It calculates the exact probabilities of errors, so no input vector sampling is involved. Also we do not have to explicitly map out signal dependencies in the network beyond specifying the gate PTMs. Larger circuits can be analyzed by applying this technique to sub-circuits in conjunction with event-driven simulations or path tracing. Having subcircuits precomputed as PTMs can speed up these algorithms.

A potential memory bottleneck in the PTM approach is alleviated through the use of ADDs (algebraic decision diagrams) [START_REF] Bahar | Algebraic Decision Diagrams and their Applications[END_REF] to compress PTMs (see Figure 1). The ADD is reduced in that identical nodes are not represented twice. Unnecessary decisions are always skipped, and the variable ordering interleaves row and column variables. For a gate with n inputs and m outputs, the straightforward representation of its PTM requires space O(2 n+m ). For a computer with 2GB memory, this limits the size of the circuit to 16 input/output signals in practice. However, the use of the ADD compression method significantly decreases the memory requirements in practice. PTM operations including information extraction are performed on the compressed form. Therefore, this method has complexity polynomial in the size of the ADD of a circuit and empirically scales to a width of 40+ signals. This facilitates exact analysis of circuit blocks used in regular circuit fabrics such as PLAs, FPGAs, memories and structured ASICs.

A major technical challenge in using ADDs for PTM representation is the lack of ADD algorithms for non-square matrices. Existing algorithms use zero-padding to make a matrix square. However, as we show, zero-padding gener-ally produces incorrect results for a key operation needed in PTM evaluation. We circumvent this difficulty by using permutation matrices and fanin gates.

The remainder of this paper is organized as follows. Section 2 outlines related work. Section 3 introduces the PTM framework and operations required to calculate circuit PTMs. Section 4 explains how ADDs are used to compress PTMs, outlines our PTM evaluation algorithm and presents empirical results. Section 5 examines several applications, while Section 6 discusses conclusions and future work.

Previous Work

Prior research on probabilistic analysis of logic circuits can be broadly classified into these areas: probabilistic behavior modeling, circuit simulation, fault-tolerant architectures and reliability improvement by adding redundancy. Work has been done in modeling dependencies between signals in the form of a Bayesian network. The relation between circuit signals and Markov random fields (undirected Bayesian networks) is described by [START_REF] Bahar | A Probabilistic Based Design Methodology for Nanoscale Computation[END_REF] in the context of probabilistic computation using neural networks. The conditional probability of outputs given input signals determines how errors are propagated through a circuit. Using this type of theoretical model it is possible to predict the probability of output error given the gate errors. However empirical results in [START_REF] Bahar | A Probabilistic Based Design Methodology for Nanoscale Computation[END_REF] are not presented for any significant circuits .

The work in [START_REF] Alexandrescu | New Methods for Evaluating the Impact of Single Event Transients in VDSM ICs[END_REF] describes a model for simulating the physical effects of soft errors on VLSI circuits. It uses an event-driven simulator with timing information to inject faults into individual gates. A transient error is latched depending on factors such as electrical, latching-window and logical masking. The functionality and connectivity of gates can make errors unobservable or influence the output error in various ways. The simulator injects faults for each test vector and determines whether the fault is latched despite the three basic sources of errors.

In [START_REF] Mohanram | Cost-Effective Approach for Reducing Soft Error Failure Rate in Logic Circuits[END_REF] the soft error or single event upset (SEU) susceptibility of gates is estimated. The soft error susceptibility of a gate g with respect to a latch l, is calculated by p error (g, l) = R SEU * P sense (g, l) * P latched (g, l). Here R SEU is the probability that an incident neutron can produce an SEU. P sense (g, l) is the probability that an input sensitizes a particular gate. P latched (g, l) is the probability that the error occurs during the latching window of the clock cycle. In order to assign an error susceptibility to an individual gate, a set of input vectors (selected from sampling runs of a circuit) are tested along with a fault at the particular gate. Each fault is propagated through critical path tracing to assess its affect on the output. This gives the approximate probability that an error appearing at a particular gate is latched.

The work in [START_REF] Bahar | A Probabilistic Based Design Methodology for Nanoscale Computation[END_REF] models probabilistic behavior of logic circuits by Bayesian networks, while our work relies on simpler modelling with matrices [START_REF] Levin | Probability Analysis of Combination Systems and their Reliability[END_REF][START_REF] Patel | Evaluating Circuit Reliability Under Probabilistic Gate-Level Fault Models[END_REF]. Our data structures enable further scalability than was shown in [START_REF] Bahar | A Probabilistic Based Design Methodology for Nanoscale Computation[END_REF].

Developments in nanotechnology have led to recent interest in fault-tolerant architectures [START_REF] Han | A System Architecture Solution for Unreliable Nanoelectronic Devices[END_REF]. In order to shrink devices reliably, techniques such as NAND multiplexing have been proposed. This technique involves analyzing the fault-tolerance of NAND multiplexing with Markov chains [START_REF] Han | A System Architecture Solution for Unreliable Nanoelectronic Devices[END_REF]. The analysis indicates that a low degree of redundancy may be sufficient for unreliable nanodevices. In our work, we wish to automate the analysis of fault-tolerant architectures using PTM evaluation. We do not require most of the assumptions used in analytical models and therefore can consider a wider range of probabilistic error patterns.

PTM Theory

We utilize the PTM model proposed in [START_REF] Patel | Evaluating Circuit Reliability Under Probabilistic Gate-Level Fault Models[END_REF] which uses tensor products as well as matrix multiplication for notational convenience. In [START_REF] Levin | Probability Analysis of Combination Systems and their Reliability[END_REF][START_REF] Patel | Evaluating Circuit Reliability Under Probabilistic Gate-Level Fault Models[END_REF] there was little discussion of implementation or applications of matrix based models of gate behavior. In this paper, we develop compuatational support for the PTM model and demonstrate practical results in applications.

The probabilistic behavior of a circuit can be described by a matrix A where the ( j, k)th entry represents the probability of output signals

O = o 0 , o 1 ,...o n having value k given that input signals I = i 0 , i 1 ...i m have value j. This is denoted p(O = k|I = j).
Here the row and column indices j and k are thought of as bit vectors whose entries represent the values of the signals that form the input and output. For convenience we omit the signal names and write this as p(k| j). For instance p(1, 1|1, 0) represents the probability that the two output variables (O 0 , O 1 ) have value (1, 1) given that the two input variables (I o , I 1 ) have value (1, 0). Probability p(1, 1|1, 0) can be alternately written as p(3|2).

Definition 1 A matrix M where the ( j, k)th entry represents the probability of output value k given input value j, i.e., p(k| j), is called a probabilistic transfer matrix (PTM).

A fault-free circuit has an ideal transfer matrix (ITM), i.e., the correct value of the output occurs with probability 1.

Circuit PTMs are calculated from gate PTMs by combining gate PTMs in a manner dictated by their connectivity. We now describe the matrix operations needed to construct a circuit PTM from the PTMs of its components.

For two gates g 1 and g 2 with PTMs M 1 and M 2 that are connected in series, the entry p(k| j) in the combined matrix represents the probability that g 2 produces output k in case g 1 is given input j. Therefore

p(k| j) = ∑ all l p(k|l)p(l| j)

This operation corresponds to the matrix product of the two component PTMs denoted M 1 M 2 . Now consider two gates g 1 and g 2 with PTMs M 1 and M 2 that are connected in parallel. We view indices k and j of the entry p(k| j) in the combined matrix as concatenated in binary from indices k 1 , k 2 and j 1 , j 2 of the two original PTMs. The value of p(k| j) is the joint probability that the input j 1 of gate g 1 causes value k 1 at the output and, at the same time, the input j 2 of gate g 2 causes k 2 at the output of

g 2 . Therefore p(k| j) = p(k 1 , k 2 | j 1 , j 2 ) = p(k 1 | j 1 )p(k 2 | j 2 ).
This operation is commonly known as the tensor product.

Definition 2 Given two matrices M 1 and M 2 with dimensions m × n and o × p respectively, the tensor product of M 1 and M 2 , denoted M 1 ⊗ M 2 is an mo × np matrix whose entries are given by p(k| j

) = p(k 1 | j 1 )p(k 2 | j 2 ).

We represent fanout behavior by explicit fanout gates.

A n-output fanout gate, denoted F n , copies an input signal to its n outputs. The ITM of a 2-output fanout gate is therefore given by 1 0 0 0 0 0 0 1 . To calculate the PTM of an acyclic combinational circuit with known gate PTMs, we combine PTMs of smaller components into larger PTMs using matrix products and tensor products. Additionally, explicit fanout gates and identity gates (buffers) may be required to reconcile dimensions before applying matrix products. This bottom-up evaluation procedure is illustrated next. Example 1 For the circuit shown in Figure 2, the 2-input NAND gates have the PTM NAND2 p given in Figure 1, and the PTM NAND3 p for the 3-input NAND gate is similar. An inverter with uniform error probability p has the PTM

NOT p = 1 -p p p 1 -p
. The circuit PTM is expressed by:

(F 2 ⊗F 2 ⊗I)(I ⊗I ⊗I ⊗NOT p ⊗I)(NAND2 p ⊗NAND2 p ⊗I)(NAND3 p ) (1)
where I refers to a 2 × 2 identity PTM. Each parenthesized term in Equation 1corresponds to a circuit level in Figure 2.

While other models for representing circuit errors exist, we use the PTM framework because of its generality and versatility. The PTM model can represent a wide variety of gate behavior including stuck-at faults and transient errors.

The fact that there are separate probabilities for each input and output and the fact that they are propagated simultaneously enable this generality. Also the PTM model can be easily extended in various ways.

PTM Representation and Evaluation

The size of a gate PTM with n inputs and m outputs is 2 n × 2 m . The memory needed to store PTMs can be reduced by compressing them and operating on the compressed forms. This section discusses compression by encoding the matrix into an algebraic decision diagram (ADD) and develops an efficient procedure for evaluating circuit PTMs.

Compressing Matrices with ADDs

In general, all entries of a 2 n × 2 m matrix can be distinct. However, matrices that represent circuits often have many identical rows. For example, in the PTM of an ideal n-input gate all but one of the rows are identical (set p = 0 in Figure 1). This suggests that circuit matrices can be significantly compressed.

In [START_REF] Bahar | Algebraic Decision Diagrams and their Applications[END_REF] the authors describe the encoding of a matrix using ADDs. Recall that a BDD is a directed acyclic graph representing f (x 0 , x 1 , x 2 ,...x n ) with root node x 0 . The subtree formed by the outgoing edge labeled 0 represents the cofactor f x 0 (x 1 ...x n ), and the subtree formed by the outgoing edge labeled 1 represents the cofactor f x 0 (x 1 ...x n ). Boolean constants are represented by terminal nodes. ADDs are variants of BDDs where terminal nodes can take on any real value. ADDs can also have multiple terminals.

In the ADD encoding of a matrix, the nodes represent decisions on row and column variables, and terminals represent values in matrix entries. The entries themselves are represented by paths starting from the root node and ending in a terminal. The same path can encode several entries if variables are skipped in a path. The input variables are queried in a pre-defined order, and this facilitates reductions by using the same node for identical sub-matrices. We use the QuIDDPro library [START_REF] Viamontes | Improving Gate-Level Simulation of Quantum Circuits[END_REF] to encode PTMs into ADDs and also to perform operations on PTMs. QuIDDPro includes the CUDD library and uses interleaved row and column variable ordering. This ordering facilitates fast tensor products and matrix multiplications -key operations in quantummechanical simulations for which QuIDDPro was designed.

Handling Non-Square Matrices

All matrix algorithms for ADDs that we are aware of assume square matrices, but can represent non-square matrices using zero padding [START_REF] Bahar | Algebraic Decision Diagrams and their Applications[END_REF][START_REF] Clarke | Multi-Terminal Binary Decision Diagrams and Hybrid Decision Diagrams[END_REF][START_REF] Viamontes | Improving Gate-Level Simulation of Quantum Circuits[END_REF]. A non-square matrix has fewer row variables than column variables or vice versa. However, any missing variable in a standard ADD is interpreted as marking replicated matrix entries. In other words, the entries of the matrix for both values of the variable are identical. To prevent this effect, missing rows or columns can be explicitly padded with zeros.

Matrix multiplication and addition are compatible with zero padding [START_REF] Bahar | Algebraic Decision Diagrams and their Applications[END_REF], however the tensor product is not. When two padded matrices A and B are tensored together, the result will have spurious rows of zeros which are carried over from the zero-padding of B.

Example 2

The equation below is an example of an ideal NOT gate tensored with an ideal zero-padded NAND gate.

0 1 1 0 ⊗    0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0    =           
0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0

           (NOT) (NAND2)
This illustrates the incorrect results obtained from tensoring padded matrices. Columns 3 and 4 erroneously consist entirely of zeros which are carried over from the zero-padding of the NAND matrix.

We develop two approaches to reconcile tensor products with zero-padding: dummy outputs and the permutation matrices. In the first approach, we add dummy outputs to a gate so as to equalize the number of inputs and outputs. This makes the gate PTM square thereby eliminating the problem with tensor products. Dummy outputs can be subsequently removed by multiplying the result by a faningate PTM, such as the one on the right for a 2-input 1-output fanin gate. In general, a

   1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0   
fanin gate is the transpose of the fanout gate introduced in Section 3. The fanin gate shown here is itself zero-padded and so in essence it moves desired outputs to the left corner of the matrix and the all-zero columns to the right. ITMs for fanin gates can be directly constructed as ADDs by first creating an appropriately-sized identity matrix and then abstracting column variables corresponding to the outputs we wish to retain, as explained below.

Definition 3 The abstraction of signals s and t from matrix M is matrix M 0 with entries p(k| j) = ∑ all x ∑ all y p(s = k, x|t = j, y). Here the p(k| j) is the sum over all possible values of the remaining input and output variables of M.

This operation generalizes the well-known existential abstraction of a single or multiple Boolean variables, but relies on arithmetic addition of matrix entries instead of the Boolean disjunction of cofactors. Its implementation in terms of ADDs is similar.

The alternative, permutation matrix method shifts spurious columns of zeros to the end of the tensor-product matrix. This can be expressed as multiplication by a permutation matrix acting as a column permutation, but such permutations have size up to 2 n (for n inputs) and are impractical if specified explicitly. Fortunately, we discovered a decomposition of zero-tracking permutation matrices into products and tensors of smaller matrices, which dramatically reduces the runtime.

Suppose we are calculating A ⊗ B for two matrices A and B with dimensions 2 p × 2 p and 2 q × 2 q after zero-padding. Spurious rows or columns of zeros will appear only if the actual dimensions of B are smaller. To this end, suppose that B has actual dimensions 2 n × 2 q , n < q. Then the zerotracking row permutation R is defined as R = r ⊗ I n where I n is a 2 n ×2 n identity and r is a 2 p+q-n ×2 p+q-n matrix where i-th row has a 1 in entry (i, i2 q-n mod 2 p+q-n ) and zeros elsewhere. The zero-tracking column permutation matrix is defined similarly; see matrix R in Example 3.

We now decompose zero-tracking row and column permutation matrices into products of permutation matrices of a special form. This special form is induced by permuting bits of row indices and column indices (these bits are known as row variables and column variables). Since there are exponentially fewer bits than rows and columns, these special-form matrices can be encoded much more compactly. Namely, for a matrix A consider a permutation σ( ) on the row variables. A row of A with index i 0 i 1 ...i n in binary is mapped to the row with index σ(i 0 )σ(i 1 ) ...σ(i n ) in binary. This defines a row variable permutation of A with respect to σ, which we denote as rperm(A, σ).

A key observation is that R can be decomposed into a product of row variable permutations tensored with identity matrices according to

R = Π q-1 k=n rperm(I p+q-k , σ k ) ⊗ I k (2)
where σ k (i) = (i -1) mod (p + qk)

Example 3 To address the problem noted in Example 2 we need the zero-tracking permutation matrix R, shown below.

          
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1

           =    1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1    ⊗ 1 0 0 1 (R) ( rperm) (I 1 )
Here, matrix rperm is a 4 × 4 identity (I 2 ) with its 1-bit column variables swapped (columns 01 and 10 are swapped).

Intuitively, for a circuit with n row variables r 0 , r 1 ...r n this corresponds to moving r n to r n-1 , r n-1 to r n-2 and so on. This method is efficient because the rperm(I p+q-k , σ k ) gates are row variable permutations on the identity matrix and I k is a k-variable identity matrix. For any n, I n = I n-1 ⊗ I 1 , and this recursive calculation of I n takes linear time in n [START_REF] Viamontes | Improving Gate-Level Simulation of Quantum Circuits[END_REF]. The row variable permutation also takes O(n) space because a matrix with 2 n rows has only n row variables. We note that decomposition of permutations into tensor products was studied in [START_REF] Egner | Decomposing a Permutation into a Conjugated Tensor Product[END_REF]. However, that work did not use variable permutations while we do not use conjugated tensor products.

Evaluation Procedure

PTM evaluation proceeds by level, from the primary outputs to the primary inputs; see Figure 3. First the primary outputs are stored in the list called CurrSigs. The gates that output these signals are tensored together to form the PTM for Cur-rLevel and are removed from CurrSigs. The CurrLevel PTM is then multiplied by the circuit PTM to form the new Cur-rCircuit PTM. This process continues until the CurrSigs are identical to the primary input signals and avoids tensoring gate PTMs together until necessary.

The intermediate level PTMs can be discarded after they are multiplied into the circuit PTM. This is important for the scalability of a circuit because tensoring two PTMs of size 2 n × 2 n and 2 m × 2 m produces a result with 2 n+m × 2 n+m entries. So suppose a level has n inputs and m outputs, then PTM is given by a 2 n × 2 m matrix. If these can be stored seperately as individual gates with one output per gate then the size is only m2 n . This is an exponential decrease in the space complexity. CurrSigs = primary out puts while (CurrSigs = primary inputs)

for j = 0:CurrSigs.size() In Figure 3 the function gate lookup(S) returns the PTM for the gate which is the source for signal S. If the source gate has multiple outputs then the desired signal is abstracted. If S is a primary input or needed in a future iteration (this is looked up in a table), the function returns the identity gate with S as the input thereby propagating the input to the previous level. At the termination of the procedure the current signals should include all primary inputs and only primary inputs.

CurrLevel = CurrLevel ⊗ gate lookup(CurrSigs[ j]) zero track(CurrLevel) remove redundancy(CurrLevel) end CurrCircuit = CurrCircuit * CurrLevel CurrSigs = CurrCircuit.inputs end
To improve the efficiency of PTM evaluation in practice, we introduce two additional ADD operations: one for removing redundancy in input signals and one for reliability calculation. In place of fanout gates, described in Section 3, we use an operation called redundancy removal. By removing each duplicated input signal, instead of adding a fanout gate, the PTM size is cut in half. Consider the case where inputs i 0 and i 2 are identical. In this case, all PTM rows whose indices have different bits 0 and 2 do not represent observable behavior and should be discarded, including row 6 = 110 2 . The redundancy removal is implemented as a variation of the abstraction operation (see Definition 3). In abstraction entries corresponding to the variables being eliminated are summed together; for redundancy removal, one of the two rows corresponding to the redundant signal is chosen. This process can be repeated for more redundancy.

The reliability operation determines the probability of correctness of a circuit by comparing the ITM with the PTM.

Definition 4

The reliability of a circuit c with PTM M and ITM J is given by Rel(c) = Σ J(i, j)=1 p( j|i)p(i). Recall that p( j|i) is found in the (i, j)th entry of M. In the case that all inputs are equally likely, Rel(g) = 1 2 n Σ J(i, j)=1 p( j|i) where n is the number of inputs to c.

Empirical Results

Results from calculation of circuit ITMs and circuit PTMs are shown in Table 1 for smaller LGSynth 91 and LGSynth 93 benchmarks with independent uniform distributions on all primary inputs. These simulations were run on a Linux workstation with a 3GHz Pentium 4 processor. In our experiments CPU time was limited to 24 hours. The runtimes and memory requirements are sensitive to the width of a circuit, i.e., the largest number of signals at any level. This determines the size of the tensor products and permutations/fanin gates for zero-tracking in tensor products. Empirically, circuits with widths of around 40 signals can be evaluated efficiently. Memory is not a bottleneck in our experiments. Table 1 gives the overall reliability of the circuits for gate error probabilities of 0.05 and also one-way gate errors of 0.05. In CMOS gates, an erroneous output value 0 is more likely than an erroneous value 1 because SEUs typically short-circuit power to ground. PTMs can encode this bias easily because the error probability depends on the input value. Relevant empirical results are given in the "one-way" column in Table 1. Note that circuits with a high output-toinput ratio, such as decod.blif, tend to magnify gate errors at fanout stems and therefore have lower reliability.

PTM evaluation for p = 0.05 takes more memory and runtime because less compression is possible. Ideal matrices have large blocks of 0s which makes for more identical submatrices to compress. When PTMs with errors are composed, there is greater variety in the matrix entries yielding less compression.

Applications

PTM evaluation has a wide range of applications. Below we describe two sample applications that we have implemented.

Gate Susceptibility

Replication is often used to increase the reliability of a circuit e.g. TMR (triple modular redundancy). In [START_REF] Mohanram | Cost-Effective Approach for Reducing Soft Error Failure Rate in Logic Circuits[END_REF] the authors show that in some circuit applications it may not be necessary to replicate the entire circuit. Only certain gates which are especially susceptible to error are chosen for replication and this increases the reliability of a circuit with relatively little area overhead. According to their heuristic, errors are injected into gates and then a sample of input vectors is applied in order to assess the probability of error at the primary outputs. Since the number of input vectors is exponential in the number of inputs to the circuit, this process can have high time complexity. Further, it can be inaccurate because a few inputs which are not included in the sampled set can lead to a drastic increase in the gate susceptibility.

PTMs can provide an accurate measure for the susceptibility of a gate using. The observability of a gate g in a circuit C can be thought of as the observability of its output signal. It is defined as the probability of output error given that gate g has error probability p on all inputs. This value is obtained by calculating Rel(C)/p where Rel(C) is reliability after insertion of an error into g. The gates with highest observability can be regarded as the most susceptible to probabilistic errors.

Since PTM calculations implicitly include all input vectors, sampling is unnecessary. Observability can be computed by introducing an appropriate error into gate PTMs and then evaluating the circuit PTM. This method can handle various error types, e.g., one-way errors. Table 2 illustrates gate susceptibility calculations in some of the standard benchmarks. The most susceptible gates are hardened by decreasing the probability of error by a factor of 10 while retaining the error probability of .05 in all other gates. For many circuits increasing the robustness of just a few gates can improve circuit reliability significantly. Note an exact calculation can can identify signals with zero observability which implies that the circuit contains redundancy. This cannot be done with an approximate method.

NAND-Multiplexing Analysis

A classic application of PTMs is the evaluation of faulttolerant architectures. The advent of nanotechnology has renewed interest in building reliable circuits from unreliable components because nanodevices are poorly controlled but available in large quantities, justifying computing techniques with high levels of redundancy, such as NANDmultiplexing and Cascading TMR which originated in [START_REF] Neumann | Probabilistic Logics & Synthesis of Reliable Organisms from Unreliable Components[END_REF].

In NAND-multiplexing, each unreliable signal is replicated N times. Then a set of NAND gates, each of which takes two of the N redundant signals as inputs, is used as a simple majority function. Some of these NAND gates may produce the wrong output due to an unfortunate combination of inputs. For instance, if 25% of the N replicated signals are 0 and 75% are 1, then 1 is most likely the correct value; however, some NAND gates may have both their inputs from the erroneous 25%. In order to compensate for this effect, the outputs of the NAND gates themselves are replicated and then fed into a "random permutation" gate. The outputs of the random permutation gates enter another series of NAND gates. These gates are likely to have fewer 0's since there are relatively few combinations which give the wrong value.

In order to calculate the reliability of N iterations of NAND-multiplexing, several types of errors need to be taken into account. These include

• Errors in the gates including the NAND gates.

• Errors due to combinations of inputs.

• Pseudo-randomness in the permutation which biases the combinations of inputs applied to NAND gates. In [START_REF] Han | A System Architecture Solution for Unreliable Nanoelectronic Devices[END_REF], this architecture is evaluated using analytical techniques. We can automate this type of analysis while relaxing some of the assumptions such as identical probabilities of error in gates, independence of input signals, and perfect randomness. Using PTM evaluation, we can input the specific probability of error and function of each of the gates, including the permutation gate analysis thereby automating the analysis. This will also take into account all the ways in which errors can cancel.

Table 3 shows results from a NAND-multiplexing instance with four replicated inputs, all of which have correct value 1 and are erroneous with probability 0.2. They are then passed through a number of NAND-multiplexing levels. Table 3 shows the probability that errors are corrected (signals are all returned to an identical 1 state). The multiplexing units themselves have probabilities of error for their constituent gates and also for the random-permutation unit. Table 3 shows that depending on the gate error probabilities, increasing the number of multiplexing stages can either increase or decrease the amount of error cancellation. This behavior is also not monotonic, thereby making analytical calculations difficult. Results for eight input replications show a similar trend.

Conclusion and Ongoing Work

In this paper we investigated the PTM framework for representing errors at the gate level, stressing its use in analyzing soft errors in logic. We provided an implementation for exact reliability calculations which used matrix operations to calculate circuit PTMs. The implementation, which compresses circuit-matrices using ADDs, shows that exact reliability measures can be calculated efficiently for larger circuits than previously thought. PTM evaluation has a wide variety of applications. Exact reliability calculations are useful for analyzing faulttolerant architectures and in calculating gate error susceptibility. Other applications include measuring the testability of signals under transient errors, and reliability-driven logic restructuring where parts of circuits are re-synthesized.

Our ongoing work promises to extend PTM evaluation to handle sequential logic blocks in addition to combinational logic blocks. This involves breaking circular dependencies in calculating conditional error probabilities. To increase the scalability of PTMs, partitioning based on logic cones, which is used in pseudo-exhaustive testing [START_REF] Srinivasan | An Effi cient Partitioning Strategy for Pseudo-Exhaustive Testing[END_REF], can be used to break larger circuits into small components. The PTM for each component is calculated, then a path tracing method can be used to compute the result for specific instantiations of a circuit. This can increase the accuracy and speed up approximate circuit reliability calculations.

Figure 1 :

 1 Figure 1: PTM (left) and ADD (right) representations of a NAND gate that produces an incorrect output with probability p for any given input. The labels r0, r1, and c1 in the ADD diagram represent row and column index variables.

Figure 2 :

 2 Figure 2: Circuit to illustrate the calculation of a PTM from gate PTMs. The junction dots represent fanout gates. The dotted lines separate levels of the circuit.

Figure 3 :

 3 Figure 3: Pseudo-code for our PTM evaluation method.

Figure 4 :

 4 Figure 4: Von Neumann's NAND-multiplexing scheme.

Table 1 :

 1 Performance of PTM evaluation and reliability of circuits with gate error p = 0.05.

			Characteristics		Performance, p = 0	Performance, p = .05	Reliability, p = .05
	Circuits gates inputs outputs width time(s) memory (MB) time(s) memory(MB) two-way one-way
	C17	6	5	2	5	.057	.003	.076	.003	.846	.880
	mux	6	21	1	23	6.13	3.16	6.13	2.51	.907	.939
	z4ml	8	7	4	20	1.74	1.54	2.22	1.59	.67	.817
	x2	12	10	7	23	18.8	7.91	35.3	9.03	.15	.099
	parity	15	16	1	23	.350	.129	.350	.144	.602	.731
	pcle	16	19	9	16	12.7	3.61	74.9	24.2	.573	.657
	decod	18	5	16	13	2.17	1.72	56.9	11.8	.000	.000
	cu	23	14	11	23	5.12	2.53	93.87	10.0	.461	.579
	pm1	24	27	17	27	24.6	6.95	7169	160	.375	.596
	9symml 44	9	1	37	362	612	1758	1200	.327	.534
	xor5	47	5	1	19	19.3	4.42	1337	57.3	.067	.071

Table 2 :

 2 Improvement in reliability after increasing robustness of the 3 and 5 most susceptible gates.

	Circuit Orig. Top 3 Improved Top 5 Improved
	C17	.864	.959	11.0 %	.980	13.4 %
	mux	.907	.974	7.39 %	.985	8.6 %
	parity	.603	.637	5.64 %	.666	10.4 %
	xor5	.047	.068	46.2 %	.070	50.5 %
	pm1	.375	.429	14.4 %	.469	25.1 %

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Acknowledgments. This work was supported by the National Science Foundation, the U.S. Department of Energy and the Gigascale Systems Research Center. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing official policies or endorsements of funding agencies. We also thank Ketan Patel of QualComm for helpful discussions.


Abdulkadir Yuvraj Singh Dhillon
email: yuvrajsd@ece.gatech.edu

Utku Diril

Abhijit Chatterjee

Soft-Error Tolerance Analysis and Optimization of Nanometer Circuits

Nanometer circuits are becoming increasingly susceptible to soft-errors due to alpha-particle and atmospheric neutron strikes as device scaling reduces node capacitances and supply/threshold voltage scaling reduces noise margins. It is becoming crucial to add softerror tolerance estimation and optimization to the design flow to handle the increasing susceptibility. The first part of this paper presents a tool for accurate soft-error tolerance analysis of nanometer circuits (ASERTA) that can be used to estimate the soft-error tolerance of nanometer circuits consisting of millions of gates. The tolerance estimates generated by the tool match SPICE generated estimates closely while taking orders of magnitude less computation time. The second part of the paper presents a tool for soft-error tolerance optimization of nanometer circuits (SERTOPT) using the tolerance estimates generated by ASERTA. The tool finds optimal sizes, channel lengths, supply voltages and threshold voltages to be assigned to gates in a combinational circuit such that the soft-error tolerance is increased while meeting the timing constraint. Experiments on ISCAS'85 benchmark circuits showed that soft-error rate of the optimized circuit decreased by as much as 47% with marginal increase in circuit delay.

Introduction

Technology scaling has been the major factor behind the increasing computing power of microprocessors. Technology scaling roughly leads to a doubling of clock frequencies every generation, a 30% decrease in node capacitances every generation and a 30% reduction in supply voltages to reduce power consumption. All these factors are leading to a drastic increase in soft-error susceptibility of combinational and memory circuits to alpha-particle and neutron strikes. Because of the reduced node capacitances, a smaller injected charge is needed to induce a glitch at a circuit node. Thus, low-energy particle strikes that earlier had no effect on a circuit can now cause soft-errors. Because of the reduced supply voltages, noise margins are reduced, which also increases the susceptibility to particle strikes. Increasing clock frequencies increase the probability of a soft-error getting latched. Furthermore, due to super-pipelining, the number of gates in pipeline stages have been reducing, which in turn reduces the electrical attenuation of glitches as they propagate to the latches.

Although these factors affect both memory and combinational elements, the overall soft-error rate of memories is not increased as much as combinational logic because memories are protected by techniques such as error-correcting codes (ECC). There has not been a need to protect combinational circuits because combinational circuits have a natural tendency to mask glitches due to three phenomena [START_REF] Dodd | Basic mechanisms and modeling of single-event upset in digital microelectronics[END_REF]. First, due to logical masking, a glitch might not propagate to a latch because of a gate on the path not being sensitized to facilitate glitch propagation. Second, due to electrical masking, a generated glitch might get attenuated because of the delays of the gates on the path to the output. Third, due to latching-window masking, a glitch that reaches the primary output might not still cause an error because of the latch not being open. The factors mentioned in the previous paragraph adversely affect all the above three factors in terms of soft-error tolerance. Due to decreasing number of gates in a pipeline stage, logical masking as well as electrical masking has been decreasing for new technology generations. Electrical masking has also been decreasing due to the reduction in node capacitances and supply voltages every generation. Furthermore, increasing clock frequencies have reduced the time window in which latches are not accepting data, thereby reducing latchingwindow masking also. Because of these factors, the softerror rate (SER) of combinational logic is expected to rise 9 orders of magnitude from 1992 to 2011, when it will equal the SER of unprotected memory elements [START_REF] Shivakumar | Modeling the effect of technology trends on the soft error rate of combinational logic[END_REF].

Generally, in mission-critical space applications combinational circuits are protected by using duplication/triplication and concurrent-error detection (CED) [START_REF] Nicolaidis | On-line testing for VLSI -a compendium of approaches[END_REF]. However, these methods have too high delay, area and power overheads to be used in commercial applications. Recently, low-cost methods for increasing soft-error tolerance of commodity applications using timeredundancy [START_REF] Nicolaidis | Time redundancy based soft-error tolerance to rescue nanometer technologies[END_REF] and partial duplication [START_REF] Mohanram | Cost-effective approach for reducing soft error failure rate in logic circuits[END_REF] have been proposed. However, these methods still add additional delay overhead to the original circuit due to the presence of the checker circuit. Also, these methods have system level overheads (such as pipeline flushes) when an error is detected, either to correct the error or to do the computation again.

This paper proposes a novel, zero delay-overhead method for increasing the soft-error tolerance of nanometer CMOS combinational logic circuits. Using an optimal assignment of supply voltages, threshold voltages, sizes and channel lengths to gates in ultra-deep submicron circuits, the electrical attenuation characteristics of the gates in the circuits are enhanced without incurring any delay overhead. Multi-supply voltage and multithreshold voltage designs are becoming increasingly common for low-power applications, however if these are infeasible, the method can still be used to just find optimal gate sizings for increased soft-error tolerance. This method can be used along with any of the traditional methods described above to greatly decrease the overhead of error detection and correction.

The paper is organized as follows. Section 2 describes characteristics of gates that affect the strike-induced glitches. Section 3 describes ASERTA, a tool for fast and accurate analysis of the soft-error tolerance of a circuit. Section 4 describes SERTOPT, a circuit optimization tool for enhancing the soft-error tolerance of circuits while meeting timing constraints. Section 5 gives experimental results. Section 6 concludes.

Glitch tolerance characteristics of individual gates

There are two characteristics of interest for a single gate in terms of soft error tolerance: glitch generation and glitch propagation. The glitch generation characteristics of a logic gate determine the shape and magnitude of the voltage glitch generated at the output of the gate due to a particle strike on the gate. The glitch propagation characteristics of a logic gate determine how the gate attenuates a glitch that is generated at some prior circuit node as it passes through the logic gate.

When a particle strikes a circuit node, the voltage magnitude of the corresponding glitch is dependent on the total capacitance of the node. The duration of the generated glitch is dependent on the delay of the gate that is driving the node. If the gate driving the node is fast, it will quickly discharge (or charge) the node back to its original value. Therefore, faster gates have better glitch generation characteristics in terms of the generated glitch width.

However, the behaviour is opposite for glitch propagation. Assuming a linear ramp at the output of the gate, for a gate propagation delay of d and glitch duration of w i at the gate input, glitch duration at the output of the gate, w o , can be approximated as follows:

( ) 0 2 2 2 o i o i i o i i w if w d w w d if d w d w w if w d = < = ⋅ - < < ⋅ = > ⋅ (1)
This model is similar to the glitch amplitude attenuation model used in [START_REF] Oman | A model for transient fault propagation in combinatorial logic[END_REF]. As seen from Equation 1, a slow gate will attenuate a glitch at its output more compared to a fast gate. Therefore, slow gates have better glitch attenuation characteristics. Figures 1 and2 show SPICE simulation results for generated glitch width and propagated glitch width, respectively, for an inverter for different values of gate size, gate channel length, gate supply voltage (V DD ) and gate threshold voltage (V th ). The SPICE models are for 70nm technology node [START_REF] Cao | New paradigm of predictive MOSFET and interconnect modeling for early circuit simulation[END_REF]. The minimum and maximum values of the variables are indicated on the x-axis. Size of 1 means a gate width of 100nm. It is clear that factors that slow down a gate (decrease in size, increase in channel length, reduction in V DD , and increase in V th ) increase generated glitch width but also increase the attenuation of propagating glitches. The insight gained from the SPICE simulation data is that only generated glitch width or propagated glitch width are not enough to characterize the "softness" of a gate as this might lead to erroneous conclusions. If only glitch propagation characteristics are considered as a measure of the "softness" of a gate (as in [START_REF] Zhao | A scalable soft spot analysis methodology for compound noise effects in nano-meter circuits[END_REF]), slowing down a gate would apparently always reduce the softness of the circuit; however, a slower gate will produce a bigger glitch at its output when it is subjected to a particle strike. Such a glitch can easily propagate to the output and cause an error. Slowing down all the gates at the primary outputs (POs) to attenuate all previous glitches (and hence to increase the soft-error tolerance of a circuit) is also not a viable solution as: (i) it is too expensive in terms of delay overhead, and (ii) it leads to very wide glitches being generated right at the latch inputs in the event of strikes at POs. Similarly, just speeding up all gates to "kill" the glitches generated at their outputs is also not viable as: (i) it would be too expensive in terms of area and power overheads, and (ii) a wide glitch generated due to a high energy strike would definitely propagate to the output because of little attenuation offered by the fast gates.

The conclusion drawn from the above discussion is that it is not possible to increase the soft-error tolerance of a circuit by just focussing on a few "soft" gates and trying to make them "hard". Gates hardened to resist glitch propagation cause generation of big glitches at their outputs and gates hardened to reduce generated glitch widths propagate glitches very easily. It is necessary to estimate the change in soft-error tolerance of the whole circuit after any optimization, as a "local" improvement of the softness of a gate might not lead to a "global" improvement in soft-error tolerance. The next section describes ASERTA, a tool for accurate estimation of the soft-error tolerance of a circuit.

Circuit soft-error tolerance analysis

ASERTA models a particle strike at a node as a current source injecting (or removing) a fixed amount of charge into (or from) that node. If the node is at low voltage, charge is injected into the node and if the node is at high voltage, charge is removed by the current source. The opposites of these two cases do can not cause a voltage glitch to be generated and are neglected. A SPICE look-up table is constructed for generated glitch width (due to charge injected at gate output) for different types of gates, fan-ins, sizes, channel lengths, V DD s, V th s and load capacitances. Although in reality the amount of charge injected (or removed) depends on the energy of the strike, for simplicity ASERTA assumes a fixed amount of injected charge. Future versions of ASERTA will have look-up tables for different amounts of injected charge. SPICE look-up tables are also constructed for delays, static energies, dynamic energies, output ramp and gate input capacitances for different types of gates, fan-ins, sizes, channel lengths, V DD s, V th s, input ramps and load capacitances. ASERTA uses linear-interpolation inside the look-up tables to compute output values for arbitrary values of input parameters. Using look-up tables allows ASERTA to have better accuracy than analytical models while still being much faster than SPICE. To estimate the soft-error tolerance of a circuit, ASERTA injects charge into every gate output, looks-up the generated glitch width from the table and then propagates the generated glitch to the primary outputs (POs) taking into account the effects of logical and electrical masking. The sum total of the widths of the glitches reaching the POs is taken as a measure of the "Unreliability" of the circuit. The following sub-sections describe how ASERTA models logical, electrical and latching-window masking.

Logical masking

Since actual signal values are not known, for every node ASERTA calculates the probability that there is at least one sensitized path from that node to a primary output. Calculation of the sensitization probability values from the input signal statistics is easy for circuits which do not have reconvergent fan-out. Sensitization probabilities for such circuits can be calculated as in [START_REF] Zhao | A scalable soft spot analysis methodology for compound noise effects in nano-meter circuits[END_REF]. However, finding the values for circuits with reconvergent fan-out is an NP-complete problem [START_REF] Najm | The complexity of fault detection in MOS VLSI circuits[END_REF]. ASERTA uses zero delay simulation of the circuit with 10000 random inputs applied (as in [START_REF] Mohanram | Cost-effective approach for reducing soft error failure rate in logic circuits[END_REF]) to compute the probability, P ij , that there is at least one path sensitized from output of gate i to primary output j. For primary output j, P jj is 1. The static probability, p i , of a node i being at logic 1 is obtained for all nodes using a commercially available tool, Synopsys Design Compiler, given a static probability of 0.5 at the primary inputs.

For all successor gates s of gate i, the probability that a glitch at i will be able to propagate through gate s to primary output j is calculated as follows:

¦ Ψ ∈ ⋅ ⋅ = k kj ik ij is isj P S P S π (2)
where Ȍ is the set of successors of gate i and S is is the probability that gate s is sensitized to gate i (i.e. all other inputs of gate s have non-controlling values). S is can be obtained by multiplying together the static probabilities of the other inputs being 1/0 for a AND/OR gate. Note that ʌ isj is not taken to be just S is . P sj since ʌ isj should have the property that ij k kj ikj P P = ⋅ ¦ Ψ ∈ π . Also note that ʌ isj is an approximation to the actual probability value since in circuits with reconvergent fan-out, the probability that gate s is sensitized to gate i conditions the probability of gate s having a path sensitized to a primary output.

The next sub-section describes the procedure used in ASERTA for computing the glitch widths at POs for charge injected at every gate output.

Electrical masking

As mentioned before, ASERTA computes the expected output glitch width, W ij , at primary output j for generated glitch width, w i , at gate i. To do this efficiently in one pass over the circuit, for every gate, the expected output glitch widths, WS ijk , for 10 sample glitch widths, ws k (k between 1 and 10) are computed.

The output glitch widths are computed for all gates in reverse topological order (i.e. from POs to PIs) as follows:

(i) Let current gate be i. (ii) If gate i is a primary output, set WS iik =ws k for all k.

Set WS ijk =0 for all other primary outputs j. Also, since gate is primary output, it will propagate generate glitch width, w i , directly. Hence, set W ii =w i and W ij =0 for all other primary outputs j. (iii) If gate i is not a primary output, for all sample glitch widths, ws k : For all successors s of gate i: Let d s be the delay of gate s looked up from the SPICE tables. Calculate the glitch width, wo sk , propagated to the output of gate s for input width of ws k using Equation 1.

For each primary output j, look up the expected output glitch width, WE sjk , for generated glitch width of wo sk from the table of expected output glitch widths for gate s, linearly interpolating if necessary.

Finally, Let At the end of this procedure, expected output glitch widths, W ij , at primary output j for generated glitch width, w i , for every gate i are known. The complexity of the procedure is O(V+E), where V is the number of gates and E is the number of circuit edges.

ijk isj sjk s W S W E π ∈ Ψ = ⋅ ¦ (iv) Compute W ij by
Lemma 1: For a very wide glitch ww i generated at output of gate i, the above procedure correctly computes the expected output glitch width at primary output j as ij i ij WW = ww P ⋅ , if it is assumed that ww i is one of the sample glitch widths used above (say sample 1). Proof: Since the generated glitch is very wide, it will pass through all gates on any path from i to j without attenuation. WS jj1 is correctly computed as ww i at primary output j. Assume that WS rj1 is correctly computed for all successor gates r of a gate p between i and j as ww i . P rj . Then, the expected width WS pj1 will be computed as:

Latching-window masking

A glitch must arrive within the setup and hold times of the latch at the primary output to be captured. Since the exact time of the particle strike is unknown, it can be assumed to be uniformly distributed within the clock cycle. The probability of a glitch being captured by a latch is directly proportional to its duration. Hence, by summing up the expected output glitch widths, W ij , for all primary outputs j, the total contribution of gate i to the circuit unreliability is obtained. However, this ignores the fact that the size, Z i of a gate plays an important role in determining the particle flux incident on the gate. Hence, the actual contribution of gate i to circuit unreliability is:

¦ ⋅ = j ij i i W Z U (3)
The total unreliability of the circuit is:

¦ = i i U U (4)
Figure 3 shows the unreliability numbers, U i , for the gates in ISCAS'85 benchmark circuit "c432" calculated by ASERTA plotted along with values calculated by SPICE for 70nm technology node. In SPICE, the unreliability was computed by applying 50 random input vectors, injecting charge at every gate output i and using the width of the glitch at primary output j as W ij in Equation 3. Only the nodes that were at most five levels deep from the POs are plotted. It is seen that there is close matching. The correlation between the two series was computed to be 0.96. For the ISCAS'85 benchmark circuits, an average correlation of 0.9 was obtained.

The next section describes SERTOPT, a tool that uses the unreliability estimates generated by ASERTA to optimize nanometer circuits for increased soft-error tolerance by enhancing the electrical masking characteristics of gates in the circuits.

Circuit soft-error tolerance optimization

SERTOPT uses a delay assignment variation method to minimize a cost function that is a weighted sum of circuit unreliability, circuit power consumption and circuit size. A designer can easily change the optimization constraints by changing the ratio of the weights.

The delay assignment variation method is based on the technique in [START_REF] Dhillon | Sizing CMOS circuits for increased transient error tolerance[END_REF] [START_REF] Dhillon | Algorithm for achieving minimum energy consumption in cmos circuits using multiple supply and threshold voltages at the module level[END_REF]. The circuit topology for a circuit with N gates and P paths from PIs to POs is represented with a binary topology matrix, T, defined as follows: In other words, ∆ has to lie in the nullspace of T to guarantee that the timing constraints are met in every iteration.

To find the circuit parameters (gate sizes, lengths, V DD s, V th s) that are needed to match a delay assignment, SERTOPT traverses the circuit from POs to PIs in reverse topological order. The capacitive loads of the gates at the POs are known since these loads do not change. From these loads and the delay assignments for the PO gates, the best matching sizes, lengths, V DD s, V th s available in the SPICE library that yield delays closest to the assigned delays are found and assigned to the PO gates. Once the parameters of these gates have been set, the capacitive loads offered by these gates to their predecessors can be found. The whole process is then repeated till the PIs are reached. The only constraint during the matching process is that only V DD values greater than or equal to successor V DD values are allowed to be used for a gate. This ensures that there is no low V DD gate driving a high V DD gate and eliminates the need for level-shifters.

Once the circuit parameters have been determined, SERTOPT calculates the circuit unreliability (U) using ASERTA and the circuit delay (T), total energy (E = dynamic energy + static energy) and area (A) using SPICE libraries. Note that although ∆ has been chosen from the nullspace of T, the timing constraint might still be exceeded slightly because of the finite size library used for matching the delays. Hence, timing can also be included in the cost. The cost is computed as:

1 2 3 4 init init init init U T E A C=W +W +W +W U T E A ⋅ ⋅ ⋅ ⋅ (5)
where U init , T init , E init and A init are the unreliability, delay, energy and area of the initial circuit. The cost is minimized by using Sequential Quadratic Programming (SQP) to search for the optimal delay assignment giving lowest cost. However, simulated annealing, genetic algorithms or some other optimization algorithm can also be used.

Experimental results

First, gate sizes were obtained for ISCAS'85 benchmark circuits by optimizing for speed using Synopsys Design Compiler. The gate sizes were then used with SPICE 70nm models [START_REF] Cao | New paradigm of predictive MOSFET and interconnect modeling for early circuit simulation[END_REF] to compute the delays of the circuits for the 70nm technology. All the gates had a transistor channel length of 70nm, V DD of 1V and V th of 0.2V. The unreliability of the baseline circuits was estimated using ASERTA.

Then, SERTOPT was used to determine new gate sizes, channel lengths, V DD s and V th s for the circuits that

Table 1. Optimization Results

would minimize unreliability while meeting the delay constraint of the baseline circuits. The results of the optimization are reported in Table 1. The second and third columns give the V DD and V th values used in the optimized circuits. Note that the values and numbers of V DD s and V th s to be used is a design variable. We report results for values that gave fair reduction in unreliability without compromising too much on power consumption. The maximum gate size used was the same as that for the baseline circuits. The gate channel lengths that SERTOPT was allowed to use for the optimization were 70nm, 100nm, 150nm, 250nm and 300nm. The fourth, fifth and sixth columns give the ratio of the area, energy consumption and delay of the optimized circuits to the corresponding values for the baseline circuits. As mentioned before, the delay constraint can sometimes be exceeded due to the finite sized library used. The seventh column gives the decrease in unreliability (as defined by Equation 4) of the optimized circuits. The first subcolumn gives the decrease calculated by ASERTA. The second and third sub-columns give the decrease in unreliability calculated by applying 50 random input vectors to the baseline and optimized circuits and measuring the average glitch width at the outputs using ASERTA and SPICE. They indicate the matching between ASERTA and SPICE for a small set of input vectors. Note that these numbers are different from the number in the previous column because 50 inputs do not capture the input statistics very well. The last 2 circuits were too big to be simulated by SPICE so we just report the unreliability reduction calculated by ASERTA. The unreliability of "c499" could not be reduced. The reason is that "c499" is an error-correcting circuit for single-bit errors and ASERTA also models unreliability by injecting single-bit errors. A modelling scheme that takes into account simultaneous multiple-error injections could still be used with SERTOPT to reduce unreliability in the face of such errors.

ASERTA and SERTOPT have been implemented in MATLAB. They take 15 second and 20 minutes to run on "c432" and 200 seconds and 27 hrs to run on "c7552" respectively † .

Conclusion

This paper presented tools for the analysis and optimization of the soft-error tolerance of nanometer combinational circuits. The analysis tool, ASERTA, is able to accurately calculate (with average correlation of 0.9 with SPICE) the "unreliability" of circuits in orders of magnitude less computation time than SPICE. The optimization tool, SERTOPT, is able to reduce the unreliability of circuits by up to 47% by using a library with multiple V DD s, V th s, gate sizes and gate lengths.

Decrease in Unreliability

Fig 2 .Fig 1 .

 21 Fig 2. Glitch propagation characteristics of an inverter for an input glitch of duration 50ps.

  the vector of path delays. The delay assignments of the gates are varied in an optimization iteration by adding ∆ such that T 0 ⋅ ∆ = . This choice of ∆ lets the delays be varied without varying the path delay vector as shown below: = ⋅ + ⋅∆ =

Fig 3 .

 3 Fig 3. Unreliability values obtained by SPICE and ASERTA for nodes in c432.

  looking up the table of expected output glitch widths, WS ijk , computed in step (iii), for a generated glitch width of w i , again linearly interpolating if necessary. Now process the next gate.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

† MATLAB is an interpreted language, hence slow. There is a 10X speed-up expected by migrating to C. Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

This research was supported by NSF Information Technology Research Contract CCR 022-0259.


Osama Neiroukh

Xiaoyu Song

Improving the Process-Variation Tolerance of Digital Circuits Using Gate Sizing and Statistical Techniques *

A new approach for enhancing the process-variation tolerance of digital circuits is described. We extend recent advances in statistical timing analysis into an optimization framework. Our objective is to reduce the performance variance of a technology-mapped circuit where delays across elements are represented by random variables which capture the manufacturing variations. We introduce the notion of statistical critical paths, which account for both means and variances of performance variation. An optimization engine is used to size gates with a goal of reducing the timing variance along the statistical critical paths. We apply a pair of nested statistical analysis methods deploying a slower more accurate approach for tracking statistical critical paths and a fast engine for evaluation of gate size assignments. We derive a new approximation for the max operation on random variables which is deployed for the faster inner engine. Circuit optimization is carried out using a gain-based algorithm that terminates when constraints are satisfied or no further improvements can be made. We show optimization results that demonstrate an average of 72% reduction in performance variation at the expense of average 20% increase in design area.

1. Introduction 1 Recent advances in VLSI have continued to shrink device geometries at a steady rate in accordance with Moore's Law. However, this advancement has also been accompanied by increasing variations in the performance of fabricated circuits. Numerous factors have contributed to this trend including clock PLL jitter, noise, PV model inaccuracies, and manufacturing variations. Nevertheless, it is often desirable to manufacture ASICs on advanced technology nodes due to substantial increase in available device count, reduction in power consumption, higher yields and lower costs due to the larger 300mm wafers.

Researchers have recently focused on statistical analysis approaches in an attempt to grapple with these sources of performance variations. Statistical timing analysis models delay arcs as random variables and propagate timing constraints using probability distribution functions (pdfs). While a substantial focus has gone into the analysis aspect of this problem [START_REF]ICCAD-2003[END_REF][START_REF]TAU Workshop[END_REF], recent research into statistical optimization of circuits has been surprisingly diminutive.

Circuit optimization was done in [START_REF] Jacobs | Gate sizing using a statistical delay model[END_REF] by using LANCELOT [START_REF] Conn | Lancelot: A FORTRAN package for large-scale nonlinear optimization (Release A)[END_REF] but had severe limitation on circuit size and used unrealistic delay models. A concept of criticality of gates was used in [START_REF] Hashimoto | A performance optimization method by gate sizing using statistical static timing analysis[END_REF] but did not address the variance of the timing path delays. A transistor level approach was presented in [START_REF] Bai | Uncertainty-aware circuit optimization[END_REF].

Several yield-specific techniques were presented in [7].

In this paper we present a unique approach that identifies worst negative statistical slack (WNSS) paths analogous to traditional worst negative slack (WNS) paths. Our method also provides flexibility for optimization objective function by assigning weights that enable user-driven tradeoffs between mean and variance of circuit performance.

The remainder of this paper is organized as follows:

x We present background on proposed research x We formulate the problem of performance variability reduction in presence of statistical delays x We derive a method for tracing the worst negative statistical slack (WNSS) path in a circuit x We derive and demonstrate efficacy of a new approximation for quick calculation of the mean and variance of the maximum of random variables x We present a robust gain-based sizing approach that handles a weighted sum of means and variances of delays x Experimental results are presented and analyzed

Related work 2.1 Gate sizing

Gate sizing has been studied extensively in the literature. It is typically performed after technology mapping during logic synthesis and repeated throughout the design process. The aim of gate sizing is to assign sizes to gates in a circuit such that a performance objective function is satisfied.

where Although sizing approaches relying on convex assumptions or analytical delay models have been proposed, more recent approaches tend to tackle the problem using greedy heuristics. According to [START_REF] Coudert | Gate sizing for constrained delay/power/area optimization[END_REF], accurate delay models make gate sizing a non-linear, non-convex, constrained, discrete optimization problem. Most greedy gate sizing algorithms share several common elements [START_REF] Coudert | Gate sizing for constrained delay/power/area optimization[END_REF][START_REF] Fishburn | LATTIS: An iterative speedup heuristic for mapped logic[END_REF][START_REF] Chen | An exact algorithm for low power library-specific gate re-sizing[END_REF][START_REF] Murgai | Technology-based transformations[END_REF]. The critical path, sometimes referred to as the Worst Negative Slack (WNS) path, is usually targeted for optimization. We note that the WNS path can change as the optimization proceeds so the path being evaluated for resizing must be updated regularly during sizing iterations. The algorithms can be run in a constrained mode where delay for example is optimized first then area is recovered as far as possible without violating a delay constraint.

Statistical static timing analysis

The focus on use of statistical approaches in timing analysis is relatively new. Pioneering works in this field appeared in [START_REF] Devades | Statistical timing analysis of combinational circuits[END_REF][START_REF] Jyu | Statistical timing optimization of combinational logic circuits[END_REF][START_REF] Brawhear | Predicting circuit performances using circuit-level statistical timing analysis[END_REF]. However, in the past few years statistical techniques for timing analysis of circuits have received tremendous focus with representative works including [START_REF] Liou | Fast statistical timing analysis by probabilistic event propagation[END_REF][START_REF] Agarwal | Statistical timing analysis using bounds and selective enumeration[END_REF][START_REF] Chang | Statistical Timing Analysis Considering Spatial Correlations using a Single Pert-like Transerval[END_REF]. Static timing analysis relies on two operations for propagating timing through a network, sum and max. Performing these calculations on pdfs is more expensive computationally than their counterparts in the deterministic case. Moreover, the correlation between two pdfs needs be taken into account for accurate calculations.

Fig. 1 gives a plot of at different optimization points. The original line represents a pdf obtained by optimizing a circuit with a goal of minimizing the mean of the longest delay in the circuit. Such a circuit will typically exhibit the widest spread in performance due to high usage of smaller devices which exhibit more manufacturing variability. Depending on target application of circuit, such a performance variance around the center can represent undesirable uncertainty that should be minimized. In [START_REF] Rich | Reducing the frequency gap between ASIC and custom designs: A custom perspective[END_REF], reduction of uncertainty was shown to be a key strategy for designing leading edge industrial designs. Decreasing variance can increase the overall yield of a design. An example of this is optimization 1 in Fig. 1 which yields more functional units at period T relative to the original design. However, our technique is quite general and is not limited to yield maximization. Decreasing performance variance is also desirable on several other accounts even if it means relaxing the original timing targets. For example, circuits on the original curve to the left of "X" in Fig. 1 below will exhibit undesirable variance in power consumption due to both dynamic and leakage power variations. These variations in turn contribute uncertainties in thermal dissipation and reliability verification. The effects of such performance variations can adversely product qualification and time-to-market. In such instances, the 2 O RV nd optimization point shown below becomes desirable due to better tolerance to manufacturing variations. Our research is aimed at providing designers with a statistically aware gate sizing methodology that allows arbitrary tradeoffs between mean and variance of .

O RV

Problem formulation and motivation

The starting point for our problem is a technology mapped digital circuit. Without loss of generality, this paper focuses on combinational circuits. We ignore interconnect delay though accounting for them can be readily accommodated. In fact, we postulate that our algorithm can help overcome the inherent interconnect uncertainty during pre-layout convergence by treating interconnect delays as random variables.

Our method uses discrete probability distribution functions (pdfs) throughout. A discrete pdf for random variable X is defined as one or more points where . The mean and variance of a discrete random variable are given by ) ( (

x X P f ) x i X i X i i X x f x x f x 2 2 ¦ ¦ P V P
We assume that every gate delay in the circuit is represented by a normally distributed random variable which is consistent with the literature. Arrival times are propagated throughout the circuit as pdfs. We define the unconstrained timing variance minimization problem for a circuit as Our full statistical analysis engine is based on [START_REF] Liou | Fast statistical timing analysis by probabilistic event propagation[END_REF]. This approach discretizes pdfs at a user controlled sampling rate. We used 10-15 samples per pdf as a reasonable tradeoff between accuracy and speed. The operations sum and max are performed on discrete pdfs using shifting, scaling, and min/max reduction. In addition to propagating pdfs, we also calculate the mean and variance at every node and store these values for use in the fast timing engine (FASSTA). This component in our algorithm can be updated as needed to track the latest emerging research in statistical timing analysis and represents the outer loop for our iterations.

FASSTA

X T Figure 1. Circuit Output Delay PDF

Statistical analysis methods such as FULLSSTA are expensive and impractical for use alone in an optimization setting. This section presents new approximations for fast statistical static timing analysis (FASSTA). This allows us to quickly evaluate costs of new gate assignments in subcircuits in the body of the optimization algorithm. The two operations needed in static timing analysis are sum and max. The FASSTA engine relies on the point values for means and variances of delays calculated in FULLSSTA rather than the complete discrete pdf representations.

Proposed approach

We studied several deterministic sizing techniques to evaluate their fitness as a basis for statistical sizing. Our preference for accurate gate delay models steered us away from methods [START_REF] Menezes | A sequential quadratic programming approach to concurrent gate and wire sizing[END_REF][START_REF] Chen | Fast and exact simultaneous gate and wire sizing by lagrangian relaxation[END_REF][START_REF] Tennakoon | Gate sizing using Lagrangian relaxation combined with a fast gradient-based pre-processing step[END_REF], which require convex analytical expressions for gate delays. Such models not adequately capture the nonlinearities in current and foreseeable DSM technologies where manufacturing variations are prevalent. Our proposed approach is shown in Fig. 2. It builds on the deterministic algorithms presented in [START_REF] Coudert | Gate sizing for constrained delay/power/area optimization[END_REF][START_REF] Murgai | Technology-based transformations[END_REF]. We show next how we deal with new challenges that arise when timing constraints are represented by random variables.

We start with two normally distributed independent random variables A and B with expected values To calculate the max, we shall expand on the formulation in [START_REF] Clark | The greatest of a finite set of random variables[END_REF]. We use the following notation:

2 2 2 1 x e x S M dt t x x ³ f ) M 2 a 2 A V + 2 B V a B A P P D
The first two moments of max(A,B) are given by 1

X D M D P D P a B A
) )

(1)

D M P P D V P D V P X a B A B B A A ) ) 2 2 2 2 2 (2)
The variance of max(A,B) is given by

2 1 2 ) , max( X X B A Var (3)
These formulae cannot be evaluated directly because the integrals do not have analytical expressions and are expensive to compute. We show next how they can be avoided altogether. We reformulate the integral:

dt t x x ³ f ) M dt t dt t x x ³ ³ ) f 0 0 M M 1 • © § ) 2 2 1 2 1 x erf x
where erf denotes the error function. To calculate the error function, we use the following quadratic approximation [START_REF] Weisstein | CRC Concise encyclopedia of mathematics[END_REF] We also note that the error function is odd:

) ( ) ( x erf x erf
These formulae give us a quick method to approximate the error function for any value. We substitute this approximation in (1) and ( 2). We note that if

6 . 2 t a B A P P D (5) then 0 , 0 , 1 | | ) | ) D M D D
Our justification for taking the partial derivatives with respect to the means of the delays is that the variances have a random component not under our direct control. and we have

V P | |

We observed that in the vast majority cases, one of ( 5) or (6) would apply obviating need for any calculation for max, while in other cases the approximations above provide quick estimates. These formulae assume independence of random variables which does not always hold. However, this approach emphasizes speed while retaining a reasonable degree of accuracy for small subcircuits. We stress that this approach is only used for the inner loop of the optimizations, while the outer loop relies on the more accurate discrete pdfs manipulation approach that can track correlations due to reconvergent paths using Principal Component Analysis [START_REF] Chang | Statistical Timing Analysis Considering Spatial Correlations using a Single Pert-like Transerval[END_REF] or other methods as long as runtime is managed appropriately.

Statistical critical path identification

As was pointed out in section 2.1, circuit optimization engines typically focus their effort on the critical or WNS path to improve the performance of the circuit. This section describes how we extend this concept to trace the Worst Negative Statistical Slack (WNSS) path in a circuit.

Consider a circuit consisting of 6 gates such as the one shown in Fig. 3. The first number in the parenthesis represents the statistical mean of delay for that arc while the second one represents the standard variation. We wish to determine the critical path with the biggest contribution to the variance at the output of node X. We note that, unlike the deterministic case, one cannot simply pick the input with the higher mean or variance to determine which input is most responsible for the variance at the output. This is due to the non-linearity of the statistical max operation where all inputs contribute to the output max.

We proceed to solve this problem by considering the sensitivity of the variance at the output of a node with respect to the inputs as follows. Starting from a given gate, we compare its inputs pair-wise. If either of ( 5) or ( 6) are satisfied, then we pick the input with the higher mean as clearly having the dominant influence on the output of this gate. If neither of these equations is satisfied, we compare One approach to obtaining these sensitivities is to differentiate (3) directly. We found the resultant expressions to be complex and would require expensive floating-point computations. Instead, we chose to use an approximation for differentiation as follows. Rewriting ) , , , (

) , max( B A B A B A f Var V V P P
We use a forward finite-difference formula to approximate the partial derivative: P is indicated by g. We also note that it is impossible in general to determine g accurately as the relationship between P and V along a given path is governed by a combination of gate performance variations inversely proportional to their dimensions as well unsystematic random variations that are unpredictable. For purposes of ranking inputs, the following linear approximation linking these two was found to be adequate:

h f g h f Var B A B A B A B A A B A ) , , , ( ) , , , ( ) , max( V V
g P V ' | ' | c
We used values for c equal to those assumed to relate mean delay through a gate to its variance.

Subcircuit extraction and ranking

For every gate being evaluated for resizing, our algorithm extracts a subcircuit around this gate based on a user-controlled depth. We have found that using two levels of transitive fanins and fanouts is sufficiently accurate without being too costly to evaluate. For every available size for this gate, we use FASSTA to calculate mean and variance of delay at the outputs of this subcircuit. In order to rank the the relative merits of gate sizing in this subcircuit quickly, we use the following cost function. For all outputs of the subcircuit O 1 ..O n , we calculate a weighted sum of mean and standard variation:

Cost(O i ) = i P + ( 7 ) i OV
where O is a user-specified weight multiplier that ranks relative importance of minimizing standard variation against mean of delay. By choosing higher values for O , the user can place more emphasis on variance reduction. We provide more analysis on effect of varying O in the conclusions section at the end of the paper. The cost of the subcircuit is given by the maximum of Cost(O i ) across all outputs. We then pick the gate size that minimizes subcircuit cost across all gate sizes for candidate gate.

Experimental results

The proposed approach was implemented in Java and run on an Intel PC running at 2.53 GHz. We tested the algorithm on various circuits from the ISCAS benchmarks and various sized ALU circuits. The circuits were first synthesized using Design Compiler [START_REF]Design Compiler[END_REF] using an industrial 90nm lookup-table based standard cell library with 6-8 sizes per gate type. In line with other researchers, we added variations to the gate delays based on [START_REF] Cong | Challenges and opportunities for design innovations in nanometer technologies[END_REF][START_REF] Nassif | Delay variability: sources, impact, and trends[END_REF]. Two variations components were added to the gate delays: one proportional to delay through gate and another random source corresponding to unsystematic manufacturing variations.

Table 1 shows the results of our optimization. The ratio of V to P obtained by optimizing for mean delay is shown in the first column entitled original. We then ran our algorithm at various values for O (7). Results are shown for optimization under two different values for O , 3 and 9. We observed that increasing O any further could not yield further reduction in variance in general though the highest value for O was different for different circuits. This is due to the unsystematic variations whose effects cannot be eliminated. Fig. 4 below shows a plot of P against V for various values of O for circuit C432.

Several observations can be made from these results. Our algorithm consistently reduces the standard variation while increasing mean delay and area. This behavior is expected since our algorithm favors bigger gate sizes that reduce the variance of delay across them. The algorithm's focus on minimizing variance also causes it to upsize gates near the outputs to reduce the overall variance at circuit's output. This is done even if that path does not have the highest mean delay which is in contrast to a worst mean-delay optimizer which would not upsize such gates. This increases overall delay due to higher loading slowing predecessor gates.

Another important observation is that the number of gates along a timing path is inversely proportional to the variance along that path and the ability to optimize it away. Paths with a shorter number of gates tend to be more susceptible to variations. The smaller ALU circuits exhibit significant variations as a percentage of their mean. Our algorithm can reduce this variation substantially but at a higher increase in area. On the other hand, circuit C6288 which is a 16x16 bit multiplier has the longest depth of any of the circuits in the table. We note that it has the lowest improvement due to its already low V to P ratio.

Concluding Remarks

We introduced a new concept of a worst negative statistical slack path and derived a procedure for tracing and optimizing such paths. In the process, we also derived a new approximation for the max operation on random variables for use in circuit optimization. Our approach allows us to steer the optimization process towards different mean-variance goals. The significance of this work is that it can be used during design cycle to increase tolerance for the effects of manufacturing variations by trading off circuit delay and area requirements for reduced timing variance with user controlled weights. We demonstrated fidelity of our approach on ISCAS benchmarks with consistent variance reduction in exchange for moderate increases in area and low increases in mean delays.

  Figure 2. Overview of StatisticalGreedy

Figure 3 .

 3 Figure 3. Tracing worst negative statistical slack (WNSS) path. Numbers in parenthesis are ( w , P ) of arrival time. The shaded nodes indicate the WNSS using our method.

Fig. 4 :

 4 Fig. 4: Normalized Mean-Std deviation Plot for C432

  which is accurate to two decimal places

	2 1	erf	© §	2 x	1 •	|	°°® 0 0 . . 49 50 1 . x 0	(	4	.	4	x	)	2	2 0 .	d	x x x	t d	6 6 . . 2 2 2 . 2

Table 1 . Results of our approach on ISCAS Benchmarks

 1

	O	3
		O	6

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

O

* This research was supported by Intel Corporation.