NDA Non-Disclosure Agreement. 47 NMI Non-Maskable Interrupt. 53

TFIT Transistor FIT. A tool developed by IROC Technologies to estimate the SER sensitivity of individual cells. These can be memory cells, sequential cells or combinatorial cells. 93

i Acknowledgments Undertaking a PhD has been an exciting and challenging experience and I have learned a great deal about the topic matter as well as about scientific research in general. I am indebted to numerous people; more than I can fully acknowledge here.

First and foremost, I wish to thank my thesis supervisor, Michael Nicoloaidis, who welcomed me warmly when I arrived at the TIMA laboratory. Over the last three years, his guidance and insight have been invaluable. He has also taught me a great deal about the importance of protecting intellectual property.

I wish to express my thanks to Jean Arlat for his contributions to the RIIF workshop and to him, Luis Entrena and Dominique Houzet for serving on my thesis committee and providing their feedback.

To Dan Alexandrescu, CEO of iROC Technologies, I am beholden for his encouragement, for granting me time to write my thesis and for helping me to obtain numerous reference materials. To the entire staff at iROC Technologies, I wish to express my thanks for providing a warm environment where I have learned immensely from experts in the field of soft errors. I especially thank Enrico Costenaro with whom I collaborated on the work on the analysis of transient errors and Jocelyne Baudoin who helped manage the time I spent working on my thesis.

The first year of my thesis was spent at the TIMA Laboratory and I wish to express my thanks to Dominique Borrione, director of the laboratory. Mounir Benabdenbi helped me with my course work and Lorena Anghel was of great assistance with the organization of the RIIF Workshop. Laurence Ben Tito and Anne-Laure Fourneret-Itie helped me navigate the administrative procedures.

Furthermore, I wish to express my thanks to Shi-Jie Wen of Cisco Systems who encouraged many parts of the work in this thesis. His help in gaining access to actual designs for the portion of the work on selective flip-flop mitigation and his support for extending the work on combinatorial SET analysis were extremely valuable.

The work related to RIIF was highly collaborative. I would like to thank Oliver Bringmann who was the co-chair of the RIIF workshop as well as Pedro Reviriego Vasallo and Alfonso Sánchez Macián of the University of Nebrija who helped develop the parser and test cases for RIIF.

The work on Bloom Filters was a collaboration with Salvatore Potarelli and Marco Ottavi at the University of Rome "Tor Vergata". The technical interaction was very enjoyable and I wish to acknowledge the Median Cost Action which covered my travel expenses for several trips.

In addition, I would like to thank Li Chen and Hao Xie of the University of Saskatchewan who lead the implementation of the work on redundant logic.

Last, but certainly not least, I express my sincere thanks to my wife Anne and my children Zoë and Ben who have been extremely patient while I have spent many hours in front of the computer. Anne's precious help in proofreading my manuscript is sincerely appreciated.

Chapter 1

Introduction to Soft Errors and System Reliability

Electronic systems based on complex silicon devices play an increasingly critical role in our lives and it is extremely important that they function reliably. Faults induced by the effects of natural radiation are a significant source of failure and there exists a vast body of research devoted to analyzing and mitigating these effects. Much of the academic work has focussed on achieving accurate results when analyzing relatively small circuits. In industry, the size of circuits continues to grow and integrated circuits with over ten million flip-flops are very common.

The focus of this thesis is on soft error analysis and mitigation techniques for very large circuits. The main contributions consist of improvements in fault-injection simulations, a technique to identify critical flip-flops in large circuits, a technique to perform a high-level analysis of the effect of Single Event Transients (SETs) and a new modeling language, called Reliability Information Interchange Format (RIIF), which can be used to model the propagation of faults through complex circuits.

The manuscript is organized as follows. The first chapter provides an overview of soft error effects, including a review of their causes, a brief history of their discovery and a discussion of the basic masking mechanisms. Chapter 2 presents an overview and comparison of the numerous hardened latch and flip-flop designs which have been proposed to mitigate faults. This review includes cells targeted to mitigate both radiation-induced faults and timing faults. Although timing faults are fundamentally different from radiation induced faults, the choice to include both was intentional as there are many similarities between the techniques to mitigate transients and those to mitigate timing faults. It is well known that the vast majority of faults do not propagate and in chapter 3, a review of the existing techniques to analyze fault propagation is presented. The second half of chapter 3 presents a case study of the analysis of soft error effects for three large design blocks from a network processor.

In chapter 4, a technique to identify functionally critical flip-flops in large designs is presented. The technique is based on grouping together similar flip-flops in order to reduce the complexity of the analysis. The results of applying these techniques to the design blocks studied in chapter 3 are then presented. Chapter 5 describes a hierarchical approach for quickly computing the effect of SETs in large combinatorial circuits. Then, in chapter 6, a new modeling language called RIIF is described. This language is designed to provide a standard means to specify the rate of occurrence of faults as well as how faults propagate in complex circuits. This is followed, in chapter 7, by the conclusions and a discussion of plans for future work.

In addition to the main topics of the thesis, additional work performed in the context of three collaborative projects is presented in the appendices. In appendix A and appendix C, two different approaches to protect a special type of memory, Ternary Content Addressable Memorys (TCAMs), against errors are described. The first technique is based on using a parallel data-structure called a Bloom Filter. The second technique is based on using a Built-In Current Sensor (BICS) to detect the actual radiation induced fault when it occurs. In appendix B,a na l g o r i t h mt o synthesize approximate logic functions that can mask both transient and permanent faults is presented.

Overall, the work presented in this thesis seeks to apply abstraction in order to enable coarser grained and hierarchical analysis of the effect of faults. The initial work in chapter 4 shows how large sets of flip-flops can be grouped together in order to simplify the process of selective mitigation. In chapter 5, the focus shifts to SETs and a hierarchical analysis approach is presented which can be applied at the Register Transfer Language (RTL) or even architectural level. Finally, the RIIF modeling language provides a framework for combining failure models for smaller blocks into complete models for chips or even systems. Taken together, these techniques facilitate the analysis and mitigation of radiation induced faults in complex integrated circuits.

Soft Error Effects

Sources of Natural Radiation

In terrestrial applications, the three main sources of energetic particles that induce soft error effects are alpha particles, high-energy neutrons and thermal neutrons [Baumann 2005]. New work has recently highlighted an emerging risk of upsets induced directly by muons [Sierawski 2011[START_REF] Ibe | Fault-based reliable design-on-upper-bound of electronic systems for terrestrial radiation including muons, electrons, protons and low energy neutrons[END_REF]] and potentially in the future from electrons and gamma rays. In space applications, the radiative environment is much harsher and soft errors can be induced directly by high energy cosmic particles including protons and heavy nuclei.

Alpha Particles

An alpha particle has the structure of a helium atom nucleus, consisting of two protons and two neutrons. Alpha particles typically have energies in the range of [4][5][6][7][8][9] MeV and travel at low speeds (5% of the speed of light). Alpha particles are created through the decay of unstable isotopes such as 238 U, 232 Th, 210 Po, 210 Pb and 212 Pb. Trace amounts of these isotopes may be found in the packaging materials that are in close contact to the die, typically in the solder bumps, ceramic package materials or aluminum interconnect. These particles do not penetrate very deeply into materials; in silicon, the penetration of a 10MeV alpha particle is less than 100µm, thus only the materials that are in direct contact with the die are of concern [Baumann 2005].

It has become common practice to select Ultra Low Alpha (ULA) packaging materials for integrated circuits used in applications where reliability is a concern. ULA implies an alpha emission rate below 0.002α/cm 2 /hour. Undesirable elements, such as uranium, can be chemically removed. However, removing specific isotopes (e.g. 210 Pb) of an element such as lead is challenging and this is sometimes achieved by 'aging' the materials in order to allow sufficient time for the unstable isotopes to decay. The fact that the unstable isotopes decay over time, makes the measurement of alpha emissivity very challenging. For example, 210 Pb has lower alpha emissivity than 210 Po, one of the by-products on its decay chain. This evolution of alpha emissivity over time makes it difficult to implement consistent quality controls.

Cosmic Radiation

The second source of soft errors results from the interactions between cosmic rays and the atmosphere. In outer space, there are primary cosmic rays consisting of [START_REF] Heald | How Cosmic Rays Cause Computer Down Time[END_REF]]:

• 92% protons

• 6% alpha particles • 1% heavy nuclei
In the outer atmosphere, these particles have a flux of approximately 1600 m 2 /s and energies up to 100 GeV [Ziegler 1996]. These particles interact with the earth's atmosphere producing complex chains of secondary and tertiary particles. At ground level, the flux of particles consists of muons, protons, neutrons and pions [START_REF] Ziegler | [END_REF]]. The typical spectrum of neutron flux at ground level as well as at some accelerated test facilities is reproduced from [JEDEC 2006]i nfi g u r e1.1.I t i s i m p o r t a n t t o note that this spectrum varies significantly based on altitude and location due to the effect of the earth's magnetic field. A comprehensive study of the neutron spectrum at ground level was performed by [START_REF][END_REF], Gordon 2005] and for higher altitudes by [Normand 1996].

The earth's atmosphere blocks most cosmic particles, however, when these particles strike atoms in the atmosphere, they produce high-energy neutrons which can travel freely through air. When these high-energy neutrons strike the nucleus of a silicon atom, they can produce either elastic or inelastic collisions. Most elastic collisions result in only a small amount of energy being released. Inelastic collisions result in a fission reaction and in two or more recoil fragments which can include protons, neutrons, ions and heavy recoil nuclei. This can result in the deposition of a large amount of charge in a small volume [Seifert 2010a]. Figure 1.2 illustrate the collision of a neutron with a silicon nuclei and lists some of the more frequently occurring by-products. A full study of neutron-silicon interactions is presented in [START_REF] Wrobel | [END_REF]]. Although the majority of soft error effects are induced by interactions between neutrons and silicon, the interactions with other atoms including oxygen in Silicon on Insulator (SOI) technologies must be taken into account [Wrobel 2003].

Thermal Neutrons

The third source of terrestrial soft errors is from low energy neutrons (E n 1MeV ). These are neutrons that have lost kinetic energy until they reach a state where they are in thermal equilibrium with their environment. Certain nuclear fission reactions become much more probable with these low-energy neutrons and result in reactions yielding charged particles. The most common such reaction is with the 10 B isotope of boron. Boron is used as a p-type dopant and is also used as an implant in insulating layers formed of Boron Doped Phosphosilicate Glass (BPSG). The natural distribution of the two boron isotopes is 11 B (80.1%) and 10 B (19.9%), however, BPSG typically has a higher fraction of 10 B. When a low energy neutron strikes 10 B, it results in an alpha particle (1.47 MeV) and a lithium nucleus (equation 1.1). Both of these cause charge to be deposited and can induce soft errors [Baumann 2005].

10 B + n -→ 14 Li + α

(1.1)

Recent work on thermal neutrons [Wen 2010a, Wen 2010b[START_REF] Zhang | [END_REF][START_REF] Fang | [END_REF]] has shown that even when BPSG is not used in the fabrication process, devices can have a sensitivity to thermal neutrons. These works also highlight the challenges in consistently testing the sensitivity to thermal neutrons due to the lack of a standard test procedure analogous to [JEDEC 2006].

Brief History of Soft Error Effects

A proper understanding of the effects of radiation on electronics started to emerge in the late 1970's and the history is well outlined in [Ziegler 1996]and [Nicolaidis 2011]. As early as the 1950's, there had been anecdotal reports of problems with electronic equipment during nuclear weapons tests. The electronics used in early satellites were known to be unreliable and redundancy thus error detection had become common practice. The first publication about the effect of space radiation on satellites was published in [START_REF] Binder | [END_REF]].

In the following year, the first study was published on ground-level soft error effects observed in a Cray-1 computer and this paper was recently republished in [Normand 2010]. In the following two years, errors due to alpha-particles in DRAMs were studied by Intel [START_REF] May | AN e wP h y s i c a lM e c h a n i s m for Soft Errors in Dynamic Memories[END_REF][START_REF] May | Alpha-particle-induced soft errors in dynamic memories[END_REF]. It is interesting to note that these first observations were on DRAM cells. Today, however, due to technology scaling, DRAM cells are among the most robust types of storage cells.

At about the same time, Ziegler (IBM) and Lanford (Yale) realized that nuclear interactions between cosmic rays and silicon materials might cause secondary particles and trigger errors. These results were first published in [START_REF] Ziegler | [END_REF]]. Later in 1979, Kolasinski (Aerospace Corporation) performed the first heavy-ion tests on electronics at Lawrence Berkeley Laboratory using iron and kyrpton ions [START_REF] Kolasinski | [END_REF]] to simulate the radiative conditions experienced by satellites. In the same year, [START_REF] Guenzer | [END_REF]] published the first results from accelerated neutron testing and provided an improved analysis of the interactions between neutrons and silicon.

Already in 1979, researchers at IBM had started to develop a framework for modeling the diffusion and collection of charge induced by energetic particles. By 1983, IBM had started to publish on SEMM, their internal Monte Carlo tool for simulating radiation effects [Sai-Halasz 1983]. The second generation of this tool (SEMM2) is still in use by IBM today [Tang 2004]. About this time, there were high-profile incidents at Intel and at IBM [Ziegler 1996] where radioactive contamination of production materials resulted in memory devices with excessively high soft error rates. The publicity associated with these events increased the awareness of soft error phenomena both in industry and in the academic community.

In 1983, the first evidence of soft errors produced by muons and pions was published [Dicello 1983]. Around the same time, internal studies by IBM showed that Soft Error Rate (SER) was dependent on altitude. These included studies using special test-boards, as well as the analysis of the logs of systems installed at high-altitude locations such as Denver, Colorado [Ziegler 1996]. In the following years, IBM continued to test 25 different chips under neutron and proton beams and studied the effect of voltage, temperature, angle of incidence, process variation and logic-state. The comprehensive results were compiled in an internal IBM report published in 1986.

In the early 1990's IBM developed the first ion micro beam which made it possible to study the effect of charge deposition at exact positions on a chip with an accuracy of approximately 1 micron [START_REF] Geppert | [END_REF][START_REF] Heidel | [END_REF]. A few years later, Baumann demonstrated the first evidence of soft errors induced by thermal neutrons [START_REF] Baumann | [END_REF].

From this brief outline of the early research into soft error effects, it can be seen that all of the fundamental concepts related to the physics of soft error phenomena as well as the accelerated test methodologies that are used today have been well understood for nearly twenty years. Currently, the outstanding challenges relate to computing the net effect of soft errors in very large circuits which is the focus of the research in this thesis.

Taxonomy of Radiation Effects

When an ionizing particle strikes a circuit, it can produce many different effects depending on the type of circuit, the energy of the particle and the nature of the strike. This section provides an overview of the different effects.

SEUs

A Single Event Upset (SEU) is an inversion in the stored value in a flip-flop, latch or memory cell as the result of radiation induced charge. In this work, the term SEU refers only to an upset that directly occurs in a sequential cell. Note that in some work [START_REF] Shuler | [END_REF]], the authors also use the term SEU to refer to a SET that has been sampled in a flip-flop or latch.

Chapter 1. Introduction

SETs

A Single Event Transient (SET) occurs when a radioactive event causes charge to be deposited around a combinatorial logic gate producing a current pulse. For this pulse to become an error, it must propagate through the combinatorial network and then arrive at the input of a sequential element just at the sampling point. Due to the low probability of a pulse being captured, the majority of SETs do not propagate and until recently it has been assumed that for terrestrial applications, the overall SER contribution from SETs is very minor.

SEFI

Single Event Functional Interrupt (SEFI) is a broad term that refers to the loss of some major functionality in a complex device due to a radiation induced event. Typically, a SEFI is caused by a SEU in critical control logic. The effect of a SEFI is detectable and it does not result in permanent damage. A SEFI can be recovered by resetting the device.

SEL

A Single Event Latchup (SEL) event occurs when the charge deposited by an energetic particle causes the parasitic thyristor (PNPN), formed by the P-drain, N-well, P-well and N-drain, to be triggered, creating a short circuit path from power to ground (see figure 1.3 and 1.4). Once latchup has occurred, the only way to restore normal operation is to cut the power to the circuit. Typically, a SEL event results in increased current consumption and if this current is too high, the effect can be destructive. A destructive SEL is sometimes referred to as a Single Event Burnout (SEB). Decreasing operating voltage makes modern process technologies less sensitive and even immune to SEL.

SEGR

Single Event Gate Rupture (SEGR) occurs in MOS power transistors. When the additional carriers produced by the strike of an energetic particle are accelerated through the electric field, the field is increased, potentially causing the dielectric to breakdown and the transistor to be permanently damaged. SEGR is of growing concern as power transistors are being increasingly used in electric vehicles.

Clock Network Faults

Energetic particles can affect the operation of circuitry in the clock distribution network of a chip. This includes PLLs [START_REF] Sondon | [END_REF][START_REF] Fujita | [END_REF] as well as in the buffers in the clock tree [Seifert 2005]. In the latter work, the authors identify two main effects due to upsets in the clock network : radiation-induced jitter and radiation-induced race. Jitter occurs if an upset causes the clock edge to move forward causing a setup violation. A race condition occurs if an upset causes a latch Thyristor Formed by PNPN Junction that is closed to become open allowing data to 'race' through to the next stage. The authors find that the contribution of radiation induced race can be on the order of 20% of the total effective SER for a full chip. Simulation based analysis of the clock network in smaller designs [START_REF] Ebrahimi | [END_REF] shows the contribution from the clock network to be much smaller. In both works, however, it is reported that the SER contribution of the clock network is dominated by the buffers at the leaf level of the clock tree.

Power Supplies

Beyond standard digital logic, radiation effects can perturb the operation of peripheral circuits including switching power supplies. In [START_REF] Ren | [END_REF]], it is shown that the band-gap reference circuit in a particular commercial power "brick" is very sensitive to radiation. Under alpha, neutron and laser radiation upsets to the band-gap reference would cause the power monitor to trigger a shut-down of the power supply. When performing a system-level SER analysis, it is important to consider the potential risk due to the power supplies, especially since these faults typically produce high-impact outages.

Dose Effects

Electronics used in space or highly radioactive environments may be degraded due to the cumulative effect of exposure to radiation. The first mechanism is due to the Total Ionizing Dose (TID) which results from charge being trapped in the oxide layer and causing a shift in the switching characteristics of the transistor. A second mechanism is caused by the displacement of silicon atoms in the regular crystalline Figure 1.7: Simulated Results of TDR in Latches and Flip-Flops [START_REF] Seifert | [END_REF] is proportional to the ratio of the induced pulse width to the clock period as shown in equation 1.3. Extensive test results have shown that at higher frequencies, the TDR factor increases and the effect of SETs is more severe [START_REF] Nguyen | [END_REF][START_REF] Gill | [END_REF], Mahatme 2011].

TDR SET = w=maxP W w=minP W w dw T clk (1.3)
In figure 1.9, all of the possible alignments of a pulse compared to the sampling clock edge are shown, including both the case when the pulse is longer and when it is shorter than the setup-hold window. For the cases of PW > t setup + t hold ,t h e overlaping width, OW , is defined to be the extent that the pulse lies within the setuphold window. As with the SEU analysis, the error capture probability is assumed to be proportional to the ratio of OW to the full setup-hold window: OW t hold +tsetup .F o r the cases of PW < t setup +t hold , the two violation cases are considered together, and the error latching probability is also taken to be linear with the overlapping width ratio as before. Since the arrival time of SETs is uniform over time, both cases can be averaged over a full clock period. The calulated error probablity for each case is shown in table 1.1 and it turns out that the overall error latching probability across a full clock cycle is given by P W /T clk .

It is important to note that in this analysis, the pulse width of interest is that at the input to the sampling flip-flop. The shape of a radiation induced pulse may be %&'( !" #$ Figure 1.9: SET Pulse Alignment Cases distorted as it propagates through a combinatorial network. This effect is referred to as Propagation Induced Pulse Broadening (PIPB) and has been extensively studied in [START_REF] Cavrois | [END_REF]].

Electrical Masking

Digital logic is based on signals crossing a switching threshold to discriminate between zero and one values. When a weak SET is created, the voltage on the affected node may not cause the switching threshold to be crossed and the fault is thus masked electrically. Due to their inherent capacitance and limited slew rate, all digital logic gates inherently act as low pass filters, blocking very narrow pulses. This ability to block narrow SETs is referred to as Electrical De-Rating (EDR). The effect of EDR is best analyzed using SPICE simulations where the true, post-layout capacitances have been included, however, in practice this is not feasible for large circuits. EDR can also be modelled in digital simulators by associating an inertial delay to individual gates.

Functional Masking

It is quite possible for a SEU or SET to significantly change the state sequence of a circuit, however, due to the function of the actual application, the effect may be benign. Some obvious examples, would be an SEU that causes a single pixel in a video stream to be modified or that causes a very small delay in the delivery of packet data, as shown in figure 1.10. If we consider the example of a delayed packet, on the output pins of the device, at the vector level, the output sequences may appear highly divergent, despite the fact that the functional effect is very minor.

The additional de-rating provided by the function of the circuit is referred to as Functional De-Rating (FDR). As will be seen in the case study presented in section 3.2, this de-rating is significant and must not be ignored. Unlike the other de-ratings, FDR does require an understanding of the application and requires that the effects of errors be divided into classes based on their system-level severity.

!"#$%&' !"#$%&( !"#$%&) *+,-!.&/$01$2"$ !"#$%&' !"#$%&( !"#$%&) /34&355$"% 6

Computing the Overall SER

Given that the intrinsic technology FIT rates and de-rating factors are available, then a full chip FIT rate can be calculated based on the following equations:

SER chip = SER sequential + SER combo + SER clock (1.4) SER sequential = i∈FF FIT SEU i • LDR(i) • TDR(i) (1.5) SER combo = i∈G w=max w=min FIT SET i (w) • TDR i (w) • LDR i • EDR i (w)dw (1.6)
In the above equations, FIT SEU i is the intrinsic rate of occurrence of SEUs for the given flip-flop instance and FIT SET i (w) is the rate of occurrence of SETs of width w in the instance of the specific combinatorial gate. The above equations raised [START_REF] Ibe | Fault-based reliable design-on-upper-bound of electronic systems for terrestrial radiation including muons, electrons, protons and low energy neutrons[END_REF], Sierawski 2011], however, it does not appear that these particles significantly contribute to the SER at current technology nodes. At some point, the critical charge may become sufficiently small that this will change.

Independent of the per-cell SER, certain broad trends can be identified:

1. The total number of integrated circuits is growing driven by larger data centers, the Internet of Things (IoT) and the proliferation of mobile devices.

2. The total number of transistors per integrated circuits continues to grow (Moore's Law [Moore 1965]).

3. Computers are increasingly used in critical applications such as autonomous driving and in medical devices.

4. Operating frequencies are roughly constant and performance increases are coming from additional parallelism (more gates).

5. The terrestrial radiative environment (≈ 14 n/cm 2 /hr) remains constant although the sensitivity of devices to different particles (e.g. alpha, muons, protons) may evolve.

To illustrate the impact of the growing number of transistors per die, in figure 1.12, we plot the transistor counts for recent processors based on data gathered by [Wikipedia 2014]. Based on the assumption that 90% of the die area of a processor is covered by cache-memory and that there are approximately 16 transistors in a latch, we can estimate the latch counts. From this graph, it appears that designs with a hundred million latches will appear by 2016. Even if the per-cell SER rate continues to decrease, given the broad trends (points 1..3 identified above), it appears that radiation-induced soft errors will continue to be a concern.

Combinatorial SER

The SER threat from memories has been well known for over fourty years and can be effectively mitigated using Error Correcting Code (ECC). As will be seen in chapter 2, there exist many cell designs for SER hardened flip-flops and using techniques such as those presented in chapter 4, it is possible to selectively harden flip-flop and thus manage the sequential component of SER.

Historically, the contribution of soft errors from combinatorial logic has been quite small, due to the numerous de-rating factors that were outlined in section 1.3. However, given that memory and flip-flop SER can be well managed, the relative contribution of combinatorial SER is increasing, as illustrated in figure 1.13.I na well known paper [START_REF] Shivakumar | [END_REF], it was predicted that by the 50nm technology node, combinatorial SER would equal sequential SER. It appears that this prediction was over-stated, however, more recent research [Mahatme 2011[START_REF] Ebrahimi | [END_REF] continues to highlight this trend. During accelerated radiation testing of complex devices such as processors, it is difficult to differentiate the sequential and combinatorial components. Due to the complexity of the de-rating analysis for combinatorial SER, it is also difficult to accurately compute the combinatorial contribution at the full-chip level. The methodology presented in chapter 5 describes a new approach to estimate the contribution of SETs.

This chapter has provided a brief overview of the causes of soft errors and the basic mechanisms that prevent their propagation. Assuming ECC is used to protect memories, then the largest contribution to the overall SER comes from flip-flops or latches. In the following chapter, we present a survey of the SER hardened sequentials that have been proposed in the literature.

Introduction

In the early 1990s, due to the growing awareness of soft errors, there was interest in developing flip-flop and latch designs that were resistant to radiation-induced upsets. Some of the earliest designs were the HIT cell [START_REF] Bessot | [END_REF]]andtheDual-Interlocked storage Cell (DICE) [Calin 1996]. The DICE circuit remains the basis for many hardened flip-flops. Layout optimizations have been proposed and are typically applied in industrial DICE implementations to provide increased robustness (e.g. LEAP-DICE [START_REF] Lee | [END_REF]).

In space applications, SETs have historically been a concern and there is evidence that they are also becoming an issue in high-end terrestrial applications [Mahatme 2011[START_REF] Evans | [END_REF]. Mitigation of SETs is generally more complex than protection against SEUs and there exist many techniques including those presented in appendix B. Although transients occur in combinatorial logic, one way to to protect against them is to detect when they reach the input of a flip-flop or latch. Special sequential cells can be designed to detect, and even filter, transients when seen their at their data input.

Starting around the year 2000, there was interest in sequential cells that could detect timing violations. Multiple factors drove this new interest, including emerging concerns about the parametric degradation of logic cells through aging effects such as Negative Bias Temperature Inversion (NBTI) and Hot Carrier Injection (HCI) which result in increased transistor switching delays. In industry, the standard approach to mitigate aging effects had been to introduce additional margins into the timing budget. Smaller process geometries fundamentally result in increased variation as the switching characteristics of transistors are now affected by defects consisting of only a few atoms. Furthermore, the increase in the number of transistors per die, requires tighter statistical variance in order to achieve a given level of yield or reliability per die. These factors are driving up the timing margins that must be budgeted to guarantee devices operate correctly over their entire lifetime. It is, however, possible to design sequential cells that can detect timing violations.

By detecting timing violations during operation, the voltage or frequency can be dynamically adjusted to enable correct circuit operation without the need for large, up-front timing margins.

Finally, as concerns about power dissipation have continued to grow, the ability to use Dynamic Voltage Scaling (DVS) to reduce voltage, and benefit from the quadratic reduction in active power, has become attractive. The use of sequential cells that can detect timing violations allows DVS to dynamically adapt to the circuit's operating conditions including the workload.

To summarize, sequential cells can be designed to mitigate three classes of faults:

(i) SEUs -Upsets that directly affect the storage node or the clock nodes within the storage cell.

(ii) SETs -Upsets in the upstream combinatorial logic that propagate to the input of a sequential cell.

(iii) Timing Faults -Increased delay in the upstream combinatorial logic causing the setup constraints to be missed and incorrect data to be sampled.

To further complicate matters, in the event of any of the above classes of errors, the goal may be to simply detect and signal its occurrence or it may be to actually correct or mask the error.

In section 2.2, we review some of the better known protected sequential designs. Each design is presented and its ability to mitigate each of the three types of faults is analyzed. This analysis includes a careful review of the additional overheads and system constraints that are imposed by the design.

The focus of this chapter is on circuit-level techniques for hardened sequentials. In many cases, transistor layout plays a critical role in the level of SER protection of the cell and some data about the extent of the impact of layout is presented. However, it is beyond the scope of this thesis to provide an in-depth study of layout techniques.

Certain sequentials are able to detect errors but not correct them. How a given system recovers from a detected error quickly becomes very application specific. Certain techniques, such as instruction replay and pipe-line counterflow, are commonly used in processor pipelines. In this chapter, the emphasis is on the circuit-level error detection mechanisms and not on the architectural or micro-architectural recovery.

It is important to note that all of the robust sequentials that are described in this chapter rely on two basic principles. Robustness is achieved either through spatial redundancy, temporal redundancy or a combination of the two. These basic principles have been well understood for a long time and their application to robust sequentials was described in detail in [Nicolaidis 1999]. It remains important, however, to study each proposed design in detail, as there is significant variation in the implementation cost and robustness, as will be seen.

There are fundamental trade-offs between area, performance and radiation robustness [Rennie 2012]. In section 2.3, we compare the different designs that were studied based on the types of faults they are able to mitigate and the penalties that they introduce (area, timing and to a lesser extent power).

Survey of Hardened Sequentials

DICE

The DICE cell is well known and the circuit diagram is reproduced from [Calin 1996] in figure 2.1. The design consists of redundant latches which are coupled together to form a feedback loop. If an upset occurs at any of the storage nodes (X 0 ..X 3 ), it will propagate only in one direction, depending on its polarity, but the state of the upset node is restored by the feedback from the other direction. In this way, the DICE cell provides strong immunity against an upset in any single storage node. Of course, the DICE was not designed to provide detection of SETs or timing faults. The DICE cell does provide SEU robustness, however, there are intrinsic limitations to its SEU resilience. The first order concern is the fact that if two sensitive nodes are struck, the stored value can be upset [START_REF] Baze | [END_REF]]. Even in 90nm technologies, multi-node upsets were a concern. This problem can be mitigated by increasing the separation between the sensitive nodes and test results presented in [Seifert 2010b] show that SER decreases exponentially with node separation. Figure 2.2 is reproduced from [Seifert 2010b] and illustrates this effect1 . [START_REF] Hazucha | [END_REF]], and more recently in [Berg 2013], point out one of the main shortcomings of the DICE design. When an upset occurs, it takes some time for the When DICE is used to build a master-slave flip-flop, if an ionizing particle affects a transistor in the slave stage when it is opaque, even if the correct value is restored, a transient is visible at the Q output and can propagate downstream. Similarly, when the slave latch is transparent and the master is opaque, the glitch that comes out of the master will propagate to the flip-flop output. With increased operating frequency, there is less TDR and the effect of SETs induced in latches is becoming more significant [START_REF] Alexandrescu | [END_REF]].

The pass transistors driven by the clock are not protected in the DICE cell thus upsets to these transistors can cause the stored value to be corrupted. Essentially an upset in the clock transistors can either (i) cause the cell to become transparent too early and latch the incorrect value or (ii) cause the cell output transition to be delayed causing a setup violation in the downstream stages [Seifert 2005]. In [Seifert 2010a], data is presented showing that without protection of clock nodes, the maximum reduction in SER that can be achieved with redundancy techniques does not exceed ≈30x.

SEUT

In the literature, especially in publications from Intel, a hardened cell called Single Event Upset Tolerant (SEUT) is frequently cited. Circuit diagrams for SEUT are found in [START_REF] Hazucha | [END_REF]]and [Seifert 2010b] and reproduced in figure 2.3. The SEUT latch is very similar to the DICE latch in that four redundant storage nodes are configured in a feedback loop. The difference lies in the write logic. In the SEUT latch, two of the storage nodes have clock transistors in series in order to facilitate the write process. In terms of SER robustness, however, the SEUT is very similar to DICE.

! ! !" #"$% &$' ())*)+,-./01+20345)6+04+%77+*/+/6.68.6+*9+! $ :6453;<*18+)6=5-)6>6/4+04+6))*)+91*3? @+4 21A!BC +D+EFG@4HH I+D+4 JKL D+4 KL +I+B+ "D+4
(t clk • (1 -α) -MIN(t CC ))
where MIN(t CC ) is the delay on the shortest combinatorial path. This region of susceptibility is labelled 'L2 susceptible to SEUs' in figure 2.5.

For an SEU to be detected by the XOR gate, there must be time for the error to propagate through the XOR gate, through the tree of OR gates and be sampled by the error flip-flop. Thus, the error must occur (t XOR + t OR + t setup ) before the falling edge of the clock. By ensuring that (t XOR + t OR + t setup ) <MIN(t CC ) full SEU protection is possible. This may be achieved through a combination of padding constraints on the logic (e.g. increasing MIN(t CC )) and a reduction the depth of the OR tree (e.g. minimizing t OR ).

SET Detection

Transient pulses due to SETs in the combinational logic can be detected by the XOR gate during the time interval from when the input of the latch is stable up to the point when the error capture flip-flop samples the error signal. Therefore, transients up to ( 1 2 • t clockt XORt ORt setup ) in duration can be detected.

Timing Fault Detection

Similar to SETs, Graal can detect timing faults up to ( 1 2 • t clockt XORt ORt setup ) in duration. Due to this ability to detect timing faults, Graal can be used for near threshold operation, assuming the circuit has a micro-architectural means to recover from the detected errors. shadow latch will falsely activate the correction mechanism causing the incorrect data in the shadow latch to be copied to the main flip-flop. Consequently, the Razor-I design does not provide protection against SEUs.

SET Detection

Depending on the duration of the transient pulse, the Razor-I technique may or may not detect the SET. The following situations are possible:

(a) If a SET is captured in the main flip-flop and the pulse is no longer present when the shadow latch samples its input, then the error will be detected and corrected in the same fashion as timing faults.

(b) A transient pulse that is longer than the delay between the sampling of the main flip-flop and the shadow latch can obviously not be detected.

(c) A SET that arrives after the sampling of the main flip-flop and that is sampled by the shadow latch will falsely trigger the correction mechanism. The incorrect value from the SET will be captured by the shadow latch and then transferred to the main flip-flop.

(d) A narrow transient pulse that occurs between the sampling of the main flip-flop and the sampling of the shadow latch will not be detected, however, such a transient is benign.

To summarize, the Razor-I design does not provide robust detection of SETs.

Timing Fault Detection

The Razor-I topology intrinsically detects and corrects timing errors that manifest themselves inside the monitoring window.

Razor-II

In an attempt to address the shortcomings of Razor-I, the team at the University of Michigan developed an improved version of Razor, called Razor-II [Blaauw 2008[START_REF] Das | [END_REF]]. Because of the redundant latch, the area and power penalties of the Razor-I design are quite high. Furthermore, Razor-I provides no protection against radiation induced errors. The metastability detector, an integral part of Razor-I, is a difficult circuit to design correctly in the presence of process variation. The Razor-II latch is based on a positive level-sensitive latch for the main storage. A simplified circuit diagram is shown in figure 2.9. The underlying design assumption is that the output of the latch should only transition shortly after the rising edge of the clock. A transition detection circuit is added to the output of the latch in order to detect timing faults, SEUs and SETs. To avoid false firing, the transition detector is disabled by a pulsed clock (DC) which goes low during a window from the rising edge of CLK through to the maximum CLK→Q delay of

TDTB and DSTB

Two variants of double sampling flip-flops were investigated by Intel and described in [Bowman 2008]. The first, called Transition Detector with Time Borrowing (TDTB), is conceptually similar to the Razor-II design. It consists of a latch that is augmented with a transition detector as shown in figure 2.11(a). The transition detector flags any input transitions during the high-period of the clock, thus requiring the input to the latch be stable during the high phase of the clock. This can be achieved by adjusting the duty-cycle of the clock or by padding the short paths. This timing constraint is identical to that required for Razor-II (see section 2.2.6).

In Razor-I, the main storage element is an edge-triggered flip-flop and the shadow copy is stored in a latch. Douple Sampling with Time Borrowing (DSTB) is a variant of Razor-I where the main storage element is a pulsed latch and the shadow copy is captured using an edge-triggered flip-flop (see figure 2.11(b)). The SET and timing fault detection capabilities of TDTB and DSTB are similar.

In the published work, a small, three stage pipeline is implemented using both types of sequentials. It appears that the error signals from all the sequentials in the design are OR'ed together, fed to the first stage of the pipeline (Input Buffer) and caused the in-flight instruction to be re-issued with a half-speed clock. There are obvious scalability issues if the error signals fan into a single point in the design.

It is interesting to note, that the Razor-I design team required the use of a dedicated metastability detector in order to achieve robust operation [START_REF] Das | [END_REF]] when the setup/hold constraints of the main flip-flop were not met. However, in the published work on DSTB and TDTB [Bowman 2008 error recovery is not specific to a given design architecture (e.g. micro-processor pipelines, etc.).

The prototype design for Bubble-Razor was an ARM Cortex-M core implemented in a 45nm technology. The original flip-flop based design was converted automatically by a tool into a latch based design. On average each flip-flop was mapped into ≈3.29 latches and the area overhead for this transformation was 8%3 . The overall area overhead for the Bubble-Razor implementation was 21%. For a typical process conditions, the Bubble-Razor techniques enables a performance increase of 22% at a given, fixed voltage. Alternatively, an energy reduction of 54% is possible at a fixed level of performance.

SEU Detection

The Bubble-Razor technique does not provide protection against SEUs. The XOR gate which compares the outputs is only active when the master latch is transparent and during this time, the latch is not susceptible to SEUs. During the time when the clock is low (G =0), the dynamic XOR gate is being pre-charged and thus does not detect errors.

SET Detection

The Bubble-Razor technique can detect SETs.I faSET is present on the rising edge of the clock, the incorrect value will be sampled in the shadow latch. Later, when the transient has expired, the output of the master latch will assume the correct value and the error detection logic will be triggered. The maximum width of SET than can be detected is equal to the high-phase of the clock less the propagation time for the error signals.

Timing Fault Detection

Bubble-Razor does effectively detect timing faults. The maximum timing fault that can be detected, is limited by the fraction of the cycle the clock is high, less the propagation time of the error signal through an OR tree.

EDC Flip-Flop

The Error Detection Correction (EDC) flip-flop [START_REF] Valadimas | [END_REF]] consists of a main flip-flop, an XOR gate, a redundant latch and a multiplexer. The XOR gate compares the input and the output of the main flip-flop and this result is sampled by the latch as shown in figure 2.14. The idea is that the data at the input to the flip-flop must remain stable for a period of φ so that the main flip-flop and the redundant latch sample the same value.

The latch is clocked with a locally generated pulsed clock that is delayed from the main clock by a delay φ as shown in figure 2.14. The width of the pulsed clock is α and it must be large enough to meet the minimum pulse-width requirements of the latch, under all operating conditions. The logic to generate the pulsed clock can be shared amongst a group of flip-flops. Increasing the value of φ is costly both in terms of area, due to the additional delay elements, but more importantly in terms of active power because the delay gates on the clock generation circuitry are toggling at the full clock rate.

If a timing error is detected, then the Error signal causes the clock to be globally gated to the entire circuit for one cycle. During this time, the inverted (Qbar) output of the main flip-flop is output and thus the correct computation occurs. This approach imposes a tight timing constraint: in less than one cycle, the Error signal must be generated at every EDC flip-flop and then propagated to the clock input of every flip-flop in order to perform the clock gating. This constraint limits the operating frequency and the size of the circuit.

SEU Detection

A SEU that occurs in the main flip-flop between the rising edge of the clock and the falling edge of C_Pulse will be detected by the XOR gate. A SEU that occurs later in the clock cycle will go undetected. Therefore the overall fraction of SEUs that are detected is φ+α t clock . In practice, due to the requirement that all combinatorial paths be padded to a minimum delay of φ and due to the power cost in generating the delayed clock, this fraction will be small and overall the EDC flip-flop provides only limited SEU protection. deisgned to cover the worst case CLK → Q delay which may be significantly longer than the actual delay.

When an SEU occurs, during the window of time it takes for the correction to occur, the incorrect value will propagate. The intended use of the SET flip-flop is that when an error is detected, the clock is gated, and extra time is allowed for correct computation to occur using the corrected value.

SET and Timing Fault Detection

The SET flip-flop does not provide a mechanism for detecting or correcting SETs or timing faults.

TMR

When the highest level of robustness is required, Triple Modular Redundancy (TMR) techniques are typically used. In the most common form of TMR, at the circuit level, just the flip-flops are triplicated as shown in figure 2.17(a). This approach only provides protection against SEUs and is often used when hardening Field Programmable Gate Array (FPGA) designs. Since the clock network is not replicated, it remains a weak point, and any transients on the clock will affect all the flip-flops. In space applications, this is addressed by replicating the clocks as shown in figure 2.17(b). If the phase difference on the replicated clocks is at least t SET , then any transients of less than this duration will be filtered as the transient is then only sampled by a single flip-flop. Of course, this comes at a penalty in timing performance equal to twice the transient pulse width.

Having three clock distribution networks is very costly and recently techniques to achieve the same robustness using only two clocks have been developed as shown in figure 2.18 [START_REF] Nicolaidis | [END_REF]]. With this approach, the third temporal sampling point is obtained by adjusting the duty-cycle of the clocks.

!" !"# $%&'( ))#*+,-./
))#0

))1

))2*+345./ $%&'( %67% !%89

Parity Codes

Parity codes have been used to protect data since the earliest computers. In some situations, they can be very effective at protecting flip-flops against SEUs.I nfi gure 2.19, it is shown how parity can be calculated over a set of data bits and the parity stored in an additional flip-flop. On the output of the flip-flops, the parity is checked and errors are detected. The major drawback to parity codes is that the additional delay to compute the parity directly affects the critical path.

For parity generation, the cost is half an XOR gate, per bit. On the checking side, the parity must be re-computed, which also costs half an XOR gate per bit plus a final XOR to compare the result with the stored parity. The cost of the extra flip-flop for the parity, is amortized across the N flip-flops that are being protected. To combine the error indications from multiple groups of parity bits, an OR tree is required which is an additional overhead.

Parity codes can, however, be very effective when data moves through several stages of flip-flops without being modified. In this case, the parity can be calculated at the front of the pipe and checked at the end. The overhead of the parity calculation and checking circuitry is amortized over the M stages, as shown in figure 2.20. Only an extra parity bit needs to accompany the data bits through the intermediate stages. In this case, per-bit the area overhead is approximately

A XOR M + A FF N .
appear on the data-path. One could thus say that parity logic does provide detection of timing faults, although this comes at the cost of a significant timing overhead.

Comparison of Robust Sequentials

As seen in the above sections, there exist a large number of robust sequential cells, each with specific error detection capabilities, different overheads and specific usage constraints. In this section, the objective is to compare the different techniques and put them in context. It is often difficult to assess the implementation cost of a cell without completing the transistor-level design. The overheads are technology specific and even for a given type of cell, multiple implementations with different drive strengths and speeds are possible. However, it is clear that certain circuit designs have intrinsically higher overhead than others. The approach taken to compare the area of the different circuits is based on counting the number of additional transistors required to implement the robust cell, compared to a minimum-sized implementation of either a standard latch or flip-flop. It is true that transistor widths vary greatly, so this measure has limitations, however, to correctly size the transistors requires a full implementation of each design, which is beyond the scope of this thesis.

The Nangate Open Cell Library [Nangate 2008] was used to facilitate the comparison. The transistor count and area of different standard cells is shown in table 2.1. The library does not include a C-element, but from a schematic it is known that a C-element can be implemented with 12 transistors. For some of the robust sequentials, there is extra circuitry that can be shared across multiple flip-flops. Specifically, this is the case of the pulsed clock generators used in the EDC and the SET flip-flop. Also, for those designs that provide detection, there is an OR tree which combines the error signals and terminates at an error flip-flop. For the purposes of this comparison, it is assumed that these structures are shared amongst 32 flip-flops. In this way, a per bit overhead is calculated in terms of the number of additional transistors. Using this approach, the area and timing overheads for the robust sequentials studied in this chapter are summarized in table 2.2. Overhead is thus 31=47-16. c Reported transistor count of Razor-I is 76. Basic flip-flop assumed to have 28 transistors.

Overhead is thus 48=76-28. d Overhead for bubble-Razor consists of a shadow latch (16), a dynamic XOR gate (10) and at least one dynamic OR gate ( 6). e In [START_REF] Hazucha | [END_REF]] timing overheads for a DICE implementation are presented and are under 2%. f The SEU detection of Razor-II is limited by the fact that the low period of the DC clock must span the worst case CLK→Qd e l a y . S e es e c t i o n2.2.6.1.

Conclusions

To provide a simple summary of the protection capabilities of the different techniques, the cells have been grouped into three sets based on whether they mitigate SEUs, SETs or timing faults. A Venn Diagram showing these capabilities is shown in figure 2.21. Cells which provide only detection are shown with a dark, red square and those that provide correction are shown with a light, blue square. For SEU robustness alone, the DICE cell is well established, including variants with improved layout (e.g. LEAP-DICE [START_REF] Lee | [END_REF]). However, it is important to remember, as pointed out in section 2.2.1.1, when an upset occurs in a DICE cell, it takes some time to recover and a glitch can propagate into the downstream logic. At higher frequencies, there is less TDR and thus an increased risk that such a glitch will be sampled downstream.

When looking for protection against both SEUs and short SETs, the Biser cell is attractive. For a cost slightly higher than a redundant latch, through the use of a C-element, the Biser can block SEUs and SETs. In order to detect wider SETs, the length of the delay chain (τ delay) at the front of the cell must be increased.

We identify three cells (Graal, which, in principle provide detection of SEUs, SETs and timing faults. All three are latch based designs and have special timing constraints. Using two-phase, non-overlapping clocking, Graal ensures that the inputs to each latch remain stable after the latch is opaque. To achieve SEU protection during the full window of temporal susceptibility, either the short paths must be padded or the depth of the OR tree must be very shallow (see section 2.2.3.1). Razor-2 achieves SEU detection using a transition detector that is disabled around the active edge of the clock. The disabling of the transition detector creates a window when SEUs may not be detected. Razor-2 imposes the requirement that short paths be padded to ensure that the inputs to the latches are stable during high period of the clock. The timing requirements for DSTB are similar to those of Razor-2, thus requiring short paths to be padded.

Although designs exist that can detect all three classes of errors, they impose specific timing constraints and have some limitations on the extent of SEU detection.

Overview of Analysis Techniques

Analyzing the effect of faults induced by soft errors in complex integrated circuits remains challenging. The vast majority of faults do not propagate due to the various de-rating factors that were identified in section 1.3. Without an accurate characterization of the fault propagation probabilities, the failure rate of the system may be grossly misestimated. Usually the raw soft error rate of basic cells (e.g. memory cells, flip-flops) can be characterized accurately and error bars of under 10%-15% are typical. Achieving the same level of accuracy in the effects analysis is difficult and often the accuracy of the full system-level analysis is limited by the accuracy of the effects analysis.

A high-level view of the propagation from faults to system level failures is shown in figure 3.1. Shown on the left are the faults that can be induced in flip-flops, logic gates and memories. Due to de-rating effects, Temporal De-Rating (TDR), Logical De-Rating (LDR), Electrical De-Rating (EDR) and Memory De-Rating (MDR), many of these faults do not propagate. After applying these de-ratings, the effective rate of visible errors is calculated. The next step is to analyze the effect of each error on the system. This comes from the FDR analysis and the result is the rate of occurrence for a defined set of system-level failures.

!" #$% &$% !# '()*+'(,*- !$% &$% #$% &,.)/01234- %250'26(3 %234- 7" 87" 89" 8$% !::4/3);400!<<,< %234- '2)(6<409(2--00= '$% 84>,<)4- ?-34> '2)(6<409(2--4- '2)(6<409(2--00@ '2)(6<409(2--00A Figure 3.1: Soft Error Effects Analysis
The most common approaches to evaluate fault propagation centre around faultinjection analysis. Many faults are injected into a model of the circuit and the effect is observed. Depending on the accuracy of the model (e.g. gate-level, RTL, etc.) only some of the de-rating factors may be taken into account. There exist many different fault injection techniques and a brief review is presented in section 3.1.2. Often FPGA-based platforms are used to accelerate fault-injection and these are discussed in 3.1.2.2.

Analytical approaches are an alternative to fault injection. These approaches use a mathematical or abstracted model of the circuit to evaluate the effect of faults. Microprocessors have been studied in depth and a widely used analytical approach is based on the notions of Architectural Vulnerability Factor (AVF) and Program Vulnerability Factor (PVF) and these are discussed in section 3.1.3.

Analytical techniques also exist for circuit level fault effect analysis. Some of these use special data-structures such as Binary Decision Diagrams (BDDs) or Algebraic Decision Diagrams (ADDs) to represent the circuit and reason about fault propagation. Other techniques are based on a formal representation of the circuit as well as the properties it must meet. Using tools for model checking or symbolic simulation, it can be verified whether the properties hold in the presence of faults. These techniques are discussed in section 3.1.4 and 3.1.5 respectively. Another set of approaches is based on associating probability distributions to the nodes in a circuit and then using these to compute the probability that faults on a given node will propagate to an output. These techniques are reviewed in section 3.1.6.

We conclude the first half of the chapter with a qualitative comparison of the different techniques in terms of their accuracy, speed, the types of faults that can be modeled and the types of masking that can be analyzed. In the second half of the chapter (section 3.2), a detailed case study of the soft error effects for several large design blocks in a Network Processor (NP) is presented.

In practice, no single technique can be applied to an entire System on Chip (SoC). Instead hierarchical and hybrid approaches must be developed. In chapter 5, a hierarchical technique for analyzing the effects of SETs is presented. The RIIF modeling language which is described in chapter 6, is intended to facilitate such hierarchical analysis by providing a means to encapsulate the results of a blocklevel analysis and make them available for an analysis at the next higher level of hierarchy.

Objectives of Soft Error Effects Analysis

The goal of any soft error effects analysis is to assess the probability that radiation induced faults result in the occurrence of a chip or system-level error. The list of chip or system-level failures must be clearly enumerated prior to the analysis. In processor applications, the two main effects that are typically identified are Silent Data Corruption (SDC) and Detected Uncorrected Errors (DUEs) [Mukherjee 2008]. A common taxonomy for processor effects is reproduced from [START_REF] Weaver | Reducing the soft-error rate of a high-performance microprocessor[END_REF]]i nfi gure 3.2. SDC occurs when a bit has no protection and its value affects the program execution. DUE occurs when there is a fault in a bit which has only detection, regardless of whether it affects the program outcome, or not. A well known consequence of the latter observation is that by simply adding error detection to a processor, the SDC rate may be reduced, but this comes at the expense of increased DUE. Leading processor manufacturers characterize the SDC and DUE rates of their designs and communicate these values to their customers, usually under strict Non-Disclosure Agreements (NDAs).

In core networking applications (routers and switches), a different approach to classifying the effects of faults is proposed in [START_REF] Silburt | [END_REF], Silburt 2009]. The specification that is presented defines outage classes based on the duration of time the network is unavailable. A very short outage, affecting only a small number of pack- As the duration of the outage increases, so does the severity. Using Quality of Service (QoS) specifications for packet traffic, card-level hardware reliability targets and network availability requirements (e.g. five 9's), the authors establish bounds on the rate of occurrence of different classes of system failures and these are summarized in table 3.1. Defects per Million (DPM) is an availability metric. When analyzing an ASIC used in networking applications, it is necessary to ensure that these system level targets are met for each outage class. As part of the FDR analysis, each fault must be classified based on the class of outage it produces. Then the total failure rate for each outage class is summed for the entire system. To summarize, the goal of a soft error effects analysis is to compute the rate of system level failures starting from the rate of technology level faults due to soft errors.

!"#$%&'($ ()&*+!,- '+.(/.& !"#$0 .1&+**1* '($&2!) +**1*&3*1$+4$(1.- !"#$&41**+4$+,0 51&+**1* ! +4$)&3*1/*!6 1"$416+- ! +4$)&3*1/*!6 1"$416+- '+.(/.& !"#$0 51&+**1* 7 8 9 :;< = !#)+ ;>? @ $*"+ ;>? A .1 %+) .1 %+) 41**+4$(1. %+) .1 .1 ,+$+4$(1. 1.#%

Fault Injection

Fault injection analysis consists of injecting a number of faults into a model of a system to evaluate how it behaves in the presence of these faults. Models with different abstraction levels can be used. Obviously, there is a trade-off between the level of abstraction versus the speed of the analysis and the accuracy of the results. The main challenge with any fault injection analysis is managing the number of faults that must be evaluated. This number grows with:

(i) Number of fault types (e.g. SEUs, SETs).

(ii) Design size (e.g. number of gates).

(iii) Number of workloads or stimulus patterns to analyze.

(iv) Duration in cycles of each workload or stimulus pattern.

The review presented in [START_REF] Yu | [END_REF]] exposes the fact that exhaustive fault simulation is not possible for commercial circuits. For example, in [Valderas 2010]a n exhaustive fault injection analysis was performed on a small micro-processor with 596 flip-flops and required 80 million fault injections. Many techniques to accelerate fault-injection simulations have been proposed and are discussed in section 3.1.2.1. An enhancement to existing acceleration techniques is presented as part of the case study in section 3.2 of this chapter.

When the objective of the analysis is to compute system-level failure rates, it is only necessary to evaluate a relatively small number of faults in order to obtain accurate estimates of the system level error rates. In section 3.3, error bounds for statistical fault injection are discussed. When the objective is fault grading (e.g. identification of which circuit elements are most critical), new techniques are required to identify the critical elements in large designs and this is the topic of chapter 4.

Simulation Based Fault Injection

Independent of reliability concerns, digital simulation is used extensively to verify the functional correctness of modern designs. The environment used for functional simulation can be reused for fault simulation. A simple approach for simulating faults is shown in figure 3.3(a).W i t ht h i sa p p r o a c h ,t h eDevice Under Test (DUT) is instantiated twice. A fault is injected in one instance while the other serves as a 'golden' reference and the output vectors from both instances are compared clock by clock. In practice, as long as the input vector sequence remains fixed, it is not necessary to actually simulate the golden version of the DUT during each run as the output vectors can simply be recorded in advance. It is, however, only possible to assess whether the output vectors diverge. This approach provides no insight into the actual effect of the divergence.

The advantage of this simple approach is that it can be applied to almost any design and does not require an understanding of the application. The corollary is that this approach provides no insight into FDR. 3.3(b) shows a more complete view of a modern functional simulation environment. The stimulus is generated in terms of transactions (e.g. packets, video frames, numeric data, etc.) which are converted to low-level vectors by Bus Functional Models (BFMs). On the output side, the raw vectors from the DUT are parsed into transactions which are checked by intelligent checkers. The stimulus generator and the checker communicate via a scoreboard which is a data-structure that tracks the transactions currently being processed by the DUT. As the intelligent checker works at a high level of abstraction, it detects and reports errors at the transaction level (e.g. missing packets, corrupted video frames, numerical errors, etc). Typically, these errors are written to a log file and it is possible to map the various error messages to the system-level impact they have. Essentially, the intelligent checkers provide an automated means to evaluate the system level effect of faults.

!"#$%$& '()(*+!,* ',%-() ./0 ./0 11 2+!345657,52+!34 8+$%! 9):(3!",) ;(3!,*& ;(3!,*& ;(3!,*& (a) Simple Simulation Environ- ment !"#$%$&'()*)+,!"-* ./0 3)&&,7) ; 3)&&,7) < 3)&&,7) = >>> ?)6!-+& !+,*&,6!"-*& ?)6!-+& !+,*&,6!"-*& 6-+) 1-,+@ !+,*&,6!"-*& !+,*&,6!"-*& (b) High Level Simulation Environment
The challenge with simulation based fault injection is the relatively low speed of digital simulators. Fortunately, the problem of fault-injection is easily parallelized. By the 1970's [Chang 1974] techniques for parallel fault simulation had been developed and already at this time, it was possible to evaluate thousands of faults per second on mainframe computers for circuits with hundreds of gates. Below, we discuss a few of the numerous techniques that have been developed to accelerate fault simulations.

Recently, [START_REF] Alexandrescu | [END_REF]] presented the implementation of an acceleration technique based on exploiting the fact that modern processors typically have a 64-bit word width. On the host processor, instead of running simulations sequentially, up to 64 simultaneous fault injections can be performed, where each bit in the data-path of the host processor is used to evaluate a different scenario. A tool was developed which can compile an RTL description into C code which, when executed, evaluates 64 faults in parallel. The combination of the parallel simulation and the optimized C code, results in a performance increase of over 500X compared to a commercial event based simulator. The downside is that it can only be used to implement simple fault injection, as shown in figure 3.3(a) and it does not provide a means to parallelize the intelligent testbench bench components shown in figure 3.3(b),t h u s limiting its applicability to evaluating LDR.

Another approach to reducing simulation time is presented in [Berrojo 2002a, Berrojo 2002c]. Through the use of rules derived from the structure of the design certain faults can be shown to be equivalent to others faults or to be dominated by other faults. For example, a fault that affects an upstream flip-flop directly feeding a downstream flip-flop through a shift register of N stages, is equivalent to a fault in the downstream flip-flop, N cycles later. Faults that affect flip-flops on primary outputs need not be evaluated, as they obviously propagate. Additional rules can be derived based on the stimulus patterns. For situations where read and write operations can be clearly identified, any faults injected between two writes with no intervening reads can be eliminated, as they will not propagate. When these techniques were applied to a circuit used in a spatial application, the static techniques allowed the total fault list to be collapsed to ≈13% and the dynamic techniques allowed a further reduction to ≈4.7%. Fault collapsing techniques are attractive to prune the number of faults; the remaining faults can then be executed in an intelligent simulation environment. In the cited work, checkpoint techniques are also described which avoid repeatedly running the portion of the simulation prior to the time when the fault is injected as well as avoiding simulating beyond the point when the system returns to its golden state.

Emulation Based Fault Injection

FPGA emulation techniques are used to accelerate fault injection campaigns [START_REF] Lopez-Ongil | [END_REF][START_REF] Valderas | [END_REF], de Andres 2008[START_REF] Mohammadi | [END_REF]]. The advantage of FPGA based techniques is that the circuit can run orders of magnitude faster than in simulation. Care must be taken to ensure that the fault-injection platform does not introduce bottlenecks that limit the effective fault-injection performance. Common sources of bottlenecks are in the communication with the host computer and also in the time required to actually inject the fault.

One of the drawbacks with emulation based techniques is that it is more difficult to assess the effect of the fault. As discussed in section 3.1.2.1, an intelligent testbench can assess the type of error and classify it based on its system-level effect. On an emulation platform, it is possible to match the bit-level state of the device under test against the state of a golden design. It is thus possible to determine if there are latent faults in the design. It is, however, more challenging to perform run-time, high-level fault-classification as this must be performed in the FPGA hardware. As will be seen in 3.2.6, an important fraction of faults may result in an ongoing perturbation of the circuit state without causing a serious error.

Another drawback of emulation based fault-injection lies in its scalability for large designs. A full ASIC today typically has between 5-20M flip-flops and can not be mapped into a single FPGA. The routing resources available in an ASIC far exceed those of FPGAs, thus congestion and management of large-fanouts may become serious issues in an FPGA implementation, requiring extensive engineering effort to resolve. Furthermore, it is common for ASICs to have hundreds of megabits of embedded memory, well beyond what is available in FPGAs. Techniques do exist for mapping large designs into FPGAs and these involve mapping embedded RAMs to external RAMs and scaling some aspects of the design (e.g. reduced bus-widths, reduced cache-sizes, etc.). Overall, emulation techniques are best suited to designs where the full circuit under test can be comfortably mapped into a single FPGA device.

Different techniques can be used to inject faults on an FPGA-based system. One approach is to instrument the original circuit [Civera 2001]. To inject SEUs, the flip-flops where faults are to be injected in the original circuit are mapped to instrumented flip-flops. The instrumented flip-flops have additional ports that enable faults to be injected and for the results of the fault injection to be observed or checked.

To fully exploit the potential of emulation based fault-injection, the controller that injects the faults must be implemented in hardware and run natively on the card with the circuit under test. The autonomous emulation platform presented in [START_REF] Lopez-Ongil | [END_REF]] has all of these characteristics and fault-injection rates of 4.2 µsec per fault are reported for test benches that require 600 clocks to execute. The largest circuits that were studied in this work had approximately 2,300 flip-flops.

A fundamentally different approach to FPGA-based fault injection is based on dynamic re-configuration of the FPGA.W i t ht h i st y p eo fa p p r o a c h ,t h eo r i g i n a l circuit is not modified when it is mapped. Instead, at the point when the fault is to be injected, the clock is stopped, the FPGA is reconfigured so that the new configuration models the effect of the injected fault and then the circuit is resumed. Because the host-controller is involved in the fault injection, there is an inherent speed penalty with this approach. Results presented in [Antoni 2002] report that it takes approximately 1 msec per experiment.

There is growing concern about the effects of SETs, even in terrestrial applications. Emulating the effect of SETs is significantly more difficult than for SEUs. First, the actual gates in the target circuit implementation do not exist in the FPGA but are instead implemented using Look Up Tables (LUTs). Secondly, the delays in the FPGA implementation are completely different from those in the target implementation. These issues were addressed by researchers at Carlos III University through a quantized time approach [START_REF] Entrena | [END_REF]]. The Standard Delay Format (SDF) file for the gate-level netlist is analyzed and a minimum time-step is identified. In the target FPGA, the circuit is then mapped with shift-registers replacing wires and by selecting the correct stage on the shift register, arbitrary delays can be emulated, with a resolution down to the selected time quantum. Transient pulses of arbitrary width can be injected by changing the value on the delay chain, for the required number of time quanta. The fine-grained temporal emulation is only required to propagate the effect of the SET until it reaches one (or many) sequential elements. In [Entrena 2012], the AMUSE system is presented where both an RTL and a gate-level implementation of the circuit under test coexist in the FPGA. The RTL model runs nearly one hundred times faster than the gate-level model and is used prior to the fault-injection and after the SET has reached the memory elements. The gate-level version, is used for the short window in time when the SET is injected. Using this platform, SET fault injections can be performed on a full Leon2 processor at a rate of approximately 3000 faults per second.

These techniques require additional engineering effort. The limited size of FP-GAs makes it challenging to deal with large designs and the level of analysis that can be performed when a failure occurs is limited by the "intelligence" embedded in the emulation platform.

Software Based Fault Injection

When studying processor based systems and when the actual hardware is available, it is possible to use code running on the processor to inject faults that model the effect of SEUs. This technique is referred to as Software Implemented Fault Injection (SWIFI) or Code Emulated Upset (CEU). The execution sequence of a typical software based fault injection platform is reproduced from [START_REF] Valderas | [END_REF]] in figure 3.4. The normal application is run on the processor and then, at a randomly selected time, the processor is interrupted, typically using a Non-Maskable Interrupt (NMI), so that faults can be injected at any instruction in the program. The interrupt routine then selects a bit to be flipped, amongst those that are accessible to software. Typically these include bits in the register file, the cache, the program counter as well as the code, data and stack segments. The interrupt routine terminates and execution of the application resumes. When designing a SWIFI experiment, the set of bits to inject must be carefully considered. For example, if the cache is ECC protected, it does not make sense to inject faults in it.

When performing SWIFI experiments, multiple Error Detection Mechanisms (EDMs) can be used [START_REF] Arlat | [END_REF]]. Of course, at the end of the application, the final output of the program must be checked. Additionally, processors also include embedded hardware checks such as the detection of bus errors or illegal op-codes. Depending on the system, external hardware checking may be also present in the form of watchdog timers. The operating system and firmware are also able to detect certain errors through protocol checks and checksums on packets. When designing the experiment, the failures detected by the EDMs must be mapped to meaningful categories, based on the application.

An alternative approach to injecting software faults is used in [START_REF] Arlat | [END_REF]]a n d consists in modifying the compiled program (code segment or static data segment) prior to its execution. This approach has the advantage that the program flow is not interrupted.

Overall, the key advantage of SWIFI or CEU techniques is in the ease of implementation and the fact that the application can run at real time in its target environment. In this way, the interactions with the overall system are accurately modeled. The main disadvantage is that not all state bits are directly accessible by software, thus only a subset of all of the real faults can be studied.

Comparison of Fault Injection Techniques

Given the variety of Fault Injection (FI) techniques, it is critical to understand how the results obtained with different techniques compare. In an early study [START_REF] Stott | [END_REF]], SWIFI techniques were compared with bit-level fault injection on a cycle accurate processor model. The application was a network interface card where the main component was a processor running a program called MCP. In these experiments, the faults were specifically targeted at the instruction currently being executed. Exactly the same set of faults was injected in both the SWIFI and the simulation platform. The results of this study are reproduced in the table 3.2. The second and third columns show the number of faults that resulted in each category using the simulation and SWIFI techniques. The column on the right shows the percentage of times that the two techniques produced the same result.

The results are interesting in that both techniques are effective at identifying which faults produce no error (99.5% correlation). The correlation is also quite good for less severe failures such as dropped messages and corrupted data. For the more severe errors, the correlation is much weaker. Given the relatively small number of faults that were analyzed in this study, the errors bars are significant and broad conclusions can not be drawn.

Other studies [Cardarilli 2002] on small designs have shown a very high correlation between CEU techniques, flip-flop level fault injection and radiation test results. In this work, two application programs were run on an 8051 micro-controller and the error rates obtained from CEU and from simulation based fault injection matched to within a few percent.

In [START_REF] Arlat | [END_REF]], an in-depth comparison of errors produced by radiation, pin-level forcing and electromagnetic interference versus SWIFI techniques was performed for an application running on a 68070 processor. This work showed that bit-flips in the code-segment are able to produce error profiles similar to the hardware injection mechanisms, however, certain hardware level EDMs were not able to be triggered by SWIFI. Furthermore, when the application was protected with dual execution, SWIFI underestimated the fraction of silent failures compared to the actual radiation testing.

A recent study [START_REF] Cho | [END_REF]] compares the results of fault injection at the microarchitectural and program level versus direct fault injection in the flip-flops. In the micro-architectural level simulations, either a random bit is flipped in a register file (RegU) or a random bit is flipped on a write operation to the register file (RegW). For the application level faults, either a single bit error is injected into the value of a program variable (VarU) stored in memory or a single bit error is injected into a piece of data being written to memory (VarW). The target system was a Leon3 processor and multiple complex applications were used as workloads running for billions of clock. An excerpt of the results is reproduced in figure 3.5. From these results, a difference of a factor of three is observed in the mean rate of hangs. The authors conclude that high-level fault injection can be highly inaccurate compared to flip-flop error injection.

Overall, care must be taken when using SWIFI to predict the actual rate of errors induced by soft error effects. First, we note that there are many different approaches to SWIFI and there is are significant variations in the error effects they produce. In some cases, SWIFI can provide a reasonable indication of the overall error rate, however, there is evidence that it can not predict the distribution of the types of errors actually produced by SEUs.

Analytical Techniques for Processors

An analytical technique for assessing the sensitivity of processor designs was introduced in [Mukherjee 2003] and further developed in [Mukherjee 2008]. This approach classifies the bits in a processor based on whether they are necessary for Architecturally Correct Execution (ACE).Ab i tt h a ti sACE is important for the program to produce correct output. The notion of Architectural Vulnerability Factor (AVF) is defined as the ratio of ACE bits to the total number of bits in a hardware structure. To some extent, AV F is a term, introduced at Intel that has the same meaning as LDR. A structure with an AV F of '1' or a LDR factor of '1' is sensitive to all upsets.

Many bits in a processor can quickly be classified as un-ACE. For example, units used for branch-prediction are inherently un-ACE as mis-predicting a branch does not affect the program's results. Certain instructions are inherently un-ACE such as NOPs and instructions used only to pre-fetch data into the cache. In addition, the results of many instruction are never actually consumed. These results represent First-level Dynamically Dead (FDD) data and are un-ACE.

Architectural and performance models for a processor are usually used for AV F analysis and can provide results about the sensitivity of the different functional units (e.g. re-order unit, ALU, etc.). These models run very quickly, and it is possible to evaluate the AV F of real applications that run for millions of cycles.

The occupancy of the queues, such as an instruction queue, plays an important role. When a queue is nearly empty, upsets to its memory locations have a low probability of propagating. Conversely, when a queue is full, almost all of its bits are sensitive. For this reason, Little's Law1 is sometimes used to estimate the steady-state AV F of structures containing queues.

One of the drawbacks with AV F analysis is that there is no distinction between the masking that is intrinsic in the hardware, and the portion of the masking that is introduced by the application. In [START_REF] Sridharan | [END_REF]], the notion of Program Vulnerability Factor (PVF) was introduced to separately capture that portion of the in the circuit including each combination of input patterns for the gate. Based on the condition being evaluated, the BDD for the impacted gate is updated and then the BDD for the upstream portion of the full network is rebuilt. An example of an updated network BDD is shown in figure 3.6(b). The delays on each gate of the network are considered, so cases where reconvergent paths cause a pulse to be cancelled out are correctly evaluated. The authors claim that the correct modeling of reconvergent paths is essential for the accuracy of the results, however, no actual data is provided to justify the claim. In order to process larger circuits, this tool partitions the network and treats each partition separately. The authors show strong correlation between the results of FASER analysis with fault injections performed using SPICE for the full network and claim a huge speedup compared to SPICE simulation. However, the FASER algorithm still involves an exhaustive evaluation of the propagation of each fault for each input state. Inherently, the accuracy of FASER is no better than that which would be obtained using SDF annotated gatelevel event-driven simulation and it is not clear that the use of BDDs is faster than gate-level simulation. Due to the exhaustive evaluation of all faults, this approach is not scalable to large circuits.

The MARS-C tool, described in [START_REF] Miskov-Zivanov | [END_REF], uses a combination of BDDs and ADDs to simultaneously model LDR, TDR and EDR. The authors start by identifying a temporal window during which a transient must arrive at the circuit output in order to meet the setup/hold window and be sampled.

For each gate, an initial ADD is created representing the duration and amplitude of a SET occurring in that gate. Models developed by [Omana 2003] are used to define how the amplitude and duration of a transient are modified as they propagate through intermediate gates. Using the initial ADD, representing the faults, and the pulse transformation rules, a full set of ADDs are generated to model the propagation of faults in each gate to each output. A terminal value of '0' in the ADD represents all the cases where the transient is completely masked (either electrically or logically). In figure 3.7,a nADD showing the propagation of a fault occurring in gate G2 through to the output of G5 is shown. In this figure, D235 represent the transformation of the initial pulse at G2 as it passes through G3 and G5. An algorithm to accurately model the effect of reconvergent paths when building the ADDs is used and it takes into account the arrival times of the pulses on each path and the controlling values of the reconvergent gate. Once the ADDs have been built, the total error rate for the entire circuit can be calculated. The complexity of the algorithm grows with the product of the number of outputs and the number of gates in the circuit. This tool is able to evaluate circuits with approximately 500 gates in a few minutes of CPU time, which is impressive given that all of the relevant de-rating factors are considered and the reported accuracy is very close to that obtained using SPICE.

Formal Techniques

Formal techniques consisting of model-checking and symbolic simulation are increasingly used in the context of functional verification. A model checker is able to exhaustively explore all the states that are reachable from a set of initial states. In the context of verification, a typical application of these techniques is to ensure that a design respects a certain formal property such as being free of deadlock. Several researchers [Seshia 2007[START_REF] Shazli | [END_REF], Darbari 2008[START_REF] Baarir | [END_REF]] have looked at using these techniques to assess the effect of faults on circuits as well as to identify critical flip-flops.

In [Seshia 2007], a SpaceWire communication circuit with 130 latches is analyzed. The Verilog description of the circuit was manually translated into a format readable by the SMV tool [Cadence 1998]. The authors then analyzed the english specification for the SpaceWire protocol and translated the requirements into 39 formal assertions that define the correct operation. The initial model was first validated to conform to the specification in the absence of faults. A formal model for a SEU was created. The model expresses that a given bit can change state at an arbitrary cycle. The model checker was then rerun repeatedly, each time with the formal model for a SEU in each of the latches. The authors found that upsets in only 28 of the 130 latches would cause a violation of the specification. A single run of the model-checker required less than 4 minutes. The approach is interesting because after protecting the 28 critical latches, the design is known to operate correctly under all situations. Unfortunately, the engineering effort required to create the formal specifications is quite high and requires experts familiar with SMV.

The approach presented in [Seshia 2007] makes it possible to determine whether a given state bit is critical for correct operation. It does not, however, provide a means to rank the critical state bits. In [START_REF] Baarir | [END_REF]], the authors introduce the notion of repairing states. When a fault is introduced in the formal model, after some number of incorrect states, it may return to the correct state. The ratio of the number of repairing states to the total number of reachable states provides an indication of the criticality of a state bit. The design considered in this work is a single state-machine with six states and small number of inputs and outputs.

Formal techniques for the analysis of SEU are certainly of academic interest, however, it does not appear that they can be applied to industrial scale designs, such as those considered in the second half of this chapter.

Probabilistic Techniques

Probabilistic techniques for analyzing fault propagation through combinatorial networks have been well studied and two early tools to perform this type of analysis were PROTEST [Wunderlich 1985]a n dS T A F A N [START_REF] Jain | [END_REF]]. The approach is based on first computing the probability, P (i), that each signal in the network has the value '1'. Next, the probability that a fault on any signal will propagate to the outputs is evaluated. Typically, a probability of 0.5 is assigned to the primary inputs of the circuit. Then working forward through the network, the signal probabilities, P(i) are propagated from the inputs to the outputs of the gates using, the relations shown in figure 3.8.

!"# !$# !%#& !"#' !$# !"# !$# !%#& !"#( !$#) !"#' !$# !%#& !"#'!*) !$##( !$#'!*) !"## !"# !%#&*) !"# +,- ",. /0 1/0 !"# !$# !%# !%# !%# !%# Figure 3.8: Forward Propagation of Signal Probabilities
Next, the detection probability of faults is calculated. These are computed separately for faults causing a signal to transition to '1', denoted DP 1(i),a n d those causing a signal to transition to '0', denoted DP 0(i) . This is done working backwards from the primary outputs. The detection probabilities, DP 0(Y ) and DP 1(Y ) of a primary output, Y ,a r es i m p l eP (Y ) and 1 -P (Y ), respectively. Then, using the relations shown in figure 3.9, the detection probabilities can be propagated backward through the network. The classic problem with probabilistic approaches is how to handle reconvergent paths as shown in figure 3.10. In this example, at E, conflicting detection probabilities are propagated backward from D and from C. To handle this case, a common assumption is to take the maximum of the detection probabilities from the upstream nodes, although this overestimates the detection probability.

!"# !$# % & '( )% &!*#+ !"#+ !$# % , '( )% ,!*#+ !"#+ !$# !"# !$# % & '( )% &!*#+!,-!"##+!,-!$## % , '( )% ,!*#+!,-!"##+!,-!$## % & '( )% &!*# % , '( )% ,!*# % '( )% ,!*# % '( )% &!*# ./0 "/% 12 312 !"# !$# % &!*# % ,!*# !"# % &!*# % ,!*# % &!*# % ,!*# % &!*# % ,!*#
Beyond simply using probabilistic analysis techniques to compute the LDR of the gates in a network, recent work [Hayes 2007, Polian 2008] has studied how to rank gates for selective hardening. In the first paper, exact solutions for computing which gates to harden are presented for small circuits. In the followup, a faster approximate technique is presented which is able to rank gates for selectively hardening and handle large circuits with over 2 million gates.

Comparison of Analysis Techniques

In the first half of this chapter, many techniques for analyzing the effects of soft errors have been reviewed. In order to compare the techniques a set of qualitative criteria have been identified.

1. SEU indicates whether the technique can evaluate the effect of SEUs. Eight different techniques were compared based on these criteria and the results are summarized in table 3.3. The row labelled 'Sim. Basic' refers to the simple fault simulation approach that is illustrated in figure 3.3(a) and the row labelled 'Sim. Adv.' refers to the simulation approach shown in figure 3.3(b). The difference between these techniques lies in how the results are analyzed. Through the use of an intelligent test-bench, it is possible to assess the functional effect of faults. Although simulation based fault injection runs slowly, there is no hard limit on the size of designs that can be simulated.

To conclude, simulation based fault injection provides the most general means to evaluate the effect of faults. Emulation is attractive when the scale limitations are acceptable. Analytical techniques have an important role in specific cases; for example AV F is valuable when evaluating processors at the architectural level. work [Chen 2011]h a ss t u d i e dR T L -l e v e lp r o p a g a t i o n . e In some work using formal techniques, [Seshia 2007], the requirements are expressed formally. In this way, only faults that cause the functional specification to be violated are flagged as errors and FDR is thus taken into account.

Networking Case Study

In this section, the results of a detailed analysis of the effects SEUs in flip-flops for three large design blocks totalling over a half million flip-flops taken from a 40nm commercial NP ASIC is presented. The objective of the analysis is to determine the expected rate of specific classes of system failures when a large population of routers is deployed in a network. The RAMs in these designs were fully protected by ECC and memories with large interleaving were selected to avoid MBUs so flip-flop SEUs were the dominant SER failure mechanism. Table 3.4 shows the flip-flop counts and major function of the three blocks that were studied.

Temporal De-Rating

The concept of TDR was introduced in section 1.3.2. Given the scale of the design blocks, performing fault-injections with a gate-level netlist is not practical. In RTL level simulation, there are no delays thus the effect of TDR is not modelled. For this reason, the TDR analysis is done separately from the fault-injection analysis.

The TDR values for the flip-flops in all three blocks were calculated using Static Timing Analysis (STA) with Synopsys Primetime to extract the post-route timing.

For each flip-flop, the delay to all end-points was obtained and the ratio of the path with the greatest slack to the clock period was used to calculate the TDR. This process was repeated for all flip-flops both at the fastest and the slowest timing corners and histograms of the results for epsilon, omega and gamma are shown in figure 3.11. The TDR value is shown on the abscissa and the number of paths with that TDR value is shown vertically. Table 3.5 shows the average temporal de-rating factors for the three blocks. At the slow process corner, the TDR is numerically lower because the fraction of time that the flip-flops are vulnerable is smaller. The three blocks being studied are all located in the same clock domain. It is interesting to note, that even at the slow timing corner, the effect of TDR is less than a factor of two.

Classifying Failure Effects

A classification of soft errors effects for micro-processors is proposed in [START_REF] Nguyen | [END_REF]] based on the following categories: 1) masked errors , 2) correctable errors, 3) DUE and 4) SDC. This classification was adapted to the networking application. It is important to make a distinction between two cases. A SEU may be logically masked, meaning that after 1..N clock cycles, the errored state is over-written and the design returns to the logical state which it would have had if the error had not occurred (e.g. golden state). An error can also be functionally masked, meaning that the circuit state remains permanently altered, however, the resulting output sequence still meets all the system level requirements. This could be because the upset occurs in a piece of circuitry that is not active and has no effect or because the output sequence is slightly modified, but is still correct. In some work, these cases are viewed as latent faults [Berrojo 2002b], since it is possible that some set of stimuli might eventually sensitize the modified state and produce a failure. From manual analysis of the simulations that produced functionally masked outcomes in the circuits under study, it was observed that these cases typically corresponded to upsets in debug-type circuitry not used in mission mode. It is interesting to note that a fault analysis technique that only looks at the structure of a circuit, without knowledge of the intended function would not be able to identify the functionally masked scenarios. Some SEUs are corrected due to ECC logic. This is the case of flip-flops on a memory data-path after the ECC generation and prior to the ECC check and correct logic. The corrected case is distinguished from the logically masked case, because in the blocks under study, correctable ECC errors result in an interrupt being flagged. This interrupt causes the testbench to "fail", as it does not expect to see these interrupts during the simulation. In the field, however, upsets in these flip-flops would be indistinguishable from SEUs in the actually RAM.

Some SEUs are explicitly detected through mechanisms such as parity. These errors are not correctable and require a reset to bring the device back into normal operation. Such failures are classified as being detected explicitly since it is clear that they are the result of a soft error effect. Sometimes, however, a SEU may provoke a detectable error through a side-effect which is classified as being detected indirectly. For example, if a FIFO pointer is corrupted, it may trigger the overflow detection logic for the FIFO. In the system, such an interrupt would result in a chip reset and traffic would resume after an outage. In these cases, it is not possible to attribute the cause of the interrupt to a soft error effect and in the field such an event might be misdiagnosed as defective hardware or as the occurrence of a rare hardware or software bug.

The remainder of the failures are deemed silent errors, however, the special case where the effect is a one time corruption of a packet or a statistics counter is explicitly called out. Although this is not a desirable outcome, it may go unnoticed in a core network application. The other silent error cases are more serious, where internal hardware state such as pointers, linked-lists, etc. are corrupted and where the chip is likely to start operating in an unpredictable fashion. In certain cases, the packet traffic ceases to flow, resulting in a testbench timeout, and these are classified as silent lockups.T a b l e3.6 summarizes the fault classifications.

Testbench Environment

The functional verification of blocks within an ASIC is normally done using a testbench environment with random stimulus and scoreboard-based result checking. Since the result checking is done at a high level of abstraction (e.g. packets, transactions), the testbench is tolerant of minor changes in the output sequence, provided the functional requirements are still met. If the testbench determines that the design is behaving incorrectly, an error message is reported in the simulation log file and usually the simulation is terminated.

In order to associate test-bench failures to the resulting system effect, each of the error messages reported by the testbench environment must be manually mapped to one of the categories in table 3.6. For example, if an injected SEU triggers a testbench error due to an unexpected FIFO overflow interrupt, then it would classified as an indirectly detected SEU effect. This mapping is performed by building a set of rules using regular expressions that matched the error messages in the simulation log files. In this way, one rule can be used to match a series of similar error messages. Using these rules, the result of a fault injection campaign can be analyzed to determine the likelihood of occurrence of different SEU effects.

Simulation Speedup and CPU Efficiency

In a typical functional verification environment, the RTL description of the block is simulated using a testcase that goes through a series of timeline steps in order to reset the device, perform configuration, apply stimulus, stop the stimulus and then audit the state of the design (e.g. check all FIFOs are empty, check the value of all packet counters, etc.). It must be ensured that the SEU injections occur during the window of time when the design is fully active and processing data so that the results are representative of a system operating in the field. It is wasteful to re-simulate the entire reset and configuration sequence for each fault simulation and the first optimization consists of storing the simulator state just prior to the It is well known that a large fraction of SEUs are logically masked because they are either not captured in a downstream flip-flop during the cycle of the upset or because after some number of cycles, the errored state is overwritten [Berrojo 2002b]. After this occurs, the internal design state has returned to the golden state. Continuing to run the simulation beyond this point is wasteful. In order to determine that the design has returned to the golden state, we need a means to compare the golden state with the state during a fault simulation. Storing the full design state over a large number of clocks requires significant disk space and accessing the data introduces an I/O bottleneck. Instead, we propose a new technique where a Cyclical Redundancy Check (CRC) is calculated over the entire design state (both flip-flops and memories) and stored in a text file file during a series of initial golden simulation runs. During the fault simulation, periodically after the SEU injection, the same CRC is computed over the design state and compared with the value stored in the text file during the golden simulation. If the values match, the design has returned to the golden state and the simulation can be terminated, with the knowledge that the outcome would have been a PASS, had it run to completion as illustrated in figure 3.12. If multiple state bits in the fault simulation differ with the golden simulation, there is a small risk that the CRC-32 could alias and produce a false match. The probability of an alias never exceeds 1 in 2 32 and thus represents a much smaller source of error than that which is intrinsic from the statistical sampling of the faults.

There is a compute overhead to calculating the CRC over the design state. Since we know a large fraction of the faults disappear quickly, we chose to compute the CRC every clock cycle for the first 100 clocks and then only every 100 th clock cycle for the remainder of the simulation. By initially checking the state every clock, we are able to accurately determine how quickly faults are overwritten in the window after the fault injection. Beyond this initial window of time after the fault, there is little to be gained from frequently comparing the design state. In the worst case, a simulation will continue to run 99 clocks after its state has re-converged, before the next comparison. In [Berrojo 2002b], a similar approach was used and the period for performing the checking was increased exponentially after the fault injection.

The combination of both techniques (checkpointing and early termination on state matching) provides an average speed-up for fault injection simulation ranging between 8x to 12x. Faults simulations that produce a testbench failure as well as those that re-converge to the golden state terminate early and therefore require less CPU time. In fact, during a fault injection campaign, a large fraction of the CPU time is devoted to simulating faults that don't re-converge to the golden state but which produce no error as shown in table 3.7. Although the passing cases with no golden match represent between 7%-15% of the simulation runs, they account for between 40%-55% of the CPU time.

Logical De-Rating Results

Logical de-rating occurs when the corrupted value resulting from an SEU is overwritten. This can occur in the clock cycle of the upset, which we refer to as LDR 1 , The abscissa of the graph in figure 3.13 is the number of clock cycles after the upset event. On the vertical axis, the cumulative percentage of simulation runs that have converged with the golden state is shown for each of the three blocks. It can be observed that a significant number of upsets never get sampled (N=1) and it is interesting to note that this percentage varies significantly between omega (23%) and epsilon (45%). A second observation is that some upsets remain present for thousands of clock cycles before being overwritten. The cases where the upset persists for an extended period of time require more time to simulate. The results of the fault injection simulations are summarized in table 3.8. The confidence intervals were computed using equation 3.3. The distribution of SEU effects between the blocks is fairly similar, however, it is clear that epsilon is, overall, a less sensitive design. Gamma and omega manipulate complex data-structures such as linked lists and free-pools and it is thus more likely that SEUs will have a serious effect. These blocks also have some parity-protected flop-based structures, thus a larger fraction of SEUs are explicitly detected.

Summary of Simulation Results

Combining the Results

Returning to the Internet router system level specification [Silburt 2009], the most critical outage category are those failures that produce an unknown effect which have been classified as silent major and silent lockup in table 3.6.F r o mt h er e s u l t so f the fault injection simulation campaign, we know the fraction of SEUs that produce such failures. As a safe bound, we know this fraction can be further reduced by the TDR at the fast timing corner and these results are summarized in table 3.9.

71

These results, combined with the technology soft error rate, can be used to predict the expected types of failures in the field. The data in table 3.9, also suggests that only a small fraction of flip-flops produce serious outages and thus selective hardening of this small set of flip-flops could produce a significant improvement in the rate of serious failures. Extension of this work to select critical flip-flops is discussed in chapter 4.

Statistical Analysis of Fault Injection Results

Statistical Fault Injection (SFI) provides a means to estimate the probability that faults cause errors. The variance of this estimate depends on the number of experiments that are performed and when presenting results of SFI campaigns, it is essential to report the error bars.

When we perform a series of fault-injection simulation runs in order to estimate the probability, p, of a given outcome, we are performing a series of Bernoulli trials. A Bernouilli trial is a random experiment that can have one of two outcomes. If the i th simulation run produces the given outcome, we define the random variable X i =1otherwise X i =0 . It is intuitively clear that, p, the best estimator of p, after n trials, is given by equation 3.1. After each simulation we can compute pn and plot the value to observe the convergence trend.

pn = 1 n n i=1 X i (3.1)
In our experiments, the full sample space consists of all the flip-flops in the block (≈ 10 5 ) sampled over a temporal window of 100 clocks considered for nine workloads and is thus large (N ≈ 10 8 ) compared to the number of simulation runs (n = 10 5 ) and therefore we assume an infinite population size 2 .

The variance of a Bernoulli random variable is p • (p -1). There are different ways to estimate a confidence interval for a given value of α which is the level of confidence. α =0.05 for a 95% confidence interval. A very loose confidence interval which does not depend on the central limit theorem is given by Hoeffding's inequality [Wasserman 2005, p. 65] as shown in equation 3.2.

pn ± 1 2n log( 2 α ) (3.2)
If we assume that the distribution of pn is normal, which for large values of n is true due to the central limit theorem, then a tighter confidence interval [Wasserman 2005, p. 130] is given by equation 3.3. The interval depends on pn , the current estimate of p after n simulations. z α/2 is the abscissa value where the area under standard normal distribution, up to that point, is equal to 1α/2 and can easily be found 2 We can apply a finite population correction factor of N -n N -1 to the confidence intervals, however, for a large sample space this is ≈ 1.

in standard tables [Trivedi 1982]. z alpha/2 is 1.96, 1.65 and 1.28 for 95%, 90% and 80% confidence intervals, respectively.

pn ± z α/2 pn (1 -pn ) n (3.3)
For small values of n, this bound is tighter if the student-T distribution [Johnson 2000, p. 213-214], is used in equation 3.3 instead of z α/2 as shown in equation 3.4.F o r large values of n, the student-T distribution converges to the normal distribution.

pn ± t α,n pn (1 -pn ) n (3.4)
The disadvantage with these two confidence bounds is that the interval depends on the estimated value of p.I n [START_REF] Leveugle | [END_REF]], it is observed that the largest interval occurs when p =0 .5, and thus a conservative confidence interval is proposed by always substituting p =0 .5 in equation 3.3, instead of the current estimated value of p.

In order to evaluate the different confidence intervals, we plotted pn versus the number of simulations, with each of the confidence intervals. The analysis was only performed for n ≥ 10 since with fewer than 10 samples it is difficult to draw accurate conclusions.

Since we only ran a finite number of simulations, we take the final estimate of p after 10,000 to be the "correct" value. In figure 3.14, we plot the estimated value of pi through the course of 10,000 simulation runs, where p is the probability that an SEU will be logically masked in epsilon. We see that most of the time the confidence interval does indeed cover the final estimated value of 71.45%, although for n between 30 and 50, the upper bound falls below the final estimate.

This analysis was performed for each of the SEU effects identified in table 3.6 for each of the three design blocks. For each confidence interval, we computed the percentage of the time the final estimate of p is captured within the given confidence interval, through the course of the simulation campaign. These results are summarized in table 3.10. In figure 3.15, we plot all four intervals for the estimated probability that an SEU is Indirectly Detected in epsilon. From the results, we see that all four intervals do indeed provide a 95% confidence interval for the estimated value of p. The *+,-./01,2. +3 4567816. +3 915:.; <+0721==> *16.0+/> ?@,,7,0 216.0+/>A915:.;A<+0721==> ?167+ <+B./ )%C *+,37;.,2. D E+/81=F GH.567816.I JGG./ )%C *+,37;.,2. D E+/81=F GH.567816.I K7,1= 4567816. L M'!$(I E@8N./O+3OP78@=167+,O?@,5 *+,-./01,2.O+3O4567816.O+3O<+0721==>O915:.;OK1@=65 Q./2.,610.O<+ 0721==>O915:.; OK1@=65 Hoefding inequality provides a very weak bound, but in all cases it covers the final estimate. Using a normal distribution with p =0 .5 provides a tighter bound that nearly always covers the estimated value. The student-T distribution provides the tightest interval and it is still correct over 95% of the time.

Conclusions

There is a very broad body of work that addresses the problem of analyzing whether faults manifest themselves as errors, and if so, as what type of errors. In this chapter, we presented a brief overview of the existing work on fault effect analysis as well as a detailed case study of the effect of faults on large design blocks taken from a NP. Part of the simulation based analysis included the development of a new, fast technique to quickly determine when a faulty simulation has re-converged with the golden trace, in order to avoid unnecessary simulation cycles. An analysis of the CPU time usage during the simulations showed that the majority of the CPU time is devoted to simulating cases where a latent fault persists until the end of the simulation. The case study also included an analysis and comparison of different error bounds on the estimate error rates. Most importantly, this case study presented a detailed SER analysis for design blocks much larger than those typically studied in the published literature.

Chapter 3. Single Event Effect Analysis

! " # $ % & ' ! ! ! !
()*+, -% . /)0123+04+ 5 6),789: ;<+=>278>+ ?;;+, -% . /)0123+04+ 5 6),789: ;<+=>278>+ ()*+, -% . /)0123+04+ 5 @)+11320A B0+CD892>E ?;;+, -% . /)0123+04+ 5 @)+11320A B0+CD892>E ()*+, -% . /)0123+04+ 5 F>D3+0> G5H2=>,2ID>2)0 ?;;+, -% . /)0123+04+ 5 F>D3+0> G5H2=>,2ID>2)0 ()*+, -% . /)0123+04+ 5 6),789 ;< J% ?;;+, -% . /)0123+04+ 5 6),789 ;< J% K2089 L=>278>+ M!#J 'N O+,4+0>8A+P)1PF27D98>2)0=PO,)3D420APB7;9242>+9EPH+>+4>+3PQD>)7+= 6D7I+,P)1PF27D98>2)0PRD0= O+,4+0>8A+PB7;9242>+9EPH+>+4>+3PQD>4)7+= Techniques for Clustering Critical Flip-Flops Contents

Introduction

As seen in the case study presented in chapter 3, flip-flops are a major contributor to the overall soft error budget of large integrated circuits. It is well known that selectively hardening a small percentage of the flip-flops can significantly reduce the effective error rate. In commercial processors used in server applications, selective hardening is common practice and this has been well documented for the Itanium family of processors [START_REF] Naffziger | [END_REF][START_REF] Stackhouse | [END_REF]]. The challenge is to identify the best set of flip-flops to harden. Current process technologies make it possible to integrate tens of millions of flip-flops into a single SoC and within a few years, chips will have over a hundred million flip-flops, as shown by the trends illustrated in section 1.4. Thus, the effects the RTL level employing the environment used for functional verification making it possible to evaluate the system-level impact of errors. For the industrial designs, a selection of three testcases (e.g. workloads) was used and for the 10GE MAC, the supplied Verilog testbench was used. The focus of this analysis is on SEUs in flip-flops, so the fault injection mechanism consisted of inverting the value stored in a flip-flop (Verilog reg )u s i n gas i m u l a t o rVPI routine. The list of flip-flops was obtained from a synthesized gate-level net-list and projected back onto the corresponding RTL signals. The time of the fault was randomized uniformly over the active region of the test-case. For the flat simulation campaign, the selection of the flip-flops was uniform.

Different networking applications have different reliability requirements. In the public Internet, important data is protected with strong checksums, thus an infrequent payload corruption can be tolerated. If the effect of the SEU causes the circuit to stop forwarding data or to start continuously corrupting data, then it is deemed critical. The latter failures are highly problematic and the goal of mitigation is to reduce their rate of occurence.

When routers and switches are used in private data-centres or in High Performance Computing (HPC) systems, the reliability constraints are different. Here, SDC is not acceptable, as the packets are carrying data between compute nodes and there are not necessarily application level checks on the data.

The designs studied in this section are from Internet networking applications and the results of the simulations are classified into three categories as shown in table 4.2. In these applications, if the effect of the SEU is a one-time corruption of a packet, it is deemed minor.

The results of the flat fault-injection campaign are presented in table 4.3.9 0 % confidence intervals are computed using equation 4.1 where n is the number of simulations and pn is the estimated probability [Wasserman 2005,p .1 3 0 ] . I tw a s also confirmed visually that the error rates had converged. The probability of critical outcomes is low, but the absolute rate of critical failures remains unacceptably high. The focus of the mitigation effort is to minimize the critical failure rate.

pn ± z α/2 pn (1 -pn ) n (4.1)

Pass

Test-bench passes. The upset was masked.

Minor Impact

Test-bench fails. Error messages show the effect is a one-time payload corruption or there is a detectable interrupt.

Critical Impact

Test-bench fails and the error messages indicate that packets have stopped flowing or are being continuously corrupted.

Static Clustering Techniques

Real-world designs are structured and contain buses, module hierarchy and often have repeated instances of the same module. This information is extracted through analysis of the RTL code and exploited to group the flip-flops into clusters likely to have similar functions and thus a similar sensitivity to errors. Three clustering techniques are outlined below followed by the results of targetted SFI campaigns.

Bus Based Clustering

In the HDL description of large circuits, most registers are declared as a bus or vector (e.g. reg[31:0] PC) and have a similar function. For example, all the bits within the program counter of a processor would be equally sensitive to upsets. In the designs under study, over 90% of the flip-flops are part of a bus and the average bus size is between 14 and 20 bits. Table 4.4 shows the number of buses extracted from each design. The size of the clusters is not uniform and it is observed that a few large clusters dominate, therefore, the number of clusters that must be considered to cover 80% of the flip-flops is presented as an indication of the number of large clusters.

The main problem with this approach is the discrete flip-flops which are not part of a bus. In all the designs, these represent less than 10% of the flip-flops, however, these are often control signals and thus critical.

Hybrid Clustering

The third clustering scheme is an extension of the two previous ones. A distance function is defined to evaluate the "proximity" of two flip-flops. The function is defined so that flip-flops in the same bus and flip-flops which have the same signal name, but which are in different instance hierarchies (e.g. a.b.c.block_enable and d.e.f.block_enable) have a small distance. Pairs of flip-flops whose names differ by only one or or two characters (e.g. a.b.c.r_ptr and a.b.c.w_ptr )a l s oh a v eas m a l l distance. This heuristic makes it possible to group signals differing only in their suffix (e.g. wr_en_a and wr_en_b) that likely have similar functions. As the differences in hierarchy and signal name increase, so does the inter-flop distance function.

Using the distance function, clustering is performed using an agglomerative clus-tering algorithm [Everitt 1993]. Initially, there is one flip-flop per cluster; then those clusters whose distance is minimal are iteratively merged until a specified number of clusters is achieved. Currently, the target number of clusters was selected manually to ensure that similar signals were combined but to prevent unrelated signals being clustered. For example, read and write pointers from multiple FIFOs were combined into a single cluster. The results of applying the hybrid clustering algorithm are shown in table 4.6 and it is seen that large clusters are acheived for the industrial designs.

Simulation Results

A clustered fault injection campaign was performed using each technique on the three designs. To both ensure that large clusters are classified accurately and to avoid running excessive simulations for small clusters, the following policy was established: for a cluster containing N flip-flops, N/5 fault-injections were performed, with a minimum of 3 and a maximum of 15 runs. This policy allocates more simulation runs to larger clusters in order to minimize the risk of mis-classifying a large cluster. With 15 fault injections, the risk of mis-classification is very low, thus by establishing a ceiling, unnecessary runs are avoided.

Bus Based Clustering

The Chapter 4. Techniques for Clustering Critical Flip-Flops There are many buses in Epsilon that are sensitive, producing a critical simulation outcome on nearly every fault.

! " # $ % %! %" %# %$ ! !! !" !# !$ & &! &" &# &$ " "! "" "# "$ % ! & " ' # ( $ )

Hierarchical Clustering

The results of hierarchical clustering on the 10GE MAC (see figure 4.5), show that the design is too small to use module hierarchy to cluster critical flip-flops. However, with hierarchical clustering on Epsilon (see figure 4.6), after 4,284 simulations it was found that only 59 out of 580 module instances, representing 14,471 flip-flops (14.1%), resulted in any critical failures. When hybrid clustering was applied to Epsilon, after only 2,100 simulations, it was found that just 24 of the 209 clusters, representing 4,248 flip-flops (4.1%), resulted in a critical failure, as shown in figure 4.8. The results for Omega are presented in figure 4.9. This design unit processes data-structures based on linked-lists, so it is expected that many sensitive clusters are observed.

! " # $ % %! %" %# %$ ! !! !" !# !$ & &! &" &# &$ " "! "" "# "$ % ! & " ' # ( $ )
!" " #" $ $!" $" $#" ! !!" !" !#" % %!" %" %#" & &!" &" &#" " $ ! % & " ' # ( ) $ $ $ $ $ $ $ *+,-./
! " # $ % %! %" %# %$ ! !! !" !# !$ & &! &" &# &$ " "! "" "# "$ % ! & " ' # ( $ )

Selective Mitigation

The results from the clustered fault-injection runs can now be used to develop mitigation policies. A policy consists of selecting an approach to protect a set of flipflops. The protection could be achieved by substitution with hardened cells, TMR or other other types of hardened sequentials discussed in chapter 2. For simplicity, it is assumed that after mitigation, the SEU sensitivity is zero, but this assumption is easily relaxed. The sensitivity of the hardened design can now be evaluated without any further simulations by re-analyzing the results from the original flat campaign. Where one of the mitigated flip-flops was randomly selected in the original campaign, the analysis is updated as if the outcome had been a pass. This approach is valid because the flat campaign has run without any knowledge of the clustering and thus the sampling is uniform across the design.

In order to clearly validate the new approach, an independent flat analysis was performed. In fact, the flat analysis is not strictly necessary and it is possible to simply perform a single, clustered fault injection campaign. The results of this campaign can be used to both assess the initial design sensitivity and to assess the sensitivity of the mitigated design. This simplification comes at the expense of an independent verification of the results.

Full Mitigation

The simplest policy is to just protect all the flip-flops in all the clusters which showed any critical failures. This provides an upper bound on the level of improvement that can be obtained. Table 4.7 shows the reduced critical sensitivity (the new percentage and the factor reduction compared to the original results in table 4.3) and the percentage of protected flip-flops to obtain the improvement.

Partial Mitigation

In practice, the goal is to achieve a reliability target with a minimum cost so it may be unnecessary to protect all clusters. The effect on the sensitivity of the designs was evaluated with various percentages of flip-flops being protected. The flip-flops to protect were selected starting with the most sensitive clusters first. The results for Epsilon and Omega are shown in figures 4.10 and 4.11. The error bars show the 90% confidence interval for the mitigated design. It is clearly possible to trade-off soft error sensitivity with the number of protected flip-flops and the steeper slope on the left shows that the most critical clusters were identified. It is important to note that these multiple design points were obtained from the analysis of a single clustered fault-injection campaign. F.*,+./ ?+,+@.,+=2 G+,H I:3 )/:3,1*+2@ F.*,+./ ?+,+@.,+=2 G+,H J+1*.*-H+-./ )/:3,1*+2@ F.*,+./ ?+,+@.,+=2 G+,H J5<*+A )/:3,1*+2@ Bus-based clustering provides policies with the lowest cost due to the smaller cluster sizes, however, there is a limit to the improvement that can be achieved because the discrete signals are excluded from the analysis. Due to the larger cluster sizes, hierarchical clustering provides more costly mitigation policies than the hybrid clustering.

!"# !# !$# % %!"# %!# %!$# % " & ' # ( )*+,+-./ 0123+,

Discussion

When performing fault injections, the fault space is three dimensional with the axes being : time, space and work-load (simulation trace), as shown in figure 4.12. Certain flip-flops are critical every clock-cycle (e.g. reset signals, interrupts, etc.) while others are only critical when specific transactions are being processed. ,+>.-8?@4A75. 8B6BAC3.)DECA6.C6.6FB5.E?BG6.BG.6BD7 With this technique, only a small number of fault-injections per cluster are needed to determine that some flips-flops in the cluster are critical. With cluster sizes of several hundred flip-flops, this represents a significant reduction. However, with larger clusters, there is a risk that the elements are heterogeneous and that some non-critical flip-flops are protected unnecessarily. This is seen by the higher cost associated with the policies from hierarchical clustering. Hybrid clustering was better able to group flip-flops with similar sensitivity.

The bus-based clusters are smaller but exclude flip-flops that are not bussed (10% of the flip-flops in the examples). With Epsilon, a maximum of 3x reduction in critical failures was possible with bus-based clustering compared to a 7x reduction with hybrid clustering. In figure 4.10, it is seen that with the finer granularity of the bus-based clustering, a slightly better reliability improvement is obtained, for a given number of protected flip-flops, but this comes with the cost of more simulations.

The proposed techniques are based on heuristics and the quality of the results is subject to implementation style, however, interesting results have been obtained on both small and large designs. Without simplifying assumptions, the problem of identifying critical flip-flops in a large design remains overly compute intensive. The circuits selected here are from networking applications, however, other types of designs such as processors have similar characteristics : presence of buses, module hierarchy and reasonable signal naming conventions, thus it is expected comparable results would be obtained.

Conclusions

In this chapter, it has been shown how clustering techniques based on design structure combined with limited fault injection simulations can be used to identify sensitive nodes. No assumptions are made about the design other than the availability of a functional test-bench used to assess the impact of SEU faults. The techniques were applied to sequential circuits with hundreds of thousands of flip-flops. Using the results from a single, clustered, fault-injection campaign, a range of mitigation policies can be developed.

Future work in this area will focus on identifying improved clustering approaches that exploit the connectivity and data-flow within the design as well as applying the techniques to a broader class of circuits. Another direction of future work relates to better optimizing the number of simulations.

Introduction

In section 1.4.1, it was shown that due to both design trends and technology scaling, SETs represent an increasing fraction of the overall SER of large SoCs. Accurately estimating this component is important but remains a challenging problem for full designs with tens or hundreds of millions of gates.

The majority of the existing work on SET analysis starts from a gate-level circuit representation, however, in an industrial design cycle, by the time a gate-level net-list is available, it is too late to make significant design changes. The hierarchical SET analysis methodology described in this chapter can be applied at the RTL level. This methodology, was initially published in [START_REF] Evans | [END_REF]]usingSER results obtained for the NanGate 45nm library. An extended version of the methodology was then developed under contract to a major networking company and was delivered in the form of a spreadsheet that can be used to estimate combinatorial SER. The commercial implementation used SER data obtained from simulations performed on a commercial 28nm cell library.

In this methodology, the SET sensitivity of the cell library and the masking characteristics of standard combinatorial design blocks are pre-characterized and stored in compact models. Then, the SET sensitivity of a complex circuit is calculated by decomposing it into blocks that have been pre-characterized. These block-level models are combined taking into account the data flow, to estimate the overall SET sensitivity. Experimental results for an ALU implemented in the NanGate 45nm library as well as partial results from the analysis of a commercial 28nm cell library are presented.

The starting point for this approach is to simulate the SET sensitivity of the combinatorial cells in the library, or at least for a representative subset. These simulations are done using a SER simulation tool and, for each cell, the result is a histogram showing the FIT rate for pulses of different widths. This step is important as the sensitivity of different cell types (INV, AND2, XOR3) can vary significantly. Due to the fact that the final analysis is done at the RTL level, this large data set is then distilled into a compact summary of the SET sensitivity for different classes of cells.

Separately, the circuit and masking characteristics of standard combinatorial blocks of the type inferred by an RTL synthesis engine (e.g. muxes, adders, etc.) are evaluated. Using the proposed methodology, the block-level models are combined with the library models to estimate the SET sensitivity of a complex combinatorial network. The proposed models are part of a chain of abstractions, as shown in figure 5.1. It is possible to output and store these models in a standard format such as RIIF [Evans 2012] which is described in chapter 6. With a standard format, it becomes possible for the intermediate models to be shared between Electronic Design Automation (EDA) tools thus automating the analysis flow.

Review of SET Masking

There are three reasons why SETs may not propagate and be sampled at a flipflop : LDR, TDR and EDR. These are outlined in section 1.3.

LDR measures the likelihood that the pulse will propagate through the logic network from a boolean perspective and is technology independent. For example, an upset at the input of an adder, will propagate to the output as the sum always depends on the inputs. In contrast, an upset at the input to a wide multiplexer, will only propagate if the affected input is selected, thus the error propagation probability is much lower.

In a ripple-adder implementation, upsets on any of the gates inside the adder will always propagate. This probability of faults on the internal gates of a circuit is referred to as the internal LDR. If we consider a Carry Lookahead Adder (CLA), however, upsets in the carry prediction logic may not propagate, if there is no carry. It is not necessary to have a gate-level implementation in order to assess the first order effects of LDR.

In [START_REF] Limbrick | [END_REF]], it is shown that the LDR, referred to as Error Propagation Probability (EPP), of a given circuit can vary based on the synthesis constraints that are applied. This work studied the effect of constraints on LDR but did not consider the variation in the intrinsic SER of the circuit. For example, the authors show a variation in LDR of between 0.14 and 0.20 (30%) based on varying timing constraints. However, the same constraint variations cause the cell count, and thus most likely the raw SET sensitivity, to vary by 500%. Therefore, the first order effect of synthesis constraints on SETs is the effect they have on the total gate count. The main reason for the variation, both in LDR and gate count, is certainly due to the synthesis engine selecting different circuit architectures based on the target frequency (e.g. CLA versus ripple adder). In the proposed methodology, this dependence on synthesis constraints is taken into account as different implementations of the same high-level logic function (e.g. adder) are considered to have different intrinsic SER rates and different LDR values.

To propagate, a transient must arrive at the input to one or more sequential elements when it is being sampled. TDR quantifies this probability and it was shown in section 1.3.2 that it can be effectively estimated as:

TDR SET = w=maxP W w=minP W w dw T clk (5.1)
EDR relates to the analog propagation of the pulse and is more difficult to analyze. One aspect of EDR is accounted for by considering how the induced analog pulse is mapped to a digital pulse. The shape of a radiation induced pulse is shown in figure 5.2 and based on the logic threshold voltage, it can be modeled as a digital pulse of width PW. Pulses whose amplitude never reaches Vthcan be ignored. The second aspect of EDR relates to the fact that when the pulse travels through the network, it may be attenuated or it may be stretched [START_REF] Cavrois | [END_REF]]a n dt h i si sn o t currently incorporated in the proposed methodology.

State of the Art

Many works have studied the effect of SETs, however, none has proposed an estimation methodology that starts from the RTL and that relies on pre-characterized models for high-level design blocks.

Some approaches are based on probabilistic techniques to estimate whether transients propagate due to LDR.I n [ Polian 2008] such a probablistic technique that consider re-convergence is presented and applied to very large circuits but neither TDR, EDR nor the intrinsic rate of SETs occuring is considered.

Other approaches are based on using on a gate-level event based simulator to evaluate the transient propagation. Algorithms to significantly accelerate gate-level transient fault simulations [START_REF] Alexandrescu | [END_REF]] have been presented and applied to moderate size circuits.

A very different approach is implemented in the MARS-C platform described in [START_REF] Miskov-Zivanov | [END_REF]. The authors propose a unified circuit representation that considers LDR, TDR, EDR using a combination of BDDs and ADDs to represent the sensitive paths to the outputs. The circuits that are evaluated include ISCAS benchmarks and the results are compared with SPICE analysis. The proposed datastructures can not scale to very large circuits and this work does not consider the variation in the intrinsic SET sensitivity of different gates.

The SEAT-DA and SEAT-LA platforms described in [START_REF] Rajaramant | [END_REF]]h a v e similarities to the work in this chapter. The SEAT-DA platform is used to calculate the neturon SET sensitivity of individual gates. The SEAT-LA tool uses SPICE to pre-characterize the pulse deformation and logic masking of indidivudal gates (LDR,EDR). The two tools are combined and used to perform SET analysis on IS-CAS benchmarks (≈ 1200 gates) and the results are compared to SPICE simulation. The SEAT-LA platform requires 1.4 min of CPU time to analyze the SER of a 4-bit ripple adder. This framework is further extended in [START_REF] Ramakrishnan | [END_REF], where the Hierarchical Soft Error Estimation Tool (HSEET) tool is presented. Instead of characterizing the logic masking and pulse transformation for individual gates, the idea is extended to small blocks (e.g. muxes). However, with HSEET the basic analysis still involves evaluating the propagation of pulses through a netlist and the results are presented for small circuits.

Other authors [Zhang 2006a, Rao 2006[START_REF] Wang | [END_REF][START_REF] Ramanarayanan | [END_REF]]ha ve presented accelerated SET analysis techniques but they all work at the gate level.

At the RTL level, soft errors are modeled as bit flips and their effects can be analyzed using fault injection [Gracia 2008[START_REF] Wang | [END_REF] or analytical techniques [START_REF] Li | [END_REF], Mukherjee 2005]. Some techniques [START_REF] Devadas | [END_REF][START_REF][END_REF]] have been proposed for error propagation analysis at the RTL level but they do not estimate the intrinsic rate of occurrence of SETs nor do they account for the TDR and EDR.

The remainder of the chapter is organized as follows: in section 5.2 the SET sensitivity of individual cells is analyzed. In section 5.3,theLDR of small circuit blocks is analyzed then in section 5.4 we present a complex circuit and perform a canonical analysis of its SET sensitivity. In section 5.5 we compute the SET sensitivity using the hierarchical approach and compare the results to the canonical analysis. In section 5.6 we summarize and consider future extensions to this technique.

Cell Level SET Characterization

Technology, Cell and Library Modeling

The first step in the methodology is to characterize the SET sensitivity of the process technology and cell library. In this work, the cell-level SER analysis is performed using TFIT [START_REF] Alexandrescu | [END_REF]], however, the overall methodology is not tied to this tool. With TFIT, the process technology is characterized using 3D TCAD simulations to yield a technology response model. Based on the radiative environment (atmospheric neutrons for terrestrial applications), a nuclear database is consulted to analyze the energy distribution of the particles and the nuclear interactions that occur with the materials to obtain a distribution of the different charge depositions that can occur. Separately, using the net-list and the layout for the cell, specifically-tailored transient current sources are added to the circuit netlist and simulated in Spice and the response of the cell is observed. This process is repeated for all the transistors in the circuit and all the possible circuit states. Using knowledge of the frequency of occurence of the underlying nuclear events and the circuit response obtained by Spice, a FIT rate for SETs of specific widths is computed.

Figure 5.3 shows the absolute FIT rates for pulses of different widths for four different cells taken from the 45nm NANGate Open cell library, including both the neutron and alpha contribution. In figure 5.4, the sensitivity of two different gates from a commercial 28nm library are shown. For confidentiality reasons, this data is presented with arbitrary units. In both cases, it is clear that the SET sensitivity can vary significantly between different gate types. This is further illustrated in figure 5.5 which compares the sensitivity of five different gates. Overall, in terrestrial applications, the upsets are dominated by short pulses (<=50ps).

In order to create a more compact model of the SET sensitivity of the library, the ) .

Data: FIT_Table[G, P W ] Compute Cumulative FIT totalF it ←-0 /* Compute Cumulative FIT */ foreach G in GateInstances do foreach PW in PulseWidths do totalF it ←-totalf it + FIT_T ABLE[G, P W ] end CumF itP erGate[G] ←-totalF it end /* Perform Fault Injection */ while ErrorInterval ≥ Threshold do /* Pick uniformly over all cases */ R ←-URandom(0..totalF it) G ← 0 /* Lookup Gate */ while R > CumF itP erGate[G] do G ← G +1 end R ←-R -CumF itP erGate[G] PW ←-minP W /* Lookup PW */ while R>FIT[G, P W ] do R ←-R -FIT_T ABLE[G, P W ] PW ←-PW + PWStepSize end Offset ←-Urandom(0..T clk ) /* In cycle */ Result ←-FaultInject(G, P W, T empOf f set) end Algorithm 1: Weighted SET Fault Injection
)9:

)/;<=>?123 ./;<=>?123 @

) .

./?A123

+,!= '8)B$ +,!- ) . ) . ) . ) .
) .

+,!= The total raw FIT rate of the gates was calculated to be 0.2173 FIT and then de-rated using the results of the fault injection campaign, shown in the column De-rated FIT. Using the observability of the simulator, the D-input to the output flops was monitored to see how many of the faults actually reached the output of the combinatorial network (after LDR and EDR) and this is reported in the column 'Not Blocked'. The pulses that are blocked in the runs without timing delays are blocked solely due to LDR. The additional pulses that are blocked with the SDF simulations are the result of EDR filtering of short pulses. Based on digital simulation, the average or statistical EDR for this circuit is approximately 2546/3272 = 0.78.

The width of the pulses exiting the combinatorial network could be longer or shorter than the original pulse, due to the reconvergence effects in the combinatorial logic. The column 'PW Ratio' shows the average ratio of the output pulse width to the original error pulse width. For those pulses that are not masked, on average the output pulse is about 50% longer.

Hierarchical Analysis of the Complex Circuit

In this section, we show how the effective SET FIT rate of the ALU circuit can be computed directly from the RTL using the methodology shown in figure 5.9. First the ALU circuit is decomposed into small combinatorial blocks, of the type that can be directly inferred by an RTL synthesis engine. Each of these blocks was synthesized using a generic (GTECH) library and the gate count and distribution of gate types obtained. The internal LDR of each of the small blocks was computed using fault injection and the resulting models for each block are shown in table 5.4. The generation of these models for standard logic blocks is a task that can be done in advance, as it is technology independent.

Combining the gate count and type distribution for each block with the results of the SET characterization of the target library (see table 5.1), an estimate of the raw intrinsic FIT rate for each of the small blocks was calculated, for different pulse widths. This is shown in the columns labelled 'Raw Intrinsic FIT'i nt a b l e5.4.

The raw intrinsic FIT of each block must be de-rated for LDR and TDR. The instrinc LDR has been pre-computed and is shown in the table. The SET intrinsic sensitivity has been pre-computed for different pulse widths (<50ps,50..75ps,>75ps) thus equation 1.3 can be applied as a discrete sum for each block to compute the de-rated, intrinsic FIT for each sub-block. Now we must address the question of how the combinatorial SET models for the small networks can be combined to estimate the SER of the entire ALU. Consider a more general network as shown in figure 5.10.

!"#! $%!&'() !"#! $%!&'($ !"#! $%!&'() !" !# !"#! $%!&'( !" !# Figure 5.10: Complex Combinatorial Network
Each block has its own de-rated, intrinsic SET contribution. The SETs in the final block (D) propagate directly to the outputs. The SETs in the upstream blocks may be logically masked, thus their internal contribution is reduced by the error propagation probability (EPP) along the path to the output. The EPP is computed for each path to the outputs and the resulting propagation model is shown in equation 5.2. Since the computed LDRs are averages over many input vectors, the correlation of vectors on reconvergent paths need not be considered.

SER Network =(IntSER A * EPP B * EPP D1 )+ (IntSER A * EPP C1 * EPP D2 )+ (IntSER B * EPP D1 )+ (IntSER C * EPP D2 )+ (IntSER D ) (5.2)
This approach was applied to the example ALU where the propagation probabilities of the branches are not equal due to the encoding of the op-codes which control the mux. The final estimated SET FIT rate for the ALU circuit, working from the RTL, is computed to be 0.76e-3 FIT which is only 15% higher than the value of 0.65e-3 FIT obtained from a fault-injection campaign on the flat-circuit without timing annotation as shown in table 5.3. Currently, the methodology does not model the pulse deformation due to EDR. It is possible to apply the EDR ratio and pulse stretching ratio obtained from the gate-level simulations to the estimated FIT rate : 0.76e-3 * 0.78 * 1.5 = 0.9e-3 which is slightly higher than the results obtained from flat simulation with SDF (0.73e-3). This is only valuable if it is expected the the EDR effects do not vary across circuits.

It may appear that the absolute FIT rate of the example circuit is extremely small and one might assume the effect of SETs is not significant. However, the ALU being studied has approximately 1800 gates. If we scale the computed SET FIT rate of 0.76e-3 FIT up to a circuit with 100M gates and reduce the TDR effect by 3.3x, based on an assumed operating frequency of 1 GHz instead of 300 MHz, the absolute FIT rate would become approximately 140 FIT. This value is not negligible and would definitely need to be carefully considered in a SER analysis. Note, that even after a SET is captured in one or more flip-flops, it is still subject to the de-rating factors that affect SEUs and thus this value must be further de-rated.

Conclusions

In this chapter, a hierarchical methodology to estimate the effect of SETs was presented. The approach started with a simulation-based characterization of the sensitivity of a cell-library. This was distilled into a compact summary. An approach to pre-characterize the LDR of common building-block circuits was presented. The LDR is not technology dependent and can thus be computed in advance. A methodology to decompose a large circuit into smaller blocks, to compute the SER of each block and then to combine the results was presented. When applied to the Open-RISC ALU, this methodology showed good correlation with the results obtained using fault-injection on a flat net-list.

As presented, the approach does not consider the impact of input vectors. Input vectors do play a role. The challenge is that the number of input states grows exponentially with the number of inputs. One practical approach to reduce the complexity would be to focus on the impact of control signals. In the example ALU circuit, it would have been relatively easy to extend the methodology to compute the SER sensitivity for any ALU operation. Thus, instead of a single SER response, there would be one per-operation or eight in the case of this circuit. This remains a tractable number, however, to make use of a more refined model, requires the ability to write-out the model and to propagate it upwards to the next level of design hiearchy. This is where RIIF models can play a role.

As presented, the methodology does not propose a predective EDR model. Of course this is important, but it is not clear to what level of accuracy EDR can be predicted at the RTL level.

Introduction

As seen in the introductory chapters, there exists an enormous body of work devoted to analyzing radiation effects and the propagation of faults to errors. However, there remains a significant gap between the state of the art in the research community and the best practices in industry, especially in terrestrial applications. One of the hurdles is the fact that there exists no framework for integrating the data about the rates of faults and de-rating factors. As a result, spreadsheets are commonly used to exchange such information [START_REF] Wong | [END_REF]]. For example, foundries and library providers often use spreadsheets to communicate the FIT rates of memory and logic cells. Fault-injection simulations are frequently used to evaluate the sensitivity of a design to faults and the results of such analysis is often archived in the form of spreadsheets [Arlat 2011]. Unfortunately, every spreadsheet is unique and combining data from multiple spreadsheets is a manual and error-prone process.

In this chapter, we review the propagation of low-level faults upwards through a system hierarchy and in the process, we identify the information that is required to model faults and how they propagate. The environment must be considered, as the operating conditions of a circuit (e.g. voltage, temperature, workload, etc.) play a key role in the determining the rate of occurence of faults as well as how the resulting errors eventually impact the system. The Domain-Specific Language [Fowler 2011] called Reliability Information Interchange Format (RIIF) is then presented. Three worked examples of systems modeled with RIIF are then presented.

The goals of the RIIF language are to:

• Enumerate the failure modes for components

• Specify the probability of the failure modes

• Specify the effect of operating parameters (e.g. voltage )

• Build composite components from simpler components

• Scale from cell level through to system-level

• Remain general purpose and not be tied to a single application domain

• Provide templates which standardize the specification of failures in commodity components (e.g. DRAMs, SRAMs).

• Specify standard operating conditions and environments for components

In industry, this type of reliability model has numerous direct applications, some examples of which are enumerated here.

1. When a component supplier provides a memory (e.g. SRAM, DRAM, TCAM) to a system company, they must deliver information about the soft error rates (e.g. SBU, MBU, SEFI, etc.). The rate of these events varies with parameters such as voltage, temperature, neutron flux and packaging options. It is beneficial for the system company to receive this information in a standard format so that they can quickly evaluate the reliability impact of selecting functionally equivalent components from different suppliers.

2.

Cell library providers run simulations (e.g. SPICE or TCAD ) and perform accelerated tests in order to determine the soft error susceptibility of the cells in their library. The number of cells in libraries is growing. For example, a frequently used commercial 28nm library contains hundreds of sequential cells and thousands of combinatorial cells. This information must be communicated in a machine readable format so that designers can compute the soft error rate of their circuits. Soft error rates vary significantly with voltage and the alpha contribution depends on the packaging options. There is also a strong correlation with voltage and a weaker correlation with process. To illustrate the importance of accurately characterizing each cell in a library, the simulated FIT rate (alpha plus neutron) of fourty different flip-flops from a commercial library are presented in figure 6.1.F r o mt h i sg r a p h , it is clear that there is a large variation between the different cells in the same library. Furthermore, the SER of the master and slave stages can vary significantly as shown by the results for CK =0and CK =1 . This need to perform accurate SER analysis which considers the SER characteristics of each cell was highlighted in [START_REF] Alexandrescu | [END_REF]].

!"#

!"$ %&' ()*+ ,-./.0 %1234%153 6*)*+ 7)82)*259 5: %1234%153 %&' ()*+; Figure 6.1: Variation of Flip-Flops SER for Cells from a 28nm Library In many ways, the problem is analagous to that of specifying the timing characteristics of standard cells which also depend on process, temperature and voltage. In the case of timing information, standard file formats, such as the Liberty [START_REF] Synopsys | Synopsys[END_REF]], already exist.

3.

When an IP provider delivers a complex block (e.g. processor core, Ethernet controller, etc.), there is a need for them to specify the failure modes and errors that can occur. This need for soft error models for IP blocks was identified in [START_REF] Aitken | [END_REF]]. A simplified view of the design flow for an automotive IC is shown in figure 6.2 and highlights the complexity of the industrial relationships. The SoC integrator needs to show compliance with reliability standards even though a large fraction of the IC design content comes from third parties. Therefore, they must have the means to produce an accurate reliability model for the SoC.

For example, if an IP block has parity protected structures, then there is a DUE failure mode whose rate of occurence depends on the number of bits that are protected and the LDR of the structure, both of which are technology independent. When this IP is mapped to a given technology, this information can be combined with the library soft error models to compute an absolute FIT rate. An example of this flow is presented in section 6.3.2.

4. When a system company designs a board which has multiple chips (as well as other components), there is a need to develop a comprehensive failure model for the board which includes both intermittent and permanent failure modes. Certain component level failure modes may not impact system reliability due to redundancy or error correction -so it is not possible to simply sum the FIT rates. There are different ways in which the board can fail (e.g. reboot, performance degradation, permanent failure), and it is necessary to individually compute the probability of each failure mode. It is important to preserve the relationship with the underlying component models so that the impact of changes to operating parameters (e.g. voltages and temperature) can be assessed. Although, there do exist industrial standards for evaluating the reliability of circuit cards [Telecordia 2011], they do not take into account fault mitigation techniques and they use a very simple model of failures in complex ICs based on a single FIT rate computed from the number of transistors. As a result, the Mean Time Between Failure (MTBF) values predicted by these standard techniques are often unnecessarily pessimistic.

6.2 Elements of the RIIF Language

Components and Parameters

The basic unit of enapsulation in RIIF is the component which is similar to a VHDL entity or a Verilog module and it can represent either a low-level circuit such as a logic gate or a complex entity such as a full SoC. Of course, a given circuit can operate under different conditions, and thus components have parameters which are similar to generics in VHDL. The parameters are typed (integer, float) and they may optionally have a value assigned when they are declared. The value of a parameter can be over-ridden when the component is used. RIIF also supports constants which are like parameters, with the difference that a value must be assigned when the constant is declared and this value can not be changed.

Failure Modes

With RIIF, the intent is to only model the faults in the system but not to model its normal functionality. The user declares failure_modes within the components.

A failure_mode represents an event that can occur and the purpose of RIIF is to calculate the rate of these events. In its current form, the language does not make the distinction between faults, errors and failures. The lack of such a distinction comes from the fact that the goal of the language is to be generic and span multiple layers of abstraction. A modification to the language to make this distinction explicit, is described in section 6.4.

Examples of common failure modes in a memory component would be a SBUs while in a CPU, SDC would be a failure_mode. Associated with each failure mode is a rate of occurence.

Complex Components

A complex component is built from one or more child components. The complex component has its own failure modes, whose rate of occurence is expressed as a function of the rates of the failure modes in the child components as well as the parameters in the complex component. The function which maps the rate of lower level failure modes to higher level failure modes can take into account the effects of error mitigation, error masking and redundancy as shown by the three examples which follow.

In figure 6.4(a),aS R A Mi st h echild component of a Single Error Correct, Double Error Detect (SECDED) memory. In this case, the SBU faults from the SRAM do not propagate and the MBU faults map directly to uncorrectable errors in the SECDED memory. In figure 6.4(b), a simple example of a model for SDC in a CPU is shown. The sum of the SEU rate in the N flip-flops is scaled by a single AV F factor to obtain the rate of SDC. Redundancy is often used to improve reliability and availability. In figure 6.4(c), the structure of a RIIF model for a RAID-1 disk array is shown. In this system, data is replicated across the N drives. As long as one of the drives is operational, the data can be retrieved, thus the probability of the array failing is the product of the rate of failure of each disk. The reliability of series, parallel and combined series parallel systems has been extensively studied. Well known, closed form expressions exist for simple systems and techniques to obtain bounds for complex systems have also been developed [Gertsbakh 1989, Chapter 1]. In RIIF, there are built-in functions (agg_single_fail, agg_gt_n_fail ) which compute these relationships. The RIIF code for the RAID example is shown in figure 6.5.

!"# !"# $% !"# #$% %&'())*'+,-.* /))() /01/12#*3()4 (a) Error Mitigation !" #$%&'#$(& )* "+* +, !"-./0#121+, )*- #$%&'#$(& )* #$%&'#$(& )* #$%&'#$(& )* 2 (b) Scaling of Fault Rates !!"#$%"&' ( )*$+$*&,-$ !!"# ."!/$*&,- *&,-$%"&' 000 ."!/$*&,- *&,-$%"&' 1 234"!!"#56234+57000723415 (c) Modeling Redundancy

Environments

The operating environment of an integrated circuit greatly impacts its reliability. The fact that RIIF components are parameterized provides a first step towards managing this dependence. However, maintaining models with a long list of parameters is not scalable. Furthermore, if different users define different sets of parameters for the same class of device, then they are no longer modular. There is thus a need to encapsulate a set of related parameters to define an environment. Essentially, an environment is similar to a 'C' struct and serves to encapsulate a set of parameters. Going forward, RIIF implementations of standard environments can be defined, protected with SECDED ECC so that single-bit errors have no impact. When there is an intermittent multi-bit error (MBE), the board is rebooted, but continues operation. Due to N +1 : N redundancy on the memory parts, if there is a permanent failure on one RAM, the board can continue to operate with N components, although the switch-over requires a reboot. If two or more RAMs fail, then the board must be replaced. The structure of the system is shown in figure 6.7.

!"##$ !%&'(! )*+,"#'-.
/ 01234356 First, the RIIF code for the SRAM is presented in figure 6.8. In this model, the SRAM has three failure modes : SBU, MBU and CHIP_FAIL. The equation for the SBU rates is taken from [START_REF] Seifert | [END_REF]]a n dt h eMBU rate is computed as a fixed ratio of the SBUs. Then, the rate of permanent chip failues is calculated as a function of the operating temperature. It is important to note, that the purpose of RIIF is not to propose specific models for silicon failure mechanisms. This topic has been extensively studied and standard equations exist for known silicon failure mechanisms [START_REF] Jedec | [END_REF]]. Instead the purpose of RIIF, is to provide a scalable, machine-readable format for such models.

Next the model for the board is created, as shown in figure 6.9. The failure modes at the board level are reboots and board replacements. The board is rebooted if there is an MBU in one of the active memories or if a permanent memory error causes a switch-over to the spare memory part. The board must be replaced if either the CPU fails or if more than one memory part fails.

Soft IP Example

The example in this section illustrates how a model for a soft processor core can be specified. The high-level failure modes of interest for this core are SDC and DUE. The SoC integrator is interested in determining the absolute FIT rate for SDC and DUE in their implementation technology. These FIT rates can then be fed into a system level reliability or safety analysis.

The SoC integrator, through their relationship with the foundry and the memory IP provider, has access to the technology failure rate (e.g. FIT/Mbit for memories, flip-flops) but they lack detailed knowledge of the processor core architecture. We show how the IP provider can deliver a technology-independent RIIF model of the core. This model is then extended with the models for the technology failure rates to compute the absolute FIT rates.

In this example, we assume there are four technology level faults :

• SBUs in the cache memory

• MBUs in the cache memory

• SEUs in the normal flip-flops

• SEUs in the hardened flip-flops

As is the case with many IPs, the core is configurable. The user can choose from different protection strategies for the cache SRAM : (i) none, (ii) parity or (iii) SECDED ECC. The selection is represented as a parameter in the RIIF model and the setting of these parameters influences how faults map to SDC or DUE. The model is illustrated in figure 6.10. On the bottom are the four technology level faults which feed into the model for the model for the CPU core.

It is assumed that the IP provider has performed fault-grading on the flip-flops and divided them into two sets : critical and non-critical. The AV F for SDC events has been determined for each set through techniques such as those discussed in chapter 3. The user of the IP may chose to map the critical set of flip-flops to a robust cell. For this reason, the model has separate parameters for the FIT of critical and non-critical flip-flops.

The rates of SDC and DUE can be calculated using the following equations:

FIT SDC = Cache SDC + FF SDC (6.1)

FIT DUE = Cache DUE + FF DUE (6.2) Cache SDC = N BITS •Cache Utilization •        FIT SBU + FIT MBU No Cache Protection
FF SDC = AV F CRIT_FF • N CRIT_FF • FIT CRIT_FF + AV F NORM_FF • N NORM_FF • FIT NORM_FF (6.5) FF DUE = AV F DUE • (N CRIT_FF • FIT CRIT_FF + N NORM_FF • FIT NORM_FF ) (6.6)
The code to implement these equations as a component is presented in figure 6.11. There is a component declaration, followed by a set of parameter declarations. The first set of parameters specifies how the IP has been configured, specifically the cache protection scheme. Next, there is a parameter to represent the utilization of the cache. This is a MDR factor and can be set based on application profiles. The next four parameters are the FIT rates for the technology level faults and these have no values assigned to them.

Technology Mapping

The model presented in figure 6.11 is technology independent and must now be combined with technology models to compute absolute FIT rates. A second way of combining models in RIIF is through an Object Oriented (OO) approach [Meyer 1997].

A new component may be derived from an existing one by extending it, similar to other OO languages such as C++ or SystemVerilog. All of the elements (parameters, failure modes) in the original component are visible in the extended component 1 .

A RIIF model for a generic SRAM was already seen in figure 6.8. This generic component can be extended to create a technology specific model, as shown in figure 6.12 where FIT rates are specified for a specific technology. For the purpose of this example, the SBU and MBU FIT rates are obtained by a lookup from assumed radiation test-results and coded using the ternary operator (?:). The full object inheritance hierarchy is shown in figure 6.14. Finally, these models can be combined to yield a model for the soft core implemented in a specific technology. This is done using OO extension. In the compact model, shown in figure 6.13, the technology FIT rates are mapped to the parameters in the model of the soft-core. 1 Currently RIIF does not have public or private data, but this is an obvious extension.

Scrubbed Memory Example

Correctly modeling the effective failure rate even of a simple system can quickly become complicated when multiple failure modes are considered and when mitigation techniques mask some of the errors. SBUs accumulate in the memory starting from the time the system is poweredup, t. Hard errors (SHEs) accumulate in the memory starting at the time the system was built, t .[ Sanchez- [START_REF] Sanchez-Macian | [END_REF] show that the rate of data corruption with this system is:

λ SDC = λ 2 SBU • t M + λ 2 SHE • t M + λ SBU • λ SHE • t M + λ SHE • λ SBU • t M (6.7)
It is common practice to use scrubbing [Saleh 1990] to prevent error accumulation. Through scrubbing, the time period during which SBUs can accumulate is limited to T s rather than the time since power-up, t. With scrubbing enabled, the rate of data corruption is given by:

λ SDC = λ 2 SBU • T S 2 • M + λ 2 SHE • t M + λ SBU • λ SHE • t M + λ SHE • λ SBU • T S M (6.8)
These equations can be coded in RIIF as shown in figure 6.16.F i r s t ,t h eb a s e component for the SRAM used in this example is shown in figure 6.15. This model is nearly identical to that in 6.12, except for the inclusion of the SHE failure mode. Clearly, it is undesirable to have inconsistent sets of failure modes for the same component, thus there is a need to establish, libraries of base components which will be standardized. The base model defines the rates of SBUs and SHEs as a function of voltage and temperature.

A new compoment is declared which extends the base component and which models the effects of ECC and scrubbing. The code for this extension is shown in figure 6.16. This model can be processed by the RIIF processor and the results of simulating the models have been plotted in figure 6.17. From the results, we see that with scrubbing, the SDC rate grows slowly with time, as the probability of an SBU and SHE occurring in the same word is small. Without scrubbing, of course, the SDC rate grows quickly with the time since power-up, as the SBUs accumulate in the memory (red/crosses, blue/star lines). With scrubbing enabled, the SDC rate due to SBUs is flat with time. However, due the the fact that the SHE rate increases with time, the total SDC rate is higher after ten years (green/Xs, purple/boxes lines) than during the first year.

This example shows that even a simple system requires a time-variant model that represents the effect of mitigation schemes such as scrubbing and ECC. In its current form, the RIIF language makes no distinction between faults, errors and failures. The notion of a failure mode is general and can cover any type of event that occurs. When the RIIF model is flattened, these events form a Directed Acyclical Graph (DAG), and the rate of the events is propagated from the leaf-level upwards. This approach is flexible, but may lead to ambiguity for the users. A more formal approach, shown in figure 6.18 has been considered where this distinction is explicit. A special technology component would be used to model faults. This type of component would define faults and their rate of occurence and would explicitely be at the bottom of the hierarchy. Next in the hierarchy would be device components. Semantically, these would require as input, a set of technology components for the known faults. Based on these fault models, the device component would compute the rate of specific errors. Then, at the top of the hierarchy, system components would take as input specific errors from the technology components and calculate failure rates.

∀ !#∃%∀& !∋∃%∀& !(∃%∀& !)∃%∀& ! * ∃%∀& !∀ !# !∋ !( !) ! * !+ !& !, !- !#∀ !## !#∋ ./0123∃4!
It seems the key distinctions with this approach are twofold. First, technology components only define faults but take no other input about incoming event rates. At elaboration time, it would be verified that technology components are at the leaf-level of the tree. Secondly, the device and system components would explicitely 6.4. Extensions to RIIF 121 declare which faults or errors are required as inputs from the level below. This would ensure there is no mismatch between the set of faults that exist, and those which are analyzed.

Mission Profiles and Timelines

Correctly modeling the environment and the mission profile of a system is critical in order to assess its reliability. Many systems do not operate continously with a homogenous workload. This is clearly the case of automotive or avionic systems where there are distinct states of operation. RIIF does not yet address this issue, although it is recognized as an important future contribution. In the following paragraphs, some early considerations about this aspect are presented.

Many system companies have extensive historical data on actual usage profiles. For example car manufacturers collect data on the number of hours and distances that are driven. For the purposes of reliability modeling, the goal is not necessarily to apply a specific historical profile, but rather to identify one or more typical profiles. One approach consists in using a probablistic model of the system state (Markov model). The duration of each state and the transition probabilities are determined based on actual profiles.

As a simple example, we consider an airplane which can be in one of three states : take-off, cruise, landing. The cruise state may be further de-composed as shown in figure 6 This type of Markov state model could be represented in RIIF using the notion of a timeline, as shown in figure 6.20. Once the time-line is defined, a set of environments can be defined. During each operational state, the environment in that state would determine operating parameters such as the workload, radiation flux and temperature.

This brief example is presented to highlight the need to model mission-profiles and show that this could be done through extensions to RIIF. Detailed definition of this aspect of RIIF remains future work.

Conclusion

The RIIF language does not contribute new concepts to reliability theory nor to the theory of modeling failures in ICs. Instead, it is a framework for expressing the existing theory in a standard, machine-readable format. This remains a key contribution, because in the absence of such a format, it is difficult to develop EDA tools which can analyze the reliability of complex SoCs. Today, models are built by manually entering data into spreadsheets; a process that is error-prone and which is not scalable.

It is clear, that the RIIF language is in an early state of development. Working through the set of examples presented in this chapter has identified certain issues which have been addressed. For example, the need to model time and to distinguish between a component's life-time and the time since it was powered-up was identified in section 6.3.3. The examples also illustrate how the use of OO techniques allows the complexity of lower level models to be hidden. Significant effort is required to correctly model the rate of cell level upsets at different voltage conditions. Similarly, evaluating the AV F of structures in a processor is a challenging task. Today, these tasks are often performed by different types of engineers and rarely are the full models combined. RIIF provides a frame-work enabling detailed models to be developed by experts. These detailed models can then be combined to create a compact model of an entire chip, without compromising the modeling accuracy. There exists an enormous body of scientific work devoted to the analysis and mitigation of soft error effects and the topic continues to attract the attention of many researchers. The physics behind soft error phenomena are well understood although the impact of new process technologies such as FINFETs and FDSOI are still being studied. Despite this research, assessing the effect of soft errors on a complex SoC remains a challenging task and the approaches taken in industry often involve large approximations. The selective replacement of critical flip-flops is common practice, however, in industry the selection is often made based on simple heuristics and may be highly sub-optimal. The techniques proposed in this thesis make a modest contribution to better addressing these problems. As with any research, this document provides a snapshot of the current state of the work, however, additional research is required to further develop the techniques that have been proposed.

Simulation Analysis and Selective Mitigation

The first contribution of this thesis (section 3.2.4) involves using a CRC as a signature for the state of a digital system. When performing fault injection simulations, this CRC can be used to identify when the system with the fault has returned to its golden state. The advantage of the CRC is that it is compact. As presented in chapter 3,theCRC was calculated over the entire system, including the state of the flip-flops and the memories. In this way, the CRC provided a strong check of the full system, however, the calculation of the CRC required every bit in the design to be accessed.

The compute cost of the CRC can be reduced by calculating separate CRCs for different portions of the system. As shown in figure 7.1, a separate CRC trace can be created for each module in the design hierarchy. When a SEU is injected in a flip-flop in a specific module, such as B, then after the fault injection, the first check is to see whether the CRC of module B matches the golden value. Assuming B represents only a small fraction of the design, this is much less costly than computing a CRC over the full system. If the CRC over B does not match, then it is certain the fault is still present and the simulation must be continued. If the CRC over module B matches, then either the fault has been masked, or it has propagated beyond B.A tt h i sp o i n t ,t h eCRCs of the other modules can be checked, starting with those that are logically adjacent to B. In order to ensure the fault has been completely over-written, the CRCs of all modules must be checked, but this will occur only once, after the fault has disappeared. It is exepected that this extension would significantly reduce the cost of the CRC calculation. Furthermore, it would make it possible to study the propagation of faults through the design hierarchy. Development is underway to implement this enhancement and to quantify the benefit in terms of reduced simulation time.

! "

#$%&'( !#$%&'( "#$%&'( )*+ In chapter 4, techniques to cluster flip-flops were presented. By analyzing clusters, rather than individual flip-flops, far fewer fault-injections are required in order to identify which flip-flops to harden. Three different techniques for clustering were identified and compared. The technique that worked best consisted of heuristics that considered signal naming and module hierarchy. Since the original work in chapter 4 was performed, the proposed clustering techniques have been applied to a full networking ASIC. Through this work, several observations have come to light. The first is that the sizes of the clusters can vary significantly with some large clusters containing over ten thousand flip-flops. When these flip-flops are homogenous and have the same function, this is highly beneficial. In some rare cases, based on insights provided by designers, large clsuters were found to be heterogeneous and had to be manually split. This typically occurred when not all the bits within a bus had the same function (some bits are used as control while others hold data). It would be beneficial if the algorithms could be extended to analyze whether the effect of the faults injected within a cluster are homogenous. In the event that they are not, this information could be used to propose an improved clustering.

Despite these challenges, clustering techniques have made it possible to effectively identify flip-flops for hardening on a large networking ASIC targeted to an application where an extremely low SDC rate is required. These techniques have provided a speedup of about two orders of magnitude and without them, it would be virtually impossible to use fault-injection simulations to identify critical flip-flops in a design of this scale.

Hierarchical SET Analysis

In chapter 5, a high-level methodology to quickly compute the effect of SETs in large ASICs was propoed. Following the initial work [START_REF] Evans | [END_REF]], a simplified version of the methodology was implemented as a spreadsheet tool which estimates the contribution of SETs based on high-level design information (e.g. gate-count, distribution of gate-types, distribution of types of circuits). Unfortunately, the accuracy of such estimations is not well understood. When complex devices are tested under radiation, while executing real workloads, it is very difficult to distinguish between faults induced by SEUs and SETs. Most of the radiation test data for SETs is from simple structures such as chains of inverters or very basic circuits such as 4-bit adders. Extrapolating this data to a full chip and validating the result remains challenging.

To make progress, more test data is required on the actual contribution of SETs in circuits of moderate complexity. As part of a research project with the European Space Agency and the University of Saskatchewan, a test-chip is being developed which will include several medium sized combinatorial circuits (e.g. state-machines, arithmetic circuits, etc.). The combinatorial structures on the chip will be tested under radiation including under laser and heavy-ion micro beam. The measured data from the test-chip will be correlated both with aggregate and detailed (e.g. per-gate) SET estimations and in this way, the uncertainties will be quantified. A part of this work will also include extensions to better model the effect of EDR which was not considered in the methodology presented in chapter 5.

Although SETs have not traditionally been a concern in terrestrial applications, there is now a clear need to accurately estimate their contribution when performing chip-level SER analysis for high-end applications.

RIIF

Of the contributions of this thesis, the RIIF language is the one that has the potential to have the most impact. At the RIIF workshop held at DATE 2013, as well as at subsequent presentations, there has been genuine interest from industry in having a standard file format for specifying and exchanging the reliability data used in the chip-design process. Based on the initial work presented in chapter 6, it appears that RIIF can be used to model radiation induced faults. However, there exist many other failure mechanisms for silicon devices [START_REF] Jedec | [END_REF]] and further work is required to investigate how RIIF can be extended to incorporate these. Some failure mechanisms such as Electro-Migration (EM) result in an explicit failure event, similar to radiation induced failures. Other mechanisms such as NBTI and HCI result in a shifting of device parameters. This shift may, or may not, provoke a failure. It remains to be seen whether this progressive degradation can be modeled in RIIF or whether it is better modeled through existing approaches such as aged SPICE models. Work is underway, in the context of the Modelling Reliability under Variability (MoRV) European FP7 project, to investigate new techniques to model these failure mechanisms and how to integrate these models into a design flow.

Beyond the question of the scope of RIIF, is the critical question of standardization. Even if the proposed language is able to model the occurence and the propagation of faults, it is of little value if there is no uptake of the language. There is thus a need to develop a formal specification of the RIIF language and then to work with multiple partners from industry to review the specification and move towards standardization. One of the challenges in proposing a new file-format is that it is only attractive when there is a critical mass of tools that can process files in that format. Therefore, another key component of the work ahead consists in improving the proto-type tool and, in parallel, working with other EDA companies to provide support for RIIF.

Summary

Without a doubt, in the years to come, electronics will play an increasingly critical role in all aspects of modern life. This is especially true as autonomous vehicules become a reality and as implantable medical devices incorporate new functonality. In these applications, the highest level of reliability is essential and there is a great need for techniques to evaluate complex systems and evaluate the impact of technology level faults. Analysis of complex systems requires abstraction in order to hide unnecessary details and hierarchical decomposition in order to scale. Both are widely employed in the silicon design process, whether it be design, functional verification, layout or timing analysis. To some extent, reliability analysis has been slow to adopt these approaches. The key contribution of this thesis is to show how abstraction and hierarchical decomposition can be applied to better analyze and mitigate the effect of faults in large, complex designs. Subsequent to the initial work, many of the techniques have been applied to production designs.

The proposed technique does not require modifications to the internal structure of the TCAM since this is often a discrete component designed in a full custom design flow to minimize power consumption and optimize the density of memory cells. The proposed technique can be implemented as a stand-alone module that operates in parallel with the TCAM and checks the correctness of the results of each access. Error detection is immediate, unlike techniques based on background parity scans. Moreover, the proposed solution is particularly well suited to TCAM applications with wide word sizes, like the ones used in modern network systems, since the overhead is independent on the TCAM word size.

In previous work [Pontarelli 2013a], a technique to add a Bloom Filter in parallel to a binary CAM was described. The technique described in this chapter extends the technique to TCAMs.

A.2 Existing TCAM Protection Techniques

In industry, the standard technique to protect TCAMs against radiation induced errors is to protect each word with a parity code. It is not practical to simultaneously check the parity of all entries and it is not sufficient to only check the parity of the matching entry, since an error on a higher priority entry can create an incorrect match. Therefore, a parity scan engine runs in the background and sequentially reads through each of the entries, checking the parity and triggering an error indication if there is a mismatch. When an error is found, software intervenes and re-writes the corrupted TCAM entry. The drawback to this method is that there can be a significant latency between when an error occurs and when it is detected and then fixed by software. During this window of time, incorrect decisions are occurring. Multiple interleaved parity bits are used to protect against upset events which corrupt adjacent cells which is an increasing concern.

In [Krishnan 2009], error correcting codes for TCAMs are proposed, however, these require a 200% overhead in order to correct single bit errors. In [START_REF] Azizi | [END_REF]], a hardened TCAM cell with cross coupled feedback loops is proposed. A SER reduction of about 30% is achieved with an area penalty of 15%. US Patent 7254,748 describes a technique to duplicate TCAM cells to provide error detection and correction, however, this represents and area and power overhead of 200%. None of the existing solutions provide strong, on-line error detection with a modest area overhead.

A.3 Background on Bloom Filters

A Bloom Filter [Bloom 1970] is a probabilistic data structure based on hashes and used to check the membership of an element in a set. A Bloom Filter performs two tasks: 1) stores a set of items in its memory, and 2) quickly responds to a query about the presence of an item. The drawback of using this structure lies in its probabilistic nature which can return false positives. With a certain probability (called the false positive rate), the Bloom Filter can report a data element as being present when in fact it was not inserted into the Bloom Filter. A false positive occurs when the hash functions alias. However, when a Bloom Filter signals that a data is not present, this is always the case ( i.e. a false negative never occurs in a Bloom Filter).

A Bloom Filter is implemented as a bit array of m bits accessed via k hash functions H 1 (x)...H k (x). Each hash function maps a set member x to one of the m bits within the bit array. We denote as v(i) the value of bit i within the bit array. 1. Insertion: An element x is inserted into the filter by setting to one all the indexes of the bit array addressed by the k hash functions. In a mathematical notation this corresponds to: ∀i ∈{1..k},v(H i (x)) ← 1 2. Querying : An element is reported as present in the filter if all the values of the bit array addressed by the k hash functions are equal to 1. result ← min{v(H i (x))},i ∈{1..k}

In other words, when a word x is inserted, the bits corresponding to the result of hashing x with all the hash functions are set to 1. An element is then said to be in the set if all the bit positions to which it is hashed are set to 1. Clearly, there can be no false negatives. It is, however, possible that the bits set by two or more words actually stored in the array correspond to the bits of another word x which is being queried but which is not stored in the set, resulting in a false positive.

For a Bloom Filter in which n elements are stored, the probability p(n) that a given bit in the filter is zero is given by:

p(n)= 1 - 1 m kn ≈ e -n k m (A.1)
If we test membership of an element that is not in the set, each of the k bit array values indexed by the hash is 1 with probability 1p(n). The probability of all of them being 1, which would cause the false positive, is then:

P fp (n)=(1-p(n)) k ≈ 1 -e -kn m k (A.2)
The probability of false positives decreases as m, the number of bits in the array, increases. The probability of false positives increases as n, the number of words stored in the filter, increases. For a given m and n,thev alueofk (the number of hash functions) that minimizes the probability of false positives is: k = m n • ln2 ≈ 0.7 • m n . Using equation A.2, we can size the Bloom Filter according to a required number of elements to be stored and a required minimum false positive rate.

A.4 Application Aware Hashing

A trivial method of inserting don't care bits in a Bloom Filter is to fully expand each of the don't care bits. This is not scalable as the number of insert operations and the size of the Bloom filter grows exponentially with the number of don't care bits and essentially this consists of treating the TCAM as a binary CAM.

From a purely hardware perspective a TCAM can have don't cares in any bit of any entry. However, some practical considerations can be used to identify patterns within the entries based on how TCAMs are used in industrial applications. In networking systems, a single large TCAM is used to support multiple features or applications. Examples of such applications are packet classification, Access Control Lists (ACLs), traffic sampling (Netflow) and QoS -to cite the most common. The entries in the TCAM are divided based on the applications and a small number of bits within the lookup word are used to select which set of entries to match when a given lookup is performed for a specific application. For a given feature, a specific set of fields from the packet header are looked up. The usage of fields within an application is regular and there are patterns in where don't care bits appear for each application. This regularity of the don't care bits can be exploited to avoid the explosion that would result from a naïve expansion of don't care bits.

TCAM entries can be divided into fields of which we identify three types:

1. Fully Unmasked This type of field corresponds to groups of N bits which must match exactly. These entries correspond to a binary CAM.

2. Prefix This represent any field of size N bits where the most significant M bits are unmasked (must match) and the least significant (N -M ) bits are masked (don't care).

3. Generic This represents an arbitrary field of N bits where any combination of bits within the field may be masked or unmasked and the combination of don't care bits can appear anywhere.

TCAM configurations are usually computed by algorithms that transform classification rules based on port ranges, IP addresses and other packet header fields into a set of TCAM entries [Lakshminarayanan 2005]. For each rule, the algorithm generates a set of similar entries. The packet fields that are relevant for classification vary from one feature to the next (e.g. QoS, ACLs, etc.) thus different similarities occur depending on the feature. For this reason, an application aware approach to building the Bloom Filter is proposed. The key idea to avoid state explosion is to select a different set of hash functions for each feature in order minimize the don't care bits. This approach is called application aware hashing.

In particular, for fields that operate on a longest prefix match1 ,w eu s et h e approach proposed in [START_REF] Dharmapurikar | [END_REF]]. This method partially masks the least significant bits, hashing only a variable prefix part of the field. The hash functions are grouped with respect to an interval of the prefix length. During the insertion phase, the field is masked following the given prefix don't care configuration, and is inserted in the Bloom Filter using the whole set of hash functions. During the search phase, the item to be searched, is progressively masked and queried in the Bloom Filter, as depicted in figure A.2). The example in the figure illustrates an old, classful networking hierarchy, however, the approach in [START_REF] Dharmapurikar | [END_REF]] also works for arbitrary prefix lengths.

Finally, for generic fields, we propose a hashing methodology aimed at compacting the number of don't care bits. The regularity of TCAM configurations allows us to define some rules, that can be applied to perform the application aware hashing. The most significant bits of the TCAM entry identify the feature and define the format of the subsequent fields of the entry. The following rules are applied:

1. Unmasked fields can be used directly as input of the hash functions.

2. Fields that are always masked can be ignored in all the hash functions.

3. Fields of prefix type can be managed using the longest prefix match algorithm. 4. Otherwise masked bits are compressed in order to reduce the number of don't care bits (e.g. XORing contiguous bits).

• Feature 3: This feature is similar to feature 1 using this part of the TCAM as ab i n a r yCAM. The first field (10), identifies this feature, the second field is unmasked and the third field is always masked. In this case, the input for the Bloom Filter are the bits in[13...8] of the original input data.

• Feature 4: This feature is composed of three fields. The first field identifies the feature (11) and the second is a 6 bits unmasked field which functions as a binary CAM. The third field uses longest prefix match. Applying the rules for application aware hashing, the full input vector is given to the longest prefix matching algorithm, iteratively setting the range for bit masking for the bits from 0 to 7. Filters strictly depends on the TCAM configuration and on the input keys applied to the TCAM. In particular, when the TCAM is configured to be used as a full classifier [Lakshminarayanan 2005], the first Bloom Filter becomes useless, since there are never any misses in the error-free TCAM. The second architecture shown in figure A.4 uses M Bloom Filters and splits the content stored in the TCAM into M different subsets. Each item is inserted in only the i th Bloom Filter, corresponding to the condition i = entrymodM . Since the false positive rate of Bloom Filters depends on the ratio between the number of inserted items and the size of the Bloom Filter, the false positive rate is independent of M, the number of sets into which the TCAM configuration set is divided. Unlike the first architecture, this architecture presents a lower error detection latency, because the query to the M Bloom Filters can all be done in parallel with the TCAM lookup. The TCAM output is only used to select which of the M responses from the Bloom Filters should be considered. The drawback of this architecture is that undetected errors can be caused both by hash collision, like in the previous architecture, or when an erroneous entry (i.e. the response of a TCAM affected by a SEU) and the correct one (i.e. the one stored in the Bloom Filter set) have the same value modulo M. The use of M = 16 or M = 32 allows us to reduce this aliasing probability to 6% or 3%. When no false positive occurs, the set of Bloom Filters provides a one-hot encoded word as output, while with the occurrence of a false positive in some of the Bloom Filters that do not correspond to the requested key, the output word has multiple bits to 1. If a false positive occurs simultaneously with an error in the TCAM, the error is undetected if the i th index given by the modular operation selects one of the Bloom Filters affected by the false positive. The algorithm for error detection using the second architecture is shown in figure A.5. First the algorithm checks if all the Bloom Filters are zero. This corresponds to the condition of a MISS in the TCAM.I ft h eTCAM gives MISS as a response, then no error has occurred. Otherwise, if the TCAM responds with an entry we assume that a pseudo HIT error has occurred. Instead, if some of the Bloom Filters give 1 as a response, we select the Bloom Filter with index i, where i is the entry number returned by the TCAM modulo M. If the i th Bloom Filter returned 1, we assume that no error has occurred, otherwise an error in the TCAM is reported. The condition of BF(i) = 1 can be caused by the simultaneous occurrence of a false positive in the Bloom Filter and by an error in the TCAM. The experimental results show that this is very unlikely.

A.6 Experimental Results

In order to evaluate the effectiveness of the proposed methods, a set of simulations have been performed. A C++ software model of TCAM and Bloom Filters was designed and both the TCAM and the Bloom Filters were configured using a real errors is less than expected, (should be 25%, since M = 4), since the aliasing does not occur when a fault inside the TCAM produces a pseudo-HIT. In fact, in this case, all the Bloom Filters give 0 as response, while the TCAM signals the presence of the key in an erroneous entry. The condition that all Bloom Filters are equal to 0 allows the error to be detected without any modular operation, and therefore without the issue of aliasing. Aliasing still remains an issue for multi-HIT errors.

When the size of the filters is sufficiently large, no false positives occur, and the error coverage is independent of the size of the Bloom Filters.

A.7 Conclusions

The result of the work presented in this chapter is a technique that can effectively detect errors in TCAMs. The method is attractive because it can be implemented as a circuit that operates in parallel with an existing TCAM device, thus it can be applied to discrete TCAM memories. With the standard approach to TCAM error detection, based on a background scrub process, there is a long error detection latency, however, the proposed approach detects errors when they occur. Furthermore, the technique works even if many bits in the TCAM memory are upset and is not limited to detecting single bit errors. The core of the proposed technique is an application aware hashing algorithm that, for practical configuration patterns, enables the don't care bits in the entries to be effectively stored in the Bloom Filter. This technique is not only attractive for error detection, but it also has applications for reducing power consumption.

Commercial TCAM devices are physically divided into banks and when a search request is issued, in addition to the search key, a bank mask is provided, indicating which banks should be enabled for that search. Of course, the fewer banks that are enabled, the less energy that is consumed. A set of Bloom Filters can be placed on-chip, as shown in figure A.6. Each on-chip Bloom Filter stores the contents of the corresponding bank in the off-chip TCAM. Before a search key is issued externally, the on-chip Bloom Filters can be queried. For those filters which indicate that the key is not present in the corresponding bank, the external bank need not be searched. In this way, only a small number of banks need be enabled. There are no false negatives, so the correct bank is always searched. Of course, false positives can occur, but the only drawback is that the corresponding bank in the external TCAM is searched unnecessarily. Further research is underway to quantify the power saving benefits and to potentially implement this technique on a commercial ASIC. In [START_REF] Almukhaizim | [END_REF]], redundant wires are inserted in a combinatorial circuit, specifically to reduce the sensitivity to transients.

In early work on approximate logic functions [Sierawski 2006], a BDD representation of the circuit was built and then pruned to produce approximate functions. In [Sanchez-Clemente 2012], the authors perform a unate decomposition of the original function and then simplify this by eliminating those lines with a testability metric below a given threshold. The coverage of the resulting circuit is evaluated with stuck-at and fixed-width transient faults. Other authors [START_REF] Choudhury | [END_REF][START_REF] Choudhury | [END_REF]] have used a Sum of Products (SOP) representation to build the approximate logic function, which is the same representation used in this work. In [START_REF] Choudhury | [END_REF]], the authors use approximate logic for Concurrent Error Detection (CED) and extend this work in [START_REF] Choudhury | [END_REF]]tothemaskingofstuc k-at and timing faults. Their algorithm does not consider the actual per-gate failure rates. The primary contribution of the algorithm proposed in this chapter is the fact that it considers the per-gate failure rates. This is achieved by incrementally performing fault injection simulations as the sequence of approximate functions is generated. Through careful consideration of the statistical confidence intervals, the number of fault injections is kept to the minimum number required to identify the next best cube to select. For several circuits, we illustrate the trade-off between masking and increased area/power and for some circuits, we show higher quality results than those obtained in previous work.

B.2 Overview of Approximate Logic Functions

The basic idea behind redundant logic is that any combinatorial logic function, G, can be augmented with a simpler approximation of the min-terms (F) and the maxterms (H), as in figure B.1. For any input vector for which F is true, G is also true. In this way, if there is a fault causing G to incorrectly be false, then it may be corrected by F. In a similar way, H may fix faults where G is incorrectly true. Potentially, F or H can be empty (e.g. H=1, F=0). The maximum added delay is two gates, and if either F or H is empty, the delay is a single gate. The challenge is to generate F and H such that they mask a maximum number of faults while minimizing the area and power overhead.

The failure rates of gates can vary significantly. Clearly, an inverter consisting of two transistors is less prone to stuck-at faults than a complex gate with 10 transistors like an XOR, as seen in figure B.2. For this reason, it is important to consider the actual technology failure rates when synthesizing redundant logic functions. We assume that the per-gate FIT rate, f i , has been characterized in advance.

Due to logical masking effects1 , a fault in a given gate has a probability of ). After selecting one cube, the FR metric for the remaining cubes is re-calculated, in a lazy fashion described below. The cubes are then resorted to identify the next best candidate.

The EPP is determined using statistical fault injection performed on the gatelevel circuit using a digital simulator. Random input vectors, within the scope of the cube, are generated based on the distribution of vectors in V (a set of vectors taken from an input trace). For each fault-injection, one gate is randomly chosen, weighted by the per-gate FIT rates, f i . A stuck at fault (0 or 1) is injected on the selected gate and it is determined if the fault propagates to a primary output. This biased fault injection approach was chosen in order to take into account the actual expected failure rates of the gates in the mapped circuit. This ensures that the redundant logic functions are optimized to cover the faults that are most likely to occur.

The objective is to perform the minimum number of fault injections necessary in order to identify the next best term to select. To avoid running more simulations than necessary, the simulations are launched in small batches of size N batch . After the first batch of simulations, the value of EPP is estimated ( epp n ), based on the fraction of simulations where the fault propagates to an output. If we assume that the distribution of epp n is normal, then the confidence interval is given by equation B.3 [Wasserman 2005, p. 130], as discussed in section 3. Of course, this benefit comes with the downside that the area of the shared logic is increased. In future work, we intent to compare the results obtained with and without logic sharing between F and H.

In figure B.5 the area and power overhead required to achieve increasing levels of stuck-at fault masking for four different circuits are shown. Each data point was produced after 5 additional cubes were added to the redundant logic and the connecting lines show the order of cube selection. It is interesting to note that in some cases there are points where adding an additional cubes reduces the area and power, presumably because the extra cubes enables new logic simplification. Two data points are plotted comparing published results on the same circuits. We note however, that with our fault model, the per-gate failure rate varies, whereas in the previous work it was fixed. B.3 summarizes the area, power and timing overhead for ten circuits, showing the first generated result providing at least a 2x reduction in FIT rate. It is interesting to note that the required overhead to achieve a 2x reduction in the FIT rate varies from 5% to over 100%. We believe this is partly due to the SOP circuit representation, however, it suggests that, we may be far from the optimal solution.

B.5 Conclusions

Protecting random, combinatorial logic from faults is a challenging problem. The proposed approach based on a SOP representation, uses a fault model that accounts for different gates having different failure rates and shows promising results for selected, small circuits. It is true that the overheads are significant compared to those for protecting memories or other regular structures. However, given that the hard and soft FIT rates due to combinatorial logic are no longer trivial and that random logic represents a small fraction of most dies, they may be acceptable. In an industrial context, generic solutions are required which can be applied directly to a gate-level netlist, however this is not the case of many on-line test techniques. The proposed technique can be applied automatically to any combinatorial circuit and the number of fault injection simulations is carefully managed.

Additional work is underway to extend the fault model to include SETs and to account for the power overhead during the minimization process. In the implementation described here, the synthesis tool was allowed to share logic between the F and H functions. A study is underway to evaluate whether better results are obtained with or without such sharing. In addition, a method to decompose large circuits is also required in order to process industrial scale designs.

Traditional ECC techniques are not easily applicable to the CRAM of an FPGA because all the bits of the entire memory are continuously read to control the logic array. A common technique to detect errors in the CRAM uses a scan engine. The scan engine cycles through the addresses of the CRAM, reading them and detecting whether there is an error. The detection can be performed using an error detecting or correcting code (e.g. parity or ECC). Typically the scan engine reads the CRAM in a linear pattern and the worst case error detection time can be on the order of several milliseconds for modern FPGAs. During the window of time between the occurrence of the upset and the detection of the error by the scan engine, the logic array is not performing the correct function. Even after the error in the CRAM is corrected, the effect of the incorrect logic function may persist. The smaller the window of time during which the fault is present, the less the risk that there will be a persistent system level effect. Scan-based techniques can be accelerated through the use of multiple, parallel scan engines, however, additional scan engines required additional area and power. In this section, we propose a technique that can significantly reduce the detection latency for SEUs in the CRAM of FPGAs with minimal area and power overhead.

C.2 Overview of BICS

A BICS is a circuit that can directly detect the current induced by the strike of an ionizing particle. BICS designs have been proposed for the detection of SEUs in memories [Vargas 1994[START_REF] Gill | [END_REF]] as well as in logic [Zhang 2010[START_REF] Zhang | [END_REF]]. An example BICS circuit is reproduced from [Wirth 2008]infigureC.2. Although these circuits are attractive for detecting Single Event Effects (SEEs), they suffer from two common shortcomings. First, a BICS circuit must be tuned so that it only detects current impulses that correspond to actual particle strikes. With increased process variability, this can be challenging. Second, BICS are subject to a high-rate of false positives. Frequently, a BICS will detect a current pulse that does not actually cause a bit-flip. These false positives may actually result in reduced availability, depending on the error recovery mechanism.

C.3 Use of BICs to Protect CRAMs

The idea proposed in this section consists of using a series of BICS circuits embedded in the CRAM of an FPGA to detect the ionizing particle when it strikes, as shown in figure C.3.E a c hBICS circuit detects upsets that correspond to a small range of logical addresses in the memory. When an ionizing event occurs, it is detected by one of the BICS and this is immediately communicated to the scan engine. Upon such an event, the scan engine interrupts its normal scan process and immediately starts scanning the small range of addresses within the array that are covered by the BICS that detected the strike. When the address with the error is located, it can be corrected immediately.

With the standard scan-based approach, the detection and correction interval depends on the time required by the scan engine to read the entire CRAM.W i t h the proposed approach, the interval is bounded by the time for the scan engine to react to the BICS and then to read the small region of the CRAM that is covered by a single BICS. This time can be made small by increasing the number of BICS. The difference between the two approaches is illustrated in figure C.4. BICS circuits must be tuned and they are prone to false positives.I n t h e proposed application, such false positives are not a concern. If the BICS incorrectly interrupts the normal scan process and directs it to a region of the memory where there is no error, this is benign. At worst, this occasionally causes a small increase in the regular scan interval. The fact that the scan engine remains active ensures that if an ionizing event occurs that is not detected by the BICS, it will eventually be detected by the background scan.

C.4 Extension to TCAMs

A TCAM is a specialized memory which matches an incoming key against a set of stored entries where each entry contains a string of zeroes, ones or don't care bits. Storage cells in a TCAM are subject to soft errors and traditional ECC are not easily applicable because all the bits of the entire memory are continuously read to match against the incoming search key. A common technique to mitigate errors in TCAMs is to use a scan engine, conceptually similar to the type used for SRAMbased FPGAs. During the window of time between the occurrence of the error and the detection of the error by the scan, the TCAM may return incorrect responses.

In networking applications, TCAMs are used for packet classification including the implementation of security features such as Access Control Lists. During the window of time between when an error occurs and when it is detected, packets may be misclassified and potentially this could represent a security threat. Exactly the same approach that is described for FPGA CRAM can be applied to TCAM. Specifically, when a BICS embedded in the TCAM array detects a potential ionizing radiation event, the existing scan engine is directed to scan the memory region where the event occurred. In this way, the average error detection time is greatly reduced.

C.5 Summary

The idea of using BICS to protect memories is quite old [Vargas 1994]. However, to the best of the author's knowledge, the idea of coupling a BICS circuit with a background scan engine in order to reduce error detection latency is new. The combination of these techniques is attractive because the false positives from the BICS are not an issue. At the same time, if there are events that are not detected by the BICS, they will be detected by the background scan.

Abstraction Techniques for Scalable Soft Error Analysis and Mitigation

Abstract: The main objective of this thesis is to develop techniques that can be used to analyze and mitigate the effects of radiation-induced soft errors in industrial scale integrated circuits. To achieve this goal, several methods have been developed based on analyzing the design at higher levels of abstraction. These techniques address both sequential and combinatorial SER. Fault-injection simulations remain the primary method for analyzing the effects of soft errors. In this thesis, techniques which significantly speed-up fault-injection simulations are presented. Soft errors in flip-flops are typically mitigated by selectively replacing the most critical flip-flops with hardened implementations. Selecting an optimal set to harden is a compute intensive problem and the second contribution consists of a clustering technique which significantly reduces the number of fault-injections required to perform selective mitigation.

In terrestrial applications, the effect of soft errors in combinatorial logic has been fairly small. It is known that this effect is growing, yet there exist few techniques which can quickly estimate the extent of combinatorial SER for an entire integrated circuit. The third contribution of this thesis is a hierarchical approach to combinatorial soft error analysis.

Systems-on-chip are often developed by re-using design-blocks that come from multiple sources. In this context, there is a need to develop and exchange reliability models. The final contribution of this thesis consists of an application specific modeling language called RIIF (Reliability Information Interchange Format). This language is able to model how faults at the gate-level propagate up to the block and chip-level. Work is underway to standardize the RIIF modeling language as well as to extend it beyond modeling of radiation-induced failures.

In addition to the main axis of research, some tangential topics were studied in collaboration with other teams. One of these consisted in the development of a novel approach for protecting ternary content addressable memories (TCAMs), a special type of memory important in networking applications. The second supplemental project resulted in an algorithm for quickly generating approximate redundant logic which can protect combinatorial networks against permanent faults. Finally an approach for reducing the detection time for errors in the configuration RAM for Field-Programmable Gate-Arrays (FPGAs) was outlined.

Keywords: Single-event effects, single-event upsets, single-event transients, reliable systems, fault-injection

Figure 1 . 3 :

 13 Figure 1.3: Parasitic Thyristor (PNPN)

  Figure 1.8: Temporal Masking of SETs

$.! 7 Figure 1

 71 Figure 1.10: SEU Causing a Minor Delay in Packet Delivery

Figure 1

 1 Figure 1.12: Over 40 Years's of Moore's Law

Figure 2 .

 2 Figure 2.1: Circuit Diagrams of DICE Cell

Figure 2 . 2 :

 22 Figure 2.2: Effect of Node Separation on the SER of DICE Latch

Figure 2 . 5 :

 25 Figure 2.5: Graal Timing Diagram

Figure 2 .

 2 Figure 2.10: Razor-II Timing Diagram

Figure 2 .

 2 Figure 2.13: Bubble-Razor Timing Diagram

Figure 2 .

 2 Figure 2.17: Use of TMR For Flip-Flop Protection

  Timing Diagram for TMR with Two Clocks

Figure 2 .

 2 Figure 2.18: Flip-Flop TMR Using Two Clocks

Figure 2 .

 2 Figure 2.21: Venn Diagram Showing Properties of Robust Sequentials

Figure 3 . 2 :

 32 Figure 3.2: Classification of Faults in Processors

Figure 3 . 3 :

 33 Figure 3.3: Fault Injection Simulation Environments

Figure

  Figure 3.3(b) shows a more complete view of a modern functional simulation environment. The stimulus is generated in terms of transactions (e.g. packets, video frames, numeric data, etc.) which are converted to low-level vectors by Bus Functional Models (BFMs). On the output side, the raw vectors from the DUT are parsed into transactions which are checked by intelligent checkers. The stimulus generator and the checker communicate via a scoreboard which is a data-structure that tracks the transactions currently being processed by the DUT. As the intelligent checker works at a high level of abstraction, it detects and reports errors at the transaction level (e.g. missing packets, corrupted video frames, numerical errors, etc). Typically, these errors are written to a log file and it is possible to map the various error messages to the system-level impact they have. Essentially, the intelligent checkers provide an automated means to evaluate the system level effect of faults.The challenge with simulation based fault injection is the relatively low speed of digital simulators. Fortunately, the problem of fault-injection is easily parallelized. By the 1970's[Chang 1974] techniques for parallel fault simulation had been developed and already at this time, it was possible to evaluate thousands of faults per second on mainframe computers for circuits with hundreds of gates. Below, we discuss a few of the numerous techniques that have been developed to accelerate fault simulations.Recently,[START_REF] Alexandrescu | [END_REF]] presented the implementation of an acceleration technique based on exploiting the fact that modern processors typically have a 64-bit word width. On the host processor, instead of running simulations sequentially, up to 64 simultaneous fault injections can be performed, where each bit in the data-path of the host processor is used to evaluate a different scenario. A tool was developed

Figure 3 . 4 :

 34 Figure 3.4: Execution Flow for Software Based Fault Injection

Figure 3 . 5 :

 35 Figure 3.5: Results of Different Types of Fault Injection

Figure 3 .

 3 Figure 3.7: ADD Representing the Path from G2 to G3

Figure 3 .

 3 Figure 3.9: Backward Propagation of Detection Probabilities

  Figure 3.10: Reconvergent Paths

2 .

 2 SET indicates whether the technique can evaluate the effect of SETs. 3. Abstraction indicates the abstraction level of the model being analyzed. 4. Scale provides an indication of the technique's ability to process large designs. 5. Speed indicates how quickly the technique can complete an analysis. 6. Domain indicates the type of designs that can be analyzed with the technique. 7. FDR indicates whether the functional effect of faults can be taken into account. 8. TDR indicates whether the technique can assess the masking effects of temporal delays.

Figure 3 .

 3 Figure 3.11: TDR Distribution in Epsilon, Omega and Gamma

Figure 3 .

 3 Figure 3.13: Logical Re-Convergence Versus Time After Fault Injection

Figure 3 .

 3 Figure 3.14: Normal Confidence Interval with p =p n for Epsilon

Figure 3 .

 3 Figure 3.15: Comparison of Four Confidence Intervals

  bus-based fault-injection campaign on the 10GE MAC required 266 simulations and the clusters were sorted based on the number of critical failures that were observed. Eight clusters produced at least one critical failure and these clusters represented 167 flip-flops. The results are shown in the histogram in figure 4.3. The clusters are binned based on the fraction of simulations that produced a critical failure, which is a measure of the sensitivity and shown on the horizontal axis. The black bars on the histogram show the number of clusters having a given sensitivity and the grey bars on the right show the number of flip-flops contained in these clusters. The climbing line indicates the cumulative number of flip-flops contained in the clusters starting with the most sensitive clusters on the left side. Note the number of flip-flops is shown on a log scale.

Figure 4 . 4 :

 44 Figure 4.4: Bus Based Clustering for Epsilon

Figure 4

 4 Figure 4.5: Hierarchical Clustering for 10GE MAC

Figure 4

 4 Figure 4.6: Hierarchical Clustering for Epsilon

Figure 4

 4 Figure 4.7: Hybrid Clustering for 10GE MAC

Figure 4

 4 Figure 4.8: Hybrid Clustering for Epsilon

Figure 4

 4 Figure 4.10: Partial Mitigation in Epsilon

Figure 4 .

 4 Figure 4.11: Partial Mitigation in Omega

Figure 4 .

 4 Figure 4.12: Three Dimensional Fault Space

Figure 5 . 1 :

 51 Figure 5.1: Modeling of SETs at Different Levels of Abstraction

Figure 5 . 2 :

 52 Figure 5.2: Conversion of a SET Pulse into a Digital Pulse

Figure 5 .

 5 Figure 5.8: Block Diagram of ALU Circuit

Figure 5 . 9 :

 59 Figure 5.9: Methodology for SET Estimation from RTL

  ............................ 105 6.2 Elements of the RIIF Language ................. 108 6.2.1 Components and Parameters .................. 108 6.2.2 Failure Modes ........................... 109 6.2.3 Complex Components ...................... 109 6.2.4 Environments ........................... 110 6.3 Worked Examples ......................... 111 6.3.1 Board Level Example ...................... 111 6.3.2 Soft IP Example ......................... 114 6.3.2.1 Technology Mapping .................. 117 6.3.3 Scrubbed Memory Example ................... 1186.4 Extensions to RIIF ........................ 120 6.4.1 Faults versus Errors ....................... 120 6.4.2 Mission Profiles and Timelines ................. 121 6.5 Conclusion ............................. 122

Figure 6 . 2 :

 62 Figure 6.2: Simplified Design Flow of an Automotive SoC

Figure 6 .Figure 6 . 3 :

 663 Figure 6.3: Failure Modes at Different Levels of Silicon Systems

Figure 6 . 4 :

 64 Figure 6.4: Computing Rates of Failure Modes in Complex Components

Figure 6 . 7 :

 67 Figure 6.7: Structure of Board with CPU and RAMs

  Figure 6.10: Fault Propagation Through a Soft CPU Core

Figure 6 .

 6 Figure 6.12: RIIF Model for a Technology Specific SRAM

Figure 6 Figure 6 .

 66 Figure 6.13: Combining CPU and SRAM Models

Figure 6 .

 6 Figure 6.16: RIIF Model for SRAM Model with SEC ECC and Scrubbing

!

Figure 6 .

 6 Figure 6.18: Formalizing the Difference Between Faults, Errors and Failures

  Analysis and Selective Mitigation ......... 123 7.2 Hierarchical SET Analysis .................... 125 7.3 RIIF ................................. 125 7.4 Summary .............................. 126

Figure 7 . 1 :

 71 Figure 7.1: Calculation of Separate CRCs per Design Hierarchy

Figure

  Figure A.1: Structure of a Bloom Filter

Figure A. 3 :

 3 Figure A.3: Architecture Using Two Bloom Filters

  Figure A.4: Modular Detection Architecture

Figure A. 6 :

 6 Figure A.6: Use of Bloom Filters to Reduce TCAM Power Consumption

Figure B. 4 :

 4 Figure B.4: Algorithm for Generating Redundant Logic

3 .

 3 epp n ± z α/2 epp n (1epp n ) n (B.3)blocked because the original function and the other approximation are correct (see figure B.1).

Figure B. 5 :

 5 Figure B.5: Area, Power Overhead versus FIT Rate Reduction

Figure C. 2 :

 2 Figure C.2: Sample BICS Implementation

Figure C. 3 :

 3 Figure C.3: Scan Engine Guided by BICS

Figure C. 4 :

 4 Figure C.4: Reduced Scan Interval due to BICS

Table 1 .

 1 1: SET Pulse Alignment and Capture Probabilities

	Pulse Width	Case	Case Error Probability	Comments
		a					0.0	correct value latched
		b	1 T clk •	tsetup 0	OW t hold +tsetup dOW	set-up time violation
	PW > t setup + t hold	c d	1 T clk •	tsetup+t h tsetup PW-tsetup-t hold OW t hold +tsetup dOW T clk	hold time violation wrong value latched
		e	1 T clk •	tsetup+t h t hold	OW t hold +tsetup dOW	set-up time violation
		f	1 T clk •	t h 0	OW t hold +tsetup dOW	hold time violation
		g					0.0	correct value latched
		h					0.0	correct value latched
	PW < t setup + t hold	i	2 • 1 T clk •	PW 0	OW t hold +tsetup dOW	metastability, partially overlapped
		j	PW•(t hold +tsetup-PW) T clk •(t hold +tsetup)	metastability, totally overlapped
		k					0.0	correct value latched
	Overall	-					PW T clk

Table 2

 2

	.1: Transistor Counts for Basic Design Elements
	Description	Cell	Transistor Count
	INV gate	INV_X1	2
	BUF gate	BUF_X1	4
	OR gate	OR2_X1	6
	XOR gate	XOR2_X1	10
	NAND2 gate	NAND2_X1	4
	2-input mux gate	MUX2_X1	12
	Latch	DLH_X1	16
	DF l i p -F l o p	DFF_X1	28
	D Flip-Flop w SET,CLR	SDFFRS_X1	52
	C-element		12

Table 2 .

 2 2: Comparison of Hardened Sequentials Reported transistor count of Razor-II is 47. Basic latch assumed to have 16 transistors.

	Circuit	setup	Timing Impact hold CLK→Q	Padding	Area	Detection SEU SET	TF	Correction SEU SET	TF
				Single Phase Latches
	DICE	≈0 e	≈0	≈0N o	10T
	Biser	t SET	0	t Celem	No	36T
	Razor-II	00	0	Y e s	31T b	f
	TDTB DSTB	≈000Y e s ≈000Y e s	30T 38T	a
				Two P h a s e L a t ch e s
	Graal	≈0	≈0	≈0Y e s	14T	a
	B-Razor	≈0	≈0	≈0N o	30T d
					Flip-Flops
	Razor-I	t MUX	00Y e s	48T c
	EDC	0	t SET	tmux	Yes	44T
	parity	N • t XOR	00	N o	12T
	SET FF	00	≈0N o	53T
	SET FF det	00	≈0N o	21T
	a The extent of SEU detection depends on timing constraints. See section 2.2.3.2 or
	section 2.2.7.1 for details.

b

Table 3

 3

		Maximum Maximum		Maximum
	Class	Outage	Outage Rate DPM Down Time
		Time (s)	(FITx1000)		(s/year)
	No outage	0	Unlimited	0	N/A
	Low	0.01	30	0.000	0.00
	Medium	3	10	0.008	0.26
	High	180	1	0.050	1.58
	Unrecoverable 1000	1	0.278	8.77
			Total	0.336	10.61

.1: Outage Classes and FIT Rate Targets for Internet Core Routers

Table 3 .

 3 2: Breakdown of Number of Errors By Category

	Fault Injection Result Simulation SWIFI Match
	MCP Hang	14	51	19.6%
	Hang Remote MCP	0	5	0.0%
	MCP Restart	14	15	33.3%
	Message Dropped	58	54	94.4%
	Data Corruption	29	19	78.9%
	No Error	270	241	99.5%
	Total	385	385	83.5%

Table 3 .

 3 3: Comparison of Soft Error Effects Analysis Techniques TDR can only be modeled in simulation with a gate-level netlist and a SDF file. c Through acceleration techniques, the speed of fault injection simulations can be improved. d Most research on probabilistic fault propagation is at the gate level, but recent

	Technique	SEU	SET	Abstraction	Scale	Speed	Domain	FDR	TDR
		Sim. Basic			RTL/Gate	High	Slow c	General		b
	Fault	Sim. Adv.			RTL/Gate	High	Slow c	General		b
	Inject	Emulation		a	RTL/Gate	Medium	Fast	General		a
		Software			Hardware	High	Faster	Processor
		AV F			Arch.	High	Fast	Processor	e
	Analysis	BDD/ADD Probabilistic			Gate RTL/Gate	Low High	Medium Fast	General General
		Formal			RTL/Gate	Low	Medium	General

a Most approaches to fault emulation do not consider temporal delays. Recent work has shown techniques to model SETs [Entrena 2012]a n dt oc o n s i d e rt h ee ff e c to fTDR [Ebrahimi 2014] in emulation. b

Table 3 .

 3 4: Summary of Design Blocks

	Name Function	Number Flops
	epsilon Output data-path	102 559
	gamma On-chip packet storage	341 615
	omega Packets re-assembly from DRAM 184 552

Table 3 .

 3 5: Summary of Average TDR Values

	Block Average TDR Average TDR
	(Slow)	(Fast)
	epsilon 0.71	0.90
	gamma 0.49	0.85
	omega 0.59	0.85

Table 3 .

 3 6: Classification of SEU Effects for Networking Application

	Category Sub-Category System	Description
			Outage
	Masked	Logically	None	Upset state is overwritten after one or more clocks.
		Functionally	None	Upset state remains but has no
				functional effect.
	Corrected		None	Error is corrected (e.g. ECC).
	Detected	Explicitly	Medium	Explicit mechanism detected the error (e.g. parity).
		Indirectly	High	Error detected due to a side-
				effect. (e.g. FIFO overflow).
		Minor	Low	Operation is silently affected, but
	Silent			impact is contained (e.g. single
				corrupted packet).
		Major	Unknown	Internal state is affected causing
				unpredictable effects (e.g. linked
				list corruption).
		Lockup	Unknown	Packet traffic ceases to flow.

Table 3 .

 3 7: CPU Usage During Simulation Campaigns LDR N . Our simulation environment gives us visibility into the full design state so we know LDR N for different values of N.

			Epsilon	Gamma	Omega
	Category	Runs CPU Runs CPU Runs CPU
			%%%
	Fail		2102 26.5	1536 32.4	3312 33.8
	Pass	Matched No Match	7148 32.6 750 40.9	7439 25.0 1025 42.6	4858 10.8 1427 55.4
	or it can occur after N clock cycles,

Table 3 .

 3 8: Observed Effect of SEUs (as percentages)

	Category Sub-Category Epsilon	Gamma	Omega
	Masked	Logically Functionally	71.5 ± 0.8 74.4 ± 0.9 60.7 ± 3.2 7.5 ± 0.5 10.3 ± 0.6 13.9 ± 2.2
	Corrected		0.9 ± 0.2	0.6 ± 0.2	0.8 ± 0.6
	Detected	Explicitly Indirectly	0.1 ± 0.1 13.1 ± 0.6	6.1 ± 0.5 1.0 ± 0.2	6.7 ± 1.6 0.3 ± 0.4
		Minor	5.6 ± 0.4	3.0 ± 0.3 11.6 ± 2.1
	Silent	Major	1.3 ± 0.2	4.7 ± 0.

Table 3 .

 3 9: Percentage of SEUs Producing Serious Outages

	Name	Percentage SEUs Producing aS e r i o u sI m p a c t
	epsilon	1.2 %
	gamma	6.5 %
	omega	5.2 %

Table 3 .

 3 10: Results of Different 95% Confidence Intervals for Epsilon

		Hoefding Normal with	Normal	Student T
		Inequality	p =0.5	with p =p n with p =p n
	epsilon	100%	99.6%	98.4%	97.6 %
	gamma	100%	100%	99.1%	96.8 %
	omega	100%	100%	98.9%	96.8 %

Table 4 .

 4 1: Summary of Design Blocks

	Name	Functional Description	Numb er Flip-Flops
	10GE MAC Simple 10G Ethernet MAC.	1,138
	Epsilon	Data-path with header processing.	102,559
	Omega	Complex packet assembly from DRAM.	184,552

Table 4 . 2

 42

: Simulation Result Classification

Table 4

 4

		.3: Sensitivity of Original Design Blocks
	Name	Number Percentage Percentage Percentage
		Faults	Masked	Minor	Critical
	10GE MAC 10 000	76.1±0.8%	21.9±0.8%	2.2±0.4%
	Epsilon	10 000	79.1±0.8%	19.6±0.7%	1.4±0.2%
	Omega	5 000	69.1±1.3%	19.1±1.1%	11.7±0.9%

Table 4 .

 4

			4: Bus Based Clustering
	Design	Number Average Clusters Clusters Size for 80%	Flops Not in a Bus
	10GE MAC	59	18.6	22	37 (3.3%)
	Epsilon	5,314	20.2	1,580	2,883 (2.6%)
	Omega	12,737	14.1	5,427	18,409 (9.3%)
	4.2.2 Hierarchical Clustering
		Table 4.5: Hierarchy Based Clustering
	Design	Number Average Clusters Clusters Size for 80%
	10GE MAC	10	114	3
	Epsilon	580	190	111
	Omega	1285	154	401

In large designs, certain modules implement functions related to the control path while others contain large data-paths. It is considered good design practice to separate control logic from data-path logic to customize synthesis constraints. It is important to note that certain modules contain non-mission mode logic for debug and thus have a low sensitivity to SEU effects. For these reasons, it is possible to cluster the flip-flops based on the module instance they belong to, as different instances may have different functions. The results of applying hierarchical clustering are summarized in table 4.5. Not surprisingly, there are fewer, larger clusters.

Table 4

 4

		.6: Hybrid Clustering
	Design	Number Average Clusters Clusters Size for 80%
	10GE MAC	93	12.2	23
	Epsilon	209	527	37
	Omega	409	485	82

Table 4 .

 4 7: Reduction in Sensitivity with Full Mitigation

		Bus Based	Hierarchy	Hybrid
	Design	Critical Flops Critical Flops Critical Flops
	10 GE 1.12±0.17%	0.39±0.10%	0.70±0.14%
	MAC	2.0x	15% 5.5x	84% 3.1x	16%
	Epsilon	0.44±0.16% 3.5x 1.9% 4.3x 0.30±0.15% 14% 7x 0.18±0.10% 4.1%
	Omega	3.15±0.49% 3.7x 13.8% 7.8x 1.47±0.28% 36% 14.9x 0.74±0.24% 39%

Table 5 .

 5 2: Gate Count and LDR for Combinatorial Blocks

	Block	Cell	Internal	Error
		Count	LDR	Propagation
	Ripple adder 8 bit	8	1.000	1.000
	Rippler adder 16 bit	16	1.000	1.000
	CLA adder 8 bit	41	0.878	1.000
	CLA adder 16 bit	125	0.759	1.000
	DX Multiplier 8 bit	387	0.928	0.960
	DX multiply 16 bit	971	0.939	0.994
	Equality comparator 16 bit		0.02	0.020
	Equality comparator 32 bit	0.090	0.0632
	ECC encoder 32 bit	61	1.000	1.000
	ECC decoder 32 bit	165	0.778	0.921
	ECC encoder 64 bit	128	1.000	1.000
	ECC decoder 64 bit	308	0.772	0.949
	MUX 8 to 1	7	0.748	0.135
	MUX 16 to 1	21	0.705	0.069
	MUX 64 to 1		0.621	0.018
	Control Register Logic		0.478	0.260
	) ./0123	$%&'( #"()(*
		!"#
		"#
			+,!-	#*$,8(
	4"+56*7
	4"+568(

Table 5 .

 5 3: Simulation Results for Flat Injection Campaign

	Simulation	Num. Num. Setup/	Not	PW De-Rated
	Accuracy	Runs Errors	Hold	Blocked Ratio	FIT
	Zero Delay	25 000	75	0	3272	1.0	0.65e-3
	Zero Delay, S&H Checks 25 000	28	85	3272	1.0	0.61e-3
	Delays, S&H Checks	25 000	45	77	2546	1.5	0.73e-3

Table 5 .

 5 4: Results of Block Level SET Characterization

	Block	Gate INV AND OR XOR CMPLX Intrinsic	Raw Intrinsic FIT
	Name	Count BUF					LDR	<50ps 50..75ps >75ps
	Bitwise AND	32	0	32	0	0	0	1.0	1.3e-3 4.6e-4 8.1e-5
	Bitwise OR	32	0	0	0	0	0	1.0	1.0e-3 3.5e-4 1.4e-4
	Bitwise XOR	32	0	0	0	32	0	1.0	3.3e-3 1.8e-3 1.7e-4
	EQ Compare	46	1	12	1	30	2	0.02	3.9e-3 2.0e-3 2.7e-4
	LT Compare	96	47	1	14	0	34	0.43	6.1e-3 2.5e-3 1.4e-3
	Mux 1	32	0	0	0	0	32	1.0	4.5e-3 2.0e-3 1.2e-3
	Mux 2	32	0	0	0	0	32	1.0	4.5e-3 2.0e-3 1.2e-3
	Adder	204	6	38	70	70	58	0.86	1.9e-2 8.9e-3 2.9e-3
	Multiplier	496	0	256	0	0	240	0.98	4.4e-2 1.8e-2 9.6e-3
	Shift Left	160	0	32	0	0	129	0.70	1.9e-2 8.4e-3 4.8e-3
	Shift Right	196	6	69	11	0	107	0.66	1.8e-2 7.8e-3 4.2e-3
	Output Mux	182	5	42	2	0	133	0.72	2.0e-2 8.9e-3 5.1e-3

  [START_REF] Sanchez-Macian | [END_REF], the authors developed a RIIF model for an SRAM with M words. The model assumes that the memory is subject to transient SBUs at a rate of λ SBU and to permanent Single Bit Hard Errors (SHEs) at a rate of λ SHE . It is assumed that this memory is protected by a Single Error Correct (SEC) ECC. If two bits in a word are wrong (two SBUs, two SHEs or an SBU and an SHE), the result is Silent Data Corruption (SDC).

  .19.

	!"# $%%	+!)' ,-.)./(# /2' 0)*3.	0#(/1# ,-.)./(# /2' &#%.	&!'()'*
		42/)5#
	Figure 6.19: Example State Sequence for an Airplane

Table A

 A In this section, two architectures for detecting errors in TCAMs are described. Both architectures use application aware hashing to insert and query items in a set of Bloom Filters. The first architecture (figure A.3) uses two Bloom Filters, one that take as input the same key that is applied to the TCAM, while the other takes as input the concatenation of the tuple key, entry, where entry is the response of the TCAM to the key input. The first Bloom Filter detects the occurrence of a SEU causing a pseudo-MISS[START_REF] Pontarelli | [END_REF]], i.e. the TCAM reports that the searched key is not present. If this type of error occurs, the output of the first Bloom Filter and that of the TCAM are discordant, the TCAM gives a MISS, while the Bloom Filter gives a HIT. The second Bloom Filter detects the occurrence of pseudo-HIT or multi-HIT errors[START_REF] Pontarelli | [END_REF]], i.e. the TCAM returns an erroneous entry or a MISS condition. This error is detected by the second Bloom Filter, which signals that the tuple {key, entry} in not present in the TCAM. If, due to hash collision, a false positive occurs in the Bloom Filter the error is undetected. The experimental data presented later shows that the occurrence of both an error in the TCAM and a false positive in the Bloom Filter are very low, even with a small Bloom Filter. The experimental data shows up to 100% error detection, when the Bloom Filters are large enough to avoid most false positives. The two Bloom Filters detect disjoint types of errors and the fraction of errors detected by the two Bloom

	A.5 Error Detection Architecture
		.1: Example TCAM Configuration
			TCAM
	Index Feature		Key
		Feature 1 -Binary CAM
			Always Masked	Unmasked
	0	00	XXXX		01_0000_0001
	1	00	XXXX		10_0010_0001
	2	00	XXXX		01_0001_0111
		Feature 2 -Generic Patterns
			Unmasked Generic	Unmasked
	3	01	00	0001	1110_1111
	4	01	01	0010	1010_1110
	5	01	01	0000	1010_0011
	6	01	11	0101	1010_0001
	7	01	11	XXXX	0011_1001
	8	01	00	XXXX	1100_1100
	9	01	00	XXXX	0000_0110
	10	01	00	XXXX	0001_0011
		Feature 3 -Binary CAM
			Unmasked	Always Masked
	11	10	00_0000	XXXX_XXXX
	12	10	00_0011	XXXX_XXXX
		Feature 4 -Longest Prefix
			Unmasked	Prefix
	13	11	10_0010	01XX_XXXX
	14	11	01_0000	1101_XXXX
	15	11	11_0000	1100_00XX

Table A .

 A 2: Simulated Results Using Two Bloom Filter Architecture

	Size of Single	Errors	Errors	Total
	Bloom Filter	Detected	Detected	Error	Total
	(bits)	by Filter #1 by Filter #2 Coverage Overhead
	2K	2013	1307	100%	32%
	1K	2332	1306	100%	16%
	512	2343	1242	100%	8%
	256	2068	1342	98.7%	4%
	128	1911	1168	89.1%	2%

Table A .

 A 3: Simulated Results Using Modular Bloom Filter Architecture

	Size of Single Number of	Total	Total
	Bloom Filter	Errors	Number of	Error	Total
	(bits)	Detected	Errors	Coverage Overhead
	2K	3211	3662	87.6%	32%
	1K	2908	3326	87.4%	16%
	512	3010	3461	86.9%	8%
	256	3130	3669	85.3%	4%
	128	4276	3507	82%	2%

Due to the test methodology, the reported data only includes upsets to the storage nodes (i.e. clock node upsets are not considered).

Ideally each flip-flop would map to two latches. In practice, when the flip-flop circuit is retimed, the cut-point can be wider and additional latches are required.

Little's Law states that the long-term average depth of a queue depends on the average arrival rate and the average waiting time.

Routing tables consist of an address and a subnet mask. When a packet address is looked up, the routing table entry with the longest match, based on the subnet mask, is selected. Normally, TCAMs are not used to store the main routing tables, as more efficient data structures exist, however, sometimes smaller address tables are stored in TCAMs.I nt h i sc a s e ,t h e yc o n t a i ne n t r i e s sorted by the length of the subnet mask.

We primarily consider the effect of logical masking. However, since the approach is based on gate-level fault injections, the effect of electrical masking or pulse stretching would be taken into

In figure 6.6, we present the RIIF code for an environment construct that captures a small subset of the neutron model presented in [JEDEC 2006]. An environment construct has a list of parameters (e.g. location) and it provides a list of generated or output parameters (e.g. neutron flux). Typically, an environment construct is used to encapsulate the operating conditions in a specific product (e.g. temperature, voltage range in an automotive application) and then to consistently apply these parameters to a set of components.

Worked Examples

Board Level Example

The first example developed with RIIF was based on a circuit board with one CPU and with N +1 memory components. We assume that the data in each RAM is The failure modes for the processor are defined and the equations above are used to calculate the SDC and DUE rates. The RIIF language is not procedural, thus the ternary operator (?:) is used to conditionally select which faults contribute to SDC or DUE based on the chosen cache protection scheme.

Use of Bloom Filters to Protect TCAMs

This appendix presents the results of a collaborative research project between University Rome 'Tor Vergata', TIMA Laboratory and Cisco Systems. The content is based on a paper which was presented at DATE 2013 [Pontarelli 2013b].

A.1 Introduction

A Content Addressable Memory (CAM) memory is capable of comparing a word of input data against all the data words stored in the memory, and provides as output the address of the first stored word which matches the input data. In a binary CAM, the memory entries are composed only of 0's and 1's. A TCAM also allows the entries stored in the memory to contain 'X' bits which represent a don't care value. This provides a compact means to store a large set of match patterns. For example an entry 10XX1 in a TCAM matches the following four patterns 10001, 10011, 10101, 10111. The typical implementation of the don't care bits is obtained by defining a mask string for each entry of the TCAM. In the previous example the mask string would be 00110 while the actual entry is 10--1 where -can be either 0 or 1. TCAMs are widely used in high speed network systems to implement features such as classification and access control [Chao 2002]. In fact, their ability to perform massive comparisons with O(1) complexity makes them extremely appealing for searching large tables with very low latency. The use of the X's makes it possible to apply admission or quality of service (QoS) policies to classes of traffic using a modest number of table entries. Currently, the use of nanometer scale technology, the reduction in operating voltages and the increase in the overall number of stored bits have caused a consequent increase in the rate of occurrence of SEUs. ECC is highly effective at protecting regular memories. It is difficult to apply techniques based on information redundancy to TCAMs because all entries are accessed simultaneously, thus the actual checking circuitry must also be replicated for each entry. Networking systems based on TCAMs require high reliability and new approaches are required to mitigate the effects of SEUs.

In the literature different techniques have been proposed to mitigate the effects of SEUs in TCAMs. Most techniques operate at the circuit level and require modifications to the CAM architecture [Krishnan 2009] or are based on a background parity scan which has a long detection latency. In order to illustrate the method, a sample 16-bit wide TCAM configuration is shown in table A.1. In this example, the TCAM contains four features:

• Feature 1: In this feature, the TCAM is configured to act as a binary CAM.

The entries for this feature are composed of three fields. The first field (00) identifies the feature. The second field represents bits that are not used and is always masked and the third field is always unmasked. This feature acts as a1 0b i tb i n a r yCAM. Based on the above rules, only bits in[9..0] of the input data is hashed.

• Feature 2: The feature is composed of four fields. The first two bits (01) identify the feature, the second field, composed of two bits, is always unmasked. The third field is generic (i.e. can be masked or unmasked), while the last field is not used and is always unmasked. For this feature, the input to the hash function is the concatenation of three bit vectors: {in[13..12],

.0] Using this vector as input for the Bloom Filter, when the third field presents unmasked entries, a regular item is inserted in the Bloom Filter. For the masked entries (e.g. the entries with the X's ) the XOR compression reduces the number of X's in the input to the Bloom Filter to a single bit. At this stage we can expand the don't care, inserting the two items corresponding to '0' and '1' into the Bloom Filter. This type of compression works well for generic fields where the values of this fields often present some regularities that are repeated among the different entries. data set provided by Cisco Systems. Ten thousand simulations were run where a fault was injected into the TCAM for each run. The activation of the fault was determined by comparing the output of the TCAM under test, with the output from a golden TCAM. For the activated faults, the number of faults detected by the proposed architectures is reported. We compute the area overhead as the number of bits of storage in the Bloom Filter with respect to the number of configuration bits of the TCAM. This is a somewhat pessimistic, as the real silicon area required to implement a glsTCAM cell is roughly twice the area of an SRAM cell, since the glsTCAM cell also contains matching logic. We do not evaluate the logic required to implement the hash function of the Bloom Filters, since it is composed of only a modest number of XOR gates and is small compared to the area required for the memory. The two architectures presented in the previous section have been simulated, and the size of the Bloom Filters has been varied, in order to study the impact of false positives on the efficiency of the proposed methods. For the second architecture the analysis is limited to M = 4, since the TCAM configuration was too small to benefit from a larger value of M. The results reported in table A.2 show that the errors in the TCAM are detected by one of the two Bloom Filters used in the first architecture (see figure A.3). As expected, the set of errors detected by the two Filters is disjoint, and the two Filters are able to detect 100% of injected faults when the size of the Bloom Filters is sufficiently large. Even without considering that SRAM memory cells are smaller than TCAM cells, the ratio 8% is less than the nominal 12.5% overhead that would be required for byte-wise parity. When the overhead is further reduced to 4% or 2% the effect of false positives in the Bloom Filters produces some undetected errors, decreasing the error coverage to 98.7% and 89.1% respectively.

In table A.3, the results for the second architecture (see figure A.4) are reported. As expected, even with a large Bloom Filter, the error coverage is less than 100%, due to the aliasing of the modular operation. However, the ratio of undetected

Approximate Logic Functions for Protection of Combinatorial Logic

This appendix presents the results of a collaborative research project between the University of Saskatchewan (Canada), iROC Technologies and Cisco Systems. The content is based on a paper which was presented at SELSE 2014 [START_REF] Xie | [END_REF]].

B.1 Introduction to Logic Repair

In chapter 1, it was identified that faults in combinatorial logic are more difficult to analyze and mitigate than those in memories or sequential elements. In modern technologies, permanent faults are a growing concern and it is now standard to implement in-field repair techniques for memories. Equivalent repair techniques do not exist for combinatorial logic, although different approaches have been proposed. Redundant logic is a technique that can mask both transient and permanent faults in combinatorial logic. Generally, the approaches to manage faults in combinatorial logic can be divided into three categories : approaches based on coding, approaches using on-line test and approaches based on defect aware synthesis.

Many authors have studied extending the coding techniques used for memories (Hamming, Berger, weight-based codes) to detect errors in combinatorial logic [START_REF] Das | [END_REF], Leveugle 2002]. In [START_REF] Dutta | [END_REF]], a selective error correction technique is proposed with area overheads from 49% to 153%, however, it results in many additional layers of logic and is thus not applicable to high-speed designs.

Another approach to manage faults in combinatorial logic is through on-line self test and selective hardware sparing. On-line testing is possible when portions of a circuit can be periodically taken off-line for test. For example, in [START_REF] Li | [END_REF]], N+1 sparing is implemented on a 16 channel DMA controller to achieve an 87% repair coverage with a small (6.3%) area overhead. Approaches based on on-line testing can be highly effective; however, they remain application specific. Special techniques exist for specific types of circuits such as arithmetic circuits [Nicolaidis 1997, Nicolaidis 1998] and digital filters [Bayraktaroglu 2000] but there do not exist general techniques to add on-line testing and sparing to a generic digital circuit. Normally, the goal of logic synthesis algorithms is to produce a circuit with minimum area within a given timing constraint, thus redundant logic is eliminated. In faulttolerant synthesis, the mapped circuit intentionally contains redundancy in order to mitigate faults. Redundant logic functions [START_REF] Mohanram | [END_REF], Sierawski 2006, Sanchez-Clemente 2012, Adeleke 2012[START_REF] Yuan | [END_REF][START_REF] Choudhury | [END_REF]

fall into this Combinatorial Logic

Using the number of cubes and the estimated EPP, the FR is computed for each cube and the cubes are ranked. Due to the error bars, at the top of the list, there may be multiple overlapping best candidates. In this case, additional faultinjections are performed, in groups of N step , in order to further reduce the error bars. Additional simulations are only run for those cubes that are potentially the best candidate, based on their error bars. A maximum of N max simulations are performed and if there are still multiple candidates, the term with the best FR is simply selected, disregarding the other candidates whose FR estimate may overlap. In these cases, there is little difference between the best candidates.

Consider the example logic function shown in figure B.3. After the first round of the algorithm, with 20 fault-injections, the results are shown in table B.2 . The term 0--1 has the highest FR metric, however, there are three other terms (-11-,--10,11--) with FR metrics that could overlap, due to the error bars. The remaining ten terms (shown in grey) can be eliminated as their FR metric is too low, even considering the error bars, which are calculated using equation B. After additional fault injections, the term 0--1 is selected as the first term to add to F. Before proceeding to the next round, the table of min/max-terms must be updated to reflect the overlap between 0--1 and the other terms. For example, the number of terms for the cube 0-1-is reduced to 2 (0011 and 0111).

For the next round, new fault injections must be performed to reflect the coverage provided by the redundant logic that has been added. Note, however, that this is only necessary for terms that overlap with the newly added, redundant term.

Furthermore, the new FR can only be lower than the FR metric from the previous round, thus the previous FR estimate serves as a valid upper bound. Additional fault-injections are only performed for those terms which are potentially the next B.4. Experimental Results 145 best-candidate in the following round. In this way, a sequence of F, H functions are generated with each one providing increasingly better coverage of G, taking into account the actual failure rates of the library gates over a set of actual input vectors.

B.4 Experimental Results

Selected

LGsynth93 and ISCAS benchmark circuits were synthesized into the 45nm Nangate Library [Nangate 2008]u s i n gS y n o p s y sD C TM .F o rb o t ht h eo r i g i n a la n d the protected circuits, the FIT rate was evaluated using equation B.1.F o r t h e purpose of evaluating the initial circuit-level FIT rate, 10,000 fault-injections were performed, to ensure small error bars. An arbitrary FIT rate (f i ), was assigned to each gate, proportional to the number of transistors in the gate.

We present the results as the FIT rate reduction which is the ratio of the protected FIT rate to that of the original circuit. It is important to note that this metric reflects the fact that failures can occur in the redundant logic and thus represents a net FIT rate reduction. If the original FIT rate was 10 and the FIT rate with the redundant logic is 5, the reduction is 2x.

The algorithm described in section B.3 was implemented using a Ruby script. The parameter N batch was set between 20 and 100 based on the size of the circuit. N max was set to 200 and N step was set to 10. An 80% confidence interval was used (z α/2 =1 .28) when evaluating the error bars. The cubes were generated with Espresso and the fault-injection simulations were performed with Mentor's Modelsim TM . The redundant logic functions (F, H) produced by the script were synthesized with Synposys DC TM . During synthesis, the tool was allowed to share logic between the F and H functions across multiple outputs but it was ensured there was no logic sharing with the original function G. We note that this approach is different from [Sanchez-Clemente 2012] where sharing between F and H was explicitly prevented during synthesis. When logic sharing is prevented, faults in one of the approximate functions are fully