Behavioral transformations to increase the noise immunity of asynchronous specifications

Behavioral Transformations to Increase Noise Immunity in Asynchronous Specifications Alexander Taubin The University of Aizu, Japan Alex Kondratyev The University of Aizu, Japan Jordi Cortadella Univ. Polit`ecnica de Catalunya, Spain Luciano Lavagno Politecnico di Torino, Italy Abstract Noiseimmunityisbecomingoneofthemostimportantdesign parameters for deep-sub-micron (DSM) technologies. Asynchronous circuits seem to be a good candidate to alleviate the problemsoriginatedbysimultaneousswitchingnoise. However, they are also more sensitive than synchronous ones to spurious signal transitions and delay variations produced by crosstalk noise. This paper addresses the problem of analyzing and synthesizing asynchronous circuits with noise immunity being the main design parameter. The techniques presented in the paper focus on cross talk noise and tackle the problem from the behavioral point of view. 1 Introduction The technology of interest for research on CAD for integrated circuits aimed at a 10-15 year time frame shouldassume feature sizes below 100 nm (deep sub-micron or DSM). Accordingto the National Technology Roadmap for Semiconductors (NTRS’97) the prediction for the year 2009 is: technology norm  0 : 07 m , 520Mtransistorsper chip, 2500MHzon-chip clock, area  620 mm 2and 8-9 wiring levels [5, 10]. It is now common to pointoutthat forDSM noiseimmunityis becoming a metric comparable in terms of importance to area, timingand power [5, 9, 25]. Among noise sources one usually considers the following:  cross couplingcapacitances and charge sharing (crosstalk),  power and groundnoise, includingsimultaneousswitching noise,  alpha particle radiation,  substrate noise,  electro-magnetic radiation from external sources. Immunityagainstexternal noisesources(thelastthreeitems) can be ensured for DSM by the same means as for VLSI (by means of appropriate packaging and electro-magnetic isolation). Contrary to that, the problem of internal noise immunity becomes much more severe due to the followingreasons:  increasingcapacitivecoupling(closerpacking,nonuniform geometrical scaling, etc.),  lower noise margins (due to scaling down power supply and threshold voltage),  higher speed of voltage changes. Crosstalk and simultaneousswitching noise are identified as a major source of problems duringDSM layout synthesis. The absence of a common clock in asynchronous systems somewhat helps to avoidthe simultaneousswitchingnoise. Recent investigations [19] show that by a self-timed approach one might reduce not only simultaneous switching noise, but also the high frequency components of noise (400% reduction for peak switchingcurrent [19])and Electro-MagneticInterference by an order of magnitude with respect to a comparable synchronous design. However,forcrosstalknoiseanasynchronousapproachgives no immediateadvantage in comparison tosynchronouscircuits. A straightforward way to reduce noise would be to constrain the layout synthesis step, by forbidding the adjacency of noisy wires. The drawback of this approach is that the information on which wires are subject to crosstalk will be available, with current synthesis-based methodologies, only at a later stage (namely after extraction and back-annotation). Crosstalk noise reduction thus requires a potentially large number of iterations between layout and analysis steps, without any guarantee of convergence. Thus researchers are beginning to advocate a new design flow, in which design errors (in particular due to noise) are identified as early as possible in the flow, and avoided by constraint propagation to subsequent steps. Hence one can speak of “design for low noise” in the same way as design for low power or design for testability. An important step in this directionwas made by Kirkpatrick and Sangiovanni-Vincentelli in [11, 12]. They suggested to extract information about the possible sources of noise at the logic(gatenetlist)level, anduse ittoguidethelayouttools. The goal of this paper is to extend that work to the asynchronous sequential logic level, so as to raise the level of abstraction to the asynchronous behavior level. The possible advantages are twofold: 1. wecanapplytothereductionofnoiselocaltransformations thatareonlypossibleatthebehavior level (e.g., reshuffling of transitions), 2. we provide a uniform approach for noise analysis and avoidance in both sequential and combinational circuits, while the methods of [11, 12] were mainly targeted for combinationalcircuits(theanalysisofsequentialpartswas complex and approximate). These techniques can be combined together with traditional methodsforconstrainedlayoutsynthesis. Behaviortransformations make the layout problem much easier, because they partly (and sometimes completely) remove the sources of crosstalk noise. The noveltyof this work with respect to existing approaches for noise avoidance is illustrated in Figure 1. engine Logic circuit Simulation Behavior specification Low noise implementation tool Layout constraints on wire adjacency constraints on wire adjacency Physical level Analysis engine Synthesis tool Gate level reshuffling, etc. Analysis engine Timing information This paper SangiovanniKirkpatrick, Vincentelli Behavior level Figure 1. Techniques for low noise design In this paper we concentrate on noise avoidance within control circuits only, for the following two main reasons: 1. Datapaths are very regular, hence during layout the task of noise avoidance within the datapath itself is easier to solve. Moreover, datapath and control can be segregated reasonably well, thus reducing the possibilityof crosstalk between these two. 2. In general it is possible to use a behavioral description in which the datapath transitions are specified together with control events, as symbolic events. This extension would allowonetoconsideralsothedatapathwithinthesuggested framework. The paper is organized as follows. Section 2 discusses the source of crosstalk noiseand its effects in terms of circuit faults. Section 3 reviews some asynchronous behavior models: State Graphs (SG) and Signal Transition Graphs (STG). Sections 4 and 5 present and extend the concept of digital sensitization to asynchronous sequential circuits [11, 12], and apply it to the analysis of crosstalk noise. Section 6 discusses under which conditions one can use behavioral (SG and STG) models for noise analysis, instead of detailed simulation or conditions developed for combinational logic in previous work. Section 7 sketchessomeofthealgorithmsforanalysis(noise-isolatedpair extraction) and synthesis (aggressor concurrency reduction and reduction of temporal adjacency) based on the previous discussion. Section 8 describes preliminary experimental results that show the promise of our approach. Section 9 concludes the paper and discusses several topics for future research. 2 Crosstalk Noise and Circuit Faults Two main types of faults can be caused by noise [20]. Definition 2.1 (Noise-Generated Faults) 1. Transient fault: a signal temporarily changes its logical value due to noise. 2. Delay fault: the delay of a wire or wire segment (e.g., a segment of wire after a fanout fork) exceeds the specified worst case.1 The source of crosstalk noise lies in the interaction between adjacent wires, due to the coupling capacitance between them (hence it is also called coupling noise). Of course, working at the logic level means that we must talk about the future possibilityof such interaction, if layouttools do not take appropriate precautions (e.g., shielding, segregation, and so on). For an arbitrary pair of wires (a, v) we will call athe aggressor and vthe victim, if a transition on amight produce a noise-generated fault on (any segment of) v. Clearly, the same pair of wires can play opposite roles in different phases of the operation of the circuit, and even at the same time. Noise analysis at the layout level can be confined to immediate adjacent lines, since they act as shields and protect a “victim”fromother “aggressors” [30]. The totalcrosstalk noise voltageon a wire can be computed as the sum of the individual noise contributions of each of adjacent aggressors. Transient and delay faults generated by noiseare of a different nature and can happen in two different scenarios. 1. In order for a transient fault to occur on a victim line that should normally keep a stable value, a short pulse must be generated on the victim due to transitions on adjacent aggressor lines. Fortunately, thevoltage swing of a victim line in response to a transition on a single adjacent line is small enough [9, 8] and can be successfullyfiltered by the rest of the circuit. However, the cumulative effect of two 1This case is dangerous even for asynchronous circuits, because it can violate some timing assumptions (e.g., Fundamental Mode or Isochronic Fork) that ensure correct operationsof an asynchronouscircuit. 2 linesswitchingin thesame directionmightproduceapulse sufficient to be sensed by gates connected to the victim line. Therefore for transition faults we will consider only the situations when two or more aggressors are switching the same direction. Figure2from[9]illustratesthiscase. Thecouplingvoltage noise on the center wire ( V coup ) can be expressed as: V coup = V sw  2 C c = ( C sub + 2 C c ) ,where C c is the coupling capacitance between two adjacent wires, C sub is the capacitance between the center wire and the substrate, and V sw is the switched voltage [9]. C CC CC SUB Figure 2. Simplified cross section of wires With the help of this simple model, one can check that even for 0 : 5 m CMOS technology (with single minimal spacing) the crosstalk voltage can be larger than the total noise margin ( V coup = 0 : 59  V sw ). The explanation of this phenomenon lies in nonuniform scaling: lateral dimensions are aggressively scaled, while vertical dimensionsare practically unchanged from one generation to the next. This results intheincrease ofthehorizontalcoupling component, and a larger swing of the crosstalk voltage. A knowndesign solutionis to space thetracks further apart thantheminimum. However, thisdoes notextend toDSM. Evenwithalinespacingthatistwicetheminimum,fora70 nm technology the coupling noise due to two aggressors switching in the same direction, with the victim wire in between, will exceed 30% of V dd [5]. Therefore, solving the problem of crosstalk noise in DSM requires a design methodologythat does not tackle it at the layout level only, but at the logic and behavioral levels as well. 2. When considering delay faults due to noise, one should consider a different scenario. A delay fault happens because ofan interactionbetween wireshavingsimultaneous transitions in opposite directions [11, 12]. The coupling between them might induce an additional delay by injecting charge on the more weakly driven wire, which will slow down its switching2. Faults generated by noise are dangerous only if they can influence the rest of the circuit. In this sense we can consider noise generation and noise propagationconditions. In order to 2Theoppositecase,makingsometransition faster when neighboringsignals switch in the same direction [8, 32], might also be a problem. For example, it could violate timing assumptions such as isochronic forks. However, it does notneedspecialconsideration,sincetheeffects ofspeedingup sometransitions in asynchronouscircuits can be modeled as slowing down other transitions. increase noiseimmunity,one can either reducenoisegeneration or reduce noise propagation. These issues are considered in more detail in Section 4. 3 Basic notions 3.1 Basic definitions about Boolean Functions An incompletely specified (scalar) Boolean function is a functional mapping F : B n !f 0 ; 1 ; ,g ,where B = f 0 ; 1 g and ’ , ’isadon’t care value. The subsets of the domain B n in which F has a 0, 1 and don’t care value are respectively called theOFF-set,ON-set andDC-set of F . F iscompletelyspecified if its DC-set is empty. A point (i.e., binary vector of values) in the domain B n of a function F (not necessarily in its ON-set) is called a minterm. Let F ( x 1 ;x 2 ;:::;x n ) be a Boolean function of n Boolean variables. The set X = f x 1 ;x 2 ;:::;x n g is called the support of the function F . In this paper we shall mostly be using the notion of true support, that is defined as follows. A variable x 2 X is essential for function F (or F is dependent on x ) if there exist at least two minterms v 1 ;v 2 different only in the value of x , such that F ( v 1 ) 6 = F ( v 2 ) . The set of essential variables for a Boolean function F is called the true support of F .Let F ( X ) be a Boolean function with support X = f x 1 ;x 2 ;:::;x n g .Thecofactor of F ( X ) with respect to x i ( x i )isdefinedas F x i = F ( x 1 ;x 2 ;:::;x i = 1 ;:::;x n ) ( F x i = F ( x 1 ;x 2 ;:::;x i = 0 ;:::;x n ) , respectively). The well-knownShannon expansion ofa Boolean function F ( X ) is based on its cofactors: F ( X )= x i F x i + x i F x i . The existential abstraction of a function F ( X ) with respect to x i isdefinedas 9 x i F = F x i + F ¯ x i . Theexistentialabstraction can be naturally extended to a set of variables. The Boolean difference,orBooleanderivative,of F ( X ) withrespect to x i is defined as  F = x i = F x i  F x i . Acontrollingset forabooleanfunction F withatruesupport f x 1 ;:::;x n g isaaset C of values of variables f x 1 ;:::;x i g such that F ( C; x i + 1 ;:::;x n ) hasthesame value,foranyvalues of the other variables x i + 1 ;:::;x n . Otherwise a set of values at f x 1 ;:::;x i g is called non-controlling. The characteristic function of a set S of n -dimensional boolean vectors is a boolean function F : B n ! B such that s 2 S , F ( s )= 1. 3.2 Behavioral models and Logic Implementability In this subsection we assume the reader to be familiar with Petri nets, a formalism used to specify concurrent systems. We refer to [23] for a general tutorialon Petri nets and to [15] for a review of applications of Petri nets to asynchronous design. 3.2.1 State Graphs AState Graph (SG) is a labeled directed graph whose nodes are called states. Each arc of an SG is labeled with an event, 3 that is a rising ( a + ) or falling ( a , ) transition of a signal a in thespecified circuit. We also allowthe notation a  if we are not specific about the direction of the signal transition. The set of signals of an SG is called X = I [ O ,where I and O denote the sets of input and output signals respectively. The behavior of the input signals is determined by the environment, whereas the behavior of the output signals must be implemented by the circuit3. We write s a ! ( s a ! s 0 ) if there is an arc from state s (to state s 0 ) labeled with a . A labeling function v : S !f 0 ; 1 g n assigns a vector of signal values to each state ( n = j X j ). We will call v a ( s ) the value of signal a in state s .AnSG is consistent if: s a + ,! s 0 = ) v a ( s )= 0 ^ v a ( s 0 )= 1 s a , ,! s 0 = ) v a ( s )= 1 ^ v a ( s 0 )= 0 s b  ,! s 0 ^ a 6 = b = ) v a ( s )= v a ( s 0 ) 3.2.2 Signal Transition Graph A Signal Transition Graph (STG) is a Petri net in which transitions are labeled with the same type of events that we defined for SGs, i.e. rising and falling signal transitions[4]. An STG has an associated SG in which each reachable marking corresponds to a state and each transition between a pair of markings corresponds to an arc labeled with the same event as that labeling the transition. Although STGs with bounded reachability space and SGs have the same descriptive power, STGs can usuallyexpress the same behavior more succinctly. Figure3.a depicts an STGwiththreesignals. Forsimplicity, places with only one input and output transitions are omitted. Figure3.bshowsthecorrespondingSG,withstateslabeledwith the binary vectors of the signal values. The SG is consistent. Inadditiontoconsistency,speedindependenceandComplete State Coding (CSC) are two properties required for an SG to be implementable as a hazard-free asynchronous circuit [13]. 3.3 Excitation and quiescent regions. Next-state function. The excitation region (ER)ofevent a  is the set of states such that 8 s 2 ER ( a  ) : s a  ! .Thequiescent region (QR) of event a  with excitation region ER ( a  ) , is a set of states in which a is stable and keeps the same value, i.e. for ER ( a +) ( ER ( a , ) ), a is equal to 1(0) in QR ( a +) ( QR ( a , ) ). In Figure 3.b, ER ( x , )= f 101 ; 111 g and QR ( x , )= f 001 ; 011 ; 010 g . The symbol 0  (1  ) indicates that a rising (falling)transitionof thecorrespondingsignal is enabled in that state. The implementation of an SG as a logic circuit is done throughthe definitionof the next-state function for each output 3In general this may require the creation of new internal signals. In this paperwe only considerSGs that are already implementablein a givenstandard cell library. See [6] for techniques to ensure gate-level implementability. signal and binary vector. It is defined as follows: f a ( z )= 8 < : 1if 9 s 2 ER ( a +) [ QR ( a +) s.t. v ( s )= z 0if 9 s 2 ER ( a , ) [ QR ( a , ) s.t. v ( s )= z , otherwise The next-state function f a is correctly defined when the SG has the CSC property, i.e., when there is no pair of states ( s; s 0 ) such that v ( s )= v ( s 0 ) and s 2 ER ( a +) [ QR ( a +) and s 0 2 ER ( a , ) [ QR ( a , ) . Note that f a is an incompletely defined function with a don’t care (DC) set corresponding to those binary vectors without any associated state in the SG. In the SG of Figure 3.b, the DC set is empty since all binary vectors have a corresponding state in the SG.Asanexample, f ( 101 )= 011 since signals x and y are enabled in that state. The Karnaugh maps for the next-state functions are depicted in Figure 3.c. From the next-state functions, a logic circuit can be derived by implementing the boolean equation of each output signal as an atomic complex gate, as shown in Figure 3.d. This is called acomplex gate implementation. If the original SG is consistent and speed-independent then the corresponding complex gate implementation will be speed-independent as well [22]. 4 Digital Sensitivity and Noise Avoidance The digital sensitivity approach [11, 12] suggests a constraint-drivendesignmethodologyinwhich theinformation extractedfromlogicalortimingcorrelationsbetweensignalsare provided to a layout synthesis tool (a constraint-based channel router). In the simplest case this information indicates which sets of wires should not be routed adjacent to each other, because of the logical possibility of noise. The latter gives a set of (usually conservative) constraints for a layout tool, that if satisfied guarantee that a circuit does not have noise-generated faults. Fromthe discussion ofSection 2 on thesources of thefaults, it follows that noise generation always happens due to several signals switching at the same time. Therefore, conditions for noise generation can be checked by analyzing the concurrency relations between signal transitions. The information on concurrency is explicitly represented in the behavior models that we consider. In particular, two transitions a  and b  are concurrent ( a * jj b  ) if they are enabled in the same state of an SG, and firing of one of them cannot disable the other. Formally, in the case when a  = a + and b  = b + e.g. a + concurrent to b + means that there exists state s in an SG such that: 1) s a + ! s 1 ^ s 1 b + ! and 2) s b + ! s 2 ^ s 2 a + ! . The following SG-based algorithm identifies sets of wires thatmightpotentiallybesources of noisefaults. This algorithm formalizes the conditions of occurrence of noise faults which were presented in Section 2. Example 4.1 Let us apply the algorithm in Figure 4 to the example in Figure 3. In the corresponding SG there are only two states from which signals might fire concurrently: 11*0* 4 x z y x+ z+ xzy+ yxyz 0*10 11*0* 100*1*1*1 1*01 001* 01*1 00*0 x+ y+ z+ yzxy+ y+xz+ a) b) d) c) 0 1 0 100 01 x=(z+x’y’)’ y=(x+z)’ z=x+yz 0 111 0 yz x00 01 11 10 0 11 yz x00 01 11 10 0 1 yz x00 01 11 10 0 10000 0011 01 Figure 3. (a) STG,(b)SG, (c) next-state functions, (d) complex-gate implementation. Input: Initial SG A Output: Set N oise of potentially noisy wires foreach s 2 A do /* Check delay faults */ foreach pair a; b s.t. v a ( s )= 1* ^ v b ( s )= 0* ^ a - jj b +do Del f aul ts = Del f aul ts [f a; b g ; /* Check transient faults */ foreach triple a; b; c s.t. v a ( s )= 1* ^ v b ( s )= 1* ^ v c ( s )= 1 ^ a - jj b -do T r ans f aul ts = T r ans f aul ts [f a; c; b g ; foreach triple a; b; c s.t. v a ( s )= 0* ^ v b ( s )= 0* ^ v c ( s )= 0 ^ a + jj b +do T r ans f aul ts = T r ans f aul ts [f a; c; b g enddo N oise = T r ans f aul ts [ Del f aul ts Figure 4. Analysis for noise fault and 1*1*1. The former implies the possibility of delay faults for the pair of wires ( y; z ) , whilethe latter might be the source of a transient fault for the triple ( x; z ; y ) ,where z is the victim and x; y are the aggressors (for a triple, the order of signals is important;thevictim isalwaysplaced between the aggressors). Hence in this example N oise = f ( y; z ) ; ( x; z ; y ) g . Forthosesignalsthatsuccessfullypass thecheck aboutnoise faults (i.e. for those that are not included in the N oise set) we will talk about logic separation. Hence, so far the notion of logic separation of signals is based completely on the analysis of the ordering/concurrency relationsbetween transitionsin the behavioral (STG) specification. However, two transitions that are concurrent in the specification do not necessarily happen (“fire”) concurrently in the circuit. This is because delays of circuit gates and wires may actually cause two signals that are specified as concurrent (e.g., pairs of gates triggered by the same transition) to actually always occur in a specific order. For this reason, the concurrency relation in the specification is a conservative approximation of reality. Refinement of concurrency is thus possible, either by considering the implementation (when delay estimation becomes possible)or by making some “reasonable” timing assumptions, which must then be satisfied (e.g., by transistor sizing or constrained routing) by the implementation. If signals are not logically separated, but according to these timing informations we can conclude that, for example, they cannot switch at the same time, we will talk about temporal separation. Temporal separation can be checked in a way similar to the algorithm of Figure 4. In [29, 14] it was shown that timing constraints can be captured at the STG level, by introducing timing arcs that reduce the potential concurrency of signals. From such STG with timing arcs one can generate the SG and apply the same algorithm to it. The resulting N oise set will contain tuples of signals that do not have logical nor temporal separation. A further refinement of these sets of potentially noisy signals could be obtained by considering the noise propagation conditions. If some signals are not separated (logically or temporally) and could generate a crosstalk noise, we would still have no problems if the generated noise faults could not propagate through the circuit. Suppose, for example, that a transient fault on wire a happens at a time when for all fanout gates of a some input different from a has a controlling value. Then the behavior of the fanout of a does not actually depend on the value a , and any transient fault affecting a could not propagate within the circuit (the formal conditions of noise propagation are considered in Section 5). If for a set of signals the conditions for noise generation or propagation are not satisfied, then the set is said to be isolated from crosstalk noise.Thelevelofdigital isolation from crosstalknoiseisthepercentageofsignalpairsforwhichthecircuit isisolatedfrom crosstalk noise (isolatedpairs),considering each signal as a victim candidate. According to [12], about 50% of digital isolation is needed tohave a reasonable impact on thereductionof circuit area after layout, due to a smaller set of layout constraints. Themain improvement introducedby thisworkwithrespect tothe contributionof[11,12] is theconsiderationof behavioral sequentialmodels in thedigital sensitivityapproach. The STGand SG-based methods that we suggest can be useful both for efficient derivationofisolatedpairsand forincreasing thedigital isolationthrough specification transformations. InSection8itwillbeshownthatthecombinationofbehavior transformations together with reasonable timing assumptions allows us to reach about 80% of digital isolation in average. The methodologyfor low-noiseasynchronous circuit design includes the followingsteps: 1. Analysis of noise-critical sets of signals. This reduces 5 to checking logical and temporal separation on a behavior specification, and providing the layout tools with constraints on adjacency of critical wires. 2. Improving logical and temporal separations of signals. This might be achieved by optimizations of behavioral specifications aimed at noise avoidance. These optimizations include a)signalreshufflingandconcurrency reduction[7](logical separation) and b) timing assumptions [14] (temporal separation). 3. Logic optimization for low noise. Logic functions for gates might be chosen according to a cost function evaluating noise. This requires different approaches to minimization (e.g., introducing redundancy in the circuit in order to avoid noise propagation). Similar ideas were exploitedin an alternative wiringscheme from [18]. 4. Clustering for reduction of crosstalk noise. Interconnections could be divided into local and global levels.  The global level (top layers of interconnect structure [2]) should include all (or most of) the long wires that couldbe dangerous from the point of view of crosstalk just because of the long cross couplings.  The local level (lower layers of interconnect) should be used only for short distance interconnects, but couldstillsuffer fromcrosstalknoisebecause ofhigh density (local lines are usually restricted to lengths less than 3mm, however starting at technologies beyond0.18  m they become vulnerableto crosstalk as well [25]). We could potentially exploit this fact and dividelarge circuits into relatively small “islands”, connected with each otherby global and vertical interconnects. Crosstalk noise analysis and synthesis could be done separately for each “island”, thatcould be small enoughto applyour behavior specification techniques The techniques presented in the paper mainly concern items 1, 2 and 3 from the list above. Item 4 gives a more systematic approach for the avoidance of noise, but it is still an open area for research. 5 Digital sensitivity analysis The analysis of logical or temporal separation4requires one to consider each signal as a potential victim, and identify sets of states in which the signals might be a subject to noise faults. Definition 5.1 (Fault Sets) 4As mentioned in Section 4, temporal separation can be reduced to logic separation by considering the SG obtained from an STG with added timing constraints. 1. Thetransient faultsetwithrespect tosignal b (denotedby S tr ( b ) ) is the set of SG states such that 8 s 2 S tr ( b ) there aretwoenabledsignals a and c , whichhavethesamevalue as b . 2. The delay fault set with respect to signal b (denoted by S del ( b ) ) is the set of SG states such that 8 s 2 S del ( b ) , b is enabled and there exists another signal a enabled in s , with the opposite logical value to b . 3. The noise fault set with respect to signal b (denoted by S n ( b ) ) is the union of the transient and delay fault sets. Note that these three sets are subsets of those (of aggressor/victim signal tuples) computed by the Algorithm in Figure 4. The conditionsunder which a noise tuple is not actually dangerous differ for transient and delay faults:  A transient fault appears as a short pulse (hazard) on a wire when it should keep its value stable. Therefore circuit malfunction is avoided if each one of these pulses is eithereliminated (bychanging the behavioral specification or the logic), or identified as not dangerous (because the involved signals actually do not switch concurrently due to some known timing propertiesof the circuit), or filtered by the circuit (if its fanout gates are not sensitive to its changes, or due to the inertial nature of gates). In this work, we will use sensitivity analysis to identify potentially dangerous transient faults, and logic (concurrency reduction) as well as timing methods to eliminate those that have been identified as dangerous.  A delay fault happens when a signal is changing according to the specification, but the delay of its transition is affected by noise. In this case, it is impossible to filter the propagation of the transition, because it is part of the functional specification. Therefore, the fault can be either eliminated or identified as not dangerous (in the same way as in the case of transient faults). The latter can be done by a timing analysis of the fault conditions, and is discussed in Section 6. In the rest of this section we will concentrate on logicmethodsfor checking and avoiding noise. They can be naturally illustratedby the consideration of transient faults. The extension of the technique to delay faults is discussed later in Section 6. Transient fault propagation. The formal conditions of transient fault propagation can be formulated in terms of sensitization [21]. Sensitizationof a gate g withrespect to signal b captures the conditions under which the value at a gate output depends on the value of b . Formally, when g implements Boolean function F , its sensitization with respect to b is: S ens F ( b )= dF db . The inverse of gate sensitization (observability don’t care, ODC) gives conditions under which the value on a wire cannot affect a gate output. In particular, if a transient fault on wire b occurs in a circuit state in which gate g is not sensitized to b , 6 then the fault cannot propagate through the gate. The idea of using gate sensitization for checking noise fault propagation in a circuit was first suggested in [12]. Definition 5.2 (Digital sensitivity) Digitalsensitivityofagate g to noise faults in a wire b ( DS g ( b ) ) is the conjunction of the characteristic function of the Noise fault set with the gate b sensitization DS ( b )= S n ( b ) ^ S ens g ( b ) 5. Digital sensitivity of a circuit to noise faults on a wire b ( DS ( b ) ) is obtained by the union of the digital sensitivity conditions of all the gates in the fanout of b . If DS ( b ) is empty, then the circuit is insensitive to faults occurring on a victim wire b . Hence all the aggressor-victim tuples that could generate these faults are actually isolatedfrom crosstalk noise. Example 5.1 For the example in Figure3.b, the sets of wires that may be the sources of crosstalk noise are: N oise = f ( y; z ) ; ( x; z ; y ) g . The only state in which a transient fault may occur is S tr ( z ) = f 1*1*1 g . Let us check, by only using the sensitivityconditionsforwire z , whether the transient faultcan propagatethrough the circuit. The functions of the individualgates in this example are: x = z + xy = z ( x + y ) y = x + z = ¯ x ¯ z z = x + yz From them we can calculate the corresponding sensitivityfunctions: S ens x ( z )= x z  x z = 0  ( x + y )= x + y S ens y ( z )= y z  y z = 0  x = x S ens z ( z )= z z  z z =( x + y )  x = xy S ens ( z )= S ens x ( z )+ S ens y ( z )+ S ens z ( z )= 1 The circuit is sensitive to a fault on wire z in every SG state. Hence the considered transient fault may indeed propagate through the circuit. Theresults of propagationanalysishence inthiscase cannot reduce the N oise set. Wehave to assume that both tuples ( y; z ) and ( x; z ; y ) might be a source of noise faults. There are two possibilities for solving the remaining noise faultsafter sensitivity (and timing)analysis: 1. touselegalbehaviortransformations,suchasconcurrency reduction, to avoid noise sources, as discussed in the rest of this paper, and 2. touseaconstraint-drivenlayouttool,avoidingtoputwires z and y adjacent to each other. 6 Noise Analysis using STG and SG 6.1 Transient faults When discussing digital sensitivity (Section 5), we made several simplificationsthat need to be justified. 5If the meaning is clear from the context, we will liberally identify the characteristic function of a set and the set itself. Simplification1. Thesuggestedmethodtreatstransientfaults oneatatime,assuming that faultsare notinfluencingeach other. We neglect the effects of faultinterference, because theprobabilityof twoglitches arrivingat thesame time tothe inputsof a gate seems to be rathersmall. Thisis similar totheassumptions that are traditionally made in testing, when considering single fault models versus multiplefault models [1]. Simplification 2. Sensitivityanalysis in general assumes that sensitivityconditionsare calculatedwhen an inputset isapplied to the circuit, and then the circuit has enough time to stabilize. This is like the standard fundamental mode assumption. However, circuits synthesized from an STG operate in I/O mode, which means that inputs might change while part of the circuit is still reacting to a previous input set. Therefore, we need to discuss the assumptions under which this“static”viewisapplicabletoacircuitoperatinginI/Omode. Let us start from an example, and consider the STG in Figure 5.a. One can derive the implementation of its signals k and e shown in Figure 5.c. eb+ abcke be+ a c be k 11101* 001*01 00100* 01*1001*0100* 1*0101 1*1*100 eaabe+ a0000*1 0*0011 ck+ 1001*1 100*01 10*101 b+ c+ ka+ Transient fault on c bae+ ck+ kc+ a+ a) b) c) Figure 5. A transient fault and its propagation In the corresponding SG (Figure 5.b) the only state which might be the cause of a transient fault is 1*1*100. This fault produces a pulse on victim wire c and the propagation of this pulse could be checked by a sensitivity analysis of the NOR gate k with respect to c : S ens k ( c )= a ) DS k ( c )= S tr ( c )  S ens k ( c )= abck e  a = 0 From DS k ( c )= 0 one can conclude that the transient fault on wire c is not propagating through gate k because it is blocked by the controlling value 1 on wire a .However,in its own turn signal a is switching in state 1*1*100. Therefore, the propagation of a transient fault may depend on the relative propagation speed of the fault and some other transition (in this case a , propagating to the inputs of gate k ). If we denote by wire del ay ( a; k ) and wire del ay ( c; k ) the delays of the wires between gates a and k and c and k respectively, then the blocking of a transient fault on wire c requires wire del ay ( a; k ) > w ir e del ay ( c; k ) 6. Thisconditionmaybe difficult to check, because of a number of reasons. It requires precise control over/analysis of wire delays, the inequalities could be inconsistent for different transient faults, etc. Therefore, our current sensitivityanalysis might be too optimistic by not considering propagation delays. 6In fact, instead of delay wire delay ( c; k ) we should consider the delay from the source of noise in wire c to the input of gate k . However, since that point is not known until after layout, we conservativelyuse wire delay ( c; k ) . 7 TheexampleinFigure5showsthatsignalswhichareenabled in a state that causes a transient fault are poor candidates for blockingthe faultpropagation. Thisleads tothe notionof static sensitivity with respect to a state (the word “static” indicates that sensitivity conditions are stable at least for the considered state and its immediate successors). Definition 6.1 (Staticsensitivity) Let an SG state s be the source of a noise fault in wire b and let En ( s ) denote the set of signals enabled in s . The static sensitivity of gate g to the noise fault in state s ( SS g ( b; s ) ) is given by the product of the characteristic function for s and the existential abstraction of the sensitivity functionwith respect to signals in En ( s ) : SS g ( b; s )= s 9 a 2 En ( s ) S ens g ( b ) . Static sensitivity assumes that checking for transient fault propagation is performed for each state separately. When state s 1) is the source of a transient fault in a victim wire b due to aggressors a and c and 2) SS g ( b; s ) 6 = ; the corresponding noise triple ( a; b; c ) is considered to be dangerous. Example 6.1 Considerthe SG in Figure 5.b. In state 1*1*100 the set of enabled signals is f a; b g . S ens k ( c )= a ) 9 x 2f a;b g S ens k ( c )= 1. Moreover, SS k ( c; 1*1*100 )= abcke  1 6 = ; , the transient fault on c may propagate through gate k , and hence noise triple f a; c; b g should be considered as dangerous. The idea behind the application of static sensitivity analysis instead of digital sensitivity (Definition 5.2) is to extend its applicability to asynchronous sequential circuits, by avoiding unrealistic (or difficult to implementation) timing assumptions about wire delays at the fanins of a gate. Let us consider Figure6andderivethetimingassumptionsbehindstaticsensitivity. Suppose that in state s a transient fault is generated at input c of gate Y , and that the fault does not propagate through Y according to the static sensitivity conditions. . . . . . . . . . . . . . . . Y X Z c B A* * Figure 6. Static sensitivity analysis The lattermeans that some theinputsof gate Y ( f anin ( Y ) ) have logical values that block propagation of a pulse on c tothe output of Y . Moreover, due to Definition 6.1, these blocking signalsare stablein state s . The blockingsignalsmay, however, change their values when the gates in f anin ( Y ) will make transitions (e.g., gates X;Z;::: ). These transitions in their own turn shouldbe caused by changes of signals in f anin ( X ) , f anin ( Z ) ;::: (e.g., A; B ). Let us estimate the earliest time when blocking signals can change their values after the circuit starts from state s .Inthe worst case scenario (from the timing point of view) the signals causing transitions in X;Z;::: are enabled in s (otherwise, the blocking signals at f anin ( Y ) will change even later). Then their propagation paths are shown in bold in Figure 6. If we denote by min wire ( f anin ( V )) the minimum delay among the wiresin f anin ( V ) and by min g ate ( f anin ( V )) theminimum delay of gates in f anin ( V ) , then the minimum delay of these paths would be: min V 2 f anin ( Y ) ( min wire ( f anin ( V ))) + min g ate ( f anin ( Y )) + min wire ( f anin ( Y )) . From here we can derive the worst case timing assumption that limits the applicability of static sensitivity: min V 2 f anin ( Y ) ( min wire ( f anin ( V ))) + min g ate ( f anin ( Y )) + min wire ( f anin ( Y )) > wire del ay ( c; Y ) ( T 1 ) This means that a transient fault in wire c will not propagate through gate Y if the wire delay of ( c; Y ) is less than the time needed to change the value of the static sensitivity function. Notice that: 1. Timing assumption (T1) can always be satisfied in an implementation by delay padding of the gates in f anin ( Y ) . Delay padding of a gate cannot affect the validity of other timing assumptions (due to consideration of states different from s ), because the righthand side (T1) contains only a wire delay, not a gate delay. This gives simple proof of convergence of the delay padding procedure. The requirement (T1) is very similar to the conditions of hazard free implementation from [17], where various delay padding algorithms are considered in detail. 2. However,(T1)isverydifficulttosatisfybygateinsertionor transistor sizing if wire delays dominate over gate delays. In this case, only relatively expensive constrained routing, with the goal of minimizing wire delay skew [27], can be used. Hence it becomes desirable to refine (T1) and make it less conservative, if possible. This refinement of timing assumptions can be performed using the following procedure Refine assumptions: 1. Start from state s that is the cause of a transient fault on wire c and such that SS g ( c; s )= 0. 2. Traverse the SG up to the states s 0 2 S 1inwhich SS g ( c; s 0 ) 6 = 0. 3. For each s 0 2 S 1 estimate the path delay for reaching s 0 from s ( del path ( s; s 0 ) ) as thesumofwireandgatedelays (for non-concurrent transitions). 4. Choose the minimal path delay: del path min = min s 0 2 S 1 ( del path ( s; s 0 )) 5. For each gate y in the fanout of c add a timing constraint del path min < w ir e del ay ( c; y ) 8 k+dka+ c+ b+ e+ ecbd+ aa e d k c b a) b) c) 1*1*1000 1*01000 01*100*0 00100*0 01*10*10 0010*00 01*1110 001*110 000110*0001*11 110*010 0*10010 000011*00*0010 11101*0 abcdek SS(c)=/=0 SS(c)=0 ae+ d+ ae+ d+ bFigure 7. Example of static sensitivity analysis Example 6.2 Let us perform the static sensitivity analysis for state1*1*1000intheSGinFigure7.b,which causes atransient fault on wire c . Consider the propagation of this fault through gate k . S ens k ( c )= d . Signal d is not enabled in 1*1*1000, therefore SS k ( c; 1*1*1000 )= d  abcde k = 0. A conservative estimation,according to T1,of thetimingassumptionsunder which the staticsensitivity analysis is valid is: min wire ( f anin ( d )) + g ate del ay ( d )+ wire del ay ( d; k ) > wire del ay ( c; k ) Let us apply procedure Refine assumptions to get less conservative timing constraints. In the procedure, traversal of the SG from state 1*1*1000 will stop by reaching states 011*100 and 001*110, in which SS k ( c; 011*100 ) and SS k ( c; 001*110 ) havea non-zero value. These statesare reached from 1*1*1000 by sequences of transitions  1 = a – e + d + and  2 = b – a – e + d + respectively. By leaving in  1 ; 2only non-concurrent transitions, we may conclude that the static sensitivity will become non-zero only after the sequential firing of a , ;e + and d + . This sequence corresponds to the bold path in the circuit in Figure 7.c. By considering the delay of this path we thus arrive to a less conservative timing assumption, that is: wire del ay ( a; e )+ g ate del ay ( e )+ wire del ay ( e; d )+ g ate del ay ( d )+ wire del ay ( d; k ) > w ir e del ay ( c; k ) . Thetraversal inprocedureRefine assumptionscanbepruned by additionaltiming assumptions. For example, in some applications we could assume that the circuit environment is relatively slow. If the environment reaction is slower than the skew among wire delays, then we can stop our traversal earlier, by forbiddingthe firing of inputs. 6.2 Delay faults In the previous section we discussed the conditions under which transientfaults are filtered by thecircuit. They are based on static sensitivity analysis together with timing assumptions which justify the analysis. This technique can also be extended for the analysis of delay faults. We briefly sketch how to apply it. Delay faults produce changes in the temporal behavior of some events. These changes may be dangerous if some timing constraints are assumed for the correct behavior of the circuit. Unfortunately, any circuit not in the class of delay-insensitive circuits is vulnerable to delay faults. Given that speed-independent circuits are correct under any gate delay, delay faults may only affect wires with isochronic forks [28]. If a wire v has a symmetric isochronic fork, a delay fault with v  as a victim is always dangerous, no matter which branch of the fork it affects. In case of asymmetric isochronic forks, delay faults are only dangerous if they affect the fast branch to become slower (or vice versa – the slow branch to become faster). A detailed analysis of different cases for delay faults is provided in [26]. Here we will give only a summary of it. 1. There are exceptional cases when delay faults can be neglected (E1) Delay fault happens at a wire which has no fork (E2) If a transition v  in STG triggers only transitions of input signals then under a hypothesis of “slow environment” any delay fault on the wires originating at gate v and feeding back to a circuit are safe. (The latter corresponds to an asymmetric isochronic fork by wire v ,where its fast branch is a branch which goes to environment) 2. For checking the propagation of delay faults through branches of isochronic forks one can apply an analysis based on sensitization. (Thisanalysis is similar to the case of transient faults with the only difference that in it we should consider a digital sensitization instead of the more complicated static sensitization.) 3. An analysis of delay faults propagation shows that under a conservative timing assumptions (similar to (T1)) no delay fault propagates through a circuit. Better (than (T1))timingassumptions might be obtained viaProcedure Ref ine assumptions . Based on analysis of noisefaultsgeneration and propagation we can suggest two extreme approaches for checking a noise isolation.  Optimisticapproach Weassumethatanytimingconstraintwhichisderivedfrom a sensitization analysis for noise faults might be satisfied inan implementation. Hence transient faultswhichare not sensitizedandalldelayfaultsareneglected. Theremaining faults are reported to layout tool as dangerous ones.  Conservative approach No timing assumptions are used for separating faults on observable and not. Under this conservative view all transientfaultsandalldelayfaults(excludingexceptionalcases (E1) and (E2)) are assumed to be dangerous. In Section 8 we show the results of noise isolation only for optimistic and conservative approaches. However in practice it might be reasonable to use an intermediate solution which lies between these two extreme cases. For example we could assume theexistence of a small set of timing constraints(either given a priori or produced by timing analysis) and only part of faults is filtered due to these constraints. 9