plain CS/EE 5750/6750: Asynchronous Circuit Design

# CS/EE 5750/6750: Asynchronous Circuit Design

### Chris J. Myers Lecture 4: Graphical Representations Chapter 4

Chapter Overview

• HDL's allow specification of large systems.
• Graphs allow pictorial representation of small examples, and they are used by virtually every CAD algorithm.
• The chapter discusses the following types of graphs:

• State machines
• Petri-nets
• TEL structures

Graph Basics

• A graph G is composed of a finite nonempty set of vertices V and a irreflexive symmetric relation, R (R Í V ×V).
• Since R is symmetric, (u,v) Î R Þ (v,u) Î R.
• E is the set of symmetric pairs, or edges (denoted uv).
• |V| is called the order of G.
• |E| is called the size of G.
• V(G) and E(G) are the vertex and edge sets for G.

A Simple Graph

• If e = uv Î E(G), e joins u and v.
• If uv Î E(G), u and v are adjacent vertices.
• If uv \not Î E(G), u and v are nonadjacent vertices.
• If e = uv Î E(G), u and v are incident with e.
• If uv and uw are edges and v ¹ w, uv and uw are adjacent edges.

A Unconnected Graph
Directed Graphs

• A directed graph, or digraph, D, is composed of a finite nonempty set of vertices, V, and an irreflexive relation, R (i.e., R Í V ×V).
• R does not need to be symmetric.
• E is the set of directed edges or arcs (denoted (u,v)).

A Simple Directed Graph
A Simple Labelled Directed Graph
Directed Graph Properties

• u-v path is an alternating sequence of distinct vertices and arcs beginning with u and ending with v.
• If there exists a u-v path, we say that v is reachable from u.
• If there exists either a u-v path or a v-u path but never both, then it is a directed acyclic graph (DAG).
• A digraph D is strongly connected if for every two distinct vertices u and v, there exists a u-v path in D and a v-u path in D.
• D is bipartite if there exists a partition of V into two subsets V1 and V2 such that every edge of G joins a vertex of V1 with V2.

A Cyclic Digraph
A Strongly Connected Digraph
A Synchronous FSM
An Asynchronous FSM
Finite State Machines

• I is the input alphabet;
• O is the output alphabet;
• S is the finite, non-empty set of states;
• S0 Í S is the set of initial (reset) states;
• d: S ×I ® S is the next-state function;
• l: S ×I ® O is the output function for a Mealy machine (or l: S ® O for a Moore machine).

Finite State Machine Diagrams

• FSM's are often represented using a labeled digraph.
• The vertex set contains the states (i.e., V = S).
• The edge set contains the set of state transitions (i.e., (u,v) Î E iff \$i Î I s.t. ((u,i),v) Î d).
• The labeling function is defined by next-state and output functions.

• Each edge (u,v) is labeled with i/o where i Î I and o Î O and ((u,i),v) Î d and ((u,i),o) Î l.

Passive/Active Shop

```shop_PA_1:process
begin
guard(req_wine,'1');        -- req_wine resets
guard(req_wine,'0');        -- req_wine resets
assign(req_patron,'1',1,2); -- call patron
assign(req_patron,'0',1,2); -- reset req_patron
guard(ack_patron,'0');      -- ack_patron resets
assign(ack_wine,'0',1,2);   -- reset ack_wine
end process;
```

Passive/Active Shop FSM

Figure
 00 01 11 10 s0 s0(-4,3) , 00 - - s1, 10 s1 s2, 11 - - s1(-4,3) , 10 s2 s2(-4,3) , 11 s3, 10 - - s3 s0, 00 s3(-4,3) , 10 - -

Burst-Mode State Machine
Burst-Mode State Machines

• V is a finite set of vertices (or states);
• E Í V ×V is the set of edges (or transitions);
• I = { x1, ¼, xm } is the set of inputs;
• O = { z1, ¼, zn } is the set of outputs;
• v0 Î V is the start state;
• in : V ® { 0,1 }m is value of the m inputs at entry to state;
• out : V ® { 0,1 }n is value of the n outputs at entry to state.

Input and Output Bursts

• Input burst is defined by transi : E ® 2I.

• xi Î transi(e) iff ini(u) ¹ ini(v)

• Output burst is defined by transo : E ® 2O.

• xi Î transo(e) iff outi(u) ¹ outi(v)

Maximal Set Property

• No input burst leaving a given state can be a subset of another leaving the same state.
• The behavior in such a state would be ambiguous.
• "(u,v), (u,w) Î E : transi(u,v) Í transi(u,w) Þ v = w.
• This restrication is called the maximal set property.

Maximal Set Property
Unique Entry Point

• A state must always be entered with the same set of input values.
• This restriction is called the unique entry point restriction.

Unique Entry Point
Extended Burst-Mode

• BM machines require prescribed order: inputs change, outputs change, and state signals change.
• In extended burst-mode (XBM) state machines, this limitation is loosened a bit by the introduction of directed don't cares.
• These allow one to specify that an input change may or may not happen in a given input burst.
• BM machines also are unable to express conditional behavior.
• To support this type of behavior, XBM machines allow conditional input bursts.

Directed Don't Cares

```Shop_PA_2:process
begin
guard(req_wine,'1');        -- winery calls
guard(req_wine,'0');        -- req_wine resets
ack_wine <= '0' after delay(1,5);   -- reset ack_wine
req_patron <= '1' after delay(1,5); -- call patron
wait until ack_wine = '0' and req_patron = '1';
assign(req_patron,'0',1,5); -- reset req_patron
guard(ack_patron,'0');      -- ack_patron resets
end process;
```

Directed Don't Cares
Directed Don't Cares

• A transition is terminating when it is of the form t+ or t-.
• A directed don't care transition is of the form t*.
• A compulsory transition is a terminating transition which is not preceded by a directed don't care transition.
• Each input burst must have at least one compulsory transition.

Directed Don't Cares
Modified Maximal Set Property
Conditional Input Bursts

```Shop_PA_2:process begin
guard(req_wine,'1');
shelf <= bottle after delay(1,2);
wait for 5 ns;
assign(ack_wine,'1',1,5);
guard(req_wine,'0');
if (shelf = '0') then
ack_wine <= '0' after delay(1,5);
req_patron1 <= '1' after delay(1,5);
wait until ack_wine = '0' and req_patron1 = '1';
guard(ack_patron1,'1');
assign(req_patron1,'0',1,5);
guard(ack_patron1,'0');
```

Conditional Input Bursts

```     elsif (shelf = '1') then
ack_wine <= '0' after delay(1,5);
req_patron2 <= '1' after delay(1,5);
wait until ack_wine = '0' and req_patron2 = '1';
guard(ack_patron2,'1');
assign(req_patron2,'0',1,5);
guard(ack_patron2,'0');
end if;
end process;
```

Conditional Input Bursts

• A conditional input burst includes a regular input burst and a conditional clause.
• A clause of the form < s- > indicates that the transition is only taken if s is low.
• A clause of the form < s+ > indicates that the transition is only taken if s is high.
• The signal in the conditional clause must be stable before every compulsory transition in the input burst.

Conditional Input Bursts
Modified Maximal Set Property
No XBM Machine

```Shop_PA_lazy_active:process
begin
guard(req_wine,'1');        -- winery calls
guard(ack_patron,'0');      -- ack_patron resets
assign(req_patron,'1',1,5); -- call patron
guard(req_wine,'0');        -- req_wine resets
assign(ack_wine,'0',1,5);   -- reset ack_wine
assign(req_patron,'0',1,5); -- reset req_patron
end process;
```

Illegal XBM Machine
Petri-Nets

• A Petri-net is a bipartite digraph.
• The vertex set is partitioned into two disjoint subsets:

• P is the set of places.
• T is the set of transitions.

• The set of arcs, F, is composed of pairs where one element is from P and the other is from T (i.e., F Í (P ×T) È(T ×P)).
• A Petri-net is áP, T, F, M0 ñ where M0 is the initial marking.

Petri-net for Shop with Infinite Shelf Space
Presets and Postsets

• The preset of a transition t Î T (denoted ·t) is the set of places connected to t (i.e., ·t = { p Î| (p,t) Î F }).
• The postset of a transition t Î T (denoted t ·) is the set of places t is connected to (i.e., t · = { p Î| (t,p) Î F }).
• The preset of a place p Î P (denoted ·p) is the set of transitions connected to p (i.e., ·p = { t Î| (t,p) Î F }).
• The postset of a place p Î P (denoted p ·) is the set of transitions p is connected to (i.e., p · = { t Î| (p,t) Î F }).

Markings

• A marking for a Petri-net is a vector M = (m(1), ¼, m(n)) of natural numbers having a component m(i) for each place pi.
• Markings can be added or subtracted using vector arithmetic.
• They can also be compared:
 M ³ M¢
 iff
 m(i) ³ m¢(i) for every i = 1, ¼, n.
• For a set of places, A Í P, CA is the characteristic marking of A:
 CA(i)
 =
 if pi Î A then 1 else  0.

Transition Firings

• A transition t is fireable under the marking M if M ³ C·t.
• In other words, m(i) ³ 1 for each pi Î ·t.
• The firing transforms the marking as follows (denoted M [ t ñM¢):
 M¢
 =
 M - C·t + Ct ·
• When a transition t fires, a token is removed from each place in its preset, and a token is added to each place in its postset.
• We denote the set of all markings reachable from a given marking by [ M ñ.

Example Firing Sequence
Place Capacity

• This Petri-net has an infinite state space.
• A series of produce and send transitions fills the shelf by any arbitrary amount.
• If we restrict the capacity of the shelf, the state space is finite.

1-Safe Petri-Nets

• A Petri-net is 1-safe if a marking can never have more than one token per place.
 "pi Î P, "M Î [ M0 ñ: m(i) £ 1
• The capacity of all places must be infinite.

1-Safe Petri-net
Free Choice Petri-Nets

• A Petri-net is free choice if and only if every pair of transitions that share a common place in their preset have only a single place in their preset.
 "t,t¢ Î T, t ¹ t¢: ·t Ç·t¢ ¹ ÆÞ |·t| = |·t¢| = 1
 "p, p¢ Î P, p ¹ p¢: p ·Çp¢· ¹ ÆÞ |p ·| = |p¢·| = 1
 "p Î P, "t Î T : (p,t) Î F Þ p · = { t } Ú·t = { p }

Free Choice Petri-nets
State Machines

• A Petri-net is a state machine if and only if every transition has exactly one place in its preset and one place in its postset.
 "t Î T : |·t| = |t ·| = 1

Marked Graphs

• A Petri-net is a marked graph if and only if every place has exactly one transition in its preset and one in its postset.
 "p Î P : |·p| = |p ·| = 1

Reshuffled Passive/Lazy-Active Wine Shop
Wine Shop with Two Patrons
Interface Nets (I-Nets)
Interface State Graphs (ISG)
Encoded Interface State Graphs (EISG)
C-element Implementation

Figure Figure
 a b c¢ 0 0 0 0 1 c 1 0 c 1 1 1

I-Net for an Arbiter
Signal Transition Graph (STG)
STG Restrictions

• An STG is live, if from every reachable marking, there exists a sequence of transitions such that any transition can be fireable.
 "M Î [M0ñ, "t Î T, \$M¢ Î [Mñ: M¢ ³ C·t
• An STG is 1-safe if there does not exist any reachable marking in which a place can contain more than a single token.
 "pi Î P, "M Î [ M0 ñ: M(i) £ 1
• An STG is persistant if for all arcs a* ® b*, there must be other arcs that ensure that b* fires before the opposite transition of a*.

Liveness
Safety
Persistency
STG Restrictions

• An STG has a consistent state assignment if the transitions of a signal strictly alternate between +'s and -'s.
• An STG has a unique state assignment if no two different markings have identical values for all signals.
• An STG has single-cycle transitions if each signal name appears in exactly one rising and one falling transition.

Consistent State Assignment
Unique State Code
Change Diagrams

• Change diagrams are composed of three different types of arcs:

• Strong precedence arcs to model conjunctive (AND) casaulity.
• Weak precedence arcs to model disjunctive (OR) casaulity.
• Disengageable strong precedence arcs for initial behavior.

Example Change Diagram
Timed Event/Level (TEL) Structures

• AFSMs cannot model arbitrary concurrency.
• Petri-nets have difficulty to express signal levels.
• Timed event/level (TEL) structures are a hybrid graphical representation method which are both capable of modelling arbitrary concurrency and signal levels.

Timed Event/Level (TEL) Structures

• N is the set of signals;
• s0 = {0,1}N is the initial state;
• A Í N ×{+,-} È\$ is the set of atomic actions;
• E Í A ×(N={0,1,2...}) is the set of events;
• R Í E ×E ×N ×(N È{¥})× (b:{0,1}N ® {0,1})
is the set of rules;
• # Í E×E is the conflict relation.

Rules

• e = enabling event,
• f = enabled event,
• ál,u ñ = bounded timing constraint, and
• b = a sum-of-products boolean function over the signals in N.

Rules

• A rule is enabled if its enabling event has occurred and its boolean function is true in the current state.
• A rule is satisfied if it has been enabled at least l time units.
• A rule becomes expired when it has been enabled u time units.
• Excluding conflicts, an event cannot occur until every rule enabling it is satisfied, and it must occur before every rule enabling it has expired.
• Special care must be taken when a rule becomes disabled.

Conflict Relation

• The conflict relation, #, is used to model disjunctive behavior and choice.
• When two events e and e¢ are in conflict (denoted e#e¢), this specifies that either e or e¢ can occur but not both.
• If two rules have the same enabled event and conflicting enabling events, then only one of the two mutually exclusive enabling events needs to occur to cause the enabled event.
• When two rules have the same enabling event and conflicting enabled events, only one of the enabled events can occur.

Example TEL Structures
TEL Structure for Wine Shop with Two Patrons
Summary

• Finite state machines (AFSMs, BM, and XBM).
• Petri-nets (I-nets, STGs, and Change Diagrams).
• TEL structures.

File translated from TEX by TTH, version 2.22.
On 2 Feb 2000, 15:48.