''r'' h ^ If/^ rV" • t ^ * i L*?>-'. 'A' If . •* ?^;/ i*** 'j ■iifA '7f < • • LIBRARY OF THE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN 510.84 no. 100-110 cop. 3 14 V DIGITAL COMPUTER LABORATORY UNIVERSITY OF ILLINOIS URBANA, ILLINOIS REPORT NO, XOh A METHOD FOR FACTORING THE ACTION OF ASYNCHRONOUS CIRCUITS by W. D. Frazer and Do E, Muller Presented at the AIEE Fall General Meeting Chicago, Illinois, October 12, I96O. This work was supported in part by the Office of Naval Research under Contract Nonr-193^(27)- November 2, I96O A METHOD FOR FACTORING THE ACTION OF ASYNCHRONOUS CIRCUITS W. D. Frazer D. E. Muller In this paper we shall discuss a procedure vhich enahles one to analyze and trace the behavior of asynchronous circuits -while testing certain properties of this behavior. Although methods for performing this type of analysis have been devised and used in the past^ they have differed from the method described here in an important respect (l)o In the present procedure information concerning the "topology" or interconnection structure of the circuit is used to simplify the analysis, while in earlier procedures this information was not used. Let a circuit C be defined by a set of Boolean equations ^i " ^i^^i^ ^2/ °°°^ ^n^ ^2 ~ PI' ^2' o o » ; z^; » z' = f (z, , z^, .. ., z ) n n^ 1' 2 ' n' Each variable z. represents a signal or measurable binary quantity in the cir- cuit, and each function f describes a logical element or gate in the circuit. J Typical elements represented by such functions are the familiar AND, OR, and NOT elements of computer logic. The dependent variables z! are called t^e implied signals and represent the signal values toward which the given signals z. are made to tend by the circuit logic. While each function f . is written as though it is a function of all n of the variables z,, it is usually an explicit function of just a few of these n variables. The remaining variables which do not influence the functional value f . may be optionally included, or not among the arg\ainents in any fonnal description of the circuit. It is precisely the information concerning explicit dependence which is used in the present analysis procedure. To specify this explicit dependence, an n x n connection matrix, M, is con- structed. Any given matrix element m . is made equal to 1 if the function f . depends explicitly on z and is made equal to otherwise. Thus, if f . repre- sents a two input AND element, m. . will, be made equal to 1 if and only if node 1 is one of the two inputs to this element. An n-tuple a = (a_, a > ..., a ) of specific values of the variables z , z , „„., z is called a state o.f the circuit. Therefore specifying the state of the circuit is equivalent to specifying the n signals in the circuit. With the passage of time the circuit will pass through a sequence of states - 2 - a(l), a(2), ..., a(k), ... In an asynchronous or unclocked circuit, the state sequence, in general, does not depend only on the initial state a(l) and the logical properties of the cir- cuit as described by the Boolean functions f .. The state sequence also depends upon the relative speeds of the logical elements making up the circuit. Nevertheless, a knowledge of the circuit logic permits one to determine a class of state sequences, called allowed sequences, such that the actual state sequence must be a member of this class. Specifically, one considers sequences in which each consecutive pair of states a(k), a(k + l) bear either the relation- ship a.(k + l) = a,(k) or a.(k + l) = a.'(k) for each i = 1, 2, ..., n. Here a.'(k) is taken as the functional value f.(a (k), ap(k), ,.., a (k)). Whenever al(k) = a.(k), the i'th node is said to be in equilibrium and the value of a.(k + l) is unambiguous. However, when al(k) 7^ a.(k) the i'th node is said to be excited and a.(k + l) may assume either value; which value it actually assumes depends upon the speed of the i'th element relative to the other elements of the circuit. One object of the analysis procedure is to determine whether or not the the circuit is speed independent in the sense that all allowed sequences starting with the given initial state a(l) either terminate in the same state or same cycle of states. While a complete determination is not made, the stronger pro- perty of semi -modularity is checked. This property, also defined with respect to the initial state a(l), is satisfied if and only if for each consecutive pair of states a(k), a(k + l) in each allowed sequence starting with a(l) and for each node i we have a.'(k) = al(k + l) whenever al(k) ^ a.(k) = a.(k + l). Thus, a circuit is semi -modular with respect to a(l) if no element in the circuit may pass from an excited to an equilibrium condition unless its signal changes. To check semi -modularity each of the Boolean functions a!!(k) = f .(a, (k), a (k), ..., a (k)) is computed for each given state a(k). This functional value a'. (k) is then compared with a.(k), the corresponding signal value to determine J J whether they differ indicating that the element is excited. The state a(k + l) is now formed from a(k) by changing the signal upon one of the excited nodes, say node i. Semi -modularity may be checked with respect to this transition by recomputing the functional values so as to form a'(k + l), and making certain that no nodes which were excited in state a(k) have passed to equilibrium in state a(k + l) save node i, the node which underwent the change. I It is important to notice, at this point that only functions f . which are J known to depend explicitly upon the variable z. need be checked during the transition described above. The other functions will not be affected and hence need not be checked, or even recomputedo Similarly, many state transitions a(k) to a(k + 1) need not be formed at all, for if all arguments of functions f . J depending explicitly on z. had assumed the same values during some previously checked transition, the calculation need not be repeated. Thus, by using the information concerning explicit dependence as provided in the matrix M it is possible to avoid construction of many superfluous states and transitions. Semi -modularity is checked whenever signal changes in two change paths occur on nodes i and ,1 such that some function f exists which explicitly depends upon both z. and z. or such that either f. depends explicitly upon z. or f. depends explicitly upon z.. This testing is done whenever the two J J change paths in question represent node changes which may be taking place concurrently. Determination of the explicit dependence described above is accomplished by use of the connection matrix M. For each change path form a vector v of O's and I's by the rule: v. = 1 if node i undergoes a change in some transition a(k) to a(k + l) in the change path in question, and v. = otherwise. Let vM represent the vector whose ,i'th component is .Z^ v.m. ., where Boolean union i=liij' is used in the summation. It may therefore be seen that the j'th component of vM has the value 1 if and only if there is some node i, undergoing a change in the change path from which v was formed and such that f . depends explicitly upon rp J the corresponding variable z.. Similarly, let v M M represent the vector whose J'th component is .Z., Z, v.m. m. , Then the j'th component of v M M is 1 "^ ^ 1=1 r=l 1 ir jr "^ ^ if and only if there is function f which depends explicitly upon both z.,z. for some node i undergoing a change in the change path. Thus, a systematic scheme for determining whether or not it is necessary to carry out a semi -modularity check may be formed by constructing the vectors v, T vM, and v M M for each change path. In the proposed analysis procedure, change sequences are constructed according to the following rules: a) In each state transition, a(k) to a(k +1), just one node i undergoes a change. UNIVERSITY Of ILLINOIS L!B'"i(7v -^- "b) This node is chosen as one not excited in the previous state a(k -1), (all nodes are considered to be relaxed in the state which precedes the initial state) and one which has not changed during an earlier part of the sequence, c) Beginning with the initial state, change sequences are formed according to rules (a) and (h) beginning with each, in turn, of the initially excited nodes. These sequences are terminated as outlined in rules (d) - (k) , For each change sequence, an n-component vector V is recorded; V has the property that v. = 1 if node i has changed in the sequence and v. = otherwise. d) A test for semi-modularity is made for each transition. e) After a change is made on a particular node k, in a change sequence C, a vector P is formed such that p, = 1 and p. = for all ± J k, T K 1 The scalar V M M P (where V is formed as above) is formed for each, in turn, of the existing previous change sequences, and for the preceding part of C . T f) If V M M P = for all of the existing V, P is added to the V for C and another node to relax is chosen according to (b) „ T g) If V M M P = 1 for V corresponding to some sequence D, the terminal state of D is retained, but D is retraced up to its interaction with C giving D-|, an abbreviated version of D. A terminal state is formed by combining the terminal states of D, and C. h) If at any point in the construction of a change sequence more than one new node becomes excited as a direct result of a given change, terminate the sequence. i) When any change sequence is terminated, the terminal state of that sequence and the V for that sequence are kept. j) When all sequences originating from the given initial state have been pursued and all interaction tests completed, the Initial state is discarded and the change sequence terminal states are treated as initial states. - 5 - EXAMPLE Illustration of the Topological Technique Consider the following circuit Equations z' = z. zl = z. Z4 = ^1 ^2 V ^1 ^3 ^ ^2 ^3 Zi' = z. Z' = Z- M = 1 o" 1 1 1 1 1 1 Initial State : 111 y 6 = Analysis in which All States are Generated (0 1 1 1) 3 (00011) 1+ (0 1) (10 l) (l 0) l) Excited Nodes Underlined 2) Numbers Indicate Changing Nodes 5 (00010) (0 0) ,(0 10 10) \ / (01000) 2 \ /I (110 0)' I ^ (l 1 1 0) (11110) (1110 1) '/ \' /' \" / (01110) (l 1 1 1 1) (01111) (1011 1) (1 1 1) / (0 1 1 1) (Cycling) /* 7 - EXAMPLE 111 3 1 1 1st sequence 1 V^ = 1 1 terminal state 10 1 1st sequence V = 1 1 terminal state 10 1 V = 1 Pseudo-initial state j discard old initial state 5 a 1 10 10 h 10 1 110 1110 1110 1 10 10 1 10 111 I 1 111 (Cycling ) 2nd sequence r terminal state V = 1 1 \ V M MP = 1 Retrace sequence No. 1 V = 1 1 1 1 Pseudo-initial state; ] discard old terminal (^states fV = 1 1 Pseudo-initial state; I discard old pseudo- \^initial state 2nd sequence {Terminal state V^ =^0 1 1 V,MM P = 1 retrace sequence No. 1 V = 1 1 1 1 Pseudo-initial state; discard old terminal state CONCLUSION The procedures outlined above and illustrated in the example lend themselves to use with high speed digital computers. A program for ILLIAC^ the University of Illinois digital computer which performs analysis by generating all allowed sequences has been in use for some three years. It has been found to be too inefficient for use in large circuits. The procedure described in this paper should be most advantageous in just such cases. One may gain some insight into the saving by considering the following example: Given two entirely independent circuits of m and n nodes, respectively, previous analysis requires the generation of, roughly 2 states, while the topological method would require the generation of some number of states greater than m + n and less than 2 +2 depending upon how complex the two circuits were, The case worked out in the example illustrates in a crude fashion the way in which such savings come about. Even in a circuit as simple as this one, it is necessary to generate only about 3/^ as many states as would be generated by the old method. The method proposed here is currently being implemented in the form of a program for ILLIAC . REFEP.ENCES 1. "An Illiac Program for Simulating the Behavior of Asynchronous Logical Circuits and Detecting Undesirable Race Conditions," W. S. Bartky and D. E. Muller (presented at the National Meeting of A.C. M., June, 195?) Digital Computer Laboratory File No, 221. wmmmM^i ,^ ^o' >iW6Vj:t??.'< o.!5*^''''