PDQ: Pretty Damn Quick


All PDQ development is now taking place on Source Forge at
http://sourceforge.net/projects/pdq-qnm-pkg/
(Pretty Damn Quick Queueing Model Package)

1 What is PDQ?

PDQ (Pretty Damn Quick) is open source software associated with the books Analyzing Computer System Performance with Perl::PDQ (Springer 2005) and The Practical Performance Analyst (McGraw-Hill 1998, iUniverse.com Press 2000). The PDQ software package may be downloaded freely from this web site whether or not you own a copy of the book. PDQ uses queue-theoretic paradigms to represent all kinds of computer systems.

Computer system resources (whether hardware and software) are represented by queues (more formally, a queueing network-not to be confused with a data network-which could be a PDQ queueing model) and the queueing model is solved "analytically" (meaning via a combination of algorithmic and numerical procedures). Queues are invoked as functions in PDQ by making calls to the appropriate library functions (listed below 3). Once the queueing model is expressed in PDQ, it can be solved almost instantaneously by calling the PDQ_Solve() function. This in turn generates a report of all the corresponding performance metrics such as: system throughput, and system response time, as well as details about queue lengths and utilizations at each of the defined queues.

This algorithmic solution technique makes it orders of magnitude faster than setting up (and debugging; a step that is often not mentioned by simulationists) and running repeated (another step that is often glossed over) experiments to see if the solutions are statistically meaningful. PDQ solves everything as though it were in steady state. The tradeoff is that you cannot computer higher order statistics. (Actually, you can but that would be major digression here. Come to a class to find out more about that).

2 System Requirements

Analytic solvers are generally faster than simulators and this makes it ideal for the Performance-by-Design methodology described in the book. As part of its suite of solution methods, PDQ incorporates MVA (Mean Value Analysis) techniques (see Chapters 2 and 3 for details). PDQ is not a hardwired application constrained to run only on certain personal computers. Instead, PDQ is provided as open source, written in the C language, to enable it to be used in the environment of your choice - from micro-computers to mainframes. Moreover, PDQ is not a stand-alone application but a library of functions for solving performance models expressed as circuits of queues. Since any PDQ model is defined using the C language, some programming is required. This approach necessitates two things:

That you are already familiar with the C language. This will be true for the many readers who work with open computer systems (e.g., Unix and Windows/NT environments). Since the source provided with the book really constitutes a library of functions for solving performance models, all PDQ models must be written in C. PDQ works by linking its library routines into the C source code for the queueing performance model you wish to solve. This implementation choice allows you to use all the constructs of a modern procedural programming language such as: block design, procedure calls, and recursion, to create and solve potentially elaborate performance models. If you know C, there is no special modeling language to learn.
That you have access to a C compiler. Almost by definition, C compilers are available in every Unix environment and C packages are also provided now with many mainframes. There are also a great number of C compiler products available for PC operating systems such DOS, Windows, Linux and MacOS. This choice of implementation is intended to maximize the portability of PDQ.

All the examples described throughout the book are constructed using this paradigm. Setting up a PDQ model is really quite straightforward as demonstrated by the M/M/1 4 example below. For those readers not yet familiar with the C language, PDQ offers another motivation to learn it. Many excellent introductory texts on the C language are also available.

3 PDQ Library Functions

Some of the PDQ library functions are grouped here in order of most frequent invocation:

`PDQ_Init()`	Initializes all internal PDQ variables. Must be called prior to any other PDQ function.
`PDQ_CreateOpen()`	Defines the characteristics of a workload in an open-circuit queueing model.
`PDQ_CreateClosed()`	Defines the characteristics of a workload in a closed-circuit queueing model.
`PDQ_CreateNode()`	Defines a single queueing-center in either a closed or open circuit queueing model.
`PDQ_SetDemand()`	Defines the service demand of a specific workload at a specified node.
`PDQ_SetVisits()`	Define the service demand in terms of the service time and visit count.
`PDQ_SetDebug()`	enables diagnostic printout of PDQ internal variables.
`PDQ_Solve()`	The solution method must be passed as an argument.
`PDQ_GetResponse()`	Returns the system response time for the specified workload.
`PDQ_GetThruput()`	Returns the system throughput for the specified workload.
`PDQ_GetUtilization()`	Returns the utilization of the designated queueing node by the specified workload.
`PDQ_Report()s`	Generates a formatted report containing system, and node level performance measures.

The complete synopsis for each function is available in the online User Manual.

4 A Simple PDQ Example

An abstract, yet simple PDQ queueing system is shown in Figure 1. It shows "customers" coming in from the left, to receive some kind of service (at the "server") after which they depart the system. Since other customers may already be waiting ahead of the newly arriving customers, a queue forms.

Figure 1: Simple M/M/1 queue.

The term "customer" is part of historical queueing parlence and might actually represent such things as:

customers at a grocery checkout
UNIX processes on the run-queue
messages in a transaction monitor
buffered packets at a router

Accordingly, the "server" might represent

the checkout stand
a UNIX CPU
transaction server
a router CPU

In queueing theory, this is known as an M/M/1 queue, meaning that both arrival and service periods are "Memoryless" or "M" (i.e., completely random in time) and there is only one server. Now, let's calculate the properties of the M/M/1 queue by hand. To do this, we need to recall the relevant mathematical relations for the M/M/1 queue.

4.1 M/M/1 Formulae

It is more convenient to think in terms of inputs and outputs. In other words, which parameters do we need to provide to the formulae versus those values we will calculate as the result of applying the formulae? We list them here:

Inputs:

The average Arrival Rate into the queue: λ.
The average Service Time at the server: S.

With these input parameters we can calculate all other performance quantities (outputs) of interest.

Outputs:

The average Residence Time a customer spends getting through the queueing system: R = S / (1 − λS).
The Utilization of the server: U = λS.
The average Queue Length of the system: Q = λR.
The average Waiting Time a customer can expect to spend before getting service: W = R − U.

To apply these relationships, we need to choose some values for λ and S. We choose the following values so as to keep the arithmetic simple.

Inputs:

The average Arrival Rate: λ = 0.5 customers per second.
The average Service Time: S = 1.0 second.

Then, the resulting queueing characteristics can be calculated using the above formulae.

Outputs:

R = 1.0 /(1 − 0.5 * 1.0) = 2.0 seconds.
U = 0.5 or 50%.
Q = 0.5 * 2.0 = 1.0 customers.
W = 2.0 − 0.5 = 1.5 seconds.

For more realistic models that combine a flow of "customers" between many queues like this one or even more complex queues, such calculations become extremely tedious and error-prone. That's where PDQ comes in. Code once; evaluate anything.

4.2 PDQ Model in C

In PDQ, the simple M/M/1 performance model described above would be coded as follows:

#include <stdio.h>
#include <string.h>
#include <math.h>
#include "../lib/PDQ_Lib.h"

main()
{
    // PDQ global variables
    extern int      nodes;
    extern int      streams;

    // Model specific variables
    double          arrival_rate = 0.5;
    double          service_time = 1.0;

    // Initialize PDQ and the model a name
    PDQ_Init("M/M/1");

    // Change metric labels
    PDQ_SetWUnit("Customer");
    PDQ_SetTUnit("Minute");

    // Create the M/M/1 queue
    nodes = PDQ_CreateNode("Server", CEN, FCFS);

    // Define the workload and circuit type 
    streams = PDQ_CreateOpen("Customers", arrival_rate);

    // Define service demand due to workload on the queueing center
    PDQ_SetDemand("Server", "Customers", service_time);

    // Solve the model
    PDQ_Solve(CANON);

    // Generate a standard report
    PDQ_Report();
}

This might look like a lot of C code for such a simple model, but realize that most of the code is for initialization and other set-up. When amortized over more realistic computer models, it becomes a much smaller fraction of the total code. Note also, that some dozen lines of comments have been added to assist you in reading this particular model.

4.3 Standard PDQ Report

The corresponding standard PDQ report begins by summarizing all the input parameters.

        ***************************************
        ****** Pretty Damn Quick REPORT *******
        ***************************************
        ***  of : Sat Oct 20 14:52:25 2001  ***
        ***  for: M/M/1                     ***
        ***  Rel: PDQ Analyzer v2.5 082401  ***
        ***************************************
        ***************************************


        ******        Comments          *******
        
This is just a simple M/M/1 queue.



        ***************************************
        ******    PDQ Model INPUTS      *******
        ***************************************

Node Sched Resource   Workload   Class     Demand
---- ----- --------   --------   -----     ------
CEN  FCFS  Server     Customers  TRANS     1.0000

Queueing Circuit Totals:

    Generators: 0.00
    Streams   :   1
    Nodes     :   1

WORKLOAD Parameters

Srcs         per Sec       Demand
--------     -------       ------
Customers    0.5000        1.0000


        ***************************************
        ******   PDQ Model OUTPUTS      *******
        ***************************************

Solution Method: CANON

        ******   SYSTEM Performance     *******


Metric                       Value  Unit      
-----------------            -----  ----      
Workload: "Customers"
Mean Throughput         0.5000  Customer/Minute
Response Time           2.0000  Minute
Bounds Analysis:
Max Throughput          1.0000      Customer/Minute


        ******   RESOURCE Performance   *******


Metric          Resource     Work              Value   Unit   
---------       ------       ----              -----   ----   
Throughput      Server       Customers        0.5000   Customer/Minute
Utilization     Server       Customers       50.0000   Percent
Queue Length    Server       Customers        1.0000   Customer
Residence Time  Server       Customers        2.0000   Minute

We see that the PDQ results are in complete agreement with those previously calculated by hand using the M/M/1 formulae 4.1. A more detailed discussion is presented in Chapters 2 and 3 of The Practical Performance Analyst.

File translated from T_EX by T_TH, version 3.38.
On 28 Jun 2009, 08:23.