ö'o i nt orma t i ca :• YU ISSN 0350 5596 SISTEM ZA ŠALTERSKO POSLOVANJE V BANKAH IN NA POŠTAH računalnišh' sistemi dekta Sistem za šaitsrsko poslovanje je sodobna računalniška oprema za delo v bankah in na poštah, opremljen z ustrezno programsko opremo. Sistem omogoča samostojno ažurno poslovanje - od posameznih operativnih del na šalterjih do zajema podatkov za nadaljnjo obdelavo. Deluje lahko povsem samostojno ali v povezavi z glavnim računalnikom (prenos informacij je mogoč prek stalno najetih ali navadnih telefonskih linij). Delovanje sistema tudi ni odvisno od razpoložljivosti računalniških kapacitet glavnega računalnika. Sistem nadomešča raznovrstno opremo, ki se uporablja pri šalterskem poslovanju - od klasičnih mehanografskih stro-iev. Disalnih stroiev do kalkulatoriev in deloma mikročitalni- Sistem za šaltersko poslovanje je savremena računarska oprema za rad u bankama i poštama, opremljen sa odgovar-jajučom programskom opremom. Sistem omogućava samostalno ažurno poslovanje - od pojedinih operativnih poslova na šalterima do zahvata podataka za dalju obradu. Može da radi sasvim samostalno, ili da komunicira sa glavnim računarom (prenos informacija je moguć preko stalno iznajmljenih ili običnih telefonskih linija). Rad sistema je takođe nezavisan od raspoložijivosti računarskih kapaciteta glavnog računara. Sistem zamenjuje raznovrstnu opremu, koja se upotrebljava u šalterskom poslovanju - od klasičnih mehanografskih mašina, oisaćih mašina do kalkulatora i delimično čitača a T [I.::! CasopLü izda3a SlovotvuKo druàtvo Irvformattka , òiiliflO Ljubljana, Parmova Jl, Jugoslavija Ur tiiin i àk i oübor : T. hìàkaié, DeociràJ; D. üitrakov, Skopje; P. Dragojlüvic, Rij'eka; S. Hodiar, Ljubljana; B. Horvat, Maribor; A. Mandile, Sarajevo; S. Mif.alić, Vdrüidin; S. Turk, Zagreb ČASOPIS ZA TEHNOLOGIJO RACUNALMIŠTVA IN PROBLEME INFORMATIKE ČASOPIS ZA RAČUNARSKU TEHNOLOGIJU I PROBLEME INFORMATIKE SPISANIE ZA TEHNOLOGIJA NA SMETANJETO I PROBLEMI OD OBLASTA NA INFORMATIKATA YU ISSN 0350-5596 Glavni in od-vcvorni urednik: prof. dr. Antuj. P. Seleznikar LETNI K 10, 1986-ŠT. 3 T»ihn i ćti I urednik*, d v. Rudo 1f Mur n Z a 1 o ž n i ii k i s v g t : T. Uar\üv«c, Z^vod SR Slovenije uLatistikO/ Voiai>jki pgt, eißÜÜ Ljubljana; A. Jerman-t I a £ J č , ÜÜ lakrü Delta, Parir.ova 6 1 L J ubi j <1 na ; b. Klenihinčic, l^kt« Tù i tjftiat i ka , 6diJv50 Krčitjj; S . S a k r^-1 d a , i n u 1.11 u L z i» rvci c i 01 o g i J o Univerze Edvarda K a r d »i I j a , 6 I ti ö J Ljubljana; J. Virant, FaKjlt.kita zj e 1 «k t ro tehru ko , Triaàka 2 C-, 6 1 üijü Ljubi jana , P. Brajak B. J . S i 1 C Ü . Frctštsrn . . . 1. Oaifiiek ... b . J t; I" w a n - I» 1 il £ i r. F.ibi^ V S K H J N A i t'arai lei Pr uce ri i ri-j : Archi-of t.ht.' I99i?'t; Ll Ur« ChuOüifKj H l'iari far t-h« Kxecution of Data Flow Prc-y f a Ri Graph I'd Paralelno proceyxranjt sììik V i dfeoterroiria ) PMT-lk^tJ 2C Tr i tii vojtfKa i h i L k t u i a in- ro t niac i J sk i h f: i s;t n^o v po u.odfelu ISO TCyV/DP Uredniitvo in uprava: Inforiuatica, Parmova 41, 61000 Ljubljana, telefon (»61) 312 988; teleks 3V366 YU Delta. Ltftna ji t oč ti za delovne organizacije ssnaša din, za zai^ebne naročnike 1590 din, za itudentir đ'jk) din; pouaniezna àtevilka 20öt} din. številka žito računa: 1 y 1 - 6 7 8 - 5 1 6 4 1 Pri f i ncinc nan JU časopisa sodeluje Raziskovalna s k li p lì o Ü t S i o v ei n 1 J fe Ka podLdt^L mnenja Republl&kega komiteja za in-fcrmirarje it. 23-Ö5, z dne 29. 1. 190G, je časopis oproščen temeljnega davka od prometa proizvodov Tisk; Tiskarna Kieuija, Ljubljana Grafična oprea.a: Raato Kirn B . Z a v r ä 111 k S.J.DjordJevlci 41 M. MJ Iekovič ß. Vilfan ... H. Ma 1ekov i Ć P. Kolbezen B . Mihovi lovi Ć B2 S 7 61 Siuteoisko vodili. Multibus I T Ot«janizacije ključe v ^ u oc -cjan i 15 ac i j ama poda t akci la.plikacioni prohien. ^a vi-šeanačne zavisnosti 1 tneha-ničkcj dokazivanje teorema Ocena proyramskih orodij IDA Podakup-zav 1snost1 u rela-cionim bazama i mehaničko doka z i van Je teorema Mikroprogran.i ranje s pretokom podatkov Nove računalniške generacije PuLlishfed by I r» f ü r ».a t: i k d , Slovenci SocieLy fui I r. f o r ma 11 CS , Patmova 41, 61000 Ljubljana, Yugoslavia Editorial Board : JOURNAL OF COMPUTING AND INFORMATICS T. AleKüic, beoyrad; D. Bicrakov, Skoi)jb; P. Dr dcjoj lov 1 ć , EJiJiika; S. Mocliar, Ljubljana; B. Hurvat, Maribor; A. Mandile, Sarajevo; S. Mill allò, V^raidin; S. Turk, Zagreb YU ISSN 0350-5596 Editor-ir-Chitf: l^rof. Dt . Anton r'. Selcaiilkat VOLUME 10, 1986 - No. 3 Exisc'.itivsi Editor: L'f. Hi.idü i f Murri Hub 1 1 sh ! ri.j Council: T. Banovfec, 2avod iJR Slovenije za statistiko, Vožarijk: po L bii3ü0 Ljubljana; A. Jer uian-E I ai 1 č , DÜ Iskta Delta, Parmova 41, blkiaa Ljubljana; B. K i 1 č , iakra Ttì 1 e ma 11 ka , 64800 Kranj," i;. I n i 1.1 t u t -ia i;ocioluyijo Uiiivc-r2tj Edvarda Kardelja, 61000 Ljubljana; J. Vitant, F«.kvilteta elektrotehniko, Triaàka 2ü, C-111ì;;i Ljubljana. P . li r a j a k B. Robi è J . All.: . 1 e à e r 11 I. CtKimek . C O N T E M T t Parallel Pi .••vf.t, i; i r.g ; Archi-tücrf'ire of thü !9yP'a n On ChooKing a Plan tot the E«fecutioi. of Flou Pro- gram Gl aph 1 0 i 2 £l. Jfi u.an-Li I ai 1 4 26 ! . F a b i r Parallel Iroage Processing Videctermlnai PMT-I0B 'fliitie Level Al .-h 1 lecture of an IS Accoidiiij to trie Mollici Ol laü/n:«//UP y«H)7 H e a d q u a r t e t s : I rtf o r ma 11 ca , tarmova JI, Gldüia Ljubljana, Yugoslavia. Phone: 61 31 SO. Telex: 31366 yu delta Annual Subscription Rate: US$ 22 for companies, and U3S liS for individuals •Jpinicns expressed in the con t r 1 bu t i on a are not necessarily stoired by ttie Editor ial Board Ptinted by; Tiskari-.a Kresija, Ljubljana B . 'i a V r a n 1 k S.J . U jurd j ev ić M. Holekuvić 8. Vi Itali ... H. Maleković P. Ko lb.::; en U . M 1 h o v i 1 o v i 1 ;ied to tüe (>ol.)C thdt ta oce.-,sor:: rietid no longer be co/ii;idered a scüt ce re^obi i:es. i^-ond sot tware is increaüing, both in ab^iolutù terras -...a .joa^pariđOii with the coat of hardware on which it execL.Le6. 'IT.e civaiiäbUicy ot large numbers of inexpensive fJroceasiiKj elciuénts quite .liturally suggest the possibility of constructing highly concurrent aysteaia capable of very rapid executions. This paper briefly surveys recent results in the field of parallel processing. The reaults show that the rapid progress has been achieved and that the parallel processing can yield high performance. il:cy a^so show that the major research issues still jeuialn to be iid.lressed. 1. latrodu-.cioii ik- iir tiuj eta üf 1 undamejital c!:ar. il. the field ül computet ch i tuccuic . in particular, a large part ot Cheat- changes i» reisreaonteU by a transition [fora the aerial to parallel proceüing. This I.I C ior. ii stimulated by at least four 1; the ..oit ot digital hardware has dropped to the point that processors need not be cutiSidcred a scarce resource regards : 1) wayi oi conceiving basic algorithjuic programming problems. and developiir-i new software tools (languages, ■:.oKpilers, operating systems, cüimuuriication mechanisms etc.). 3 i developing non architectures. Von Neuoian computer iiript OVciLer.t of aioi'iL/pt :;ceosors is limited. performance of technologically 3) tlie scope of problems whose algorithmic ■-ciaplexity exceeds the capacity of the today aiost powerful computers is very large, 4) the rormulacions of these problems naturally suggest their parallel realization. Parallel piocessing can iiot guarantee to produce all desired performance levels in speed, t ciiat-'il 1 ty, accuiacy, availability etc. Its liiLÌts are far from well known yet. On ttio other iiand, it Is certain that parallel processing requires large changes as For these reasons the basical question is wliether parallel processing can reach high levels of the desired performance. In other words, whether It Is worth such changes. This paper tries to explain certain problems regarding these changes and tries to present some of the research work that has been accumulated In recent years. Primarily, the paper is concerned with the problems due to changes In developing new parallel architectures. first, we are presenting a short discussion of measures and metrics used in evaluating the performance ot the parallel systems. Afterwards, we will give an overview of some characteristics of the moat typical examples. I") originally presented as an invited paper at Mll'RüBB, Symposium on Hew Generation of Computers, section Comp. Arch., üpatija. May 14-16 15B6 Tdxor.omieä It Js safe co say that all computers made today ustì concurrency to Improve their speed. This para lidi 1:4111 Is manifested on several levels : 1) inside tlie ar 1 tlirae t Icdl and logical un 1 s : - tid/ibJei by uoids rathdr than bits, - X/E oveI lapi, - Cart'y Look Ahe.nJ, ecc., Z) inüiürr ciic C'Titial procsäsof - lJipeiir.ii;>), - :o'.,i;c,i iufiOUlùnai unita, J I inäiüe a aionopt ocu-ss.or ■ 1/0, - carl.c-, - interléàviny, t-ctc., 4) and principally - inside multiprocessor ayatein. He cìiinK tt\al: there are no fully developed Cä:<',no!üieü chat can cover all characteristics òf patalU-l co.Tif-uter circhi tectures. Tlie widely uicd one based on SIl-lD, MIMO modes ot operation is not appr;ipriate, since it does not sii-.^ij diversity oi alsjori thmic and applicati-in feacur--s Lhat luodern computers use in Older to explote concurieiicy. 'ii-.ereiorc-, we uho'.,- Chtee different tuionciiied, tiicl rtie one based on modes of operations, i-.-cond the one based on applications tl..:;y usually run and third the one based on types ot alyurithiiis they exploit. Based on the uioue of operation parallel cosnpucet coulj be in one of the followitiS, (ìgì-l-w: , là Inadf.^iuatu tor vector type ■■if paral lr.'i ayott-jiià tlirtt opci aie in ainqle iijütruct;on aulliplc lutj moüe ol' operation-T'r.ey jcì.ì/vof concut-rency potloriainq d nuiaber of ilit fet-fnl Operations with a äintfle i nat-ruc t ion. òJightly b'-'iter. thou-jn still tar from guoU aietricš i»«.- MfLOFS (million i'loatiiKj point operations per secono i and HLÜPS (million lo()lcdl opetätlona per aeconJ). KFLOPS is used di ipe<--d aetric tor àuporcoinputers while MLOP£ là preferred with the fifth generation cocputers. The proMem with these units is that chèy provide vdluahle results only for coiipucations witli doiainant arithmetical or loLjlcal operations. Another problea. is th-.it it is not possible to define a priori tlie üpoed of new, unfaii.illar programs. Iri oiiner „ords, it is impossible to say that the nachiiie with X MFLOFS rate is ijoing to solve a probicu. ir. tlie H/X seconds knowing that the specific problem has M iiUEber of coißputer instructions. For Biultiprccessors, data flow machines and other pjiaile; sysCeic.-; tliat operate asy iici.i-lii-:-.JV..J i y jf. tne (iveri of data, the prob.U-in is t-ve:i haidèr, Ml'Lür'.S is not an •idequate metric since Miese iystems do not exfiloit concurrency b^,sed on one instruction moltlpifc data principle. MIPS, on the other aide is inadequate since It does not take into account the degree of concurrency. Very often we use terms such as speedup and efficiency as tfie luetrics that measure the perforKiànce as a function of parallellsm/l/. Let Tili - tìie liiiie required to execute Of; a siivjìe processor. Tip) - the time le^uired to execute tlie sanse job using p procesooro. then .Speedup: Ut p/ T( li T(pi üipi ■ Tili Efficiency: £(pj ^ ------ - ------ . p pT(p) Anothei. very useful definition of efficiency is Efficiency; Kip) - --- P where A represents ttie nu.iiber of usefully active processors. This defir.itlon gives a notion of concurrency. that is, a quality of a given algorith:E. Hultiproceasora can, at best, reach a linear speedup. That is, :J of processors can be at best i/tJ tiite the speed of the monoptocessor. Àaong the factors tliac effect the non linear speedup are; synchronization. algorithm set i ali i:a t ion, inter-processor coiurauiiications, comuion resources, iriput/output etc./2/. Vector coihputers The Vector computing is tlie most frequent forji of parallel i .-jiii w.ltl] aiodein computers. The reason simply is the equipara t i ve ly simple architecture which ericibles a simultaneous processing ot only thri regularly ordered vector elemento . Kur thei ta-.^i e . che additional prjce of the vector compared to Che already existing segueni.ial one is relatively small. Altliougli the vector computers do .lOt uelong to real parallel systems they liave to be included ill each grouping of such -ystenis since they are the only ones cojüiuercially used tot' quite some period ot ciiae. For tlie:ie, the largest rajinber of sampie cases have been written, new algortthuis developed and comparisons made. Such, tliey are or high importance for the development of future systems. Vector processing is based on employing two aspects of parallelism: on pipelining/4/ and on employing multi functional units/5/. In pipelining the speed increase is obtained tlirough instruction overlapping. Mostly it based on execution of a single instruction on vector elements that uiiiforicly streaiti tlirough the pipeline. The major characteristics are: - aynchroniaiation is siep^le: based on d.Hta structure of operarids; once all opeiaiids are in order and pipe activated, relative order of results is assured, - die results come out of the pipeline by the speed determined by tlie speed of its slowest segment, increasing the number or segments, tlie total pipe speed is increased as well, - better for operations on long vectors (relatively smaller start-up time), - degradation is enlarged with jumps interrupts, scalar operations, - pipelinig can be successiully and easily applied to arithmetic operations. In vector computers with multi r'unctional units each unit independently executes predetermined operations simultaneously witt respect to other units. rtost frequenCly vector coKpucers uje urne s for addition, multiplication, addresses generation, noriiiali^ation etc. Multi functional units have the following characteristics: - synhroniv;atioii is more complicated: based on data availability, - instiuction dependency is usually resolved using additional coordinating unit, - there must be a meclianism for instruction queuing: stack. - technique Is better for p«ublems that Ccin be onjaiiiiej in short fast inđLfuctioti loops. The l^ijijest piolUeiu with vector computers Is not the co.'ap]ek:ity o£ hata^are, hut the alaorithais that can be tound emboüyimj Pdtólj.;; cuJv de.,iiiiont£. llie Amdahl's law theorerjcdlly sliOWà tlu.- potential degradation oi vector computer operations; the experiiiice ^ähcws how haid it is to adapt algori that i;..; vectot computers /6,7/. The •iyriätüic- rtjt'..ie o: noi. .'aiinerical progiaws; •iata -acpciid-iricy, inttrrrupts brtj-ik the regular data ilov.- tlw.iu.ih vector units and so reduce tti..- paia J Jfi i i.,1,. This is evident, t roai the iollo-ing Ji.ici; displays speeds ot fastest contompuiat j vortor computet s on saiiiples 14 test pi (.»yt ams iroiii Laurence LiveniiOre Hational Lai-uraLoty/a/. 1 I !.. i Si.nu,i.s Vf.iui * <»M llir saiu.-tt sef SX l Ci.H ituwp Vtu<.il< v liM ili H\P V02 M FurvM SX H»» I"«* Ifh-s «li| l-Alf Vt«ck IV«6 %Wck <«6 Mb.^ . Mft.*.. M**."» MOü»/» in ) . . Ì 4 i »•J». J 1-V. } •ni) > w * M ' 1 > . VJ? 1 :sv i 423 ? M ■ M: : i\v » :N. V Vài fr .» > - w i Itir. l t* 7 124 4 1« .< ■ i : 4 li 1 4 i 1'- «-. ; Il 1 :t*j ij ;< 1 . «■•: 4 v «J7 ; u> •• M ;; «.' 4 * <> f p IM a • VI t ■ f. . { ■ 4 :4 ih .i : 7i3 6 47 * H [.M t)7 1 VX U : .i 5 1 4 » .- i t 24 « JI } i 4 .■ H liti w 27« J : /1 : 1 O ? 0 1 7 il X 15 > R J 24 2 .'•IS : |i'4 t 2KM 2 ' ' f? 'V }1 5 t iaU ääya char when ■ d «Jüütt^UCdtlüJi if : percentage ol scalar operation vector processor quality: pipe speed related to the scalar one. then that is T-. pi ^ f*T(li + (l-f)*T(l)/p òpreuupipi = 1/(f+(1-f»/p) capabilities cutnponents pruccssor /. but due installed to the (memory. fastest scalar 5. Multiprocessors is pertorsiTd in two inodt-a of opeiatioii the net speed ii iiiwstiy detei mined by the computation speed of the siowei mode. rroKi the displayed diagram it is evident that foi vector coi.ipuLer s the quality of algorithms is uttei importance and that ^fily the highly i-i^aralelllzcd algorithms siutiii I t ^iiaintaiij tlic desired speed. In the last few yeai s a lai'ge ptogiess was achic-yeU in the t ield of parallel processing as cOficcrns mul t iprocessot systems. Several yea» s -»go multiprocessors were otily a tupic of a-.o^aeoiic re^earcii works iC.i.uiip, CM«. flutiLu;,, HEP-1Ù,] l,i:,13/; »hile t..da> und u ui.)-: idly tiiote ^re .-ieveiaj hundiedi ->r .-jllitillfl dlid ayot<.-lli;. tiaaed IJ!": l;iu 1 I I pfuCi-.',-i-ug .1,1 l.,ectui.il 14. . Li-ithu.-j la-.B ai'iLjcs 11 i. J Ili the facts that:? ■ can i-u obtained By a latget number ol amallet, cheaper proceasors, - speed OI sector and otiicr ilMD computers is bounded by percentage of scalar opeiations, - special purpose computers are not general and cannot can be used on larger class of problems. Most of today available multiprocessors ate neither in theoretical concepts nor in practical performance level characteristics that should be expected fron: a truly multiprocessor system. These aiachines Ijave not obtained the desired lesults due to: iiie:iiv>i y contentions arising accesses cowaotv memory. as each taak loo much time is tetjuiied to syncfaoniie tile ex-ciiange of data between tasks. Llie scheduling consuming, taskä tiiiie ■ the algorithms shoud be well developed tliat would enable the activity of all processors. The ultimate multiprocessor based ori Schwartz's "Patacomputer" /15, wuula be a general puipouse computer, fast as well as any special purpouse parallel computers, with unliniited number of processors and conflict tree access to the common memory. Such systems are presently the subject of reaseaich work with two dominant academic projecti, (CHUFP, Ul.'iKA ) / lo, 17/. Most -.-ther comiaercially aval i.iljlf multiprccebsors are based mainly on priiuitive 3ynchroni2ation and communication inechaniams with networks that do not support a large number of processors. Different trom vector processors uheie architecture is brought to its optimum level, multiprocessors still have no defined architectural standards. We can say that there are as many different concepts and solutions as there are multiprocessor systems. Tliere are two basic questions to be put regarding this topic: what processor convenient for processors? connection is most a certain number of Vectoi computers are still today tho fastest computers, but not due to their parallel are the systems with a processor access to the common memory "better" tlian those with message passing and local memories? • i t'i'ocčbjoi conr.fctions Ilic aiiiwtri tO ihe fiiòc ^'jeaCion is well k;iGWri a.-iJ ciiii bi' ùbtjiined by a siiaplitieU ;:di'_'uljitior] Ol network cjuiility which is •Jeriiiea ùù a q jotietiL ot it;i pet t oniiarice and price. pcM oriüa.-ice - F/T price = V ^ t; interpfoceasor communi cation is the luoat suitable one lor ^ a given number of processor-I. For a small number of processors i<=4) it is most coiiveniejiL if all processors are fully connected; for up to £•) processors the most convenient is to connect pioce.-fsors using cross-bat switch; and for those above ti4 processors the best quality show the permutation networks sudi as n-binary cube. w.htre P - r,ua,ber of aieusaqes in the network T - I'oui'id trip delay V ■■ ii,.»;ber ^.f link5 E - nuii.bei of network switches tiEl-ViORK MKSSrtCi;:^; DKLAY PERFORMANSE bvii t -V 1/2 r i n:^ !i N 1 n-cube H / Z 21ogW M/(41ogN) X-bar N 4 H/4 f. conn. N 2 W/2 METWüfiK Li.fJKi' iJUITCMES PRICE bus 1 N N+1 ring N tJ 2N n-cube N logt.'/2 .W + JNloglJ/2 .<-bar 2tl !if;/-l NN/4 + 2IJ f, conn 2 tJ!,' N+(tJN_N)/2 KLT/JORK WUA .LITV bus 1/ 1 iW-t-ii r i ng I / JiJ 11-cube il I logN ) croso-bat 1/1 N/2+4Ì fully c onn. l/(«>-l) 5.2 Coiiinion vs. Local Memory The clioice between common or local ineujory system is the ;iiost chal len^jliiy task and depends on price, v^enerality, speed, applicataon and nunibei: of processors an architect sets while choosim} a desiij/i for his multiprocessor. ociiwarfz /15/ showed thac Lti applications where thousands of processors cooperatively solve larije problems, the systems supporting hitjh speed concurrent access to the coiumoii memory are more efficient and less complicated for programniing. For a programer it is very important Chat the interprocesor network geometry is hidden and that each processor independently performs message routing along the network. In systems with local memories, routing is needed on the programniing level. Undoubtedly, the Increasing number of processors mounts the price of coitiiuon memory systems while the quality falls because of memory iequiierjenta collision. This can be observed froai the flooding of multiprocessors developed on Hypercube principle /18/, a network that supports message passing coiiiiiiuni ca t ion between local memorie:». It has a very jimpie geometry: in a m-pfocessor system each processoi" has its numbet fioii. 0 to iu-1. The I piocesaor is connected to lo^jvm/ pi'ocessors whose number differs from 1 in only one bit ot its binary representation. Tiie proof chat the increasing jf processor nuiiibei does not cause an increase of collisions in common memory systems is the "Conflict Free Memory" - U.S. Patent 254563/1^/ which proves that the access to Che common memory does not depend on the processor number and that synchronization can be performed using /letworlc switching elements. It s a very ojiginal idea, apllied in CHOPF, in ULTRA and In some other projects /20/. It is characterized by the following features : all processors can read any memory location simultaneously, all processors can read the SAME memory location simultaneousiy, / - all processors can write location simultaneously. into the same ...... I ! ft I « ij; - ____ From the quality diagiam we can see what This can be achieved using "intelligent" network switches, so that they intercept simultaneous requests for a single memory location and let only one request be present at the memory bank containing that location. Each node in the network must maintain a list of memory requests that have passed through the node to avoid sending out more than one request for a single memory location. However, multiple accesses to different locaCions in the same memory bank still conflict at that particular bank. Conflicts Call be ävolJeJ by a ataCiatical Inteileavimj ■-•f ^iieiaoiy loca.tions and by program specified inLei lcaviii-.) of code. Each procedüor must iiapleinötit a tixed , one to one, onto raappinij o: aeKory requests to the physical addresses in ti.e N iiit.-.'uory banks. nie mappimj must be fixtd and random. Thei c la another rt--luireinent for an jptimai use or such system. Frojrains must be (■resć;it-.-d to the processor in terms of tasks. I:. vjidc-i' to garaiitee full processor ut 11 iTidt.loii thi'ie must be sulficient number of tjoks activf- at all tlie times to overcoae the latency oi the interconnection network. It IS evident tiiat in the near future we can not -jxpect joiujiierci-i 1 ly available systems Chat «ouJvi suppoi t the above mentioned concepts fot a lar'.je number of processors. Not only becrtuse of weight on the architir-'tuta 1 level lexperisive and comp ! 1cated switches) but because of the sottwart equipment that stagnates considerably, ttowcver, these concepts, plus the soluLiüri for software synchronization, could be used as standards we should follow in building general purpose, highly parallel multiprocessors. Special fui pose Parallel Systems A Very popular way to increase apeed is to optiaiiie '.he coiamu/jj cat ion ■ structure among ptoceSoors iw that It corresponds to specific proble;3i Li.,«c j.'.oulu 1-.,= performed on it. The i-.li.'a I loui 1 :.-.iie'! Ill ■■'!,<.: lale 70 ' £ with the develcpiicnt 01 /1.31 tech!:..)loay lil/ and tJie belief Lhat coK.mur:i :ar. i jn li the basic factor in the pt let- OS p.iraii<'.-l processing. Such systems, lor the -price or speciality give --•ptiiual solutions in perrorinance levels ot the parallel coKputatiOns. oistolic piocessors /22^ are examples of proces.s'^jrs basel on neighbour to neighbour principlco. Coauuunicat lonal 1 y, they are optlmi-zed lür solving specific numerical probleiiis. A large number of raatheuatical oi.-erat 1 ^115, like maitics operations, linear e.juatioiii solutions, FKT can be hardwared to a corre.-:ponding pro-jessor geometry, giving ai.iiost ti.ecrctacally •-•ptinial results /23/. ;iistolic pi'-'Cesses are tiii.e synchronined and ^.perate -^ii t!:e piinciplo ol overlapping ilike in pip-.-l ining ; with diiference that all processors perforiti identical functions. Data elements sLteam regularly from one nei-glibout iii.j pr...ce3s jf to another . Such 1 low through processors is constant, without interrupts and optimal since all processors ate active. From tr.is technology more complicated and general ar ctiitectures wer e developed which art- often used in fields o£ artificial intelli-^jence. relational databases, computer vision, and in some other non-numerical applications. Simply saying, 5th generation computer architectures had emerged, based on the ideas from slstollc processor (putting algoritliai on interprocessor geometry) and ideas from the bO-ies when first associative computers were developed: PEPE, STARAI'!, ALAP, ECAM /25/. Tlie idea is ttiat memory values are not referenced by address but by a comparison of the very value (Content .Addressed Memory - CAI'l. A apecilIc parallel system for pruduction (expert) systems could serve as an example ot such a system. It Is based on the binary tree interprocessor geometry, which is ideal for searching problems. As we know, the production system is detined as a set of rules, productions, and a database, called working meniury (WM) . Each production consists of left hand side tLHS) and right hand side iKHS): ( ( ^x ÜN = y ) (- =z ON -X) (- -X uN =yi (ÜN -r) I Ttie tollowing cycle of operation is repeatedly executed: 1. Match: for each rule, determirie whether the ÜH3 matches tiit current environment of WH, 2. Select: choose one of the matctiing rules according to some predefined critetion, 3. Act: add or delete from WM all assertions specified in the RHS of the selected productions. ParallelisBi can be achieved at all chiee steps, especially at the tirst one where tlie need tor a CAM system Is stressed. The idea is that each production is stored ^n one processur element of a binary tiee and all pri/Ce.'isors tliat are aubtrc-es to this process'jr are part of Its WM. Example ot a functional distribution in a simplitied system (4 productions only) would be tlie follu-.Jing: synhronizatlon, selection, act WM Parallelism ot this ijyotem io manirested so that LH3 of :;acri production could be simultaneously compared to tlie content ot the corresponding WM. Eacli production processor (PP) sends to its subtree pattern elements of LHS. After KlogM steps where K is the nuiober of elements of LHS and KHS and M is tlie number ot WM processors, all PPa that matched LHS obtain the appropriate elements of the KHS. A selective step chooses one of the RHS in 21ogtJ steps, where N is the number of productions (a way to the top of the tree and back to PP). The third step deletes or adds the RHS of the chosen production to each WM in KlogM steps. Similar systems could be applied for relational data bases, expert systems, that is, for all forms of knowledge based retreivals /Jo,27,2a,Ji/. A very interesting concept of specialized pdraileJ systems is, by no doubt, the idea of reconfiqurably connected proceasors. The primary idea was initiated by CHiP project /30,31/ and nowadays lots of researchers work in this field /32,33,34/. It is a network of processors connected with switches such that before the program execution each switch performs a short program which defines the form of connectivity among the processors. As an example, if a data searching algorithm is concerned, processors configurate themselves in a binary tree geometry; if the matrix multiplication is concerned, processors are connected as a hexagonal array. Hie power ut these systems is that it is possible CO achieve the generality of multiprocesiots and the speed of specialized parallel systems. Froblenis encountered by such systems are similar to those encountered by multiprocessots : - complicated synchronization, - information propagation time is not equal for all processors, - memory conflicts. 7. "DATA FLOW" computers Data flow systems have the potential to becoae the moat prospereous arhitecture of parallel processing systems. What makes them so attractive is that: - they perform data dependency analysis at run time, thus repiesenting convenient way of exploiting implicit parallelism, - the numtjer of processors can be increased wittiout changing applications code. negative aspects, future trends and difficulties. possible - computation is deterministic, - parallelization is automatic. Experiments and following! experience suggest the 1) significant gain in speed can be achievied using concepts of parallel processing, even for systems with small number of processors, Z) a broad spectrum of applications can be applied to parallel processing, J i simple structures could be adequate to support parallel computation (this is true even for highly parallel systems). 'ITiese are the encouraging results, which however, should not diminish major research problems tliat remain to be addressed: 1) software and software tools: - decomposition and analysis of parallel formulation of algorithms, - debugging, - data dependency, 2) system problems: - I/O, - interactive graphics, - local networks, 3) highly parallel arhitectures: - measure and performance of highly parallel systems with thousands of processors. ACKNOWL£X)GHENT Authoi wishes to thank prof. A. Zeleznikar for many useful comments. ■Without him this work would not even be conceived. Tlie first and the third of these points are particularly appealing because on many iO-parallel systems computation is not necessarily repeatable. Since implicit parallelism includes explicit parallelism, dataflow is considered the most general operational principle for parallel processing. Although dataflow arhitectures enjoy popular support among scientists, their greatest disandvantage is the considerable large overhead that comes from the self-synhronizing manner of their parallel operations. It is especially evident in applications where the parallelism is primarly inherent in the data structure objects, or in simple repeatable concepts. Tills is the reason why relatively few systems are operational, and relatively little experience available. 8. Conclusion There are numerous encouraging results that prove that the rapid progress is being made in the field ol parallel processing. In this paper we give a broad overwiev of some of the most important classes of parallel processors, we show their positive and References /1/ Buzbee B.L., Applications of MIMD Machines, Proc. in Vector and F.irallel Processors in Comp. Sci., Oxford 1964 /2/ Jones A., Schwarz, Experience Usirig Multiprocessor Systems-A Status Report, ACM Surveys, June 1980 /3/ Amdahl Ü. , Tlie Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities, AFIPS 1967 /4/ Kogge P., The Arhitecture of Pipelined Computers, 19B1 /S/ J.E. Thornton, Parallel operation in the CDC 6600, AFIPS 1964 /6/ D.J. Kuck, Parallel Processing of Ordinary Programs, Advances in Computers, Academic Press, 1976 /7/ Rodrigue G., Glroux D., Pratt M., Perspective on Large Scale Scientific Computation, IEEE Computer, Oct. 1980 /8/ Steen A., Results on the Livetmore Loops on some new supercomputers. Supercomputers, Match 1986 /9/ Hüllenberg J. The Cray-2 Computer System, Supercomputer, 8/9 1985 /10/ Wulf W. A., Bell C. G., C.rampi A Multl-Minl-Processor, AFIPS 1972 /11/ Katsuki at. all, Pluribus-An Operational Fault Tolerant Multiprocessor, Proc. IEEE, 1978 /12/ Swan R.J, Fuller S.H., Sieworek D.P.. CM*: A Modular Multiprocessor, AFIPS Conf. Proc 46. 1977 /13/ Snelling D. HEP applications. Proc. In Vector and Parallel Processors in Comp. Sci., Oxford 1984 /14/ Lineback R., Parallel Processings Why a Sliakeout Nears, Electronics, 1985 /15/ Schwartz T. J, Ultracomputer, ACM Trans, of Ptog. Lang. 1980 /16/ A Gottlieb at. all. The NYU ULTRAcomputer - Designing an MIMD Shared Memory Parallel Computer, Trans, on Comp., 1983 /17/ Sullivan H, Bashkow T, A Large Scale Homogeneous, Fully Distributed Parallel Machine, 4-th Ann. Sym. on Comp., 1977 /18/ Seitz C. The Cosmic Cube, Communications of ACM, 1/85 /19/ Sullivan H., Bashkow T. Cohn L., private communications /20/ Bra jak P., A Design of a Fully Distributed, Parallel System With a Common Memory, Jahorlna 1985 /21/ Mead C. Conwey L., Introduction to VLSI Systems, 1980 /22/ H.T. Kung, C.E. Leiserson, Systolic Arrays (for VLSI), Sparse Matrix Proc., 1978 /30/ Snyder H, Programming Processor Interconnection Structures, Dept. of Comp. Sci. Perdue U., 1981 /31/ Snyder H, Intro, to the Configurable Highly Parallel Computer, IEEE Computer, 1982 /32/ S.P. Kartashev, S.I. Kartashev, Efficient Internode Communications in Reconflgurable Binary Tree, IEEE Trans, on Comp. 1984 /33/ 3. Yalamanchlli, K. Aggarwall, Reconfiguration Strategies for Parallel Arhltectures, IEEE Computer 1985 /34/ D. Hillls, The Connection Machine, MIT Presa, 1986 Petar Bra jak was born in Rijeka, Yugoslavia on June 19. 1957. He receved the B.Sc. and M.Sc. in computer science form Columbia University, 1981 and 1983 respetevely, where he worked on two parallel processing projects: NON-VOM and CHoPP. From 1984 he works at the Reactor Centre of "J. Stefan" Institute, Ljubljana. His work Includes Instalation of large programs on vector processor CSPI MAP6410, and developing software tools for vectorization of serial programs. His research interests are in the field of higly parallel multiprocessor systems. especialy synchronization software levels. protocols on /23/ H.T. Kung, TJie structure of Parallel Algorithms, Dept. of Comp. Sci,, Carnegie-MelIon U., 1979 /24/ Lee C. Y., Paul M. C., A Content Addressable Distributed Logic Memory with Applications to Information. Retrieval, Proc of IEEE, June 1964 /25/ Yau S.S., Fung H.S., Associative Processor Architecture A Survey, ACM Syrveys, 9/1977 /26/ Shaw D., NON-VON Supercomputer. Dept. of Comp. Sci., Columbia University 1983 /27/ Stolfo S., DADO AI machine. Dept. of Comp. Sci., Columbia University 1983 /28/ Fahlman S. The Hashnet Interconnection Structure, Dept. of Comp. Sci., Carnagie-Mellon U., 1979 /29/ Forgy C., Note on Production Systems and Illiac IV, Dept. of Comp. Sci., Carnagie-Mellon U., 198Ü ON CHOOSING A PLAN FOR THE EXECUTION OF DATA FLOW PROGRAM GRAPH Borut Robič, Jurij Šlic Jožef Stefan Institute. Ljubljana UDK: 681.519,7 ABSTRACT - In the paper we present a generalized analisys af static data Mow progran graphs. These graphs are allowed to have nodes that use more than one unit of time lor their execution. Such graphs are more realistic then graphs with nodes that execute in one unit of time. Ue restrict our consideration to graphs with Integer execution times of their nodes. In the paper we first briefly describe the data flow concept of computation. Next ue describe the basic data flow architecture and a common way of the execution of a graph on it. Ue show that this way of the execution has a drawback. In the next sections we introduce the notion of a static data flow prograa graph and describe the state of the execution of such graph. The state consists of a few time depending sets of nodes. Ue define a plan for the execution of a program graph which is the result of the analysis of the graph made before its execution. There are two special plans for the execution. Information, obtained by these two plans is used for defining the third special plan, which we call the heuristic plan for the graph execution. The execution of a graph according to this plan may minimize the number of processors needed, without lengthening the total execution time of the graph. Finally, we informally describe the algorithm for obtaining plans for the execution. 0 IZBIRANJU NACRTA ZA IZVRŠEVANJE PODATKOVNO PRETOKOVNIH GRAFOV - V delu je podana posplošena analiza statiCnih podatkovno pretokovnih grafov. Toöke taksnih programskih grafov se lahko izvrSujejo poljubno celo Število Časovnih enot. Uvodoma je opisan koncept podatkovno pretokovnega rafiunanja. Sledi opis znaöilne podatkovno pretokovne arhitekture ter enega izmed moünih izvrSevanj podatkovno pretokovnega grafa na njej. Prikazana je slabost taksnega nafiina izvrSevanJa. Po opisu statiänega programskega grafa sledijo definicije onoüic toäk, ki sestavljajo stanje izvrševanja grafa. Definiran Je naCrt IzvrSevanJa programskega grafa, ki Je rezultat njegove predhodne analize. V sploSne« obstaja vefi naCrtov za izvrševanje. IzvrStve, ki ustrezajo posaaezni« naCrton, se razlikujejo po uporabljenem Številu procesnih elementov in ne podaljšujejo minimalnega Casa, potrebnega za izvršitev programskega grafa, v kolikor Je na voljo dovolj procesnih elementov. Obstajata dva posebna naSrta za t.i. takojSnJe in leno izvrševanje, ki v spIoSnea ne ninimizirata Števila potrebnih procesnih elementov. Ker sisteaatiäno pregledovanje vseh možnih naCrtov vodi v koabinantorieno eksplozijo. Je v delu predlagan hevristiCni postopek za izbiro nafirta izvrSevanJa, ki teii k minimizaciji Števila procesnih elementov. 1. INTRODUCTION A data flow system comprises a user-oriented high-level l_anguage, a low-level base language, and a highly-parallel computer architecture. User programs are written in the highlevel language and , are translated into corresponding programs in the base language. A base language program is a graph composed of nodes interconnected via directed arcs. Each internal node is an operation and represents a separate processing elemet capable of accepting, processing and emitting value tokens travelling along the graph arcs. Each operation executes only when all tokens, carrying operands required by that operation have arrived. At that point the operands are consumed by the node and new tokens, carrying results, are placed on the output arcs CC0M82D. This fundamental principle permits the graph to be napped onto a computer architecture consisting of a very large number of independent processing elements and switches, able to connect any two processing elements, making a data path between them. Separate data paths can cross the switch simultaneously CKF6SSA]. For example see Fig.1. 2. SIHULATION OF DATA FLOU ARCHITECTURE In general not all operations ( nodes of a graph ) need to be assigned to processing elements at the same, moment since not all operations have available all input operands at that moment. To make the data flow concept possible even without a very large number of processing elements data flow computers are Fig.1: In the switch lattice the squares represent processing elements, circles represent switches, lines represent data paths. PROCESSrNG UNIT . PEB X MEMORY i i ! : PRIMARY i 1 i SECONDARY 1 -/ Fig.2: The model of data flow machine. usually based an a packet communication machine organization, consisting ol a circular instruction execution pipeline ol resources, The resources are memory, arbitration, processing and distribution unit. The «emory unit is divided into the primary and secondary part, the lormer beeing faster. The processing unit consists of a number of processing elements (Fig,2). Nodes, having none of their input operands arrived reside in the secondary memory. These are noncreated nodes. At the moment when the first input operand has arrived the node is created, i.e. moved to the primary memor, to wait for the other input operands. A created node becomes executable at the moment wher' the last input operand has arrived. Executable node is ready for the execution and may be transferred (fired) to the processing unit where a processing element Et Arts to execute it. It is the arbitration unit that decides which of the nodes are executable and which processing elements are to be allocated to. The place in the memory unit which was occupied by that node is now set free. While the node is beeing executed the distribution unit finds out where the nodes waiting for the result are. When the result is produced, the distribution unit send;, it to all nodes waiting for it, creating iome of them if neccessary. The node that has been executed is now deleted. Such execution may need more processing elements than there are in the processing unit. The problem where there are more executable nodes than processing elements must be solved during the execution of a graph. All these nodes are executed in several steps implying the lengthening the total minimum executiun time of a graph. Note that after each such step again the same problem may appear. An anaysis of the graph before its execution may prevent the problem discussed above. The basic observation is that in general not all executable nodes have to be fired immediately, since some of tfiem may wait a period of time in the memory without lengthening the total minimum execution time of a graph. Analysing the graph we obtain several plan'., for Its execution, each execution having its own characteristic. Information obtainded b> the plan is used by the architecture components during the actual exfaculion of a graph in deciding which executable nodes should be retained. The execution according to a properly chosen plan may result in minimization of some resources needed, such as the number of processing elements. We point out three special plans for the execution. Execution according to the first of them is essentially the immediate execution, described above. The execution according to the second plan is the opposite of the immediate execution, while the execution according to the third plan often uses minimum number of processing elements. Executing graphs according to this plan we may avoid the problemi, discussed above. 3, STATIC DATA FLOW PROGRAM GRAPH There are two ways of envisaging d data flow program: as a static or as a dynamic data flow program graph. We limit our discussion to static graphs. In short, static data flow program graphs are acyclic, while the dynamic are not. We define a static data flow program gi-aph 6 = ( V,A ), in further discussion program graph, to be a directed, acyclic, and simple (no multiple arcs ül the same direction between two nodes) graph. The set V of nodes is partitioned into three disjoint sets Vg ,Vi , Vp Ol starting, internal and final nodes, respectively. The starting nodes have no input archs while the final nodes have no output archs. Furthermore, there must always exist a path to any internal or final node Irom some starting node and, similarly, a path from any starting or internal node to soae final node. Starting nodes are used to carry the input values while the final nodes store the results. Internal nodes carry operations CRDfiS63. The time of the execution of a node n is t„, where t„ = 1 tor all starting and final nodes n. 11 a node n is beeing executed at the moment j we deline l', the plan Implyes a certain degree of control flou in data flow architecture and is realized by a time control vector associated to each node of a progran graph. The plan for the execution of a graph is de-terained by the rule which selects the sets Ej . There are two trivial plans for the ene-cution of a graph. These are a plan for inne-diate and a plan for lazy eKecution, The plan for immediate eKecution is determined by choosing Ej to consists of all those executable nodes at the moment J that could be fired even later. The plan for the lazy execution is determined by forcing Ej to be empty at all moments j. Consequently, the immediate execution fires the nodes as soon as possible while the lazy execution defers firing to the last possible moment. In general, none of these two executions minimizes the number of processing elements needed. The plan for the execution that uses minimum number of processing elements could be found by sistematic examxnatiun of all passible rules for the choosing tne sets E'. Since we want to avoid the coBt) 1 ridtori 3 ! explosion we try to find a heuristic rule such tiiat the execution according to the associated heuristic plan would use the number of processing elements as close as possible to the theoretical lower bound. For example, execution of the graph on Fig.3 according to the immediate p 1 an needs n+1 processing elements, since at the moment j = 1 the node 1 is fired simultaneously with the nodes n + i, 14iin. Similarly, the lazy plan implies the execution that involves n+1 processing elements, too. Namely, at the last step the node n is fired 'together with the nodes n + i, 1iiin. On the other hand, the heuristic plan offers an execution with only two processing elements for at each step only the pair of nodes k, and n+k are beeing executed . The plan for the heuristic execution will be discussed below. 6. THE TIME CONTROL VECTOR Every node n is associated with a time control vector T„ = ( Tc,„ , tE.„ , Tfn ). ^c^ t 'E.n V.n ^fe the moments when the node n becomes created, executable and fired. Tiae control vectors are computed for each node while the plan for the execution is beeing constructed. Since all the sets described above are affected by the rule for choosing the set Ej , the time control veotoi's depend on a plan constructed. Every plan for the execution has its own set of time control vectors. To point out that the time control vector of a node n is computed according to the plan for immediate or lazy execution we write TS™"or respectively. 7. THE PLAN FOR HEURISTIC EXECUTION 7.1. CRITICAL NODES and tI"» = < , 11«» ) time control vec- tors of a node n accordino to lazy execution. Then ue say that an internal node n is critical if 4';;'" 'F.n THEOREH 1. Timm ' vectors of "à nod'e n according to be time control inimed iate Every critical node n is fired at the noaent , regardless of the plan of the execution. PROOF; t'^^J" is the first possible moment when the node n can be tired, regardless of the plan of the execution of a program graph. On the other hand, is the last moment when the node can be fired without lengthening the total execution time, taken over all possible plane of the execution. Consequently, if n is a critical node, then tji^^"' = il?^» = r^i, which means, that the moment is the only moment when the node n can be fired in all possible plans of the executions. Q.E.O. LEMMA 1. There is at least one critical node in the program graph. PROOF; Let be p the longest path from the set of starting nodes to the set of final nodes. Then, in any plan of the execution the son of starting node on the path p must be fired at the moment j=I so as not to lengthen the total execution time. Consequently, the son of the starting node is critical. Q.E.D. THEOREM 2. A node is critical if and only if it is on a longest path from the set of starting nodes to the set of final nodes. PROOF; Let p be some longest path from the set Vg to the set Vp . By Lemma 1 the son of the starting node on the path p is critical. Now suppose that all first k > D internal nodes n, , n2 i. .., n^ on the path p are critical. Consequently, the first moment at which the node n^», can be fired is the moment l + E-L, tn,. Since the node n^^., is on the longest path' from the set V^ to the set Vp this is also the last moment, when it can be fired, so as not to lengthen the total execution time of the graph implying that the node n,,^, is critical. Conversely, suppose a node n Is.critical. Consider the longest path p of the all paths from Vj to Vp , passing the node n. Ue define the subpath p' of the path p to be the path consisting of all the nodes from Vg to the father of the node n. Similarly, the subpath p" of the path p consists of all the nodes from the son of the node n to the set Vp . Ue define l(p') and Up") to be the lengths of the paths p' and p", respectively. Note, that since p is the longest path from Vg to Vp through the node n, the path p' must b« the longest of the paths from V^ to the set of fathers of n. Similarly, the path p" oust be the longest path from the set of sons of the node n to the Vp . Suppose the relation Hp')+tn+l»la2, > the number of proces-in the immediate ana rogram graph, respec-average parallelism of be n = tseq /t*, where maximal parallelism define a = max,- Then the following the upper and lower c I = IE* - Vp I + IF?'" I j if. o - a then E- : = 0 else begin 11 lEj- Ef I < m then Ej != E, -E| else Choose m nodes n from Ej - E* having the longest values Hn,VF) and put them into the set E' ; find? THEOREM 3. Minimal number of processing elements needed is bounded by a i - ßv Fig.^!- Heuristic choosing the sets Ej . PROOF; In case of ^àFitl the proof is evident since there exists a moment j when at least 5 critical nodes must be fired. Suppose now that ^ U (E, n Vp ) ; (15) Choose a subset E' of the set Ej - E| j (16) pnew ■ = E* U E' i (17) Fi ! = U clew (18) 0, ; = D|., U Fi* i (19) Ni • = V - ( C| U Fi U D, ) i (20) Adjust m C. the components of time control vectors for the nodes , E«" and FP'" i end J Fig.5: Algorithm for obtaining execution plans of a program graph. 9. CONCLUSION What is the time coalexity of the algorithm on Fig.5? The time conplexity of the step (1) is O(IVl^), since this is the time complexity of the computing the longest paths between all nodes in a graph CLaw763. The time complexity of the steps (2) to <20) is OCIVI^), since the loop (3) is entered O(IVI) times, each of the steps (A) to (20) having time complexity O(IVI). Consequently, the overall tine complexity of the algorithm on Fig.5 is IS 0( I Vt^ ) . The algorithm was tested on iiOO randomly generated program gi-aphs with at most b't nodes. In only 0.57. of analysed graphs >j(,ou >ß was Dbtained. In all other cases was less than or enual to p. Heuristic plan improved both immediate and lazy execution in SO.257. of cases. Furthermore, many (55.757.) of heuristic executions were also proved to be optimal, since the associated numbers of the processing elements needed equaled the values o, as was the case on the Fig.7. Note, that this number is pesimistic since there uere very probably graphs that could not be executed using only a processing elements. The results are depicted on Fig,6. It is to point out that the algorithm on Fig.5 can be used for minimiiation of some other resources such as the number of primary memory locations needed . Mheu > P (O.SOX) Mheu < ß (50.25X) Mheu « « (55.751) Flg.òi The behavior of the heuristic plan. +---+----------+----------+----------+ 1 v I tf^' I t'I^» i t^«" i 1 a K O, O, on ( O, Q, 0) I ( O, 0. 0) I I b I ( O, O, on ( o, D, 0) I ( o, o, on I C k o, o, 0) I ( o, o, on ( o, o, 0> I +---+----------1--------------------+ I d I C 1, 1, 1)I( 1, 1, 6)I( 1 , 1 , 1)1 ♦---+----------+----------♦----------+ I e 1( 1, 1, 1n( 1, 1, 1)I( 1, 1, 1)1 ♦---+----------+--------------------+ I I K 1 , 1, 1 ) 1 ( 1, 1 ,10) 1 ( -1, 1 , <|) 1 +---+----------+-----------+----------♦ I g I ( 1, 1 , 1)I( 1, 1 , 9)I( 1, 1, 1)1 +---+----------+----------+-----------♦ I h K 2, 7, 7)I( 7, 7, 7)I( 2, 7, 7)1 +---+----------+----------+-----------» I i K 1 , 1 , 1 )I C 1, 1,19) 1( 1 , 1 , 9)1 +---+----------4------------+----------4 I j K 1 , 1, 1)I( 1, 1 ,10) I ( 1, 1, 2)I +---+----------+----------+----------+ 1 k K 1, 1, 1)I( 1, 1 ,18) 1 ( 1 , 1 , 6) I +---+----------+----------«----------+ I 1 K 1 , 1 , 1 ) I ( 1 , 1 .U) I ( 1 , 1 , 4) I +---+----------+----------+----------1 1 a 11 3,12,12)1(12,12,12)1 C A,12,12)1 ♦---+----------+-----------1----------+ 1 n K 1, 1, 1)I< 1, 1 ,15) I ( 1 ; 1 , 6) I ♦ —.-+----------+----------+----------1 I o M 3,1A,1'i) I (1)l( 1,H,U)I ♦-----------+----------+----------* I 4 I (16,16,It)I(16,16,16)1(16,16,16)I I r K 5,19,19)1(19,19,19)1(10,19,19)1 I s K 3,21,21)I(19,21,21)1( 9,21,21)1 +---+----------+----------+ ----------+ I t 1(22,22,22)1(22,22,22)1(22,22,22)1 Mimm = ' (»lajy = ^ Mheu = 3 mi = 3 ? = 1 o = 3 In this case the heuristic plan is also optiaal! Fig.7: Plans (or immediate, lazy and heuristic execution of a given program graph. 10. LITERATURE CC0MB2: COMPUTER, Soecial Issue On Dataflow Systems, Vol.15, No.2, Feb.1982 CKFSSa^D Kapauan A., J,T.Field, D.B.Gannon", L.Snyder: 'The Pringle Parallel Computer', Proc. 11th Inf 1 Symp. Comp. Arch., IEEE Press, New York, 198',, pp.12-20 CLaw763 Lauler E.: Combinatorial Optimization! Networks and Matroids, Holt, RinehartiWinston, New York, 1976 CRaSfi6] Robie B., J.Silc ! 'Analysis of Static Data Flow Program Graphs' , to be published in Elektrotehniški vestnik, (in Slovene) CTJS83] Tokoro M., J .R.Jagannathan, H.Suna-hara: 'On the Working Set Concept for Data-flow Machines', Proc. 10th Int'l Symp. Computer Architecture, IEEE Press, New York, 1983, pp.9097 C8ÌR85] fiilc J., B.Robie : 'Basic .Principles of Data Flow Systems' , Informatica 2/85, pp.10-15 (in Slovene) PARALELNO PROCESIRANJE SLIK INFORMATICA 3/86 Saša Prešeren, Rudolf Murn, Dušan Peček Institut Jožef Stefan Ljubljana, Jugoslavija UDK: 681.3:514.1 Proo«sir. Zato zahteva procesiranje slik hitre matematične procesorje in veliko pomnilnika. Pri problemih procesiranja slik v realnem Času se poslutujemo prijemov paralelnega procesiranja, kjer oentralno procesno enoto razbremenimo «tevlnlh iterativnih obdelav, ki so povezane s procesiranjem slik. V ta namen v zadnjem Času uporabljajo paralelne arhitekture računalnikov in sioer artitaktura, kjer anemu ukazu ustreza vetikratni podatek (SIHD - singla Instruction multiple data) ter arhitekture, kjer večkratnim ukazom ustreza večkratni podatek (HIMO - multiple Instruction multiple data) (STOaO), R0'8t, Opatija 1986. VIDEOTERMINAL PMT-100 INFORMATICA 3/86 Igor Ozimek, Viktor Avbelj Institut Jožef Stefan, Ljubljana UDK: 681.3.06 Članek govori o video terminalu PMT-100. Poudarek je na nekaterih bistvenih izvirnih elementih organizacije logike in programske opreme. Nekaj besed je posvečenih tudi opisu razvojnega dela in njegovi organizaciji ter učinkovitosti, kar v razmerah nizke produktivnosti v naèem okolju zasluži posebno pozornost. The article is about a VTIOO compatible video terminal PMT-100. Some interesting hardware and so-ftware solutions are described, which enables the complete logic circuitry and power supply of the terminal to be housed in the keyboard housing. UVOD PMT-100 je terminal, t-.i je funkcionalno enakovreden terminalu VTIOO (DIGITAL). Ob obstoječih tovrstnih terminalih na naSem tržišču (PAKA 1000, PAKA 3000) je seveda opravičljivo začudenje, čemu razvijati še enega. ftazlog je preprost: Obstoječi^terminali so sorazmerno dragi. Visoka cena terminala postane problem pri trženju cenenih mikroračunalnikov. Lahko se zgodi da je terminal celo dražji od računalnika. (V našem primeru je élo za mikroračunalnik PMP-ll, raz/it na IJS. To je računalnik, programsko skladen s sistemi PDP-11 m LSI-11 oziroma ustreznimi sistemi DELTA ali ENERGOINVEST). Cilj razvoja je bil torej terminal, ki bi imel funkcionalnost terminala VTIOO, vendar bi bil bistveno cenejši od obstoječih tovrstnih terminalov na našem tržišču. Ideja, ki je bistveno poenostavila (torej: pocenila) PMT-100, je za terminale razreda VTIOO neobičajna, ob misli r.a obstoječe hiSne računalnike pa niti ne preveč originalna: vsa logika terminala skupaj s pripadajočim napajalnikom, transformatorjem in tipkami je narejena na eni sami tiskanini, ki je vgrajena (seveda) v ohišje tipkovnice. Uporabljene so domače tipke proizvodnje lEVT. Napajalnik je preklopnega tipa in priključna moč je manjša od 0 (osem) M. Celotna zadeva je enako velika kot so običajne tipkovnice - uporabljen je isti tip ohišja, v kakršnega je vgrajena tipkovnica terminala PAKA 1000 ali PAKA 3000. Na to "tipkovnico" (to je pravzaprav terminal) priključimo običajen (ceneni računalniški monitor. MATERIJALNA OPREMA (HARDWARE) Uporabljena so tri standardna integrirana vezja iz družine 2ó7j; (Signetics): - 2ó74 - CRT kr.TiilniI (z video RAM pomnilnikom je zvezan v načinu "Independent Mode" - 2675 - krmilnik atributov (podčrtavanje, mežikanje, ...) - 2671 - krmilnik tipkovnice, ki je hkrati tudi serijski asinhroni komunikacijski vmesnik s programskim generatorjem takta, generator zvočnih signalov in prekinitveni krmilnik v načinu za intelBOeO. Kot znakovni generator je uporabljeno EPROM vezje 2764, ki omogoča definicijo 512 različnih znakov. Izbrano število točk prikazovanih znakovnih celic je 10 x 12, Znakovne celice so definirane z matriko dimezije 8 x 12. Prirojena lastnost CRT krmilnika omogoča, da se vsebina S. kolone v opisu celice uporabi tudi za 9. in 10. kolono (npr.j velika črka A ima v tem opisu dimenzijo 7x7). Sorazmerno visoka matrika znakov (12 vrstic v primerjavi z 10 vrsticami pri VTIOO) omogoča lep zapis jugoslovanskih znakov, onemogoča pa delovanje terminala po ameriškem video standardu (60 Hz), čemur smo se že vnaprej brez škode odrekli. Na plošči je še video RAM pomnilnik zmogljivosti Bk znakov in atributov (dve integrirani vezji 6264), potrebna "lepilna" logika v tehniki 74LS in mikroračunalnik v naslednji konfiguraciji: - procesor ZBOB. B izvedba procesorja je potrebna zaradi potrebe po izredno hitri obdelavi prekini-tvenih zahtev. Glavni vzrok za to je sorazmerno skromna (cena!) materijalna oprema terminala - za mehak pomik (soft scroll) je edina materijalna podpora tista, ki je že vgrajena v CRT krmilniku, ki pa je (kot bomo še omenili), zelo nepopolna. Procesor deluje v prekinitvenem načinu mode 1 (vstopna točka obdelave vseh prekinitev je skupna), kar se je v tem primeru pokazalo kot najboljše. EPROM pomnilnik zmogljivosti vezji 27128). 32k zlogov (dve delovni RAM pomnilnik zmogljivosti Bk (6264) zlogov v CMOS tehniki in zaščiten pred izpadom napajanja (alkalne, litijeve ali NiCd baterije na tiskanini). Zaščita omogoča uporabo tega pomnilnika za "SETUP" nastavitve, s čimer se izognemo zapletom pri uporabi EEPROM (electrically ereasa-ble PROM) vezij, malce pa si tudi olajšamo pisanje programske opreme v visokem programskem jeziku. BATERIJSKA ZAŠČITA CPU zaoB DELOVNI POMNILNIK Bk RAM 1 X 66264 TIPKOVNICA ZVOČNI SIG^4AL SERIJSKA LINIJA PREKINITVENI KRMILNIK 2671 PROGRAMSKI POMNILNIK 32k EPROM 2 X 27128 CRT 2674 ZNAK. GEN. EPROM 2764 ATRIBUTI 2675 VIDEO MONITOR VIDEO POMNILNIK 8k x 16 RAM 2 X 6264 Blačna shema PMT-100 Logični načrt terminala ni priložen, ker (razen pravkar opisanih stvari) ne prinaša ničesar novega. NEKAJ PRIPOMB O CRT VEZJU 2674 OD prvem pogledu v priročnik daje to vezje zelo dober vtis, saj podpira mehak pomik in znake dvojne v'i^ine/éirine, kar je potrebno za emulacijo VTIOO in česar CRT krinilniki običajno nimajo vgrajenega. (V povezavi s krmilnikom atributov podpira tudi vse VTlOO 2n»l-.ovn€ atriDute - podčrtovanje, mežikanje, intenzivnost, ozadjeJ. Kmalu nato pa sledi kruta stvarnost: uporaba pomika (scroll) in znakov dvojne vi«iine/^irine zahteva nenavadno močno dinamično programske podporo na osnovi prekini tveni h zahtev. V skrajnem rim&r-_; imamo pri uporabi mehkega pomika iSQit serali) samo 64 mikrosekund časa za obdelavo prešlim tvene zahteve, kar predstavlja za procesor ZSO (m njegovega programerja) zelo težko nalogo. (Vpražanje časa je, kdaj se bo- na tržišču pojavil Kak "inteligentnejši" CRT krmilnik, ki bo samostojno rsSeval opisane probleme pa morda še problem mapira-nja vrstic zaslona, ki je opisan spodaj.) PROGRAMSKA OPREMA Programska oprema je pretežno pisana v jeziku C, kar se je pokazalo kot zelo dobra odločitev. Visok programski jezik omogoča mnogo večjo učinkovitost pri programiranju (manj napak), lažje vzdrževanje (poprav 1janje, dopainjevanje), razpoloŽlji vost i n enostavnost uporabe ar i trnetičnin operacij pa tudi večjo moinost "off-line" razvojs. in testiranja delov programa na poljubnem (velikem) računalniku z ustreznim prevajalnikom. Uporaba visokega programskega jezika pomeni dve potencijalni nevarnosti : i. povečanje obsega prevedenega programa. V našem primeru saseda program 24k, kar je kar 3-krat več, kot v nekaterih starejših enakovrednih .tef— minalih. To zelo veliko razliko lahko pripišemo predvsem avema vzrokoma.: - strojna koda procesorja Z80 je precej neprimerna 2a prevode iz višjih programskih jezikov; dovolj je omeniti nezmožnost naslavljanja sklada relativno glede na kazalec sklada. Zaradi tega so prevodi velikokrat precej "okoli ovinka", • ' - obstoj "lepih" podatkovnih struktur (record v PASCALU, struct v C) kaj hitra "zapelje" programerja k njihovi uporabi, pri čemer hitro •pozabi, kako naporna postane potem takšna stvar za procesor, kot je Z80 (zopet zairadi neobstoja primernih strojnih instrukcij in naslovnih načinov). Vendar so danes EPROM vezja dovolj poceni, da opisana težava pravzaprav ni težava,* vse dokler nam ne zmanjka spominskega prostora; 2. Druga nevarnost je podaljšanje časa izvajanja (ki je seveda povezano z večjo dolžino prevedenega programa). Ta težava je kritična samo na določenih posebej obremenjenih delih programa, ki se jih da običajna napovedati (v primeru PMT-100 je to pot od sprejema izpisljivega znaka po serijski liniji do njegovega izpisa nà zaslon). Tej težavi se da izogniti z več ukrepi, ki imajo skupno ime "grdo programiranje". V kritičnem delu se je potrebno izogibati zapletenim podatkovnim strukturam (bolje več enostavnih spremenljivk kot niz), preveč modularnemu programiranju (bolje ena dolga procedura kot - več kratkih), pametno izbrati deklaracijo spremenljivk (v jeziku G npr.: register bolje kot auto, static bolje kot auto), zadnja rešitev pa je programiranje kritičnih delov v zbirnem jeziku. Nekateri visoki jeziki omogočajo vstavljanje zbirnih ali strojnih instrukcij neposredno v višjem jeziku, malce nerodnejša varijanta pa je pisanje ločenih zbirnih procedur, ki jih lahko potem kličemo iz • visokega jezika. ORGANIZACIJA PROGRAMSKE OPREME - NIVOJI Programsko opremo PMT-100 lahko razdelimo na dva nivoja. Zgornji nivo (to je nivo, kjer se med drugim dogaja razpoznavanje krmilnih zaporedij), je pisan tako, da je neodvisen, od materijalne opreme. Vse osnovne operacije materijalne opreme (recimo: postavitev kazalca (cursor), vpis znaka na zaslon. pomik vrstic (scroll!, zvocni signal, prižiganje lučt ) ;:ahteva s HicetTi ustreznih procedur.. Seveda je treoa p-ri^nati, da način uporabe teh procedur do neke mere vendarle odseva strukturo materijalne opreme in organizacije spodnjega nivoja programske opreme, kar je nujen (ininimalen) kompromis za doseganje cimvecje hitrosti obdelave- Spodnji nivo programske opreme sestavljajo procedure, ki neposredno krmilijo periferijo. Ta delitev programske opreme na nivoje je hkrati naravna delitev dela pri programiranju. ZGORNJI NIVO neodvisno od materijalne opreme SPODNJI. NIVO poganjalniki materijalne opreme ORGANIZACIJA PROGRAMSKE OPREME - PROCESI V videoterfliinalu tece hrati več opravil. Medtem ko uporabnik pritisne tipko (terminal jo ne sme spregledati), prileti po serijski liniji znak (terminal ga ne sme spregledati), medtem je potrebna programska podpora osveževanja zaslona, itd. V naSem prioieru imamo procese (opravila), ki so našteti spodaj. Vsi razen glavnega procesa imajo svoj izvor v prekinit/enih zahtevah. Glavni proces je proces najnižje prioritete, ki časovno ni kritičen. Nad njiffl so nanizani prel.initveni procesi, ki imajo različne prioritete glede na nujnost akcije, ki jo opravljajo. Frioriteta posameznega procesa je fiksna. Proces z višjo prioriteto lahko (mora) prekine proces z niijo prioriteto. Seznam procesov ipo rastoci prioriteti). Glavni proces - nivo O Tu je vključena procedura za nastavitev terminala ("SETUF";, procedure za razpoznavanje VTb2 in VTIOO krmilnih zaporedij, ter procedure" za komunikacijo med prekinitvenimi procesi. Ta komunikacija poteka preko pooatkovnif' vrst. ki so prirejene večini prekinitvenih procesov (razen CRT procesu). Primer: - tipl-ovni proces sprejme tipko in jo postavi v svojo oddajno vrsto - glavni proces to ugotovi in pod določenim pogoji (recimo: če terminal ni v lokalnem načinu) vzame znak IZ oddajne vrste, ga postavi v sprejemna vrsto oddajnega procesa in oživi oddajni proces (dovoli prekinitve oddajnika) . - oddajni proces odda znak po serijski Uniji. Ce ni več znaka, se izključi. (Manipulacija podatkovnih vrst poteka s pomočjo ustreznih procedur spodnjega nivoja programske opreme. Te procedure morajo biti v kritičnem delu zaščitene pred prekinitvijo. Prekinitev jemanja iz vrste in hkratno postavljanje v isto vrsto bi povzročilo zmedo.) TX (odda ini) proces - nivo 1 Ta proces skrbi za oddajanje znakov iz sprejemne vrste TX procesa po liniji ftS232. Poleg tega skrbi za oddajo XQN/XOFF, če ju najde v posebenem visoko-prioritetnem vmesniku. KEY (tipkovnil proces - nivo 2 Ta proces sprejema tipke s tipkovnice in jih postavlja v oddajno vrsto tipkovnega procesa. Posebej procesira nekatere tipke (npr. SETUP, SCR) in postavlja ustrezne zastavice za glavni proces. Proces CRT vertikalnih prekinitev - nivo 3 Precej obsežno procesiranje med vračanjem žarka v zgornjo levo točko. Tu se dogaja urejanje tabel kazalcev vrstic na zaslonu v zvezi s pomikanjem vrstic na zaslonu - glej spodaj. RX (sprejemni) praces - nivo 4 Proces sprejema znake z linije RS232 in jih postavlja v oddajno vrsto sprejemnega procesa. Nekatere znake posebej prepoznava in obdeluje (NULL, DEL, (NO)SCR). Proces je kritičen in ne sme zamuditi znaka tudi pri hitrosti komunikacije 19200 (cca 0.5 msec na znak). Zato ga CRT vertikalni proces ne sme (in tudi ne more) prekiniti. Proces CRT horizontalnih prekinitev - nivo 5 To je najvišji nivo. Ta proces skrbi za dinamično postavljanje registrov CRT krmilnika. Dovoljen čas za obdelavo je izredno kratek, največ 120 mikrosek., zato ima ta proces najvišjo prioriteto in ga ni moč prekiniti. ppgSLSM .gRSBlTVS SI.ÌK6 V VIPEO PWtWNtKg Poseben problem predstavlja ureditev slike v video pomnilniku v zvezi z delnim pomikanjem (scroll) zaslona. Delno pomikanje namreč podre enostavno razmerje med spominom in zaslonom, kar vidimo na spodnjem primeru pomikanja vrstic 1 do 3 navzdol (vrstica 3 zgine z zaslona in jo moramo pobrisati, nakar jo lahko uporabimo kot 1. vrstico nove slike na zaslonu). RAM zaslon pred skrolanjem ! po skrolanju (pobri sana) Obstajata dve rešitvi tega problema: 1. Ohranja se stalno razmerje med video pomnilnikom in zaslonom. Vsebina video pomnilnika neposredna ustreza prikazu na zaslonu. To pomeni, da se pomikanje izvaja v video pomnilniku, kar zahteva intenzivno prepisovanje in porabi veliko časa ter bistveno upočasni delovanje. 2. Vsebina video pomnilnika se ne preureja, pač pa se preureja posebna tabela kazalcev, ki kažejo na mesta v video pomnilniku, kjer so zapisane posamezne vrstice zaslona. V zvezi s tem je potrebno tudi dodatno procesiranje pri osveževanju zaslona, vendar se izognemo zamudnemu prepisovanju video pomnilnika. Seveda mora uporabljeni CRT krmilnik omogočati tak način dela. Ta način je uporabljen tudi pri PMT-100. Procesiranje pomika (scroll) opravlja proces CRT vertikalnih prekinitev. Glavni proces zahteva to s pomočjo procedure, ki postavi ustrezno zastavo (DOL / - / GOR) kot zahtevo zgoraj omenjenemu procesu. Območje pomika postavlja glavni proces s pomočjo druge procedure. PREKINITVENA STRUKTURA Zaradi neobstoja prioretizirane materijalne prekini- tvene cpre;ne Is stališča materijalne opreme (hardware) imajG vse prekinitve isti nivo) je stvar reéena na ni/ojL. proGramst e opreme, kar seveda zahteva nekaj vec oDdelave. Zadeva je resena na ta način, da vsak od procesov nastavlja prekinitveno masko tako, da onemogoči tiste prekinitve, ki imajo po de-finiciji nitjo prioriteto od njega, po zaključku pa restavrira stara prekinitveno iriasko. Zadeva se seveda ie malo :aplete, ker sta v našem primeru dve prekinitveni T.aski , od katerih .ie ena naslovljiva samo po posameznih bitih, pcleg tega pa je treba voditi ie evidenco o iivljenju oddajnega procesa (ki se-eda ni /edno ;iv). F:i2vQjr.G deio na Pr^T-IOO je dalo Videoterminal, ki je glede na zasnovo, majhne Število integriranih vezij ir. jpcradljene domače tipke cenejži od običajnih VTlOO-sklidnih terminalov. Pri tem ima standai— dno vgrajene spsosobnosti kot VTIOO i flVO opcijo (132 X 30 makov, vsi snako/ni atributi), jugoslovanski nabor znakov, mehak pomik (soH scroll ) in celostranski pregleden "setup". Vgrajeno ima možnost izpisovanja krmilnih znakov in zaporedij brez njihove interpretacije. Vgrajena je semigra-tika 160 K 96 (264 ■.■.961. k/aliteta emulacije ('.'T52 m VTIOO) je bila presku-žena na vrsti igric (ii so najboljši test za take stvari!. Pri tem je bila pokarana popolna skladnost : VTiOO, kar nikakor ne fci mogli trditi" ra nekatere druge tovrstne terminale na našem tržišču. Ce odštejemo net-aj začetnih tavanj in standardne usluge (izaela.a tislanine), sta na projektu terminal a delala dva človeka. Efektiven čas na projektu: - razvoj materi jalne opreme in spodnjega nivoja programske opreme: 1 človek, 4 meseci - razvoj zgornjega nivoja programske opreme (emulaci ja, setup, ...): 1 človek, 2 meseca Tako Kratek cas je bi i inojoč iz naslednjih razlogov! - enostavna realizacija '.r.ateri jalne opreme, praktične ni (nehanskih montažnih problemov. - uporaDa visokega programskega jezika (C) pri programiranju z izjemo časovno kritičnih delov. Pri tem velja omeniti, da ni bilo na voljo skoraj nikakršne razvojne opreme (nobenega in-circuit emu-latorja). Uporabljeni C prevajalnik je izdelek firme Whitesmith in teče na računalniku LSI-11 pod RT-11 ali SHORE. DODftTEK; ZflKflJ JEZIK C Jezik C se vse bolj uveljavlja, vendar še ni povsem udomačen in nekaj besed o njem ne bo škodovalo. Nepoučenemu pusti pogled na program v C vtis zmede, ki je kaj malo podobna recimo Pascalu. Vendar je ta razlika samo navidezna in izvira iz neobičajnih označb za operatorje in nekatere simbole. Vlogo pascalskih begin/end besed imajo tukaj recimo zaviti oklepaji. Ko odmislimo te razlike, sodi C v isto skupino kot PASCAL. V čem je torej razlika in zakaj -je C primeren za pisanje sistemske programske opreme (recimo operacijskega sistema UNIX). Predvsem: C nima nikakršnih konstruktov za programiranje paralelnih procesov (recimo obdelava preki-nitvnih zahtev) in je v tem enakovreden PASCALU. Pač pa ima C vgrajen nabor operatorjev za boolove operacije in pomikanje (shift), kar je nujno potrebno za sistemsko programiranje. - V PASCALU je to izvdeljivo s klicanjem ustreznih procedur, kar pa je nujno neučinkovito. Marsikdaj je koristno tudi dejstvo, da obvlada celoštevilčno računanje na 32 bitov. Kontrole nad tipi spremenljivk, številom in tipom argumentov v procedurah, velikostjo nizov ipd. sploh ni. Zaradi te kontrole v PASCALU ni moč definirati ekvivalenta PASCAL-skega stavka WRITE. V C-ju je to možno, zato tak stavek v standardni jezik C sploh ni vgrajen. Ta odsotnost kontrole omogoča storiti marsikaj neprecenljivo koristnega, neizkušenemu programerju pa še več usodno in skrivnostno napačnega. Lahko bi nadaljevali, vendar strnimo na kratko. Jezik C omogoča vrsto stvari (pravzaprav malenkosti), ki so koristne ali nujne za sistemsko programiranje in ki jih PASCAL in podobni jeziki običajno ne omogočajo, vsaj ne na učinkovit ali standarden način. Vendar pa je s svojo pomankljivo notranjo kontrolo lahko tudi nevarna past za neizkušene programerje. Za programiranje jedra operacijskega sistema ali vhodno izhodnih procedur pa se je v splošnem še vedno treba v večji ali manjši meri zateči k zbirniku. TRINIVOJSKA ARHITEKTURA INFORMACIJSKIH SISTEMOV PO MODELU ISO TC97/DP 9007 B. Jerman-Blažič, I. Fabič Institut Jožef Stefan, Ljubljana UDK: 681.3^(497.1) Abstract Three level architecture of IS0/TC97/DP 90Q7 an information system according to the model of The paper deals with the three level architecture of an information system designed according to the model defined in 180/TC97/OP 9007. Previously this model was known under the name ANSI/X3/SPARC DBMS Framework.The model was widely accepted in the fields of data base design and systems analysis. The model is set -'up on three level architecture, i.e three schema framework. The conceptual schema comprises a unique central description of the various information contents that may be in a data base of an information system. This Includes the description of what actions, such as changes and retrievals are permissible on the information content. The data base itself nay be implemented in any one at a number of possible way. Users and application programs may be view the data in a variety of ways, each described by an external schema. Each external schema is therefore derived from the common conceptual schema. The physical storage structure that may be in use at any given time is described by an internal schema that is also derived from the conceptual schema. I Povzetek V prispevku Je podana trinivojska arhitektura informacijskega sistema, zgrajena po mcdelu IS0/TC97/DP 9007. Modal je nastal v okviru ANSlJa in zato je znan tudi pod imenom ANSI/X3/SPARC koncept podatkovne baze. Model se je uveljavil zlasti na podroCju na&rtovanja podatkovnih baz in sistemske analize. Model je zasnovan na konceptu treh nivojev ali treh shem. Konceptualna shema je enotni, centralizirani zapis vseh informacij, ki nastopajo v podatkovni bazi sistema. Poleg zapisa informacij v konceptualni shemi so zapisane vse dovoljene in nedovoljene akcije nad podatki. Implementacijo podatkovne baze lahko izvedemo na veö naöinov. Kako uporabniki vidijo podatkovno bazo od zunaj, zapiSemo v zunanji shemi. FiziSen zapis podatkov na hranilnih medijih je opisan v notranji shemi. Skupen pregled nad vsebina zunanje in notranje sheme se hrani v konceptualni shemi. l.Uvod Trendi v razvoju informacijske tehnologije in sistemov, za obdelavo podatkov katejo na uvajanje različnih priponofikov, ki imajo za namen poenostaviti delo uporabnikov, oziroma oblikovati delo z računalnikom na najbolj human naćin. Za te pripomoCke je znafiilno, da 50 načrtovani z najvišjo stopnjo abstrakcije, ki omogofia posplcSitev procesa izdelave programske opreme. Visoka stopnja abstrakcije omogoča z druge strani tudi standardizacijo programske opreme, kar samo po sebi prinata ekonomičnost v procesu proizvodnje, poenotenost izdelkov, njihovo laljo distribucijo ter lai je vzdrlevanje. Standardizacija izdelave programske opreme dovoljuje tudi enostavno prilagajanje izdelkov glede na potrebe različnih naročnikov. Med temi prizadevanji za standardizacijo izdelave programske opreme zavzema poleg fe znanih in uveljavljenih metod pomembna mesto metoda za izdelavo standardnih podatkovnih modelov in podatkovnih slovarjev v informacijskih sistemih, znana pod imenom KONCEPTUALNA SHEMA in MODEL TRINI-VQJSKE ARHITEKTURE (Conceptual schema and three level architecture ali skrajiano CS and TLA). Metodo so razvili najprej- v okviru ANSIa, zatem je bila sprejeta s strani ISOa TC97/SC21 1.1985. Naloga, ki je bila zastavljena v okviru odbora za plan ANSI, komite X3, je zajemala naslednje tofikei 1.Definirati koncepte CSL (Conceptual Schema Language), kot orodje, ki avtomatično opite miselni model in poenostavi testiranje pri razvoju in uporabi informacijskih sistemov) 2.Opredeliti definicije v konceptih za CSLi 3.Razviti metodologija za oceno predlogov za jezik CB, ki naj omogoSa formalen opis informacijskih zahtev uporabnikov) 4.Oceniti prispele predloge za jezik CS| 5.Definirati koncepte razliCnih stopenj abstrakcije CS) 6.Opredeliti možnosti uporabnikov pri CSf ?.Rdiviti koncepte in terminologijo za upora-Lo CS in njeno vkljućitev v reierenönl nadel OSI (Open System Interconnection) v sodelovanju I IS0/TC97/SC21. 2.0anovnl principi CB In InforaaoiJcka baz« V te« poglavju borna predstavili prablsnatlko CS li) TLA in podali osnovne informacije o uporabljeni terminologiji in konceptih informacijskega modela. 2.1 InforBšolJskl flitaal Osnovna lahteva vs informiranje ali pos temeljna zahteva vs ob uporabi dolofieneg je to znanje razpolo nja znanja ne poteka se pa poskusih inn mo, ampak z inforair uäi »o le, će od n informacijo. V te« k cija "znanje" o n« Konceptih, metodah i njujemo. Proces i dobni drufbi poteka okolju. ake ölovetke družbe je redovanje informacij. Ta ake sodobne druZbe poteka a znanja pod pogojem, da fljivo. Proces prldoblva-individualno, ne uClmo a napakah, ki Jih naredl-anjea. To pomeni, da se «kod ali od nekoga dobimo ontekstu pomeni Informa-«em, o stvareh, dejstvih, pd. To znanje lahko Izme-zmenjave Informacij v sa-najpogosteje v tehnlfinem Vsak proces izmenjave informacij je zasnovan na sledefiih dejstvihi -dobavitelj informacije (poCl1 jate 1 j) In uporabnik (prejemniki nista nikoli na isti lokaciji, torc_! vsaka komunikacija turi'' Opis in zapis vseh razvrstitev, abstrakcij, posploSitev in vzpostavitev pravil o svetu 15. To je mentalni proces, ki poteka v glavah razvijalcev; 2)Zapis dejstev in dogodkov iz sveta potrebnih nosilcev na formalen na&in. 15 in CS vsebuje sploftna pravila, ki opredeljujejo obnaSanje sveta IS. Ta pravila doloCajo, kaj se lahko in kaj se ne sne zgoditi v informacijski bazi. InforMoiJaki prooaaor vsebuje kaocfptiMiM tbtm «ferfflacijtka bata Slika 2. Prooes opisovanja IS I (porotito J»-- {|ioffl*a (poroiilat- lailCEPTUALli H IVO iatormscijtki prstKor j ^konceptualna ^^^^^ / I ktnccptuolna I V'podthetng' \ \ infortnacijiko baza V \ zunanji procttor I fonmit I JL zunanja V podatkovno baza ZUXAMJI «IVO notranji procesor (lizifna 7 podatkovna baza I NOTRjNJI DIVO Slika 3. Trinivojska arhitektura •vat IS 2birka objektov (nosilcev), ki so, ali ki so kadarkoli bili, oziroma bodo sestavni del izbranega dela realnega sveta, ki bo Obravnavan v IS; konoaptualn« ahasa ■ Opis motnih stanj sveta IS, ki vkljuäuje tudi razvrstitve, pravila, omejitve ipd. v svetu IS| inloFMolJaka baia Opis nosilcev, ki v jajo v svetu IS stanja. Proces, s katerim opiiemo svet 15, je dvokom-ponenten in je ponazorjen na sliki 2. danem trenutku abstain njihova dejanska mehanizme za aanipulaoijc~ z vsebino infaraa-oijske baze. Sprememba, ki jih opravlja nad informacijsko bazo in v CS se opravijo na podlagi sprejetih sporofiil. Vsebina sporofill so ukazi ali dolofiena informacije in te prihajajo iz okolja. Informacijski procesor Je brez lastne iniciativa in se vede le tako kot dolofiaja pravila. To zlasti poudarjamo, ker imajo po principih ISO TC 97/00V007 svoj delel v informacijskem procesorju tudi imajo manualni posegi. 2.6 Trinivojaka «rhltaktura Na podlagi opisanega trinivojskega pristopa nafirtovanja informacijskih sistemov Je zgrajena Trinlvojaka arhltaktura, ki je prikazana na sliki 3. I^dpi pu 1 aci jo z vsebino infornacij opravljamo na konceptualnem nivoju i Informacijskim procesorjem. Informacijski procesor je sestavljen iz materialne in programske opreme ter ljudi. Informacijski procesor izpelje spremembe ali iskanje infornacij za potrebe uporabnikov iz okolja IS. V rafiunalniSko zasnovanem informacijsKem sistemu je informacijski procesor dejansko računalnik skupaj s sistemsko programsko opremo, programska oprano za delo s podatkovno bazo in aplikacijskimi programi. Informacijska baza je implementirana kot vsebina podatkov v podatkovni bazi (PB) skupaj s programi za generiranje sekundarnih podatkov iz vsebina PB. Pravila za delo informacijskega procesorja so delno implementirana v podatkovnih strukturah PB, delno v rutinah sistema za DBS in delno v aplikacijskih programih. Pojem informaoijkke-ga procesorja je v Trinivcjski arhitekturi podan precej spIoSno. Edini pogoj, ki ja postavljen pred informacijskim procesorjem je, da deluje aktivna pri manipulaciji z informacijami v skladu z doloCenimi pravili. To vel ja. za ljudi in za tehnične sisteme. Pod manipulacija jf3 miSljeno sledečei Informacijskemu sistemu je poslano sporočilo, ki vsebuje nove informacije za vnos v informacijsko bazo. Informacijski procesor bo na podlagi pravil, določenih v CS in mogoče v drugih stavkih, zakodiranih v informacijski bazi, informacije sprejel ali jih bo zavrnil in istočasno poslal sporočilo o rezultatih te akcije. Vse astale akcije informacijskega procesorja delujejo na podoben način. V informacijskemu, procesorju lahko delujejo računalniški sistemi tudi kot uporabniki. Tak primer je mreia računalniških sistemov, ki komunicirajo med seboj. V primerih,. ko vsak sistem deluje na podlagi množice neodjvisnih pravil, je vsak sistem uporabnik drugega. Iz tega sledi, da je opredelitev, ali je kakSen sistem uporabnik ali informacijski procesor, odvisna od vloge, ki jo ima sistem in ki jo določajo zastavljena pravila obnaSanja. V praksi je uporabnik v glavnem zainteresiran le za.svoje potrebe, za svoj svet IS. To pomeni, da je zainteresiran za dele CS in IB, za katere je že prej določil, da nu ustrezajo, oziroma da jih potrebuje. Ponavadi imamo več uporabnikov takSnih svetov in jih zaradi tega združujemo v CS s äirSo zasnovo. Tako na primer potrebe večjega Števila oddelkov združimo v skupino s podobnimi potrebami oziroiù "podsveti". Na podlagi tega opiiemo CS zatea kot "unijo" skupin, oziroma kot unijo različnih "podsvetov", ki imajo ekvivalent vsak v svoji "podshemi". Na zunanjem nivoju je za razliko od konceptualnega zelo pomembna prav oblika za predstavitev informacij, zato so formati podatkov v notranji shemi natančno opredeljeni. Formate podatkov določamo glede na potrebe naročnikov oziroma uporabnikov. V kontekstu CS in I.B to pomeni, da je predstavitev podatkov prilagojena različnim uporabniškim procesom. Ta posebni , zunanji videz informacij in njihov pomen je opisan v lunanjl shaal. Sami formati pa so podani v tunanji podatkovni baxl. Z oziram na to, da imamo več "podsvetov", ima vsaka uporabniško prirejena skupina informacij, ki pripada določenem uporabniškem procesu, preslikavo v eni ali več zunanjih shen. V vsaki od teh shem je definirana oblika predstavitve in opis zunanje podatkovne baze, za katero predpostavljamo, da odraža vsebino in obseg tega uporabniškega procesa. Vsaka od teh zunanjih podatkovnih baz je navldatna in je dejansko preslikana v odgovarjajoči del informacijske baze celotnega sistema. TakSna zgradba pa zahteva sledeče: Na zunanjem nivoju je za razliko od konceptualnega zelo pomembna prav oblika za predstavitev informacij, zato so formati podatkov v notranji shemi natančno opredeljeni. Formate podatkov določamo glede na potrebe naročnikov oziroma uporabnikov. V kontekstu CS in IB to pomeni, da je predstavitev podatkov prilagojena različnim uporabnitkin procesom. Ta posebni, zunanji videz informacij in njihov pomen je opisan v lunanjt ahaal. Sami fornati pa so podani v lunanji podatkovni bail. Z ozirom na to, da imaBO vaS "podsvetov", iaa vsaka uporabniško prirejena skupina infornacij, ki pripada določenan uporabniškem procesu, preslikavo v eni ali vaö zunanjih shen. V . vsaki od teh shen je definirana oblika predstavitve in opis zunanje podatkovne baza, za katero predpostavljamo, da odraža vsebino in obseg tega uporabniškega procesa. Vsaka od teh zunanjih podatkovnih baz je navldazna in je dejansko preslikana v odgovarjajoči dal informacijske baze celotnega sistena. TakSna zgradba pa zahteva sledeCai Intagraoljo akcij različnih uporabnikov; tranaforaaeljo zunanjega videza v skupni kon-oaptualni videi, znan celotnemu infornaclj-skemu sistemu. V prinerih, ko je zunanji videz unija vač videzov (na primer, če so zunanje podatkovna baze več individualnih oddelkov grupirane v skupno zunanjo podatkovno bazo na skupnen nivoju), bo zunanja shema zajela vsa posana-zne'individualne zunanja shane. tako združena zunanja shena je dejansko le opis skupne podatkovna baze, ki ina poanotano zunanjo obliko. Vse funkcija zunanja sheme vzdržuje in nadzira zunanji Lnfarnaoijski procesoc. Informacije so predstavi Jane v računalniku kot fizični.podatkovni elementi, kot so zapisi, segmenti, polja in pd. in so del fizične podatkovne baze. Ti formati so zapisani v notranji shemi. Zunanja podatkovna baza je preslikana v II-ilCno podatkovno baio. Najpogosteje se ta preslikava opravi na ani PB. Po principih ISO DP9007 to ni onejitev, preslikava več zunanjih baz je možna na več podatkovnih bazah ali obratno, eno zunanjo podatkovno bazo lahko preslikamo na več podatkovnih baz. Dovoljeni so tudi porazdeljeni sistemi. Notranji procesor opravi transfornaolJo iz zunanje v notranjo obliko. V prinaru distribuiranih podatkovnih baz opiSamo povezave nad notranjo in zunanjo podatkovno bazo s porazdeljeno shemo, ki Ja lahko dal poenotena zunanje sheme ali pa Ja podana kot vnesnik med zunanjo in notranja shemo. Naloga informacijskega procesorja laplanantirano kot nno-žico "postopkov" ali prooedur. Ni rečeno, da opravlja vse te naloge le en procesor, tako so v primeru distribuirane obdelave lahko procedure porazdeljene ned odgovarjaJočini zunanjimi in notranjimi procasorji. Pri vsan tem ostane najbolj pomembno, da konceptualna shema nadzira, kaj Ja opisano v informacijski bazi in ne, kako je opisano. Konceptualna shema nadzira semantični pomen vseh predstavitev, to pomeni, da definira vsa dovoljene akcije nad vsebino podatkov (set of checking, generating and deducing prooeduras). Vmesna stanja (interned lata states) v prooasu transformacije mad zunanjo in notranjo obliko niso opisana. Zunanja shema opisuje, kakSna Je oblika informacij, ki ustreza uporabnikom. Zunanji procesor direktno komunicira z uporabniki in koordinira izmenjavo infornacij. Notranja shema opisuje interno fizična predstavitev informacije. Transformacijo med zunanja obliko in notranjo obliko opravi notranji procesor. To pomeni, da zunanji procesor komunicira z notranjim procesorjem. Preslikava ned zunanjo in notranjo shemo ohranja pomen informacij, tako kot je to doloCeno v CS. Glede na principe Trinivojske arhtekture dovoljujeta zunanja in notranja shea« veCnlvoJ-sko strukturo v notranjem in zunanjea procesorju. Notranja podatkovna baza js lahko implementirana kot drutina internih podatkovnih baz, v katerih je shranjen dal Infori»«-cijske baze. V nekaterih primerih sa lahko ta baze prekrivajo (porazdeljeni sisteat). in sinhronizira njihov dialog oziroma njihovo izmenjavo (zunanjo) podatkov. Za Izvajanje teh funkcij vzpostavlja nivo seje povezave med nivoje predstavitve dveh enot in podpira potek izmenjave podatkov. Transportni nivo ter ostali trije nižji nivoji skrbijo za tehniCne pogoje povezovanja raCunalnika, arete, komunikacij, ki jih potrebuje nivo prad-stavitve. Korelacija med trinivojsko arhitekturo in referen&nim modalom OSI ja prikazana na sliki A. koBciptuatni nivo aplikacij s k i nivo u^abnik sporotila nivo prese Itoci je rac. thr. usluge 1 transportni nivo 1 trans, uslug* trans, usluge 1 nivo mreie mreia usluge ----- nveia uslug« znfiL nivo liniji fiiiCkl ni«o linijtke utluge no Ir. p roc. roč. shr. usluge rapnna za (iz. ■hranjen Vasii/ Slika I,. Nivojska struktura referenčnega modela v povezavi trinivojsko arhitekturo 2.7. Nodal odprtih sistaBOV povaiovanja in trlnivoj«ka arhltaktura Referenčni model ISOa opredeljuje koncepte komuniciranja informacijskih sistaaov (aplikacijski nivo) ob uporabi mehanizmov za povezovanje odprtih sistemov. Hödel Je razdeljen v sedem funkcionalnih delovi uporabnlftki nivo, nivo prezentacije, nivo seje, nivo prenosa, nivo linije in fizični nivo. Uporabnitki nivo ima vlogo okna oziroma okvirja, «kozi katerega poteka izmenjava informacij z Idan-tificirano vsebino v času trajanja koaunika-cije med dvema uporabnikoma. Nivo predstavitve skrbi za predstavitev informacij (v zunanji obliki predstavitve) in za ohranitev vsebine informacij pri slntaksnl analizi podatkov v času komunikacije med dvema uporabnikoma. Funkcija nivoja seje Je, da preskrbi potrebne pogoje za nemoteno sodelovanja dveh enot na ravni predstavitve ter da organizira Konceptualni In zunanji nivo trinivojske arhitekture sta povezana s funkcijami nivoja aplikacije In nivoja predstavitve. Za pričakovati Je, da bodo koncepti, razviti v okviru konceptualna shema, Inplanantlranl v semantika Informacijskega prometa v okviru teh dveh najvišjih nivojev. Točna korelacije in povezave med konceptualnim In zunanjim nivojem CS in IB z ene strani, ter funkcij aplikacijskega nivoja in nivoja predstavitve v aodalu OSI, so ia naprej pradaet raziskovanj In natančnih spaolflkaclj v okviru delovnih skupin ISOa. Notranji nivo ima opravka z notranjo predstavitvijo podatkov, z obdelavo podatkov ter z dejanskim shranjevanjem podatkov na fizičnih medijih. Značaj teh operaolj lahko primerjamo z značajem, ki ga Imajo nivoji 1 do S v modelu ISO. Pri tem moramo seveda opozoriti, da so njihove funkcije (shranjevanje in komu- nikaclje) popolnoma razli&ne. Skupne raziskave (CS in IB ter ISO) »o trenutno u«»«rJeno ki < Studiju stopnje korelaoij, koinoidenpe in uporabnosti konceptov ISO na informacijskih BiStSBih, tako kot je to prikazano na sliki • Studiju uporabnosti (izbrane segnenta) konceptov OSI pri' räzvoju notranjih komunikacij v inforaacijskih sistemih (porazdeljeni Informacijski sistemi). je zadoščeno z definicijo "macroJev^'. Izbor;: teh macrojev Ja odvisen od vrste aplikacij. V opisu sveta IS se sklicujemo na nosilce informacij z imeni. Ta zahteva previdnost glede uporabe sinonimov in uporabe hononimov. CS in IB vsebujeta opise stanj v svetu IS in hkrati njihovo evolucijo, zato morajo uporabljeni konstrukti ömogoOati hkrati opis nosilcev informacij in manipulacij z njimi. Meje in vsebino CS dolcöajo razvijalci informacijskega sistema, pomoö in vodilo pri tem predstavljajo prinoipi, obdelani in predstavljeni v ISO DP 9007. 2.B. Zakljueak Najbolj pomemben prispevek zastavljenih konceptov v ISO OP 9007 je harmonizacija komuniciranja med ljudmi. V zvezi s tem je treba pričakovati, da bodo zastavljeni prinoipi vplivali predvsem na metode, s katerimi analiziramo poslovne sisteme in njihove potrebe. Naloga CS je, da poda spletni dogovor o tem, kaka opisati "obravnavani svet" v poslovnem sistemu, ki pa ima to lastnost, da ne omejuje evolucije in razvoj aplikacij teko» livljen-skega cikla IS in sprememb v svatu IS. CS in IB opisujeta le konceptualni (logiöni) vidik informacijskega sistema, kar pomeni, da »ta CS in IB definirani z elementi in konstrukti, ki se nanaSajc na objekte iz svata IS in ki odralajo stanje teh objektov. Tac-, retska osnova la zapis teh stanj najdemo v formalni logiki. Uporabljani elementi formalne logike pa morajo biti enostavni zaradi zahtev po enostavni uporabi modela. Potrebam po bolj kompleksnih konstruktih, ki omogcfiajo ugodnejši opis razliCnih dogodkov v svetu 13, 3. Reference Delovni dokumentii ISO TC/97/SC5/WG5 on DBlis Coordination ISO TC97/8C21/UGt on 081 Referano« Hödel ISO TC97/8C2t/UQ5 on OSI Application and Presentation Layers ANSI/X3/SPARC X3H<>, IRDS Teohnical Committee Zahvala« To delo Je bilo delno podprto s strani Iskre Oalt« in za to se avtorji zahvaljujejo DO Iskra Delta. SISTEMSKO VODILO MULTIBUS II INFORMATICA 3/86 UDK: 681.519.7 B. Završnik Iskra Elektrooptika, Ljubljana nii'i » i Dus il iG» ntipredno sistemsko vodi io odprtega tipa,nameni.-na ^is^emofn s porasdel ,it?na arhitekturo ter multipro-ct; iii ÌU. óxstcm »'lultibus li je ncHjbal i uporaben sa indu-i:r,ri rsk(> aplik,aci je, kot so, kontrola procesov, robotika, u i r.riic :ni ci risk.č4 oprt-ina ter zbiranje? podatkov. Prednosti so pri računalniško podprtem načr tovan ju, gra+iki, r.ir. 1 h vn simulaciji s pomočjo računalnikov. J-J'; ; ? il IS an advanced open-svste/H& bus designed to I. L Uit' riL-e-ds Ol systeois that are moving t.oward distribu-I.■ h 11 Gct'ir r? ana mu i 11 processi ng . Multibus 11 systems • i\pprupriate i or real-time industrial applications il pracF-si: control and rohotics.as well as for biome- ü;;-..i > a«.! V prtiCiTi t artd dat.> acquisition. Uther applications ".nciLicir «-Qmputer--aided-desiqn and enqineerinu work stations, vjr or^h 1 c. equi pmerit, devGlopmerit systems, and computer simu- I 3 on . li . DC. iAz prodoru znvjci i i v i r. nitnih mi kr or ačunal-r.i > oHK-ii M I.' sisteme je nastala po .'r.c i I i.i, li bs nitro m učinkovito povt'::ovai r..-: I'f. 11? m. ^Jovo vodilo Multibus li I pr eül^odn ; t. ..A v Mu 111 bti,-.-u i, od katerega je privjt.i cr.t- .-.Out .Lì .odi i 1 . nULI IBÜb 11 naj ne bi leqc^ vodila, temveč qa do- poin.it?v/aJ , ria.) .ic n,;. 4e zelo maio -S'^ ! j 11 n 1 h a p I 1 t e I 1 . b'iika pjri M .)€:• arra tek ti.iro MüLMbÜä 11 vodila: ARHITEKTURA MULTIBUS II \7 m ft TV \7 Iz \7 -O Vodilo je odprtega tipa, kar omoqoca velikose-r 1 isko prQi::vodnjo komponent in kar je najvaf-ru? J ie .prenosi iivOTSt programske opreme,preko velikega števila r anriovratni h si st emov. Vodi 1 o ima popolno bitno strukturo, ki omoqoda preko (iii.t I t i p 1 r čin ja , prenosne hi tr ost i preko me-gabaytov na sekundo. Velika prednost Intlovega ,'Odi J a ie v tem,da ima močno podporo v liULIlbUS 1 vodilu,za katereqa je dosedaj 2ot> izdelovalcev proisvaialo prt-ko i 30U izdell:ov. PriČetki ra::vo3a MULI 1 BUS II vodila segajo tri leta nazaj,kci je tntel spoznal,da starejše vodilo ne bo moqlo služiti za 32 bitne aplikacije. Pri načrtovanju novega vodila so bile upoštevane Žt^l je mnogih proi z va jal cev opreme in med njimi le hilo izbrano 17 podjetij, ki so kasneje tudi določile karakteristike MULlItìUb 1 J vodJ 1 a. Vrif/j J o 1 h tib Par a 1 f> i uo sistemska vodilo iPSts, predstavlja QlavMo vadila za rUJLIlBUb li, Ja vlogo mu da~ )C' IO «I K^anve značilnosti : univerzalnost vodi-i , velika prepustnost, zanesljivost delovanja J n 1 :• va larije si stc-mskih tun);ci j , blavnc? značilnosti vodila iPSH so : " ri.-A vodilo lahko priključimo do udeležencev, ki so krmiljeni s 8.1c> aii bit-rn nu pročesor ,i t. i ri iniii io moSnost prenašanja t.1,16,2'1 ali 32 bjtne podatke. -• udöl t-ifc-nc. J i ar-, k t.) poveitijo med seboj preko štirih na^slrivnih Dorfročij : 32 bitno ^iCjCJiTij n^l C , ] bitno vhodno.'i shodno, b bitno i.",c.';>ro' :i? sporočil in lö ditna pov6?2o-lic:- poJ.-'oč le. •• J I..CÌ pr e^pu^t.1 .(;iu.t vodii^ je omogočena 2 hitrost jo del o v-an .1 j; 4 u meg a b^jtov na se~ i:i.:f-.dc in f-aüc-'Ufi i iiu protoKOii deiovan.ia : tiJc'Vi-T.'ni ur ar,erf. li-, prenos sporotii. •• v vodiio .ic t.nd) mehan i 2 em, k i omo- pr ltri juutv.jajG po vnaprej določeni p» t Cif 1 let 1 . •• ^öfic'bi livori deiovöfi.ia .ie irbolSana s sin-hroaim dč?t.ovan >ecn vodila, parni zaščiti prc'ftosi£C 2CKEC CCNTHALM uoor. .i^ijočecj^i udeleženca. Z istimi ijnidami se izvede tudi izmen jalni protokol med dvema udele-? em C efiia n a vodi 1 u. Pamen signalov med pozivno fazo : SCI) začetek pozivne -faze SCI zaklenjeno vodilo . SC2 4irina podatka SrM"' širina podatka SL"',4 naslovno področje SC5 naslovno področje aCfc čitanje/z api GOvanje SĆ7 rezerviran ace parnost za SC7 - ÖC4 SC'/ parnost za SC3 - SCO Komen sxqnalüv nied tazo odqovora : SCij začetek pozivne -faze SCI zak:lenjeno vodilo 'oC'.^ konec prenosneqa cikla ■:;,C-:'. pozivni udeleženec pripravljen SC^ pozvani udeleSenec■pri pravi jen riCf:. r-iapak:a udeleženca dCo napaka udeleženca napaka udeleženca sca parnost za SC7 - SC4 ■ciCS' parnost za SC3 - SCO Siqnalna skupina izjeme opravlja -funkcijo javljanja vsem udeležencem na vodilu, da je pri prenosu podatkov prižlo da napake. Dve signalni liniji javljata napake : IlMÜUf javi napako pri izmenjalnem protokolu in BllSERP;, ki javlja napak:e na nasi ovno/podatk-ovni h linijah. Centralna kontrolna skupina služi za izvajanje aistemekih funkcij celega sistema. Incijal izaći ja sie izvrći s signaloma RSI in RSTNC.ia javljanje napak na napajalnih linijah služiti, -.vijnala ÜCLijW in PRUf. Sistemska ura za cel at-rif' vodilo je generirana po linijah bCLK iri (JC-LK. S pomočjo signalnih linij l.MCHn določimo trenutek, kc> so na vodilu naslov udeleženca in njegova prioriteta. Vse te siqnale generira central ni udeleženec. Napa lanje udeležencev je izvedeno preko iPSb vodila, +5V, +12V, SNU in možnim rezer- vnimi napajanjem. pf citokol na iPSB vodilu Iriie cikli na iPSB vodilu določajo protokol: pozivni cikel, prenosni cikel in cikel izjeme. Izvajajo ga udeleženci na vodilu s krmiljenjem kontrolnih signalov. Poz i vnv-'^ <-:.LC.mala iPSti vod li a, priäko pozi ti vodsf.-o nad -.-odi lom. za začetek prenosa po naslednji signali ; hiKt pomočjo prvega izrazi stopu na vodi i o, pr-ev^o zagonu si Steina določil q naslov vsataega uaeležeri Iste linije deleča io pr riteto udeleženca. v oiTiogoča udeležencem vnega protokola,prevze- lo je potreben pogoj odilu. Sestavljajo jo Ü m ARBS do «R-BO. S dsleüenec äeljo po do-ostalih signalov se ob eaqra-fski in pozivni ca na vodilu. i pozivnem ciklu prio- Nasl ovno, padstliovno skupino lahko uporabljata samo lastnik; voaila in poz vam . Skupino sesta-.Ijajo nasi o ,no.'pdatk:ovne J mi je A031 do ADO in Štirje signali parnostl PAR3 do PARÜ, od k al eri ki -/sat- si;.roi z s pravilnost osmih AÜ linij. (Jb pozi-.-u 5e na mL) linijah naslov in ob c-dqo-or i-i podatek, ki li^ lahko 8,16,24 ali 32 b)tni. bi y: t emsiia sl:Lipiii=i le ic-.?fra iz deset kon- trolnih signalov Hcv do SCO. ki kontrolirajo ptenosni c i !■ o 1 na i i'I:.)!! vocliiu. Signali so časovno mu I t i CI j ek 11 jn imajo različen pomen odvisno oa taz.:' prc'nnaa. ub pozivni -fazi dolo-fajo ukaze in ob iazi odgovora stanje odgovar- Slika prikazuje cikle na iPSB vodilu. /tebon« l«a POZIVNI CIKEL ■ v X: PRCNOSNI CIKEL ■ CIKEL IZJEME- \ CIKLI NA IPSB VODILU poz i ci kel Lld.rH,&!e;nc?i. , ki hoče prenesti intormacijo po vodilu mora izvajati pozivni cikel, rted pozivnim ciklom lahko eden ali več udeleSencev izrazi Sel JO, da postane lastnik vodi 1 a.Rezultat tega cikla je, da satno eden udeieäenec dobi lastništvo nad vodilom in iahko nato izvaja prenosni cikel. V primeru, ko veC udeležencev istoiasno 2eli postati lastnik vodila, dobi lastništvo tisti, ki preko fìRBb do signalov izkaSe največjo prioriteto. Obstajata dve vrsti prioritete, normalna in velika prioriteta. Vsi ostali,med pozivnim ciklom ne i zbrani,udeleSenci in.ajo priviiiqiran poioia.i m po končanem prenosnem, ciklu izbranega ude1eienea,dobi jo glede na svojo prioriteto lastništvo nad vodilom.Tako je moien vsem udeležencem hiter dostop na vodi 1 o. Poz i vni cilrel sestavljajo izborna -faza, ki izbere lastnika vodila in prevzemna -faza,v kateri i.obrani udeleženec prevzame kontrolo nad vodi 1om. Prenosni cikel Udeleženec izvede prenosni cikel s pomoSjo naslovno/podatkovnih linij AD31 do ADOO ter sistemskimi kontrolnimi signali SCS* do SCO. prenosni cikel je razdeljen v -fazo poziva in fazo odgovora. Obstajajo tri vrste prenosnega cikla: enojni prenos, blokovni prenos in prenos sporočil. Enojni prenos potrebuje samo en prenosni cikel za njegovo izvrSitev. Podoben mu je tudi blokovni prenos le da je -faza odgovora podal Sana. Pri tem prenosu si dva udeleženca na vodilu izmenjata vlak podatkov. Prenos sporočil uporablja udeleženec, ki hoče istočasno prenesti sporočilo večjemu Številu udeležencev.Med prenosnim ciklom mora pozivni udeleženec kontrolirati in detektirati eno od pet možnih napak, ki se lahko pojavijo na vodilu: trajna napaka, napaka v Sirini podatka, napaka podatka,napaka sporočila, večkratna napaka. Kot posledica de-tektiranja napake sledi prekinitev prenosnega cikla s strani pozivnega udeleženca. Pri prenosnem ciklu je možno izbirati med tremi naslovnimi področji s katerimi lahko izmenjamo podatke ali sporočila: - spominsko področje ima 32 bitni naslov in 8, 16,l"t,32 podatke,blokovni prenos z inkremen-tom ter možnostjo izmenjave z enim udeležencem. - vhodno/izhodno področje s 16 bitnim naslovom in 8,10,24,32 bitnim podatki, blokovnim prenosom z enim udeležencem. - področje sporočil z 8 bitnim naslovom,z možnostjo samo zapisovanja 16,32 bitnih podatkov , bi okovni m prenosom z enim ali veS udeleženci . - povezovalno področje je 5 bitno z B bitnimi podatki in možnostjo izmenjave podatkov z enim udeležencem. Vsako od teh področij ima svoje značilnosti m uporabnost v MULTIBUS II arhitekturi. Cikel izjeme Cikel izjeme izvede potrebne postopke za odpravo nepravilnosti na iPSB vodilu.Prekine vse aktivnosti na vodilu in omogoči mrtvi čas, ki je potreben,da se obnovi normalno stanje vodila.Cikel izjeme je sestavljen iz -faze detekti-ranja napake ter faze obnovitve. Napako dekodira centralni udeleženec in jo preko signalov izjeme BUSERR in TIMEOUT javi ostalim udeležencem ria vodi 1 u. Udel ež ene i , ki dekodirajo prisotnost signalov napake, prekinejo vse tekoče aktivnosti in ostanejo rieaktivni do trenutka, ko preteče mrtvi čas. Centralne funkcije fiULIlBUS II sistema Izvaja Jih centralni udeleženec preko kontrolne skupine signalov. Preko njih se izvede hladni zagon, vroči zaqon ali inci jal i zaci ja sistema ter regeneracija sistema ob izpadu napetosti . Električne značilnosti iPSB vodila Tri vrste eleektričnih vezij so uporabljene za prenos informacij preko iPSB vodi 1 a :tri ni vojska vezja, vezja z odprtim kolektorjem in diferencijalna vezja. Vsa gonilna vezja morajo generirati tokove do 60 mA in izpolnjevati Časovne zahteve, ki jih določa največja hitrost prenosa informaci j.Na vezni ploSČi morajo biti vsi signali ustrezno orosko zaključeni.Pri kiju-Čni 96 polni konektorji morajo izpolnjevati zahteve po maksimalnem toku potrebnim za delovanje iPSB vodila. Mehanske značilnosti iPSB vodila MULI1ÖUS II določa tudi mehanske dimenzije povezovalnih in osnovnih ploSč ter DIN 9ó polne pri kijučitvene konektorje. Povezovalna ploiča za iJ?SB vodilo ima 20 konektorjev in vse potrebne omske zaključitve. Poznamo dve vrste osnovnih plošč:enojna <220mm K lOOmm ) in dvojna ( 220mm k 233.4mm ). Pri dvojni osnovni pložči je zgornji konektor izbran za iPSB vodilo, spodnji pa za ÌLBX II vodilo. Pri efiojni osnovni plofiči imamo samo en konektor, ki je povezan na iPSB vodilo. □ snovne pložče so standardi z i rane po lEC normativih. Vodilo ÌLBX II To vodilo omogoča lokalnemu procesorju razširitev spomina.Zaradi velike hitrosti prenosa ( 48 mega baytov ) se dodani spomin vede kot lokalni spomin vgrajen na sami mikroproceaorski ploiči. Vodilo lahko povezuje do 6 udeleìencev,pri marni in sekundarni udeleženec ter Štirje udeleženci, ki prvim dvema razSirjajo spomin. Upravljanje vodi la,si med seboj menjata primarni in sekundarni udeleženec po izmenjalnem protokolu.Vodi-lo ÌLBX II je ločeno od iPSB vodila.Možna povezava med obema vodiloma je preko primarnega ude-1eženca. Slika prikazuje maksimalno konfiguracijo iLBX II vodi 1^ : MAKSIMALNA KONFIGURACIJA ÌLBX VODILA Glavne značilnosti ÌLBX II vodila so : - možno je priključiti največ äest udeležencev na vodilo od teh sta dva vodja vodila - možna je blokada vseh aktivnosti na drugih vodilih, dokler poteka nujna izmenjava podatkov med udeleženci na ÌLBX II vodilu - zaradi ločenih linij za nasi avl janje,sistem-ske ukaze in podatke je omogočeno prekrivanje aktivnosti na vodilu - vse operacije na vodilu se izvajajo sinhrono po taktu, ki ga daje XBCLK ura ( maksimalno 12 MHz ) - vodilo uporablja zaradi veČje hitrosti delovanja enosmeren izmenjalni protokol - omogočen je dostop do dveh naslovnih podro- ci j, spominsko in povezovalno. -- delovanje vodila je določeno 2 naslednjimi cikli : ponivni cikel,prenosni cikel in ci-kei i :: jeme. - velikost podatkovnega vodila je 32 bitov - velikost naslovnega vodila je 26 bitov Üpis-SI gnal ni h linij na iLBX M vodilu Za izvajanje opnraci 1 na iLBX II vodilu so potrebne siqniUrvG I ini je, ki so glede na -funkcije, ki jih opravljajo, razdeljene na ^tiri grupe : - por. ivria signalna qrupa • - prenosna siqnalna qrupa signalna grctna sistemsko kontrolna signalna grupa Pozivna signai^\^< grupa Sestavljata ,ja dva signala XBUSACK in XBUSREQ, katera omogočata isffienjavo lastnistva nad vodilom med primarnim in sekundarnim udeležencem. Trenutno stanjf teh dveh linij dolofia tudi lastnika ÌLBX II vodila. Prenosna signalna grupa Sestavljajo jo 64 signalnih linij, ki omogòiajo dve -fazi prenosa po iLßX II vodi I u: poz i vno -fazo in fazo odgovora. Pri pozivni +azi prenosa sodelujejo naslednje si gnal ne 1 i n i ,ie : - naslovne linije XAjfi do XwOu - komandne linije XC3 do XCO - signal parnosti AMPAR Pri -fazi odgovora sodelujejo naslednje signalne linije: - podatkovna iinij^ aij.31 do XDOO - signal parnosti XOPaP Naslovne linije krmi 1i mea pozivno fazo prenosa primarni aki sekundarni udeleženec. Vsi udele-5erici,»::i odgovarjajo na poz 1 v , spr e jema jo te linije. Naslovnim in komandnim linijam je dodan saradi zaneslj1vosti prenosa signal parnosti. Komandne linije krmili pozivni udeleženec ter preko signalnih linij aCI xn XCO določa obliko podatkov pri prenosu ( 1 do 4 byte ).Lini ja XC2 pove ali bo prenos zapis ali čitanje. Linija X-C3 določa področje nasi avljanja, spomin ali povezovalni spomin. Podatkovne linije so dvosmerne in prenašajo zapisane in čitane podatke po vodilu iLBX II.Tudi tem linijam je zaradi zanesljivosti prenosa dodan signal parnosti. Signalna grupa izjeme la signalna grupa omogoča javljanje napak,ki se pojavljajo pri prenosu. Temu namenu služita signala XDERR in XAERR, ki označujeta napako na naslovnem oziroma podat kovnem,vodilu. SistemsJ:o kontrolna 5:,ignaina grupa Omogoča kontrdlo sistemskih -funkcij celega iLBX II vodila, reset, i ne 1 jal i zaci jo, takt ter kontrolo sprejema. Te funkcije omogočajo naslednji ■ si gnali : XWrtIT signal podalŽuje operacije na iLBX II vodilu in tako omogoča priključitev počasnih ude-1eženccv. XACCREQ signal označuje začetek in konec pozivne faze prenosnega cikla ter veljavost naslovnih in komandni h signa1ov. XLÜCK signal izključi vse aktivnosti udeležencev iLlšX XI vodila na ostalih MULTIBUS II vodilih. XB'fCTL označuje blokovno izmenjavo informacij med udeleženci. XlNI signal omogoča udfi-i ežencem, da javijo pri- marnemu udelesenČu prekinitev izmenjave informacij na iLBX II vodilu. XBCLK signal je sinhrona ura za celo iLBX II vodilo in ga generira primarni udeleženec. RESET signal omogoča i nei jal isacijo vodila. XID2 do X1DÜ signali priredijo enolične naslove vsem udeležencem na vodilu. Po iLBX vodilu so speljane tudi napajalne linije +5V in GND. Protokol na iLBX II VODILU Protokol na iLBX II vodilu sestavljajo trije cikli : - prevzemni cikel - prenosni cikel - ci kel iz jeme Slika prikazuje iLBX 11 protokol iLBX II PROTOKOL pREvzoM oca -h "V / V- / ■H i >+- I i""" bytov. Povezovalni spomin omogoča i nei jal i zaci jo vodila ob resetu-Prenosni cikel omogoča tudi zelo hitre paketne prenose irHormacij. Enemu pozivu lahko sledi več odgovorov. Pozivu pri prenosnem ciklu sledi odgovor, ki je lahko s pomočjo signala XWAIT poljubno zakasnjen. Udeleženci na iLBX II vodilu morajo imeti 32 bitno podatkovno priključitev in s pomočjo prenosnega protokola lahko izločijo 8, lö ali 32 bitne podatke. Cikel izjeme . , . Namenjen je javljanju napak, nastalih pri izmenjavi informacij na iLBX II vodilu. Javljene so lahko tri vrste napak : napaka poziva, napaka odgovora in stalna napaka. Protokol te napake javlja,ne določa pa načina za njihovo odpravljanje. t-, i ekt r I ir.is jn«>^ilnosti iLHa li vadila Siqr.aJi v-ijcliiu «lo r=.::del le^ni v tri qrupe:tri niv'ojsi.1 -ir.iiJ i , sKinalj r odprtim koJ el'tor jem in diioronci talni sionaii. Umsko zaključitve si-qn.:ilov so j.'ìvgcigtu? na tt i r i q L asi tn i povezpvalni pioaii. I-i nosi Vi) kontaktnih konektorjev U IN 410,11; J. HlGcie na potrebno hitrost iLBX II v'Odila je izbraiìa töhnaloqija za krmiljenje si-F^.Si in (hI>V(ANi..H L- ÓCHUlfKY. VOC} ilo 1 Vodi ic, i iVjB DiTiocoČa «ieri povezavo enot na sistoi'fnu ilULl'IhiUS 11. Predstavlja ceneno alterna--t i vo D«ir Ò ! b-i ne-ftiu ü i t vodilu iPSb, kate- rega nadomei^:^ ali dopolnjuje pri kontroli ter d:«gnoatiki. (31 «vne i I no'üt 1 vocivia Vodilo lankG sizT-1 iHLko poveze do 32 enot,pri ki ju-it^nih di rcjl. t no , al i vei , idruSeni h preko repeti-torjev. heptìf. 11cr 11 2:man4u jejo in izolorajo kap cic i J .'nfe?n 11 e v. NaksimaJna dolžina iSS8 vodila je lahko iu metrov . hepivt i tor .U iahko povežejo v celoto največ ■^O enot. Ülika pri kasu i e mofrìosti za priključevanje enot n.i iCìSu vodilo : Napake na vodilu detektiramo s pomoč io aodatne 16 bilnc kode, ki se dodaja prenosu.Umoqočen je tudi ponoven prenoB sporočila, Če le ta,ni vei- j aven. Vodilo MULIlCHrtNNAL Ii.kU to vodilo je bilo privzeto od riUL I I BUS X in omogoča priključevanje peri+ernih enot, ki uporabijajo zelo hitre blokovne prenose podat-Icov. Priključitev takih enot direktno na iPSB vodilo, bi povzročilo močno zmanèanje njegove prepustnosti.bol S i na vodila je lahko do Ib metrov m omogoča priključevanje do 16 naprav, ki so prilagojene za delovanje na tem vodilu.Vsaki od teh naprav je dodeljen naslov,razen kontrol-rti napravi, ki vodi celotno vodilo. Podatki, katere prenašamo po vodilu so lahko a iyl\ 16 bitni. Področje nasalavl jan ja obsega 16 niaga--bytov.' Blokovni prenosi uporabljajo asinhroni protokol in prenašajo zaporedne lokacije spomina tako, da pošiljatelj, t-akor tudi sprejemnik Starna skrbita za pravilno naslavljanje. l-'renos se prične z vodilnim naslovom in vsak udoležervec. v prenosu sam povečuje naslov odvzemanja ali shranjevanja podatka. Zanesljivost prenosa preverjamo s pomočjo par-nošti podatkov. Na sliki je prikazan sistem, ki ga povezujejo v celoto MULTICHANNAU vodila. Video kamera je izvor velikega števila podatkov, ki jih posredovalna naprava lahko preusmeri direktno na gra-■fični terminal ali posije podatke na drug MUL-riBLlS sistem, kjer se dodatno obdela io in nato izpišejo na grafični terminal. MOŽNA KONFIGURACIJA iSSB VODILA PRIMER UPORABE MULTICHANNEL V00lL^ Serijsko voaiio isbB tizično sestavljajo dve liniji z odprtim koiektorjem ( SDA, SÜB ).Te linije vsAka ejnota lahko cita ali krmili. Dekodirana «stanja na dveh linijah prikazuje tabela. iütH lini ja SOÜ lini ja pomen zmešnjava logična O logična 1 neakti vno Sperejemniki lanKo spn/jet signal vzorčijo in tako izločijo motnje iz sporočila, kar omogoča ^•unkci jonal nost vodila v teikih pogojih delovanja (velike motnje iz okolice in ostalih vodil). Protokol na iSbB vodilu Vsaki enoti na vodilu je omogočen prenos kadar— koli je pripravi jena. Pred prenosom se mora prepričati, da je vadilo prosto in počakati na okno . katerem lahlo posije sporočilo.Ker je mo2nü,da več enot istočasno prične s prenosom sporočila IG dodan posebni algoritem, ki preprečuje zmešnjavo na vodilu. Ob detekciji takega stanja se (frtsovno f.inrctzdeli .'^i.^iki enoti okno v katerem lahko pričrte 5 prL-;n050tn. lako je čas, potreben za razrešitev zmešnja^vo na vodilu, zelo kratek,kar amcqo(;a zelo hitre- prenose. Udeleženci na MULTICHANNEL vodilu. blede na funkcije, ki jih opravljajo na vodilu jih delimo na : -vod 3a vodi 1 a -kontrol or vodi 1 a -osnovni udei ezeneč Vodja vadila opravlja funkcijo organizatorja delovanja celega vodila. Qn določa kakšno delo bodo opravljali kontrolorji vodila in lahko v vsa-keio trenutku prekine aktivnosti na vodilu ter provzanie kontrolo. To je tudi edini udeleženec vodila, ki nima prirejen naslov. Na enem MULTICHANNEL vodilu je lahko samo eden vodja vodila. Kontrolor vodila lahko samostojno usmerja podatke po vodilu m obenem opravlja iste funkcije kakor osnovni udeleženec. Ne more pa prevzeti kontrole nad vodilom in odgovoriti na interapt. Na vodilo je lahko priključeno do 15 kontrolorjev katerim so prirejeni naslovi od OH do GEH. Üsj-jovni udeleženec lahko na zahtevo vodje vodila .^li kontrolorja vodila pošilja ali sprejema podatke. Lahko opravlja tudi obe operaciji istočasno, Na vodilu je lahko istočasno priključenih 15 osnovnih udeležencev, katerim so prirejeni na-ovi . Vse enote priključene na vodilu so lahko v dvehi ütanjih, «ktJvne»n in neaktivnem. Vodja vodila I iihkcj f>noie iziadi is vadila taka, da ji^i preklopi v nor3kti.no «stanje. Aktivna onota je? lahko v t'nen c(i riii'ikiti't i h ist anj : 1 vTiCJ stanje •• i/br^.j.o -it im je ■• jn pf.rsl uČ.3n ja - ^ t .. : C- p C) ž 1 I J an J a • itanir popolne odvisnosti • --^.tanie ^Kiwnlneqa n^^dsora V p-5», ki ;e ci\ < cr cjac i tal r».-*, Irbran vocJ.ia vu.di i 1 kontr olor vodila krmili i.ontrolni rt i f er c?nc i lai n i liniji ( ADDfttEiS-NOT- , f-WFU ! H" '.Preko njih označu je , kda j jG na vodilu naslov ali podatek ter pove kdaj se izvaia operaci JÄ čitanj<.< ali zapisovanja. Linije za cioqaVv^r j^n le ^(u2ijo pošiljatelju in posi u&ji I cu za dogovor o iiimenjavi podatkov med seboj, lo cpisracijo opravlja d i f erenc i j al na linija C DhTA in dve liniji { ADDRESS MODE AUCEPì.DrTh nüDt «CLEPf >. Linija , ki ozna-Ču.ie spfr-'ion. je loaiČnn povezana v AND funkcijo, kar oino-ioč^^. c3a vsi poslušalci na vodilu sprt-jmojo njsJov. Uve prekinitvene linije SUPERVISOR UiK.E ÜVEfV, SERVICE REÜUES1 > sta povfezan: z loqiino UK' funkcijo,da lahko istočasno vtič enot qenorira prekinitev. Edini posredovalec pri prekinitvi je lahko samo vodja vodila. F'r ek 1 n i tev of3nR?r i r a JO enote, ki zaznajo parno napal:o n^ podatkovnih linijah ali napako same enote. ioiUc^ndni I i ra J i vodje- vodi 1 a , s 1 ui i t a za incija-1 i zaci JO vodila in za prevzem kontrole nad vodi .I aa.. Uznačeni sta s t SUPERVISOR ACT IVE,RESET>. Üb rtJsetu preside io vse enote na vodilu razen vodje vodi 1-5 v stanie poslušanja. Protokol i-ILJLi ICHnNMEL vodila Protokol jC' sestavi j€»n iz ciklov vodila, ki se zdrui2uje;o v spnroč i i j. Minimalno sporočilo šesta.-,- ijajo : - dva uvodna c j i a , ki izbirata poslušalca - on ciksi za prenos podatka (8,16 bitnega) •• dvij zakl iuČna cikla za izklop poslušalca uvodni.na i n z ak 1 juČn i ma cikloma je lahko poljubu.. dolq vlr.k podiitlov. PreruDS poteka asinhrono trc^h abiik.4h : - naslovna oblika - podatkovna oblika - hontrolni« oblika Naslovna oblika prenosa omogoča izbor poslušalca in njegovo i z kiopitev.Sestavi jena jo iz dveh ciklov, ki preneseta sporočilo ::druSena v dveh (Ü ali 16 bitnih), besedi določata naslov spomina ali regi strov,nas)ov enote s katero ^•c.li dogovarjanje in smer prenosa. Podatkovna oblika slu2i za prenos podatkov med dvema enotama na vodilu in je lahko le sestavni del celeqa sporočila. Število prenesenin podatkov rni^d.pozivom in izklopom pozvanega ni omejena. Smc?r pošiljanja podatkov je določena v uvodnem nasi (jvntcm aporoč i 1 u, posi anem poz van emu. Kontrolna oblika sluSi izmenjavi vodstva nad vodilom med vodjo vodila in kontrolorjem vodil«. Kontrolna oblika je potrebna tudi, ko vodja vodila prevzame kontrolo in izklopi vse udeležence. Polek spominskega naslavljanja,ki obsega.16 me-qa bajtov, imamo tudi registrsko naslavljanje z obsegom 32 mega bajtov. Registri so lahko 16 ali 8 bitni. Prvih 16 registrov ima poseben namen v MULTICHANNEL vodilu in so namenjeni za sistemsko uporabo.Preko njih lahko vodja vodila ugotavlja vzrok napake v priključenih enotah in programira koritrol or jp vodila, da izvedejo samostojne naloge. Elipktr K^-ne lastnosti MUL TI CHAr-4NEL vodila SčiMiu vodilo ni namenjeno tudi napajanju posamez-riih t?not , temveč mora vsaka od n iih imeti svoje lat%tnti Ttapajanje. liiqndlne linije so izvedene s pomočjo preplete-tieua. kabl.a z maksimalno dolžino IS metrov. Trije »ipi ojačevalnikov signala so uporabljeni za pre-non signalov : tri nivojski TTL, 1 TL z odprtim kol t» k t or lem in di + erenc i jalni . Mehanske značilnosti MULTICHANNEL vodila Priključitev MUlVIbUB 11 kompatibilne plošče na MUL. riCHANNEL vodilo je izvedeno s oO pinskim ko-ncr^k tor jG?m, priključenem na 60 linijski ploSčat pr£?plt?ten kabel. MoSki del konektorja je pritrjen poljubno na vrhu plo&če, ki je prilagojena za MULnCHANNEL enoto. Kabel mora imeti na začetku i ri koncu ustrezno prilagoditev. Vodi lo iStiX II» vodilo ie bilo privzeto od MULTlbUS 1 in omo-ogača enostavne in cenene razširitve vhodno/iz licidnih funkcij osnovnih MULTIBUS II ploŠČ.CJsnov-ni plošči dodamo preko iSBX vodila manso ploščico, ki ima lahko dve.' normirani velikosti. Tako osnovni plošči, ki je lahko pol jubfvo zasnovana, dodanio paralelni vhod/izhod, serijsk vhod/izhod, gr^ifiko ali izpopolnjene matematične funkcije. Vsak uporabnik lahko tako doda speci+ične značilnosti univerzalni plošči in v svoje izdelke vrui'^^e nove dosežke LSI tehnologije. Ker dodajamo vfidno le ti sto, kar potrebu jemo , se zmanŠajo stro— 2,ki za razširitev sistema. Vodilo iSBX sestavljajo naslednje linije : Naslovne linije- in linije za izbor vezja Podatkovna lini je KontraJ ne linije Prekinitvene linije Dodcitnc 1 ini je Napa i al ne linije Kt'.^&rvne? linije Niislavne liniie in linije za izbor vezja sestavljajo tri naslovne linije tMAO,MAl,MA2) in dve liniji ra irbor vezij U'lCSO,Mt;öl ) . Te linije omo-qoiajo osnovni plošči, ki jé lahko ló ali 8 bitna, da naslavlja naslo\'e na 16 ali Ö bitni raz-Siritveni plošči. Podatkovne linije e.o namenjene obojestranskemu prenosu podatkov med razžiritveno ploSto in osnovno ploèio. Odvisno od vrste plo^č, jih povezuje, je uporabi leno 8 ali 16 linij. Osem bitnemu prenosu slujijo linije (MDÜ-MD7) in Šestnajst bitnemu, linije (MIJÜ-HD15) . Kontrolne linije kontrolirajo smer pretoka informaci j z ukazoma za čitanje in zapisovanje (I-ÜR1>, 1QWRI). 1 nei jal izaci jo dodane plo4Ce izvedemo preko linije (RESET). Takt za razširitev je voden preko linije (MCLK) in sistemske linije za pavzo in prisotnost razširitve, preko alskf Oó^MDE POOATakä : predstav lja osfjcvm CPLIK JRCamzcvanja podataka. nije ■ mali brcj 'knjiga' ktjc sluje ìa različite evidencije a KCC KCJIh je CF cani zacicna jedinica podataka je:an (ili vise» ked kcji je u automatskoj "ißfadi podataka .najjeoncstavhije i cesto i najefikasnije cpiiaim züvat i kao slog. i poftto savreh^nijih oölika organizacije podataka uvek će "cstcjat:- jsllvi PCO kojima je optima lna cfcamz4c1ja P3E,atàka upravo organizacija pcoataka pr'tkc slcgova condsno dpranizacija pg' dataka pkekc catcteka. u slocrvi««! crg^nizacija pcdataka, u datotekama, mcje pcstqjati, u 0p5tim uslovima, samo jedan foe«alm fizički reüosled slcgcva. forca-lni redosle: jf fecosltc slogova kcji predstav lja oblik cr0aniza3ije podataka na osnovu kojeg se projektuje korijćet.je öaze podataka. poo fo rm;.ln1m fj't.kim fćdosledom pcdkazumeva se RtD-csled slogova U OCUUSU na adrese slogova u hem-criji. p0dra2uweva s£ üa je jejan skup slcgcva, jedna datct-ka, u hertüru: smejien samc jedncm. ürucim rfčim»,ikc se na osnovu jednog polja slogova foi^kipa formalni fizički redosled ckoa, u cpstim uslcvimi, i.e postcji formalni fizički reogsleo u goncsu na bilo koje drucc pclje slogova. reocslsd sadržaja drugih polja ü odnosu na fizički reccslfo sllgova je slučajan. na primer, u cp5t1m uslovima slogovi mugu biti sortirani samo opr^a sadržaju jednog polja. JEDAN »=CR,viLM fizički fEDOSLED SLOGCVA JE ATKIßüT VI5'!KLJUCNE CRGANIZACIJE PODATAKA. FORMIRANJE FCRMAL.NUi RtOCSLEOA SLCGCVA JE PC SLEDNJA C PF L JE KTOVAN JU ORGANIZACIJE PODA- TAKA. POP'^O FCPMALNOC FIZIČKOG J-'OCSLSCA POSTO JE FORMALNI RECOSLEDI KOJISF ZADAJU SPfEGOM UI TABELA-^A. L VISEKLJüCNCJ ORGANIZACIJI PODATAKA PKISTUPS SE FCRMlRAfiJU FGfMALMH FEDOSLEDA A NA OSNCVL SACFZAJM OSTALIH POLJA U SLOGU JER se SAMD JECNC POLJE SL'üGA M02E UPOTREBITI ZA FORMIRANJE FTRXALNOG F I ZI CKOG REDOSLEDA SLOGOVA, VISEKLJU^NA CPGANIZACiJA PODATAKA PREDSTAVLJA 'FORMIRANJE VISE FORMALNIH REOOiLEDA A NA OSNOVU VISE RAZLIČITIH PCLJA U SLOGOVIMA. KLJUČEVI SU SADRŽAJI POLJA U SLOGOVIMA KOJA SU ISKtRISCENA ZA FORMIRANJ? FORMALNIH REDQSLEüiA. U VISEKLJUCNCJ organizaciji podataka KLJUCtVi SE DELE NA JEDAN PRIMARNI I VISE SEKUNDARNIH KLJUČEVA A PREfA bRDJU FORMIRANIH FORMALNIH RE' DOSLEDA. POD PRIMARNIM POLJEM NEKOG SLOGA PODR-AZUMEVACE SE PCLJF ZA KOJE VAŽI DA U CATOM SKUPU SLOGOVA NE POŠTUJE OVA SLOGA SA ISTIM SADRŽAJEM TOG PCLJA. PCD SEKUNDARNIM POLJEM PODRAZU MEVAĆE SE POLJE KCJE NIJE PRIMARNO. KLJUC JE SADRŽAJ PfLJA KOJE JE UPOTP Eßi.Ji NQ. Z A OEfllUi. ANJE FORMAL'NOÄ REDOSLEÜA. BEZ ZNAČAJA Jt Ofc LI SE POLJE CUI SADRŽAJ PREDSTAVLJA KLJUC NALAZI ILI NE NALAZI U SAMOM SLOGU. DEFINISANJE PRIHA-RNOSTI KLJUCA NA CSNCVU PRIHARNOSTI POLJA CUI SADRŽAJ JF ISKCRISCEN ZA KLJUC, NIJE EFIKASNL. MOGU POSTOJATI I TAKVE ORGANIZACIJE PODATAKA, PREKO SKUPA SLCOOVA, TAKO DA NI JEDAN KLJUi NIJE PRIMARNI, DA SE NI JEDAN KLJUC NE OEFINISE NA OSNOVU PGLJA KLJE JE PRIMARNO. PRIMARNI KLJUC SE DEFINISE TAKO DA SE NA OSNOVU PRIMARNOG KLJUCA FORMIRA FCRMALM REDOSLED SLOGOVA. SEKUNDARNI KLJUC JE KLJUC KOJI NIJE PRIMARNI 5T0 ZNACI DA SE NA CSNÙVU SEKUNDARNIH KLJUČEVA FORMIRANJU FORMALNI REUDSLEDl SLCGCVA ALI OVI FORMALNI REDOSLEDl NE ZAVISE 00 POLOŽAJA SLOGCVA U MEMORIJI. OVAKVI FORMALNI RLOOSL-EDI MOGU SE FCRMIRATI BEZ OBZIRA NA REDCSLED SLOGOVA U MEKCRIJl. VISEKLJUCNE ORGANIZACIJE POOaIAKA MOGU QUI I BEZ PRIMARNOG KLJUCA STO ZAVISI 00 USLCVA PRIM-ENE. 2. TRAŽENJE 1 PRETRAŽIVANJE U VISEKLJUCNIM ORGANIZACIJAMA PODATAKA sa stanqvista organizacije podataka, prema(2) memorija se »cže shvatiti kao skup znakova, kac skup polja ili kao skup slogova. izmedju znaka pclja i sloga postoje samo organizacijske razl ike jer sv? tri c fg an i ZAC ione jtoimce PfEDSTA vljaju S«CRJ»J SKUPOVA, SKUP Ht.2E IMATI I SANU JEOAN EL^'^'^NiT ME KOR IJ SKI H ĆELIJA. CVE MEMOHJ-SK.E ćelu:- su ITErAIIV'Jt SUSEDf.ć. OVAKVE MEMCSUSKE ĆELIJE OBF.AtUJU SKUPuVE MEMGRlJSKlh ĆELIJA KOjI se FCfMlf-AJU PFEKC LEVC SUSEDMH ( ILI DESN*" S'-SECrilU MFMOF USKIH ĆELIJA PCCfcV GC PfvÜUVOLJNE "CfJrUSKL ĆELIJE. DUŽINA ITEFACIJE JE PRjlZVCLJNä. iKO JE DPCAllI ZACIüNA JEÜlNItA fCFMIRAN^ 'JA SAMO JEJNtJ HtMORIJSKOJ ĆELIJI qnüa Jt ĆELIJA 3AMA ifßl IIERATIVNC SUSEDHA, BIT KAO i-^G rJIZACIt.JA JEDINICA PODATAKA ^iEMA ZfiAĆAJA CG^i.NIZACIJE PODATAKA KCJE SU NAJČEŠĆE U PRSKTI^NCJ FRIMCf.I. za JEFTMSANJE TFAJEMJA I pret P.až IVAf. ja MCGU SE ZANEM'.FITI r.AZL!K£ 1ZMEÜJU OkCANl z acl ON IH JEDINICA K4KC 51 SE ^ET-INISALI uPSII ASPEK11. h^fDVERSKT PCLJE SE PLORAZUMEVA KAC. SKCF !TEFA TIVNC SuS-^ONlt- ME^OF USKIH ĆELIJA LDMOSrZ CELIM, S UUiJP---^ NS PAFALEL^E CPEFACUE, PAFALELMI FrJSIJ? r-SK JrOIMCAMA, VISEKL^UCNA CFCANIZAC lJA PÜ0ATÄK3 vržE G?: f.ALJf 'JN APR E 01 T1 AKO SE HAkDVEFSK'^ CELINE SHEiUAJ'J :.A F.AZLICITE U1 SK J5D1/.ICE. indeks;;-AfJJfc se VFSI NIVCU HARCiVt-FSKIH CELINA PC 0I5K jLOlMCA.-iA NAJEFIKASNIJE JE DA TO ^.iJDU CILIHOH. ::A TAJ fJAilfJ, F'F.l UOBF-CJ CFGAMIiCIJIi FREIFA2IVAMJE SF MCiE VF 51TI BEZ POMEilSNJl «EHA.NIZWA ZA ČITANJE 1 PISANJE. OVAKVI, "AI^AL'L.U ĆELIJSKA OF G Ai^I Z ACI JA, UNAPF.-EOJÜJE PP'-.TRJnVA.NJF Na OSNOVU KAF.CVERSKIH KAF ■ AKTEBISIIKl AKO Ll^TA K,:;tKSA SAOFll UPIS PO SVAKCM SLOGU CATOTEKE rN-:! JE TC IÌ:VFFT^VANA LISTA. U IMVEF,-TÜVANÜJ LIST! s: NALh^E, U SVAKOM SLOGU INVERT-OVAfiE LltT'?, sv: SEKJ^GARr,! KLJ>.(".EVI PC KOJIMA SE VF.5I F^ETSJJIVA.MJE KAO I ACCESE ILI PHIMAFM KLJUČ SLOGA 12 KOJEG SU PF.EUZEl I TI SEKUNCAkM KLJUČEVI. I'IVEFTOVA.ilK LISTAMA SMANJUJE SE MEM CFIJSKI OFCSTCF KCJI SE PFETFA2UJE A KAD REZULTAT PRETR IJIVANJA UUaiJA SE SPISAK AORESA ILI PRIMARNIH KLJUČEVA SLCCOVA IZ KCJlH ČE SE PREUZETI ?CD".C1. Si S CAN J E MM VESv-RIJSKIH PfOSTOFLK SMANJUJE S"^ KRETANJE MEHANIZMA ZA ČITANJE I PISANJE ČI'-E SE UüRZAVA PRETRAŽIVANJE. DRUGA MCG UČNOST JE, KSDA IR;ERT^VAKE LISTE MSU VELIKE, OA SE INV^^.RTOVSNE LISTE U CELINI, ILI U DELOVI-MA, PPETF^!■^.JL 0 C;;)TFALf;LJ JEDINICI ČIME SE ZNATNO U3F2AVA Pi"; ETR AZ I VAN JE . I INVEOTOViNE L13TE l'iOOU IWAU SAMO JEOAN FO RHALNI FHIČK: FEGÜSLEL. FORMIRANJEM FDRMALNIN REDOSLECA MOJE iE, NCF>;ALNO, POVEĆATI EFIKASNOST PRETRAŽIVANJA l'iVtklCVAriE LISTE. SADA SE INVERTCVENE LISTE MOGU SHVATITI KAC VISEKLJUČNA ORGANIZACIJA PCOATAKA TE SE MÜZE PRIMENITl PRF THCONO REČE.IO C FORMIRANJU FORMALriIFi REÜOSLEOA. MOGU SE nCVCJITI SEKu.NOAFNI KLJUČEVI KOJI IM AJU ZMAČAJMJE MESTO u PRETRAŽIVANJU I SAMO NA OSMOVU NJ'.b '^:RHIRATi FOFMALN'. REUCSLEOl INVEF-TOVANE L'STE. POSIUPAK Sb MOZE NASTAVLJATI U ZAVISNOSTI Cj EROJA SEKUNDARNIH KLJUČEVA. POVEĆANJEM BRZINE PKcTRAZI VAr;jA LFGANIZACIJA POCATAKA POSTAJE SLOZtrajA I ZAUZEČt MEMCRIJS-KOG PROS''CRS PC3TÌJE VEČE. RE5ENJE OVOG PROBLEMA.JE U 'OTI^rZAClJI A PREMA SOPSTVENIM KRITFF-IJUMI.MA. MLJ' V (SK 1 'ILI' • ILI' K I : V tS!< ) v \ k»1 H jr afc) vh^cnosti i-ic.& sckokoaf.t.co ključa. KAKÜ J= 1,11.1 I NE POTPUNI SKUP Pf^EKIDACKIH FUNKCIJA TT 5F SVI OSTALI ISKAZI MCGU FEALI3CV ATI PR£Kn l.lLl 1 !<£ SKUPA ISKAZA. SVAKO PRFTPjnVAflJE Jt ISKAZNL PA JE PREKICA" CKA INIE=.P<=ET1CI JA NAfOĆITO EUKASNA KACA SE PFETRAZIVif. JE VF. 51 PF.EGLEDAVANJEM SVAKOG SLOGA. DAJE SE ■^ADELi VRĆ3NCJST I SEKUNDARNIH KLJUČEVA PO KQJIM» S; PSETF42UJE I OOREOJUJE SE VFEDNCST ISKAZNE FUNKCIJE ÌA SVAKI SLCG. AKL JE VFEDNCSI ISKAZNE oRFKICačKE FUNKCIJE 1 ONDA JE SLOG REZ ULTAl PRETPA?IVANJA. PROBLEM ISKAZ'ICG PRETRAŽIVANJA PC VEĆEM BRL" JU SEKUN'^IPNIH KLJUČEVA U ORGANIZACIJAMA PCOAT AKA SE SPREGNUTIM SEKUNDARNIM KLJUČEVIMA JE SLOŽENIJI. CESENJE :VC/C PROBLEMA BI TREBALO UA BUDE, ZUTG CBIM.'^OSTI, PR1CME1 PCEEBNE AUALUE. U OVOM TEKSTU PAZCATF„ĆE SE SAMO PRETRAŽIVANJE SORTIRANJEM OCEMA SLGZEMM I, ILI I iNE ISKAZIMA. SVAKA VREDNCST JEDNOG SEKUNDARNGC KLJUČA JE JECNA PREKIC4ČKA rFOMENLJIVA. U OKVIRU ÙOFEDj; VANJA RECCSLEC.^ SEKUNDARNIH KLJUČEVA PO KCJIhA ĆE SE VRŠITI SCRTIRANJE RADI JEDNOSTAVNIJEG PRETRAŽIVANJA RAZLIKUJEMO DVA POSTUPKA. PRVI JE 0SL0BADJ4NJE CD SVIH KOMPLEMENATA PREMA RELACIJI J2l. 'iCUGI PjSIUPAK JE IZRAŽAVANJE FUNKCIJE PREKO PRCIZVTCS PFGMENLJlVIH, PREKO IMFLIKANA TA FUNKCIJE. CVÜ PREDSTAVLJA OSLOBADJANE OC ZAGRADA NA CSN-IVU DISTRIBUTIVfJDSTl I CPEFACIJE U CCNCSU NS !LI CPERACIJU. IMPLIKANTI NE SAORiE KOMPLEMENTE FPCMEhLJIVlH JER SU DEFINISANI, PP.EMA RELACIJI (i), TAKO DA SE ZAMENJUJU ILI ZBIROM N^KCMPLE.HENTIRmNIH PP OME NL J I VIH. ÀKC Sf U JEDNOM DRCIZVOCU PROMENLJIVIH JAVI JEDAN ISTI SEKUNDARNI KLJLČ $A OVE ILI VISE VKEDNCSTI CNOA SE TAJ POCIZVC: MTZl ISKLJUČITI IZ SKUPA PROIZVODA PROMENLJIVIh JEh NE POSTOJI SLCG KOJI MOZE IMATI DVE VREDNOSTI ISTCG SEKUNDAFNCG KLJUČA. M PROSTI IMPLIKAtUI fUNKlJE ISKAZA UE SAORZE KOMPLEMENTE opcMENLJlVIH JER JE VREDNOST FUNKCIJE j UVEK KADA JE MAKAR JEDNA OD PROMENLJIVIH JEDNAKA »iUt!. iZ MINII-IALNCG POKRIVANJA GDREDJ UJE SE bBCJ REOOSLEDA SEKUNDARNIH KLJUČEVA NA OSNOVU KHJIH ČE SE IZVR5ITI SCRTIRANJE. MINIMIZIPANJE BROJA REDOSLEDA JE JC5 JEUAN, VRLO SLOŽEN, PRU8LEM KÜJ1 SE ZBOG TOGA NEĆE RAZMATRATI U CVC TEKSTU. ZA MAH JE SLOŽENE ISKAZE PF L TK Al I VAN JA JtDNCS' TAVNO SE rORDJUJE ilRGJ REDOSLEDA PC KCJIMA ČE SE IZVR5IT1 SCPTIFANJE. U PRAKSI SU ČESČI JEDN OSTAVMJ! ISKAZI PRETRAŽIVANJA. U SKUPU PROSTIH IMPLIKANATA BIRA SE NAJVEĆI PODSKUP, CSNCVNO CDRCÜJIVANJE PODSKUPOVA, TAKAV DA SE U SViKCV PRCSTOM IMPLIKANTU NALAZI ISTI SEKUNDARNI KLJUČ BEZ LbZIRA NA VREDNOSTI. CVAJ SEKUNDARNI KLJLČ FCSTAJE FCLJE ACOl. U PODSKUPU S£ DALJE 3IR» NOVI PODSKUP NIŽEG REDA SA ISTOM OSOBINOM ALI Z1 NEKI ÜFUGI SEKUNDARNI KLJUČ KCJl POST»JE FClJč A(i). POSTUPhK SE LALJE NASTAVLJA D^K SE N? UKLJUČE SVI SEKUNDARNI KLJUČE VI U POLJE 4. SKC Sc OVA ILI V14C KLJUČA NALAZE U ISTOM BCQJU ORCSTIH IHPLIKANAIA LNDA SE DIRA KLJUČ KOJI S» fANJIM BKOJEM VkćONOSIl UČESTVUJE U IMPLIK&NT'.Mi. AKÓ JE 1 BFOJ VREDNOSTI JEDNAK ONCA SE DR': I ZV^L BIRA JEDAN KLJUČ. SCFTIRA NJEM PO SaORjAJU PÜLJA A FIZIČKI REDOSLED SLL GOVA ZAVIS! 'C ZAHTEVA PRETRAŽIVANJA. POVOLJAN FIZIČKI RECOSL'D POSLEDICA JE P^vEDPLSTA VKI SORTIRANJA. UOCJVANJr. PODSKUPOVA U SKUPU MINIMAL NIH IMPLlKSNila ZAVRŠAVA SE KADA SE SVI MINIMALNI IMPLIK.VJTI IZ .■■IIMMALNOG POKRIVANJA UVF STE U NEKI PnOSKUP. JFOAN MINIMALNI IMPLIKANT SE UVRSĆUJE U SAV: JEDAN PODSKUP JER NIJE POTREBNO DUPLITATt pretraživanje PC. TOJ KCMEINALIJI SEKUNDARNIH K.'.JLCEV. BRCJ OSr.OVMH ODREOJIVANJA POOSKUPQVA COREOJUJE BROJ' SORTIRANJA KCJE BI TREBALO IZVESTI. OPISANIM POSTUPKCK DOEIJA SE ZADOVOLJAVAJUĆI BROJ SORTIRANJA. ZA VRLO SLC2E NE ISKAZE 5RCJ REDOSLDA SEKUNDARNIH KLJUČEVA PC KOJIMA TREBA SCRTiRAII POSTAJE NEPRIHVATLJIV. NA PRIMER, NEKA 5U DATA DVA ISKAZA PRETRAŽIVANJA FUNKCIJAfA: F ='A 121, PREKO LINEARNIH LISTULISTE SA HALJM li. Tf- So LIHEAR-NL LISTE U DONOSU NA indeks MSTPICE KCJI se nalazi u POLJU KCJt SE KCO SCRTTRANJi TRETIKA KAO POLJE NAJMANJE TEDINE. OVE L1NSAR.WE LISTE SE MEMORI 5U JEDNA PCF ED DRUGE ST: je PCSLEOICA SORTIRANJA. SKUP ISTIH SLOGOVA, SVI SLOGOVI SAORIE REDOSLED ISTIH PCLJA, »»OŽE SE SMATRATI KEMORISANOM RETKO PÜSECN'JTCM SATBICCM. SADRŽAJ JEDNOG POLJA POSTAJE MATRICE OuK SU SADRŽAJI OSTA LIH POLJA INCEKSI MATRICE. KAKO SU SA0F2AJI OSTALIH POLJA U OPSTEM SLUČAJU ALFANUMERIČKI TO SE TABEL»MA S1CR7AJI ZAMENE PRIRODNIH BROJEVIMA PA SE SL^'.G'IVI HC::u SMATRAT I'PTTKG PCŠECNUTI'M MATRICAMS. TI^'E 11 ZA 5LCGCVE OATCTtKE MOGU PR-IMENJIVA'I CGlNlZACIOf.A RESENJA KEJA SE PRIME NJUJU KCO "ATRICA. INVERI';VANJ LISTA PREDSTAVLJA MEMORISANU RLT-KO POSEDNUTU matricu, SA STANGV14TA OBCANIZACÌ-JE ZA EL'^MCNT vatrice NAJPOGODNIJE JE UZIMATI PRIMARNI KLJUČ DOK SU SEKUNDARNI KLJUČEVl,PREKO TABELA,IVOEKSI ELEMENATA MATRICE. SCRTIRANJEM INVEPTOVSNE LISTE PREMA NEKOM RĆDOSLEDU SEKUNDARNIH ključeva, Pi-lHArNl KLJUČ JE U PCLJU NAJMANJE TEŽINE, I'JVEPTuVANA LISTA SE PREDSTAVLJA FOfHALNl" REDOSLECOM linearnih LISTI PREMA SEKUNDARNOM KLJUČU KOJI JE U PCLJU NAJh anje težine co polja za sekundarne ključeve. SORTIRANJE PC CRUGOK ^ELDSLEOU SEKUNDARNIH KLJUČEVA PRECSTSVLJA formiranje NOVOG FORMALNOG . REDOSLEDA LINEARNIH LISTI. DG SORTIRANJA KAO «TODE PR"=TR J2IVANJA MOŽE SE CCĆI 1 PREDSTAVLJANJEM INVERT0V4NE LISTE PREKO RÜRKALNOG fIZIC KCG REDOSL^Dl LINEARNIH LISTI. JE VRLO VELIKC. KCO DATOTEKA Si BRZIM PRETRAŽI VANJEM NE POSTCJI PROBLEM VELIČIN^ INDEKSNOG PODRUČJA. BITNC JE DA PRETRAŽIVANJE 8UCE 5TC BRŽE, DA COSCVCR EUDE U RtALNvM VREMENU. INDEKS NAGCHILAVANJA JE TAKVO UKAZIVANJE DA PC SVAKOJ VREDNOSTI SEKUNDARNOG KLJUCA POSTOJI SPISAK ADRESA (ILI PRIMARNIH KLJUČEVA« SVIH SI OGOVA KOJI SSCRŽE TU ISTU VREONCST SEKUNDARNOG KLJUCA. MOŽE PCSTCJATI 1 RAZLIČITO INDEKSIRANJE U ODNOSU NA VREONCSTI SEKUNDARNIH KLJUČEVA, PRETRAŽIVANJE U CVAKO ORGANIZOVANÜJ DATOTECI JE JEDMOSTAVIC I VRLO BRZO A SVODI SA NA fCRMlRA UJE UNIJA ILI PRESEKA SKUPOVA PREMA INDEKSIMA NAGCHILAVANJA. INDEKS NAGCHILAVANJA SE MOŽE MODIFIKCVATI U CILJU POBOLJŠANJA BRZINE PRETRAŽIVANJA. INVERT' CVANA LISTA SORTIRANA PO NEKCM REDCSLEDU SCKLIN-OAhNlH KLJUČEVA, PRIMERNI KLJUČ JE U PCLJU NAJMANJE TEIINE, PREDSTAVLJA INDEKS NAGCMILAVAMJA U ODNOSU NA SEKUNDARNI KLJUČ KCJl SE NALAZI U • POLJU NAJVEĆE TEŽINE. TO J£ JECNOSTAVAN POSTU PAK DÜßlJANJl INDEKSA NAGUKILAVAN JA. CVAKC PROŠIREN INCEKS NAGCHILAVANJA SADRŽI jC5 1 VREDNOSTI OSTALIH SEKUNDARNIH KLUCEVA PC SVAKOM SLC GU. DA BI SE CCBIC PCTPUNl SKUP INDEKSA NAGON. I LAVANJA POTREBNO JE INVEfiTOVANU LISTU SORTIRA TI VISE PUTA. BROJ SORTITANJA JEDNAK JE BROJU SEKUNDARNIH KLJUČEVA JER bi TREbALO DA SE SVAKI SEKUNDARNI KLJtC NADJE U POLJU NAJVEĆE TEŽINE. REDCSLEO SEKUNCARKilfTLJUtEVA PC PCLJIHA CIJA TEŽINA NIJE NI NAJVEĆA NI NAJMANJA MOŽE DA BUDE PROIZVOLJAN »LI MOŽE DA PREDSTAVLJA I CRGAMZA CIJU PREHA N»JCESĆIM ZAHTEVIMA PRETRAŽIVANJA. 7. ZAKLJUČAK TEKST PREDSTAVLJA INTERPRETACIJU VESEKLJUCNE ORGANIZACIJE PODATAKA SA STANOVISTA REOOSLEDA SLOGOVA KOJI JE UZET KAO OSNOVNI ELEMENT ORGANIZACIJE. ZA INT':RPRETIRANJE SORTIRANJA KAC METODE,SORTIRANJA KAO PREDPOSTAVKE PRETRAŽIVANJA, NIJE KORISĆENA NIKAKVA LITERATURA. BEZ LITERATURE JE POSMATRAN I PROBLEM FORMAL IZOVANJA ISKAZNOG PRETRAŽIVANJA. Ü TOM SMISLU OTVORENI SU I PROBLEMI CIJU SE RESENJA MOGU SMATRATI IMPLIKACIJAMA OBOG TEKSTA. OPISANI POSTUPAK GENERISAUJA PREUZETOG INDEK SA NAGOMILCVANJA SA MOGUĆIM KORISNIH PROŠIRENJEM MOŽE.SE ISKORISTITI U PROJEKTQVANJU DATOTEKA SA BRZIH PRETRAŽIVANJEM. 6. DATT.TEKE SE ERZIM PRETRAŽIVANJEM 8. literatura DATOTEKA SA BRZIM PRETKAŽI VANJEM. PREMA -(I), PREDSTAVLJAJU CRGANIZACICNA RESENJA PRETRAŽIVA NJA TAKV, C4 JE LSIJOVNI KRITERIJUM BRZINA ODGOVARA. U ORGAMZACIJI PODATAKA POVEĆANJEM INDEKSNOG PRCSTTRA SHAMJLJt SE SREDNJI BROJ PRIST UPA PO SLCGU TE S: POVEĆAVA bRZINA PRISTUPA. ZA ZAHTEVE VELIKIH- aPll'iA INDEKSNU PODRUČJE Pf.STA 1. J. WARTIN, COMPUTER DATA BASE ORGANIZATION , SECCNC EDITION, PRENTICE-HALL, ENGLEWOOO CLIFFS, NEW JERSEY 07f32. 2. H. WEDEKIND, ORGANIZACIJA PODATAKA, ZAK. IMPLIKACIONI PROBLEM ZA VIŠEZNAČNE ZAVISNOSTI I MEHANIČKO DOKAZIVANJE TEOREMA II Maleković Mirko CVVTŠ „General arm. Ivan Gošnjak", Zagreb UDK: 681.3.01:519 Specifikacija uvjeta koje mora zadovoljavali relaciona sema da bismo korektno modi-lirali neku pojavu predstavlja joian od važnih problema u teoriji projektiranja relacionih baza podataka. Od posebnog interesa du uvjeti nazvani zavisnostima. Prilikom optimalne specifikacije dolazimo do implikacionog probisma za dani skup zavisnosti. U ovom radu prezentiramo motod rješavanja impli-kacionoK problema /.:i višeznačne zavisnosti. Metod se bazira na reprezentiran.iu viiieznačue zavisnosti pomoću Skolemove standardne forme i primjeni procedura dokazivanja koju su razvijene u teoriji mehaničkog dokazivanja teorema . IMPLICATION PROELEM FOR MULTIVALUED DEPEHDÖlCIES AND MECflANICAL THEOHUI PROVINO; The Specification of the constraints that the data must satisfy to model correct y the part of the world under consideration is one of the important issuses in the design thcor;^ of the relational database schemas. Of particulsr interest are the constraints called data dependencies. In this work we present a method for solving of implication problem for multivalurjd dependencies. The method is based on representation of multivalued dependencies by ükolem's standard forms and aplication 'jf proof procedures which arc developed in mechanical tneorem prov.ing. 1. Uvod U radu L^ 1 , prezentirali smo motod rješavanja implikaciono?, problema za funkcionalne zavisnosti. Sada proširujemo navedeni metod i na viueznačae zavisnosti. Kako su višeznačne zavisnosti suptilnije prirode nego funkcionalne zavisnosti, Skolemova standardna forma višeznačne zavisnosti je općenito složenija od iste forme funkcionalne zavisnosti, dokazi teorema, tj. rješenja implikacionih problema, su znatno kompleksniji u slučaju vi-šeznačnih zavisnosti nego u slučaju samo funkcionalnih zavisnosti. Kompleksnost procedura dokazivanja za višeznačne zavisnosti očituje se ne samo u dužini dokaza već i u poteškoćama vezanim za manipuliranje skupovima atributa. Navedene poteškoće su ozbiljna prepreka u potpunoj automatizaciji rješenja implikacionop; problema za višeznačne zavisnosti. Za potpuno razumijevanje članka, prctposta _ vlja se poznavanj- teorije projektiranja relacionih baza podataka na nivou r5] i re-zolucijskih proceJura dokazivanja na nivou [IJ iii [i] . 2. Implikacioni problem za viStznačne zavisnosti U ovoj sekciji uvodiita pojam višeznačne zavisnosti i upisujemo implikacioni problem . Definicija Neka je U = { Aj^, , A^ j konačan skup atributa, li (A^^,.. , A^) rela-cione Sema, nad U , X, Y è U. Izraz oblika zovemo višeznačnii zavisnost. U navedenom slučaju kažemo da X višeznačno odrc'luje i- Definicija Neka je relacija r primjer rela-cione šeme R(A,.. . Kažeiiioda X-«-^I vrijedi (ili da je zadovoljeno) u r ako i samo AtpfX]- tjfX]At^n:]= t^[>äl= tjCxY])) Hapoicena U skladu sa uobičajenom rotacijom u teoriji baza podataka, piüemo jecJnočlan skup [k\ls.ao A, komplemeati'^ = U VX. kao X, te uniju XUy'skupov.-: X i Y atributa kao Xy . Definicija Kažemo da je relacija r model od X ako i samo ako je zadovoljeno u r. Istaknimo da se rclacija r konvencionalno predstavlja tabelom, redovi tabele su elementi (tiplovi) od r, a stupci su imenovani atributima iz relacione šeme E( A ,A2,. . ,A , Definicija Kažemo da vrijedi u relaci- onoj semi R(A^,. - .A^) ako i samo ako je svaki primjer r relacione šeme . . model od Uvedimo skup KVD(U) - f XY / X ,y žuj Definicija Neka je VSMVD(U). Za relaciju r ćemo reći da je model od V ako i samo ako je model svakog člana iz V. Sa M(V) ćemo označavati skup svih modela od V. Lako uočavamo da vri jedi fl(X--rY) S M(X-.^i) Definicija (logičke implikacije) Neka je V SMVD(U), VC MVD(U) Kažemo da V logički implicira v ako i samo ako svaki model od V jeste i model od v . Da V logički implicira v označavat ćemo sa Vt=v ili i Notaciju I upotrijebit ćemo u sekciji zbog pogodnosti. Za dane Y i v implikacioni problem je da testiramo da li Vt=v. Kako zahtjev za optimalnom specifikacijom skupa zavisnosti vodi na implikacioni problem opisano je u radu C^] • 3. Reprezentacija vižeznačue zavisnosti pomoću Skolemove standardne forme U prošloj sekciji smo rekli da X-»->X vrijedi U r ako i samo ako (t^[X] = t2[X]=i' =,3tjcr ( t^[X]= ^[X]At2^]= tjLX] A t3[Yl/\t2CXi]= tjCXXi)) . Za Z U uvodimo predikat > znači jednakpst tiplova t^^ i tg na skupu atributa Z tj. t^fz]= t2[z: . Pomoću predikata E^ , E.^ , Ejj , višeznačnu zavisnost prikazujemo u obliku l'rema tome formulu (1) interpretiramo na skupu tiplova (relaciji) r, tj.domena interpretacije D je skup tiplova r. l'r.i. Nuka je zadana relaciona Sema K(A,B,C). koja je u danom trenutku vremena predstavljena relacijom r; r A B C h =1 b^ C2 Lako provjerimo da je r model za A-^B. Također, r je model i za AB-^C. U slijedećoj sekciji ćemo pokazati da X—Da ^^ vrijedi obrat pokazuje upravo zadana relacija r; u r vrijedi B-»>C, ali ne vrijedi B—»C. Skolemizacijom formule (1) nalazim Skolemovu standardnu formu odX-»^Y. V Ej^(t2,r(t^,t2)) Isti postupak primijenjen na ~(X-»-»y) daje E^(a,b) (2) SSF(X-<^I) (3) ssr(-(x -^D) e Primjeri rješavanja implikacionog problema pomoću rezolucijskih procedura dokazivanja U ovoj sekciji ćemo na primjerima pokazati točnost nekih pravila formalnog sistema^ za funkcionalne i višeznačne zavisnosti. Dokaz točnosti pravila vodi na implikacioni problem. Ocrtajmo ukratko opći postupak dokazivanja. Neka je C'S:FD(u)U MVD(U), f £ FD(U)VD(U) i P neka treba riješiti implikacioni problem — f Negirajući f i transformirajući C/V'~f u Skolemovu standardnu formu, dobit ćemo skup rečenica S. Sada na skup S primjenjujemo odgovarajuću proceduru dokazivanja sa ciljem da izvedemo kontradikciju koja će biti označena sa □ . Ako uspijemo, dokazali smo da je S kontradik- Q toran skup rečenica, odnosno da je zaista — . f U dokazima koji slijede skup C će osim zavi- 48 snosti sadržavati i ueke uobičajene relacije na skupovima atributa. Takoiler, okup S ćemo' trebati proširiti sa aksiomima koji karakteriziraju predikat K.^. Proširenje skupa S ćemo označiti sa s'. Rješenje implikacionog problema svodi se onda na dokazivanje kontradiktornosti skupa S*. X--Y Primjer 4.1. Dokazujemo - Transformiramo X—^(X-^Y) u Skolemovu standardnu forma. Dobivamo skup S koji se sastoji od slij^'dećih rečenica: {(1) f(2) E^Ca.b) !.S Proširimo skup S šemom aksioma Sada, dokazujemo kontradiktornost skupa S= . Stablo dokaza je dano na slici 1. . (pravilo ko- Primjer 4.2. Dokazujemo -ujplementiranja) Transformacija X->-Y a (X—ITi) daje skup S: (1) Ej^(tj^,f(t^,t2)) (2) vEj^(t2,f(t^,t2)) (5) vE^(t^,f(tj^,t2)) (4) r-E^Ct^.tg)-^ Ej^Ctg.fCtj^.tg)) (5) E^Ca.b) (6) ~'Ejj.(a,tj)v ~E^(b,tj)v~Ejf^(a,t j) V j/.Ej^Cb.tj) Kako je XXl = XaY, rečenica (6) ima oblik : (6*) ^E^(a,tj)v~E^(b,tj)v~E^(a,tj) V V^E^^^Cb.tj) . Dalje, jer je t,f( b,t2) ) ekvivalentno sa rečenicu (3) transformiramo u ekvivalentnu (2) (2) E^Ca.b) E Cb.b) X E^jCb.b) (5) Ej^Cb.b) formu . (5) ^E^Ct^.tj) vE^Ct^.fCt^.tg)) Sada pokazujemo kontradiktornost skupa 3'= t(l),(2),(5).(5).('^),(5),(6)\ koji je ekvivalentan sa skupom S . Stablo dokaza sa komentarom je dano na slici 2. Primjer 4.3. doV.azujemo da vrijedi Kako je ZfeY vrijedi Y —»Z. Transformiramo XA W-^Z A Y-» Z/^" (XZ) u standardnu formu i dobivamo skup S: (1) Ej^Ct^.fCt^.tj)) (2) ,-E^(t^t2) vEj(^(t2,f(tj^,t2)) (3) - " EyCti.fCt^.tg)) (7) E^(a,b) (8) -E^Ca.b) Rezolyirano po Ej^^^ uz fCb.tg) tj Ej^(b,t2)v~E3f(a,f(b,t2))v, f (b, tj) )v ,f (b .tg) ) po uz a —»t^ b (1) po E^ u z r b -^tj^ .E^(b,a)v~E5^(a,r(b,a)) -Ex(b,a) po Ej, uz b -»t. Slijedi stablo dokaza: ' (7) E,,(a,f(a,b) E^Ca.fCa.b)) SI.3. Intervencija 1. Sada ćemo iskoristiti pretpostavku WHY =0 . Haime, WflY = = (Wr\X)UXl . Zato, (E^(b,f(a,b)) AEj-^(b,f(a,b)))«^Ey(b,f(a,b)) Ej(b,f(a,b)) E^Cb.fCa.b)) 51.5. . Intervencija 2. Iz Ej(b,f(a,b): nosti dobijemo E^Caib) . Iz E^^Cb.fCa.b)) i E^Ca.fCa.b)) po tranzitiv- (7) (2) E^(b,f(a,b)) 51.t. E^Ca.b) E^(b,f(a,b)) Prokomentirajmo navedeni dokaz-Stablo dokaza je dano na slikama 3., i 6.. ^idimo da je stablo dokaza prekinuto intervencijama 1. i 2. . I dok je intervencija 2., (tranzitivno-st od Eg) mogla biti aksiomatizirana i dodana skupu S , intervencija 1. je problematično mjesto sa stanovišta potpune automatizacije procedure dokazivanja. Da intervencije mogu biti još kompleksuije pokazuje slijedeći primjer. 60 Primjer 'v. Dokazujemo X , Iskazani teorem predstavlja pravilo unije. Skolemizacijom XY a X---»Z a-(XYZ) , nalazimo skup S: (1) ^E^Ct^.tg) vE^Ctj^.fCt^.tj)) (2) ^E^CCj^.tg) vE^(t2,f(tj^,t2).) (3) ^E^Ct^.tg) v^Ct^.rCtj^.tg)) (5) (6) -E^(t^,t2)V E^(t2,g(t^,t2)) (7) vE2(t^,6(ti,t2)) (8) 'v'^Ctj^.tg) vEj2(t2,g(t^,t2)) (9) E^(a,b) •»KX-^YZ) (10) u rečenici (10) iskorištena je ekvivalencija • koja ustvari predstavlja razbijanje unije XZ na pojedinačne skupove Y,Z. Pravilo razbijanja treba respektirati prilikom formiranja skupa S. Intervencija 1. Želimo doći do tipla w za koji je (11) ej^(a,w) asy(a,w) ae2(a,w) ae^(b,w) , što je u kontradikciji sa (10). Početak stabla dokaza dan je na slici 7. Intervencija 2. Pokazujemo da je traženi tipi w=g(a,r(a,b)) tj, da vrijedi; (u) E^(a,g(a,r(a,b))) (b) Ej^(b,g(a,f(a,b))) (c) E^(a,g(a,f(a,b))) (d) E^^^'S^S'^^a.b))) (e) E3^(b,g(a,f(a,b))) (a) i (d) su rezolvente (12), odnosno (l'^). (b) slijedi iz (9) i (a) zbog simetričnosti i tranzitivnosti predikata E^^. Ostaje pokazati (c) i (e). Dokazujemo (c): Trebauio dokazati E^(a,g(a,f(a,b))). Vrijedi Ey(a,f(a,b)) AEj^(f(a,b),g(a,f(a,b))) =f Ex^Y(a,B(a,r(a,b))). Prema tome, dobili smo rečenicu (16) E^^^(a,g(a,f(a,b))). Kažemo da je (16) dobiveno po tranzitivnosti za presjek. Pokažimo još da je (17) ^x(a,6(a,r(a,b))), odnosno da je Ej^(a,g(a,f(a,b))) V AcX\X. Dokaz je kao što slijedi: A«Y \ X =»AtYA AiX a(Aa programska orodja. brez katerih si ne moremo več predstavljali razvoja sodobnih. računalniško podprtih informacijskih sistemov. Razen tega pa smo v zadnjici letih priča tudi naglemu razvoju drugih programskih pripomočkov < jeziki za p ovpr^aševan je. generator ji poročil. programski generatorji itd.). ki v tesni povezavi s sistc^mi za upravljanje podatkovnih baz bistveno poenostavljajo postopek prosramiranja, s tem pa tudi povečujejo produktivnost pri razvoju novih aplikacij. Sledeč tem tendencam v razvoju uporabniške sistemske programske» opreme je DO Iskra Delta razvila več programskih pripomočkov, ki so znani rod skutmim imenom IDA < Iskra Delta Arhitektui^a ), Osrednjo vlogo med njimi igra prav gotovo sistem za upravljanje podatkovnih baz IIiA-Baza. predmet naše ocene pa sta še IDA-Cogen.ravIjanje podatkovnih baz Ultra ameriške firme Cincom Systems, U tem članku oceno programs primerjavo s predstavlja po analize obeh si Iskra Delta opr opremo na Fa Ljubljani. Pod lize so zbrani Ocena prugramsk lelimo Podati kratek opis in kih orodij IDA ter njihovo sistemom Ultra. tlanek vzetek rezultatov obširnejše stemov. ki jo je za potrebe DO avil Laboratorij za programsko kul.teti za elektrotehniko v robni rezultati omer>jene ana-V posebni študiji z naslovom ih orodij IDA. Poudariti želimo. da je bila analiza (na predlog naročnika > izvršena zgolj na podlasi podatkov, ki so dostopni v priročnikih, nismo pa imeli moinosti. da bi oba sistema preizkusili v praksi. Zato tudi ne podajamo ocen o performansah. temveč ocenjujemo predvsem funkcionalne karakteristike. 2. OPREDELITEV KARAKTERISTIK, PO KATERIH OCENJUJEMO SISTEME ZA UPRAVLJANJE PODATKOVNIH BAZ Da bi lahko izvršili oceno programskih orodij IDA in njihovo primerjavo z Ultro. smo najprej definirali karakteristike, po katerih bomo ocenjevali oba sistema za upravljanje podatkovnih baz. Razdelili smo jih na 4 skupinc-j; A. Logični nivo - konceptualni podatkovni model in njegova sposobnost modelirati stvarnost - z mod6>lom podprte integritetne omejitve - uporabniški modeli in njihova sposobnost modeliranja uporabniških Pogledov na st va TM'i ost - fleksibilnost povezave med konceptualnim modelom in uporabniškimi modeli - loaična podatkovna neodvisnost B. Interni nivo - struktura datotek in pristopne metode - fizična podatkovna neodvisnost - sočasnost dostopa do podatkov - zaščitni mehanizmi za dostop do podatkov in za obnovo podatkov po nesrečah - žurnal in njegova uporabnost - kontrolirana redundantnost Cr Pripomočki 7a upravljanje podatkovne baze - generiranje in spreminjanje konceptualne sheme - generiranje in spreminjanje internih shem. - usla&evanje podatkovne baze 2 ozirom na povprečn'i pristopni čas ~ misracija podatkov - nadzor nad delovanjem sistema za upravljanje Podatkovnih baz D» F'ripomoćki za uporabljanje podatkovne baze s strani končnega uporabnika - jeziki za povpraševanje - vmesniki na visok onivojske 3osteče jezi ke - generiranje zunanjih shem v uporabniških programih - generiranje zaslonskih slik 3. OCENA PROGRAMSKIH OROniJ IDA 3,1 Logični nivo ceptualni shemi. V okviru vsakega tipa zapisa je možno navesti samo tipe podatkovnih elementov, ki uporabnika zanimajo', ostale pa izpustiti. Za vsak tip zapisa pa lahko nave^ demo tipe setov. ki jih uporabnik teli uporabljati za dostop do zapisov. Za uporabniSki pogled velja» da mora biti zasnovan na istem podatkovnem modelu kot konceptualna shema» tako da uporabnik nima možnosti izbire podatkovnega modela. ki bi morda bolj ustrezal njegovi aplikaciji. Prav tako je uporabnik vezan na uporabo imen tiPov zapisov in imen tiPov podatkovnih elementov, kot so definirana v konceptualni shemi. Logična podatkovna neodvisnost je v pretežni meri pogojena z mreinim podatkovnim modelom, na katerem je osnovana konceptualna shema, S tega staliSča je najvišja. ki jo je možno doseči. Uporabni&ke sheme in s tem uporabniške programe je treba spremeniti le v primerih, če spremembe v konceptualni shemi zadevajo tipe zapisov in tipe setov, ki jih uporabniški program uporablja. Sistem za upravljanje podatkovne baze IDA-Baza sloni v logičnem Pogledu na mrežnem podatkovnem modelu, ki pripada površinskemu tiPu podatkovnih modelov in temelji na konceptih - tip p odatk üvr^ega elementa < Bata Item Type) - tip zapisa C Record Tijpe ) - tip seta (Set Type) kar je v skladu s specifikacijami mr'ežnega podatkovnega modela, kot ga je specificiral CODASYL, z izjemami: - v setu lafiko nastopa le en tiP zapisa, kot član; - vsi tipi zapisov, obvezno vsebovati seta; ki so člani seta, morajo Primarni ključ lastnika - na uporabniškem nivoju se lahko pojavlja določeni zapis kot član .le v enem setu, . če naj nastopa kot član v dveh ali več setih, ga je Potrebno večkratno definirati, 2 opisanim mrežnim podatkovnim modelom lahko predstavimo tipe močnih entitet in njihove povezave s tiPl šibkih entitet s pomočjo tiPov zapisov, v katerih je ime tipa zapisa običajno ime tipa močne c^ntitete. Povezave med tiPi močnih entitet pa so predstavljene s tiPi setov, pri čemer ime povezave postane ime tipa seta. Model podpira omejitev! dve vrsti integritetnih - iz definicije ključa v tipu zapisa sledi funkcionalna odvisnost šibkih entitet od močne entitete, v katere zapisu nastopajo; , - iz definicije seta sledi intesritetna omejitev, da vsaki močni entiteti. ki je predstavijeria z zapisom — članom, pripada natanko ena močna entiteta. ki je predstavljena z zapisom - lastnikom. Podshema, s katero Je opisan uporabniški posled. je podmnoiica globalnega logičnega opisa podatkov oziroma konceptualne sheme. Sestavlja jo lista zapisov, ki jih uporabnik namerava uporabljati in so definirani v kon- 3.2 Interni nivo Fizično podatkovno bazo sestavljajo datoteke, imenovane vsebovalniki (containers). ki so pod kontrolo operacijskega sistema in lahko vsebujejo eno ali več logičnih datotek v celoti ali pa delno. Vsebovalnik je razdeljen na logične bloke. Logični blok lahko vsebuje le zapise istega tipa. obsesa pa lahko enega ali več fizičnih blokov - sektorjev na disku. Usak zapis zaseda v logičnem bloku svojo celico (celi ). ki je adresabilna. Seti so fizično predstavljeni s pomočjo kazalcev 'naprej' in 'nazaj*. ki omogočajo dostop do naslednjega oziroma predhodnega zapisa v setu. Žal ne obstajajo tudi kazalci na lastnike setov. Prehod s člana seta na lastnika lahko izvedemo le s pomočjo ključa seta, ki je istočasno tudi ključ zapisa lastnika. Spremembe v fizični organizaciji podatkovne baze,. . ki niso posojene s spremembami v konceptualnem podatkovnem modelu. se lahko nanašajo na povečanje obsega posameznih datotek. prerazporejanje vhodno izhodnih vmesnikov. razmeščanje vsebovalnikov na različne diskovne enote in spreminjanje velikosti logičnih blokov. Naštete spremembe ne vplivajo na logično strukturo podatkovne baze in uporabniške programe. zato lahko ocenimo fizično podatkovno neodvisnost relativno visoko.- ^^ sistemu IDA-Baza lahko sočasno deluje nad Podatkovno bazo do 52 oz. do 99 uporabniških programov. Konsistentnost podatkovne baze se ščiti z zaklepanjem podatkov. •Najmanjši del Podatkov. ki se ga da zakleniti za ekskluzivno rabo. je zapis. Uporabnik lahko zaklene tudi več zapisov zapored. kar mu omogoča izvesti večfazno ažuriranje brez nevarnosti za konsistentnost podatkovne baze. F'ri večfaznem ažuriranje predvideva sistem vključevanje sprememb v podatkovno bazo za vse faze ažuriranja skupaj ali pa njihovo zanemarjanje z ukazoma Pomni (COMMIT) in Pozabi (CANCEL). Problem mrtve zarike (dead lock) je reèen s časovno omejitvijo zaklenitve zapisa. ori čemer je čas zaklenitve določljiv s strani upravitelja podatkovne baze> za uPorabniSke orograme. vpletene v mrtvo zanko. pa sistem za upravljanje podatkovnih baz izda ukaz Pozabi. ZaSčitne mehanizme za dostop lahko razdelimo na dva dela: do podatkov Prvi del se nanaža na pristopne kontrole. ki temelje na seslih, in pravice do spreminjanja podatkov (samo branje ali tudi dodajanje, brisanje in modifikacija zapisov). Dodeljevanje teh pravic je v pristojnosti upravitelja podatkovne baze. Drusi del zaščite se nanaša na restavriranje podatkovne baze v situacijah. ko le-ta zaide v nekonsistentno stanje. lUA-Baza uporablja v ta namen dve vrsti beletenja aktivnosti nad podatkovno bazo s pomočjo dnevnikov (los file). Eieleienje vrednosti zaoisov pred ažuriranjem predstavlja zažčito pred napakami v podatkih ali programski opremi in omogoča, da se postopek večfaznesa ažuriranja v primeru napake v uporabnižkem programu ali kot posledica mrtve zanke v celoti anulira. Beleženje vseh aiuriranj pa omogoča. da na osnovi kopije podatkovne baze izvrtimo restavriranje podatkovne baze v primeru fizičnega uničenja podatkov. Prvi tip dnevnika (za razveljavljanje sprememb v podatkovni bazi ) uporablja sistem za upravljanje» podatkovnih baz avtomatično, drugi tip dnevnika (za obnovo podatkovne baze na osnovi kopije) Pa uporablja restavracijski program. ki ga sproži upravitelj podatkovne baze. Sistem IDA-Eiaza ne podpira namerno uvedene redundantnosti podatkov v smislu avtomatskega ažuriranja vseh obstoječih kopij istega podatka. 3.3 F'r ipomočki ba ze za upravljanje podatkovne - s orerazporejanjem vsebovalnikov po različnih diskovnih enotah. Žal pa upravitelj podatkovne baze nima na voljo trdnih iihodiSč la optimizacijo niti možnosti dovolj natanko preveriti uspeènost izvedenih modifikacij, ker ne raipolasa s podatki o pristopnih časih do podatkov za posamezne aplikacijske programe. Kot poseben primer uglaževanja podatkovne baze navajamo tudi migracijo podatkov, vendar v okviru IDA-Baze te možnosti nimamo na razpolago. Za izvajanje nadzora nad delovanjem sistema je upravitelju podatkovne baze na voljo poseben kontrolni program^ ki omogoča določevanje načina vodenja dnevnikov med delovanjem sistema. ustavitev sistema in pregled nad delujočimi aplikacijskimi programi. njihovimi statusi, načinom uporabe podatkov in zahtevki po podatkih, ki čakajo na servisiranje. 3.4 Pripomočki za uporabljanje podatkovne baze s strani končnega uporabnika Med pripomočki za uporabljanje podatkovne baze s strani končnega uporabnika zaenkrat najbolj Rosreèamo jezik za povpra&evanje. ki pa je v zaključni fazi razvoja, Vmesnik na visokonivojske gosteče jezike je realiziran kot zbirka klicev podprogramov, ki so sestavni del sistema za upravljanje podatkovnih baz. tako da o pravem jeziku za manipulacijo podatkov. ki bi bil vgrajen v gosteči jezik. ne moremo govoriti. Glavne pomanjkljivosti take realizacije "jezika" sos - obsežen opis podatkovnih struktur in raznih konstant. ki nastopajo kot parametri v klicih podprogramov» - kompliciran in s prosramerskesa staliSCa redundantno opisan klic podprogramov! razmeroma zapleteno in aplikacijskih programov. zamudno Pisanje Postopek generiran ceptualne sheme Komunikacija med s realizirana prek u 1 nje sheme in določi zapisov in za defin ja tudi kontrolo na jami in preverja n je za upravitelja ročrio orodje. ja in spreminjanja kon-poteka interaktivno, istemom in uporabnikom je očenih menujev za imenova-tev sesia. za definiranje iranje setov. Sistem izva-d posameznimi specifikaci-jihovo konsistentnost ter podatkovne baze zelo pri- Podobno velja tudi za postopek generiranja in spreminjanj» interne sheme. ki pa Je omejen predvsem na definiranje vsebovalnikov in vhodno izhodnih vmesnikov. S sredstvi. ki so mu na voljo v okviru modifikacij interne sheme, ima upravitelj podatkovne baze možnost optimizirati delovanje sistema IDA-Baza na naslednje načine! - z različnimi načini prirejanja posameznim tiPom zapisov; vmesnikov z določanjem étevila kopij Posameznih vhodno izhodnih vmesnikov; Te pomanjkljivosti do neke mere odpravlja programski pripomoček IDA-Cosen. ki skrbi tako za avtomatsko vključevanje zunanjih shem v uporabniške programe kot za generiranje skeleta programov. vendar je njesova uporabnost omejena le na cobolske programe. 2 njegovo pomočjo lahko kreiramo praktično celoten aplikacijski program za ažuriranje ali vnašanje zapisov določenega tipa v podatkovno bazo. Tako generiran program je pripravljen za interaktivno delo preko zaslonskega terminala in obsega tudi rutine za prikazovanje vsebine zapisov oziroma za njihovo zajemanje s pomočjo zaslonskih slik. Naslednji programski pripomoček iz družine IDA. ki olajSa Pisanje programov. je IDA-Ekran. Namenjen je za avtomatsko generiranje zaslonskih slik in obsega: - urejevalnik CEH. ki je namenjen kreiranju in modificiranju zaslonskih slik; - podprogram CRT. ki skrbi za komunikacijo med zaslonskimi slikami in uporabniškimi programi, s prirejanjem optimalne dolžine logičnih blokov slede na dolžino zapisov in pristopne metode; IDA-Ekran je zasnovan za uporabo iz programov. ki so napisani v visokonivojskem sostečem Jeziku, slike, ki jih oodpira. pa so alfanumeridne. Podatke, ki jih v zveii z opisom slike sene-rina itiA-Ekran, uporablja modul IDA-Cogen pri seneriranju ustreznih prosramov, predvidena oa je tudi vključitev te?h podatkov v podatkovni katalos, kar pomeni, da postane slika potem dostopna vsem uporabnikom Podatkovne baze. . Zar-adi aktualnosti zaslonskih slik in priro-ćnoati njihovesa generiranja lahko ocenimo prosramski pripopmoček IDA-Ekran kot zelo koristen dodatek k sistemu za upravljanje podatkovnih baz. PRIMERJAVA Z OZADJEM ULTRA Primerjava sistemov. za upravljanje podatkovnih baz IDA-Paza in Ultra pokaie, da sta si oba sistema po svoji zasnovi v veliki meri sorodna. Ta sorodnost je Posledica skupnih izhodišč., saj tako IDA-Baza kot Ultra v svojem bistvu izhajata iz sistema za upravljanje podatkovnih baz Total. Razlike med obema sistemoma pa so posledica različnih poti, ki so Jih njuni razvijalci ubrali z namenom, da odpravijo nekatere pomanjkljivosti Totala. ostali ukazi Jezika za manipulacijo s podatki) so realizirani kot samostojni stavki v okviru aostečesa programskega Jezika (velJa za COEIOL. in FORTRAN), poseben predprocesor pa jih nadomesti s klici ustreznili rutin sistema za upravljanje podatkovne baze. Ugotovimo lahko torej, da Je bil pri razvoju Ultre velik poudarek namenjen enostavnejši uporabi sistema, Rrilasadaniu uporabniku in večanju produktivnosti pri programiranju. Seveda tudi pri razvoju programskih pripomočkov iz druiine IDA ta področja niso bila zanemarjena, saJ je bilo ob osnovnem' modulu IDA-Saza razvitih èe več orodij, katerih namen Je povečati produktivnost pri Prosramiran ju. Tako IDA-Cosen (generator cobolskih programov ) v preceJénJi meri odpravlja pomanjkljivosti zaradi neustrezne realizacije Jezika za manipulacijo podatkov pri IDA-E relacionom šemom. Postupak transformacije relacione šeme R u šemu baze podataka 5> jeste dekompozicija relacione šeme R . Da bismo opisali ugrađene višeznačne zavisnosti, trebamo karakterizirati projekciju relacije. Definicija Neka je SCR neprazan skup, (R,r) relacija. Projekcija od (R,r) na S, u oznaci TTg(r), je relacija (S.Tj^), gdje je rj^ = (sc Tipl(S)|^t c r: t[sV-Si. Ovdje je tfSj restrikcija tipla t na skup atributa S Slijedeći uobičajenu notaciju u teoriji baza podatake, jelDočlan skvp pišeno kao A , uniju skupova atributa XUY kao XY, a komplement skupa X u odnosu na skup R , R\X, kao X. Sada definiramo pojam ugrađene višeznačne zavisnosti, te pojam podskup-zavisnosti. Definicija Neka su X,Y,ZgR, Xn mZ'^ Izraz X-«YlZ zovemo ugrađena višeznačna zavisnost. Definicija Kažemo da X-»-»y\Z vrijedi u relaciji (R,r) ako i samo ako X-»-»Y vrijedi Uočimo, da ako vrijedi u r da onda i X-«Y|Z vrijedi u r . Obrnuto nije istina, pa moramo biti oprezni u iskazivanju uvjeta za r , a da ne ignoriramo ugrađene višeznačne zàvisnosti. Definicija Neka su X,Y,Z&R. Izraz Z(X)ĆZ(Y) zovemo podskup-zavisnost. Definicija Kažemo da Z(X)1U sub "t: Napor, ki ga je vse obseSnejsi h 1 j 1 v i h r atr.unal n javi s programi javi Jajo dodat van.iem za nia^ «i vir ov. Na i v eit j mogoile doseči z ii a s J a pri i z v a j bi v takižnih pr oiriogotal dovol j preqled riad soif vanega procesa potrebno vlagati pri načrtovanju tni kroprogramov sodobnih, zmog-ikov, vse bolj narašča. V primer-ranjem na nivoju zbirnika se pone težave, ki rastejo s prizade-ifitalno 1 z kor i Äit enost vseh moifnih o učinkovitost v tem pogledu je uvajanjem čfim popolnejšega soar» ju mikrooperacij. Programer naj imerih uporabljal jezik, ki bi mu učinkovito opisovanje in dober asnim izvajanjem operacij natrto- Obstajala fjodobnosti na podroifju i nterpr eter jev in paralelnih računalnikov: oba področJja se u-kvar.iata niaks i ma 1 n i m i z kor i Üifan jem' večkratnih virov. iato ie ^e posebej pomembno slediti raz-1 «ikav«=il li i Hi do&e2kc;rti na podrotf ju superraHunal ni-kov, sai su la* ti na itie^ife uporabljivi tudi pri nalfrtovaoiu m i h r opr ogr amov in njih pr i pada io2f i h i nterpreter jih. 2. DF HlKRÜPRüGRAniRANJE Nov princip krmil ierìja s tokom podatkov /2/ je mogoči e prilagodi ti tako, da je primeren tudi za .ni kroprograirii ran IG. V primerjavi s konvencionalnim i 2 vr^e van it?ir» praqrama obstaja bistvena razlika v metodi kontr-'oie. Programi , ki so krmi 1 je-ni s to^iotii podatkov, noajo asinhrono kontrolo, kar ponitj-ni, d^» je pogojc-nast izvajanja operacije Slika 1. Program krmiljenja s tokom podatkov, ki izratfuna izraz a = 2b~b/c Na sliki 1 je prikazan taksen princip kontrole na asemblerskem nivoju. Glede na pravilo, da se priifne operacija izvajati takoj, ko so na vhodu prisotni vsi podatki velja, da se operacija COPY izvr^Éi s pr-i sotnost jo vrednosti b na vhodu operatorja. Ta vrednost se prenese pr-eko vhodne poti na procesor, ki izvrìéi operacijo COPY. Kot rezultat se pojavita na izhodu operatorja dve enaki vrednosti, ki izpolnjujeta pogoj, potreben za priifetek. sočasnega izvajanja operacij MUL in t>lV. Qba paralelna tokova sta (po istem pravilu) sinhronizirana na vhodu operatorja SUB. Ta namreč ^aka na izvajanje operacije toliko ^asa, dokler (\ista dosegljiva oba podatka: iz operatorja MUL in iz operatorja DIV. Programi, ki so krmiljeni s tokom podatkov, ka-iiejo le odvisnost med podatki. Tako je v na-!éem primeru operacija SUÜ odvisna le od rezultatov operacije. MUL in DIV. Kontrola operaci j ni oddvojena od podatkov. Ti se ne shranjujejo na neke dolotlene lokacije, ampak le zatlasno v pom-nilniöke vmesnike med operatorji.. Pri novem na-ifinu se ne doloC'a mehanizma krmilnega toka, niti ne? shranjevanje podatkov in stanj pomnilnika. Konkurentni programski tok je izraifen in krmi 1-ieri izkliuifno s podatkovnim pre,tokovni m" programskim gradom (data flow program graph). 62 Üb'ütdja if ti v&tf lezikov z^ opisovanje pudat kavno pr t^to^: o. n I h pi-oar ime ti dve vrednosti in iu vstavi v dve Šabloni operatorjev MUL in DIV, ki sta s tem pripravi jena na izvajanje vsak svoie instrukciie. Adresi obeh instrukci j sta poslani v vrsto a-dros instrukcij. Vsaki je dodeljen svoj procesor , ki priCneta instrukciji izvajati skoraj istočasno. cüi'v ....."..-riT HUI. 5ub ---i DIU " >-1> ------ Slika 3. Vsebina pomnllnl^:a pri kodu a = 2b-b/c roc n F uin DOL' I_____ u1 i Legenda : PÜE. , . pctmr. i i n 1 äka ür»ota s celicami Nl,...,l*1m Dot. . . doivtiAvna enot^ (Fatch Unit) PRF . . . |'«r ac C;'sn-5i oiìot^» s pr'ocesor ji Pl , . . , ,F'p UDI::.. . . od I =iqa 1 er^ota (Up-date Unit) Vlrt... vrsta i rtstrukci iskih adres VM ... vrst a i z vrSl ii vih instrukci j VPÜ . . . vt st podatkovnih znakov (data token) SI 1 k.3 -J. Pa^.et,ni k amun i kac i i sk i računalnik Instrukcije lahko izvaja veC procesoriev hkrati. Procesorji so lahko enaki, vsak od niih pa mora v takISnem primeru izvajati vse potrt-ufie niikro-operaci le. Lahko pa obstajajo tudi grupe enakih procesorjev, od katerih je vsak procesor iste grupe sposoben izvajati le mikrooperacijo, ki je karakter istiCna za grupo. Torej izvaja vsak procesor- iste grupe le eno vrsto mikrooperaci ie. tip mikrokodnega i nterpreter ja bo DF mi-krokoda z veüjo ali manjüo stopnjo paralelizma izv<;iial 'popolf>oma'' asinhrono. H.adar sg med procesi ran jem pojavi istoiiasno veü poti, bo interpreter avtomatično izbral takBno Hteviio procesoriev, da bo izvajanje mikroprrj-qr-ama kar n^^jbol j ufiinkovito. Zaradi asinhronega izvaianja tepa interpreter ja bo avtomatidno tudi cevi jen je mikrooperaci j» Ce je povzročeno z erio mak r ooper ac i jo ali, de je povzročeno & sek-venco veCih identi^fnih (vektorskih) makr-oopera-cii. Programer ie s tem re«en napora, ki ga sicer mora vlomiti za ugotavljanje on i-Jf.'uniuf ifi civti-ija tip?>.. Uv-jotovi so uasltìdr» it» bistver*«* raziike; - » apđci Let.i« poji.niiffika le vetija, ker se pamnil-rii-Skü- c^ljct? < . enuUi POE) med isva.ianiein proti r nu- upufcjbl iaio za vet^kratno shranjevan- ie. Proqramerju \\i potrebno posebe.i skrbeti za optimalno i s kor iStfan je virov. Ti se namreC dolo-Caio in optimaifio iskoriftćfajo povsem avtomati- Za proqramerja «so pomembne ie podatkovne od-vi«,nosti , m«.i?dtein ko je zanj eksplicitni potek; kontrole programa nepomemben. Programerju ni potrebno upoštevati programska stanja, niti upravljati s pomnilnikom. •• '^ii&te-mu cJodar.a posebna odlagalna enota DOE lUp-date Unit.', ki skupaj z obit^ajnim pomni 1-niäkjn. iidresirànjein ugotavl ja veljavnost ins-trukCi.i i ri liti uvräCü v vr^to. - i^iinj ifv :;nAf?iJno dodfl ievane procesorjev, ki se riiridiia.ia procesni enoti PRE. Za dodeljevanje s.kr bi pose'bna «lad»*! .levalna enota DOE (Fetch Unit». l3lc.-de tia z:goraj opisarie lastnosti je dovolj očigledno, da je obravnavana arhitektura za inter-pretcici jo mi krokode ugodna povsod tam» kjer ie ob prisotnosti moSnega paralelizma v obseSnejSih mi kroprogranii h pomembna velika uCii nkovi tost i?-va.tü«\ja mi kroprogr amov in s tem kar na ibol jsi i r karistek str oja. Ue upo£ti:-vdntic» üeiÄ^ivo, da it cena teh dodatriih funk:ci ì'àl'.ih eiioL u<'-)r"acdel ii:?«»«« na vse procesorjts, katerih =.l.t:.rilc» le r.ic.'?r vtvliko, tio pa dobro iz--koriatft'iiv . lo- ijF \ Il 1. er ur «ter relativno centsn. I C kor i II-"j, L pr" {:;C-ef.or lov ič doka .I razi iCna^ Oa pi- rào {io-. ■l^'ì'-m: 1 . fff n.:^ i nterpreter ju veči (lu 1; r opr o.j,- s-jiiio-v hkrati. HiüUnost obstaja. Ce se mi kr opr oqr^mov -pomeSanih med sebo i- soCasrto .iüqotovi i e tf?qa pa ne zahteva od proqra.ii«r dociatneqa napora. 4. LITERATURA /i/ Ptvr.niii, j. b. , "Data -flow supercomputer s", IEEE Computer, vol. 13, no. 11. pp. 44-üö, Nov. 19B0 /2/ Acker .nan, W. B. , "l>ata F-iow Language", IEEE- UompuLer, vol. 15, no. 2, Feb. 19Ö2 /3/ "frattnig; W, , Kerner , H. , "EDDA, a very, high level programmino and speci-f i cat i on language in the style of SADT", lEEE-CSt Proc. oi the 4th Int. Computer Software St Applications Loni., pp. 436-443, Oct. 19Ö0 Giede na aornie ugotovitve je moqoile zakl ju-Citi, d«« kaže mi kraproqramski interpreter za DF jtruike s proqraoier skfc^qa vidika naslednie lastnosti : 1. O Prologu □ JAPONSKEM PROJEKTU RAČUNALNIKOV NOVE GENERACIJE Ljubo Jur ak Projekt razvoja r aćunal ni I-ov nove generacije se je prićel na Japonskem leta 1979. Na predlog ministerstva za mednarodno trgovino in industrijo (MITI) v Tokiu je "Japan Information Procesing Development Center" osnoval komite za ètudij in raziskave računalnikov nove generaci je. Na osnovi dvoletnih raziskav je MITI pripravilo nacionalni projekt za razvoj računalnikov nove ("Pete generacije računalniških in ga 14. aprila 1982 uradno generaci je si stemov") objavi lo. Desetletni projekt je razdeljen na tri faze. V prvi fazi je predviden razvoj prototipnega osebnega računalnika za programi ranje v jeziku, podobnem Prologu. .Prolog je programirni jezik, posebej primeren za opis postopkov pri umetni inteligenci : učenju, logičnem sklepanju itd. Tak računalnik naj bi po hitrosti sklepanja nekajkrat presegel sposobnosti najboljéih danaènjih sistemov, ki razumejo Prolog. Po obsegu znanja pa bodo na ravni danaènjih ekspertnih sistemov. Ta faza naj bi trajala 3 leta. V drugi fazi trajajoči 4 leta, se bodo raziskave usmerile k večjim problemom : nadaljnemu razvoju prototipnih računalnikov in povezave mnoiice računalnikov v sočasno in vzporedno delujoč sistem. V tem delu je predvideno tudi naaaljevanje vseh spremljajočih raziskav iz prve faze, z uporabo programske opreme, razvite v prvem delu. V zadnji fazi bodo vso razvito opremo programsko in aparaturno povezali v enoten sistem. Končni cilj je stroj za logično sklepanje, ki bo nekaj 11sočkrat hitrejèi od današnjih. Uporabiti ga bo mogoče v zelo različne namene. Časovni plan 81-84 začetna faza 85 - 88 osrednja faza 89 - 91 zaključna faza Razvoj osnovne računalniške tehnologije in planiranje Raz voj podsi stemov Razvoj celotnega sistema Zato, da bi dosegli te cilje, naj bi po japonskem načrtu arhitekture nove generacije računalnikov, učinkovito podpirale logični sklep kot osnovni korak in vzporedno procesiranje. Na tem temeljijo ostale osnovne funkcije v sistemih nove generacije, to so baze znanja, mehanizmi sklepanja in relacijske baze podatkov. Japonci menijo, da je od sedanjih programirnih jezikov za te namene Prolog najpr1mernejéi. Osnovni del Prologa je zato izbran za strojni jezik nove generacije računalni kov. Prva implementacija Prologa je bila narejena leta 1972 na univerzi v Marseillu. Prvi implementaciji so sledile nove. Največji napredek je pokazala implementacija Prologa na računalniku DEC-10, ki vključuje poleg Interpreterja èe prevajalnik. DEC-10 Prolog je tako postal nekakšen neuradni standard za Prolog, V osemdesetih letih so se vrstile nadaljne implementacije. Najpomembnejša je Quintus Prolog, ki je izboljšana verzija DEC-10 Prologa. Prolog je bil izbran kot osnova za strojni jezik računalnikov nove generacije. Prolog je enostaven in učinkovit programirni jezik, osnovan na simbolični logiki. Služi za logično programiranje. Podobno kot LISP je Prolog interaktiven jezik, v osnovi razvit za simbolično procesiranje podatkov. V splošnem je program v Prologu zbirka procedur, vsaka procedura pa je sestavljena iz klavzul. Prolog lahko opazujemo iz dveh aspektov. Proceduralni ali operativni je bolj konvencionalen način in opisuje zaporedje stanj med izvajanjem. Deklarativni, kjer program opazujemo kot zaporedje stavkov, ki opisujejo problem. V splošnem so v Prologu vsi objekti imenovani termi. Neformalno si lahko predstavljamo terme kot okrajšave naravnega jez i ka. Deklarativen aspekt Prologa omogoča učinkovito, jasno in hitro programiranje. Program lahko razbijemo v majhne, neodvisne enote. V Prologu programiramo tako , da : — deklariramo dejstva o objektih in odnose med njimi — definiramo pravila o objektih in odnose med njimi — sprašujemo o objektih in odnosih med njimi Tipična področja za programi ranje v Prologu so simbolično procesiranje , obravnavanje objektov in relacij med njimi. 2. Prva faza japonskega projekta razvoja računalnikov nove generacije Osnovni koncept projekta je rekonstruirati aparaturno in programsko opremo računalnikov na osnovi logičnega sistema, imenovanega predikatna logika, Z drugimi besedami: računalnik naslednje generacije naj bi bil stroj za predikatno logiko. Lahko bi ga imenovali stroj za logično sklepanje, ker je logični sklep osnovna operacija predi katne logike. Današnji računalniki uporabljajo strojni jezik. Strojni jezik določa arhitekturo računalnika. Programska oprema je zgrajena na osnovi strojnega jezika. Značilnosti von Neumanovega tipa strojev so strojnim jezikom. intenzivno predstavi jene s konceptu nove generacije računalnikov je ekvivalent strojnem-., jeziku, -l.ernel i anguage" ' Ki, ) . J-i. je osi"iovan hö predlt.^tni logiki iri f:» -i'O 5!: ^ i j š nov -itrajni je^ik. Nov strojni je;iii novo apAfaturno in programsko opremo. Apar atarna oprema se v osnovi pro jt?l t ■ r ■■ Id, vrpor.sdno procesiranje ali ct soc i ij 11 ■.■ric O^riovna operacija bo logiir.i si. 1 ep. Dariair. J1 tipi von Neuraanovih arhitektur so gr^jjeni :: sekvenćno procesiranje in iskanje po nčj^sl ovi t"). Torej bo vzporedni raćonilnik ; äscc i at i vni'm sklepanjem neka vrsta ne-vort NeüiTianove arhitekture. Froyr opr eina -se gradi s komb i n i r an j eni ovnovnih -funkcij epc-ri ja » ki jih bo izvajal iiparaturni -Jel . 'r-'er-nel language" KL sodi kot neprocedur al ni jei^il med visokio razvite pr-jgra'T.sv e jt=.;il;t-. fJa ■:)snovi KL se razvijajo upor abn i usiiter jent piogramirni jeziki. Ti jeziiv:i boaa omocjo-^ali procesiranje baz znanj in r àzuiiie'v an je naravni ri jez i r'.Ov . Zgr-aoili so i=eV.venùne stroje za sklepanje, ki sluiija za orodja pri nadaljnem razvoju. Eden takinin strojev je "F-ersonal Inference Machine" CF'SI). "kerr-.el' language 0" KL0 je strojni jezik sekvenćnih strojev za skp1epanje.. . PS I stroj uporabi Jit k.Lö. V osnovi je KL0 razširjena verzija Frc-loga. KL0 je strojni jezik, Prolog pa je upoiabiii èki jezik. Ker je programi ran je v strojnem jeziku neuclobno, je raz vi t. programi r-ni jezil "£:-:tende>J Serial, prolog" (ESP). ESP jé prijeten za uporabo in vključuje modularne ter makro ^ k-z i . ESP bi lat^ko imenovali mčtkro-zbi-'-ni ja k'ufi'. Operacijski sistem na PSI se liTie-nùje ^slIlPuS. V--:^ i moduli operaci jsk.ega = i st-i-ir.-:, SlnPOr; so napisani v jeziku ESP". Kritiki jezikov pr-edikatne logike postavljajo vprašanje, ali je mogofÄ- te jezike uporabiti za pisanje kontr-ial n i h programov, kot so operacijski sisteirii. t-.^P se je na tem področju zelo obnese! in z rijim napisan ■ operacijski sistem JĆ ućinkovi:;. SlMPOS se razvija in trenutno na nje.n ie ne tečejo ^^e^ji aplikativni programi. -Ui-.! ;e bil r.azvit na začetku projekta, :atc -sdraia omejitve sekvenčnega procesi ran J 5. Zato so razvili KLl, ki vključuje vzporedno p. ocesiran je in ostale izboljšave glede na K.Li-''. ^r i razvoju KLl je bil v velika pomoč konkurentni Prolog, ki je razširjena verzija Ffoioga. t.cjnkurentni Prolog je primeren za objektn-i: orientirano programiran je in simulirarije vzporednih dogodkov. Za poiTic-u pr-; rai'voju so izdelali PSI sekvenčni stroj za si-lepaaje in Delta stroj za poslovanje z r-el ar,i jsk:i .1:1 oazami. SERI JSc.l STROJ 2A SKLEPANJE Za gener jez i k i n račun or oa j nudi Ok.ol J ra. KL0 je osnovan na logičrtem programiran ju. DEC-lliJ Prolog iz Edinburga (19B3) in Prolog II iz Marseilla (19B2) nista primerna za strojni jezik ali jezik za opis sistema. Zato je bilo potrebno spremeniti kontrolne strukture, podatkovne tipe i rt vgrajene pr-evdi ):;ate osnovnega nivoja. Te spremembe otitogočajo napisati osnovni operacijski sistem in potrebne aplikativne programe. Erio^jtaven "cut" oper «tor DEC-lii' Prologa ne, zadošča za interpreter, oči4čevaiec, procesiranje napak itd. Zato je dodan večnivojski "cut" operator. Nadalje sta dodani operaciji "bind-hook" in "eKception-hoor;", ki sta podobni "-freeze" operaciji v Prologu II. Podatkovni tipi Potrebni, so dodatni podatkovni tipi : nizi in vektorji. Ti podatkovni tipi so dodani in vgrajeni so predikati za poslovanje z njimi. Vektorji se uporabljajo za kontrolne tabele operacijskega sistema. Vgrajeni predikati osnovnega nivoja Dooariih je mnogo posebni^^ pr edi katov za dostop in kontrolo aparaturnih komponent, kot so: :?iJaratur-ni registri za kontrolo in testiranje CPU, pomnilnika in V/l enot. Ti predikati se pogosto uporabljajo v osnovnem operaci" jskem sistemu, predvsem pr i poslovanju s poiTini Ini kom in i:r-milniki perifernih enot. K tem predikatom so ée dodani predikati za obi čajne- ar itmetične operacije s celimi in naravnimi étevi1i. KL0 je projektiran tako, da doseie nivo DEC-10 Prologa. S tem se pridobi več prostora za uvajanje firmvera in aparaturnih mehanizmov za povečanje hitrosti izvajanja. 2. Glavne komponente SIM 2.1 Osnovna aparaturna oprema Arhitektura PSI (1) ttrhi tektura celice so pomn i I ni ka dolge 40 vse spominske bitov in vsebujejo O bitov označbe in 32 bitov za podatkovno pol je. (2> Mi V ropr ogr amiran-ä kontrola: prevedeno interno kodo KL0 izvaja (lu r r opracjrafniran i nterpreter J (?') nehamsem strojnega sklada : glavni pomnilnik, je razdeljen v 256 logično neodvisnih! področij od katerih je vsako Innko uporàbljeno kot sklad ali polnilno poaroč-je. F"'rirejanje strani izvaja -glede n^ trenutne zahteve. iJi Podpora za .imltiple prociese: aparaturna oprema podpir.-» lio 63 pr^ocesov. (5) V/I vodilo je standardno IEEE 796 vodi lo. (ÒI je lipa CSMA/CD podobna Ether-netu. Hitrost prenosa je 10 Mbps. 2. ; (3) (6) Aparaturna oprema PSI Hitrost Izvajanja: 30 K LIPS (logičnih sl.lepov na sekuridoJ Ml Kroprograni-il-1 spomin: 64 bitov X 16 K besed Cas strojnega cikla: 2iiii:i nsec (4) Pomnilnik: 4ià bitov X 16 tib besed (5) Hitri vmesni pomnilnik: 4l£) bitov X 4 K besed X 2 Tennologija : 1 TL za CPU in NMOS za cjlđvni pomni Ini K 2.3 Razžirjena aparaturna oprema Hitri procesorski modul (1) Strojni jezik: a«;ira na instrukcijskem setij orientiranem na sklad. Vključuje 170 vgrajenih predikatov ter podpira KL0 iri ESP. ;2) Interpreti':-1 jsk 1 mehanizem: bazira na kopiranju str uktur i f\ uporablja 3 «;klade. (3) Arhitekitura pomni IniJ^a : vse spomirtske celice so dolge 36 bitov m vsebujejo 4 bite označbe in 32 bitov podatkovnega polja ali T bitov označbe in 29 bitov za podatke. (4) Mi kropr ogr aitiska kontrola : strojnj jezil-interpretir a mi I-roprogramiran interpreter '.Zi Poslovanje s pomnilnikom: glavni pomnilnik je r-azdeljen v 8 logično neodvisnih področij. (6) V/I je projek;tiran za povezavo na P"SI prek. nadzornega procesorja. (7) Hitrost izvajanja: 2r;i0 K LIPS, (8) Mlkroprogramski spomin: 80 bitov X 11 K besed. C?) Strojni cikel: 100 nsec. (10! Velikost pomnilnika: 36 bitov X 64 Mb besed. (11) Hiter vmesni pomnilnik: 36 bitov X 0 K besed. (12) Tehnologija: CML za CPU in NrtCDS za glavni pomni 1 ni k. 2.4 Sistem programske opreme Profil sistema SIMPOS ; (1) Osebni operacijski sistem z mul ti procesna podporo. (2) Modularna struktura je objektno orientirana. (3) Koriiuni kaci ja s str ojem poteka prek podsistema oken, ki vključuje V/l z Japonskimi pismenkami. Pi smerike so predstavljene s 16 biti. (4) Podsistem mreie omogoča uporabniku, da uporablja oddaljene izvore; procese in datoteke, (5) Programirni sistem vključuje knjižnico v kateri je prevajalnik ESP m povezovalni k, interpreter in očiščevalnik, struktuiran editor itd. SIMPQS sestavlja programski sistem iPS> in operacijski sistem (OS). OS sestavljajo : jedra, nadzornik in podsistem za V/I medije. PS sestavljajo podsistemi - eksperti. Te podsisteme nadzirajo uporabniki, potr-ebna pa je koordinacija med podsistemi in procesi. To opravlja podsistem koordi riator-. Ostali podsistemi so; okna (OS) datoteke (OS) mreia (OS) očiščevalni k/interpreter (F'S) editor (PS) knjiinica (PS) Določeni deli SIM se èe vedno razvijajo. Prvi cilji pa so ie doseženi. To je računalnit PSI, mreia ICOT-Net in programska oprema SIMF'OS. 2,: Proizvodnja PSI Proizvodrija aparaturne opreme PSI se je pričela maja 19B2 z detaljnim projet:tir j^njem pomn i I ri i èkega sistema in V/I vodil. Podrobna speci-f i kaci ja je bila izdelana konec junija 1983 in takrat se je pričela tudi proizvodnja. Za tem so opravili več tiiod i-f i kac i j iri iztjoij'aav. Prwi F'SI sisteiii vključno z V/1 enotami je bil izdelan konec leta 1983. Pr-i razvoju PSI je kot orodje služil mitJi računalnik PDP 11/23, ki je bil priključen na DEC 2060 prek DEC-Neta. Mini računali.l^ so imenovali SVP (supervisor procesor- za- PSI > in je iluiil za odkrivanje napak v -firmveru in aparaturni opremi. Kasneje je bil uporabljen za odkrivanje napak v osnovnih komponentah sistema SIMPOS. 2.6 Razvoj -firmvera Najprej je bilo potrebno napisati mikro-zbirnik in 'zmogljiv mikro-simulator za pisanje in popravljanje mi k;r o-programov. Sploèni mikro-zbirnik bi lahko bil napisan v Prologu.Zato je Prolog osnovni del zbirnièkega procesorja. Na ta način je možno opisati arhitekturo s Prolog programom. Mikro-simulator je napisan v Pascalu. KL0 obsega več kot 10(3 vgrajenih predikatov. Za razvoj osnovnih delov mikro-interpreterja je bilo potrebno veliko časa. Kodiranje in testirai'ijö ^ra t.r rj-pt ofgf siiiov je Dilo irvrseno na ÜtC ik'ósii 2 ;ni kr o-sb i r ni l.:a in, siiiiul auor Ja. Veiina nu ro-procjr amov zd 3IMPQS je Olla ii-aüldiia marca 1984, [Zelotno itevilo ■Iii K t-o-pr c.;jrain = t: 11-1 KOr akùv je ükrog 12 K. Aparatu/na i.on str ukc i j a in implementacija PSI ib) PSI ottiogo^la ; Uć i Hh Ov i tlG pr ami r nega je: i ; va J an J Ć? jerika KL0, logičnega ki je strojni PSI. Arniter tura apciraturne opreme podpira Sir-.POS uperacijaki sistem, razvit PSI. de+inira -funticije strojnih ukazov PSI računalnika. Strojni ukaz, predstavljen na sliki je enostavno preveden iz KLtr) izvornega progratna. Strojni ukaz izvaja -firmverski interpreter, ki zniore unifikacijo in avtomatsko vraćan je. Strojna instrukcija KL0 je predstavi jene i glavo k:lavzule, argumenti glave in z nekaj cilji. Ti cilji vsebujejo uporabnikove predikate in vgrajene predikate. Većina vgrajenih predi katov ima kompakten -format, ki vsebuje v eni besedi kodo operacije in najveć 3 operande. pi (X,V,test) p3(A,256,Y) :- p2(X,Z), add(Z,5,A), (C) id) Veli'Ost pOiTin i 1 ri i ka in hitrost sta dovolj velika za izvajanje velikih programov. <16 I-lb pomnilnika in hitrost 30 LIPS; Zelo ^iT.cigjjivL- 11-1 f. er akt 1 vne V/I naprave : b i t--niap 1 r an ekran, miška itd. Lokalna (LrtN) za interno komunikacijo mc-d P'SI in skupna uporaba per irerfiin napr Za ućini:.ovitG izvajanje programov ima PSI : logičnih (C i 2. e Adaptiranrj aparaturrio opremo ( ICOT lazvojj., ki povečuje hitrost i z vajanja . Fletaibiien mi^roprogramiran sekvenčni kontrcler velikim vpisovalnim t- CM-I r r- O 1 ri i ril i p Qin I, n om. Mc^rio-.!: je apar atur-ne opreme - in fir,iivettt ;: merjenje dinamičnih k ar jl. t é?r 1 ät 1 k 11-, zbiranje statističnih POdaL 0-. . Arhitektura PSI gl ava klavzule argument i gl ave 1 Cl 1 j telesa 2 ci 1 j -teleša 3 cilj telesa . 39 32 24 16 8 0 int int rei 1 var 1 var atom ::oda 1 var vgr :odä 1 var int tip narg ni fig vel i kost rezervirano atom# od 'test' vgrajen pr edi kat 256 al tern. 1 a v z u 1 a od p 1 ---- X .---Y — X 2 f or r^e'-itfCli- BesecJo sentavi ja 'IO bitov, 8 bitov jö "tag" osoAĆbo in 32 pod:>tKö. Označba vsebuje 2 bita za "2DÌ ran J e f. neti" in 6 bitov, , ki predstavljajo tip pod^tK:'. : — nčfde-f 1 n i r-an s i itidoI i ir.i ato Prologu. edino lor-alni sklad DEC-10 Prologa je na PSI ra.^deljen na kontrolni in lokalni stlađ, ker je potreben neodvisen kontrolni okvir za razširjene kontrolne strukture. P-' - O, -J unifikacija i.:- T V jVetrc insUuk. Objektna koda\ p 0 .s \ poirt'l' g. T U podroèjeJ sled •) kontrol. L g/oha 1. Lokal. ittrez instrakcij kUccttt^a uporaba if skiacioi/ Za izvajanje KLii) programov so potr ebni 4 skladi in polnilno področje. PSI potrebuje konkurentno izvajanje več procesov in razdeljevanje 1natrukcxjskih kod med procese. Da zadosti tem zahtevam, je naslovni prostor razdeljen v logično neodvisna področja, kjer je vsako področje predstavljeno s itevi!ko. Področje je lahiko prirejeno enemu od skladov ali polnilnemu področju in skupno več procesom. Področje sluii za shranjevanje kode m skupnih prostorov za spremenljivke. Zato je naslov predstavljen z S bitno ètevilko področja in 24 bitnim notranjim področjem naslova (glej sliko 4.) 31 23 številka področja Naslov notranjega podr. 2.3 liS 9 0 St. logične strani rei . z am i k Podr-očje : logični naslovni prostor maN. 16 M besed. Naslovni prostor i32 bitov); sestavlja 256 podr oč i j. Slika : predstavitev naslova PSI ima do 25Ò puor-očij, v^riakeniu prirediti 16 M besed spomina. je iitoino 2. 12 Pretvarjanje naslovov PSI ima največ 16 M besed realriega spomina. Za prirejanje in sproičanje področij v spoininu je izdelan mehanizem za pretvarjanje naslovov. Fizični pomnilnik se uporablja v straneh jjo 1 t; besed. Strani se na zahtevo prirejajo področjem, sprošča pa jih "pobiralec smeti". Slika 5 ponazarja mehanizem pretvarjanja naslovov, ki je izveden z dvema tabelama, eno za mapo baz strani m drugo za mapo strani. Na sliki je prikazano izvajalno ok.ol je k.L0 med izvajanjem uri i f i k ac i je. Strojne instruk.cije za klavzule in kazalci se nahajajo na polnilnem pocjročju. (okor pri DEC-lß Prologu, se sestavi skupina celic . okvir, glede na ki i catel j a- i n klicanega. Ti ovvir ji se shranijo v lok.alni sklad za spremenljivke in v globalni sklad za spr emenl j i vi. e v str ukt ur i r an i h podatkih. Da doseiemo določ-^no celico v okvirju, uporabimo relativni z amii od oaze okvirja. Kontrolni sklad sluii za srir ai. jevanje okvirjev, ki vsebujejc in-formacijo pri vračanju po verigi, kakor tudi kazalce okolja za nadaljevanje s povratne točke. Sklad sledi se uporablja za shranjevanje naslovov celic, ki jih moramo sestaviti pri vračanju. Dostop v s(:lad se vréi na osnovi kazalca začetra srlana. Ti kazalci : kazalci na ukaze, kazalci na baze okvirjev in kazalci na začetek sklaoa sestavljajo izvajalno okolje k'L0. 31 24 23 10 9 St. področja St. logične strani rei. zamik Tabela področij -r Mapa strani 23 10 9 0 fiz. naslov s t r an i rei. zamik Slika ; mehanizem pretvarjanja naslovov. 2. 13 Multipli proces,! 2. I? V/I enote Editor ji, prevajalniki ui upor-abniéki programi, =e izvajajo na PSI kot ločeni procesi. Vsak od ten procesov ima svaj status, ki vključuje KL0 izvajalna ot ol je istrojno kontrolno in-formaci JO : prioriteto procesorja àa procesiranje pr eK i n 11v . Okolje in in-f ormaci je so iDfane v tn.Cieli, t.i se imenuje kontrolni tlak procesi iPCBi. F-CB neaktivnega procesa je shranjen v lokalna-.n pomnilniku procesorja, medtem ko je PC£ prccesi v obdelavi porasdeljen med registre procesorjđ. VseDina trenutnega PCB se spremeni, kadar se izveae preklop procesa. Preklop procesa se sproii s prekinitvijo ali s ra:iličnimi vtgrajenimi predikati. Zaradi omejenega itevila področij je največje ètevilo procesov 63. 2. 14 Pret initve — üit-mapiran ekran (12liti21 X 901(1 točk) — optična mièka, tastatura — trdi disk (37 MD X 2) — gibki disk (1 Mb X 2) — lokalna mreia (LAN) — linijski tiskalnik Priključimo lahko poljubne periferne enote, ki imajo standarden vmesnik IEEE 796. Na V/I vodilu je 512 K bytov vmesnega pomnilnika, ki se uporabija ,pri prenosu podatkov na sekundarne pomnilne enote ali v LflN. Ta vmesni pomnilnik uporablja programska oprema kot hitri vmesni pomnilnik pri prenosu podatkov z diskov. Bitmapiran kontroler ima neodvisen pomnilnik za sliko, in lastne rasterske -funkcije. V ta pomnilnik se lahko shrani več kot 10 polnih ekranskih slik. Shranjevanje okenskih slik selo zmanjèa obremenitev V/1 vodila. V PSI je adaptiran v£-ktorski sistem prekinitev. Za vsak li-vai prekinitve je pripravljen pr i n i t veri i toi . Vsakei\»u vektorju je prirejen register-, ii i dent i-f i c ira proces. I^o -se pref: inj Uev , se proces preklopi ria ustrezen proces i; registra, ki ga zatem izvede -firmver. Obstaja 6 nivojev prekinitev, 2 za zunanje m 6 za notranje prekinitve. PSI ima tudi -jn -ai^teii. pasti za poslovanje z napak -jt- ;q-j>dijb mea izvajanjem prograoiov. " i-i; i r al t-c i.ii.{rT: i " (Garbage col lectori se SP' oli ko'. ser. proces na osnovi posebne piiti. Doioćeri.s prekirutve imajo vièjo prioriteto od zbiralca.. Te fiujne prekinitve obravnavajo vzporedrii procesi, ki uporabljajo nek.aj posetiru h podrcjči j Ze» sl.lade in polnilno področje. 7birilec. smeti teh posebnih področij ne procesit a. 2. 15 k.rjn-r" i -ji.-.!- i^ci ja si -stema sektfnin. poc/ati. hitri enota procej. pomn. I--- lOfi^Ù' [ FPU,.... skuflno i/oc(do sil t a: k :jnl 1 gur-ad i ja sistema. Slika predstavlja konfiguracijo PSI sistema. CPü vsčDuje ie-venčno kontr'-olno enoto za procesiranje po.-'.a';.; , spominsko enoto s hitrim vmesnim pomni 1 ni i on. enoto za pretvarjanje naslovov, V/1 vodilu. Medsebojno so en.:3te povezane- ;• -'n.'-r an j i mi vodili. V/I sistem PSI je st àn.jar .-me lEEE-796 vodilo in več V/l enot . konzolni procesor je priključen na CPU za vzciriev an je , ini ci jI i zaci jo in za podporo pri oOkri/anju napai- . Ce je potrebno močnejie or-odje za odkrivanje r.apak, je na CPU mogoče priklopiti mi kr-oračunalr,i k PDP 11/23 plus. E5P - RAZÈIPOEN SERIJSKI PROLOG(Extended Serial Prolog) PSl .računalnik, na katerem deluje sistem SlMPOS.ima strojni jezik kL0, podoben Prologu. ESP prenesen v KLC-i -ie direktno izvaja. Vse značilnosti ESP izhajajo iz kL0. Razmerje ESP proti KLl.'i je podobno kot i-lavors proti Uispu.ESP omogoča logično programiranje. Je objektno orientiran in vključuje makro ekspanzije. -Logično programi ranje ESP vljučuje značilnosti logičnega programiranja KL0. Pri prenosu uni-ficira parainetre in ima vgrajen mehanizem pr-ei skovan ja AND-OR dreves najprej v globino, ter avtomatsko vračanje. Vsak Prolog program lahko skoraj neposredno prevedemo v ESP. Objektna or.ientacija Z gledišča logičnega programi r-an ja je v tSP 3bj.2kt predstavi jen z zbirko aksiomov. I jporabo zbirke aksiomov se si. dokazati določeno predpostavk-3 o objektu. Objekti s-i sestavljeni v razrede. El^iP program je sestavljen iz ene ali več definicij razredov. Niz aksiomov povezanih z objektom osnovi unija aksiomov, de-finiranih .v razredu in aksiomov de-finiranih v super r azr edu tega razreda. Zraven logičnih znač 11 iiost i jezika, ima KLia značilnosti podobne Lispu, kot so : cons, rplaca itd. Makro ekspanzije ESP vključuje zelo -fleksibilen mehanizem makro ekspanzij. Kjer. je makro poklican, se nadomesti z ekspandirano oblika. Makroje lahko kličemo tudi iz ostalih jezikov, ki imajo to moinost.Na ta način lahko vstavljamo določene cilje v klavzule. Natančna pozicija vstavka je odvisna od tega, kje =e pojavi klic makroja, v glavi klavzule ali v telesu cilja. Na osnovi tega mehanizma se lahko v glavi klavzule ali telesu cilja pojavijo kot argumenti aritmetični izrazi.. 1 Časovno odvi Y-.na stanja Fv oar-ami komun i ci r a to ob lekt1 raitunal ni 1. a : V/I enotami, dreg i .m računalniki v mreti, z upar abrii kom za terininalom, Zunanji objerti iifiajo 1 ahkio ćaBovno odvisna stanja, ki ào cannili va za progr =1111«. Zato mora sistem zgraditi modele ćasovne odvisnosti zunanjega Sveta. Naivna 1 mp ' e.iie?n tac i j a V iisti lagil. 1 je časovna odvisnost predstavi Jena :: logicčimi relacijaiTii med ćasovni.Tii periodaiTii m ustreznimi stanji. Take relacije so same po sebi permanentne in niso časovno odv i arie. Časovno neodvisna predstavitev je. logično elegantna,- toda naivna implementaciji, ki m učinkovi ta.Raz 1og neučinkovitosti je d>>j = tvo, da je dokaj težko ugotavljati t-..»te relacije informacij, ki programu več i)atrebne. Ce uporabimo enostavno oqji>ü baj.? u-.j.jatkov, recimo tako kot JO vipor aDl JÜ trenutrii? verzije Prologa, potrebujemo cgr oiiir.a "ii. 111 n 1V a in upočasn ju jemo SI s t e;n. F^rogr am i r an j e v realnem času V tlasiinih operacijskih sistemih konvencionalnih računalnikov se modelira čas zunanjega sveta direi-tno s časom obdelave. Časovno odvisna stanja zunanjega sveta so preastavl jena časovna odvisnimi stanji obdelave. Tai-, ns'in 1 nienujemo programiranje v realnem č:'S'... Nsir.ogoče je restavrirati predhodno stinj^, i.o je dolečena obdelava izvr4ena.Cc obar i imo relacije med časovnimi periodami in ;itanji v podatkovni bazi, lahko prograiTii r amo v realnem času. Zato je v ESP uvederia notc.cija časovno odvisnih stanj. 2. Obietti m razredi i-ietođe Guje^t je . pr edst^iv 1 jer» z nizam aksiomov. To Je v ciLnovi enr-k koncept, kot "svetovi" v net.aterin t-r o t ütj i r.. Isti klic predikata ima là^l'•'- rjuli'ii« -^e.iiòi 1111-e , če ga uporabimo na različni!' fnzih . 11 oiiiov . Pri mehanizmu svetov se ni2 aksiomov .jüloci ob izvajanju. V ESP se določi z objekta.!!, pooanim s prvim argumentom klica. Pi-edii.ati i ta^ 4no samantiko, ki je odvisi'ia od argumeiita, se imenujejo metode, kakor v ostalih objektno usmerjenih jezikih. f'lice metod r«z)iiujemo od klicev vgrajenih ali lokalnih predi'.atov tako, aa postavimo pred klic ":" \pr liner " : odpr" t ( Vrata) " . V primeru ima spremeni j 1vka "Vrata" vrednost, ki je objekt povezan z nizom atsiomov, v katerem se nahaja predikat "odprt". Raz redi Posamezen objek.t pripada razredu objektov. Razrec objektov je enostavno razred, ki definii a skupne lastnosti skupini podobnih objektov. Objekt, ki pripada nekemu razredu je temu razredu prirejen. Ena ali več definicij razredov sestavlja EBP program. De-finicija razred« obsega različne atribute razreda, vključno z nizon. aksiomov, t:i so povezani 2 objei-tom prirejenim razred'-i. Razred se lahko obravnava ►ot objekt, ki predstavi ja določen niz aksiomov. Sestavi objektov Objekt lijnko i ii.a časovno odvisne spremenljivke stanj, 11 Jih imenujemo sestav objekta. Sestavi niso logične spremenljivke, ampak za logično programi ran je l-.onst an ci le vrednosti. Vrednosti sestavov 1 ari^ o odčitaiiio z navedbo imena po .iietodi "qet-3lot" definirani v nizu objektu ustreznih aksiomov. Vrednosti sestavov definirajo del aksiomov iz niza povezanih z objek;tc>(ii. Prireditve istemu razredu imajo ista imena sestavov. Vrednosti sestavov lahko spreminjamo z metodo "set-slot". To ustreza spreminjanju niza. aksiomov predstavljenih z objektom. Ta značilnost je podobna ukazoma "retract" m "assert" v DEC-lSi Prologu, le da je način spreminjanja pri Prologu dokaj omejen. "Assert" in "retract" je mogoče uporabiti samo pri interpreti ranju programov, ne pa v prevedenih programih. ESP uporablja kratko notacijo za poslovanje s sestavi. Na primer "X'.a" nam da vrednost sestava X in "X!a := V" priredi X-u vrednost V. Mehanizem prir^ejanja V ESP je več mehanizmov, ki so podobni Flavors sistemu. De-finicija razreda je lahko naravna, ki ae-finira eden ali več superrazredov. Ce ima superrazred nadaljni superrazred, je ta tudi superrazred originalnega razreda. Superr-dZr edi razredov tvorijo drevesno strukturo. Hirearhija razredov in vse prirejene relacije med razredi se določijo statično pri prevajanju, medtem ko se pri Prologu določijo ob izvajanju. Prirejanje metod Niz aksiomov povezan z razredoni je unija aksiomov definiranih v razredu in tistih, ki so de-finirani v superrazredu. Nekateri superrazredi iri podrazredi vsebujejo al<'siome za isti predikat. Nizi aksiomov superrazredov so enostavno sestavljeni, aksiomi za isti predikat pa povezani z operatorjem OR. Dokler se obravnava ista logika, lahko sestavitiio semantično mrežo n« osnovi IS-ft hirearhije. Ce se uporablja ista logika, zaporedje z OR povezanih aksiomov nima vpliva.Ima pa vpliv, če se obravnavajo izven računalnika. Zato ESP predvideva speci-f i kaci jo zaporedja lastnosti, kar je isto, kot zaporedje preiskovanja aksiomov, kadar imajo različni razr-edi aksiome za isti predikat. Lastnosti sestavov Razredi imajo sestave definirane v definicijah razredov in v definicijah superr-azredov. Ce imajo sestavi enako ime, se privzame samo en sestav s tem imenom. Za sestave objektov se lahko uporabi "PART-OF" hirearhija na osnovi IS-A hirearhije. Predpostavimo, da je ključavnica del vrat. Najprej podamo definicijo enostavnih vrat brez ključavnice. Potem definiramo razred s_kl jučavnico, tako da ima prirejen sestav z razredom ključavnica. Nazadnje definiramo razred vrata_s_kl jučavnico, ki vsebuje oba razreda, razred vrata in razred s_ključavnico. Vrata s ključavnica so vrata in prav tako objekt s ključavnico. V naèem primeru smo definirali razred s_ključavnico kot ločen razred. To je bolje, kot da bi razred vrata_s_ključavnico direktno vseboval razred vrata. Tako v ESF' v celoti izkoristimo moinost večkratnega vsebovanja. Razred s_k1jučavnico lahko za tem uporabimo za definiranje nadaljnih razredov, na primer okno_s_k1jučavnico. 3. Nemonotoni ja Pri mehanizmu prirejanja mora biti niz aksiomov podrazreda superniz tistih iz super-razreda. Torej mora biti predikat uspeèno dokazan v superrazredu uspeèno dokazan tudi v podrazredu. Tak mefianizem prirejanja je monoton. Zaradi monotonije vrata_s_ključavni co ne morejo biti podrazred od vrat, ker vrata_s_k1jučavnico ne inoremo ocJpr č-t , dö so veüna oapremo. Za »T.ehani z-:..» pr i re jan ja r azr ed i^nostavni h podrazred vr s»t_£»__r: hirearhi je razredov vr dt d na to , üa '«ie potreboval vr 1 je selo težavno pr&o uporabo monoton eg «j ra;:vijati pr ograme. zaklenjen«^, vroL« pa lahko vzdrievanje enostavnega mora biti v naèem primeru vrat brez ključavnice 1 j uiiavni co. Projektant mora misliti pri razredu l-afiko zgodi ^ da bo nekdo Juii:avnico. Take razširitve ideti. Kadar gradimo z nanja, je mnogo lai je Operator- Nemonotonija :Tiehani zn-odià. ver z \ J a •:lcür * v'.:jr"äjt-n pr eö i nivoja . v :j r 1 e n -ä jpoaiötfiL-i-.e J é rnčtođ i p*' ekr \r\\r an&'ja ae-finirtnn v rj postav i.ifio V k i por eie do superra::r eda upor ablj h, n« vrnnjem p r e v e d i? J o v Cut " je v ESP vpeljana z dvema Eden je neliakéna razširjena inane "cut" operacije. V KL0 kat poreie alternative do podanega jdeni^i klicev predikata. Ena ih uporab "cut" operatorja je pri ivanja. To je zamenjava aksioma v superra.zredu s tistim, ki je vo jerii podr čizredu. "Cut " operator dt? t X f > 1 C 1 jc -iksi omo v eg ä pìodr azr eda , tal ega mvoja, da odr€?že aksiom iz ker se tal;:o prekrivanje pogosto e "Cuit" simboli ki nastopajo (iivoju kiavzul metod avtomatično ečni vojsk.? "Cut" ukaze. Né-v} i-t i vn J znanje predstavimo s prekrivanjem in e» ici rr.iii^ pogro=»>.om. Na primer :ptice letijo, pifiy/im 50 ptice, vendar pirigvini ne letijo. I upo'òno većnivojskega "cut" -»kupaj s poqreiki riàsTane podobna kontrolna struktura kot "c'i^.tcri" in "throw" v določenih Lisp 'il steo.i r.. k'.ontrolna struktura je nepogrešljiva v mehaniziiiu obravnavanja napč*k , ki je potreben v skoraj vseii deiih operac i jskega sistema. S'^etoda pr - : r e jan j a Klavzule m-.vioo v i r> i c i j 1 " razreda 30 ra;:vričtjrie v 3 kateL.iorije ; principielne k i a v ; u i e , p ; • a einon s ^ e t 1 a v z u 1 e in p o-d emon s k e »;1 avzui e. De.nuns). r.. I «vzul e se sintaktično oz je J o • T. val i f i kator jem "be+ore" ali "after- pr-vci • Principielne klavzule v iglici ji. re,£rer.ö za isto ime predikiÄta m i lito ariteto a::'I i t n jejo principielni predi kat j r ixr-o'' niz ;-iavZ'-a oblikuje predikat v obi'čajne(t. Pr ol oy;.«. Fod:-D no -f or mi rajo pred-demons k e k 1 avzul e pred Tionskl pred i kat. hetoüa «it^ uvecur- = predikatom "method". Telo prediV.ata ■.netfico" sestavlja AND kombinacija naslednjega dre-^v/so: — At-iD r.o»i,Di n-isci ja klicev vseh pred-deinons^ih predikatov de-finiranih v prirejenik razredih. Zaporedje je tako kot je bilo p r i r e j an j e. — OR v bmoii-.aci ja »-lic^av v=iet\ pr i ru: i pi elnih predikatov, de-finiranih v prirejenih razredih v zaporedju prirejanja. -- AND »omDii-acija klicev vseh" po-OčiT.on =,v : h predikatov definiranih v prirejttiiih razredih v obratnem zaporedju pr i re .l'in J a. Zaporedje je obrnjeno zato, da se pred in po-demonski predikati pravilno v g n e z r? 1 : o. me^.hod.jjr- edicate(Al , . . , b 1 (Ai........A.ii) , . . , (p 1 1 r. iiioinostjo niakro ekspanzij atrijjà t^noätavno nadomesti z ooliV'^.. TiU mtì^lanizem je zadosten eiiiu pi-dbin'i jiüziljh.ne zadožča pa il J emu podobnih jezikih. Na primer: pisfidira 11 j : •spremenljivk v "Expansion" in prirejanjem spremenljivk v "Condition". S tem je omogoiiena enostavna optimizacija, ker se vrednosti konkretnih izrazov izračunavajo v -fazi prevajanja. v Zaporedje- c:iljev ne pa v : p 1. a , ^ ( ;< + y ) ;■ oidd ( ):, y , Z ) , p ( a , ( Z ) p ■ i., t ( add < X , V ) ) ne more biti j »iiei-iani zrnom enostavne zamenjave. Popoln Tormat mal-ro de-finicije v ESP je prikazan na siiti. Pattuirci == ■• E/ipansion when Generator where Checker : - Cofici i 11 ori. Slila : mäkro definicije. Vzore.-, il i.iiificiri "Pattern" <=t iparid i ra v "E;l)i za odločitev, ali se klicni vzort2c ek'ap ar,.:: 1 r i ali r,e. Lakiko se upor-abi za računski del od "fTxpansion" s pisanjem 5. Uporaba ESP prevajalnika Od avgusta 1984 je na "main-frame" računalniku na razpolago prečni prevajalnik iz ESP v KLiil. S povezovanjem objektne kode z majhnim "runtimesupport" sistemom napisanim v KL0, se programi lahko izvajajo direktno na PSI računal ni ki h. ačlt.na je potreba po objektni usmerjenosti. Objekt je pr-edstavl jen z vektorjem, shranjenem v enem od polni Iruh področij. Prvi element vektorja je kazalec na opiänik objekta, ki vsebuje naslova dveh tabel. Opisnik je razdeljen med prireditve, ki pripadajo' istemu razredu.. Torej je za objektno orientiran j .tem ki i car,ja potrebna 1 beseda. Ostali elementi vektorja &o za shranjevanje vreonosti sestavov objekta. Prva tabela, na katero kaie opisnik objekta se imenuje tabela metod. Tabela metod povezuje atome predi katnih imen s predikati metode. Druga tabela se imenuje tabela sestavov, ki povezuje atome imen sestavov z relativno pozicijo sestava znotraj objekta.Tabel i sta predstavljeni kot KL0 predikata. Klice objektno orientirane metode prevede KL0 prevajalnik v klice runtime podprogramov z atomi imen metod in originalnimi argumenti.Runtime podprogram preveri prvi originalen argument, ki je vektor za predstavo objekta. Zatem preveri prvi element vektorja, ki je opisnik objekta. Zatem ponovno preveri prvi element, ki je tabela metode. Tabela metod se pregleda z uporabo imena metode in s številom argumentov kot ključem, z uporabo kode objekta, ki je predikat metode. Končno se ta predikat pokliče z or--i gi nal ni mi argumenti. V večini primerov so nekateri klici predikatov v mehanizmu objektno or i e'nt i rani h povezav redundantni. Na primer, če metodo sestavlja samo eden principielni predikat, ni potrebe za predikat metode, ki vsebuje demonsko kombinacijo. Te optimizacije opravi prevajalnik med prevajanjem. Kar se tiče hitrosti izvajanja, sedanja verzija ESP ni zadovoljiva. Klici metod so .3 do 4 krat počasnejsi, kot direktni klici KL0 predikatov. Procesiranje sestavov ima enak balast. Izvori balasta so klici "runtime-support" podprogramov in preiskovanje tabel sestavov. Planirane izboljèave Planira se vgradnja novih predikatov v KLIä za zmanjšanje balasta. Klici runtime podprogramov bodo nadomeščeni z vgrajenimi predikati in funkcijo podprogramov bo izvajala strojna oprema. Dostopi do sestavov bodo prav tako prevedeni v klice vgrajenih predikatov. Mehanizem preiskovanja tabel metod je dokaj neunčikovit zaradi v KL0 vgrajenega mehanizma indeksiranja klavzul. Preiskovanje se lahko pospeèi s podporo firmvera. Z uporabo firmvera bodo tabele shranjene v hitrih vmsnih pomnilnikih, kar bo zmanjéalo potrebe po ceiitralnem pomni I ni ku. Qb podpori planiranega firmvera bodo klici metod dvakrat hitrejèi. Izboljšave pri dostopanju v sestave bodo ée večje, ker posegi ne bodo vključevali klicev predi katov. NacJ.dljna op 11 éTiì z ac. i j a Za imanjianje balasta pri preiskovanju tabel so zelo učinkoviti hitri vmesni pomnilniki (cashe), v ■ katere se shranijo imena najbolj pogosto klicanih metoO, njihovi prvi argumenti in ustrezni naslovi kod predikatov. Hitri vmesni pomnilnik bi moral biti dovolj velik, da bo razmerje zadetkov zadovoljivo. . Potrebna bo posebna izvedba, kot je na primer asociativni pomfi i 1 n i k . Izkuénjs s BIMPQS strojne -funkcije, kot je vezje za avtomatsko sledenje, :a avtomatsko sproStanje itd. Da bi dosegli hitrost 100 LIPS na enem procesorju, mu je potrebno dodati posebne strojne -funkcije. Sekvenčni Prolog računalnik sta projektirala Evan Tick in David Waren. Uporablja cevenje (pipelining), reduciran instrukcijski set, prepleten pomnilnik. S tem se poveča hitrost izvajanja Prolog programov. PEK je eksperimentalen računalnik za raziskovanje arhitektur, . ki bi omogočile hitrejée izvajanje Prolog programov. ^Sekvenčno izvajanje Pr ©i 1 ITU nar i-ie /er-zije tr-.eh najnižjih podsistemov 5IMF0S ; jc-cl( o,, nadzornik in V/l podsistem so kodirane v ESP in v celoti testirane na PSI. Trenutno se preverjajo Izboljéave teh podsistemov in programskega sistema SIMPOS. Med razvojem SIMPOS je postalo jasna, da mehanizem večkratnega prirejanja zelo olajša deljenje kode. Na primer -funkcije za modul nadzornik, ki poslujejo s tabelami, imeniki, procesi in tokovna orientirano komunikacijo med procesi, je mogoče uporabiti direktno v modulih na vièjem nivoju. Spreminjanje programskih modulov je dokaj enostavno. hoduli SIMPOS so ločeno razviti, kljub temu, da so tesno povezani. Pri spremembi je v večini primerov dovolj ponovno prevajanje. Včasih se je zgodilo, da so bili povezani moduli napačnih verzij. Zato je skoraj nepogrešljivo avtomatsko poslovanje z verzijami tiiodulov. Mehanizem uiakro ekspanzij omogoča bol j-čitljive programe. Posebej ker- dovoljuje ar-i tmet 1 čfLe izraze l-.ot argumente. Ostale aplikacije Kljub malo izkušnjam z ESP', so se lastnosti jezika pokazale kot zelo dobre. Ce bi bil SIMPOS kodiran direktno v KL0, bi bilo projektiran je mnogo teije.Ker se analizira odnos povezav med razredi statično med prevajanjem, je nepogreèlj i va programska podpora za avtomatsko sledenje verzij. Programska podpora za sledenje verzij bo dodana v knjiinico SIMPOS. SEKVENČNI PROLOG RAČUNALNIK PEK je eksperi mental ni računalnik, konstruiran za Izvajanje Prolog programov. Uporablja LSI bit-rezine za sekvenčnik in ALU , ter mi kroprogrami r-arto kontrolo. Da omogoča veliko hitrost izvajanja Prolog programov, vključuje vezja za uni-fikacijo in vračanje. Razvit je enostaven Pr-aiog interpreter. Zmogljivost stroja je okrog 40 LIPS (logičnih sklepanj na sekundo), kar je enako, kot zmogljivost DEC-10 Prologa na računalniku DEC 2060. 1. Uvod Prolog je logični programirni jezik in se največ uporablja na področju umetne inteligence. Mehanizem izvajanja v Prologu se zelo razlikuje od 1-on vene i onal n 1 h jezikov. Zato je pomembno raziskati arhitekture za izvajanje Prolog programov. PSI je l-.onstr ui ran za raziskave in razvoj. Ima posebno arhitekturo : strojne sklade in multl-pr očesne -funkcije. PEK vključuje speci-fične Znano je, da je za učinkovito izvajanje logičnih programov potrebna velika mera vzporednosti. Pomembno pa je raziskati kolikšna je največja prepustnost stroja pri sekvenčnem izvajanju. Zato je v PEK računalniku malo vzporednosti., razen : -- prenos podatkov je izveden v 3 poljih: okvirnem, aznačbenem in polju vrednosti. — podatkovna področja so ločeno razporejena v spominskih modulih, kot so skupni pomnilnik, pomnilnik procesa, vodilni sklad itd. — vodoravni format mikro-instrukcij simultano nadzira strojne module. — sproščanje prireditev Izvaja pddsekvenčnik-. spremeni jivkara — branje Instrukclj teče po načinu cevenja. Mlkroprogramska kontrola PEK uporablja mikroprogramsko kontrolo in Prolog interpreter je napisan v mlkro-kodi. Prevajalnik pretvarja Prolog programe v mikro-kodo. Metoda deljenih struktur PEK uporablja deljene strukture, tako da je za procese, ki potrebujejo dodatne informacije predvidena posebna strojna oprema. Ostale lastnosti Ker so podatkovna področja ločeno razporejena po pomnilniku, je moino v ta področja posegati s kompleksim načinom naslavljanja, ki ga Izvaja strojna oprema : — indeksno naslavljanje za pomni 1 ni k procesa — naslavljanje prek sklada za strojni sklad — post-lnkrementalno za naslovne registre — 1zračunavanje naslovov za celice spremenljivk in globalni sklad PEK. vključuje specialno strojno opremo za uni-fikacijo in vračanje: — primerjalna vezja — vezje za avtomatsko sledenje — vezje za samodejno sprožčanje Kan-f i gur ac 1 j a sistema Slika: kotrf i gurac i ja PEK sistema. Sistem sestavlja osnovni procesor MC 68000 in PEK. Vse V/l enote so priključene na osnovni procesor prek Z-80. Osnovni procesor inicializira PEK in podpira V/I operacije med isvajanjeiTi Prolog programov. PEK kofitroiira osnovni procesor prek CML registra (izvajanje HAlT, STEP itd.) Ostali registri za komunikacijo so ICR ("input commands" osnovnega računalnika k PEK) in OCR ("output commands" od PEK k osnovnemu računal ni ku). Strojna oprema Strojna opredia obsega 5 plo^č: — CCU sekvenčnik, WCS, vmesnik za osnovni procesor MC 68001!) ALU , "by-pass" kontrolerji, pomnilnik procesov, strojni sklad — Uni-f i kaci j ska plošča j globalni / sklad, vodilni sklad, primerjalno vezje, sprostitveno vez je. — Skupni pomnilnik : ima dva naslovna registra,dva registra za čitanje in dva za pisanje. — Plošča za evaluacijo sistema : ura za čas izvajanja, žtevec mi kroinstrukci j. Format besede Beseda je sestavljena iz 14 bitov dolgega okvirnega polja in 20 bitov dolgega polja za terme, da je omogočen prenos molekul. Polje terma je razdeljeno na 4 bitno označbo in 16 bitno polje za vrednost.Uporabi jene so naslednje označbe: celo število -- atom i i teral nede-f ini rano globalna spremenljivka lokalna spremenljivka prosta spremenljivka struktura (term) — struktura (seznam) — konec strukture — klavzula — koda Seznami so predstavljeni z enodimenzionalnimi vektorji. Imajo ločeno označbo in povezano shranjene elemente. Na koncu vsakega seznama je dodana posebna označba EOS (end o* structure), kl določa dolžino seznama. Sestavljeni termi so sestavljeni na podoben način kot seznami. Spominski moduli Spominski moduli so razvrščeni glede na njihovo uporabo in se lahko procesirajo vzporedno. Spominska integrirana vezja imajo pristopni čas 55 nsec. — WCS vsebuje mikro program 96 bitov X 16 K besed. — skupni pomnilniki 20 bitov X 32 K besed — pomnilnik procesa: 20 bitov X 16 K besed — globalni sklad — vodilni skladi 14 bitov X 16 K besed pomnilniški sklad — strojni sklad: 34 bitvo X 4 K besed — registerske datoteke: 34 bitov X 16 besed Interna vodila R, S in Y vodilo v širini 34 bitov. Bekvenčn.i k Sekvenčnik sestoji iz 4 Am 2909 A 4 bitnih rezin LSI. Minimalni izvajalni čas je 120 nsec za izvajanje instrukcije in 160 za večino vejitvenih ukazov. Aritmetična logična enota Vsebuje 9 4 bitnih rezin LSI, ki so razdeljene v 3 bloke, glede na -format besed. ALU operacije so neodvisne za vsako polje kakor tudi rezultati operacij. Nadalje je dodanih 9 LSI kot eksterna register datoteka, kjer je shranjenih 32 registrov. Obhodni kontrolerji Predvidena sta dva obhoda. Eden za prenos podatkov iz R vodila k Y vodilu in drugi za prenos podatkov od S vodila k V vodilu. Uporaba obhodov omogoča na primer prenos podatkov od izvornega vodila k namembnemu vodilu in simultane operacije ALU. Pomi kalni ki Uporabljena sta dva. Levi za pomikanje spodnjih 14 bitov polja terma v polje okvirja. Desni pomika okvirno polje ali označno polje v polje vrednosti, Primerjalno vezje Z njim se primerjata dva atoma z eno instrukci jo. Avtomatično določanje naslovov za celice spremeni jivk Naslovi celic spremenljivk se izračunavajo avtamatiino z uporabo dveh registrov. Ce je spremenljivka prosta ali vezana, se ugotovi iz indikator ja in ni potr ebno odčitati- vrednosti iz globalnega sklada. Avtomatsko sledenje Vraćanje zahteva sproščanje prireditev oz. resetiranje vrednosti spremenljivk v nede-f i nirano stanje. Fvi prireditvi se mpra naslov celice shraniti na globalni sklad. PEK izvede to operacijo strojno. Kadar se izvede operacija pisanja na globalni sklad, se naslov' avtomatično zapiše na vodilni sklad. Avtomatično sproščanje Sproščanje se v PEK vrši avtomatično in ga izvaja sekvenčnik. Kadar je vodilo prosta, se izvaja . sproščanje vzporedno z glavnimi operacijami sekvenčnika. Pobiranje z vodilnega sklada in zapisovnaje v globalni sklad se prekrivata, kar poveča hitrost operacije. Čitanje struktur v cevnem■načinu mikroinstrukcij 1. Na mikro-zbirnik pri najprimernejši cikel. ta način zbiranju lahko izbere Napisana sta dva programa, ki ugotavljata dolžino cikla. Prvi ugotavlja doliino cikla tako, da razdeli operacijski čas za vsako enoto na enote À0 nsec. Drugi ugotavlja doliino cikla tako, da poišče najdaljšo podatkovno pot in skrajša čas cikla za 15 % glede na prvi program. Caa cikla se lahko skrajša za nadaljnih 40 X pod posebnimi pogoji: če je bil izbran naslov z globalnega sklada v predhodni mikro instrukciji, potem se zveča hitrost čitanja z globalnega sklada za 96 nsec. Moni tor/očiščevalnik Monitor je razvit na osnovnem procesorju MC 68000 in sluii za odkrivanje napak v strojni, opremi. Monitor obsega ekranski editor, mikro-zbirnik, razbirnik in dodatke kot so: postavljanje prek i nitvenih točk, izpisovanje vsebine registrov itd. Kadar se izvaja Prolog uni-fikacija med dvema elementoma strukture, PEK vsebuje dva naslovna registra (ADI, AD21, dva pisalna registra (WR1, WR2) in dva čitalna registra (RDI in RD2). Kadar se čita RDI ali RD2, se Adi ali Ad2 avtomatično poveča za 1 in prične se operacija čitanja naslednjega podatka. Podatek z naslednjega naslova se vpiše v RD približno 250 nsec kasneje. Okvirno polje čitalnega registra ima enako vrednost kot okvirno polje, shranjeno v naslovnem registru. 4. Interpreter 3. Razvojna programska oprema Prolog jezik je kompatibilen z DEC-10 Prologom. Razvit je enostaven Prolog interpreter za merjenje zmogljivosti sistema. V sedanji verziji so vse spremenljivke obravnavane globalno in niso implementirane zahtevne ■funkcije, kot je indeksiranje klavzul ali optimizacija rekurzije. Za testiranje sta bila izvedena z interpreterjem 2 Prolog programa. Prvi je dodajal seznamn elementov v prazen seznam, drugi pai: invertirai seznam elementov.Povprečen cikel je znašal okrog 170 nsec, torej je hitrost okrog 40 K LIPS. Mi Viro-zbir ni k Mikroinstrukcija PEK računalnika je horizontalna, dolga 96 bitov in vsebuje 24 polj. V začetku je bil napisan zbirnik, ki je specificiral mnemonike za vsako polje. Ugotovili so, da so programi težko čitljivi. Zato so razvili podprocesor, ki vključuje klice makro -funkcij s primerjavo vzorcev . Na PEK se uporablja Am 2925 časovni generator, ki lahko generira 8 vrst 4 -faznih časov. Izbira časa se vrši s 3 bitnim CYC poljem v Li teratura FIFTH GENERATION COMPUTER SYSTEMS 1984 Proceedings o-f the International Con-ference on Fi-fth Generation Computer Systems 1984 _ Tokyo, Japan, November 6-9, 1984 **«<*•*«***««#«««««*•*«•••«*<•«*«««* « Podatkovno pretokovni procesor • t )iP07281 • •**4***t»*<***t«*<«***f««»***t»t**«« Načrtovalci slsteaov za procesiranje slik so obitiajno prisiljeni poiskati koaproals «ed hitrostjo in 1leksibilnostjo sistena. Sistea, ki ga sestavljata oiniraäunalnik za procesiranje slike in masovni pomnilnik za shranjevanje slik, je okoren in pottasen, kar je nesprejemljivo za delo v realnea Času. Z do-datko» posebne materialne opreme se hitrost procesiranja poveäa, vendar vsaka sprememba programske opreme narekuje spremembo materialne opreme - fleksibilnost sistema se zato zmanjSa. Omenjeni razkorak med hitrostjo in fleksibilnostjo sistema je moC omiliti z uporabo pro-gramabilnega slikovnega procesorja, ki se odlikuje s podatkovno vodeno arhitekturo. Primer takänega procesorja je NEC )iPD7281 , katerega moü temelji na kroüno organizirani pipeline arhitekturi ter bogatem naboru ukazov. pPD7281 je prvi VLSI eip,^kl deluje po naCielih podatkovno pretokovne arhitekture. Ta omogoCa veCjo uCinkovitost procesorja v mnogih veCprocesorskih aplikacijah, kot sta procesiranje slik ter razpoznavanje vzorcev na področju umetne inteligence, kjer se uporabljajo algoritmi za dvodomenzionalno konvo-lucijo, povefiavo, pomanjSavo in rotacijo. Njegova učinkovitost postane oäitna predvsem pri procesiranju slik v realnem Času, kjer dodobra izkoriSCa vsebovane vzporednosti uporabljenih algoritmov. pPD7281 ni uporaben le pri procesiranju slik, temveC tudi pri zahtevnih numerittnih izraCunih, kot so matriCno matrifino mnoienje, matrifino vektorsko mnole-nje, aritmetika s plavajofio vejico ter Izračuni transcendentnih funkcij v realnem Času, V nasprotju s von Neumannovlmi procesorji, procesira ^PD7281 pakete (tokens), ki so nosilci operandov in med izvrševanjem ne potrebuje dostave ukazov, V von Neumannovih procesorjih je vsak korak sestavljen Iz dostave, dekodiranja ter izvršitve ukaza, pri Čemer se vsi trije deli izvrSijo zaporedno. Tako je izraCun A = B + C je sestavljen iz dostave ukaza "seStej B m C ter shrani v A" v procesor, iz dekodiranja ukaza, dostave operandov B in C v procesor, seStetja obeh operandov ter prenosa rezultata A v pomnilnik. Podatkovno pretokovni procesor ne pozna dostave ukaza. Namesto tega vsebuje 'grafni' pomnilnik (LT in FT), v katerega se pred začetkom izvrševanja vpiSe prcgramski podgraf. Pretok podatkov se vrsi s pomoCjo paketov, ki vsebujejo polje z naslovom procesorja, identifikator, podatkovno ter krmilno polje. Notranja kroZna pipeline organizacija (Slika 1) oaogoCa procesni enoti neprekinjeno delovanje s hitrostjo 5 MHz. Procesna enota vsebuje 17 X 17 bitni mnoüilnik ter ALU, kl omogoCa ostale standardne aritmetično logltine operacije. Nabor ukazov je äiräi kot pri veČini klasičnih von Neumannovih procesorjev. Komunikacija z okolico poteka s pomoäjo vhodne in izhodne enote (IC In OC). Glavni procesor posije paket procesorjem )iP07281 . Iz naslovnega polja paketa pPD72ai ugotovi, Ce je paket namenjen nJemu ter ga v tem primeru sprejme, izloCi naslovno polje in poSlJe v 'obtok' - najprej v LT. Paket, ki nI namenjen danemu procesorju, se nespremenjen poSlja v istem ciklu preko izhodne enote (OC) naslednjemu )iP07281 . Procesor je tako za 'tuje' pakete praktiCno transparenten. Na ta naCin vsak procesor zbira 'svoje' pakete. Med 'ob- tokom' po |iPD72ai paket Se nekajkrat spraaeni vsebino In dolülno. Identifikator sprejetega paketa omogofia doloCltev prlpadaJoCe povezave v opisu programskega podgrsfa. Vsebina identifikatorja Je naslov lokacije v LT (povezava). Iz LT pride paket z novi* Identifikatorjem (ki je vsebina naslovljena lokacije v LT) in vstopi v FT, kjer se nahajajo opisi toCk programskega podgrafa. Del Identifikatorja Ja naslov lokacije v FT. Vsebina naslovljene lokacije v FT opisuje toCko prograaskega podgrafa in Je sestavljena iz dveh delov. Prvi del je koda operacije in Je del novega Identifikatorja ob izstopu paketa Iz FT - namenjen je procesni enoti. Drugi del pa posredno opisuje oznake povezav, ki vstopajo v toCko in slu2i AGIFC pri generiranju naslova lokacije v DM. Ta naslov se doda kodi operacije v okviru novega identifikatorja. Tako spraae-njen paket vstopi v 'paketni' pomnilnik DM. Ce predstavlja ta paket zadnjega Izaed operandov, se skupaj s svojim paro« (ta te Caka v DM), preko vrste Q prenese v procesno enoto PU, sicer pa se podatkovno polje paketa shrani v naslovljeno lokacijo v OH. Vpis ter branje iz paketnega poanllnika potekata ao-dasno z izvrševanjea v procesni enoti. Ce operacija zđhteva en saa operand, se paket prenese Iz FT direktno preko vrste Q v procesna enoto PU. Procesna enota sestavi pakat, ki vsebuje rezultat in identifikator, ki Je oznaka izhodne povezave. Paket ponovno vstopi v LT, ter nato v FT. Ce procesor ne vsebuje nobene operacije, ki bi potrebovala ta paket, prenese AGiFC ta paket preko vrste S In Izhodne vrste 0Q v Izhodno enoto OC. iobh-ioBOO:? IR6Q X»OOB,sOODn -JJSS5. -OACK ICi Input Controller OC! Output Controller LTi Link Table FT! Function Table DM: Data Memory Q: Sueue PUi Processing Unit OQ: Output Queue AGSFC! Address Generatop and Flow Controller RC: Refresh Controller Sllka 1 Npr., za izvršitev operacije A = B + C aora procesor prejeti paketa, ki nosita vrednosti B in C, Sele nato lahko IzvrCl operacijo seštevanja. Vhodna paketa lahko prispeta v poljubnem zaporedju, saj Je procesor sposoben razpoznavati pakete, iz opisa podgrafa, ki je vneSen v procesor pred izvrSevanJea, le ta ugotovi, da paketa B in C pripadata preko operacije '+' paketu A, zato paketa B in C zdruZi in poSIje v procesno enoto. Vrednost, ki je rezultat izvrSltve v procesni enoti, se vstavi v paket in opremi z oznako A. Ce Je A vhodni paket neke nove operacije, ki se aora izvrSitl v istem mPD7281, se shrani v paketni pünr.ilnih, dukler ne prispe v procesor tudi paket, ki nosi vrednost drugega operanda. Tedjj 56 of.isanl postopek ponovi. Pravilna iztijra predhodno vpisanega podgrala zagotavlja neprtk in ja'io delo procesorja. Proc&corji (jp|j72«1 se povezujejo v veCprooe-sar&ki iistuiii na dva osnovna naCinat kaskadnl (Slika 2i> in krbi^ni (Slika 2b). Za kroüno bihitÈkturo je v razvoju tudi podporni Cip MAGIC (K^inory Access ì, General bue Interface Chip) . 000 PHOC. li.i )iPD nt U.i (a) C PU M yi* SUKCVNI POMI«. Opravljena testiranja opravičujejo uporabo vefiprocesorske arhitekture z pPD7281. Tako na primer rotacija binarne slike 512 X 512 zahteva O,is pri kroilni povezavi treh procesorjev; en procesor porabi za isto nalogo 1.5 s. Za i:raeun funkcije cos(x) potrebuje en procesor ^Ojis, kaskada treh procesorjev pa ISps. J. Sile in B. RobiC