Symbolic-Timing-Equation Generation from a High-Level Specification of Interface Behavior* Ajay J. Daga, William P. Birmingham Abstract We present a scheme for the generation of symbolic timing equations that establish the temporal relationship between arbitrary events on an interface transaction. We discuss a representation for the temporal and sequencing aspects of interface behavior, using causal event graphs and state-transition graphs, that is amenable to the equation-generation task. We present algorithms used to traverse these graphs to establish the temporal relation of events with respect to the start of an interface transaction. We also present an algorithm used to establish the temporal relation between any arbitrary event pair. 1. Introduction The sequencing and temporal aspects of an interface transaction for a component1 are typically specified through timing diagrams and state diagrams [1, 2]. It is desirable to automatically generate the symbolic timing relation between arbitrary events on an interface transaction. This is useful to support manual and automated synthesis,,a^t tling,-verification tasks. For example, high-levelsynthesis tools need to consider compoqeflide^ ays relatiVe to a critical path to aid the part-selection task [3]. Symbolic equations, whichr.ae generated'from:,high-level specification of interface behavior, may be input to linear proih1ming totolto aid sue1c-ynthesis decisions. Likewise, timing verifiers need to consider path delas, Ajplicqt' lke;'ties;t.hed to establish the temporal relation between arbitrary events that do notc;^q~l. have a $pecliacd',elation. In this paper, we describe an algorilii tihi gfi en*tn.g.ni: diagr mn and state diagram, will generate a symbolic equation between arbitrary &etSvert0 i1leQ a7' ay: ftifng-verification tools [4, 5, 6, 7] use timing equations internally, none of htes to.:,proVilq 4 qiOtns to the user. We do not focus on the manipulation or solution of symbolf'lxuatiions,' f thefi transformation from one form to another, but instead on their automati0 eZnaIion irqm.a high-level specification of interface behavior. The paper is organized as follows. Section 2 briefly characterizes interface behavior. Section 3 discusses our representation schemes for temporal and sequencing aspects of interface behavior. Section 4 presents the algorithms used to traverse a causal-event-graph. Section 5 outlines the algorithm used to traverse a state-transition graph. Section 6 discusses the technique used to generate timing equations between an arbitrary event pair and Section 7 summarizes this paper. 2. Interface Behavior The interface behavior of a device is defined by a collection of bus cycles that describe how a device communicates with its environment. A bus cycle may be synchronous or asynchronous, master or slave [8]. A bus cycle is composed of a sequence of bus states. Bus states define subactivities of a bus cycle, i.e., signal activity on a set of interface ports for a portion of the bus cycle. This research was supported by Digital Equipment Corporation and the National Science Foundation grant MIPS-905781. All views expressed here are those of the authors, and not necessarily those of the funding agencies. 1Component is used in a general sense, indicating a VLSI device (e.g., a microprocessor), or a cell in an ASIC cell library. 1

A sequence of bus states that form a complete bus cycle is called a transaction path for the bus cycle. A read bus cycle for the Motorola MC68020, for example, consists of bus states SO, SI, S2, S3, S4 and S5 [9]. Taken in that order, these bus states represent a transaction path for the read cycle. A bus cycle may have multiple transaction paths. We assume that asynchronous cycles, such as a fullyinterlocked handshake [8], have a single transaction path. The temporal information associated with signal activity during a bus cycle is typically documented using timing diagrams. If a bus cycle has a single transaction path, then a timing diagram completely specifies the sequencing of events for a given cycle. These diagrams do not, however, convey other non-temporal information needed for a complete interface specification, such as conditional information associated with a bus cycle. Conditional information is required, in the event of multiple transaction paths, to specify transaction paths as a function of signal values. Thus, in addition to timing diagrams, state diagrams are required to specify sequencing aspects of interface behavior. 3. Representation of Temporal and Sequencing Information 3.1 Causal Event Graphs A typical timing diagram, captured using the tool Xwave [10], specifying the read bus cycle for the Motorola MC68020 [10], is shown in Figure 3.1. The labels SO through S5 associated with the phases of the CLK signal, referred to as a sequencing signal, represent different bus states of the read cycle. A sequencing signal is one that sequences a cyqle th'ough its different bus states. A representation of temporal iPformation that suppoprts the equation-generation task is a causal event graph (CEG). An event graph;is a directed acyclic graph (DAG) whose nodes, E = {el, e2...,en} represent events, and arcs, A =' {tnl t2,t mj }, represent timinig links between pairs of events. A timing link, tl, is represented by a directed arc frofm efrmto.e to An event graph essentially encapsulates the timing behavior of a bus cycle with logic levels abstracted avay. While there are two types of tilinig, ig'hks shown on a timing diagram, causal and constraint [10], for the purpose of equation generation they are-both treated and represented identically (constraint links are represented as causal links). This assumes thati'nput events will occur at times consistent with specified timing constraints. Hence'wj refer to: tis:representation as a CEG. Note, in general, the time of occurrence of an input event cannot be anticipated, and therefore, the need to represent causal and constraint links differently [10]. The CEG for the timing diagram of Figure 3.1 is shown in Figure 3.2. Events on a sequencing signal are referred to as sequencing events. The representation of a sequencing signal is such that each sequencing event ei is associated with a bus state si, the state entered by an interface when the event ei occurs. For example, CLKrj, a sequencing event, is associated with state SO in Figure 3.1. The undirected CEG is connected and has a single component. A CEG that has more than one component manifests an incompletely specified timing diagram. It is the connected property of a CEG that allows the temporal relation of an arbitrary event pair to be established. A CEG has a set of events that serve as temporal reference points for other events. These events are referred to as reference events. Reference events are cut-vertices of the undirected CEG. There are two important properties with regard to the reference events on a CEG: * If there is no state diagram associated with a bus cycle, then there is exactly one reference event, the start event eS. The start event is the first event to occur in a bus cycle and is specified by a user. 2

* When a bus cycle has multiple transaction paths, and consequently a state diagram is specified, then the number of reference events is the number of sequencing events with an out-degree greater than one. The events rooted at a sequencing event ei occur when the device enters the bus state si associated with ei. S0 l R 0 tQ 4 _ B TI —)T o 1 S ilS[ ___ Figure 3.1: An example timing diagram. ~~T6 ~ ~ ~T 1 T 7A 4T T4 Til - T12A-i T18 T47A T21 fi -T10 rl T47A DS[- -- T47AT2 FirT47 32 --- x-147- C Figure 3.2: An example CEtiming diagram. Y-r^ VfKSl f2(^U33

3.2. State-Transition Graphs State diagrams are captured using the tool Xstate [10]. Every state diagram has a single start state, so, one or more final states and transitions between states. Each state transition is labeled with the sequencing event at which the transition is made. In addition, if sequencing between states is dependent on the logic levels sensed at input signals then a conditional expression is used to specify this sequencing information. For the purpose of equation generation, conditional expressions may be omitted from a state diagram, and a non-deterministic state diagram specified (Figure 5.1). A state diagram specifying sequencing aspects for the read cycle of the MC68020 is shown in Figure 3.3. The sequencing signal is CLK. A state diagram is represented as a state-transition graph, that essentially has the same structure as the diagram. R P: Request Pending 1: DSACKO=1 & DSACK1=1 CLK r)& not R_P 2 DSACKO=O or DSACK1=0 CLK(r) B&l n 1 s3: HALT=1 & BUSERR = 1 ELK(r) #' 4: HALT=O & BUS_ERR=O S 0CLK( f) S CLKr) S2 CLK S3 L S4 LK S5 CLK(r) & ((R_P & 3) or 4) Figure 3.3: State diagram for the read bus cycle of the MC68020. 4. Traversing Causal Event Graphs Traversing a CEG refers to the propagation of timing values from a set of reference events R = (erl, er2...,erkl to events that are connected directly or indirectly to R [10]. Event-graph traversal is necessary to define the temporal relation of a non-reference event, connected indirectly to a reference event, through a direct link that subsumes the information contained in the indirect links. Traversal occurs by following arcs leading from a reference event er to all non-reference events ei E E rootec at e r E R. The propagation of timing values gives a timing equation, t(ei), to an event ei, relative to ar event er. A CEG is traversed using the traversegraph algorithm, which calls propagatevalue to establish timing equations for a non-reference event, and to establish state-transition times (if a state diagram is specified). The propagate_value algorithm calls resolve_reference_event to resolve the situation where an event has multiple reference events. These algorithms are discussed in the following sections. 4.1 The Traverse_Graph Algorithm The traversegraph algorithm passes reference events to the propagate_value algorithm. The algorithm consists of two steps that are repeated iteratively until all arcs in a CEG have been traversed. In Step 1, the start event es and all sequencing events with an out-degree greater than one are passed to propagate_value. After all reference events have been passed to the propagatevalue algorithm there may remain untraversed arcs; for example, the arc between DSACKOfl and CLKf2, in Figure 3.2. In this situation (Step 2), those untraversed arcs, tl, whose event eto has received a timing equation are examined. The timing equation associated with the event efrom of such arcs is established in the following manner: 4

If eto E er: * t(efrom) = - tl * e refrom) = eto Else: * t(efrom) = t(eto)- tl * e refrom) = e reto) Step 1 is then repeated, with those events with an out-degree greater than one that received a value through Step 2 passed to propagate_value. The algorithm terminates when all arcs have been traversed. 4.2 The Propagate_Value Algorithm The propagate_value algorithm is given a reference event er, and traverses the CEG affixing an equation for events rooted at er. An event ei has a set of parent events P = {epl, ep2.... epm} and children events C = {ecl, ec2...,eck}. The algorithm performs a breadth-first search of the CEG rooted at er by traversing arcs connecting a parent event with its children. All the arcs connected directly or indirectly to er are traversed, except as follows: * If event e r is a sequencing event and is associated with bus state Sr, and is connected directly or indirectly to a sequencing event ei (associated with bus state si), then ei is not traversed during a traversal of the CEG rooted at er. Furthermore: * If e r and e r+l are consecutive sequencing events then the arc tl between them specifies the state transition time of state Sr associated with e r. The propagate_value algorithm is shown in Figure 4.1 and an example execution of this algorithm is shown in Figure 4.2. 4.3 The Resolve_Reference_Event Algorithm Consider the case, depicted in Figure 4.3, where an event ei has two reference events erl and er2, and that ei has received a timing equation relative to erl. When the CEG relative to er2 is traversed ei will be reached. At this point a decision has to be made, if possible, on which of the two reference events, erl or er2 to use when determining ei's timing equation. The resolve_reference_event algorithm performs this task using the following rule: *If an event ei (an eto event) is indirectly or directly connected to events erl and er2 (efrom events), and if it is known that e rl occurs before er2, then the link between er2 and ei is the true causal link. The link between erl and ei is shown for documentation purposes. Note that for an event to have multiple reference events, these reference events need to be sequencing events. Event eri is associated with bus state sl and er2 with bus state s2. If it can be shown, by traversing the state diagram, that state sl (s2) always occurs before state s2 (sl), then er2 (erl) is the reference for event ei. The traversal of a state diagram to determine if state s2 occurs after state sl requires two conditions to be satisfied: (1) it must be shown that state sl has a transaction path to state s2, and (2) that state s2 does not have a transaction path to state sl. 5

The search for a transaction path between two states is performed by a depth-first search of the statetransition graph. The start state for condition 1 is sl, and that for condition 2 is state s2. A state once visited is marked, and is not revisited. Arcs leading into the start state, so, (SO in Figure 3.3) are not traversed as they represent the start of a new bus cycle. The search terminates for condition 1 (2) when state s2 (sl) is reached, or when there are no more arcs to traverse. Propagate_value (er) ep = er; tl = next_bfs_arc(); ebfs = eto(tl); while (tl<> null) { change = 0; If (e bfs not visited and ep = e r) { /* Illustrated as Case A in Figure 4.2 */ t(ebfs) = t; change = 1; } Else If (ebfs not visited and ep <> er) { /* Illustrated as Case B in Figure 4.2 */ t(ebfs) = tl + t(ep); change = 1; } Else If (ebfs visited and er(ebfs) = er) { /* er(ebfs) refers to the reference event of ebfs */ t(new) = tl + t(ep); /* Illustrated as Case C in Figure 4.2 */ t(ebfs) = tighter (tnew, t(ebfs)) /* computed using the actual values associated with If (t(ebfs) = tnew) the timing symbols and comparing their lower and change = 1; upper bounds [10] */ } Else If (ebfs visited and er(ebfs) o er)) { e rebfs) = resolve_referenceevent(er(ebfs), er, ebfs); If (e rebfs) <> er and ep o er) { t(ebfs) = tl + t(ep); change = 1; I If (er(ebfs) <> er and ep = e r) { t(ebfs) =t; change = 1; } } If (change) e rebfs) = er; tl = next_bfsarc (); /* The next arc to be traversed is chosen so that it satisfies Rule 5.1 */ If (ti <> null) { ebfs = eto(tl); ep = efrom(tl); If (ep and ebfs E consecutive sequencing events) ttrans(ep(sp)) = tl; } Figure 4.1: The propagate_value algorithm If condition 1 is not satisfied, then nothing can be said about the temporal relation between the two states sl and s2. If condition 2 is not satisfied, then sl may or may not occur after s2, and consequently no a priori decision can be made on the temporal relation between the two states. If both conditions are not satisfied both ern and er2 are retained as reference events. 6

The resolve_reference_event algorithm is illustrated in Figure 4.3. The tree representing the depthfirst search of the transition diagram is also shown in Figure 4.3. From the tree shown in Figure 4.3, it is clear that SO has a path to SI, and that SI does not have a path to SO. Therefore, bus state SI is always reached after SO and, consequently, the falling edge of the clock signal is the true reference event for the falling edge of AS. Case A 1550 0, 40 e 20 1) )e Case C 20, 40 10, Case B []|s C represents a set of events and could have a depth greater than 1 Figure 4.2: Illustration of propagate_value so erl Cr2 S1 CLK\ CLK -I rl(S0) fl(Sl >ro^ ^ Tree representing depth-first search S2 of state diagram using the rules of the resolve_jeference_event algorithm Event graph representing multiple reference events Figure 4.3: Illustration of resolve_reference_event. The CEG of Figure 3.2, after traversal is shown in Figure 4.4. Note that all non-reference events are directly connected to reference (sequencing) events and that the temporal relation between a nonreference event and a reference event is contained in this direct link. Also, note that the temporal relation of sequencing events with regard to the start event is not yet established. To do so it is necessary to traverse the state-transition graph. 5. Traversing State-Transition Graphs In the presence of sequencing events, it is necessary to traverse the state-transition graph associated with a cycle to determine the timing equations that relate the occurrence of a state relative to the start of a cycle. It is necessary to identify the transaction paths to a state, and loops in a state diagram. Once this is done, the timing equations relating the occurrence of a bus state relative to the start of a cycle may be expressed as a function of: the paths to a state, the time associated with each statetransition in a path (determined by the propagate_value algorithm), and the possible loops that may be encountered (the number of times a loop is executed is expressed as a constant). 7

rl(SO CLK {r2(S2^ Q r3(S4 CL> T6 Figure 4.4: Example CEG after traversal. are not traversed, nor are the arcs that signify completion of a bus cycle. For example the arc from S5 to SO on the state diagram, shown in Figure 3.3 is not traversed as it leads into so. Also, the arc from $5 to the Read box is not traversed as it signifies the completion of the read cycle. The path being traversed relative to so is maintained in current__ath. When a state, si, is visited, and it does not exist in T6mbe ADDR en crrenp is dded o e lis of p47A from so. If the state si is a member DSACK1 sDAT T29 ttrans(SO)= 73; ttrans(SI)= T2; ttrans(S2) = T3; ttrans(S3)= T2; ttrans(S4) = 73; ttrans(S5) T2; Figure 4.4: Example CEG after traversal. of currentpth-first search of the state-transition graph s performed starting from s. Arcs leadindex, loop_counter, are not traversed, nor are the arcs that signify completion of a bus cycle. For example the arc from S5 of the loops in the state diagram is mahown in Figure 3.3 is not traversed as it leads into s. Loopcounter is incremented 55 to the Read box is not traversed as it signifies the completion of the read cycle. The path being traversed relative to so is maintained in currentQath. When a state, si, is visited, and it does not exist in current path, then current path is added to the list of paths to si from so. If the state sj is a member of currentQath then a loop in the state-transition graph has been traversed. An index, loop-counter, of the loops in a state diagram is maintained; it initially has a value of 0. Loop counter is incremented when a loop is identified and with it is associated those states in current_path that form the loop. All paths to a state are enumerated and so are all the loops in a state-transition graph. If, after the traversal of the state-transition graph, there are states that do not have a transaction path from so, then these state are unreachable. Such a condition manifests an incorrect state-diagram specification. Figure 5.1 shows an example state-transition graph and the result of traversing this graph. TEST Paths: S1: SO, SO-S2 S2: SO, SO-S1 S3:SO, SO-S1-S2 Loops: 1: SI 2: S1, S2 Figure 5.1: Illustration of state-transition-graph-traversal

6. Generating Timing Equations The timing equation relating an arbitrary event pair, el and e2, may be determined by: finding the closest common ancestor, ea, to the reference events of ej and e2, and generating timing equations that define the temporal relation of ej and e2 with regard to ea. It is necessary to find the closest common ancestor to a pair of reference events to avoid examining false transaction paths. When a bus cycle has a single transaction path, there is only a single reference event, es. The event es is, therefore, also the closest common ancestor, ea., for any event pair. In the presence of multiple transaction paths, all reference events are sequencing events. Given two reference events e i and ej associated with bus states si and sj, if si = sj then ea = e i = ej. If s i ~ sj then the transaction paths to both states, established by the state-transition-graph-traversal algorithm, are examined. If a transaction path to si (sj) includes sj (si) then ej (e i) is the ancestor event for ei (ej). Note that, in general, either ei or ej, or both, are ancestor events when given a pair of dissimilar reference events ei and ej. This is important because it eliminates the possibility of considering a transaction path that does not include both ei and ej when determining the temporal relation between events rooted at these reference events. For example, consider the the state diagram shown in Figure 5.1. Assume that si is S2 and sj is S3, ea is S2. If instead ea was assumed to be SO then a transaction path that does not include S2, SO-S3 will be considered when generating equations that establish the relationship between S2 and S3. Given an ancestor event ea and a pair of events e 1 and e2 whose reference events are ei and ej, associated with bus states si and sj, respectively, the timing equations that define the temporal relation of e with regard to e2 are determined as follows. The equation t(el/e2) is to be generated. The symbol t(el/e2) refers to the separation of el relative to e2; t(el/e2) = - t(e2/el). Without loss of generality let ea = ej, then t(el/e2) = t(el/ei) + t(ei/ej) - t(e2/ej). The equation t(ei/ej) is established as follows. There are as many timing equations defining the relation between ei and ej as paths from sj to si. The paths from sj to s i are determined by examining the transaction paths to si. These transaction paths have the form socsjpsi2. There are as many paths from sj to si as unique state sequences P. Each of these paths yields a timing equation from sj to si. Each timing equation is composed of the state-transition times associated with the sequence of states that form sjp. In addition, if any of the states in the sequence sjf are part of a loop in the state-transition graph (recognized using the state-transition-graph-traversal algorithm), then the timing equation is also composed of the transition time of the loop. The transition time of a loop is the sum of the transition times of the states in a loop, multiplied by a unique constant associated with each loop. Each loop is factored into a timing equation only once. The transition time of loops that include the state si are not added to the equation. This is because the timing equation establishes the temporal relation between the last occurrence of ej and the first occurrence of ei. The equation between a non-reference event and a reference event (t(el/ei) and t(e2/ej)) is established by examining the arc in the traversed-causal-event-graph connecting a non-reference event with a reference event. Consider, for example, the CEG shown in Figure 4.4 and the state diagram shown in Figure 3.3. The timing equation between DATAsi (ej) and ADDRsl (e2) is established as follows. First note that ei, 2a and p denote a concatenation of a sequence of states. 9

the reference event for DATAsl is CLKr3, and is associated with bus state S4. The reference event for ADDRsl, ej, is CLKrl, and is associated with bus state SO. The transaction path from SO to S4 is SO-S1S2-S3 with a loop at S3. The equation t(ei/ej) is therefore 2xT3+(2+nl)x72. The equation t(el/ei) is -T27 and the equation - t(e2/ej) is -T6. Therefore, the equation t(el/e2) is 2xT3+(2+nj)xT2-727-T6. 7. Summary In this paper, we have discussed a technique for generating symbolic timing equations from a graphical specification of interface behavior. This technique employs a scheme for the representation of temporal and sequencing information using casual-event-graphs and state-transition graphs. Some of the important characteristics of a CEG are that it has a single component, and either a single reference event, or as many reference events as sequencing events with out-degree greater than one. We have outlined algorithms used to traverse a CEG to establish timing equations of non-reference events relative to a reference event, and to determine state-transition times. The resolve_reference_event algorithm handles the situation wherein a non-reference event has multiple reference events. The state-transition-graph-traversal algorithm determines all paths to a state and loops in a state diagram. It, in effect, establishes the temporal relation of reference events with regard to the start of a bus cycle. Finally, we have discussed an algorithm that determines the timing equation between arbitrary events. The symbolic-timing-equation generation tool is functional and uses components of the SpecIT [10] suite of tools (Xwave and Xstate) for the specification of interface behavior. References [1] W.I. Fletcher. An Engineering Approach to Digital Design. Prentice-Hall, Inc., 1980. [2] M. McFarland. CPA: Giving an Account of Timed System Behavior. In Proceedings of TAU'90, August 1990. [3] W.P. Birmingham, A. P. Gupta and D.P. Siewiorek. Automating the Design of Computer Systems: The MICON Project. Jones and Bartlett Publishers, 1992. [4] F. Mavadatt and T. Gahlinger. On Deducing Tight Bounds from Partial Timing Specifications. In Proceedings of TAU'90, August 1990. [5] K. Khordoc, E. Cerny, and M. Dufresne. Modeling and Execution of Timing Diagrams with Optional and Multi-Match Events. In Proceedings of TAU'92, February, 1992. [6] A.R. Martello, S.P. Levitan and DM. Chiarulli. Timing Verification using HDTV. In Proceedings of the 27th Design Automation Conference, June 1990. [7] T. Amon and G. Borriello. An Approach to Symbolic Timing Verification. In Proceedings of the 29th Design Automation Conference, June 1992. [8] H.S. Stone. Microcomputer Interfacing. Addison-Wesley Publishing Company, February 1983. [9] Motorola, Inc. MC68020 32-bit Microprocessor User's Manual. Prentice Hall Inc., 1990. [10] A. J. Daga and W. P. Birmingham. Specification of Interface Behavior for the Automatic Generation of BusInterface Models. Technical Report, The University of Michigan, 1992. 10