Automatic generation of synchronous test patterns for asynchronous circuits

. 38.3 Automatic Generation of Synchronous Test Patterns for Asynchronous Circuits Oriol Roig Jordi Cortadella Marco A. Peiia Enric Pastor Department of Computer Architecture, Universitat Polithcnica de Catalunya. Barcelona, Spain. Abstract This paper presents a novel approach for automatic test pattern generation of asynchronous circuits, The techniques used for this purpose assume that the circuit can only be exercised by applying synchronous test vectors, as is done by real-life testers. The main contribution of the paper is the abstraction of the circuit’s behavior as a synchronousfinite state machine in such a way that similar techniques to those currently usedfor synchronous circuits can be safely applied for testing. Currently, the fault model being used is the input stuck-at model. Experimental results on different benchmarks show that our approach generates test vectors with high fault coverage. 1 Introduction Testing is one of the crucial problems that remains to be satisfactorily solved for asynchronous circuits. Since they are implemented as arbitrary interconnections of gates and their behavior is not subordinated to the timing dictated by a global clock, controllability and observability of intemal signals become significantly more costly than in synchronous circuits [ 141. Moreover, asynchronouscircuits tend to have more feedbacks and more state holding elements than their synchronous counterparts. Thus, test pattern generation is harder and design for testability techniques like full scan-path may be unacceptably expensive. Furthermore, testers are inherently synchronous and cannot properly reproduce the environmental behavior for which an asynchronous circuit is designed. Several studies have been presented in the last years addressing the testing and the design for testability of asynchronous circuits. Some classes of asynchronous circuits are said to beself-checking under certain fault models, i.e. a fault will cause the circuit to halt while it is being operated normally. Speed-independent, delayinsensitive and quasi-delay-insensitive circuits are self-checking Work supported by ACiD-WG (Esprit 21949), CYCIT TIC 95-0419and Departament d’Ensenyament de la Generalitat de Catalunya. Design Automation Conference Copyright @ 1997 by the Association for Computing Ma%ery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantageand that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted, To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or [email protected]. 0-8979 1 -847-9/97/0006/$3 SO DAC 97 - 06/97 Anaheim, CA, USA under the output stuck-at [3, 111, the input stuck-at [13] and the isochronic transition [21] fault models, respectively. For asynchronous circuits designed under absolute delay assumptions, the problem of ensuring some bounds for the delay along each path must be considered. Under the path delay fault model [25], a given path in a fabricated circuit is faulty if it has a delay outside the specified interval. Several approaches tackle the testing of path delay faults in different ways [18, 17, 151. Considerable effort has been devoted to proposing design for testability methodologies such as the insertion of observation and controlpoints [13] or test signals [21], as well asfull scan-path [17, 15, 21 and partial scan-path [ 161 techniques. Since commercial testers are inherently synchronous, some authors have proposed testing asynchronous circuits by synchronous test vectors. In [5,2], feedbackloops are cut by virtual synchronous flip-flops during ATPG. Thus, ATPG can be done by using standard state-of-the-art synchronous techniques but the obtained test vectors must be validated on the asynchronous circuit. In section 6.1 the main differences with our approach will be discussed. In this paper we propose a testing strategy for input stuck-at faults in asynchronous circuits with the following features: The circuit’s behavior is modeled as a synchronous finite state machine. The original circuit specification is not required for testing. Test patterns are generated automatically by means of symbolic techniques. Test pattems can be synchronously applied to the inputs of the circuit and faults can be made observable at the outputs, thus allowing interaction with real-life synchronous testers. The paper is organized as follows. In section 2 the overview and motivation of the method are outlined. Section 3 introduces the circuit model. Section 4 presents the synchronous abstraction of the asynchronous circuit. In section 5 the ATPG methodology is detailed. Finally, sections 6 and 7 respectively present results and conclusions. 2 Overview of the method Unlike synchronous circuits, asynchronous circuits may manifest non-deterministic and/or unstable behavior if an inappropriate environment is applied to their inputs. This is a consequence of the usually contrived circuit topology, where many gates have reconvergent fanout. Two problems may arise if input pattems are not selected conveniently: non-confluence of settling state and oscillation. The former occurs when the final stable state of the circuit can 620 be different depending on the arrival times of the input events and the delays of the internal gates. This phenomenon can potentially lead to metastability [22]. The latter occurs when the circuit cannot rest in a stable state. Wl II A x Figure 1 : Circuits showing (a) non-confluence and (b) oscillation. To show non-confluence of settling state we will take the circuit in figure l(a). Let us assume the circuit is in the stable state ABabcdey = 01010000 and that the input pattem AB = 10 is applied. Even if A and B change simultaneously, because of the delay on primary inputs, we cannot assure that both a and b will change at the same time. A “competition” between all sensitized paths starts as soon as some input is switched. %o feasible sequences of gate transitions can be at, ct, bl, yr, df, cl and at, ct, bl, c.1. If gate c is slow to fall the stable state 10101 101 will be reached, otherwise the circuit will settle to state 10100000. The other problem is oscillation or cycles of unstable states. Let the circuit in figure l(b) be in the initial stable state ABabcd = 00001 1. If input A is set to 1, the circuit starts oscillating. After ar, the sequenceof transitions cl, dl, cT, dt is repeatedly generated and the circuit never stabilizes. Other circuits may present transient oscillations that should or should not be avoided depending on the maximum desired settle time. There is a need of providing some technique that assures using only valid test vectors, i.e. input patterns that produce neither nonconfluence of the settling state nor indefinite or too long oscillation cycles’. The overview of our testing approach is as follows. 1. 2. 3. Both The non-faulty circuit is analyzed to find all input sequences that can be used “a la synchronous”, such that neither nonconfluence nor oscillation is produced. After this analysis, the asynchronous circuit is modeled as a synchronous finite state machine (the Confluent Stable State Graph, CSSG, presented in section 4) with deterministic behavior. Random Test Pattern Generation (Random TPG) on the CSSG is initially used to quickly cover a significant number of faults. A symbolic ATPG strategy on the CSSG looks for a test sequence for each uncovered fault. Each test sequence is simulated on every remaining faulty circuit to find all other faults covered by the same sequence. random TPG and fault simulation are efficiently performed by combining parallel and ternary simulation [24, 121. Symbolic ATPG is performed by using BDD-based techniques similar to those used for synchronous finite state machines [lo]. 3 Circuit Model An asynchronous circuit can be represented as an interconnection of gates and delay elements. A gate is a component with several inputs and outputs. At each gate output a function dependingon the gate inputs is instantaneously computed. A delay is a single-input single-output element that reproduces its input after a certain time. Wires are used to interconnect gates and delays. In our approach, asynchronous circuits are modeled following the unbounded gate delay model [ 191. Under such a model, delay elements are attached only to gate outputs and the delay magnitude is positive and finite, but unknown. The delay type we assume is inertial delay, i.e. pulses shorter than the delay magnitude are filtered out. In the sequel we will refer to the pair formed by a gate and its associated delay simply as a gate. Test vectors that would be valid under a bounded delay model, might be considered invalid under an unbounded delay model. On the other hand, test vectors generated assuming unbounded delays will also work on circuits with bounded delays. Therefore, our methodology while pessimistic, is independent of those aspects that may vary the gate delay, such as the technology, the fabrication process or the temperature at which the chips are being tested. Each primary input of a circuit will be modeled as the input of a gate implementing the identity function. The circuit in figure 1 (a) illustrates how primary inputs (A and B) are modeled. These buffers introduce the idea of delay associated with primary inputs. 3.1 Circuit State Graph (CSG) In synchronous circuits the state depends on a subset of circuit signals called state signals. Usually this subset includes input and flip-flop signals. The order of the transitions along combinational paths is not relevant. The only limitation is that they all must occur in a limited cycle time. On the contrary, asynchronouscircuits often have a more complicated structure. Since feedback loops are not cut by clocked flip-flops, the state of an asynchronous circuit is defined by all the binary values of both primary inputs and gates, rather than by a small subset of them. A state graph (SG) is a pair (S, E), where S is the set of states and € C S x S is the set of edges (or transitions). Acircuitstate graph(CSG) is a7-tuple (S, E, P, G, SO, XP, XG), where (S, E) is a SG, P = {PI,. . . ,pm} is the set of primary inputs, 4 = {gl, . . . , gn} is the set of gates, and SO C S is the set of initial states. The labeling functions Xp : S --3 (0, 1)” and XG : S --i (0, 1)” map each state s with a binary vector consisting of the values in s of primary inputs and gates, respectively. Under the unboundedgate delay model the next state of a circuit uniquely depends on its present state. A gate is said to be excited if its output differs from the function it implements, and stable otherwise. If all the gates in a circuit are stable, the circuit is in a stable state. A next statefinction S : S x G --+ S can be defined for each gate. Function 6(s, g,) returns either the state reached by switching the output of gt if it is excited or s if gt is stable. A transition relation, R, relates pairs of predecessortsuccessor states. If state s’ is an immediate successor of state s, we say that both states are in relation R, denoted sRs’ or (s, s’) E R. By using the next state function of each gate, the transition relation associated to circuit gates can be defined as R6 = {(s, s’) E s x s I (s is stable A s = s’) V (3gI E G such that s’ = S(s, gt) # s)} . For each pair (s, s’) E &, ifs is stable, its successor is the same s, otherwise the successor is obtained by switching an excited gate. 3.2 CSG in test mode In our approach, asynchronous circuits are tested in synchronous mode: provided the circuit is stable, an input vector is applied and the circuit is allowed to, eventually, settle. The time between the ‘In section 4 this notion of “too long” will be discussed. 621 application of two input pattems is called the test cycle. Until otherwise noted, we will assume the test cycle is long enough to let the circuit stabilize (unless it oscillates). Figure 2(a) illustrates a possible CSG in test mode. In principle, in a circuit with n inputs, the number of possibleinput pattems is 2“, but in this picture only a few pattems are represented for the sake of simplicity. Labeled boxes represent stable states, while shadedcircles are unstable states. The outgoing arcs from a stable state are labeled with the changes at the circuit primary inputs. Only in such arcs it is allowed more than one signal transition, whereas outgoing arcs from unstable states represent single signal transitions. The latter are not labeled for clarity. We will refer to this circuit state graph in test mode as TCSG. AC 7 At F\- E+ A+ 0. B+ Figure 2: (a) A TCSG and (b) its corresponding CSSG. The transition relation associated to input signals can therefore be defined as follows: RI = {(s, s’) E S x s I s is stable A XP(s) # XP(S’) A XG(S) = XG(S’)} . Relation RI describes all input pattems that can be applied to a stable state. Thus, SRJS’ if s is stable and s’ only differs in certain number of inputs. This represents the situation in which several inputs have been changed but no gate has begun to switch yet. The transition relation of a circuit in test mode is defined as R = RI U Ra. Consequently, we can formally define a TCSG as a CSG such that S and E are strictly defined by the following recursion: 1. so E s . The set S is the set of reachable states of a circuit in test mode, while E is the transition relation R restricted to S. S can be calculated by using a symbolic traversal algorithms similar to the ones described in [lo, 71. 4 Synchronous abstraction of the TCSG We will use figure 2 as an example. Let us assume that s 1 and s2 are initial states. A vector producing non-confluenceis A + Capplied to state s 1, since either 93 or 94 can be nondeterministically reached. If vector D+ is applied to state s4 the circuit oscillates. The only valid vectors are A+B+ and ABappliedrespectively to 92 and 94. This fact is manifested in figure 2(b). Note that the initial state s1 appears in the CSSG, even though no valid input pattem can be applied to it. Nevertheless, still some fault could be detected when forcing sl as reset state. 4.1 Unbounded gate delays and “long enough” test cycles are unrealistic assumptions for testing. Instead, boundedgate delays and short test cycles must be assumed. Moreover, the analysis of oscillation conditions is a difficult problem still under investigation. Let U be the longest sequence of transitions from a stable state s to the final stable state or states when certain input pattem is applied to s. If a is the longest gate delay, then r = CY . Iu\ is an upper bound of the test cycle. On the contrary, if a test cycle of length t is desired, then IC = It/@] can be an estimation of the maximum number of allowed transitions before the circuit finally stabilizes. This is just an approximation we will use henceforth, but once the layout is provided, a more accurate cycle time can be calculated. Estimation of the test cycle 4.2 Practical computation of the CSSG In order to calculate the TCSG synchronous abstraction, we first will define the pairs of states (s, s’) such that SI is reached from s at the end of the test cycle. Each pair has an associated input pattem, given by the different values of inputs in s and s’. For the sake of clarity, subsequent pairs (s, s’) will be assumed such that s is stable and s’ is reached by propagating a single input-pattem applied to s. We call the set of all these pairs of states the test cycle relation. For practical reasons we will assume that the circuit must settle in at most k transitions. The IC-step test cycle relation (TCRk) represents the pairs (5, s’) distant at most k transitions. Formally, given a TCSG (S, E, P, G, SO, XP, XG), TCRk is defined as: TCRk = {(s, s’) E S x S I 351,. . . , sk such that k SRIS~ A (Asi-iRss;) A sk = s’} . i=2 The next step consist of removing invalid pairs of states. Vectors causingnon-confluence are detected if pairs (5, s’) and (s, d’) such that both s’ and s” have the same input values exist. Pattems producing oscillation or unacceptable long test cycle are found if s‘ is unstable. The IC-Confluent Stable State Graph, denoted as CSSGk, is formed by those pairs in TCRk that present neither nonconfluence nor cause the circuit to be unstable after k transitions. Formally, it can be defined as: CSSGk = {(a, a’) E TCRk I a’ is stable A $(s, s”) E TCRk such that [s’ # s” A XI(S’) = XI(S”)]} . Informally the CSSGk contains the following information. Each one ofits nodes represents a stable state. An arc between two nodes and s’ exists if st is stable and the only state reachable from in at most IC transitions by applying 5 Testing Many techniques have been proposed for Automatic Test Pattern Generation (ATPG) for sequential synchronous circuits. As we This section explains how the TCSG is Prunedin such away that the input pattems that produce neither non-confluence nor oscillation are considered as valid candidates for test sequences. Roughly speaking, the TCSG will be reduced to a set of stable states and edges between stable states. For an edge (s, s’) to exist, 3 must be stable and s’ must be stable and the only state reached at the end of the test cycle. The finally obtained state graph will only contain the confluent and stable behavior of the original TCSG, hence the acronym CSSG, standing for ConJluent and Stable State Graph. input pattern, 622 have been explaining, however, non-confluence of settling state and oscillation make that those techniques cannot be directly applied to asynchronous circuits. Our approach resembles the Three-phase ATPG [8] proposed for synchronous circuits. We also propose a method with three phases: fault activation, state justification and state differentiation, describedin sections 5.1 to 5.3. The way these three phases are implemented, though, will be different because of the asynchronousnature of circuits. Section 5.4 introduces Random TPG and fault simulation as techniques to increase the speed of the whole approach. 5.1 Fault activation The first step to generate a test is to find a set of states that activate or excite the fault. It is easy to see that the fault signal 2 stuck-at-c is excited in some stable state if z # c. Since the set of stable reachable states has been already obtained during CSSG computation, finding the stable states exciting a fault is straightforward. In most examples, there is always some stable state that excites a fault. However, it can occur that some signal always equals either 0 or 1 when the circuit is stable and only takes the opposite value in some unstable states. This situation arises when a signal switches an even number of times between stable states. Finding a test for such faults is left directly to the last phase, explained in section 5.3. 5.2 State justification Justifying a state means to provide a sequence of input vectors that drive the circuit from the initial or reset state to that particular state. In our case, a sequence of test vectors that put the circuit in some of the excitation states mkst be given. By using the reachability information it is easy to give a justification sequence. This sequence will put the correct circuit in a state that excites a given fault. However, the test vectors applied on the faulty circuit may result in a sequence of states that differs from that obtained in the correct one. In addition it has to be taken into account that some available sequences for the correct circuit can cause a faulty one to diverge or oscillate. P corruption alwxa conuption sozctimes x manifested \ Figure 3: Corruption detected (a) always and (b) sometimes. As noted in [8], there could be corruption, so the fault would manifest before. In a synchronous circuit the sequence that produces the corruption can always be taken as a new shorter excitation sequence. However, in an asynchronous circuit corruption has to be noticed in all terminal stable states. If this symptom does not appear in some stable states, the entire sequence has to be applied. The consequence when testing the real circuit will be that sometimes the fault will be detected before others. Figure 3 illustrates this by means of an example. According to the reachability analysis done in the correct circuit, the sequence of states Rst + S1 -+ S2 + Act is exercised. Act indicates the proposed activation state actually being justified. When the same inputs are applied to a faulty circuit the following situations might be observed. The stable state S1 in figure 3(a) has S3 as its successor, instead of S2 as in the correct circuit. Because of the different behavior of the correct and the faulty circuit, the fault can be detected before expected. The case in figure 3(b) is different. Now depending on the delays of the gates, two states, S2 and S3, are reachable from S1. Since the fault can not always be detected, we have to apply the full sequence of input vectors. During the real test operation however, the fault may be detected before. 5.3 State differentiation Once a fault has been excited, it still has to be made observable. The most favorable case occurs when the fault is propagated to some primary output. In general, the fault will propagate to some memory element. By applying successive input vectors we have to make the difference noticeable at a primary output. The CSSG gives all the feasible input vectors that can be used in each state. All of them are simulated by using similar techniques to the ones described in section 3.2, and the sequenceresulting in a shorter test length is chosen. Figure 4: (a) Correct circuit (b) Faulty circuit. As an example we can use figure 4. The different Acti are the fault activating states, while S1 and S2 are their stable predecessors. In the correct circuit, S1’ and 52’ are reached, respectively, from S1 and S2. In the faulty circuit, S3’ is always reached from S1, therefore there is an appropriate excitation vector. However, depending on the gate delays, from S2 the fault can either be detected (S2’) or not (S4’). In the latter case, the test would not be conclusive. 5.4 Improving ATPG performance The three phases described above are sufficient to find a test for any testable fault. However, they may be time consuming. Next we describe how techniques used to improve the speed of synchronous ATPG algorithms can be adapted to asynchronous ones. Fault simulation is commonly used to find out if a test for a given fault also detects other faults. When a test is found to detect a fault, the same input patterns are simulated on the remaining faulty circuits. This technique will be efficient only if fast simulation algorithms are provided. Symbolic algorithms are good at managing multiple states of a same circuit. The problem when simulating a fault is just the opposite: dealing with a same state for each different faulty circuit. Thenparallel simulation [24] is widely used because of its speed. Non-confluence and oscillation are problems that have to be taken into account in simulation as well. A very efficient, though conservative, method called ternary simulation [ 123, has been widely used to detect when an input vector causes critical races. This conservativeness, however, does not affect the fault coverage of our approach. Let us assume that a given test detects some fault. The objective of fault simulation is just to find out if the same test detects other faults. If temary simulation says that a test is unable to cover other faults, when in fact it could, tests for those faults can still be found by the previous three phases. 623 In ternary simulation a signal can have any of the three following values: 0, 1 or a. The symbols 0 and 1 have their usual boolean meaning, whereas the symbol @ stands for an uncertain value which is neither 0 nor 1. Temary simulation consists of two algorithms namely A and B. Algorithm A sets each signal to the least upper bound of its current value and its evaluation. The result is that unstable signals are set to Cp. By repeating this process, uncertainties are propagated through the circuit. Algorithm B sets each signal to its evaluation. Consequently, some signals are set to a known value (either 0 or 1). Let us assume the circuit is in state s and we apply input vector a. After algorithms A and B we reach the final state s’. We can conclude that if all the signals in s’ have a definite value (0 or l), s’ is the only successor of s when a is applied. On the contrary, if some signal in s’ has an unknown value (a), either there are several final stable states or the circuit oscillates. It has been proved that temary simulation is polynomial in the number of circuit gates [6]. This is due to the fact that in the worst case 2n states are produced, n being the number of gates. In each state at most n fnnction evaluations are required. Therefore, detection of critical races and/or oscillation can be detected in O(n2) for each pair of stable states and input pattern. Random Test Pattern Generation has tumed out to be a very efficient method in finding a test for an important number of faults at a very low CPU cost [4]. The number of faults covered by this technique highly depends on the circuit, but coverage ratios between 40% and 80% are commonly achieved. By using temary simulation with Random TPG the speed of the overall approach can be improved in similar percentages. vbe5b vbe6a Total FC Table 1 : Experimental results (speed-independent) 32 32 52 52 42 10 0 19 62 18 126 29 23 6 0 29647 69.91% 63.16% example alloc-outbound atod chul50 converta dff ebergen hazard master-read mmu mp-forward-pkt KUl nak-pa nowick ram-read-sbuf rcv-setup rpdft shuf-ram-write sbuf-send-ctl sbuf-send-pkt2 seq4 trimos-send vbelOb vbe5b cov 32 26 26 22 20 32 20 62 60 28 60 40 28 42 20 32 50 40 40 40 58 50 22 vbe6a Total FC tot 66 40 52 44 44 70 44 130 136 58 140 80 54 82 36 62 102 86 116 86 132 114 42 - ou tot 32 26 26 22 20 32 20 62 60 28 60 40 28 42 20 32 50 40 40 40 58 50 22 38 10 - - - sim 3 3 0 1 0 0 0 0 0 0 0 7 0 2 0 1 2 0 0 4 0 0 0 0 1t-S II CPU 52 5 10 8 18 43 7 5049 21067 6 27231 43 4 465 4 14 1760 254 7137 256 16030 5534 9 562 cov - 66 40 50 44 40 70 44 130 136 58 139 80 54 82 36 62 102 86 116 84 132 110 41 78 - - 1putmd 51 36 50 20 7 32 22 55 44 57 5 68 54 54 31 60 40 45 31 28 6 22 33 17 9.16’ - - - 3-ph 12 1 0 23 33 38 22 75 92 1 134 5 0 26 5 1 60 41 85 52 126 88 8 61 - 6 Results We show the effectiveness of our ATPG methodology over a set of benchmarks. Table 1 presents the results obtained for speedindependent and table 2 for hazard-free circuits with bounded delays. Both sets of benchmarks have been automatically synthesized from the same specifications, the former by Petrify [9] and the latter by SIS [23]. Results in the tables are structured as follows. The second and third columns respectively present the total (“tot”) and covered (“cov”) number of faults under the single output stuck-at fault Table 2: Experimental results (hazard free with bounded delays) I I output-s (I input-s II 1 chul50 converta ebergen hazard nowick rpdft 36 vhel0b 60 136 CPU 487 15 5008 5 20 4 8 254851 26774 model. The fourth and fifth columns show analogous results for the single input stuck-at fault model. The next three columns, namely “md”, “3-ph” and “sim”, detail the number of faults covered by each step of our approach. The last column reports the CPU time, in seconds, needed to find the whole set of test vectors. Benchmarks have been run on a Sun 4 workstation with a Sparc-20 processor and 64 megabytes of RAM. The input stuck-at fault model includes all output stuck-at faultS. The results on output stuck-at faults are shown to illustrate that the well known theoretical result of speed-independent circuits being 100% output stuck-at fault testable in operation mode [3] still holds when our methodology is used. Conversely, this is not true for the set of circuits generated by SIS. Most circuits present similar results to those of speedindependent circuits, but three benchmarks, trimos-send, vbelOb and vbe6u, presented a very poor fault coverage. This is due to the logic redundancies added by the synthesis tools in order to avoid spurious pulses in this type of circuits. Note that these examples also take a very long time to finish. When a test for an undetectable fault is searched, all possible input pattems are tried, thus time is wasted with no positive results. Finding out a priori undetectable faults may result in significant performance increase. In those cases with very low fault coverage, testability can be assisted by partial scan-path [16] or variable phase splitting [17]. The number of faults detected by random TPG depends highly on the example topology, but an average of 45% is achieved. This fact represents an important speed-up of our methodology. If a low coverage is achieved in the random step, much work will be left to the 3-phase step. 3-phase ATPG (fault activation, state justification and state differentiation) is the most complex step and the one dominating CPU time. Note that the highest test generation times correspond to those benchmarks where the random TPG step has covered a low number of faults (see e.g. converta and trimos-send in table I). In some cases the same vector is reported to cover different faults. Due to the conservativeness of temary simulation, it sometimes fails to detect equivalent tests. This is the reason for the low number of faults covered by fault simulation. Despite the the low number of faults covered by fault simulation, this last step is still performed because its execution time is negligible when compared to the 3-phase ATPG algorithm. As a general consideration, such results can be significantly improved by speeding up the 3-phase step. Three possibilities we have in mind are: studying better variable ordering strategies in the use of BDDs, using hierarchical techniques similar to those utilized in some formal verification approaches 1201 and classifying undetectable faults to avoid wasting time in covering them. 6.1 Discussion Banerjee et al. [2] also propose synchronous testing of asynchronous circuits. They model the asynchronous circuit as a synchronous 624 one by cutting feedback loops by virtual synchronous flip-flops. Hence, ATPG can be done by using efficient state-of-the-art synchronous techniques. Test vectors are validated afterwards on the asynchronous circuit by using zero-delay and unit-delay simulation [l]. Clearly, that validation can detect oscillation, but it is unable to identify non-confluence. This causes their approach to be optimistic. Our approach assumes the pessimistic unbounded gate delay model, which assures that test vectors generated with our methodology are independent from the technology and the gate delays. Another difference between the method in [2] and ours is that we analyze the asynchronous circuit to find out those vectors that can be used in ATPG, so no further validation is needed. This analysis is done on the asynchronous circuit, rather than on a synchronous simplification. Consequently, our approach is computationally more expensive, but it can cope naturally with oscillation and non-confluence. Possibly, a hybrid method could take the best of both approaches. 7 Conclusions Testing of asynchronous circuits is a problem still far from being solved satisfactorily. This paper has presented a method for ATPG based on well-known techniques for synchronous circuits. The results shown in this paper indicate that asynchronous control circuits are highly testable without applying partial scan techniques. Automatic techniques to select those signals in which the insertion of scan paths can contribute to improve testability is also one of the goals to be pursued in the future. The main contribution of this work is the synchronous abstraction performed over an asynchronous system such that real-life synchronous testers can be used to exercise the input signals. This is only a preliminary work that will be further developed towards covering a wider spectrum of fault models (e.g. delay faults) with more efficient approaches. In the near future we want to explore the possibility of using hierarchy to tackle the testing of complex asynchronous systems. The synchronous abstraction of the circuit’s behavior allows partitioning of large circuits into several interacting asynchronous circuits. We believe this feature will help to generate test patterns with techniques based on the composition of finite state machines. REFERENCES [ 11 S. Banerjee. Personal communication, Mar. 1997. [2] S. Banerjee, S. T. Chakradhar, and R. K. Roy. Synchronous test generation model for asynchronous circuits. In Proc. of the Int. Con$ on VLSI Design, Bangalore, Jan. 1996. [3] P. A. Beerel and T. H.-Y. Meng. Semi-modularity and testability of speed-independent circuits. Integration, the VLSI journal, 13(3):301-322, Sept. 1992. [4] M. A. Breuer. A random and an algorithmic technique for fault detection test generation for sequential circuits. IEEE Trans. on Comp., C-20(11):1364-1370,Nov. 1971. [SI M. A. Breuer. The effects of races, delays, and delay faults on test generation. IEEE Trans. on Comp., C-23(10), Oct. 1974. [6] J. A. Brzozowski and C.-J. H. Seger. Asynchronous Circuits. Monographs in Computer Science. Springer-Verlag, 1995. [7] J. R. Burch, E. M. Clarke, D. E. Long, K. L. McMillan, and D. L. Dill. Symbolic model checking for sequential circuit verification. IEEE Trans. on CAD, 13(4):401-424,1994. [8] H. Cho, G. D. Hachtel, and E Somenzi. Fast sequential ATPG based on implicit state enumeration. In Proc. Int. Test Con$, pages 67 - 74, Nashville, TN, Oct. 1991. [9] J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, and A. Yakovlev. Petrify: a tool for manipulating concurrent specifications and synthesis of asynchronous controllers. In XI Congreso de Disc60 de Circuitos Integrados, Barcelona, Nov. 1996. [IO] 0. Coudert, C. Berthet, and J. C. Madre. Verification of sequential machines using boolean functional vectors. In Proc. IFIP Int. Workshop on Applied Formal Methods for Correct VLSIDesign, pages 11 1-128, Leuven, Belgium, Nov. 1989. [ll] I. David, R. Ginosar, and M. Yoeli. Self-timed is selfdiagnostic. Journal of Electronic Testing:Theory and Applications, (6):219-228, Jan. 1995. [12] E. B. Eichelberger. Hazard detection in combinational and sequential switching circuits. IBA4 J. Res. and Dev., 9:90-99, Mar. 1965. [ 131 P. J. Hazewindus. Testing Delay-Insensitive Circuits. PhD thesis, California Institute of Technology, 1992. [14] H. Hulgaard, S. M. Bums, and G. Bomello. Testing asynchronous ciruits: A survey. Integration, the VLSI journal, [ 151 K. Keutzer, L. Lavagno, and A. Sangiovanni-Vincentelli. Synthesis for testability techniques for asynchronous circuits. IEEE Trans. on CAD, 11(1):87-101, Dec. 1995. [ 161 A. Khoche and E. Brunvand. Testing self-timed circuits using partial scan. In Proc. of the 2nd Working Con$ on Asynchronous Design Methodologies, pages 160-1 69, London, May 1995. [17] L. Lavagno, M. Kishinevsky, and A. Lioy. Testing redundant asynchronous circuits. In Proc. EURO-DAC. IEEE Computer Society Press, Sept. 1994. [18] C. J. Lin and S. M. Reddy. On delay fault testing in logic circuits. IEEE Trans. on CAD, 6(5), Sept. 1987. [ 191 D. Muller and W. Bartky. A Theory of Asynchronous Circuits. In Annals of Computing Laboratory of Hardward University, pages 206243,1959. [20] 0. Roig, J. Cortadella, and E. Pastor. Hierarchical gate-level verification of speed-independent circuits. In Proc. of the 2nd Working Con$ on AsynchronousDesign Methodologies, pages 128-137, London, May 1995. [21] M. Roncken and R. Saeijs. Linear test times for delayinsensitive circuits: a compilation strategy. In S. Furber and M. Edwards, editors, Asynchronous Design Methodologies, volume A-28 of IFIP Transactions, pages 13-27. Elsevier Science Publishers, 1993. 1221 C. L. Seitz. System timing. In Introduction to VLSI Systems, chapter 7. Mead & Conway, Addison-Wesley, 1980. [23] E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. R. Stephan, R. K. Brayton, and A. Sangiovanni-Vincentelli. SIS: A system for sequential circuits synthesis. Technical Report M92/41, UCBERL, May 1992. [24] S. Seshu. On an improved diagnosis program. IEEE Trans. on Electronrc Comp., EC-12(2):76-79, Feb. 1965. [25] G. L. Smith. A model for delay faults based on paths. In Proc. Int. Test Con$, pages 324-349, Sept. 1985. 19(3):111-13 1, NOV. 1995. 625