Running time of dimensionality reduction

In this section, we evaluate the running time of DR, DR-PI, and DR-CI. We measure the running time as CPU time on a 1 GHz Pentium III with 512 MB RAM, using Matlab 6 running on Linux. In all our experiments, we approximate the ``busy period'' distribution by a two-phase PH distribution.

We first discuss the running time of DR when it is applied to analyze the preemptive priority queue, specifically an M/M/$k$ queue with $m$ priority classes. Figure 3.35 shows the running time (a) as a function of the number of servers, $k$, and (b) as a function of the number of classes, $m$. Here, we assume that all the $m$ classes have the identical service demand distribution (the exponential distribution distribution with rate $\mu$), and have the identical arrival rate, $\lambda$. We choose $\mu$ and $\lambda$ such that the total load is 0.5, i.e. $\frac{m\lambda}{k\mu}=\frac{1}{2}$. Although not shown, the running time becomes longer when the load is higher or when the error bound $\epsilon$ is set smaller.

The solid line in Figure 3.35(a) illustrates the computational efficiency of the DR when it is applied to an FB process (2D Markov chain), showing the running time of DR for two priority classes ($m=2$) as a function of the number of servers, $k$. Recall the DR analysis of the preemptive priority queue with two classes ($m=2$), illustrated in Figure 3.3. Most of the running time is devoted to computing the stationary probabilities in the 1D Markov chain (Figure 3.3(d)) which is reduced from the FB process. When there are $k$ servers, the 1D Markov chain has $k+2$ states in each level (level $\geq k$), and the running time increases as the number of states in each level in the 1D Markov chain increases. As shown in the figure, the running time increases quite slowly with the number of servers, and in fact, the running time is within 30 seconds for up to $k=89$ servers. Overall, DR is computationally efficient when it is applied to 2D Markov chains, i.e. RFB processes with $m=2$ (FB processes) and GFB processes. For most of the analysis of the 2D Markov chains in Chapters 5-7, the running time of DR is within 0.1 seconds.

Figure 3.35: Running time of DR, when applied to an analysis of the preemptive priority queue with $k$ servers and $m$ classes (a) as a function of $k$ and (b) as a function of $m$.

(a)

(b)

The solid line in Figure 3.35(b) shows the running time of DR as a function of the number of classes, $m$, when the number of servers is $k=2$. This is the running time of DR when it is applied to $m$D Markov chains. Again, the running time increases gradually as $m$ increases, and it is within 40 seconds for up to $m=12$ servers ($m$D Markov chains). In fact, as we will see later, the running time is bounded by a polynomial in $m$.

However, the rest of Figure 3.35 suggests that the running time of DR increases quickly when both $k$ and $m$ increase. In general, the running time of DR is dominated by the time to compute the stationary probabilities in the 1D Markov chain that tracks the exact number of lowest priority jobs (class 1 jobs), i.e. the first (foreground) process. This 1D Markov chain has ${m+k-3\choose k-1}^2$ types of busy periods of higher priority jobs (jobs of classes 2 to $m$), and hence the 1D Markov chain has

$${m+k-2 \choose k-1} + 2 {m+k-3\choose k-1}^2$$

states in each level^3.11. That is, the number of states in each level in the 1D Markov chain is polynomial in $k$ if $m$ is constant ($\Theta(k^m)$), and it is polynomial in $m$ if $k$ is constant ($\Theta(m^k)$); however, it is exponential in $k$ and $m$ if neither $k$ nor $m$ is constant.

Note that, in the analysis of the preemptive priority queue, the number of different types of busy periods of higher priority jobs in the $m$-th process (foreground process) does not depend on the number of phases in the PH distributions that are used in the analysis of higher priority jobs, i.e. in the analysis of the $i$-th (background) process for $1\leq i\leq m-1$. However, this is not in general true in the analysis of the RFB process. Specifically, in the analysis of SBCS-ID, the number of phases in the PH distributions that are used in the analysis of the background processes affects the number of different types of busy periods in the foreground processes. As a result, the running time of DR increases more quickly as the number of classes, $m$, increases in the analysis of SBCS-ID. This is exactly a situation where an approximation of DR is needed.

Figure 3.36 shows the running time of DR, DR-PI, and DR-CI as a function of the number of classes, $m$, when they are applied to the analysis of SBCS-ID. In all the plots, we assume that the load made up of each class is fixed at 0.8 (i.e. $\rho_i\equiv\frac{\lambda_i}{\mu_i}$ = 0.8), and $\mu_i$ is chosen such that class 1 jobs are the shortest and class $m$ jobs are the longest (``stealing idle cycles of a server for longer jobs''; specifically, $\mu_i = 2^{i}$), or $\mu_i$ is chosen such that class 1 jobs are the longest and class $m$ jobs are the shortest (``stealing idle cycles of a server for shorter jobs''; specifically, $\mu_i=2^{-i}$). Although not shown, the running times of DR, DR-PI, and DR-CI tend to increase when the load is higher of when the error bound $\epsilon$ is set smaller.

Figure 3.36: Running time of DR, DR-PI, and DR-CI, when applied to an analysis of SBCS-ID.

(a) Stealing idle cycles of server for longer jobs

(b) Stealing idle cycles of server for shorter jobs

In both cases, the evaluation of RDR becomes prohibitive when $m\geq 5$. The running time of DR-PI also quickly grows, and its evaluation becomes prohibitive when $m\geq 8$ in both cases. The running time of DR-CI grows far more slowly than DR and DR-PI. We are able to evaluate DR-CI for up to 21 servers in less than a minute. The running time of DR, DR-PI, and DR-CI can be compared to the number of states in each level (phases) in the 1D Markov chain that tracks the exact number of class 1 jobs (foreground process). In DR, the number of phases $S_{DR(m)}$, grows double exponentially; specifically, $S_{DR(m)}$ can be determined by the following recursive formula: $S_{DR(m)} = S_{DR(m-1)} + 2(S_{DR(m-1)})^2$ and $S_{DR(1)}=1$. In DR-PI, the number of phases grows exponentially: $S_{PI(m)} = 3^{m-1}$. In DR-CI, the number of phases grows linearly: $S_{CI(m)} = 2m+1$.