Performance

Archived Posts from this Category

Performance of Shortest Queue Discipline

Posted by Bobby Corpus on 04 Feb 2007 | Tagged as: Performance

We computed the performance of random line queuing discipline in the previous article. However, in real life, we don’t really throw a coin in order to pick which of the two lines we take. Most of the time, we go to the shortest line for service. Using the techniques we have learned in modeling, we will compute the performance of this queue and compare the performance to the other queueing discplines we have computed so far.

Markov Diagram

markov_shortest_line.png

As usual, the arrival rate of customers is 2 customers per minute. Each customer is given a service at an average of 20 secs, which means that an average of 3 customers are being serviced per minute.

Continue Reading »

Comments Off

Computing Performance of Symmetric Multi-Processing Scheduling

Posted by Bobby Corpus on 21 Jan 2007 | Tagged as: Performance

You might have noticed that when you do a transaction in a bank, you usually see a single line being served by 2 or more tellers. You must have perceived that this technique of lining up customers is better than when each teller has its own line. This will lessen the chance of you being stuck for a long time when the guy before you takes a long time to complete transaction.

In computer systems, you can view the customers as tasks to be executed by 2 or more processors. Each processor will pick from a common line, a task that it will execute. In this article, we will analyze the performance of symmetric multiprocessing using continuous markov chain analysis. We will also be using the tool available from www.extremecomputing.org to help us compute the probabilities.

Continue Reading »

Comments Off

Computing Continuous Markov Chains Using Extreme Optimal Solver

Posted by Bobby Corpus on 04 Jan 2007 | Tagged as: Performance

In the last article, we computed the probabilities associated with the states in a continuous markov chain model using balance equations. The computation, although elementary, was tedious and distracts us from the real problem, which is understanding the performance of a queueing model. Fortunately, there is an online tool we can use in order to speed up the computation of continuous markov chains. This tool can be found in the site http://www.extremecomputing.org. This site contains numerous solvers that can be of interest to the computational scientists. However, the tool we are interested in is the Continuous Markov Chain solver which can be accessed in this link.

Continue Reading »

Comments Off

Modeling Queuing Systems Using Markov Chains

Posted by Bobby Corpus on 10 Dec 2006 | Tagged as: Performance

Have you ever notice how various establishments make people line in a certain way? Have you gone to a bank and noticed a number of tellers servicing each client but there is only one line? Wouldn’t it be more natural to let people line up before each teller like you see in a grocery? The way customers are lined up in a server or system of servers is called Queueing Discipline.
In this article, we will learn how various queuing disciplines will affect the values of the performance metrics. We will use continuous markov chain analysis that we learned in the last article.

Motivating Scenario

Assume that the counter of a certain fast food store is arrange in a 2-stage way. The customers first place their order in counter 1, pays the cashier and proceeds to counter 2 to wait for their order to be picked up. Let $a$ be the rate at which customers arrive, $b the rate at which customers places their order and also the rate at which they leave the second counter. Let us draw the markov chain diagram of this system.

Each state is described by two numbers. The first number refers to the number of customers in the first counter. The second number refers to the number of customers waiting at the second counter. For example, state 00 mean that there are no customers being serviced. State “12″ mean that one customer is in counter 1 and 2 customers in counter 2. The blue arrows represent arrivals at rate a and red arrows are represent the rate of customers going to counter 2 and those leaving the counter 2.

markov1.png

Let us examine the four states in the diagram below. There is a blue arrow from state “00″ to state “10″ because when the first customer arrives, the first station will have 1 customer but no one in line yet in counter 2. This means that when the first customer arrives, the system will be in state “10″. There is an arrow from state “10″ to “01″. The means that the first customer is already in counter 2 to pickup his/her order but no new customer has arrived yet. There is a red arrow from state “01″ to “00″. This means that the single customer has already picked up his/her food and has left leaving the system with no customers at both stations. Notice that there is no arrow from state “10″ to “00″ because the customer who is in counter 1 cannot just leave the system but has to go to counter 2 before leaving.

markov2.png
Balance Equations
Now that we have understood why the arrows point from one state to the next, we now setup the balance equations. At steady state, the sum of flows going to one state must equal the sum of flows going out of that state. By definition, the flow along an arrow is equal to the rate along the arrow multiplied by the probability of the system being in the current state.Let us do the balance equation for state “00″. There is one arrow going to state “00″ and one arrow going out of state “00″. Therefore the flow going to state “00″ is equal to the rate going from state “01″ to “00″ multiplied by the probability of the system being in state “01″ : $bP_{01}$. This is equal to the flow going out of state “00″ to state “10″: a*P00. Therefore,we have,

\[a P_{00} = bP_{01}

Let us now compute the balance equation for state “01″. As you can see, there are 2 arrows out of state “01″ and one arrow going into state “01″. The balance equation is therefore:

a P_{01} + b P_{01} = b P_{10}

Doing this for all states, we get the following balance equations:

\begin{gather*} aP_{02} + bP_{02} = b P_{11} + b P_{03}\\ b P_{03} = bP_{12}\\ aP_{00} + bP_{11} = bP_{10} + aP_{10}\\ aP_{01} + bP_{12} + bP_{20} = bP_{11} + bP_{11} + aP_{11}\\bP_{12} + bP_{12} = aP_{02} + bP_{21}\\ bP_{20} + aP_{20} = aP_{10} + bP_{21}\\ bP_{21} + bP_{21} = aP_{11} + bP_{30}\\ b P_{30} = a P_{20}\end{gather*}

We add to these equations the condition that the sum of all probabilities is equal to 1:

\[P_{00} + P_{01} + P_{02} + P_{03} + P_{10} + P_{11} + P_{12} + P_{20} + P_{21} + P_{30} = 1

Solving for the probabilities using elementary algebra, we get the following:

\begin{align*}P_{01}&=\frac{ab^2}{b^3+2ab^2+3a^2b + 4a^3}\\P_{02}&=\frac{a^2b}{b^3+2ab^2+3a^2b + 4a^3}\\P_{03}&=\frac{a^3}{b^3+2ab^2+3a^2b + 4a^3}\\P_{10}&=P_{01}\\P_{11}&=P_{02}\\P_{12}&=P_{03}\\P_{20}&=P_{02}\\P_{21}&=P_{03}\\P_{03}&=P_{30}\\P_{00}&=(b/a)P_{01}\end{align*}

A simple Example

Suppose that customers arrive on the average of 1 customer per minute and can place and pay for their order in 2 minutes. After that they wait on the average of 2 minutes at the second counter to take out their order. Using the formula above, we have $a = 1$ and $b=2$. We can now solve for the probabilities by substituting these values to the above formula.

\begin{align*}P_{01}&= \frac{ab^2}{b^3+2ab^2+3a^2b + 4a^3} = \frac{1\cdot 2^2}{1^3+ 2\cdot 1\cdot 2^2 + 3\cdot 1^2\cdot 2 + 4\cdot 1^3}\\&=\frac{2}{13}\end{align*}

Computing the rest of the values, we get the following table:

P00 4/13
P01,P10 2/13
P02,P11,P20 1/13
P03,P12,P21,P30 1/26

We can compute for the Utilization of the first counter by using it’s idle time. Notice that the first counter does not have anything to do when there are no customers lining in front of it. This happens in states P00, P01, P02 and P03. Notice that these states have the first number equal to 0 (which means: no customer in that counter). Therefore, the utilization is equal to 1 minus the idle time of counter 1, i.e,

\begin{align*}U_\text{counter 1} &= 1 - P_{00} - P_{01} - P_{02} - P_{03}\\ &=\frac{11}{26}\end{align*}

Using the Utilization law we learned in a previous article, we can compute the throughput of counter 1 to be:

\begin{align*}X_\text{counter 1} &= \frac{U_\text{counter 1}}{S_\text{counter 1}}\\ &=\frac{11/26}{2} \\&=\frac{11}{52}\end{align*}

This happens to be the system throughput also since each customer will visit a counter only once per transaction.

Now that we know how to model using markov chains, in the next article, we will analyze other queueing disciplines and compare them according to throughput and response time.

Comments Off

Performance Arithmetic 2

Posted by Bobby Corpus on 15 Nov 2006 | Tagged as: Performance

In the previous article, we learned the various performance laws that we can use to do quick and dirty calculations related to performance. In this article, we will learn how to compute the lower bound on response time. Let us start with a little known law.

Suppose you are a manager of a restaurant and you want to know how many people are dining in your restaurant during a certain time period of the day. Suppose you observe that on the average 3 people leave the restaurant every 30 minutes. Furthermore, the average time a customer spends on your restaurant is 1 hour. Let us denote this time as R. We can compute the throughput of the restaurant as

\begin{align*} X &=3/30 \\ &=0.1\end{align*}

person per minute. If the customers will remain for 1 hour (or 60 minutes) on the average, then we can expect to have 0.1 *60 = 6 customers at any time in the restaurant.
This result is very intuitive and is known as Little’s Law:

\[N = XR\]

where N is the number of concurrent transactions on the system and R is the response time.

Example 1: A financial institution has a server that computes the financial indicators for the day for all stocks in a certain stock exchange. Suppose there is 5 jobs are always running for this task. If a job is finished for a company, another job is launched to compute the indicators for another company. In other words, there are always 5 jobs doing this task at any given time. If each computation takes about 15 minutes to complete, how may stocks can be processed in a day?

Using little’s law:

\begin{align*}N &= X_0 * R \\ X0 &= \frac{N}{R}\\ &= \frac{5}{15 * 60}\\ &= 0.0055\end{align*}

jobs/s

In one day, only \[0.055\times 24\times 3600 = 480\] stocks can be computed.

In a call center there are 50 operators that each receive a query from a customer. There is a backend database that supports the query of the operator. Let us call the duration of time where the operator receives a call and composes a query to the database as the think time \[Z\]. The time that elapses from the time the operator presses the submit button to the time it receives the response from the database as the response time \[R\]. We can view the operators as alternating between two states namely “thinking” and “waiting” for response. Let \[\bar M\] be the average number of operators in “thinking” state and \[\bar N\] be the average number of operators “waiting” for response. Then since an operator can either be “thinking” or “waiting”, we have \[\bar M + \bar N = M\], where M is the number of operators.

Applying little’s law to the operators in “thinking” state, wehave:

\[\bar M = X_0 Z \]
and
\[\bar N = X_0 R\]

Adding the two equations we get:

\begin{align*}\bar M + \bar N &= M \\ & = X_0 Z + X_0 R\\ &=X_0 (Z+R)\end{align}
Solving for R we get

\[R=\frac{M}{X0} - Z\]

This is known as the interactive response time Law.

Example 2: Suppose we were to design a system in which the response time is not to exceed 2 secs and we have 50 operators. If the average think time is 5 minutes, what is the throughput of the system?

From the interactive response law we have:
\begin{align*}X_0 &= \frac{M}{z+R}\\ &=\frac{50}{5*60 + 2} \\ &=0.1655\end{align*}

transactions/s
or 0.1655 * 24 * 3600 = 14304.64 transactions per day.
We now come to an important consequence of thelittle’s law, that of estimating the lower bound of
the response time of a system.

From Little’s Law, the response time is give by

\begin{align*}N &=X_0 R \\ R &= \frac{N}{X_0}\end{align*}

The lower bound for R occurs when the throughput is maximum, or when

\[R >= \frac{N}{1/\text{max}\{D_i\}} = N \times \text{max}\{D_i\}\]

Example 3: A webserver serves images and other static files in disk1 with a service time of 15msecs and its dynamic content is put it disk2 which is faster with a service time of 5msecs. On a peak period of 3 hours, there is an average of 50 concurrent users and the CPU utilization is observed to be 35%. A transaction visits disk1 3 times on the average and disk2 2 times. The webserver completes 50000 transactions in 3 hours. Compute the lower bound of the response time of this system.
\begin{align*}D_\text{disk1} &= S_\text{disk1} V_\text{disk1}\\ &= 0.015 \times 3 \\ &=0.045\end{align*}
\begin{align*}D_\text{disk2} &= S_\text{disk2} V_\text{disk2} \\ &= 0.005 \times 2 \\ &=0.01\end{align*}

\begin{align*}D_\text{cpu} &= \frac{U_\text{cpu}}{X_0} \\ & = \frac{0.35}{50000/(3*3600)}\\ & =0.0756\end{align*}

Since the CPU has the greater service demand,it is the system bottleneck. The maximum throughput this system can attain is 1/0.0756 = 13.22 transactions per second and the response time this throughput is 50 * 0.0756 = 3.78 seconds.

Comments Off

— Next Page »