07.pdf

Asynchronous Circuit Design. Chris J. Myers

ISBNs: 0-471-41543-X (Hardback); 0-471-22414-6 (Electronic)

Timed Circuits

Time is what prevents everything from happening at once.

--John Archibald Wheeler (1911- )

Dost thou love life?Then don’t squander time, for that is the stuff life is made of.

-Benjamin

Franklin

We must use time as a tool, not as a couch.

-John F. Kennedy

Time is a great teacher f but unfortunately

it kills all its pupils.

-Hector Berlioz

In previous chapters, synthesis of asynchronous circuits has been performed

using very limited knowledge about the delays in the circuit being designed.

Although this makes for very robust systems, a range of delay from 0 to in-

finity (as in the speed-independent case) is extremely conservative. It is quite

unlikely that large functional units could respond after no delay. It is equally

unlikely that gates and wires would take an infinite amount of time to respond.

When timing information is known, this information can be utilized to identify

portions of the state space which are unreachable. These unreachable states

introduce additional don’t cares in the logic synthesis problem, and they can

be used to optimize the implementation that is produced. In this chapter

we present a design methodology that utilizes known timing information to

produce timed circuit implementations.

259

260

TIMED CIRCUITS

7.1 MODELING TIMING

In this section we introduce semantics to support

the synthesis process. This is done using a simple

timing information

during

example.

Example 7.1.1 Consider the case where the shopkeeper actively calls

the winery when he needs wine and the patron when he has wine to sell.

To save time, he decides to call the patron immediately after calling the

winery, without waiting for the wine to arrive. Although the patron gets

quite irate if the wine is not there, the shopkeeper simply locks the door

until the wine arrives. So the process goes like this: The shopkeeper

calls the winery, calls the patron, peers out the window until he sees

both the wine delivery boy and the patron, lets them in, and completes

the sale.

After a while, he discovers that the winery always delivers its wine

between 2 and 3 minutes after being called. The patron, on the other

hand, takes at least 5 minutes to arrive, even longer when he is sleeping

off the previous bottle. Using this timing information, he has deter-

mined that he does not need to keep the door locked. Furthermore, he

can take a short nap behind the counter, and he only needs to wake

when he hears the loud voice of his devoted patron. For he knows that

when the patron arrives, the wine must already have been delivered,

making the arrival of the wine redundant.

The timing relationships described in the example are depicted in Figure 7.1

using a TEL structure. Recall that the vertices of the graph are events and

the edges are rules. Each rule is labeled with a bounded timing constraint of

the form [E,u], where Z is the lower bound and u is the upper bound on the

firing of the rule. In this example, all events are simple sequencing events and

all level expressions are assumed to be true.

In order to analyze timed circuits and systems, it is necessary to determine

the reachable timed states. An untimed state is a set of marked rules. A timed

state is an untimed state from the original machine and the current value of

all the active timers in that state. There is a timer ti associated with each

arc in the graph. A timer is allowed to advance by any amount less than its

upper bound, resulting in a new timed state.

Example 7.1.2 In the example in Figure 7.1, the rule T6 = ( Wilne is

Purchased, Cull Winery) is initially marked (indicated with a dotted

rule), so the initial untimed state is {ye}. In the initial state, timer t6

has value 0. Therefore, the initial timed state is ({Tg), t6 = 0). In the

initial state, the timer i!6 is allowed to advance by any amount less than

or equal to 3.

Recall that when a timer reaches its lower bound, the rule becomes satisfied.

When a timer reaches its upper bound, the rule is expired. An event enabled

by a single rule must happen sometime after its rule becomes satisfied and

before it becomes expired. When an event is enabled by multiple rules, it

must happen after all of its rules are satisfied but before all of its rules are

MODELING

TIMING

261

tl t2 *-.

f I -.I

Call Winery

~2~31 12~31 *..

Cal 1 Patron

Wine Arrives

\ I t5

Patron Arrives

..*:

~2~31 .-.

Wine Is Purchased

Fig. 7.1 Simple timing problem.

expired. To model the set of all possible behaviors, we extend the notion

of allowed sequences to timed states and include the time at which a state

transition occurs. These timed sequences are composed of transitions which

can be either time advancement or a change in the untimed state.

Example 7.1.3 Let us consider one possible sequence of events. If

t6 > 2, the initial rule becomes satisfied. If t6 reaches the value of

3, the rule is expired. The CaZZ Winery event must happen sometime

between 2 and 3 time units after the last bottle of wine is purchased.

After the CaZZ Winery event, timers ti and t2 are initialized to 0. They

must then advance in lockstep. When ti and t2 reach a value of 2, the

events Wine Arrives and CaZZ Patron become enabled. At this point,

time can continue to advance or one of these transitions can occur.

Let us assume that time advances to time 2.1, and then the event CaZZ

Patron happens. After this event, the timer t2 can be discarded, and

a new timer t3 is introduced with an initial value of 0. Time can be

allowed to continue to advance until timer tl equals 3, at which point

the Wine Arrives event will be forced to occur. Let us assume that the

Wine Arrives when tl reaches 2.32. The result is that tl is discarded

and t4 is introduced with value 0 (note that t3 currently has value

0.22). Time is again allowed to advance. When t4 reaches a value

of 2, the rule between Wine Arrives and Wine Is Purchased becomes

satisfied, but the wine cannot be purchased because the patron has not

yet arrived. Time continues until t4 reaches a value of 3 when the same

rule becomes expired, but the patron has still not arrived. At this point,

we can discard t4, as it no longer is needed to keep track of time. We

replace it with a marker

that that rule has expired.

Currently,

t3 is at a value of 3.22, so we must wait at least another

2.78 time units

~2~31

denoting

262

TIMED CIRCUITS

before the patron will arrive. When t3 reaches a value of 5, the rule

(Call Patron, Patron Arrives, 5, inf ) becomes satisfied, and the patron

can arrive at any time. Again, we can discard the timer t3, since there

is an infinite upper bound. After the patron arrives, we introduce t5,

and between 2 and 3 time units, the wine is purchased, and we repeat.

The corresponding timed sequence for this trace is as follows: (( [{r~},

t6 = 01, o), ([{7-g},

t6 = 2.221,

=2),

([{'rl,r2},

tl = t2 = 01, =2),

([{rl,r2},

tl = t2 = 2.11, 4.32), ([{ri,~~},

tl = 2.1, t3 = 01, 4.32),

([{n,rg},

tl = 2.32, t3 = 0.221, 4.54), ([{~3,~4},

t3 = 0.22, t4 = 01,

4.54), ([{r3,r4},

t3 = 3.22, t4 = 31, 7.54), ([{r3,r4}, t3 = 3.221, 7.54),

([{7-374}],

g-32),

([{7-4,7-g},

t5 = 01, 9.32),

([{r4,7-g},

ts = 2.21, 11.52),

([{7-S>,

t6 = 01, 11.52)).

Since time can take on any real value, there is an uncountably infinite

number of timed states and timed sequences. In order to perform timed state

space exploration, it is necessary either to group the timed states into a finite

number of equivalence classes or restrict the values that the timers can attain.

In the rest of this chapter we address this problem through the development

of an efficient method for timed state space exploration.

7.2 REGIONS

The first technique divides the timed state space for each untimed state into

equivalence classes called regions. A region is described by the integer com-

ponent of each timer and the relationship between the fractional components.

As an example, consider a state with two timers tr and t2, which are allowed

to take any value between 0 and 5. The set of all possible equivalence classes

is depicted in Figure 7.2(a). When the two timers have zero fractional com-

ponents, the region is a point in space. When timer tl has a zero fractional

component and timer t2 has a nonzero fractional component, the region is a

vertical line segment. When timer tl has a nonzero fractional component and

t2 has a zero fractional component, the region is a horizontal line segment.

When both timers have nonzero but equal fractional components, the region

is a diagonal line segment. Finally, when both timers have nonzero fractional

components and one timer has a larger fractional component, the region is a

triangle. Figure 7.2(a) depicts 171 distinct timed states.

Example 7.2.1 Let us consider a timed sequence from the example

in Figure 7.1. Assume that the winery has just been called. This

would put us in the timed state shown at the top of Figure 7.3(a).

In this timed state, timers tl and t2 would be initialized to 0 (i.e.,

tl = t2 = 0), and their fractional components would both be equal to

0 [i.e., f(h) = f(h) = 01. Th e g eometric representation of this timed

state is shown at the top of Figure 7.3(b), and it is simply a point at

the origin.

In this timed state, the only possible next timed state is reached

through time advancement. In other words, the fractional components

REGIONS

263

0 0 0 0 0

t2 (45)

0 0

0 0 0

0 0

t1(0,5)

h(O,5)

Fig. 7.2 (a) Possible timed states using regions. (b) Possible timed states using

discrete time. (c) Timed state represented using a zone.

for the two timers are allowed to advance in lockstep, and they can

take on any value greater than 0 and less than 1. The result is the

second timed state shown in Figure 7.3(a). This timed state can be

represented using a diagonal line segment as shown in the second graph

in Figure 7.3(b).

Once the fractional components of these timers reach the value 1,

we must move to a new timed state, increase the integer component of

these timers to 1, and reset the fractional components. The result is

the third timed state shown in Figure 7.3(a), which is again a point in

space.

Advancing time is accomplished by allowing the fractional compo-

nents to take on any value greater than 0 and less than 1, producing

another diagonal line segment. When the fractional components reach

1, we again move to a new timed state where the integer components

are increased to 2 and the fractional components are reset. In this

timed state, there are three possible next timed states, depending on

whether time is advanced, the wine arrives, or the patron is called.

Let us assume that time is again advanced, leading to the timed state

t1 = t2 = 2,f(t1) = f(t2) > 0.

In this timed state, the patron is called. In the resulting timed state,

we eliminate the timer t2 and introduce the timer t3 with value 0. The

fractional component of tl is greater than the fractional component of

t3, since we know that tl > 0 and t3 = 0 [i.e., f(tl> > f(ts> = O].

Pictorially, the timed state is a horizontal line segment, as shown in the

seventh graph in Figure 7.3(b).

In this timed state, either the wine can arrive or time can be ad-

vanced. Let us assume that time advances. As time advances, we allow

both fractional components to increase between 0 and 1. However,

since we know that tl’s fractional component is greater than t$s, the

resulting region in space is the triangle shown in the eighth graph in

Figure 7.3(b).

Once the fractional component for tl reaches 1, we must increase

the integer component for timer tl to 3. Note that in this timed state,

the fractional component can be anywhere between 0 and 1. Also note

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: