59
SINHRONIZIRANA PODATKOVNA PRETOKOVNA	INFORMATICA 2/92
RAČUNALNIŠKA ARHITEKTURA (I)
Keywords: parallel processing, dataflow computing,	Jurij Šile
scheduling, allocator, performance evaluation	Laboratorij za računalniške arhitekture
parallel computer architecture.	Institut Jožef Stefan, Ljubljana
Delo obravnava problem časovne optimizacije asinhronega procesiranja na omejenem številu procesorjev. Predlagamo izvirno rešitev, ki temelji na uvedbi nekaterih mehanizmov sinhronizacije v asinhrono računanje. Graf pretoka podatkov, ki opisuje asinhrono procesiranje, opremimo s časovno optimalno sprožitveno funkcijo, ki služi tako pri vlaganju grafa v računalnik, kakor tudi pri njegovem časovno optimalnejšem izvrševanju. V ta namen smo razvili hevristična algoritma pOptSinh in TOptSinh za konstrukcijo optimalnih sprožitvenih funkcij, ki po pesimistični oceni vračata optimalno rešitev v 80% primerov. Nadalje predlagamo algoritma za dodeljevanje MinGlDol in MinGIGor, ki temeljita na optimizaciji medprocesorskih komunikacij. V primerjavi z znanimi razvrščevalnirrii algoritmi dobimo s predlaganima algoritmoma boljše rezultate, kar potrjujejo analizirani primeri algoritmov za izračun hitre Fourierjeve transformacije, dinamične analize scene in LU razcepa matrike. Končno podajamo tudi zasnovo hibridne vzporedne arhitekture računalnika, ki podpira pre'dlagano preoblikovanje asinhronega računanja.
SYNCHRONOUS DATAFLOW COMPUTER ARCHITECTURE - We discuss the problem of time optimization of asynchronous processing on a limited number of processors. We present an original solution to the problem based on introduction of synchronization mechanisms into asynchronous processing. The dataflow graph describing asynchronous processing is associated with the corresponding time-optimal firing function. This function is used both for loading a dataflow graph into the computer and for time-optimal graph execution. In order to do this, we have developed two heuristic algorithms, pOptSinh and TOptSinh, which are used for optimal firing function construction. According to conservative estimates, these algorithms return optimal functions with 80% probability. Furthermore, we propose two scheduling algorithms, MinGlDol and MinGIGor, which are based on interprocessor communication minimization. These two algorithms give better results compared to some other well known scheduling algorithms. This fact is illustrated in Fast Fourier Transformation, Dynamic Scene Analysis, and LU matrix decomposition algorithms. Finally, we present a design of hybrid parallel computer architecture capable of supporting modified asynchronous computing.
1.	Uvod
Asinhrono (podatkovno vodeno) procesiranje [1,
2,	3, 4, 5, 6, 7] najlaže predstavimo z grafom pretoka podatkov [8], katerega točke ponazarjajo operacije oz. ukaze, usmerjene povezave pa so nosilke vrednosti operandov oz. podatkov. Ko v neko točko stečejo podatki po vseh njenih vhodnih povezavah, postane točka izvršljiva in prične takoj z izvrševanjem pridruženega ukaza. Pravimo, da se je točka sprožila. Ko točka konča izvrševanje ukaza, pošlje rezultat v vse svoje izhodne povezave. Graf pretoka podatkov je "strojni" jezik računalnikov, ki podpirajo podatkovno vodeno procesiranje in je rezultat prevajanja visokega programskega jezika z
enkratno prireditvijo [9, 10]. Čeprav segajo osnovne ideje, na katerih temeljijo takšni računalniki, v pozna šestdeseta leta, so šele s pojavom VLSI tehnologije postale te ideje tudi uresničljive [11, 1'2]. V osemdesetih letih so se porodili v svetu številni projekti, katerih cilj je realizacija podatkovno pre-tokovnega računalnika [13, 14, 15, 16, 17, 18].
Intuitivno si lahko zamislimo implementacijo asinhronega procesiranja tako, da je vsaka točka podprta s svojim procesorjem in vsaka povezava s komunikacijskim kanalom. Izkaže se, da ni nujno vsaki točki prirediti lasten procesor že vnaprej, saj je v danem trenutku izvršljivih le nekaj točk. Takšen pristop se je uveljavil v krožni arhitekturi, kjer se dodeli točki procesor šele tedaj, ko
60
postane slednja izvršljiva. Ker se v veliki večini algoritmov vsebovana vzporednost dinamično spreminja, ni smiselno uporabiti toliko procesorjev, kot jih zahteva maksimalna vsebovana vzporednost, saj bi bila njihova izkoriščenost nizka. Po drugi strani pa lahko povzroči pomanjkanje procesorjev občutno upočasnitev procesiranja, ker prihaja do ti. nasičenj, ko izvršljive točke čakajo v vrsti na sprostitev procesorjev. Zaradi nedeterminističnega vstopanja so točke v vrsti neurejene glede na svojo pomembnost: npr. kritična točka (tj. točka, ki bi se morala takoj izvršiti) ne more prehiteti ostalih točk, ki se nahajajo v vrsti pred njo. Nedetermi-nistično vstopanje v vrsto v splošnem podaljša čas izvrševanja grafa pretoka podatkov.
Predpostavimo, da je na voljo podatkovno pretokovni računalnik s potencialno neskončnim številom procesorjev ter izberimo poljuben graf pretoka podatkov. Denimo, da je za najhitrejšo asinhrono izvršitev izbranega grafa potrebnih vsaj m procesorjev. Tedaj označimo s Tm najkrajši čas, v katerem se ta graf izvrši na m procesorjih. Na računalniku z n < m procesorjev pa bi se v splošnem isti graf asinhrono izvršil v času Tn = Tm + ATn, kjer ATn > 0. Za nalogo si zadajmo minimizirati podaljšek izvrševanja ATn, tj. časovno optimizirati asihrono procesiranje pri n danih procesorjih.
2. Vzporedno procesiranje in arhitekture
Cilj vzporednega procesiranja in pripadajočih računalniških arhitektur [19, 20] je povečati "moč" računalnikov, tj. povečati njihovo zmogljivost in hitrost procesiranja ter odpraviti ozka grla v procesu računanja, ki so posledica von Neumannove arhitekture. Zaporedni računalniki so neučinkoviti pri reševanju nalog, ki se porajajo na področjih umetne inteligence (razpoznavanje slik in govora, ekspertni sistemi, avtomatsko dokazovanje itd.) in pri zahtevnih numeričnih izračunih (simulacija, modeliranje, grafika itd.). Zato je v zadnjih letih poseben poudarek na raziskavah novih načinov vzporednega procesiranja in programiranja [4, '21, 22] ter na vzporednih računalniških arhitekturah [19, 23, 24, 25, 26].
Eden obetavnejših načinov vzporednega procesiranja izvira iz modela podatkovno vodenega
računanja [6], ki ga podpirajo pripadajoče podatkovno pretokovne arhitekture [3, '27, '28]. Ker bo podatkovno vodeno računanje predmet nadaljnje obravnave, določimo najprej mesto pripadajočih podatkovno pretokovnih arhitektur v množici računalniških arhitektur.
2.1. Razvrstitev arhitektur
Razvrščanja se lahko lotimo z zelo različnih zornih kotov. Tako predlaga Feng ['29] razvrščanje na osnovi stopnje vzporednosti ter Händler [30] razvrščanje na podlagi stopnje vzporednosti in cevljenja1. Najpogosteje se uporablja Fhjnnova [31] razvrstitev računalniških arhitektur, ki temelji na ukaznih in podatkovnih tokovih . Arhitekture razvršča v štiri skupine: en ukazni in podatkovni tok (SISD), en ukazni in več podatkovnih tokov (SIMD), več ukaznih in en podatkovni tok (MISD) ter več ukaznih in podatkovnih tokov (MIMD). Skillicorn [32] je predlagal razširjeno Fly-nnovo razvrstitev. Na osnovi števila ukaznih in podatkovnih procesorjev, ukaznih in podatkovnih pomnilnikov ter načina njihovega povezovanja je razdelil računalniške arhitekture v '28 razredov. V razredih od 1 do 5 so podatkovno pretokovne in redukcijske arhitekture, v razredu 6 so zaporedne von Neumannove arhitekture, razredi od 7 do 10 obsegajo procesorska polja, razreda 11 in 12 sta MISD arhitekture in končno v razrede od 13 do 28 razvrsti večprocesorske arhitekture. Das-gupta [33] je odpravil nekatere pomankljivosti v Skillicornovi razvrstitvi in predlagal hierarhični sistem razvrstitve arhitektur. Treleaven [4] razvršča računalniške arhitekture glede na: organizacijo računanja, programsko organizacijo in organizacijo stroja. V slednji razvrstitvi je mesto podatkovno pretokovnih arhitektur zelo jasno opredeljeno, zato bomo v nadaljevanju to razvrstitev v grobem tudi predstavili.
2.1.1 Organizacija računanja
Faze računanja. Računanje je proces, ki ga sestavlja zaporedno ponavljanje treh faz, in sicer: izbiranje, preverjanje in izvrševanje.
Izbiranje: Določi se množica ukazov programa, ki so možni kandidati za izvrševanje. V splošnem izbira ukaza še ne pomeni njegove takojšnje
'Cevljenje iz angl. "pipelining"
61
izvršitve. Pravilo, po katerem se ukazi izbirajo, imenujemo pravilo izbiranja. Poznamo tri pravila izbiranja: brezpogojno (ukaz se izbere ne glede na njegov položaj v programu), notranje (izberejo se najglobje gnezdeni ukazi izraza) in zunanje (izbirajo se samo negnezdeni ukazi).
Preverjanje: Ugotavlja se izvršljivost ukaza, kar pomeni, da se preverja prisotnost vseli potrebnih vrednosti operandov v izbranih ukazih. Pravilo za preverjanje imenujemo pravilo izvršitve. Izvršljivi ukazi preidejo v tretjo fazo računanja. Ce ukaz ni izvršljiv, se bodisi odloži ter se izbere kasneje ali pa se zahtevajo manjkajoče vrednosti operandov.
Izvrševanje: Izvršljivi ukazi se dejansko izvrže.
Vodenje računanja. Ločimo tri osnovne načine vodenja računanja: krmilno vodeno računajo, r zahtevo vodeno računanje in podatkovno vodeno računanje.
Krmilno vodenje: Izbiranju ukazov, ki je brezpogojno, sledi izvrševanje ukaza. Torej se pri krmilnem vodenju ne izvaja preverjanja ukazov.
Vodenje z zahtevo: Ukaz se izbere (navadno po pravilu zunanjega izbiranja) tedaj, ko prej izbrani ukaz zahteva njegov rezultat. Nato se ugotovi, če so izbrani ukazi izvršljivi, če so torej znane vrednosti njihovih operandov; če vrednost operanda še ni znana, se posreduje zahteva tistemu ukazu, ki ga more izračunati. Izvršijo se vsi tisti ukazi, katerih potrebni operandi so znani.
Podatkovno vodenje: Izbiranje poteka tako, da se vsakemu ukazu dodeli procesor. Preverjanje sestoji iz sprotnega ugotavljanja vrednosti vseh vhodnih operandov, sledi mu izvrševanje vseh preverjenih ukazov.
2.1.2 Programska organizacija
Krmilni mehanizem. Krmilni mehanizem določa vpliv izvršitve nekega ukaza na izvrševanje ostalih ukazov ter je bodisi zaporedni (ukazi se izbirajo drug za drugim in se po vrsti izvršujejo), rekurzivni (posreduje se zahtevo po operandih ter sproži izvrševanje tistega ukaza, katerega rezultat je bil zahtevan) ali sočasni (ugotavlja se prisotnost vhodnih operandov ter sproži izvrševanje tistih ukazov, ki imajo na voljo vse potrebne operande).
Podatkovni mehanizem. Podatkovni mehanizem določa način, po katerem si ukazi delijo
skupne operande. Ukazi si lahko delijo skupne operande s pomočjo: vstavljene vrednosti (če je vrednost operanda znana že pred pričetkom računanja, se takoj vpiše v vse ukaze, ki jo potrebujejo), sprotne vrednosti (kopije operanda, ki se je izračunal, se posredujejo vsem ukazom, ki jim je ta operand skupen) in reference (vsi ukazi vsebujejo tudi referenco na skupen operand).
Modeli računanja. Vodenja računanja realiziramo z različnimi modeli računanja. V vsakem modelu se zrcali izvirni način vodenja računanja v obliki krmilnega ter podatkovnega mehanizma. Opredelitev različnih modelov računanja glede na podatkovni in krmilni mehanizem prikazuje slika 1.
Krmilno vodenje: Realizirati gaje mogoče z naslednjimi modeli: z zaporednim krmilnim tokom, s sočasni krmilnim tokom in s tokom krmilnih paketov.
Vodenje z zahtevo: Uporabljata se dva modela, in sicer: redukcija izrazov in redukcija grafov.
Podatkovno vodenje: Pripada mu le model računanja s tokom podatkovnih paketov.
2.1.3 Organizacija stroja
Pod izrazom "organizacija stroja" razumemo način sestavljanja in medsebojnega povezovanja osnovnih računalniških materialnih virov: procesorjev, pomnilnikov in komunikacijskih enot. Ločimo tri osnovne organizacije.
Centralizirana organizacija. Sestavljajo jo procesor, pomnilnik in vodilo med njima. To je tradicionalna von Neumannova arhitektura.
Organizacija za obravnavo izrazov. Osnovni gradniki, ki so sestavljeni iz procesorja, pomnilnika in komunikacijske enote, so povezani v pravilno strukturo.
Organizacija za posredovanje paketov. Procesna enota (več procesorjev), pomnilniška enota in komunikacijska enota so preko čakalnih vrst krožno povezane. Izvrševanje programa poteka cevljeno v obliki enosmernega pretoka paketov skozi omenjene enote, ki delujejo sočasno. Vrste opravljajo nalogo začasnega skladiščenja paketov: paketi, ki so pripravljeni za obdelavo v eni od enot, čakajo v ustrezni vrsti, dokler jih ta enota ni pripravljena sprejeti.
62
K R M I L N I
M
E
H
A
N
I
Z
E
M
s
0 č a s n
1
r
e k u r z i
v n i
Tok podatkovnih paketov
Sočasni krmilni tok
Tok krmilnih paketov
VOD EN J K Z ZAHTEVO
Redukcija izrazov
Redukcija grafov
sprotne vrednosti vstavljene vrednosti	reference
PODATKOVNI M Eli ANIZEM
Slika 1: Modeli računanja.
2.2 Podatkovno pretokovne arhitekture
Podatkovno pretokovni računalniki [2] se bistveno razlikujejo od krmilno vodenih računalnikov. Prvič: njihova struktura je zasnovana tako, da poteka procesiranje na osnovi vrednosti, nc pa naslovov spremenljivk. In drugič: v podatkovno pretokovnih računalnikih ni ničesar, kar bi bilo podobno programskemu števcu, saj postanejo operacije izvršljive ta.koj, ko so na voljo vsi potrebni vhodni operandi. Torej temeljijo ti računalniki na načelih asinhronosti in funkcionalnosti [34],
2.2.1 Podatkovno vodeno računanje
Model, s katerim realiziramo podatkovno vodeno računanje, je tok podatkovnih paketov. Opredeljujeta ga sočasni krmilni mehanizem ter podatkovni mehanizem s sprotnimi in vstavljenimi vrednostmi. Računanje se odvija s pomočjo podatkovnih paketov2. Ukazi sestojijo iz operacij, operandov
2Uporablja se tudi izraz žeton (iz angl. "token")
(vstavljene ali sprotne vrednosti) in kazalcev na neposredne naslednike. Ukaz se prične izvrševati takoj, ko mu je zadnji od neposrednih predhodnikov poslal podatkovni paket.
Podatkovno vodeno računanje si ilustrirajmo s primerom 2 = (x + 2) * (x — y), x = 3,7... in y — 1, 6,3 ..., ki je prikazan na sliki 2.
2.2.2 Graf pretoka podatkov
Strojni jezik podatkovno pretokovnih računalnikov je graf pretoka podatkov (G P P) [8], ki je posebna oblika Petrijeve mreže [35]. Točke v GPP ponazarjajo operacije, usmerjene povezave pa so nosilke podatkovnih paketov (vrednosti operandov). GPP je rezultat prevajanja visokega podatkovno pre-tokovnega jezika (Val, Id, Lucid, Sisal, Valid itd.) [9]. Osnovni jezik strojnega nivoja v podatkovno pretokovnih arhitekturah je torej GPP. Izvrševanja programa si zatorej predočimo s pretokom podatkov v GPP. Ko v neko točko stečejo
63
st_dev
Slika, 3: GPP funkcijo Statistika.
podatki po vseh njenih vhodnih povezavah, postane točka izvršljiva in prične takoj z izvrševanjem pridružene operacije. Pravimo, da se je točka .sprožila. Ko točka izvrševanje konča, pošlje podatkovne pakete (rezultat) v vse svoje izhodne povezave. Samoumevno je, da. stoji za. vsako točko procesni element in za vsako povezavo komunikacijski kanal.
Za ilustracijo vzemimo še fukcijo Statistika, ki vrne srednjo vrednost sr_vred in standardni odklon st_dev vhodnih spremenljivk x, y in z. Zapis funkcije v visokem podatkovno pretokovnem jeziku Val [10] je naslednji:
function Statistika ( x,y,z: real returns real, real);
let
sr_vred := (x + y + z)/3;
st_dev := SQRT((x**2 + y**2 +
z**2)/3 - sr_vred**2);
in
sr_vred, st_dev endlet endfun .
V primeru izračuna funkcije Statistika smo dobili aciklični G P P. Tedaj ko v algoritmih nastopajo ponovitve (iteracije), pa se srečujemo s cikličnimi G PP. Vzemimimo npr. izračun fakto-
64
riele števila n. Ustrezen program za. izračun n! bi se zapisal v visokem podatkovno pretokovnem jeziku Id kot (GPP prikazuje slika 4):
( initial j <- n; k <- 1 while j > 1 do
new j <- j - 1; new k <- k ♦ j ; return k )
Slika. 4: GPP za izračun n!.
Če primerjamo GPP za izračun funkcije Statistika (slika 3) z GPP za izračun n! (slika, 4), opazimo, da se v slednjem poleg zank pojavljajo tudi pogojni konstrukti ter da se po neka.-terih povezavah pretakajo tudi podatki, ki predstavljajo logični vrednosti T in F.'V splošnem so povezave nosilke različnih tipov podatkov: integer, real, boolean itd..
Pri cikličnih GPP pogosto nastanejo dodatne težave. Kadar v posamezni ponovitvi zanke naletimo na podatkovne odvisnosti med operacijami, to ne ustavi nadaljnjih ponovitev, čeprav predhodna ponovitev ni v celoti končana. Tako se v določenih povezavah podatki prekrivajo. Vzemimo za primer naslednji segment programa:
input a
a[0] = 1 b[0] = 1 for i from 1 to n begin
a[i] = i + a[i-l] b[i] = a[i] * b[i-l]
end output b
Predpostavimo, da, je za seštevanje potrebna 1 časovna enota in za množenje 2 časovni enoti.
Pričakovani rezultat bi bil: b [0] = 1, b[l] = 2, b[2] =8, b[3] = 56 itd. Dejansko pa bi dobili naslednje rezultate: b[0] = 1, b[l] =2, b[2] = 14, b [3] = 308 itd. Oglejmo si nekaj prvih korakov izvajanja programa. Zaradi hitrejšega izvrševanja zanke pri seštevanju se nekateri elementi vektorja a [i] preprosto prekrijejo. Ta.ko se a[2], ki je bil v trenutku t = 2 še 4, prekrije z vrednostjo 7, še preden se uporabi kot fa,ktor pri izračunu b[2].
2.2.3 Statični in dinamični modeli računanja
lz zadnjega primera vidimo, da ni mogoče s prisotnostjo kateregakoli podatka razglasiti točke za izvršljivo, saj v splošnem pripadajo vhodni podatki različnim delom izračuna. Obstaja nekaj rešitev nastalega, problema oz. modelov podatkovno vodenega. računanja, ki vplivajo tudi na izvedbo podatkovno pretokovnega računalnika.
Model 1: Vsaka ponovitev zanke se sme pričeti šele teda.j, ko se je predhodna končala. Ta model [11] ne dovoljuje vzporednosti med ponovitvami in zahteva dodatno ugotavljanje konca ponovitve.
Model 2: V vsaki povezavi GPP dovoljujemo istočasno le en podatkovni paket [1], To pomeni, da. se sme točka sproži le tedaj, ko so prisotni podatkovni paketi v vseh vhodnih povezavah in ni v izhodnih povezavah nobenega podatkovnega paketa.. Takšno pravilo izvršitve uresničimo s pomočjo potrditvenih signalov. Prednost tega modela je, da omogoča cevljenje, slabost pa, da se število povezav podvoji.
Model 3: Ciklični GPP transformiramo tako, da vsako ponovitev opišemo z acikličnim podgrafom. Takšen model zahteva večje programske pomnilnike in sprotno generiranje koda v primeru, ko je izstop iz zanke izračunan šele v času njenega izvajanja. Ti zahtevi se odražata kot resna pomankljivost v praktičnih sistemih.
Model 4: Podatkovne pakete opremimo z dodatnimi oznakami3 [15, 36], ki vsebujejo indeks oz. nivo ponovitve. Točka se sme sproži le tedaj, ko imajo vsi vhodni podatkovni paketi enako oznako. Ta model zahteva, povečan pretok po GPP ter mehanizme za primerjanje oznak.
Model 5: Povezave v GPP opravljajo tudi funkcijo vrste [37], kar pomeni, da so v njih podatkovni paketi ravrščeni v istem vrstnem redu, kot
3V angl. literaturi imenujejo tak paket "tagged token".
65
P-2 Pa
al
61 |cl[ a!2 1/2 |c2| "^3
l>:\
b> 1 c1
«8
68 c8
rti	«2		ali		a 4		rt5		a 6		ri 7		a 8			
	b 1		b 2		M		M		b',		60		b 7		68	
		c 1		c'2		c.'S		H		r:5		'Ji		cl		c 8
l\
al	a 5	61	65	cl c2 c.'i cA c5 cO cl c8
a 2	«6	62	66	
aA	al	6,'i	67	
cA	rt8	b'1	68	
P1	«I	rt 5		cl	c'2	cl	cA	c 5	c6 cl	cS
P-2	a'2	61	62		M		66		68	
PA	a\\	a 6		b:t			5	6	7 |	
Pa	a'1	a. 7			a 8					
i_i_i_:_i_:__i_i_:_n_L
n	5	10	1.')	20	25	45
Slika 5: Primerjava, modelov podatkovno vodenega računanja.
so vstopali v povezave'1. Takšen model omogoča, enako stopnjo vzporednosti kot model z označenimi pa.keti, le da je izvedba, čakalnih vrst cenovno zelo zahtevna.
Primerjavo navedenih petih modelov podatkovno vodenega računanja si oglejmo na naslednjem testnem programu [5]:
input d, e, f
c [0] =0 for i from 1 to 8 begin
a[i] = d [i] / e [i] b[i] = a [i] * fCi] c[i] = b[i] + cCi-1]
end
output a, b, c
Predpostavimo, da so potrebne za deljenje tri, za množenje dve in za seštevanje ena časovna enota. Zamislimo si podatkovno pretokovni računalnik s štirimi procesorji Pi, P2, P3 in P,\, ki izvajajo katerokoli od potrebnih operacij. Ideatizi-
4 Povezave so FIFO vrste.
raj m o računalnik tako, da ne bo zakasnitev v pomnilniku in pri medprocesorskih komunikacijah. Nadalje definirajmo pospešitev računanja SP in izkoriščenost procesorjev Ep, s katerima bomo merili kvaliteto računalnika. Ce je Ti čas potreben za zaporedno izvrševanje programa in Tp čas izvrševanja istega programa na p procesorjih, potem je
Za naš testni program bi dobili 7\ = 48. V tabeli 1 so povzeti rezultati primerjave posameznih modelov podatkovno vodenega računanja. Podrobnejša analiza je prikazana tudi na sliki 5.
Model 1: Tak model nas pripelje do zaporednega izvajanja programa, saj se naslednja ponovitev sme pričeti šele, ko se predhodna konča. Za takšno izvrševanje zadošča en procesor (slika 5a).
Model 2: Ker dovoljujemo v povezavah istočasno le en podatkovni paket, nas to privede do cevljenja prireditvenih stavkov znotraj zanke. Za takšno izvrševanje bi zadoščali že trije procesorji (slika 5b).
66
p = 4	Iv	S,	Ev
Model 1	48	1	.250
Model 2	27	1.77S	.444
Modeli 3,4,5	14	3,129	.8.57
Tabela, i: Primerjava modelov podatkovno vodenega računa,nja..
Modeli 3, 4, 5: Najboljše rezultate dobimo pri statičnem računanju z razvitjem zank ter pri obeli dinamičnih modelih (slika 5č).
Za,radi primerjave je na, sliki 5c prikazan tudi potek računanja na. vektorskih računalnikih [19]. Med prevajanjem testnega programa, bi se prva dva, prireditvena, stavka, v zanki vektorizira.la., tako da bi
dobili 7; = 18,5p
2.067 in Ep = 0.607.
2.2.4 Modeli računalnikov
Z razvojem VLSI tehnologije so posta.le uresničljive mnoge ideje v računalniških arhitekturah non-von Neumannovega tipa,. Tako je bilo v zgodnjih osem deseti h letih mogoče realizirati tudi prve podatkovno pretokovne računalnike. Dober pregled in primerjavo zgodnjih podatkovno pretokovnih arhitektur je podal Srini v delu [27], Nekatere novejše arhitekture pa so predstavljene v [38, 28, 39, 40, 7]. Podatkovno pretokovno računanje (statično in dimanično) običajno uresničimo na računalnikih, ki temeljijo na. organizacijah za posredovanje paketov. Oglejmo si arhitekturi, ki sta značilni za statični in dinamični model podatkovno vodenega, računanja,.
Statična arhitektura. V statični arhitekturi (slika. 6) je uporabljen sinhronizacijski mehanizem, ki temelji na shranjevanju paketov. Podatkovni paketi se shranjujejo v uka.ze, ki se izvrše, ko prejmejo vse vhodne operande. Ukazi se nahajajo v pomnilniku in vsebujejo: operacijo, prostor za. vhodne operande in kaza.lce na neposredne naslednike. Enota. za. ažvriranje hrani naslov ukaza ter števec manjkajočih vhodnih opera.ndov (podatkovnih paketov). Podatkovni pa.ket, ki zapusti procesno enoto, vsebuje poleg rezultata tudi naslov ukaza, ki mu je namenjen. Enota za ažuriranjc posreduje rezultat ustreznim uka.zom v pomnilniški enoti ter zmanjša števec manjkajočih vhodnih opre-ra.ndov za ena.. V primeru, ko pa.de števec na nič, posreduje naslov ukaza enoti za dostavo. Leta pešljc naslovljeni ukaz iz pomnilnika v procesno enoto.
Značilni prestavniki statičnih arhitektur so: SDFiVI5 (Tehnološki institut Massachusetts, ZDA) [1], LAU'1 večprocesorski sistem (CERT - Toulouse, Francija) [Fl], DDP7 (Texas Instruments, ZDA) [13], /¿PD72818 (NEC, Japonska) [11] itd..
enota za primerjanje		, (
		' k
		
C
<
podatkovni paketi
podatkovni paketi
pomnilnik			
			
enola za doatavo in ažuriranje			
			
—\
ukazi	1
Slika 7: Dinamična arhitektura.
Dinamična arhitektura. Za razliko od statične arhitekture je v dinamični arhitekturi (slika 7) uporabljen sinhronizacijski mehanizem, ki temelji na primerjanju paketov. Ustrezno označeni podatkovni paketi, ki zapustijo procesno enoto, se zbirajo v množicah v enoti za primerjanje. Množice so opremljene z naslovi pripadajočih ukazov v pom-
bStatic Dataflow Machine.
Slika 6: Statična arhitektura.
6 "Language a assignation unique" pomeni jezik z enkratno prireditvijo.
' Distributed Data Processor.
8 Prvi VLSI podatkovno pretokovni mikroprocesor.
67
nilniku. Enota za, primerjanje razporeja prispele pakete v množice glede na njihove oznake. Ko se množica napolni, se vsi paketi prenesejo v enoto za dostavo in ažuriranje. Le-ta združi prispele pakete s pripadajočim ukazom iz pomnilnika, ter jih posreduje procesni enoti.
Med dinamične arhitekture uvrščamo: TTDFM9 (Tehnološki institut, Ma.ssa.chusett,s, ZDA) [41], M DFC10( Univerza v Manchestru, Velika Britanija) [16], PIM-D11 (ICOT, Japonska) [42], PATTSV12 (Univerza v Queenslandu, Avstralija) [43] itd..
Slika 8: Hibridna arhitektura.
Hibridna arhitektura. Poleg omenjenih statičnih in dinamičnih arhitektur se predvsem v zadnjem času pojavljajo mnoge izvedbe arhitektur, ki jih ni mogoče uvrstiti v omenjeni dve skupini. Za, te arhitekture je značilna, organizacija, ki jo prikazuje slika 8. GPP se porazdeli med strukturne pomnilnike ob posameznih procesnih elementih. Procesni elementi izvršujejo pripadajoče dele GPP ter preko nadzorno - povezovalne enote izmenjujejo podatkovne pakete, pripadajoče delom GPP, ki se nahajajo v drugih strukturnih pomnilnikih. Izvrševanje GPP poteka, bodisi statično bodisi dinamično.
Nekateri novejši računalniki iz tega razreda so: HDFM13 (Hughes Aircraft Co., ZDA) [17], Sigma-11'1 (Electrotechnical Laboratory, Japonska) [18], EPSILON-215 (Sandia National Laboratories,
9Tagged-Token Dataflow Machine
'"Manchester Dataflow Computer.
11 Parallel Inference Machine.
12Processor Array Tagged-Token System.
13llughes Dataflow Multiprocessor (statična arhitektura).
14Dinamična arhitektura.
15Ilibridno krmilno-pedatkovno vodeno računanje.
ZDA) [44], Monsoon16 (Tehnološki institut Massachusetts, ZDA) [45] itd..
3. Motivacija in opis problema
Maloprej smo videli, da se tako v statičnih kot v dinamičnih arhitekturah izvršljivi podatkovni paketi (ukazi) preko vrste dodeljujejo procesorjem. Zal pa ima procesna enota omejeno število procesorjev, zato se v primeru, ko so vsi procesorji zasedeni, paketi kopičijo v vrsti pred procesno enoto, kjer čakajo na, svojo izvršitev. Posledica takšnega čakanja je lahko občutno upočasnjeno izvrševanja, GPP. Da se temu izognemo, je potrebno bodisi povečati število procesorjev v procesni enoti ali pa zagotoviti ustrezen način vstopanja paketov v čakalno vrsto (ali izstopanja iz vrste) pred procesno enoto in ustreženo dodeljevanje paketov prostim procesorjem.
3.1 Primer računanja FFT
Problem upočasnjenega izvrševanja GPP, ki nastane zaradi pomanjkanja procesorjev, osvetlimo s primerom izračuna hitre Fourierjeve transformacije (FFT) na 8 točkah (slika 9).
A I Q •s(0) v(@>--7(§\--5(°)
•s (4)	/V®-"•¿'(1)
•s(2)	-S(2)
•s(6)	-^VVV^-5(3)
.«(i)«k v(©v——
s(5)	/VV1©-~ S(5)
s(:i)	-
Slika 9: GPP za FFT z 8 točkami.
, Osnovni operaciji sta seštevanje (označeno z ®) ter odštevanje in množenje (označeno z ®). Če sta Im in ¡n vhodna podatka, potem velja
lm ® In — Im ~(" /i 10 Dinamična arhitektura.
68
in
Im®In = (Im - In) x e2nikl%, O < k < 7.
Predpostavimo, da je za izvršitev operacije © potrebna 1 časovna enota in za izvršitev operacije ® 5 časovnih enot. Potem je čas potreben za zaporedno izvrševanje FFT algoritma T\ = 72 časovnih enot. Vzporedno izvrševanje algoritma bi ob predpostavki, da imamo na voljo neomejeno mnogo procesorjev, zahtevalo le T^ = 15 časovnih enot. Torej je idealna pospešitev FFT algoritma
št.
proce.sorje\ 8
4 -
5	10	15 čas
3.1.2 Primer 1: Premalo procesorjev
Naj bo dan podatkovno pretokovni računalnik s tremi procesorji P\, P2 in P3, ki morejo izvajati katerokoli od operacij © in ©. Idealizirajmo računalnik tako, da ne bo zakasnitev v pomnilniku in pri medprocesorskih komunikacijah. Predpostavimo statično arhitekturo (slika 6), ki podpira podatkovno pretokovno računanaje opredeljemo z modelom 3. Točke GPP bi se porazdelile med procesorje P\, P2 in P3, kot je prikazano na sliki 10. Za ta primer dobimo Tp = "25, Sp = 2.8S in Ep = 0.96. Pospešitev Sp je manjša od S^.
Slika 11: Dinamična vzporednost FFT algoritma.
Pi EElED QU) ED
P2 I b I 1. I x j P3 IC| K iS I	j
1 D INI	V 1
	
IKLMI U 1	
	
1 F 1	P 1
	
kil O 1	w 1
1 H |	
l-1-1-1-1-1-1-V
0	5	10 15 20 25 30 35
P\ IAI D I H Ml O IHI V I P2 I B Iclrl K IN-I P IS I W 1 P3 IclEl F IJI L M U hI X I
I-1-1-1-1-i-,-
O	5	10 15 20 25 30 35
Slika 10: Izvrševanje FFT pri p = 3.
3.1.2 Primer 2: Optimizacija procesorjev
Predpostavimo enako arhitekturo kot v primeru 1, le da vsebuje procesna enota neomejeno mnogo procesorjev. Naj nam bo število delujočih procesorjev v trenutku t merilo vzporednosti algoritma v tem trenutku. Za FFT algoritem je prikazan časovni potek vzporednost na sliki 11. Opazimo, da vzporednost-niha med 1 in 8 ter daje povprečna vzporednost enaka idealni pospešitvi algoritma S00 = 4.8. Postavlja se vprašanje, koliko procesorjev p bi zadoščalo, da bi veljalo Sp = Soo- Ce bi se odločili za število procesorjev, ki je določeno z maksimalno vzporednostjo, tj. p = 8, bi dobili rezultat, ki je prikazan na sliki 12.
Dobimo Tp = 15 in Sp = 4.8. S tem smo zagotovili, daje Sp = Soo, žal pa je izkoriščenost procesorjev le Ep — 0.6. Ep je mogoče povečati le tako,
Slika 12: Izvrševanje FFT pri p — 8-
da uporabimo manj procesorjev. Sedaj je mogoče uvesti prvi problem, ki ga želimo rešiti, tj. optimizacija procesorjev.
Optimizacija procesorjev: Za dani GPP moramo določiti takšno število procesorjev p, da bo Sp = Soo <Ja bo Ep čim bliže 1.
Morda bi zadoščalo, če bi vzeli toliko procesorjev, kot jih določa povprečna vzporednost S^. V našem primeru bi bilo p = [S^] =5. To možnost prikazuje slika 13. V tem primeru je rezultat naslednji: Sp = 4.235 in Ep = 0.847, kar pomeni, da je Sp < Soo-
Pojavi se vprašanje, ali bi bilo mogoče zagotoviti ustrezen način vstopanja paketov v čakalno vrsto (ali izstopanja iz vrste) pred procesno enoto in s tem takšno dodeljevanje paketov prostim procesorjem, da bi uspeli v primeru p = 5 zagotoviti tudi SP = Sqq. V našem primeru je to mogoče, kar prikazuje slika 14. Rezultat, ki ga dobimo po takšni optimizaciji, je: Sp = 4.8 in Ev = 0.96.
Postopek optimizacije procesorjev bomo opisali v
69
IAI F IJI P	1 X 1
	
1 ¡3 Kil L 1	vv 1 :
/Ji P2
P3 IclčiTTT
Pa
~—r
D
hud
PS IKI H IN 10IRI v I
10
15
20
25
Slika 13: Izvrševanje FFT pri p
30
o.
—
35
P\ P2 Pi P*
Ps lAlclKblMlNlllJlOlHl.Shl
1 H	1 P	1 X 1
		
1 F	1 O	1 w 1
		
1 d	1 l	1 v 1
		
1 B	1 K	1 u
10
15
20
25
30
—V-
35
Slika 14: Optimizirano izvrševanje FFT pri p = 5. nadaljevanju.
3.1.3 Primer 3: Optimizacija časa
Tudi sedaj predpostavimo enako arhitekturo kot v primeru 1; torej podatkovno pretokovni računalnik s p = 3 procesorji Pi, P> in /3. Upeljimo najprej upad idealne pospešitve računanja. Dp, ki ga definiramo kot
/-) _ ^CO — S p
UP - s„
V primeru 1 dobimo Dp = 0.667, kar pomeni 66.7% upad idealne pospešitve. Tudi tokrat je mogoče zagotoviti ustreznejši način vstopanja paketov v čakalno vrsto (oz. izstopanja iz vrste) pred procesno enoto in s tem zagotoviti manjši upad idealne pospešitve. Rešitev prikazuje slika 15. Rezultat, ki ga dobimo po takšni optimizaciji, je: Sp — 3, Dp = 0.6. V tem primeru dobimo tudi Ev = 1, kar pomeni, da smo dosegli tudi največjo izkoriščenost procesorjev. Ker se bomo v nadaljevanju še sklicevali na to rešitev, jo poimenujmo "optimalna".
Uvedimo sedaj drugi problem, ki ga želimo rešiti, tj. optimizacija časa.
Optimizacija časa: Za dani GPP in dano število procesorjev p, moramo določiti takšno dodeljevanje, da bo Dp čim bliže 0.
Poizkusimo problem optimizacije časa še nekoliko zaplesti. Vzemimo sedaj hibridno arhitekturo
Pi C P-2 C Ps C
103
TTTkT
ZET
ZEJ
~IČTAT
w
o
10
20
25
30
35
Slika 15: Optimalno izvrševanje FFT pri p =
:s,tc = 0.
(slika S). Število procesorjev naj ostane p = 3, predpostavimo pa, da je za medprocesorsko komunikacijo tc potrebnih 5 časovnih enot. Dodeljevanje procesorjev, kot je bilo v primeru "optimalne" rešitve, rezultira v Sp = '2.25, Dp = 1.133 in Ep = 0.75 (slika 16).
i\ C
Pi C P3 C
IEEE]
TiTfn
"FT
m
IČlAl
ZEED I v I
o
10
15
20
25
30
35
Slika 16: Izvrševanje FFT pri p = 3,/c = 5.
S primernim dodeljevanjem procesorjev je mogoče doseči določene izboljšave. Tako npr. z rešitvijo, ki je podana na sliki 17, dosežemo Sp = 2.4, Dp = 1 in Ep = 0.8. Za izboljšanje Dp gre zahvala predvsem zmanjšanju medprocesorskih komunikacij. Uporabljenih je le 14 medprocesorskih komunikacij, medtem ko jih je bilo v prejšnjem primeru kar 24.
Pi P7 P3
1 II	ICIAI 1	p	1 K 1	X 151
				
1 n	1 B 1	I.	n	1 u MrRI
				
1 F	1O1KI O	N	1.1 M v	1 w i :
10
15
20
25
30
35
Slika 17: Optimizirano izvrševanje FFT pri p = 3, tc = 5.
Tudi postopek optimizacije časa bomo opisali v nadaljevanju.
3.2 Primerjava rešitev
Iz dosedanje analize (tabela 2) vidimo, da tako problem optimizacije procesorjev kakor tudi optimizacije časa uspešno rešimo le, če zagotovimo ustrezen način dodeljevanja paketov prostim pro-
70
ccsorjem (proko čakalne vrste), oz. zagotovimo ustrezno porazdelitev GPP med procesorje. Kot bomo videli kasneje, je to moč doseči le s preoblikovanjem podatkovno vodenega računanja.
p	'c	tp	Sp	Op	ep	vodenje računanja
8 5 3	0 0 0	15 17 25	4.8 4.235 2.88	0 0.133 0.667	0.6 0.84? 0.96	podatkovno podatkov no podatkovno
5 3	0 0	15 24	4.8 3	0 0.6	0.96 1	mod. podatkovno mod. podatkovno
3	5	33	2.182	1.2	0.727	podatkovno
3	5	30	2.4	1	0.8	mod. podatkovno
Tabela 2: Primerjava računanja FFT.
3.3 NP-polnost problema
Sedaj bomo spoznali, da je problem optimizacije časa NP-poln. Neposredna posledica tega. je tudi NP-polnost problema optimizacije procesorjev. Ti dejstvi sta pomembni, saj opravičujeta uporabo hevrističnih metod pri reševanju obeli problemov.
Kot vemo, je AfV razred problemov, ki so nedeterministično rešljivi v polinomskcm času (in zato deterministično rešljivi v eksponentnem času). Nekateri med njimi so deterministično rešljivi celo v polinomskcm času in tvorijo razred V. Seveda je V C AfV■ Odprto pa je vprašanje, ali je V ^ AfV. Zato ne vemo, ali obstaja problem, ki je deterministično rešljiv v eksponentnem, ne pa tudi poli-nomskem času.
Nekateri problemi iz razreda. AfV imajo še posebej zanimivo in pomembno lastnost, ki se kaže v tem, da moremo reševanje kateregakoli problema iz AfV v polinomskem času prevesti na reševanje kakega od teh odlikovanih problemov, imenovanih NP-polni problemi. V tem smislu so NP-polni problemi med najtežjimi v razredu AfV. Če bi nam uspelo pokazati za vsaj enega izmed njih, da je deterministično rešljiv v polinomskem času, bi s tem pokazali, da je v polinomskem času rešljiv vsak problem iz AfV. Kljub velikim naporom pa doslej kaj takega še nikomur ni uspelo, čeprav zbirka znanih NP-polnih problemov šteje že nekaj sto problemov. Zato prevladuje prepričanje, da NP-polni problemi v resnici niso deterministično polinomsko rešljivi. Praktična posledica tega pa je, da se v primeru, ko na,letimo na. NP-poln problem, vedemo pragmatično, torej ne iščemo polinomskega algoritma (zaradi majhne verjetnosti, da bi ga našli), ampak raje pričnemo sestavljati hevristični algoritem.
Problem optimizacije časa ter problem op-
timizacije procesorjev soadata v razred NP-polnih problemov! Prvi se v literaturi pojavlja pod imenom dodeljevanje urejenih opravil (PCS17) v naslednji obliki
Na j bo Jana množica V — {«],..., ?;„} opravil dolžine 1, ki so urejena, z relacijo i—► stroge delne urejenosti, p € IN procesorjev ter mejni čas T € IN. Ali obstaja, takšna, preslikava, s množico V v množico {0,1,..., Tj, da za vse t € {0, 1,..., 7'}
ter ?/,, v £ V velja. ) .s-1 ( t ) | < p in hkrati ?i i-- v =>
s(?/.) < *(?,') ?
Dokaz NP-polnosti problema PCS je podan v [46], Ker imajo vsa opravila enako časovno zahtevnost, je PCS le posebna oblika problema optimizacijo časa - torej je slednji gotovo NP-poln. NP-polnost problema optimizacije procesorjev pa, pokažemo tako, cia nanj polinomsko časovno prevedemo problem PCS [47]. Če namreč nek NP-poln problem A polinomsko časovno prevedemo na problem 13 6 HV, potem je (zaradi tranzitivnosti ■relacije polinomsko prevedljivosti) tudi B NP-poln.
3.3.1 Reševanje NP-polnih problemov
Kot smo uvodoma omenili, imajo najboljši znani algoritmi za, reševanje NP-polnih problemov vsi eksponentno časovno kompleksnost. Zaradi hitre rasti eksponentne funkcije to običajno pomeni, da ne znamo dobiti optimalnih rešitev že pri relativno majhnih problemih. Eden od pristopov k reševanju NP-polnega problema je zato pospešitev danega, algoritma, tj. pospešitev pregledovanja množice možnih rešitev. Takšen pristop ponuja delno rešitev ter sproti preverja, ali le-ta vodi do optimalne rešitve. Kadar temu ni tako, delno rešitev opusti ter sestavi kako drugo" delno rešitev. Med takšne pristope spada, npr. razveji in omeji.
Drug pristop pri reševanju NP-polnega problema je razvoj algoritma, ki v sprejemljivem času vrne rešitev, ki usreza danim zahtevam. Takšni algoritmi se imenujejo hevristični. Dve družini hevrističnih algoritmov obsegata aproksimacijske ter verjetnostne algoritme. Aproksimacijski algoritmi vračajo rešitve, za katere je znano, koliko največ utegnejo odstopati od optimalne reštve. Verjetnostni algoritmi [48] pa ob polinomski časovni zatevnosti dovolj pogosto (z določeno verjetnostjo) vračajo optimalne rezultate. Slednji bodo
17 Prccedence Constrained Schedulir.,
71
uporabljeni pri reševanju problemov opt,irniza.cije časa, in optimizacije procesorjev.
Literatura
[1]	J. B. Dennis. The Variaties of Data Flow Computers. In Proc. First Int'l Conf. Distributed Comp. Sys., pages 430-439, October 1979.
[2]	J. B. Dennis., Data Flow Supercomputers. IEEE Computer, 13(11 ):48-56, November 1980.
[3]	S. Ribaric. Racunari upravljani tokom podataka. Informática, 6(4):3-ll, 1982.
[4]	P. C. Trelcaven, D. R. Brownbridge, and R. P. Hopkins. Data-Driven and Demand-Driven Computer Architectures. Computing Surveys, 14(1 ):93-143, March 1982.
[5]	J. Silc in B. Robic. Osnovna nacela DF sist.emov. Informática, 9(2): 10-15, 1985.
[6]	J. B. Dennis. Dataflow Computation: A Case Study. In V. M. Milutinovic, editor, Computer Architecture - Concepts and Systems, pages 354-404. North-Holland, 1988.
[7]	L. Bic and J. L. Gaudiot. Special Issue on Data-Flow Computing. Journal of Parallel and Distributed Computing, 10(4):277-385, December 1990.
[8]	A. L. Davis and R. M. Keller. Data Flow Program Graphs. IEEE Computer, 15(2):26-41, February 1982. '
[9]	W. B. Ackerman. Data Flow Languages. In Proc. National Comp. Conf., pages 1087-1095, June 1979.
[10]	J. R. McGraw. Data-Flow Computing: The VAL Language. ACM Trans. Prog. Languages and Systems, 4(l):44-82, January 1982.
[11]	T. JefTery. The //PD7281 Processor. Byte, pages 237-246, November 1985.
[12]	S. Weiss, I. Spillinger, and G. M. Silherman. Architectural Improvements for Data-Driven VLSI Processing Arrays. In Proc. Functional Programming Languages and Computer Architecture, pages 243259, September 1989.
[13]	M. Cornish. The TI Dataflow Architecture: The Power of Concurrency for Avionics. In Proc. 3rd Conf. Digital Avionics Systems, pages 19-25, November 1979.
[14]	D. Comte, N. Ilifdi, and J. C. Syre. The Data Driven LAU Multiprocessor System: Results and Perspectives. In Proc. World Comp. Congress IF IP'80, pages 175-180, October 1980.
[15]	J . Gurd and I. Watson. Preliminary Evaluation of a Prototype Dataflow Computer. In Proc. 9th. World Comp. Congress IFIP'83, pages 545-551, September 1983.
[16]	J. R. Gurd C. C. Kirkham, and I. Watson. The Manchester Prototype Dataflow Computer. Comm. ACM, 28(l):34-52, January 1985.
[17]	R. Vedder, M. Campbell, and G. Tucker. The Hughes Data Flow Multiprocessor. In Proc. 5th Int'l Conf. Distributed Computing Systems, pages 2-9, May 1985.
[18]	T. Shimada, K. Hiraki, K. Nishida, and S. Sekiguchi. Evaluation of a Prototype Data Flow Processor of the SIGMA-1 for Scientific Computations. In Proc. 13th Annual Int'l Symp. Comp. Arch., pages 226-234, June 1986.
[19]	K. Hwang and F. A. Briggs. Computer Architecture and Parallel Processing. McGraw-Hill Book Company, 1984.
[20]	B. Robič in J. Silc. Razvrstitev novogeneracijskih računalniških arhitektur. Informática, 10(4): 18—32, i 986.
[21]	N. Gchani and A. D. McGettrick, editors. Concurrent Programming. Addison-Wesley Publishing Comp., 1988.
[22]	G. S. Almasi and A. Gottlieb. Highly Parallel Computing. The Benjamin/Cummings Publishing Comp., 1989.
[23]	V. M. Milutinovic, editor. Computer Architecture - Concepts and Systems. North-Holland, 1988.
[24]	L. M. Patnaik, R. Govindarajan, M. Spegel, and J. Silc. A Critique on Parallel Computer Architectures. Informática, 12(2):47-64, 1988.
[25]	V. M. Milutinovic, editor. High-Level Computer Architecture. Computer Science Press, 1989.
[26]	R. Duncan. A Survey of Parallel Computer Architectures. IEEE Computer, 23(2):5-16, February 1990.
[27]	V. P. Srini. An Architectural Comparison of Dataflow Systems. IEEE Computer, 19(3):68-88, March 1986.
[28]	J. Silc and B. Robič. The Review of Some Data Flow Computer Architectures. Informática, Il(l):61-66, 1987.
[29]	T. Y. Feng. Some Caracteristic of Associative/Parallel Processing. In Proc. 1972 Sagamore Computing Conf., pages 5-16, August 1972.
[30]	W. Handler. The impact of classification schemas on computer architecture. In Proc. 1977 Int'l Conf. Parallel Processing, pages 7-15, August 1977.
72
[31]	M. J. Flynn. Sonic Computer Organizations and Their Effectiveness. IEEE Trans. Computers, C-21(9):948-960, September 1972.
[32]	D. B. Skillicorn. A Taxonomy for Computer Architectures. IEEE Computer, 21 (11 ):46-57, November 1988.
[33]	S. Dasgupta. A Hirarchical Taxonomic System for Computer Architectures. IEEE Computer. 23(3):64-74, March 1990.
[34]	D. D. Gajski, D. A. Padua, D. J. Kuck, and R. If. Kuhn. A Second Opinion oil Data Flow Machines and Languages. !EEE Computer, 15(2):58— 89, February 1982.
[35]	J. L. Peterson. Petri Net Theory and the Modeling of Systems. Prentice-IIall, 1981.
[36]	Arvind and D. E. Culler. Dataflow Architectures. Ann. Rev. Com.put. Sci., 1:225-253, 1986.
[37]	A. L. Davis. A Dataflow Evaluation System I3a.sed on the Concept of Recursive Locality. In Proc. 1979 Nat. Computer Con}., pages 1079-1086, 1979.
[38]	J. Šile and B. Robič. Data Flow Based Parallel Inference Machine. Inform a hca, ll(4):27-34, 1987.
[39]	A. V. S. Sastry, L. M. Patnaik, and J. Šile. Dataflow Architectures for Logic Programming. Elektrotehniški vestnik, 55(1):9— 19, januar 1988.
[40]	J. Šile and B. Robič. Efficient Dataflow Architecture for Specialized Computations. In Proc. 12th World Congress on Scientifics Computation, pages 4.681-4.684, July 1988.
[41]	Arvind and V. Kathail. A Multiple Processor Dataflow Machine That Supports Generalized Procedures. In Proc. 8th Annual Intl Symp. Comp. Arch., pages 291-302, May 1981.
[42]	N. Ito, M. Sato, E. Kuno, and K. Rokusawa. The Architecture and Preliminary Evaluation Results of the Experimental Parallel Inference Machine PIM-D. In Proc. 13th Annual Int.'l Symp. Comp. Arch., pages 149-156, June 1986.
[43]	V. L. Narasimhan and T. Downs. Operating System Features of a Dynamic Dataflow Array Processing System (PATTSY). In Proc. 3rd Annual Parallel Processing Symp., pages 722-740, March
1989.
[44]	V. G. Grafe and J. E. Iloch. The Epsilon-2 Multiprocessor System. Journal o} Parallel and Distributed Computing, 10(4):309-318, December
1990.
[45]	D. E. Culler and G. M. Papadopoulos. The Explicit Token Store. Journal o} Parallel and Distributed Computing, 10(4):289-308, December 1990.
[47]	B. Robič. Minirnizacija števila procesorjev v podatkovno pretokovni arhitekturi. Magistersko delo, Fakulteta za elektrotehniko, Ljubljana, 1987.
[48]	J. Žcrovnik. Verjetnost v kombinatorični optimizaciji. Doktorska disertacija, Fakulteta za elektrotehniko in računalništvo, Ljubljana, 1992. V pripravi.
[46] K. Mehlhorn. Graph Algorithms and NP-Compleieness. Springer-Verlag, 1984.