A formal model of computer architectures for digital system design environments

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN. V O L

Y. NO. 5. M A Y 1'440

473

A Formal Model of Computer Architectures for Digital System Design Environments PHILIP A. WILSEY

AND

Abslracl-The process by which computer systems are designed and implemented has become a topic of considerable interest in recent years. Work in this area includes techniques for the automatic generation and optimization of microcode, synthesis of datapaths and control units, and machine description and simulation tools. An important aspect of these efforts i s the use of one or more models of the machine as the basis for the design system. The adequacy and generality of these models becomes particularly important when the design system i s to be useful for several types of machines (i.e., is retargetable) and across several abstraction levels (i.e., i s multilevel). As a result of this desire for retargetable and multilevel capabilities, investigations have also been carried out on the design of models of computer architecture. I n this paper we present a new and rather powerful model of computer architecture that i s designed for use in multilevel, retargetable computer system design environments. This model and its formal definition will then serve as the common basis for the construction of a set of design tools that will form an integrated computer architecture design environment.

I . INTRODUCTION ECENTLY developed techniques for automating the computer design process has spawned an increased interest in modeling computer architectures. This is primarily due to the fact that, on a per machine basis, the construction of design automation systems incurs a large cost and, thus they can only become widely and economically used if they can be applied to the design of a large class of machines. In order to enlarge their domain of application then, design automation systems need to use one or more models to describe the behavioral and/or structural characteristics of computer architectures. Naturally, the more general the underlying architecture model, the more useful will be the design automation system. Unfortunately, most architecture models are constructed to provide information for one particular aspect of the design process [ 11-[6]. Thus the goal of providing an integrated set of design automation tools (e.g., [7]) is inhibited since it is necessary to provide, possibly at several abstraction levels, multiple design-system-dependent descriptions of the architecture. Therefore, recent investigations have also included the design of architecture

R

Manuscript received October 19, 1988: revised June 19. 1989. This work was supported in part by the National Science Foundation under Grant DCR 8408750. This paper was recommended by Associate Editor R . K . Brayton. P. A . Wilsey is with the Department of Electrical and Computer Engineering. University of Cincinnati. Cincinnati. OH 4522 1-0030. S . Dasgupta is with the Center for Advanced Computer Studies. University o f Southwestern Louisiana. Lafayette. LA 70504-4330. IEEE Log Number 893352 1 .

SUBRATA DASGUPTA

models that can both describe a large class of computer architectures and provide sufficient information about the described architecture to drive a large number of design automation systems [8]-[10]. Computer architecture models also can serve other aspects of the design process than as input to design automation systems. For example, they can be used to reason about the correctness of the machine design [3], identify and enforce correctness preserving transformations [ 1 11, or demonstrate specific properties (liveness, safeness, etc.) about the machine under consideration. Our primary concern in this paper is to present a new and quite powerful model of computer architectures for machine description. This model is capable of representing a machine across the abstraction levels ranging from the exo-architecture' to the gate level. The goal of this work is to establish a formal framework for the construction of a new hardware description language that will be useful for a large class of retargetable design automation systems. The model in this paper has evolved from an earlier model that we had developed for describing clocked architectures [ 131, [ 141. The current model retains the axiomatic techniques for describing the behavior of machine components but extends the control mechanisms available to coordinate the interaction of the behavioral components. We have used this model to describe a large variety of computer architectures and have found it to be sufficiently general for the range of abstraction levels that we desire. The rest of this paper is organized as follows. Section I1 briefly discusses several issues related to the problem of modeling computer architectures. These issues have been discussed in more detail in [15]-[17]. Section 111 reviews a temporal logic, developed by Allen [18]-[20], which we use to formally define the execution semantics of the model. Section IV presents a semi-formal definition of the model; the formal definition appears in [21]. Section V presents two examples which, in conjunction with the examples presented in Section IV, serve to demonstrate the power of the model to represent the behavioral properties of many different machines. Section VI presents some applications of the model. Finally, Section VI1 contains some concluding remarks. 'The exo-architecture abstraction level is the view o f a computing syatern taken by an assembler language programmer or compiler writer [ 121.

0278-0070/90/0500-0473$01.OO 0 1990 IEEE

11. T H EPROBLEM SPACE

There are several properties of computer systems that must be considered when designing a model of computer architecture. With regard to the problem domain of this investigation, these properties are: 1) what abstraction levels are to be described; 2) whether the structural or behavioral properties (or both) of a machine are to be described; 3) whether functional or operational (or both) description techniques are to be used; 4) whether the statement execution semantics are to be procedurally or nonprocedurally controlled.

In modeling computer architectures. a consideration of particular importance is whether the model is to exhibit the structural or behavioral characteristics of the machine. The structurul characteristics of a machine are concerned with the physical resources and their interconnections. In contrast, the functions performed by the machine are termed its behavioral characteristics. A given model can provide either operational or functional notations for describing computer systems. An operational description defines the behavior of the system in terms of an algorithm or program and may be taken to imply, in some sense, the method by which the behavior is to be realized. Afufitnctionaldescription defines the behavior of a machine in terms of logical relationships between data stores and results of operators. Thus a functional description does not concern itself with the method used to implement the described function; rather, it defines a set of logical relationships that characterize the behavior of the entity being described. We have argued elsewhere for the need of a functional style of architectural descriptions [22], [ 171. There, we identified two key advantages to functional descriptions. First, they provide a method for postponing decisions regarding how a particular behavioral entity is to be realized. Second, functional description techniques allow us to confess ignorance pertaining to how a particular machine component's behavior is implemented. That is, we may know, for example, the behavioral properties that the arithmetic logic unit of the VAX 11i780 [23] exhibits without knowing the means through which the behavior is realized. Without a functional description style, we would have to make certain, possibly incorrect, assumptions regarding how the behavior is realized. Despite [he advantages of functional descriptions, a model to describe a wide range of abstraction levels must also contain an operational component. Consider, for example, the instruction fetchldecodeiexecute cycle of the VAX 1 11780 [24]. We can model each component (fetch, operand decode, and execute) as a functional entity but we know that the interaction of these components canand may need to be-characterized algorithmicallyhence, the need for an operational component. The execution semantics of the statements composing a description can be either procedural or nonprocedural. The semantics of a procedural statement set are such that

the textual ordering of the statements implies the statement execution sequence. That is. let s,,&. * . . s,,be an ordered set of statements in a description. I n a procedural description if S, is not a branch statement then S, + I will be executed after S, for all 1 Ii < n . In a nonprocedurul description the textual ordering of the statements does not imply their order of execution. Rather a statement or set of statements is executed based upon some condition being true. In other words, let C,, C', . * , C,, be a set of conditions and SI, S,, . . . s,, be the respective set of statements corresponding to the conditions. I n a nonprocedural language, a statement S, is executed whenever the corresponding condition C, is true. Statements are executed according to this scheme until no condition is true, in which case the system terminates. 9

111. A TEMPORAL LOGIC The execution semantics of our model are formally defined using an interval temporal logic developed by Allen [ 18]-[20]. There have been two other temporal logics used within the domain of computer architecture, namely: the work of Bochmann 1251 which used the temporal logic defined in [26], and the work of Moszkowski [27], [28]. Our main reason for selecting Allen's formalism over these others is that Allen's logic allows us to easily reason about the relationships of time intervals to one another as well as the relationships of actions to time intervals. The logic is based upon time intervals rather than time points. This approach is taken so that one can easily reason about the occurrence of an action without concern as to the precise point in time that the action actually occurs. With respect to time intervals there are thirteen relationships that can hold between intervals. For our purposes we are only concerned with the six relationships shown in Fig. I . The meaning of these relationships is given using t - and t+ to represent, respectively, the lesser and greater endpoints of the interval t . Each of the interval relations of Fig. 1 has a corresponding predicate in the logic. Let t and s each represent some time interval; then the relationships between t and s are:

t and s represent the same time interval, t is before s and there is not an inMEETS(t, s ) : terval r that is between t and s, t is fully contained within s, DURING ( t , s ) : OVERLAPS ( t , s ) : t begins before s, s begins before t finishes, and t finishes before s, t and s begin together, but t finSTARTS(t, s ) : ishes before s finishes, FINISHES ( 1 , s): t starts afters starts, but they finish together.

EQUALS(t, s ) :

Allen has defined a set of axioms for the behavior of these predicates. Some of these assert the mutual exclusiveness of the relationships; others define the transitivity of the predicates. A detailed discussion of these can be found in 1191. For our purposes, we are only concerned with the

47.5

WlLSEY A N D D A S G I J P T A : A R C H I T E C T U R E S F O R S Y S T E M D E S I G N E N V I R O N \ I E I \ ; I S

Interval Relatwn 1=s t meets s t during s I overlapss

tsms t finishes s

Equivalenr Endpoint Relations

A

(I+ 5 S+))

1:; 2;1 2%{ 1-

< S-

A

t+

> S-) A

V ((t- 2 S-) A (I+ (t+ < S+)

< S+))

Fig. I . Relationships of time intervals

fact that for any given interval, t , there exists some other interval such that each of the predicates of the logic holds. That is, given an interval t, there is an interval that meets t, that equals t , that starts with t, and so on. Three additional predicates that will be useful in our work are: IN(t, s) H DURING(t, s) V EQUALS(t, s), BEGINS (t, s) e STARTS (t, s) V STARTS (s, t) V EQUALS(s, t), ENDS(r, s) e FINISHES(t, s) V FINISHES(s, t) V EQUALS(s. t ) . Informally, the predicate I N states that either t and s represent the same interval or t is fully contained within s. The predicate BEGINS states that t and s begin together. The predicate ENDS states that t and s finish together. Two other components of Allen’s logic relate to properties and events. A property is a time dependent predicate defined on some aspect to the universe under consideration, or a particular state of that universe (e.g., a static value of a program variable). An event is something that may cause a state change or the value of a particular predicate to change (e.g., incrementing the value of a program variable). Corresponding to these two notions, Allen defines two predicates: HOLDS and OCCUR. The predicate HOLDS takes a property, p , and a time interval, t , and is true if the predicate p is true throughout t. For example, if the property p represents the equality of the program variable x to the value 6 , and t is a time interval throughout which the value of x is 6, then the predicate HOLDS ( p , t) is true; if, however, the period of time during t in which the value of x is not 6 then the predicate HOLDS(p, t) is false. One of the most important properties of the HOLDS predicate is that if it is true for some predicate p and time interval t then it is also true for every time interval s contained in t. Formally, we state HOLDS(p, t ) e Vs:IN(s, t)

=)

HOLDS(p, s).

The predicate OCCUR takes an event e , and a time interval, t, and is true if the event e occurs in t and there is no subinterval s o f t in which e occurs. For example, let the event INC ( x ) denote the action of incrementing the program variable x and assume that INC ( x ) executes completely within interval t; then the predicate OCCUR(INC(x), t ) is true if and only if there is no subinterval o f t in which INC(x) executes (completely). Thus the predicate OCCUR has the property that if it is true for an event e in time t, then it is not true for any subinterval o f t . Formally, this property of the OCCUR predicate is defined by the axiom: OCCUR(e, t ) A DURING(s, t)

1

OCCUR(e, s ) .

IV. T H EMODEL An architecture, A . is defined as a 7-tuple: A = ( T , C. S, F M , I M , C M , C M , )

where Tis an entity called the timekeeper, C is a (possibly empty) set of clocks, S is a set of stores, FM is a set of functional module types, IM is a set offinctional module instances, CM is a (possibly empty) set of control modules, CM, is a (possibly empty) set denoting which control modules are active upon machine startup. The timekeeper and the set of clocks together provide the temporal framework for the architecture. The set of stores define entities in the architecture for the storing of information. Together, the set of functional module types and functional module instances denote devices for the transmission and processing of information. The set of control modules provides entities which can be used to control the activation of functional module instances.

4. I . Time In designing or describing architectures, timing information can be completely abstracted away (e.g., at the exo-architecture level), be very detailed (e.g., at the register-transfer level), or be sufficient to show only those intervals of time at which “interesting” events occur (e.g., the times at which a micro-operation begins and completes its execution). A model of architectures, then, must be able to capture the concept of time at several abstraction levels. Thus in our model, we define a hierarchy of timing constructs. 4. I . I . Timekeeper The timekeeper, T, provides a single universal temporal framework for an architecture, and is defined as a 3-tuple: T = ( U , TS, TI ) where U is the unit interval (representing the smallest unit of time in which architectural actions can occur), TS is the set of positive integers such that n E TS denotes the n t h unit interval of the timekeeper, and T, E TS is the initial interval of the timekeeper. The timekeeper defines a set of unit time intervals that are related to one another in the following way. Let tk( i ) denote the ith unit interval of the timekeeper,? then for each unit interval i, i > 0, the predicate: MEETS(tk(i), tk(i

+

I))

is true. Stated more simply, the timekeeper defines a set of intervals of unit length that are adjacent to one another (Fig. 2). The timekeeper provides unit intervals to depict and control actions that occur in the architecture. It provides a temporal framework within which the flow of informa‘We will ube this notation throughout the rest of this paper to avoid contusion with what are later detined as clock intervals.

U 1

r1

I

’ T,+I

I

I

I

I

r1t2 ~ , + 3I T,+I

T

I

2) The first interval of the initial clock state. CS,, E CS, occurs such that

Fig. 2 . Pictorial view of the timekeeper.

tion through the architecture can be traced. As will be seen later, the timekeeper can be used to: 1) synchronize cyclic events that are defined using clock and clock state intervals; 2) determine when a transient store takes on a transient value; 3) determine when the effects of instances of functional modules types are asserted; 4) control the effects of the delay action in a control module.

4. I . 2. Clocks A clock c E C is used to control a particular set of periodic or repetitive architectural events. We motivate the definition of clocks with the following example: Consider as an architectural event, the microinstruction fetch/execute cycle. The timing of this event may be controlled by a two state clock C ‘ which alternates between clock states C S ; and CS; such that when C’ is in states C S ; , microinstruction fetch occurs and when C ‘ enters state CSi. microinstruction execution occurs. The clock then returns to state CS; and so on. The duration of each clock state must be sufficient for the respective subevents “fetch” and “execute” to complete successfully. Thus if on one instance of microinstruction execution it requires twice the “normal” time (say, due to the encoding in the microinstruction of a memory read operation) then the duration of the clock state CS; must be “stretched” to twice its normal duration. Finally, the clock C ’ must also be initially synchronized or “aligned” with some particular value of the timekeeper. Formally, a clock, c , is defined as a 6-tuple:

c

=

( I , A , CS, DC, CSo, S T )

where I is a (possibly empty) set of input ports, A is a positive integer called the alignment, CS is an ordered set of symbols called clock stares, DC is an ordered set of positive integers called clock state durations, CS,, E CS is the initial clock srate, and ST is a (possibly empty) set of 2-tuples called stretch conditions. A clock and its states define sets of time intervals that are related to timekeeper unit intervals as follows: let CS = { CSO, C S , , * . . , CS,, } and let c ( j ) and CS, ( j ) denote, respectively, the j t h interval of the clock c and clock state CS,; then: 1 ) Each stretch condition st

st

=

E

ST is a 2-tuple:

(b,, n , )

where b, is a Boolean expression over a subset of the input ports and constant values, and n, is a positive integer denoting the stretch factor.

BEGINS(tk(A), CSo(I ) ) is true. That is, the first interval of CS, is aligned with the Ath unit interval of tk. 3) The intervals of the clock states are such that MEETS( CS,(i ), CS, + I ( i ) ) A

MEETS(CS,,(~), CSn(i + I ) )

holds for 0 I j < n and i = I , 2. . . . . That is, the clock states are adjacent and the tzth clock state is followed by the zeroth clock state. 4) A stretch multiplier, m,, is defined for each interval, i , of the clock in the following way. Let EVAL(b, t ) be a function that returns the result of the Boolean expression b during the interval t , and let j be such that BEG I N S ( t k ( j ) , C S o ( i ) ) is true for all i , j > 0; then

m,

=

r

if 3 ( b k ,n k ) : ( b,!, t i k ) E ST

n,!

A

(EVAL(b,, t k ( j ) ) = true)

otherwise

I,

That is, for each interval t k ( j ) for which the Boolean expression bk is true, the multiplier mi equals nk (where ( b k , nk ) E S T ) , otherwise mi equals I . The use of the stretch multiplier is shown below. 5) Associated with each clock state CSj E CS is a unique integer d j E DC called its duration. 6) The length of each interval of a clock state is determined with respect to timekeeper intervals by BEGINS ( t k ( i ), CS,(k))

=. ENDS(tk(i

+(tq

x d,)

- l ) , CS,(k))

f o r 0 5 j I ti and i, k = 1, 2, . * . 7) Each interval of the clock c is then related to the intervals of its clock states by the axiom:

BEGINS(CS,,(~), ~ ( j )A )E N D S ( C S , , ( ~ )~, ( j ) ) forallj

=

1 , 2,

-

*

*

.

Informally, a clock controls cyclic actions that are initially synchronized with the timekeeper interval specified by the alignment A . The action occurs over an interval whose length (with respect to timekeeper intervals) is determined as a function of the clock state delays and the stretch multiplier. An example of a clock with two clock states is shown in Fig. 3 . The clock C,, defines an unbounded, repetitive sequence of time intervals with the first interval defined to begin with the timekeeper unit interval 0. Within each interval of C,, there are two subintervals represented by the clock states p h l and ph2. A timing diagram of the clock C,, is shown in Fig. 4. Notice that the first interval of C,, spans a total of 100 timekeeper unit intervals whereas the second interval spans 200 timekeeper unit intervals. This is due to the stretch factor included in the

-177

WILSEY A N D DASGUPTA. ARCHITECTURES FOR SYSTt.hl Dt.SIGN t . N V I K O N M E N T S

.fin

C , = I = (a) DC= (50.50) A=O CSo = phl cs=(phl,ph~) .V’= l)

I 49

I 49

I

1b

2$9

3149

Ik

Fig. 4. Pictorial v i e w of a clock with 2 clock states.

clock description, which states that if at the start of any interval of the clock C,,, the predicate “ a = 1 ” is true, then the duration of the clock is doubled. The second interval of C,, as shown in Fig. 4 is thus stretched.

4.2. Stores , SI, } be the set of stores in an Let S = { S , , S?, architecture and let VI be the set of values that SI can contain. Then each store SI is called a state component and the state set of an architecture is defined as the product set:

ss = VI x v.

x

* * .

( I . 0, P. DF, E )

where I is a (possibly empty) set of irzput ports, 0 is a (possibly empty) set of output ports, P is a (possibly empty) set of private srores, DF is a (possibly empty) set of delays, and E is a set of assertions called the effects. The sets I and 0 may be empty but the relation I U 0 # 0 must hold. The set of effects, E , of a module type define its behavioral characteristics. An effect, e E E , is a 2-tuple:

Fig. 3 . Modeling a c l o c h with 2 cloch state\

‘0

=

x VI,.

In other words, a particular machine state, M S E SS, of an architecture is an n-tuple of values of the state components. A store, S, E S, is said to be static if a change in the value of S, only occurs as the result of an action of an instance of a functional module type (Section IV-4.3). The values contained in a static store are called static values. A transient store is a store whose value may change, either as the result of an action of an instance of a functional module type, or as the result of an elapsed period of time. The values of a transient store may be static or transient. At any given time the machine state, M S E SS, is termed static if all of its stores, SI E S, contain static values; MS is called transient if one or more of its stores hold a transient value.

4.3. Behavior A model that captures the behavioral characteristics of a computer system at several abstraction levels must be very robust. It should support both functional and operational methods of descriptions; behavioral entities that are procedurally or nonprocedurally activated; both synchronous and asynchronous methods of control; and a means to easily replicate behavioral entities. Because of this, our model defines a hierarchy of behavioral constructs.

4.3. I . Functional Module Types The set of functional module types ( F M ) in an architecture are entities that can be instantiated one or more times for the purposes of describing devices that process and transfer information of the machine state. A functional module type (or simply module type),f m E FM, is a 5-tuple:

...

e

=

( pre, post)

where pre is an assertion called the precoriditiori, and post is an assertion called the postcotiditioti. Thus the behavior of the module type is defined by the postconditions for which the corresponding precondition is true. The set of delays, DF, of a module type defines the amount of time required by the module type to assert its effects. A delay, df E DF, is a 2-tuple: df

=

(h,d)

where b is a Boolean expression called the delay guard. and d is a positive integer called the delay lengrh. The delay of the module type-the total number of timekeeper intervals-is determined at any given timekeeper interval by the length of the delay corresponding to whichever guard is true. Note, if no delay guard is true or the set of delays is empty then the delay of the module type is unknown and will be determined by each particular instantiation of the module type. The case of multiple delay guards being true at the same time indicates an error condition. A module type defines a mapping from input ports and private stores onto the output ports and private stores. This mapping occurs such that it will satisfy the assertions of the effects set after an interval of time provided that the input port values remain stable. In the case where the input port values do not remain stable. the output ports and private stores whose values would have changed will still be defined with new values but what those resulting values are, will be unknown.3 Formally, the behavior of a module is defined by means of an event called ASSERT. However, before presenting the definition of the event ASSERT, we must first present several predicates, functions, and events. First, we define the following functions and predicates:

V A L f s , t ) = the value of the store s in the interval t , E V A L ( e . t ) = the value of the expression e in the interval t , true, if the store s is an input

SRC(s, a )

=

r

operand of assertion a false, otherwise

’These unknown \,slues will s t i l l he binary values. That is. the vi~lue\ held by the data stores will ~ / i i . r r ~ . be s binary values-in the case o f an unknown value. we simply iiiean that the particular binarq value held bq that data store is not dctined.

47 8

IhEE TRANSACTIONS O N COMPUIER~AIDFI)D t S I G N . VOI.

true, if the store s is an output operand of assertion a

DEST(s, a ) =

false, otherwise true, if Vi,j:IN(tk(i), t ) A

I N ( t k ( j ) ,t )

Ai # j

\false.

A

(VAL (s, t k ( i ) )

=

VAL(s, r k ( j ) ) )

otherwise

true, if 3 (pre, post)

E

E:

SRC(s, pre) V SOURCE (s, E,

r)

(SRC(s, post) A =

(EVAL (pre, t ) = true))

false, otherwise d,, if 3 ( b , ,d,) E D F :

DELAY(@, t )

=

EVAL ( b ( ,t ) = true

0, otherwise. The predicate STABLE is true if the value of the store s does not change during the interval t ; the predicate SOURCE is true if the store s is used as a source operand of the effects E during the interval r ; finally, the function DELAY returns the delay length of the module t y p e b in interval t if it is defined and returns zero otherwise. With each mapping characterizing the behavior of the module type, there is a subset of the set of input ports and private stores whose stability is important. That is, for the interval of time in which the module type defines its mapping some of the input port and private store values must not change. This subset is composed of all input ports and private stores that (a) appear in a precondition, or (b) appear in any postcondition for which the corresponding precondition is true. A formal characterization of the effects of a module type proceeds as follows. First, we introduce two events DEF and UNDEF. The event DEF will be used to assert a new machine state if the values of the input ports remain stable and UNDEF will assert a new machine state in the case where the input port values do not remain stable. Formally, these events are defined as OCCUR(DEF(E),r) 3j:ENDS(tk(j),t) A ( V (pre, post) E E : (EVAL(pre, t)=true) 3 HOLDS(post,rk(j+ l ) ) ) , OCCUR( U NDEF(E ) ,t ) =. 3 i , j : BEGINS(rk(i),f) A ENDS(tk(j),r) A (V(pre, post) E E:(EVAL(pre, tk(i))=true) * V S, S, E 0 U P A DEST(sL ,post), 3 ~ ) /z)/ : E V, A (VAL(s,,rk(j+ I ) ) = 211)).

Y. NO

5 . MAY IYYO

The events DEF and UNDEF cause a trznsformation of the machine state based upon the effects set E. DEF causes the new machine state to be such that for each precondition that is true in interval t , the corresponding postcondition will be true immediately after t . The event UNDEF will be used to define new values for the output ports if the input port values to not remain stable. Essentially, UNDEF defines new values for the destination operands (stores) at the end of time t , but precisely what those values are, is not specified. That is, the store sk is defined with a value zil from its domain of values V , , but what, precisely, that value is, we cannot say. We can now define the behavior of a module type in the form of an event called ASSERT, which for any module type, fm and some interval of time f : OCCUR(ASSERT( @), t ) 3 3 j : BEGINS(fk( j ) , t ) A ((D,= 0) v ( v k : (b,, d,) E D , , EVAL(b,,rk(j)) = false) V ( 3 k : ( bk,dk) E D, A (EVAL(b,,rk(j)) = true) A V l : ( B / , d / ) E Or-- { (bk,d,) 1, (EVAL(b,,rk(j)) = false))) A (((V s : s E I U P A SOURCE(s,E,rk(j)), STABLE(s,r)) * OCCUR(DEF(E),t)) V (( 3 s : s E I U P A SOURCE(s,E,tk( j ) ) , 1STABLE(s,t)) 3 OCCUR(UNDEF(E), t ) ) ) . Thus if all of the source operands of the effects set remain stable throughout the interval t , the occurrence of the event ASSERT causes an occurrence of the event DEF; whereas, if one of the source operands does not remain stable then the event UNDEF occurs. An example of a functional module type is given in Fig. 5. In this example, we have described a four input multiplexer where the value of the input port SEL is used to select the appropriate input port value as the new value of the output port OUT. In this example the set of delays is empty, therefore, we cannot make any statements about the time necessary for this module type to assert its output value. However, we can assume that there will be some interval of time in which it is to perform its mapping and use this assumption to discuss the input port stability requirements. Let t be a time interval in which an instance of the module type FM,,,,.,is to perform its mapping; and let the value of the input port SEL be 1 at the beginning of t . Thus the input port values whose stabilities are important are SEL and B. Now assuming that the values of SEL and B remain stable (i.e., do not change) during the interval t then the value of the output port OUT at the end of t will be such that the assertion OUT = B is true. If, however, the value of either SEL or B changes during the interval t then at the end o f t the value of OUT will change but we cannot make any claims concerning what the new value of OUT will be.

4.3.2. Instantiations of Functional Module Types Functional module types define possible operations that are instantiated as components of the architecture that

WILSEY A N D D A S G U P I A . AKCHITECTLIKES F O R SYSTEM DESIGN E N V I K 0 K S l t . N . l - S FMh =

I = [A. B. C. D.SEL) OUT]

o= P = b

DF =0 E = (. . . )

where

postj = OUT = A

pre I = SEL = 0 p r e l = SEL = I pre3 = SEL = 2

post*=

OUT = B

post3 = OUT = C post4 = OUT = D

p r e 4 = SEL = 3

Fig. 5. Functional module type description of

il

multiplexer.

transform the machine state. The instantiated components are called functional module instances and they are represented as the set IM in the model. A f i n c f i o n a l module instance (or simply instance), im E I M , is a 4-tuple:

im

=

( S M , N A , TY, G )

where SM is the name of the module type to be instantiated, N A is a set of name associarions, TY denotes the activation type (procedural or nonprocedural) of this instance, and G is a (possibly empty) set of guurds used to control a nonprocedurally activated instance. Note that only in a procedurally activated instance will the set of guards be empty. The set of name associations connected the input and output port sets of the instanced module type to data stores of the machine state. That is, each module type is instantiated with the data stores properly substituted for the corresponding port element. A name association, na E N A , is a 2-tuple:

nu

=

( FN, A N )

where FN is called the formal name, and A N is called the actual name. The formal name denotes an element of the module type’s input or output port set. The actual name denotes a store of the machine state. The activation type, TY, of an instance signifies how it is activated. An instance can be activated procedurally or nonprocedurally. A procedurally activated instance is invoked by an action of a control module (see Section IV-4.3.3). Once invoked by a control module, the instance becomes active and remains active for the number of timekeeper unit intervals determined by its set of delays (this time defaults to one timekeeper unit interval if the set of delays is empty or it has no true delay guard). After this time the instance becomes inactive and, provided that the input port values remain stable, new values are defined for the output ports and private stores such that the assertions of the effects set are satisfied. In more formal terms, if irn is a procedurally invoked instance then the behavior of im is defined by an occurrence of the event PROC-IM: OCCUR(PR0C-IM(iin),r) 3 3 j : BEGINS(tk(j ) , t ) A (((DELAY(SM,rk(j ) ) # 0) A ENDS(tk( j + DELAY(SM,tk(j)) - I ) , t ) ) v ((DELAY(SM,tk(j ) = 0) A EQUALS(tk( j ) , t ) ) ) A OCCUR(ASSERT(SM),t).

Thus the event PROC-IM uses the function DELAY to determine the length of time in which the effects of the instance occur. If DELAY returns a nonzero value, 17, then n will denote the number of timekeeper intervals necessary for the instance to assert its effects. If DELAY returns zero then the instance will assert its effects in one timekeeper interval. The activation/termination characteristics of a nonprocedurally activated instance is governed by the set of guards. There are two types of guards, namely: docked guards and nonclocked guards. A clocked guard, g E G, is a 2-tuple: g = (b,c )

where b is a Boolean expression and c is a clock (or clock state). A nonclocked guard is simply a Boolean expression. A particular set of guards is composed either entirely of clocked guards or entirely of nonclocked guards. In the case of a procedurally activated instance, the set of guards is always empty. Instances controlled by clocked guards are synchronized to activate (terminate) with the first (last) timekeeper unit interval of a clock interval. Activation occurs when: 1 ) there exists a timekeeper interval, t k ( i ) . in which the instance is inactivc: 2) there exists one and only one guard ( b , , c , ) E G suchthatBEGINS(tk(i).( , , ( k ) ) A ( E V A L ( b , , r k ( i ) )= true) holds for some interval k of clock c,. Once the instance becomes active, the clock of the guard satisfying condition (2) above is called the controlling clock, Crl. Note that if more than one guard satisfies condition (2) above then an error exists. A nonprocedural instance with clocked guards exhibits one of two behaviors based upon the instantiated module type’s set of delays. The first behavior occurs when either the set of delays is empty or if, at the beginning of the controlling clock, no delay guard is true. In this case the instantiated module type will assert new values for its outputs at the end of the controlling clock. The second type of behavior exhibited by this type of instance occurs when the instantiated functional module has a nonempty set of guards and if one and only one of the delay guards evaluates to true. In this case, the set of delays is evaluated in every timekeeper unit interval of the controlling clock to establish the length for a time interval beginning with each evaluation. The resulting time intervals that are contained within the controlling clock each represent a mapping of inputs to outputs by the instanced module. Formally, these subintervals of the controlling clock are such that the axiom DELAY(SM,tk(i)) # 0 A I N ( t k ( i + D E L A Y ( S M , t k ( i ) ) -l),Ctl). 3 t, : (BEGINS(rk(i),r,)A ENDS(rk(i+ DELAY(SM.rk(i))- I ) , t , ) A IN(t, .Cd)

V i : IN(tk(i),Crl) A

holds. Each t, satisfying the above axiom represents an interval of time in which the instance will assert new values for its output ports and private stores. Note, in this particular case, the set of delays must define a nonzero delay length during each timekeeper interval of the controlling clock. Formally, the behavior of an active nonprocedural instance with a clocked guard is defined by the event IM-C:

Instances controlled by noticlocked guards can become active in every timekeeper unit interval if one (or more) of the Boolean expressions is its guard set is true. The duration of any particular activation of this type of instance is determined by the set of delays of the instantiated module. If the set of delays of the instanced module is empty or if no Boolean expression of the delay set evaluates to true, then the activation of the instance is defined to occur in one timekeeper interval. Formally, this behavior is defined by the axiom:

OCCUR(IM- C(IM, t ) = 3 i : BEGINS(tk(i),r) A v i : i 2 TI A 3 bi: b, E G A (EVAL(b,, tk(i)) ((DELAY(SM,tk(i)) # 0) A = true) * ( v j : j > i A IN(tk( j ) , t ) , (DELAY(SM,tk( j ) ) 3 t : BEGINS(rk(i),r) A = 0 ) = false)) A (((DELAY(SM,tk(i)) # 0) A ENDS(tk(i+ ( V k : k 1 i A IN(tk(k+DELAY(SM,rk(j))-1,t), DELAY(SM,rk(i))- l),t) V 3 ?: BEGINS(rk(k), ?) A ENDS(rk(k+ ((DELAY(SM,rk(i) = 0) A EQUALS(rk(i),t))) A DELAY(SM,fk(j))- 1 ,?) A OCCUR(ASSERT(SM) ,t). OCCUR(ASSERT( SM ) ,?))) v ((DELAY(SM,tk(i)) = 0) A Informally, this axiom states that for every timekeeper inOCCUR(ASSERT(SM),t))). terval t k ( i ) in which a guard of the instance is true, the event ASSERT occurs in a time interval, t , such that: That is, if the delay length of the module type is nonzero in the first timekeeper interval of the controlling clock t , then: (a) the delay must be nonzero everywhere in the controlling clock interval and (b) the instance will assert new values for its output ports and private stores at the end of each of the subintervals defined by the previous axiom. If in the first timekeeper interval of the controlling clock the delay is zero then the instance asserts new values only at the end of the controlling clock (f). The event IM-C defines only the behavior of an activated instance with a clocked guard. Thus we must provide an additional axiom to determine when these instances are activated. This axiom is TlA3(b,,c,),k:(b,,c,)~GAk>OA EVAL(b, ,tk(i)) = true A BEGINS(tk(i),c,(k)) A ( V ( b / , c / ) ,m : ( b / , c , ) E G - { ( b , , c , ) }A m > 0 A (EVAL(b1 ,tk(i)) = false V i BEGINS(tk(i),c,(m)))) A 1 ( 3 1: OVERLAPS(t, ci(k)) A OCCUR(IM-C(IM),t)) OCCUR(IM- C(IM ) ,ci (k)) .

V i : i L

Stated more informally, the instance becomes ctive in any timekeeper interval, rk( i ), provided that the following three conditions hold. 1) There exists one guard of the instance’s set of guards in which: (a) the Boolean expression is true and (b) the clock defines an interval that begins with rk ( i ). 2) No two guards satisfy condition ( 1 ) above. 3) The instance is not active in an interval t that overlaps the clock interval of the guard satisfying condition (1) above (i.e., the instance is not already active). If these three conditions are met then the instance becomes active as denoted by the occurrence of the event IM-C.

1 ) t begins at the same time as t k ( i ). 2) the length of t is equal to the delay o f the imtance module type provided that it i s either noniero and one. Fig. 6 give4 three examples o f functional module type instantiations. In this example we use the clock state ph2 from Fig. 3 and the multiplexer description given in Fig. 5. The instance IMP is activated procedurally by an invocation action of a control module. Since the set of delays in the instantiated functional module is empty, this instance will perform its mapping (with the port sets appropriately connected to the machine state stores) one timekeeper unit interval after it is invoked. The instance IM,rp-lis activated nonprocedurally and since the Boolean expression of its guard is simply “true” it will be active during (every interval of) the clock state p h 2 . Due to the fact that the set of delays in the instantiated functional module is empty, the delay of this instance is determined by the duration of $72. The instance IM,,/] is also activated nonprocedurally, however, unlike IM,,,, I , there is no clock in the guard, i.e., IM,,, is controlled by a nonclocked guard. Thus whenever the Boolean expression of the guard is true the instance is activated and asserts a new value after one timekeeper unit interval. In order to get a better understanding of the behavioral characteristics of instantiated module types, assume that DF = { ( true, 45 ) ] in Fig. 5. Then the behavioral characteristics of the instances of Fig. 6 would be: IM/,: Once invoked by a control module, this instance will become active and assert a new value for the store alu-out (since, by the name association list, OUT is connected to alu-out) after 45 timekeeper unit intervals. After which time it will become inactive. IM,,!,-,: During each interval of the clock state ph2 this instance will become active. In a nonstretched interval of ph2, this instance will assert a new value for the store alu-out 5 times. That is, the instance provides a contin-

WILSEY AND DASGIJPTA. ARCHITECTURES F O R S Y S T E M DESIGN E N V I K O K M E N T S

IMP =

IM,,,,-l = G z, = (mir-alu-in-a = 1 )

Fig. 6 . Some examples of functional module instances

uous mapping function with a delay of 45 timekeeper unit intervals whenever it is active. Thus since there are 5 distinct subintervals each 45 timekeeper unit intervals long each wholly contained within a nonstretched interval of p h 2 , the instance will assert its effects 5 times. Note, in a stretched interval o f p h 2 , this instance will assert a new value for ah-out 10 times. ZM,tp-z: For each timekeeper interval in which the Boolean expression "mir-alu-in-u = I " is true, this instance will assert a new value for the store alu-out 45 timekeeper unit intervals later.

4.3.3. Control Modules The set of control modules, CM, denotes devices used to control the harmonious communication and cooperation of asynchronous processing entities. A control module cm E CM, is a 6-tuple: cm = ( I , 0, A , HEAD, SUCC, C ) where Z is a (possibly empty) set of inpur ports, 0 is a (possibly empty) set of ourpur ports, A is a set of ucrions, HEAD and SUCC are functions that are used to order the execution of the actions in the set A , and C is a set of Boolean conditions that are used by the functions HEAD and SUCC. Note, unlike functional module types, the sets Z and 0 can both be empty. There are two types of actions within a control module, namely: invocarion and syrzchronizurion. Invocation actions are used to activate procedurally invoked modules or other control modules. The issuance of an invocation action is instantaneous. That is, when invoking a module4 in timekeeper interval t , the invoked module will, provided it is not already active, respond (become active) in the same timekeeper interval t. In the case where an attempt is made to invoke an already active module, an error exists. There are two types of invocation actions, namely: cull and fork. A call action causes execution of the issuing control module to be suspended until the invoked module terminates. A fork action causes parallel execution of both the invoked module and the control module issuing the fork action. Formally, the behavior induced by a call action is defined by the event CALL: 'Henceforth. when there is no cause f o r ambiguity. *e will u x "module" to refer to either another control module or a procedurally activated instantiation of a functional module type. When necessary. we will distinguish between "control modules" and "procedural instances."

OCCUR(CALL(M),r) * ( M E CM A OCCUR(PR0C-CM(M),r)) V ( M E ZM A OCCUR(PR0C-ZM(M),t)). That is, if the module to be invoked, M , is a control module then the call action is defined by the event PROC-CM, and if M is a procedural instance then the event PROC-ZM defines the behavior of the call action. In order to ensure that a signal is not sent to an already active module we require the additional axiom:5 OCCUR(CALL,,(M),r) A OCCUR(CALL,(M),?) A ( P + 4) A (OVERLAPS(r,?) v OVERLAPS(?, t ) v IN(t,?) v IN(?,r)) 3 false. This axiom states that if a call action is issued to a module M in the interval t , then no other call can be issued to module M in another interval ? if the intervals r and 2 overlap in any way. The fork action is defined by the event FORK: OCCUR(FORK,,(M),t) 3 i, ? : EQUALS(tk(i),t) A BEGINS(t,?) A OCCUR(CALL,,(M),?). A fork action executes in one timekeeper unit interval and, beginning with the same timekeeper interval that the fork action executes, the event CALL occurs. Using the event CALL in this fashion allows us to ensure that a fork or call action cannot be issued to a module that is currently active via some other fork or call action. There are two concerns in the synchronization of modules in an architecture. First, there is a need to synchronize modules with respect to time. Second, there is a need for intermodule synchronization. In the case of nonprocedurally activated instances, the use of clocks in the guard achieves the first concern and the Boolean expression of the guard achieves the second. However, the synchronization of control modules requires some additional control mechanisms. The synchronization of control modules with respect to time is accomplished by the delay mechanism. The delay mechanism appears as an action in a control module and requires one argument. This argument is a positive integer denoting a number of timekeeper intervals. When encountered, a delay action causes continued execution of the control module to be suspended until the respective number of timekeeper intervals occur. After the requested number of timekeeper intervals occur, execution of the control module continues. Formally, the effects of executing a delay are defined by the event DELAY: OCCUR(DELAY(n),t) 1 3 i : BEGINS(rk(i),r) A ENDS(fk(i+n- l ) , f ) . 'We use p and q throughout this section to denote elements o f an indexing set that uniquely identities each distinct primitive action contained in t i l l of the control modules of the architecture.

This axiom determines the bounds on the time interval needed LO execute a delay action. Execution of a delay action does not alter the machine state other than to cause a temporary suspension of the execution of actions in a control module. Synchronization of control modules with respect to one another is accomplished through the use of a semaphore mechanism. A semaphore is a store s E S of the architecture on which only three types of operations can be performed. The first operation is initialization. Initialization of a semaphore occurs only once in a description and causes the semaphore to have a known value. The other two operations on semaphores occur as wait and signal actions of a control module. A signal action issued to a semaphore causes the value of the semaphore to be incremented by one. A wait action causes the value of the semaphore to be decremented by one if the value of the semaphore is greater than zero. The behavior of the wait and signal actions are similar to the P and V semaphore operators of operating system theory [29]. The behavior of a wait action is defined formally as the event WAIT: OCCUR(WAIT(s),t) * 3 j : ENDS(rk( j ) , r ) A (VAL(s,rk( j ) ) > 0) A (VAL(s,tk(j+ I ) ) = VAL(s,tk( j ) )- 1) which simply states that in the timekeeper interval that ends with the interval f , the value of the semaphore s will be greater than zero and after the interval f , the value of the semaphore will be decremented by one. There remain, however, two other concerns that must be addressed in the definition of a wait action. First, we must ensure that no two semaphore operations complete at the same time. This behavior is defined by the axiom: OCCUR(W AIT, (s),t ) * v q,?:ENDS@,?)A p q A 1 (OCCUR (SIGN A L, (s),? ) V OC C U R (W A IT, (s),? ) )

+

where the event SIGNAL represents a signal action. Informally, this axiom states that if a wait action updates the value of semaphore s at the end of time t , then no other wait or signal action can update s in an interval that ends with t. Secondly, we must ensure that whenever a wait action is executed, it completes at the earliest possible time. That is OCCUR(W AIT, (s),t ) * 3 i , j : BEGINS(tk(i),t) A ENDS(tk(j),t) A ( ( i = j ) V ( v k : i l k < j , 3 q,?:ENDS(rk(k),i) A (OCCUR (SIG N A L, (s),? ) v OCCUR (WAIT,,(s),?)V (VAL(s,tk(k)) = 0)))) which simply states that if a wait action occurs on a semaphore s in interval t then either: 1 ) the interval t is only one timekeeper unit interval in length, or

2) for every timekeeper interval in t (except that which finishes with t ) : (a) another wait or signal operation occurs on the semaphore s, or (b) the value of the semaphore s is zero. Similarly, there are three axioms governing the execution of a signal action. The behavior of the signal action is defined by the event SIGNAL: OCCUR(SIGNAL(s,t) * 3 j : ENDS(tk(j),t) A (VAL(s,tk(j+ I ) ) = VAL(s,tk( j ) )+ 1) which simply states that in the timekeeper interval that immediately follows t, the value of the semaphore s will be one greater than its value in the timekeeper interval that ends with t. As with the wait action, we must ensure that no two semaphore operations occur to the same semaphore in time intervals that end together. This is defined by the axiom: OCCUR( SIG N A L,, (s),r ) * v q,?:ENDS@,?)A 4 4 A l ( ~ ~ ~ ~ ~ ( ~ v~OCCUR(WAIT,,(~),?)) ~ ~ ~ ~ , ( . ~ ) , j )

+

which simply states that if a signal action occurs to the semaphore s during the time t , then no other signal or wait action can occur to the same semaphore s in a time interval ? that ends with t . Finally, we must also assert that execution of a signal action completes in the earliest possible time: OCCUR( SIGN A L,, (s),t ) * 3 i,j:BEGINS(tk(i),t) A ENDS(tk(j),t) A ( ( i = j ) V ( V k : i l k < j , 3 q,?:ENDS(tk(k).j) A (OCCUR(SIGNAL,(~),?) v OCCUR(WAIT,(~),?)))) which simply states that if a signal action occurs in time t then either t is equivalent to one timekeeper interval or in every timekeeper interval preceding the timzkeeper interval that ends with t some other signal or wait action is updating the value of the semaphore s. The order in which execution of the actions of a control module occur is defined by the functions HEAD and SUCC. The function HEAD is used when the control module is invoked to determine which actions are to begin execution with the beginning of the control module. More specifically, HEAD has one argument, the timekeeper unit interval in which the control module begins execution. It returns a subset of the control module's of actions that are to begin execution with the control module. The actions returned by HEAD are all performed in parallel. If HEAD returns the empty set. then the control module terminates after one timekeeper unit interval without performing any actions. The function SUCC is used to order the execution of the actions of the control module into parallel and sequential activities. SUCC returns a set of actions from A that are to be executed in parallel. It has two arguments: a set of actions, R , that are executed in parallel, and a

WILSEY A N D D A S G U P T A

48.3

A R C H I T E C T U R E S FOR S Y S T E M DESIGN FNVIKOI\;I\IFN~IS

timekeeper unit interval, t k ( i ). The arguments R and rk( i ) of SUCC are related in the following way: t k ( i ) is the timekeeper unit interval immediately following the complete execution of all of the actions in R. SUCC then returns the set of actions that are to begin execution immediately after the actions in R. Thus SUCC orders execution of the actions of the control module. Whenever the function SUCC returns the empty set, the control module terminates. Formally, we define execution of the actions of a control module as the event ACTION: OCCUR(ACTION(R,r),r’) 3 U ; : U; E R A OCCUR(a, , f ’ ) A ( V U ; : U, E R - {U;},3 f ; : BEGINS(!, , t r ) A IN(ri , t ’) A OCCUR(a, , t i ) ) A 3 k : MEETS(r’,tk(k)) A ((SUCC(R,tk(k)) # 0 A 3 t “ : MEETS(t’,r”) A

OCCUR(ACTION(SUCC(R,tk(k)),r),r”)) v (SUCC(R,fk(k)) = 0 A MEETS(t,tk(k)))) where R is a subset of the set of actions of the control module, t is the time interval in which the control module executes, and OCCUR ( s j , t i ) denotes the appropriate event for the statement s i . This axiom states that all of the actions in R occur in parallel. Once execution of the actions in R are complete, the next set of actions, as determined by the function SUCC, begin execution. Control modules are procedurally activated by call or fork actions of other control modules. Activation of a control module causes a subset of its set of actions to begin execution. After execution of the actions of a control modulc completes (i.e., the function SUCC returns the empty set) the control module becomes inactive. Formally, we define the activation of a control module by the event PROC-CM: OCCUR(PR0C-CM(M),r) * 3 i:BEGINS(fk(i),t) A ((HEAD(tk(i)) # 0 A 3 t‘ : BEGINS(r’,r) A

OCCUR(ACTION(HEAD(rk(i)),r),r’)) v (HEAD(tk(i)) = 0 A EQUALS(tk(k),t))) which indicates that if the function HEAD returns a nonempty set, then the event PROC-CM causes the event ACTION to occur. If, however, HEAD returns the empty set then PROC-CM occurs in one timekeeper unit interval without causing any other actions to occur. Fig. 7 is an example of a control module representing the instruction fetch/decode/execute cycle of a typical exo-architecture. The respective parts of the instruction cycle, fetch, decode, and execute, are modeled using either more primitive control modules or procedurally activated instances of functional modules.6 This control module characterizes the behavior of the instruction cycle “The choice is entirely dependent upon when. in the design cycle. iniplementation details are desired. The introduction of operational information (control modules) intn the design will introduce certain implementation constraints that may not be included if the design is expressed functionally (using instances of functional modules).

I=0=0

S2 = (ca//(decode))

succ(sz,I”)= s3 c =( C l )

C1= halt = 0

where t. I’, I”. and t”’ eachdenole some timekeeper unit interval.

Fig. 7 . An cxaniple of a control module

operationally. It states that the machine behaves in a manner characterized by the repeated application of the actions in S1 followed by S2 followed by S 3 . This behavior continues until, at the beginning of execution of the actions in S1, the condition ((halt = 0 ) = true) holds. Since the model is defined such that there can be control modules that are active upon machine startup, we require one additional axiom denoting which control modules are initially active. This axiom is defined as the event INIT: OCCUR(INIT,T,) * V cm, : cm, E CM,, 3 t, : BEGINS( TI,t, ) A OCCUR(PROC- CM(cm, ) ,t, ) . Stated more simply, the event INIT occurs once in the machine during the initial timekeeper unit interval, T I , and causes activation of all of the control modules of the set CM, to be activated in a time interval that begins with the initial timekeeper unit interval. V. Two EXAMPLES It should be clear from the examples in the previous section how the model can be used to represent both clocked and nonclocked machines at either the registertransfer or micro-architecture levels of abstraction. However, the use of the model at the gate and endo-architecture abstraction levels may require further clarification. Therefore, in this section, we present two examples to demonstrate the model at these two abstraction levels. The first example is concerned with modeling an SR flip-flop. The second example is of a pipelined machine with asynchronously communicating pipe stages. Fig. 8 is an example of a NOR gate implementation of an SR flip-flop. For demonstration purposes, we will assume that each NOR gate has a IO-ns switching time. The inputs and output of the top NOR gate are labeled so that all such gates can be modeled by a common functional module type with ports of the same name. Formally, the SR flip-flop of Fig. 8 is modeled in Figs. 9 and 10. Fig. 9 is a functional module type representing the behavior of a NOR gate. The input ports in-a and in-b are mapped onto the output port out in a manner that satisfies the pre/postcondition pair in E . The set of delays specifies that this mapping occurs over a period of 10 timekeeper unit intervals (representing, in this case, nanoseconds). Note that a functional module type by itself does not represent an active component that modifies the

I E E E TRANSACTIONS ON ('0MPLI'Tt.K~All)t.l) I)l-.SlGi% V O I .

5 . M A Y IYYO

D-unit

I-feeh

(?

Y. N O

Buffei

Q

s=

R-

Fig. 8 .

NOR

Fig. I I . Aaychronous pipe stages

gate implementation o f an SR Hip-Hop

A = < T , C, S. FM.IM. CM, CM,> T=

F M N ~=Rd.0.P. DF. E > I = (in-a. in-b)

-buf.

...I

,oZdputl

D F = (] E = () Fig. 9 . Functional module type description of a

F i g . 12. Architecture of a pipelined processor KOR

gate

IMs = SM = F M , , , R NA, = [ < S . i n - a > .

.~.our>)

TY = non-proccdural G = (true} IMR= NA = (..