12,076,206 members (43,156 online)
alternative version

12.4K views
11 bookmarked
Posted

# Primef: Free Choice Petri net Library in C++

, 17 Mar 2014 BSD
 Rate this:
Free choice Petri net library in Policy-based design. Not only Concurrent software but also hardware support is available.

## Introduction

I am a reader of the book 'Modern C++ Design' written by Alexandrescu, Andrei. If someone wants to learn from "What is Policy based design?", you had better read it. I am also a reader of the book 'Free Choice Petri Nets' written by Jo:rg Desel and Javier Esparza especially Chapter 7 'Reduction and Synthesis'. This book is rare so in this article, the practical (free choice) Petri nets and the ability of synthesis nets has been explained. Well, someday after I learned policy, I imagined the assumption that policies are classified by prime numbers each of that aggregates each number of policies corresponding to the design patterns. And another day, I am aware 'policy' is similar to 'Process' in VHDL (hardware language). Hardware is intrinsically concurrent so I decide to introduce the concurrent modeling free choice Petri net is well-studied and the subclass of Petri net.

## Background

I am the author of the article primel.h and in it I ignore one axiom among Peano axioms. That is about the recursion axiom. Why? Because it is algorithm in user codes call the library functions. But I've found some regularities in user codes so the modeling follows.

Frankly speaking, a recursion is:

`array[n+1]=function(array[n]);`

then its data flow is checked out:

1. `array[n]` is invalid and not calculated so function is suspended.
2. `array[n]` is valid because `array[n]` is initialized or function`(array[n-1]) `is completed.
3. `array[n]` has evoked function(`array[n]) `but under calculation.

Beside it, what is Petri net is confirmed below: Petri net consists of nodes and arcs. Two kinds of nodes are placed and transitions exist. Arcs has directions and connect from every node to every node, but a connected node pair (from,to) must be either (a place, a transition) or (a transition, a place). In addition to the net, the tokens play a role when these put on the places. A placed token will fire when a certain synchronizing condition have been satisfied, then the transition node starts to work. Places concerned with the synchronization decrease each owning tokens. After the transition works, tokens are passed to each connected place by arcs to evoke the place job with passed data from the transition node. After every place completes its job, a token is added to every place implying its place data is ready. And this behavior repeats infinitely.

Well, this returns to the recursion. Can the recursion translate into the Petri net? Yes, it's very easily. First (2) corresponding to the token is put on the place node. (3) corresponds to the transition and the place jobs. (1) is not explicitly coded because the number of (1) state is infinite so implicitly treated in the transition node as only next data array[n+1]can start its ready waiting. Further `array[] `doesn't exist. In conclusion one place node, one transition node, one the place to the transition arc, and one the transition to the place arc, and one token put on the place are the simplest Petri net can calculate the mathematical recursion. Someone complains practical Petri nets are more complicated, but well-formed Petri net is restricted both live means if the token has decreased, sooner or later the token is added through the token propagation and bounded means if the token has not decreased, the number of the tokens bounded to the maximum number because of no token addition through no token propagation. Thus well-formed Petri net loops infinitely without the overflow. So (well- formed) Petri net should be the loop of the recursion.

## Using the Code

First of all, Primef library includes the three policy based host classes and these are the mathematical subclasses of the another class, class `Primef2 `of class `Primef3 `and class `Primef3 `of class `Primef5 `respectively. But the callback manner is quite the same. When tokens in the net were fired, every number of the place tokens is decremented and the correspondent transition node starts to callback the user implementing code. After the callback returns, tokens are propagated to its place nodes but number of the tokens of each place doesn't increase at once. First this library callbacks the user implementing code and second number of the tokens of their places increase although the number of the increasing place tokens is return value of latest callback of the place thus in usual case callback function returns `1 `and in special case returns the number of the ordered data in the reordered FIFO returned so out of order data is treated as execution is not completed. Also its member methods are quite the same that are `Mark()`, `MakeNets()`, `RemoveNet()`, `Implement()`, and `ImplementIs()` (except notifier concernings). But the nets parameter in `MakeNets` (class `NodeBase2` (or `NodeBase3` or `NodeBase5`) **nets) is deferent and practically each class restricted to each BNF grammar in which the nets represent. (BNF detail is explained in policy section.) `Mark(long num)` is for putting `num `number of tokens. Once token is put tokens run through the net under the race condition. It must be remembered that if you want stop Petri net infinite loop, you must achieve in the callback code called when a token arrived. Codes breaking the net out of it is unsafe. `RemoveNet()` makes its node to all unconnected. Unconnected node cause dead link so behavior of its net is sometimes deadlock termination, so use of this function is recommended when the net terminates. `Implement()` is for setting its callback function. It also can be done call `Node(T *imp)` (constructor) with the imp variable. Again, this function call is also under the race condition, be careful. `ImplementIs()` returns its callback function object.

The basic program flow is as follows:

```//NodeBase::Construct();
Call first for initialize
|
V
// *a4p.MakeNets(net);
Chose one node is *a4p in this sample
and load the Petri net is the net follows the node.
|
V
//for(i=0;i<6;i++) {
p6=a4pi.a6.Front();
a4pi.a6.Write(p6);
}
load the initial data to the FIFO correspond to what the data is.
|
V
//a0p.Mark(2);
put tokens on the place using Mark() function call.
|
V
All Petri nets run in the threads.
This function returns when all Petri nets dead means
no fire occurs in their tokens placements. (In practice it is dead lock
so it is right that this function returns.)
|
V
//NodeBase::Destruct()
All petri nets are destructed and return to the condition before Construct()```

#### Policies

`Primef2 `synthesis rule:

```psiS
Policy choices:
//template <class T> class Bridge
//template <class T> class Proxy```

BNF grammar for nets** in `Primef2::MakeNets `(class `NodeBase2 `**nets)

```<net>:='class NodeBase2 '<net name>'**={'<nodes>'NULL};'
<nodes>:=''|<pointer to Proxy policy node>','<nodes> ```

Recursions can express in the simplest Petri net but if lemmas are used in the mathematical proof, the concurrent execution in each lemma should be available. Thus the synthesis rule is used to express the code about its place is concurrently executable and one transition node is for the synchronization means all lemmas in the proof are ready to continue.

Anyway, do this Petri nets communicate over the internet? Yes, they can when parameters setup in the callback user function are prepared. The Related `enum `is `enum `domain, the related `static `function is `Bridge::sendTo()`, and related callback methods deployed to Implement are `BeforeBlock()` (`Bridge `transition only) and `Execute()`. `Enum `domain is the return parameter of `BeforeBlock()` and decides the notifying receiver is inserted or not between `BeforeBlock() `and `Execute()` callback successively.

• `return domain::noNotify;` causes immediate callback to `Execute()`
• `return domain::localNet;` causes wait for `Mark()` call to this `Bridge `increases its internal place counter and fire to callback to `Execute()`

`return domain::crossDomain;` causes receive an OS supported socket prepared in the `Datagram::rec` passed when `BeforeBlock(&rec)` returned. After socket receives some information (data or error) `Execute(&rec)` is called back with `Datagram::rec` changed. `SendTo()` also sends an OS supported socket if `Datagram::snd` is prepared If an OS supported socket is not used, `Datagram::parm` is dummy; These are advanced information in transition nodes.

`Primef3 `synthesis rule:

```psiA
policy choices:
//template <class T> class Composite
//template <class T> class Decorator
BNF grammar for nets** in Primef3::MakeNets(class NodeBase3 **nets)
<net>:='class NodeBase3 '<net neme>'**={'<nodes>'NULL};'
<nodes>:=''|<pointer to Composite policy node>','<nodes>|
<pointer to Adapter policy node>','<pointer to connected node as output>','
<nodes>'NULL,'|
<pointer to Decorator policy node>','<pointer to connected node as input>','
<nodes>'NULL,'```

If an assumption of lemma is from another lemma result, the pipeline concurrent execution is available. It is called Marked graph and/or T-System. In short, the execution in the net is divided step by step and required data written in a step is synchronized with another but the depending execution starts as fast as it can. Using this template class is quite similar to `Primef2`, only the needed thing is how to write the nets array in the proper grammar. Composite is for writing each step so repeats ->Proxy->Bridge->Proxy->Bridge->... and executes infinite loop. But another looping execution is also available although it synchronized with the main loop. Adapter is for making a side path without backward referencing and the path means the looping branch starts from Adapter node and ends to Composite node just before the Adapter node declared. Decorator is also for making a path without backward referencing but the first declared node is endpoint of the side path and startpoint of the side path is Composite node just before the Decorator node declared. Totally backward referencing is avoided.

`Primef5 `synthesis rule:

```psiT
policy choices:
//template <class T> class Template
//template <class T> class Observer
//template <class T> class Strategy
//template <class T> class Command
//template <class T> class Cor```

BNF grammar for nets** in `Primef5::MakeNets` (class `NodeBase5 **nets`):

```<net>:='class NodeBase5 '<net name>'**={'<nodes>'NULL};'
<nodes>:=''|<pointer to Template policy node>','<nodes>|
<pointer to (Template, Strategy, or Cor) and Bridge policy node>','
<observer choices>','<nodes>|
<pointer to Proxy policy node>','
<command choices>','<nodes>
<observer choices>:=''|<pointer to Observer policy node>',
'<place node pointers>'NULL,'<strategy side paths>'NULL,'<observer choices>
<strategy side paths>:=''|<pointer to Strategy policy node>',
'<place node pointers>'NULL,'<nodes>'NULL,
'<restricted nets>'NULL,'<strategy side paths>
<place node pointers>:=''|<pointer to Proxy policy node>','<place node pointers>
<restricted nets>:=''|<pointer to (Template and Adapter),
Observer, or Command policy>',' <nodes>','<restricted nets>
<command choices>:=''|<pointer to Command policy node>','
<pointer to (Template, Strategy, or Cor) and Bridge policy node>','
<place node pointers>'NULL,'<Cor side paths>'NULL,'<command choices>
<Cor side paths>:=''|<pointer to Cor policy node>','<place node pointers>'NULL,'
<nodes>'NULL,'<restricted nets>'NULL,'<Cor side paths>```

`Primef5 `make it available to use the free choice Petri net consisted of the clusters each of them is grouped places and grouped transitions. Grouped places means the same as in `Premef3 `which is going to make fire and to propagate to the transition node. But in `Primef5`, the number of the transition nodes is not one so the propagation occurs to one of them chosen freely. This is why the net is called 'free choice'. But choosing freely requires fairness and truly random choosing is very difficult so only round robin algorithm is implemented. Thus, `Primef5 `is for compressing the net as follows.

`Primef3 `(before compression):

```t0->p0->t1->p1->t0->p0->t2->p1->t0->p0->t3->p1->t0(LOOP)
Primef5:
/---->t1----\
t0->p0--->t2--->p1->t0(LOOP)
\---->t3----/```

How to program net** array is complicated. First, check the target net can't express in T-system because the transition node is not one in the cluster or if it is T-system, Template policy can be chosen and write quite the same as in `Primef3`. If it includes some free choices, you must remove a CP-subnet from the net. CP-subnet is defined a subnet of the net that starts from a way-in transition node which all pre-set place nodes don't belong to the CP-subnet and ends some way-out transition nodes which all post-set place nodes don't belong to the CP-subnet. If the CP-subnet includes another CP-subnet, you must remove the included one first. Then if the rest net is not a T-system, you must repeat removing CP-subnet. Finally, T-system is the rest and you can start to write the net with Template policy nodes. Then if you write the node that was connected to a certain CP-subnet and with its node all of nodes that was connected to the CP-subnet is prepared you may branch out writing the subnet. If the CP-subnet node connected to the latest node is a way-in transition the CP-subnet starts from Observer policy node just after the Template policy transition node, or if the last CP-subnet node is a way-out transition the CP-subnet starts from Command policy node just after the Template policy place node. Observer policy node is followed the way-out node connections from the way-in transition node is Observer policy node itself, one NULL pointer, the Strategy policy nets start from Strategy policy node, nodes connections from the way-out node is Strategy policy node itself, net connections between the way-in node to the way-out node like Decorator policy manner in Primef3, one NULL pointer, and additional connection to the way-out node like the Adapter policy manner in Primef3. If the way-out node is not one, repeat adding Strategy policy node and its net connection. This is the case the CP-subnet node is the way-in transition just before adding the CP-subnet. if the CP-subnet node is the way-out transition, start from Command policy node, where the Template policy node is included into the cluster along with the way-in transition, and CP-subnet expressing like that of the Observer policy case except use Cor (Chain of responsibility) policy node instead of Strategy policy node.

main.c is the sample of 1-bounded Petri net in which the number of tokens marked on the place node is limited to 0 or 1 so the race condition on the same node is eliminated. (a race condition needs at least 2 tokens.) It is corresponding to the pipeline program technique. In this sample a key input loop net and one 2-stage pipeline calculator is implemented and is notifying each other.

```Petri nets in main.c
--->: Arc between nodes          ...>: Notify
P: Place                         T:Transition
/------------------------------------\
|                                    |
\->ek---------------->kt-------------/
(P,job less) /....->\............................\
.    (T,key enter and wait)         .
(notify).                                   .(notify)
.                                   .
.                                   .
.                                   .
\.\ <.............................../
/----------------pb<--------------\  /--->ep-----------\
|               (P,back side sync)|  |   (P,evaluator) |
\->pt---------\      /------>pst--/  |                 \-->et-------------\
(T,job less)|      |   /-->   -----/                   (T,Result or not)|
|      |   |  (T,data pass)                                 |
\->pp--/   |                                                |
(P,parser)\--------------ee<-------------------------------/
(P,job less)```

main2.c is the sample of Fibonacci number. It is defined that:

```a[0]=0;
a[1]=1;
a[n]=a[n-2]+a[n-1] where n>=2
But this can be rewritten such that
a[0]=0;
a[1]=1:
a[2]=1;
a[3]=2;
a[4]=3;
a[5]=5;
a[n]=-a[n-6]+2*a[n-4]+2*a[n-2] where n>=6```

It must be checked out that in the latter `a[n]` of odd number `n `is calculated from `a[k]`s where `k `is an odd number, and `a[n]` of even number `n `is calculated from `a[k]`s where `k `is an even number respectively. So odd and even number's data is treated independently that the program can execute concurrently. But it is very confusing that the answers are passed out of order such as a[0],a[2],a[1],a[4]... so reorder technique must be implemented in many cases. This consists of the FIFO recording out of order information and the place node can add the arbitrary number of the tokens when its callback code completes. When callback function is about to return, FIFO writing should be executed for storing the data calculated in this node but out of order in some case. If it is out of order, return 0; to inform no data is available in order and the token is not added for avoiding irrelevant data is coupled with another FIFO data. If FIFO writing is in order and moreover out of order caused by the overtaken writing is solved, return n; to inform as if some executions were achieved to end simultaneously for matching the number of the flowed tokens along with the in order data. But be careful to read FIFOs because reading is also in race condition and reading FIFOs simultaneously implies mutex needed. Transitions in this sample are devoted to be with mutex (added one place and one token to the transition) and to make the tuple in which all input and output data or data reference is synchronized one because every FIFO is in order and read and write all FIFOs are in mutex. The tuples are passed to way-out place nodes, then prepared synchronized data in the tuple is used to execute freely from its timing restriction.

## Points of Interest

In the main.c program sample, some wise persons are aware that initializing many tokens to the evaluation stage makes more parallel executions. It's OK but how many tokens must be prepared? The number of CPU threads is one answer but it makes the evaluation stage to the scheduling stage less semantics and illiterate. It is better to limit schedulers for real time applications. In the main2.c program sample, true concurrency is achieved but code is shapeless. But if the algorithm verification is needed, the cost of translating to HDL (Hardware Description Language) is very little in this style. Soft FIFO is to Hard FIFO, Place is to Hard counter, Petri net Propagation is and gate, and tuples are wires. To tell the truth if the functional programming is assumed, the application using this library is seamless between software and hardware with its notifying feature. Here some kind of frame works and/or OS are expected to develop the free choice Petri net.

## History

• Version 0.1: September, 2013

## Share

 Software Developer Japan
I'm an old programer. My Skill starts from i8085 assembler
coding. The Object oriented programing is over 20 years
and I achived the Policy based programing. Latest interests

## You may also be interested in...

 First Prev Next
 Interesting article xawari17-Mar-14 8:06 xawari 17-Mar-14 8:06
 Now I have plenty of good reading, thanks! in another thousand years we'll be machines or gods█
 Last Visit: 31-Dec-99 19:00     Last Update: 12-Feb-16 2:31 Refresh 1