EPFICIE?TCY OP MULTIPLE BUS STRUCTURE
I. Rozman, M. ColnariS, B. Stiglio
TEHHTŠKA FAKULTETA MARIBOR
* ISKRA AVTOMATIKA LJUBLJANA
UDK: 681.3.02
ABSTRACT - Analyaia of efficienoy two or more busea linked withabua llnker io ahovra in this ar-
tlole. A queueing theory ia uaed. AnalyBis exaotly valid only for ejcponential diatribution8 for
both A. andv^. It la ahown how the linking of two buaea influenoea the mean bua reaponse
time in compariaion with the architecture with oonsiats of one bus and the aame number of com-
puters that are oonnected to two buaea.
IJJTRODUCTTON
Analyais of effioienoy of multicomputer ar-
chltecturea with a common bua ia well know in
literature /1/, /2/, /3/, /4/. A model of theae
arohitecturea ia derived. An anlytical treat-
ment of thla model ia baaed on a queueing the-
ory or better on already derived equation3 for
mean time ezaiatence in the ayatem whloh i3
deaoribed by the queue M/G/l/N. V/ith the aid
of introduced approzimationa ia ahovm that re-
aulta obtained without mador toleranoe are va-
lid alao ln oasea where diatributiona are un-
eiponential i. e. in auch caaea whioh can be
treated by a queue. Por thia queue an exaot
mathematical aolution ia not knovm. Thi3 ata-
tement ia alao valid for the oalculation of
throughput /but not for the mean bua reaponae
time WN/ in the caaea where the arbiter is not
FCPS. But in all theae caaea, individual pro-
ceaaora whioh are oonneoted on a common bua
perform a atatiatically equal work. In litera-
ture /3/ ia ahovm the approzimation whlch
tranaforma a model with a atatiatically unequal
work into a model with a 8tatistically equal
work.
The problem of connetlng two or more buaea
where computera are oonneoted to eaoh bua atill
remaina an open question. The moat important
problem ia how the linking of two buaea in-
fluenoea the mean bu8 reaponoe time in com-
parialon with the arhitecture which oonaiata
of one bua and ot the same number of compu-
tera that are conneoted to two buaea.
DESCRIPTION 0P ARCHITECTURE
The linking of two bu3eB to each other ia made
for the following reasona:
- the inoreaae of the throughput of the whole
arohitecture la greater if we add ane more
bua with oonneoted oomputeraj
the realization price for a bua linker ia
low in oopariaon with the prlce of the whole
ayatem;
the fault tolerance 18 exiating.
bus 1
Common
resorces
Common
resorces
bus 2
Pioture 1: Two-Bua-Llnking
Bua linker ia an active interface which en-
ablea two-direction conmtunioation between two
bu3ea. Tn its inherent atruoture, it muat con-
tain a memory with enough capaoity. Into ti.is
memory computera vrrite measagea for the coir.pa-
tera whioh are located on t!ie other bus. A too

55
amall memory cauaes an inorease oi the reapon-
ae tirae beaou8e the meaaagea have to urait to
obtaln bus and alao have to wait that the me-
mory is empty. Therefore it is convenient that
the memory ia great enough for a two-3ide
tranamiaaion in order to permit the tranami-
asion of all oomputers from one bua to the
computera in the other bua in tHe aarae moment.
Th» bua linker alao packs mesaagea into a
block. T/hen the bua linker obtaina another bua,
it permita the transmisaion of all existing
meaaagea in the block to the eomputera to
whioh the meaaagea are addreaaed.
TKE MODEL
Searohing for the auitable model the following
auppoaltiona are made:
- bua linker aota undependently 'for each dire-
rection of tranamiaaion;
- the time vrtiich ia neceaaary for the trana-
miaaion of meaaage through the bua linker ia
ahort in oomparlaaon with the bua occupation
•time. Therefore it oan be negleoted;
- the arbiter at eaoh bus 1B FCFS;
- the bua linker aota in the aenae of bua
oooupation alway3 then when the message en-
tera ita empty memory. In caaea there are
still meaaagea in the memory (the bua linker
ia waiting for bua occupation3), the new
measage is loaded into the memory.
On the ba8ia of the above mentioned aupposi-
tiona and the queueing theory the model ia
formed.
bVl
21
Picture 2(a): Tha model for tranamiaaion of
mea8agea in the following
directiona: bu3 1 - bus 2
X
bV2
ii
lTI
Ploture 2(b): The model for transmisaion of
measage8 ln the oppoaite direotl-
on
In the model ahown on picture 2 the bua linker
ia devided into two parta - aeparately for
eaoh direction. The influenoe of one bu8 upon
the other ia expreased by the aouree which ge-
nerates the bua ocoupationa /\- BL^ or A. 3^2
aooording to the direotion of tranamlasion.
A,-,..... /l-^n are processora whioh generate
bua oooupationa for bua 1 with the mean tlme
between bua oooupatlon8 -^-7—. ^U. preaenta a
bus with the mean bua oooupation tlme ——. The
aame lmpretertation ia valid alao for bua 2.
TIIE ANALYSIS
In the analyaia of the model oijly exponential
diatributiona are taken into account for both
A and/U. . Other diatributiona oaniiot be taken
into account ezactly. In auch caaes some appro-
zimation method8 ahould be applled. The ezpo-
nential diatribution leada to the aolution of
•the quene Mi/Mi/1/N. '
The mean time of retardanee in the sya1;em ia
aolved by Perdinand /5/,/6/.
(1)
(2)
(3)
1, requeat from aource k
waiting for or being
aerviced
0, requeat aource k ia in
operational atate

56
W,
du,
lnZ.
1 -•
V du
•lnz.
i
The calculation Wi acoordlng to the equation
(4) ia diffloult. When the value N ia high,
the caloulatlon of Z^ ie not almple. In the
calculation Wi the derivation 1 Z,r is naoe-
aaary to be oalculated whioh additionaly com-
plioatea the whole procedure.
Perdinand /5/, /6/ presenta the efficiency of
eaoh element II
(i)
N
aa a probability that i
th
element ia not wai.ti.ng for or being serviced:
(i) (1)
N
(1)
(5)
U«1"1' can be ezprvaaed with the followlng ex-
preaaion:
1
Ai (6)
i
from whioh the mean bua reaponce time Wl for
the element i oan be derived (7).
(7)
u
(i)
N
If we wont to oaloulate the throughput of the
whole arohitecture according to the equation
(8),
1
(8)
VT7
ezample are equal, too.
A6
tO 2O 30 ',0 £0 60 70 80 30 100
A (7.)
Ploture 3: Wr va. % 7^.
Wr ia normative value of the mean bus reaponoe
tlme of the bua:
the oorreot result will not be obtained. The
equatlon (8) is valid only in such cases in
which eaoh ta3k obtalna the bus. In our oaae
a part of taaks ia concluded on the level of
one bua. The equation (8) involves only thoae
taaka whioh occupy another bua but does not
inolude the local oaea.
TIIE NiraERICAL REStlLTS
In the preaentation of a nuraerical calculation
two ezamples are ahovm (picture 3). They ole-
arly present all featurea whioh are typical
for a link wlth two buses. In the flrat exam-
ple two computera are oonneoted to eaoh bua.
In the aecond example four ooraputera are con-
nected to each bus.
The parametera u,, i = 1 ... 4 are equal in
the firat example.
The pararaetera u,, i = 1 ,,. B in the seoond
7\ presenta the mean arrlval of demanda in
one bua:
A
(N - L)
(10)
In the equatlon (10), L standa for the mean
time of retardanoe in the syBtem for the cfueue
M/M/l/N. This parameter can be simply calcula-
ted.
Prom the plcture 3 we oan see that the increaae
of traffio through the bua linker approximately
parabolioally prolonga V/i, The parabolicity
becoraea more aharp with the saturation.
If we oompare V/i for one processor in the two-
bua arohiteoture with that in one bua arohi-
teoture wit!i that in one bua architecture, un-

57
der the aame conditiona, we notice that IVi is
alwaya smaller in the two-bus architecture.
In the firat case, in the two bus architecture,
when u^, i = 1 ... 4 = 0,1, A = 0,1 is wr =
1,090 vrhile wp =1,320 In one bus arhitecture.
In the second caae we can notice a sirailar
difference in favour of two-bus arohiteoture.
Thia dlfference beoomea more atreased in
higher density of traffic (htgher u±). Thia
difference is oauaed by the paoking of messa-
gea into a blook.
COITCLUSION
Prom the reaulta obtained we can oonclude that
the link of two or mor« buaea ia eapeoially
effective in auoh caaes where one bus become8
aaturated. AI30 the price for the bua linker
13 not so high that it cannot juatify the re
alization of the linker. The price ia appro-
ximately 5 % ot the prloe ofthe whole arcHi-
teoture. '.Vhen we deal wlth a very highly
coupled ayatem, one bua can be devided into
several buaes which are oonneoted by bua lin-
kera. Phla leada to the so oalled cluster
arohltecture.
REFERENCES
/1/ Rozman, I., ColnariS, M.: Model multi-
proceaorake/niultiraSunalniške arhitektu-
re a akupnlm vodilom, Jiigoslovenako sa-
vetovanje o mikroproceaorsklm siatemima
MIPRO 83, Rijeka 1983, atr. 2.109-2.111.
/2/ Colnari5, H., Rozman, I.: Simulacija
raultiprooeaorakega raSunalnika a skupnim
vodilora, Jugoalovensko aavetovanje o mi-
kroprooeaorskim siatemima MIPRO 83, Ri-
jeka 1983, str. 2.32-2.38.
/3/ Rozman, I., ColnariS, M., BonaSič, D.:
Analiza ucinkovitoati arhitekture a 3kup-
nim vodilora prl atatično neenakem zaae-
danju vodtla, Jugoalovenako 3avetovanje
o mlkroprooeaorakim aistemima MIPRO 84,
Rijeka 1984, atr. 3.80-3.84.
/4/ Rozman, I., ColnariS, M.: Modeliranje
MP/MC arhitektiir a akupnim vodilom,
Jugoalovanaki mednarodni aimpozij za
raSunalniško tehnologijo in probleme
informatike, Infonnatioa 83, Ijubljana
1983, atr. 14-18.
/5/ Ferdinand, A.E.: A Statiatlcal Meohani-
cal Approach to Syatems Analyaia, IB?! J.
Rea. Develop. Sept. 1970, pp 539-547.
/6/ Ferdinand, A.E.: An Analyaie of the I.'a-
ohine Interference Model, 13?.! Siatem J.,
No 2, 1971, pp 192-202.