In this paper we describe how efficient data-structures and algorithms are used to dramatically improve the performance of a simulator for Coloured Petri Nets compared with earlier versions. We have improved the simulator with respect to three areas: Firstly we have improved the transition occurrence scheduler algorithm so that we use lazy calculation of event lists. We only keep track of disabled transitions which we have discovered during the search for an enabled transition, and use the locality principle for an accurring transition in order to minimise the changes of enabling status of other transitions. Secondly we have improved the data-structures which hold multi-sets for markings. A kind of weight-balanced trees, called BB-trees. are used instead of lists as in the original version of the simulator. Although this kind of trees are more difficult to maintain at run-time they are surprisingly efficient, even for small multi-sets. Thirdly we have improved the search for enabled binding elements. We use the first enabled binding element we find in a fair serach and make it occur immediatly instead of calculating all bindings and then randomly select one. The search is guided by a binding "recipe" which is specially generated and optimised for each individual transition. The improved simulator is implemented in both the Design/CPN and CPN tools software packages, and has been used in several industrial projects.
Third Workshop and Tutorial on Practical Use of Coloured Petri Nets and the Cpn Tools, 2001, p. 57-75
Main Research Area:
Third Workshop and Tutorial on Practical Use of Coloured Petri Nets and the CPN Tools, 2001