Tài liệu Queueing mạng lưới và chuỗi Markov P12 ppt

12

Performance Analysis

Tools

Performance analysis tools have acquired increased importance due to increa￾sed complexity of modern systems. It is often the case that system mea￾surements are not available or are very difficult to get. In such cases the

development and the solution of a system model is an effective method of

performance assessment. Software tools that support performance modeling

studies provide one or more of the following solution methods:

l Discrete-event simulation.

l Generation and (steady-state and/or transient) solution of CTMC and

DTMC.

l Exact and/or approximate solution of product-form queueing networks.

l Approximate solution of non-product-form queueing networks.

l Hierarchical (multilevel) models combining one or more of the preceding

methods.

If we use DES, then the system behavior can be described very accurately,

but computation time and resource needs are usually extremely high. In this

book queueing network solutions as well as Markov chain analysis methods

have been introduced to analyze system models. Queueing networks are very

easy to understand and allow a very compact system description. For a limited

class of queueing networks (see Chapters 8 and 9), so-called product-form

queueing networks, efficient solution algorithms (such as convolution, MVA,

SCAT) are available. But many queueing networks do not fulfill the product￾form requirements. In this case approximation methods can be used (see

571

Queueing Networks and Markov Chains

Gunter Bolch, Stefan Greiner, Hermann de Meer, Kishor S. Trivedi

Copyright  1998 John Wiley & Sons, Inc.

Print ISBN 0-471-19366-6 Online ISBN 0-471-20058-1

572 PERFORMANCE ANALYSIS TOOLS

Chapter 10). It is also possible to develop a multilevel model to approximately

solve a non-product-form queueing network. If the approximation methods

are not accurate enough or cannot be applied to a certain problem, as can,

for example, be the case when we have non-exponentially distributed service

times or when blocking is allowed in the network, then DES or CTMC is used.

As we have seen in earlier chapters, the state space for even simple systems can

be huge and grows exponentially with the number of nodes and the number

of jobs in the network. Nevertheless, due to increasing computational power

and better solution algorithms, CTMCs have acquired greater importance.

For the solution of our models we realize that:

l The application of exact or approximate solution algorithms for queue￾ing networks is very cumbersome, error prone, and time consuming and

hence not feasible to carry out by hand calculations.

l The generation and solution of the CTMC/DTMC for even small sys￾tems by hand is nearly impossible.

We therefore need tools that can automatically generate the state space of

the underlying CTMC and apply exact or approximate solution algorithms

and/or that have implemented exact and approximate algorithms for queue￾ing networks. In this chapter we introduce four representative performance

modeling and analysis tools: PEPSY, SPNP, MOSES, and SHARPE. As men￾tioned previously, tools differ not only in their solution algorithms (DES, exact

and approximate solution algorithms for queueing networks, generation and

transient and steady-state solution of CTMCs) but also in their input/output

facilities. There are tools that have a graphical user interface (GUI) and/or

a special input language (batch mode or interactive) or both. Some tools

are based on special model types such as queueing networks, SPNs, CTMC

models, or precedence graphs (and others) or a combination of these model

types.

12.1 PEPSY

PEPSY (performance evaluation and prediction system) [BoKi92] has been

developed at the University of Erlangen-Niirnberg. Using this tool it is pos￾sible to describe and solve PFQNs and NPFQNs. More than 30 solution

algorithms are incorporated. It is possible to specify open, closed, and mixed

networks where jobs cannot switch to another job class. Closed job classes

are described by the number of jobs in each class, while open job classes are

described by the arrival rate of jobs at the class. To compute performance

measures such as throughput, utilization, or mean response time of a given

network, different exact as well as approximation algorithms are provided for

PFQN and NPFQN. The network is described in textual and/or graphical

form. The X11-windows version of PEPSY is called XPEPSY [Kirs93]. PEPSY

PEPSY 573

can be used on almost all UNIX machines, whereas XPEPSY needs the X11

windows system. A Windows95, WindowsNT version WinPEPSY with similar

features is also available but it has a restricted set of solution algorithms.

12.1.1 Structure of PEPSY

12.1.1.1 The input File The PEPSY input file contains the specification of

the system to be modeled. The specification file has a name of the form

e-name and is divided into a standard block and possibly additional blocks that

contain additional information specific to solution algorithms. The standard

block contains all necessary descriptions for most of the solution methods, for

example, the number of nodes and job classes, the service time distribution at

each node, the routing behavior of the jobs, and a description of the classes.

The input file is usually generated using the input program, which is provided

by PEPSY. Information that is not asked for by the input program is provided

using the addition program.

The type of each node (and its characteristics) needs to be specified: the

-/M/m-FCFS, -/G/l-PS, -/G/-IS, and -/G/l-LCFS) and several other node

types. For example, two types of multiple server nodes with different ser￾vice time distributions -/M/m-FCFS-ASYM and -/G/m-FCFS-ASYM can

be specified. The service time distribution is defined by its first and second

moment, or by the service rate and the squared coefficient of variation.

For the solution of the specified models, many different algorithms are

implemented in PEPSY. These algorithms can be divided into six groups:

1. Convolution algorithm for product-form networks.

2. MVA for product-form networks.

3. Approximation algorithms for product-form networks.

4. Approximation methods for non-product-form networks.

5. Automated generation and steady-state solution of the underlying

CTMC.

6. DES.

In addition to these six groups, there are some methods and techniques that

do not fit in any of these groups. For example, the bounds method performs

a calculation of the upper bounds of the throughput and lower bounds of the

average response time.

12.1.1.2 The Output file For each file name e-name, an output file with

the computed performance measures is generated. It is called xx-name where

“name” is the same as in the input file and “xx” is an abbreviation for the

used method. The output file consists of a short header with the name of