By January 2, 2012 0 Comments Read More →

Simulated Naughtiness in CPN Tools

This post has 1370 words. Reading it will take approximately 7 minutes.

GD Star Rating
loading...

Today I got a question about simulating a sequence of named transitions in CPN Tools.  While this is not immediately possible, it can be done using Access/CPN, which has a Java component (featured here ) and a SML component, which is leading a much more secret life as the underpinning of ASAP.

Access/CPN is described in the papers

  • [PDF] M. Westergaard and L. M. Kristensen, “Two Interfaces to the CPN Tools Simulator,” in Proc. of 9th CPN Workshop, 2008, pp. 83-102.
    [Bibtex]
    @InProceedings{siminterface,
    Author         = {Westergaard, Michael and Kristensen, Lars Michael},
    Title          = {{Two Interfaces to the CPN Tools Simulator}},
    BookTitle      = {{Proc. of 9th CPN Workshop}},
    Volume         = {588},
    Series         = {DAIMI-PB},
    Pages          = {83-102},
    year           = 2008,
    }
  • [PDF] [DOI] M. Westergaard and L. M. Kristensen, “The Access/CPN Framework: A Tool for Interacting with the CPN Tools Simulator,” in Applications and Theory of Petri Nets, G. Franceschinis and K. Wolf, Eds., Springer Berlin / Heidelberg, 2009, vol. 5606, pp. 313-322.
    [Bibtex]
    @incollection{accesscpn,
    author = {Westergaard, Michael and Kristensen, Lars Michael},
    affiliation = {Aarhus University Department of Computer Science Denmark},
    title = {The Access/CPN Framework: A Tool for Interacting with the CPN Tools Simulator},
    booktitle = {Applications and Theory of Petri Nets},
    series = {Lecture Notes in Computer Science},
    editor = {Franceschinis, Giuliana and Wolf, Karsten},
    publisher = {Springer Berlin / Heidelberg},
    isbn = {},
    pages = {313-322},
    volume = {5606},
    doi = {10.1007/978-3-642-02424-5_19},
    note = {10.1007/978-3-642-02424-5_19},
    abstract = {Coloured Petri nets (CP-nets or CPNs) is a widely used formalism for describing concurrent systems. CPN Tools provides a mature environment for constructing, simulating, and performing analysis of CPN models. CPN Tools also has limitations if, for example, one wishes to extend the analysis capabilities or to integrate CPN models into external applications. In this paper we present Access/CPN, a framework that facilitates such extensions. Access/CPN consists of two interfaces: one written in Standard ML, which is very close to the simulator component of CPN Tools, and one written in Java, providing an object-oriented representation of CPN models, a means to load models created using CPN Tools, and an interface to the simulator. We illustrate Access/CPN by providing the complete implementation of a simple command-line state space exploration tool.},
    year = {2009}
    }

The idea is to use Access/CPN to execute the transitions and then force the GUI to update itself after the fact.  The SML component of Access/CPN is instantiated using the Enter State-space tool of CPN Tools.  Starting with version 3.2, CPN Tools has an extra option which loads the ASAP tool instead of the old one in CPN Tools.  See more about ASAP in CPN Tools here.

Now, we have access to the structures Bind and ASAP.CPNToolsModel (and a couple others as well, but let’s not worry about those here).

Let us consider the model below:

Let’s assume that we want to perform some setup, so we need to execute first a with n = 1 and then b (also with n = 1).  To do that, we can use the executeSequernce function of ASAP.CPNToolsModel.  The function has interface:

executeSequence: state * event list -> (state * event list) list

Thus, we need to give a source state and a list of events to execute.  The result is a set (list) of states and enabled events, namely the result of executing the event sequence (which we ignore).  We can use the function

getInitialStates: unit -> (state * event list) list

to get the initial state (the interface allows multiple initial states to handle non-deterministic models, but the function always returns exactly one for CPN models).

The Bind structure contains a type event which is a union of a value for all transitions in the model.  Transitions are described using two values, an integer indicating the instance number (the number shown next to the page name or 1 if none is shown) and the binding of all variables.

We thus devise the code:

let
open Bind ASAP.CPNToolsModel
val [(s, _)] = getInitialStates()
val r = executeSequence (s, [Top'a (1, { n = 1 }), Top'b (1, { n = 1 })])
in
CPN'Sim.reset_scheduler()
end

We first open the structures we need (l. 2) and obtain the initial state using pattern matching to only get the actual state descriptor (l. 3). We then execute the desired sequence of events. Here, we execute transition a on instance 1 of the page Top in the binding n = 1, then the transition b on the same page in the same binding. In line 6 we reset the scheduler. We need to do this as we are executing transitions without using the scheduler. Read more about the scheduler in a separate post.

Now we are nearly done: CPN Tools has actually executed the events, but the GUI does not reflect this. To reset the GUI, we need to fast forward (at least) one step.  This may execute any transition, however, so we use a trick to ensure that a particular transition without importance is executed.  The construction is shown below:

The idea is that the low-priority transition will never be executed until no other transitions are enabled and the high-prioritry transition will be executed before all others.  The trick is that using Access/CPN to execute transitions allows us to execute the low-priority transition even though it is not enabled (it is only pre-enabled).  See more about priorities in

  • [PDF] M. Westergaard and H. M. W. Verbeek, “Efficient Implementation of Prioritized Transitions for High-level Petri Nets,” in Petri Nets and Software Engineering. International Workshop PNSE’11, 2011, pp. 27-41.
    [Bibtex]
    @InProceedings{priority,
    author =   {Westergaard, Michael and Verbeek, H. M. W.},
    title =   {Efficient Implementation of Prioritized Transitions for High-level {Petri} Nets},
    pages =   {27-41},
    booktitle =   {{Petri} Nets and Software Engineering. International Workshop PNSE'11},
    editor =   {Duvigneau, Michael and Moldt, Daniel and Hiraishi, Kunihiko},
    month =    jun,
    year =    2011,
    volume =    723,
    series =    {CEUR Workshop Proceedings},
    ISSN =    {1613-0073},
    publisher =    {CEUR-WS.org},
    url =    {http://CEUR-WS.org/Vol-723},
    urn =    {urn:nbn:de:0074-723-C}
    abstract =    {Transition priorities can be a useful mechanism when
    modeling using Petri nets.  For example, high-priority
    transitions can be used to model exception handling and
    low-priority transitions can be used to model background
    tasks that should only be executed when no other
    transition is enabled.  Transition priorities can be
    simulated in Petri nets using, e.\,g., inhibitor arcs,
    but such constructs tend to unnecessarily clutter models,
    making it useful to support priorities directly.
    
    Computing the enabling of transitions in high-level Petri
    nets is an expensive operation and should be avoided.  As
    transition priorities introduce a nonlocal enabling
    condition, at first sight this forces us to compute
    enabling for all transitions in a highest-priority-first
    order, but it is possible to do better.  Here we describe
    our implementation of transition priorities in CPN Tools
    3.0, where we minimize the number of enabling
    computations.  We describe algorithms for executing
    transitions at random, useful for automatic simulation
    without user interactions, and for maintaining a set of
    known enabled transitions, useful for interactive
    user-guided simulation.  Experiments show that using our
    algorithms we can execute $4-7$ million transitions a
    minute for real-life models and more than $20$ million
    transitions a minute for other models, a significant
    improvement over the $1-5$ million transitions a minute
    possible for simpler algorithms.}
    }

Combining it all yields this model:

You can also get the model as a model for CPN Tools here.  Note that we have added the low-priority transition at the end of the list of transitions to execute.  The model is used by loading it in CPN Tools.  Then the ASAP option is switched on for the Enter State Space tool and the tool is used on the model.  Entering the ASAP tool instead of the old one normally used in CPN Tools is significantly faster.  Now, the auxiliary text is executed using Evaluate ML.  Finally, we Fast Forward, making sure to set the number of steps to skip ahead to 1 beforehand if it isn’t already set to that.  The model is now in a state, where A contains 1`2 and C contains 1`1 and the other places are empty.

The constructions used are completely generic, which is why they may seem a bit complicated.  The priority construction does not introduce new behavior (as long as we ensure that the priorities are indeed lower than/higher than all other used priorities).  Dead-locks are preserved and (I’m fairly certain but haven’t bothered to prove) so are LTL properties.

Simulated Naughtiness in CPN Tools, 2.3 out of 5 based on 3 ratings
Posted in: Uncategorized

Post a Comment