<figure><img src="image_1.png" /></figure>

HAL
open science

# Analytic methods for multiprocessor system modelling

Alain Kurinckx, Guy Pujolle

► To cite this version:

Alain Kurinckx, Guy Pujolle. Analytic methods for multiprocessor system modelling. [Research Report] IRIA-RR-331, IRIA. 1978, pp.24. hal-04716519

HAL Id: hal-04716519

https://inria.hal.science/hal-04716519v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Inv: 05600, RR331

IRIA

laboria

(HS)

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_3.png" /></figure>

ANALYTIC METHODS
FOR MULTIPROCESSOR
SYSTEM MODELLING

Alain KURINCKX
Guy PUJOLLE

Rapport de Recherche N° 331

Novembre 1978
ANALYTIC METHODS FOR MULTIPROCESSOR SYSTEM MODELLING

Alain Kurinckx, Guy Pujolle

IRIA/LABORIA

Résumé :

Nous résumons et étendons quelques résultats mathématiques obtenus sur les systèmes de files d'attente en parallèle et les files d'attente à plusieurs serveurs. Devant le manque de possibilités des méthodes exactes, nous développons un algorithme permettant d'étudier de tels systèmes avec des probabilités de routage et des temps de service dépendant de l'état du système. Nous construisons également un modèle mathématique d'un calculateur multi-processeurs. Nous utilisons la méthode approximative développée auparavant pour étudier les effets des politiques d'allocation sur les performances du système.

Abstract :

We review some mathematical results on parallel queueing systems and on many servers queues.

We develop an approximate general method to solve such systems with global state dependant routing probabilities and service rates. We also build a mathematical model of a multiprocessor system and we use the approximate method to study the effects of scheduling policies on system performance as mean response times or queue length distributions.
# 1. Introduction

In a recent classification by Fuller and Sieviorek [1], multi- processors systems have been distributed in three classes : the tightly coupled processors systems (multiprocessors as Illiac IV, Staran,...), the loosely coupled processors systems (computer networks) and interme- diate systems. Extensive works have been realised for the first two categories but there are only few studies devoted to intermediate mul- tiprocessors systems.

The aim of this paper is to develop a method to solve models arising in this type of systems. In particular, we are interested in scheduling policies for jobs on the processors.

In the first section we are going to review some mathematical results obtained in the literature on queueing systems composed of queues in parallel or of one multiserver queue (Figure 1). Moreover we give some extensions of these results and in particular we find conditions for the existence of product form solutions in systems of parallel queues.

In the rest of the paper, we develop a queueing model of a more realistic multiprocessor system. None of the available methods are applicable to the solution of that model; this is because the routing probabilities and the service rates depend on the global system state. For instance the general "join the shortest queue" policy cannot be studied by any exact mathematical method.

For this reason we introduce an approximate method to solve rather general systems with parallel queues. The method yields approximate values for the marginal probability distributions of queue lengths the mean numbers of customers, and the mean response times.

The analysis of the model proceeds in two stages : first, using decomposition, the general system is replaced by one consisting of parallel queues where the service rate are function of the number of busy processors; these queues are then analysed by the iterative method to study the effect of scheduling policies on the performance of the system.
Finally we give numerical results for the response times as a function of jobs and system parameters. Several scheduling policies, such as "random access" or "join the shortest queue", are thus investigated and their performance is compared.

## 2. Mathematical models of many-servers queues.

We shall decompose the available models in two categories (Figure 1) : those of category A includes just one queue and several parallel servers, those of category B which are composed of several queues in parallel, each with one server.

<figure><img src="image_4.png" /><figcaption>Figure 1</figcaption></figure>

In both categories many policies are available to allocate servers to arriving customers. We are going to study the cases where this allocation is dependent on the state of the systems. Other considerations can be added : state dependent service times, possibility to jump from one queue to another one (jockeying). Some studies are devoted to this class of problems, we are going to summarize them, and, in the same time we shall examine some extensions.

We assume that service times and interarrival time are independent and exponentially distributed.

Let $\lambda$ be the total arrival rate, $\mu_i$ be the service rate at station i, $i=1,...,M$, and let us denote

$$ \rho_i = \lambda/\mu_i \quad \text{and} \quad \rho = \lambda/(\sum_{j=1}^{M} \mu_j) $$
For the sake of simplicity we describe only the two servers cases;
extensions to M servers are straightforward.

2.1. Models of category A

- Case 1 : When a customer arrives then :

a) if both servers are busy then, it waits in a single
queue managed by FIFO discipline. The customer at
the head of the queue occupies the server that becomes
idle first.

b) if only one server is free : it occupies the free
channel.

c) if both channels are free : it chooses server 1 with
probability $\Pi_1$ and server 2 with probability $\Pi_2=1-\Pi_1$.

This case is well known and named "Maître d'Hôtel" if $\Pi_1=\Pi_2=\frac{1}{2}$ and "Maître d'Hôtel with preference" otherwise. The case $\Pi_1=\Pi_2=\frac{1}{2}$ has been studied by Gumbel [3] in the general case of M servers. The general case has been studied by Krishnamoorthi [4] with 2 servers. Moreover Krishnamoorthi has shown that the average waiting time is minimized when $\Pi_i=1$ if i is the faster channel.

- Case 2 : Let us assume $\mu_1 \le \mu_2$, namely the server 1 is slower than server 2. When a customer arrives then :

a) if both servers are busy, it waits in a single queue
in order-of-arrival sequence. If server 2 becomes
vacant the customer at the head of the queue occupies
this server. If server 1 becomes vacant the customer
at the head of the queue occupies this server if and
only if the total number of customers awaiting service
is less than a given value m.
b) if server 2 is free, it occupies it.
if server 1 is free, it joins the queue and the
customer at the head of the queue occupies this
server if and only if the total number of units
awaiting service is less than m.

c) if both channels are free, it chooses server 2.
The exact analysis of this system is quite diffi-
cult and a solution is proposed by Krishnamoorthi
[4] when the number of servers is 2. This solution
uses a complex algorithm. The value of m which mini-
mized the average waiting time is an open problem.
Krishamoorthi proposes the greater integer less than
$\mu_2/\mu_1$.

- **Case 3**: This system is identical to the previous one except in the following point : when the number of customers decreases from m+1 to m, server 1 stops and the customer in service goes to the head of the waiting queue. We provide now a solution (believed to be novel) to this case.

Let n be the number of customers in the waiting room. If n ≤ m the service rate is μ₁ and if n > m the service rate is μ₁+μ₂, (we must have m ≥ 1). Let ρ₁ = λ/μ₁ and ρ = λ/(μ₁+μ₂), we have :

$$
p(n) = \begin{cases} \rho_1^m p(o) & \text{if } 0 \le n \le m \\ \rho_1^{m} \rho^{n-m} p(o) & \text{if } n > m \end{cases}
$$

In normalizing, we obtain :

$$
p(o) = \frac{(1-\rho_1)(1-\rho)}{1-\rho-(\rho_1-\rho)\rho_1^m}
$$

The mean number of customers in the system can be written as follows:

$$
E = \frac{1-(m+1-m\rho_1)\rho_1^{m+1}}{(1-\rho_1)^2} + \frac{(m+1-m\rho)\rho_1^m}{(1-\rho)^2} \rho p(o)
$$
The stability condition of this system is obtained writing
$p(o) > 0$ [5], namely $\lambda < \mu_1+\mu_2$. This value does not depend on $m$.

A special case has to be noted : $m=1$. When there is only one
customer in the system, then it occupies server 1; if there is more
then one customer, both servers are busy. This system can model a
system with two processors which cooperate when only one customer is
in the system and which work independently otherwise. The solution of
this model can be easily extended to more than two parallel servers.

## 2.2. Models of category B

We recall that a waiting room is associated with each server. In
a first step, we shall examine only two queues in parallel. Let $\lambda$ be
the external arrival rate and $q_i$, $i=1,2$ the routing probabilities.
We denote $\lambda_1=q_1\lambda$, $\lambda_2=q_2\lambda$, $\rho_1=\lambda_1/\mu_1$, $\rho_2=\lambda_2/\mu_2$ and $\rho=\lambda/(\mu_1+\mu_2)$.

- **Case 0**: The two queues are independent (a Bernoulli switch routes the customers). We have $E_1 = \frac{\rho_1}{1-\rho_1}$, $E_2 = \frac{\rho_2}{1-\rho_2}$ and $E=E_1+E_2$, if $E_i$ is the mean number of customers in queue i.

- **Case 1** :

a) In this system, arriving customers join queue i with a fixed probability $q_i$ ($q_1+q_2=1$)

b) If both channels are free : it chooses server 1 with probability $\Pi_1$ and server 2 with probability $\Pi_2=1-\Pi_1$

c) If, at any time, the difference in queue lengths exceeds $k$, the last customer in the longest queue joicks to the end of the shortest line. Jockeying is instantaneous.

Such a system has been studied by Koenigsberg [6] when $k=1$ and is
named "Tellers'Windows with Jockeying" (with preference if $\Pi_1 \neq \frac{1}{2}$).
Koenigsberg shows that the total mean number in the system is identical
to this of case 1 of category A.
- Case 2 : In this paragraph we study the system where customers join a queue by a global state dependent switch. Once in the assigned queue, jockeying is forbidden.

First, we are going to examine condition for the solution to be
in product form for the general case of M parallel processors. Let
$\vec{n} = (n_1, n_2, ..., n_M)$ be the state vector where $n_i$ is the number of cus-
tomers in queue and server i. Let $q_i(\vec{n})$ be the routing probability
for an incoming customer to enter queue i when the state of the sys-
tem is $\vec{n}$. Let us note $\vec{n}+1_i=(n_1, n_2, ..., n_i+1, ..., n_M)$. Local balance equa-
tions write as follows :

$$
\mu_j p(\vec{n}+1_j) = \lambda p(\vec{n}) q_j(\vec{n})
$$

This equation have a solution verifying global balance equation
if the following conditions are verified : starting from a state
$\vec{n}+1_i+1_j$ to enter state $\vec{n}$, the same value of $p(\vec{n})$ must be found by
going either through state $n+1_j$ or through state $n+1_j$. This necessary
and sufficient condition can be written : $q_j(\vec{n}+1_i)q_i(\vec{n})=q_i(\vec{n}+1_j)q_j(\vec{n})$,
$\forall i, \forall j, \forall \vec{n}$. If routing probabilities verify these conditions, we
obtain a product form solution :

$$
p(n_1, \dots, n_M) = C \prod_{j=1}^{M} \left( \frac{\lambda}{\mu_j} \right)^{n_j} q_j(\vec{n}-1_j) \dots q_j(\vec{n}-n_j 1_j)
$$

If M=2 the condition is

$$
\frac{q_1(n_1, n_2)}{q_1(n_1, n_{2+1})} = \frac{q_2(n_1, n_2)}{q_2(n_1+1, n_2)}
$$

Some interesting cases can now be treated : if routing probabilities
verify : $q_i(\vec{n}) = \frac{n_i}{||\vec{n}||}$ with $||\vec{n}|| = \sum_{i=1}^{N} n_i$ or (see also [7])

$$
q_i(\vec{n}) = \frac{s_i - n_i}{||\vec{s} - \vec{n}||} \quad \text{with} \quad ||\vec{s} - \vec{n}|| = \sum_{i=1}^{N} (s_i - n_i), \text{ etc...}
$$

we obtain a product form solution.
Extensions to a service time dependant on the state of its queue and an arrival rate dependant on the total number of customers in the system is possible.

Unfortunately, only the solution of few cases is in product form. For example, the simple scheme consisting in joining the shortest queue has neither a product form nor a closed solution. (A study in truncating the state graph is performed by Chow and Kohler [8] and a diffusion approximation by Foschini and Salz [9]).

Now, if service times are dependant on the state of the entire system, no method is known. Nevertheless, as we shall show it, accurate models of many *processors* systems need a service time dependant on the total state of the system. It is the reason why we are going to develop a new algorithm yielding a solution of a very large class of multi servers systems.

## 2.3. Comparisons of the many servers models.

Before to conclude this section, we are going to give an idea of the performance obtained by the models described previously. We have chosen as a criterion of performance, the mean number of customers in the system. The results of eight models are shown in table 1. The 7 first results are exact results, the last one is obtained by the algorithm that we shall develop in the next section. It corresponds to the "shortest queue" policy with equal probabilities when queue lengths are equal. The common model has just 2 servers, the second one with a fixed exponentially service rate $\mu_2=1$, the other with an exponentially service rate varying from 2 to 10 by step 1. The cases of column 6 and 7 correspond to product form solutions where the routing probabilities are defined by :

$$ \text{Case 6} \qquad q_i(\vec{n}) = \frac{10-n_i}{||10-\vec{n}||} \qquad i=1,2 $$

$$ \text{Case 7} \qquad q_i(\vec{n}) = \frac{5-n_i}{||5-\vec{n}||} \qquad i=1,2 $$
the waiting rooms are limited to 10 and 5 respectively in this two cases.

We can note on these comparisons the important difference between the 8 cases. These models are however too rough to approximate correctly a multi-processors system and it is for this reason that we are going to develop a new algorithm to take into account more possibilities as global state dependant service times.

mean number in the system

$$ \lambda = 1.5 \ (\lambda_1 = 1, \lambda_2 = 0.5) \ \mu_2 = 1 $$

<table><caption>Table 1</caption><thead><tr><th rowspan="2"></th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th></tr><tr><th>2 independent queues</th><th>Maitre d'Hotel<br>or<br>Tellers'Windows<br>with Jockeying</th><th>Maitre d'Hotel with<br>preference<br>Teller's Windows with<br>Jockeying and with<br>preference</th><th>A1<br>Π₁=1<br>Π₂=0</th><th>B1<br>Π₁=0<br>Π₂=1</th><th>Queue 1<br>preemptive<br>resume<br>m=1</th><th>product<br>form<br>solutions</th><th>Join the<br>shortest<br>queue</th></tr></thead><tbody><tr><td>μ₁ = 2</td><td>2.</td><td>1.227</td><td>1.191</td><td>1.256</td><td>0.8</td><td>2.391</td><td>1.996</td><td>1.378</td></tr><tr><td>μ₁ = 3</td><td>1.43</td><td>0.727</td><td>0.667</td><td>0.769</td><td>0.571</td><td>2.061</td><td>1.663</td><td>1.046</td></tr><tr><td>μ₁ = 4</td><td>1.33</td><td>0.563</td><td>0.484</td><td>0.613</td><td>0.379</td><td>1.930</td><td>1.525</td><td>0.890</td></tr><tr><td>μ₁ = 5</td><td>1.25</td><td>0.482</td><td>0.389</td><td>0.537</td><td>0.281</td><td>1.860</td><td>1.449</td><td>0.797</td></tr><tr><td>μ₁ = 6</td><td>1.2</td><td>0.434</td><td>0.329</td><td>0.492</td><td>0.223</td><td>1.817</td><td>1.403</td><td>0.736</td></tr><tr><td>μ₁ = 7</td><td>1.167</td><td>0.402</td><td>0.288</td><td>0.463</td><td>0.184</td><td>1.787</td><td>1.371</td><td>0.692</td></tr><tr><td>μ₁ = 8</td><td>1.143</td><td>0.380</td><td>0.257</td><td>0.443</td><td>0.156</td><td>1.766</td><td>1.348</td><td>0.659</td></tr><tr><td>μ₁ = 9</td><td>1.125</td><td>0.363</td><td>0.233</td><td>0.428</td><td>0.136</td><td>1.750</td><td>1.330</td><td>0.634</td></tr><tr><td>μ₁ = 10</td><td>1.111</td><td>0.350</td><td>0.214</td><td>0.417</td><td>0.12</td><td>1.737</td><td>1.317</td><td>0.614</td></tr></tbody></table>
### 3. An approximate general method

In this section we present a general method to solve the queueing systems of category B we have described in the previous sections. The method leads to approximate values of the marginal probability distributions of queue lengths, of mean number of customers and of mean response times for systems which verify the following assumptions:

(i) customers arrive into the system according to a Poisson process of parameter $\lambda$

(ii) the probability that an arriving customer joins queue i ($1 \le i \le M$) is $q_i(\vec{n})$, an arbitrary function of the number-in-queue state vector $\vec{n} = (n_1, \dots, n_i, \dots, n_M)$. Notice that these functions must verify

$$ \sum_{i=1}^{M} q_i(\vec{n}) = 1 $$

i in the state space

(iii) service times of queue i server are independent and identically exponentially distributed with mean $\mu_i^{-1}(\vec{n})$.

The method we propose consists in computing for each queue a fictive arrival rate and a fictive service rate only depending on the number of customers in the queue :

$$ (1) \qquad \lambda_i(n_i) = \sum_S \lambda_i q_i(\vec{n}) p_i(n_i|\vec{n}) \qquad n_i=0,1,\dots $$

$$ (2) \qquad \mu_i(n_i) = \sum_S \mu_i(\vec{n}) p_i(n_i|\vec{n}) $$

where

- S is the set of states with a fixed number of customers n in queue i.

- $\vec{n}$ is a vector of dimension M-1 identical to $\vec{n}$ after removing its ith component.

- $p_i(n_i|\vec{n})$ is the conditional probability to have $n_i$ customers in queue i if there are $n_j$ customers in queue j, $j=1, M, j \neq i$.
From the fictive arrival and service rates, it is possible to
evaluate the marginal queue length distributions. For queue i :

$$
(3) \qquad p_i(n_i) = p_i(0) \prod_{j=1}^{n_i} \frac{\lambda_j (i-1)}{\mu_j (i)} \quad n_i = 1, 2, \dots
$$

$p_i(0)$ is given by the normalizing equation

$$
(4) \quad \sum_{n_i=0}^{\infty} p_i(n_i) = 1
$$

Notice that to write equation (3), it is necessary to assume
that the arrival Poisson flow splits up in M Poisson flows so that
each queue behaves like a M/M/1 queue. In the following we assume
this property approximatively verified although it is true only in
particular cases (for example qᵢ state independant for each i).

The main difficulty is to express the value of pᵢ(nᵢ|n̄). In
order to be able to compute λᵢ(nᵢ) and µᵢ(nᵢ) we substitute in (1), (2)
pᵢ(nᵢ|n̄) by pᵢ(nᵢ), namely in the computation of fictive arrival
and service rates we assume the conditional probability to be
equal to the marginal one. This simplification is the most important
approximation of our method. Although the equality of the two proba-
bilities is true only for systems having a product form solution
(see section 2), we shall see later that our method gives good results
in almost all cases.

With this approximation we have to solve the system composed by
equations (1), (2), (3), and (4) by the mean of an iterative scheme.
In order to have a finite state space we limit the capacity of each
queue i to a value mᵢ choosen such that the errors due to truncating
the distributions are not too important. The algorithm we propose is
the following :
begin give an initial value to pᵢ(nᵢ) {i=1,...,M
rᵢ(nᵢ)=0
while M sup i=1 ∪ nᵢ=0,...,mᵢ | pᵢ(nᵢ)-rᵢ(nᵢ)| > ε do

begin rᵢ(nᵢ):=pᵢ(nᵢ) i=1,...,M nᵢ=0,...,mᵢ;

for i equal 1 to M do

begin compute λᵢ(nᵢ) and μᵢ(nᵢ), nᵢ=0,...,mᵢ

from eq. (1) (2);

compute pᵢ(nᵢ) nᵢ=0,...,mᵢ from eq. (3), (4);

end;

end;

end.

Remarks :

- ε is the accepted error on each marginal state probability

- as initial value we adopt

$$
p_i(n_i) = \frac{1}{m_i + 1}
$$

- if mᵢ=m for each i, storage requirements of this algorithm is proportional to (m+2)(M+1), μᵢ(↓n) and qᵢ(↓n) being implemented as internal or external procedures.

The problem of the convergence of the algorithm has not been
tackled in a pure mathematical way (one should show that the iterative
function is of Lipschitz), but, it is easy to see that the iterative
function is monotoneous; this property suggests the convergence of our
algorithm. Be that as it may, all the experiences we performed show
that the solution is obtained after few iterations.

The problem of stability of parallel queues systems with global
state dependant service rates is still an open problem. Nevertheless,
in some particular cases it is possible to give a sufficient condition
of stability. If the stability condition is not satisfied, our algorithm
provides the following solution :
$$ 
\begin{array}{l@{\qquad}l}
p_i(n_i) = 0 & \text{if } n_i < m_i \\
p_i(m_i) = 1 & \text{for } i=1, \dots, M
\end{array}
$$

We are now going to give some details about the accuracy of the method. First notice that exact results are obtained in cases where a product form solution exists.

We performed a great number of experiences in order to compare results obtained by our method with simulation results. These experiences show good agreement : the difference is of the same order of magnitude as the looseness of simulation results.

As an example (Table 1) we give one of the most unfavourable case we met : "join the shortest queue" with equal routing probability when queues are of the same length. We note an accuracy of about 10 % on the mean numbers in the stations

$$ \lambda = 1.5 \quad \mu_1(n_1,n_2) = \mu_2(n_1,n_2) = 1.5 \quad \forall n_1, \forall n_2 $$

<table><thead><tr><th></th><th>p(0)</th><th>p(1)</th><th>p(2)</th><th>p(3)</th><th>p(4)</th><th>mean number in station 1</th><th>mean number in station 2</th></tr></thead><tbody><tr><td>Algorithm</td><td>0.5</td><td>0.375</td><td>0.117</td><td>0.008</td><td>0.000</td><td>0.633</td><td>0.633</td></tr><tr><td>Simulation</td><td>0.5</td><td>0.341</td><td>0.114</td><td>0.028</td><td>0.007</td><td>0.698</td><td>0.703</td></tr></tbody></table>

## 4. A specific application to modelling of a multiprocessor computer system

In this section, we examine the behaviour of a computer system including n distributed processors. The architecture of such a system can be modeled by the idealized queueing network shown in figure 2.
<figure><img src="image_5.png" /><figcaption>Figure 2</figcaption></figure>

Jobs, which enter the system with rate $\lambda$ are directed to a processor according to some scheduling policy (for example one of the policies described in the previous sections). The aim of this section is to compare the global mean response times of a job with several policies. In a first step we are going to describe the behaviour of the system.

Jobs are queued behind a processor and are served according to the FIFO discipline. When running a job, a processor can access to informations (instructions and data) contained in its private memory. If the information needed is not present a request is made to a global memory shared among all processors. During its execution, a job can
ask for an I/O operation in which case it joins a specialized processor.
After completion of a request (I/O or global memory) the execution re-
starts.

Remarks :

- only one job is loaded in the private memory of a processor

- a job stays into the private memory until it has finished its execution

- when a job is queued or served in the I/O or in the global memory device, its processor is blocked.

Firstly, we want to know the time a job spends in a processor before completing, as a function of system parameters (such that : number of processors, size of the memories...) and program behaviour parameters.

Secondly, we want to know the time a job spends in the system from its arrival instant into the queue of a processor to its exit of the system. This time depends on the scheduling policies we use to route the arriving jobs.

To compute the residence time in a processor, we use a decomposition scheme : the idea of the decomposition is to form, with state variables of a complex system, a small number of groups such that :

- interactions of variables, inside a group can be studied as external interaction does not exist.

- interactions of groups can be studied without the necessity to take into account interactions between variables inside each group.

In a queueing network, decomposition consists in substituting a subsystem by a simpler entity. The parameters of this entity are computed in the replaced subsystem with a fixed number of customers circulating in it. Systems before and after replacement are equivalent if at steady state:

- probability distributions of the total number of customers in both systems are identical

- probability distributions of state variables which do not belong to the replaced subsystem are identical.
Only few systems have the so-called decomposition property but often it can be shown that the studied system is "near decomposable". The interactions between the subnetwork to be replaced and other parts of the network are then weak compared to the interactions inside the subnetwork. It is the case when internal time constants are at least an order of magnitude smaller than the external one.

Our model shows three levels of decomposability in the terminology of Courtois [2].

- level 1 : user level

- level 2 : processor level

- level 3 : instruction level.

The constants of times of these three levels satisfies for the decomposability conditions.

We are going to study these three levels step by step.

**Level 3.** We need to know the real busy time of a processor, namely the time during which the processor is either executing, or awaiting for an instruction of its private memory. This level is shown in figure 3 following two points of view (see also [10]).

<figure><img src="image_6.png" /></figure>

Assumption : idt+pet ≥ mrt

<caption>Figure 3</caption>
Let $t_e$ be the total execution time required by a job; the time $t_r$ during which the job occupies the processor at the level 3 is $t_e$ plus the access times plus the decoding times. We assume that one decoding time plus one executing time is greater than one rewriting time. Let $s$ be the mean time between two memory accesses and $D$ be the time of one memory access plus the time to decode the instruction. If we assume $D$ fixed, we have

$$t_r = t_e \left(\frac{D}{s} + 1\right)$$

Notice that this time does not include I/O operations and accesses to the global memory.

Level 2. The model of the level 2 is shown in figure 4

<figure><img src="image_7.png" /><figcaption>Figure 4</figcaption></figure>

We have to study this closed network with a fixed number ($l=1,...,n$) of jobs. When a job completes (with probability $p_3$), it is instantaneously replaced by another one statistically equivalent. Station 0 is composed by a number of servers equal to number of jobs. By an argument of decomposition the mean response time of a job will be used in level 1 as the mean occupation time of a processor if there are 1 busy processors. The mean service time of such station 0 has been studied at the level 3. Let $a_1$ be the number of instructions executed between two I/O requests and $a_2$ the number of instructions executed between two memory faults (request
made to the private memory but insatisfied or direct request to the global memory) and $a_3$ the total number of instructions of a job.

We assume that $a_1, a_2, a_3$ are exponentially distributed with parameters $v_1, v_2, v_3$ respectively, and let a be the number of instructions executed by the processor without interruption (except those of its private memory). We have $a = \min(a_1, a_2, a_3)$. This variable is exponentially distributed with parameter $v_0 = v_1 + v_2 + v_3$.

Branching probabilities are easily found : $p_1 = \frac{v_1}{v_0}$, $p_2 = \frac{v_2}{v_0}$, $p_3 = \frac{v_3}{v_0}$. Let r be the mean time to execute one instruction, and $v_0$ be the distribution of the uninterrupted execution time.

From level 3 and from the exponential distribution of a, f is the exponential distribution with mean service time : $\mu_0^{-1} = ar(\frac{D}{s}+1)$.

Let us assume that $\mu_1$ and $\mu_2$ are the rates at which are satisfied I/O requests and global memory requests. The state of the system shown in figure 5 is given by the vector $e = (l_0, l_1, l_2)$ ($l_i$ is the number of customers in station i, $l_0+l_1+l_2=1$) and we denote by $p(l_0, l_1, l_2)$ the probability of state e.

From Baskett, Chandy, Muntz, Palacios theorem [11] we have :

$$p(l_0, l_1, l_2) = C \frac{1}{l_0!} \left(\frac{1}{\mu_0}\right)^{l_0} \left(\frac{p_1}{\mu_1}\right)^{l_1} \left(\frac{p_2}{\mu_2}\right)^{l_2}$$

where C is a normalizing constant.

Let $W_0, W_1$ and $W_2$ be the mean response times of stations 0, 1, 2 respectively. They can be obtained using BCMP formula. The response time of a job before completion is now :

$$W(1) = \frac{W_0}{p_3} + \frac{1}{p_3} \left[ \frac{p_2}{p_1+p_2} W_2 + \frac{p_1}{p_1+p_2} W_1 \right]$$

This value will be used at level 1 as the occupation time of a processor when there are 1 busy processors. So before studying level 1, we have to evaluate $W(1)$ for $l=1,...,n$.
**Level 1.** By the equivalent scheme we substitute the level 2 network by a server of mean service time $W(1)$ that we assume exponentially distributed. The model at level 1 (the user level) is a parallel queueing system of category B, we have studied in section 2. From level 2 we have seen that the service time depends only on $1$, the number of busy servers when the characteristics of the system are fixed. We find a model which cannot be studied by an exact mathematical technique; so we use the algorithmic approach. Moreover, we shall use scheduling policies, as "join the shortest queue", which require for themselves the algorithmic solution.

We have compared three scheduling policies :

1 - equal routing probability ("random access")

2 - a job entering the system occupies one of the idle processors with equal probability. If all the processors are busy, it joins one of the queues with probability $1/n$.

3 - "join the shortest queue" with equal routing probabilities to join one of the shortest queues if more than one.

We assume in our example 5 processors in parallel. If the unit of time is the second we take $\mu_1 = \mu_2 = 100$. The other parameters of the system are $r = 10^{-6}$, $s = 10^{-5}$, $D = 10^{-6}$, $v_3 = 1.5 \cdot 10^8$ instructions. Now we have treated the example for three values of $v_1$ and $v_2$ :

1 - $v_1 = 10^6$ instructions, $v_2 = 5.10^5$ instructions

2 - $v_1 = 0.6 \cdot 10^6$ instructions, $v_2 = 10^5$ instructions

3 - $v_1 = 0.2 \cdot 10^6$ instructions, $v_2 = 5.10^4$ instructions

These values correspond to 15s of total execution time and :

1 - 10 I/O requests by second, 20 memory faults by second

2 - 30 I/O , 100

3 - 50 I/O , 200
Figure 5a, 5b, and 5c display the mean response time of a job as a function of the input rate ($\lambda$). We also draw in each case a vertical line corresponding to a sufficient (and not necessary) condition of stability :

$$ \lambda^* = nW^{-1}(n) $$

When the I/o and global memory requests rates are law (figure 5a), we see that policy number 3 leads always to best performance but response times of second and third policies are very closed. If the input rate is greater than $\lambda^*$, the performance of the "join the shortest queue" policy degrades itself more quickly than first policy performance. From this remark one can say that real stability condition of third policy is reached more quickly than with the "random access" policy.

Figure 5b exhibits the same phenomena but brought out more strongly. In particular, beyond $\lambda^*$ the "join the shortest queue" policy becomes the worst one. When the input rate still increases, the best policy is the first one. Notice that, in this case, the real stability condition of the third policy is very close to sufficient condition $\lambda^*$.

Figure 5c leads to the same conclusions. With "bad" jobs (high I/o and global memory request rates), it may be dangerous to use the third policy because response times are very large just beyond $\lambda^*$.

The phenomena we have just emphasized are easily explainable. Analysis of level 2 brings out a "thrashing" : performance degrades itself (i.e. the occupation time of a processor increases) when the number of busy processors increases with "bad" characteristics of jobs (it is due to the congestion of I/O and global memory units). Due to this thrashing it is preferable, in some cases, to let some processors idle. This explains why the "join the shortest queue" policy which shares out very well the load, becomes the worst one with high input rate and "bad" jobs.
To summarize it is surely useful to schedule jobs according to the "join the shortest queue" or the second policy provided that the inputs are controlled as soon as the input rate reaches $\lambda^*$. An other reason to use this scheduling policy is that the yielded queue length distribution decreases more rapidly than the distribution obtained with the "random access" policy. Figure 6 provides an example of such a situation. Potential advantage is the reduction of response times dispersion which is highly desirable property in computer systems.

### 5. Conclusion.

After reviewing some mathematical models of parallel queues systems we remarked the bad adequacy of these models to evaluate multi-processors systems performance. So we developed a rather general algorithmic method to solve parallel queues systems with global state dependent routing probabilities and service rates. This method is sample and yields to accurate results. It can be implemented as a computer program with limited storage requirements.

In the sequel of the paper we described a multiprocessors system with private and global memories and one I/O device. We built a mathematical model and we solved it in two steps. Firstly using the decomposition method we simplified the model to obtain a parallel queueing system. Secondly, we used our algorithmic method to study the effect on the performance of the scheduling policy for various job behaviours. The main conclusion is the absolutely necessity to implement a dynamic control to take into account the fluctuation of the load. This control will operate on the scheduling policy in order to keep active all the processors when jobs have "good" characteristics and to limit the number of busy processors otherwise.
<figure><img src="image_8.png" /><figcaption>Figure 5a</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 5b</figcaption></figure>

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /><figcaption>Figure 5c</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Figure 6 queue length</figcaption></figure>
REFERENCES

1 - Fuller S.H., Siewioreck D., "Some observations on semi conductor technology and the architecture of large digital modules", Computer 6, 10, 14-21, 1973.

2 - Courtois P.J., "Decomposability - queueing and computer system applications", ACM Monograph series, Academic press, New York, 1977.

3 - Gumbel H., "Waiting lines with heterogeneous servers", Operations research 8, 504-511, 1960.

4 - Krishnamoothi B., "On a Poisson queue with two heterogeneous servers", Operations Research 11, 321-330, 1963.

5 - Pujolle G., "Applications of some Markov chains results to computer systems modelling", IRIA/LABORIA Research Report 289, 1978.

6 - Koenigsberg E., "On jockeying in queues", Management Science, 12, 5, 412-436, 1966.

7 - Glorennec P.Y., Pellaumail J., "Sur une extension de la formule de Jackson, donnant les probabilités stationnaires d'un réseau de files d'attente", IRISA Research Report 23, 1975.

8 - Chow Y.C., Kohler W.H., "Dynamic load balancing in homogeneous two-processor distributed systems", Proc. of the International Symposium on Computer Performance.

9 - Foschini G.J., Salz J., "A basic dynamic routing problem and diffusion", IEEE Trans. on Communications 26, 3, 320-328, 1978.

10 - Bhandarkar D.P., "Analytic models for memory interference in multi-processor computer systems", Research Report, Carnegie Mellon University, 1973.

11 - Baskett F., Chandy M., Muntz R., Palacios J., "Open, closed and mixed networks of queues with different classes of customers", JACM 22, 2, 1975.