KOMUNIKACIJSKI PROCESI V TRANSPUTERSKIH SISTEMIH INFORMATICA 2/87 
UDK 681.324 
Branko Mihovilovič, Peter Kolbezen, Jurij Šile 
Institut »Jožef Štefan«, Ljubljana 
Komunikacijske povezave «ed transputerji predstavljajo zaradi ceneno­
sti, enostavnosti in preproste uporabe nov standard v povezovanju 
rafiunalnikov. V prispevku so na kratko opisani oceanski konstrukti, 
ki so osnova pri natrtovanju transputerskih sistemov. Na primeru s»o 
pokazali kako pomembno vlogo igrajo komunikacijski procesi pri naKrto-
vanju transputerskih sistemov, ter kako pomembna je njihova preuredi­
tev v programu, fle belimo varno in v polni meri izkoristiti soCasno 
izvrgevanje opravil v sistemu, 
Coitimunicatlng processes in transputer systems - The transputer coaau-
nication llnk is a new standard for computer system interconnection, 
since it is a cheap, slmple and easy-to-use. This paper describes the 
occam constructs that are (undamental for transputer systems design. 
Their use is given by an example uhere some program transiormations 
are performed for the sake of achieving the advantages of cancurrent 
operating transpur system. 
1. Uvod 
Transputerji oziroma transputerski sistemi 
temeljijo na krmilno vodenem raBunanju in jih 
uvrSeamo v skupino arhitektur, katerih model 
rafiunanja je bodisi zaporedni ali soBasni kr­
milni tok C13, Ti sistemi dovolj pogumno in 
verjetno tudi uspeSno zadJrtujejo novo smer v 
razvoju rafiunalnikov pete generacije. Organi­
zacija stroja je sicer centralizirana, toda 
izrabljajafl VLSI tehnologijo je »ikro rafiunal-
nik s pomnilnikom, procesorje« in komunikacij­
skim delom narejen kot ena komponenta (flip). S 
preprostim povezovanjem takSnih komponent pa je 
molfno zgraditi visoko sposobne računalniške 
sisteme. 
Vsparedno z razvojem materialne opreme, se 
je pojavila potreba po visokei programskem 
jeziku, ki pa ne bi bil namenjen samo programi­
ranju ra(:;unalni^kega sistema, temved^ bi bil 
primeren tudi za njegovo načrtovanje. TakSne 
zahteve danes izpolnjuje samo jezik OCCAM, 
Jezik je enostaven, sloni pa na dveh konceptih: 
'soflasnasti in komunikaciji. Uporablja se enako 
dobro za opisovanje tako sistema »edseboj pove­
zanih mikroračunalnikov, kot za programiranje 
enega mikroračunalnika. 
Semantično gledano, inaoio na voljo anoSico 
pravil, ki nam služijo pri ti. transfordaoiji, 
oziroma optimizaciji prograaa. Pri slednji 
načrtovalec eksperimentalno izbira aed razliC 
nimi implementacijami programa, ki so enakovre­
dne. S tem doselJe najboljSe lastnosti načrto­
vanega sistema v pogledu soCasnosti, velikosti 
sistema in podobno. 
V OCCAM modelu je proces zaporedje akcij, ki 
jih imenujemo osnovni procesi. LoUiBO tri 
osnovne procese. Vhodni in izhodni procas 
skrbita za prenos vrednosti spremenljivk preko 
oceanskih kanalov (c ? x, c ! «), s po«o6Jo 
prireditvenega procesa pa spreminjano vrednofti 
spremenljivk (v ;= e>. Osnovne procese kombi­
niramo tako, da se le-tl v konstruktih lahko 
izvajajo sekvenfino, paralelno ali pa se v 
množlici procesov izvaja tisti proces, ki je 
prvi pripravljen. 
Element 
2. SakvenOnl konstrukt 
out 
opravlja dva sekvenfina procesa - vhodni in 
izhodni. Konstrukt 
P = <\iX. inp 7 X -> out I X -> )( ) 
zagotavlja, da se bo vhodni proces koniSal prej, 
ko bo zaCel izhodni proces, V oceanu zapisan 
program ima naslednjo obliko: 
HHILE TRUE 
VAR x: 
SE« 
inp ? X 
out ! X 
Tu velja opozoriti, da laamo v oceanu na 
voljo HHILE stavek za opisovanja ponavljajočih 
procesov. To ja povsea razunljivo, 6e veno, da 
GO TO in podobni stavki ne sodijo v druiino 
stavkov s katerinl popisujemo paralelne proce­
se. 

75 
3. Paralelni konatrukt 
Paralelni konstrukt 
na lastne« procesorju, ki je lahko enostaven 
zato pa izredno hiter (RISC). 
V sekvenCnen procesu W 
P = (^X.inp ? X -> ald ! Ca»x) -> X) 
Q « ((jY.«ld ? y -> out ! <bty> -> Y) 
R ° P II t 
/ponazorjen z naslednji« eleatntoa 
povezuje sekvenline procese. Vsak proces upora­
blja svoje spreaenljivke, aed seboj pa procesa 
koeunlcirata preko koaunikaoljskaga kanala. V 
occaau zapisan progra« iaa naslednjo obliko: 
CHAH aidi 
PAR 
UHttE TRUE 
VAR X, a, r i 
SCt 
inp ? X 
r 1= atx 
nid ! r 
HHILE TRUE 
VAR y, b,_p. 
sEa 
oiid 7 y 
p 1= b«y 
out '. p 
Vabite sta procesa P in S paralelna, ni pa 
nujno, da te<!eta so(!asno. Sotiasen proces upo­
rablja svoje spre«enljivke, katerih ne acre 
dodeljevati drugeau soSasnaau procesu. SoBasna 
procesa lahko koaunicirata saao preko kanalov. 
Po enea kanalu poteka saao ena enosaerna, 
sinhronizlrana koaunlkaclja nad dvoaa proceso­
ma. V kanalski kaaunlkacijl ne pcznaao vmesnih 
poanilnlkov (bufferiranja). 
4. SoISaani procesi 
Bodita dana procesa P in 9, ki iaata oblikoi 
P = ((iT.inp ? X -> outp I X -> X) 
Q = ()iY.lnp 7 y -> outp ! y -> Y) . 
U = <)iX.inp?x -> out!x -> inp?y -> outly -> X) 
poKKeao tiste podprocese, ki ee lahko izvršu­
jejo sobasno (dekoapozlclja). Najdeao dva para 
soCasnih procesov 
P = P1lj P2 = (inp ? X -> out ! y -> P) 
Q = aiM Q2 = (out ! y -> inp 7 X -> 8) 
in doblno 
H = Inp 7 y -> (tiX.P -> Q -> X) 
S. Prieer 
Oglejmo si iterativna polje (kvadratna areila 
transputerjev), ki je nadrtano tako, da z njia 
lahko izrafiunano a skalarnih produktov vektor­
jev v in 
nekatere 
ozlrona 
slstenlh 
izrazoa: 
l^ii^B. Na priaeru boao razlofill 
posebnosti konunlkaclj aed procesi 
transputerji v takSnea in podobnih 
Nat prlaer zapiSeao z naslednjia 
'I 
'Ti g, 
1=0 ' 
X v 
Prlaer torej reSiao z iterativni« polje« 
transputerJev, ki ga ponazarja slika 1. Vidi­
mo, da gre v bistvu za izradfun i skalarnih 
produktov aed enim vhodni« vektorje« v in • 
vektorji w, , katerih koaponente (aatrika U) so 
zapisane v posaaeznih transputerjih. ZapKiao 
sekvenco procesov, ki Jih izvajajo posaaazni 
transputerji v iterativne« polju: 
"UUT„ 
HULT, 
i(W) 
(pX.Pg -> X) 
= ((lX.P, -> P2-> P3-> P4 -> Ps-> X) 
HULT. ,,„»„- (>'X.Pe-> P,-> X) 
Poglejmo Ce obstaja eotnost sofiasnega izva­
janja teh dveh procesov. Ta eoZnost Je dana, 
saj lahko vhodni in izhodni koaunlkacijski 
proces teCeta soCasno: inp7 x in outp! y, ter 
outp! X in inp? y. Vendar po pravilih o soča­
snih procesih obstaja aed sofiasniaa prooesoaa 
potencialna dead locK stanje, kar poaani, da bi 
tudi procesa P in 8 zatla v to stanja. Oa 
preprečimo pojav dead lock stanja, noraao vsaj 
v enem paru sofiasnlh procesov en notranji 
proces zaBeti izvrSevatl pradno se zaBne fiasov-
no prekrivanje procesnega para (preaaknitev 
procesa po levi strani Časovne osi). ZapKiao 
to Se enkrat: 
(a -> P) 1.1 (b -> 8) (dead-lock) 
(a -> P) II (o -> d -> 8) » c->((a->P) II (d->9)). 
C c 
Zgornji izrazi naa povedo, da lahko nek 
proces delimo (Ce je to nogoCe) na podprooese, 
ki (Ce so med seboj povezani s kanali) tebejo 
soCasno z ostaliai podprooesl (tudi s tlstial, 
ki pripadajo drugeau procesu). Teau pravlao 
tudi dekonpozicija procesa. Heliao, da Je 
dekompozlclja hierarhična (varovanje pred dtad 
lock stanji), da aaogoCa uporabo paralelnih 
konstruktov In da so pri delitvi tisti kontfni 
procesi kar se da preprosti. Tako lahko ustva-
riao programe, ki uporabljajo visoko stopnjo 
sočasnosti; vsak enostaven proces pa se izvaja 
v V 
1 
Uft 
' 
Tr. 
1-
d 
MULT 
10 
m 
' 
d 
righl 
•-* 
1 
I J 
MULT 
i 
»i 
T 0^ 
MULT 
m(rH-l 
slika 1 

76 
kjer so 
mid. 
P = mld,, ? y 
P4' "^^fH) 
left, ? v 
Pr,= 2 := («„ v) + y 
P5 = rightj ! v 
P, = right|,„„) ! s 
Na sliki 2a je podan preprost grafni model 
prograna za eno transputersko celico. Posta­
vlja se vprašanje, kako v najboljši aeri izko­
ristiti prednosti iterativnih polj, tj. aolfno-
sti pohitrltev pri reSevanju takSnih in podob­
nih problemov. Ali povedano drugafle, zagotovi­
ti, da kar največ! celic lahko deluje sočasno. 
"I 
Z 
zgornj 
transp 
zakasn 
to, da 
terjEV 
tov) . 
proces 
transp 
soCasn 
sekven 
TakSno 
obliki 
resne 
em p 
uterj 
itev 
proč 
ne 
Sled 
a P1 
uterj 
o 
Cnifta 
tra 
jSi« preai 
rograau ug 
ih teCejo p 
pri iivaj 
esi v ostal 
teKeJo soC 
nje bi bil 
in P5 teftet 
u takSna 
Re&itev Je 
procesona 
nslornacijo 
slekon 
otovia 
rocesi 
anju 
ih n-1 
asno ( 
o not 
a soBa 
proces 
t> 
vsaj z 
bi t 
ob 
o, da 
soKas 
proces 
veri 
skal 
no ob 
sno, v 
a n> 
asovnt 
a en 
apisal 
sliki 
lahk 
no in 
a P5 
g ah 
arnlh 
pog 
endar 
aore 
za 
obhod 
i v n 
2b in 
o le v n 
da je 
kriva za 
transpu-
produk-
oju, da 
na enea 
ta teCi 
Iku aed 
zanke. 
aslednji 
8E8 i = CO FOR i>: 
SE« 
P<1) 
aci) 
=> 
SE« 
P(Q) 
SE« i°CO FOl 1-13 
S€« 
8(i) 
P(i+1) 
Q<a) 
Occaaski prograa z zgornjo transioraacijo 
dobi naslednjo obliko: 
PROČ MULT (CHAN »id, left, right) 
VA« y, v, a, z 
SE« 
lelt 1 v 
mid ? y 
8E« i = C 1 POR (» - 1 3 
SE« 
PAR 
z 1= n t v + y 
aid ! z 
right 1 v 
PAR 
lett 7 v 
mid ? y 
PAR 
z 1= « « v + y 
mid t z 
right ! v 
slika 2a slika2b 
Hkrati 
problem po 
izvajanju 
zanbni del 
imamo zap 
koaunikaci 
soCasnih 
zacijskih 
TeHavaa 
spremeni ji 
sona in do 
s transfora 
Java dead-loc 
procesov fi 
zgornjega 
oredje dveh 
jskih proceso 
procesov kaj 
telfav in s te 
e izogneao 
vke vhodnima 
daao priredit 
aci jo 
k sta 
in 
progra 
izhodn 
V 
hitro 
a do 
tako, 
komuni 
vena p 
SBO 
nja 
P5. 
ma 
ih in 
takSn 
pride 
dead-
da s 
kaolj 
roces 
reSili 
pri so 
Ce pog 
gotovia 
dveh v 
ea zap 
do sin 
lock s 
premeni 
skiaa 
a. 
tudi 
tiasnen 
ledaao 
o, da 
hodnih 
oredju 
hroni-
tanja. 
ao iae 
prooe-
V naiiem primeru najdeao dve skupini proce­
sov, ki se lahko izvršujejo soCasno. V prvi 
skupini sta procesa P^ in P2, v drugi pa so 
procesi P3, PA in PS. Grafni aodel ra sliki 2b 
prikazuje taksno strukturo soiifasnih procesov. 
Procesi Px združujejo v sebi vse potrebne 
nadzorne strukture paralelnih oziroaa soCasnlh 
procesov (sinhronizacija). V occaau zapisan 
program za n x m celic iaa sedaj naslednjo 
obliko: 
PROČ nULT (CHAN mid, left, right) 
VAR y, v, a, z 
SE8 i = C1 FOR a3 
SE« 
PAR 
left ? v 
mid ? y 
PAR 
z :° U * v + y 
aid ! z 
right ! v 
PAR 
left ? v 
• id ? y 
= > 
PAR 
SE« 
left ? a 
v ;= a 
SE« 
mid ? b 
y := b 
Prireditvena procesa %eliao loCiti od koau-
nikacijskih procesov. To bomo storili z nasle­
dnjo transformacijo. Oznafiiao s 01 in C2 
komunikacijska procesa, s P in 8 pa prireditve­
na procesa. Glede na to, da procesa C1 in C2 
ne zafineta istotSasno lahko zapičeno: 
(C1 -> P)ll (C2 -> Q) = ((01 -> P) II 02) -> « = 
C c 
(C2II (C1 -> P)) 
C 
•> a = ((C2II 01) -> P) 
C 
•> e 
(C2IJ 01) -> p -> a (CIII 02) 
c 
-> p -> « 
Ce upoštevamo zgornjo transforaacijo, dobi 
naS prograa konbno obliko: 

77 
PROČ nULT (CMAM aid, left, right) 
VAR y, v, •, I, a, b 
SE« 
lett ? v 
mid ? y 
SE« i = C1 FOR a - 13 
set 
PAR 
2 1= « » v • y 
• Id ! z 
right ! v 
PM 
left ? a 
nid 1 b 
:<• a 
t= b 
v 
y 
PAR 
z := • • 
mid ! z 
right ! v 
v + y 
KoaunlkaciJski procesi igrajo poaeabno vlogo 
pri izbiri tistih procesov, ki Jih lahko zdruz-
lao v sistene soCasnih procesov. Pokazali sao, 
da lahko soCasnosti lorniraao na dveh nivojihi 
al kjer veb transputerjev deluje soEasno, 
ter 
b) kjer na enem transputerju sofiasno poteka 
veC procesov. 
7. Litiratura 
C13 Borut RobiK, Jurij Sile, Razvrstitev novo-
generacijskih raCunalnifikih arhitektur, Inlor-
natica 10 (^) (19fi&) 1S-32. 
C2] Branko Mihovilovid!, Slavko HavrlC, Peter 
Kolbezen, Transputer - osnovni gradnik veflpro-
cesorskih sisteaov, Inforitatica 10 H) (1966) 
81-84. 
Procesiranje podatkov v zadnjih dveh progra-
nih Je popolnoaa enako, razlika pa Je v ten, da 
v zadnjem prograau ne aore priti do izpisov 
rezultata (aid • z>, predno se ne izvedeta 
vhodna soCasna procesa (left ? a, aid ? b). 
6. Z«kljue*k 
Nedvoano Je Jezik ocean . v priaerjavi s 
scrodniai Jeziki najprinernsjiii tako za opiso­
vanje strukture, kot za prograairanje tranšpu-
terskega sisteaa in njegovih koaponent. Na 
prlaeru sao pokazali ponen podrobnejše analize 
programskega dela transputerskega sisteaa) po­
sledica neustrezne Časovne razporeditve proce­
sov Je lahko neučinkovitost celotnega sisteaa. 
C33 C.A.R. Hoare, Cosaunlcating sequential 
processes, Prentice-Hall International (1985)-. 
C43 Jane Curry, Occaa solves classical opera-
tlng Eystea probleas, Ricroprocessors and Hi-
orosyste«s 8 (6) (1984) 280-283. 
C5] David Kay, Richard Taylor, Occaa - an 
overviev, Microprocesscrs and l1icrosyBteas S 
(2) (1964) 73-79. 
tbl Richard Taylor, 'Transputer coaaunicatlon 
link, Hicroprocessor and nicrosysteas 10 (4) 
(1986) 211-215. 
C?] David nay, Roger Shepherd, The transputer 
implementation of occaa, Proč. Int'l Conf . 
Fifth Generation Coaputer Systeas 1984, OHfl 
North-Holland (1984) 533-541.