Home

Manual

1. For each model type it may be developed an optional animator that graphically animates the simulation progress This facility is called token game in Petri nets As shown in Figure 24 for example SAN Animator has the following parts e An animator log in the right hand of the animator screen e A graphical animator that shows the model with the marking of each place and emphasizes the firing of activities e A table that shows the current values of reward variables e Some graphical button in top of the animator screen that control the animation progress which includes stop the animation pause the animation play resume animation and animate event by event step by step You can change the speed of animation by determining interval time between events execution in millisecond EEl Case_Studies M_M_3_100 SAN Model Animator ex Simulation Logs Compiling Start in 2 31 PM Compile Finished in 2 31 PM Simulation Started in 2 31 PM Confidence Mean Variance 4 03109467637514 23 57 75585585242 71 7947830258815 Figure 27 SAN animator in PDETool You can also use SDES Animator Figure 25 SDES animator has the following parts e An animator log which logs execution of each event in the model e Table of state variables and their values e g in SAN models places and global variables e Table of events and their scheduling time for execution e g activates in SANS e An event log in the left hand of scree
2. PDETool Version 1 0 6 User Manual Performance and Dependability Engineering Lab PDE Lab School of Computer Engineering Iran University of Science and Technology http pdel iust ac ir projects pdetool html Last edit 2009 09 17 Author Ali Khalili email kAhalili dot ir at gmail dot com Copyright 2008 PDE Lab of Iran University of Science and Technology All right reserved Table of Content Mu oduc BOTE sooo cei eoe tueatur tuf i Re cee were See eprom DUM Not ne SD cde I duh eee epee rere 3 TIO CU CH OM MR a 3 The sonware AL COIL elits EE m m T 3 PDETOOLDacEPEOUDG ARAS 4 InistalTalloll ssh ao 5 Inistalline Summe and EDEN 5 Modeling Background 5 oie e re t toten tete n Io Ceuta EUR o NOR Coke ana Tage e Ta cda 6 ESTI NES ENS tradi AC MA RE E DUE HE iden 6 Generalized stochastic Petri Nets OSENS us it ote e ea cee tease 7 Stochastic Reward Nets SERNA nata 7 Stochastic Activity Networks SANS cccccccssssssesssecceeeeeeeeeesseeceeeeeeseaeeseseeeeeeeeeaeeeenees 8 Coloured Stochastic Activity Networks CSANS ooooocccccccccccncnnocccncnnnnononnnanonoccnnnnnnnnnnos 10 OVER WO PDE ToO sc erario eos 11 CONS MUCHO models tics acallar 12 Adding editing SAN elements dan 13 Modifying properties of SAN elements ccccccooooonncnnnnnnnnnononocnnnnnnnnononononnnncnnnnnnnnnnnos 14 Addmereditumne elobal Variables unidad 17 Addms editing C SAI elements eene tie et bati bati eee e bet
3. 2 Aa n 0 0020 83 83 8 8 B D DU DO O G G G 8 B D DB D UB GU GB G G G9 B8B B DB D 0O D B B 8 B 8 B UB DO G G saca du iw v eo m M ee m M m eee w N M m MIR E 7 mw m TLLA a LT TIU cU A E CN M SET ND BON CNC A A SON CAT RUE T SR Trier Lc ix poa n 2 2 2 2 2 2 R BR 2 2 2 2 R BR 32 BR B 32 B 2 3 2 2 2 BR 2 B B 2D RB BR 32 R B 8 R B 2 BR 2 2 2 2 2 R B B B D 2 2 2 2 2 3 Rewards Reward Variables Variable2 Variable Name Figure5 SAN Model Editor To add a new SAN primitive you must use graphical menu shown in Figure 6 To add a new Place Timed Activity Instantaneous Activity Input Gate or Output Gate drag the proper icon Figure 6 to the model grid and drop whenever you want location of the new place To connect two SAN elements places to gates gates to activities places to activities and opposite sides of them by an Arc push the icon Arc Figure 6 6 Now left click the first element of the connection and while holding the button move the mouse to the destination of the connection and release the mouse button Something like drag and drop In Figure 6 Icons include 1 input gate 2 output gate 3 instantaneous activity 4 timed activity 5 place 6 arc 7 global variable 8 reward 9 save and 10 convert to SDES 13 EE KABZE Jj 45 6 7 8 9 10 Figure 6 SAN Model Editor graphical menu Graphical and textual editors also can be used to e Add a global variable and reward variabl
4. T A and M are as in simple Petri nets and R is the set of firing rates possibly marking dependent associated with the PN transitions where K i eras The underlying reachability graph of a SPN model is isomorphic to a continuous time Markov chain CTMC Generalized stochastic Petri nets GSPNs 5 try to extend SPNs further by introducing immediate transitions which fire in zero time once they are enabled in addition to timed transitions that fire after a random exponentially distributed enabling time like in SPNs Usually timed transitions are represented by hollow rectangles while immediate transitions are represented by thin bars The markings of a GSPN are classified into two types A marking is vanishing if any immediate transition is enabled in the marking A marking is tangible if only timed transitions or no transitions are enabled in the marking If several conflicting immediate transitions are enabled in a marking a firing probability must be defined The usually marking dependent firing probability 1s specified for only timed transitions and does not need to be specified for timed transitions Another type of arc exists in GSPN called inhibitor arc An inhibitor arc connects a place p to a transition and imposes an additional constraint on the enabling of that transition The transition is now enabled iff the enabling rule of ordinary Petri nets concerning the usual arcs between places and that transition 1s satisfied and if the pl
5. submenu 12 e To load an existing model double click on it It opens another form for editing and modifying models The type of model editor depends on type of models e g in case of SAN models SAN Model Editor will be opened e You can also import a model from another project into the current project Model 2Import Model Adding editing SAN elements For constructing and modifying a SAN model you must use SAN Model Editor As shown in Figure 6 SAN Model Editor includes 6 parts a textual menu 1 a graphical menu 2 model grid 3 reward variable list 4 global variable list 5 and properties editor 6 EE c 4USTSimiTemp2 SAN2 PDETool E e A o o o 0 0 n co co co co clo o o 5o 5n 0 no 5o 50 5 n 5 n o n 5 n co co o 5 5 8 c3 c5 c5 2 50 o n n BD 85 DO v co 9o 9 o lgz Z m um A wo wow ww AAA a a AAA n Ea da a ww Saas E Distribution rex CINE r ECE E AA NA m Function Exponential Rate Wo wow A O A 08 8 RA ee HORN LUE CR UA ON OW UU we CR LAO RI LU E Public maa a A A AAA ASA AA A TE gt Name Ti Ww wx 4 NUN M a a ww CK um lee RR AR RAR RS m RTI UN 2A RR 9 A os iis aa E woes a RT Ee s s EI RTS e Decr E 783 9 2 73 dw Hala ja exa aa ws ae M ee n El ReadOnly Property 1 3 se ow 2 we AA M ww Ww s AA CR ee ee ie AAA ANN o JN N R E A NR 3 2 AS AA A 77 A wu xa wa xS a ca wa aM m RN CN E E m LET ea M Oe M u ere B PE da melee 2 IN ee
6. can be specified both rate function and impulse function as follows e A rate function is body of a function which assigns some quantity of reward when the model is in a particular situation and must be written in code editor Figure 19 The situation can be checked using a conditional statement that tests the state of model marking of places or value of global variables Assigned quantity of reward 1s the float return value of this rate function When model is in a specific state 1f rate reward function returns value r 1t means while model remains in that state reward will be accumulated with rate r 24 DETool user IL Editor Cancel Figure 21 Rate reward editor e An impulse function can be used to observe execution of some desired events and specifies amount of reward earned when state of the model changes by execution of those particular events Name of the desired events e g activities in SANS or transitions in SRNs must be designated and body of method that its return value characterizes the amount of reward earned upon completion of the specified event must be specified in the code part of the impulse reward editor Figure 21 ImpulseReward Collection Editor Members Impulse For properties i Impulse For 4 Ea Al E Hisc Activity Code Remowe Figure 22 Impulse reward editor In addition for all rewards two values must be defined named confidence interval and confidence level which determin
7. of PDETool shown in Figure 1 is separated to two layers a front end layer and a back end layer as follows e Front End Layer PDETool interface This layer provides some graphical user interfaces and a model translator The user interfaces includes editors model editor reward variables editor global variable editor SimGine interface simulation and animation GUI described in the previous subsection Each formalism supported by the tool has its own editor translator and an optional graphical animator which are responsible for communicating with the underlying layer This layer can be viewed as an interface between users and the back end layer e Back End Layer SimGine engine PDETool uses SimGine simulation engine as the underlying layer This back end layer 1s responsible for simulation of the model and evaluating reward variables and also provides model animation facility As we mentioned before for simulating a model based on particular stochastic discrete event formalism a model translator prepares the input model of SimGine mapped from the original model where these two models should be behaviorally equal As depicted in Figure 1 the internal architecture of SimGine includes parser code generator utility library simulator animator and SDES simulation manager PDETool user manual Miodel Editor SimGine Model Simulator amp Interface Animator Model lranslator Simulator I 1 SDES Simulation Manager Utility Libra
8. project in the installation directory of the tool to store save and load the projects models reward variables and etc It can be changed in the setting screen Figure 16 e SimGine engine parameters To use some parameters in initialization of SimGine you may use this field e Random number generator RNG seed SimGine does not need to use a seed number for generating random numbers automatic seed auto but you can specify a seed value manually which will be used by SimGine for RNG PDETool does not use this value directly and it is one of the simulation engine s parameters e Simulation output directory Result of simulation can be saved when the simulation progress is finished In this case output directory must be specified You can use models directory as the output directory of simulation project directory nodel directoryNSim set a permanent directory as the default destination to store simulation results or use the Always ask me option Project folder SimGine Parameters po SimGine Random Seed 2 Auto O Mand Simulation Results Directory Always Ask me C3 In Simualtion Directory Projectfalder Sim Figure 18 PDETool Setting 22 PDETool user manual SDES Interface PDETool has an interface for direct working with the SimGine This feature is useful when the modeler wants to simulate a SimGine file which is based on SDES description In this situation modeler can load edit and simulate a S
9. ace is not marked is empty A GSPN model describes an underlying stochastic process captured by the extended reachability graph ERG as a reachability graph with additional stochastic 1nformation on the arcs which can be reduced to a CTMC in the state space analysis step Stochastic Reward Nets SRNs Stochastic reward nets SRNs 6 are based on GSPN but extend it further In SRNs every tangible marking can be associated with a reward rate It can be shown that an SRN can be mapped into a Markov reward model Thus a variety of performance measures can be specified and calculated using a very convenient formalism SRN also allows several other features that make specification convenient Each transition may have an enabling function also called a guard so that a transition 1s enabled only if its marking dependent enabling function is true This feature provides a powerful means to simplify the graphical representation and to make SRNs easier to be understood Marking dependent arc multiplicities are allowed This feature can be applied when the number of tokens to be transferred depends on the current marking Marking dependent firing rates are allowed This feature allows the firing rate of the transitions to be specified as a function of the number of tokens in any place of the Petri net Transitions can be assigned different priorities and a transition 1s enabled only if no other transition with a higher priority 1s enabled Besides
10. ae tr eade e batte oda A 18 Primitives of CSANS are the same with SANs in addition to the following ones 18 Addis edititie SIINDELDHEDV S 1 A A arte Each 19 Genera CONAM dao tedio 22 Ba E PR 23 Specityine Reward Y artables cnica 24 OGSPINS performance measures siria siii idilio 26 Model Siinulation Mit DE TOOL a daa 27 simulation using Model Simulator 552 99 0 092 Bitenicene ii 28 Simulation using Model AniMatoT oooooonnnnncnnnnnnnnnnononcnnnnnnnnnonannnnnnnnnnnnnnnninnncnnnnnnnnnnnos 20 Example Ses eicere cai M IM ME E E ILI EE EM UE 3l Example 1 Modeling a Queue Using SANS ooooooccccnnncncnononocnnnnnnnononononnnnnnnnnnonnnnnninnnnss 3l Example 2 Modeling a packet generator system using CSANS esses 32 Example 3 SRN model of a multi processor system oooooonnccnnnnnononnnonnnnnnnnnnnnnnnnannnnnss 34 Appendix A Known bugs and limitation oooooncnnnnnccnnnnnnonnnnnnnnnnonnnanocnnnnnnnnnnnnannnnnnnnnnos 36 ls usine T 37 Introduction PDETool is a multi formalism modeling and simulation framework for discrete event models based on a unified abstract description named SDES 1 It uses a simulation engine for simulation of discrete event simulation of stochastic models called SimGine PDETool can be easily extended to support variety of stochastic formalisms It currently supports SANs CSANs GSPNs and SRNs which will be explained next The Software Architecture The software architecture
11. an be a place or an input gate and each output can also be a place or an output gate To each timed activity is associated an enabling rate function 1 e a computable partial function which is the activity execution speed and an n ary computable predicate called the reactivation predicate Timed activities are represented graphically as thick vertical lines Enabling rate functions can be generally distributed random variables Each distribution can depend on the marking of the network For example one distribution parameter could be a constant multiplied by the marking of a certain place Reactivation predicate function gives marking dependent conditions under which an activity is reactivated Reactivation of an activated activity means that the activity is aborted and that a new activity time is immediately obtained from the activity time distribution Instantaneous activity Instantaneous activities represent system activities which relative to the performance variable in question are completed in a negligible amount of time These activities are represented graphically as thin vertical lines An instantaneous activity has m inputs and n outputs where m n gt 0 Input gate Gates are introduced to permit greater flexibility in defining enabling and completion rules An input gate has a finite set of inputs and one output To each such input gate 1s associated an n ary computable predicate called the enabling predicate and a computable
12. c reward nets SRNs stochastic activity networks SANs and coloured stochastic activity networks CSANSs In this section we review some modeling background about these models Petri Nets PNs Petri nets originally were introduced by C A Petri in 1962 3 A Petri net PN or sometimes Place Transition net is a bipartite directed graph whose nodes are divided into two disjoint sets called places and transitions Directed arcs in the graph connect places to transitions called input arcs and transitions to places called output arcs A cardinality number may be associated with these arcs A marked Petri net is obtained by associating tokens with places A marking of a PN is the distribution of tokens in the places of the PN There are several definitions for Petri nets and even more for stochastic Petri nets Petri net formally can be defined by a 4 tuple P T A M where e Pzlpipso pm is a finite non empty set of places e T tj t gt tnj is a finite non empty set of transitions where PAT e A PxT U T x P is the set of input and output arcs e M P 2 0 1 2 is the marking of net which denotes the number of tokens in each place P Initial marking is denotes as Mo In a graphical representation of a PN places are represented by circles transitions are represented by bars and the tokens are represented by dots or integers in the places Input places of a transition are the set of places which are connected to the tran
13. cluding input gates output gates input places and output places These properties show that which elements are connected to the activity e g places that are connected as the input places of this activity When you change the model or modify it these properties change automatically EY El Activity Reactiwation Predicate El Distribution Distribution Exponential Rate 2 El Public Server El Hare Event Simulation I5 Distribution El Read Only Property Figure 8 Timed Activity properties 15 Distribution Editor Exponential Figure 9 Distribution Editor 3 Instantaneous Activity e Name A unique name that identifies the instantaneous activity e Probability Weight If two or more activities have the same completion time these activities must compete probabilistically to determine which event completes first and the Probability is used to determine probability of firing each activity these probability 1s normalized first FERA El Probabilty Probabilty 0 5 instantanenus1 Figure 10 Instantaneous Activity properties 4 Input Gate e Name A unique name that identifies the input gate e Enabling predicate A Boolean function an expression or a sequence of statements written in C which return a Boolean vale e Input function A sequence of statements that their execution may change the state of model marking of some places or value of some global variables just before firing the activity which is connec
14. d a selection policy which specifies the order of tokens for removal by the occurrences of linked activities Different kinds of the selection policies are as follows e FIFO In this case tokens can be taken from the place in same order they have been appended e LIFO In this case tokens can be taken from the place in reverse order of their appendance e PRI In this case tokens have a priority that can be specified by a user defined order function e NSP no selection policy In this case the list of tokens is unordered Therefore a multi set or bag can be used to hold tokens The type of the objects being held by a coloured place is defined by a token type A token type can be defined similar to the declaration of data types records or structures in high level programming languages like C Java or CF in PDETool Each token type has one or more data fields which may be an ordinal type or a user defined type Both of the number of tokens inside a coloured place i e the size of the token list and the values of its fields can be read in predicates and functions or can be read or manipulated by functions of input output gates Table 1 Graphical notation of CSAN elements Simple place A graphical representation of the elements of CSANs is shown in Table 1 For the coloured place tt is the name of a token type and sp is a selection policy for the place 10 PDETool use Overview of PDETool This section looks into the g
15. e Figure 6 7 and 8 This will be explained in detail in the following subsections e Save the current model To save the current SAN model push icon Save Figure 6 9 It can be done using the textual menu too e Convert to SimGine input To convert the current SAN model into the input language of SimGine push icon Convert to SDES in the graphical menu Figure 6 10 e Export models as an image SAN Model Editor can export current SAN model into an image with type JPEG To do so use textual menu Model 2Export as Image and specify destination location of the output 1mage file Modifying properties of SAN elements Note that name identifier of each element as an object primitive or variable must be unique in the model Properties of each element in a SAN model can be accessed and modified via Property Editor right hand of the Model Editor as presented in Figure 6 6 Like traditional programming languages names identifiers can be defined by a string which satisfies some constraints Here the lexical rules constrains that names must be satisfied is as existed in NET languages In the subsequent paragraphs we will describe attributes of each element type 1 Place e Name A unique name that identifies the place Marking of a place p in functions defined in a gate can be accessed modified by property Mark For example one can write p Mark 2 e Initial Marking The initial marking m of each place is an integer value equal
16. e 23 4 For simulating a model you can use simulator or animator To save the simulation studies push Save button Token Play and Simulation button are used to simulate and animate the model correspondingly To simulate or animate a model you have to choose a simulation study first 27 PDETool user manual SAM Sample M M 3 100 Simulation Manager Variable ra Study blasi Ler Study Set 1 Max Time of Simulation Number of Events per data update 100 Mame Type Len Steady State isFull Steady State O Transient 9 Steady State 9 3 isEmpty Steady State Simulation Type Figure 25 Simulating a model using Simulation Manager Simulation using Model Simulator PDETool provides a general graphical simulator It can be used for any formalism which the tool can deal with Model Simulator as shown in Figure 24 contains three parts Simulation logs which log the simulation events occur during simulation progress compilation start finish etc a status bar shows simulation progress and a table that shows the current values of reward variables El SAN_ Simulator AD Value Confidence Mean Variance Simulation Logs gt LE 1 0011262140873 0 100086897877671 118 601255041081 Simulation Time s 7 468 Number Itteration Olecured 453960 Simulation Succefully Finished in 6 24 PM Figure 26 Model simulation using Model Simulator 28 PDETool user manual Simulation using Model Animator
17. e precise of computed value of the reward and affect duration of simulation When simulator reaches the desired confidence interval in specific confidence level for all reward variables the simulation progress will be stopped Confidence level can be 0 95 0 98 0 99 or 0 999 Greater levels with smaller intervals lead to more reliable results For timed interval rewards timed interval and averaged timed interval start and end time of the evaluation interval also should be defined using properties editor as in Figure 22 For example for instance of time rewards the moment of evolution must be specified Figure 23 25 Heward Impulse Collection Fate E Simulation Contidencelnterval ConfidenceLewel El Time EndTime StartT ime Figure 23 Properties of a reward variable with type Interval of Time GSPNs performance measures GSPNs have performance measures instead of rewards These performance measures are translated into the rewards which can be computed during simulation progress and include following measures Steady State Average number of Tokens in a Place Expected number of Tokens in a Place at time t Steady State Throughput of a Transition Throughput of a transition at time E Figure 24 GSPN performance measures 26 Model Simulation with PDETool For simulation of a model in PDETool modeler must first define a simulation study using Project Editor following these steps e Define a simulation study in P
18. f an input gate 1s connected to a single activity Different input gates of an activity are connected to different places Each output of an output gate is connected to a unique place and the input of an output gate is connected to a single activity Different output gates of an activity are connected to different places Each place and activity is connected to some input or output gates Note Be aware that the order in which state updates occur in PDETool may differ from some other tools Input gates execute before arcs directly connect places and activities and they execute before output gates in PDETool Also if there are multiple instances of the same item for instance multiple input gates and the order of application of the gates is not specified Models must be constructed so that the gate functions are execution order independent anytime there are multiple instances of the same type of gates connected to an activity Coloured Stochastic Activity Networks CSANs A CSAN model 13 is composed of the five primitives of a new definition of SANS including place input gate output gate timed activity and instantaneous activity plus a new type of places called coloured place A coloured place holds a list of tokens of a user defined token type To differentiate the two kinds of places we will refer to the ordinary places of SANs as simple place The term place is used to refer to both kinds of places To each coloured place is associate
19. imGine file A simple model animator is also available for this purpose For direct simulating a SimGine model use SimGine Tool from menu Projects Projects 2SimGine Tool in main console This opens the SDES Interface presented in Figure 18 Events Collection Cot Constants f Functions B V Variables W Variable P3 W Variable P2 W Variable P1 E dnitilieer E y Events TI aR R Reward Events Figure 19 SimGine Interface 23 Specifying Reward Variables For evaluation of models modeler have to specify some reward variables which define functions that measure interested information about the system being modeled One of the key features of each reward is its evaluation time There exist two main classes of evaluation time includes transient and steady state Transient type itself can be instance of time interval of time and time averaged interval To add a new reward variable in SAN and SRN models use graphical icon of rewards Figure 18 in model editor When you create a reward variable it is added to the list of reward variables Figure 5 5 Like elements and variables a reward variable has a unique identifier Steady State Reward Instant of Time Interval of Time Time Avg Interwal Figure 20 Add a reward variable within a particular type PDETool and its simulation engine SimGine use performance reward variables which introduced in 2 and include rate rewards and impulse rewards For each reward it
20. imulation results obtained from Model Simulator depicted in Table 5 33 Table 3 Parameters of the presented CSAN model PriorityFunc return TPacket Priority PriorityFunc return TPacket Priority tempPacket new TPacket tempPacket Protocol byte Distribution Random 3 1 GenGate Function tempPacket Len Distribution Random 100 tempPacket Priority Sp stribution ien 1dom 5 InBuf Mark gt 0 im tmpPacket InBuf Remove OutBufl Add tmpPacket Enabling Predicate InBuf Mark gt 0 tmpPacket InBuf Remove IG3 OutBufl Mark gt 0 tmpPacket OutBufl Remove OutBuf2 Mark gt 0 ii SERE 7 tmpPacket OutBut2 Kemover Enabling Predicate tmpPacket InBuf Remove Table 4 Reward variable specification and simulation results 1 20341797 0 018929343 1 980087407 0 60774698 0 012793362 0 904446091 Example 3 SRN model of a multi processor system Consider a simple multiprocessor system consisting of two dissimilar processors P1 and P2 as in 15 which can be failed and repaired The system is functioning as long as one of the two processors 1s functioning and failures of the two processors to be independent While both processors work the time to occurrence of a failure in the two processors Pl and P2 is assumed to be a random variable with the corresponding distributions being exponential with rates and A respectively When only one processor is functioning the rate of failure could be correspond
21. ingly altered to reflect the fact that a single processor shares the load of both the processors When only P1 is functioning we assume its failure rate 1s o and when only P2 is functioning its failure rate is ho The both processors can also fail simultaneously in exponential time A Assume that the system has imperfect coverage of the failure of the processors Whenever a processor suffers a failure with some probability c called the coverage probability the failure 1s properly detected With probability c the processor suffers an uncovered failure wherein the failure goes undetected We assume that this undetected failure results in the other normal processor also failing causing the system failure 34 We could consider repair of the processors where the time to repair the processors 1s also exponentially distributed with rates 6 and 62 respectively We also assume that when both the processors are waiting for repair P1 has priority for repair over P2 Figure 32 SRN model of the multi processor system Table 5 Availability of the multiprocessor system 0 1 09 Availability 0 5629779 0 5629779 0 56297792 35 Appendix A Known bugs and limitation Here 1s the list of known bugs e Exporting model as an image has bug when the model is bigger than the screen e In graphical editor multiple elements cannot be selected We appreciate your feedback on this tool and bugs report by sending an email to pde
22. l iust ac ir Please look at the home page of the tool for more information on how to get in contact with the developers 36 Reference 10 11 12 13 14 15 A Zimmermann Stochastic Discrete Event Systems Modeling Evaluation and Applications Springer 2008 W H Sanders and J F Meyer A Unified Approach for Specifying Measures of Performance Dependability and Performability Dependable Computing for Critical Applications Vol 4 Springer Verlag pp 215 237 1991 C A Petri Kommunikation mit Automaten PhD thesis Universitat Bonn 1962 RI IC Molloy Performance analysis using stochastic Petri nets IEEE Transaction on Computers 3 1 9 9 13 9 17 September 1982 Ajmone Marsan M Balbo G and Conte G A class of Generalized Stochastic Petri Nets for the performance evaluation of multiprocessor systems ACM Transactions on Computer Systems Vol 2 No 2 pp 93 122 1984 Ciardo G and Muppala J K and Trivedi K S Analyzing Concurrent and Fault Tolerant Software Using Stochastic Reward Nets Journal of Parallel and Distributed Computing Vol 15 No 3 pp 255 269 1992 SimGine Framework Homepage http pdel iust ac ir projects simgine html PDETool Homepage http pdel iust ac ir projects pdetool html M Abdollahi Azgomi and A Movaghar An Interchange Format for Stochastic Activity Networks Based on PNML Detinition Proc of the ICATPN 04 Satellite Workshop on the Definition Implementa
23. n e A table that shows the current values of reward variables e Some graphical button to control animation progress 20 PDETool user manual 7 SAN SimulatorAnimator Simulation Logs Compiling Start in 7 01 PM Compile Finished in 7 01 PM Time 0 327 T1 fired Simulation Started in 7 01 PM Time 1 04 gt T1 fired Events Watch Time to ID Enabled Complete EN O 070025 Confidence Mean Variance Cd Figure 28 SDES animator in PDETool 30 PDETool user manual Examples Here we bring some case studies which may be useful to understand modeling with PDETool More examples can be found in the tools sample models Example 1 Modeling a Queue Using SANs Consider an M M 3 100 queueing system that is modeled in SAN The model is depicted in Figure 27 As shown in the figure the model has an activity for customer arrival three activities that present service execution and a place models the number of customers in the queue The input gate of the model controls the admission of customers The structure of model is depicted in Figure 26 You can use the tool to export the model as an image like Figure 28 E Case Studies M M 3 100 PDETool Model a gt 100a Hik Figure 29 SAN Editor for modeling a M M 3 100 with SAN o CheckQueue Customer Arrival Server2 Server3 Figure 30 Exported image of model generated by SAN Editor 31 Table 2 Timed activities configura
24. partial function called the input function An input gate 1s represented graphically as a triangle The enabling predicate is a Boolean function that controls whether the connected activity is enabled or not and can be any function of the markings of the input places The input gate function defines the marking changes that occur when the activity completes If a place is directly connected to an activity with an arc it is equivalent to an input gate with a predicate that enables the activity when ever the place has more than zero tokens along with a function that decrements the marking of the place by one when ever the activity fires An input gate is represented as follows Output gate An output gate which is represented by triangle has a finite set of outputs and one input To each such output gate is associated a computable function called the output function which defines the marking changes that occur when the activity completes Like in input gates there 1s also a default scenario for output gates 1 e 1f an activity is directly connected to a place it 1s equivalent to an activation in which an output gate has a function that increments the marking of the place whenever the activity 1s fired An output gate represented as bellows D Structurally a SAN model is an interconnection of a finite number of primitives subject to the following connection rules Each input of an input gate 1s connected to a unique place and the output o
25. raphical user interface GUI of PDETool and describes constructing editing and simulating models by the tool After installation you can run the tool using Start Menu 2PDELab DPDETool The main console of PDETool is shown in Figure 2 PDETool 1 0 6 6 PEE Projects Ukility Setting Help Events Logs Welcome to POE Tool version 1 0 6 6 Figure 2 Main console of the PDETool Before constructing a model you have to create a new project or select one of existing ones using Project Manager Projects 2New or Projects 2Open which is shown in Figure 3 11 PDETool user manual ES Project Manager 1 Madel s 1 5tudy s 1 Modelis O Study Cancel Figure 3 PDETool Project Manager Constructing models Opening a project in Project Manager or creating a new one causes to open Project Editor depicted in Figure 4 In this form you can create some models or some simulation studies to evaluate the existing models in the current project ES Safayi Project Editor Sele Mew SAMs Extention New Pls Extention Mew GSPN Model Mew PEPA Model New SRN Model Mew RayLang Model Import Model Rename Model Delete Model Figure 4 Project Editor In Project Editor you can create a new model in the current project or load and modify existing models as follows e To construct a new SAN CSAN SRN and GSPN model or rename delete a selected existing one use menu Model in Project Editor and select the proper
26. roject Editor using menu Simulation e Open Simulation Manager by double clicking on the defined study e Use Simulation manager to setup a simulation study and simulate the model Simulation Manager Figure 23 has the following parts and functionality o Simulation Study Editor Figure 23 1 As mentioned before modeler can define some global variables A simulation study is defined by a set of values correspond to these global variables as the parameters of the simulation A simulation study parameters of simulation or values of defined global variables can be saved for future use o Simulation Parameters Figure 23 2 During simulation progress graphical user interface which shows current values of rewards is updated periodically after execution of some predefined number of events which can be set by modeler in Event per update field Note that low values of this field reduce the simulation speed Maximum simulation time 1s a stop criterion 1 e when the simulation time model time not computation time exceeds this value the simulation will be stopped Minimum number of event before finish says that at least a minimum number of events activity must be executed fired before finishing the simulation unless there is not any enabled activity or the model time exceeds the maximum simulation time o Simulation type Figure 23 3 There exist two types of simulation steady state simulation and instantaneous simulation o Some buttons Figur
27. ry Sim Gine Engine Figure 1 The software architecture of PDETool and SimGine PDETool background As mentioned before PDETool uses SimGine for discrete event simulation of stochastic models SimGine is a simulation engine based on SDES unified description and has its own model structure and file format For simulating a model based on a particular formalism in PDETool the model must be translated into the XML based input language of SimGine For more information about SDES description see 1 More information about SimGine and its manual are also available in SimGine homepage 7 Installation PDETool runs under Microsoft Windows XP 2000 Vista and needs Net Framework version 2 or higher to be installed on the system If you do not have it installed on your system you must first install Net framework NOTE PDETool is not tested on Windows 95 98 Millennium and NT But we guess it will work in these versions of Microsoft windows if Net framework 1s installed The last version of Net framework currently version 3 5 can be freely downloaded from http msdn microsoft com en us netframework default aspx installing SimGine and PDETool To install PDETool download and run PDETool installation file from 8 It installs both PDETool and SimGine and everything needed to construct a model and simulate it Modeling Background PDETool supports multiple formalisms including generalized stochastic Petri nets GSPNs stochasti
28. se SRN Model Editor As shown in Figure 13 and like in SAN Model Editor SRN Model Editor includes 5 parts a textual menu 1 a graphical menu 2 model grid 3 reward variable list 4 and properties editor 5 EE Case Studies SRN1 SRNEditor Model AA EL V PW E XA cee es Cee SUR NR Ro ee ee eS eee 5 ek ee 52553 ee REN xis 5 3 5 E s Gs E 83 21 115 EU Place Initial Initial Marks 0 E Public Name Place3 Figure 15 SRN Model Editor 19 Constructing SRN models is very similar to SANs and SRN Model Editor is somehow alike In the following paragraphs we only describe the differences 1 Place e Name e Initial Marking 2 Timed transition e Name e Rate In SRNs all timed transitions are exponentially distributed Rate of firing can be a constant or a marking dependent number e Guard In addition of traditional enabling condition of each transition there may exist another enabling condition named transition guard based on net marking A guard is a Boolean expression and can use Boolean operators and marking of some places using property Mark for instance p Mark lt 3 amp amp p2 Mark 2 p3 Mark gt 5 e Priority priorities is defined by assigning an integer priority level to each transition and adding the constraint that a transition may be enabled only if no higher priority transition 1s enabled A priority 1s an integer number erea
29. sition through input arcs Similarly output places of a transition are those places to which output arcs are drawn from the transition A transition is considered enabled in the current marking if the number of tokens in each input place 1s at least equal to the cardinality of the input arc from that place The firing of a transition 1s an atomic action in which one or more tokens are removed from each input place of the transition and one or more tokens are added to each output place of the transition possibly resulting in a new marking of the PN Upon firing the transition the number of tokens deposited in each of its output places is equal to the cardinality of the output arc Each distinct marking of the PN constitutes a separate state of the PN A marking is reachable from another marking if there is a sequence of transition firings starting from the original marking which results in the new marking The reachability set graph of a PN 1s the set directed graph of markings that are reachable from the other markings connected by the arcs labeled by the transitions whose firing causes the corresponding change of marking In any marking of the PN multiple transitions may be simultaneously enabled Generalized Stochastic Petri Nets GSPNs The stochastic PNs SPNs 4 are obtained by associating with each transition in a PN an exponentially distributed firing time An SPN model can be formally defined by a five tupple P T A M R where P
30. ted to the gate 16 EA E Functions Function FredicateF unction E Public igl Figure 11 Input Gate properties 5 Output Gate e Name A unique name that identifies the output gate e Output function A sequence of statements that their execution may change the state of model marking of some places or value of some global variables just after firing the activity which 1s connected to the gate Functian E Public Name Figure 12 Output Gate properties Adding editing global variables For adding global variables which may change or remain constant during model execution you have to use the global variable icon Figure 6 7 in SAN Model Editor For each global variable a unique name must be chosen and type of the variable must be specified Table 1 shows the available types for global variables Table 1 Available type for global variables Type Size Byte byte l short 2 ushort 2 Int 4 uint 4 bool float 4 double 8 17 After adding a global variable to the SAN model you can change its name and type To do so select the variable in Global Variable List Figure 6 4 and change properties of the variable in the Properties Editor Figure 6 6 Figure 12 shows properties of variable Variable 1 with type int Figure 13 Global variable properties Adding editing CSAN elements Primitives of CSANS are the same with SANs in addition to the following ones 1 Color A color is a data struct
31. ter than or equal to zero and greater number shows greater priority FERMER EO Activation Guard Place1 Mark 4 Priority 1 Distribution Rate Plcae2 Mark Public Mame activity ReadOnly Property OutPutPl Figure 16 Timed transition properties 3 Immediate transition e Name e Guard e Priority 20 aR E Activation Guard Priority 1 Public Mame instantaneous ReadOnly Property OutPutPlaces Figure 17 Immediate transition properties 4 Arc e Multiplicity Multiplicity of an arc can be an integer number e g 2 marking of a place e g placel Mark a parameter or an integer expression like 2 placel Mark 1 0 2 5 Inhibitor Arc e If an inhibitor arc exists from a place to a transition then the transition will not be enabled if the corresponding inhibitor place contains a token Like Arcs inhibitor arcs can also associate a multiplicity number e Multiplicity is like multiplicity of arcs An inhibitor arc between a place and an arc with the multiplicity m is same as m replicate of a simple inhibitor arc 1 e the transition cannot be fired 1f there exist more than m token in the corresponding place 2 General Configuration Configuration of PDETool stored in file config ini in the directory which PDETool is installed can be changed using menu Setting in main console of PDETool The Setting form contain following functionality e Default project directory By default PDETool uses directory
32. the traditional output measures obtained from a GSPN such as throughput of a transition and the mean number of tokens in a place more complex reward function can be defined Stochastic Activity Networks SANs Stochastic activity networks SANs 10 introduced in 1984 are a stochastic extension of Petri nets 3 SANs are more powerful and flexible than most other stochastic extensions of Petri nets that use graphical primitives and provide a high level modeling formalism with which detailed performance dependability and performability models can be specified relatively easily PDETool uses a new definition of SANs which 1s introduced in 12 Each SAN model is composed of the following elements primitives Place Like any extension of Petri nets places which represent the state of the modeled system are represented graphically as circles Each place contains a certain number of tokens an Integer value which represents the marking of the place The set of all places marking defines the marking of the model All tokens in a SAN place are homogeneous in that only the number of tokens in a place is known there is no identification of different kinds of tokens within a place Graphically each place is represented as a circle Timed activity Timed activities represent activities of the modeled system whose durations impact the system s ability to perform A timed activity has m inputs and n outputs where m n gt 0 Each input c
33. tion and Application of a Standard Interchange Format for Petri Nets XMLAPN 04 pp 1 10 Italy 2004 A Movaghar and J F Meyer Performability Modeling with Stochastic Activity Networks Proc of Real Time Systems Symp Austin USA pp 215 224 1984 Peterson J L Petri nets theory and the modeling of systems Prentice Hall 1981 Movaghar A Stochastic activity networks A new definition and some properties Scientia Iranica 8 4 pp 303 311 2001 M Abdollahi Azgo mi and A Movaghar Coloured stochastic activity networks definitions and behaviour Proc of the 20th Annual UK Performance Eng Workshop UKPEW 04 Bradford UK July 7 8 2004 pp 297 308 A Jalaly Bidgoly A Khalili and M Abdollahi Azgomi Implementation of Coloured Stochastic Activity Networks within the PDETool Framework in Proc of 3rd Asia Int l Conf on Modelling amp Simulation AMS09 2009 pp 710 715 Jogesh K Muppala Gianfranco Ciardo Kishor Trivedi Stochastic Reward Nets for Reliability Prediction 37
34. tion of presented SAN model Timed Activity Distribution rate Exponential 5 Exponential 1 Exponential 1 Exponential 1 Table 2 shows the distribution and rate of all activities The simulation results of the model with confidence level 95 within the confidence interval 0 are presented in Table 3 Table 3 Reward variable specification and simulation results Queue length 52 045 850 94 Rate if Placel Mark 100 return 13 0 0097 0 0009 0 0096 Rate if Placel Mark 0 return 1 0 0094 0 0009 0 0093 Example 2 Modeling a packet generator system using CSANs Consider a simple example of a packet generator system presented in 14 The system generates packets with random protocol type TCP UDP 2 or RTP 3 length and priority and inserts them into an input buffer An error checking e g a CRC check is done on the generated packets If an error is detected the packet will be discarded otherwise it will be routed to output buffers Packets are routed probabilistically to two output buffers with probability 0 599999 and 0 4 The probability of detecting an error is 0 000001 The initial capacity of the system is 6 and it will stop whenever 6 packets are in error and have been discarded The graphical representation of the model is shown in Figure 30 Reward variables color definitions and global variables are also be defined in model editor For example in this case study we define a color named TPacket as follo
35. ure which can be used for colored tokens To add a new color use the graphical menu A color 1s the list of fields with the following properties o Name A unique name that identifies the color o Amn ordered list of fields The type and name of each field must be specified Type of each field must be a built in type Table 1 or a color that 1s defined before 2 Coloured Place o Name A unique name that identifies the color o Color Color of the coloured place determines the type color of tokens can be in the place o Policy The policy determines how tokens are added or removed from the place and can be FCFS for queue like places LCLS for stack like places or Priority o Priority Function The body of function that is used when the policy of the place is Priority o Initial marking To specify the initial marking of a colored place you have to specify the value of a colored token values of all fields and count of that token which should be added to the place for example see Figure 14 in which the initial marking of place has 6 coloured tokens that in 5 of them field a is 1 and field b equals 4 18 PDETool user manual ColorValue Collection Editor Members B a 1 b 4 properties Ol 1fa 3 b 2 Ez LE EE Count Initial Marking Remove Cancel Figure 14 Initial Marking Editor for coloured places Adding editing SRN primitives For constructing and modifying a SRN model you have to u
36. with or greater than zero m0 Initial marking must be as an explicit integer number or value of a global variable within type int e Position Position of a place is a set x y where x and y is horizontal and vertical position of the place in the model editor grid This property as the common property of all graphical elements of SAN is not shown in Property Editor but you can change the position of each element by dragging the element move it and drop it somewhere else 14 E Place Initial Initial Marks E Public Name Figure 7 Place properties 2 Timed Activity e Name A unique name that identifies the timed activity e Distribution It includes both a distribution function and its parameters For example if execution of an activity is distributed exponentially the mean of distribution must be specified Each distribution function has one or more parameters which must be specified in Distribution Editor Figure 9 e Reactivation predicate A Boolean function an expression or a sequence of statements written in C that return a Boolean value which reactivates the activity in a state that the activity is enabled and reactivation predicate is true Reactivation means that a new delay will be sampled from the distribution function and the activity will be scheduled to fire after delay units of time from the current simulation time Some read only properties are also shown in both instantaneous and timed activity in
37. ws TPacket byte Protocol int Len byte Prioriy j The model is composed of a simple place Capacity three coloured places InBuf OutBufl and OutBuf2 five input gates UG IG2 IG3 IG4 and G5 three output gates GenGate OGI and OG2 three timed activities GenPacket Sendl and Send2 and three instantaneous activities Routel Route2 and ErrChk The selection policy for InBuf is FIFO and for OutBufl and OutBuf2 is Priority The Priority function of these two coloured places that determines the priority of sending packets from the each output buffer and other parameters of the model are shown in Table 4 which depicts parameter table for the definition of priority functions of coloured places and enabling predicates and functions of input output gates of the model 32 The CSAN model has also a global variable tempPacket within type TPacket In the initial marking of the model there are three tokens inside Capacity and two coloured tokens inside InBuf There is also one token inside OutBuf and no token inside OutBuf2 OGl OutBufl IG Serv 1 Figure 31 CSAN model of the presented packet generator To evaluate the constructed model modeler must define some reward variables After definition of model and related reward structures the model can be evaluated by Model simulator For example if Reward and Reward2 are steady state rate rewards which denote the average number of tokens in OutBufl and OutBuf2 respectively the s

Manual

Contents

Download Pdf Manuals

Related Search

Related Contents