PARALELNI VEKTORSKI PROCESORJIIN NJIHOVA UPORABA I INFORMATICA 2/88 UDK 681.3.019 P. Kolbezen S. Mavrič B. Mihovilovič Institut »Jožef Stefan« POVZETEK. Vefije raCunalniskB zmogljivosti, ki jih zahtevajo danasn.is aplikacijs na podroeju razpoz- navanja govora, procssiranja slik, umetne inteligence in &e vrsta drugih, je mogoCe iskati le v novih paralelnih siotemih, pri katsrih je znatno vBčja uCinkovitost moSna le s posebno organizacijo materialne opreme, prsdvsom v VLSI procsBorBki tehnologiji, in taksni opremi prilagojeno programsko opremo. Proizvajalci raeunalniekih Eistemov, ki naertuJBJo zmogljive vektarske operacije, BD izdelali poseb- ne FORTRAN - prevajalnike. Ti razpoznavajo, Ce SB sanka D0 lahko zamenja z eno ali veC vektorskimi instrukcljami. Zanka D0 je tako skalarna predstavitev mnoiice vektorskih operacij in zato more biti izvedena mnogo bolj uCinkovito s strojnimi instrLikcijami, ki so v takSne namsriB posebej naCrtovane in se zato njihovs opsracije uCinkovitBjs izvajajo. Arhitekturne Ddlike SB kaŽEjo z uporabo bodisi CBvanih aritmstienih enot, kot jih sreeujsmo pri cevanih vektorskih raCunalnikih (npr. pri CYBER 205 ali CRAY—1), bodisi z veCkratnimi procBsnimi elementi, kot jih sreCujemo pri vaktorskem aritmetiCnem multiprocBOorju ali pri matriCnih procesorjih (npr. pri ICL DAP, BSP ali TRANSPUTER ARRAY>. Paralelne vsktorske organizacije in podrobnejei opis strukture raCunalnika ICL DAP so predmet ob- ravnavs prvega dela prispsvka. Prikazan ja tudi stil programiranja, ki ga narekujs takfisn raCunal- nik. V Clanku je prikazano, kako so lastnosti paralelnih implementacij sekvenfinih kodov na materialni opremi paralslnBga sistema pomembne, da prirojeni parslelizem v problemu, ki ga reSujemo, ustrsza uporabljsni arhitekturi oziroma organizaciji raCunalniSke materialne oprems. ABSTRACT. PARALLEL ARRAY PROCESSORS AND ITS APPLICATION, I. With nsw applications Buch as robotics, spBBCh rscognitiDn, artificial intel 1 i gencs, image prDCessing, etc, the need -for -fastsr processing devicss becomes more important. The only solution is to employ the nsw parallel systems. Mare ef-fi— ciBnt 5ysteni5 can bs attained in -firet of all with the new VLSI technology and with. new organiza- tions of computer hardnars and to thsse onss appropriate software. Al 1 manu-factursr o-f computsris decignsd -for sfficient operatiDtnB on vectors of numbers have produced FORTRAN compilsra that recogniaa when a D0 loop can be replaced by one or ssvsral vector inotruc- tions. This is ths rscognition by softuare that a particular D0 loop ie just the Bcalar rBprsssenta- tion o-f a set of vector operation, and can there-fore bs e«scuted rouch mora ,s-f-f scti vely by machine instructiono that are espBCially engineered to per-form such operations s-fficisntly. Ths architsctur- al -fsatures ussd are thsn aithar ths pipelined arithmstic units in the cass of pipelined vector com- putars (e.g. CYBER 205 and GRAY-1) or the replicated processing elemsnts in thB case o-f vector arithmetic multiprocesor (VAMP) or procsasor array . In thB prBssnt -first part of this work thB basic categories D-f parallsl computsrE wi 11 be describBd and ths dstailsd structure o-f ICL DAP will be givcn in more detai 1 , togethBr with an overvisw o-f thB programroing styls that is requirss. In ths sscond part ths optimization algorithm based on matrix computations as a tool for implsinentations o-f application algorithms wi 11 be continued. In the paper is shown that the behaviour o-f parallel implementati ons o-f S6quential codee on parllel hardwars depsnds critically on a carsful match bstween the innate parallelism of the problsms, ths algorithm and ths hardwars. 1. UVOD prednosti novih konceptov nih sistemov. paralel- Zadnja leta ED tehnolottke spremembe in Stevilne inovacijs dramatiCno zmanjealE csno rafiunalniS- kih zmogljivosti. Na vsakih nekaj 1et so BB pojavili bistvsno hitrsjsi in cenejsi procesor- ji. PosBbnB prsdnosti tah procssorjev EO se pritelE kazati pri sestavljanju le-teh v raz— liCne paralelne siEteme. Sistemski programerji so dobili spodbudo, da so rnodi-f iciral i obstoja- Co sisternsko programsko opremo enoprocesorskih sistamov tako, da je z nja magotle kar najboljt? bomo kolikor mogoile jasno predstaviti rszultate na novejSeni podrotju raCunalniSkih arhitektur oziroma organizacij, ki naj bi poka- zali bistvene prednosti rabe paralBlnih procs- sorskih Bistsmov. Prednosti BB kaiejo v novih aplikacijah, kot so robotika, razpoznavanJB govora, umetna intBligsnca, procBsiranjB Blik itd., kjer so postals zahtave po hitrsjsih procesorskih napravah vsa pomembnejse. Zaradi zaporednega izvajanja instrukcij, ki se izvaja- 84 jo druga za drugo, je razvoj sekvenenih arhi- tektur skoraj obstal. RsSitve je nadalje mogoee iskati le v novih paralelnih eistemih, pri katerih je znatno veCja uCinkovitost moina le s pooobno organizacijo matorialne in njej ustrez- ne programeke oprente. Polpretakla zgodovina kaie, da je paralelizem mogaCe vpeljati na razliCnih nivojih, ki jih lahko opredelimo takole: 1. Nivo posla 1.1., med posli; 1.2., med -fazami poslaj 2. Programaki nivo 2.1., med deli programa; 2.2., znotraj DO zankj 3. Instrukcijaki nivo 3.1., moc) -fazami izva.janja instrukci joji 4. Aritmetifini in bitni nivo 4.1., med elementi vektorskih opsracijji 4.2., v Bklopu aritmetiCnih logiCnih vezij; Proizvajalci raCunalnifikih sistemov, ki naCrtu- jejo uCinkovite vektorske operacije, so izdela- li posebne FORTRAN - prevajalnike. Ti razpozna- vajo, Ce se zanka DO lahko zamsnja z eno ali vee vektorskimi instrukcijami. Zanka DO je tako skalarna predstavitsv množice vektorskih opera- cij in zato more biti izvedena mnogo bolj uCin- kovito e strojnimi inatrukcijami, ki ao v takffi- tiB namene posebej naCrtovane in se zato njihove operacije kar naJuCinkoviteje tudi izvajajo. Arhitekturns odlike ae kažejo z uporabo bodisi cevanih aritmetiCnih enot, kot jih sreeujemo pri cevanih vsktorskih raCunalnikih (npr. pri CVBER 205 ali CRAY-1), bodisi z veCkratnimi procasnimi elemanti, kot jih srBeujemo pri vektorskem aritmstienem multiproceaorju (VAMP) ali pri matrienih procesorjih (npr. pri ICL DAP ali BSP). Paralelne vektorske organizacije bodo predmet prvega dela nste obravnave, medtem ko bo drugi del priepsvka posveten uporabi sistema s takfeno organizacijo. Med drugim bomo obravnavali opti- mizacijski postopek, ki je zasnovan na matriC- nem raCunu in se lahko uporablja kDt ufiinkovi- to orodje za implementacijo darmga algoritma na paralelnem rafiunalniku. Videli bomo, da ao lastnosti paralelnih imple- mentacij sekvenčnih kodov na materialni opremi paralelnega sistema moCno odvisne od prilago- ditve prirojenega paralelizma v problemu, ki ga resujemo, uporabljeni ratlunalni fiki materialni oprami. To odvisnost lahko v doloCeni meri ugotavljamo na primeru, pri katerom uporabljamo paralelni rafiunalnik za reSevan.ie problemov, ki so izrazito aekvenCni. Drug podoben primer je, Ce na specifienem paralelnem procesorskem sj- etemu izvajamo takSen algoritem, v katerem sicer obstaja nek paraleliiem, je pa ta povsem drugaCne narave, kot paralelizem algoritmov, za izvajanje katerih je bil speci-fiCni paralelni sistem tudi zgrajen. Zato bomo v priapevku aledili ugotovitvam uCinkovitosti rabe posamez- nih arhitektur pri resevanju problemov doloCe- nsga razreda. 2. PARALELNI SIBTEMI Klasi-f i kaci ja procecorskih Bistemov JB dandanes ponovno vse manj zadovoljivo refiena. Znana avtorja na tem podroCju sta Flynn (1972) in Shore (1973). Problem ustrezne klasi -f ikaci je tifii v tem, da vefi dobro vpeljanih aodobnejeih arhitektur, predveem ufiinkovitih cevanih raCu- nalnikov, ne sodi dovolj jasna niti v en, niti v drug razred poznanih kl asi-f i kaci j , oziroma, da tako kot raCunalnik ICL DAP, le-ta enako dobro ustreza hkrati dvema razredoma. Alterna- tivni pritstop do primerne kl aai-f i kaci je je, da doloCimD razrede glede na osnovno naCine, na kakrttne se paralelizem javlja v arhitekturi nekega rafiunalnika. Tako 1ahkogovorimo o para- lelizmu cevanja, kopiranja oziroma vsktorskE porazdel jenoati proceeorjBV, -f unkcionalnosti ali o multiprocesorBkem paralelizmu: (1) Paralelizem cevanja (pipelining) je zasno- van na tehniki t.im. zbirne linije, ki poveCuje zmog1jivost aritmetiCne ali krmil— ne enote; (2) Paralelizem -funkcionalnosti je zasnovan na veC med seboj neodvisnih enot, ki lahko iz- vajajo razliCne funkcije (kot BO logiCne •funkci je, -funkcije ssStevanja in mnD2enja) in soCaeno izvrfiujejo operacije nad razlie- ni mi podatki. (3) Vektarski paralelizem je zasnovan na polju identiCnih procesnih elementov pod skupnim nadzorom ene same krmilne enote. Ti elemen- ti 5oeaeno izvajajo enake operacije nad razliCnimi podatki, ki BO shranjeni v nji- hovih zassbnih pomnilnikih. To BO t.im. ko- raCne (lock—step) operacije z zaklepanjem; <4) MultiproceBorski paralolizem izkorisea veC- je Stevilo procesorjev, od katerih izvaja vsak EVOJH instrukcije, medtem ko navadno med seboj komunicirajo preko skupnega pom— nilnika. Flynn /1/ je razdelil paralelne raCunalnike, ki procesirajo vsC podatkovnih tDkov hkrati v dve kategoriji. To sa vsCinstrukcijski veCpodat- kovni stroji MIMD (Multipl-Instruction Multi- ple—Data) in enoinstrukcijski veCpodatkovni stroji SIMD (Single-Instruction Multiple-Data). Vsaka od obeh kategorij ima evoje znaCilnosti. Oglejmo si jih na kratko. RaCunalnik MIMD ima navadno majhno stevilo nepretirana uCinkDvitih in med seboj povezanih procesorjev, ki lahko sodelujejo med seboj ali pa deluje.io neodvisno drug od drugega. Zato je potrebno, da so neodvisna programaka opravila kodirana in dodeljevana poeameznim procesorjem. Posebna skrb mora biti poBveCena Binhronizaciji dodsljevanja informacij med procscorji, ko eden od procesorjev zahteva in-fDrmacijo od drugega procesorja. Dokaj jasno je, da pri obse£nejsih opravilih in pogoBtejai sinhronizaciji nekateri proceBorji Cakajo brez dela, dokler drugi pro- cesorji ne dokonCajo svDJega opravila. Primer stroja taksnega tipa je Loughborough—ov raCu— nalnik Neptun, ki je zaanovan n» otirih mini- raeunalnikih Texas Instrument 990/10. Ta rafiun- alnik in njegovo uporabo je podrobneje opisal R.H.Barlow /1 /. RaCunalniki, vodeni s tokom podatkov, ki pripa- dajo kategoriji strojsv MIMD, prBdstavljajo lo- Ceno podkatargorijo. Vzrok loCitve tiCi v dru- gaCnem postopku vodenja, ki temslji na drugih in ne na klasiCnem von Neumannovem konceptu. Pri klasiCnem tj. sekvenenem raCunalniku pred- stavlja program, ki ae na njem izvaja, neko zaporcsdje (Bekvenco) instrukcij. V raCunalniku MIMD pa BB veC sekcij kode lahko izvaja para- lelno na razliCnih procesorjih. V vsaki od sekcij lahko se nadalje obstaja vzporedje, ki pa ie nevidno programerju, kor se le-to pojav- lja znotraj pasameznih inatrukcij. PriEtop vodenja B tokom podatkov se naslanja na dirsktno prsdBtavitev z gra-fom. Vzemimo enafibo: 3 2 y = a.>s +b.K + c. n + d Gornjo enafibo mDremo izraziti na obiCajen naCin v viekonivojskam programu. Moremo pa JB pred- staviti tudi direktno z gra-fom, ki ga vidimo na eliki 1. V grafu na taj sliki predstavlja vsako vozliSCe eno od osnovnih opsracij (tj. množenje ".", ki je na aliki oznaCsno z ">:", in seste- 85 vanje, ki je oznaCeno 2 " + ">. Vidimo, da so vozliaea grafa povezana s pusei- cami, ki so obrnjene v smeri toka informacij: vhod-izhod. In-formacija potuje od izhoda VDZ- lisCa, ki je pravkar izvrfiilo svojo funkcijo Preprost BekvenCni rafiunalni k 1 : 2 ! :" -v- (b) Vsktorsko cevani raCunalnik -V-! >'2-V2 1 i : — i -v-i x3.y 21 i i : | j -v- 2j <- 3 i 2 ! 1 z2 <- 3 1 2 \ ! \ z3 <- 3 1 b [ V X ! V ; i ; X 1 V J V !. > i V I V r «3- 1 : 2 ! <- 3 : _____ i (c) Paralelni vektorski procesor -V- 1 2 3 Slika 1. Krmiljsnje s tokom podatkov V Z2 -v-: 1 : 2 : 3 I v Z3 namreC omejeni v taksnem Bfnislu, da opravljajo enake operacijs. Kot primer vektorskega cevanja Slika 2. Csvanje pri VBktorska cevanem in paralslnem vektorBkem proceBorju 86 primer, ko se izvrfii mnoSenje segmentov >:j in yj, se priCne seStevanje eksponentov segmentov *1 *n yl ' ^oda istoCasno starta tudi mnoiienje naslednjih dveh segmentov K^ in Y2< itd. Mimograde povedano, tudi srednji in zelo hitri sekvenCni stroji izkoriseajo prednosti cevanja. Obravnavani primer je prikazan na sliki 2. (za n=64). Pri sekvenCnem stroju BD potrebni tri je urini impulzi za izraCun vsakega "delnega" rszultata, kar pomeni 192 impulzov, da se izrafiuna csloten vektor z. DrugaCe je pri vektorskem cevanju, kjer je po prvih dveh impulzih potreben le 6e en sam urin impulz na "dolni" rezultat. To pomeni skupaj 66 impulzov, da BB izraCuna celotan vektor x. V primaru matrifinega procesiranja pa dobimo vssh n (delnih) rezultatov v treh urinih impulzih. Torej lahko zakljutimo: Ce primerjamo vse tri mDžne natine mmoienja n = 64 komponentiji h vektor jev in upo— rabimoj a) BBkveneen raCunalnik, potrebujemo 3n=192 im- pulzov, b> vektorsko cevani računalnik, potrebujemo 2+n = 66 impuzov, c) paralslni vektorBki procesor, potrebujemo 3 impulze. AL60RITMI EXPLICITNI PARALELI2EM i SIMD MIMD/SIMD MIMD I IMPLICITNI PARALELIZEM TDK PODATKOV (DATAFLOH) CEVANJE (SISTOLICNO POLJE) POLJE PROCESNIH ELEMENTOV VECKRATNI CEVANI SISTEM i VECKRATNI PROCEBNI SISTEM DODELJEN POMNILNIK Tesno povezan ei stsm STRUKTURA SPOROcANJA PREKO VODILA •*••*# ••**••»* Rahlo povezan eistem NOTRANJE POVEZOVALNO VEZJE *#*•*•*#***** Rahlo povezan si stem Slika 3. Klasifikacija paralolnih raCunalniskih arhitBktur. naCin isvajanja paralelisma v algoritmu, lahko paralelne arhitekture kl asi-f ici ramo /9/ po she- mi na eliki 3. 2.1. Vektorski in aeociativni procasorji Glede na zgora.j omenjsne vidike procesi ran.ja pa lahko paralelne procesorske Bicteme razdelimo v Sest razredov, in sicer: BPWSAR - bitno paralslni (BP), besedno serijski (WS>, vektorski (AR) procesorji:UNGER, SOLOMON, VAMP, CDC 7600, BRAY-1, ILLIAC, BSP in NASF; UIPBSAR - besedno paralelni I.UP) , bitno serijski (ES), vektorski serijski (S) in paralelni (P) asociativni (AS> pro- ceBorji ali tim. ortogonalni procesar- jisOMEN 60. RaCunalniki tega razre-da se lahko zdruSujejo v ustrejne MSIMD (ti. veCkratne SIMD raCunalnike): MAP, PM ; BPWSAS - bitno paralelni (BP), besedno serijski (WS) , asociativni , bitno serijski (E procesorjit STARAN, RELACS; UNCNAS - riBpovezani (UNCN) asociativni procesorji z beeednimi rezinami (bitno sserijski)! PEPE; CNAR - povszani (CN) vektorski (AR) procs- sorji z bBBBdnimi rezinami (bitno se- rijaki): ILLIAC IV. Msd pridružene ra- Cunalnike MSIMD tega razreda lahko priStevamo sistem PHOENIX. Vsi vsktorski procesorji podpirajo koncspt lo- Cenih podatkovnih pomnilnikov (DM) in procesnih enot (PU), ki BO povazani med seboj z nskim podatkovnim vodilom ali stikalnim elemBntom. Pri tem jcs nepomembno, da imajo nakatere imple— mentacijs enobitnih strojBV WPBSAR procesno enato in podatkovni pomnilnik realizirana na isti vtiCni enoti (tiskanini). Taksen procesor je npr. ICL DAP. Nevektorski procesorji pa pradstavljajo alternativni pristDp k porazde- ljeni procBsarski lagiki, ki js preneSena na pomnilnik. ImEnujemo jih "Vsebinsko naslovljivi paralelni proceeorji" (CAPP) ali "A«ociativni procssorji" (LIMA) in zavzemajo abseino podroC- js procesorjev od najprsprostejsih asociativnih pomnilnikov do zelo kompleksnih asaciativnih procesnrjev /10,11/. ShBmD arhitekture te vrste procssorJBV iz razreda LIMA prikazuje slika 4. PodrobnoBti drugimi tudi o rafiunalniku Sray-1 v dalih /6/ in /7/. najdemo med Podrobnejso klasifikacijo strojev je mogote podati bodisi z vidika organizaciJB njenih sBstavnih delov, v katerih ss vzporedjB po— pojavlja, bodisi z vidika uporabljenega naCina krmiljenja. Slednja kl asi-f i kaci ja ja obravna- vana v delu B.RobiCa /8/. V nadaljevanju pa se bomo omejili predvaem na prvo omenjeno klasi-fi- kacijo, ki je osnovana na paralelnem procesi- ranju bitov ali/in bessd in na stsvilu uporab- ljenih krmilnih enot. Vse pogosteje .pa dandanes BreCujemo tudi sisteme, ki vkljuCujBJo oba na- Cina vodsnja: podatkovnsga in rtBpodatkovnega, od katerih slednji sloni na klasi^ni von- Neummanovi arhitekturi. TakSen "mefiani" sistem je npr. navsfront procssor. UpoatBvajoe obe omenjeni kl asi -f i kaci ji , je mogoie klasi-f i kaci jo strojev BB bol j nadrobncj razdelati. Blsds na CU PU DM Slika 4. Arhitektura procBSorja iz razrBda LIMA. PodroCje aplikacij strojev iz razreda LIIiA, ki se odlikujajo po izradno hitrih opcracijah in po lahkem programiranju, je zslo veliko. Msd napogostajse aplikacijB BQdijo: procssiranje radarskih podatkov, testiranja povezanosti, ki jo sreCujemo v detErminiBtiCnih implikacijah semantienih mret umetns intEligBncs, pravopiBno popravl janje, digitalno dif erencialno arvalizi- ranjB analognih podatkov (kar prBdstavlja bist- veno bolj uCinkovito rBBBvanje problemov, ki jih sicer refiujsjo analogni raCunalniki), nad- zorovanje zraCnega prometa, urejanjB, časovno 87 vhodno/i zhodno dodeljevanje med tsrminali in glavnim rafiunalnikom in reSevanje relaksacij- skih problemov v fiziki. Pogosto pa se asocia- tivni paralelni procesorji uporabljajo tudi za opravljanJB stevilnih specififinih -funkcij v konvencionalnih računalnikih. Veebinsko naslavljiv paralslni proceeor CAPP .je zaenovan na vsebinsko naelovljivem pomnilniku CAM, ki mu je dodana spoeobnost paralelnega vpisovanja v beoede, ki so za ta namen pocebej oznaCene. Lahko se sprsminja celotna vsebina besed, ali le del besede, ali celo samo posa- mezni biti v oznaCeni besedi. V taksnBm primeru govorimo o sposobnosti pomnilnika z veCkratnim zapieom. Po tej apoBObnosti ss loCi CAM od CAPP. Le-ta omogofia izvajanjs paralelne aritme- tike, sestavljeno iBkanjs in v splottnem emula- cijo vektorskih raCunalnikov, kot na primer ra- Cunalnika ILLIAC. Prvi predlog pomnilnika CAM je dal Slade *e leta 1956, v letu 1972 pa je Goodyear Aerospace Corporation poslal na trtm- Ce rafiunalnik STARAN, kot prvi komercialno doaegljiv CAPP. Nadalje si oglejmo se ostale razrede paralelnih procssorjsv in veaj po enega predstavnika vsa- kega razreda. {. ProcBBor JB konvenciDnalne von Neumano- ve arhitekture z eno samo krmilno snoto , krmilnim ali inotrukcijs- kim pomnilnikom , ki se odlikuje po svoji preprosti arhitBkturi. Shemo arhitekture raCu- nalnikov tega razreda ponazoruje slika 5. ! I I I i ! IM I—>—! CU !—>--! Horizontalna PU ! ; i ! ! : ! I ! ! ! i I i ! !!!!!!! I' i Besedne rezine DM ! Slika 3. Arhitektura procssorja iz razreda BPMSAR UNBER <1958) je zasnoval raCunalnik za reSavan- js prostorskih problmDv, predvsem za aplikacije kot so npr. razpoznavanja vzorcsv. Ta raCunal- nik, imanovan tudi "prostorski raCunalnik", ima dvodimenzionalno polje PE pod ekupnim nadzorom. V raCunalniku S0L0M0N je bil vpeljan koncept t.im. "zaklepanja po korakih" v operacijah strojsv BIMD. Koncapt je predlagal Slotnick (1962), rsaliziran pa je bil Bele v seriji strojev ILLIAC in oe nskaterih kasnejBih stro- jih tipa SIMD. Tri leta kasnsje je bil zgrajsn vektorski aritmetiCni procesor VAMP (Ssnzing in Smith), ki js aestavljsn iz linearnih vektorjev PE z dodeljenimi jim ppmnilniskimi moduli in cavano aritmetiCno snoto. Vsaka PE je virtualni procesor, ki vssbuje samo nskaj dslovnih rsgis- trov. Cevani vektorski procesor pa je bil naCr— tovan z namenom, da zmanjfia ceno materialne •preme, potrsbns za vektorsko procBsiranje. Prvi modBl raCunalnika GRAV-1 je bil zgrajen pri Bray Research Inc. kot najhitrejoi raCunal- nik na ovstu in dobavljen laboratoriju "Los Alarnos Scienti-fic Laboratory" leta 1976. To JB tudi prvi komBrcialno dosegljiv cevani vektor- ski procssor. Ima 12 *unkcionalnih enot, sedaj Se vse cevarie, hitrjso uro }2,5 ns, 16 bank bipolarnega pomnilnika z 10 besed in 50 ns ciklDm ter osem 64-bitnih vBktorskih registrov za pomnenje 64-ih stevi 1 v pDmiCni vejitfi. AritmetiCne operaci je nad temi vsktorji izvaja B približno 32 strojnimi ukazi. Tri -funkcional — ne enote so namenjene vektarskim operacijam (pomiku, logiCnim operacijam in sefitevanju), trl enoto pa skalarnim operacijam (seBtevanju v plavajofii vejici, množenju in reciproCni aprok- simaciji) /7/. Burroughs Corporation JB igral vodilno vlogD pri razvoju vsktorskih paralolnih procesorjih. Ta se JB priČBl s procesorjem ILLIAC IV in nadaljeval s paralslnim procesorjem PEPE. Kmalu mu JB slBdil BSP E komsrcialnimi teSnjami na psrspektivnem tržiseu, ki ga JB predstavljalo Se takrat Bkspanzivno splbsno znanstveno - raziskovalno okolje. Projskt ILLIAC IV je imel cilj, da BB razvijs viaoko parelelni raCunalnik z velikim stsvilom ari tmetiCnih enot, ki bi izvajalB vektorstce al i matriCne izraCune s hitrostjo reda 10 operacij na sekundo. Da bi SB doŠBgla taksna zmogljivost sistema, je bil rafiunalnik prvotno natrtovan z 256 PE-mi, katars naj bi nadzorovale 4 central- ne procesne enote (CU). Zarade pravisoke csne in neeprejemljivih zakaenitev operacij dodelje- vanja JB bil prvotni BiBtem okrnjen na sno Ce- trtino. Tako konfini produkt, ki je namenjen j predvsem resevanju parcialnih diferencialnih enafib (v numeriCni obdelavi vremeno&lovnih kart za napovedavanje vremena, v nuklearnih raziska- vah in v drugih fitevilnih aplikacijah), sestav— lja le polje 8 x 8 po 64-bitnih procesnih ele- mentov za raCunanje B plavajoCo vejico pod ' nadzorom ene same CU. S taka okrnjenim sistemom so doesgli hitrDBt 200 milijonov operacij na sskundo. Vsaki PE je dodeljen pomnilnik z 2K basedami, ki dala po naCinu koraCnega zaklB- panja z najblifjimi Bosednimi povezavami. Eden od problemov, ki so nastopali pri uporabi eksparimentalnega prototipa ILLIAC IV, so bile zakasnitve pri prenasanju podatkov na dolge razdaljs preko polja PE zaradi omejitev v Ste- vilu najbli2jih sosednih povezav med 64—imi procesorji in njihavimi 64—imi bankami pomnil— nikov —I I I CU ; i : i ! 1 ! Verti : : i ! 1 ! Bitne kalna ! ! ! 1 ! I rBzine PU : ; I ! DM Slika 6. Arhitsktura procesorja iz razrada WPBSAR. Vektorski procesor CLIP-4 je procssai-, ki je zasnovan na bitnih rezinah. PE pracesorja so razporejene v celiCno mrežo 96 x 96 PE. Vsaka procesna enota ima osem sosedov v dvodimenzio- nalnem polju, lahko pa je povezana le s atirimi najblifjimi sosedi. RaCunalnik MPP je t.im. masivni paralelni pro- cesor (maseively parallel procesor), ki je bil razvit v NASA Goddard Space Flight Center za procesiranje satelitskih posnetkov. "Masiven" se imenuje zato, ker ima 128 >: 128 = 16384 mikroprocesorjev, ki lahko vsi hkrati paralelno procesirajo. Procesor MPP raCuna v aritmetiki bitnih rezin z operandi spremenljivih dolSin. Ima mileroprograml ji vo krmilno enoto, ki ji je mogoCe vprogramirati popolnoma pri1agodljive instrukcijs za vsktorsks, akalarna in 1/0 ope- racije. SistBm MPP je izvsdsn v celoti v pol- pravodnifiki integrirani tehnologiji vezij in uporablja mikroprocssorske Cipe in bipolarne RAM-pomnilni ks. MBSPAS. ProcsBorji tega razreda BQ Kestavljeni iz kombinacijs arhitektur Etrojev iz razreda BPWSAR in WPBSAR. Arhi,tekturo WBSPAR sestavlja dvodimenzionalni pomnilnk, iz katerega BE? lahko Citajo ali beseds ali bitne rezins, horizontal- na procesna enota, ki procosira besede, in vsrtikalna proceBna snota, ki proceoira bitne rezine. To je v bistvu ortoganalni raCunalnik, ki ga je zaenoval Shooman Se leta 1970. Oba omenjena raeunalnika iz prejsnsga razrsda ICL DAP in STARAN sta sicsr lahko programirana tako, da zagotavljata eposobnoBti raCunalnika iz tsga razreda, ker pa nimata loCenih proces- nih enot za procesiranjs besed in bitnih rezin, ne pripadata tBfnu razredu. Impl emsntaci jo stro- jev, katerih arhitsktura papolnoma ustreza definiciji strojev iz razreda WBSPAS, predstav- lja serija raCunalnikov OMEN-60. RaCunalnik OMEN-60 JB zaanoval Higbis *B leta 1972, njiho- vo arhitekturo pa ka£e slika 7. I IM I Vsrtikal.PU I ! I : ! i : i ! CU !—>-! Horizon. PU I i I ! I ! I I l_l l_l !_!.. i ! : ! Podat.pomn. ! | DM I I - ! Slika 7. Arhifcaktura procesorja iz razreda WBSPAR. Serija raCunalnikov DMEN (Ortogonal Mini Embsd- meNt) JB komercialna implBmentacija ortogonal- nsga raCunalniBkega koncBpta proizvajalca San- ders AsEociates za aplikacije, kot ja procesi- ranja Bignalov. Ta esrija uporablja raCunalnik PDP-11 za konvsncionalno horizontalno aritmsti- Cno enoto in polje 64 procesnih enot (PE) za asociativno vertikalna aritmstiCno enoto. Dpe- racije te enote se izvajajo predvsem nad zlo- govnimi rszinami in ne toliko nad bitnimi rezi- nami, odvisno od modela; ali ima ls-ta bitno serijsko aritmstiko z osmimi biti pomnilnika, k.i pripada vsaki PE, ali pa ima aritmstiko v plavajofii vsjici, izvedeno v materialni opremi z osmirni 16-bitnimi rsgistri in petimi maokov- nimi ragistri. Posebna logika msd PE-mi Dbraea vrstni red zlogov v rezini ali invrsujs popolno premesCanje (per-fect shu-f-fla) al i cikliCni pomik. Med MISMD primere tega razreda lahko pristsvamo raCunalnik MAP (Multi-AssociatiVB Procesor) . z oEmimi.CU, ki jim je dodsljeno 1024 PE in sia- tem PM , ki js bil naCrtovan kot "rEkon-f i gura- bilni" raCunalniski Bistsm. PosBbnost tsga procBsorja je, da lahko procesira na tri naCi- ne: kot MSIMD, MBISD in kot MIMD. TipiCno kon- •figuracijo PM Bestavlja 16 centralnih enot s 1024 procesorskimi pomni1niSkimi snotami. Sis- tem je bil kasneje na Pardue University izpo- polnjsn v t.im. PUMPS tako, da ga je mogoCe uporabljati tudi za splofins raziskavB VBfiproce- iiorskih sisteuiov. BPklSAS. Arhitsktura raCunalnikov tsga razreda je analogna arhitekturi raCunalnikov iz razreda WPBSAR, kot jo ka«e Blika 5. V ta razred spada- jo asociativni procssorji, ki uporabljaja bs- sedno BBrijski asociativen pomnilnik. Na to- vrstnih procesorjih ja zasnovan tudi rafiunalnik PEPE. Ker je le-ta hkrati tudi t.im. "nepovezan asociativen procesor", ga bomo obravnavali v prav tako imenovanem razredu UNCNAS. MPBSAS. Arhitektura raCunalnikov tega razreda je analogna arhitekturi raCunalnikov iz razreda WPBSAR (Blika 6). Predstavnik tsga razreda je STARAN. Uporablja bitno serijski asociativen pomnilnik. Ima dD 32 asociativnih vektorskih modulov. Prvi raCunalnik tsga tipa je bil na— menjen procesiranju digitaliziranih slik leta 1975. Popolnoma paralelna struktura uporablja zahtevno in drago logiko v voaki pomnilniflki celici in zapletene komunikacije msd celicami. Bitno Bsrijski aBDCiativBn procesor je bietveno 89 cenejsi od popolnoma paralelne strukture, ksr ss istoCasno primerja le ena sama bitna rezina. Vsak od 32 aoociativnih vektorskih modulov ima 256 x 256 bitnih besed veCdimenzionalno dostop- nega pomnilnika (MDA), 256 procesnih elementov, permutacijsko (flip) vezje in selektor. Vsak procesni element obravnava serijsko bit po bitu nad podatki v vseh besedah MDA pomnilnika. S pomotfjo permutacijskega vezja so podatki, ki so shranjeni v pomnilniku DMA, dostopni preko 1/0 kanalov v bitnih ali besednih rezinah ali v kombinaciji obeh. Permutacijsko vezje izvaja pomike ali opravila, ki omogoeajo paralelno iskanje, aritmetiCne ali logiCne operacije nad besedami pomnilnika MDA. Ta pomnilnik je Good~ year Aerospace implementiral tako, da je RAM Cipom dodal XOR logiCna vezja, v kasnejSih, draijih modelih pa je MDA-pomnilnik povefial na 9216 x 256 bitov na modul in znatno pavieal hitrost 1/0 operacij in pročeairanja. Med izva- janjem ene instrukcije BB podatki v vseh selek- tiranih pomnilnikih vseh modulov procesirajo BoCasno s preprostimi procesnimi elementi, ki so dodeljeni vsaki podatkovni bssedi. Vmssniitka enota vsebujs vmasniks s senzorji, konvencio- nalne raCunalnike, signal proceBOrje, interak- tivne pri kazovalni ke in masovns pomnilniftke? naprave. RazliCne 1/0 opcije BO implementirane v "cuetom design" vmssnitlki enoti , ki omogota direkten dostop do pomnilnika, 1/0 kanale z vmesnim shranjevanjom, zunanje funkcijBke kana- le in paralelni 1/0. Vsak asociativni vektorsski modul ima 256 vhodov in 256 izhodov, prav tako v posebni "custbm design" vmesniski enoti. Ta omogofia veCjo hitrost komunikacij vektorskih podatkov raCunalnika z visoko pasovno sirino 1/0 naprave in dovoljuje katerikali napravi, da neposredno komunicira z asociativnimi vektor- skimi moduli. Navedene eposobnosti znatno pove- Cujejo v zahtevnih aplikacijah prepustnost sistema, poenoatavl jsno kompl eksnoost pragramske opreme pri Borazmeroma manjfii ceni materialne opreme. Posebna odlika rafiunalnika STARAN je viaoka 1/0 hitrost oz. zmogljivoat komuniciran- ja z okolico in Bposobnost preprostega povero- vanja z konvencionalnimi raCunalniki. STARAN v sistemu s konvencionalnimi raCunalniki nadzoru- je paralelno proceairanje opravi1, konvsncio- nalni raeunalniki pa opravila, ki se morajo procesirati serijsko- Dandanes je vefiina asociativnih proceBOrjev na- Crtovanih za iskanje in-formacij in obdelave podatkovnih baz. TakSne vrste je asociativen rafiunalnik RELACS, ki ga je predlagal Stevens (1979) in je namenjen raziskavam na SyracuBB University. Zasnovan je na uporabi veestopenj- ekih pomnilnikov med diski in gostiteljskim ra- čunalnikom. UNCNAS• Stroji tega razreda imaJD pDmnožene PU in DM iz strojev prvega razreda BPWSAR. PU in pridru2eni DM EO V tem razredu definirani kot procesni elementi PE. Vse PE izvajajo instruk- cije ene same krmilne enote CU. Dobro poznan stroj tega razreda je PEPE. Ker procesne enate med seboj niso povezane, je uporaba teh strojev omejena, po drugi strani pa obatajaja dcJloCene prednosti le-teh zaradi relativno enostavnih procesnih elementov. Arhitekturo raCunalnikov tega razreda kaSe slika 8. Kot vidnejSega predstavnika tega bomo agledali rafiunalnik PEPE. razreda Dbstajata dva tipa popolnoma paralelnih asocia- tivnih procesorjevs besedno organizirani in s porazdeljeno logiko. Pri besedno organiziranih procesorjih je prisotna primerjava vsakega bita vsake besede in so inožne logitne odloCitve po procesiranju vsake besede. Asociativni proce- sorji s porazdeljena logiko so manj zapleteni in zato tudi cenejSi. Taksen procesor je PEPE, ki je bil razvit v Bel1 Laboratory-jih za apli- kacije pracesiranja radarskih signalov. Proce- Bor oesstavlja BBdem razlifinih f unkci onalni h podsistemov. Od teh je pet nadzornih enot, kot BO nadzorna enota izhodnih podatkov in pomnil- niSkih elementov, aritmetiCna, korelacijeka in asociativna izhodna nadzorna enota, ter nadzor- ni sistem in stevilne procesne enote. Vsako PE sestavlja aritmetidfna cnota, korelacijEka erio— ta, aoociativna izhodna nadzorna enata in pom- nilnik z 1024 32-bitnimi besedami. 2BB PE je organiziranih v osem elementne svitke. Selekti— rani deli opravil se nalagajo iz gostiteljskega raCunalnika CDC-7600 v procesne enote. Selekci- jo doloffa inherentni paralelizem opravil in speci-fiCna arhitektura procesorja PEPE, ki lahko obravnava posamezna opravila veliko bolj uCinkovito kot gostiteljski univerzalni raCu- nalnik, in se uporablja le kot koprocesor tega raCunalni ka. CNAR. Stroji tega razreda so podobni Btrojem iz prejsnega razreda s to razliko, da ED pri stro- jih iz razreda CNAR procesne enote PE razvrsCe- Centralna procesna enota CU PU DM PU :—> DM PU DM Slika 9. • Centralna procesna enota CU ! I PU I t I DM ! 1 V PU I 1 I DM I V i PU : ! ! ! I ~"~ \ i DM i i : Slika 8. Arhitektura procesorja iz razreda UNCNAS. Arhitektura procesorja iz razreda CNAR. ne v liniji in med seboj povezane znajbliSji sosedi. To pomeni, da morejo nekatere procesne enote naslavl.iati besede v svojem lastnem pom— nilniku in tudi'od neposrednih sosadov. Na ta naCin je v dolotleni meri odpravljena slabost pracesorjev iz prejsnega razreda, ki izvira iz nspcjvezanosti PE. Primer atroja tega razreda je ILLIAC IV, ki omogoea hkrati tudi direktne komunikacijs med vsakimi osmimi procesnimi enotami PE. KarakteriBtiCno shemo arhitekture procesorja iz tega razreda vidimo na sliki 9. Vidnejsi predstavniki tega razreda so poleg ra- Cunalnika ILLIAC IV tudi izvedenke MIMD tega raCunalnika, kot je procesor PH0ENIX. N.iegov 90 predhodnik je proceeor, ki ga v bistvu ssstav- lja originalen rafiunalnik ILLIAC-IV. Ta je na- Crtovan tako, da ima stiri centralne enote, ki jim je dodeljeno 256 PE (4 krat 64 PE). V okvi- ru rafiunalnittkega projekta PHOENIX pa je zdru- žehih 16 po 64 PE, kot razSiritev raCunalnika ILLIAC IV za SB uejnkovitejss MSIMD vektorsko proceeiranje. lied procesorje MIMD tega razreda lahko priftta- vamo tudi TRANSPUTERSKI SISTEM, ki ga bomo posebsj obravnavali kaeneje. Pregled zmogljivosti nekaterih paralelnih raCu- nalnikov daje Tabela 1. HOl1AND MULTIMIKROPROCESORSKE MATRIKE SIMD sistemi UNGER SOLOMON VAMP CDC 7600 STARAN ILLIAC IV PEPE CLIP OMEN 60 MAP BRAV-1 ICL DAP BSP PM4 RELACS PHOENIX CDC NASF CYBER 205 MPP Tabela Legenda: Ueto zasnove 1958 1962 1965 1969 1970 1972 1973 1967 1976 1977 1978 1978 1979 1979 1979 1979 1979 1982 1983 Arhitek- tura WB,AR ws,AR WB, AR ws,AR be,AS WB,AR bs,AS,UNCN bs,AR bs,AS,0RT ws,AS,M ws,AR * be,AR ws,AR ws,AS,M bs,AS ws,AR,CN,M ws,AR * ws, AR 1. SIMD-raCunalniski ws besedne rezins M(SIMD) bs bitne rezine AR vsktorski AS asociativni * SISD z MFE ORT CN UNCN NajveCja zmogljivost v M-flop/B 80-200 10g-288 10 pi>:el ops 130-200 10-30 20-50 104 1000-3000 3000 200-6000 sistemi vefikratni (Multiple SIMD) ortogonalni pavszani nepovezani 2.2. Pregled razvoja paralelnih sistemov. V Tabeli 2 je prikazan Casovni prikaz razvoja paralelnih vektorskih in asociativnih procesor— jev. Med prve , ki so jih zaenovali, sodijof von Neumann, Holland in Shooman. Povezava med posameznimi procoeorji v razpredelnici kaSejo v smsri od deone proti levi njihove prednike po arhitekturnih znaCilnosti. V zakljuCku tega sestavka naj omenimD, da BO stroji MIMD neprimerni za reSevanje prDblemov, ki se nanaSajo na reSevanje siBtemov parcialnih di-f Brencialnih anaCb (p. d. e.s. > al i razsefinih optimizacijskih problemov. Tako nam za roSe- vanje tovrotnih problomov oBtansjo le matriCni in vektorsko csvani raCunalniki. Msd prve sodi na primsr ICL DAP, msd druge pa Gray-1. Od obeh je za omenjens raziskave primtarnejfli vektorski raCunalnik ICL DAP iz naslednji razlogov: 1. MrsSa procBBorjev (matrika) se enostavno prsslika v mreio, ki je za tip problemov, ki BB reSujejo, najuEtrznejsa, in 2. Vektorski raCunalnik omogoča poglobljen stu- dij soCasnosti v algoritmu, medtem ko vek- torsko cavani raCunalnik (npr. BRAY-1) so- CasnoBt (paralelizem) v algoritmu) na nek nafiin prekriva. von Neumann ! UNGER ! <*> i PM !__(*> MAP VAMP (*») CLIP I —„_. — — — — — — »«.«••_.«••>_ »_•«»•«_• __^M__ —~ ««_ — » — ! SHODMAN STARAN OMEN RELACS MPP S0L0M0N (**) I DAP PEPE BSP NASF ILLIAC <*) PH0ENIX —55 60 65 70 —75 80— >—85- leto Tabela 2. Razvoj paralelnih vektorskih in aBOciativnih procssorJBV. Zato se bomo v naslBdnjBm poglavju poglobili v strukturo vektorskega raCunalnika, kakrsna Bta na primer raCunalnika ICL DAP z jezikom DAP FORTRAN in novejsi TRANSPUTERSKI SISTEM z jezi- kom OCCAM. 3. PORAZDELJEN VEKTORSKI RACUNALNIK Zgled vektorskega porazdeljanega procssorja je raCunalnik ICL DAP. Med novejse tovrstne raCu- nalnike lahko priatsvamo tudi sistem t.im. transputerjev. Transputsr prsdstavlja procssor- eki modul. Vektoreki raCunalnik pa dobimo, fe te module matrieno povežemo med seboj. Ena od bistvenih razlik obeh raCunalnikov je v tem, da ICL DAP pripada razredu SIMD, medtem ko lahko TRANSPuterBki SiBtem pripada tudi razredu MIMD. Prvi ima v danasnji verziji (Queen Mary Colege, UniVBroity of London) v enoti 4096 procBEorJBV, ki EO razporejsni v mariki 64 x 64. Ta enota ne dela kot samostojni raCunalnik, ampak le kot pomnilniaki modul, ki JB povezan z obiCajnim centralnim pomnilnikom. Podrobnejsi opis rafiunalnika DAP najdemo v delu Reddaway-a /8/. V TRASPS pa so elementi matriks povssm BamoEtojni procesorji tim. TRANSPUTERJI, ki pripadajo procesorjsm iz razrada SISD /9/. NB le v omsnjBnBm primeru, ampak tudi eicer lahko ugotavljamo, da imajo procesorji v raCunalni- kih, ki pripadajo raCunalnikom iz razreda SIMD, v primer.iavi s proceBorji v raCunalni ki h, ki pripadajo razredu MIMD ali csntralnim procssor- jem, praviloma zelo preproeto osnovno arhitek- turo. V ratiunalniku DAP so procesorji, ali bolje refieno procesnB enote PE, bitno organiEi- rane, kar omogoea sistBmu veliko prilagodlji- vost aplikacijam, ki so skladne z njsgava orga- nizaci.io. Med takans, najbolj pDgoste aplikaci- JB, eodijo: procBBiranjB slik, preglsdavanje podatkov in simbolno procesiranje, ki je zdru— 2sno z osnovno aritmetiko. 91 3.1. RaCunalnik ICL DAP •snovno organizacijsko shemo raCunalnika DAP podaja slika 10.Iz nje je razvidno, da je vsa- ka proceona enota povezana z najblifjimi stiri- mi sosedi. Blavne podatkove poti, ki potekajo po kolonah in vrcticah, pa povezujejo vse procesorje dane vrstice oziroma kolone. Te poti omogoeajo hitro oddajanje in sprejemanje in-for- macij preko matrike procesorjev in je mogoCe vzpostavljati diametralne povezave, tudi preko celotne matrike, al i veC loCenih povezav. V ra- Cunalniku DAP ima vsak procesor 16k bitov pom- nilnlka RAM, kar predstavlja skupaj 16k x 64 >: 64 / Q = B megazlogov. Pri tem naj omenimo, da imajo drugi podobni stroji, ki ao danes. inata- lirani, le 4 kilozlogov na procetor ali akupaj 2 mogazloga. 64 x 64 Procesna matrika 64 x 64 16k bitov pomnilnika na procesno enota i/ Sika 10. Osnovna organizacijska shema raCunalnika ICL DAP Vsaka procesna enota poseduje ovoje lastne podatke, ki jih obdeluje, Eprejema pa tudi nekaj skupnih instrukcij, ki jih poSilja glavna kontrolna enota (MCU). Zato ta raCunalnik pri- Stevamo med raCunalnike tipa SIMD. Iz elike 11 js razvidno, da ima procesna enata PE tri registrei delovni register A omogoCa prekinjajoCe delovanje procesorja v skladu z zahtevami programa, msdtem ko je A enobitni akumulator in C register, ki hrani prenos. Pomembna lastnost raCunalnika DAP je cposobnost izkljuCevanja posameznih proceBorJBv v raCunal- niku. Na primer, Ce reSujemo problem, za reiie- vanje katerega zadosCa mreža proceBDrjev, ki je manjSa Dd 64 >: 64, moremo s pomoejo logiCne matrike odveCne procesorje z maskiranjem pre- prosto izkljuCiti. Na ta nadin mDremo izvajati .je prilagojena doloCeni m zahtevam. Slednje bomo kasnejGs ogledali bol i nadrobno. 3.2. SISTEM TRANSPUTERJEV Rafiunalniki z veC med seboj povezanimi proces- nimi enotami, imenovanimi TRANSPUTRJI /12,13, 14/, predstavljajo razliCne sisteme, med kate- rimi bo za nas posebej zanimiv porazdeljen vektDrski raCunalnik. Inmos, ena na jpomembne jfli h britanskih -firm ra- CunalniSkih kDmpDnent, je ponudila tr2i«Cu 16- bitne (T 212 in M 212) in 32-bitne (T 414), napoveduje pa tudi 2e nove Se zmogljivejSe ! ; i \: / i Matrika 16 x 16 Traspu- terjev T414 i < — > I ^' „ _ V !< — > i < — > !< — > K — > \ ! / P o V e V e j e neke matemati ttne operaci.ie na delu matrike, ki Slika 12. TransputerEki vektorski eistem 92 Slika 12 ka2e transputerski vektorski sistem, ki ga sestavljaja kvadratna matrika N=16xl6 procesnih enot, sistem pomnilniSkih vmesnikov, povezovalni sistem, matriCna krmilna enota, gostiteljski raCunalnik in vhodno/izhodna eno- ta. Kot smo 2e omenili, so transputerji zelo zmDg- ljivi 32 bitni procesorji (n.pr. T424)s statie- nlm pomnilnikom : MB : :, . Z . . i . . 0 I v ! a !<- 1 ! n ! .a.. I . . PE MB z I j : a :<- PE MB I Slika 13. Kon-f iguraci ja komuni kaci j znotraj vektorskega polja (PE=procesne eno- te, MB=pomnilniski bloki, N=16>tl6> komponente so integrirane v enem samem £ipu, ki predstavljajo odliCne gradnike kDnkurenCnih procesnih vezij /15/. Transputerske zanke pred- stavljajo kanale za medprocesne komunikacije v materialni opremi. Tako obetaja zelo tesna povezanost med povezavami (zankami) transputer- skih kanalov in komunikacijokim protokolom, ki je primeren za komuni kaci je v t.im. "wavB-front" vektorskih procesorjih v serijBki verziji), z X<-, ) pa dose- itemo toCko v predhodni vrstici, itd. Pomembno je, da vemo, da so vse taCke v matriki istoCas- no aiurirane. V taksnem primeru cefitevalne matrike ne potrebujemo veC. Meje matrike? se urejajo avtomatiCno z vnasanjem niCel na mesta, ki jih daloCa geometrija. Pri ravninBki goome— triji vstavljamo nifile na ustrezna mesta v ravnini , madtem ko pri ciklitni geometriji zato, da dobimo cilinder, povezujemo ali sever- južne ali vzhod-zahDdne robove, - neodvisno od uporabljene smeri pomika. Lahko pa pomikamo tudi vee Stiri robove in 5 tem dobimo "toruE". Sedaj predpostavimo, da 2elimo refiiti Laplaceov problem z iregularno pblikovano mejo (ali s pravokotnim poljem, ki je manjtte od 64 >: 64). DAP FORTRAN omagoCa kreiranje lDgiCnB matrike, imenovane DOMAIN. V njej oznaCimo pravilne vrednosti (TRUE: logifina "1") v tiste dele matrike, ki odgovarjajo podroCju problema in neprave vrednosti (FALSH: logiCna "0") povsod drugod v matriki. Refiitev je podana v naslednji kodi : D0 10 I=I,LIMIT OLDX=X X GOTO 20 10 CONTINUE CONVERGED=.FALSE. RETURN 20 CONVERBED=.TRUE. RETURN 5. ZAKLJUCEK S tem smo se na kratko Beznanili z naravo raCu- nalnika ICL DAP in naCinom programiranja, ki je primeren za takfien raCunalnik. Iz teh spoznanj moremo sklepati, da je ueinkovitost raCunalnika ICL DAP za reSevanje tako linearnih kot neline- arnih p.d.e. izredno velika. To dejstvo je preprieijivo potrjeno tudi e strani uporabnikov tega raCunalnika. Drugi del prispevka bo posvefien programiranju TRANSPUTERSKEGA SISTEMA in optimizacijskemu postopku, ki je zasnovan na matrienem raCunu in ga je mogoCe uCinkovito izvajati le na paralel- nem vektorskem rafiunalniku. Omenjeni postopek se lahko uporablja kot uCinkovito orodje za implementacijo uporabniSkih algoritmov, ki vse- bujejo velika Btopnjo inherentnega paralelizma, na paralelnem vektorskem rafiunalniku. h. REFERENCE /i/ Flynn M., IEEE Transactions on Computers, C-21,9, pp. 948 - 960, 1972. /2/ Barlow R.H., The Neptun Procecsing System, Loughborough University o-f Technology. /3/ Johnson D.,et al., Automatinc Partitioning o-f Programs in a Mul ti processor System, Tt?xas Instruments, Austin, Texas, 1979. /4/ Sauber W. , A Data-flow Architecture Imple- mentation, Texas Instruments, Auetin, Texas, 19S0. /5/ da-5ilva J.G.D., Woods J.V., Deeign of a processing subsyštem iar the Mancheeter data—flow computer, Proceedings of the IEEE, 128,5, 1981. /6/ Hwang K. , Briggs F.A. , Computer Architec- ture and Parallel Processing, McGraw-Hill Book Company, 1985. /7/ Kogge P.M. , ThB Archi tecture o-f Pipelined Computero, McBraw-Hill Book Company, 1981. /8/ Robie B., Silc J., Razvrstitev novogene- racijskih raCunalniSkih arhitektur, Informatica 10,4, 1986. /9/ Hockney R.W., Jesshope C.R., Parallel Computers, Adam Hilger Ltd, Bristol, 1981. /10/ Foster C.C., Content Addrecable Parallel Processors, Van Npstrand Reinhold Company, 1976. /11/ HsiaD D.K., Advanced Data Baee Machine Architecture, Prentice-Hal1, Englewood Cli-f-fs, N.Y. ,1983. /12/ INMOS Limited, OCCAM language overview, November 19B5. /13/ INMOS Limited, Transputer architecture, November 1985. /14/ INMOS Limited, November 19B5. /15/ MihovilovičB., IMS T414 Traneputer, MavriC S., Kolbezen P., Transputer - osnovni gradnik veCprocesor- skih sistemov, In-formatica 4/81, 1986.