94 IZBIRA JEZIKA ZA PODATKOVNO VODENE RAČUNALNIKE P. KOKOL, M. OJSTERŠEK, V. ŽUMER TEHNIŠKA FAKULTETA MARIBOR B. STIGLIC - ISKRA AVTOMATIKA LJUBLJANA UDK: 681.3.06 POVZETEK - V članku opisujemo lastnosti programskih jezikov, ki so primerni za programiranje podatkovno vodenih ra- čunalnikov. ABSTRACT - Language evaluation for data flow systems. In this paper properties of programming languages suitable for data flow systems programming are given. 1. UVOD Večina današnjih računalnikov temelji na več kot trideset let stari von Neumannovi organizaciji. Ti računalniki so sekvenčni, opravijo eno operacijo na časovno enoto, ima- jo en sam procesni element, sekvenčno centralizirano kontrolno enoto, nizek strojni jezik in linearen pomnilnik s fiksno dolžino celic. Da se poveča hitrost takšnim raču- nalnikom, je potrebno povečati hitrost posameznim enotam računalnika. Vendar maksimalna hitrost, omejena s hi- trostjo svetlobe, ne bo zadoščala za kompleksne izračune, kakršne lahko pričakujemo v prihodnosti. Zato računal- niki prihodnjih generacij temeljijo na arhitekturah, ki do- voljujejo paralelno delovanje in s tem omogočajo, da se mnogo operacij izvrši naenkrat. Od paralelnih arhitektur, ki veliko obetajo, so za nas zanimive podatkovno vodene arhitekture. Delovanje teh je asinhrono, kar pomeni, da vrstni red izvajanja operacij ni določen z nekim central- nim kontrolnim mehanizmom, ampak se operacije izvr- šijo takrat, ko imajo na voljo vse potrebne vhodne argu- mente. Podatkovno vodene programe predstavimo kot us- merjene grafe, katerih vozlišča so operacije, povezave pa predstavljajo pretok podatkov, zato jim pravimo grafi pretoka podatkov. Dobre lastnosti podatkovno vodene arhitekture so: a) asinhrono proženje, b) velika možnost paralelnosti, c) velja pravilo enkratne prireditve, d) nadzorne ali kontrolne enote niso potrebne. Slabosti podatkovno vodene arhitekture so: a) da je potrebno pri vsaki operaciji s polji ali zapisi prenesti celoten podatek, kajti podatkovno vodeni mo- deli nimajo pomnilnikov, kamor bi te podatke sprav- Ijali, b) da v primeru, ko algoritmi vsebujejo premalo para- lelnosti, so te arhitekture manj učinkovite kot kon- trolno vodene. Zaradi naštetih slabosti podatkovno vodeni računalnik ni primeren za splošno namenske računalnike. Njegove do- bre lastnosti pa kažejo, da je uporaben za vodenje proce- sov, robotiko in superračunalnike. 2. PROGRAMSKI JEZIKI V zadnjih letih so bili razviti mnogi prooramski jeziki, ki omogočajo hkratno izvajanje programov (Ada, Modula, Concurent Pascal, Edison, razni dialekti Fortrana...). Slabost teh jezikov je, da so jezikovni konstrukti, ki omo- gočajo hkratno izvajanje programov, le pripomoček pro- gramerju, da pokaže prevajalniku, kje so možne paralel- nosti. Ti jeziki so nenaravni, kajti prilagojeni so siste- mom, na katerih se izvajajo, ne pa načinu, kako človek (programer) razmišlja. Če opazujemo razvoj program- ske opreme, na eni strani,vidimo, da se je pojavila t.i. "softverska kriza", ki bi jo lahko rešili z uvedbo mnogo višjega programskega jezika, ki bi zadovoljeval množico zahtev t.i. "referential transparency" /7/. Na drugi stra- ni, pa razvoj tnaterialne opreme z uvedbo VLSI teži k vse večji paralelnosti in k vse bolj paralelnim arhitekturam. Tudi jeziki, ki bi ustrezali takšnim arhitekturam, bi mo- rali zadovoljevati natanko enake zahteve kot so zahteve "referential transparency". 2.1. Paralelnosti v programskih jezikth Vidimo, da tako razvoj materialne kot razvoj program- ske opreme zahteva uvedbo jezikov, ki bi omogočali eno- stavno (blizu človekovemu načinu razmišljanja) in učin- kovito izražavo paralelnosti. Zato si poglejmo, na kak- šne načine se paralelnosti pojavljajo v programskih jezi- kih/14/: a) eksplicitna paralelnost - pomeni, da je program na- ravno paralelen (inherentna paralelnost), ali da so za paralelnost dodani posebni jezikovni konstrukti (forall zanke, cobegin itd.), b) lokalna paralelnost - pomeni, da se paralelnost odkri- • va v majhnih delih programa (interproceduralno) kot so bloki, zanke itd., c) globalna paralelnost - pomeni, da je za odkrivanje pa- ralelnosti potrebna neka globalna intraproceduralna analiza, ki je nepraktična in neučinkovita, d) neodkriljiva paralelnost - ta nastane zaradi odvisnosti med podatki ali zaradi neučinkovtte predstavitve pro- grama.. Postopkovni programski jezikl z globalnimi špremenljivkami, stranskimi efekti in nestrukturira- nimi jezikovnimi konstrukti (GO TO, aritmetični if stavek) vsebujejo v glavnem neodkriljive paralelnosti. P-ralelnost lahko odkrivamo na treh nivojih: a) na algoritemskem nivoju (npr. program v zelo viso- kem programskem jeziku ali posebni paralelni algo- ritmi) odkrivamo paralelnosti, kadar programski je- zik omogoča zadostno abstrakcijo algoritma in vsebn- je veliko eksplicitnih paralelnosti, b) na nivoju izvornega jezika (npr. program vvisokem programskem jeziku) odkrivamo paralelnosti s po- 95 sebnim predprocešorjem. Te paralelnbsti zaradi slabe reprezentacije ne moremo odkriti na algoritemskem nivoju, c) v času izvajanja (npr. program v strojnem kodu) od- krivamo paralelnosti dinamično. To postane nepraktič- no, kadar se mora paralelno izvesti mnogo instrukcij in torej ni primerno za moderne VLSI arhitekture, ki omogočajo hkratno izvajanje več tisoč instrukcij. 2.2. Lastnosti programskih jezikov Programske jezike lahko razdelimo, kot so prikazani na sliki 1. Programi pisani v postopkovnih jezikih imajo naslednje pomembne lastnosti: a) Uporabljajo model s stanji, kar onemogoča učinkovito paralelno izvajanje in zahteva uporabo arhitekture s stanji. b) Uporabljajo kompleksne nematematične strukture, s čimer otežkočijo ali celo onemogočijo odkrivanje pa- ralelnosti ter optimizacijo, preslikavo in verifikacijo programov. c) Uporabljajo globalno okolje, kar povzroča velike od- visnosti med podatki, s čimer omejujejo paralelno iz- vajanje in dekompozicijo programov. d) Izvajajo operacije z eno besedo podatka na časovno eno- to, tudi če mora biti ista operacija izvedena z mnogo besedami (von Neumannovo ozko grlo). e) Preslikavajo "pomnilnik" v "pomnilnik", zaradi tega so nefleksibilni in jih je težko sestavljati v obsežnej- še programe. f) Povzročajo veliko semantično vrzel med koncepti viso- kih programskih jezikov in koncepti obstoječih arhitek- tur. g) Omogočajo samo deterministično programiranje, zara- di tega jih je težko uporabljati za reševanje problemov umetne inteligence, ki zahteva heuristično obdelavo podatkov. V nasprotju s postopkovnimi jeziki pa nepostopkovni jezi- ki vsebujejo mnogo lastnosti, ki omogočajo izražava pa- ralelnosti, enostavno verifikacijo programov, sestavljan- je programov v kompleksnejše programe idr. Lastnosti posameznih jezikov so podane v tabeli 1, kjer imajo okrajšave naslednji pomen: S model s stanji N programski jezik vsebuje nestrukturirane konstrukte G programski jezik uporablja globalno okolje P paralelnost SE možnost sestavljanja manjših programov v večje PR postopkovni jezik NPR nepostopkovni jezik V možnost matematične verifikacije programov R repetativen - vsebuje konstrukte za ponavljanje (npr. zanke) ND oimogoča nedeterministično programiranje. Značilnost definicijskih jezikov je t. i. pravilo enkratne povezave. Zaradi tega pravila so definicijski jeziki zelo primerni za verifikacijo programov in za programiranje podatkovno vodenih računalnikov. Logični jeziki omogočajo paralelno in logično programi- ranje. Predvideni so za programiranje računalnikov pete generacije in tudi za podatkovno vodene računalnike. Objektni jeziki uporabljajo kot osnovo t.i. sporočilo /ob- jekt - model in ne bolj znan operator/ operand - model. V objektnih jezikih definiramo pbjekte ali razrede objek- tov (ti imajo skupne lastnosti). Objekti vsebujejo tako deklaracijo (opis) podatkov kot postopke za obdelavo teh podatkov. Če hočemo izvršiti kakšno operacijo, pošljemo določenemu objektu sporočllo, ta izvede ustrezno akcijo ali pošlje sporočilo drugemu objektu. LlSP-ovski in čisti funkcijski jeziki vsebujejo tri vrste struktur: procedure, izraze, spremenljivke in konstante. Glavne značilnosti funkcijskih jezikov so: - ne vsebujejo ponavljalnih struktur, prireditvenih stav- kov in spremenljivk, - preslikujejo objekte v objekte (teh objektov ne smemo zamenjati z objekti v objektnih jezikih). Čisti funkcijski jeziki so zelo primerni za programirahje podatkovno vodenih računalnikov kakor tudi za druge arhi- tekture prihodnosti kot so Magov /8/ računalnik, reduk- cijski računalnik idr. Programiranje v redukcijskih jezikih je dosledno funkcij- sko in temelji na enostavnih matematičnih konstruktih, ki predstavljajo strukturo binarnih dreves, iz katerih z re- kurzivno uporabo sestavljamo kompleksnejše izraze. Ke- dukcijske jezike uporabljamo predvsem za programiranje redukcijskih računalnikov. Vsi trije tipi jezikov pretoka podatkov (JPP) so si zelo podobni v svojih osnovnih lastnostih. Vsi predstavljajo abstrakcijo grafa pretoka podatkov.za neki algoritem. Razlika med grafičnim in visokim JPP je podobna kot raz- lika med opisom algoritma v psevdokodu in opisom algo- ritma z grafičnimi pripomočki, kot so npr. diagrami po- teka. Kodirni JPP pa je s posebnimi instrukcijami opisan graf pretoka podatkov. S stališča verifikacije, dokumentacije, preglednosti in ob- sežnosti (programa, ki obsega samo nekaj vrstic teksta v visokem JPP, bi obsegal več strani in množico povezav v grafičnem JPP) mislimo, da je iz trojice jezikov preto- ka podatkov visoki JPP najboljši. Visoki JPP vsebuje elemente (sintakso) postopkovnih je- zikov in semantiko čistih funkcijskih ter definicijskih je- zikov. Uporabljamo jih za programiranje podatkovno vo- denih računalnikov in za avtomatično programiranje. 3. LASTNOSTI JEZIKA PRIMERNEGA ZA PODATKOVNO VODENI RAČUNALNIK (PVR) Da bi jezik ustrezal podatkovno vodenim arhitekturam, • mora ugoditi zahtevama: I. Pretok podatkov se mora ugotoviti iz operacij programa. II. Potek izvajanja mora biti enak pretoku podatkov. Kadar programski jezik ustreza gornjima zahtevama, mo- ra imeti naslednje lastnosti: a) lokalnost efektov, b) ni stranskih efektov, c) pravilo enkratne prireditve, d) posebni konstrukti za iteracije, e) ni nestrukturiranih konstruktov, f) ni zgodovinsko občutljiv, g) ni globalnega okolja, h) ni spremenljivk (imena so le označbe vrednosti) i) primeren za arhitekture z asinhronim proženjem. Zgornje lastnosti omogočajo: - enostavnejšo verifikacijo programov, - paralelnosti se ugotavljajo interproceduralno (lokalna paralelnost), - paralelnosti se ugotavljajo na algoritemskem nivoju (program je zelo dobra abstrakcija algoritma), - jezik je bolj razumljiv uporabnikom in predvsem za- četnikom, - graf pretoka podatkov je naravna preslikava programa, - ustreza VLSI arhitekturarrt. 96 Vrednosti in imena Jeziki, primerni za programiranje PVR morajo biti vred- nostno orientirani, kar pomeni, da v programih uporab- ljajmo zgolj vrednosti, imena pa vam predstavljajo le oz- načbe teh vrednosti. Lokalnost efektov V postopkovnih jezikih je mogoče ista imena za spremen- Ijivke uporabljati v različne namene - v različnih delih programa. Če ne bi bilo enakosti imen, bi te dele programa lahko iz- vajali paralelno. Odkrivanje takšnih paralelnosti je mogo- če, vendar je enostavneje omejiti delovanje imen le na ne- ko določeno območje programa in kontrolirati vhode in iz- hode tega območja. Še bolje je, če se izognemo globalnim imenom, proceduram dovolimo le dostop do svojih para- metrov in strukturiramo programe v bloke. Lokalnost efektov torej onemogoča odvisnosti podatkov, ki so v raz- ličnih blokih. Stranski efekti Odsotnost stranskih efektov je nujen pogoj za enakost med pretokom podatkov in potekom izvajanja. Medtem ko lokal- nost efektov zahteva le nekatere manjše spremembe v je- ziku, odsotnost stranskih efektov zahteva spremembo na- čina obdelave podatkov. Zaradi tega prepovemo globalna imena in dodamo pravilo, da procedura ne sme spremeni- ti ničesar - niti svojih vhodnih parametrov. S tem odstra- nimo enostavne stranske efekte, ostangjo pa stranski efek- ti, ki nastanejo zaradi obdelave sestavljenih podatkovnih struktur (npr. polja ali zapisi), Pri teh je namreč skoraj nemogoče ugotoviti, kakšne odvisnosti podatkov povzroči sprertiemba posameznega elementa sestavljene podatkovne strukture. V takšnem primeru je treba vzeti največjo mož- no odvisnost podatkov, s čimer zelo zmanjšamo možnost paralelnega izvajanja. Temu se izocjnemo, da obravnava- mo sestavljene strukture enako kot skalarne, ter da v pro- cedurah parametre kličemo z vrednostjo in ne z referenco. Posledica tega je, da moramo pri spremembi vrednosti po- sameznega elementa sestavljene strukture zgraditi celot- no novo strukturo. Pravilo enkratne prireditve V prejšnjih razdelkih smo se odločili za vrednostno ori- entiran način programiranja. V tem načinu prireditveni stavek ne pomeni več prireditve vrednosti spremenljivki, ampak zgolj povezavo med imenom na levi in vrednostjo na desni strani prireditvenega stavka. S tem postane pro- gram enak sistemu matematičnih enačb, kajti kjerkoli v programu lahko zamenjamo izraz na desni z ustreznim imenom na levi strani, ne da bi s tem kakorkoli spreme- nili pomen programa. Postavimo še naslednji pravili: Pl: ime se mora povezati prej preden ga uporabimo, P2: ime lahko povežemo samo enkrat. S pravili P 1 in P 2 in vrednostno orientiranim načinom programiranja dosežemo, da v programih ni spremenljivk in da je prireditveni stavek kar definicija imena. Iteracije Zaradi pravil P 1 in P 2 se pojavijo problemi pri iteracijah, ki uporabljajo prireditvene stavke oblike: I : = I op J kjer so: I iteracijsko ime J ime op operator. Ta stavek je v nasprotju a pravilom P 1, ker zaradi pra- vila P 2 I uporabljamo prej, preden ga definiramo. Ven- dar so stavki takšne oblike zaradi iteracij potrebni. fre- poved uporabe nestrukturiranih jezikovnih konstruktov nam omogoča, da z ustrezno prireditvijo wliile-do zanke omogočimo iteracije, ne da bi kršili ostale lastnosti. Tako prirejena while-do zanka vsebuje: (1) deklaracijo in inicializacijo iteracijskih vrednosti, (2) test, če naj se zanka konča, (3a) če se zanka konča, definicijo izhodnih vrednosti, (3b) če se zanka ne konča, izraze, ki gcnerirajo nove vrednosti iteracijskih imen. Čeprav se iteracijske vrednosti spreminjajo, se to zgodi le v prehodu iz ene iteracije v drugo, tako da pravilo en- kratne prireditve še vedno velja, četudi samo v sklopu ene iteracije. Zgodovinsko občntljivo računanje Ena pomembnih lastnosti, ki jih mora imeti programski jezik primeren za podatkovno vodene računalnike, je zgo- dovinska neobčutljivost. Zgodovinska neobčutljivost po- meni, da procedure ne vsebujejo spremenljivk, v katere bi shranile podatke med posameznimi klici procedur. To pomeni, da procedure nimajo zmožnosti "pomnjenja", kar v sklopu z ostalimi lastnostmi predstavlja veliko težavo pri računanju v realnem času. Prepoved globalnega okolja in nestrukturiranih konstruktov Uporaba globalnega okolja in nestrukturiranih konstruktov nam oteži ali celo onemogoča odkrivanje paralelnosti in analizo pretoka podatkov. 4. VREDNOTENJE JEZIKOV V tem razdelku bomo ovrednotili jezike glede na lasnosti, ' ki jih mora imeti programski jezik za učinkovito progra- miranje podatkovno vodenega računalnika. Poleg navede- nih lastnosti v razdelku 3 smo ocenjevali še dve pometnb- ni splošni lastnosti: - preglednost programa in - možnost matematične verifikacije programov. Pri vrednotenju jezikov upoštevamo naslednje ocene: + . jezik ima potrebno lastnost, 0 jezik lahko ima potrebno lastnost, vendar se to od jezika ne zaliteva, jezik nima potrebne lastnosti. Spodnjo mejo primernosti dobimo tako, da seštejemo last- nosti označene s +, zgornjo pa tako, da spodnji meji pri- štejemo lastnosti označene z 0. Tabela 2 vrednoti posamezne jezike z upoštevanjem lastno- sti od a do i. Vrednotenje logičnili in objektnih jezikov ni realno, ker se struktura njihovih predstavnikov (Prolog, Smalltalk) ne ujema popolnoma s shemo našega vrednotenja. Iz tabe- le vidimo, da čisti funkcijski jeziki, redukcijski jeziki in visoki JPP vsebujejo vse zahtevane lastnosti. Visoki JPP so po sintaksi jezika bližji postopkovnim jezikom kot fun- kcijski ali redukcijski jeziki in zaradi tega bolj sprejem- ljivi za uporabnike vajene postopkovnega slila progrnini- ranja. 97 5. ZAKLJUČEK V članku smo na kratlco opisali jezike, ki so primerni za programiranje podatkovno vodenih arhitektur. Program- ske jezike smo razdelili v več skupin in ocenili njihove lastnosti. LITERATURA 1. Data - flow computers, IEEE Computer, Vol. 15, No. 2, Februar 1982. 2. Ackerman, W. B. Dennis J. B., VAL-A Value oriented Algorithmic Language, Preliminary Reference Manual, MIT Laboratory for CS, W79. 3. Japanese Computer Technology Culture, IEEE Com- puter, Vol. 17, No. 3,'Marec 1984. 4. Treleaven, P. C, i.dr., Data - Driven and Demand - - Driven Computer arhitecture, Computing Surveys, Vol. 14, No. 1, Marec 1982. 5. Lerner, J. E., Data Flow arhitecture, IEEE Spectrum, Vol. 21, No. 14,April 1984. 6. Kokol, P., Stiglic, B., Žumer, V., Pretvorba aplika- tivnega jezika v grafe pretoka podatkov, ETAN 1984, Split. 7. Turner, J. D., Sequin, C, Discusion on Very High Level Languages. 8. Backus, J., Function - level computing, IEEE Spe- ctrum, Vol. 19, No. 8, August 1982. 9. Backus, J., Can Programming Be Liberated from the von Neumman Style?, Communications on the ACM, Vol. 21, No. 8, August 1978. 10. Cox, J. B., Message Object programming, An Evelutionary Change in Programing Technology, IEEE . Software, Vol. 1, No. 1, January 1984. 11. O'Keete, R. A., Prolog compared with LISP?, SIGPI.AN notices, Vol. 18, No. 5, Maj 1983 12. Fifth Generation Computer Systems, edited by T. Moto - oka, North Holland, Pub. Co., 1982. 13. Berkling, K. J., Reduction Languages for Reduction Machines, Proc. Second, Int. Symp. on Computer Architecture, April 1975. 14. Flynn, M. J., Hennessy, J. L. Parallelism and Representation Problems in Distributed Systems, IEEETrans. on Computers, Vol. 29, No. 12, De- cember 1980. 15. Hoare, C. A. R., Programing: Soucery or Science, IEEE Software, Vol. 1, No. 2., April 1984. 16. Kokol P., Aplikativni jeziki in njihova interpretacija v realnem času, Magistrska naloga, TF - Maribor. programski jeziki lgoritmični matrični zorčni finicijski unkcijski (aplikativni) jeziki pretoka podatkov (JPP ogični ijektni USP-ovski isti funkcijski redukcijski Slika 1: Delitev programskih jezikov