1
______
MODELING OF ASYNCHRONOUS CIRCUITS
USING
PETRI NETS
EXTRA CREDIT PROJECT
EE552
PROF JAMES ELLISON
ANAND KUMAR AKELLA
Email:
I alone prepared and wrote this project. I received no help from anyone one else. This material is not copied or paraphrased from any other source except where specifically indicated. I grant my permission for this project to be placed on the course homepage during future semesters. I understand that I could receive an F for the course retroactively, even after graduation, if this work is later found to be plagiarized.
The extra credit I did, is basically a study of the five papers which I quoted in the Bibliography, and taking excerpts from them which are relevant to our coursework. All the matter included is correct to the best of my knowledge, and I sincerely apologize for any mistakes which I made.
The Website quoted in the Bibliography has extensive material on Asynchronous logic, and I got some of the papers which I stated from that site.
Anand Kumar Akella
STRUCTURE OF THIS PROJECT
1. Why Petri nets……………………………………………………………………….…4
2. Definition of Petri nets………………………………………………………..………..5
3. Firing a Petri net……………………………………………………………….……….7
a. Source and Sink transitions……………………………………..…………..7
b. Pure and Ordinary Petri nets…………………………………….………….7
c. Infinite and Finite capacity nets………………………………….………….8
4. Modeling using Petri nets…………………………………………………..…………9
a. Conflict…………………………………………………………………..……10
b. Parallel Activity…………………………………………………………..…..11
c. Confusion……………………………………………………………….……12
5. Modeling event based elements……………………………………………….……13
a. C-element……………………………………………………………….…...13
b. X-OR……………………………………………………………….…………13
c. Toggle………………………………………………………………..……….14
6. Modeling level based elements…………………………………..………………….15
a. Inverter…………………………………………….………………………….15
b. OR……………………………………………………..………………………16
7. Modeling a basic communication protocol…………………..……………………..17
8. Modeling Micropipeline FIFO…………………………………….………………….18
9. Properties of Petri nets: Introduction to Analysis of Petri nets…………..……….21
10. Conclusions…………………………………………………………..………………..22
11. Bibliography……………………………………………………………..……………..23
1. WHY PETRI NETS?
This project deals with Modeling of various Asynchronous circuits using Petri nets. Some important reasons why Petri nets are used are listed below
l The Graphical representation used in Petri nets makes it attractive to use than the algebraic notation, which is less intuitive and cumbersome.
l The descriptive power of Petri nets allows a reasonable modeling of a wide range of Asynchronous Circuits, whether they are built in two phase (micropipeline) or four phase (logic gate based) design styles.
l Timing Analysis and Synthesis of Petri nets is easy and systematic.
l Petri nets can be used to check potential hazards in circuits.
l Petri nets can be used as a modeling language to perform formal synthesis.
l Practical asynchronous circuits are not completely speed independent, and Petri nets can be used to model them very efficiently.
Let us now study the modeling of asynchronous circuits using Petri nets.
2. DEFINITION OF A PETRI NET
A Petri net is a kind of graph, which is directed, i.e., the flow of control is pre-specified. It has an initial state. The initial state is called the “Initial Marking”, M0 of the Petri net.
A Petri net consists of two kinds of nodes, called Places and Transitions. Places are drawn as circles and transitions are drawn as bars or boxes in the graph.
Arcs are used to join them, from place to a transition, or from a transition to a place (Fig 1).
.
FIG 1
Arc with weight
Place and a Token
Transition ( can be represented in either of the two ways)
An example of a simple Petri Net Graph
All the arcs are labeled with their weights, which are positive integers. Also, a k-weighted arc can be interpreted as a set of k parallel arcs. (Unity weights are usually omitted).
Thus, broadly speaking, a Petri net is directed, weighted, bipartite graph.
A “Marking” assigns a place p with a non-negative integer k, which implies
that, the place has k tokens in it.
A Marking is denoted by M, an m-vector, where m is the total number of places. M (p) denotes the number of tokens in place p. Generally in Modeling, places represent a condition and transitions represent events. The presence of a token in a place is interpreted as the truth of that particular condition.
Interestingly enough, there is only one rule in Petri Net Theory: The rule for
Transition enabling and Firing.
Let us discuss more about this in the next section.
3. FIRING A PETRI NET
The state of the Petri Net changes according to the following Transition (firing) rule.
· If each input place has at least one token, then the transition gets enabled.(if the weight of the arc is w, then each input place should have at least w tokens to get enabled)
· Depending on whether the event takes place or not, a given enabled transition may or may not get fired.
· If an enabled transition gets fired, then, w tokens are removed from each input place, and w tokens are added to each output place of the transition, w being the weight of the arc.
A transition without an input place is called a Source transition .
A transition without an output place is called the Sink transition.
Thus a source transition is unconditionally enabled, and a sink transition consumes tokens (but does not produce any).
Self loop: A place p and a transition t is said to be a self loop if p is both an input and output place to t.
The analysis of Petri nets having self loops is somewhat difficult than the ones which don’t have them.
A net without self-loops is called Pure Petri net.
A net with all arc-weights 1 is called an Ordinary Petri net.
FIG 2 Example of a water molecule 2H2 + O2 → 2H2O . Note the weights on the arcs.
If a Petri net can accommodate infinite number of tokens, it is called an Infinite capacity net and if an upper limit is kept on the number of tokens in a place, it is said to have a Finite capacity.
There is also another rule for the Finite capacity net, that after the enabling and firing of a transition, the number of tokens at an output place cannot exceed the upper limit fixed. This is known as the Strict Transition Rule.
4. MODELING USING PETRINETS
Petri nets are used for modeling purposes in many areas, and most importantly, it is one of the very few tools which is used to model Asynchronous logic circuits. The models so generated are very simple and intuitive, and above all very easy to analyze and synthesize.
Initially, an example, a vending machine is shown in FIG 3, which accepts nickels and dimes and sells 15 cent and 20 cent candies. From this, we can intuitively understand the rationale behind a place, transition and triggering (or firing).
FIG 3
Note that each transition has one incoming and one outgoing arc. The subclass of Petri nets having this particular property is known as a State Machine.
In the literature, we come across some technical terms which are very important for studying modeling. Some of them are listed below.
Conflict: If a place p1 has two or more output transitions, it is known as a Conflict, Decision or Choice. The figure shown below illustrates a very simple case of a conflict.
FIG 4
the token takes the path whose transition triggers first, and that’s why its called a conflict.
Parallel activity: From figure 5, we can notice that the transitions t2 and t3 are initiated when t1 gets triggered, and end when t4 is triggered. This is known as parallel activity.
FIG5
Note that in this case, the transitions t2 and t3 are called Concurrent as one transition may fire before or after or in parallel with each other.
Again if in a Petri net, there is exactly one incoming arc and one outgoing arc from a place, then it is known as a Marked Petri net. In marked graphs, concurrency will be present, but there will be no decisions (conflicts)
Two events e1 and e2 are in conflict if either e1 can occur or e2 can occur, but not both and they are said to be concurrent if they can occur in any order, without conflict.
Confusion: A situation in which conflict and concurrency are mixed is known as Confusion.
Two types of confusion are shown, Symmetric and Asymmetric, the figures of which are self-explanatory.
FIG 6
In the next section, a few basic elements are modeled using Petri nets.
5. MODELING EVENT BASED ELEMENTS
C-element: It implements AND causality or synchronization between different processes. The Boolean equation describing its behavior is
y = x1x2 + y(x1+x2)
where y is the output and x1 and x2 are the two inputs.
FIG 7
Merge or XOR: It implements the OR causality between the input changes, but requires that only one input can change at a time. Inputs must thus arrive on a mutually exclusive basis.
FIG 8
Toggle: It switches between two outputs for every input change, as a complementary flip flop. It is used to unconditionally alternate between two possible directions of control flow. Whenever a token comes to the place p, the net changes the output.
FIG 9
p
Thus, we notice that, in all the above models,
· Places are associated with input or output wires and the transitions are associated with signal events.
· Since we do not distinguish between rising and falling edges of transitions in the two phase discipline, it is possible to associate one net transition with both.
· All the elements are made such that, they can be implemented in communication protocols.
6. MODELING LEVEL BASED ELEMENTS
Any efficient circuit design contains a combination of two-phase and four-phase signaling styles. So discussing level based elements is very necessary as they are used in four phase signaling. Level based modeled circuits are also called Circuit Petri nets. To understand these completely, a good knowledge of Signal Transition Graphs is required. In these, each signal y is associated with two places, representing its two logical states.
The groups of transitions labeled with y+ and y- are connected to these places in such a way that proper enabling or firing coupled with the appropriate labeling mechanism, adequately represents AND or OR conditions in logic. Self loops are often used in these designs.
FIG 10
Thus, we can see from the given two examples that, interpreting the logical behavior of the Petri net is not very obvious, and requires knowledge of the state-of-the-art, and a lot of training to identify the logical function. The figures given here were just meant to show that we can implement four phase logic using Petri nets, but in-depth analysis of these is outside the scope of my paper.
FIG 11
Another important point to note is that, if we go further into this, we can model all the circuits made up of these logic-gates using this technique(This is further explained in paper 4 listed in the bibliography). Many methods have been developed by which, we can find out the hazards and eliminate them in these circuits using Petri nets.
7. COMMUNICATION PROTOCOLS
The discussion is limited to two phase protocols only. A very basic model for a protocol is shown (FIG 12). The diagram is very self explanatory, and we can see that by playing with the token at ready-to-send and ready-to-receive, we can demonstrate how a communication protocol works. Thus, Petri nets are very effective in modeling communication protocols.
FIG 12
8. MODELING A MICROPIPELINE FIFO
The diagram of a Basic Sutherland Micropipeline FIFO is shown below (FIG 13). It is assumed that the reader knows the basic operation of the micropipeline FIFO.
FIG 13
We can see that, the basic micropipeline FIFO is based on a data path storage element, known as the Capture Pass Element (FIG 14).
Synchronization between data and control in this FIFO is done using the bundled data technique, which requires explicit delay elements between the stages. These delay elements compensate for the delays and signal skewing in the bundles of data wires.
Dual rail signaling can be used, but as it is expensive in terms of area and power consumption, this option is generally discarded.
FIG 14
Capture pass element
The control circuit for two adjacent FIFO stages is shown in FIG 15 and its corresponding Petri net is also given. Delay elements offer some redundancy to the given circuit. We can reduce the redundancy by properly removing them, and the reduced model is also shown in the diagram. The Petri net so modeled is persistent and safe and above all, it is hazard free.
Two parameters determine the performance of the pipeline.
1. Latency: It is the time the pipeline takes to propagate a datum through the stages.
From the figure, we can see that latency is the time taken from Rin to Rout.
Reverse latency: It is the time taken by the acknowledgement signal to pass through the stages. Sometimes, reverse latency is calculated instead of latency, and hence, it is an important parameter.
FIG 15
2. Cycle Time: The time it takes one stage of a pipeline to process one value and accept the next one.
Throughput: The maximum cycle time in a micropipeline determines the throughput.
9. PROPERTIES OF PETRINETS
Until now we discussed the various aspects of modeling Petri nets. Now the immediate question is, what can we do with these models? We can answer this question if we study some properties of Petri nets, which will allow us to analyze them.
There are two types of properties of Petri nets- Behavioral and Structural
This classification is based on the fact that, behavioral properties are dependent on the initial marking, whereas structural properties are not.
By getting a broader idea of the properties of Petri nets, we can analyze Petri nets analytically as well as mathematically. This discussion is not in the scope of the paper.
My actual intention when I started this paper was to work on the “Applications of Petri nets in the Modeling, Analysis, and Synthesis of Asynchronous circuits”. But, due to constraints like time and the load of the other courses which I took, and as the topic which I chose was too “Herculean” for me, I stopped my work here.