LIBRARY OF THE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN 510.84 no.445-450 The person charging this material is re- sponsible for its return to the library from which it was withdrawn on or before the Latest Date stamped below. Theft, mutilation, and underlining of books are reasons for disciplinary action and may result in dismissal from the University. UNIVERSITY OF ILLINOIS LIBRARY AT URBANA-CHAMPAIGN L161 — O-1096 Digitized by the Internet Archive in 2013 http://archive.org/details/controlpointstra450reyc TJC^ Re P° rt No * ^° mo ■ <{ so /K^^<-4\ CONTROL POINT STRATEGY AND ITS AUTOMATED DIAGNOSIS COO-2118-0009 by Christian A. Rey June 1971 COO-2118-0009 Report No. U50 CONTROL POINT STRATEGY AND ITS AUTOMATED DIAGNOSIS* by Christian A. Rey June 1971 Department of Computer Science University of Illinois Urbana, Illinois 6l801 *This work was submitted in partial fulfillment of the requirements for the degree of Master of Science in Computer Science, June 1971, and was supported in part by Contract AT(ll-l)-21l8 with the U. S. Atomic Energy Commission. CONTROL POINT STRATEGY AND ITS AUTOMATED DIAGNOSIS Christian A. Rey, M.S. Department of Computer Science University of Illinois, 1971 The design technique known as Control Point Strategy has been used in the design of the Illiac III Pattern Recognition Computer. The control of this machine is functionally partitioned and physically divided into small, etched integrated circuits. The testing of these cards is the object of this thesis. The first chapter is devoted to defining a formal model for the pseudo-asynchronous control strategy. A detailed analysis of the concepts of task, event, and transition in pseudo-asynchronous systems is given. A close study of what are called "external con- ditions" shows that transitions exhibit a very definite structure with respect to these conditions. This property is used to define a basic building block, called a control point, which logically implements the fundamental functions assumed by a transition. The second chapter starts with a brief review of how the control point strategy is actually realized in terms of logic circuits in the Illiac III Control. Given a control point design, a method based on the model of Chapter 1 is then proposed for generating appropriate test patterns. The essential idea here is to partition the control point design into "independent subnetworks" , to find tests for these subnetworks and to concatenate these tests according to a set of rules which take into account the connectivity properties of the Control Point Network. An algorithm is developed which realizes this concatenation. The problem of physically applying the tests to individual cards is developed in Chapter 3. First the maintenance facilities provided by the Illiac III implementation of the control points are described. Although simple, these facilities appear to be extremely time-saving for the debugging process. Since the actual test in our case is monitored by a mini-computer (PDP8/e) the design of a special interface »called the Sequence Tester, is needed. The Sequence Tester has two functions: (l) it submits input patterns to the card and (2) preprocesses the card response before trans- mitting it to the PDP8/e. The processing function facilitates the fault location. A detailed study of the Sequence Tester logic design is given in Chapter k. Factors such as speed, reliability and cost are evaluated before presenting the selected solution. A review of the test generation procedures available to date for combinational circuits is given for completeness in Appendix 1. Appendix 2 contains a complete listing of the FORTRAN program which implements the test generation algorithm developed in Chapter 2. Ill ACKNOWLEDGMENT The author is indebted to Dr. Bruce H. McCormick whose suggestions , comments and criticisms helped greatly during the research work. The author is also grateful to all his friends and colleagues whose help has been invaluable during the writing of this thesis. Acknowledgment is also due to Roberta Andre' for her patience in typing the final draft and to Stanislav Zundo for the excellent quality of his drawings. TABLE OF CONTENTS Page 1. CONTROL POINT NET: a model for the representation of pseudo-asynchronous events 1 1. 1 Introduction I 1.2 Pseudo-asynchronous Control Strategy 2 1.2.1 Definitions 2 1.2.2 Interconnections of events 6 1.2.3 The contingency matrix Ik 1.2. U Transitions 21 1.2.5 An algorithm to derive maximal transitions 22 1.2.6 Structure of a transition 2h 1.2.6.1 Wait Function of a transition 28 1.2.6.2 Sequence Function of a transition 29 1.3 The control point net 29 2 . PSEUDO-ASYNCHRONOUS CONTROL DIAGNOSIS : a method 33 2.1 Introduction 33 2.2 Control point implementation: an example 33 2.2.1 The basic design 33 2.2.2 Calling control points „ 3o 2.2.3 An example of CP design 38 2.3 Fault detection and location in combinational networks: a review kh 2.3.1 A model for fault analysis ^ 2.3.2 Test generation ^7 2.U Fault detection in pseudo-asynchronous logic ^9 2.U.1 Fault location or fault detection *+9 2.U.2 The test generation strategy 50 2.U.3 Aggregates and associated modules 51 2.5 The algorithm: basic principles 55 2.5.1 Generating tests for the sequence stage 55 2.5.2 Generating tests for the task stage 57 2 . 6 The algorithm: implementation • 58 2.6.1 Concatenation of lines of the A-table: CPTEST1 62 2.6.2 Merging of B and C-tables 66 2.6.3 Program specifications 70 3. DESIGN OF THE SEQUENCE TESTER 7^ 3.1 The Sequence Tester „ 7^ 3.1.1 The problem jk 3.1.2 Signal blocking in control point logic 75 3.1.2.1 MH-control points 75 3.1.2.2 GO-control points 77 3.1.2.3 Conclusion 83 V Page 3.1.3 The method: a computer-monitored test 83 3.1.4 The Sequence Tester hardware 88 3.2 Programming. . . . ., . „ 95 3.2.1 Action (a) 95 3.2.1.1 New phase 95 3.2.1.2 New subphase 96 3.2.1.3 Stop and Initialize 96 3.2.1.4 Diagnostic 96 3.2.2 Action© 98 3.2.3 The main program 3.3 Advantages and disadvantages of this solution 101 3.3.1 Disadvantages 101 3.3.1.1 Long processing 101 3.3.1.2 Big interconnection matrix 107 3.3.2 Advantages 107 3.3.2.1 Simpler Signal Analyser 107 3.3.2.2 Versatility 1°? 4. SEQUENCE TESTER: logical design 1°9 4.1 Sequence Analyser 109 4.1.1 Requirements 10 4.1.2 Realization 109 4.2 Output Register HO 4.2.1 Requirements HO 4.2.2 Realization H^ 4. 3 Comparator H^ 4.3.1 Requirements H4 4.3.2 Realization Il6 4.4 START line, CC line, enable lines, input register INPREG... 116 4.5 The DOWN Logic H6 4. 6 The UP decoder : 119 4.7 Matrix 122 4.8 The Control Block 127 4.8.1 Flowchart 127 4.8.2 Realization 127 4.9 Signal Catalogue 132 4.9.1 Tester Signals 132 4.9.2 Control Block Signals 132 5. CONCLUSION 134 APPENDIX A. A REVIEW OF TEST GENERATION PROCEDURES 135 E . CPTEST LISTING 142 REFERENCES 151 VI LIST OF FIGURES Figure Page 1.1 lifferent Structures of Events h 1.2 Predecessor and Successor Definitions 7 1.3 PERT Graph 11 l.h Contingency Representation of System of Figure 1.1. c 13 1.5 Contingency Matrix for System of Figure l.k 16 1.6 Contingency Operations 19 1.7 Transition Matrix and Corresponding Maximal Transitions 23 1.8 Minimal Representation of System of Figure l.U 25 1.9 Transition T( {e ,e, }|{e,,e ,e„,e.}) 27 a b +'_**'t ._ Control Point Network for System of Figure 1.1. c 32 The Basic Design 35 2.2 Unconditional Sequence of Events 37 2.3 Mechanism of a Calling Control Point 39 2.k Flow Chart of "EXAMPLE" ^0 2.5 CPN of "EXAMPLE" *+l 2.6 Control Point Implementation of "EXAMPLE" ^2 2.7 A Wired Routine ^3 2.8 NAND and NOR DTL Circuits ^5 2.9 A Composite Aggregate 52 2.10 A Simple Aggregate 52 2.11 Flyback Routine 5 1 * 2.12 General Structure of CPTEST 59 2.13 Ai-Tables for Flyback Routine 63 2.1U A-Table Line Concatenation: CPTEST1 6H 2.15 B-Table for Flyback Routine 65 2.16 C-Table for Flyback Routine 67 2.17 Merging of C and B Tables: CPTEST2 68 2.18 FC-Table for Flyback Routine 69 3.1 :P-MH with Test Sequence 76 2. Blocking Effect Due to MH Lines (Unconditional string of CP's) 78 vii Figure „ & Page 3.3 CP-GO with Test Sequence 79 3.U Blocking Effect of the Sequence GOTASK=GODELY=0 , G0TASK=G0DELY=1 on the Advance of the Signal (Unconditional string of CP's). 8l 3.5 CCP-GO with Test Sequence 82 3.6 Task Logic with Specified and Unspecified Outputs SU 3.7 Sequence Tester Flow Chart 87 3.8 Architecture of the System 89 3.9 Tester Organization 9*+ 3.10 I/O Conventions 97 3. 11 Main Program 102 3.12 Test Specifications 103 3.13 CP simulation 10U 3.1^ Output Simulation . . . . 105 Test-DGWiJ Rout ine 106 k.l Signal Analyser Logic Design Ill k.2 Two SA Configurations 112 k. 3 Signal Analyser for Bit #i 113 k.k One Stage of OUTREG 115 h. 5 The Comparator 117 h.6 MH and Input Registers 118 k.l DOWN Register Input Logic 120 h.Q UP Decoder: Principle 121 k.9 Subsequence A: Flowchart 128 i+.10 Subsequence B: Flowchart 129 4.11 Subsequence A: Design 130 h. 12 Subsequence B: Design 131 1. CONTROL POINT NET: a model for the representation of pseudo-asynchronous events 1. 1 Introduction A control can be considered as being basically synchronous, asynchronous , pseudo-asynchronous or micro-programmed and the design techniques used are a function of these classifications. The Department of Computer Science at the University of Illinois has been, historically, flor the most palrt involved in the design and con- struction of asynchronous computers. The fact that this Department has been primarily interested in the parallel processor computers is strongly related to that involvement. An asynchronous control possesses some advantages over synchronous controls due to the relative independence of the speed of the different units. However an asynchronous control "does require hardware which greatly increases the design complexity and renders a logical design problem of flow chart realization [^]". Because of this complexity, this design has remained mostly "an art and not a science." (Swartout, 1963). Some work [l], [2], [3], toward a formalization of this problem has been done already and some methods have been proposed to stan- dardize the design. The solution proposed in [h] introduces a building block called a control point . The purpose of this chapter is to formalize and enlarge the control point concept. We introduce a model called a control point net which yields a unique topological representation of a given pseudo-asynchronous system from which the control point design is easily derived. 2 1.2 Pseudo-asynchronous Control Strategy Coordination "between events can be represented in many ways. A widely used method consists of drawing the flow chart illustrating the interrelationships between these events. In order to convert the flow chart into an actual logic circuit , the only method avail- able to date has been a set of heuristics. However, it is believed that, according to the control mode (clocked, asynchronous or pseudo- asynchronous) there exists a simplified flow chart which directly leads (without too much interpretation) to a "low-cost implementation." In this chapter, we first study some of the properties of pseudo-asynchronous control implemented using the so-called Control Point Strategy. Structural properties of the transitions are then investigated and a model based on this study is set up: the control point net. The control point net has basically the same topology as the logic circuit which implements it. 1.2.1 Definitions The following definitions will refer to the usual flow chart representation where a rectangular box ( I I ) represents a task to be performed, a rhombus (fC/^ ) represents a con- ditional branch and a circle ( (/ ) represents a routine. A new symbol, the dotted circle © , and its function must be presented here. Parallelism is possible in hardware and one must provide a way to represent this graphically. If the termination of the events e, , e_, •••» e is necessary before some other action is initiated, then a dotted circle is used where all the reply signals r-,, r ? ,..., r converge. Let us examine the flow chart of figure 1.1. c for the significance of some dotted circles. Events e^ and e c must be terminated 2 6 before the condition "Cl" is checked. However, if e is also terminated, then e_ can be initiated whereas the condition "W " is checked for possible activation of e, . In the trivial case where only one event must be finished in order for some other action to occur, the dotted circle is omitted, as between e and "W " or between e_ and e r . 1 3 6 In conventional programming, parallel actions cannot be performed and hence dotted circles are not used. Definition 1 ; Task A task in our context is the performance of a singular action or a set of singular actions in a fixed order. For instance, resetting a register can be thought of as a singular action. On the other hand, if two registers are always reset at the same time, these two separate actions can be merged in only one task. Moreover, if the gating in the first one always occurs after it has been reset, then the actions: reset register 1 reset register 2 gate register 1 (in this fixed order) can be considered as only one task. A task is activated by a task signal (t); after completion of the task, a reply signal (r) is set. In asynchronous systems this latter signal is produced by the termination of the task itself. In synchronous systems, it is produced by a clock whose period is greater than or equal to the task duration. In (0) <• EVENT H Figure 1.1 Different Structures of Events pseudo-asynchronous systems the reply signal is produced by a "timing stage" which merely simulates the duration of the task. A timing stage is associated with each task. A task can be represented simply by a rectangular box with an incoming signal t and an outgoing signal r. Definition 2: Event An event is the performance of an elementary task or of a set of elementary tasks in a time-dependent order. In terms of our flow chart conventions, an event is a set of connected rectangular boxes, rhombuses, circles and dotted circles having the following properties: (1) There exists one and only one incoming signal in the set ( calling signal ) i.e. a signal the origin of which is not in the set. (2) There exists one and only one outgoing signal in the set ( reply signal ) „ i.e. a signal the extremity of which is not in the set. (3) All the other elements within the set are connected to each other. It is clearly realized that an event can be limited to a task or embrace an entire routine as shown in figure 1.1. a, b, c. For this reason, a task box will be simply labeled e. (for event), The notion of an event is useful to retain since it provides an interesting modularity which destroys the traditional difference between a simple task and a routine. In the following only events are mentioned regardless of their exact nature. Accordingly, the symbols used in our flow charts consist only 6 of circles ( to represent events), rhombuses ( to represent branches) and dotted circles. A point must be emphasized, the interpretation of t. and r. for an event e. in the extended case: t. is simply the 1 1 i ^ incoming signal in the event — when e. is a routine, t. is often called a calling signal — and r. is the reply signal generated by the timing stage of the final task in the event. We have now defined the concept of event and the strategy used in pseudo-asynchronous control. We must now see how the structure of the physical hardware implementation of a flow chart like 1.1. c can be derived from this flow chart. 1.2.2 Interconnections of events The purpose of this paragraph is to study relationships between events in a flow chart and to derive from them some structural properties of this flow chart which are useful for the design. An interesting notion to introduce first is that of predecessor-event and successor-event. Definition 3 : Predecessor and successor-events If an event e. can be connected in an oriented flow chart J to an event e n through a finite number of rhombuses and at k ° most one dotted circle, then e. is called a predecessor-event of e.. and in turn, e, is called a successor-event of e. k k j. In figure 1.2. a, e is a predecessor-event of e and e is a successor-event of e.- In other words, an event e. is called a predecessor event of e if there are any conditions (a) Predecessor-events and Successor-events Case 1 Q 7 j Case 2 Case 3 (b) Three Representations of the Same Predecessor-event Description SYSTEM PREDECESSOR DESCRIPTION (e^) — KD — *{*5 @ — -0 — -@ @ KD — H@ e 4 ) — h3> SUCCESSOR DESCRIPTION (c) Two Systems having the same Successor Description Figure 1.2 Predecessor and Successor De f ir.i Moats .which can cause e to be performed immediately after e has been performed. The above relation does not define completely the exact connection between events. For instance in figure 1.2. a e r and e„ are also predecessor-events of e . However, there 6 1* l ■ exist other configurations having e , e,-, e_ as predecessors of e (see cases 1, 2, 3 of figure 1.2.b). Each of these configurations has its own significance. In case 1 , e and e £ 2JL e £ an ^ L e 7 mus t 1 ° e performed before e is initiated. In case 2, e is initiated when e , or_ e^, or e 7 are performed. In case 3 , e,., e^ and e„ must be realized before initiating e . We introduce next the notion of predecessor-set or simply, predecessor, as one means to uniquely define a system. Definition k : Predecessor, contingency In a system of n events, E = {e ,e , ...,e }, a predecessor of event e., noted p(e.), is a set of all predecessor-events J J of e. such that the paths from any of them to e. go through J J the same dotted circle. An event e. may have many predecessors p.(e.), i = 1, 2, ..., n.: the set of all of them is called i J J the contingency of e. and is noted: J C(e.) = { Pl (e.), p 2 (e.),...,p n> (e.)} J In other words if all the events belonging to a predecessor of e. are terminated, then there is a chance (if some external J conditions are met) for e. to be performed next. For instance 9 in figure 1.2.b, we have: Case 1 : C(e 1 ) = {{e , e^} ,{eg, e }} Case 2 : C( e;L ) = {{e },{e 6 },{e }} Case 3 : C(e )={{e ,e^,e }} In a similar way we can define the concepts of successor and influence which are the duals of the concepts of predecessor and contingency respectively. However it is shown that the concept of successor is not sufficient to describe a system. Definition 5 : Successor, influence In a system of n events E= {e ,e ,.,.,e }, a successor of event e. , noted s(e. ) , is a set of all successor-events of e, which are k' k ' k such that the paths from e, to any one of them go through the same dotted circle. An event e, may have many successors s.(e ), K. i K. i=l,2,...,n ; the set of all of them is called the influence of k e, and is noted: k Ke k ) = {s 1 (e k ),s 2 (e k ),...,s (e k )} k In figure 1.2.b the influence of e > e^> e„ > are: Case 1 : l(e M^}} ilie^Ue^ ,{6^}; Ke^Ue^} Case 2 : ite^Ue^} ^(egM^}} ^(e^Ue^} Case 3 : l(e ) = {{e 1 >} ;l(e 6 )={{ ei }} ;l(e M^}} It is clear from the above example that the influence definition of a system is not sufficient to describe it uniquely, since two different topologies (case 2 and 3) have the same description. This comes from the fact that the notion of the dotted circle on which the contingency and the influence definitions are based is not"symmetrical"with respect to the 10 predecessors and the successors. A dotted circle (in figure 1.2.c) between {e~ e, } and{ e e^ } means that all of the events e^ e, must be terminated before one or both of the events e^,e^ 3, k 5 6 may be initiated. In another way, saying: description (l) l(e )={{e e ^)} I(e u )={{e e 6 }} is not equivalent to saying: description \2J C(e )={{e e, }} C(e.)={{e_ ek}} 6 3, since a different system having the contingency description: description (3) C(e ) = {{e },{e,}} C(e 6 )={{e 3 },{e u }} also satisfies description (^y (see figure 1.2.c). Because of this lack of completeness, the influence definition is not used in what follows. It must be noted that in decision making, the word- description of a PERT graph is done in terms of the contin- gencies of the various "jobs" to be scheduled [20], In figure 1.3. a, a PERT network is represented using our con- ventions. The contingency definitions of this network are: C( ei ) = {0} C(e ) = {{e 2 ,e 3 }} C(e 2 ) = {{e^} C(e 8 ) = {{e^}} C(e 3 ) = {{e^} C(e ) = {{e^.e }} C(e h ) = {{e ± }} c(e 10 ) = Ueg.e^} C(e 5 ) = {{ ei }} C(e 1± ) = Ue 6 ,e 10 }} C(e 6 ) = {{e 2 ,e 3 }} 11 Figure 1.3 PERT Graph 12 A PERT graph is not an example of a general pseudo-asynchronous system since it is restricted in particular by the fact that it does not contain loops and the contingency set of any "job" is always composed of one element at most. A more complex diagraph is represented in figure l.U; it corresponds to the flow chart of figure 1. i.e. The word- definition of this system is more complex than above since external conditions must be explicitly stated: (1) e terminated :W =0, initiate e :W =1, wait (2) e and e^ terminated :C ,C =1, initiate e :C ,C =1, initiate e :0 =1, initiate e, : initiate e„ (3) e_ terminated : initiate e^ 3 o (h) e_ and e c and e„ terminated : initiate e nn 3 ? 7 11 (5) e> terminatedo :W =0, initiate e :W =1, wait (6) e and e^- and e terminated : initiate e _and e (7) e„ terminated, o :initiate e Q and e_ I o 9 (8) en and e terminated :W =0, initiate e« :Wo=l, wait :initiatee„ e and e -j » J » 7 (9) e terminated :W,=0, initiate e fi :Wi=l, wait 13 A EXIT START Figure l.k Contingency Representation of System of Figure 1.1. c 11+ However, starting from this definition ,the contingency- definition can very easily be obtained: C( e;L ) = {{e 5 ,e 6 ,e T }} C^hUe^ 9 {e^ e Q } ,{e Q ^H C(e 2 )={{ ei }} C(e 5 )={{e 10 },{e T }} C(e 3 )={{e 2 ,e 8 },{e 8 ,e 9 }} C(e 9 )={{e T }} C(e i| )={{e 2 ,e 8 },{e 8 ,e 9 }} C(e 10 ) = {{e 5 ,e 6 ,e T }} C(e 5 )={{e 2 ,e 8 ),{e 8 ,e 9 }} Cie^iie^e^e^} C(e 6 )={{e 3 >} C(e ) is for instance determined by knowing that event e is initiated if e and e^ are terminated (statement (2)) or e and e_ are terminated (statement (8)). b 9 1.2.3 The contingency matrix For convenience, we define in what follows, the set of predecessors of a system of n events: P -U C(e ) J It is realized that P represents the set of all possible predecessors in the system. For our example P is listed below. There are nine possible predecessors in this system. p = { Pi,.P2,P3» p U»P5»P6»PT» p 8^9 } where: Pi ■ {e 5 , e 6» e 7 } p 2 = {e x } p 3 = {e 2 ,eg} Pit = {e 8» e 9 } 15 P 5 ={e 3 } p 6 = { V p 7 = {e io } P 8 = {e T > P 9 = ^ e 3> e 5 » e Y^ It is clear that for a system of n events, E, the set P is unique since it is directly derived from the word state- ment as shown before. For this reason the contingency relation between events can now be stated in a more formal way. For that we must define the "contingency matrix." Definition 6 : contingency matrix The contingency matrix of a system of n events and m distinct predecessors is an m x n matrix having a one in column (j) of row (i) if: p . € C(e ) j = 1,2,... ,n i = 1,2 , . . . ,m For our example, the transition matrix is represented in figure 1.5. This matrix shows that there is a mapping from the space of events E to the space of predecessors P: C E — ^P Reversely ,a mapping C* exists from P to E: C* p e*e (see figure 1.6. a) These mappings can be defined in terms of the "contingency operation." lb in (T O in en LU o LU Q LU cc 0- % EVENTS e l e 2 ®3 e 4 e 5 e 6 e 7 e 8 e 9 'K) c ll 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Figure 1. 5 Contingency Matrix for System of Figure lo U IT Definition 7 : Contingency operation (figure 1.6.b) Given the set E={e.} (i=l,...,n) of all possible events and the set P of all possible predecessors, the contingency operation, C is defined by the following relation: cle j )=( % }=p j P.={p v ) representing the set of all possible predecessors of e . . Definition 8: Star-contingency-operation (figure 1.6.b) Given the set E={e.} (i=l,...,n) of all possible events and the set P, the star- contingency operation, C* , is defined by the following relation: C.(p k Me j} =E k E ={e.} representing the set of all possible events e. such that k J J Pk £p j The two above definitions can be stated in terms of the transition matrix. C is the mapping columns > rows C* is the mapping rows > columns C* may appear as a kind of inverse operation; in fact in the general case: C*.C 4 I (identity operation) Theorem 1 : If p, 6 P. then e . £ E n and reversely. k j j k Proof: If p, € P. then from definition 8 { e . } Q E. i . e e . e E. J k j k 18 The converse proposition is proved in the same way. A more general contingency operation which operates on sets can now be defined. Definition 9 : Set-contingency operation (figure 1.6. c,d) Given the set g ={E.} of all possible subsets of E and the set 2 ={ P } of all possible subsets of P, the set-con- tingency operation . C, is defined by the following relations: C (E.) = C(e ) J ^ r*- J Definition 10 : Set-star-contingency operation (figure 1.6.d) Similarly the set-star- conting ency operation, C*, is defined by: c* (P k )=Hc*(p s ) E P Since both 2 and 2 contain the empty set, by definition: C(0)=2 P C*(0)=2 E Theorem 2 : C*(C(E.))D E. and reversely C(C*(P,))d P. Proof: Case 1: If C(E.)=0 then the proposition is obvious since J C*(0) = E D E. - J (a) 19 (d) Figure 1.6 Contingency Operations 20 Case 2: If C(E.) = llc(ej then for any p^ 6 C(Ej J e r e e. r we have p. € C(e ) \je € E k * r then e € C*(p, ) from theorem 1 r k (e r }CGMp k ) \je r €E. B C C*(p k ) p k 6 C(E^) then E. qUc* (p )= C*(C(E.)) J P k €c( Bj ) k i.e. C*(C(E )) D E. J J The reverse proposition is proved similarly. Theorem 3 : If P C C (E.), then E. C C*(P ) and vice versa. ■K- J j k Proof: A If P, C C(E.) then from Definition 8 and 10 k J A A A C*(P V ) 2 C*(C(E.)) 2 E. from theorem 2 so k J J E. C C*(P. ) J *■ A If reversely E, C C*(P, ) then from Definition 9 J & C(E.) ? C(C*(P, )) 5 P. from theorem 2 so J k a P, C C(E.) K J The set contingency operation and the set-star contingency operation defined above correspond to the contingency and star- contingency operation of Definition 7 and 8 when the cardinality of the set on which they operate is one. From now on, only 21 set-operations will be considered. It is now possible to introduce the concept of "transition." 1.2. h Transitions Definition 11 : Transition A transition exists between p and E.={e . } ( j=l,. . . ,q) if: E. C C*({p, }) (strict inclusion) 1 K. When there are"l's"in columns (l ),..., (q) of row (k) of the contingency matrix, then a transition exists between p, k and the set of events E.={e n ,...,e }. l 1' q Definition 12 : Maximal transition A maximal transition exists between p and E.={e .}( j=l, . . . ,q) k l j if E. = C*({p k )) When there are "l's" in columns (l), . ..,(q) of row (k) and zeros in all other columns of row (k) in the aontingsncy matrix, then a maximal transition exists between p n and the ■^k set of events E.={e_, , . . . ,e }. l 1* ' q For our example the contingency matrix is represented in figure 1.5. A transition exists between p and {e je, } whereas amaximal transition exists between p„ and {e je, ,e c »e„} . s> j h p f Each row of the contingency matrix corresponds to a> maximal transition. Since each of these rows also represents a distinct predecessor in the system and since the set P is, as said before, given by the word description, there is a unique set of maximal transitions in a given system. It can also be shown that this set is minimum. 22 1.2.5 An algorithm to derive maximal transitions The cost of a graph implementation is widely related to the number of transitions it contains since they represent "wires", transfers", in our case, "gates and delays". Consequently, obtaining a minimum set of transitions is necessary in order to decrease the cost. The notion of maximal transition is helpful in this sense. An algorithm to derive maximal transitions from the contingency matrix is developed next: (1) Is there a row (k) with more than one "l" in it? NO: go to (6) YES: continue (2) If columns (i ),..., (q) have a "l" in row (k) , add a column labeled (i,...,q) having a "l" in row (k). (3) Delete the "l" in row (k) of columns (i),...,(q). (k) Delete all zero columns (5) Go to (1) ( 6 ) STOP As an example let us apply this algorithm to the matrix in figure 1.5. Columns (3), (U), (5), (T) have a "l" in row (3): a new column labeled (3,^,5,7) is added with a "l" in column (3) and the"l»s" are deleted in row (3) of columns (3),( 1 +),(5),(T). A similar operation can be done for columns (3), (M, (5), (?) and row (U), and for columns (8), (9) and row (8). The result is shown in figure 1. 7 together with the corresponding maximal transitions under the format: T(p, I E ). The equivalent minimal k q representation (minimal number of dotted circles) is shown in 23 EVENTS 4 5 6 7 8 9 10 II 1,10 3,4 8,9 5.7 X CO 4 or H o ^ 5 CO Ixl V 6 UJ Q iu 7 tr CL 8 X \ x \ Transitions : T({e ,e^,e }|{e ,e 1Q >) T({e 1 }|{e 2 }) T({e 2 ,e 8 }|{e 3 ,e u ,e 5 ,e T )) T({e 3 }|{e 6 >) T({e l4 }|{e T }) T({e 10 >|{e 8 » T({ e7 }|{e 8 ,e 9 }) T({e 3 ,e 5 ,e T }|{e 1]L }) Figure 1*7 Transition Matrix and Corresponding Maximal Transitions 2k figure 1.8. The matrix whose "l" entries each represents a maximal transition is called transition matrix . The determinations of maximal transitions is a first step in the study of a system. It permits the discovery of the inherent modularities of a given problem. The maximal transition however (which we shall simply call transition in the following chapters) remains an entity which is still to be defined as to its structure. We have so far ignored the presence of "external conditions" which control the transfer function assumed by a transition. A study of these conditions and their relations to the design is presented next. 1.2.6 Structure of a transition The transition is in fact the decision element of a net. It is the delay after the occurrence of an ordered set of events where some computation has to be made to determine "what to do next". Previously a transition has ber r ^efined as a relationship existing between two sets of events p. = p and E = s. For this k q relationship to hold there must be some restrictions between the elements of p, those of s and "external conditions": (1) All the events belonging to p must be terminated in order for an element belonging to s to be initiated. (2) If all the elements belonging to p are terminated, external conditions determine -.hat event belonging to s is next. 25 EXIT START Figure 1.8 Minimal Representation of System of Figure l.k 26 We must now define what we mean by "external conditions." An external condition for a transition T(pls) is a constraint which does not involve any of the reply signals belonging to p. "Constraints" may have many different meanings. They might be defined as a set of events which must not be active at the same time; they might be defined relative to the set s as a set of requirements to meet before starting any event belong- ing to s. For instance let us assume that the task: x = a * b (x,a,b variables) is to be performed by a time shared processor and let us consider the transition: T({e ,e } {e ,e ♦ e^,e j ,}), see figure 1*9* The flow chart for this transition is described as follows : (1) Are e and e, finished? a b NO: Wait, i.e. go to (l) YES: The transition may be started, i.e. go to (2) (2) Is the processor ready? NO: Wait, i.e. go to (2) YES: All the requirements to realize the next step are gathered, go to (3) (3) Select the next step according to op-code (here the event e^ corresponding to the multiplication is entered next). Many of the features that a transition exhibits show up in this example. Two kinds of conditions are distinguished: 27 'W MULTIPLE CONTROL POINT e a SEQUENCE -~f e_ *i e Events: e : computation of a e : computation of b e : addition e : substraction e # : multiplication e. : division External Conditions :C TT : processor ready or not C : instruction decoding -*■ next operation is o multiplication Figure 1.9 Transition T({e 9 e^}\ (e + ,e_,e # ,e + }) 28 WAIT CONDITIONS &, ) : If processor not ready, wait. SEQUENCE CONDITIONS (C ): The next operation is g # . Accordingly, a transition is a tvo-step process : Wait phase : where the system waits for all the requirements needed to undertake the next step. Sequence phase : the next step is selected 1.2.6.1 Wait .Function of a transition All the conditions needed for the accomplishment of the next task in a transition T.=T(p.|s.) can be 1 il l gathered and processed within a same unit: the Wait Logic. The Wait Logic is the implementation of the "Wait Function" of a transition. Definition 13 : Wait Function The Wait Function, W. of a transition T(p.|s.) is _ — L i' *i' i a binary function V i =W i (r il' r i2>"-^in.> C w) i l where w. is 1 if all the reply signals r. . coming from the events e. .belonging to p. have been received and the set of Wait Conditions C TT are satisfied. W. l w. is otherwise. i The Wait Logic can be understood as a single output switching circuit the input of which is the replies trom the events belonging to p. and the Wait conditions of set C I7 W. l. 29, 1.2.6.2 Sequence Function of a transition The decision about "what to do next" is performed by the "Sequence Function" of the transition T(p.|s.) Definition ik : Sequence function The Sequence Function, S. , of a transition T(p.js.) where s.={e.,,...,e. } is a set of binary functions: 1 il' ' m. i where t. . is 1 if w.=l and the set of Sequence Conditions ij i C are satisfied. ij t. . is otherwise. Here t. . is the task signal of event e. . £■ s.. The Sequence Logic can be understood as a multiple output switching circuit, the input of which is w. and the Sequence Conditions of set \_J C J 1J 1.3 The control point net An interesting representation of pseudo- asynchronous events can now be introduced. Definition 13: Control point net The Control Point Net (CPN) is defined as the triple < E,T,C > where: E is a finite set of events {e n ,e^,...,e } 12 n T is a finite set of maximal transitions {T n ,T_,...,T }; and 1' 2 m C is a set of initial conditions (set of task signals activated o initially) . 30 ■A maximal transition itself being defined as T. =< p.,s.,W.,S.> ° 1 *i* i* i* i where : p. is the predecessor (subset of E) so that: f 0r T 4 T p 4 p # i j l j s. is the successor (subset of E) so that p. (\ s. = 0. W. is the Wait Function of T. which processes the reply signals coming from the events belonging to p. and a set of Wait Conditions C,, to produce a signal w. i which is : 1 if all conditions for the accomplishment of the next event are satisfied otherwise S. is the Sequence Function of T. which processes w. and a set of Sequence Conditions C to determine what event (s i belonging to s. must be initiated next when w. = 1. It is worthwhile to notice that the condition T. 4 T. it p. 4 P i J i is sufficient for all T's to be maximal transitions because it implies that one row of the contingency matrix be represented by only one transition. It is now possible to introduce -:, basic building block of the CPN. Definition l6 : Control point Within a CPN a basic unit called a control point is defined as the ordered triple: < p. ,W. ,S.> r i' i' l 31 There are as many control points in a CPN as there are maximal transitions in the transition matrix (i.e. as there are predecessors in the system). From this definition, a control point has a constant structure which consists of a set of events followed by a Wait Function followed by a Sequence Function. Figure 1.10 represents the system of figure 1.1. c in terms of control points. A new symbolPX^l is used here to represent the Wait and Sequence Functions; if the flow is from left to right, the Wait Function is on the left side and the Sequence Function on the right side; the common point of these two triangles symbolizes the w. line. Control points are distinguished within the heavy black lines in figure 1.10. Two kinds of control points are defined: Multiple control points for which |p.|>l Single control points, briefly, control points when |p.|=l The CPN configuration has been widely used in the Control Design of the Illiac III Pattern Recognition Computer. The problem we will attempt to solve in the following chapters is the one of testing the logic circuits implementing such a net. Before doing this, some explanation about the actual physical implementation of the control point configuration is necessary. 32 Figure 1.10 Control Point Network for System of Figure 1.1. c 2. PSEUDO-ASYNCHRONOUS CONTROL DIAGNOSIS: a method 2.1 Introduction The previous chapter has introduced a convenient model for pseudo-asynchronous logic: the control point net (CPN). One of its advantages lies in its modularity. This modularity has been developed in order to furnish a practical unit for logic design: the control point In this chapter we develop a possible implementation of this "build- ing block" and briefly show how it can be used for the logic design of a pseudo-asynchronous machine. The test is then considered and a method based on the modularity of the design is proposed. Fault detection alone is considered. 2.2 Control point implementation: an example 2.2.1 The basic design In Chapter 1, a control point has been defined as the triple CP. = < p. , W. , S.> where p. is a set of events (predecessor) W. is the Wait function l S. is the Sequence function When p. contains more than one event, we have a. multiple control point, otherwise CP. is a single control point or simply control point . It is shown [k] that a multiple control point can be implemented using a set of control points, so that in the next chapters, only control points are considered. Each of the three parts composing a control point corresponds to a logical unit: 33 34 (1) the DO-logic (2) the Wait logic (3) the Sequence logic An example will more clearly show how this works out. Let us assume the flow chart in figure 2.1. a is to be implemented. The first step in this design is to draw the equivalent CPN. This is done in figure 2.1.b. The self loop for the rhombus (labeled C ) w is characteristic of a Wait logic. On the other hand, it is easily seen that the conditional branches C and C determine the S l S 2 sequence, i.e. the next event; they are realized by the Sequence logic. A possible implementation is shown in figure 2.1. c. The DO-logic contains a memory element and the timing stage . Here the incoming signal t is simply delayed with an R-C circuit to create the desired delay. A memory element is used because t is, in fact, a pulse. When this pulse occurs, the memory element is set; it is afterwards reset when the whole transition is completed. The DOl signal represented here is the actual control signal: it is used throughout the computer to set or re^et flip-flops, ga~e other signals, etc. However, before exiting to the computer, th J signal is processed by a Task logic . This logic is merely a box" where the DO signal is "duplicated" according to certain .ui. ditions. When the event is terminated (delay A elapsed) a negative pulse appears at r n . The Wait logic lets this signal go only when the conditions C TT : is satisfied, W otherwise r is "blocked" until the above Wait Conditxon is satisfied. (Hence, the name "Wait".) 35 Cw^ ■<§>■ ^ e,.ej.e 8 .e, events C,,.R © (a) Flow Chart (b) Control Point Net DO - LOGIC_ MEMORY D — T R S> 001 £>-4 DOl TIMING STAGE £0 T j j i WAIT LOGIC X^ «i SEQUENCE LOGIC K > > ti- 651- h - (c) Logic Design of CP1 and Signal Diagram in the case C.D.R = 1 Figure 2.1 The Basic Design 36 The Sequence logic directs w toward the "good" t. according to some Sequence conditions: C : < if D =1 then t n = w_ s 9 1 if D.R = 1 then t_ = w_ 5 1 if D.R = 1 then t = w > Some remarks must be made on the actual realization of this network. The part referred to as DO-logic is the same for all control points. Only the capacitor determining the delay time A must be changed from one DO-logic to another. If R = 8.2K, it is shown in [k] that A obeys the formula: A = 1. 5 x C ; C in pFd and A in ns. Since it is a standard logic, in the near future we could expect the DO-logic to be available directly in IC packages. The parts labeled Wait logic and Sequence logic are essentially variable and depend on the flow chart. The simplest case is where r is directly connected to DO-logic (figure 2.2). In this case we have an unconditional sequence of events. However, we are sure that e ? occurs after e is completed. In this figure a Task Logic is represented: the signals X and Y are the signals which actually exit to "the different computer processors. 2.2.2 Calling control point It is interesting to notice that t. , r. , and DO. are all i ' i ' i signals of the same nature, normally at the one level. For this reason r. can be directly used as a task signal; DO. can be used in the same way. When so used, DO. is called a calling signal and is used to call a routine (as in software). In this case 37 TASK LOGIC D- O 001 D02 d ^i 3d d d T = A + Td typically d = 10 ns (TTL series T'+OO) A = 50 ns Figure 2.2 Unconditional Sequence of Events 38 the DO-logic is called a calling DO-logic and is slightly mod- ified: it contains no timing stage. The information regarding the completion of the called routine is carried by a reply signal from this routine which is processed by the Wait logic of the calling program. An example is shown in figure 2.3. The signal DO is the calling signal; at the same time, it resets a flip-flop in the routine. This flip-flop supplies the REPLY signal. When completed, the routine sets the flip-flop; this makes REPLY = 1, thereby allowing r to propagate if con- ditions C I7 are satisfied. W The difference between a normal CP and a calling CP is, of course, artificial since in principle they work in almost the same way. However, such a distinction will later be necessary when the test will be considered. Most of the time two CP's are necessary in the main program when a routine is called (as shown). 2.2.3 An example of CP design We want to show how control points can be linked together in order to implement routines. The routine must be first defined by means of a flow chart (see figure 2.U) from which the CPN can be obtained (figure 2.5). The logical design follows in an obvious way from the CPN. One or two CP's in the logical network corresponds to each black-lined box in the CPN: One CP if the event is not a routine call Two CP's if the event is a routine call (figure 2.£) For convenience, the complete logic corresponding to routines like "EXAMPLE" are organized in one ''sometimes two) UU-pin IC 39 Figure 2.3 Mechanism of a Calling Control Point Uo Description of Events ; e.:Z» D01.M and reset reply EXB e :call routine BD and wait for reply BDR e. :Y= DOU.A X- DOU.A BU= DCft" e : call routine ED and wait for reply EDR e_: call routine FY and wait for reply FYR e : set reply signal EXR Figure 2.U Flow Chart of "EXAMPLE" kl Figure 2.5 CPN of "EXAMPLE" U2 •OZ o BOC •oY •o X •oBU •oEDC •oFYC •oEXR EXC« CARD INPUT "OBDC-CARD OUTPUT Figure 2.6 Control Point Implementation of "EXAMPLE" U3 »M23Jl I ja, S307A I ' - Figure 2.7 A Wired Routine kk boards (figure 2.7). These cards are then connected to form the Control Strategy. More information concerning the logic design can be found in [h], 2.3 Fault detection and location in combinational networks: a review 2.3.1 A model for fault analysis Many methods have been developed for fault detection and fault location in combinational nets. However, the same fault model consisting of stuck-at-1 , stuck-at-0 permanent faults is used everywhere. If a stuck-at-b fault is present the circuit behaves exactly as if a "b" value were applied to the faulty line. In figure 2. 8. a, a 2-input DTL-NAND circuit is represented: z i = x r y i assume diode D, ,is open: we say that line a, is stuck at 1 (s-l) because Z l = y i = X - y l On the other hand, an open diode D ,in the 2-input DTL-NOR circuit figure 2. 8.b is a (s-0) fault for line x because the initial circuit Z 2 = X 2 + y 2 is transformed into z 2 = y 2 = + y 2 There are many different possible failures in a circuit such as the one in figure 2.7. a: Dl open, D2 open, Tl open or shortened... We consider only those which can be modeled by a (s-0) or a (s-l) fault . ^5 12V h *fa % n + 12V Ri O Z^Xj'Y! y 2 - (a) 2- input NAND D 2 Ri -6V 12V (b) 2-input NOR o z 2 = x 2 + y 2 Figure 2.8 NAND and NOR DTL Circuits U6 Furthermore, we consider the single fault assumption, i.e., only one fault at a time is present in a given circuit. This assump- tion of course is. very, unrealistic for IC technology since, if a package is bad, probably more than one failure exists in the gates within this package. No good theory or method has yet been found to deal with multiple faults. Such a theory is necessary since for a package with n single possible faults there exists 3 - 2n - 1 multiple faults and an enumeration process is there- fore impossible. A study of the multiple fault assumption has been made by J. P. Hayes [lO], This study is essentially based upon the indistin- guishability between faults developed in [9]. Two faults are said to be indistinguishable if any test which detects the first one also detects the other one and conversely. In figure 2. 8. a the f ault (x - 0) (x stuck-at-0) is indistinguishable from the fault (z - l) and also from the fault (y, - 0), since the only way to detect any of these faults is to make x = 1 and y = 1 (which should make z = 0). On the other hand, faults (x - l) and (z - 0) are distinguishable since the test x = 1, y =0 (which should make z = l) detects the fault (z - 0) but not (x - l). A complete study of indistinguishability relations between faults can be found in [lO]. It is shown that in the hypothesis of multiple faults not all cases of multiple faults need to be examined; only an amazingly small subset of the initial multiple fault set needs to be tested. In fact there is an upper bound in the multiplicity of the faults to test for in any net. It is also shown that for ^7 a fan-out free network s a single fault detection test detects all faults up to a multiplicity of h. Furthermore, in some special circumstances (2 level AND-OR, OR-AND, AND-NOR , OR-NAND...), a single fault detection test also detects all multiple faults [ll]. Although the above results represent a big reduction in the number of faults to consider ( we mean by fault, a single as well as a multiple fault), this number is still very large. For instance Hayes develops an example which consists of 2 fan-out free subnet- works. The total number of single faults is 22; the total number 22 10 of multiple faults is 3 - 1 - 3.1 x 10 , the multiple faults being from multiplicity 1 to 22. By the theorems mentioned above, it is proven that the maximum multiplicity of the faults to test for is 6. Therefore, the new set of multiple faults has 6 21 1+ £ ( ) = 8,5 x 10 elements, which is still a very large number i=l X although, the circuit itself is rather small). For these reasons, the single fault assumption is still taken as tub general rule. 2.3.2 Test generation When the set of faults we want to test for has been decided, different methods of test generation are possible: Path sen- sitization [6] [7] [12], indistinguishability classes [9] [11 J + path sensitization, boolean difference method [8] [13] [lb] [15] s random generation [l6] and exhaustive method [17]. Only the exhaustive generation method is described here, since this is the only one which has, in our case, appeared to be the simplest. However, a review of all of them is done for complete- ness at the end of this thesis. (Appendix l) kQ As it is shown later , a control point network can functionally be decomposed into small subnetworks. Individual testing of each of them is necessary. Therefore, a partic- ularly efficient method for small networks is needed . Besides, methods like path sensitization or boolean differences are not applicable because these circuits can be partially sequential (presence of flip-flop or feedback loops in them). The most obvious (and the simplest) method in this case is the so-called exhaustive test generation . Input vectors (i.e. sequences, of O's and l f s at the input of the network) are exhaustively generated. For each of them 2n + 1 simulations are done (n = number of possibly faulty lines), each of them but one simulating the network with a particular fault. In this way, a table (fault table is built. It contains one row per test and one column per fault. Input vector (test) generation is terminated when each column has been "covered" by at least one test. The table can then be reduced in the same way as prime implicant tables are in switching theory. The final reduced fault table is obtained in this way; it can be used directly to test the network. When finding a minimum number of tests is not imperative, this reduction may not be necessary. Furthermore, simulating the network is no longer necessary if, when the tests are physically applied to the card, in parallel, some kind of simulator gives the operator the fault-free network output. As it will be seen in Chapter 3, this is actually the case for us. k9 2,k Fault detection in pseudo-asynchronous logic Before undertaking the explanation of the method itself, a brief review of our definitions is necessary: Input set: Set of input lines of a network Input vector: A particular set of values assigned to the elements of the input set. (Noted: IV ) Output set: Set of output lines of a network. Output vector: Same as above. A test: A particular input vector, t, such that the output value of a fault-free circuit changes if a given fault occurs. A set of tests which detects all faults in a circuit is also referred to as a test (T). A test is also the name of the operation which consists of applying the tests to the card. In all cases, the context will resolve the amDiguity. Fault detection test: a test T such that there exists at least one test t € T, which fails if a given fault occurs in the circuit. 2.U.1 Fault location or fault detection? A decision has to be made here as to what degree of diagnosis is needed. Do we need fault detection or fault location? In the particular technology used here, control boards are composed of IC's which can be changed very easily. These IC's are interconnected with wires and we must assume that these connections are well realized because there is no model- like stuck-at-1, stuck-at-0 lines - yet found to deal with such kinds of wiring mistakes. 50 Therefore, if a fault occurs, it must come from a bad chip. As a card is only composed of about 25 chips, it has seemed a good solution, in the case of a failure, to find the wrong chip just by changing each chip sequentially. Besides, only one card of a kind exists and it would certainly be too expensive in terms of computer time to generate a location test for each card. From now on we consider that only a fault detection test is needed. We will see later that a certain degree of fault location is possible. 2.4.2 The test generation strategy The purpose of this section is to explain a "first approach" algorithm wnich generates input patterns for the test of control point logic cards. The basic strategy is to take advantage of the modularity of the design. As said previously, the logic corresponding to a given control routine is arranged and wired on one (sometimes two) etched, integrated circuit card. This logic can be partitioned into: (1) the control point network (or sequence stage ) which implements the sequencing of the different tasks in the routine. It is composed of all the DO, Wait and Sequence logics of the card. (2) the task stage which "performs" the action associated with each task within the routine (see figure 2.2 and figure 2.6). 51 The idea is to generate tests separately for these two quasi-independent subsets: this is the object of the CPTEST algorithm. CPTEST decomposes into two algorithms CPTEST1 and CPTEST2 which corresponds respectively to (l) and (2) above. A listing of CPTEST can be found in Appendix 2. CPTEST1 generates exhaustively a set of fault detection tests for the sequence stage; whereas CPTEST2 does the same thing for the task stage. Completeness of the test sequence of this latter algorithm is highly dependent on the exact nature of the task stage and on the precautions taken when applying the tests. CPTEST2 is based on the assumption that the task stage is entirely combinational - which is of course, not always true. However, it is believed that it gives an adequate basis for debugging the task stage if some conditions are met before applying each test (like resetting all flip flops). 2.^.3 Aggregates and associated modules The card to be tested is first divided into task stage and sequence stage logic, as described above. These two sets are then divided into modules and aggregates respectively. An aggregate consists of a control point or a set of unconditionally connected control points. To each aggregate corresponds a module. The module associated with an aggregate is composed of the task logic (s) attached to the DO-line (s) of this aggregate. It should be noted that the division into aggregates and modules provides a unique partitioning of the card logic. In figure 2.9 52 TASK LOGIC INPUT LINES {«_ FOR AGGREGATE NO. k TASK LOGIC ' L WAIT- SEQUENCE INPUT LINES FOR AGGREGATE NO k MODULE TASK LOGIC TASK LOGIC ..t-ig CPi.2 DO , CAAD OUTPUTS AGGREGATE . I TO NEXT [AGGREGATES Figure 2.9 A Composite Aggregate TASK LOGIC INPUT LINES FOR AGGREGATE NO.q WAIT- SEQUENCE INPUT LINES FOR AGGREGATE M NO.q MODULE i TASK LOGIC CPj DOj DO CARD OUTPUTS AGGREGATE W TO NEXT AGGREGATES Figure 2.10 A Simple Aggregate 53 aggregate #k is called a composite aggregate since it consists of three CP's. The module associated with this aggregate is enclosed with broken lines. In figure 2.10, the simplest case is illustrated: one CP in the aggregate and therefore a module composed of only one task logic. In the same way, card inputs are partitioned into module input sets and aggregate input sets. These may overlap in many cases; the algorithm still handles them. For clarity, consider the example of the Flyback Routine of figure 2.11. As shown the card input lines are given labels from 1 to 2U. Table 1, lists the aggregates and modules of this card together with their input set. Aggregate or The aggregate Aggregate Module Module # : consists of: input set : input set: 1 (CP1) (15) (none) 2 (CP2) U,5,6) (none) 3 (CP3,CPM (5,16,17) (1,2,3,7,8) i+ (CP5,CP6) (Ik) (1,2,3) 5 (CPT) (none) (1,2,3,7,8) 6 (CP8) (none) (2) 7 (CP9,CP10) (12,13) (none) 8 (CPU) (none) (9,10,11) Table 1: Aggregates and Modules for FLYBACK Routine Several remarks must be made about this example: 5^ a; c •H -P O u d H 8) •H 55 (1) The module attached to a given aggregate is sometimes hard to find since the same logic can be shared by several aggregates. This is the case for aggregates #3 and #5. The operator must remember that modules may overlap each other. (2) The module associated with aggregate #8 is a particular one: it is not attached to the DO-line. However, the reader will realize easily that this logic is task logic rather than sequence logic since no control point can be hit after CPU. (3) In the same way, the Wait-sequence logic is not always attached to the Ao-signal of a CP (or of an aggregate). This is the case for aggregate #2 which is in some way a "calling control point" since its DO line is used to select the next aggregate (#3, 6 or 7). It follows from the above remarks that the partitioning into aggregates and modules is sometimes far from systematic. In this case, the experience of the reader in interpreting the logic is decisive. In practice, aggregate input sets and module input sets can be taken larger than necessary. 2.5 The algorithm : basic principles 2.5.1 Generating tests for the sequence stage A table, the A-table, is first constructed which contains all tests necessary to test exhaustively each aggregate. The tests for aggregate #i are contained in the Ai-subtable. However, a line in the Ai-subtable contains not only a test vector for aggregate #i but also the number (label) of the aggregate (s) hit next after aggregate #i under this input vector. This is made 56 possible by simulating the Wait-sequence logic of aggregate #i. This information is part of the card-dependent data fur- nished to the program. If one imagines the aggregate network as being tree-like (with possible circuits, however) and the control signal as following the branches of this tree, each line in any Ai-sub- table represents an oriented edge in this tree. From a test standpoint, this information is not directly usable by the operator since the possibility does not exist to start in- dependently any aggregate: the only possibility available is to start at aggregate #1. Hence a process referred to as "concatenation of the Ai-tables" which produces the B-table , generates from the information available in the Ai-subtables a minimal set of paths and for each path, its associated input vector. Each of these paths starts at aggregate #1 and represents the actual path in the network taken by the control signal under the corresponding input vector. Each elementary branch represented by a line in a Ai-subtable is contained in at least one path of the B-table. The B-table is the information necessary to test the sequence stage of the card. Each of the input vectors in the B-table must be applied to the card and the corresponding path taken by the signal (i.e. the aggregates hit successively) must be recorded. In order for the operator to verify that for each test the control signal follows the right path in the aggregate network, some means must be given to track this signal. The only observable points for the operator are the output lines and more precisely the 57 v task stage output lines. One possibility is to sensitize paths in the task stage from all the control point DO signals to the output lines. In other words a task stage input vector called "a sensitizing vector" which will be permanently applied during the test, has to be determined by the operator before undertaking the test itself. This vector must sensitize a number of output lines for a maximum number of DO-lines. Finding such a vector is simple and can be done manually. This vector must be concatenated with all the input vectors found previously (B-table) in order for them to be efficient. 2.5.2 Generating tests for the task stage A module is often of small size and its exhaustive test is therefore possible. Using this idea a table, the C-table , is constructed which contains all the task stage input vectors necessary to exhaust- ively test each module. Like the A-table, this table is not directly usable since there is no way to activate separately the DO signals feeding a given module. A process referred to as "merging of B- and C-tables" is necessary. It simply merges the input vectors of the C-table with the input vectors of the B-table. The rules for this merging are: If IV (input vector in C-table) is a test for module #i, look for a path in the B-table which contains aggregate #i. When one is found, then merge the corresponding input vector with IV if possible. Otherwise look for another path in the B-table which contains aggregate #i...and so on. The results of the mergers are stored in the final C-table, or 58 PC-table. This table has all the information necessary to test the task stage. The card input vectors it contains must be applied to the card and the corresponding output variations must be recorded. 2.6 The algorithm: implementation A general description of CPTEST can be found in figure 2.12 and its listing in Appendix 2. The following is a detailed explanation of how the two algorithms CPTEST1 and CPTEST2 are im- plemented in our FORTRAN program. Some description must first be given of the way information is stored in this program. The A- table If KMAX is the number of aggregates in a card, there exist KMAX Ai-subtables (Al ,A2, . . . ,AKMAX) composing the A-table (figure 2.1?) Each line in each of these subtables represents an oriented branch in the aggregate network, as stated above, and is divided into three parts: (l) the table of predecessors, (2) the input vector and (3) the table of successors. The first represents the aggregate currently under test (the origin of the branch); the second is a record of the current input vector, and finally the third represents the aggregate (s) hit next under the present input vector (extremity (ies) of the oriented branch). To implement this division, four arrays are defined: APRE (K,I,J), AOC (K,I,J), AINP(K.I.j) and ASUC (K,I,J). K is the aggregate number(or subtable number), I is the input vector number and J is : (1) An aggregate number in APRE and ASUC (2) An input signal number in AOC and AINP The table of predecessors is implemented using the array APRE. In 59 ENTRY PARAMETER INITIALIZATION A-TABLE Construction CPTEST1 Concatenate Lines of A-TABLE to form the B-TABLE Reduce B-TABLE: Sequence Logic Test Patterns C-TABLE Construction CPTEST2 Merging of C and B-TABLES : FC-TABLE Task Logic Test Patterns Figure 2.12: General Structure of CPTEST 60 the A-table, tests within a Ai-subtable concern aggregate #i. It is therefore clear that the following must hold: APRE (K,I,K) = 1 and APRE (K,I,J) =0 for J 4 K if a "l" in the table of predecessor indicates the aggregate under test. This can be verified in figure 2.13. The input vector is defined using two arrays since an input line can be three=valued: 0, 1 or "." ("." means don't care.) AOC is the occupancy array and tells whether or not a input line is a don't care. AINP carries the value of. this input line when it is not a don't care. The array ASUC is used to define the successor (s) of a given aggregate under a particular input vector. If, ASUC (K,I,J) =1 J = J ,J ... and ASUC (K,I,L) =0 L = L,L »,... with (J J" 2 ... t )ft (L 1 ,L 2 ,. .. ,)= 0, then for the test #1 of aggregate #K, the aggregates #J ,J , ..., are hit next by the control signal. As an example, consider line 10 of the A-table of figure 2.13. This line is contained in the A2-subtable since there is a "l" in column 2 of the table of predecessors. The input vector corres- ponding to this test is: (U,5,6) = (l,l,l) (all others are don't care) The successor for this test is aggregate #3 since there is a "l" in column 3 of the table of successors. When there is no successor for a test (line 1 of the A-table for instance) the control signal is blocked by the current aggregate. 6l In conclusion, a line of a AK-subtable is represented by: APRE(K,I,J) J=l,2,...,12 AOC(K,I,j) | > J=1,2,...,2U Sl=l,...,I AINP(K,I,J) J ASUC(K,I,j) J=l,2,...,12 The B-table Four similar arrays are used to describe the B-table: BPRE(l,J), BOC(l,j), BINP(I,J) and BSUC(I,J). All but the first have the same significance as for the A-table. A line in the B-table represents a path. Accordingly ,in this table the notion of a pre- decessor is replaced by the notion of a path. This path is stored in the BPRE array. If BPRE(I,1) = 1 BPRE (I, 2) = 1 BPRE(I,3) = 1 and BPRE (I, J) = ■ J a k,5 9 . . . ,12 then test #1 in the B-table corresponds to a path containing aggregates #1,2, and 3. The C and FC-tables As already explained the C-table contains the input vectors necessary to individually test each module. Three arrays are defined: CPRE(I,J), C0C(I, J) and CINP(l,j). COC and CINP concern the input vector. On the other hand if CPRE(I,J) = 1 and CPRE(j,L) =0 L j J then the input vector #1 of the C-table is a test for module #J (associated with aggregate #J). 62 The FC-table is in fact a part of the C-table and hence obeys the same conventions. The similar structure chosen for the A,B,C and FC-tables is of considerable value when it is necessary to compare or merge two lines of two of these tables. In the following we explain how the concatenation of lines in the A-table is actually carried out , then how the merging of the B and C-tables is done, and finally, we will develop the program specifications, 2.6.1 Concatenation of lines of the A-table: CPTEST1 (figure 2.15) The result of this process is the B-table where each line describes a path starting at aggregate #1 and its associated input vector. The flow chart of CPTEST1 is given in figure 2.lU. First the Al-subtable is copied on top of the B-table. Then lines of the B and A-tables are concatenated according to the following criteria: If line 1 belonging to the B-table contains a "l" in position j of its table of successors and line 1 belonging to the A-table has a "l" in the same position of its table of predecessors, then lines 1 and 1 are concatenable: a a If furthermore, the input vectors in lines 1 and 1 A D are compatible tr+en iines 1 and 1 are concatenated ' A £5 as shown in the flow chart and form a new line at the bottom of the B-table. This process is continued until no more concatenations are possible. Precautions are taken to detect circuits in the aggregate network and so to avoid infinite loops in the program. Also mergings are done so that the aggregates hit consecutively (the path taken by 63 — o «:• cs c, r- r> o o c o o o r. o C' c-> c. r* <^ OCOCC'OOOC>00000©C'OOC' 000000 oooooooonoooooooooooooooooo oooooooooooooooooooo^joooo — o OO— . — • — iOr-,<->oaOOOOO<->00000 — ooooo © o o o o — ooooooooooooooooooooo 0000000000000000000 — noooono 00000000000000 — — — oooooooooo Ooocc.o — — — — OOOOOOOOOCOOOCCC. © O — ©0©©©0©©©©C©0©0©0©eOOOO©C ooooocoeoooocoocoooooccoooo f- ......... .0000 — — —•—<• •••••■• ,0 ..........oo — — 00 — — •••••••• o — u> p>* *••••• ■ < I •<•■••••> I • I I • I qc o * © — u w /Ll \Line A-(KA.IA) IA = IA+1 KA = KA+1 YES Output Un- checked Lines of B-TABLE: New B-TABLE Figure 2.1.1+: A-table Line Concatenation : CPTEST1 65 r- r- r*~ r- r- r-r^^r-f^r-r^r^r^-^-r^h-r^r^f*- r-r**r , --r-f-r'-r*-r-r--p-r*.r*-r'- ~-i <\j m -4- irs -o r*- odo-o O'-'fNii^^io^^oc© o •-< in f<"i sj- ir. ^o p- ec c a o u. z 1/1 — . z KJ IXI < •— i _) UJ t- 03 X — OCOCC'C— c. c — C--0 — — o -• o - c - c f • O — O — CO o c. C C O O . — w .m -. -i _ 0-'»'»'J33'>3-«-<-<*-<-«-«-<-<-«->3'>3">'>-«-'-<-<-«-«3-« o o o o o o o o o o o o o o o o o o o o o o o o o "3 D O .> J ■i A A -« ■4 A A A A A A A ■A A Ml A -A A A A Figure 2.15 B-Table for Flyback Routine 66 the control signal) appear in the table of predecessors of each line of the B-table. This information will be useful later. For the routine of figure 2. 11, the A-table is represented in figure 2.13. The B-table obtained by application of the algorithm of figure 2.lU, is represented in figure 2.15. Thirty- nine tests are necessary to test the sequence stage of the Flyback routine. On the top of the B-table the "sensitizing vector" defined in section 2.5.1 is shown. In this case none is applied (all inputs are don't care). As the reader can verify a maximum number of DO signals are "seen" at the card output with- out applying any sensitizing vector. 2.6.2 Merging of B and C-tables Recall that the C-table contains the tests necessary to check separately each module (see figure 2.l6). For instance, test #55 concerns module #5 since CPRE(55,5) = 1, the input vector being: (1,2,3,7,8) = (0,1,1,1,0) (all other lines don't care) If module #i is to be tested, the DO line(s) feeding module #i must be activated i.e. ,the aggregate # i must be hit by the control signal. Hence the following method is used. First, the last line in the B-table is copied in the final C-table (FC-table), then: If line 1 in the C-table has a predecessor table which contains a "l" in position and line 1^ of the B-table has a "l" in the same position of its table of predecessors, then 1 and 1 are mergeable: if, furthermore, the input vectors in line 1 and 1_ are compatible, then 1~ and 1,, are merged and the resulting line is added to the FC-table. 61 PREDECESSORS * 5 o 7 8 9101112 C-TABLE FOR CARD * I"." MEANS DONT CARE) INPUT VECTOR 9 10 11 12 13 14 IS 16 IT 18 19 20 21 22 23 2 «. JutOOOOOOOOO . uuiOOJOOOOOO 1 . uuiooooooooo 1 . juiOOoOOOOOO 1 1 . Ob* OOuOOOOOO 1 . uuiOOoOOOOOO 1 1 . uuiOOoOOOOOO 1 1 . JuiOOoOOOOOO 1 1 1 . u-.UGuOOOOOO . 1 OjiOCOOOOOOO 1 . 1 JuiOOoOOOOOO 1 . 1 JuiOOoOOOOOO I 1 1 JutOOjOOOOOO 1 . 1 JuiOOOOOOOOO 1 1 . 1 JuiOOoOOOOOO 1 1 , 1 JuiOOoOOOOOO 1 1 1 . 1 u u i OOuOOOOOO 1 JuiOOoOOOOOO 1 . 1 ouioOOOOOOOO 1 1 JuiOOuOOOOOO 1 1 1 v - i u 1 1 JuiOOOOOOOOO 1 1 1 O..iouu000000 I I 1 l) w i 000000000 1 1 1 1 OuiOOOOOOOOO Jul OOuOOOOOO 1 JuiOOoOOOOOO 1 OuiOOOOOOOOO 1 1 Owl OOuOOOOOO 1 OuiOOuOOOOOO 1 1 OuiOOOOOOOOO 1 1 JuiOOoOOOOOO 1 I 1 u u J lOuOOOOOO OuulOuOOOOOO 1 JuulOuOOOOOO 1 . u u 100000000 1 I OuulOOOOOOOO 1 OuulOoOOOOOO 1 1 . UuulOuOOOOOO 1 1 UuulOoOOOOOO 1 1 1 . uuuOluOOOOOO . JuuOloOOOOOO 1 OuuOloOOOOOO 1 . . JuuOluOOOOOO I 1 . . OuuOl oOOOOOO 1 . . OuuOluOOOOOO 1 1 . . uuuOloOOOOOO 1 1 . JjuOluOOOOOO 1 1 1 . OuuOlOOOOOOO . 1 . OuuOloOOOOOO 1 . 1 . OwuOlOOOOOOO 1 . 1 . uuuOl uOOOOOO I 1 . 1 . JuuOluOOOOOO 1 . 1 . OuuOloOOOOOO 1 1 . 1 . OuuOlOOOOOOO 1 1 . 1 . sucressa-is 4 5 i 7 9 9! -in ' n 12 M 14 15 16 17 18 19 20 21 22 23 24 25 ?6 27 28 29 30 34 15 36 40 41 42 50 51 OluOOOOOO I 1 1 . 1 56 OloOOOOOO . 1 57 01O0O0OO0 1 1 58 OluOOOOOO 1 . 1 ■ 59 OluOOOOOO 1 1 . 1 60 OloOOOOOO I 1 61 OluOOOOOO 1 1 . 1 62 OluOOOOOO 1 1 . 1 63 OloOOOOOO 1 I 1 1 64 010000000 65 OloOOOOOO 1 66 OluOOOOOO 1 67 OloOOOOOO 1 1 68 010000000 1 69 01 uOOOOOO 1 1 70 OluOOOOOO 1 1 71 OluOOOOOO 1 1 1 72 001000000 . 73 COlOOOOOO 1 , 74 OOuOlOOOO . . . . 75 OOuOlOOOO . . 1 76 OOuOlOOOO . . . . I 77 O0O01O0OO , . . . 1 1 78 OOuOlOOOO . . 1 79 OOoOlOOOO . . . . . I 1 80 000010000 . . . 1 1 SI 000010000 . . . . ] 1 82 Figure 2.16 C-Table for Flyback Routine 68 Merge Input Vec- tor of Line C- (IC)andFC-(l) and Put Result in Line FC-(I) ( ehtry J QOLangth of C-TABLE QB"L»nfth of B-TABLK Q" Be ginning of FC- TAMJ"QO»l Hf-Ind of PC-TABLE Bote: PC-TABLE • C-TABLE line Q to CJ Line X-(Y) aaacs: X-TABLE, line Y. Copy Last Line of B-TABLE in Line fC-(Q) IC - 1 Search the One in prede- cessor table of Line C-(IC) CPRK(IC,J)- .TRUE.;I - Q I - 1*1 /Input ine C-(lC)and \FC-(I) Compatible' NO/ IC - QC IC = IC+1 YES OUTPUT FC-TABLE IBB • 1 IB-QB-IBB+1 „ Input /Vector in^ Lines C-(IC)and\NO (IB)Conpatible>~ ? Merge Input Vector of Lines C-(IC), B-(IB) and Put Result in FC- (QP). Copy Pred. Table of Line B-(IB) in Line FC-(QF) IBB * IBB+1 Figure 2.17: Merging of C and B tables: CPTEST2 69 i/i i_) c OOOOC>OOOOOOOOOOOOOOOOOOOCOOOOOOC> • *. f\J ........ «t UJ H- "■ or =3 < a. -i oocjO — — ---- O O Z -" a — OK -" z O a O — O— ' © -- O — a: C o 00 OOOOOOoOOOOOOOOO— '**—'-*•-<'*— '-< r- OOOOOOOO-- — i-*-4-*-*-*-*0©0©00©0 O O © O — — '.*-*000©.*-h^-<0000.-4^i--i-<©0©0-*.- i -. -* . • 0_i©--C-<©--0--0-.©-iO — 0--0^.0-<0--0--0-jO^©-^ . . (SJ oooooooooooooooooooooooooooooooooo -• oooooooooooooooooooooooooooooooooo oO o oooooooooooooooooooooooooooooooooo a: -" o tr> oooooooooooooooooooooooooooooooooo CO !/, CO _«_._ ( .j_i,H.-l~l-«.-t.-l-*-«-J.-«-<-<.-l.-..-i.-<-H-<-i-<-«-*-<.-l.-(-<_«,*.-. LU (_> *"• 0000000000000000000000000©0000©0-J-« LU XI a. \J -t -t -* .i-i-4-«-<-<-<-i-4-<-«-tH-.-«.H-«-<-<-«-«H-»-<-«-<-«-«-«-<-t Figure 2.18 FC-Table for Flyback Routine TO In fact CPTEST2 (figure 2.17) is a little more sophisticated. It tries first to merge a line of the C-table with a line of the current FC-table; if this is possible, the merging takes place and no line is added to the FC-table. This reduces the size of the FC-table. Moreover, for the same purpose, if no merging is possible with any line of the FC-table, the B-table is considered from bottom to top , since bottom lines always correspond to a longer path. This algorithm has been applied to our example and the result is shown in figure 2.18. Only thirty-four tests are needed to test the Task logic. 2.6.3 Program specification s Three kinds of program specifications must be given to the program: parameter specifications, sequence specifications and task specifications.* Parameter specifications After giving labels to the card input lines (from 1 to 2k) and partitioning the card logic into aggregates and modules, the operator must enter the following parameters: SERIAL = reference number of the card KMAX = maximum number of aggregates N (J) = number of input lines for aggregate #j(j=l,. . .KMAX) TASK(J) = number of input lines for module #J(J=1,. . . ,KMAX) SENS = sensitizing vector * The author is aware of the fact that this program could be further simplified. Nevertheless, in its present state, its efficiency has been proved for several samples. 71 For this operation he uses a DATA statement which is part of the DECLARATIONS in the main program (see Appendix 2, statement 10). Sequence specifications Information must be given to the program in order for it to construct the A-table. This information must include for each aggregate, the labels of the input lines of this aggregate and a description of the Wait-sequence logic belonging to this aggregate (for simulation purpose). Consider aggregate #2 of the Flyback routine (figure 2.1l). The Wait-sequence logic of this aggregate is shown within the broken lines. Inputs are R(#U), CWC(#5) and TS(#6), and the logic implemented is: If TS =1 . .o aggregate #3 hit next If TS.R.CWC = 1 aggregate #6 hit next If TS.R. CWC = 1 aggregate # 7 hit next The information inserted in the program has the following format : 2k CALL ASSIG (U,5 ,6,0,0,0,0,0) ASUC (K,I,3) = AINP (K,I,6) ASUC (K,I,6) = .NOT. AINP (K,I,6) .AND. AINP (K,I,U) .AND. AINP (K,I,5) ASUC (K,I,T) = .NOT. AINP (K,I,6) . AND. .NOT. (AINP(K,I ,h) AND. AINP (K,I,5)) GO TO 6 The i of label ik shows that this part of the code concerns aggregate #i (in our case i=2). The first part (CALL ASSIG statement) is the input assignment which gives aggregate inputs (in our case #4, 5 9 and 6) the values of the 1st, 2nd, ..., 72 8th stage of an incremental counter. The maximum number of inputs for an aggregate is taken to be 8; if there are fewer than 8 inputs ( as in our example) the remaining parameters in the CALL ASSIG statement must be equal to zero. The second part of the code is the Wait-sequence logic simulation. In our case aggregate #3 is hit if TS = 1 i.e. AINP (K,I,6) = .TRUE. Similarly for aggregate #6 and #7. The last statement is a GO TO 6 if i = 1,2,..., KMAX. Otherwise (for i = KMAX +1,...,12) the sequence specifications are replaced by the single statement: ±h CONTINUE . The sequence specifications must be inserted in the deck after statement #32 (as shown in Appendix 2). Task specifications In the same way information must be given the program to describe the logic of a given module. 2kh CALL ASSIG (1,2,3,0,0,0,0,0) GO TO 16 The label 2iU (i = h in our case), indicates that this part of the code corresponds to module #i. The code itself says that module #U has input lines XDUF(#l) , X0RY(#2) and YDUF(#3). The maximum number of input for a module is taken to be 8; if there are fewer than 8 inputs, as in the example, all the remaining parameters in the CALL ASSIG statement must be equal to zero. When i = 1,2,. . . ,KMAX, the last statement is: GO TO 16 73 Otherwise (for i = KMAX + 1, ...,12) the task specifications are replaced by the single statement: 2iU CONTINUE The task specifications must be inserted in the deck as shown in Appendix 2. 3. DESIGN OF THE SEQUENCE TESTER 3.1 The Sequence Tester 3.1.1 The Problem In the previous chapter we designed a minimization procedure applicable to any Control Card. The result of this procedure is a set of input vectors T=(t^, t^j t_, . . . ,t ) . If the card produces the desired outputs for all these t.'s, it is said to be fault-free; otherwise it is said to gontain a failure. No mention has been made of the way the t.'s are applied to the Individual board. This is the purpose of this chapter. As it will be seen in the next paragraph, facilities have been added to the control point design to make the fault location process easier in the case of a failure. It is now our aim to show how to use these facilities in the most efficient way. In our case, a processor PDP/8e is available to monitor the testing process. Therefore, the design of a special interface between the card and the processor is necessary. This interface must: (1) Take full advantage of the card design regarding fault location capabilities. (2) Give as much information as possible to the processor about the card behavior in the case of a failure. (3) Be able to handle one or two cards at a time. 7^ 75 (U) Be fast. (5) Be versatile (if possible), i.e. provide the possibility of testing sequential circuits as well as combinational circuits. (6) Be economically feasible. 3.1.2 Signal blocking in control point logic We have already developed in Chapter 2 the basic, functional implementation of the control point. In fact, the control points actually used in the Illiac III Control are slightly more com- plicated to allow for testing. The. basic idea is to permit the operator to observe step-by-step the propagation of the contro] signal through the logic. In the case of a malfunction, this would allow the operator to locate exactly the failing element, in our case, the failing control point. For this, the control signal needs to be blocked at each control point. This can be done in several ways . In the following we explain two means used in Illiac III. They correspond to two different designs that we shall call: MH-control point (CP-MH),and GO-control point (CP-GO). 3.1.2.1 MH-control points (figure 3.1) An extra line called maintenance halt (MH) is added to the initial DO-logic. When MH=0 and a pulse signal appears at Ai , the flip flop F is set (A=l) , but the signal does not propagate through B since the signal EN=0. However, when MH switches to 1, EN=1, 1)0=0... , and 16 (or t) (or r) Ai MH DO Ao Figure 3.1 CP-MH with Test Sequence 77 the signal propagates normally through the CP. We say that, by making MH=0, we disenable the CP; otherwise we enable it. Let us consider an unconditional string of CP's (figure 3.2): CP ,CP ,...,CP Initially MH1=MH2=. . .=MHn=0: all CP's are disenabled. If however, a pulse appears at Ail, F is set. If we make MH1=1 and MH2=MH3=. . .=MHn=0 , the signal propagates through CP and is blocked at CP If then we make MH2=1 and MH1-MH3=MHU=. . . MHn=0 , the signal propagates through CP and is blocked at CP and so forth; the signal progression can be easily seen. In this design the MH lines are independent and they are each connected to a particular pin at the edge of the card. 3.1.2.2 GQ-control points (figure 3.3) Two extra lines per CP are provided here for test purposes, GOTASK and GODELY. Both lines are normally one when the system is operating and are complements of each other when the system is under test, i.e. G0TASK=1 , GODELY=0 and vice versa. Furthermore, the GOTASK and GODELY lines are common to all the CP's of a same card. Let us assume that GOTASK=0. If a pulse appears at Ai , the flip flop F is set and the signal is blocked at B. Let us now switch GOTASK to 1. Then the signal propagates normally through the CP until it is blocked at gate C (because of the value of GODELY). If we switch GOTASK 78 MH1 MH2 MHN 1 I DOl 1 l D02 Ail CP1 Ai2 F 2 CP2 Aol Ao2 AiN Figure 3.2 Blocking Effect Due to MH-lines (Unconditional String of CP's) 79 GOTASK Ai #— Ao GODELY Ai GOTASK DO Ao GODELY A Figure 3.3 CP-GO with Test Sequence 80 back to 0, then C is enabled, F is reset, DO goes back to 1 as well as Ao: the cycle is completed. In other words accomplishing the cycle G0TASK=1, GOTASK=0 , is exactly equivalent to the already explained cycle MH=1,MH=0, for a CP-MH. It can be shown (figure 3.M as done above, that a set of GOTASK-GODELY lines can be used for a step-by-step propagation of the control signal. The obvious advantage of this method is that only two lines are needed for each card. There exists a slightly different CP-GO named "Calling CP-GO" or CCP-GO based on this technology (figure 3.5). Only one extra line is provided here (GOTASK). However, two more functional lines exist: the reply lines (R and IR). The function of this special CP is to call routines using the DO line and to wait for a reply at either R or IR. When this reply appears (i.e. R or IR=l) , the signal resumes its cycle through the logic and initiates the next CP through lo or Ao. As can be seen in the signal diagram, IR and R are- from a test standpoint exactly equivalent to the GODELY line previously defined. In fact, the sequence: GOTASK=1,IR=R=0 then GOTASK=0 ,IR=R=1 (for a CCP-GO), produces the same effect as the sequence: (for a CP-MH) MH = 1 then MH = From that it follows that for test purposes all the IR and R lines in a given card are tied together and connected to the GODELY pin. 81 GOTASK GODELY Al A2 A75i=Ai? Ai DELAY TIME __ CYCLE TIME OF CP1 OF CP1 Figure 3.U Blocking Effect of the Sequence GOTASK=GODELY=0 , G0TASK=G0DELY=1 on the Advance of the Signal (Un- conditional string of CP's) 82 GOTASK Ai REPLY \ IR SIGNALS J R Ai GOTASK GODELY = IR,R DO Ao.Io Figure 3.5 CCP-GO with Test Sequence 83 3.1.2.3 Conclusion Although two (or three) different techniques are used to realize the "signal blocking" at each CP, they are (or can be made) equivalent. From now on, the CP-MH will be considered most of the time. This implies the following relations: GODELY=GOTASK=IR=R=MH1.MH2.MH3 MHn i.e. if one MHi=0, then GOTASK=0,GODELY=IR=R=1 3.1.3 The method: A computer-monitored test The test method applied here is a comparison method. The actual card is compared to a simulated one. In Chapter 2 we have computed a set of tests in terms of input vectors. Each input vector must make a certain sequence of signals appear at the net- work outputs; this sequence must be checked. Since a step-by-step command of the control signal propagation is possible, this sequence is m fact decomposed into several subsequences. ^ subsequence corresponds to the propagation of the control signal through a control point. Our problem is now to check the validity of the subsequence corresponding to each step of the propagation. A subsequence can be defined using a Specified Output Vector, (SOV) and a Dynamic Output Vector (DOV). Specified Output Vector (SOV) When a particular Input Vector (IV) is applied to a card, there exists two sets of output signals: those specified and those which are non-specified. In figure 3.6, we represent the task logic "of a CP. If the IV, (A,B,C,D,E,F) = (1,1,1,0,0,0) is applied and DO = 1, 81* B D E TASK LOGIC £>o^> J DO Ao The value of Y is defined for any input sequence The value of X is not defined for: (A,B,C,D,E,F)»(l,l,l,d,d,d) where "d" means "don't care". However X is defined after the first pulse (DO=l-0-l) The value of X is always defined for: (A,B,C,D,E,F)=(0,d,d,d,d,d) or (l,0,d,d,d,d) or (l,l,0,d,d,d) SOV associated with (A,B,C,D,E,F)-(l,l,l,0,0,0) is (Od 10) SOV associated with (A,B,C,D,E,F)«(0,0,0,0,0,0) is (11 10) Figure 3.6 Task Logic with Specified and Unspecified Outputs 85 it is clear that output X is unspecified. However if (A,B,C,D,E,F) = (0,0,0,0,0,0_) , X is always specified. On the other hand, Y is always specified. Hence, we define a SOV as a 2p-bit vector such that: bit 2k+l=l if line k is specified, = otherwise bit 2k+2=value of line k when specified k =0 ,1,2, . . . ,p-l p= number of output lines Dynamic Output Vector (DOV) A subsequence is defined by a SOV (initial conditions) and by a vector describing the variations of the output lines during the subsequence. These changes can be of four kinds for line m: (1) no change in line m (2) 1 change in line m (3) 2 changes in line m (pulse) (h) more than two changes in line m (malfunction) Thus two bits per line are necessary to code these changes: Yl/m,Y2/m. Yl/m=0 Y2/m=0 in case (l) Yl/m=0 Y2/m=l in case (2) Yl/m=l Y2/m=l in case (3) Yl/m=l Y2/m=0 in case (h) m=l,2,3 , • - • ,p At each step the dynamic behavior of the card is defined by the DOV. Other definitions are necessary for the understanding of what follows : 86 MH-Vector : This vector defines the values assigned to the MH-lines of a card; it says which CP are enabled and which CP are not. Phase : In the test process a phase begins when a new input vector is applied and ends when the next is applied. Subphase: In the test process a subphase begins when a new MH-Vector is applied to the card and ends when the next is applied. A subsequence is checked at every subphase. A phase in- cludes one or many subphases . In the solution proposed, an interface which we shall call the Sequence Tester ( ST), does the following operations: Gets the new IV from the processor and applies it to the card. Compares the actual SOV with the simulated SOV and sends the result to the processor. Gets the new MH-Vector and applies it to the card. Compares the actual DOV with the simulated DOV and sends the result to the processor. These operations are represented in boxes 1 to 8 in figure 3.7. The discontinuities in <^a) and (b) correspond to operations performed by the processor: Act ion (a) ; Diagnostic of the last subphase or table look-up to get the next IV; computation of the next MH-Vector, and the next DOV, coding of information and transmission to the tester. 87 Note: SSOV: Simulated SOV SDOV: Simulated DOV Figure 3.7: Sequence Tester Flow Chart 88 Action (V) : With the previously defined IV, computation of the corresponding SOV. OperationsTaJ and CbJ require the simulation of the card. The control program in figure 3.7 is entirely prewired in the Control Block of the ST. 3.1.U The Sequence Tester hardware The ST acts exactly as a subroutine and hence is called by the processor (call line: ACTDEV). After completion of its task, the ST sets a reply signal (REPLY line). Exchanges of data between the processor and the Sequence Tester are done by means of two registers: the UP register for data going from processor to ST and the DOWN register for data going from ST to processor. The interconnections between these different units are shown in figure 3.8. Some numbers are necessary at this point. The ST must be able to handle a set of two cards at a time, so: maximum number of input lines : hQ maximum number of CP's (or of MH-lines): 12 maximum number of output lines: 2k These numbers determine the size of the different ST units which we must now consider. To introduce each of these units we will follow the requirements of the flow chart of figure 3.7. Box 1 and 2 : Here information is available in the UP register. The UP register is a 60- bit register divided from 89 CALLING SIGNAL CARD UNDER TEST SEQUENCE TESTER 7 r > \ UP1 UP2 UP3 UP4 UP5 00WN1 DOWN 2 DOWN 3 DOWN 4 * a o a NOT USED i - i \ - DOWN 5 DIGITAL PROCESSOR (PDP/8e) REPLY SIGNAL Figure 3.8 Architecture of the System lox 3: Box h: 90 left to right into UP1, UP2, UP3, UPU and UP5 (12 bits each). If UP5 is filled with ones, we enter a new phas w , " ^ f — j | A__ A A_ A A, \ MHREG CTL ■n r INPUT REGISTER A UP DECODER S E Q U E :ctlj OUTPUT REGISTER H &* €h SIGNAL ANALYSER COMPARATOR C E T E S T E ii -0 CONTROL BLOCK (CTL) UPl UP2 UP 3 UP4 UP 5 --> Ui V DOWN 1 DOWN 2 DOWN 3 DOWN 4 NOT USED PDP/8e DOWN 5 Figure 3.9 Tester Organization 95 These logic elements are entirely defined in Chapter k. A general i nterconnection diagram is shown in figure 3.9. 3.2 Programming It is now time to develop the actions fa) and (V) roughly outlined in section 3.1.*+ (see flow chart figure 3.7). 3.2.1 Action fa) Three possibilities can occur at point fa) : The tester must enter a new phase The tester must enter a new subphase The tester must stop and reinitialize itself In all cases a diagnostic of the previous subphase must be done. 3.2.1.1 New Phase A new phase is entered under the following circumstances: At the beginning of a test When the end of the path corresponding to an input vector has been reached. We consider the control signal as traveling through a path in the card. This path (a string of control points) is a function of the input vector. The "new phase" specifications are: (i) Fill UP5 with ones (ii) Put new input vector in UP1, UP2 , UP3, UPU, beginning at the left, (figure 3.10.1) 96 3.2.1.2 New subphase A new subphase is entered if the end of the path corresponding to the present input vector has not been reached. The new subphase specifications are: (i) UP5 = MH- Vector - all bits corresponding to a CP to be enabled are 0; otherwise they are 1. (ii) UP1, UP2, UP3, UPh = simulated DOV (according to code in section 3.1.M Yl = leftmost bit (figure 3.10.10 3.2.1.3 Stop and Initialize This occurs when the test is finished (set of tests exhausted) or, if the operator wishes, when a failure is found. The specification for a stop is: "UP = all zeros" (figure 3.10.6). 3.2.1.U Diagnostic We have mentioned that all the previous operations must follow a diagnostic procedure. This operation is mainly concerned with the contents of D0WN1, D0WN2 , DOWN 3 , DOWNU, D^9', D50. (figures 3.10.3 and 3.10.5) If D50= 0,no diagnostic is necessary (the previous step worked without error) If D50=l, a diagnostic is necessary. If Dl+9 = 0, the failure occurred at the beginning of a phase (after comparison of two SOV's). If DU9=1, the failure occurred during a subphase 97 NEW — r IrfPUT VECTOR ALL ONES UP1 UP2 UP3 (l) PHASE INFORMATION UPU UP 5 T "I r- — — SIMULATED SPECIFIED OUTPUT VECTOR -L- - 1 - - - I NOT USED UP1 UP2 UP3 (2) OUTPUT VERIFICATION UPU UP 5 1 Dl+9 = ACTUAL 1 1 OUTPUTS VECTOR NOT USED DOWN1 D0WN2 DOWN 3 DOWNU II (3) OUTPUT VERIFICATION (RESULT; comparison failed SIMULATED T DYNAMIC OUTPUT VECTOR MH VECTOR UP1 UP2 UP3 {h) SUBPHASE INFORMATION UPU UP5 UU9 _ l ACTUAL DYNAMIC "T" OUTPUT 1 I VECTOR 1 NOT USED DOWN1 D0WN2 DOWN 3 (5) SUBPHASE RESULTS DOWN4 -D50 = 1 if comparison failed ALL ZEROS ALL ZEROS ALL ZEROS ALL ZEROS ALL ZEROS UP1 UP2 UP3 (6) STOP INFORMATION UPU UP5 Figure 3.10 I/O Conventions 98 (after comparison of two DOV's). In both cases, D0WN1, 2,3,*+ gives the actual card response. The failing line can thus be localized easily. 3.2.2 Action (b) At point (b) the specification is(SOV verification): UP1,2,3,U: SOV as defined in section 3.1.U (figure 3.10.2). 3.2.3 The main program The main program provides the following facilities: (1) it is standard for all the cards to test, i.e. composed of a fixed listing which calls a set of card-dependent sub- routines. (2) It halts when a malfunction is found and diagnostic of the failing line (card status, name of failing line, nature of malfunction). Possibility to re-start the test must be provided for the operator through a set of I/O directives. (3) The operator is allowed ^V a set of I /° directives to apply a single input vector of his choice (this can be useful in the debugging process). (h) Different "modes" are possible, for instance, an "automatic" mode which halts only when a failure is found or when the test is finished, and a "step" mode which halts after every subphase (with a complete printout of information about this "step"). The second can be changed to "automatic" at any time. 99 A complete flow chart of the main program is given in figure 3.11. Actions (&J and (bj developed above are easily recognizable. Some explanations concerning our conventions are needed: Box 1 : "Test Specification" (figure 3.12) represents an I/O. At this point the operator must input the parameters concerning (3) and (k) above. ? INPUT = OPERATOR or TABLE (N) This directive concerns (3) . If INPUT=OPERATOR then the operator i s required by a next I/O directive to give the value of the input vector he wants to apply. For example: ?INPVTR = .7777. 7772. 1001. 7622 (octal) If ? INPUT = TABLE(N), then the program takes the value at location N of the table as the input vector to apply. In this case, a next I/O directive defines the mode. For instance: ?M0DE = STEP or AUTOMATIC, refers to (h) above. Another I/O directive exists which later allows the operator to end the process. It indicates whether or not the test must finish. ?FINISH = YES or NO In box 1, FINISH is always NO. Box 5 Box 7: Box 8: 100 "CP-SIMULATION: (figure 3.13) : NXT and INPVTR are the inputs to this subroutine. NXT is a 12 -bit word, the zeros of which represent the CP which are enabled in the present subphase. INPVTR is the input vector. SDOV and NXTI are the outputs of this subroutine. SDOV is the simulated dynamic output vector corresponding to the present subphase (2** x 2 bits). NXTI is a 12 -bit word., the zeros of which represent the CP enabled in "une next subphase . "Table look-up" : In Chapter 2 we have developed a procedure for finding a set of detection tests to apply- to each card. This procedure written in FORTRAN, is run on the IBM 360/75. The table obtained is then inserted as data in the PDP/8e main program. "Output simulation" (figure 3.1^-): This subroutine is called once at the beginning of every phase. This subroutine scans the outputs to determine (l) if they are specified under the present input vector (2) and if yes, what their logical values are. The result is the simulated specified output vector (SSOV). Box 11: 101 Box q, : Takes the actual output vector present in the even bits of D0WN1, 2, 3, k and puts it in storage (0UTVTR). "Test DOWN" (figure 3.15): This subroutine is entered once after a new input vector is applied, then once after each subphase. Its purpose is to give an explicit diagnostic of the step just executed. If D0WN50=1, failure (diagnostic necessary). If D0WN50=0, no failure. A print out of the card status is done if we are in STEP mode, otherwise the pro- gram goes directly to the next operation. In case a printout is done, the possibility is provided for the operator to change the program parameters by two I/O directives. 7FINISH = YES or NO If YES, the test ends. If NO, the test continues. In this case, we need to determine the mode: ?M0DE = STEP or AUTOMATIC 3.3 Advantages and disadvantages of this solution 3.3.1 Disadvantages 3.3.1.1 Long processing Due to the complexity of the boards to be tested, the simulation routines will probably take the major part of the test duration. Input vector search will however be reduced to a minimum by a simple table lookup. 102 "H ■xr-Trn BR "H7 I SPXCinCATIMB L- Actlon O ■otat Th« teata (HVTR) to apply to th« card are picked aequantlally in a Table. (PDP/oe etorage) «8 CALL TMT-DOWI .Diagnostic .Teat Jul End of teat ■ra mra ♦ ixti JSd ■ev Subphaae UP-A11 Zoroa Table Look-dpT UP1,2,3,U * N«v LHVTR aOTeV -TJ" (Call Teater) CALL DE CP-8IMULATI0I : UP1,2,3,1» * SDOV ■xri ■ f(axt, IHVTP) ASttfcV -TJ- ICall Teater) acTTjEV -t-t (Call Teater) Action r 9 REPLY "tT Teater Repl£>22- YES CALL IE OUTPUT SIMUL- ATION UPl.2,3, 1 * ~SS0V NXT1«- 3777 ACTDEV --LT (Call Teater) 'REPLY »"LT\ YES Teater Reply ^Received m GET D0WN1,2,3,U,5 Figure 3.11: Main Program 103 ? INPUT (OPERATOR or TABLE (N))/ YES /operator^ N0 ? MODE Figure 3.12: Test Specifications 101+ UP5 '* NXT Simulate Card and get: -SDOV -NXT1 Figure 3.13: CP Simulation 105 k - In SSOV Bit(2k+l)» 1 YES Compute Logical Vp.lue of OUT, k+1 Take Output Line #(k+l)« OUT, In SSOV Bit(2k+2) = 0UT, YES UP1,2,3,U * SSOV NXT1 «- 3777 In SSOV Bit(2k+1)= Figure 3.1J+: Output Simulation 106 Compare DOWNl.2,3, 1 * and SDOV NO * DU9"0 YES Compare D0WN1,2,3,U and SSOV Print Out Diagnostic ? MODE (STEP or AUTO) NO D50-0 DU9-0 NO Print Out DOWNl.2,3,1* and SDOV YES YES YES ? FINISH = (YES or NO) NO FINISH YES jf STEP >v "S. MODE /~ NO Print Out DOWNl.2,3, 1 * and SSOV Figure 3.15: Test-DOWN Routine 107 3.3.1.2 Big interconnection matrix No mention has been made of the way in which the card to test and the ST are interconnected. In our case this has been realized in a simple way by a big "pinboard" type matrix (100 x 100 pins). The solution which makes the connections under program control has been abandoned for reasons of economy. 3.3.2 Advantages 3.3.2.1 Simpler Signal Analyser Each of the n output lines is coded during each CP delay. We are not interested in the relative position of the signal changes during this delay; therefore, we only need n independent similar output coders which are simple to design. In this way, we can test the n output lines simultaneously. The whole card is verified in only one pass of program. 3.3.2.2 Versatility We can subject a control card to a few critical tests before using the Automatic mode. This enables the operator to screen out some of the more common defects. When a failure is found, he can momentarily stop the automatic testing sequence to "jump" to some fault diagnostic sequence in order to localize the fault, and then return to the automatic sequence. The versatility of this tester is such that testing of entirely combinational circuits as well as asynchronous sequential circuits is possible. The upper limit in the 108 number of inputs (kQ) and in the number of outputs (2k), permits us to think also about using this tester for the checking of entire wired sections of the computer. 109 h. SEQUENCE TESTER: logical design U.l Sequence Analyser i+.l.l Requirements During each subphase, the Signal Analyser (SA) is in charge of giving a coded image of the different types of variations which occur at the card output lines (DOV). It is composed of 2k similar asynchronous sequential units; each unit receives input from: the output of the card the output register and control. Control lines are provided in order either to clear the SA or to enable the SA (beginning of a subphase). The codes for the DOV are: 00 : no change 01 : 1 change 11 : 2 changes (pulse) 10 : more than 2 changes U.1.2 Realization The SA is built in two parts serially connected. Each stage of it is a U-state asynchronous sequential circuit which produces two outputs Yl and Y2 according to the state diagram in figure U.l.a. The flow chart and excitation tables for an R-S flip flop implement- ation are shown in figure 4.1.b and U.l.c respectively. Two remarks must be made. (1) The system needs to be cleared at the beginning of each subphase to go back to the initial state 00. This is done by the signal CLSA from the Control Block. (2) We can easily see that such a unit produces the desired coding only if the input is initially zero. The SA Initializator 110 (SAI) assumes this function. When the card output is at the beginning of a subphase, the SAI simply connects this c to the input of the SA. In the other case, it complements the signal before connecting. This can be done easily by storing the values of the card outputs in the 0UTREG at the beginning of each sub- phase and then by using this information to gate appropriately the card output to the SA. An EXCLUSIVE-OR gate is used for this purpose, as shown in figure k.2. a. Note that the contents of 0UTREG is constant during a subphase. We must consider carefully the speed of the circuitry in building the SA. We have estimated the minimum length of the worst pulse (or spike) to detect : 10 - 15 ns. The circuit must be fast enough to react for such a narrow perturbation. This leads us to forget about using classical flip flops (too slow). Instead, we build our flip flops out of the new "Schottky-clamped TTL IC's" which provide delay time of about 3 ns for a 2-input NAND. A close look at the delays introduced by the different ways of implementing the SA (figure k.2. a and k.2.h) leads to the con- clusion that solution 1 (k.2. a) must be chosen which will allow the detection of pulses down to about 6 ns (theoretically). The SAI must also be sensitive to such narrow pulses. The EXCLUSIVE-OR 7*+86N with a delay time of 12 ns is fast enough. The total design of one unit of the SA is shown in figure U. 3. k.2 Output Register U.2.1 Requirements The output register (0UTREG) receives information from three sources : Ill (a) State Diagram for SA Stage X yly2 1 00 © 01 01 11 ©> 1 1 co 10 10 © © yly2 1 00 1- 1- 01 0- 1- 1 I -1 -1 10 -1 -1 X yly2 1 00 1- 0- 01 -1 -1 1 1 -1 -0 10 1 - 1- Y1Y2 SjRt S2 R2 s r x - y 2 H x -1 S 2 =x„ yi R 2 =x.y 1 [b) Flow Table and Excitation Table for SA INITIALLY (c) NAND Implementation of SA Figure k.l Signal Analyser Logic Design 112 R — ! — ^T7n\ x ' . i ""S. OUT — H13> ; SI Rl 01 oi Yl — yT S A I S2 A2 02 02 1 \ r4_> Yl 77 Y2 Y2 Propagation delay = d = 3 ns (Schottky Cl.TTL Logic) a mini = 2 d = 6 ns (mini pulse) b mini = h d = 12 ns (a) First SA Configuration (chosen) R OUT $^-> Yl Yl Y2 Y2 *4+i a mini = 3 d = 9 ns (mini pulse) b mini = 3 d = 9 ns (b) Second SA Configuration (not chosen i Figured. 2 Two SA Configurations 113 74S04 Ri > — \ OUTi> — 1 1— ►Yl/i CLSA Figure U. 3 Signal Analyser for Bit # i Ill* (1) The card outputs (line 0UT k): the value of which must be gated into the ^UTREG when the control signal G(ZSUT-R occurs. (2) The UP register (lines UPi/j and UPi/j+l): If UPi/j = 1, the value in line UPi/j+l must be gated into the 0UTREG when the control signal GUP-R occurs (i=l,2,3,l*; j=l,3,5,...,ll). (3) The signal analyser (SA)(lines Yl/k and Y2/k): the value stored in bit k of the 0UTREG must be changed if Yl/k.Y2/k = 1 when the control signal GSA-R occurs. 1*.2.2 Realization This circuit is composed of 2U similar sequential units. To eliminate the hazards caused by feedback lines, we have chosen a J-K Master Slave flip-flop as storage unit for each bit of the register. We use it as a trigger by setting J=K=1 and making the occurence or the non-occurence of the clock pulse a function of all the inputs and Ri (True output of the OUTREG bit #i). Under these conditions a pulse should occur when Ri is supposed to change. This word dictates the use of EXCLUSIVE-OR gates to detect whether or not Ri and the data line have different values. The complete drawing of the circuit associated to one bit of 0UTREG is shown in figure k.k. h, 3 Comparator U.3.1 Requirements The comparator will be asked to compare either two 2^-bit words (RI, R2, .o,R2l+ and dUTl, $UT2 ,. . . ,(Z5UT2U) or two U8-bit words (Yl/1, Y2/1, Yl/2,...,Y2/2l* and UPl/1, UPl/2 , . . . ,UPl/l2 , UP2/1, 115 OUTk^ GOUT-R^ UPi/j^ UPi/jM^ GUP-R^ Yl/k> GSA-R> ;j©> 7486 7400 7410 7410 7410 * Rk *Rk J + I2(i - 1) = k Figure U.U One Stage of OUTREG 116 UP2/2,.. . ,UPU/12). The first pair will be compared when the signal COMPREG occurs, and the second pair at the occurence of Control Signal C0MPSA-, U. 3. 2 Realization The TTL MSI SN 7UL85 from Texas Instrument is able to compare two 1*- bit words. Twelve of these chips are serially connected in order to realize the comparison of U8 bits at a time. The general drawing of the COMPARATOR appears in figure h.;'>. k.k START line, CC line, enable lines, input register INPREG (figure U.6) The START line sets the memory element of the first control point of the card. The signal START is a pulse produced by the control. The CC line is used to clear all the control points of a card before execution of a test. The enable signals are produced by the same control signal (MH) gated to the different MHi of the card according to the state of the register UP5 (MH-vector): MHi = MH.UPi/5 The input register stores the values of the card inputs at the beginning of each phase and keeps it during the whole phase. The IITFK5G consists of U8 latches receiving data from UP1, UP2, UP3, UPh and gated by the control signal GUP-IN. Texas Instruments SN7V75 latches are used for the INPREG. k.5 The DOWN Logic (figure U.T) The DOWN register is part of the interface and receives in- formation from the Sequence Tester. The DOWN register is a 60-bit ( 5 x 12 bits) register composed of 15 quadruple latches (T I SN7^75). It consists of five 12-bit registers (D0WN1, D0WN2 , D0WN3, DOWNU, D0WN5): 117 Yl/1> ( IF A«B) COMPSA> Figure 4*5 The Comparator 118 MH >■ UP5/1 >■ UP5/2 >■ 02)0 \1*M .►— X -i 7402 -► MH1 -► MH2 UP5/12 > i i J 7402yO ■* MH12 nni /i > ^ D C SN7475N Q Url/1 - > I I P 1 / o ***, D C SN7475N Q < UP4/12> GUP-IN > * ► INI ► IN2 ► IN48 Figure ^.6 MH and Input Registers 119 D0WN1, D0WN2, DOWN 3 , DOWNU: receive information from (i) the Card outputs when the control signal G0UT-DWN occurs (ii) the Signal Analyser when the control signal GSA-DWNb occurs. The two leftmost bits of D0WN5 (dU9 and D50) are used by the tester to communicate the results of the comparisons it executes to the processor. These two bits can be used by the main program to diagnose the malfunction of the card. The following code is used: D50 = 1 : malfunction D50 = : no failure DU9 = : specified output vector comparison D^9 = 1 : dynamic output vector comparison Bits 51 to 60 are not used. U.6 The UP decoder At two different points in the Control Block prewired program the register UP must be checked. UP register can be in any one of the three different states: (1) UP all zeros (2) UP5 all ones (3) UP mixed These three states can be coded using two variables. The chosen code is: (1) UPSETO = UPSET1 = (2) UPSETO = 1 UPSET1 = 1 (3) UPSETO = 1 UPSET1 = 120 7404 Yl/1> 0UT1 > Yl/2 > Yl/24> 0UT24> Y2/24> GSA-DWN> *■ GOUT-DWN> ► DOWN 1/1 ► DOWN 1/2 ► DOWN 4/tl ► DOWN 4/12 Figure ^«7 DOWN Register Input Logic 121 UP5/1> UP5/12> UP1/1 > UP4/12> UPTEST > -►UPSET1 ► UPSETO Figure U.8 UP Decoder : Principle 122 UPSETO and UPSET1 are outputs of two memory elements. A general net- work is shown in figure U.8. A 12-input AND and a 60-input OR are used to test the values of the 60 UP bits and the 12 UP5 bits. U.T Matrix The matrix provides communications between the card and the tester, i.e. between card pins and - the input register (kQ lines) - the Maintenance Halt lines (12 lines) - the GODELY, GOTASK, CC , and START lines (k lines) - the Card 0UTPUTS {2k lines) - the power (2 lines : ground, +6v) - complement lines (8): Sometimes complements of input lines must be available for some other inputs. This matrix is approximately 100 x 100 pins (10,000 cross points). A logical matrix, monitored from the PDP8/e has been abandoned since it would require considerably more hardware and consequently would greatly increase the cost of the tester. Furthermore, connections between card and tester are done only once at the beginning of the test; accordingly such expense would not be justified. Instead, a manual "pinboard" type matrix is chosen. 123 Mat: rix pin partition We consider the matrix as The columns : Col. Name Signal CI C1P1 C2 C1P2 C3 C1P3 Ck G1PU C5 C1P5 C6 cip6 CT C1P7 C8 C1P8 C9 C1P9 CIO C1P10 Cll C1P11 C12 C1P12 C13 C1P13 ClU ClPlU C15 C1P15 ci6 C1P16 C17 C1P17 ci8 C1P18 C19 C1P19 C20 C1P20 C21 C1P21 C22 C1P22 composed of 100 rows and 96 columns, Col. Name Signal C23 C1PA C2U C1PB C25 C1PC C26 C1PD C27 C1PE C28 C1PF C29 C1PH C30 C1PJ C31 C1PK C32 C1PL C33 C1PM C3i+ C1PN C35 C1PP C36 C1PR C37 C1PS C38 C1PT C39 C1PU cUo C1PV Cl+1 C1PW CU2 C1PX cl+3 C1PY cU4 C1PZ Ci Pj means Card i , pin j 12U Col Name Signal Col. Name Signal Col. Name Signal Ci+5 C2P1 C67 C2PA C89 Kl Cl+6 C2P2 C68 C2PB C90 K2 Ci+7 C2P3 C69 C2PC C91 K3 CU8 C2PU CTO C2PD C92 YLk Cl+9 C2P5 CTi C2PE C93 K5 C50 C2P6 CT2 C2PF C9k k6 C51 C2PT CT3 C2PH C95 K7 C52 C2P8 C7H C2PJ C96 K8 C53 C2P9 C75 C2PK C5*+ C2P10 C7o C2PL C55 C2P11 C7T C2PM C% C2P12 C78 C2PN C57 C2P13 C79 C2PP C58 C2P1U C80 C2PR C59 C2P15 C8l C2PS C60 C2P16 C82 C2PT c6i C2P1T C83 C2PU C62 C2P18 C81+ C2PV C63 C2P19 C85 C2PW C6U C2P20 C86 C2PX C65 C2P21 C87 C2PY C66 C2P22 C88 C2PZ Ki : input to inverter #i The rows 125 Row Name Signal Row Name Signal Row Name Signal LI iki L25 IN25 Ll+9 Kl L2 IN2 L26 IN26 L50 K2 L3 IN 3 L27 IN27 L51 K3 Lk ink L28 IN28 L52 KIT L5 IN 5 L29 IN29 L53 K5 L6 in6 L30 IN30 L5l+ K6 L7 IN 7 L31 IN31 L55 K7 L8 IN 8 L32 IN32 L56 K8 L9 IN9 L33 IN33 L57 MH1 L10 INIO L3^ IN31+ L58 MH2 Lll IN 11 L35 IN35 L59 MH3 L12 IN12 L36 IN36 L60 MHl+ L13 IN13 L3T IN37 L6l MH5 Lilt INlU L38 IN38 L62 MH6 L15 IN15 L39 IN39 L63 MH7 Ll6 IN16 Ll+0 inUo L61+ MH8 LIT IN17 Ll+1 inUi L65 MH9 L18 IN18 Ll+2 IN 1+2 L66 MH10 L19 IN 19 Ll+3 INl+3 L67 MH11 L20 IN20 iM IN 1+1+ L68 MH12 L21 IN21 IN22 IN23 Ll+5 IN 1+5 IN 1+6 IN 1+7 L69 L70 L71 GOTASK L22 GODELY L23 START L2U IN2U Ll+8 IN 1+8 L72 L73 L71+ +6 VOLT Ground INi Ki MHi input tf i output of inverter # i Maintenance halt # i 126 Row Name Signal L75 0UT1 LT6 0UT2 LTT 0UT3 LT8 0UTU LT9 0UT5 L80 0UTb L8l 0UT7 L82 0UT8 L83 0UT9 L8I4 0UT1O L35 0UT11 L86 0UT12 L87 0UT13 L88 $unu L89 0UT15 L90 0UT16 L91 0UT17 L92 0UT18 L93 0UT19 L9U 0UT2O L95 0UT21 L96 0UT22 L97 0UT23 L98 0UT2U L99 Blank Line 0UTi = Card output #i 127 4.8 The Control Block I*. 8.1 Flow chart The flow chart implemented by the Control Block (figure 3.7) can be divided into 2 subsequences (A and B). Flow charts of these 2 subsequences can be found in figures 4.9 and 4,10. 4.8.2 Realization (figures 4.11 and 4.12) Each BOX has a number. This number refers to the actual CP implementation. A task (box) having #i is executed by the Control Point #i. One Control Point (CBll) needs some explanation. The DO signal attached to this CP is the signal which enables the control points of the card to test: it enables a one-step advance of the control signal through the card under test. After this signal is sent, one needs to wait until the end of the propagation. Thir, time can be variable in a wide range (40 ns to 2700 ns for one CP). It is a function of the number of CP enabled or/and the duration of the timing stages of the CP's under test. We could therefore choose a minimum delay time and attach the corresponding capacitor to CBll. This solution would cause the circuit to react too slowly in any case. Instead a variable capacitor (0 4 3000 fF) will be connected to the timing stage of CBll. Before use of the tester, one will have to set this capacitor to the proper value (the longest delay in a card). The signal INIT comes from a manual switch. It produces the initialization of the Control Block. 128 Initialize INITIAL =_n_ Gate Card Output OlITREG and ..Reply REPLY = -LT Update OUTREG According to UP1,2,3,1* GUP-R = ~l_T Compare OUTREG to Card Output COMPREG = _TL Clear All CP's Gate UP1,2,3, L tp INPREG CC = ~U ~ SuT-TN = ~LT D50 = 1 DU9 = YES D50 Dl*9 Gate Card Out- put to DOWJJ1, 2, 3, U, Prime First Aggregate Figure ^.9: Subsequence A : Flow Chart Gate Card OUT to OUTREG Enable SA GOUT- R « IT ENSA ■ a Clear SA CLSA -_n_ Ji3 Enable CP's MH = 1 GOTASK = 1 GODELY = ht WAIT FOR PROPAGATION [lib Disenable CP's MH = GOTASK = GODELY = 1 lie WAIT FOR PROPAGATION Disenable SA Update OUTREG according to SA Content ENSA = 1 GSA-R = ~U~ fjj Compare SA and DOWNl.2,3, k COMPSA =ir 129 r Same ? NO> COMPOUT=0 ^ YES 1 ' \ I D50 = 1 Dl+9 = 1 [E D50 = DU9 = 1 (Hb" \ ' Gate SA to D0WN1,2,3,U J =~LT |lUc "GSA-DWl ' ' Reply = ~LT REPLY 1 F Figure' U.10: Subsequence B: Flow Chart 130 131 m a. B u K 1 9 If < < i ■ i I II 1 1 ■ 1 ■ i 14 1 14 1 £ 8 18 = 1 18 »> M »? I« u la 1 o 1 a IS i«l_ * 18 lit 1 8 1 8 1 4 IS u. 18 M. a • a - U a o u la la 1 i is ut__ 1 5p8 is| 1 i g % 18 « i - O o la o 1 i IS i-L_ 1 ( a 18 ° o ii ■ i i IS ■L. ctA n \ a y a i. 5 I = -1 A" ™ " 1 8 18 IL (J o> (J la . i. i i 7 ST&l I~! i, . i i i i i •H w I— |0 la la la 2 i» a la 132 9 Signal Catalogue U.9.1 Tester Signals OUTi (i=l, . .. ,2k) , OUTi Ri (i=l, ...,2k) Card output tied to matrix pin L(i+75) (and complement) OUTREG bit # i (and complement) INi (i=l, ... ,U8), INi UPj/i - UPj7i DOWNj/i - DOWNj/i Di+9, D50 (DOWN 5/1.DOWN5/2 respectively) Yj/i, Yj7i (j=l,2,i=l,...,2U) MHi (i=l, ... , 12) GOTASK GODELY COMP0UT UPSETO UPSET1 INPREG bit # i (and complement) UP subregister # j, bit # i ( and complement ) Input to DOWN subregister # j , flip-flop # i (and complement) Input to DOWN subregister #5 flip-flops 01 and 2 Signal Analyser unit # i, output Yj (and complement) Maintenance Halt # i (for CP-MH control logic) General enable signal (for CP-GO control logic) General enable signal (for CO-GO control logic) Output of COMPARATOR (= if compared words are the same) UP decoder output # UP decoder output # 1 133 U.9.2 Control Block Signals CLSA G0UT-R GSA-R GUP-R COMPSA COMPREG, COMPREG G0UT-DVW GDWN GUP-IN MH=GOTASK=GODELY START CC UPTEST ACTDEV REPLY ENSA INIT INITIAL CALLb REPLYb GOUT-Rb GSA-DWNb Mi i=l to 15 Clear Signal Analyser Gate card outputs to 0UTREG Update 0UTREG according to content of SA Update 0UTREG according to content of UPl 9 2 9 3 9 k Compare SA output to UPl^^, 1 * register Compare 0UTREG to card outputs Gate card output to DOWN register Gate DOWN register Gate UPl^^, 1 ! to INPREG General enable signal for CP-MH and CP-GO logic Set pulse of the first CP in the board Clear all the CP of the board Enable UP decoder Signal by which the tester is called by the PDP/8. Starting signal for subsequence A Signal by which the tester transfers control to the PDP/8 Enable Signal Analyser Manual signal to initialize the Control Block (boot strapping) Initializator signal Starting signal for subsequence B Reply of subsequence B G0UT-R for subsequence B GSA-DWN for subsequence B Maintenance halt for the Control Block CP's 5. CONCLUSION It has been shown that pseudo-asynchronous control systems can be designed using a standard building block called a control point. The conversion from the flowchart notation to the actual machine appears to follow a definite set of rules. Since it is beyond the scope of this thesis this conversion has not been emphasized but it is believed that the study realized in Chapter 1, could be further developed for an algorithmic solution of the design problem. The test generation method proposed takes advantage of the structure of the Control Point Network to reduce the problem to finding tests for smaller circuits. Although it is not new, this process had not been used before for testing this kind of system. Programs and results are given for test of an example drawn from practice. The way in which input patterns are applied to the card and responses are analyzed deeply depends on the facilities available. In our case two points have greatly influenced our solution: (l) the possibility offered by our design for following the propagation of the control signal through the card "step-by-step" (2) the opportunity we had to use a minir-computer to control the operation. The Sequence Tester was initially conceived to test any control card using the control point technique. However, it is now thought that it could be used as well (together with the mini- computer) for the checkout of entire wired sub-units of the machine. 13U 135 APPENDIX A: A REVIEW OF TEST GENERATION PROCEDURES 136 A REVIEW OF TEST GENERATION PROCEDURES 1. Path sensitization : the D-algorithm In this method, given a fault, we want to "sensitize" the output to the faulty line, i.e. we want, "by applying a particular input to the network to make: output = faulty line or output = faulty line The example in figure A. 1.1 shows a h input, 1 output circuit with 9 lines and 3 gates. Eighteen single faults are possible and each of them needs the execution of the following process. Consider fault (3 - 0). Forward trace : From line 3 to the output we sensitize a path "by the following operation: 7 = h + 3 make k = logical so 7 = 3 9 = 7.8 make 8 = logical 1 so 9 = 7 = 3 Backward trace : We must now express the values in lines 3, k 9 8 in terms of inputs a, b, c, d, e 3 = logical 1 is necessary to test for (3 -.0) As 3 = 1.2, we can make 1 = logical and 2 = don't care i.e. a = 1, b = don't care h = logical line c = line k = 8 = logical 1, as 8 = 5 + 6, we can make 5=1 and 6 = don't care so 8 = 1. Therefore the input vector (a, b, c, d, e) = (0, d, 0, 1, d) tests the fault (3 - 0_) . .More and more sophisticated algorithms are being found to accomplish the "sensitizing process". The basic one is the D-Algorithm [7]. The advantage of this method is that it will find a test for all the 137 faults in the general case. However, the algorithm has to go through all the possible faults in the circuit and generate a test for each of them. This process can be very long for certain particularly tricky faults for which multiple path sensitization is necessary [12]. 2. Indistinguishability classes + D-algorithm : The previous method can be associated with a method which first reduces the number of faults to test. This method is developed in [9]. For the single fault assumption it can be explained as follows: Figure A. 1.2 represents a 2 input NAND gate. Its 6 possible single faults are represented by two dots associated with each line; the upper one rep- resents the stuck«at-l fault and the lower one represents the stuck-at-0 fault. We have already developed the notion of indistinguishability between faults. For this NAND gate: A test for (l - 0) is a test for (3 - l) and (2 - 0). Dots (l - 0), (2-0), (3 - l) are tied by a solid line (1st stage indistinguishability class ) . A test for (l - l) is a test for (3-0) but r.he opposite is not true, Dots (l - l) and (3 - 0) are tied by a broken line with an arrow indicating the direction of the above implication. Same for (2 - l) and (3 - 0). Classes (2 - 1, 3 - 0) and (l - 1, 3 - 0) are called 2nd stage indistin- guishability classes. In the first stage indistinguishability classes, the indistinguish- ability property is reflexive whereas in the second stage indistinguish- ability classes it is not. 138 As a result only 3 tests (instead of 6) are necessary: one test for each class i.e. (1) a test for (l - 0) (2) a test for (l - l) (3) a test for (2 - 1) A similar study can be made for any kind of gate, then for an entire network. Figure A. 1.2 shows the indistinguishability classes for the example in figure 2.A.I. We can show for instance that a test for (1 - 1) is a test for (8-0): since (l - l) M3 - 0) and (3 _ o) M7 - 0), (1 - 1) »»(7 - 0), since (7 - )««-*( 9 - 0) <4-+ (8-0), (1 - 1)^-^(8 - 0) which we must test. In this way we can reduce the number of faults which we must test. In this case the necessary tests are: (1) a test for (l - l) (2) a test for (2 - l) (3) a test for (1+ - 0) (U) a test for (5 - 0) (5) a test for (6 - 0) (6) a test for (l - 0) (7) a test for (5 - l) Only 7 runs of the D-algorithm are necessary (instead of 18). 3. Boolean difference: This method is based on a paper by Akers [13] and F. F. Sellers, et.al. [15]. The boolean difference on a function F(x.. ,x~, . . . ,x ) with 1* 2' ' n respect to the variable x. is defined as being: 139 f = dF = F(x , x ,... ,x ,...., x )0F(x x , . .. ,x. ,.,. ,x ) i = F(x l5 x 2 ,..., 1, ..., x n ) F(x , x ,..., 0,...,x ) = i 1' x 2'***' x i-l' x i+l' •••» X n' where © is the EXCLUSIVE-OR operation. For some particular values of X = (ic, , x_,...,x. _ 9 i. J _,...i ) f. may 1 2' 1-1 l+l n l be one-valued. Let us consider such a case. If f\ = 1, F(x 1} x 2 ,... ,x iS ... ,x n ) ^ F(x 19 x 2 ,. .. ,x i5 ... ,;■: ) i.e. F is only a function of x. like F = x. or F = x.. l li In other words, the output is "sensitized" to line x. with the input pattern A — IX.. , X„ j . . . , X i_T_ ' X i+1'***' X n * Thus, this method applies the path sensitizing method but determines the input values by simply solving the boolean equation (to test for (x. -b) ): 'dF = 1 dx. l x. = b (1) in terms of input values. The advantage of this method is that it gives a solution in all cases (even in case of multiple path sensitizing) but it is time con- suming because if n is the number of lines in the net, we need to compute and then solve 2n systems like (l). This method has been improved recently by the introduction of the concept of partial boolean difference [15]. k-. Random generation: This stochastic method is very general and needs only a network simulator; on the other hand, it can appear to be very inefficient for detecting some faults ( see ref. [l6]). Input vectors (i.e. sequences of 1 and at the input of the net) are determined randomly. For each one, 2n + 1 simulations are done, 2n being the number of possible faults in the network. By fault insertion in the simulating routine, a list of the faults detected by the present input vector can be set up. In this way a table is built: the fault table . This table contains one row per test (or input vector) and one column per fault. If fault detection only is needed, the process stops when all columns are covered at least once. If fault location is needed, more rows are necessary to assume the fault location requirements (see [5] pp 67-81). In the case of fault detection, the table may afterward be reduced. Methods for such a reduction have been developed in switching theory. McClusky method for reducing prime implicant tables may be used if the table is small [l8]. Otherwise, the star-method developed by Michalski [19] and which guarantees to find quasi-minimal cover can be applied. 5. Exhaustive generation : In the case of very small circuits (number of output less than 6), one can apply all possible input patterns to the network and simply verify the output. This method guarantees the detection of all detectable faults (single and multiple). The only need here is a simulator to give the fault free network output. lUi *3-0 3 Figure A. 1.1 Example Figure A. 1.2 NAND Gate and Associated Indistinguishability Classes 1-indistinguishable : [(l-0)(2-0)(3-l)][(3-l)(U-l)(7-l)] [(5-D(6-l)(8-l)][(7-0)(8-0)(9-0)] 2-indistinguishable : 9 [(l-lW3-0)][(2-lh(3-0)] [(3-0WT-0)][ [(U-o)-(7-o)][(5-o)-(8-o)] [ (6-o W 8-o)] [(7-lW9-l)]t(8-lM9-l)] Reduced fault set (detection) ; (l-l) (l-O) (2-1) (U-0) (3-0) (6-0 ) Figure A. 1.3 Indistinguishability Classes for Example A. 1.1 1U2 APPENDIX B: CPTEST LISTING 1U3 FoKjKAN IV 6 LEVEL 18 COUNTR DATE * 71123 uJj! SUBROUTINE C0UNTR IF (IJ) 80*80,70 ww i. O 70 DO 90 JC=1,IJ WWX 7 90 C(JC)=. FALSE. ww i. b GO TO 80 wwj.9 50 CONTINUE WW.-G F=l. WW t 1 80 RETURN WW*, c END CPTEST Listing: Subroutine COUNTR 1UU C^iUnAM U t, LtVcL 18 ASSIR DATE * 71 ] 2-» |o/f [)IMENSIONAU12,32,2<»),AO(12.32,2*),rm8<.,2,CO(3P4,;>'..),r:(;><,) ».,»<. COMMON C,I I/AR1/KK.APAR/AR2/AI.AO — -J EQUIVALENCE I A I , C I ) , ( AO, CO) ...o IFIAPAR) GO TO 10 w- / IF ( Bl.EO.O) GO TO 30 — «a CI (I I,Rl)*C(l) -«-*» C0< I 1.R1 J*.TRUF. v-*u IF IR2.EQ.CI GO TO 30 j.tl CIU l,B2)=C<2) ,W4 -J4* COI I I ,R61 = .TP.UF. — *j IF 1 B7. EO.O I GO TO 30 ^..o 1.1 II I ,B7)=CI7) -j..f COI I I ,R7) = .T0UF. — ..« IF ( RP.FO.O) GO TO 30 -j.J Cim»B8)«C(8l -»-•. COI I I,8R)a.TPUE. -v>i GO TO 30 .»-.*< 13 IF ( Bl.E'J.O) GO TO 30 ..-iJ AI IKK, I I ,P.l )=C| 1 ) w.*.>«i AU( .> AUKK, I I ,R? )*C.i2) -jj'/ AOIKK.I ! ,B2) = .T«UE. -jjc IF (B3.F0.ei GO TO 3C «JV A1IKK.I I,B3 )=C(3I ■/-".- AOIKK, I I ,d3 l = .TKUE. "ti IF (B4.EQ.C ) GO TO 30 -w*4. AI I KK,I I ,84 ) =CI4) --.-♦J) AOIKK, I I ,PA) = .TRUE. ***** IF (R5.E0.0) GO TO 30 ^ts AI (KK.I I ,85>=CI5) --■»t AlJlKK, II ,B5 ) = .TRUE. --/•» / IF I B6.=0.ri ) GO TO 3"? — <*0 AUKK, I I ,B6)=C(6) --•»* AOI KK, I I ,BM=.TRl)F. — 30 IF ( B7. FQ.C) GO TO 30 -w-»l AUKK, I I ,B7)=CI7» --->«: AJIKK, I I ,R7 )=.TRUE. vi^pjj IF (BP.FQ.O) GO TO 30 „>,.><, A1IKK.I I ,B8)=CI B) > AdfKK, I I ,BR )= .TRUE. ^;t, 10 RETURN jjj 7 ENO CPTEST Listing: Subroutine ASSIG 1U5 r„n.lnA<\ Iv V, LEVEL I d MAIN DATE = 71123 l<>/3<>/4? ;,*«*« ..■»«•*. «*-..*-**maiN**«**«-*******************PROGRAM******»»» *•***««•** .„.,i IMPLICIT L0GICAL*1< A-DI , INTEGER! l-Z) „....<. DIMENSION ACHECKI 12,32), APREI 12 , 32, 1 2 ) , A INP I 1 2 , 32, 24 ) , A3C ( 1 2 , 3? , 24 G) ,ASUC( 12,32,12) .^j DIMENSION BCHECK1200) , B I NP ( 200, 24 ) ,BOC( 200,20 ,BSUC( 200,12) ,BPBEI' H00.12) „„..•. DIMENSION R124) ,PR< 12) ,S(12) ,N( 12) ,TASK( 12) ,SFNSI24) „„„:j DIMENSION C.PRE(384,12 ),C JNP1384, 241.C0C I 384,?4),CCHECK( 3P4 I „»j.j EQUIVALENCE (APRE.CPREI , (CINP.AINP) , (AOCCOCI .-w / DIMENSION COUNT (24) »w »o COMMON COUNT, I/AR1/K, AP/AR2/AINP.A0C -,<*■» INTEGER ONE/' 1 • / , ZERO/ • ' / , POINT/' .' / «„*.. DATA N/ I, 3, 3, 1,0, 0,2,0/, TASK/0,0 ,5,3,5,l,0,3/,K>1AX/8/,SENS/.' , 4- '. •/ H, StRI AL /O/ L^«»» «*****» ****i**fMO DECLARATIONS**********************************"'**'' L ,.* **«»-<**» *.*»**«.**rt = r,IN INIT I Al I ZAT [ON OF A-T ABLE* 1 ***** 1 ********' ■■ -«* ► * .. ti DU 2 K*1,KMAX ..... NK=2**N(K) ....-• 00 2 1 = ! ,NK »«*=• DO 3 .1*1,1? .v.i APRE (K, I , J I = . FALSE. . ,4. i A SUC ( K, I , J ! =.FAt SF. ... / AP*t (K, I ,< l=.T*UE . ..t-. OJ 2 J^l ,74 ..*■ A INP ( *. I . J ) = . FALSE. .... i AOCIK.I , J) =. FALSE. ^ »•«,»,.«***** »**« *»r\jn INITIALIZATION OF A-TAPL F **«*****«-"'*'•-**''-*•*' «* L «« «»■*■* ♦*««••**• ***^t-GIN SEQUENCE SPC IP I CAT IONS** *****♦*"-* *-<■ *♦* ***** . **«« .„.l AP=.TPIJC. ».#«.. FlAGM. .....> K=0 ...,.-. 4 K = K+1 .^wJ 1-0 „„..~ IFIK.FQ. (KMAX+1 > ) GO TO 134 „j«. 7 IF (N(K).EO.O) GO TO 7 „.,..< b IF (NIK ). E3.0) GO TO 4 >,.<. 7 LALL CflUNTRIFL AG.NIK) ) ^ji IF ( FL4'j .EQ.l. ) GO TO 4 «;i GO TO f>, .^j.- 7 1=1*1 ...>.> a GO TO ( 14, 24, 34,44, S4, 64, 74, 84, 94, 104,1 14,124) ,K L SPECIFICATIONS FLYBACK ROUTINE -oj-. 14 LALL ASSIGI 1?, 0,0, 0,0,0, 0,01 ,^3 ......ASUCIK, UZ1=AINP(K, 1,15 1 „w^<.. GU TO 6 — j/ 2<. CALL »SSIGI4,S f A,P,f», 0,0,0) .^j< ASUC1K, I ,3)=AINPIK, 1,6) »jj'/ ASUC(K,I,6)=.NJT.AINP(K,I,6).AN0.AINP(K,I,4).ANI').AINP1K,I,-) „.y»c A SUC 1 ", I ,7 ) = .NOT.AINP(K, I , 6 ) . AND. .NOT. ( A I NP ( K , I , 4 ) . AND. A I M°l K , I , S ) H) .^-,1 GJ TC 6 ^-.^ 34 i-ALl ASSIGI 5, 16, 17,0,0,0,0,0 wv*J ASUC (K. I ,4 ) =A INPIK, I, 1 7 I .AND. .NO T . 1 A INP 1 K , I , 5 ) .ANO. A INPI K , 1 , 1 6) I CPTEST Listing: Main 1U6 r^lKAN IV G LEVEL 18 MAIN DATE - 711?3 l'/i"/*? mw4<) GO TO 6 „„•»:> <>4 CALL ASSIGI 14, 0,0,0, 0,0,0,0.) vwto ASUCIK, I ,5)»AINP(K, 1,1*1 .^•♦7 GJ TO 6 „w«e 5« ASUCIK, 1 ,8 )*.T»UE. ,„<»S) GJ TO 6 „ji. 6* ASUC (K, I ,7)».TRUE. ,vji GU TO 6 .vj, 7* CALL ASSir,(12,lJtO,0,0,0,0,r> w,,^ ASUCIK,1,8)*AINP IK, 1,121 .AND.AINPfK, 1,13) .,.,.<•. GJ TO 6 ^-o o<. CUNTINUF -j^. GJ TO 6 ,*j1 44 CONTINUE wv-.a 1CK lGN t INUF «;V 114 CONTINUE - JU u W. CUNTINUF l END SPECIFICATIONS FLYBACK ROUTINE , -»»«.««*«•*****«» ***fno SEQUENCE SPEC IF IC AT IONS *♦»•** *♦•*»*****«#• • « •»■:*-•-• L ««*»»-■.*»♦»** ■»****occ,j^ OUTPUT A- Tip |E *»**•«**»**»« • ♦***•«*♦*»»» »< «**«♦*«• »voi 1J-. WKITECi,«s) SFRIAL v..j« rtKITF(b,05) -..»,.- W«ITF(ft,?SI ..^ t)ll 71 K=1,KMAX **„:■ NK=->*«N(K) ,-^u DJ 71 1=1, NK .^u/ DO 68 J=l, 1 2 „„«,t; IF ( APRt (K , t, J ) ) PR(JI=ONE ,v»-. IF ( .NOT.APRFIK, 1,1 I ) PRIJI=ZEPO „„/,. IF ( ASUC (K, I , J) ) SIJl'ONE „»/i oH IF ( .NO' .ASUCIK, I ,.M I S(J)«ZERO j.,/ t DO 6') Jsl,?4 „wO IF (MNP(K,I,J1) R(J)=ONE j*/* I c I ,N3T.A!NP(K f I, J.) \ R(J)=ZEP0 „*/■; b4 ]" ( .NDT.AnCIK.I , J) ) R(JI = POINT -vWc 71 wRlTE(6.?5)((PR(J),J=l,12l,(R(J),J=l,24),(S(JI,J=l,12)l C «*»*«**«***■** ****«F NO OUTPUT A- TAPLE********** ******************' «*•*♦***-*-• C «»»** «**«*•* **««««qc(;jm CONC ATE NAT I ON* ****•♦* *•*♦*****« • '****##**<****»♦•* „u// NK=2**N(1) „„/w DO I 1 01 1 = 1, NK „u/-> rtCHECM I )=. FALSE. — o: 00 2l r J=l,?4 „-«i BINPU , J) = AINP( 1, I , J) _-j^ ^10 rtUCI I ,J)=ArX. ( 1 ,1 ,J) -»oJ 00 UC1 J= 1 , 1 2 wot tiPRF ( I , JI=APRr(l , I , J) «i„o3 1101 BSUC ( I, J ) = ASUC( 1,1 , J) ^./uu P = NK w»o7 DO 410 IB=1,P -«oa 00 410 KA=2,KMAX -jo-7 NK=2**N(KA) ^j'jc DU 410 IA=1,NK «v*i DO 51C JA=1 ,12 CPTEST Listing: Main (contd) ll+T « w"»t %J ji; J w'JH J ^■7 5 w *) to - w»/ - JIO v J> 1 - 1* w r-wisfKrtN Jv l. LnVbL 18 MAIN DATE = 71123 1 9/3Q/^2 IF ( .NOT.APREI KA, IA, JA) ) GO TO 510 IF IBSIJC1 IB, JA) ) GO TO 510 GO TO MO MO CUNTINUF UO MC JAM,2 DO «10 JAM.l? u.w? t*r i RF(D,jA) = BPRE(!B,JA).OR.APRE(KA,IA,JA) -.-j fa SUC (P, J A) =BSUC( IB, JA) .OR. ASUCIKA.IA, JA I ~*wV IF ( .NOT .BS'JC (P, JA) ) GO TO BIO -.1. hSUC (P, J A) =.N()T.BSUC ( » , J A) .ANO. .NOT. APR F[ KA,IA,JA).OR.BSUC(P,JA).A JND.APRF (KA, I A, JA) ^ll i HiUC (P, JAI = .NOT.BSUC (P.JA) -.1^ MJ CuNTIMJ c ..i j b^HhO ( IR)^ .TRUF. -n.-, MJ CuNTIMJF ^^*«»»»«***»»***«**f:fvjQ £ qnCATENATIUN***************** *■***********♦■'*"'* ''*'" l_ ^«*a *»********#« -*****b£q im MERGING OF B-T ABL t ***********»** + *** ** * "■•*\ + ■> ^.i ■ NK = o ».i., 00 1?G IBM.P „../ IF ( aCHPTK, ( I «) ) GO TO ^20 ...*.. NK.-NK.+ 1 -.<.'. 0') 930 J8= I ,2 1 W R ! T F ( 6 , 2 5 ) vxj^ DO IK IH = !,NK ,.jj DO 11"? JB=1,?4 uijt IF ( BJNPI IB, JB) ) R(JB)=ONE -ij3 IF ( .NOT.B INPI IB, JB) ) R(JB)=ZERO u»jfc 1100 IF ( .NOT .BOC( IB, JBI ) R(JB) = POINT ^ul 00 12^0 JR=l,12 L.UC IF I BPRE( I R, JB) ) PR(JB)=ONE CPTEST Listing: Main (contd) 11*8 (■unlKAiM lv G LtVEL 18 MAIN DATE * 71123 19/39/4? * 4J s 1200 IF ( .NOT.BPREI IB,JB) ) PRIJ8)»ZERO , t n wRITE<6,45l((PR(JB),JB*l,12),IRIJB),JB-1.24),IB,P) wiii ^10 CONTINUE C***«*****»*******«fN0 OUTPUT OF B-TA8LE****»********«********»»" ►*»• »*-• C *« «..**»«*<«« »»«*«begIN C-TABLE INITIAL I Z AT ION***** *•♦****«*« »•*«■••**••• witi NK = 11) OU 17 K=1,KMAX Its IF 1 TASK(K) .EQ.O) GO TO 17 .1) IA«NK*1 .16 NK=2**TASK(K) it* NK=NK+I A-l «. 1 1) DO 1? I=IA,NK »•*>> CCHFCKI I )=. FALSE. 4 -<»- 00 13 J»l, 12 1 J 1 U CPRFII, J)=. FALSE. 4 V . CPRF ( I ,K)=.TRUE. 4 J 1 00 12 J=l,24 1. J 1 CINPI I , J>=. FALSE. . ^ > COCI I ,J) = .FUS6. . -» 12 CONT INUF 4J * 1 7 CONTINUE L ,«.„,....i(.*.i.»FND C-TABLE INITIALI ZAT I ON* *** ** ** * »*****«•*♦***♦*«•♦ L •***»**•***< -*****hfgi«4 TASK SPFTIFICAT I ON ************ **■••«*•»•» «*►♦»#•;.** jijc AP=.FALSF. ■ tj-i FLAG-!. ,»v>- K=0 .tg, 1=0 *»w. IV ",-K + l -i.o.1 IFIK.FO. (KMAX*1) ) r.O TT 213* .u'. IF ( TASKIK ) .FQ.O) GD TO 19 „ iU rj lo CALL COUNTRI FLAG, TASKIK ) I wi^o IF (FLAG.NE.l.l GD TO 18 j».W 1=1-1 „iUo G.J TO 19 .u-i Id GJ Tn ( ?14,224, 234, 244,254, 26*, 274, 284,294, 2104,2114, 2124) , K. C TASK SPFCIFICATIONS w/u 214 CJNTINUF ^../l GO TO lb -W* ^24 CONTINUE -i / J GD TO 16 **/«• 234 CALL ASSIGI 1,2,3, 7, 8,0,0,0) »i/3 GD TO 1ft -i/c 244 CALL A S S IG ( 1 , 2 , 3 ,0 , , 0, ,1 1 w.// GU Til 16 wu/o 234 CALL ASSIG ( I ,2 ,3, 7,8, 0,0,0 ) j,/-< GO TD lft w.oc ^b-. CALL ASS IG(2, 0,0,0, 0,0,0,0) ,iol GO TO 1ft ,io t 274 CON T INUE gioj GO TO 16 u io'. 284 CALL ASSIGI 9 , 1 0, 1 1 , C, 0, ,0 ,0 ) ,/»ot> GO TO 1ft wioo 294 CDNTINUF CPTEST Listing: Main (contd) li+9 f^lKAN iv G LEVEL 18 MAIN DATE = 71123 19/39M? wio/ 210i» CONTINUE .ion 2114 CONTINUE »io 2124 CONTINUE C******-***********END TASK LOGIC SPEC IF I C AT I ON** ************** *****•*» *** C**»***************0UTPUT C -TABLE** ***************************** *"'***** -!•»». 2134 WRITEI6.125) SERIAL -..vi HRITF(6,95) wi7<: WRITEI6.25) - a »j I C= I *i*-t DO 0270 1=1, IC -..»:> 00 02S0 J = l ,24 - t ^t> IF (CINP(I.JI) R(J)=0NE -i»7 IF { .NOT.CINPI I, J) ) R(J)=ZERO ».« 0280 IF I .NOT.COCU ,J) ) R(J) = P0INT ^*v 00 0290 J=l,12 -<...i. IF (CPREII.JI) PR(J) = ONE -^^l 0290 IF I .NOT.CPREI I , J) ) PR(J)=ZERO ..<.-* WRITE(6,45)((PRIJ),J=1.12>, ww-J 0270 CUNTINUE (,***<<-»*****•*******•£ no C- TABLE OUTPUT*********************** *»« «»*- > *•* C*»«*»*****»*******M C RGING OF 8 AND C- TABLE S************ 1 1 **-*♦*«***»■* * -,<.*.<. QC = IC u^ w 3 Q ii = I B -two Q=QC+l -<.„/ QF=Q j.jt DO 3C0 J=l,l2 -4^ 0300 CPREIC, J>=BPRE(QB,J> «^*U DO 0310 J=l ,24 u<.il COCtO, J)=B0C(QB,J> w^i^ 03I0 CINPIO, J)=BINP(QB, J) „<. A -> DO 0320 IC = l,0C wi A 4 DO 0330 J=l ,12 w««.i3 IF (CPRE(ICJ) ) GO TO 0340 u<.io 0330 CONTINUE j t iJ u340 DO O350 1=0, QF u ao IF < .NOT.CPREI I , J) ) GO TO 0350 -«.!■» DO 0360 JJ=1,24 j^u IF I .NOT. (COCI I ,JJ) .AND.COCI IC, JJ) ) ) GO TO 0360 uctl IF (C INP( I , J J ) .AND.CINPI I C, J J). OR. . NOT.CINP ( I , J J ) . AND. .NOT .C I MP ( IC H,JJ) ) GO TQ 0360 - t <.2 GO TO 0350 ^..^3 0360 CONTINUE w, „<:<: 1 GO TO 0320 ^<.c 0350 CUNTINUE u tt V DO 03B0 IBB=1,0B ^j^ IB=QB-IBB*1 ^jl IF ( .NOT.BPREI IB, J) ) GO TO 0380 ~<.it DO 0390 JJ = 1 ,24 vcjo IF I .NOT.ICOCI ICJJ) .ANO.BOCIIB, JJ) ) ) GO TO 039"* -<..»•♦ IF(BINP(IR,JJ) .AND.CINPI ICJJ) .OR . .NOT.BINPI IB, JJ) .AND. .NOT.CINPI CPTEST Listing: Main (contd). 150 l-jrvfuAN IV G LEVEL 18 MAIN DATE * 71123 19/'=/42 HICJJ) ) GO TO 0390 *<..>!> GO TO 03H0 u.« 0390 CUNTINUE »ij7 yF=QF+l w ^jb 00 0400 jj=l ,12 ^.,9 0400 CPRE IQF, JJ )»BPRE( 1B.JJI Wt -»u 00 2*10 JJ«1,24 ^„ CINP (OF, JJ>*BINPI IB. J J) . OR.CINPI IC.JJI ** + i 2410 COCIQF, JJI=BOr( 1B.JJ I .UR.COCI IC.JJ) ,.u GO TO 0320 j.t^ 0380 CONTINUE Jt ii 0320 CONTINUE 0*»******»»****«***ENO MERGING OF B AND C -TABLE********** ***"»*•*•**»♦ »• C »»«,*»»«**********9 EG IM OUTPUT OF TASK TEST TABL E******« »**«»*»*»••••♦ » *4to MRITEI6.11SI SERIAL *,*.*? ^RITFI6,95) wite *RITE(6,?5) -..•.<> NK=0 mcj- DO 042^ I = y,OF .ujl NK=NK*1 „.. j. 10 0430 J=l ,12 ,-jj IF irPREII.JM PR(J) = ONE *„.,«. u <,30 IF ( .NOT.CPKEI IfJH PR(J)=ZERO .^) 00 0440 J*l,?4 rt ;o II- (CINP( I , J) ) R( JI=ONE u^/ IF I .NOT.C INPI I i J) I RIJI'ZERO wt jo u440 II I .NOT.CnCI I ,J) ) R ) ,NK ) 04<;0 CUNT1NUE (_■»<••«»*****<< ******END OUTPUT UF TASK TEST TABLE ***»**♦*•■***** g "'*•♦** » l** ********* *-*+****? R M A T S**' ♦********♦**•****-•**••***'»* *»" *«'»* " 13 FiJRMATdH ,15X,7H TEST* , I ?, 5X , 2 4A3 , I 1 0) 25 PURMATdH ,24H 12 3 4 5 6 7 8 9 10 1 U 2, 3X , 72M 1 2 3 4 S fe 7 H 8 9 in ii i 2 n !<, 15 if, it 18 19 2" 21 22 23 2a.3X.24H I 2 "» 4 H 3 6 7 3 9101112/1 33 FORMATION , 1 2 A2 , 4X , 2 4A3 , 2 X , 1 2 A2 ) 43 F0RMATI2H , 1 2 A2 , 4X , 24A 3 , 2 I 10 ) 33 FGRMAT(2H ,40 X , 20HSE NS I T I Z ING VECTOR :/) 03 FURMAT(1H ,29X,24A3/» 7 3 FORMAT! 12L 1 , 2X , 24L I , 2 X, 24L 1 , 2X , L 1 ) d5 FURMATI lHl .40X.24H A-TABLE FOR CARD « ,11^1 93 FORMATd" , <»0X , 23H1 " . » MFANS OHNT C ARE I /9 X , 1 2HPRE [JECFS 5rHS , 37 X , 1 H3HINPUT V ECTOR, 39X, 1 OH SUCCESSORS/) 105 FORMATI 1H1 ,40X,24H B-TABL^ FOR CARD « , 1 10 , 2 3H( S PQUPNC r LC1SIC H TFST I ) 115 FORMATI 1H1 ,40X,24H C-TABLE FOP CARD « • I 1? , 1 7H( TASK LO'-.y T^ST H) ) 125 FORMAT ( 1H1 ,40X,24H C-TABLE FOR CARD * ,110) STO° END »<- j *<. ^ 1 c W <- OJ ^ 4_ LJ *« Jt «■> 3 ««. o *<, u / «<- Ou -«- uV -C /v; ^ /I uc / t •>£ 1 1 WC 74 CPTEST Listing: Main (end) 151 REFERENCES [l] C. A. Petri, "Kommunikation mit Automaten," Schriften des Reinish-West filischen Inst. Instrumental Math., and der Universitat Bonn, Nr.2., Bonn 1962. [2] A. W. Holt, R. M. Shapiro, H. Saint, and S. Warshall, "Final Report for the Information System Theory Project," Applied Data Research, Inc., ADR ref. 6608, February, 1968. [3] S. S. Patil, "Coordination of Asynchronous Events," M.I.T., MAC.TR 72, June, 1970. [h] R. G. Martin, "Standardization of Control Point Realization," Report No. ^00 , Department of Computer Science, University of Illinois, May, 1970. [5] H. Y. Chang, E. Manning, and G. Metze, "Fault Diagnosis of Digital Systems," Wiley-Interscience, 1970. [6] D. B. Armstrong, "On Finding a Nearly Minimal Set of Fault Detection Tests for Combinational Logic Nets," IEEE Trans, on Elec. Comp. , Vol. EC 15 No. 1, pp. 66-73, February, 1966. [7] J. P. Roth, "Diagnosis of Automata Failures: a calculus and a method," IBM Journal, pp. 278-291, July, 1966. [8] C. Durante, J. Erceau, and J. P. Richard, "Sur la Detection des Pannes dans le Ensembles Logiques," LAAS du CNRS Toulouse, France, 1970. [9] D. R. Shertz, "On the Representation of Digital Faults," Report R4l8, Coordinated Science Laboratory, University of Illinois, 1969. [10] J. P. Hayes, "A Study of Digital Network Structure and Its Relation to Fault Diagnosis," Report RU67 , Coordinated Science Laboratory, University of Illinois, May, 1970. [ll] R. D. Schertz, and G. Metze, "On the Indistinguishability of Faults in Digital Systems," Proc. of the 6th Annual Allerton Conferences on Circuits and System Theory, pp. 752-760, October, 1968. [12] G. C. Goldbogen et al. , "Implementation and Extension of Multi-dimensional Pathsensitizing in a Simulation and Diagnostic System," Proc. of the 7th Annual Allerton Conferences on Circuits and System Theory, pp. 28i+-293, October, 1969. [13] J. B. Akers, "On a Theory of Boolean Functions," Journal Soc. Indust. Appl. Math, Vol. 17, No. h , pp. 1+87-^98, December, 1959. [lU] F. F. Sellers, M. Y. Hsiao, and L. W. Bearnson, "Analysing Errors with the Boolean Difference," IEEE Trans, on Elect. Comp. Vol. EC IT, pp. 676-683, July, 1 152 [15] P. N. Marinos , "Derivation of Minimal Complete Sets of Test-input Sequences Using Boolean Differences," IEEE Trans, on Elect. Comp. Vol. C20, No. 1, pp. 25-32, January, 1971. [l6] V. Moreno, "A Logic Test Generation System Using A Parallel Simulator," Illiac IV Report, Department of Computer Science, University of Illinois, January, 1971 (in publication) . [17] R. Borovec, and C. Rey, "A Description of the Illiac III Printed Circuits Testing Facilities," Illiac III Report, Department of Computer Science, University of Illinois, (to be published 1971). [18] E. J. McCluskey, "Introduction to the Theory of Switching Circuits," McGraw-Hill, New York, I965. [19] R. S. Michalski, "Automatic Synthesis of Quasi-minimal Multiple Output Switching Circuits," VI International Symposium on Information Pro- cessing, Yugoslavia, Bled, September, 1970 (FCIP70). [20] H. M. Wagner, "Principles of Management Science with Applications to Executive Decisions," Prentice-Hall, 1970. Form AEC-427 16/68) AECM 3201 U.S. ATOMIC ENERGY COMMISSION UNIVERSITY-TYPE CONTRACTOR'S RECOMMENDATION FOR DISPOSITION OF SCIENTIF C AND TECHNICAL DOCUMENT ( See Instructions on Reverse Side ) 1. AEC REPORT NO. REPORT No. ^50 COO-2118-0009 2. TITLE CONTROL POINT STRATEGY AND ITS AUTOMATED DIAGNOSIS 3. TYPE OF DOCUMENT (Check one): [3 a. Scientific and technical report I I b. Conference paper not to be published in a journal: Title of conference Date of conference Exact location of conference _ Sponsoring organization Qc. Other (Specify) 4. RECOMMENDED ANNOUNCEMENT AND DISTRIBUTION (Check one): 6 a. AEC's normal announcement and distribution procedures may be followed. ~2 b. Make available only within AEC and to AEC contractors and other U.S. Government agencies and their contractors. [] c. Make no announcement or distrubution. 5. REASON FOR RECOMMENDED RESTRICTIONS: 6. SUBMITTED BY: NAME AND POSITION (Please print or type) Christian A. Rey Research Assistant Organization Department of Computer Science University of Illinois Uroana, Illinois Signature Date May 2k 9 1971 FOR AEC USE ONLY 7. AEC CONTRACT ADMINISTRATOR'S COMMENTS, IF ANY, ON ABOVE ANNOUNCEMENT AND DISTRIBUTION RECOMMENDATION: PATENT CLEARANCE: I I a. AEC patent clearance has been granted by responsible AEC patent group. b. Report has been sent to responsible AEC patent group for clearance. 1 I c. Patent clearance not required. JUL 2 1 197 1