Peps 2007 User manual
Contents
1. lt exp2 gt lt expl gt lt exp2 gt lt expl gt lt lt exp2 gt lt expl gt gt lt exp2 gt lt expl gt gt lt exp2 gt jogical not ED lt e p1 gt lt esp gt logieal or 6 gt 317 lt 8 logical and 56 gt 3 amp amp 7 lt 8 TEDEN Table 4 1 Operators 4 2 Modeling Examples In this section three examples are presented to illustrate the modeling power and the compu tational effectiveness of PEPS 2007 For each example the generic SAN model is described 4 2 1 A Model of Resource Sharing The first example is a traditional resource sharing model where N distinguishable processes share a certain amount R of indistinguishable resources Each of these processes alternates between a sleeping and a resource using state When a process wishing to move from the sleeping to the using state finds R processes already using the resources that process fails to access the resource and it returns to the sleeping state Notice that when R 1 this model reduces to the usual mutual exclusion problem Analogously when R N all the processes are independent and there is no restriction to access the resources We shall let A be the rate at which process i awakes from the sleeping state wishing to access the resource and u the rate at which this same process releases the resource AW sleeping sleeping sleeping using Using Figure 4 3 Resource Sharing Model v2. 5 1 1 Sparse Markovian Descriptor The first step is to convert the set of small matrices Full Markovian Descriptor created in SANcompilation module in a set of sparse matrices Sparse Markovian Descriptor This pro cedure converts the textual matrices format used in descrption phase to a PEPS 2007 internal representation format This step also implements the aggregation methods Two aggregation methods are implemented in Peps 2007 The first one does an algebrique automata aggregation i e tensor operation are applied in a set of automata The second method applies a replicas aggregation methods More informations about theses techniques can be find in This step is implemented in compile_dsc module compile_dsc Module Implementation This module implements the Markovian Descriptor generation in the internal PEPS format from the standard input textual matrices generated in san compilation phase Source code path peps2007 src ds compile_dsc Required files des dic fct tft res Generated files dsc dct ftb inf rss Command compile_dsc options file Options aggr This option applies the algebrique aggregation method lump This option is used to apply the semantic aggregation method 5 1 2 Normalized Markovian Descriptor The second data manipulation step normalizes the model and extract the matrices diagonal elements The diagonal generation removes all synchronizing adjust matrices and all diagonal
3. probability of average number all resources being used all resources being available the first process use the resource of occupied resources 4 2 2 First Server Available Queue The second example considers a queue with common exponential arrival and a finite number C of distinguishable and ordered servers C i 1 C As a client arrives it is served by the first available server i e if C4 is available the client is served by it otherwise if Ca is available the client is served by it and so on This queue behavior is not monotonic so as far as we can ascertain there is no product form solution for this model The SAN model describing this queue 26 is presented in Figure The basic technique to model this queue is to consider each server as a two state automaton states idle and busy The arrival in each server is expressed by a local event called L with a functional rate that is nonzero and equal to A if all preceding servers are busy and zero otherwise At a given moment only one server the first available has a nonzero arrival rate The end of service at each server is simply a local event D with constant rate pi Figure 4 5 First Server Available Model The PEPS 2007 textual formats for this model is as follows 2 22 2 FSA HON 2222 YA with functions c 4 sss sss SSS SSS SSS SSS SSS SSS SSS SSS SS SSS SSS SS SSS SSS SSS SS SS SSS SSS
4. 1 Mu14 n5_c2 Mu02 Mu04 n5_c1 loc 1_FL_classi_queue1 FL_classi_queuel loc loc syn syn syn l_rot_classi_queue3to0UT rot_class1_queue3toOUT 1 rot classi1 gueue5toDUT rot_class1_queue5toOUT s_class1_queueltoqueue2 rot class1 gueueltogueue 2 s_class1_queueltoqueue4 rot classi gueueltogueue4 s_class1_queue2toqueue3 rot class1 gueue2togueue3 30 syn syn syn syn syn syn s_classi_queue2toqueue5 s_classi_queue4toqueue3 s_classi_queue4toqueue5 s_class2_queueltoqueue4 s_class2_queue4toqueue5 s_class2_queue5toqueuel rot class1 gueue2togueue5 rot class1 gueuedtogueue3 rot class1 gueuedtogueue5 rot class gueueltogueue4 rot class gueuedtogueue5 rot class gueue5togueuel reachability st amp amp st amp amp st amp amp st classi_queuel classi_queue4 classi_queue5 class2_queuel class2_queue1 lt k1 class2_queue4 lt k4 class2_queue5 lt k5 class2_queue4 st class2_queue5 N2 network man continuous aut class agueuel stt n K1 to to aut classi_queue2 stt n K2 to to aut classi_queue3 stt n K3 to to aut classi_queue4 stt n K4 to to aut classi_queue5 stt n K5 to to aut class2_queueil stt n K1 to to aut class2_queue4 stt n K4 to to aut class2_queue5 stt n K5 to to results nri00 st nri01 st nri02 st nri
5. Identifiers can be used to define an interval 1 1D1 5 7 D2 where ID1 and ID2 are identifiers with constant values In all cases domain must respect an increasing value order e lt exp gt is areal number or a mathematical expression The mathematical expressions are described in Section A real number has one of the following formats an integer such as 12345 a floating point real number such as 12345 6789 a real number with mantissa and exponent such as 12345E or e or 10 or 12345 6789e 100 Sets of indexes are useful for defining numbers of events automata or states that can be described as replications A group of replicated automata of A with the set in index 0 2 5 8 10 defines the set containing the automata A 0 A 1 A 2 A 5 A 8 A 9 and A 10 4 1 2 Events The events block defines each event of the model given e its type local or synchronizing e its name an identifier e its firing rate a constant or function previously defined in the identifiers block Additionally events can be replicated using the sets of indexes domains This facility can be used when events with the same rate appear in a set of automata Format of the events block events loc lt evt_name gt replication_domain lt rate gt syn lt evt_name gt replication_domain lt rate gt e loc define the event type as local event e syn define the
6. These may be used to generate the transition matrix of the Markov chain representing its dynamic behavior using only elementary matrices This formulation of the transition matrix is called the SAN descriptor Chapter 3 PEPS Presentation PEPS is software package implemented using the C programming language and although the source code is quite standard only Linux and Solaris version have been tested The main features of version 2000 are e Textual description of continuous time SAN models without replicas e Stationary solution of models using Arnoldi GMRES and Power iterative methods e Numerical optimization regarding functional dependencies diagonal pre computation pre conditioning and algebraic aggregation of automata and e Results evaluation PEPS 2003 includes some bug corrections and three new features e Compact textual description of continuous time SAN models e Semantic aggregation of SAN with replicas e Numerical solution using probability vectors with the size of the reachable state space and e Fast er function evaluation PEPS 2007 is able to e Read a file which describes a SAN in a textual format replicas features are improved This interface is described in Chapter Section provides simple examples of models that can be used to experiment with the software e Compile a SAN model to form all the small matrices then to assemble them to construct the complete SAN descriptor At t
7. elements in local matrices All theses elements will be placed in a diagonal vector used by the solutions methods This technique improves the solution methods performance In this step some model analisys are performed as product and reachable space state analysis constant functions replacement matrices multiplication order generation etc Two modules was implemented to perform this step The first one uses a extended vector implementation norm_dsc_ex and the second one uses a sparse vector implementation to store the reachable space state norm_dsc_ex Module Implementation This module implements the Markovian Description normalization using a extended vector Source code path peps2007 src ds norm_dsc_ex Required files dsc dct ftb inf rss Generated files cnd ftb rss Command norm_dsc_ex file norm_dsc_sp Module Implementation This module implements the Markovian Description normalization using a sparse vector Source code path peps2007 src ds norm_dsc_sp Required files dsc dct ftb inf rss Generated files cnd ftb rss Command norm_dsc_sp file 5 2 Harwell Boeing Format HBF 5 2 1 HBF Generation This module performs the eguivalent Markov Chain generation from the SAN model This Markov Chain represented by a transition matrix is stored in HBF format This generation is implemented in gen hbf module gen hbf Module Implementation This module implements the eguivalent markovian model
8. lt aut name gt lt stt name gt gives the sum of the rewards of the automata in the interval sum_rw processA processD util lt aut_ name gt lt aut_name gt which are in the state lt stt_name gt prod_rw lt aut_name gt lt aut_name gt product of the rewards of the current of the automata of interval prod_rw processA processD lt aut_name gt lt aut_name gt prod_rw lt aut_name gt lt aut name gt lt stt name gt product of the rewards of the current states of the automata of interval product_rw processA processD util lt aut_name gt lt aut_name gt which are in the state lt stt name gt Arithmetic Operators lt expl gt T lt erp gt sum of lt ezpl gt and lt exp2 gt lt expl gt lt exp2 gt substraction of lt exp2 gt minus lt expl gt lt expl gt lt exp2 gt product of lt expl gt and lt exp2 gt 5 3 lt expl gt lt exp2 gt division of lt expl gt by lt exp2 gt lt expl gt QU lt exp2 gt integer division of lt expl gt and lt exp2 gt lt expl gt MOQ lt exp2 gt rest of integer division of lt expl gt by lt exp2 gt a as ea ae Es Relational Operators lt expl gt lt exp2 gt if lt expl gt is equal to lt exp2 gt gives true 1 else false 0 lt expl gt
9. smallest 2222185315615217e 01 0 smallest 2222218259405468e 01 0 smallest 2222221796718014e 01 0 smallest 2222222176534054e 01 0 smallest 2222222217316495e 01 0 smallest 4861419985454539e 02 5481023256267900e 02 5547552710857144e 02 5554696256649189e 02 5555463289038043e 02 5555545648513671e 02 5555554491795035e 02 5555555441335135e 02 5555555543291231e 02 Iteration 10 largest Iteration 20 largest Iteration 30 largest Iteration 40 largest Iteration 50 largest Iteration 60 largest Iteration 70 largest Iteration 80 largest Iteration 90 largest Iteration 91 Power solution DDDNDDNDDNDDDNDDN III ma aa A Number of iterations 92 user time spent 8 3432745304548583e 20 seconds system time spent 2 4987471944001860e 19 seconds real time spent 3 4348982153460383e 03 seconds Residual Error 7 0642436345025317e 11 The method converged solution found file v vct saved 3 3 3 3 3 3 3 3 3 file rs tim saved Thanks for using PEPS 10 Part I PEPS BASIC MODULES Chapter 4 Interface This chapter presents the SAN textual interface to PEPS 2007 This new textual interface is full compatible with PEPs 2003 and incorporates new features to replications sets Addictionally we present some modeling examples to show the interface powerful to model systems based replicated components 4 1 SAN Textual Interface A textu
10. a prob ability of occurrence is assigned to each possible transition The label on the transition is given as evt prob where evt is the event name and prob is the probability of occurrence When not explicitly specified this probability is set to 1 0 There are basically two ways in which stochastic automata interact First the rate at which an event may occur can be a function of the state of other automata Such rates are called functional rates Rates that are not functional are said to be constant rates The probabilities of occurrence of events can also be functional or constant Second an event may involve more than one automaton the occurrence of such an event triggers transitions in two or more automata at the same time Such events are called synchronizing events They may have constant or functional rates An event which involves only one automaton is said to be a local event Consider a SAN model with N automata and E events It is an N component Markov chain whose components are not necessarily independent due to the possible presence of functional rates and synchronizing events A local state of the i th automaton AM where i 1 N is denoted x while the complete set of states for this automaton is denoted SU and the cardinality of S is denoted by n A global state for the SAN model is a vector amp x 2 S S x x SM is called the product state space and its cardinality is equal to ja n The reachable sta
11. conducted in a SAN context The modular structure of a SAN model has an impact on the mathematical structure of the Markov chain in that it induces a product form represented by a tensor product Other formalisms have used this Kronecker technique as e g stochastic Petri nets and process algebras The basic idea is to represent the matrix of the Markov chain by means of a tensor Kro necker formula called descriptor This formulation allows very compact storage of the matrix Moreover computations can be conducted using only this formulation thereby saving considerable amounts of memory as compared to an extensive generation of the matrix Recently other for mats which considerably reduce the storage cost such as matrix diagrams have been proposed They basically follow the same idea components of the model have independent behaviors and are synchronized at some instants when they behave independently their properties are stored only once whatever the state of the rest of the system Using tensor products a single small matrix is all that is necessary to describe a large number of transitions Using matrix diagrams a repre sentation of the transition matrix as a graph transitions with the same rate are represented by a single arc At this time SAN algorithms use only Kronecker technology but a SAN model could also be solved using matrix diagrams A particular SAN feature is the use of functional rates and probabil
12. in a simple text file and the file name must have san as extention You can use a simple text file editor like vi to create your file model The model description must respect the SAN interface described in Chapter Some models examples are presented in Section 3 3 Compiling a model The first step to solve a SAN model is to compile the san model file to generate the Full Markovian Descriptor files To compile a san file we use compile_san module as follow Command compile_san file Typical module output compile_san rs Start model compilation First Passage Compiling identfier block Compiling event block Compiling reachability function Compiling network block Compiling results block Creating automata and states structures Second Passage Compiling identfier block Compiling event block Compiling reachability function Writing events informations Compiling network block Compiling results block Checking events integrity Model compiled Creating description files model file des rs des saved file des rs dic saved file des rs fct saved file des rs tft saved file des rs res saved The description files to rs model were created in des directory The second step in the compiling phase is to transform the Full Markovian Descriptor files in Sparse Markovian Descriptor This step keeps only non zero values of the matrices and run the aggregation procedures if choice To perfor
13. in hbf format generator from the SAN Markovian Descriptor Source code path peps2007 src ds gen hbf Required files dsc dct ftb inf rss Generated files hbf Command genhbf option file Option conv This option converte the sparse matrix generated by PEPS C language in a sparse matrix in MARCA pattern Fortran language 34 Chapter 6 Solution Methods PEPS 2007 implements two sets of methods to analytical solutions of a SAN model The first set works with a kronecker format and the second set works with a sparse format HBF 6 1 Kronecker Format 6 1 1 Shuffle The shuffle method basic idea is multiply the probability vector by the set of matrices that compose the Markovian Descriptor In fact each small matrix multiplies a part of the vector The sum of all small matrices multiplication is a complete vector descriptor multiplication This multiplication method was implemented in two versions The first one works with extended vector with the global espace state size The second one works with sparse vector only the reachable space state size solve_cnd_ex Module Implementation This module implements the solution methods using an extended vector Source code path peps2007 src solve solve_cnd_ex Required files cnd ftb rss inf dct Generated files vct tim Command solve_cnd_ex options file solve_cnd_sp Module Implementation This module implements the solution methods using a sparse
14. res name gt lt exp gt 3 e lt res_name gt is a single identifier e lt exp gt isa mathematical expression The mathematical expressions are described in Section 2 4 1 6 Function Expressions This section presents the possibilities that PEPS provides to build expressions and functions In general the expressions are similar to common mathematical expressions with logical and arithmetic operators The arguments of these expressions can be constant input numbers but can also be automata or states identifiers The format of the operators is summarized in table The internal format used in PEPS solver is given in the fourth column and it is useful only when debugging PEPS The arithmetic operators are x div mod max and min and are not typed integer or real values PEPS expressions do not have operators priorities and are evaluated from the left to the right To specify priorities it is necessary to use brackets For example 5 6 7 is computed as 5 6 7 in PEPS The relational operators are lt gt lt gt Their result is 1 coding for TRUE if the relation is verified and 0 coding for FALSE otherwise The logical operators are not coded with or with and with amp amp XOR with As we already mentioned the arguments of these operators can be consta
15. 03 st nri04 st nrii10 st nrii3 st nrii4 st 1 FL class1 gueuel s_classi_queueitoqueue2 s_classi_queueitoqueue4 s_classi_queueitoqueue2 s_classi_queue2toqueue3 s_classi_queue2toqueue5 s_classi_queue2toqueue3 s_classi_queue4toqueue3 l_rot_class1_queue3to0UT s_classi_queueitoqueue4 s_classi_queue4toqueue3 s_classi_queue4toqueue5 s_classi_queue2toqueue5 s_classi_queue4toqueue5 l_rot_class1_queue5to0UT s_class2_queue5toqueuel s_class2_queueltoqueue4 s_class2_queueltoqueue4 s_class2_queue4toqueue5 s_class2_queue4toqueue5 s_class2_queue5toqueuel classi_queuel classi_queue2 classi_queue3 classi_queue4 classi_queue5 class2 gueuel class2_queue4 class2 gueue5 31 Chapter 5 Data Structure The data structures used in PEPS 2007 can be divided in two large blocks The first block uses a Kronecker tensor format and the second one uses a sparse matrix format HBF Each block and theirs modules implementation are described below 5 1 Kronecker Format In Kronecker format we use a set of small matrices to store a large model This structured format allows to save storage space in comparison to non structured format Compiling phase for kronecker structures is composed by two step The first one transforms a Full Markovian Descriptor in a Sparse Markovian Descriptor and the second one transforms a Sparse Markovian Descriptor in a Continuous Normalized Descriptor Theses steps are described below
16. 10 Sri13 Sril4 Lri00 Mu00 Mu01 Mu02 Mu03 Mu04 Mu10 Mu13 Mul4 F_queuel F_queue2 F_queue3 F_queue4 F_queue5 FL class1 gueuel ni ci ni c2 nd ci nd c2 n5_ci n5_c2 rot_classi_queueitoqueue2 rot class1 gueueitogueued rot class1 gueue2togueue3 rot class1 gueue2togueue5 rot class1 gueuedtogueue3 rot class1 gueuedtogueue5 rot_class2_queueitoqueue4 rot_class2_queue4toqueue5 rot_class2_queue5toqueuel 10 O O OOOO OO OPRU SEUN E 1 5 E 8 24 81 1 Sri00 1 Sri01 1 Sri02 1 Sri03 1 Sri04 1 Sri10 1784118 1 Sri14 st st st st st st st st st st st ER class1 gueueil st class2_queue1 st class1_queue4 st class2_queue4 st class1_queue5 st class2_queue5 st rot class1 gueue3toDUT rot class1 gueue5toDUT events class1 gueuel classi_queue2 classi_queue3 classi_queue4 classi_queue5 Lri00 F_queuel MQN model Mixed Queueing Network lt K2 lt K3 a st class2_queuei1 lt kl st class2_queue4 lt k4 st class2_queue5 lt k5 class2_queue1 class2_queue1 class2_queue4 class2_queue4 class2_queue5 class2_queue5 classi_queuei st classi_queuei st classi_queue4 st classi_queue4 st classi_queue5 st classi_queue5 st 0 5 Mu00 ni1_ci 0 5 Mu00 ni1_ci 0 5 Mu01 0 5 Mu01 0 5 Mu03 n4_ci 0 5 Mu03 n4_ci 1 Mu10 n1_c2 1 Mui3 n4_c2
17. 3 stt using to sleeping R3 aut P4 stt sleeping to using G4 stt using to sleeping R4 results full nb using empty nb using usel st Pi average nb using amount of resources rate for leaving a resource for process 1 rate for requesting a resource for process 1 nb using lt R rate for leaving a resource for process 2 rate for requesting a resource for process 2 nb using lt R rate for leaving a resource for process 3 rate for requesting a resource for process 3 nb using lt R rate for leaving a resource for process 4 rate for requesting a resource for process 4 nb using lt R cal event Gi has rate f1 cal event Ri has rate mul cal event G2 has rate f2 cal event R2 has rate mu2 cal event G3 has rate f3 cal event R3 has rate mu3 cal event G4 has rate f4 cal event R4 has rate mu4 ing lt R only the states where at the most R resources are being used are reachable network rsi continuous R probability of all resources being used 0 probability of all resources being available using probability that the first process uses the resource 5 average number of occupied resources It was not possible to use replicators to define all four automata in this example In fact the use of replications is only possible if all automata are identical which is not the case here since each automaton has different events with different rates If all the processes had the sam
18. EPS translates it into an internal index The user should be careful when using this function it might lead to errors when there are automata having a state named lt stt_name gt but with different internal index or when there are automata without a state named stt name gt PEPS gives a warning in this case 20 nb lt aut name gt lt aut_name gt lt stt name gt it is an extension of the preceding function but the count is done on the automata interval lt aut_name gt lt aut name gt The notion of interval refers to the total ordering described above This notation is very useful when an automaton is replicated and the interval is exactly all the replicated automata rw lt aut_name gt in SAN rewards may be associated to states This function gives the current reward of automaton lt aut_name gt lt aut_name gt is an external identifier and the output of this function is a reward thus a real or integer value This function is very similar to st lt aut name gt Remember that if the reward is not explicitly given by the user the internal state index is used as a reward This makes sense when the states coded 0 1 2 etc are the number of customers in a queue In this case the two functions rw lt aut_name gt and st lt aut_name gt are identical sum rw lt aut_name gt lt aut name gt gives the sum of the current rewards of the automata in the interval aut name gt
19. PEPS 2007 User manual The PEPS develoveper team Anne Benoit Leonardo Brenner Paulo Fernandes Brigitte Plateau Ihab Sbeity William J Stewart The PEPS 2007 User manual author Leonardo Brenner November 10 2008 Contents Chapter 1 Introduction Parallel and distributed systems can be modeled as sets of interacting components Their be havior is usually hard to understand and formal techniques are necessary to check their correctness and predict their performance A Stochastic Automata Network SAN is a formalism to facilitate the modular description of such systems and it allows the automatic derivation of the underlying Markov chain which represents its temporal behavior Solving this Markov chain for transient or steady state probabilities allows us to derive performance indexes The main difficulties in this process are the complexity of the model and the size of the generated Markov chain Several other high level formalisms have been proposed to help model very large and complex continuous time Markov chains in a compact and structured manner For example queueing net works generalized stochastic Petri nets stochastic reward nets and stochastic activity nets are thanks to their extensive modeling capabilities widely used in diverse application domains and notably in the areas of parallel and distributed systems The pioneer work that use of Kronecker algebra for solving large Markov chains has been
20. SSS SSS SS SSS SSS SSS SSS SSS SSS SSS SSS SSSSSSSSS5 identifiers lambda 5 mul 6 f1 lambda mu2 5 2 st C1 busy lambda mu3 4 3 nb C1 C2 busy 2 lambda mu4 3 4 nb C1 C3 busy 3 lambda events loc Li 1 loc D1 mul loc L2 2 loc D2 mu2 loc L3 3 loc D3 mu3 loc L4 4 loc D4 mu4 reachability 1 network fsa continuous aut C1 stt idle to busy L1 stt busy to idle D1 aut C2 stt idle to busy L2 stt busy to idle D2 aut C3 stt idle to busy L3 stt busy to idle D3 aut C4 stt idle to busy L4 stt busy 27 to idle D4 results full nb busy C empty nb busy 0 usel st P1 busy average nb busy The same model can also be expressed as a SAN without functions In this case each function is replaced by a synchronizing event that synchronizes the automaton representing the server ac cepting a client with all previous automata in the busy state The PEPS 2003 textual formats for this alternative model is as follows WE FA HON 2222222 with synchronizing events C 4 1 seen sess ee sae esas s esas ease na esse nn identifiers lambda 5 mul 6 mu2 5 mu3 4 mu4 3 events loc L1 lambda C1 loc D1 mut C1 syn L2 lambda C1 C2 loc D2 mu2 C1 syn L3 lambda C1 C2 C3 loc D3 mu3 C3 syn L4 lambda C1 C2 C3 C4 loc D4 mu4 c4 reachability 1 network fsa2 continuou
21. a domain identifier defined in identifiers block e reward is optional and specifies the state reward When it is not specified PEPS gives a default value to the reward which is the internal state index From Description The from section is quite similar to the stt section but it cannot define local states This is commonly used to define additional transitions which cannot be defined in the stt section A typical use of the from section is to define a transition leaving from only one state of a group of replicated states to a state outside the group e g a queue with particular initial or final states may need this kind of transition definition Format of the from block from lt stt name gt to lt sttmame gt replication_domain f cond lt evt_name gt replication_domain lt prob gt I f_cond Transitions description e lt stt name gt is a state identifier defined in stt section Use x after the state identifier TEE to appoint a specific state in a group of replicated states x must be an identifier previously defined in identifiers block Transition Description A description of each output transition from this state is given by the definition of a to section The identifier lt stt_ name gt inside the parenthesis indicates the output state of this transition x can be used to appoint to a specific or a set of replicated states In this case
22. al formalism for describing models is proposed and it keeps the key feature of the SAN formalism its modular specification PEPS 2007 incorporates a graph based approach which is close to model semantics In this approach each automaton is represented by a graph in which the nodes are the states and the arcs represent transitions fired by the occurrence of events This textual description has been kept simple extensible and flexible e Simple because there are few reserved words just enough to delimit the different levels of modularity e Extensible because the definition of a SAN model is performed hierarchically e Flexible because the inclusion of replication structures allows the reuse of identical automata and the construction of automata having repeated state blocks with the same behavior such as found in queueing models This section describes the PEPS 2007 textual formalism used to describe SAN models To be compatible with PEPS 2007 any file describing a SAN should have the suffix san Figure shows an overview of the PEPS input structure A SAN description is composed of five blocks Figure which are easily located with their delimiters in bold The other reserved words in the PEPS input language are indicated with an italic font The symbols lt and gt indicate mandatory information to be defined by the user The symbols and indicate optional information 1The word delimiters is use
23. astic Reward Nets for Reliability Prediction Communications in Reliability Maintainability and Serviceability v 1 n 2 pp 9 20 1994 B Plateau De Evaluation du Parellelisme et de la Synchronisation These de Doctorat d Etat Paris Sud Orsay France 1984 B Plateau On the Stochastic Structure of Parallelism and Synchronization Models for Dis tributed Algorithms In Proc ACM Sigmetrics Conference on Measurement and Modeling of Computer Systems Austin Texas 1985 39 15 16 17 18 19 20 21 B Plateau J M Fourneau K Lee PEPS A Package for Solving Complex Markov Models of Parallel Systems In R Puigjaner D Potier eds Modeling Techniques and Tools for Computer Performance Evaluation 1988 PEPS team Pers 2003 Software Tool On line document available at http www apache imag fr software peps visited Feb 14th 2003 Y Saad Iterative Methods for Sparse Linear Systems PWS Publishing Company 1995 W H Sanders J F Meyer An Unified Approach for Specifying Measures of Performance De pendability and Performability Dependable Computing for Critical Applications v 4 pp 215 238 1991 W J Stewart MARCA Markov Chain Analyzer IEEE Computer Repository No R76 232 1976 W J Stewart Introduction to the Numerical Solution of Markov Chains Princeton University Press 1994 Sun Microsystems The JIT Compiler Interface Specification On line document available at http java sun co
24. ce for process 1 rate for leaving a resource for process 2 rate for requesting a resource for process 2 rate for leaving a resource for process 3 rate for requesting a resource for process 3 rate for leaving a resource for process 4 rate for requesting a resource for process 4 domain to describe the available resources pool event G1 has rate f1 and appears in automata P1 and RP event Ri has rate mui and appears in automata P1 and RP event G2 has rate f2 and appears in automata P2 and RP event R2 has rate mu2 and appears in automata P2 and RP event G3 has rate f3 and appears in automata P3 and RP event R3 has rate mu3 and appears in automata P3 and RP event G4 has rate f4 and appears in automata P4 and RP event R4 has rate mu4 and appears in automata P4 and RP P1 P4 using st RP the number of Processes using resources must be equal to number network rs2 continuous aut P1 stt sleeping to using stt using to sleeping aut P2 stt sleeping to using stt using to sleeping aut P3 stt sleeping to using stt using to sleeping aut P4 stt sleeping to using stt using to sleeping aut RP stt n res_pool to G1 G2 to R1 R2 results full st RP empty st RP use1 st P1 average st RP G1 R1 G2 R2 G3 R3 G4 R4 G3 R3 G4 R4 n R n 0 using of occupied resources in the Resource Pool probability of probability of
25. d of a set of automata each automaton is composed of a set of states each state is connected to a set of output arcs and each arc has a set of labels identifying events local or synchronizing that may trigger this transition network Example state 00 f Figure 4 2 Structure of network hierarchy The first level named network includes general information such as the name of the model and the type of time scale of the model Format of the network block 15 network lt net name gt lt type gt aut lt aut_name gt replication_domain stt lt stt name gt replication_domain reward to lt stt name gt replication_domain f cond lt evt name gt replication_domain lt prob gt f cond Automata description e lt net_name gt is the name of the model It is a string of alphanumeric characters beginning with a letter e lt type gt is the time scale of the model Two type are possible continuous or discrete Currently only continuous model analysis is available in PEPS 2007 The following subsections provide further detail on each of the levels of the network description Automaton Description In this level each automaton is decribed The delimiter of the automaton is the reserved word aut and the name of the automaton Optionally a domain definition can be used to replicate it i e to create a number of copies o
26. d solve_hbf options file Options iter n Set the maximum number of iteration to n n default value is 1000 min_err err Set the tolerance accepted to err err default value is 1 0e 10 iter type type This option set the stop iteration criterion Three type are proposed fix set stop criterion to fixed iteration number stb set stop criterion to stability test cnv set stop criterion to convergence test The convergence test is the default option err type This option set the error test Three type are proposed abs_ind set the error test to maximum of individual absolute errors The maximum of individual absolute errors is the default option abs_acc set the error test to accumulated individual absolute error rel ind set the error test to maximum individual relative error vec_type Set the initial vector type We have three possibilities eq set the initial vector to equiprobable Default option in read a user vector as initial vector The vector is read from a file ap use an aproximated by the inverse of the diagonal vector 38 Bibliography 10 11 12 13 14 M A jmone Marsan G Balbo G Conte S Donatelli G Franceschinis Modeling with General ized Stochastic Petr Nets John Wiley 1995 K Atif and B Plateau Stochatic Automata Networks for Modeling Parallel Systems IEEE Transactions on Software Engineering v 17 n 10 pp 1093 1108 1991 A Benoit L Brenner P Fernande
27. d to indicate necessary symbols having a fixed position in the file identifiers lt idname gt lt exp gt lt dom_name gt i j 3 events without replication loc lt evt name gt lt rate gt syn lt evt name gt lt rate gt with replication loc lt evtname gt replication_domain lt rate gt syn lt evt name gt replication_domain lt rate gt partial reachability lt exp gt network lt net name gt lt type gt aut lt aut name gt replication_domain stt lt stt name gt replication_domain reward to lt stt name gt replication_domain f cond lt evt name gt replication_domain lt prob gt f cond lt evt name gt replication_domain lt prob gt f cond from lt stt name gt to lt stt name gt replication_domain f cond lt evt name gt replication_domain lt prob gt I f_ cond stt lt sttmame gt replication_domain reward to lt stt name gt replication_domain f cond lt evt name gt replication_domain lt prob gt f cond aut lt autname gt replication_domain results lt resname gt lt exp gt 3 Figure 4 1 Modular structure of SAN textual format 4 1 1 Identifiers and Domains This first block identifiers contains all declarations of parameters numerical values func tions or sets of indexes domains to be used for replicas in t
28. e acquiring A and releasing u rates this example could be represented more simply as N 4 R 2 identifiers N 0 3 R 2 amount and identifier of processes amount of resources 24 mu 6 rate for leaving a resource for all processes lambda 3 rate for requesting a resource for all processes i at current automaton index f lambda nb using lt R events loc Acq N f local events Acq have rate f loc Rel N mu local events Rel have rate mu reachability nb using lt R only the states where at the most R resources are being used are reachable network rs1 continuous aut P N stt sleeping to using Acqli stt using to sleeping Relli results full nb using R probability of all resources being used empty nb using 0 probability of all resources being available usel st P 0 using probability that the first process uses the resource average nb using average number of occupied resources We wish to point out that in the PEPS documentation a number of variants of this model are included to show that it is possible with only simple modifications to introduce a complete set of related models Within the scope of this manual it is interesting to describe a specific variation of this model that describes exactly the same problem but which does not use functions to represent the resource contention In fact in this case and in many oth
29. e the number of customers in the system Na In this example all queues block when the destination queue is full even though other behavior e g loss could be easily modeled with the SAN formalism Figure 4 6 Mixed queueing network The equivalent SAN model for this example has eight automata AG AG AE AG AG AA AG AG representing each possible pair customer gueue The model has two local events arrival and departure of class 1 customers and nine synchronizing events the routing paths for customers from both classes Functional transitions are used to represent the capacity restriction of admission in queues accepting both classes of customer The reachability function of the SAN model representing this gueueing network must take into account both the unreachable states due to the use of two automata to represent a gueue accepting two classes of customer and the fixed number of customers of class 2 Assuming queue capacities K 10 Ko 5 K3 5 K4 8 Ks 8 and a total population of class 2 customers N2 equal to 10 the equivalent SAN model has a product state space containing 28 579 716 states of which only 402 732 are reachable This model is described as follow More detailes can be obtained from the PEPS web page 29 identifiers N2 10 K1 K2 K3 Ka K5 kl k2 k3 k4 k5 Sri00 Srio01 Sri02 Sri03 Sri04 Sri
30. ers synchronizing events can be used to generate an equivalent model without functional rates fregeuntly with many more automata states and or synchronizing events Figure presents this new model where an automaton is introduced to represent the resource pool The resource allocation events G rate A and release events R rate u that were formerly described as local events will now be synchronizing events that increment the number of occupied resources at each possible allocation and decrement it at each release The resource contention is modeled by the impossibility of a process passing to the using state when all resources are occupied i e when the automaton representing the resource is in the last state where only release events can happen AW AW Al sleeping sleeping sleeping R Rz Gy using using using Gi Go Gn R Figure 4 4 Resource Sharing Model without functions version 2 The PEPS 2003 textual format of this model is as follows RS model version 2 N 4 R 2 identifiers R 2 mul 6 lambdai 3 mu2 5 lambda2 4 mu3 4 lambda3 6 mu4 3 lambda4 5 res_pool 0 R events syn G1 f1 P1 RP syn R1 mu1 P1 RP syn G2 f2 P2 RP syn R2 mu2 P2 RP syn G3 f3 P3 RP syn R3 mu3 P3 RP syn G4 f4 P4 RP syn R4 mu4 P4 RP reachability nb amount of resources rate for leaving a resource for process 1 rate for requesting a resour
31. ersion 1 In our SAN representation Figure each process is modeled by a two state automaton AM the two states being sleeping and using We shall let st A denote the current state of automaton AG Also we introduce the function N f 6 gt 6 st A using lt n i l where b is an integer function that has the value 1 if the Boolean b is true and the value 0 otherwise Thus the function f has the value 1 when access to the resource is permitted and has the value 0 otherwise Figure provides a graphical illustration of this model called RS1 In this representation each automaton A has two local events e G which corresponds to the i th process getting a resource with rate X f e Ri which corresponds to the i th process releasing a resource with rate ui The textual san file describing this model is RS model version 1 N 4 R 2 TE identifiers R 2 mul 6 lambdai 3 f1 lambdai mu2 5 lambda2 4 f2 lambda2 mu3 4 lambda3 6 3 lambda3 mu4 3 lambda4 5 4 lambda4 events loc G1 f1 lo loc R1 mul lo loc G2 2 lo loc R2 mu2 lo loc G3 3 lo loc R3 mu3 lo loc G4 4 lo loc R4 mu4 lo reachability nb us aut P1 stt sleeping to using G1 stt using to sleeping Ri aut P2 stt sleeping to using G2 stt using to sleeping R2 aut P3 stt sleeping to using G
32. event type as synchronized event 14 e lt evt name gt the event identifier begins with a letter and is followed by a sequence of letter or numbers The maximum length of an identifier is 128 characters e replication domain is a set of indexes The replication_domain must be a domain iden tifier defined in identifiers block An event can be replicated til three levels Each level is defined by replication_domain For example an event replicated in two levels is defined as lt evt name gt replication_domain replication_domain e lt rate gt defines the rate of the event It must be an expression identifier declared in the identifiers block 4 1 3 Reachability Function The reachability block contains a function defining the reachable state space of the SAN model Usually this is a Boolean function returning a nonzero value for states of S that belongs to S A model where all the states are reachable has the reachability function defined as any constant different from zero e g the value 1 Optionally a partial reachability function can be defined by adding the reserved word partial In this case only a subset of S is defined and the overall S will be computed by PEPS 2007 Format of the reachability block partial reachability lt exp gt 4 1 4 Network Description The network block is the major component of the SAN description and has an hierarchical structure a network is compose
33. f this automaton In this case if i is a valid index of the defined domain and A is the name of the replicated automaton then Afi is the identifier of one automaton Format of the aut block aut lt aut_name gt replication_domain stt lt stt name gt replication_domain reward to lt stt name gt replication_domain f cond lt evt name gt replication_domain lt prob gt I f_cond States description e lt aut_ name gt is the name of the automaton It is an alphanumeric identifier and it may be used for expression definitions e replication domain is a set of indexes The replication_domain is a domain identifier This identifier must defined in identifiers block State Description The stt section defines a local state of the automaton Format of the stt block stt lt stt name gt replication_domain reward to lt stt name gt replication_domain f cond lt evt_name gt replication_domain lt prob gt I f_cond Transitions description 16 e lt stt name gt is the state identifier which might be used in function evaluation PEPS uses an internal index for the states for each automaton The first declared state of an automaton gets the internal index also called internal state id zero the second gets 1 and so on e replication domain is the number of times that the state appears in the automaton It is described by
34. have been previously defined in events block Use x after the lt evt_name gt to specify a replicated event or a set of replicated states In this case three situation are possibles use a constant to define a static state use a function to define one variable event index where the target event index is defined by the current automaton state index or the target state use a domain to define multiply transitions Remember we can have three replications level for each event the three situations described here are able in each replication level To address events replicated in two or three levels you must use x x and x x x respectively e lt prob gt is the routing probability for this event If only one destination is possible this information can be omitted The lt prob gt can be a real value or an expression identifier defined in identifiers block e f_cond defines a condition to include an event f_cond is an function identifier previously defined in identifiers block Normally this function value depend of the current automaton and or current and or target state 4 1 5 Results Description In this block the functions used to compute performance indexes of the model are defined The results given by PEPS are the integral values of these functions with the stationary distribution of the model This module is optional Format of the results block 18 results lt
35. he model definition An identifier lt id_name gt can be any string of alphanumeric characters The numerical values and functions are defined according to a C like syntax In general the expressions are similar to common math ematical expressions with logical and arithmetic operators The arguments of these expressions can be constant input numbers input parameters of the model automata identifiers or states identifiers In this last case the expressions are functions defined on the SAN model state space For example the number of automata in state n0 which gives an integer result can be expressed as nb n0 A function that returns the value 4 if two automata Al and A2 are in different states and the value 0 otherwise is expressed as st Al st A2 4 Comparison operators return the value 1 for a true result and the value 0 for a false result The format of an expression is described in Section Format of the identifiers block identifiers lt idname gt lt exp gt 13 lt dom_name gt i j e lt id_name gt is an expression identifier which begins with a letter and is followed by a sequence of letter or numbers The maximum length of an expression identifier is 128 characters e lt dom name gt is a domain identifier It is a set of indexes A domain can be defined by an interval 1 3 by a list 1 2 3 or by list of intervals 1 3 5 7 9
36. his level a choice of granularity is given to the user some automata can be grouped to form an equivalent SAN with fewer but larger automata Theses features are described in Chapter e Provide the user with a selection of iterative solution methods to compute stationary and transient probability vector and a number of numerical options as it is explained in Chapter e Inspect data structures such as the reachable state space the stationary probability vector and compare two of them and the SAN descriptor e Output results and data structure files results probability vectors SAN descriptor HBF format of the descriptor compatible with the software MARCA PEPS 2007 is composed by some modules Each module implements a step to a model resolution The modules are grouped in three phases Description Compiling and Solution Description phase is composed by the interface modules The data structures modules compose the compiling phase and the solution phase concerns the solution modules The next sections presents a brief description of the steps from to describe a model til to solve its in the PEPS software Including PEPS installation procedures 3 1 Pers 2007 Installation Being a academic open source software the PEPS 2007 installation is quite simple and do not demand any special feature from your system The Makefile does not perform any test to verify the availability of the GNU C compiler in the system This compile
37. is 2 If there are replications the corresponding offset is applied For a single queue a state is replicated and it works as follows take a queue with a block of replicated states This block has one state rep replicated four times Then the internal index ranges from 0 to 3 in the order repl0 rep 1 rep 2 and rep 3 but the first rep 0 and the last rep 3 have some transitions to outside the group ignored e PEPS maintains a global for all the automata table giving a correspondence between a state external identifier and state internal index called name index table If several distinct automata have the same state identifier a warning is output if and only if these states do not have the same internal index This situation might lead to errors if these state identifiers do not correspond to the same internal index internal indexes are computed per automaton So the user should be aware of this implementation when writing a function based on external identifiers as number of automata in state n0 These functions are e st lt aut name gt gives the current state of automaton lt autname gt lt aut_ name gt is an external identifier and the output of this function is an internal state index Another historical syntax for this function is lt aut_name gt e nb lt sti name gt gives the total number of automata of the SAN in the state lt stt name gt lt stt name gt is an external identifier and P
38. ities These are basically state dependent rates but even if a rate is local for a component or a subset of components of the SAN the functional rate can depend on the entire state of the SAN It is important to notice that this concept is more general than the usual state dependent concept in queueing networks In queueing networks the state dependent service rate is a rate which depends only on the state of the queue itself Chapter 2 SAN Presentation In a SAN a system is described as a collection of interacting subsystems Each subsystem is modeled by a stochastic automaton and the interaction among automata is described by firing rules for the transitions inside each automaton The SAN models can be defined on a continuous time or discrete time scale In this paper attention is focused only on continuous time models and therefore the occurrence of transitions is described as a rate of occurrence The concepts presented in this paper can be generalized to discrete time models since the theoretical basis of such SAN models has already been established Each automaton is composed of states called local states and transitions among them Tran sitions on each automaton are labeled with a list of the events that may trigger them Each event is denoted by its name and its rate only the name is indicated in the graphical representation of the model When the occurrence of the same event can lead to different arrival states
39. lt aut_name gt sum_rw lt aut_name gt lt aut name gt lt stt_name gt gives the sum of the rewards of the automata in the interval lt aut name gt lt aut_ name gt which are in the state lt stt name gt prod_rw lt aut_name gt lt aut_name gt and prod_rw lt aut_ name gt lt aut_name gt lt stt name gt are similar to the preceding functions with a change of operator xternal Format semantic of the Format xample Description Operators at gives the current automaton index at gives the current state index sts std gives the target state index S AN Operators st lt aut_name gt gives the current state of automaton lt aut_name gt st processA lt aut_name gt the same as above another notation processA nb lt stt_name gt gives the total number of automata in the state lt stt_name gt nb lt aut_name gt lt aut_name gt lt stt name gt for the automata in the interval lt aut_name gt lt aut_name gt gives the total nb processA processD util number of automata in the state lt stt_name gt gives the reward associated with the current state of automaton lt aut name gt sum_rw lt aut_name gt lt aut_name gt gives the sum of the rewards of the current states of the automata in the interval sum_rw processA processD lt aut_name gt lt aut_name gt sum_rw lt aut_name gt
40. m docs jit_interface html visited Feb 14th 2003 40
41. m this step we use the compile_dsc module Command compile_dsc options file Typical using example with standard options compile_dsc rs Compilation of a SAN model Internal Descriptor Generation Compile_Network Compile_Function_Table file des rs tft read file dsc rs ftb saved Compile_Descriptor file des rs des read file dsc rs dsc saved Compile_Reacheable_SS file dsc rs rss saved file des rs fct read Compile_Dictionary file dsc rs dct saved file des rs dic read Compile_Integration_Function file des rs res read file dsc rs inf saved Translation performed compilation of a SAN model user time spent 4 0000000000000001e 03 seconds system time spent 0 0000000000000000e 00 seconds real time spent 2 7468191855587065e 01 seconds Thanks for using PEPS The last step in the compiling phase is the model normalization This step normalizes the Sparse Markovian Descriptor files to Continuous Normalized Descriptor Two modules can be used in this step The norm_dsc_ex module uses an extended vector format and norm_dsc_sp module uses a sparse vector format Command norm_dsc_ex file or norm_dsc_sp file Typical using example output message norm_dsc_ex rs Normalization of a SAN Descriptor file dsc rs rss read file dsc rs ftb read file dsc rs dsc read file dsc rs dct
42. nt values input of the model but also functions of the SAN state We can have two kind of functions The first one is called description functions and the second one is SAN functions Description Functions Description functions are used in the model description and they are useful to replicate states transitions and events When PEPS 2007 genere the Markovian Descriptor set of matrices that describe the model it take in to account these functions to build the model PEPS 2007 defines three functions e at returns the current automaton index If automaton is a replicated automaton then this function returns the internal replication index else it returns the general automaton index in the model e sts gives the current state index in the current automaton As well the previous functions this functions returns the internal replication index to a replicated state and the general state index to a non replicated state e std this functions returns the target state in a transition The states indexes returned by this functions follow the previous functions behaviour 19 SAN Functions With the idea that aSAN has a state which evolves with time we use the term current state These functions are used to express SAN behavior such as the rate of this event is 0 if the SAN is in state x and equal to r otherwise or to compute performance index by integration of a function such as the number of automata in s
43. r is needed to compile the PEPS software itself during the installation but also during the execution PEPS 2007 uses the compilation of functional elements just in time This procedure calls the g compiler so make sure this command is reachable from your environment type which g at your prompt to verify it 3 1 1 Getting the source Retrieve from our site the file Peps2007 tgz for full PEPS 2007 package or the compressed file for each individual module Use tar xvzf file e g tar xvzf Peps2007 tgz for full PEPS 2007 package to uncompress this file and to generate the directory Peps2007 and all the hierachy of files 3 1 2 Compiling If you want to compile all PEPS 2007 modules just type make and the binary files of PEPS will be generated You can compile just one individual module In this case type make module_name e g make compile_san or run make into module directory You can change the compiling options for each module into module directory 3 1 3 Binary files In the directory bin in each module directory there is a file with the module name e g compile_san which is the executable To run a Peps module just type the module name If you compiled the full PEPS 2007 package all executable files generated by each module are copied to the directory peps2007 bin The first time that Peps is running in a directory it will initialize all auxiliary subdirectories 3 2 Model Description A model must be described
44. read file cnd rs cnd saved file cnd rs ftb saved file cnd rs rss saved file peps peps2007 bin jit peps_jit C saved Translation performed normalization of a SAN descriptor largest element in reachable states 1 5000000000000000e 01 user time spent 4 0000000000000001e 03 seconds system time spent 4 0000000000000001e 03 seconds real time spent 8 9477301982697099e 01 seconds Thanks for using PEPS 3 4 Solving a model After the compiling phase the model can be solved The solution methods are implemented in two modules and as in the last compiling step solve cnd_er module uses an extended vector format and solve_cnd_sp module uses a sparse vector format If you compile your model using the extended vector we must use the extended vector representation also to solve its Command solve_cnd_ex options file or solve_cnd_sp options file Typical using example output message solve_cnd_ex rs file cnd rs rss read file cnd rs ftb read file peps peps2007 bin jit peps_jit C saved file cnd rs cnd read file dsc rs dct read Solution of the model cnd rs cnd 4 automata 11 16 states Enter vector file name v Iteration 0 largest 1 6363636363636364e 01 0 smallest 5 4545454545454550e 02 3 1944567435636364e 01 0 smallest 2192409302507105e 01 0 smallest 2219021084342858e 01 0 smallest 2221878502659678e 01 0
45. ror test to accumulated individual absolute error rel ind set the error test to maximum individual relative error vec_type Set the initial vector type We have three possibilities eq set the initial vector to equiprobable Default option in read a user vector as initial vector The vector is read from a file ap use an aproximated by the inverse of the diagonal vector 36 meth_type type This option set the Vector Descriptor product method PEPS implement 4 methods A use avoid permutation method B use minimize permutations C use minimize function evaluations M use mixed method Default option precond This option set the diagonal preconditioning as true zin_impl type Set the zin representation format to type This option is implemented only to solve_cnd_sp module and two zin types are proposed full use full implementation including zeros sparse use sparse implementation only non zeros krylov n Set the krylov subspace size to n Default krylov subspace size is 10 This option is not implemented to solve_cnd_sp module 6 2 Harwell Boeing Format HBF This section presents solution methods based in sparse format HBF 6 2 1 HBF This module implements the vector infinitesimal generator multiplication using a sparse matrix representation for the infinitesimal generator solve_hbf Module Implementation Source code path peps2007 src solve solve_hbf Required files hbf Generated files vct Comman
46. s aut C1 stt idle to busy L1 stt busy to idle D1 to busy L2 L3 L4 aut C2 stt idle to busy L2 stt busy to idle D2 to busy L3 L4 aut C3 stt idle to busy L3 stt busy to idle D3 to busy L4 aut C4 stt idle to busy L4 stt busy to idle D4 results full nb busy C empty nb busy 0 use1 st P1 busy average nb busy 28 4 2 3 Example A Mixed Queueing Network The final example is a mixed queueing network Fig in which customers of class 1 arrive to and eventually depart i e open and customers of class 2 circulate forever in the network i e closed This quite complex example is presented to stress the power of description of PEPS 2003 and to provide a really large SAN model Due to its size the equivalent SAN model is not presented as a figure However the construction technique does not differ significantly from the technique employed with the previous models In this model each queue visited by only the first class of customer Queues 2 and 3 is represented by one automaton each A and A respectively Queues visited by two classes of customers are represented by two automata one for each class and the total number of customers in a queue is the sum of customers of both classes represented in each automaton The size of this model depends on the maximum capacity of each queue denoted K for queue i For the second class of customer closed system it is also necessary to defin
47. s B Plateau and W J Stewart The PEPS Software Tool In 4 International Conference on Modeling Techniques and Tools for Computer Performance Evaluation Urbana Illinois USA 2003 Springer Verlag A Benoit B Plateau and W J Stewart Memory efficient Kronecker algorithms with appli cations to the modeling of parallel systems To appear in PMEO PDS 08 2003 G F Ciardo A S Miner A Data Structure for the Efficient Kronecker Solution of GSPNs In Proc 8th International Workshop on Petri Nets and Performance Evaluation 1999 S Donnatelli Superposed Stochastic Automata a Class of Stochastic Petri Nets with Parallel Solution and Distributed State Space Performance Evaluation v 18 pp 21 36 1993 P Fernandes M thodes Num riques pour la Solution de Syst mes Markoviens a Grand Espace d Etats These de doctorat Institut National Polytechnique de Grenoble France 1998 P Fernandes B Plateau and W J Stewart Efficient Descriptor Vector Multiplication in Stochastic Automata Networks Journal of the ACM v 45 n 3 pp 381 414 1998 J Fourneau B Plateau A Methodology for Solving Markov Models of Parallel Systems Jour nal of Parallel and Distributed Computing v 12 pp 370 387 1991 E Gelenbe G Pujolle Introduction to Queueing Networks John Wiley 1997 J Hillston A Compositional Approach for Performance Modeling Ph D Thesis University of Edinburg United Kingdom 1994 J K Muppala G F Ciardo K S Trivedi Stoch
48. tate 0 Before proceeding to these functions let us describe the way names identifiers are handled in PEPS e a reference to an automaton identifier is translated in PEPS into a reference to the automaton internal index This internal index is computed according to the declaration order in the Network block The first automaton of the network has internal index zero the second 1 and so on Replicated automata are internally numbered using the index of the first one as a base and then incrementing it with the replication index For example assume a SAN with automaton test1 replicated in the interval 1 2 automaton test2 without replication and automaton test3 replicated 3 times 0 2 then we have the external identifiers test1 1 test1 2 test2 test3 0 test3 1 and test3 2 The internal indexes are 0 for test1 1 1 for test1 2 2 for test2 3 for test3 0 4 for test3 1 and 5 for test3 2 This internal numbering allows to defined subsets of automata as intervals The interval test1 2 test3 1 is exactly the subset of automata test1 2 test2 test3 0 test3 1 e a reference to a state identifier is also replaced in PEPS with a reference to an automaton index The external identifiers correspond to an internal index computed according to the declaration order and the number of replications For example if the automaton test1 has 3 states named A B and C declared in this order the internal index of A is 0 B is 1 and C
49. te space of the SAN model is denoted by R it is generally smaller than the product state space since synchronizing events and functional rates may prevent some states in S from being reachable The set of automata involved with a local or synchronizing event e is denoted by Oe The event e can occur if and only if all the automata in Oe are in a local state from which a transition labeled by e can be triggered When it occurs all the corresponding transitions are triggered Notice that for a local event e Oe is reduced to the automaton involved in this event and that only one transition is triggered Figure presents an example The first automaton AU has three states 2 y and ZO the second automaton A has two states x and y The events of this model are e c1 e2 and es local events involving only AU with constant rates respectively equal to Ai As and As e e4 a synchronizing event involving AU and A with a constant rate Ay e es a local event involving A with a functional rate f f u if AD is in state 2 f 0 if A is in state yD f m if AD is in state s0 When the SAN is in state 2 yo the event e4 can occur at rate Ay and the resulting state of the SAN can be either y z2 with probability m or x 2 with probability 1 r Figure 2 1 Very Simple SAN model example We see then that a SAN model is described as a set of automata each automaton containing nodes edges and labels
50. three situation are possibles e use a constant to define a static state e use a function to define one variable state where the target state index is defined by the current state index e use a domain to define multiply transitions Inside a group of replicated states the expression of the other states inside the group can be made by positional references to the current the previous or the successor Larger jumps e g of states two ahead 2 can also be defined but any positional reference pointing to a non existing state or to a state outside the replicated group is ignored Format of the to block 17 to lt stt name gt replication_domain f cond lt evt_ name gt replication_domain lt prob gt f cond Events description e f_cond defines a condition to include the transition f_cond is an function identifier previously defined in identifiers block Normally this function value depend of the current automaton and or current and or target state Event Description Finally for each transition defined a set of events local and synchronizing that can triggers the transition can be expressed by their names and optionally the probability of occurrence and firing condition Format of the event block lt evt_name gt replication_domain lt prob gt I f_cond e lt evt_name gt is the event name that trigger a transition The event name must
51. vector Source code path peps2007 src solve solve_cnd_sp Required files cnd ftb rss inf dct Generated files vct tim Command solve_cnd_sp options file These modules have almost the same options and we will explaine only one time The options that can be used for just one module will be mentioned Options sol_meth method This option set solution method that will be used to solve the model Four methods are proposed power use the power method Power method is the default option gmres use the gmres method This method is not implemented to solve_cnd_sp module arnoldi use the arnoldi method This method is not implemented to solve_cnd_sp module unifor use the uniformization method int_func Set the function integration to true This option will integrate the result functions iter n Set the maximum number of iteration to n n default value is 1000 min_err err Set the tolerance accepted to err err default value is 1 0e 10 iter type type This option set the stop iteration criterion Three type are proposed fix set stop criterion to fixed iteration number stb set stop criterion to stability test cnv set stop criterion to convergence test The convergence test is the default option err type This option set the error test Three type are proposed abs_ind set the error test to maximum of individual absolute errors The maximum of individual absolute errors is the default option abs_acc set the er
Download Pdf Manuals
Related Search