Home

Layered Queueing Network Solver and Simulator User Manual

1. Figure 1 5 Slices The slice time is shown using the label By default the demand of a slice is assumed to be exponentially distributed but a variance may be specified through the coefficient of variation squared cv o 5 parameter for the entry or activity The method used to solve the model depends on the solver being used Analytic Solver All servers with cv Z 1 use the HVFCFS MVA approximation from 131 Simulator The simulator uses the following distributions for generating random variates for slice times provided that the task is not a bursty reference task cv 0 deterministic 0 lt cy lt 1 gamma cv 1 exponential cv gt 1 bizarro If the task is a bursty reference task then the simulator generates random variates for slice times according to the Pareto distribution The scale m gt 0 and shape k gt 0 parameters for the distribution are derived from the service time s and coefficient of variation squared cv parameters for the corresponding activity or phase 1 k 1 1 CV k 1 k On off behaviour can simulated by using two or more phases at the client where on phase corresponds to the on period and makes requests to other servers while the other phase corresponds to the off period Im 8 1 1 6 Precedence Precedence is used to connect activities within a task to from an activity graph Referring to Figure 1 2
2. ordered 0 2 0 7 0 unordered 0 2 i i 0 7 fan in fan out entr i iviti result task distribution service task activities Figure 3 4 TaskType 3 2 5 FanInType and FanOutType 3 2 6 EntryType Elements of type Entry Type shown in Figure are used to define the entries of tasks Entries can be specified one of three ways based on the attribute type of an ent ry element namely 27 Default See TL Seld priority integer optional The priority used by the processor for scheduling queue length integer optional Maximum queue size for open class requests replication integer optional set CSCS schedul enumeration optional FCFS The scheduling of requests at the task The allowed scheduling types are ref fcfs hol pri inf burst and poll and semaphore See sctivity graph emmeration reqired vesorno think time float optional 0 Reference tasks only Customer think time initially integer optional multiplicity Semaphore tasks only Set the initial number of semaphore tokens to zero By default the number of tokens is set to the multiplicity of the task Table 3 7 Attributes for elements of type Task Type source meger required Ge SS value integer required Gee Table 3 8 Attributes for elements of type FanInType dest integer requi
3. drop prob_activity to_entry float_phase_list A 2 8 Join Delays join join_t_tbl join_a_tbl J ne join t tbl M end_list task name join a tbl end_list join entry 15 from activity to_activity real real 1 join_entry 2 9 Service Time service X ne 116 endist service_t_tbl taskname service e tbl end_list service_a_tbl opt _ 101 service_entry 89 service_entry entry name float_phase_list service a tbl service activity o list F a a 3 service_activity float_phase_list 97 A 2 10 Service Time Variance variance VAR ne variance_tthl end list variance t_tbl taskname variance e tbl end_list variance_a_tbl ps variance_e_tbl variance_entry variance entry entry name float_phase_list variance a tbl gt variance_activity 8 list variance_activity float_phase_list A 2 11 Probability Service Time Exceeded variance VAR ne variance t tbl M endist A 2 12 Service Time Distribution distribution D entryname statistics hist bin o end_list D statistics hist bin 9 end_list statistics phase mean std
4. Figure 2 4 Service Time Components for Join 2 9 Service Times The service time is the total time a phase or activity uses processing a request The time consists of four components shown in Figure 2 4 1 Queueing for the processor shown as items 1 4 6 and 8 in Figure 2 5 b 2 Service at the processor items 2 5 and 9 3 Queueing for serving tasks item 6 and 4 Phase one service time at serving tasks items 3 and 7 Queuing at processors and tasks and can occur because of contention from other tasks items 1 6 and 8 or from second phases from previous requests For example entry SE3 is queued at the processor because the processor is servicing the second phase of entry SCE3 Using the results shown in Figure 2 1 the service time for entry SE3 21 7 is the sum of 16 td service time components J idl service time 1 receive 4 8 ready phase 1 _ i 2 blocked 3 7 sen send A L I 1 l receive V SE3 idle ready reply phase 1 phase 2 SCE3 l L I L I l l receive reply idle ready phase 1 phase 2 eae CE1 SE3 SCE3 1 Other Idle 1 1 1 1 1 1 BookstoreProc Figure 2 5 Service Time Components for Entry SCE3 the processor wait 0 767 it s own service time 6 x 1079 the queuei
5. Introductionito LOX 45 zu Pe Sav ye oe bbe ew 309 34 SUS dei 39 4 11 InputFile 39 412 _ Writing LOX o s s as saccis Soe GOR aD Ww weed Ww 41 4 1 3 Program Input Output and External 44 4 1 4 Actual Example of an LOX 1 47 4 2 APIDocumentation s s eR RR RR RR 48 421 Bultan Class Array o oU Ox woher W 4 om R Be p Q N Bex Boves 48 48 qu 50 Us Bw nd aiid OR PP Gees EPI eio 50 Sind eee ee eee Pe HOw Oke Bae ee ees 50 ee eee ee 50 TP 50 TTE 51 51 cT 51 52 43 9 Intervals a poc ben Mee ewes ed dee S 52 53 S I Lexical Conventions p s a e py x CO Vd Aw oy a we SS p s S p YQ 53 White SpaGel o S aa Bede eae 53 5 4 bd os 65 E REPE v PS 55 5 1 3 z 2 z os S w dor e ede S E D aede ose Ae S a 55 e Pcr 55 vcr 55 Leek S 55 5 rr 55 Soh en Gos Joh SEAR s s ps ae oe OR ee n 56 e
6. Semaphore initially empty task t has ne entries entry identifier open class queue length task priority optional Group for scheduling Source task Destination task fan in to this task fan out from this task total number of entries maximum number of phases histmax hist bins hist type Signal Semaphore Wait Semaphore a entry_id arrival rate A entry_id activity id from entry to entry p_forward H entry_id phase M entry_id max service time M endist P entry_id V entry id Z entry_id think M end list c entry_id coeff of variation M end_list f entry_id ph type flag V end_list p entry_id entry_priority s entry id service time T y from_entry to_entry rendezvous M end list z from entry to entry send no reply M endist open arrival rate to entry squared service time coefficient of variation Source of a message Number of bins in histogram Median service time Median service time bin type Median service time probability of forwarding phase of entry stochastic phase deterministic phase nb of calls per arrival mean number of RNVs ph send no reply real variable mean nb of non blck sends ph service time real variable mean phase service t
7. 8 1 Fatal Error Messages Internal error Something bad happened e No more memory A request for memory failed e Model has activity entry task processor This should not happen e Activity stack for identifier is full The stack size limit for task identifier has been exceeded e Message pool is empty Sending from identifier to identifier Message buffers are used when sending asynchronous send no reply messages the buffers have been used 8 2 Error Messages e task processor identifier Replication not supported The simulator does not support replication The model can be flattened using rep2flat 1 e nnReplies generated by Entry identifier This error occurs when an entry is supposed to generate a reply because it accepts rendezvous requests but the activity graph does not generate exactly one reply Common causes of this error are replies being generated by two or more branches of an AND fork or replies being generated as part of a 1 Replies cannot be generated by branches of loops because the number of iterations of the loop is random not deterministic 79 Activity identifier is a start activity The activity named identifier is the first activity in an activity graph It cannot be used in a post precedence fork list Activity identifier previously used in a fork The activity identifier has already been used as part of a fork expression For
8. Finally the simulator lists the name of the machine that it was run on the time spent executing the simulator code the time spent by the system on behalf of Iqsim and the total elapsed time 2 20 1 Throughput Bounds The Type 1 Throughput Bounds are the guaranteed not to exceed throughputs for the entries listed The value is calculated assuming that there is no contention delay to underlying servers 13 Iqns VI Generated lqns version 3 9 Darwin 6 8 Darwin Kernel Version 6 8 Copyright the Real Time and Distributed Systems Group Department of Systems and Computer Engineering Carleton University Ottawa Ontario Canada K1S 5B6 Input bookstore lqn Output bookstore out Command line lqns p Tue Nov 1 21 37 54 2005 Comment lqn2fig Lg bookstore lgn pragma multiserver conway Convergence test value 7 51226e 07 Number of iterations 5 MVA solver information Submdl n k srv step mean stddev wait EM 5 2 4 44 8 8 1 4697 4776 2 9 1 1 51 5 6667 0 94281 594 3 9 8 3 240 26 667 9 4751 4 0365e 05 4 9 10 3 271 30111 7 0623 7 7481 05 5 9 2 1 70 T TELS 1 6178 3408 6 5 0 0 0 0 0 0 Total 46 0 0 676 14 696 12 464 1 1872e 06 greg frankss Computer local Darwin 6 8 User 0 00 01 35 System 0 00 00 00 Elapsed 0 00 01 40 mean 955 2 66 44850 86090 378 67 25809 Wed Sep 10 15 20 55 PDT 2003 stddev 299 82 22 627 32163 40554 181 73 0 41253 Figure 2 2 Analytic
9. entry id real 1 opt obs 1 Activity definitions task id S activity id real opt obs y lt activity id gt lt entry id gt real opt obs activity list gt activity list 1 f Result defintions SPEX R 0 Svar expression 1 Convergence defintions SPEX Svar lt expression gt 1 54 5 1 2 Comments Any characters following hash mark through to the end of the line are considered to be comment and generally ignored However should a line begin with optional whitespace followed by pragma then the remainder of the line will be treated by the solver as a pragma more on pragmas below 5 1 3 Identifiers Identifiers are used to name the objects in the model They consist of zero or more leading underscores _ followed by a character followed by any number of characters numbers or underscores Punctuation characters and other special characters such as the dollar sign 5 are not permitted Non numeric identifiers must be a minimum of two characters in lengtil The following 1 p1 p_1 and P 21 proc are valid identifiers while proc and 1 are not 5 1 4 Variables Variables are used to set values of various objects such as the multiplicity of tasks and the service times of the phases of entries Variables are modifed by SPEX see to run multiple experiments Variables start with a dollar sign 557 followed by any nu
10. ActivityOrType ActivityPhasesType ActivityType ActivtyDefType ActivtyEntryDefType ActivtyPhasesType AndJoinListType EntryActivityDefType Entry ActivityGraph 30 EntryMakingCallType EntryType FanInType FanOutType GroupType 26 HistogramBinType LqnModelType MakingCallType OrListType OutputDistributionType 32 OutputResultForwarding ANDJoinDelay 32 OutputResultJoinDelayType OutputResultType PrecedenceType 30 ProcessorType ResultContentType SingleActivityListType TaskActivityGraph 30 TaskType type under relaxation under relaxation coefficient 91 error 86 underflow bin B5 underrelax_coeff underrelaxation 68 user cpu time utilization entry 36 high 85 error 86 processor 11 semaphore 18 task utilization 36 valid value Variables SPEX variables parameters report indication spex variance initialize only Method of Layers service time variance version 114 wait 5 82 83 error wait 67 wait waiting processor 77 waiting waiting time 18 75 open arrival 18 36 98 waiting variance warning ignore 67 76 warning white space x samples Xerces error error messages validation XML debug 68 input validation xml XML Grammar XML Grammar 38 xml debug XMLSpy XSDvalid xsi noNamespaceSchemaLocation 88 115
11. iteration reply duplicate invalid reply activity response time scheduling 86 completely fair schema semaphore task send no reply 79 server task service time stack size standard deviation false 9 error 82 fan out 9 error 82 FanInType FanOutType fast Jcfs file debug 75 monitor 74 tracing 75 first activity floating point exception 66 74 infinity 66 fork I error precedence 8 fork list 8 80 forks forward 84 forwarding 15109 probability error forwarding forwarding probability full reinitialize start activity 80 synchronization generate tag global delay 76 end 82 Gnuplot 62 task creation 80 Grammar think time XML throughput XML B8 infinite grammar under relaxation coefficient original 87 utilization group 4 high 561 textb 4 wait error Xerces events share exact 70 error Excel 62 tasks exit error success group share exponential GroupType ore vo El hardware software layers histogram 35 107 no phase overflow 18 statistics underflow 18 histogram bin B5 HistogramBinType 35 hol holding time host demand cvsq host demand me an 32 hwsw hyper icon stacked identifier duplicate LQN identifiers idle_time ignore overhanging threads infinite loop call graph 80 infinite server 78 error infinity
12. maxium forwarding 72 infinite server 72 interprocessor delay multi server 72 open arrival 72 phase maximum type processor maximum 72 scheduling task maximum 72 think time active server 3 activities 165 activity 1 3 4 5 5 30 connection see precedence defined demand 30 error LQN not reachable error 85 reply 1 error reschedule results service time start activity activity graph connection 32 error semantics start task activity list LQN 60 Activity CallGroup activity graph ActivityDefBase ActivityDefType ActivityEntryDefType ActivityGraphBase ActivityListType ActivityLoopListType ActivityLoopType ActivityMakingCallType ActivityOrType ActivityPhasesType Activity Type ActivtyDefType ActivtyEntryDefType ActivtyPhasesType advisory ignore advisory all allow AND fork reply error and fork 94 AND join AndJoinListType and fork and join arcs arrival loss probabilities 15 arrival rate async call asynchronous connections attribute activity graph attribute begin bin bin size bound to entry 30 call order calls mean cap conf 95 37 conf 99 37 conv val 25 conv val count description dest elapsed time end first activity host demand cvsq 32 host demand mean 32 initially it limit iterations 103 join variance join waiting loss pro
13. speed factor SPEX AGR arrays convergence 53 grammar convergence expressions paramters report 94 if then else LQX parameter control 55 parameters Perl report 62 results ternary expressions 60 Variables variables 95 array control 60 Observation scalar versions spex variables 60 squared coeff variation squashed 69 squashed layers 69 srvn srvn layers 69 srvndiff 75 stack size error standard deviation error standard input start activity error 80 statistical counters 75 statistics blocked 25 simulation step stochastic stochastic stop on message loss 71 stopping criteria submodel population Suri sync call 32 synchronization error synchronization server synchronization task system cpu time tag end error task LON maximum 78 queue reference 113 bursty semaphore server synchronization trace task task creation error task activities TaskActivityGraph TaskType tau tex think time entry error think time 28 B2 thread threads three point approximation throughput bounds infinite error interlock zero throughput 67 throughput throughput bound time timeline trace processor task tracing true type ActivityDefBase ActivityDefType ActivityEntryDefType ActivityGraphBase ActivityListType ActivityLoopListType ActivityLoopType ActivityMakingCallType
14. teration limi 168 method of lay rs 68 n n n 0 p E UE o execute 66 75 o variance 68 o warnings l 671 76 utput 66 75 arseable 66l 75 ragma 661 75 rint interval 6 rocessor sharing 68 aw statistics 75 eload 1qx 68 estart t 66 un time 76 S 5 5 5 5 chweitzer amva 68 eed 75 pecial 67 quashed layering 68 rvn layering 68 top on messag 1055 68 5 t t mM M ee race 66 75 race mva 68 nderrelaxation 68 erbose 67 76 67176 n1 67 76 80 see precedence A 25 74176 B 25 74176 c 2574 75 H 66 P 66 69 70 75 7 74 5 s F5 76 v 6176 65 b 65 4 65 671174 e 66 74 66 h 75 m 74 75 n 66 75 o L1 I65 66 741 75 p 65 66 74 75 r 66 t 25 66 72 73 75 85 _v 67 76 w 6776 x 65 67 76 2 67 76 6 62 1 62 4551631 pragma 55 0 62 block_t ime 60 coefficient of variation 60 comment 60 convergence limit 60 Siteration_limi t 60 model comment 60 number of blocks 60 print interval 60 result 60 seed value 60 Swarm up loops 60 V 63 102 gt 80 asynchronous connections 72 coefficient of variation 72 entry
15. 66 init only initial loops 74 82 initially input invalid 69 multiple XML interlock 69 interlock interlocking 69 interprocessor delay it limit 25 iteration limit error iteration limit iterations join 1 and 33 delay 11 16 32 Be 71 97 error precedence quorum 8 variance 16 join list error join variance 36 join waiting 36 joins 65 67 lambda layer spanning 1 Layered Queueing Network 1 layering batched 69 loose method of Method of Layers 69 squashed 69 srvn 69 strategy 69 layering 62 layers hardware software 69 layers length simulation 77 limits Iqns 72 Iqsim line continuation Linearizer linearizer livelock 80 LOOP reply error loop loop count 8 loss probability loss probability Igiolib 58 LQN activity 58 59 activity list 60 comment 55 entry 57 group 56 identifier 55 multiplicity parameter 55 pragma d processor task 57 white space Iqn core xsd 21 Iqn model 24 108 lgqn schema version Iqn sub xsd 21 Iqn xsd 21 Iqn2ps lqncore schema version 24 LqnModelType LONS 65 parameters Iqns 11 2 1 convergence value LONS PRAGMAS 69 lqsim scheduling 4 LOSIM PRAGMAS 77 debug 68 error execution error intrinsic types 391 40 Operators 40 Iqx mak Mak Lundstrom 71 MakingC
16. For any key location combination that takes a phase argument if none is supplied then the sum of the values for all phases is reported This also happens if a phase of zero is given 61 Listing 5 8 Report Information R lt int gt Svar Svar lt expression gt 1 5 3 2 Report Information The purpose of the report information section of the input file is to specify which variable values including result indications are to be printed in the spex result file The format of this section is shown in Listing 5 8 There may be any number of report declarations however the integer parameter to R must either be the number of report declarations present or The lt expression gt be any valid LQX expression as discussed above Note that in this section the report indication variables and the parameter variables may both be used together The values of the variables listed in this section are printed from left to right in the order that they appear in the input file separated by commas This output can then be used as input to Gnuplot or a spreadsheet such as Excel There is a special variable called 0 which represents the independent variable in the results tables the x axis in plots The variable 0 may be set to any expression allowing for flexibility in producing result tables This variable cannot be used as a parameter in the model 5 3 3 Convergence Information Spex allows a parameter value to be modified at the
17. The processor rate parameter is used to scale the speed of the processor A value greater than zero must be used e Processor identifier using CFS scheduling has no group If the completely fair share scheduler is being used there must be at least one group defined for the processor e Reference task identifier cannot forward requests Reference tasks cannot accept messages so they cannot forward e Reference task task identifier entry entry identifier cannot have open arrival stream Reference tasks cannot accept messages e Reference task task identifier entry entry identifier receives requests Reference tasks cannot accept messages e Reference task task identifier replies to entry entry identifier from activity activity identifier Reference tasks cannot accept messages so they cannot generate replies The activity activity identifier replies to entry entry identifier e Required attribute attribute was not provided The attribute named attribute is missing for the element e Semaphore wait entry entry identifier cannot accept send no reply requests An entry designated as the semaphore wait can only accept rendezvous type messages because send no reply messages and open arrivals cannot block the caller if the semaphore is busy e Start activity for entry entry identifier is already defined Activity activity identifier is a duplicate A start activity has alr
18. join to finish If this attribute is not specified then all of the branches must finish which makes this object an AND Join Table 3 15 Attributes for elements of type AndJoinListType 33 PrecedenceType precedence ordered AndJoin 1 0 4 ActivityLoop SingleActivity ListType p de uH E dur 1 Activity Or ListType ListType quorum unsigned 0 P gt _ListType ListType pre pre AND pre OR post post AND post OR post LOOP ordered ActivityType TT name string ActivityOr ActivityLoop Type Type prob float count float 52 result join service time activit delay distribution activity activity Figure 3 8 Schema diagram for the type PrecedenceType name swing prob float optional 1 0 The probability that the branch is taken on average c f Table 3 16 Attributes for elements of type ActivityOrType Name Use Default Comments end string required Table 3 17 Attributes for elements of type Activity LoopList Type Use count float optional 1 0 The number of times the loop is executed on average c f 81 1 6 Table 3 18 Attributes
19. mean delay for joins entry service times and variances distributions for the service time task throughputs and utilizations e processor utilizations and queueing delays Figure shows some of these results for the model shown in Figure after solving the model analytically using Iqns 1 The interpretation of these results are describe below in Section 2 1 2 Results can be saved in three different formats 1 in a human readable form 2 in a parseable form suitable for processing by other programs The grammar for the parseable output is described in Section A on page 3 in XML again suitable for by processing by other programs The schema for the XML output is shown in Section 3 on page If input to the solveris in XML then output will be in XML Human readable output will be produced by default except if output is redirected using the ooutput flag and either XML or parseable output is being generated Conversion from parseable output to XML and from either parseable or XML output to the human readable form can be accomplished using qn2ps 1 2 1 Header The human readable output from the the analytic solver and simulator consists of three parts Part 1 of the output consists of solution statistics and other header information and is described in detail in Sections 2 1 I and 1 2 below Part 2 of the output lists the input and is not described further Part 3 contains the actual results These results are described in Sect
20. n First come first served Polled service at entries Head of line priority First come first served Infinite delay server Read Write lock taskT Semaphore task Semaphore task Table 5 3 Task Scheduling Disciplines see 41 1 3 5 2 6 Entry Information Entries are specified in the entry information section starting from lt int gt and ending with 1 The int parameter is either the number of entry definitions in this section or zero Each record in the entry section defines a single parameter for an entry such as its priority or a single parameter for the phases of the entry such as service time Listing 5 6 shows the syntax for the most commonly used parameters entry records start with a key letter followed by an lt entry id gt followed by from one to up to five arguments Table lists all the possible entry specifiers The table is split into six classes based on the arguments to the Line 3 is a continuation of line 2 27 Option Parameter lt integer gt Task priority for tasks running on processors supporting priorities z lt real gt Think Time for reference tasks q lt real gt Maximum queue length for asynchronous requests m lt integer gt Task multiplicity r integer Task replication g lt identifier gt Group identifier for tasks running of processors with fair share scheduling Table 5 4 Optional parameters for tasks see 41 1 3 Listing 5
21. precedence is subclassed into Pre or join and Post or fork To connect one activity to another the source activity connects to a pre precedence or a join list The pre precedence then connects to a post precedence or a fork list which in turn connects to the destination activity Table summarizes the precedence types Nm Nm Icn Icon BDesripionn ees eme Transfer of control from an activity to a join list menm fg A Synchronization point for concurrent activities bod A Synchronization point for concurrent activities where only n branches must finish Ljb Transfer of control from fork list to activity And Fork Start of concurrent execution There can be any number of forked paths Or Fork ys A branching point where one of the paths is selected with prob P ability p There can be any number of branches Repeat the activity an average of n times n2 Table 1 1 Activity graph notation The semantics of an activity graph are as follows For AND forks AND joins and QUORUM joins each branch of a join must originate from a common fork and each branch of the join must have a matching branch from the fork Branches from AND forks need not necessarily join either explictily by a dangling thread not participating in a join or implicitly through a quorum join where only a subset of the branches must join while ignoring the rest However all threads
22. stop on message loss arg This pragma is used to control the operation of the solver when the arrival rate exceeds the service rate of a server Arg must be one of false Ignore queue overflows for open arrivals and send no reply requests If a queue overflows its waiting times is reported as infinite true Stop if messages are lost The default is false tau arg Set the tau adjustment factor to arg Arg must be an integer between 0 and 25 A value of zero disables the adjustment threads arg This pragma is used to change the behaviour of the solver when solving models with fork join interactions exponential Use exponetial values instead of three point approximations in all approximations 8 hyper Inflate overlap probabilities based on arrival instant estimates mak Use Mak Lundstrom approximations for join delays none Do not perform overlap calculation for forks The default is hyper variance arg This pragma is used to choose the variance calculation used by the solver init only Initialize the variances but don t recompute as the model is solved mol Use the MOL variance calculation no entry By default any task with more than one entry will use the variance calculation This pragma will switch off the variance calculation for tasks with only one entry none Disable variance adjustment All stations in the MVA submodels are either delay or FIFO servers stochastic 71 6 3 Stopping Criteria Lqns computes the mod
23. trace utilization waiting processor processor sharing Processor Type program limit error ps quantum quantum queue queue length 92 error queue length queueing delay processor task queueing model closed customers 5 queueing network extended 1 layered time 36 queueing time processor 18 variance quorum 94 quorum 33 quorum quorum join 8 QUORUM join 8 quorum join 8 random number generation 75 reference task reference task bursty error reiser reiser ps remote procedure call 3 rendezvous 1 9 cycle delay error 87 reference task variance rep2flat replication 9 convergence error 79 flatten iteration error processor ratio simulator task replication 26 28 reply activity duplicate error error explicitly implicit invalid error phase reply activity error reply activity reply element 111 reply entry 30 request 1B 9 asynchronous 1 blocked forward reply synchronous types 9 reschedule activity phase reschedule on async send 77 resource passive possession simultaneous I software response time error result activity result entry result forwarding result general 24 result join delay result processor result task 27 ResultContentType 35 results activity intermediate 66 phase valid rolia rolia ps root mean
24. 3 Pragmas Pragmas used to alter the behaviour of the simulator in a variety of ways They be specified in the input file with pragma on the command line with the P option or through the environment variable LOS IM_PRAGMAS Command line specification of pragmas overrides those defined in the environment variable which in turn override those defined in the input file The following pragmas are supported An invalid pragma specification at the command line will stop the solver Invalid pragmas defined in the environment variable or in the input file are ignored as they might be used by other solvers scheduling enum This pragma is used to select the scheduler used for processors Enum is any one of the following default Use the scheduler built into parasol for processor scheduling faster custom Use the custom scheduler for scheduling which permits more statistics to be gathered about processor utilization and waiting times However this option invokes more internal tasks so simulations are slower than when using the default scheduler default natural Use the parasol scheduler but don t reschedule after the end of each phase or activity This action more closely resembles the scheduling of real applications custom natural Use the custom scheduler don t reschedule after the end of each phase or activity messages n Set the number of message buffers to n The default is 1000 stop on message loss bool This p
25. 4 1 10 1109 71 80155 11 Martin Mroz and Greg Franks A performance experiment system supporting fast mapping of system issues In Fourth International Conference on Performance Evaluation Methodologies and Tools Pisa Italy October 20 22 2009 doi 10 4108 ICST VALUETOOLS2009 7807 12 John Neilson PARASOL A simulator for distributed and or parallel systems Technical Report SCS TR 192 School of Computer Science Carleton University Ottawa Ontario Canada May 1991 10 13 Martin Reiser A queueing network analysis of computer communication networks with win dow flow control IEEE Transactions on Communications 27 8 1199 1209 August 1979 doi 10 1109 TCOM 1979 1094531 100 14 J A Rolia and A Sevcik The method of layers IEEE Transactions on Software Engineering 21 8 689 700 August 1995 4 1 10 1109 32 403785 15 Jerome Alexander Rolia Predicting the Performance of Software Systems PhD thesis Univerisity of Toronto Toronto Ontario Canada January 1992 16 Rainer Schmidt An approximate MVA algorithm for exponential class dependent multiple servers Performance Evaluation 29 4 245 254 1997 4 1 10 1016 50166 5316 96 00048 X 17 C U Smith and L Williams performance model interchange format Journal of Systems and Software 49 1 63 80 1999 doi 10 1016 S50164 1212 99 00067 9 18 C U Smith and L G Williams Performance Solutions A Practical Guide to Cr
26. 4 Warning 9 11 MOL Multiserver Approximation Failure A l InputFile A 1 6 Entry Information 1 7 Activity Information A 1 8 SPEX Report Information A TL ET Identiierg zuo es aie aioe s aa 0 UQ 1 12 Varabled A 2 Output File A 2 3 Waiting A 2 4 Waiting Time A 2 7 ArrivalLossProbabilites 65 65 69 72 72 72 74 74 76 77 77 78 79 79 79 85 86 88 89 90 90 90 90 90 90 A 2 10 Service Time Variance A 2 11 Probability Service Time Exceeded A 2 12 Service Time Distribution A 2 13 Throughputs and Utilizations A 2 14 Arrival Rates and Waiting Times A 2 15 Utilization and Waiting per Phase for Processo Abstract The Layered Queuing Network LQN model is a canonical form for extended queueing networks with a lay ered structure The layered structure arises from servers at one level making requests to servers at lower levels as a consequence of a request from a higher level LQN was developed for modeling software systems but it applies to any extended queueing network with multiple resource possession in which multiple resources are held in a nested fashion
27. Default Value convergence limit real 0 00001 iteration limit int 100 Sprint_interval lt int gt Scoefficient_of_variation lt real gt model comment lt string gt Snumber_of_blocks lt int gt Sblock_time lt int gt Sseed_value lt int gt result precision lt real gt Swarm_up_loops lt int gt Table 5 8 Spex Control Variables SPEX augments the input file described in 45 adding variables for setting input values a Report Information 5 3 7 used to format output and an optional Convergence Information for feeding result values back into input variables Listing 5 1 shows these sections starting with comments red The syntax of these sections are described next in the order in which they appear in the input model 5 3 1 Variables SPEX variables are used to set and possibly vary various input values to the model and to record results from the solution of the model There are four types of variables control scalar array and observation Control variables are used to define parameters that control the execution of the solver Scalar and array variables are used to set input parameters to the model Finally observation variables are used to record results such as throughputs and utilizations Control Variables Control variables are used to set parameters that are used to control either the analytic solver gns or the simula tor Igsim With the exception of comment all of these variables can b
28. If the x samples is not set this behaviour is the default log The logarithm of the range specified is divided by number bins This has the effect of making the width of the bins small near min and large near max A minimum value of zero is not allowed sqrt The square root of the range specified is divided by number bins Bins are smallest near bin are smaller than those near max The results of the histogram collection shown in Figure consist of the mean standard deviation skew and kurtosis of the sampled range followed by the histogram itself Each entry of the histogram contains the probability of the sample falling within the bucket and if available the confidence intervals of the sample The statistics for the histogram are found by multiplying the mid point of the range defined by begin and end not counting either the overflow or underflow bins If the mean value reported by the histogram is substantially different than the actual service time of the phase or activity then the range of the histogram is not sufficiently large 2 13 Semaphore Holding Times The Semaphore Holding Times section lists the average time a semaphore token is held it s service time the variance of the holding time and the utilization of semaphore FigureD 7 shows how these values are found 2 14 Throughputs and Utilizations per Phase The Throughputs and Utilizations per Phase section lists the throughput by entry and activity and the utilization
29. Solver Status Output 00 00 00 00 00 200 00 User 00 00 00 01 00 00 01 01 00 19 15 00 00 35 00 00 00 00 00 00 00 System 00 00 00 00 00 00 00 00 00 00 00 00 00 00 Power Macintosh So oo o 6 00 00 00 00 00 00 200 Elapsed 00 00 00 01 00 00 01 00 00 21 19 00 00 40 Generated by lqsim version 3 9 Linux 2 4 20 31 9 1686 Copyright the Real Time and Distributed Systems Group Department of Systems and Computer Engineering Carleton University Ottawa Ontario Canada 15 5B6 Wed Nov 2 11 42 25 2005 Input bookstore lgn Output bookstore out Comment lqn2fig Lg bookstore lqn Run time 4 34765E 09 Number of Statistical Blocks 15 Run time per block 2 89651E 08 Max confidence interval 7 32 Seed Value 1130948006 epsilon 13 sce carleton ca Linux 2 4 20 31 9 User 0 04 47 78 System 0 200 200 07 Elapsed 0 14 27 66 Figure 2 3 Simulator Status Output 2 3 Mean Delay for a Rendezvous The Mean Delay for a Rendezvous is the queueing time for a request from a client to a server It does not include the time the customer spends at the server see Figure 2 4 To find the residence timeresidence time add the queueing time to the phase one service time of the request s server 2 4 Variance of Delay for a Rendezvous The Vari
30. arg Set the underrelaxation to arg Arg must be a number between 0 0 and 1 0 The default value is 0 9 If any one of convergence iteration limit orprint interval are used as arguments the corresponding value spec ified in the input file for general information is ignored convergence arg Set the convergence value to arg Arg must be a number between 0 0 and 1 0 exact mva Use Exact MVA to solve all submodels hwsw layering iteration limit arg Set the maximum number of iterations to arg Arg must be an integer greater than 0 The default value is 50 srvn layering Solve the model using submodels containing exactly one server squashed layering Use only one submodel to solve the model method of layers This option is to use the Method Of Layers solution approach to solving the layer submodels processor sharing Use Processor Sharing scheduling at all fixed rate processors schweitzer amva Use Bard Schweitzer approximate MVA to solve all submodels stop on message loss Do not stop the solver on overflow infinities of open arrivals or send no reply messages trace mva underrelaxation arg Set the underrelaxation to arg Arg must be a number between 0 0 and 1 0 The default value is 0 9 Do not use variances the waiting time calculations 1 1 program without re solving the models Results must exi
31. end println output filel Model run 4d i tl throughput tl throughput print output filel Model run 4 i tl throughput tl throughput endl It should be noted that with the extra endl parameter both of these calls will produce the same output The acceptable inputs to all print functions are valid file handles quoted strings LQX variables that evaluate to numerical or boolean values or expressions that evaluate to numerical boolean values as well as the newline specifier endl Parameters should be separated by commas To print to standard output no file handle is specified as follows printin subprocess lqns run 4d i tl throughput tl throughput To specify the content between columns the print functions print spaced andprintln spaced are used The first parameter after the file handle the second parameter when a file handle is specified is used to specify either column widths or a text string to be placed between columns If no file handle is specified as when printing to standard output then the first parameter is expected to be the spacing specifier The specifier must be either an integer Or a string N S The following println spaced command specifies the string to be placed between columns It could be used to create comma separated value csv files println spaced output file2 Spl 5 2 Syl 5 2 tl throughput Example output 0 2 0 1 0 05 0 0907554 The f
32. execution after the send takes place A forwarded request results when the reply to a client is redirected to a subsequent server which may forward the request itself or may reply to the originating client CBE SCE1 BME2 IME8 CAMES 131 2 1 I Send Send 1 Send Forward Reply a Rendezvous b Forwarding c Send no reply Figure 1 6 Request Types 1 2 Multiplicity and Replication One common technique to improve the performance of a system is to add copies of servers The performance model supports two techniques multiplicity and replication Multiplicity is the simpler technique of the two as a single queue is served by multiple servers Replication requires a more elaborate specification because the queues of the servers are also copied so requests must be routed to the various queues Multi servers can be replicated Figure shows the underlying queueing models for each technique a Multi server b Replicated Figure 1 7 Multiple copies of servers Replication reduces the number of nodes in the layered queueing model by combining tasks and processors with identical behaviour into a single object shown in Figure The left figure shows three identical clients making requests to two identical servers The right figure is the same model but specified using replication Labe
33. formal description of Layered Queueing Network input file and parseable output file grammars in extended BNF form For the nonterminals the notation nonterminal_id is used while the terminals are written without brackets as they appear in the input text The notation where n lt m means that the part inside the curly brackets is repeated at least n times and at most m times If n 0 then the part may be missing in the input text The notation dont means that the non terminal is optional A 1 Input File Grammar LQN input file general info processor info group info p task info entry info activity info Yo parameter_list processor info group info task_info entry info activity info o report info p convergence info A 1 1 SPEX Parameters parameter list variable_def variable def 1 variable ternary_expr Cexpression list real real real 1 A 1 2 General Information general info comment conv val itJimit print int underrelax coeff end list comment string comment on the model conv val real convergence value it_limit integer max nb of iterations print int integer intermed res print interval underrelax_coeff real under relaxation coefficient end_list 1 list mark string text A 1
34. instead Messages dropped at task identifier for open class queues Asynchronous send no reply messages were lost at the task task This message will occur when the stop on message loss pragma c f is set to ignore open class overflows Note that if a task accepts both open and closed classes an overflow in the open class will result in zero throughput for the closed classes Model failed to converge after n iterations convergence test is limit is n n 1408 Sometimes the model fails to converge particularly if there several heavily utilized servers a submodel Sometimes this problem can be solved by reducing the value of the under relaxation coefficient It may also be necessary to increase the iteration limit particularly if there are many submodels With replicated models it may be necessary to use loose layering to get the model to converge Convergence can be tracked using tconvergence 85 8 4 No solve call found in the lqx program in file filename solve was invoked implicitly An LQX program was found in file filename However the function solve was not invoked explictity The program was executed to completion after which solve was called using the final value of all the variables found in the program Replicated Submodel n failed to converge after n iterations convergence test is n n limit is m m Iqns The inner replication iteration failed to converge Service tim
35. list loop activity loop activity o end_activity p prob activity real activity id loop activity real activity_id end_activity activity id reply_activity 4 reply list reply_list entry id entry id o 1 quorum count integer Quorum A 1 8 SPEX Report Information report info R nr report decl list 94 A 1 9 SPEX Convergence Information convergence info 55 A 1 10 Expressions ternary_expression or expression and expression compare_expression expression term power prefix factor expression_list int double A 1 11 Identifiers Identifiers may be zero or more leading underscores _ followed by a character followed by any number of charac ters numbers or underscores Punctuation characters and other special characters such as the dollar sign are not C nc convergence decl list or expression or expression or_expression or_expression or expression and expression Logical OR and epxression amp compare_expression Logical AND x and expression compare expression compare expression expression compare_expression expression compare_expression lt expression compare_expression lt expression compare_expression gt expression compare_express
36. name string description string Iqn schema version float Iqn model ordered 0 1 0 1 1 1 2 0 0 1 run control plot control solver params processor slot Iqx comment string conv_val float it_limit unsigned print_int unsigned underrelax coeff float ordered 0 1 0 result general pragma param string value string Figure 3 2 Top level Schema Default name optional The name ofthe model description string optional A description of the model lqn schema version integer fixed 1 0 The version of the schema used by the solver in case of substantial schema changes for model conversion ancore schema version meger ied 10 i dibus boolean optional fase Table 3 1 Attributes for elements of type LqnModelType from Figure 3 2 The element solver params is used to set various operating parameters for the analytic solver and to record various output statistics after a run completes It contains the elements result general and pragma The attributes for solver params are shown in Table These attributes are mainly used to control the analytic solver Refer to Section 6 3 for more information The attributes for result general are shown in Table Refer to Sections and 2 1 2 for the interpretation of h
37. show the number of times the core MVA step function was called The following three columns show the number of time the wait function responsible for computing the queueing delay at a server is called Finally the last three columns list the time the solver spends solving each submodel Finally the solver lists the name of the machine the it was run on the time spent executing the solver code the time spent by the system on behalf of Iqns and the total elapsed time 2 1 2 Simulator Iqsim Figure 3 shows the header information output by the simulator after execution is completed The first line of the output shows the version of the simulator and where it was run The lines labeled Input and Output are the input and output file names respectively The Comment field contains the information found in the comment field of the general information field of the input file c f q3 2 1 Next optionally the output lists any pragma used The remainder of the header lists statistics accumulated during the solution of the model and is specific to the simulator Run time The total run time in simulation time units Number of Statistical Blocks The number of statistical blocks collected when producing confidence intervals Run time per block The run time in simulation units per block This value multiplied by the number of statistical blocks and the initial skip period will total to the run time Seed Value The seed used by simulator
38. slot Iqx ordered ordered 0 1 0 2 0 2 bo 11 2 result general pragma result processor group ordered B 1 1 2 result group task ordered M 0 0 0 tunordered 0 E E 0 fan in fan out nt i iviti result task distribution entry service task activities ordered 0 0 0 1 0 1 entry phase entry activity result entry forwarding activities graph ordered 1 3 1 1 0 0 0 activity precedence reply entry ordered a 0 Lg 0 unbrdered 0 1 0 1 1 0 service time SEDE MER reply result activity distribution synch call asynch call pre i TOR activity 0 2 result call pre pre or pre and post post or post and post loop 02 o ordered 4 12 result join service time activit delay distribution Figure 3 1 Top level LQN Schema Elements shown in blue results found in the output Elements shown in red are not implemented Unless otherwise indicated all elements are ordered from left to right 23 3 2 1 LqnModelType The first element in a layered queueing network XML input file is Lqn model which is of type LqnModel and is shown Figure 3 2 LqnModelType has five elements namely run control plot control solver params processorandslot Run controlandplot controlarenotnotimplemented Processor is described under SectionB 2 2 510 is described in 22 The attributes for LqnModelType are shown in Table 1 LqnModelType
39. the call graph The interlock adjustment is disabled disallow Disallow cycles in the call graph The default is disallow interlocking arg The interlocking is used to correct the throughputs at stations as a result of solving the model using layers 51 This pragma is used to choose the algorithm used Arg must be one of none Do not perform interlock adjustment throughput Perform interlocking by adjusting throughputs The default is throughput layering arg This pragma is used to select the layering strategy used by the solver Arg must be one of batched Batched layering solve layers composed of as many servers as possible from top to bottom batched back Batched layering with back propagation solve layers composed of as many servers as possible from top to bottom then from bottom to top to improve solution speed hwsw Hardware software layers The model is solved using two submodels One consisting soley of the tasks in the model and the other with the tasks calling the processors mol Method Of layers solve layers using the Method of Layers 14 Layer spanning is performed by allowing clients to appear in more than one layer mol back Method Of layers solve layers using the Method of Layers Software submodels are solved top down then bottom up to improve solution speed squashed Squashed layers All the tasks and processors are placed into one submodel Solution speed may suffer because this method generates
40. the input and output file names respectively The line labelled Command line shows all the arguments used to invoke the solver The Comment field contains the information found in the comment field of the general information field of the input file c f 3 2 1 Next optionally the output lists any pragma used Much of this information is also present if the simulator is used to solve the model The remainder of the header lists statistics accumulated during the solution of the model and is solver specific convergence test value The convergence test value is the root of the mean of the squares of the difference in the utilization of all of the servers from the last two iterations of the solver If this value is less than the convergence value c f q3 2 1 A 1 2 specified in the input file then the results are considered valid number of iterations The number of iterations shows the number of times the solver has per formed its outer iteration If the number of iterations exceeds the iteration limit set by the model file the results are considered invalid MVA solver information This table shows the amount of effort the solver expended solving each submodel The first column lists the submodel number Next the column labelled n indicates the number of times the MVA solver was run on the submodel The columns labelled k and show the number of chains and servers in the submodel respectively The next three columns
41. the most number of chains in the MVA solution See also SRVN layers solve layers composed of only one server This method of solution is comparable to the technique used by the srvn solver See also The default is batched back 69 multiserver arg This pragma is used to choose the algorithm for solving multiservers Arg must be one of bruell Use the Bruell multiserver 2 calculation for all multiservers conway Use the Conway multiserver calculation for all multiservers reiser Use the Reiser multiserver 13 calculation for all multiservers reiser ps Use the Reiser multiserver calculation for all multiservers For multiservers with multiple entries scheduling is processor sharing not FIFO rolia Use the Rolia multiserver calculation for all multiservers rolia ps Use the Rolia multiserver calculation for all multiservers For multiservers with multiple entries scheduling is processor sharing not FIFO schmidt Use the Schmidt multiserver 16 calculation for all multiservers suri experimental The default multiserver calculation uses the the Conway multiserver for multiservers with less than five servers and the Rolia multiserver otherwise mva arg This pragma is used to choose the MVA algorithm used to solve the submodels Arg must be one of exact Exact MVA Not suitable for large systems fast Fast Linearizer linearizer Linearizer one step Perform one step of Bard Schweitzer approximat
42. the value a to b using a step size of c The value of b must be greater that a and the step size must be positive Regardless of the format the values for array variables must be constants During the execution of the solver SPEX iterates over all of the values defined for each array variable If multiple arrays are defined then SPEX generates the cross product of all possible parameter values Note that if a scalar variable defined in terms of an array variable then the scalar variable will be recomputed for each model generated by SPEX Observation Variables There is a set of special symbols that are used to indicate to spex which result values from the solution of the model are of interest This result indication has the following form 9 key phase var where lt key gt is a one or two letter key indicating the type of data to be observed and lt phase gt is an optional integer indicating the phase of the data to be observed The data once obtained from the results of the model is placed into the variable var where it may be used in the Result Information section described below To obtain confidence interval info the format is o lt key gt lt phase gt confidence varl var2 where confidence can be 95 or 99 varl is the mean and 2 is the half width of the confidence interval The location of a result indication determines the entity to be observed Table 5 9 describes each of the keys and where they may be used
43. using activities c f 1 1 5 Requests can be served using the following scheduling methods FIFO First in first out first come first served Requests are served in the order in which they arrive This schedul ing discipline is the default for tasks PPR Priority preemptive resume Requests arriving at entries with priorities higher than entry that task is currently processing will preempt the execution of the current entry HOL Head of line priority Requests arriving at entries with higher priorities will be served by the task first Requests in the queue will not preempt the processing of the current entry by the task Priorities range from zero to positive infinity with a priority of zero being the highest The default priority for all entries is zero The subclasses of task are Reference Task Reference tasks used to represent customers in the layered queueing network They like normal tasks in that they have entries and can make requests However they can never receive requests and are always found at the top of a call graph They typically generate traffic in the underlying closed queueing model by making rendezvous requests to lower level servers Reference tasks can also generate traffic in the underlying open queueing model by making send no reply requests instead of rendezvous requests However open class customers are more typically represented using open arrivals which is simply encoded as a parameter to an en
44. with this option only one input file can be specified 1 Generate parseable output suitable as input to other programs such as Iqn2ps 1 and 1 If input is from filename parseable output is directed to filename p If standard input is used for input then the parseable output is sent to the standard output device If the ooutput option is used the parseable output is sent to the file name out put In this case only parseable output is emitted pragma arg Change the default solution strategy Refer to the PRAGMAS section below for more information rtf Output results using Rich Text Format instead of plain text Processors entries and tasks with high utilizations are coloured in red trace arg This option is used to set tracing options which are used to print out various intermediate results while a model is being solved arg can be any combination of the following activities Print out results of activity aggregation convergence arg Print out convergence arg after each submodel is solved This option is useful for tracking the rate of convergence for a model The optional numeric argument supplied to this option will print out the convergence value for the specified mva submodel otherwise the convergence value for all submodels will be printed delta wait Print out difference in entry service time after each submodel is solved forks Print out overlap table for forks prior to submodel solu
45. 1 Basic XML File Structure In XML layered models are specified in a bottom up order which is the reverse of how layered models are typically presented First a processor is defined then within the processor block all the tasks than run on it are defined Similarly within each task block all the entries that are associated with it are defined etc A simplified layout of an incomplete LON model written in XML is shown in Figure Activity graphs specified by task activities belong to a task and hence are siblings to entry elements The element entry activity graph specifies an activity graph contained within one entry but is not supported by any of the LON tools The concept of phases still exists but now each phase is an activity and is defined in the entry phase activities element 3 2 Schema Elements The XML definition for layered models consists of three files lqn xsd lqn xsd is the root of the schema lqn sub xsd lqn core xsd l qn core is the actual model specfication and is included by Iqn xsd All three files should exist in the same location If the solver cannot located the 1gn xsd file it will emit an and stop Figure shows the schema for Layered Queueing Networks using Unified Modeling Language notation The model is defined starting from 1gn model Unless otherwise specified in the figure the order of elements in the model is from left to right i e solver params always preceeds processor in the inpu
46. 3 Processor Information processor info np P np p decl list gt integer total number of processors 91 p decl list p decl proc id scheduling flag quantum multi_server_flag replication_flag proc rate copies ratio l p decl endist p 4 scheduling flag quantum replication flag proc rate multi_server flag opt opt opt integer identifier processor identifier f First come first served h Head Of Line p Priority preemeptive c real completely fair scheduling s real processor sharing i Infinite or delay r Random real variable m copies number of duplicates i Infinite server r copies number of replicas R ratio variable Relative proc speed integer variable real variable A 1 4 Group Information group _info ng Eun aha et cap flag k 4 W L U ng g decl_list end_list integer total number of groups g decl 79 end list g group id group share cap flag proc id identifier real variable A 1 5 Task Information task_info nt t_decl_list t_decl task_id task_sched_type TE 2 T nt tdecl_list integer total number
47. 4 25 sync call 32 task task activities underflow bin 35 unkown error end entry activity defined different error error LON maximum 78 message type error parameters phase priority 4 service time signal type error wait entry entry phase activities EntryActivityDefType 32 Entry ActivityGraph 30 EntryMakingCallType 32 EntryType environment variable override environment variable error activity not reachable reply activity graph 83 AND fork reply attribute missing not declared 80 106 coefficient of variation 86 convergence value cycle activity graph 80 call graph 80 duplicate identifier parameter 87 start activity unique value element duplicate name unkown 85 entry different 81 message type type 81 external variable fan in fan out fatal fork 83 fork list 80 forward forwarding probability group 84 share tasks infinite server iteration limit join join list 80 LOOP reply LOX execution maximum phases message pool model 82 multiplicity 86 not defined not reachable open arrival OR fork Parasol phase deterministic population infinite post precedence 80 pre precedence 80 primary document 21 priority probability processor creation not used rate sharing program limit queue length reference task rendezvous replication
48. 6 Entry Information E int A entry id activity id Start activity F entry id entry id real forward lt entry id gt real 1 Service time by phase y entry id entry id real 1 Synchronous request by phase parameter Records used to specifiy service time and call rate parameters for phases take a list of from one to three arguments and terminated with 1 other entry records with the exception of histogram information take a fixed number of arguments Records which only apply to the simulator are marked with a 5 2 7 Activity Information Activity information sections are required to specify the parameters and connectivity of the activities for a task Note that unlike all other sections each task with activities has its own activity information section An activity information section starts with lt task id gt and ends with 1 The data within an activity infor mation section is partitioned into two parts The first part lists the parameter data for an activity in a fashion similar to the parameter data for an entry the second section defines the connectivity of the activities Listing 5 7 shows the basic syntax Listing 5 7 Activity Information A task id S activity id real activity id real activity id int c f y lt activity id gt entry id real z activity id lt entry id gt real activity
49. 89 0 001603 16 17 0 0243 0 001058 0 001425 17 18 0 02214 0 001087 0 001466 18 19 0 02001 0 001122 0 001512 19 20 0 01806 0 001016 0 001369 20 21 0 01653 0 0009079 0 001224 21 22 0 01499 0 001018 0 001372 22 23 0 01365 0 0007152 0 0009639 23 24 0 01229 0 000955 0 001287 24 25 0 0112 0 0008691 0 001171 25 26 0 009997 0 0006182 0 0008331 26 27 0 009227 0 0007344 0 0009898 27 28 0 008282 0 0006896 0 0009293 28 29 0 007444 0 0005936 0 0007999 29 30 0 006802 0 0005752 0 0007751 overflow 0 06532 0 001561 0 002104 Figure 2 6 Histogram output td holding time components 2 H4 holding time ON 7 Z ready amp wait signal reply m blocked p reply send 1 1 1 1 1 1 Figure 2 7 Time components of a semaphore task 20 Chapter 3 XML Grammar The definition of LQN models using XML is an evolution of the original SRVN file format c f 5 Appendix A 1 The new XML format is based on the work done in 22 with further refinement for general usage There are new features in the XML format to support new concepts for building and assembling models using components The normal tool suite like gns 1 and 145 1 do not support these new features however other tools outside the suite are being written to utilize the new parts of the XML format 3
50. F the Group Summary of Constructors Group processor string name Returns an instance of Group from the current LQN model with the given name 4 3 4 LQN Class Task Summary of Attributes double throughput The throughput of the Task double utilization The utilization of the Task double proc utilization This Task s processor utilization Array phase utilizations Individual phase utilizations Summary of Constructors Task task string name Returns an instance of Task from the current LON model with the given name 50 4 3 5 LQN Class Entry Summary of Attributes boolean has phase 1 boolean has_phase_2 boolean has phase 3 boolean has open wait time double open wait time double phasel proc waiting double phasel service time variance double phasel service tim double phasel utilization double phase2 proc waiting double phase2 service time variance double phase2 service tim double phase2 utilization double phase3 proc waiting double phase3 service time variance double phase3 service tim double phase3 utilization double proc utilization double Squared coeff variation double throughput bound double throughput double utilization Summary of Constructors uni ii iii 4 3 6 LQN Class Phase Summary of Attributes double double double service time service time variation utilization double proc waiting Summary of Constructors Phase phase object entry numeric_in
51. FIFO used processor using processor sharing scheduling needs a quantum value when running on the simulator No requests made from from identifier to to identifier The input file has a rendezvous or send no reply request with a value of zero The processor task and entry chapters of the original input grammar can specify the number of objects that follow The number specified does not match the actual number of objects Specifying zero as a record count is valid Parameter is specified multiple times A parameter is specified more than one time The first occurance is used Processor identifier is not running fair share scheduling A group was defined in the model and associated with a processor using a scheduling discipline other than completely fair scheduling Processor identifier has no tasks A processor was defined in the model but it is not used by any tasks This can occur if none of the entries or phases has any service time Queue Length is incompatible with task type at task identifier A queue length parameter was specified at a task which does not support bounded queues Reference task identifier does not send any messages Reference tasks are customers in the model This reference task does not visit any servers so it serves no purpose Reference task identifier has more than one entry defined Reference tasks typically only have one entry The named reference task has more than one Reque
52. Layered Queueing Network Solver and Simulator User Manual Greg Franks Peter Maly Murray Woodside Dorina C Petriu Alex Hubbard Martin Mroz Department of Systems and Computer Engineering Carleton University Ottawa ON 5B6 cmw greg sce carleton ca January 30 2013 Revision 11145 Contents 1 Layered Queueing Network Mode 1 1 Model Elements 1 1 1 Processor 1 1 7 Request 13 Brief History 2 Headey 2 1 1 29 Service Times N 3 XML Gramma 3 22 Schema Element 12 Multiplicity and Replicatio Analytic Solver 145 Te ee s aan ee ee er ee orc OPEN M eee ee a eee a usus Tr 3 1 Basic XML File Structure Sen oh CPC rnm VERSNS Tr o P COO QA EE E U WW m 11 13 13 13 15 15 15 15 16 16 17 17 18 18 18 18 18 ied Bee pea See sss 30 ECS Ree be yee esas EE US 30 dow whew aude ea NS eae s oe oo 32 TL 32 Sous pees es eee es 33 32 12 OutputResultTy pe 2 29 eo 3099099 wa a VOR E Y MUR are a wo Gb we wet 35 beige eoi Eve n 35 hopes Ee S 35 a 35 35 39
53. This document describes the elements found in Layered Queueing Network Model the results produced when a LQN model is solved and the input and output file formats It also describes the method used to invoke the analytic and simulation solvers and the possible errors that can arise when solving a model The reader is referred to Tutorial Introduction to Layered Modeling of Software Performance for constructing models Chapter 1 Layered Queueing Network Model Figure illustrates the LQN notation with an example of an on line e commerce system In an LQN software resources are all called tasks have queues and provide classes of service which are called entries The demand for each class of service can be specified through phases or for more complex interactions using activities In Figure a task is shown as a parallelogram containing parallelograms for its entries and rectangles for activities Processor resources are shown as circles attached to the tasks that use them Stacked icons represent tasks or pro cessors with multiplicity making it a multiserver A multiserver may represent a multi threaded task a collection of identical users or a symmetric multiprocessor with a common scheduler Multiplicity is shown on the diagram with a label in braces For example there are five copies of the task Server in Figure Entries and activities have directed arcs to other entries at lower layers to represent service req
54. all reply activity elements refers to an activity defined within the men tioned task activities element The head attribute of all post loop elements refers to an activity defined within the mentioned task activities element 88 All post LOOP elements which contain the optional attribute end refers to an activity defined within the mentioned task activities element Not enough elements to match content model elements run control plot control solver params processor slot 8 6 LQX Error messages e Runtime Exception Occured Unable to Convert From juninitialized To Array An unitialized variable is used where an array is expected like in a foreach loop 89 Chapter 9 Known Defects 9 1 MOL Multiserver Approximation Failure The MOL multiserver approximation sometimes fails when the service time of the clients to the multiserver are signif icantly smaller than the service time of the server itself The utilization of the multiserver will be too high Sometimes the problem can be solved by changing the mol underrelaxation Otherwise switch to the more expensive Conway multiserver approximation 9 2 9 3 9 4 9 5 Chain construction for models with multi and infinite servers No algorithm for phased multiservers OPEN class Overtaking probabilities are calculated using CV 1 Need to implement queue lengths for open classes 90 Appendix A Traditional Grammar This chapter gives the
55. allType 67 manual blocking 74 markov max max service tim 271 B2 maximum phases error maximum service time 93 94 message see request asynchronous 5 buffers 777 pool error 5 messages meta model 3 Method of Layers 69 variance method of layers 69 method of samples mid point min min steps model comment 91 error mol mol back mol ms underrelaxation monitor file msgbuf multi server multiplicity 1 9 error infinite server LQN mult iplicity 26 28 multiserver algorithm approximation error Bruell Conway default Reiser Rolia Schmidt multiserver MultiSRVN MVA Bard Schweitzer exact Linearizer mva name no entry node none 69 not defined error not reachable error 84 number of iterations number bins I8 37 on off behaviour 8 one step 70 one step linearizer open arrival error 81 loss probability 97 overflow 71 waiting time open model 5 open arrival rate open wait time OR fork 8 109 error 84 phaseX service time variance 36 or fork 94 phaseX utilization 36 OR join 8 94 platform info 25 OrListType 33 plot control 24 or fork population Or join infinite output error conversion post 33 csv 75 post loop 88 human readable post precedence 8 parseable T1 74 75 error 80 XML 11 65 74 p
56. ample perl script that can be used to control a LONX child process usr bin perl w script to test the creation and control of an lqns solver subprocess using the LOX language with synchronization 45 use FileHandle use IPC Open2 phases 0 0 0 25 0 5 0 75 1 0 calls 0 1 3 0 10 0 run lqnx as subprocess receiving data from standard input open2 lqnxOutput lqnxInput lgnx 99 peva pipe lqnx for Scall calls for Sphase phases print lgnxInput y call p Sphase STOP READ while Sresponse lt lgnxOutput gt m subprocess lqns run print Response from lqnx subprocess S response send data to terminate Iqnx process print lqnxInput continue processing false STOP READ The above program invokes the Iqnx program with its input file as a child process with open2 Two file handles are passed as parameters These will be used to send data over the pipe to the LONX process to be received as standard input and to receive feedback from the program which it sends as standard output The while loop at line 17 waits for the desired feedback from the model solve before continuing This example uses stored data but a real application such as optimization would need to analyze the feedback data to decide which data to send back in the next iteration therefore this synchronization is important When the data is exhausted the LONX process n
57. ance of Delay for a Rendezvous is the variance of the queueing time for a request from a client to the server It does not include the variance of the time the customer spends at the server see Figure 2 4 This result is only available from the simulator 2 5 Mean Delay for a Send No Reply Request The Mean delay for a send no reply request is the time the request spends in queue and in service in phase one at the destination Phase two is treated as a vacation at the server 2 6 Variance of Delay for Send No Reply Request 2 7 Arrival Loss Probabilities The Arrival Loss Probabilities 15 lqsim lqsim 2 8 Mean Delay for a Join The Mean Delay for a Join is the maximum of the sum of the service times for each branch of a fork The source activity listed in the output file is the first activity prior to the fork e g 112 in Figure 2 1 Similarly the destination activity listed in the output file is the first activity after the join AJA131 The variance of the join time is also computed td join time components idle ready running AFBA112 blocked send fork join time join send idle ready running blocked AFBA130 idle ready running blocked AFBA133 receive idle reply ready running blocked IME6 idle ready running blocked CAME2
58. anks Traffic dependencies client server systems and their effect on performance prediction International Computer Performance and Dependability Symposium pages 24 33 Erlangen Germany April 1995 IEEE Computer Society Press 4 1 10 1109 5 1995 395840 6 Greg Franks Tariq Al Omari Murray Woodside Olivia Das and Salem Derisavi Enhanced modeling and solution of layered queueing networks IEEE Transactions on Software Engineering 35 2 148 161 March April 2009 doi 10 1109 TSE 2008 74 7 Roy Gregory Franks Performance Analysis of Distributed Server Systems PhD thesis Department of Systems and Computer Engineering Carleton University Ottawa Ontario Canada December 1999 8 Xianghong Jiang Evaluation of approximation for response time of parallel task graph model Master s thesis Department of Systems and Computer Engineering Carleton University Canada April 1996 9 Lianhua Li and Greg Franks Performance modeling of systems using fair share scheduling with layered queue ing networks In Proceedings of the Seventeenth IEEE ACM International Symposium on Modeling Analysis and Simulation of Computer Telecommunications Systems MASCOTS 2009 pages 1 10 London Septem ber 21 23 2009 doi 10 1109 MASCOT 2009 5366689 Victor W Mak and Stephen F Lundstrom Predicting performance of parallel computations IEEE Transactions on Parallel and Distributed Systems 1 3 257 270 July 1990
59. bability Iqn schema version Iqncore schema version max max service time mid point min missing error multiplicity name not declared error number bins open arrival rate open wait time param phase phaseX proc waiting phaseX service time phaseX service time variance phaseX utilization platform info print_int priority prob prob exceed max service time proc utilization proc waiting 36 quantum queue length quorum replication scheduling 26 sempahore service time service time distribution service time variance share solver info source speed factor squared coeff variation system cpu time think time throughput B6 throughput bound 36 type 21801 underrelax coeff 25 unique name unique phase user cpu time utilization valid 25 value 25 waiting 36 waiting variance x samples xml debug 24 xsi noNamespaceSchemaLocation attribute automatic blocking autonomous phase Bard Schweitzer batch means 77 69 batched layers batched back 69 begin bin bin size block automatic 74 manual 74 simulation 13 size bound to entry 30 32 81 bounds throughput 65 branch AND 1 deterministic exit loop count 8 OR probability bruell 70 buffers 4 call graph 69 call order Call List Group 32 call order 32 calls call s mean 32 cap chain class closed 83 open 83 closed mode
60. between 0 0 and 1 0 full reinitialize For multiple runs reinitialize all processors generate arg This option is used for debugging the solver A directory named arg will be created containing source code for invoking the MVA solver directly ignore overhanging threads Ignore the effect of the overhanging threads iteration limit arg Set the maximum number of iterations to arg Arg must be an integer greater than 0 The default value is 50 man arg Output this manual page If an optional arg is supplied output will be written to the file nameed arg Otherwise output is sent to stdout min steps arg Force the solver to iterate min steps times mol ms underrelaxation arg Set the under relaxation factor to arg for the MOL multiserver approximation Arg must be a number between 0 0 and 1 0 The default value is 0 5 overtaking Print out overtaking probabilities print interval arg Set the printing interval to arg The d or v options must also be selected to display intermediate results The default value is 10 single step Stop after each MVA submodel is solved Any character typed at the terminal except end of file will resume the calculation End of file will cancel single stepping altogether skip layer arg Ignore submodel arg during solution 67 tex arg Output this manual page LaTeX format If an optional arg is supplied output will be written to the file named arg Otherwise output is sent to stdout underrelaxation
61. by phase and activity The utilization is the task utilization i e the reciprocal of the service time for the task c f 2 9 The processor utilization for the task is listed under Utilization and Waiting per Phase for Processor see 42 16 2 15 Arrival Rates and Waiting Times The Arrival Rates and Waiting Times section is only present in the output when open arrivals are present in the input This section shows the arrival rate Lambda and the waiting time The waiting time includes the service time at the task 2 16 Utilization and Waiting per Phase for Processor The Utilization and Waiting per Phase for Processor lists the processor utilization and the queueing time for every entry and activity running on the processor 18 lqsim 61 Service time distributions for entries and activities SCE3 PHASE 1 Mean 11 58 Stddev 8 457 Skew 0 8501 Kurtosis 0 2496 Begin End Prob 95 99 0 1 0 03355 0 001048 0 001412 1 2 0 03786 0 001605 0 002163 2 3 0 05406 0 002026 0 002731 3 4 0 06333 0 002031 0 002737 4 5 0 06545 0 001631 0 002199 5 6 0 06369 0 001578 0 002127 6 7 0 06049 0 001692 0 00228 7 8 0 05591 0 001822 0 002456 8 9 0 05133 0 001272 0 001714 9 10 0 0472 0 001767 0 002382 10 11 0 04318 0 001618 0 002181 11 12 0 03931 0 001185 0 001597 12 13 0 03579 0 001073 0 001446 13 14 0 03231 0 001654 0 002229 14 15 0 02952 0 001033 0 001392 15 16 0 02677 0 0011
62. d analytic solver limit the number of phases to three 1 1 5 Activities Activities are the lowest level of specification in the performance model They are connected together using dence c f to form a directed graph to represent more than just sequential execution scenarios Activities consume time on processors The service time is defined by a mean and variance the latter through coef ficient of variation squared El The service time between requests to lower level servers is assumed to be exponentially distributed with the exception of bursty reference tasks so the total service time is the sum of a random number of exponentially distributed random variables 2 meta model in Fieure 1 2 only shows activities phases a notational short hand 3The squared coefficient of variation is variance divided by the square of the mean el Sel 1 2 1 2 y el el 12 212 1 1 2 2 1 2 a Phases Figure 1 3 9 J sd Phases J client Task server Task reply Pi QR 1 al 2 1 t s al 1 s 2 2 y al 2 1 y 2 e2 1 l A t2 s all S a2 2 al e2 gt a2 l b Activities Entry Specification Phase 1 Phase 2 Phase 3 Figure 1 4 Phases for an Entry Activities also make requests to entries on other task
63. dentifier has no tasks The group named by identifier has no tasks assigned to it A group requires a minimum of one task Group identifier has invalid share of nn The share value of n n for group identifier is not between the range of 0 n n lt 1 0 Infinite throughput for task identifier Model specification error 1408 The response time for the task identifier is zero The likely cause is zero service time for all calls made by the task Initial delay of is too small client s still running Iqsim This error occurs when the initial loops parameter for automatic blocking is too small Invalid fan in of n source task identifier is not replicated Iqns The fan in value for a request specifies the number of replicated source tasks making a call to the destination To correct this error the source task needs to be replicated by a multiple of n Invalid fan out of n destination task identifier has only m replicas Iqns The fan out value n is larger than the number of destination tasks m In effect the source will have more than one request arc to the destination 82 Invalid path to join join list for task identifier backtrace is list The activity graph for task identifer is invalid because the branches to the join join list do not all originate from the same fork List is a dump of the activity stack when the error occurred Invalid probability of nn The probability of n n is not between the ran
64. dev skew kurtosis hist_bin begin end probability binconf 3 mean real stddev real skew real kurtosis real probability real bin conf conf_level real A 2 13 Throughputs and Utilizations Distribution mean Distribution standard deviation Distribution skew Distribution kurtosis 0 0 1 0 x thpt_ut FQ nt thpt_uttask end list thpt_ut_task taskname net lt thpt_ut_entry gt end_list thpt_ut_task_total ps thpt_ut_entry entry_info thpt_ut confidence Yo entry info throughput utilization end list total_util throughput real Task Throughput utilization float phase list Per phase task util total util real thpt ut task total entry info thpt_ut_conf Yo thpt_ut_conf conf_level entry_info conf_level integer A 2 14 Arrival Rates and Waiting Times open arrivals R no open arvl_entry end_list no gt open_arvi_entry from entry to entry real real from_entry real Inf integer 98 Number of Open Arrivals A 2 15 Utilization and Waiting per Phase for Processor processor proc group proc task proc task info priority multiplicity proc info proc entry info sched delay proc entry_conf task_tota
65. e Source entry id entry_name Destination entry id identifier identifier real float identifier end_list integer A 2 1 General Information i n n general valid convergence iterations processors phases 4 4d dod valid convergence iterations n processors V yes_or_no real I integer PP integer NP integer A 2 2 Throughput Bounds bound bounds entry nt EX gt A 2 3 Times waiting_t_tbl waiting_e_tbl waiting entry waiting a tbl waiting_activity na 1 B nt bounds entry M end taskname real integer Total number of tasks W ne waiting ttbl M end_list task name waiting e tbl end list waiting a tbl A 2 4 Waiting Time Variance wait var wait_var_t_tbl wait_var_e_tbl wait_var_entry wait_var_a_tbl k opt waiting_entry 10 from_entry to_entry float_phase_list integer Number of Entries waiting_activity 6 end_list from_activity to_entry float_phase_list integer Number of Activities VARW ne wait_var_ttbl end_list taskname wait var e tbl end_list wait var_athl op 0 from_entry to_entr
66. e MVA for each iteration of a submodel The default is to perform Bard Schweitzer approximate MVA until convergence for each submodel This option combined with Playering srvn most closely approximates the solution technique used by the srvn solver one step linearizer Perform one step of Linearizer approximate MVA for each iteration of a submodel The default is to perform Linearizer approximate MVA until convergence for each submodel schweitzer Bard Schweitzer approximate MVA The default is linearizer overtaking arg This pragma is usesd to choose the overtaking approximation Arg must be one of markov Markov phase 2 calculation none Disable all second phase servers All stations are modeled as having a single phase by summing the phase information rolia Use the method from the Method of Layers simple Simpler but faster approximation special The default is rolia processor arg Force the scheduling type of all uni processors to the type specfied fcfs All uni processors are scheduled first come first served hol All uni processors are scheduled using head of line priority ppr uni processors are scheduled using priority pre emptive resume 70 ps uni processors are scheduled using processor sharing The default is to use the processor scheduling specified in the model severity level arg This pragma is used to enable or disable warning messages advisory all run time warning The default is all
67. e changed as SPEX executes though this behaviour may not be appropriate in many cases Scalar Variables Scalar variables are used to set input values for the model and are initialized using any lt ternary expression gt using this syntax name lt ternary expression gt The lt ternary expression gt may contain any variables defined previously or subsequently in the input file order does not matter However undefined variables and observation variables more on these below are not permitted Refer to Appendix A for the complete grammar for lt ternary expression gt 60 Key Phase Description 7 Su no Utilization processor declaration p info yes task declaration t info yes entry service declaration s info SE no Throughput task declaration t info e Ley servien ection in Spu no Processor Utilization task declaration t info eny semiee gectaaion Cinto Call waiting time entry call declaration y info no entry open arrival declaration a info Table 5 9 Observation Key location oe oe Array Variables Array variables are used to specify a range of values that an input parameter may take on There are two ways to specify this information Sname x y Z Sname a b The first form is used to set the variable name to the values in the list x y z The second form is used the set the variable name from
68. e execution of the simulator since the Parasol output routines do no emit this information at present Output is directed to stdout unless redirected using m ile error error This option is to enable floating point exception handling 74 a Abort immediately on a floating point error provided the floating point unit can do so b Abort on floating point errors default i Ignore floating point errors w Warn on floating point errors The solver checks for floating point overflow division by zero and invalid operations Underflow and inexact result exceptions are always ignored In some instances infinities will be propogated within the solver Please refer to the stop on message loss pragma below houtput Generate comma separated values for the service time distribution data If output is a directory the output file name will be the name of a the input file with a csv extension Otherwise the output will be written to the named file nfile n t Direct all output generated by the various debugging and tracing options to the monitor file file rather than to standard output A filename of directs output to standard output no execute Read input but do not solve The input is checked for validity No output is generated output output Direct analysis results to output A file name of directs output to standard output If output is a directory all output fro
69. e fork join matching process interlock Print out the interlocking table and the interlocking between all tasks and processors joins Joins not functional layers Print out the contents of all of the layers found in the model 14 Debug parser overtaking Overtaking not functional quorum Print out results from pseudo activities used by quorum 65 n xml Debug XML error arg This option is to enable floating point exception handling Arg must be one of the following 1 a Abort immediately on a floating point error provided the floating point unit can do so 2 d Abort on floating point errors default 3 i Ignore floating point errors 4 w Warn on floating point errors The solver checks for floating point overflow division by zero and invalid operations Underflow and inexact result exceptions are always ignored In some instances infinities will be propogated within the solver Please refer to the stop on message loss pragma below fast This option is used to set options for quick solution of a model using One Step Bard Schweitzer MVA It is equivalent to setting pragma mva one step layering batched multiserver conway help arg no execute Read input but do not solve The input is checked for validity No output is generated output arg Direct analysis results to output A filename of directs output to standard output If Iqns is invoked
70. e parameter types for Iqns An error will be reported if an unsupported parameter is supplied except when the value supplied is the same as the default 6 5 Diagnostics Parameter Phases Scheduling Open arrivals Phase type Think Time Coefficient of variation Interprocessor delay Asynchronous connections Forwarding Multi servers Infinite servers Max Entries Max Tasks Max Processors Max Entries per Task 1408 3 FIFO HOL PPR yes stochasic deterministic yes yes yes yes yes yes yes 1000 1000 1000 1000 Table 6 1 LONS Model Limits Most diagnostic messages result from errors in the input file If the solver reports errors then no solution will be generated for the model being solved Models which generate warnings may not be correct However the solver will generate output 72 Sometimes the model fails to converge particularly if there several heavily utilized servers in a submodel Sometimes this problem can be solved by reducing the value of the under relaxation coefficient It may also be necessary to increase the iteration limit particularly if there are many submodels With replicated models it may be necessary to use srvn layering to get the model to converge Convergence can be tracked using the t convergence option The solver will sometimes report some servers with high utilization This problem is the result of some of the approximations used in particular two p
71. ead loop Sample input y 10 0 p 1 0 STOP READ continue processing false STOP READ Controlling LQNX from a Parent Process The file output and data reading functions can be combined to allow an LQNX process to be created and controlled by a parent process through pipes Input data can be read in from pipes be used to solve a model with those parameters and the output of the solve can be sent back through the pipes to the parent process for analysis A LQX program can easily be written to contain a main loop that reads input solves the model and returns output for analysis The termination of the loop can be controlled by a boolean flag that can be set from the parent process This section describes an example of how to control LQNX execution from a parent process in this case a per1 script which uses the open2 function to create a child process with both the standard input and output mapped to file handles in the per1 parent process This allows data sent from the parent to be read with read_data stdin and output from the print statements sent to standard output to be received for analysis in the parent This also provides synchronization between the parent and the child LONX processes The read data func tion blocks the LONX process until it has received its expected data Similarly the parent process can be programmed to wait for feedback from the child LONX process before it continues The following is an ex
72. eader information The attributes for pragma are show in Table 3 4 Refer to Section 6 2 for the pragmas supported by 14 and to Section 7 3 for the pragmas supported by 1451 24 conv_val Convergence value for Iqns c f 96 3 Ignored by Iqsim it limit Iteration limit for 146 c f 86 3 Ignored by 19 print int integer optional Print interval for intermediate results The tprint must be specified to Ilqns to generate output after it limit iterations Blocked statistics must be specified to Iqsim using the An Bn or Cn flags underrelax coeff float optional 0 5 Under relaxation coefficient for Iqns c f nored by lqsim Table 3 2 Attributes of element solver params from Figure Peonv val or required Convergence value CELD valid enumeration required Eithervesorno iterations float optional The number of iterations of the eoi solver or er erem emer Fslapsed time optional The wall clock time used by the solver Lsystem cpu time string optional The CPU time spent in kemel mode Fuser cpu time string optional The CPU time spent in user mode platform info string optional operating system and CPU type soiver info sting optional The version ofthe solver Table 3 3 Attributes of element result general from Figure 3 2 Default sing required The
73. eady been defined This one is a duplicate e Symbol identifier not previously defined All identifiers must be declared before they can be used e Task identifier cannot be an infinite server This error occurs whenever a reference task or a semaphore task is designated as an infinite server Reference tasks are the customers in the model so an infinite reference task would imply an infinite number of customerd An infinite semaphore task implies an infinite number of buffers no blocking at the wait entry would ever occur e Task identifier has activities but none are reachable None of the activities for identifier is reachable The most likely cause is that the start activity is missing e Task identifier has no entries No entries were defined for identifier 2 An infinite source of customers should be represented by open arrivals instead 84 8 3 Task identifier has n entries defined exactly required The task identifier has n entries m are required This error typically occurs with semaphore tasks which must have exactly two entries Task task identifier Activity activity identifer is not specified An activity is declared but not defined An activity is defined when some parameter such as service time is specified Task task identifier Activity activity identifer makes a duplicate reply for Entry entry identifier An activity graph is making a reply to entry entry id
74. eating Responsive Scalable Software Object Technology Series Addison Wesley 2002 19 Connie U Smith and Catalina M Llad Performance model interchange format PMIF 2 0 XML definition and implementation In Proceedings of the First International Conference on the Quantative Evaluation of Systems QEST pages 38 47 Enschede the Netherlands September 27 30 2004 IEEE Computer Society Press C Murray Woodside John E Neilson Dorina C Petriu and Shikharesh Majumdar The stochastic rendezvous network model for performance of synchronous client server like distributed software IEEE Transactions on Computers 44 8 20 34 August 1995 4 1 10 1109 12 368012 21 Murray Woodside and Greg Franks Tutorial introduction to layered modeling of software performance Revision 6554 5 22 Xiuping Wu An approach to predicting peformance for component based systems Master s thesis Department of Systems and Computer Engineering Carleton University Ottawa Ontario Canada August 2003 Available from ftp ftp sce carleton ca pub cmw xpwu mthesis pdf 101 Index um b b utomatic 74 locks 74 ounds only 65 onfidence 74 onvergence 68 f g h h i ebug 65 74 ebug 1qx 68 76 ebug srvn 69 ebug xm1 68 76 rror 66l 74 xact mva 68 ast 66 1 1 1 76 1 66 wsw layering 68 gnore advisories 65
75. eeds to be told to quit This is done with the final print statement which sets the continue processing flag to false This causes the main loop in the LOX program which follows to quit lt lqx gt lt CDATA i 1 p 0 0 y 0 0 continue_processing true while continue_processing read_data stdin read_loop read data from input pipe x if continue processing 1 Spl 2 0 lt p 5 2 2 0 x 1 p Syl yi y2 0 5 y solve send output of solve through stdout through pipe printin subprocess lans run 4d i tl throughput tl throughput i i 1 46 11 gt lt 1 gt The variables p y and continue processing all need to be initialized to their correct types before the loop begins as they need to exist when the read data function searches for them in the symbol table This is necessary as they are all local variables External variables that exist in the LON model such as p and y don t need initialization 4 1 4 Actual Example of an LOX Model Program The following code is the complete LQX program for the model designated peva 99 The model itself contains a few model parameters which the LQX code configures notably p1 p2 y1 and y2 The LQX program is responsible for setting the values of all model parameters at least once invoking solve and optionally printing out certain result values Accessing of result values is done via the LONS bindin
76. el is unique in that it is more closely aligned with the architecture of a software system that it is with a conventional queueing network model such as Performance Model Interchange Format PMIF 17119 The latter consists of stations with queues and visits whereas a LQN has processors tasks and requests A Layered Queueing Network is a directed graph Nodes in the graph consist of tasks processors entries activi ties and precedence Arcs in the graph consist of requests from one node to another The model objects are described below LayeredQueueing Network T puse 2 gt Processor Reference I Task i I I I I Group Task Semaphore Task invokes 5 0 1 5 m 0 0 0 1 1 26 FanOut Entry Activity Precedence 1 src dst 1 src 1 next Y next 0 1 0 1 connects 1 forwards Request Pre next gt Post calls 02 0 0 2 Forward SendNoReply Rendezvous OrJoin AndJoin OrFork AndFork Loop Figure 1 2 LQN Meta Model 1 1 1 Processors Processors are used by the activities within a performance model to consume time They are pure servers in that
77. el results by iterating through a set of submodels until either convergence is acheived or the iteration limit is hit Convergence is determined by taking the root of the mean of the squares of the difference in the utilization of all of the servers from the last two iterations of the MVA solver over the all of the submodels then comparing the result to the convergence value specified in the input file If the RMS change in utilization is less than convergence value then the results are considered valid If the model fails to converge three options are available 1 reduce the under relaxation coefficient Waiting and idle times are propogated between submodels during each iteration The under relaxation coefficient determines the amount a service time is changed between each itera tion A typical value is 0 7 0 9 reducing it to 0 1 may help 2 increase the iteration limit The iteration limit sets the upper bound on the number of times all of the submodels are solved This value may have to be increased especially if the under relaxation coefficient is small or if the model is deeply nested The default value is 50 iterations 3 increase the convergence test value Note that the convergence value is the standard deviation in the change in the utilization of the servers so a value greater than 1 0 makes no sense The convergence value can be observed using t convergence flag 6 4 Model Limits The following table lists the acceptabl
78. end of a model solution and then fed back in to the model The model is solved repeatedly until the parameter value converges The convergence section is declared in a manner similar to the result section Listing 5 9 Convergence Information lt int gt Svar Svar lt expression gt 1 Only this time the convergence variables must be parameters They cannot be result variables or tag variables 5 3 4 Differeneces to SPEX 1 This section outlines differences in the syntax between SPEX version 1 and version 2 SPEX version was processed by a Perl program to convert the model into a conventional model file SPEX version 2 is now parsed directly and converted into LQX internally Array Initialization Lists used for array initialization must now be enclosed within square brackets Further the items must be separated using commas Figure shows the old and new syntax Perl Expressions Perl Expressions are no longer supported in SPEX 2 0 Rather a subset of LQX expressions are used instead For SPEX convergence expressions Perl if then else statements must be converted to use the ternary operator SPEX 2 cannot invoke Perl functions 5The number is ignored it is present in the syntax so that the report section matches the other sections 62 1 Sarray 1 2 3 1 1 2 3 Sarray 1 10 2 2 array 1 10 2 a Spex 1 b Spex 2 Figure 5 1 x Line Continuation Line continuation
79. ent was not found in the input file External synchronization not supported for task identifier at join join list Iqns The analytic solver does not implement external synchronization External variables are present in file filename but there is no LQX program to resolve them 14 The input model contains a variable of the form Svar as a parameter such as a service time multiplicty or rate The variables are only assigned values when an LQX program executes Since no LQX program was present in the model file the model cannot be solved Fan ins from task from identifier to task to identifier are not identical for all Calis Iqns All requests made from task from identifier to task to identifier must have the same fan in and fan out values Fan out from activity entry task src identifier n n replicas does not match to entry processor dst identifier n 1408 This error occurs when the number of replicas at src identifier multiplied by the fan out for the request to dst identifier does not match the number of replicas at dst identifier multiplied by the fan in for the request from src identifier A fan in or fan out of zero a common error case can arise when the ratios of tasks to processors is non integral Fewer entries defined n than tasks m A model was specified with more tasks than entries Since each task must have at least one entry this model is invalid Group i
80. entifier even though the entry is already in phase two This error usually occurs when more than one reply to entry identifier is specified in a sequence of activities Task task identifier Activity activity identifer makes invalid reply for Entry entry identifier An activity graph is making a reply to entry entry identifier even though the activity is not reachable Task task identifier Activity activity identifer replies to Entry entry identifier which does not accept rendezvous requests The activity graph specifies a reply to entry entry identifier even though the entry does not accept rendezvous requests The entry either accepts send no reply requests or open arrivals Unknown element element The element is not expected at this point in the input file Element may not be spelled incorrectly or if not in an incorrect location in the input file Advisory Messages Invalid convergence value of nn using m m 1405 The convergence value specified in the input file is not valid The analytic solver is using m m instead Invalid standard deviation sum n n sum sqr n n n n n When calculating a standard deviation the difference of the sum of the squares and the mean of the square of the sum was negative This usually implies an internal error in the simulator Iteration limit of n is too small using m Iqns The iteration limit specified in the input file is not valid The analytic solver is using m
81. es defined in the convergence section for change and if any of the variables changes by a non trivial amount the loop repeats Listing shows a model defined defined using SPEX syntax Listing 5 11 shows the corresponding LQX program generated by the model file 63 Listing 5 10 SPEX file layout ly 25 3 ly 2 3 m server 2 m client m server s server P2 p client i P server s 0 1 1 T2 t client r client 1 client m m client f f client t server n server 1 server m m server u u server 1 2 client 1 1 client server s_server 1 S server 1 1 1 R 3 50 Sf_client Su_server 1 Listing 5 11 LQX Program for SPEX input m_client 1 2 3 Sm_client m_server 2 3 4 m server foreach m client in m client foreach m server in m server s server m client 2 s server solve Sf client task client throughput f 5 1 u server task server utilization u Sres2 printin 50 5 client S server 64 1 2 3 2 3 4 Sm_client 2 Chapter 6 Invoking the Analytic Solver 1408 The Layered Queueing Network Solver LQNS is used to solved Layered Queueing Network models analytically Lqns reads its input from filename specified at the command line if present or from the standard input oth erwise By default output for an input file ilename specified on the command line will be placed in the file f
82. es for processor identifier have a range of nn nn Results may not be valid 1408 The range of values of service times for a processor using processor sharing scheduling is over two orders of magnitude The results may not be valid Specified confidence interval of n n not met after run time of Actual value is n n lqsim Submodel n is empty 1408 The call graph is interesting to say the least Underrelaxation ignored n n outside range 0 2 using mm 1408 The under relaxation coefficient specified in the input file is not valid The solver is using m m instead The utilization of at task processor identifier with multiplicity mis too high This problem is the result of some of the approximations used by the analytic solver The common causes are two phase servers and the Rolia multiserver If identifer is a multiserver switching to the Conway approxima tion will often help Values of n n in excess of 10 are likely the result of failures in the solver Please send us the model file so that we can improve the algorithms Warning Messages activity entry task processor identifier is not used ry The object is not reachable This may indicate error in the specification of the model Processor Task identifier is an infinite server with a multiplicity of m Infinite servers must always a multiplicty of one This error is caused by specifying both delay scheduling and a multiplicity fo
83. for elements of type ActivityLoopType 34 3 2 12 OutputResultType The type OutputResultType shown in Figure is used to create elements that store results described earlier in Section OutputResultType is a subtype of ResultContentType This latter type defines the result element s attributes Elements of this OutputResultType can contain two elements of type ResultContentType which contain the 95 and 99 confidence intervals provided that these results are available The attributes for elements of ResultContentType are listed in Table 3 19 and are used to store the actual results produced by the solver Note that all the attributes are optional elements of this type will only have those attributes which are relevant Result ContentType Output ResultType result processor result group result task result entry result activity result call 0 1 0 1 result 95 conf result 99 conf Figure 3 9 Schema diagram for type OutputResultType 3 2 13 OutputResultJoinDelayType The type OutputResultJoinDelayType is similar to OutputResultType The attributes of this type are shown in Table 3 20 3 2 14 OutputDistributionType Elements of type OutputDistributionType shown in Figure 3 11 are used to define and store histograms of phase and activity service times The optional underflow bin overflow bin and
84. fter 30 blocks Confidence intervals can be tightened by either running additional blocks or by increasing the block size A rule of thumb is the block size should be 10 000 times larger than the largest service time demand in the input model 77 7 5 Model Limits The following table lists the acceptable parameter types and limits for lqsim An error will be reported if an unsup ported parameter is supplied except when the value supplied is the same as the default Parameter Phases Scheduling Open arrivals Phase type Think Time Coefficient of variation Interprocessor delay Asynchronous connections Forwarding Multi servers Infinite servers Max Entries Max Tasks Max Processors Max Entries per Task Iqsim 3 FIFO HOL PPR RAND yes stochastic deterministic yes yes yes yes yes yes yes unlimited 1000 1000 unlimited Table 7 1 Lqsim Model Limits 78 Chapter 8 Error Messages Error messages are classified into four categories ranging from the most severe to the least they are fatal error advisory and warning Fatal errors will cause the program to exit immediately All other error messages will stop the solution of the current model and suppress output generation However subsequent input files will be processed Advisory messages occur when the model has been solved but the results may not be correct Finally warnings indicate possible problems with the model which the solver has ignored
85. ge of zero to one inclusive The likely cause for this error is the sum of the probabilities either from an OR fork or from forwarding from an entry is greater than one Name identifier previously defined The symbol identifer was previously defined Tasks processors and entries must all be named uniquely Activi ties must be named uniquely within a task Model has no reference tasks There are no reference tasks nor are there any tasks with open arrivals specified in the model Reference tasks serve as customers for closed queueing models Open arrivals serve as sources for open queueing models No calls from entry activity from identifier to entry to identifier Iqns This error occurs when the fan in or fan out parameter for a request are specified before the actual request type Switch the order in the input file No group specified for task task identifier running on processor proc identifier using fair share scheduling Task task identifier has no group specified yet it is running on processor proc identifier which is using com pletely fair scheduling No signal or wait specified for semaphore task identifier Task identifier has been identified as a semaphore task but neither of its entries has been designated as a signal or a wait Non reference task identifier cannot have think time A think time is specified for a non reference task Think times for non reference tasks can only be specified by entry Non semap
86. ges e Number All numbers are stored in IEEE double precision floating point format e String Any literal values between and in the input e Null This is a special type used to refer to an empty variable e Boolean A type whose value is limited to either true or false e Object An semi opaque type used for storing complex objects See Objects e File Handle File handles to open files for writing appending or reading See File Handles 39 also supports pseudo intrinsic Array type Whereas for any other object types the only way to interact with them is to explicitly invoke a method on them objects of type Array may be accessed with operator and with operator familiar C and C style syntax The Object type also allows certain attributes to be exposed as properties These values are accessed with the traditional C style object property syntax An example property is the size property for an object of type Array accessed as array size Only instances of type Object its derivatives have properties Number String Null and Boolean instances all have no properties Built in Operators Arrays and Iteration The built in Array type is very similar to that used by PHP It is actually a hash table also known as a Dictionary or a Map for which you may use any object as a key and any object as a value It is important to realize that differe
87. gs API documented in Section 3 The program begins by defining an array of values that it will be setting for each of the external variables By enumerating as follows the program will set the variables for the cross product of phase and calls phase 0 0 0 25 0 5 0 75 1 0 calls 0 1 3 0 10 0 1 foreach idx p in phase 1 foreach idx y in calls Next the program uses the input values p and y to compute the values of p1 p2 5 1 and y2 Any assign ment to a variable beginning with a requires that variable to have been defined externally within the model definition When such an assignment is made the value of the right hand side is effectively put everywhere the left hand side is found within the model Spl 2 0 p 5 2 2 0 1 Syl y2 0 5 y Since all variables have now been set the program invokes the solve function with its optional parameter the suffix to use for the output file of the current run This particular program outputs in out pl p2 yl y2 files so that results for a given set of input values can easily be found As shown in the documentation in Section 3 solve opt suffix will return a boolean indicating whether or not the solution converged and this program will abort when that happens although that is certainly not a requirement if solve str pl1 p2 S y1 y2 false println peva 99 xml LOX Failed to solve the model properly abo
88. hase servers Utilizations in excess of 10 are likely the result of failures in the solver Please send us the model file so that we can improve the algorithms 73 Chapter 7 Invoking the Simulator Iqsim Lqsim is used to simulate layered queueing networks using the PARASOL simulation system Lqsim reads its input from files specified at the command line if present or from the standard input otherwise By default output for an input file filename specified on the command line will be placed in the file filename out If the p switch is used parseable output will also be written into filename p If XML input is used results will be written back to the original input file This behaviour be changed using the ooutput switch described below If several files are named then each is treated as a separate model and output will be placed in separate output files If input is from the standard input output will be directed to the standard output The file name is used to specify standard input The ooutput option can be used to direct output to the file or directory named output regardless of the source of input Output will be XML if XML input is used parseable output if the p switch is used and normal output otherwise multiple input files cannot be specified If output is a directory results will be written in the directory named output Output can be directed to standard output by using 1 the output f
89. his processor serving a common queue Multiplicity is specified using the syntax shown in Table By default a single copy of a processor is used for the model Scheduling Discipline First come first served Priority preemptive resume Random Delay infinite server Head of Line c real Completely fair share with time quantum real s real Round Robin with time quantum real Table 5 1 Processor Scheduling Disciplines see 41 1 1 Multiplicity m int int identical copies with a common queue i Infinite or delay lt opt repl gt Repliplication lt int gt replicated copies with separate queues Table 5 2 Multiplicity and Replication see 41 2 5 2 4 Group Information Groups are specified in the group information section of Listing 5 4 Group Information U lt int gt g lt group id gt lt real gt opt cap proc id 1 3The number of processors lt int gt is ignored with all current solvers 56 5 2 5 Task Information Tasks are specified in the task information section of the input file using the syntax shown in Listing 5 5 The start of the task section is identified using lt int gt and ends with 1 lt int gt parameter is either the number of task definitions in this section or zero Listing 5 5 Task Information T int t task id sched entry list 1 lt proc id gt opt pri opt think time opt mult lt opt rep
90. histogram bin elements all the elements are of type HistogramBinType are used to store results The attributes of OutputDistributionType elements are used to both store the parameters for the histogram and output statistics Refer to Table 3 21 3 2 15 HistogramBinType 3 3 Schema Constraints The schema contains a set of constraints that are checked by the Xerces XML parser 1 to ensure that the model file is valid XML editors can also enforce these constraints so that the model is somewhat correct before being passed to the simulator or analytic solver The constraints are as follow e All processor must have a unique name e Alltasks must have a unique name 35 xref proc utilization Processor utilization for a task entry or ac 42 16 tivity proc waiting Waiting time at a processor for an activity phaseX proc waiting Waiting time at a processor for phase X of an entry open wait time Waiting time for open arrivals service time Activity service time loss probability float Probability of dropping an asynchronous phaseX service tim service time variance t a t 5 NIN 2 NO 1 eise phaseX service time variance Variance for phase X of an entry phaseX utilization Utilization for phase X of an entry prob exceed max servicectime fou squared coeff variation float Squared coefficient of variation over all phases of an entry throughput bound float Thro
91. hore task identifer cannot have a signal wait for entry entry The entry is designated as either a signal or a wait However identifier is not a semaphore task Number of entries tasks processors is outside of program limits of 1 An internal program limit has been exceeded Reduce the number of objects in the model Number of paths found to AND Join join lit for task identifier does not match join list During activity graph traversal one or more of the branches to the join join list either originate from different forks or do not originate from a fork at all Open arrival rate of nn to task identifier is too high Service time is 1408 The open arrival rate of n n to entry identifier is too high so the input queue to the task has overflowed This error may be the result of a transient condition so the stop on message loss pragma c f may be used to suppress this error If the arrival rate exceeds the service time at the time the model converges then the waiting time results for the entry will show infinity Note that if a task accepts both open and closed classes an overflow in the open class will result in zero throughput for the closed classes 83 e OR branch probabilities for OR Fork list for task identifier do not sum to 1 0 sum is mn branches from an or fork must be specified so that the sum of the probabilities equals one e Processor identifier has invalid rate of n n
92. ile name is 7 1 Command Line Options automatic run time precision skip Use automatic blocking with a simulation block size of run time The precision argument specifies the desired mean 95 confidence level By default precision is 1 0 The simulator will stop when this value is reached or when 30 blocks have run Skip specifies the time value of the initial skip period Statistics gathered during the skip period are discarded By default its value is 0 When the run completes the results reported will be the average value of the data collected in all of the blocks If the R flag is used the confidence intervals will for the raw statistics will be included in the monitor file B blocks blocks run time skip Use manual blocking with blocks blocks The value of blocks must be less than or equal to 30 The run time for each block is specified with run time Skip specifies the time value of the initial skip period C confidence precision initial loops run time Use automatic blocking stopping when the specified precision is met The run time of each block is estimated based on initial loops running on each reference task The default value for initial loops is 500 The run time argument specifies the maximum total run time d debug This option is used to dump task and entry information showing internal index numbers This option is useful for determining the names of the servers and tasks when tracing th
93. ilename out If the p switch is used parseable output will also be written into filename p If XML input or the x switch is used XML output will be written to filename 1 This behaviour can be changed using the ooutput switch described below If several files are named then each is treated as a separate model and output will be placed in separate output files If inputis from the standard input output will be directed to the standard output The file name is used to specify standard input The ooutput option can be used to direct output to the file out put regardless of the source of input Output will be XML if XML input or if the switch is used parseable output if the switch is used and normal output otherwise Multiple input files cannot be specified when using this option Output can be directed to standard output by using o 1 the output file name is 6 1 Command Line Options ignore advisories Ignore advisories The default is to print out all advisories b bounds only This option is used to compute the Type 1 throughput bounds only These bounds are computed assuming no contention anywhere in the model and represent the guaranteed not to exceed values d debug arg This option is used to enable debug output Arg can be one of activities Activities not functional all Enable all debug output calls Print out the number of rendezvous between all tasks forks Print out th
94. ime think time real variable Think time for phase to entry entry id Destination of a message A 1 7 Activity Information activity info activity defn list activity connections p 1151 Activity definition activity defn list activity defn 1 activity defn activity_id coeff of variation Sqr Coeff of Var f activity_id ph type flag Phase type H entry_id histmin hist bins hist_type M activity_id max _service_time s activity id ph_serv_time Service time Z activity_id think time Thinktime y activity id rendezvous Rendezvous 2 activity_id to entry Send no reply Activity Connections activity connections activity_conn_list activity conntist activity conn _1151 join list gt fork_list join list reply activity and_join_list or join list fork list activity id and_fork_list or_fork_list loop list and_join_list reply activity amp reply activity Ji quorum count ops or join list 1 and fork list activity id activity id 1 or_fork_list prob activity prob activity loop
95. ime float fanin unsigned max service time float fanout unsigned call order CallOrderType TaskActivity EntryActivity Graph Graph ActivityMaking Activity ActivityDefT EntryActivity CallType PhasesType ANER O DefType a entry activity calls mean float phase 1 3 bound to entry string first activity string task activities graph ordered ordered ordered is 0 o activity activity precedence reply entry name string unordered 0 5 ordered o 0 2 0 2 T result activity r mi x synch call asynch call distribution reply activity name string Figure 3 6 Schema diagram for the type ActivityGraphBase name string required The name of the activity which generates a reply The entry is either implicitly defined if this element is de fined within an EntryType or part of list defined within a reply element Table 3 12 Attributes of element reply activity from Figure 31 3 2 9 ActivityDefBase The type ActivityDefBase shown Figure is used to define the parameters for an activity such as demand and call order This type is extended by ActivityPhasesType EntryActivityDefType and ActivityDefType to def
96. in a oe be ee PRI MIS RET E 56 Ledge kee MUERE I eee NE EMI NM 57 bees 57 58 58 5 3 1 Variables 2x 2 de a Sy uzi noh Ge he Sc AMEN ie ded Wen d inc 60 VE bbe a eee od bee hae 6 2be eases des ec 62 PITT 62 534 _ Dittereneces to SPEX l zu iuo ack ioe Ae 8 W N RUD wo Gua 62 525 SPEX and LOX uode ROPA EE eae oe Sud emu uer s 63 In 6 Invoking the Analytic Solver 146 6 1 Command Line Option 6 3 Stop ping Criteria 6 4 Model Limit 7 Invoking the Simulator d1gsim 7 1 Command Line Option 7 2 Return Statu 7 4 Stopping Criteria 7 5 Model Limit 8 Error Messages 8 1 Fatal Error Messages 8 3 Advisory Message 8 5 Input File Parser Error Message 8 6 LOX Error message 9 Known Defect 92 Chain construction for models with multi and infinite servers 9 3 No algorithm for phased multiservers OPEN class 9 4 Overtaking probabilities are calculated using CV 1 9 5 Need to implement queue lengths for open classes A Traditional Gramma A 1 9 SPEX Convergence Informatio A 1 10 Expressions A 2 1 General Informatio A 2 2 Throughput Bound A 2 5 _Send No Reply Waiting Time A 2 8 Join Dela A 2 9 Service Time ROTE 52 Error Messages c es coco xeu Rok Bed S Gres 8
97. ine the requests from an activity to an entry and to connect the activity graph to the requesting entry Table 3 13 lists the parameters used as attributes and the attributes used by the three sub types Refer to Section A 1 7 for more in formation on these parameters Refer to MakingCallType 13 2 10 for the Act ivit y Cal1Group used to make requests to other 2 Refer to OutputResultForwardingANDJoinDelay 13 2 13 for result join delay and result forwarding for join delay and forwarding results respectively Refer to OutputDistributionType B 2 14 for service time distribtion Finally refer to OutputResultType 13 2 12 for result activity This element contains most of the results for an activity or phase a host demand mean float required The mean service time demand for __ host demand cvsq float optional The squared coefficient of varia c ss think tine mec a E call order enumeration optional aoa DETERMINISTIC ActivtyPhasesType phase _ rqa ActivtyEntryDefType Hstcactivity swing ActivtyDefType bound to entry string optional If set this activity is the start of an activity graph Table 3 13 Attributes for elements of type ActivityDefBase 3 2 10 MakingCallType The type MakingCallType shown in Figure B 7 is used to define the parameters for requests to entries This type is extended by ActivityMakingCallType a
98. ing example illustrates how values may be added to an array and how you can iterate over its contents and print it out The following snippet creates an array stores some key value pairs with different types of keys and values looks up a couple of them and then iterates over all of them Create an Array array arrayN create Store some key value pairs array 0 Slappy array 1 Skippy array 2 Jimmy Iterate over the names foreach index name in array print Chipmunk 4 index name Store variables of different types shorthand array true gt 1 0 false gt 3 0 one gt true three gt false 43 N Shorthand indexed creation with iteration x foreach value in 1 1 2 3 5 8 13 1 print Next fibonacci is value 4 1 3 Program Input Output and External Control The LQX language allows users to write formatted output to external files and standard output and to read input data from external files pipes and standard input These features may be combined to allow LQNX to be controlled by a parent process as a child process providing model solving functionality These capabilities will be described in the following sections File Handles The LQX language allows users to open files for program input and output Handles to these open files are stored in the symbol table for use by the print functions for file output and the read_data function for data i
99. instance of the Array class where the first argument to the constructor is used as the key and the second is used as the value and so on The result is a n array arg0 gt argl arg2 arg3 Summary of Methods ref lt gt boolean 4 2 2 Built in Global Methods and Constants Intrinsic Constants Summary of Constants double double double double double double array set object Array a key value array get object Array a key array has object Array a key infinity type_un type_boolean type _double type_string type_null 48 This method sets the value value of any type for the key key of any type for array a The shorthand nota tion for this operation is to use the operator This method obtains a reference to the slot in the array a for the key key If there is no value defined in the array yet for the given key a new slot is created for that key assigned to NULL and a reference returned Returns whether or not there is a value defined on array a for the given key key IEEE floating point numeric infinity The type id for an Undefined Variable The type_id for a Boolean Variable The type_id for a Numeric Variable The type id for a String Variable The type id for a Null Variable General Utility Functions Summary of Methods abort numeric n string This call will immediately halt the flow of the program r with failure code n and description string
100. ion gt expression expression expression term expression term term power term power term power Modulus power prefix power Exponentiation right associative prefix factor Logical NOT factor expression identifier expression list variable expression_list 1 variable expression expression Yo Non negative integer Non negative double precision number permitted The following p1 and _P_21_proc are valid identifiers while 21 and proc are not A 1 12 Variables SPEX variables all start with a dollar sign followed by any number of characters numbers or underscores _ The following 551 1 and _x are all valid variables SPEX variables are treated as global symbols by the underly ing program Variables used to store arrays will also generate local variable of the same name except without the leading dollar sign 95 2 Output File Grammar LQN output file from entry to entry entry_name task_name float_phase_list real 25 t 44 general bound p waiting p wait var o snr_waiting snr_wait_var drop prob ops join service variance p lt exceeded gt opt lt distribution gt o thpt ut open arrivals p processor opt entry_nam
101. ion 2 1 2 starting on page 13 The section headings here correspond to the section headings in the output file 11 Iqsim SEI SE3 SEG 4e 06 6 06 8e 06 Entry demand 127 21 7 97 2 Server 5 2 0 0016 0 189 Task multiplicity Queueing delay SEI w 0 0 1 lt Request rate to processor 7777 gt SE3 w 0 0 67 3 8Be 10 SE6 w 0 0511 Queueing delay Entry service time ShoppingCart inf Task throughput 2 A 0 000135 u 0 0268 and utilization 95 2 06 Branch probability Activity demand Activity service time AFBAII2 1 4 06 Join delay AJAISI 2e 06 0 0256 ID D 3 83b 10 5 SCE3A95 w 0 0258 OFBA97 wz0 0811 3 79 7 52 7 CustAccMgr A 0 000359 u 0 0251 CEI 10 10 Catalogue inf 0 000263 0 0 00264 mere 131 w 0 0256 BA146 w 0 0255 OJA110 w 0 0255 CE CAMES w 0 0491 CAME2 w 0 0491 Processor utilization Figure 2 1 Results 12 2 11 Analytic Solver 14016 Figure 2 2 shows the header information output by the analytic solver The first line of the output shows the version of the solver and where it was run This information is often useful when reporting problems with the solver The lines labeled Input and Output are
102. ists as all of the branches associated with the activities in the join list must finish i e join before the activities in the subsequent post element can start The post element itself is referred to as a fork list Elements of PrecedenceType can be of one of five types SingleActivityListType Elements of this type have no attributes and a sequence of exactly one activity element of ActivityType ActivityListType Elements of this type have no attributes and a sequence one or more activity elements of ActivityType AndJoinListType Elements of this type have an optional quorum element and a sequence of one or more or more activity elements of ActivityType Table 3 15 show the attributes of AndJoinListType OrListType Elements of this type have no attributes and a sequence one or more activity elements of Activity OrType These elements specify an activity name and a branch probability Table 3 16 show the attributes of ActivityOrType ActivityLoopListType Elements of this type have one optional attribute and a sequence one or more activity elements of ActivityLoopType These elements specify an activity name and a loop count The optional attribute is used to specify the activity that is executed after all the loop branches complete Tables 3 17 and 3 18 show the attributes of Activity LoopListType and ActivityLoopType respectively name swing required quorum integer optional The number of branches which must complete for the
103. ivities c f and their relation ships to each other They are used by elements of both EntryType and TaskActivityGraph types Elements of the ActivityGraphBase consist of a sequence of one or more activity elements followed by a sequence of precedence elements Activity elements are used to store the demand for an activity and re quests to other servers through the ActivityDefType and optionally results through elements of ActivityDefType Precedence elements are defined by the PrecedenceType in Section 3 2 11 3 2 8 TaskActivityGraph Task Activity Graphs defined using elements of type TaskActivityGraph and shown in Figure B 6 used to specify the behaviour of a task using activities This type is almost the same as EntryActivityGraph except that the activity that replies to an entry must explicitly specify the entry for which the reply is being generated The actual activity graph is defined using elements of type ActivityGraphBase described in Section 3 2 7 The attributes for elements reply entry and reply activity are shown in Tables 3 11 and 12 respectively name string required The name of the entry for which the list of reply activity elements generate replies Table 3 11 Attributes of element 1 from Figure 30 d ActivityDefBase name string Activity MakingCallType host demand mean float 9 GraphBase host demand cvsq float dest string think t
104. k lists are on the right hand side of the gt operator in the old grammar and the post precedence expressions in the XML grammar This error will cause a loop in the activity graph Activity identifier previously used in a join The activity identifier has already been used as part of a join list Join lists are on the left hand side of the gt operator in the old grammar and are the pre precedence expressions in the XML grammar This error will cause a loop in the activity graph Activity identifier requests reply for entry identifier but none pending The simulator is trying to generate a reply from entry identifier but there are no messages queued at the entry This error usually means there is a logic error in the simulator An error occured while compiling the LOX program found in file filename syntax error was found in the LOX program found in the file filename Refer to earlier error messages A An error occured executing the LOX program found in file filename A error occured while executing the the LQX program found in the file filename Refer to earlier error messages Attribute attribute is missing from fype element The attribute named attribute for the t ype element is missing Attribute attribute is not declared for element element The attribute named attribute for element is not defined in the schema Cannot create processor processor for task task identifier Parasol co
105. l proc_total proc total_conf F kok ko k de oL proc group 7777 end list P nt proc task list proc_total task name proc_task_info proc entry info 1 end list task total opt opt ne priority multiplicity i integer Prio of task integer Number of task instances entry name proc entry info proc entry conf o utilization sched delay end list float phase list Scheduling delay integer real proc total conf Yo real proc total conf o list amp integer real 99 Bibliography 1 The Apache Software Foundation Xerces C Documentation 2 S C Bruell Balbo and P V Afshari Mean value analysis of mixed multiple class BCMP networks with load dependent service centers Performance Evaluation 4 4 241 260 1984 doi 10 1016 0166 5316 84 90010 5 3 Adrian E Conway Fast approximate solution of queueing networks with multi server chain dependent FCFS queues In Ramon Puigjaner and Dominique Potier editors Modeling Techniques and Tools for Computer Performance Evaluation pages 385 396 Plenum New York 1989 4 Edmundo de Souza e Silva and Richard R Muntz Approximate solutions for a class of non product form queueing network models Performance Evaluation 7 3 221 242 1987 001 10 1016 0166 5316 87 90042 3 5 Greg Fr
106. l 5 coefficient of variation 104 error command line incorrect comment LON components concurrency 4 conf 95 conf 99 confidence intervals confidence level constraint checking 38 contention delay conv val conv val Convergence SPEX convergence error failure test value value error convergence convergence value conway copyright count counters statistical customer cycle activity graph error call graph error detection cycle time entry task cycles cycles allow d LON pragma 655 deadlock debug 65 delay contention interprocessor delta wait demand 1 description 24 dest deterministic directed graph 5 disallow distribution exponential gamma Pareto service time driver duplicate identifier error parameter error 87 start activity error unique value error egrep 75 elapsed time element 105 activity Activity CallGroup async call Call List Group duplicate name error entry entry phase activities forwarding histogram bin 35 Iqn model overflow bin 35 plot control post post loop pragma pre precedence processor quorum reply activity reply element reply entry result activity result entry result forwarding 32 result general result join delay result processor result task run control service service time distribtion slot solver params 2
107. l gt lt opt grp gt i task id task id int fan in for replication o task id task id int fan out for replication l Each task definition within this section starts with a t and is is defined using the syntax shown in lines 2 and 3 of Listing 5A lt task id gt is an identifier which names the task lt sched gt is used to define the request distribution for reference tasks or the scheduling discipline for non reference tasks The scheduling and distribution code letters are shown in Table 5 3 Some disciplines are only supported by the simulator these are identified using T lt entry list gt is a list of idententifiers naming the entries of the task The optional opt pri is used to set the priority for the task provided that the processor running the task is scheduled using a priority discipline The optional lt opt think time gt specifies a think time for a reference task The optional lt opt mult gt specifies the number of copies of this task serving common queue Multiplicity is specified using the syntax shown Table 5 2 By default a single copy of a task is used for the model Finally the optional lt opt grp gt is used to identify the group that this task belongs to provided that the task s processor is using fair share scheduling Reference tasks customers Request Distribution r Poisson b Bursty u Uniform Non Reference tasks servers sched 7 Queueing Discipline
108. list activity list 5 3 SPEX Software Performance Experiment Driver SPEX the Software Performance ExPeriment driver was originally a Perl program used to generate and solve multiple layered queueing network models With version 5 of the solvers this functionality has been incorporated into the lgiolib and 1 libraries used by the simulator and analytic solver The primary benefit of this change is that analytic solutions can run faster for reasons described in 11 58 Key One argument a lt entry id gt lt real gt Arrival Rate A lt entry id gt lt activity id gt Start activity lt entry id gt lt int gt Entry priority One to three phase arguments s lt entry id gt real 1 Service Time The entry s entry id and mean service k a s s c lt entry id gt real 1 Coefficient of Variation The entry s entry id and value for f lt entry id gt int 1 Call Order STOCHASTIC or DETERMINISTIC M lt entry id gt real 1 Max Service Time Output probability that the service time re sult exceeds the lt real gt parameter per phase Arguments for a single phase H int lt entry id gt real real lt opt int gt Histogram An int phase followed by a range from real to real and an op tional lt int gt buckets Destination and one argument F lt entry id gt real 1 Forwarding Probability Source and Destination ent
109. ll the servers in the submodel If the derived population is infinite the submodel cannot be solved This error usually arises when open arrivals are accepted by infinite servers Destination entry dst identifier must be different from source entry src identifier This error occurs when src identifier and dst identifier specify the same entry Deterministic phase src identifier makes a non integral number of calls mn to entry dst identifier This error occurs when a deterministic phase or activity makes a non integral number of calls to some other entry Duplicate unique value declared for identity constraint of element task One or more activities are being bound to the same entry This is not allowed as an entry is only allowed to be bound to one activity Check all bound to entry attributes for all activities to ensure this constraint is being met Duplicate unique value declared for identity constraint of element qn model This error indicated that an element has a duplicate name the parser gives the line number to the start of the second instance of duplicate element The following elements must have unique name attributes but the uniqueness does not span elements Therefore a processor and task element can have the same name attribute but two processor elements cannot have the same name attribute The following elements must have a unique name attribute processor task entry Empty co
110. ls within angle brackets in Figure I 8 b denote the number of replicas Replication also introduces the notion of fan in and fan in denoted using the O n and I n labels on the request from t1 to t2 in Figure I 8 b Fan out represents the number of replicated servers that a client task calls Similarly fan in represents the number of replicated clients that call a server The product of the number of clients and the fan out to a server must be the same as the product of the number of servers and the fan in to the server Further both fan in and fan out must be integral and non zero The total number of requests that a client makes to a server is the product of the mean number of requests and the fan out If the performance of a system is being evaluated by varying the replication parameter of a server the number of requests to the server must be varied inversely with the number of server replicas in order to retain a constant number of requests from the client 1 0 673 1 0 673 2 0 673 0 673 0 699 10 699 a Flat b Replicated Figure 1 8 Replicated Model 1 3 A Brief History LQN 6 is a combination of Stochastic Rendezvous Networks and the Method of Layers 14 10 Chapter 2 Results Both the analytic solver and the simulator calculate throughput bounds Iqns only mean delay for rendezvous and send no reply requests variances for the rendezvous and send no reply request delays Iqsim only
111. m the simulator will be placed there with filenames based on the name of the input files processed Otherwise only one input file can be processed its output will be placed in output parseable Generate parseable output suitable as input to other programs such as MultiSRVN 1 and srvndiff 1 If input is from filename parseable output is directed to filename p If standard input is used for input then the parseable output is sent to the standard output device If the ooutput option is used the parseable output is sent to the file name output In this case only parseable output is emitted pragma pragma Change the default solution strategy Refer to the PRAGMAS chapter 17 3 below for more information raw statistics Print the values of the statistical counters to the monitor file If the A B or C option was used the mean value 95th and 99th percentile are reported At present statistics are gathered for the task and entry cycle time task processor and entry utilization and waiting time for messages seed seed Set the initial seed value for the random number generator By default the system time from time fime 3 is used The same seed value is used to initialize the random number generator for each file when multiple input files are specified trace raceopts This option is used to set tracing options which are used to print out various steps of the simulation while it is executing Traceopts is any c
112. mber of characters numbers or underscores var and 1 are valid variables while 15 not 5 2 LQN Model Specification This section describes the mandatory and option input for a basic LON model file SPEX information namely Vari ables 85 2 7 Report Information 5 3 2 and Convergence Information 5 3 3 are described in the section that follows input files are composed of three mandatory sections Processor Information 5 2 3 Task Information 15 2 5 and Entry Information 45 2 6 which define the processors tasks and entries respectively in the model of the other sections for a basic model file are optional They are Pragmas General Information 85 2 2 Group Information 5 2 4 and Activity Information The syntax of these specifications are described next in the order in which they appear in the input model 5 21 Pragmas Any line beginning with optional whitespace followed by the word pragma efines a pragma which is used by either the analytic solver or the simulator to change its behaviour The syntax for a pramga directive is shown in line 2 in Listing 5 1 Pragma s which are not handled by either the simulator or the analytic solver are ignored Pragma s can appear anywhere in the input fid though they typically appear first 5 2 2 General Information The optional general information section is used to set various control parameters for the analytic solver LONS These parameters with the exception of
113. nalysis This language allows a user to perform a wide range of different actions on a variety of different input sources and to subsequently solve the model and control the output of the resulting data 4 1 4 Input File Format The LQX programming language follows grammar rules which are very similar to those of ANSI and PHP The main difference between these languages and LQX is that LQX is a loosely typed language with strict runtime type checking and a lack of variable coercion type casting Additionally variables need not be declared before their first use They do however have to be initialized If they are un initialized prior to their first use the program will fail Comment Style supports two of the most common commenting syntaxes C style and C style Any time the scanner discovers two forward slashes side by side it skips any remaining text on that line until it reaches a newline These are C style comments The other rule that the scanner uses is that should it encounter a forward slash followed by an asterisk it will ignore any text it finds up until a terminating asterisk followed by a slash The preferred commenting style in programs is to use C style comments for single line comments and to use C style comments where they span multiple lines This is a matter of style Intrinsic Types There are 5 intrinsic types in the LOX programming langua
114. name of the parameter c EA TA value string required the value assigned to the pragma Table 3 4 Attributes of element pragma from Figure 25 3 2 2 ProcessorType Elements of type ProcessorType shown in Figure are used to define the processors in the model They contain an optional result processor element and elements of either GroupType or TaskType The scheduling attribute must by set to c s for completely fair scheduling if GroupType elements are present and to any other type if GroupType are not found GroupType and TaskType elements may not be both be defined in a processor Element result processoris of type OutputResultType and is described in Section 3 2 12 Element task is described in Section 3 2 4 The attributes of Processor Type described in A 1 3 are shown in Table ProcessorType name string speed factor float scheduling SchedulingType multiplicity unsigned replication unsigned quantum float processor ordered 0 2 2 X3 result processor GroupType name string cap boolean share float T f 2 group TaskType task Figure 3 3 Processor Schema scheduling enumeration optional fcfs The allowed scheduling types are fcfs hol pp rand inf ps hol ps pp and cfs See 41 1 1 See 7 quantum float optional Mandatory for processor sharing
115. nd EntryMakingCallType to defined requests from activities to entries and for forwarding requests from entry to entry respectively Requests from activities to entries can be either synchronous 1 a rendezvous through a sync ca11 element or asynchronous 1 a send no reply through a async call element Section 1 1 7 defines the parameters for a request TableB T lists the attributes for the types Default Comments dest string required The name of the entry to which the requests are made ActivityMakingCallType cal e mean required The mean number of requests EntryMakingCallType prob float required The probability of forwarding requests Table 3 14 Attributes for elements of type MakingCallType Call List Group is not defined at present MakingCallType dest string EntryMaking ActivityMaking ivi CallType entry CallType activity prob float calls mean float 0 unorde ed forwarding 0 0 synch call asynch call Figure 3 7 Schema diagram for the group MakingCallType 3 2 11 PrecedenceType The type PrecedenceType shown in Figure is used to connect one activity to another within an activity graph Each element of this type contains exactly one pre element and optionally one post element The pre elements are referred to as join l
116. ng time to entry SCE3 0 the phase one service time at entry SCE3 11 6 the queueing time to entry CE1 3 83 x 10719 and the phase one service time at entry 1 10 Queueing time for serving tasks is shown in the Mean Delay for a Rendezvous section of the output c f 2 3 Queueing time for the processor is shown in the Utilization and Waiting per Phase for Processor of the output c f 42 16 2 10 Service Time Variance The Service Time Variance section lists the variance of the service time c f for the phases and activities in the model 2 11 Probability Maximum Service Time Exceeded Iqsim The probability maximum service time exceeded is output by the simulator for all phases and activities withamax service time This result is the probability that the service time is greater than the value specified In effect it is a histogram with two bins 17 2 12 Service Time Distributions for Entries and Activities Service Time Distributions are generated by the simulator by setting the service time distribution param eter c f for an entry or activity histogram of number bins bins between min and max is generated Samples that fall either under or over this range are stored in their own under flow or over flow bins respectively The optional x samples parameter be used to set the sampling behaviour to one of linear Each bin is of equal width found by dividing the histogram range by the number of bins
117. nput Files may be opened for writing appending or for reading The LQX interpreter keeps track of which file handles were opened for writing and which were opened for reading The following command opens a file for writing If it exists it is overwritten It is also possible to append to an existing file The three options for the third parameter are write append and read file_open output_filel test_output_99 peva txt write To close an open file handle the following command is used file_close output _filel File Output Program output to both files and standard output is possible with the print functions If the first parameter to the functions is an existing file handle opened for writing output is directed to that file If the first parameter is not a file handle output is sent to standard output Standard output is useful when it is desired to control LQNX execution from a parent process using pipes If the given file handle has been opened for reading instead of writing a runtime error results There are four variations of print commands with two options One option is a newline at the end of the line It is possible to specify additional newlines with the end1 parameter The second option is controlling the spacing between columns either by specifying column widths in integers or supplying a text string to be placed between columns The basic print functions are print and println with the 1n specifying a newline at the
118. nt types of keys will reference different entries That is to say that integer Oandstring 0 will not yield the same value from the Array when used as a key The Array object exposes a couple of convenience APIs as detailed in Section 4 2 These methods are simply short hand notation for the full function calls they replace and provide no additional functionality Arrays may be created in three different ways e array_create andarray create map key value The explicit but long and wordy way of creating an array of objects or a map is by using the standard functional array create takes an arbitrary number of parameters from 0 up to the maximum specified for all practical purposes infinity and returns a new Array instance consisting of 02 argl 1 gt 2 2 gt arg3 The other function array create map key value takes an even number of arguments from 0 to 2n The first argument is used as the key and the second argument used as the value for that key and so on The resulting Array instance consists of argl gt arg2 arg3 arg4 Bothofthese methods are documented in Section e arg1 arg2 Shorthand notation for array_create e gt 1 k2 gt v2 Shorthand notation for array_create_map The LQX language supports two different methods of iterating over the contents of an Array The first involves knowing what the keys in the array actually are This is a tradi
119. nt the message However entries may also forward the reply The next entry which accepts the forwarded reply may forward the message in turn or may reply back to the originating client For example in Figure entry IME8 on task IventoryMgr forwards the request from entry BME on task BackorderMgr to entry CAMES on task CustAccMgr The reply from CAME will be sent directly back to BME2 The parameters for an entry can be specified using either phases or The activity method is typically used when a task has complex internal behaviour such as forks and joins or if its behaviour is specified as an activity graph such as those used by Smith and Williams 18 The phase method is simply a short hand notation for specifying a sequence of one to three activities with the reply being generated by the first activity in the sequence Figure shows both methods for specifying a two phase client calling a two phase server Regardless of the specification method used for an entry its behaviour as a server to its clients is by phase shown in Figure Phases consume time on processors and make requests to entries Phase one is a service phase and is similar to the service given by a station in a queueing network Phase one ends after the server sends a reply Subsequent phases are autonomous phases which are launched by phase one These phases operate in parallel with the clients which initiated them The simulator an
120. ntent not valid for content model element result processor task Entry identifier accepts both rendezvous and send no reply messages An entry can either accept synchronous messages to which it generates replies or asynchronous messages to which no reply is needed but not both Send the requests to two separate entries Entry identifier has invalid forwarding probability of nn This error occurs when the sum of all forwarding probabilities from the entry identifier is greater than 1 Entry entry identifier is not part of task task identifier An activity graph part of task task identifer replies to entry identifier However entry identifier belongs to another task Entry identifier is not specified Anentry is declared but not defined either using phases or activities An entry is defined when some parameter such as service time is specified Entry identifier must reply the reply is not specified in the activity graph The entry identifier accepts rendezvous requests However no reply is specified in the activity graph Entry identifier specified using both activity and phase methods Entries can be specified either using phases or using activities but not both 81 Entry identifier specified as both a signal and wait A semaphore task must have exactly one signal and one wait entry Both entries have the same type Expected end of tag element The closing tag for elem
121. number of bins in the distribution mia poine How bin size optional Table 3 21 Attributes for elements of type OutputDistribution Type segin How Lower limit ofthe bin Pend Upperlimitofihebin prob float The probability that the measured value lies sont 95 Wo 17 cont ss feu j Table 3 22 Attributes for elements of type HistogramBinType 37 entries must have a unique name All activities must have a unique name within a given task All synchronous requests must have a valid destination All asynchronous requests must have a valid destination All forwarding requests must have a valid destination All activity connections in precedence blocks must refer to valid activities All activity replies must refer to a valid entry All activity loops must refer to a valid activities Each entry has only one activity bound to it e Phases are restricted to values one through three e All phase attributes within an entry must be unique Further validation is performed by the solver itself Refer to Section 8 for the error messages generated One downside of using the Xerces XML parser library is that the Xerces tends to give rather cryptic error messages when compared to other tools If an XML file fails to pass the validation phase and the error looks cryptic chances are ve
122. o fib n minus two fib n minus one fib n minus one fib n println Currently fib n As you see this language is extremely similar to or PHP One of the few differences as far as expressions concerned is that pre increment decrement and post increment decrement are not supported Neither are short form expressions such as ete Re using Code Sections Many times there will be code in your LQX programs that you would like to invoke in many places varying only the parameters The LQX programming language does provide a pretty standard functions system as described earlier Bearing in mind the caveats some degree of overhead in function calls plus the inability to see global variables without having them passed in we can make pretty ingenious use of user defined functions within LQX code When defining functions you can specify only the number of arguments not their types so you need to make sure things are what you expect them to be or your code may not perform as you expect We will begin by demonstrating a substantially shorter but as described earlier much less efficient implementation of the Fibonacci Sequence using functions and recursion function fib n if 0 1 return 1 return fib n 2 fib n 1 Once defined a function may be used anywhere in your code even in other user defined functions and itself recursively This particular example f
123. ocedure l requests may jump over layers such as the request from the Administrator task to the InventoryMgr task 051 Administrator AdminProc inf CustProc inf AdmitiICust Proc x Forwarded request Asynchronous request Synchronous request Layer 6 0 0844 6915 T 0 000422 BME2 SEI SE3 SEG 3e 06 4e 06 6 06 8e 06 T T Y BackorderMgr Server 5 1 L Y 1 SCE3 ShoppingCart inf SCE3A95 2e 06 0 one OFBA97 1 112 n 4e 06 OJA110 AFBA130 AFBA133 2e 06 1 AJA131 2e 06 0 5 10 1 j x z E x Y IME7 IME6 IMEI IME8 5 CAME2 3e 06 5 2 2 3 10 CustAccMgr Catalogue inf BookstoreProc Figure 1 1 Notation Layer 1 Layer 4 20 x CADE4 CADE5 150 100 191 Database 3 DatabaseProc L DatabaseProc calls RPCs or rendezvous and the model captures these delays by incorporating the lower layer queueing and service into the service time of the upper layer server This active server feature is the key difference between layered and ordinary queueing networks 11 Model Elements Figure shows the meta model used to describe Layered Queueing Networks This mod
124. of tasks t decl end list t task_id task_sched_type entry list queue length proc id task_pri think_time flag p multi server flag replication flag group flag i from task to_task fan in o from task to_task fan out opt integer identifier task identifier reference task non reference task Head of line FIFO Scheduling Infinite or delay server Polled scheduling at entries Bursty Reference task Semaphore HoT Fe ph P P RK 92 entry list entry id queue_length task_pri group flag from task to task fan in fan out l Se AS 2 entry_id end_list integer identifier q integer integer g identfier task_id task_id integer integer A 1 6 Entry Information entry info ne entry decl list entry decl arrival_rate coeff of variation from entry hist bins hist max hist min hist type max_service_time p forward phase ph type flag rate rendezvous TE ttf 4 b j 4 E ne entry decl list integer entry_decl end list real variable real variable entry id integer real real log linear sqrt real real 1 2 3 0 il real variable real variable 93
125. ollowing println_spaced command specifies the integer 12 as the column width println spaced output file3 12 Spl Sp2 Syl 5 2 tl throughput Reading Input Data from Files Pipes Reading data from input files pipes is done with the read_data function Data can either be read from a valid file handle that has been opened for reading or from standard input Reading data from standard input is useful when is useful when it is desired to control LONX execution from a parent process using pipes If the given file handle has been opened for writing rather than reading a runtime error results The first parameter is either a valid file handle for reading or the strings stdout or specifying standard input The data that can be read can be either numerical values or boolean values There are two forms in which the read data function can be used The first is by specifying a list of LOX variables which correspond to the expected inputs from the file pipe This requires the data inputs from the pipe to be in the expected order read data input file y p keep running The second form in which the read data function can be used is much more robust It can go into a loop attempting to read string value pairs from the input pipe until a termination string STOP READ is encountered The string must corespond to an existing LQX variable either numeric or boolean and the corresponding value must be of the same type read data stdin r
126. ombination of the following driver Print out the underlying tracing information from the Parasol simulation engine processor regex Trace activity for processors whose name match regex If regexis not specified activity on all processors is reported Regex is regular expression of the type accepted by egrep 1 task regex Trace activity for tasks whose name match regex If regex is not specified activity on all tasks is reported pattern is regular expression of the type accepted by egrep 1 75 eventsregex regex Display only events matching pattern The events msg async msg send msg receive msg reply msg done msg abort msg forward worker dispatch worker idle task created task ready task running task computing task waiting thread start thread enqueue thread dequeue thread idle thread create thread reap thread stop activity start activity execute activity fork and activity join msgbuf Show msgbuf allocation and deallocation timeline Generate events for the timeline tool T run time run time Set the run time for the simulation The default is 10 000 units Specifying T after either A or B changes the simulation block size but does not turn off blocked statistics collection v verbose Print out statistics about the solution on the standard output device V version Print out version and copyright information w no warnings Ignore warnings The default is to print out all warning
127. ons A Task activity definitions optional R SPEX result definitions optional C SPEX convergence optional Section 5 2 describes the input sections necessary to solve a model i e P U T E and A Section 5 3 describes the additional input sections for solving multiple models using SPEX i e R and C The complete input grammar is listed in Appendix A 5 1 Lexical Conventions The section describes the lexical conventions of the SRVN input file format 5 1 1 White Space White space such as spaces tabs and new lines is ignored except within strings Object definitions can span multiple lines 53 21 22 23 24 25 40 41 43 44 45 46 47 48 49 50 Listing 5 1 file layout Pragmas pragma lt param gt lt value gt Parameters SPEX Svar lt expression gt Svar lt expression list gt General Information lt string gt real int int real 1 Processor definitions 0 lt proc id gt sched lt opt mult gt opt repl opt obs 1 Group definitions U 0 g lt group id gt lt real gt lt opt cap gt lt proc id gt 1 Task definitions t task id sched entry list 1 proc id opt pri opt think time opt mult opt repl lt gt opt obs 1 Entry definitions E 0 activity id entry id real 1 opt obs y lt entry id gt
128. ority for all tasks is zero 1 1 2 Groups Groups 9 are used to divide up a processor s execution time up into shares The tasks within a group divide the share up among themselves evenly Groups can only be created on processors running the scheduling discipline completely fair scheduling Shares may either be guaranteed or capped Guarantee shares act as a floor for the share that a group receives If surplus CPU time is available i e the processor is not fully utilized tasks in a guaranteed group can exceed their share Cap shares act as a hard ceiling Tasks within these groups will never receive more than their share of CPU time Note Completely fair scheduling is a form of priority scheduling With layered models calls made by tasks within groups to lower level servers can cause priority inversion Cap scheduling tends to behave better than guaranteed scheduling for these cases 1 1 3 Tasks Tasks are used in layered queueing networks to represent resources Resources include but are not limited to actual tasks or processes in a computer system customers buffers and hardware devices In essence whenever some entity requires some sort of service requests between tasks involved A task has a queue for requests and runs on a processor Items are served from the queue in a first come first served manner Different classes of service are specified using entries c f 1 1 4 Tasks may also have internal concurrency specified
129. ovided a boolean of true or false respectively It will re turn the passed value for a double 0 0 for a null and fail NULL for an object If it was passed a string it will attempt to convert it to a double If the whole string was not numeric it will return NULL otherwise it will return the decoded numeric value This method will return t rue for a numeric value of not 0 0 a boolean true or a string true or yes It will return false for a numeric value 0 0 a NULL or a string false or no or a boolean false It will return NULL otherwise numeric double x boolean 49 4 3 API Documentation for the LQN Bindings 4 3 1 LQN Class Document double iterations number of solver iterations simulation blocks double invocation The solution invocation number double system cpu time Total system time for this invocation double user cpu time Total user time for this invocation double elapsed time Total elapsed time for this invocation boolean valid True if the results are valid Summary of Constructors document Returns the Document object 4 3 2 LQN Class Processor Summary of Attributes Pdouble utilization TheutHzation of the Processor Summary of Constructors Processor processor string name Returns an instance of Processor from the current LQN model with the given name 4 3 3 LQN Class Group Summary of Attributes doble i utilization Theulllzation o
130. pr OutputDistributionType pragma OutputResultForwardingANDJoinDelay invalid OutputResultJoinDelayType command line OutputResultType input file over relaxation pragma 24 overflow 66 71 75 77 pre B3 overflow bin B5 pre precedence 8 overlap calculation error 80 overtaking precedence Markov activity I Method of Layers and fork overtaking 65 67 70 and join 8 loop param or fork 8 parameter or join LQN quourm join Parasol sequence 8 error precedence Pareto distribution PrecedenceType Performance Model Interchange Format precision Perl simulation SPEX primary document phase 1 5 6 error 21 88 asynchronous print autonomous print interval deterministic lqns error print interval 67 76 maximum 78 print int D5 reply prioity reschedule premptive resume results priority second entry service time error type 78 93 94 head of line 4 70 phase 30 32 highest 4 phases inversion approximation preemptive resume error preemptive resume phaseX proc waiting 36 processor 4 phaseX service time 36 priority 28l 30 110 prob B2 B4l B7 prob exceed max servic probability branch error forwarding proc utilization proc waiting processor creation error maximum not used error priority queueing rate error scheduling completely fair custom natural sharing sharing al error
131. programming language has support for user defined functions When defined in the language functions do not check their arguments types so every effort must be taken to ensure that arguments are the type that you expect them to be The number of arguments will be checked Variable length argument lists are also supported with the use of the ellipsis notation Any arguments given that fall into the ellipsis are converted into an array named va_list in the functions scope This is a regular instance of Array consisting of 0 or more items and can be operated on using any of the standard operators User defined functions do not have access to any variables except their arguments and External prefixed and Constant prefixed variables Any additional variables must be passed in as arguments and all values must be returned All arguments are in only There are no out or inout arguments supported All arguments are copied pass by value The basic syntax for declaring functions is as follows function lt name gt lt argl gt lt arg2 gt lt body gt return value You can return a value from a function anywhere in the body using the return function A function which reaches the end of its body without call to return will automatically return NULL return is a function not a language construct and as such the brackets are required The number of arguments is not limited so long as each one has a unique name there a
132. r This can not be caught any way by the program and will result in the interpreter not executing any more of the program copyright Displays the LQX copyright message print symbol table This is a very useful debugging tool which output the name and value of all variables in the current inter preter scope print_special_table This is also a useful debugging tool which outputs the name and value of all special External and Constant variables in the interpreter scope numeric type id any This method returns the Type ID of any variable in cluding intrinsic types numeric boolean null etc and the result can be matched to the constants prefixed with type type_null type_un type_double etc return any This method will return any value from a user defined function This method cannot be used in global scope Numeric Floating Point Utility Functions Summary of Methods numeric abs numeric n Returns the absolute value of the argument n numeric ceil numeric n Returns the value of n rounded up numeric floor numeric n Returns the value of n rounded down numeric pow numeric bas numeric Returns bas to the power x x Type casting Functions Summary of Methods string Es This method will return the same value as the function print would have displayed on the screen Each argument is coerced to a string and then adjacent values are concatenated This method will return 1 0 or 0 0 if pr
133. r the named task or processor The multiplicity attribute is ignored sched scheduling specified for processor task identifier is not supported The solver does not support the specified scheduling type First in first out scheduling will be used instead Activity identifier has no service time specified No service time is specified for identifier Coefficient of variation is incompatible with phase type at entry task identifier phase activity identifier Iqns A coefficient of variation is specified at a using stochastic phase or activity 3 Values of under relaxation from 1 lt n lt 2 are more correctly called over relaxation 86 Entry identifier does not receive any requests Entry identifier is part of a non reference task However no requests are made to this entry Entry identifier has no service time specified for any phase No service time is specified for entry identifier Entry identifier has no service time specified for phasen No service time is specified for entry identifier phase n Histogram requested for entry identifier phase n phase is not present A histogram for the service time of phase n of entry identifier was requested This entry has no corresponding phase Priority specified is outside of range n n Value has been adjusted to n The priority n is outside of the range specified No quantum specified for PS scheduling discipline
134. ragma is used to control the operation of the solver when the arrival rate exceeds the service rate of a server The simulator can either discard the arrival or it can halt The meanings of bool are false Ignore queue overflows for open arrivals and send no reply requests If a queue overflows its waiting times is reported as infinite true Stop if messages are lost reschedule on async send bool In models with send no reply messages the simulator does not reschedule the processor after an asynchronous message is sent unlike the case with synchronous messages The meanings of bool are true reschedule after each asynchronous message false reschedule after each asynchronous message 7 4 Stopping Criteria It is important that the length of the simulation be chosen properly Results may be inaccurate if the simulation run is too short Simulations that run too long waste time and resources Lqsim uses batch means or the method of samples to generate confidence intervals With automatic blocking the confidence intervals are computed after the simulations runs for three blocks plus the initial skip period If the root or the mean of the squares of the confidence intervals for the entry service times is within the specified precision the simulation stops Otherwise the simulation runs for another block and repeats the test With manual blocking lqsim runs the number of blocks specified then stops In either case the simulator will stop a
135. re no other constraints 41 2 Writing Programs in LQX Hello World Program A good place to start learning how to write programs in LQX is of course the traditional Hello World program This would actually be a single line and is not particularly interesting This would be as follows 41 N printin Hello World The print1n function takes an arbitrary number of arguments of any type and will output them barring a file handle as the first parameter to standard output followed by a newline Fibonacci Sequence This particular program is a great example of how to perform flow control using the LQX programming language The Fibonacci sequence is an extremely simple infinite sequence which is defined as the following piecewise function 1 0 1 fib z 1 fib a 2 otherwise Thus we can see that the Fibonacci sequence is defined as a recursive sequence The naive approach would be to write this code as a recursive function However this is extremely inefficient as the overhead of even simple recursion in LQX can be substantial The best way is to roll the algorithm into into a loop of some type In this case the loop is terminated when we have reached a target number in the Fibonacci sequence 1 1 2 3 5 8 13 21 4 1 Initial Values fib_n_minus_two 1 fib_n_minus_one 1 fib_n 0 Loop until we reach 21 x while fib n 21 fib n fib n minus one fib n minus tw
136. red value integer required Gee Table 3 9 Attributes for elements of type FanOutType 28 MakingCallType EntryType dest string fanout unsigned name string open arrival rate float Figure 3 5 Schema for type EntryType 29 inai priority integer fanin unsigned semaphore SemaphoreType 2 Activity type enumeration ActivityDefBase GraphBase name string host demand mean float EntryMaking host demand cvsq float CallType think time float EntryActivity ent Phase max service time float Graph prob float y Activities call order CallOrderType rap 0 2 0 1 0 1 E ivi try activity result ent forwardin entry phase Activity 3 a activities PhasesType graph phase 1 3 ActivityMaking 5 7 CallType 1 3 1 0 0 ealismoan float activity activity precedence reply entry unordered 0 0 synch call asynch call phiph2 The entry is specified using phases The phases specified using an entry phase activities element which is of the ActivityPhasesType type Activities defined within this element must have a unique phase attribute graph The entry is specified as an ac
137. rformance model and are linked together in a directed graph to indicate precedence When a request arrives at an entry it triggers the first activity of the activity graph Subsequent activities may follow sequentially or may fork into multiple paths which later join The fork may take the form of an AND which means that all the activities on the branch after the fork can run in parallel or in the form of an which chooses one of the branches with a specified probability In Figure a request that is received by entry SCE3 of task ShoppingCart is processed using an activity called SCE3A95 that represents the main thread of control then the main thread is OR Forked into two branches one of which is later AND forked into three threads The three threads starting with activities 109 AFBA 130 and AFBA133 respectively run in parallel The first thread replies to the entry through activity OJA110 then ends The remaining two threads join into one thread at activity 131 When both OJA110 and AJA131 terminate the task can accept a new request The holding time for one class of service is the entry service time which is not a constant parameter but is determined by its lower servers Thus the essence of layered queuing is a form of simultaneous resource possession In software systems delays and congestion are heavily influenced by synchronous interactions such as remote pr
138. ries and proba bility reply is forwarded Destination and one to three phase arguments y lt entry id gt lt entry id gt real 1 Rendevous Rate Source and Destination entries and rate per phase ecl z lt entry id gt lt entry id gt real Send no Reply Rate Source and Destination entries and rate per phase Semaphores and Lockst P lt entry id gt Signal Entry lt entry id gt is used to signal a semaphore task gt U lt entry id gt Read unlock 000000000000 W lt entry id gt Write lockt X lt eniry id gt Table 5 5 Entry Specifiers one to three phase arguments The entry s lt entry id gt and mean service time value per phase Coefficient of Variation Squared entry s lt entry id gt and value for each phase Call Order STOCHASTIC or DETERMINISTIC Destination and one to three phase arguments Rendevous Rate Source and Destination entries and rate per phase Send no Reply Rate Source and Destination entries and rate per phase Table 5 6 Activity Specifiers 59 Post or Join lists lt activity id gt lt actvityid gt lt actvin d gt p E lt activity id gt amp lt activity id gt amp Pre or Fork lists activity id lt activin id gt p sasi p SS lt activity id gt amp lt activity id gt 62 Table 5 7 Activity Lists Control Variable Type of Value
139. rom the current string name LQN model whose name corresponds to an activ ity in the given task 4 3 8 LQN Class Call Summary of Attributes double waiting Call waiting time double waiting variance Call waiting time double loss probability Message loss probability for asynchronous mes sages Summary of Constructors Call call object phase string Returns the call from an entry s phase phase to destinationEntry the destination entry whose name is dest 4 3 9 Confidence Intervals Summary of Constructors conf int object int level Returns the level for the attribute for the object 52 Chapter 5 LQN Input File Format This Chapter describes the original SRVN input file format augmented with the Software Performance EXperiment driver SPEX grammar In this model format models are specified breadth first in contrast to the XML format described B where models are specified depth first This specification means that all resources such as processors tasks and entries are defined before they are referenced Furthermore each resource is grouped into its own section in the input file Listing 5 the basic layout of the model Each of the sections within the input file begins with a key letter as follows SPEX parameters optional G General solver parameters optional P Processor definitions U Processor group definitions optional T Task definitions E Entry definiti
140. rt 1 Failed to solve the model else The remainder of the program outputs a small table of results for certain key values of interest to the person running the solution using the APIs in Section 3 tO task t0 pO processor p0 0 entry e0 phl phase e0 1 ctoel call phl el println my s println tO Throughput tO throughput println tO Utilization tO utilization Jos Prime lo 2 println eO Throughput eO throughput println eO Bound eO throughput bound println eO Utilization eO utilization yos 47 println f _ 2 printin ph Utilization phl utilization printin ph Svt Variance phl service time variance println ph Service Time phl service time println ph Proc Waiting phl proc waiting Due printin qty println call Wait Time ctoel wait time gt printin 4 0 API Documentation 4 2 1 Built in Class Array Summary of Attributes numere size The number of key value pairs stored in the array Summary of Constructors object Array object Array array create _ This method returns a new instance of Array class where each the first argument to the method is mapped to index numeric 0 the second one to numeric 1 and so on yielding 0O gt arg0 1 gt argl This method returns a new
141. ry good that there is a genuine problem with the XML input file Xerces has a bad habit of coming back with cryptic errors when constraint checking fails and only gives you the general area in the file where the actual problem is One easy and convenient solution around this problem is to validate the XML file using another XML tool Tools that have been found to give more user friendly feedback are XMLSpy any edition and XSDvalid Java based freely available Another solution is to check if a particular tool can de activate schema validation and rely on the actual tool to do its own internal error checking Currently this is not supported in any of the LQN tools which are XML enabled but it maybe implemented later on If the XML file validates using other tools but fails validation with Xerces or if the XML file fails validation on other tools but passes with Xerces then please report the problem The likelihood of validation passing with Xerces and not other tools will be much higher then the reverse scenario because Xerces does not rigorously apply the XML Schema standard as other tools Other sources of problems could be errors in the XML schema itself or some unknown bug in the Xerces library 38 Chapter 4 LQX Users Guide 41 Introduction to LQX The LQX programming language is a general purpose programming language used for the control of input parameters to the Layer Queueing Network Solversystem for the purposes of sensitivity a
142. s x xml Generate XML output regardless of input format zspecialopts This flag is used to select special options Arguments of the form n are integers while arguments of the form n n are real numbers Specialopts is any combination of the following print interval nn Set the printing interval to n Results are printed after nn blocks have run The default value is 10 global delay n n Set the interprocessor delay to nn n for all tasks Delays specified the input file will override the global value global delay Set the inter processor communication delay to n n print interval Ouptut results after n iterations restart Re run the LQX program without re solving the models unless a valid solution does not exist This option is useful if print statements are changed or if a subset of simulations has to be re run debug lqx Output debugging informtion as an LQX program is being parsed debug xml Output XML elements and attributes as they are being parsed Since the XML parser usually stops when it encounters an error this option can be used to localize the error 7 2 Return Status Lqsim exits 0 on success 1 if the simulation failed to meet the convergence criteria 2 if the input was invalid 4 if a command line argument was incorrect 8 for file read write problems and 1 for fatal errors If multiple input files are being processed the exit code is the bit wise OR of the above conditions 76 7
143. s The distribution of requests to lower level servers is set by the call order for the activity which is either stochastic or deterministic If the call order is deterministic the activity makes the exact number of requests specified to the lower level servers The number of requests is integral the order of requests to different entries is not defined If the call order is stochastic the activity makes a random number of requests to the lower level servers The mean number of requests is specified by the value specified Requests are assumed to be geometrically distributed For entries which accept rendezvous requests replies must be generated If the entry is specified using phases the reply is implicit after phase one However if the entry is specified using activities one or more of the activities must explicitly generate the reply Exactly one reply must be generated for each request Slices Activities consume time by making requests to the processor associated with the task The service time demand specified for an activity is divided into slices between requests to other entries shown in the UML Sequence Diagram in Figure 1 5 The mean number of slices is always 1 Y where Y is total total number of requests made by the activity sd Slices J client Activity server Entry server Processor T 1 i compute loop ly lt send gt Slice
144. scheduling when us ing 1451 Table 3 5 Attributes for elements of type ProcessorType 26 3 2 3 GroupType Optional elements of type GroupType shown Figure 3 3 are used to define groups of tasks for processors running completely fair scheduling Each group must contain a minimum of one task The attributes of GroupType are shown in Table name string reged share float required The fraction of the processor allocated to this fav all iene E dan cap boolean optional false If true shares are caps ceilings Otherwise Table 3 6 Attributes for elements of type GroupType 3 2 4 TaskType Elements of type TaskType shown in Figure are used to define the tasks in the model These elements contain an optional result task element one or more elements of and optionally elements of service task activities Element result task is of type OutputResultType is described in Section 3 2 12 Element ent ry is described in Section 3 2 6 The attributes of TaskType described in Section A 1 5 are shown in Table TaskType name string multiplicity unsigned replication unsigned scheduling SchedulingType think time float priority unsigned queue length unsigned activity graph bool intially unsigned FaninType FanOutType source string dest string x value unsigned value unsigned EntryType task TaskActivityGraph
145. square round robin 4 run time simulation run control 24 run time scheduling 78 cfs completely fair error 83 delay error fair share FCFS fifo head of line head of line 56 priority processor processor sharing random round robin semaphore task scheduling schedul ing 26l schema constraints 35 error schmidt schweitzer seed semaphore counting 5 service time signal 93 utilization wait semaphore task error sempahore send no reply 1 9 delay 15 error loss probability overflow 71 variance 15 server active infinite pure 3 synchronize 8 task error 87 service class request 1 service service time 5 11 16117 18 B2 36 871 93 P4 97 demand 77 distribution distributions entry error 86 exceeded 98 histogram 35 kurtosis maximum 93 maximum exceeded 17 112 phase 15 probability exceeded skew standard deviation variance service time 36 service time distribtion 32 service time distribution l service time variance 36 severity level 71 share cap exceed 4 guarantee 4 27 share signal simple simulation block statistics single step SingleActivityListType skip skip period 74 skip layer slice slot 24 solution statistics solve implicit solver info 25 solver params 24 source special
146. st from previous solution run This option is useful if LQX print statements are changed debug lqx Output debugging informtion as an LQX program is being parsed debug xml Output XML elements and attributes as they are being parsed Since the XML parser usually stops when it encounters an error this option can be used to localize the error 68 debug srvn Lqns exits with 0 on success 1 if the model failed to converge 2 if the input was invalid 4 if a command line argument was incorrect 8 for file read write problems and 1 for fatal errors If multiple input files are being processed the exit code is the bit wise OR of the above conditions 6 2 Pragmas Pragmas are used to alter the behaviour of the solver in a variety of ways They can be specified in the input file with on the command line with the P option or through the environment variable LONS PRAGMAS Command line specification of pragmas overrides those defined in the environment variable which in turn override those defined in the input file The following pragmas are supported Invalid pragma specification at the command line will stop the solver Invalid pragmas defined in the environment variable or in the input file are ignored as they might be used by other solvers cycles arg This pragma is used to enable or disable cycle detection in the call graph Cycles may indicate the presence of deadlocks Arg must be one of allow Allow cycles in
147. started by a fork must terminate before the task will accept a new message i e there is an implied join collecting all threads at the end of a task s cycle Branches to an AND join do not necessarily have to originate from a fork for this case each branch must originate from a unique entry This case is used to synchronize two or more clients at the server For OR forks the sum of the probabilities of the branches must sum to one there is no default operation AND forks may join at OR joins The threads from the AND fork implicitly join when the task cycle completes OR joins may be called directly from entries This case is analogous to running common code for different requests to a task LOOPS consist of one or more branches each of which is run a random number of times with the specified mean followed by an optional deterministic branch exit which is followed after all the looping has completed Replies can only occur from activities in pre precedence and join lists Activities cannot reply to entries from a loop branch because the number of times that a branch is executed is a random number 1 1 7 Requests Service requests from one task to another be one of three types rendezvous forwarded and send no reply shown in Figure A rendezvous request is a blocking synchronous request the client is suspended while the server processes the request A send no reply request is an asynchronous request the client continues
148. sts are generated in proportion to the service times of the entries Task task identifier with priority is running on processor processor identifier which does not have priority scheduling Processors running with FCFS scheduling ignore priorities 87 Number of processors tasks entries defined n does not match number specified m Iqsim lqsim Iqsim 1408 1418 8 5 Value specified for fanin fanout is invalid Iqns The value specified for a fan in or fan out is not valid and will be ignored The x feature is not supported in this version Feature x is not supported in this release Input File Parser Error Messages error not well formed invalid token This error occurs when an XML input file is expected but some other input file type was given Parse error An error was detected while processing the XML input file See the list below for more explantion The primary document entity could not be opened Id URI while parsing file name This error is generated by the Xerces when the Uniform resource indicator URI specified as the argument to the xsi noNamespaceSchemaLocat ion attribute of the Lqn mode1 element cannot be opened This argument must refer to a valid location containing the LQN schema files The key for identity constraint of element Ilgn model is not found When this message appears Xerces does not provide many hints on where the actual error occurs be cause i
149. t always gives a line number which points to the end of the file i e where the terminating tag l1qn model is In this case the following three points should be inspected to ensure validity of the model 1 All synchronous calls have a dest attribute which refers to a valid entry 2 All asynchronous calls have a dest attribute which refers to a valid entry 3 All forwarding calls have a dest attribute which refers to a valid entry If it is not practical to manually inspect the model run the XML file through another tool like XMLSpy or XSDvalid which will report more descriptive errors The key for identity constraint of element task is not found When this error appears it means there is something wrong within the task element indicated by the line number Check that The name attribute of all reply entry elements refers to a valid entry name which exists within the same task as the task activity graph All activities which contain the attribute bound to entry have a valid entry name that exists within the same task as the task activity graph The key for identity constraint of element task activities is not found When this error appears it means there is something wrong within the task activities element indicated by the line number Check that activities referenced within the precedence elements refer to activities which are defined for that particular task activity graph The name attribute of
150. t file Optional elements are shown using a multiplicity of zero for an association Note that results optional shown in blue are part of the schema 1 See the error message primary document entity could not be opened 88 21 20 21 22 23 Listing 3 1 XML file layout lqn model solver params lt pragma gt lt solver params gt lt processor gt lt task gt lt entry gt lt entry phase activities gt lt activity gt lt synch call gt lt asynch call gt lt activity gt lt activity gt lt activity gt entry phase activities entry entry entry lt task activities gt lt activity gt lt precedence gt lt task activities gt lt task gt lt task gt lt task gt lt processor gt lt processor gt lt processor gt lt lqn model gt 22 Iqn model ordered 0 1 0 1 1 0 7 0 1 run control plot control solver params processor
151. t nr 4 3 7 LQN Class Activity Summary of Attributes double proc utilization double proc waiting double service time variance double service time double Squared coeff variation double throughput double utilization Whether the entry has a phase 1 result Whether the entry has a phase 2 result Whether the entry has a phase 3 result Whether the entry has an open wait time Entry open wait time Phase 1 Processor Wait Time Phase 1 Service Time Variance Phase 1 Service Time Phase 1 task Utilization Phase 2 Processor Wait Time Phase 2 Service Time Variance Phase 2 Service Time Phase 2 task Utilization Phase 3 Processor Wait Time Phase 3 Service Time Variance Phase 3 Service Time Phase 3 task Utilization Entry processor utilization Squared coefficient of variation Entry throughput bound Entry throughput Entry utilization Returns the Entry object for the model entry whose name is given as name Phase service time Phase service time variance Phase utilization Phases processor waiting time Returns the Phase object for a given entry s phase number specified as nr The activities share of the processor utilization Activities processor waiting time Activity service time variance Activity service time The square of the coefficient of variation The activity throughput Activity utilization Summary of Constructors Activity activity object task Returns an instance of Activity f
152. the model comment are ignored by the simulator lqsim Listing shows the format of this section Note that these parameters can also be set using SPEX variables described below 45 3 1 Listing 5 2 General Information lt string gt Model title lt real gt convergence value lt int gt iteration limit lt int gt Optional print interval lt real gt Optional under relaxation Single characters are used for section and record keys Pragma s are processed during lexical analysis 55 5 2 3 Processor Information Processors are specified in the processor information section of the input file using the syntax shown in Listing 5 3 The start of the section is identified using P lt int gt and ends with 1 The lt int gt parameter is either the number of processor definitions in this section or Listing 5 3 Processor Information P lt int gt lt proc id gt sched opt mult 1 Each processor in the model is defined using the syntax shown in line 2 in Listing 5 3 Each record in this section beginning with a p defines a processor lt proc id gt is either an integer or an identifier defined earlier in 45 1 3 sched is used to define the scheduling discipline for the processor and is one of the code letters listed in Table The scheduling disciplines supported by the model are described in Section 1 1 1 Finally the optional lt opt mult gt specifies the number of copies of t
153. they only accept requests from other servers and clients They can be actual processors in the system or may simply be place holders for tasks representing customers and other logical resources Each processor has a single queue for requests Requests may be scheduled using the following queueing disci plines FIFO First in first out first come first served Tasks are served in the order in which they arrive PPR Priority preemptive resume Tasks with priorities higher than the task currently running on the processor will preempt the running task HOL Head of line priority Tasks with higher priorities will be served by the processor first Tasks in the queue will not preempt a task running on the processor even though the running task may have a lower priority PS Processor sharing The processor runs all tasks simultaneously The rate of service by the processor is inversely proportional to the number of executing tasks For qsim processor sharing is implemented as round robin a quantum must be specified RAND Random scheduling The processor selects a task at random CFS Completely fair scheduling 9 Tasks are scheduled within groups using round robin scheduling and groups are scheduled according to their share A quantum must be specified This scheduling discipline is implemented on the simulator only at present Priorities range from zero to positive infinity with a priority of zero being the highest The default pri
154. tion idle_time Print out computed idle time after each submodel is solved 66 interlock Print out interlocking adjustment before each submodel is solved joins Print out computed join delay and join overlap table prior to submodel solution mva arg Print out the MVA submodel and its solution A numeric argument supplied to this option will print out only the specified mva submodel otherwise all submodels will be printed overtaking Print out overtaking calculations print Print out intermediate solutions at the print interval specified in the model The print interval field in the input is ignored otherwise quorum Print quorum traces throughput Print throughputs values variance Print out the variances calculated after each submodel is solved wait Print waiting time for each rendezvous in the model after it has been computed v verbose Generate output after each iteration of the MVA solver and the convergence value at the end of each outer iteration of the solver V version Print out version and copyright information w no warnings Ignore warnings The default is to print out all warnings x xml Generate XML output regardless of input format Z special arg This option is used to select special options Arguments of the form nn are integers while arguments of the form nn n are real numbers Arg can be any of the following convergence value arg Set the convergence value to arg Arg must be a number
155. tional iteration Traditional Array Iteration x for idx 0 key lt array size 1 print Key idx gt array idx In the above code snippet we assume there exists an array which contains n values stored at indexes 0 through 1 continuously However the language provides a more elegant method for iterating over the contents of an array which does not require prior knowledge of the contents of the array This is known as a foreach loop The statement above can be rewritten as follows More modern array itteration foreach key value in array 1 print Key key gt value This method of iteration is much cleaner and is the recommended way of iterating over the contents of an array However there is little guarantee of the order of the results in foreach loop especially when keys of multiple different types are used 40 Type Casting The LQX programming language provides a number of built in methods for converting between variables of different types Any of these methods support any input value type except for the Object type The following is a non extensive list of use cases for each of the different type casting methods and the results Complete documentation is provided in Section double 6699 epe 1 true 0 gt 1 1 gt 1 null bool bool bool bool bool bool bool User Defined Functions The LQX
156. tivity graph defined within the entry The demand is specified using elements of type ActivityEntryDefType This method of defining an entry is not supported currently none The entry is specified using an activity graph defined within the task task activities element of type ActivtyDefType must be present and one of the activities defined within this element must have a bound to entry attribute The TaskActivityGraph type is defined in Section ActivityPhasesType ActivityEntryDefType and ActivtyDefType are all based on ActivityDefBase described in Section 8 2 9 They only differ in the way the start of the graph is identified and in the case of ActivityPhasesType the way the activities are connected The attributes for Entry Type described in Section A 1 6 are shown in TableB 10 The optional element result entry is of type OutputResultType and is described in SectionB 2 12 The optional element forwarding is used to de scribe the probability of forwarding a request to another entry it is described in Section 3 2 10 Default mane soing required __ Theentryname SS enumeration required PHIPH2 GRAPH or NONE open arrival rate float optional priority meger optional CA sempahore enumeration optional signal orvat CELIA Table 3 10 Attributes for elements of type EntryType 3 2 7 ActivityGraphBase Elements of type ActivityGraphBase shown in Figure are used to define act
157. try Bursty reference tasks are a special case of reference tasks where the service time for the slices are random variables with a Pareto distribution c f 91 1 5 Semaphore Task Semaphore tasks are used to model passive resources such as buffers They always have two entries which are used to signal and wait the semaphore The wait entry must be called using a synchronous request whereas the signal entry can be called using any type of request Once a request is accepted by the wait entry no further requests will be accepted until a request is processed by the signal entry The signal and wait entries do not have to called from a common task However the two entries must share a common call graph and the call graph must be deterministic The entries themselves can be defined using phases or activies and can make requests to other tasks Counting semaphores be modeled using a multiserver Synch Task Synchronization tasks are used Cannot be a multiserver 1 1 4 Entries Entries service requests and are used to differentiate the service provided by a task An entry can accept either synchronous or asynchronous requests but not both Synchronous requests are part of the closed queueing model whereas asynchronous requests are part of the open model Message types are described in Section I 1 7 below Entries also generate the replies for synchronous requests Typically a reply to a message is returned to the client who originally se
158. uests or A request from an entry an activity to an entry may return a reply to the requester a synchronous request or rendezvous indicated in Figure I T by solid arrows with closed arrowheads For example task Administrator makes a request to task BackorderMgr who then makes a request to task InventoryMgr While task InventoryMgr is servicing the request tasks BackorderMgr and Administrator are blocked A request may be forwarded to another entry for later reply such as from InventoryMgr to CustAccMgr Finally a request may not return any reply at all an asynchronous request or send no reply shown as an arrow with an open arrow head for example the request from task ShoppingCart to CustAccMegr The first way that the demand at entries can be specified is through phases The parameters of an entry are the mean number of requests for lower entries shown as labels in parenthesis on the request arcs and the mean total host demand for the entry in units of time shown as a label on the entry in brackets An entry may continue to be busy after it sends a reply in an asynchronous second phase of service 7 so each parameter is an array of values for the first and second phase Second phases are a common performance optimization for example for transaction cleanup and logging or delayed write operations The second way that demand can be specified is through activities Activities are the lowest level of granularity in a pe
159. ughput bound for an entry throughput Throughput for a task entry or activity 2 14 utilization float Utilization for a task entry activity waiting float Rendezvous delay waiting variance Variance of delay for a rendezvous ISIS SISIN i T N B EN Table 3 19 Attributes for elements of type ResultContentType ResultJoinDelay ContentType on OutputResult JoinDelayType 0 result join delay 0 1 0 1 result 95 conf result 99 conf Figure 3 10 Schema diagram for type OutputResultJoinDelayType oat Join delay join variance Join delay variance 82 8 Table 3 20 Attributes for elements of type OutputResultJoinDelay Type 36 Output DistributionType min float Histogram in size flo i uber hina unsigned mean float begin float std dev float end float prob float conf 95 float conf 99 float task activity pre AND 0 0 1 0 1 service time h distribution underflow bin histogram bin overflow bin Figure 3 11 Schema for type OutputDistributionType Us flot required The lower bound of the collected histogram data min max The upper bound of the collected histogram data number bins
160. uld not create an object such as a task or processor Cycle in activity graph for task identifier back trace is list There is a cycle in the activity graph forthe task named identifier Activity graphs must be acyclic List identifies the activities found in the cycle Cycle in call graph backtrace is list There is a cycle in the call graph indicating either a possible deadlock or livelock condition A deadlock can occur if the same task but via a different entry is called in the cycle of rendezvous indentified by list A livelock can occur if the same task and entry are found in the cycle In general call graphs must be acyclic If a deadlock condition is identified the cycles allow pragma can be used to suppress the error Livelock conditions cannot be suppressed as these indicate an infinite loop in the call graph Data for n phases specified Maximum permitted is m The solver only supports m phases typically 3 data for n phases was specified If more than m phases need to be specified use activities to define the phases Datatype error Type InvalidDatatypeValueException Message message Delay from processor identifier to processor identifier previously specified Inter processor delay 80 Iqsim 14 14 Iqsim lqsim Derived population of for task identifier is not valid Iqns The solver finds populations for the clients in a given submodel by traversing up the call graphs from a
161. unctions very well for the first 10 11 fibonacci numbers but becomes substan tially slower due to the increased number of relatively expensive function invocations Remember return isa function not a language construct The brackets are required A much more interesting use of functions specifically those with variable length argument lists is an implemen tation of the formula for standard deviation of a set of values 42 N function average Array lt double gt inputs double sum 0 0 foreach v in inputs sum sum v return sum inputs size function stdev booleanx sample x_bar average _va_list sum_of_diff 0 0 Figure out the divisor divisor list size if sample true divisor divisor 1 Compute sum of difference foreach v in _va_list sum of diff sum of diff pow v x bar 2 return pow sum of diff divisor 0 5 You can then proceed to compute the standard deviation of the variable length of arguments for either sample or non sample values as follows from anywhere in your program after it has been defined stdev true 1 2 8 7 9 11 stdev false 2 9 3 4 2 Using Iterating over Arrays As mentioned in the Arrays and Iteration under section 1 1 of the Manual LQX supports intrinsic arrays and foreach iteration Additionally any type of object may be used as either a key or a value in the array The fol low
162. where a line is terminated by a backslash is not needed with Version 2 SPEX All whitespace including newlines is ignored Comments In Version 1 of SPEX all text before a dollar sign or either an upper case P at the start of a line was treated as a comment Since Version 2 SPEX is parsed directly all comments must start with the hash symbol String Substitution Version 2 SPEX does not support variable substitution of string parameters such as pragmas and scheduling types This restriction may be lifted in future versions Pragmas Version 1 SPEX did not require the hash symbol for setting pragmas Version 2 SPEX does SPEX AGR SPEX AGR is no longer supported 5 3 5 SPEX and SPEX uses LQX to generate individual model files All scalar paramaters are treated as globally scoped variables in If the assignement expression for a scalar variable does not reference any array variables it is set prior to the iteration of any loop Otherwise the scalar variable is set during the execution of the innermost loop of the program Array variables are used to generate for loops in the LQX program Each array variable generates a for loop and the loops are nested in the order of the definition of the array variable Local variables i e without the store the array values Finally if SPEX convergence is used a final innermost loop is created This loop tests the variabl
163. y float phase_list wait var activity o end_list 96 wait_var_activity to_entry float_phase_list 2 5 Send No Reply Waiting Time snr_waiting Z ne snr_waitingttbl i end_list 1101 taskname snr waiting e tbl end_list snr_waiting athl L snr_waiting_etbl snr_waiting_entry 6 snr_waiting_entry from entry to_entry float_phase_list snr_waiting_a_thl snr waiting activity Y9 end_list snr_waiting_activity to entry float_phase_list A 2 6 Send No Reply Wait Variance snr wait var VARZ ne snr wait var t tbl X end list snr wait var t tbl taskname end_list snr_wait_var_a_tbl D sn snr wait var e tbl 2 snr_wait_var_entry from_entry float_phase_list snr_wait_var_a_tbl snr_wait_var_activity end_list snr_wait_var_activity to entry float_phase_list A 2 7 Arrival Loss Probabilities drop prob DP ne drop prob t tbl M end_list drop prob t fbl task name drop prob e tbl end list drop prob a tbl drop prob entry o opt drop prob entry to entry float phase list drop probe 16 drop prob a tbl drop prob activity o list

Layered Queueing Network Solver and Simulator User Manual

Contents

Download Pdf Manuals

Related Search

Related Contents