m informatica < YU ISSN 03505596 SISTEM ZA ŠALTERSKO POSLOVANJE V BANKAH IN NA POŠTAH računatnišhi sistemi dei^a Sistem za šaltersko 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 otidelavo. Deluje lahko povsem samostojno ali v ponzavi z glavnim računalnikom {prenos informacij je mogc^ 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 strojev, pisalnih strojev do kalkulatorjev in deloma mlkročitalni-kov. Sistem za šaltersko poslovanje je savremena računarska oprema za rad u bankama i fX)š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 dsradu. Može da radi sasvim samostalno, ili da komunicira sa glavnim računarorp {prenos informacija je moguć preko stalno iznajmljenih ili običnih telefonskih linija). Rad sistema je takode 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, pisaćih mašina do kalkulatora i delimično čitača mikrofiševa. dT Ld tasopis izdaja Slovenska druitvo Informatika, 610D0 LJubljana, Farnova 41, Jugoslavija ČASOPIS ZA TEHNOLOGIJO RAČUNALNIŠTVA IN PROBLEME INFORMATIKE ČASOPIS ZA RAČUNARSKU TEHNOLOGIJU I PROBLEME INFORMATIKE SPISANI E ZA TEHNOLOGIJA NA SMETAN JETO I PROBLEMI OD OBLASTA NA INFORMATI KATA Urednlikl odbori T. Alekslč, Beograd; D. Bitrakov, Skopje; P. Dragojlovlé, Rijeka; S. Kodiar, Ljubljana; Đ. Horvat, Maribor; A. Mandii ration Computer Architectures 33 PosBlbllltleB Offered to Hicroelectronic Systen Designer 44 The Interconnection Network in a HultlpcocesBor Syste» 51 Ship's Information System and Loading by Computer 60 The Parallel Character Recognition System 68 PLOTS - A Simple Software for Graphic Terminals and Plotters 74 Dsts Flow Architecture Baaed Processor 81 Transputer - The Basic Component of Multiprocessor Systems 85 New Telenatic Services Environment and ISDN 90 Advanced Hicroprocessors... (A Review) 97 Letters LOGIKA I PROCESIRANJE ZNANJA UDKoo1:681.3.04 Mario Radovan Sveučilište Rijeka, SET Pula Univarza Ljubljana, US Ljubljana u ölanku J» dat* analiza nogućnosti koje logika pruta u okviru problsaatiks prodstavljanja i procesiranja »nanja. Rezultati fiu sabrani u oj«lovit prijadlog nodela logičke baze 2nanja, koji je definiran u tersinina logike i realiziran Brad«tviua logičkog prograniranja. U kontekstu predlotenog nodela dati iu i prijedlozi rjeÈenja dvaju probleaa nepotpunosti sistema klautalna togike sa SLDKF-reaotuoijon kao aetodoB dedukcije. Inanja su podjeljen« na pozitivna, negativna te deiinioiju hijerarhijo entiteta u bazi. Dati su natini predstavljanja tih znanja i njihova uloga u procesu dedukcije, nasljeđivanja svojstava i odriavanj« integriteta bate manja. Model je inplenentiran u Prologu, a rad sistena ilustriran je priejeriaa. Pokazan je nafiin obrazlaganja uspjelih kao i neuspjelih pokutaja dedukoije Cizraöunavanja) odgovora na upite postavljane sistemu. LOGIC AND KNOWLEDGE PROCESSlNSi The artiole presents an analysis al the po-Esibilities which logic offers to the Probiens of representing and processing knowledge. The results are collected in a propoaal of an integral aodel ol a knowledge base, defined in terns of logic and realised through logic progra-nning aeans. Uithin the nodel, solutions are propcsad for two inconpleteness problems ol systems of clausal logic with SLDNF-resolution as a deduction nethod. Knowledge is classified into positive and negative knowledge and defini' tians cI hierarohies of entities in the knowledge base. Uays of representing these types of knowledge and their role in ttie process of deduction, property inharitanoB and naintanance of the integrity of the knowledge bass are given. The aodel was iaplenented in PROLOG, and a few exanples of its behavior are included here. They illustrate the Banner in which the attempts ai deducing (coaputing) the answers to queries are explained. 1. UVOD Cesto se istifia da je problen predstavljanja znanja centralni problen tehnologije znanja, a time i raivoja sistena zasnovanih na znanju, odnosno ekspertnih sistena. U ovon filanku dat Je prijedlog sistena za predstavljanja i procesiranje znanja, koji sno nazvali nadelon logiCke baza znanja. Model je definiran u terniniaa natenatitke logika odnosno lagiùkog prograairanja, kao osnovnog sredstva ali i jedinstvenog aetodoloSkog pristupa problenatioi predstavljanja i procesiranja znanja. Odlikaaa logike (prvoga reda>, a tine i razloziaa za njenu priujenu, u daton kontekstu ■ natrano i - Deklarativnost seoantike jezika logike. Znanja izrađena u jeziku logike iprvoga reda) direktno su "čitljiva", za razliku od znanja predstavljenih u proceduralnin jezičina, gdje se "tto" (tj. logika) - zagubi u "kako" (tj. proceduri).. - Precizna sintaksa i senantika jezika, čine sa izbjegava problen viSeznafinosti, svojstven prirodnon Jeziku. - Postojanje aetoda za autoaatsku dedukciju (izračunavanje) ispravnih odgovora iz datog skupa prenisa (tj. baze znanja), datih u (pod)Jeziku logike prvoga reda. Iako je logika prvoga red* potpuna (tj. svaka logička konsekveno* skupa prenisa je i deduoibi-Ina), ne postoji (općenit) algoritaa kako tu logičku konsekvencu deduoirati. Kao rezultat traženja jezika, za koji postoji efikasan algoritam za Cautonatsko) deduoiranje logičkin kcnsekvenoi iz datog skupa premisa definiran je jezik prvoga reda koji sno nazvali jeiikoa definitnih klauzula. DEF 1.1. Oefinitnom klauzulo» nazivamo fbraulu oblika \ h 61 b & Bn gdje je A atom (tj. atoaarna foraula), a 01.....Bn su literali (pozitivni ili negativni). Pritoa atea A nazivano glavom (head) klauzule a konjunkciju literals Bt, ..., Bn tijelom (body) klauzule. Oefinitnu klauzulu oblika A < — nazivana činjeniooa. Pojam definitne klauzula uveo je van Endea u , ali u ule» značenju pojaa (bez negativnih literals u tijelu), nego Sto to ovdje činimo. f Razlog za pocsbno bavljenja jazikoa dafini-tnih klauzula Joste u tosa ito ta klauzula) porsd uobičajene deklarativna sanantike (inafia-nja, "fiitanja"), iaaju i prikladnu prooaduralnu saaantiku, ito ih £ini pogodnla da budu uzete kao jezik za predstavljanje znanja, ali ujedno i kao koepjutacijeki jezik, Maine, delinitnu klauzulu A BI 1 . . . J, Bn <1> aotau deklarativno shvatiti (Sitati) kaa pravilo koje kale da istinitost litarala BI, ..., Bn implicira istinitost ataaarns larmule A. No, istu klauzulu Boieno interpretirati i proceduralno, tj. kao Lnstrukaiju, koja katai zadatak A izvrtavano tako da izvrtino sva zadatke BI, Bn. Klauzulu oblika Al V . ..V Aa <— BI & . . . i Bn <2) nazivaao nedatinitnoa klauzulon. Deklarativno, klauzula C2} kazuje da istinitost (svih) lite-rala BI, ..., Sn iaplieira istinitost bar jadnog (aa da ne znano kojeg i kolikih), literata' od Al, Aa. Mađutiua, procaduraln« interpreta- cija, a posebna iaptenentaci ja autoDfateka dedukcija kod nadaCinitnih klauzula Je znatno kritičnija. Tako npr. u <¥ah a5> nalazioo lakljuCak da je nadefinitnost klauzula "vrlo nepoželjno svojstvo", zato Sto predstavlja znatno koapleksniji problea za autonatsku dedukciju. DEF 1.2. Zapis Cforaulu) oblika <— BI 4 ... i Bn I.., Bn litorali, nazivano gdja su BI, oiljea. Fornule navedene u datinioijaaa <1.1> i (1.2) jesu zapravo sano natrice lornula logike prvoga reda, koje bi zajedno sa inplioitno niti jenin kvanti!ikacijskin prefiksina glasilet a) dafinitna klauzula iz definicije (1.1) i VkI ... VujtA <— 61 & ... ti Bn) odnosno, fiinjenioai VmI ... Viij(A) gdje su xl, ..., xj sve varijabla koje se Javljaju u atonu A i/ili literaliaa BI, ..., Bn. Dakle, svaka varijabla, koja nastupa u definitnoj klauzuli, implicitno je vezana univerialnia kvantifikatoron. ta> cilj iz definicije <1.2), tj.i <— 81 & ... L Bn eitaaoi "nije istina da BI i ... i Bn". Dakle, VkI ... V)iJ, gdje Je 6 zapravo negirana tvrdnja iz oilja. U praktiCkiB terniniaa rečeno, SLDNF-resoluciJa, kao natoda autonatske dedukcije, provjerava deduoibilnost nekog cilja 6 iz datog skupa prenisa . Ukoliko takav dokei . Opie same prooedure SLDNF-opovrgnuäa ireso-luoije) dat Je u , gdje su ujedno date definicije teneljnih pojmova iz logičkog programiranja, koje ovdje' koristiao. 2. 0 POTPUNOSTI SLĐNF-RE80LUCIJE Sistem klauzalne logike smatramo potpunim ukoliko ja za dati skup premisa 8 i cilj fi, svaka ispravna odgovor supstitucija ujedno i izračunata (odnosno izračuniJiva) odgovor supstituBiJe. U , Str.64 - 6S, naUiima primjer skupa definitnlh klauzula (premisa)i (e) p(K) <— (b) q(a) < — (o) r(b) <— i oiljai <-- p ispravna odgovor supstituoiJa, ali ne i izračunata odgovor supstitucija. Dakle vrijedit oonp(S) I- p(b) & n(q(b)) (2) ali na upit (1) ne uspjevamo dobiti izračunatu odgovor supetituoiju , ii čega bi proizatlo da u klauzalnom sistemu •• SUDHF-resolucijom kao metodom doduciranja, ne vrijedit S I- p(b> & n(q(b)). (3> ObrailoliBo ukratko tvrdnja (2) i (3>. Iz dalinicija jezika definitnih kUuiul« ofiito ja d« ii aana taorije S ne note biti deduclbllan ni jadan nagativan literal. Stoga ja pri SLDNF-rasoluoiji je za dadukoiju negativnih litarala usvojana neaonotona pravilo izvođenja nazvano "negacija kao konaäan neuspjeh dedukcija" (negation ae finite failure - HF). Prana tan pravilu, ako ja za dati skup klauzula S i oilj '<— p' pripadno SLDNF-drvo kanaöna i baz ijedne grane uipjaha, onda zakljuCujeno S I- n

. haJutia, kako casa taorija 8, dat« u klauzalnon jeziku, ne noie leati negativne litorale za logičke posljadioe, pouzdanost pravila 'Uf "spaiava" ss uvoJenjan nadopune (conplatition) caap(S) za taoriju S. Srubo reiena, oonip (S> nastaja iz teorije S tako da sve Sto ii S nija daducibilno dodamo teoriji kao negirano (tj. naistinito^t za fornalnu definioiju cd*p(S> vidi npr. ) Prema 'teorija - Bodel' paradigBi u kontekstu, problematika predstavljanja znanja, akup klauzula snatrano teorijon kojom taliBo opisati neku strukturu kao dio realnog Ili hipotetiökog svijeta. ObziroB da u toa slučaju pri formiranju teorije znamo o Cbbu govorimo ~ tj. struktura je unaprijed data - izrafavanje znanja pomoću netameljnih fiinjanioa ne ■«•a da dovodi do nepotpunosti deduktivnog sisteBa, već izgleda i. napriBjernim, Naima, mi promatranom klauzulom 'p(K) <—' zeoijelo nismo laljeli izraziti znanje da "svi" posjeduju svojstvo p, veä da to svojstvo posjeduju "svi iz strukture" koju teorijom opisujemo. Utoliko i znanja izratano klauzulom 'p(K> <—' Boieao - bar sa aspekta predstavljanja znanja - adekvatnije predstaviti u alijadećoj formii p(x) <— element,atruktureCK) tj. "Svaki element, ako je iz domene struktura onda posjeduje svojstvo p." (U predlotanos modelu logifika baze znanja uCinJano je to na prikladniji ali analogan naCin.) S druga strane, vrijedi i S I- p i (S) zajedo, potvrJuju tvrdnju (2> o ispravnoj odgovor supstituciji <)i/b> za oilj (1) i dati skup premisa E. Pokazani nadin transforBaciJe netameljnih činjenica u pravila navodi nas na definioiju podjazika jazika definitnih klauzula, u kojem óa spomenuti prinoip ved vrijediti. Takav Jezik nazvali sno ovdje jezikom regularnih klauzula. DEF 2.1. Definitnu klauzulu Pogledajmo sada zaüto SLDNF-resaluoija tu ispravnu odgovor supstituciju ne uspjava izračunati. Preaa definiciji SLONF-derivacija, ako literal 'A' iz negativnog litarala 'n(A)' iBa opovrgnuče (a u naiaa primjeru je to litara! 'qtic)' i ima opovrgnuće ! ), onda se iz eilja 'n(A>' ne derivira novi cilj. Utoliko i na Bofano Etiöi do prazne klauzule za polazni cilj '<— p.(ii) & n(q(ii)>' (tj. do opovrgnuča i izračunate odgovor supstitucije za taj oilj), već pokutaj SLDMF-opovrgnuća Ctj. izračunavanja odgovor supstitucije), zavrtava neuspjehom. A odatle i slijedi iznad izneCena'tvrdnja C3), o nededuoibiInasti prosatranog oil ja. U nastavku dajana prijedlog rjaftenja tog problema. Snatraaa da razlog nemogućnosti izračunavanja ispravne odgovor supatituoije u pro-natranom primjeru leii u klauzuli 'p(K) <—' iz skup« premisa B. Naima, Činjenica je ali nija taaeljna, jer aadrli varijablu x, te sa utoliko njanim uspjeinin rasolviranjem (i«ta) varijabla K iz negativnog litarala 'n(q(x))' nije instan-oirala. Nadalje, obzirom da SLDNF-derivaciJa pri resolviranju sa negativnim literaliaa kao najopćenitiji unifikator užina supstituciju identitete a, nije ni moguće očekivati da za postavljeni upit (1> izračunata odgovor supstitucija bude {x/b>. A <~ BI i ... & Bn nazivamo regularnoa ukoliko zadovoljava slijedeće uvjet«) a) Ako je n ° 0, tj. klauzula je ćinjenica, onda ja to teneljni atom. b) Ako ja n > 0 ondat 1) svaka varijabla koja sa javlja u glavi klauzula Javlja ee i u bar Jednom litaralu tijela klauzulet 2) svaka varijabla koja se javlja u negativnom literalu Bi tijela klauzula, javlja sa i u bar jadnom pozitivnom literalu BJ tijela klauzula, tako da literal Bj prethodi litaralu Si. DEF 2.2. Cilj <-- Bt & ... fc Bn je regularan ako svaka varijabla koja sa Javlja u negativnoa literalu Bi iz oilja, javlja se i u bar Jednom pozitivnon literalu Bj iz oilja, tako da literal Bj predhodi literalu Bi. Obzirom da problea leži u klauzuli 'p(x> <--', za samu problematiku predstavljanja znanja vaino je pogledati ito ta klauzula zapravo "znaći" (predstavlja-, kazuje) . Striktno govoreći, ta klauzula ne "kazuje" nitta, već ja to samo dobro oblikovana klauzula (formula), prena definiciji (1.1). Do uobičajenog značenja ta klauzule, tj. "svaki x posjeduje svojstvo p" ili pak "la svaki k vrijedi p - arnia, naravno, supstitucija . ix/tì - Je i Ispravna odgovor supstitucija. Naime, obziron da činjenice q(o), qCd), ... nisu deduoibilne iz sk'Upa prenisa B, daduoibilni su negativni literali nCqCo)), nCqCd)), ... (A) S druge strane, il (neregularne) činjenice 'p(x)' slijedi i p(c), p, (7) Prana CA) vrljadl dakla, 1 a tina - ii (7) i (6> - slljadi da au aupati-tu-cija <>(/o>, , ... ispravna Cali opet n« i lira&unats> odgovor •upatitucija. Ù jsiiku regularnih klauiula, proaatrani pri-■jar izrazili biaao na alijedaći naöini p(x) <— olB«ent„»trukturB(K) qCa) < — q) < — Bla«ant_etrukturB(a) <— • l»Mnt_strul, koja la isto znanja - tj. prsaiss, ali Izralana u Jaziku datinitnih klauzula - nija bila izrafiun-IJiva, sada jasta iirafiunata odgovor supstitu' oija. Stoviia, pralaskon na ragularnu larau klauzula i ciljava, supstitucija , , ... , vita nisu niti ispravna odgovor supstitucije, niti iiraCunata odgovor supstitucija. Ta pak driino isto tako pavaljnia (i polaljnia) • faktoa uvo SaatraBO da regularnaklauzula (b) naprosto adakvatnija (prirodnije) izražava nate znanja o strukturi M, iiraiano u prirodnon jsiiku rafia-nicoa "Sva iiva bića dittu'*. S I- pCa> No, pradstavlBo II foraulu iz skupa S u klauzal-noj lorai, tj. hao kalauzulu p(a> <~ n(p(a)) (10) onda iz t« klauzule Cuzete k«o praaisa), preaa SLONF-resoluoiJi, 'p(a)' nija deduoibilnoi No, avaj sluCaj (oblik) nepotpunosti bitno •a razlikuje od ranija razaotranog CLloydovog) aluCaja. Kaiaa, dok Je u prijatnjea priajeru pokutaj dedukcije bic kona£an, dajudi pritoa pograian odgovor "ne", cvdja pokutaj daduoiranja Oilja 'p(a) < —' (tj. pokutaj BLDHF-opovrgnuä« za taj oil j i klauzulu (IG)), uopće ne zavrtava, jer ppipadno BLDNF-drvo nija konačno. Naiaa, pokutaj dedukcija oilja '<— p(a}' dovodi do generiranja izvedenog oilj« '<— n(p(a>)', koji se opet svodi na pokutaj dedukaije cilja '<— p(a)', ltd. Pored sasa naobidnosti znanja, koje iiratava (interpretirana) loraula iz skupa (S), tj. dai Ako entitet 'a' ne posjeduje svojstvo 'p' onda entitet 'a' posjeduje svojstvo 'p'. očito Ja da se ovdje radi i o oirkularnoa naCinu definiranja i iirafavanja znanja. Jer svojstva 'p' za entitet '«' definirano Je u terainiaa tog istog svojstva za taj Isti entitet. Prijedlog rjatanja problaBa konafinosti SLDNF-drva (i koapJutaoiJa), dat j« u . Praaa toa prijedlogu, sva svojstva (predikatni «ioboli), koji «e javljaju u teoriji (tj. skupu klauzula e>, razvrstavaju sa u hijerarhijske nivoe. PritOM, u tijelu klauzule iz skupa fi saiju nastupati saao svojstva Cpredikatni siab-oli) koji su nileg nivoa od svojstva koje sa Javlja u glavi klauzula. U tom slučaju oirkular-nost definicije u skupu klauzula S je sasvla onanogudena, tako da Ja svaki pokufaj SLDNF-opovrgnuäa (tJ. izračunavanja odgovor supstitucije) konačan, i zavrtava uspjehoa ili nauspijehoa. HeJutin, takvo ograničenje postavljano na jezik skupa prenisa (klauzula) - iako garantira konačnost kompjutaoiJa - izglada isuvita restriktivni«. Naiae, njiae se isključuje aogudncst rskurzivnog definiranja (opisivanja), koje pak smatramo izrazito značajnia za pradstavlJanja manja. Ilustrirajno to priajeroa. Neka znanja, koja laliao predstaviti u jaziku regularnih klauzula budei Krvnu grupu nasljeđuje se od oca (tt) U , str. 220, dat je priajer (drugačija prirode), kojla se pokazuje drugi slučaj (vid) nepotpunosti SLDNF-resolucija, kao aetade izvođenja u aisteau klauzalna logika. Pogladajno taj slučaj. < n(p(a)) --> p(a) ) (8) Logičkoa transi arsaci Jod (jedine) fornule iz skupa 3, dobivana { n(n(p(a))) v pCa) > a odakle i {. pCa) } U jeziku regularnih klauzula to aoteao učiniti sa : krv_grupa_od(K,y) <— otao^od(x,z) t krv_grupa_od(z,y) (12) U jeziku logičke baza znanja, sintaktički sao poljaptali jezik regularnih klauzula, tako da bL manja (11) bilo predstavljeno kao praviloi krv_9tupa_od(X«¥) ako Qtaa_od(XtZ) i krv_ofupa_od(Ii¥) (13) U jeziku sa hiJerarhijskia ureJenJea pradikatnih fiitnbola takovu tvrdnju na bisao aogli izreći. Jar sa pradikatni siabol 'krv_grupa_od' iz glave klauzula (pravila) javlja i u tijelu klauzule, Ste hijerarhijsko uređenje svojstava Cpradikata) ne dopufita. No, nogudnost rekurzivne definicije iiglsda isuvite značajna da bisuo Ju Jednostavna zabranili. Jsr "teoretska fiietoCa" nodela (tj. garantirana konaćnast svakog pokušaja SLDNF-opovrgnuda), koju zabranon rekurzivns daiinicije paetilema, izglada ipak praelabon nadoknado» za izgubljene aparativna nogućnosti baza znanja. ZaklJuCiniD razmatranje ii ovog odjeljka opi-«OB rjatenja utvojenog Ci inp 1 anentiranog> u iaa~ delu logičke baze znanja, koji ovdje predlažeao. Priliko» svaka izajane aadrtaja logičke baze znanja - tJ. upisa/brisanja pravila/činjenica - (autoaataki) se provjerava da li Je tine stvorena nogućnost postavljanja upita CtJ. oilja) za koji bi pripadno SLDNF-drva iaalo beskonafinu granu. Ukoliko je takova Bogudnost zaista stvorena, onda već u toku same provjere postojanja te mogućnosti, dolazi do prekoraCenJa raspolo-iivB Bcmorija na sistemu, tto nan ujadno i sluti kao znak postojanja beskonaCne (ili baren operativna prevelike) grane. U inplenentaciji aodala logifika baze, ilustriranoj prinjarina u odjeljku razvijena ja naredba 'loop*, po- Boäu koje prilikom nastupa prakoraäenja, od sistema dobivano odgovor'koji Je to cilj za koji bi, u aluriranaj bazi tnanja, pripadno SLONF-drvo inalo beskana&nu granu. Na slijedeći upit - 'sh.loop' - Bisten eksplicira (pokazuje) tu granu (odnosna, pokulaj SLDNF-opovrgnuĆa, koji ju slijedi), i to do dubine koju sani zahtjevano. Tada Je na kreatoru baze znanja (koji upis/brisanje vrti), da odluei je 11 zaista rijae o "oCito beskonačno'j" grani SLDNF^drveta, (tJ. oirkularnoj definioiji), ili pak bi bilo vrijedna ponoviti pokutaj SLONF-opovrgnuda sa vaöon raspoloiivon neno-rijon. Ukoliko potonje nije slufaj (a u pravilu nijal), onda se zahtjeva pretorkulaciJa znanja u bazi, tako da se cirkularnost izbjegne, a tine i postigne konainost svake noguće grane SLDNF-drveta odnosno svakog pokuSaJa SLDNF-opovrgnuöa za neki dati cilj (upit) postavljen skupu prenisa (tj. logiCkoj bazi znanja). Problem cirkularnosti daliniranja je jedan od valnih (i otvorenih) problana logifikog pro-graniranja, posebno u kontekstu značaja koji tna rekurzija (ali i potpunost!). Orlino, da ovdje dato operativno rJaCanJe jest« zadovoljavajuće, posabno u kontekstu problanatike predstavljanja i dedukcije znanja, Naine, njine se zadrtava noguAnost rekurzivnog definiranja • ujedno i snjesta otkriva i eksplicira eventualno postojanje beskonaćne (točnijei prevelike) grane. Viie od toga (osin isuviie rigoroznln restrikcijama jezika!), u kontekstu neodlučivo-fiti logike te primjene pravila "nagaoija kao konaCan nauspjeh dedukcija", ne izgleda dosefnia. 3. hödel logičke baze znanja Modelon logičke baze znanja dat Je cjelovit prijedlog nafiina predstavljanja znanja u Jaziku logička baza znanja, sa SLDNF-resoluoijom, kao netodon deduciranja (odnosno izračunavanja) odgovora iz baze. Da bi (larnalna) dedukcija u bazi (implicitno) sadrlanih znanja bila noguća, noraju znanja u bazi hiti data u Jeziku precizne sintakse i senantike. B druga strane, obziran da sa u ton Jeziku izratavaju znanja koja potjeCu od čovjeka i Čovjeku slule, poleljno Je da taj jéxik bude ujedno i blizak prirodnom Jeziku. Stoga sno jazikoa logičke baza nazvali jezik regularnih klauzula u kojen su izvrtene iimjana na nivou sintakse (točnijei abecede), i to sa ciljam da se jezik učini bliii prirodnom Jeziku. U tu svrhu smo logičke simbole iz jezika regularnih klauzula zanijenili njihovin uofaifia-JeniB ekvivalentima (interpretaciJana) u prirodnom jeziku, U nastavku čeno, kad« bude riječ o 'znanju', govoriti u terniniaa i notaciji jezika logičke baze znanja. Kada pak budenc nad tim 'znanjaa' izvodili neke logičke transformacije (dedukoijei dokaze), činiti de«o to u notaoiji i terminologiji jezika regularnih klauzula. U jezik logičke baze znanja uvodino i disjun-koiju, i to na slijedeći načini Neka su 'glava' ako 'tijoIo_l' (1) 'glava' ako 'tijolo_2' (2) pravila iz.Jezika logička baze znanja. Tada ja i 'glava' ako 'tiJelD_l' ili 'tijelo.2' (3) pravilo jezika logičke baze znanja. Drugin riječima, disjunkciju u Jezik logička baze uvodimo kao skraćenu notaciju za dva (ili vite) pravila sa identičnia glavama. Da je zaista riječ sano o notaoijakoj varijanti stijdi it toga Ito je konjunkoija pravila (1) i (2) logički ekvivalentna pravilu (3). Za predstavljanje atonarnih znanja predlateno slijedeću shenui Svojstvo(Entita11 Vrijednost) (4) U sheni 'Svojstvo' ima istu ulogu kao i dvo- ■Jesni predikatni sinbol u logici prvega reda, odnosna 'ine relacije' u relacijskoj shemi. U , unjesto izraza 'svojstvo' koriSten Je izraz 'opis' (description), uz naponenu da taj izraz "zvuči suviie sintaktički". U stvari, drtino da bi na nivou samoga Jezika (sintakse), termin 'opis' iigladao pri kladniJ in, dok na nivou nodela (struktura), koju tin Jezikoa opisu jeac, adekvatnijin izgleda ternin 'svojstvo'. abziroB da Je cilj logičke baia manja (kao teorije), da opite unaprad danu strukturu, notano snatrati da su predikatni siBboli iz jezika već a priori interpretirani, te naa govoriti u tarainina 'svojstava' izglada prikladnijin. U ulazi 'Entiteta' aafa se pojaviti bilo koji poja* koji označava neki entitet iz strukture, kojeg lelino opisati u terminina pridruženih nu svojstava i pripadnih vrijednosti. 'Vrijednost' ix sheae izralava vrijednost prosatrancg svojstva za dati entitet. Vrijednost ncle biti izralena nuneričhi' ili nekim atributon (pojnon, jeiičkln izraion). Na prinjer u broJ_kotaCa_od(auto*4) vrijednost svojstva 'brcj.kotača.od' xa entitat 'auta' data je nunerlčki, 8 druge straha, u prinjerina putB&(petart strastven) putaÖClvaniunjeren) vrijednosti su date jezičhia Izrazima. Analitcn razloga upotreba upravo (i saao) binarnih predikata (svojstava) ovdje •• na bavino) prikaz osnove te prcblenatika dat Ja u . 3.1. Sadrlj baza znanj« Šadrlaj logitk* baia znanja sačinjavaju tri koaponanta i - pozitivna znanje - hijerarhija entiteta - negativno znanja Sv0 tri konponante Sin« infarnaoi Jek i eadrlaj logifike baze, tj. «adrtavaju i«kaze baze znanja, thvadena kao logifike teorije. Podjela «adrlaja baze u tri koaponente uvjetovana Je kako aaaoa railieitoCću iakaza (znanja) tako i EpeoifiCno-■tisa SLDNF-resaluaije, kao aetada daduciranja poaadu koje *a genariraju (daduciraju) odgovori iz baze znanja. a) Pozitivna znanje Pozitivno znanje saCinjavaju ona znanja koja su iirazljiva praviliea i öinjenicana iz jezika logifike baze znanja. Tako bisao na prinjer (hipotetiCku) zakonitosti Svatko nasliJeJuJe boju oöiju od najke u Jeziku logiCke baze sogli predstaviti (izreói) praviloBt boja oai ad(XiV) ako aajka od(XiZ> i taoJa.oei.odCZiV). (5) Nadalje, Ainjenice poputi Ana iaa sae^e oći aoleao u Jeziku logitke baze izraziti sai boja_oei_adCana)SBB4a). Inanja, koja na analogan naäin izratavano ponoiu pravila i Činjenica u jeziku logiAke baze, nazvali sao pozitivni« znanjiaa. Ta znanja iskazuju neka svojstva entiteta, tj. iskazivanjen takovih znanja entitetima pridFUiujeBD svojstva sa datia vriJednostiaa, 6iaa se entiteti pozitivna određuju. Napoaeniao da sao u pravilu (S), u skladu sa zahtjeviaa standardnog Prälag interpreterà u kojea je aodel inpleasntiran, varijable predstavili valikia sloviaa (X,V,Z). b> Hijerarhija entiteta Hijerarhijska struktura definirana ja tzv. tipizacijoB entitet«, öioe je stvorena nogućnost nasljeđivanja svojstava aaJu entitetima u strukturi. Entiteta tipiziraao upotrebo» svojstva 'vrsta.od'. Na prlajsr, Činjenicu (pozitivno znanje) dai Ivan Je «ovjek (6) predstaviti äaao u Jaiiku baze einjanicont vrBta_od, nedaao iiralavati u terainima svojstva 'vrsta.od', već npr. sat zaniaanje_od(ivanivozafi> Pored svojstva 'vrsta.od', na hijerarhijsko uređenje entiteta odnosi se i svojstva 'je', kojaa Ja ovdje dato nezavisno i raztieito zna-Senje od svojstva 'Je', koriitenog u loraalizau senantiCkih arata. Ovdje Je to svojstvo definirana za svaki entitet e iz baze tnanjai b) je(alie2> ako postoji takcv entitet e3, da 'vrsta_od(alie3>' i 'jeCe3iB2>'. Đrugin rije&iaa, svaki entitet 'Je' on saa| isto tako, svaki entitet al iaa svojstvo da 'ja' i a2, ako sa entitet e2 nalazi u hijerarhiji iznad entiteta al. Svojstvo 'Ja' korlstiao kod izratavanja pravila poputi dlta nijB d«finltna klauzula jer Ja to negativan litaral. Mogućnost da se takova (tj, negativna) manja ipak izraza u jaziku logiäke bais Jasta da sa to užini poBDću cilja (upita). Naine, prama definiciji (1.2) i pripadnan obraz 1otanju, fornula (S) ina toćna oblik cilja. Stoga ćsao znanja (7) izrateno (arnulon (8) izraziti rsgularnin ciljem (odnosno upiton ii jeiika logifike baze)i T- boja_o6i_od(X1 crvena) (in Upit (11) jeste regularan jer u njemu negacija uopće na nastupa. latalfniAa ovdje razliku izmetu 'negativnog znanja' i 'neznanja'. Obzira« da Je u SLONT-resoluciji la negaciju već usvojeno pravilo izvodsnja nazvana "konaäan neuspijeh dedukcija", negativna znanja ne bi ni trebalo predstavljati u bazi znanja. Naine, na upit 7 - hoja_oći_od(Xicrvena). (12) postavljen bazi znanja - po SLDHF-reialuci.ji -odgovor de glasiti "ne", obziron da za nijedan entitet o (kao moguću Instancu varijable X), baze znanja nije deducibilnoi boja_Dfii_od(cicrvena). Drugis rijeäima, za (neko dato) stanje baze znanja i upit (11), ne postoji ispravna adgovar supstitucija, pa stoga ni izračunata odgovor supstitucija. Me^utiA, ukoliko bismc u toku razvoja (aturiranja) bazs znanja unijali, na priBjar znanja boja_oći_od(narkoicrvana) (13) onda bi odgovor na upit (It) glasio "narko". No, ako znano da "nitko neaa orvene ofii" (tj. (7) odnosno (S)), onda - u kontekstu toga znanja - znanje (13) nije snijelo biti uneieno u bazu. Jer baza znanja, koja sadrti znanja (A) i (13) jesta - kao logička teorija - nekonsistentna. Naine, iz (13) fai slijediloi Ex(boja_aći _od(Kicrvana)) (H) tto zajedno sa (S) dokazuje nekonsistentnost logičke baze kao teorije, jer je iz nje deduoi-bilno A i n(A), tj. loraule (3) i (14). Kako navedeni prinjer pokazuja, iako je samo 'naznanja' (tJ. neizratavanja znanja) dovoljno za generiranje negativnih odgovora, ono nije dovoljno i za spriječavanje da ae u logiöku bazu unesu znanja, koja to nisu! - tj. gre£ke, poput "znanja" (13). S druge strane, izražavanje negativnih znanja u logiCkoj bazi (u obliku ciljeva (upita)), onogućava da unos (ili uopće deduoibi1nost) pogrebnih "znanja" (tj. gra4aka) učini logiäku bazu znanja (tj. teoriju), nekonsistentnoo. Negativna znanja, izražena poBoću upita, saatrati ćeao stoga uvjetima integriteta logifike baz« znanja. Ta znanja na učestvuju pri saBoj dedukciji odgovora (jer je negacija kao 'konačan neuspijeh dedukcija' za to dovoljna), već 4tita bazu znanja pred tako-vin proBjanana (ažuriranjiaa), koje bi istu učinila logički nekansistentnon. Općenita, uvjeti integriteta, Izraženi kao upiti, iskazauju negativna znanja (lornuta) n(£KlEi<2. , .EkJ Celenenti cilja')) (15) Formula.oblika (15) istinita Ja u strukturi koju znanjen iz logičke baze opisujemo, ako i samo ako ne postaje instanca varijabli h1,x2, .... Mj, za koje bi fornula 'elementi cilja' bila istinita u proaatranoj strukturi. ForBulu oblika (15), tj. uvjet integriteta, općenito izralavaBO u bazi znanja (upitom)) 7- 'elesienti cilja' (16) Tada zadovo1Jivost upita (16) - dakle, bilo koja izračunata odgovor supstitucija različita od "ne" - ujedno laplicira deducibilnost formule 'elementi oilja', i to za one inetanoe varijabli koje su dobivene kao izraftunata odgovor supstitucija za upit (16). To pak, onda općenito znači i deducibilnost formulai Eii1EK2 Exj ('elementi oilja') (17) eto zajadno sa forsuloB ('t5> pokazuje nekonsistentnost baze znanja, pronatrane kao logičke teorije. Na taj način je i pojan integriteta baze tnanja konzekvantnd preveden u logičku terminologijUi i sveden na pajan konsistentnosti taorij«. PriDjeron logičke baze znanja, dato» u odjeljku (A>, ilustrirani su neki od magudih načina i slučajeva izražavanja negativnih znanja kao uvjeta integriteta. Radi ilustracije, saaoga principa predstavljanja znanja ponoću uvjeta integriteta, pokažimo ovdje kako nofemo njihovo« upotrebom adekvatno i jednostavno riJeSiti (laBozni!) pro-blen predstavljanja inanjai Sve ptice lete oeiB pingvina (18) Pozitivno znanje sadržano u rečenici (18) - tj. da sve ptioe koje nisu pingvini, lete. - izraziti čBBO u jeziku logičke baza pravilom iBti(Xida) ako Je(Xiptiea> i ni_ja(X« pingvin), (19) Pri tone je svojstva 'ni_je' (po definiciji) ekvivalentno negaciji svojstva 'je' (tj, 'nije je') - a dato Ja kao način sintaktičkog uljepšavanje jezika. Negativno znanje, tj. da "svaka ptica, koja Je pingvin, na leti", počanioo» (Itt) nije zapravo niti izrečeno, ali - kao tto Je to često slučaj u prirodnoB Jeziku - padrazuBijeva.se. Naravno, prinjanon pravila (19), znanje leti(pingvintda). (20) neće nikad biti deducibilno. Ma^utiB, sano pravilo (19) ne noža spriječiti da (20) postane deducibilno na neki drugi način. No, nožanp to učiniti tako da negativno znanje, tj, "pingvin na leti", izrazimo uvjetom integriteta (upitom) 7- leti(pingvinida). (21) Ažuriranja baie znanja, koje bi dovelo do dedu~ oibilnosti "znanja" (20), učinila bi ujedno ' zahval jujudl 'negativnon znanju' (21) - da baza znanja postane nakonsistentnoB, kako je to iznad opisano. Stoga sistea logičke baza takovo ažuriranje i na doputta. To pak znači da čeao - prena pravilu (19) - za svaki entitet koji "je ptica", osiB za one koji su pingvini, aoči daducirati "da leti". S druge strane, uvjet integriteta (21) onenogućavati će svako ažuriranje baze zna- nj«, koja bi inalo la posljadicu da "lati pingviTi" poatana daducibilno. 3.2. Nastjeifivarija svojstava Ovdja Čamo ilustrirati mogućnosti itralava-nja manja, tj. pripisivanja svojstava antitati-na, iz hijerarhijska struktura, tako da ta svojstva nasljaJuju ili na nasljeđu ju podraJani sntitati u struk'turi, u zavisnosti od naSina na koji su ta manja izrafana. U tu svrhu analizirati ćeso kako, uz ađskvatno izražavanja znanja, logički konsistentna baia Boia sadriavati skup znanja poputi ljudi vola livotinja ljudi na vole zmija zaija su livotinja (22) (23) (24) Znanja C22> notawi - kao i obiCno, kada J« ( prirodnon jaziku rijaCt - shvatiti a onda i forsalno (pracizna) izraziti u jaziku logiAka baza, n« vita različitih načina. U&inino to najprije činjanico«« volitčovjakilivotinja), (2S) Činjenica <2S) interpretira znanja (22) kao« Entitet '£ovjak' (kao klag«) voli entitat 'Üvotinja' (kao klasu). (2 Cinjanicoa (26) nisao nitta ustvrdili o pojadi-nie Ijudiaa (tj. antitatiaa koji su 'vrste' čovjak), niti pojadinia tivotinjana. Madatja, znanje (22) motano shvatiti i na način kako je to precizno izrečeno alijadadin pravilom! voliCXiŽivotinja) ako Je(XsCovjak). Tiae je znanje (23> interpretirano kaot (27) Entitet 'čovjsk' (kao klasa), a i svaki po-jadini njegov podentitet (koji 'ja' čovjek), voli entitet 'Životinja' (kao klasu). (2S) Interpretacija (2fi) znanja (22), izrađena pravilom (27) isto tako ne kazuje nifita o pojedinim antltetiiaa koji su podantiteti entiteta 'livotinja'. Konačna, nogući bio bi i slijedeći) anja (22) Entitat 'čovjek' (kao klasa),a i svaki pojedini njegov podantitat (koji 'ja' čovjek), voli entitet 'životinja' (kao klasu), a i svaki pojedini njegov podantitat (koji 'ja' livotinja'). (29) Interpretaciju (29) pozitivnog manja (22) mo-lemo u jaziku logička baze izraziti pravilomi voU(XiV) ako je(Xieovjek) i jB(V. <30) Negativno znanje (23) mogli bismo isto tako interpretirati na vi$e načina. No, odaberimo ovdja samo slijadači načini Nijedan entitet koji 'je' čovjek ne voli nijednog entitet« koji 'je' zmij«. (31) Znanja (23), interpretirano kako ja dato u (31), izraziti ćemo u logičkoj bazi upitomi 7- volKXiY) i Ja(Xieayjek) i ja(VizBiJa>. (32) I na kraju, znanje (24) izraziti čema činjenicont vrsta_od(zi«ij«i livotinja). (33) Interpretacije (26) 1 (2S) manja <22), iz-ralene činjenioon (25) odnosno pravilom (27), u logičkoj bazi znanj«, koja usto sadrli negativno znanje (32) i znanje (33), ne dovode do nekonsiatentnofiti baze znanja. Kaim«, negativnim znanjem (32), svakom entitetu koji 'je' čovjek, odriče se svojstvo 'voli' sa vrijednošću koj« 'je' iiolja, Mo, niti činjenioa (25) niti pravilo (27) ta svojstvo sa takovom vrije-dnofidu ne pripisuju entitetu koji 'je' čovjek. S druge strane, intarpretaolJa (29) znanja (22), izralena pravilom <30), dovodi do nekonsistentnosti logičke baze znanj«. Ta je (i ne-icrnalno) sasvim razumljivo, obzirom da se negativnim znanjem (32) iskazuje da nitka tka 'je' čovjek ne voli nikoga tko 'ja' zmija, dok se pravilom (30) iskazuje da svatko tko 'je' čovjek voli svakga tko 'Ja' livotinja, pa prema tona i zmiju! Sa naveden« tri načina interpretiranja (shvaćanja) znanja (32) izralenog u prirodnom jeziku, ieljell sno Istadi nulnost precizne (i adekvatna) interpretaoiJa 1 formalnog predstavljanja znanja iz prirodnog jezika u jeziku logičke baze znanja. Cinjenioa da znanje (22) noleno interpretlati na vite načina, od kojih neki dovode i do nekonsistentnosti, ne znači da čovjek normalno komunloira i zaključuje na osnovu nakonslstantnog skupa znanja (premisa), kako se to ponekad tvrdi. Mnijenja smo, da čovjek vrlo uspjeino i adekvatno interpretira znanja izratan« prirodnim jezikom (i to naj-Čeiće u zavisnosti od nekog datog konteksta), a ne da zaključuje iz nakonslstantnog skupa pranis«. Pradlolenlm načinima pripisivanja svojstava i vrijednosti entitatima, kako ja to opisano u ovom odjeljku, ieljeli SKO omogućiti izražavanje znanja, na način koji bi adekvatno odrata-vao mehanizam pridrutivanja i (na)nasliJe^lva-nja svojstava kakav (na da nalormalno) postoji u prirodnom jeziku. 3.3. Ekvivslenoija U prirodnom Jaziku ekvivalenciju obična iskazujemo izrazom "ako i samo ako", lako valja istaći da u prirodnom Jeziku ekvivalenciju nnogo čelče mislimo (podrazualJavamo) nego (to ju aksplioitno iskazujemo. U avam odjeljku data ja analiza dviju interpretacija (shvaćanja) ekvivalencije kaa 1 prijedlog načina da se ekvivalanolj« (odnpšn'o, Jadna od njenih interpretacija), izrazi u modelu logičke baze znanja. Račeniau pCK) ako i samo ako q(H) (34) izraziti ćemo u logici prvog« reda formulom p(K) < —> q(x) (3S) gdje Je simbol '<-->' najOetće definiran na metanlvou sistema (dakle, znak '<•' pripada metajeziku), kaai p q(*) <= q --> pCK)> C36) Fareulu <35) na salsBo diraktna zapifidti u J«zlku loqiCkB t>«z« in«rija, jsr ne raspol4žaifia izrczon (sii>balon> 'ako i. sano ako', već sano inplikativnia veinikoa 'ako'. S druge strane, pokuiaj da ekvivalenciju (35) ìzraiino tako da u logiäkoj bali izraiisa desnu stranu definicije (36), tj. regularne klauzulat pf*) <-- q(x) qtn) <— pt») (37) C3a> iato tako ne uspijeva. Naine, u toa sludaju inali bisso afiigledan primjar cirkularne definicije tj, p po«o£u p(x>. Naravna, tada bi npr. cilj <— p(N> (39) lajsdno sa premisama (37> i (3a) imao SL.DNF-drva sa beskonaCnon grsnoa, ito sno vać okarakterizirali kao neprihvatljiva. Na, time nagudnoet iiralavanja ekvivalencije u logiökoj bazi znanja Jafi nije sasvia izgubljena. Kaias, značenje (ulogu) ekvivalencije - posebno u kontekstu predstavljanja znanja - Boteac shvatiti nt dva' raitičita naAinai a) Uspostavljanje «kvivalanoije U ton slufiaju, koji sao nazvali 'uspostavljanje ekvivalencija', ukoliko u skup prenisa koji sadrli foraulu (3S> dodaao Sinjenicu p(a) < — (40) deducibilnoB de postati i fornula (Činjenica)) q(a> <— (41) Peduoibilnost Činjenice (41) slijedi iz klauzula C3S), koja je - prena deliniciji (3è) - "dio" (ili toinijei slijedi iz) loraule C3S>, te Sinjanice (40). Na analogan na£in bi dodavanja Sinjenice (41), poaredstvoa klauzule (37), de-ducibilnoB uäinilo Činjenicu (40). No, kako je već istaknuto, takovo predstavi janje ekvivalencija ne Bote«o pciajaniti u logiCkoj bazi, jar ono zahtjeva prisustvo (ornula <37) i (3S} u bazi, tto pak znaCi postojanje SLDNF-drva sa beskonaönoa granoa. Shvaćanje ekvivalencije preaa Ca'> izgleda čaiCin (uobičajeni«), barea pri hipotati&kon zaključivanju, u koje« ne sunljavo u nijednu od prenisa, pa prena tome nenano ni razloga za njeno odbacivanje. No, kako Ja iznad obraztols-no, takvo shvaćanje ekvivalencije ne nalemo izraziti (predstaviti) u aodelu logiCks baze. S druge strana, u kontekstu probleaatike predstavljanja i procesiranja znanja, zaktjuöi-vanja na naCin kako ja to'pokazano u (b'), aote biti vrlo priajenljiva i korisno. Naine, u raalnia situaoijau, deducibilnoat neka infor-naoije (tj. znanja) iz baze manja aaie biti znak da neka od prenisa nije istinita. Utoliko nan i aogudnost predstavljanja znanja i zaključivanja u skladu sa intarpretacijon ekvivalen-ci je (b') izgleda znaAajnin korakoa u saijeru "vite cd sane inp1ikaaiJa". Pokaiiao sada kako ekvivalenciju izreCenu sa (3S) i shvaćenu u skladu sa (b'>, predstaviJaao u logiäkcj bazi znanja. Kao znanje koje Ceao predstaviti pravilom, odabarimó regularnu klauzulu (37), tjl p(H) <— q(x) Klauzulu (38) - koju pored klauzule (37)! - na saiJeBo unijeti u pozitivan dio znanja logiCke baze, prevesti öaao u uvjet integriteta kako slijedi. Klauzula (38), zajadno sa (iapllcitno aiilJenen) univerzalni« kvantillkatoroa, glasil V*(p(x) —> q(*)) (42) TransfarnaoiJob foraule (42) dobivano VMCn(p(H)) v q(K)) i dalja, n(EK(n(n(p(x>) v q(x)))) )> (43) Fornula (43) iaa toAno oblik slijededeg oiljai <— p(x) & n(q ili - u jeziku loglCka baze - uvjeta integriteta: ' b) Odrlavanje ekvivalencije Drugi naCin shvaöanja (i predstavljanja) ekvivalencija jeste takav da u logiökaj bazi "jedan sajer" iz ekvivalencije (35) - u skladu sa daCinicijcn (36) - izrazimo klauzulon (tj. iaplikativncn forauloB), dok se "drugi srajar" izvorna ekvivalencija iz (33) odrtava, i to zabranon unosa/bri sanJa onih znanja, koja bi dovela do narufiavanja ekvivalencije koju tvrdi (zahtjeva) loraula (35). U svrhu iskazivanja zabrane upotrijebiti ćaao cilj (upit), tj. uvjet integriteta. Shvadanja ekvi va lanci je iznesena u (a) i (b) pokutajno dalje eksplicirati slijededia opisiaat (a') A je istinito ako i easo ako B je istinito. Nije poznato da bi B bila istinito. Ne^utia, poznato je da je A istinito. Slijedit 1 6 nora biti istinita. (b') A je istinita ako i sano ako B ja istinito. Nije poznato da bi B bilo istinito. neiutia, postoji tvrdnja (dedukcija) da A jeste istinito, takljueujemoi tvrdnja A je neprihvatljiva. 7- p(*> i nije q(*). (4s) Uvjet Integriteta (45) zabranjuje da se baza znanja nijenja tako, da iz nje bude deducibilno p(c> za neku instanou o varijabla x, za koju nije deducibilno q(o). Obziran da je uvjet integriteta (45) dobiven logiCkia transfornacijaaa pravila (3&}, Bogli bismo raäi da sac u logiCkoj bazi (ipak!) uspje' li izraziti ekvivalenciju (35). HeJutia, uvjet integriteta (45) aole stanje baza sano kontrolirati (a posradstvoB sistaaa za upravljanje bazoB i autoaatski odrtavati). Btoga se iz njega (tj. njegovin posredstvsB), ne aogu dedu-cirati nova znanja u bazi, pa je utoliko i ■logude ekvivalenciju predstavljati sano u skladu sa njenim shvadanjea opisain u (b'). - Uz prisustvo uvjeta integriteta (45), ažuriranje baze, kojs bi dovelo do deducihilnosti Činjenice p(a) a da pritoB nije deduoibiina i Činjenica q(a) (46) nedopultano j«, jer dovodi do nehonsistentnosti baia kao taorija. Naine, kada <4ò> nije deduci-bilno, deducibiInin postaje - prsna negaciji kaa 'konaCno* neuspijehu dedukcije't n((ii(p tta, zajedno sa uvjetoa integriteta - adna- sna lorsulon (43), kao njeqovie ekvivalantcm u logici prvoga reda, pokaiuje nekon«istentnoat logi£ke baia manja. U priajeru iupleuentacije nadela logiCke baia znanja, izražavanje ekvivalencija ilustrirano je prinjaron predstavljanja slijedećeg znanj*' Metke ja dobra idravlja ako i sano ako je liiiöki aktivan i nije strastven pufiafi. HÒ) Rečenicu odnosno znanje (^S) nogli bisau u baii predstaviti pravilo«! zdraviJe.adCXidobra) ako fiz.aktivan(Kida> i nije pu£aö(Xi«traetven>. i uvjetoa integriteta (upitoa): ( zdravlja od(Ksdcbro) i nija (iz aktlvan(Xtda) ) ili ( zdravlja odCXidobro) i puia£ Prema upitu (SO), integritet logifiks baie bio bi prekrien - a time i baia uCinjena logički nakansistentnoa - ukoliko bi iz nje, la neku instancu c varijable X, bilo deducibilno zdravi je.od(oidobra> (BI) a priton ne bi bilo deduoibilno liz_aktivan(cida) iti pak ukoliko bi bilo daducibilno (SI), ali bi prito« bilo deducibilno i puiaA(ci strastven) Upit (SQ> nije jedini naäin da se dati uvjet integriteta izrazi. Jednostavniji naCin da «e to Udini bio bi sa eliJadaCa dva upitat ?- zdravija_Dd T- zdraviJe.odtXidobro) i puta£(XI strastven). C53> Konjunkcija upita (tj. negiranih egzistencijalna kvantifioiranih foraulal (£2) i (53), logički ja ekvivalentna upitu (SQ). Općenito, upite (tj. uvjete integriteta), kao i pravila izražavati ćeno na način (tj. u obliku) za koji snatrano da najprirodnije (naj-čitkije) izralava neko dato znanje. Priton nije ■itljeno da se do uvjeta itegriteta dolazi (or- malnin logidkim transfornaci Jana, kako je to ovdje ufiinjeno la ktauiulu <38). Nai»a, direktno izražavanje "jednog snjera" ekvivalencije u obliku uvjeta integriteta, izgleda na* dost« jednostavnim, ito potvrđuje navedeni prinjeri (S2) i (53). 3.4. Redundantnost Ekstenzijon baie znanja nazivano skup svih äinjenioa, deduoibilnih iz baia. Za pravilo (ili Činjenicu) kaženo da je redundantno, ukoliko sa njegovim upison (ili brisanjen), eks-tanzija baza manja ne Mijenja. Drugin rijeSina, sve Sto je iz baze deducibilno, deduoibilno Je i bez tog pravila (ili Činjenice). Pravilo (ili Činjenica) nože biti redundantno u trenutku upisai isto tako, redundantni» nože postati zbog upisa ili brisanja nekog drugog pravila (ili fiinjenicel. NaCin provjeravanja redundance u logiökoj bazi znanja ilustrirajno slijsdeóin prinjaron. Neka skup pranisa (tj. baze znanja) S budei p(a) <--qca) < — Pretpostavimo pravila q{x) <— p(*> (54) U notaciji logike prvoga reda, pravila glasii Viitp q(K)) (SS) Fornula (SS) logifiki Ja ekvivalentna lornuli nEx(p(j() & n(q(>i})) (S6> koja ima tcCno oblik upita (cilja)t ?- p(x) i nije q(K) . (S7) Za dato Btanje baze znanja, odgovor na upit (57) glasi "ne". Pri ton odgovor "ne" znaCi da iz skupa prenisa nije deducibilno 'p(c)' za nijednu instancu c varijable la koju ne bi bila deducibilno i 'q(c)'. Utoliko i dodavanje pravita (S4) bazi znanja ne bi pronjenilo eks-tenzju baze, te stog« kažemo d« je redundantno. No, ta ne inaSi da je san« fornula (S4) (ili pak (SS)) deducibilna iz datog skup« premisa, vad samo da njenin upisom - iz date baze znanja - niäta nova ne bi postalo deduoibi1nim. Naravna, naknadna mijenjanja baze znanj« nogu učiniti da redundantna fornula (pravilo) to viie nije, kako je to ilustrirano prinjerina (4) i (S>. Zato i govorino a izračunavanju odgovor supstituoija odnosno o dedukciji na nivou ekštenzije, • ne o (logiCkoj) dedukoiji u inaćenju koje taj pojan ina u kontekstu sistena standardna logika prvoga red«. Ukoliko pravilo (S4) usprkos redundantnosti upifieoo u bazu znanja, onde de Činjenica 'q(a) <—' postati redundantnom. Naime, biti će deducibilna pomoću upisanog pravil« i Činjenice 'p. ILUSTRACIJA RADA SISTEMA U svrhu ilustracije nodela logifike baze znanja, navadimo nekoliko primjera rada sistema za upravljanja logifikon bazom. 1 apienentaoija sis-t.ema izvedena je u C-Prologu. Neka stanje baza znanja bude slijedeće) Znanje dato u okviru daiinioija hijerarhije entiteta u bazi norulno sa alurira kao i ostale öinjenioe. Pritom, svojstvo 'vrsta.od' Caka ja za entitet dato>, mora biti jadinstvana za svaki entitet, o fiemu eist«« xe upravljanje lo-giäkom bazom vodi računa. o) Negativo xnanje U Inplementaolji logifike baza znanja, upiti su imenovani. Imanovanja uvjat« intagritata izvedeno je sa ciljem optimizacije prooeeiranja znanja u baii. Naima, integritet baza provjera' vamo tako da pozivamo upita, kojiaa ou uvjeti integriteta izrateni. No, obziroa da aturiranja tamo nekih svojstava mofa izazvati krianja na-kih uvjeta integriteta, ti se Jednostavno Je iii:adi kaoi Nije Istina da 'Izraz'. a> Pozitivna znanja krv_gr_od i boJ«_oai_od(Zt¥). zdravlja odCKidobro) ako fiz aktivan C Xida) i nije puiaötXistrastven). fiz_aktivanCJureida) . puftaćCpetaristrastven). pui«e(ahaistra«tvan). b) Hijerarhija entiteta Iz lagiCke baza. Imenovsni i u opisanoj notaoiji l.ir.alanl, uvjeti integriteta (tj. negativna manja), kojima eno se bavili u odjeljku (3), g:l!a>ai ui.boja ui_zdravl ni Ja_lstina_da zdravi Ja:.pd CXI dobro)' 1 pu 1 nije flz_aktivantXtd«).. ui voli nije_lBtina_d« vollCXiV) 1 Je 1 J»C'.Y'| zmija) Rad siBtama za upravljanja logbaio* znanja ilustriran Ja priBjarim« koji slijeda. vrsta_odCiivotinJailivo.bića). vrsta^odtfiovjekiitva^biće). vrsta.odCana t&ovjak). vrsta^odCpetariĆavJek). vrsta_od(aara:öovjek). vrsta_od C jureiCovJek). vrsta_od. Cinjanic«! zdravijv.od t: d. Cinjanic« i idravlJa_cid navodi inatanoirana pravila, koja u prooacu opavrgnuda pa ih tako niti na tretira. U ovoa alufiaju sna upisivane filnjanioa prihvatili, jar naa prva sluti u priajaru (3) « druga u prlajariaa (4), (S> 1 (A). PRIKJCR 3. Pokutaj upisa pravila, koja bi dovalo do krtanja uvjet« Integrität». t 7- irule. Il zdravijB_od(Xidobro) ako volKXivino). Uvjet Integrität«! ul.tdravl niJo_istina_đ« zdravij«_od(Xidobro) 1 putafiCXistrastvan) bio bi prakrten! Dedukoija bi bilai zdravije_odtpat«ridabro} slijedi iz vol Kpatari vino) volKpatarivino) - Ainjenioa u LB putaCCpetaristrastven) - Oinjenioa u LB Upis nije izvrtan yaa primjer u ovoa priajaru u b«xu unoslao (rtkurzlvno a i redundantno) pravilo, kojia Iskazujaao znanje* Svatko lm« boju oSlju jednaku boji oelju svoga brata. Pored unosa pravila, u priajaru ja Ilustrirano i obrazlaganje nauspjatlh pokut«Ja dadukoijei koaantar slljadl priajaru. I 7- irule. li boj4_oöi_ad(XiV) ako brat_od(l(i Z) i bo3«_o6t_odCIiV). Pravilo Ja redundantno - iaa praznu akstenziju! tt) Dedukoija 7 Celaa./n.) li boja_aei_od(Jakovil), •«» Nije dsduoibllno Jari Cilji boja.oÖl.odtJakoviX) E0 unificira sai boja_oöi_Dd(JakoviX) ako brat_od(jakoviV) 1 boja_oaL.ad(YiX) (2) NiJa deduolbilnoi brat.odCJakoviX) 1 faoja_o«l odClCiV) C3> Doduoibilno j«> brat_Dd » unifioir« sai bDja_oAi_od(stavcniX) «ho br«t_od(«tsvaniY> 1 boJa.oOi.odCViX) Nija daduoibilnai brat.adCstvvantX) i boJa_aei_odCXiY) Z* — brat.odCstBvaniX) — nau nijadna unifIhaoija. et) <7) Cilji b(iJa_očl„Dd< (9) la — «ajka ad(stovantX> — naaa nijedna unifikaaij». <10) Za — hoj*_oai_Qd(»t»vantX) — nana drugih unifikacija. (li) Cilji boja_oCi_od Za — «ajka_Qd(jakoviX) — naša nijadna unilikaoija. Za — boja_oai_od(Jakovi X) — nana drugih . unifikacija. Dedukcija T Il n. Upisati pravilo 7 (d./ ,) Itd. Kontrola U1 OK. Drug« proajena u LB« Movo stanja LS prihvatljivo ? (14) (15) (16) (17) (1) Obiiroa da ja akstaniija pravila prazna, jasno ja da nijadna öinjanica nija daduoi-bilna il toga pravila la sadainja stanja baza. Pogladajao zatto nije daducibilna fiinjanioa (1) (2) Sa ton einjaniooa unifabilno Ja upravo upisano pravilo, ... C3) ... no, tada trsba daduoirati (djalonlöno instancirano) tijalo toga pravila, tto iz data baze nija noguća, jer ... C4) ... prvi od ciljeva iz tijela daduaibilan je, uz istodobno daljnje inetanolranja (vezivanje) varijabli, ali ... (5> ... drugi nije. Naina, drugi oil J je uni- fabilan sa uprava upi'sania praviloB, no ... (Ä) ... pokuiaj dadukoija oil Ja Cl) ui upotrebu toga pravila ... (7) ... na uspijeva. (S) Cilj (S), kao izvedeni oilj u pokutaju dedukcija oil ja (1), pokutava sa tatia dadu-oirati posradstvoa drugog pravila iz baza, sa kojia Je unitabilan, no ... (9) ... ni taj pokuftaj ... (10) ... ne uspijeva, ... (11) ... eise Ja pokutaj dadukoija oilja (1) poBoću upravo upisanog pravila (2), iavr~ tio nauspjehoa, (12) Cilj Cl) pokuiava sa latia daduoirati pono-ću drugog pravila ii baza sa kojia Ja uni-fabilan, ... ... no, ni taj pokuftaj ... ... na uspijeva, ... ... fiine su baxuspjaftno iscrpljene sva ao-gudnoati dadukoija, tj. sva unilabilna pravila, ta oilj Cl) nija daduoibilan ii datoga atanja baia znanja. (16) Redundantno pravilo sbo u baiu upisali, i novo stanje baie prihvatili. (13) (14) (15) (17) OCito ja da obrazlaganja nauspjatih pokulaja dadukoije nalazi i ahsplioir« rado« sva grana neuspjeha n« pripadno« SLDNF-drvu, i« dati upit i stanja baza znanja. PRIHJCR 5. UnosoH öijenioe 'boJa_oöi_ad(stevanizelana)' äini da pravilo uneteno u pcinjeru (4) ne buda vi£e redundantno. U ovoa prinjaru data Je i uapjatna dedukcija Cinjanioa - 'boja^oei.od(Jakov i zelena)', koja prija ovoga, upisa nije bila deduoibilna, kako ja to pokaza-' no u priajeru C4>. I 7- ilaot. II boja_ofii_Dd(Btavanilalena). Kontrol« UI OK. Druge promjene u LBi Promjena akstanzija pravila* boja ofii odCXiY) ako brat Dd(X)Z> i boJa„o6i_ođ(IiY> Pokazati proajanu 1 (d./_.) < I d. Prijainja akstanzija pravilai prazna SadaAnJa akstenzija pravilai boJa_o&i_od(JakoVI za 1ana) Dadukoija 7 (elaa./n.) li baja^ofii.adtJakavtialana). Činjenica i boJa.oCi.od(Jakovizalana) DadukoiJal boJ«_odl^od(jBkovizelena) stijadi iz brat.odtjakovistavan) i boJa.oći.odCstavanizelena) brat_od(Jakovistevan) - fiinjanioa u LB boja~o6i_Dd(Btavaniialena) - Cinjenioa u LB Dedukcija T (alen./n.) Il n. Novo stanje LB prihvatljivo T Cd./ .) 11 d. Pronjana izvrtana PRIKJER 6. Upis ftinjenioa brat.od(stavam Jakov) Ca) dovodi do toga da postoji, upit, koji za novo stanje baza znanja, ima SLDNF-drvo s« baskona-etio« granoa. Prilikoa kontrola Integriteta baze (kao d Jala postupka upisivanja), sistea za 16 upravljanj» b*io» - tnkrauntdnia poiivanjae oiljava, na koja upisana manj« mala utjaoatl -nalazi takav upit. PokulaJ njagova dadukoija ttj. aLDMF-opovrflnuća) - ibog paatojanja hasko-na£na grana - dovodi do prakoraAanja raspoloživog prostara na sisteau i da prakida pokuiaja dedukcije. Obrailolanje pojadinih koraka «lijadi priajaru. I ?- iiaot. II brat.odletavanijahov). > Out of local stack during axaoution C Execution aborted 3 I 7- loop, Pokutaj dadukQija oilja — boja_oäi.od brat_od beat, brat.odfstevantjakav) boja.oei.odCJakovtX) brat_ brat_Qd{jakovistavan) bDja_oÖi.od brat. ■lijedl ii odCjakovistavan} i boja_ofii_od(stevaniX) - ftinjanioa u LB slijedi iz odtstavaniJakov) i boJa.oäi_ad ~ Cinjanioa u LB slijadi ii odistavanijakov) i boja_oäi.od prestalo ja biti redundantno, dok je oirkularni« postalo tek ovdje i to upisoa Qinjenioa (a) u bazu znanja. S druge strana, analogna pravilo, koji« sa svojstvo 'boja.oöl.od' definira u ovisnosti od svojstva 'aajka.od' Cdato u po6a-tnoa stanju baza manja), naäa nikada devasti do oirkularnoati. Ili toCniJei nede dovesti do oifkularnosti ava dok u bazu znanja budan upisivati iskaza (einjanioa, pravila), koji su u 'raalnoa svijatu' - kao aodalu baza-taorija -istiniti. Razlika izaa<»u ta dva svojstva Cu kontekstu plsutnostl rakunlvnlh dafinioij«), jasta, na prlajar, Ito ja svojstvo 'brat.od' sinetrlftno, dok svojstva 'Mjka.od' nije. No, to ili aliena saznanje nisu dovoljna da bi a priori aoQli znati hoda ti nako pravilo 111 Činjenica dovesti do olrkuiarnosti dafinioija nekog svojstva u logičkoj bazi. U toa kontakstu, 1 dato rjalanja, koje oaoguóava aksplikaolju cirkularnosti a tise i proajanu (ispravak, rs-de(inioiju) znanja iz baza znanja, izglada operativno zadovoljavaJuđiB rjatanjaa. phihjer 7. (1) u Cl) Prolog intarprator Javlja da ja dotle do prakida pokutaja SLDHF-opovrgnuda za neki cilj, i to zbog prekoračenja raspolo-livog prostora. <2) Naredbo* 'loop' od sisteaa logidka baze tratiaa koji ja ta oilj bio. (3) Odgovor ja dat sa C3>. Da bi pri prekidu rada Prolog interpratora bilo aogude dobivanja takvog odgovora, sistea baza znanja paati zadnji oilj koji se pokutalo daduoi-rati. <*) NaredboB 'sh.loop', uz navođenje oil Ja dobivenog narsdboB 'loop' ta dubina pradenja pokutaja SLDNF-opovrgnuda (u nate« prlwja-ru IQ), aksplioirati deBO pokutaj dadukoije, koji slijedi beskonatnu (ili bar preveliku) granu SLDNF-drveta. Iz pokazanih koraka u pokutaju SLDNF-opovrgnuda, trebalo bi biti vidljivo da Je grana beskonačna, tj. da se radi o olrkularnoj definiciji, u kojoj aa oilj boja_aei_od), date su na upit 'ans' u (3). Negativno manje, (tj. znanje o pingvinu, kao izuzaiku od pravila), upisujeu sa naradbo« 'inaio' u (4). Tine je uneteno znanje da "pingvini ne leta". Pokutaj upita pravila u (S) ne doputta se, Jer bi to prekrtilo uvjet integriteta upisan u (4), kako to sistea (u (5)) i obrazlafa. I 7- ifact. ti vrsta.odCslavujiptlaa), II vrsta_od(pingviniptloa)< (1) Kontrola UI OK Druge prasjene u LB Novo stanje LB prihvatljivo 7 (d./ .) Ji d. ProDijana izvrSena yes I 7- irulB. I: letiCXida) ako j« sdi netvena ili < v ) ižestruii a 7 I I j. Kontrola UI 0« Oruga promjana u LQ t Novo stanje LB prihvatljivo 7 lid. Pronjena izvriena yes I 7- ans. I I X taho.da leti(Xida>. Odgovori) (3) ptica . slavuj ObjaSnjanja 7 slijedi iz vrst»_odtslavujiptioa) i jetptica«ptica> vrsta_od(slavujiptica) - ćinjanioa u LB NIJE daduclbilnoi je(s1 avuj Ipingvin) Objainjenja 7 Cn-torka./n.) li n. yes i 7- insto. I: ui_leti I: nije_istna_da I et i(pingvi ni da). (4) Upis izvršen yes I 7- irule. I: leti jeCpingviniptica) slijedi iz vrsta_od(pingviniptica) i je(ptica)ptica) vrsta_ad(pingviniptioa) _ Cinjenicau LB Upis nija izvrSen yes S. ZAKLJUČAK U Članku ja dat prijedlog nadela loglCke ba^e manja, koji Je deliniran u teralniBa la-glNs i realiziran sredstvlna i matodava logičkog prograniranJa. Kodal ja ilustriran prlnjerlna rada sistaiia za upravljanja loglCkoa bazon znanja, koji J« realiziran u prograaskom Jeziku Prolog. PradlolanlD nadaloB (1 lupienentaoljo«) dat Je prikaz naClna predstavljanja i procesiranja znanja zasnovan na Jeziku (1 sistesu) Logike, za koju saatraao da - u kontekstu ta probleaatike - otvara najvlfte Boguanasti. 7. reference Bojadlljev, D.i Harbrandov lirekt nehaniena dokazovanje izrekov In relacijska bai« podatkov, 0P-2f36, Ins. "J. Stafan", Ljubljana, 19A3. Bratko, I.i Eitpart Systens and PROLOG, u Sunnar, F. t Supercaaputar Sygtsa Tsohnology, Pargaaon Infoteoh Ltd. Stata of the Art Reports, Sarles 10, No. 1982. Clark, K.L.i Predicata Logic as a Conputatlonal Forva-liBBiflas. Mon. T9/B9, laparlal Callage, London, Dept. of Conputing, 1979. van Enden, H.H., Kowalski, R.I The Sanantlos of Predicata Logic as a Progranaing Language, J. of the ACH, Vol.23, Ho.1976. van EndaB, H.H.) Conputation and Deductive Infornation Retrieval, u Neuhold, e. (ed>i Foraal Oasoription of Programaing Concepts, North-Holland, 1978. Eallalra, H., Ninker, J., Nicolas, J.i Loglo and Databases! A Deductive Approach, Computing Surveys, 198*. Kltakaai.H. at all A Metodology lor laplenentation of a Knowledge Aoquisitlon Systea, Int. Synp. on Logic Programaing, Atlantic City, 198^. <:Kaw 79> Kowalski, R.i Logic far Problea Solving, North Holland, 1979. Kowalski, R.) Logic as a Database Language, Tech. Rep., Inperial Coll. London, Dept. of Coapt. 1981. Lloyd, J.U.i Foundations of Logic PrograaBlng, Springer-Varlag, 1984. Lloyd, J.W., Topoc, R.U.I A Basis for Deductive Database Sysen, Tec. Rap. 85/1, Univ. of Melbaurne, Dept. al Comp. Soience, 1985. Nilson, J.N.I Principles of Artificial Intelligence, Springer-Varlag, 1982. Pereira, L.H., Porto, A., Dias, V.t Knowledge Sytttaas, Tao. Rep. DI/UNL - 2/8B, Univ. Nova da Lisboa, 1985. Radovan, M.i Hödel deduktivne baie podataka iaplenenti-ran u Prologu, Intoraatloa, LJubJana, br.l, 198é. Radovan, H.i A Knowledge Aoqulsition Systaa for Logic Database, Tea. Rep. UNL - 2/86, Univ. Nova da Lisboa, Dept. da Inforaatioa, 19a&. Robinson, A.J.I Logioi Forn and Function, Ediaburg University Press, 1979. Vahya, A., Menschen, L.J.t Deduction in Non-Horn Databases, J. of Autoaatad Reasoning, Vol.1, Ho.2, 198S. RAZVRSTITEV NOVOGENERACIJSKIH RAČUNALNIŠKIH ARHITEKTUR UDK: 681.3.02 Borut Robič in Jurij Šile Institut Jožef Stefan, Ljubljana v ćlanku pr»det4vtjava razvrstitev raäunalniCklh arhitektur, porojeno it treh nadinov vodenja raCunanj«! krmilnega, podatkovnega in vođenja i zahteva. Opisani so ustrezni raCunski «odeli ter njihove realizacije na različnih organizacijah stroja. Classification of New Generation Codiputer Arohitectures - Classification of neu generation computer architectures based on control driven, data driven, and deaand driven computation is described. Also, ue present several simple operational models and their iopleoentations on different machine organizations. 1. Prolog Ideja o računalnikih pete generacije je bita prviC predstavljena na mednarodni konferenci v Tokyu oktobra 1981. Peta generacija bo idru*Bvala rezultate raziskav na podroBjih umetne inteligence, programirnega inženiringa, VLSI .2 CENTRALIZIRANA 0R6ANIZAC1JA S.1 TOK KRniLNlH PAKETOV 4.3 REDUKCIJA IZRAZOV 4.5.1 REDUKCIJA GRAFOV 4.5.2 PODATKOVNO VODENJE 3.2 TOK PODATKOVNIH PAKETOV 4.4 VODENJA RAČUNANJA 3 MODELI RAČUNANJA 4 ORGANIZACIJA ZA OBRAVNAVO IZRAZOV 5.3 ORGANIZACIJA ZA POSREDOVANJE PAKETOV 5.2 ORGANIZACIJA STROJA 5 Slika 1. Eleaenti raCunalni^ke arhitekture. Uvod Rezultat raziskav na podrDtjju novejših računalniških arhitektur so tri osnovne družine arhitektur, ki se railikuje jo po naöinu vodenja rafiunanja CTralSID, :Trel82a:. Ustrezne arhitektur* «e inenujejo krailno vodene, podatkovno vodene ozlroaa arhitekture, vodene z zahtevo. Znotraj vsake družine pa se arhitekture lotti jo Se po izbrane® oodelu raCunanja ter seveda po organizaciji stroja. Iiraz raCunalnlSka arhitektura je torej doloren s treni elementi ;!= C <¥odenje raeunanja>, <(i\odel raffunanj8>, K DruKina krailno vodenih arhitektur zdruluje tradicionalne von Neuaannove računalnike skupaj z njihovi«! paralelnini različicami, kot sta na priaer SIND in MIHO arhitektura. Ostali dve družini pa združujeta novejSe, visoko paralelne ne-von Neunannove arhitekture. V nadaljevanju bo prikazana podrobnejša razdelitev računalniških arhitektur ter razlike med njini. Bralcu bo v ponoC slika 1, kjer se oznake ob posaneznih elementih arhitekture nanašajo na ustrezna poglavja v Članku. Vodenja caäunanjd HaCunanja lahko siatraao kot zaporedno ponavljanje treh faz: . a> izbiranja /selection/, b) preverjanja /ex an inati on/ ter c> izvrševanja /execution/. a) Izbiranje: v tej fazi se dolotii skupina ukazov pro9raaa, ki so notni kandidati za izvršitev, IzvrSljo se lahko le izbrani ukazi, vendar izbor ukaza Se ne zagotavlja njegove takojšnje izvršitve. Pravilo, po kateren se ukazi izbirajo, iaenujeao pravilo izbiranja. LoCioa tri pravila izbiranja: - brezpogojna /imperativa selection/, - notranje /inneraost selection/ ter - zunanje /outerinost selection/. Pri brezpogojnem izbiranju se izbere ukaz ne glede na njegovo lego v programu. Izbor se izvr)ti na podlagi posebnega registra (programskega Števca) ali pa na podlagi prisotnosti vseh krailnih paketov. Notranje izbiranje izbere najgloblje gnezdene ukaze izraza, zunanje izbiranje pa ukaze, ki ne gnezdijo v nobene» izrazu. b) Preverjanje: v tej fazi se ugotovi, Ce so izbrani ukazi izvršljivi, kar poneni, da se preveri, Ce so prisotne vse potrebne vrednosti cperandcv v izbranih ukazih. Pravilo, po kate-rea poteka preverjanje, isenujeno pravilo izvršitve /firing rule/. IzvrSljive ukaze prev-zaae tretja faza radunanja, izvrševanje. Ce ukaz ni izvršljiv, pa ga faza preverjanja bodisi odloii, dokler ga neka kasneJSa faza izbiranja zopet ne izbere, ali pa ga poskuSa napraviti izvršljivega s ta«, da zahteva določitev vrednosti njegovih arguaentov, c) Izvrševanje; v ukazi dejansko izvrSe. tej fazi se iivrSljvi LoCiao krmilno vodeno /control driven/ računanje, podatkovno. vodeno /data driven/ računanje ter raCunanJe vodeno z zahtevo /demand driven/. Čeprav bodo vsa tri vbdehja raCunanJa podrobno opisana v nadaljevanju, že tu omenimo, da pri podatkovnea vodenju prisotnost vseh potrebnih operandov sproti izvrSevanJe ukata, aedtea ko pri vodenju na zahtevo zahteva po rezultatu sproži izvrševanje tistega ukaza, ki ta rezultat lahko priskrbi. 3-1- l^rmtlr LU Krmilno vodeno računanje ima sledeCe zna-Cilnostii - izbiranje ukazov je brezpogojno, - preverjanje ukazov se ne izvaja in - izvrševanje ukazov sledi neposredno po izbiranju. Torej se ukazi izvrCe takoj, ko so izbrani. 3.2. Podatkovno vodenje Značilnosti podatkovnega vodenja lahko strnemo v naslednje: - izbiranje poteka tako, da se vsakenu ukazu dodeli procesor, - preverjanje sestoji iz sprotnega ugotavljanja prisotnosti vseh vhodnih operandov ukaza, - izvrševanje pa sestoji iz izvrSitve vsah ukazov, katerih vsi potrebni operandi so prisotni« Torej pri podatkovno vodenem raCunanju ukazi pasivno bakajo na svoje vhodne operande. 3.3. Vodenle z zahtevo Vodenje z zahtevo pa ima BledeCe značilnosti : - ukaz se izbere (navadno po pravilu zunanjega izbiranja) tedaj, ko nek prej izbrani ukaz zahteva njegov .rezultat, - v fazi preverjanja se ugotovi, Cs so Izbrani ukazi iivrSlJivi, torej Ce so znana vrednosti njihovih operandov. Ce vrednost operanda Se ni znana, se posreduje zahteva tistemu ukazu, ki ga lahko izraCuna, - izvrševanje je sestavljeno iz izvrSltve vseh tistih ukazov, katerih potrebni operandi so znani. Torej se pri vodenju na zahteva ukaz izvrSi tedaj, ko je bita podana zahteva po njegovem rezultatu. lodeli. i-aOMnanja Vodenja raCuncnJa realiziramo z razliCnini ■odeli raCunanJa. Krmilno vodenenu računanju pripadajo sle-deGi modali: - z zaporednim krmilnim tokom /sequential control (low/, - s sočasnim krmilnim tokoo /parallel control flou/, - s token krailnih paketov /control flow with control tokens/. Podatkovno vodenetnu raCunanju pripada le model : - s tokom podatkovnih paketov /data flow/, Računanje, ki je vodeno z zahtevo pa je moä realizirati z dvema aodelomas - z redukcijo izrazov /string reduction/, - z redukcijo grafov /graph reduction/. V vsskea fflodelu rafiunanja se trčali izvirni naCin vodenja raCunanja v obliki sproiitvenega ter podatkovnega mehaniiaa. Spraiitveni «ehanizeni /control mechanism/ doloöa naöin, kako iivrSitev nekega ukaia vpliva na iivrSitev ostalih ukazov in s tem vodenje izvrševanja programa. Sproüitveni aahanize« je lahko: - laporeden /se()uential/ i ukazi se izbirajo drug za drugi» in se po vrsti izvršujejo, - soCasen /parallel/i kjer se na nek naBin ugotavlja prisotnost vhodnih operandov ter povzroiJi latìetek izvrševanja tistih ukazov, ki imajo na voljo vse potrebne operande, - rekurzivan /reoursive/s kjer se posreduje zahtevo po operandih ter spraü izvrševanje tistega ukaza, katerega rezultat je bil zahtevan. S podatkovnim mehanizmoa /data mechanisai/ pa je doloCen naBin, po katerem si ukazi delijo ikupre operande. Pri te« sL lahko ukazi delijo operand s posoäjo: - vstavljene vrednosti /literal/i äe je vrednost operanda znana Ze pred priCetkom raCunanja, se takoj vpiSe v vse ukaze, ki jo uporabljajo, - sprotne vrednosti /value/: kopije operanda, ki se je izradunal, se posredujejo vse« ukazom, ki jim je operand skupen, - reference /reference/i tu vsebujejo vsi ukazi referenco (naslov) na skupen operand . 2vezo med obema mehaniznoeia ter razliünioi modeli raäunanja prikazuje tabela 1. PODATKOVNI tlEHANIIEM vstavljene in sprotne vred. zaporeden soCaeen tok podatkovnih paketov rekurziven redukcija izrazov vstavljene vred. in reference zaporedni kriailrii tok sotJasni krmilni tok tok krmilnih paketov redukcija grafov Tabela 1. Modeli cabunanja glede na sproüitveni in podatkovni aehaniiem. 4.1. Zaporedni krmilni tok hodel z zaporednim krni Inim tokom iiua naslednje značilnosti: - krmilno vodenje raäunanja, - zaporedni sproüitveni »ehanizem, - podatkovni mehanizem s pomotìjo vstavljenih vrednosti in referenc. Model z zaporednim krmilnim tokom uporablja en sam procesor za raäunanja in programski fitevec, s kateri«, se izbere naslednji ukiiz, Torej obstaja en sam krmilni tok, ki prehaja z ukaza na ukaz in temelji na zaporednem sproiitveneffl aehanizemu. Ko krmilni tok dosege ukaz, se razreSijo vse reference, kar pomeni, da se dostavijo vrednosti operandov iz naslovljenih ponnilniäkih lokacij. V inodelu z zaporednim krmilnim tokom se torej uporablja podatkovni mehanizem z vstavljenimi vrednostisi in referencami. Ukaz se nato takoj izvrSi, saj fazi (brezpogojnega) izbiranja neposredno sledi laza izvrševanja - ratìunanje je torej krmilno vodeno. Rezultat iivrflitve se vpiSe v skupno lokacijo. Po izvršitvi ukaza se programski StevBC bodisi neposredno ali posredno aturira, s «ioer krmilni tok preide na naslednji ukaz. Izvrševanje v nodelu z zaporednio krmilni« tokom ponazorimo na stavku z (ii«'2)*(K-y) ^ ki je predstavljen z zaporedjem ukazov, pri temer vsak vsebuje operacijo, kateri sledijo operandi (Slika 2). Ti so bodisi vstavljene vrednosti ali pa naslovi lokacij, kjer so shranjene vrednosti operandov. PrenaSanje vrednosti med ukazi se vrSi B pomotijo skupnih lokacij v pomnilniku. .. I + X 2 ti ( - K y t2 I * 11 t2 z I . . , »tili yin'T'^^Tiis) t2i( ) z!( ) (S> t2>(2} zi( > .. . I + K 2 t1 I - K y t2 I * ti t2 z I . . . x>(3) yi(1J t11 krmilni tok podatkovni tok Slika 2. Računanje v modelu z zaporedni« krailnia tokom. 4.2. Soeagni krajini toK Model sDbasnega krmilnega toka ima eledeCe značilnosti) - krallno vodenje raBunanja, - soBasni sprolitveni «ehanizen, - podatkovni mehanizem s pomoBjo vstavljenih vrednosti in referenc. V modelu s soöasni» krmilni» tokom uporabljamo ukaza FORK za zadetek soCasnega raCunanjö ter JOIN za sinhronizacijo. Ukaz FORK i povzroči nastanek novega zaporednega krmilnega toka s priCetkom pri ukazu » naslovo» i. Ukaz na naslovu i Ima tedaj na voljo ite vse potrebne vhodne operande. Sobasni sprolitveni mehanizem v tem modelu ne zahteva preverjanja prisotnosti potrebnih operandov, saj je priCetek novega krnilnega toka eksplicitno doloCen z ukazoa FORK. Krillni tok, ki je IzvrSil ukaz FORK i, nadaljuje z izvrfievanje« naslednjega ukaza (iapllcitnl krmilni tok). Ukaz JOIN n zaustavi prvih n-1 krmilnih tokov, ki so prispeli do njegaj ko prispe do tega ukaza zadnji, n-ti ■ krmilni tok, nadaljuje z izvrSevanje« naslednjega ukaza. Ker se v ten modelu soCasno vrSi nekaj zaporednih krmilnih tokov, je njegov podatkovni mehanizem enak mehanizmu v modelu z zaporednim krmilnim tokom. Seveda zahteva tak model uporaba veCjega Števila procesorjev. Primer izraCuna stavka z ;= tii + 2)»{K-y) opisuje slika 3. ____________________-_________i:-....., ... t fork 1 I + X 2 ti I GOTO j I - K y t2 t JOIN 2 1 * t1 t2 i I ,.. mO) y! <1) tl! ( > t2: C ) Zi ( ) i : ■ j = I fork 1 i + h 2 t1 1 goto j I - X y t2 1 join 2 i t t1 t2 i 1 Z!C ) [ i! ^j! J f FORK i I + * 2 tl I GOTO j I - « y t2 I JOIN 2 I * t1 12 z I k;<3) y;Ct) t1;C5) t2;C2J 2:C ) is j: t FORK i I + X 2 tl I GOTO j I - x y t2 1 JOIN 2 I * t1 t2 z I *;C3) yiCI) tl!<5) t2H2) ) J! t FORK i I + K 2 t1 I GOTO J I - X y t2 I JOIN 2 I « t1 t2 z I m(3) ysd) t1s(5) t2l(2) itdOj krmilni tok podatkovni tok Slika 3, Računanje v modelu s safiasnini krnilniiti tokom. '..3, Tok krmilnih paketov Tok podatkovnih paketov tiodei toka s krailnimi pakati ina sledeCe značilnosti : - krailno vodenje raCunanja, - saCaani sproiitveni mehanizem, - podatkovni mehanizem s pomoCjo vstavljenih vrednosti in relernec. Tudi pri modelu s tokom krnilnih paketov poteka raCunanje sotiasno, zato ta model zahteva veCJe Število procesorjev. Vsah ukaz hrani poieg operacije ter operandov Se naslov svojega naslednika, ki bo uporabil njegov rezultat, ter prostore za krailne pakete, ki jih prejme od svojih predhodnikov po njihovi iivrSitvi! Ko ukaz zbere vse krmilne pakete, se sproSi njegovo livrSevanje, pri Čemer se najprej, rairettijo vse reference ter nato iivrSL operacija. Na koncu se rezultat shrani v skupna lokacijo, krmilni paket pa se posreduje vsem naslednikom ukaza. Vidimo, da je iivrSevanje krmilno vodeno s soäasnim sproÄitveni m mehanizma«, ki ugotavlja prisotnost potrebnih krmilnih paketov. Podatkovni mehanizem pa temelji na vstavljenih vrednostih in relarencati. Potek rafiunanja stavka z i= (x+2)«'x-y) je opi&an na sliki <>. Model s toko» podatkovnih paketov lota naslednje značilnosti: - podatkovno vodenje raCunsnja, - sotìasni sprolfitveni Biehanizem, - podatkovni mehaniiem s pomoCjo vstavljenih in sprotnih vrednosti. Ta model Je podoben modelu s tokom krmilnih paketov, le da se tu iivrCevanja odvija 6 pomoCjo podatkovnih paketov. Ukazi sestojijo iz operacij, mest za operande ter oznak vseh ukazov, kamor naj se posreduje rezultat. Operandi so bodisi vstavljene ali pa sprotne vrednosti, s Cimer Je doloBen podatkovni nehanizem. Ukaz se lahko priCne izvrSevati takoj, ko mu je zadnji izmed njegovih neposrednih predhodnikov posredoval podatkovni paket s sprotno vrednostjo, na katero Baka. Izvrševanje Je podatkovno vodeno, saj soISasni sproiitveni mehaniiem v tem modelu ugotavlja prisotnost vseh potrebnih vrednosti vhodnih oper«ndov. V primeru toka -padatkovolh paketov so programi navadno predstavljeni s pomoCjo usmerjenih grafov, s katerimi je opisan tok podatkov ned ukaii. Toftke programskega grafa so ukazi, li il. k: 1) t K 2 t1 ktn I • ■ - K y t2 kC2] I o o t ti t2 z 1C13 I ... i: KI (3) y: CD t1:( > t2:( ) } Ji . . k, mos y;t1) tlHB) t2:<2) ii( ) -------------nržžžzzG3_L.________________ ... I o + » 2 11 kCI] I o o - x y t2 kC23 I • • • ti t2 i Itn I ... x)(3> y)<1) t1»C5) t2:<2) liC ) Jt k» Is ki<3) yi<1) t1i t2iC2) ii<1Q i: j' ki I o + » 2 t1 kCi: I o o - H y t2 hC2: 1 o o • ti t2 z IC13 I ki(3) yiC1) t1:(5) t2iC2) ziC10) tok krnilnih paketov podatkovni tok Slika 4. RaCunanJe v modelu s toko« kroilnih paketov. povezave pa skrbijo la prenos vrednosti (podatkovnih paketov) ned njimi. Toäka se lahko pciäne iìvrSevati 4jele tedaj, ko su prisotni podatkovni paketi v vseh njenih vhodnih poveia-vah. Ob priCetku izvrSevanJa toGka absorbira vse svoje vhodne podatkovne pakete Cs tiimer ti izginejo i2 vhoanih poveiav), po izvrSitvi pa postavi rezultat (izhodni paket) istočasna v vse svoje izhodne povezave. Izhodni paketi toCke so hkrati vhodni paketi neposrednih naslednikov. Pri «odelu raCunanju s tokon podatkovnih paketov je k vsakemu ukazu prldruZen procesor, ki pasivno Caka na potrebne vhodne vrednosti. Faza Izbiranja Je torej kar pridrulitev procesorjev vse» ukazos. Faza preverjanja sestoji iz ugotavljanja, Ce so prisotne vrednosti vseh vhodnih operandov, tie te vrednosti niso prisotne, ostane procesor neaktiven, v nasprotne« pa Jih sprejme, preide v fazo izvrSevanja ter zate« posreduje rezultate vsem svojim naslednikom. IzvrSitev stavka ! := , kje so tako funkcija kot njeni «rguoanti bodisi atoai (npr. + ali 2) ali pa Izrazi, sestavljeni iz atonov in izrazov. Uporaba funkcije Je sestavljena iz dveh korakov: - zahteve za dodelitev vrednosti njenim neznanim argumentom ter - izračuna funkcije nad njlai. Izratiun funkcije sa torej odtoil, dokler niso dodeljene vrednosti vse« argumentom. Na prlner, zahteva za dodelitev vrednosti argumentu a1, kjer je al definiran z al = , sproifi nadaljno uporabo funkcije g nad argumenti b1,...,bM. Takine zahteve po uporabi fiinkcij lahko porodijo nove zahteve, s einer Je dolotien rakurzivan «profitvani mehanizem. Oflitno Je, da nora biti vsak argument definiran z eno «aao definicijo, kar iaenujemo pravila D enkratni prireditvi /single assigne-ment rute/. Pravi«o, da se dani argument sklicuje /reference/ na svojo definicijo. Poleg tega definicija vrne pri veaki uporabi vedno enako vrednost kar imenujemo referenbna trans-parsntnoat tadukcije. Pri redukciji poteka faza izbiranja navadno iti ( + C ] 2 1/1 ) i2i ( - C D C 3 2/1 ) ilt ( + C33 2 1/1 ) i2i ( - Cn z/2 ) 2/2 ■> ys.l., .Redmic^.li izrajgtf Model t redukcijo izrazov inta siedeäe znaffilnostti - vodenje raCunanJ« j zahtevo, - cehurzlvni sproiitvenl nehanizen, - podstkavni Behaniiein % poaotijo vstavljenih in sprotnih vrednosti. Zahteva za dodelitev vrednosti argumentom poteka tako, da se neatonarni argument nadomesti s kopijo definicije, na katera se sklicuje. Podatkovni mehanizem zato temelji na vstavljenih in sprotnih vrednostih. Ce funkcija vsebuje veö neatonarnih argumentov, se vsi nadoiseste soKasno. Be so argumenti lunkcije atonarni, se funkcija iiraCuna in nadonesti t reiultatom. IzraCuni funkcij potekajo eoCasno. V tem nodelu je zelo pomembno dejstvo, da se postopek nadomeščanja izvrši vsakokrat, ko se zahteva izraCun acgusenta. Priaer redukcije izrazov pri izvrševanju stavka z := (x+2)t(x-y) je opisan na sUki 6. def iniciJe x: (3) yt (1) in (+ * 2) i2: <- X y) i: U il i2) . . . -> -> C. . .z.. .1 -> -> (...(• il i2)...) -> -> (...<* (+ X 2) (- X y)) . . -> -> (...<* <+ 3 2) (- 3 1 ))...) -> -> C...t* 5 2)...) -> -> <... 10 ...) -> -> .. . Slika 6. Raäunanje v modelu z redukcijo izraiov. Slika S. Računanje v oodelu s toko« podatkovnih paketov. <..5.2, RijitfukcvU qrfttBY po -pravilu zunanjega izbiranja. Procesorji se pridruiijo ukazo« v äasu faze izbiranja, Fa;a pr»verjanja pregleda argumente ukaza ter ugotovi, Ce Je IzraCun tnoien. Ce je, preide računanje v fazo izvfSevanJa, v kateri se ul yt (1) 12l t- * y) i: (t i1 i2 j/1 j: (...lt..) K: '^'•«ssss!^,-^^ Ili (+ * 2 1/1) ^^ìTT^k li (»"^il i2'*jV1) (i (3 i1/1 i2/1>-.._ y: (1 i2/2) i1s <+ K 2 2/1) y^t/2) Zi la^jV'i) j 1 C.. . if. . ) x: (3). il s (+ 2 z/1) y ! ( n LÌÌT^S 1 1/2) I! (* il i2'j/"l) Ji (...if. Kl (3) il! tS z/1) yj (1 ) i2! C2 z/2) Zi <# il i2 j/1) J ! t . . . z"f. . ) H! (3) il: (5) Xi (3) i1 i CS) XI (3) i1: ■ procesor koaunlkacijska enota I. pomni inik Slika Bi Centralizirana organizacija stroja. 5.2. Oraanizaciia za oosredovanie paketov Organizacijo sestavljajo tri glavne enotei procesna enota, ki zdruiuje veCje Število procesorjev, pcaniiniSka enota ter komunikacijska enota. Enote so krožno povezane, kot to prikazuje slika 9. Med enotami se nahajajo Se vrste /pools dI work/, ki cpravljajo nalogo začasnega skladiščenja paketov, kadar je to potrebno. Izvrševanje programa v takSni organizaciji poteka v obliki enosmernega kroinsga toka paketov skozi njene enote. Enote delujejo sodasno, torej je iivrftevanje programa cevijeno /pipelined/. Paketi, ki so pripravljeni za obdelavo v eni izned enot, čakajo v ustrezni vrsti, vse dokler jih ustrezna enota ni pripravljena sprejeti. Ko Jih ta enota obdela, shrani tako spremenjene pakete v vrsto pred naslednjo enoto. S|3. Organizacija za obrjvnavp izrazov Tak. Redukcija ^zrazov na oraanizaci.ii eentrallilrant Pri ceallzaoiji modela z redukcija izrazov imajo enote v centralizirani organizaciji sledeöe značilnosti! - pomnilnlfika enota zdruiuje določeno Število skladov /etsck/, med katerlni se ponavljajoče prenaša izraz, - procesna enota skrbi za prenos trenutnega izraza li zadetnega /source/ sklada v kantini /aink/ sklad. Pri prenašanju Izraza procesna enota razpoznava njegove reducibllne podizraze. Jih sproti izračunava (reducira) ter namesto njih shranjuje v konCni sklad njihove rezultate. Po prenosu celega izraza prevzame konäni sklad naloge zaöetnega in obratno. Prenašanje se ponavlja vse dokler ni izraz atomaren, - koaunlkacijska enota je vadilo, po katecen se .prenašajo iirall iz zaöetnege sklada v procesno enoto in ii te v konöni sklad. Vsak izraz (in s ten tudi glavni izraz - pro-grao) je zapisan v prefiksni obliki, pri Ceaer so v taki obliki zapisani tudi vsi njegovi podizrazi. Pri prenosu izraza Iz zaCebne^a sklada v kon&ni se nora takSna oblika ohraniti, zato navadna prenos poteka preko dodatnega, vmesnega /intermediate/ sklada. Projekti! Primer takCne ac-hitekture je GMD (6esel Ischaf t (iir Mathematik und Datenverarbeitung), ki so jo realizirali v Bonnu, ZRN CKlug79:. arhitekture za visoke jezike /HLL Architecture/ Predstavljena razdelitev novogeneraoijskih arhitektur je le ena iz vrste «ainih razdelitev. Kot je le bilo omenjeno, je pri tej razdelitvi osnovno vodilo vodenje raCunanja. Marsikatera realizirana arhitektura teiko najde mesto v eni sani predlagani poddružini (poglavje 6), saj je v novejSih arhitekturah pričakovati različne koobinacije podatkovnega in sproiitvenega sehanizaa, s tem pa tudi me&anih «odelov računanja ter vodenja. Omenimo vzorBno vodenje /pattern driven/ raCunanja, kjer se ukaz pribne izvrševati, ko pride do ujemanja vzorca, ki je pogoj za priCetei! izvrfievanja CTrel84]. Pojavljajo se tudi kompleksnejše organizacije stroja. Kot ilustracijo navedino ii dva najnovejša podatkovno pretokovna raCu-nalnikai SlSMA-1 CShifflSt] in veCprocesorski podatkovno pretokovni sisteo na osnovi procesorjev >iPD72ö1 CJeffSS, SilcBil. V obeh pri-■erih gre za organizacijo stroja, ki je podobna organizaciji za obravnavo izrazov, le da so gradniki podatkovno pretokovni procesorji, katerih oraanlzacija temelji na posredovanju paketov. RaCunalniSke arhitekture je noä razdeliti tudi z dveh drugih, diansetralnih zornih kotov: z vidika jezikov ozirona strojne oprene. Tako obstaja razdelitev novejših računalniških arhitektur, temelječih na visokih prograairnih jezikih /high level language computer architectures/. TakSna razdelitev je podana v CMituSùl in jo prikazuje slika 1A. Čeprav ni naaen tìlanka predstavitev takSne razdelitve arhitektur, pa vendarle omenimo skupino reduciranih arhitektur, med katere sodijo IBH 801, RISC , Elsevier Scinoe Publishers B.V. tNorth-Hol-1 and), 1983. CGurd85] Gurd J.H., Kirkham C.C., Watson I. "The Manchester Prototype Dataflow Computer", Comm. ACM, Vol.28, No.1, Jan. 1985, pp.34-52. tJefffiSJ Jeffery T. "The pPD7261 Byte, November 1985, pp.237-246. Processor", [;Xapa84a Kapauan A,, Field J.T., Gannon D.B., Snyder L, "The. Pringle Parallel Computer", The 11th Ann. Infi Symp. Arch., June 6-7, 1984, Ann Arbor, Michigan, pp.12-20. CKell79] Keller ft.M. et.al. "A Loosely Coupled Aplicatlve Nultiprccessing System", Proc. Nat. Comp. Conf., 197?, pp.861-870. CMago8Q: Magò G.A. "A Cellular Computer Architecture for Functional Programming",.Proc. IEEE COMPCON 80, Feb. 1980, pp.179-187. CMiluS6] Milutinovic V, Tutorial on Advanced Microprocessors and High-Level Language Computer Architecture, IEEE Comp. Soc. Press, 1986. [Patnfi63 Patnaik L.M., Govindarajan R., Rama-doss N.S. "Design and Performance Evaluation of EXMAN: An Extended MANchester Data Flou Computer", IEEE Trans. Comp. Vol. C-35, No.3, March 1986, pp.229-244. CPatt85] Patterson D.A. "Reduced Instruction Set Computers", Comm. ACM, Vol.28, No.1, Jan. 1985, pp.8-21, CPreiBSJ Preiss B.R., Hamacher V.C. "Data Flow on a Queue Machine", The 12th Ann. Infi Symp. Comp. Arch., June 17-19, 1985, Boston, Massachusetts, pp.342-351. CftobiSSa] Robiä 8., «Ilo J., MihoviloviC B. "Funkcionalno progranirni sistemi", Inlornatica 4/85, str.366-370, Nova Gorica, 1985. CRobieSbJ Robić! B, «ilo J.i "Jeziki in arhitekture sodobnih raöunalniSkih sistemov", US OP-4058, Ljubljana, November 1985. CRobi86a] Robie B., «ilo J., "On Choosing a Plan for the Eiieautian of Oata Flow Program Graph", Informatica 3/B6, pp.11-17. CHobiB6b3 fioblB 8,, Silo J., "Analiza statiCnih podatkovno pretakavnih programskih gcalov", Elektrotehniški vectnik 86/2, etr.S3-56. CShi«>863 Shimada T. , Hiraki K. , Nishida K. , Sekiguchi S. "Evaluation of a Prototype Data Flow Processor of the SIGNA-1 for Scientific Computations", Proo. 13th Infi Symp. Comp. Arch., June 1986, pp.226-234, CShor733 Shore J.E. "Second Thoughts on Parallel Processing", Coaput. Elect. Eng., Vol.1, 1973, pp.95-109. CSteeai] Sleep M.R., Burton F.U. "Towards a Zero Assignment Parallel Procesor", Proc. 2nd Infi Conf. Distributing Computing, April 1961. CSnydfitl Snyder,L. "Superoonputera and VLSls The Etfect ol Large-5c4le Integration on Computer Architecture", Advances in Canputers, Vol.23, MirshalJ C. Yovite, Ed.,AcadeBÌc Press, 198A. CStan7S] Stone,H.S. Introduction to Computer Archltaotuce, 5RA,Chicago 1975. Cliilc84] fiilo J., Roble B. "Računalniki krmiljeni 3 tokoB podatkov", US DP-3579,Ljub 1 Jana, Oktober 19B4. CSilcSSa3 «ile J., Robie B.i "Osnovna naäela OF Bistepiov", Inioraatioa 2/65, str.ia-IS. t«ilc65b] Silo J., Roblß S., IHHovilovitt 6. "Podatkovno vodene raCunalniSke arhitekure", Informatica <./85, str.371-376. CSilcflil äilc J,, Robie B. "Procesor 6 podatkovno pretokovno arhitekturo",Inlormatica 4/86. CTrauSS] Traub K.R. "An Abstract Parallel Graph Reduction Hachine", The 12th Ann. Int'l Syap. Coap. Arch., June 17-19, 19SS, Boston, Hassachueetts, pp.333-341. CTreiaoa Treleaven P.C., Kole 6.F. "A Multiprocessor Reduction Machine for User-delIned Reduction Languages", Proc. 7th Int'l Syap. Co«p. Arch., Hay 6-8, 1980, pp.121-13D, CTrelsn Treleaven P.C. , Hopkins R .P.. "Decentralized Computation", The Bth Ann. Synp. Comp, Arch., May 12-U, 1981, Hinneapolis, Minnesota, pp,279-290. [:Trsl82a3 Traleaven P.C., Brounbridge O.R., Hopkins R.P. "Dati-Oriven and Oemand-Orlvon Coaputer Architecture", Conp. Surv,, Vol.lA, No.1, «arah 1982, CTrel82b3 Treleaven P.C., Hopkins R.P. "A recursive Computar Architecture Jor VLSI", The 9th Ann. Synp. Coap. Arch., Apr. 26-29, 1962, Austin, Texas, pp.229-23B. CTreia2c3 Treleaven P.C., Hopkins fi.P., Rautenbach P.U. "Cosbining Data Flow and Control Flow Computing", Comput.J., Vol.25, No.1, Feb. 1982. CTrel843 Treleavan P.C., LUa I.S. "Future Cooputersi Logic, Data Flow,...,Contral Flou?", Cooputer, Vol.17, «o.4, March 1984, pp.47-57. [:U.ats793 Uatsan 1., Surd J. "A Prototype Data Flow Cooputer with Token Labeling", Proc, Nat, CoBputer Coni., New York, M.V., June 4-7, 1979, pp.623-628. Clale8S3 lelsinikar A.P. "Hadnarodna konferenca o raSunalnKhih elsteaih oete generacije v Tokyu", Inforaatica 85/3, str.60-70. MOŽNOSTI, Kl JIH PONUJA MIKROELEKTRONIKA SISTEMSKIM NAČRTOVALCEM UĐK: 681.327.6:621.38.049.7-181.4 M. Jenko In A. Vodopivec Iskra Mikroelektronika Podan je pregled mikroelektronskih tehnologij, njihovih razvojnih možnosti, vrst današnjih mikroelektronskih vezij. smernic razvoja naortüvalake opreme. Dani so kriteriji racionalnega pristopa sistemskega načrtovalca k mikroelektroniki. Opisan je načrtoval ski postopek od zasnove logicne sheme do narejenih ntask v DO Mikroe lekCi'onika. Possibilities Offered to Microelectronic System Designer A view of microeiectroriics technologies, their growth alternatives, sorts of present integrated circuits, directives for evolution of design support are qiven. Criterions on design solutions for custom integrated circuits from the system designer's view are described. Design procedure beginning with completed logical scheme to process masks in Iskra Microelectronics div. is depicted. Gradivo je razdeljeno na ; 1. Primerjava obstoječih mikroeiektronskih tehnologij in načrtovanja po možnostih, ki jih nudijo načrtovalcem 2. Smernice razvoja tehnologije, razvoja načrtovanja mikroelektronskih vezij 3. Oris nacrtovaIskega postopka od zasnove logicne shene do narejenih mask v DO Hikroelektronika Primerjava obstoječih mikroeiektronskih tehnologij in načrtovanja po možnostih, ki jih nudijo načrtovalcem Danes obstoje tri osnovne mikroeiektronskih tehnologij; planarna tehnologija na siliciju galijevem arzenidu debeloslojna tehnologija tankosiojna tehnologija veje 1,1 Planarna tehnologija - osnovni postopki; tehnološki silicij z kontrolirano vnašanje primesi v difuzijo, ionsko implantacijo termično ali plazemsko stimulirana plasti na siliciju naparevanje. napraevanje med elenenti litografski postopki topologi'je vezja debeloslojna oksidacija za zaseito veaij, tankoslojna oksidacija za definiranje aktivnih območij tranzistorjev rast metalnih povezav za definiranje površine silicija 1.2 Debeloslojna tehnologija Ust4&vni tehnološki postopek je sitotisk. NanaSarac prevodne, uporovne, dielektricne, izolacijske paste preko sita, na katerem je definirana geometrija vezja, na keramično podlogo. Sledi zapecenje posameznih nanesenih plasti. Oblikujemo lahko upore, kondenzatorje, prevodne steze. 1.3 Tankoslojna tehnologija Osnovni tehnološki postopek je vakuumsko naparevanje in ionsko naprSevanje. Oblikujemo pasivne komponente in tankoslojne tranzistorje. Njihove karakteristike ne dosegajo monolitnih tranzistorjev. Ce se le da, se vezja realizira v planami tehnologiji. Glavni problem je, da imamo za vse elemente, ki jih hoCemo narediti, na razpolago le ene in iste tehnološke postopke. Zato je na ta naein težko izdelati kombinacijo npr. hitre logike in nekaj amperov močnega izhodnega tranzistorja. Zato imata svojo vrednost tudi tankoslojna in debeloslojna tehnologija, kjer aktivne dele vezja prilepimo na podlago, povežemo in lahko opremimo s Se nekaj pasivnimi komponentami, zapremo v ohišje ter prodajamo kot zaključeno vezje. Razvoj gre v smer vse vecje integracije različnih gradnikov vezja samo na rezini -planarna tehnologija. Planarnih integriranih vezij je danes na trziacu ogromno. Lahko jih klasificiramo po tipu osnovnega aktivnega elementa (1.3.1), po stopnji integracije (1.3.21, po uporabi in pristopu k izdelavi vezja (1.3.3). 1.3.1 Bipolarna in unipolarna vezja. Osnovni gradnik bipolarnih vezij je bipolarni tranzistor. Ta vezja so načeloma hitrejša od unipolarnih, so nanj občutljiva na elektrostatiko, njihova izdelava žahteva vee tehnoloških postopkov, statična poraba je večja, porabimo vec prostora- Osnovni gradnik unipolarnih vezij je MOS tranzistor. Ločimo: - PMOS vezja■ - SMOS vezja - CMOS vezja Začelo se je s PMOS vezji - aktivni gradnik vezja je p kanalni tranzistor. Tehnologija manj zahtevna kot za NMOS in CMOS. Pragovna napetost ie razmeroma visoka, gibljivost nosilcev toka - informacije je razmeroma nizka, zato so ta vezja soratinerno počasna. Tudi brez preklopov porabljajo ža svoje delovanje energijo, zato za aplikacije z nizko porabo niso primerna. SMOS vezja so tehnološko zahtevnejša, pragovna napetost tranzistorjev Je niz ja. gibljivost nosilcev toka je približno se enkrat veCja kot pri tranzistorjih s p kanalom, zato so ta vezja hitrejša. Slabost pa je fie vedno statična poraba energije. CMOS - /Complementary Metal Oxide Semiconductor/ vezja združujejo na isti rezini p in n kanalne tranzistorje. Vedno prevodni pull-up tranzistor PMOS in NMOS vezij je nadomesOeii z aktivnemu kompleinetitarnim tranzistorjem. Prevodna proga je naenkrat sklenjena le na nie ali na napajalno napetost in tako v mirovanju ni prevajanja med nielo in napajalno napetostjo. V mirovanju vezje zato praktično nima porabe. Omejitev so le plazeči tokovi nekaj laikroamperov. Ta vezja so tehnološko najbolj zahtevna, so malo veeja kot logični n ali p kanalni ekvivalent, zelo ao primerna za aplikacije z Seljeno majhno porabo. Nacrtovalsko ima vsaka družina vezij svoje tnale skrivnosti, osnovni principi so enaki. i.3,2 Delitev po stopnji integracije SSI - Small Scale Integration - v vezju je do sto elementov MSI - Medium Scale Integration - v vezju je med sto in tisoC elementov LSI - Large Scale Integration - v vezju je med tisoc in deset tisoc elementov - VLSI - Very Large Scale Integration - v vezju je med deset tisoc in dvesto tisoc elementov - üLSI - Ultra Large Scale Integration - v vezju je nad dvesto tisoe elementov. 1.3.3 Delitev po uporabi načrtovanju vezja Standardna vezja - Standardna LSI vezja - LSI vezja po naročilu® /Application Specific IC's/ in pristopu ASIC vezja Začelo se je z uporabo standardnih vezij, ker drugih v začetku ni bilo. Sera sodijo družine kot serija logičnih vezij 74, 7ilLS,. 54, 4000 ipd, enostavna analogna vezja (operacijski ojačevalniki, komparatorji, stabilizatorji napetosti in tokov ipd» in diskretni elementi (tranzistorji, diode, senzorji ipdl. Prednosti standardnih vezij so, da se jih v dolgem časovnem obdobju da kupiti praktično povsod, so relativno poceni, apremetnbe sistema so relativno neboleče tudi potem, ko je sistem Ze nacrtan. Slabost je obsežnost sistema, s tem združena poraba, zanesljivost je zaradi velikosti in atevila tiskanih povezav manjša, končna cena izdelka Je v primeru velikoserijake proizvodnje velika, saj je evropa kartica z dvajsetimi vezji gotovo dražja od enega vezja, ki bi opravljalo isto funkcijo. Standardna LSI vezja soi - elementi procesorskih družin (mikroprocesorji,PIA, ACIÄ, ROM, RAM, timerji ipd), modemi, filtri, linijski oddajniki in sprejemniki, naročniška vezja za telefonske centrale. Z standardnim LSI vezjem običajno reSimo kljucne probleme sistema, sistem Je običajno zanesljiv, majhen, cenen, poraba energije Je majhna. Slabost načrtovanja s takimi vezji je, da ta vezja naertovalcu aisteiwa vsiljujejo svojo filozofijo' delovanja Vez]a Ciato po naročilu so razvojnu izredno draqa in ni garancije za zelo kratek razvojni Oas. Nacrtovalec si za zastavljen problem izbere standardne celice, ki jih razmeati in poveze tako, da porabi Ci^m manjao površino silicija, Vkolikor reaitev v obliki standardnih celic za vse dele vezja nična, mora narediti nove standardne celice oziroma dele vezja na novo. Vez-^a iz standardnih celic so tista vezja po naročilu, kjer za vse dele vezja ze obstoje preizkušene standardne celice, ki jiti nacrtovalec , poveže v delujočo celoto. Standardne celice in povezave med njimi razmescano v vzdolžnih vrstah tako, da dobimo ob sicerSnji omejitvi naCrtovalske svobode z vzduiznifni vrstami C im nanjae dimenzije in optimalno delovanje vezja. Izdelamo vse maske za zahtevano vezje - ne le maske povezav, saj georaetrija vezja ni vnaprej definirana. Prihranimo na površini silicija, izboljšamo lastnosti vezja, razvojni stroSki so vecji kot pri mrežah . Je veC važnih kriterijev, kako ae odločiti za pravo ASIC vezje za kar najboljši ekonomski učinek. Napačna odločitev na tem nivoju je lahko katastrofalna, saj potegne za sabo od predragega izdelka do popolne zamude na trgu, kar pomeni veliko izyubo, nadaljnji odpor do take izdelave sisteraa in gotovo zato nadaljnjo nekonkurencnost. Kriteriji : velikost serije cena aiateraa zahtevana zanesljivost Število in kompleksnost funkcij Ijovrsina vezja realizacija analognih in digitalnih vezij poraba energije posebne zahteve doravnavanje lastnosti vezij možnost nadaljnjega razvoja sistema možnost načrtovanja in proizvodnje doma roki za izdelavo konkurenčnost na trgu Velikost serije - Stroski izdelanega vezja ae deiijo na začetne in proizvodne stroške. Jasno je, da majhne serije zelo slabo prenesejo visoke začetne stroekis in da gre pri velikih serijah predvsem za manjšanje proizvodnih stroskov, pa četudi je zato načrtovanje nekoliko dražje. Tako ima vsaka vrata ASIC vezij svojo količino, v kateri ima pogoje za optimalno ekonomska učinkovitost. Optimalna količina za PLA vezja je do nekaj deset tisoč, za ULA in UAA med nekaj tisoc in dvajset tisoc, za vezja po naročilu od nekaj deset tisoc naprej. Cena sistema - Z oziron na trzne zakonitosti, katerim je nas izdelek podrejen, se Ze v začetku odloČimo, ali je končni cilj nizka cena sistema ali velike zmoinoati, zaradi katerih bo sicer drazji, pa zaradi zmoznosti ne bo imel dovolj velike konkurence, ki hi zavrla njegovo prodajo. Ce je kriterij cena, bomo uporabili eira vec standadnih komponent in ASIC vezja pridejo v postev le pri velikih serijah in se to v poceni obliki (plastična DIL ohišja). Ce je kriterij velika zmožnost izdelka, pogosto uporabimo vezja po naroČilu v kakovostnejših ohišjih, Zaključene enote običajno realizirano z vezji po naroČilu. Zahtevana zanesljivost je dejavnik v prid vezjem ASIC, saj je vzrok odpovedi sistema navadno stik preveC ali premalo, za kar je v integriranem sistemu bistveno manj možnosti. Število in kompleksnost funkcij nam pomagata pri odločitvi med vezjem po naroČilu in laed predefiniranimi nreiami. Vkolikor so vezja mešana digitalno analogna, seveda izberemo vezje po naroČilu. Površina vezja je zelo ozko povezana s ceno vezja. Cena naraSCa z velikostjo vezja vec kot linearno, saj je zaradi napak v kristalni strukturi silicijeve rezine dober le določen odstotek vezij. Iiplen pada z velikostjo vezij, saj je pri vecjem vezju veCja verjetnost, da se bo na njen pojavila napaka. Sledi nelinearno visja cena vezja. Priznana rešitev je načrtovanje vezja .v tehnologiji a Cim manjao osnovno geometrijo - pet, trije mikroni, večkrat tudi manj in načrtovanje po naroČilu, kjer nacrtovalec praviloma dobro izrabi površino silicija. Poraba energije se z uporabo ASIC vezij navadno drastično zmanjša. Nastopijo pa lahko problemi s temperaturno disipacijo, vkolikor zahtevamo tokovno zmogljivejše izhode. Reaitev je prigradnja diskretnih komponent, kar pa je kompromis z zanesljivostjo. Z energetskega staliSCa so najugodnejša vezja CMOS, ki praktično nimajo statične porabe. Posebne zahteve navadno iahko uresničimo le z vezjem po naročilu. Take zahteve so povezane tudi s posebno ceno, saj samo z racionalnim načrtovanjem vedno vseh zahtev ne moremo uresničiti. VeCje sistemske hise razvijajo za potencialno ekonomsko zanimive posebne zahteve celo posebne tehnologije kot na primer za vezja, kjer je na isti rezini logika in močnostni elementi. Tudi velika hitrost je posebna zahteva. Klasične simulacije na hitrostni meji dane tehnologije odpovedo. Logična vrata simuliramo kot analogen element. Pred standardnimi komponentami ima ASIC vezje glede hitrosti vgrajeno prednost, saj je . vsota parazitskih kapacitivnoati priključkov in povezav gotovo manjša. Tako iahko a pet raikronako CMOS tehnologijo doaežemo do 25 MHz, s tri mikronsko CMOS tehnologijo do 100 MHz hitrosti. Doravnavanje lastnosti vezij je gotovo željena možnost, saj se tako Izognemo raznim potenciometrom, trimerjèm, doravnavanju lastnosti vezja na tiskani ploaci, ki je praviloma dražje od doravnavanja na silicijevi rezini pred inkapsulacijo. Poravnavamo tako, da izdelamo na vezju vrsto prezigalnih elementov, ki jih prezigatno a tokom ali z laserskim Žarkom . S tem povežemo ali razklenemo doravnalne elemente; navadno precizno «merimo uporovno verigo, določimo kapaciteto kondenzatorja. Seveda je preJiganje ireverzibilen postopek in moramo pred preziganjem izmeriti karakteristike vezja ter izračunati, katere elemente moramo prezgati, da bomo dosegli željene lastnosti. Zato je doravnavanje 2e del testiranja silicijeve tabletke na rezini in ga krmilimio z računalnikom testne naprave. Možnost nadaljnjega razvoja sistema je vedno dobrodošla In nujna, vkolikor naj bo sistem vsaj par let trZno zanimiv. Zato moramo pri razdelitvi aisteina paziti, da ga razdelimo na smiselne vase zaključene celote s Cim manj zunanjimi povezavami. Modularnost omogoča, da posamezne dele vezja spreminjamo ali naredimo v novi tehnologiji, ne da bi zato morali apreminjati cel sistem. Moinoat načrtovanja in proizvodnje doma 2riiza atroake vezja tudi za velikostni razred, stroški so dinarski. Po tem kriteriju realizirano vezja v MOS tehnologiji. Roki za izdelavo nas vcasih prisilijo v izbiro enostavnejših ASIC vezij - PLA, ULA in rešitve zato telmicno lahko v prvem koraku niso najboljše. Vendar je bolje prodati slabši aiatem, ta sistem nato naprej razvijati kot priti na trg za vso konkurenco. V aploanem se eas načrtovanja z večanjem nacrtova1akih izkušenj in uvajanjem simulatorjev, računalniške grafike, krajša. Konkurenčnost na trgu je posledica majhnih, zmogljivih, cenenih aistemov, kar ASICs vsekakor omogočajo veliko bolje kot samo standardne komponente. 2 Smernice razvoja Pri smernicah razvoja se kazeta dokaj ostro ločeni področji razvoja tehnologije in razvoja načrtovanja. 2.1 Smernice razvoja tehnologije Bazvoj tehnologije gre v vec smeri, saj ima industrija vec zahtev, ki niso vae združljive in naenkrat zahtevane. Glavne razvojne smernice ao aledece: skaliranje dimenzij izdelava Smart Power vezij izdeiava Bi«OS vezij izdelava vezij na galijevem arzenidu 2.1.1 Skaliranje Danes so industrijski standard vezja z oinimalno dimenzijo dveh mikronov. Ce je roinimalniB dimenzija (običajno je to dolžina tranzistorja» manjša, je celo vezje manjše, načelno hitrejše, manj porabi. Same dobre atvari. Je pa vezje gotovo draije, saj ob manjšanju dimenzij naatopi vrsta stranskih pojavov, ki iih le treba upoštevati ali el iiiiiniraci.. Po Dennardovem pravilu pri skallranju zmanjšamo vae geometrije in napajalno napetost s faktorjem akaliranja S, koncentracijo neeiatoc v substratu povečamo z l/S. Namen tega je Izdelati manjše elemente s karakteristikami večjih elementov. Teoretično s faktorjem skdliranja S zmanjšamo tok skozi elemente, zmanjšamo S-krat tudi zakasnitev skozi elemente, disipacija moci je zmanjšana z faktorjem S2. Vkolikor skaliramo tudi povezave, se jim upornost poveca - ob zmanjšanju parazitskih kapacit ivnosti se RC konstanta ohranja. v praksi povprečna dolžina povezave po akaliranju ni krajša, saj je namen skaliranja gradnja večjih (in hitrejših» vezij. Torej bo v prihodnje poleg zelo dobrega modeliranja elementov v submikronskem območju velik poudarek na tehnikah za zmanjšanje RC konstant. So povaem fizikalne omejitve, zaradi katerih je spodnja meja uporabne minimalne dimenzije tranzistorjev, kot jih danes poznamo, pri pol mikrona. - Napajanja v nedogled ne moremo nizati, saj je pragovna napetoat tranzistorja podana z razliko energijskih paaov p in n dopiranega si 1icija. Prebojne napetosti ao določene s kritično poljsko jakostjo in debelino izolacijskih plasti . Spodnja meja tankosti povezav je določena z zacetkOBi migracije prevodne kovine kot posledico maksimalne tokovne gostote. Skaliranje je omejeno tudi s stališča uporabnika. Danes je industrijski standard pet voltno napajanje in TTL logični nivoji. Prehod navzdol ekonomsko se ni upravičen, saj potegne za sabo poleg kopice formalnih problemov tudi novo poglavje o Sumu in motnjah. Kljub visokim vlaganjem - za skaliranje pod dva mikrona je v precej tehnoloških korakih potrebna drugačna oprema zaradi tanjsih in bolje definiranih plasti - tudi razvita Evropa sledi Japoncem in Američanom, saj je bila prva lekcija o tehnološkem zaostajanju na področju elektronike dovolj poučna. 2.1.2 Izdelava Smart Power vezij Ogromno je aplikacij zlasti v industrijski elektroniki, avtomatizaciji, avtomobilski elektroniki, široki potrošnji, kjer na osnovi logičnih odločitev izvedemo določene moCnejSe preklope. Ustaljena realizacija je tiskano vezje z elementi ene logičnih družin s podatkovnim držalom, ki krmili diskretne tranzistorje, sledijo pa lahko Se releji. Velikost, temperatura, poraba, zanesljivost so dejanski problemi. Smart Power vezja, kjer Je na istem cipu logični in močnostni del, nam na stopnji svoje tehnološke zrelosti te probleme odpravijo. Pobudo za taka vezja je dal uporabniški del mikroelektronike sistemskih hia, odgovor je moral priti s strani tehnologije. Zato so začetki vidnih poskusov v letu 1983, večji razmah takih vezij pa je Sele letos. Glavni tehnološki problem je ustrezna izolacija med mocnostnirai stikali in logičnim delom, majhna upornost, tokovna zmogljivost, visoka prebojna napetoat stikal. izolacijo dosegajo z zaporno polariziranimi p" n spoji, s posebnimi izolacijskimi difuzijami. Trenutno najboljša in najdražja je izolacija i dielektriki, vnesenimi v silicijevo rezino, na katerih oblikujemo močnostne elemente. Tovrstna izolacija prenese napetosti cez tisoc voltov. Majhno upornost stikal dosegajo z vec manjših stikal povezanih vzporedno. Druga bolj ravna pot je striktno manjšanje upornosti kanala, vira, ponora, dovodov toka. Ustrezni tehnološki koraki pa istočasno nizajo prebojno napetost med virom in ponorocn, tako da v tej ameri ni reSitve. Trenutno znajo v avetu narediti močnostne tranzistorje z do tri miljone vzporedno vezanih stikalnih celic na kvadratno inco. Obenem z manjšanjem upornosti pridobivamo na tokovni zmogljivosti stikal. visoko prebojno napetost dosežemo z razmaknitvijo vira in ponora tranzistorja. Izdelamo strukturo npn-n. Vrata ao p področje, n- v primeru pozitivno polariziranega ponora sluzi kot izolator. Tako razlika napetosti vira in ponora ni omejena le na ozko območje p, ki predstavlja dejanski tokovni ventil. Današnja tipska področja uporabe Smart Power vezij so krmiljenje motorjev IGEStoartl, avtomobilska industrija ISGS, Motorola, Hostek, International Rectyfier, Rockwell), krmilniki prikazalnikov (SGS, Supertex, Siliconi*, Telmos, Sprague, TI, Moatekl, napajalniki (Integrated Power Semiconductors, International Rectifier), krmiljenje koračnih motorjev (Integrated Power Semiconductors, Unitrode). 2.1.3 BiHOS vezja so v končni obliki hitrejša in manjša od bipolarnih in MOS vezij posebej. ZdruZujejo prednosti MOS - nizka disipacija moci, manjsa občutljivost na 6um, in prednosti bipolarnih tranzistorjev - preklopna hitrost, bolje definirano obnašanje v linearnem območju, boljši tokovni viri. Da ae ta vezja niso pojavila 2e prej, so krivi postopki izdelave. Trebà je namreč postaviti proces izdelave vezja, ki istočasno zagotavlja dobre bipolarne in MOS tranzistorje. Letos tak proces zahteva taćd šestnajst in dvajset mask. Potencialna uporaba teh vezij je DRAM (hitrost kombinirana B cim nil jo porabo), vezja za prenos in obdelavo podatkov. 2.1.4 Vezja na galijevem arzenidu V razvoj tovrstnih vezij ae investira iz veC razlogov: Ta vezja so do pet krat hitrejša od ECL vezij na siliciju. Gibljivost elektronov v GaAs je okrog devet krat vecja od gibljivosti elektronov v siliciju. Mnogo laze je doseči visoko stopnjo integracije, saj je nedopiran GaAs izolator in 9 tem prihranimo precej procesnih korakov, ki ao pri siliciju potrebni zaradi izolacije med aktivnimi deli vezja. Vezja na GaAs manj sumijo od vezij na siliciju. Toplotna prevodnost GaAs je veoja od le te silicija (hlajenje). V temperaturnem obinoOju -200, 200 stopinj Celzija se električne lastnosti gradnikov ve^ij na GaAs spreminjajo znosno in lahko z dobrim načrtovanjem definiramo tako področje uporabe. Glavni problem danes pa so dragi substrati. So tudi krhki in imajo mnogo napak. Danes je cena GaAs rezine tridesetkrat vecja od cene silicijeve rezine. Ce k temu prištejemo se laanjsi izplen zaradi veCje gostote napak, pa del razvojnih stroškov, je cena vezja na GaAs hitro dva velikostna razreda viaja od cene vezja na siliciju z enako logično shemo. Največ v pridobivanje substratov investirajo Japonci, tako da lahko upravičeno pričakujemo, da bodo japonski proizvajalci vezij na GaAs osvojila večji delež trzisca. Danes je največje torišče delovanja na GaAs področje nizkosumnih ojačevalnikov, ki jih zahtevajo satelitske in vojaške komunikacije. Tako visokih frekvenc in tako nizkega nivoja suma na siliciju ne moremo doseči. Tuđi logične mreže na GaAa so že razvite. Letos so poprečne zakasnitve na vratih 30 ps, poraba je 200 mW. Proizvajalci so Harris, Honeywell, TI, Ford Microelectronics, NT4T, Toshiba. stroški Hooeywellove logične mreže z dva tisoč vrati in gestinpetdeset I/O celicami ao sto desettisoc dolarjev. 2.2 Snernice razvoja načrtovanja V zadnjih nekaj letih se je programska oprema za načrtovanje integriranih vezij neverjetno razvila. Starejsi programi na miniraCuna1nikih so postali zastareli, saj potrebujejo preveC računalniškega casa na teh relativno dragih procesorjih. V industriji integriranih vezij je prevladalo mnenje, da je pisanje lastne programske opreme za načrtovanje integriranih vezij zelo zahtevno in neekonomično. To si lahko privoščijo le največje družbe. Večina manjših in srednjih proizvajalcev programsko opremo kupuje pri za to področje specializiranih firmah. Njihovi lastni strokovnjaki se ukvarjajo samo 3e z združevanjem različnih paketov v enoten sistem. Večina te programske opreme sedaj deluje na delovnih postajah, ki jih je moc povezati z. mrežo Ethernet. Te delovne postaje so opremljene s posebnimi pospeaeva1niki specializirano opremo namenjeno enemu samemu postopku. Ti pospesevalniki so prišli najbolj do veljave pri logični simulaciji in simulaciji napak, kjer le to sedaj opravlja v veliki meri strojna oprema eama, kar je seveda hitrejše kot programi z najboljšimi algoritmi. Razlika v hitrosti delovanja je med 10 in 100 krat. In izdelavo zelo obsežnih integriranih vezij ne pride veC v postev klasično načrtovanje vezij po naroČilu, saj bi tako načrtovanje vezij z 100.000 do 1.000.000 vrati trajalo nekaj let, kar seveda ni sprejemljivo. Trenutno so na vrhuncu programi za avtomatično namestanje in povezovanje standardnih celic in logičnih mreZ, vedno bolj pa se uveljavljajo prevajalniki na silicij. Končni cilj načrtovanja je eira hitrejša izdelava vezja, ki bo delovalo le v prvem poskusu. Torej je treba povsem izključiti predvidljive napake. Le te lahko nastopajo v interakciji med posameznimi programi, lahko so napake v programih samih, lahko so posledica človeškega faktorja. Prvo in drugo možnost s skrbnim preverjanjem programske opreme lahko izključimo, tretjo pa zmanjšamo tako, da cimvec načrtovalskih postopkov avtoisatiziramo. Pri načrtovanju integriranih vezij z prevajalniki na silicij nacrtovalec vnese logično shemo, ieljene signalne zahteve, oznako procesa, v katerem bo vezje izdelano in s tem posredno izbere za ta proces specif iena nacrtovalska pravila. Izhod programskega paketa je končna geometrija vezja, po kateri izdelajo maske. Človeški faktor je omejen le ae na napačno zastavljen problem. Gotovo bo Bel razvoj na področju programske opreme v prihodnjih letih v smer Izdelave Cim popolnejših prevajalnikov na siliciju. Danes anajo najboljši prevajalniki nacrtati bit slice procesor. Razvojno zahtevna vezja pa bodo gotovo tudi v prihodnje delali precej roCno, saj je znanje treba najprej osvojiti, da ga-lahko vgradiš v samostojen nacrtovalski sistem. Gotovo bodo avtomatizmi na področju načrtovanja vezja lahko pocenili, razvojni cas bo krajši in načrtovalskih napak bo manj. Tudi razvoj danes zahtevnih vezij bo lahko hitrejši in cenejši. 3 Oris načrtovalskega postopka od zasnovane logične sheme do narejenih mask . v DO Mikroelektronika Načrtovanje integriranih vezij je zelo zahteven postopek. Integrirano vezje lahko sestavlja nekaj sto do nekaj sto tisoC medsebojno povezanih aktivnih in pasivnih elementov. Podatkovne baze za opis takega vezja so zato velike, kljub temu pa ne sinejo vsebovati napak, v naslednjih nekaj vrsticah bi rada pokazala možnosti in perspektive načrtovanja integriranih vezij v Iskri. Zaradi obsežnosti podatkov, ki opisujejo integrirano vezje, je moZnost vnosa napake pri načrtovanju zelo velika. Vsaka napaka ponavadi pomeni, da vezje ne bo delovalo tako, kot je bilo zamišljeno, zato se vedno bolj uveljavljajo postopki, ki avtomatizirajo posamezne postopke v procesu načrtovanja. Integrirana vezja po naročilu delimo glede na metodo načrtovanja na tri skupine: - naročniška vezja - vezja iz standardnih celic logične mreZe v Iskri DO Mikroelektronika imamo precej zmogljiv sistem za računalniško podprto načrtovanje integriranih vezij, ki omogoča načrtovanje vseh treh zvrsti. Postopki za načrtovanje se od skupine do skupine razlikujejo. Razlikuje se tudi potrebni Cas za razvoj takega vezja, s Cem pa tudi stroški razvoja. Ti direktno vplivajo na konCno ceno vezja. Drug pomemben faktor, ki vpliva na 38 končno ceno, pa je površina vezja na Biliciju. stroski razvoja so obratno sorazmerni površini vezja na siliciju. Najdražji in najbolj dolgotrajen je razvoj naroCniekih vezij, ki da najmanjšo površino na siliciju. Najcenejši je razvoj logičnih mreZ, pri katerih je za končno konfiguracijo potrebno izdelati eno samo masko, sestevek obeh stroškov pokaie, da ae izplača izdelovati glede na atevilo kosov: do 20.000 vezja na osnovi logičnih itire2 - od 20.000 do 100.000 vezja na osnovi standardnih celic - nad lOU.OOO naročniška vezja. Nekateri postopki so pri vseh treh metodah načrtovanja enaki, drugi pa se razlikujejo, lajeni shematskega opisa vezja in logična simulacija sta n.pr. enotna medtem ko je izdelava geometrije različna. V nadaljevanju bova najprej opisali programsko opremo, ki jo imamo v Mikroelektronik!, nakar bova podrobneje obdelala vrstni red postopkov pri vseh treh metodah načrtovanja. TeZko je oceniti caa, ki je potreben za izdelavo logičnega oz. funkcionalnega opisa vezja. Ta je odvisen predvsem od izkuaenoatl nacrtovalca in kompleksnosti vezja. Mnogo laze je oceniti caa, ki je potreben od trenutka. ko je opis vezja gotov, do konCne realizacije. 3.1 Pregled programske opreme VeČina obstoječe programske opreme bazira na niniracunalniku VAX 11/760. Nekaj manj obsežnih programov, ki jih v glavnem uporabljamo za vnos podatkov deluje na osebnih računalnikih. To so programi za izdelavo integriranih vezij z metodo standardnih celic, ki pa pridejo do prave veljave 9ele, ko imamo na [niniracunalniku obsežno in preverjeno bazo podatkov. Programski paket SItjS za načrtovanje integriranih vezij po naročilu smo kupili od licencnega partnerja Gould AMI. Ta paket programov je deloval na računalnikih Prime, zato ae je tedanje vodstvo razvoja odloČilo za konverzijo te programske opreme na računalnik VAX, ki ima v Jugoslaviji zagotovljeno vzdrževanje. Kupili smo tudi programe za vnoa logičnega opisa vezja in logično simulacijo. Kupljeni so bili naslednji programi; bOLT - prevajalnik opisa vezja - SIMAD - logični simulator - HOLONET - ekstrakcija velikosti tranzistorjev in povezav med njimi iz logičnega opisa SIDSED - simbolično urejevanje geometrije vezja uporabljamo za načrtovanje naročniških vezij in standardnih celic SDRC - preverjanje naCrtovalakih pravil v simbolični bazi podatkov - STKACE - preverjanje električne skladnosti simboličnega opisa in ekstrakcija velikosti tranzistorjev in povezav med njimi iz simboličnega opisa SPRINT - izpis simboličnega opisa STP - pretvarjanje iz simboličnega v geometrični opis GPLOT - izris geometrične baze podatkov - compare - primerjava velikosti tranzistorjev in povezav med njimi, ki jih dohitno IZ logičnega in iz simboličnega opisa. SPICE - analogni simulator Kritični elementi v tem paketu so: SIMAD, ki je za zelo obsežna vezja zelo počasen. Simulacija poteka tudi po nekaj dni STRACE je za zelo obsesna vezja zelo počasen 0 0 0 e 0 0 B 0 0 0 0 8 0 0 0 0 i 1 2 2 3 0 e 0 6 0 6 0 0072 007J 0070 0069 0067 0066 0066 0B64 saE3 0062 0061 0060 0069 00G8 BB67 0OS6 8366 0064 0063 0062 0061 0068 0049 0048 0047 0046 B04S iiiiiiiimuiuiiiiiiiituiiiiii 111111 inisniiixiiniin limili VDDlllllADIlllllBUlllllQUlUlll 111 ! ì 111 n 111 / / 111 -------a-----8—---♦++ ♦OH----a-----a----+++ ♦++-—a-----a----- 0022 0021 0020 0019 aeie 0017 001E 0014 0013 0012 0011 aaiB 0008 0007 0005 0004 0003 0002 ♦♦+----a-----a-----+++ ♦++----a---a-----^0+ ♦++----a-----4-----+0+ +++----a-----a-----+S+ ♦ <•4.----,-----4-----+S* -------a----a-----*D* ♦0*----■-----«-----»0+ -------,-----,-------- -----aia-----aaa------ -a—+0«-—a- —«---------a // // // // // II it // // // // // // H n t! It H // // U u ----4--- / iniiixiiinmiQx 0044 / / »X 0043 . / / 11 0042 i / 11 0041 mi m 11 8040 ì / 11 0039 / / NOZl U 8038 / t 11 0037 gs«gg / t ggggggggeE 0036 gGGGg / ! gGGGggggGG 0036 geSGg / / gGtSggggBG 0034 gGGGg / ! flGGGflgggGG 0033 gGGGg ! / oGggggggGG 0032 111 / / 1 11 0031 111 t / 1 11 0030 111 ! / 1 11 0029 111 U / 1 11 0028 llllllIllllDIlllll 11 0027 11 / / 11 0026 11 / / 11 0026 ------- ■a— —J— ---- 11 0024 •»— —a— ----- 11 0023 -4+---- -a— —a— -+++111111 ++H----J-----,---tt+llUll ♦0*----a-----a----«-0*111111 ---,-----4----«+111111 ---1-----a----+++111111 ♦♦♦----m----------♦♦+111111 ----,-----4----+♦+111111 +0+" -1---+0+111111 ++♦----J-----J----+++U1111 ----a-----J----+++1111U in ui 111 111 ///tit ///KM ///%S% ////// fnm m /// +♦+----a-----a---- ♦++----a-----a---- ++H----a----a--- +++----a----a--- -a-----a---- ♦ OH--- 0072 0071 0070 0069 0OS8 0067 0066 0066 0064 0B63 0062 0061 0060 00B9 «057 BBSS 0064 0053 0062 aeei 006« 0049 004B 0047 0046 0045 0044 0043 0042 0041 0039 0038 0037 0036 003B 0034 0033 0032 0031 0030 0029 0028 0027 0026 0026 B024 0023 0022 0021 0020 0019 0018 0017 0B16 0016 0014 0013 0012 B011 0018 0009 0^7 +++----,----.J--- 111 / / lllUtllUXllUlXlllUllMIllllll iiiiiiiiiixiitiitiiiiiiUMmiii vssuiumuiivBiuuiioxtviim 0002 0001 SUka 1 Izris simbolične baze podatkov za dvovhodna vrata NaND na elektrostatičnem risalniku. Nekaj osnovnih znakov; "a"- vrata tranzistorja difuzija "1"-metal "/"- pollsilicij SDRC, ki je za obaeina vezja lelo počasen. Preverjanje nacrtova1akih pravil poteka tudi po nekaj dni. Ni ga moC uporabiti za zelo obaezna vesja STP, ki je za obaeina vezja lelo počasen. Pretvarjanje siinbo J icnega opisa v geometrični opis poteka tudi po nekaj dni. Na ga moC uporabiti za zelo obsežna vezja COMPARE, kl je za zelo obsežna vezja zelo počasen. Simulacija poteka tudi po nekaj dni. Probien smo reševali z uvedbo metode načrtovanja s standardnimi celicami, pri kateri podatke zajemamo in logično aimuliramo na osebnih računalnikih s programakim paketom SCF.PTSE. Pomanjkljivost tega paketa je, da je njegov izhod komandna procedura za program SIDSED, ki iloli celotno vezje v simbolični obliki. Celice so nacrtane tako, da ne r.ioremo kršiti nacrtovaiakih pravil " pri njihovem nameščanju in povezovanju, zato preverjanje nacrtovalskih pravil na simboličnem opiau odpade. Compare prav tako odpade, ker ga do neke mere nadomesti programska oprema SCEPTRE. Problem predstavlja pretvorba iz simboličnega v geonetricni opis, zato smo sami napisali program, s katerim je moC komandno proceduro, ki je rezultat programskega paketa SCEPTRE, direktno pretvoriti v geometrično obliko. Ta postopek je na ta način atokrat hitrejši. Pri AMI-ju smo kupili tudi paket CIPAR, ki üncjgoCrf avtomatično nameščanje in povezovanje standardnih celic. Program je dokaj neučinkovit. Izkoriščenost površine na siliciju se precej izboljša z uporabo optinizator ja Tiiuberwolf l.U z Beckeleyske univerze, se bolj pa bi se z uporabo procesa z dvema plastema metala. Shematski vnos in logično simulacijo iz paketa SCitPTHE uporabljamo tudi za načrtovanje vezij po metodi logičnih mre2. Sami smo morali napisati program za grafično urejanje geometrije vezja. Končni produkt postopka načrtovanja so datoteke, ki jih zapišemo na trak, 3 katerim krmilimo generator vzorcev - napravo, s katero se izdelajo maske in vzorci za avtomatsko testno opremo. Program za pretvorbo geometrijske baze podatkov v datoteke za generator vzorcev (PG( smo napisali sarai. 3.2 Načrtovanje z logičnimi mrežami Kot ava ze omenila, le to metoda, s katero najhitreje pridemo do integriranega vezja. Samo načrtovanje je zelo podobno načrtovanju z metodo standardnih celic, bistvena razlika pa je koncni produkt procesa načrtovanja. Pri metodi logičnih mrež dobimo eno masko, medtem ko pri metodi načrtovanja a standardnimi celicami dobimo toliko mask, kot jih proces zahteva (8-9 maski. Ko je maska pripravljena, je pot do konCnega vezja zelo kratka. Logične mreze se izdelujejo na ze pripravljenih rezinah, ki so izdelane do določene stopnje, tako da jih je moC dokončati v enem tednu. Načrtovanje se zaCne z vnosom logičnega opisa v računalnik. Pri tem imamo dve možnosti. Logiko lahko z urejevalnikom teksta vnesemo na alfanumericnem terminalu računalnika VAX ali pa na osebnem računalniku Sirius ali IBM PC/XT. Vnađanje logike je lažje na osebnem računalniku, kjer je v paketu programov SCEPTRE grafični urejevalnik, ki omogoča shematski vnos. Pn vnosu logike je treba zelo paziti, da je mozno vezje na zunanjih sponkah zadovoljivo testirati. Pri intergiranih vezjih naiarec ni nozno merjenje signalov med (n CJ 2: o a: in X cc I Slika 2 Izris geometrične baze podatkov za dvDvhodna vrata NAND posameznimi elementi vezja. Ko je logika vnesena, jo preizkusimo s programom za logicno simulacijo. Ce izhodni vzorci, ki jih dobimo s simulacijo, ne ustrezajo zamial jenin, z graficnini urejevalnikom popravimo shemo in ponovno simuliramo. Postopek ponavljasio toliko casa, da smo zadovoljni z odzivi vezja, ki jih pokaZe aiinulacija. Logično shemo lahko izrišemo na matričnem tiskalniku ali pa na risalniku, ki omogoča izdelavo dokuKietaci je vezja. Pravilnost logičnega opisa je seveda predpogoj za pravilno delovanje vexja. Logičen opis zàtero prenesemo na VAX, kjer vezje ponovno simuliramo s programom SIMAĐ. Ta simulacija je samo dodatna kontrola. Izhodne datoteke, ki jih dobimo, pa je nozno i drugim programom pretvoriti v testne vzorce ia avtomatsko testno napravo. Vnos logike in izdelava potrebne dokumentacije vzame načrtovalcu en do dva tedna. Tu prevzame delo naCrtovalec aestavnice mask ali pa ga nadaljuje načrtovalec aam. Ko je simulacija gotova, pristopimo k zadnjemu interaktivnemu postopku. S posebnim programom začnemo sestavljati geometrijo. Na predefinirani mreli' postavljamo in povezujemo celice. Program je uporabniško prijazen, zato je delo hitro in učinkovito. Vse spremembe, ki jih vnesemo s pomočjo tipkovnice in miake, se sproti pojavljajo na zaslonu, na katerem lahko prikajemo manjši del vezja in s tem večje podrobnosti ali celotno vezje zaradi boljšega globalnega pregleda. Tudi geometrijo lahko izrišemo na matričnem tiskalniku. Za to delo Slika 3 Primer vezja iz standardnih celic, ki ga je sloziL program za avtomatično nameščanje in povezovanje celic. Vezje je razdeljeno na periferijo, ki jo sestavljajo vtuxlno izhodne celice {A, 3, C; D, CL, 8, VSS, VDD ) in jedro. Z jedrnimi celicami realiziramo beljene logične ali analogne funkcije, ki jih uporabljamo preko vhodno izhodnih celic, ki hlcrati varujejo vezje pred elektrostatskimi razelektritvami. potrebujemo enega Človeka nekaj dni. Ko je poatavljanje in povezovanje celic gotovo> dru9 načrtovalec preveri skladnost med logično Bhesio in geometrijo, napake ae popravijo. Podatke a posebnim programom nato preneaemo v obliki tekstovne datoteke po terminalaki liniji na VAX, kjer drug program celice nadomesti z njihovo vsebino, povezave pa zamenja z ustreznimi pravokotniki. Do končnega rezultata, t.j. maake za generator vzorcev, moramo izvesti ae nekaj avtooaticnih poatopkov. Dobljeni geometrijski bazi podatkov pripiaeno podatke, ki bo na metalnem nivoju fiksni (napajalne linije, ...), vezje za dokumentacijo izrieemo na elektrostatičnem risalniku in nazadnje pretvorimo geometrično detoteko v datoteke za generator vzorcev. Izurjen nacrtovalec potrebuje za celoten proces načrtovanja dva do tri tedne. Izdelava mask traja en dan, vendar je treba zaradi zasedenosti opreme včasih čakati tudi po dva do fttiri tedne. Rezine z logičnimi mrežami je treba &e dvakrat maskirati. Od vezja do vezja se spreminja samo metalna maska. Izdelati je treba metalne povezave in narediti odprtine v paaivaciji na mestih, kjer se pritrdijo zicke, ki silicijevo ploščico povezujejo z nozicami na ohitfju. Procesiranje poteka nekaj dni. Z dobro časovno usklajenostjo posameznih poatopkov je tako pri logičnih mrežah možno priti od logične sheme do vezja v enem mesecu. 3.3 Načrtovanje a standardnimi celicami Z metodo standardnih celic dosežemo boljši izkoristek površine na siliciju. Tu je postopek načrtovanja podoben opisanemu postopku načrtovanja po metodi logičnih mrež. Rezultat načrtovanja so maske za vae nivoje. Pri nasih standardnih osem in devet nivojakih procesih traja procesiranje približno en mesec. Metoda standardnih celic omogoča izdelavo logičnih in analognih integriranih vezij. Pri analognih vezjih je fiogosto potrebno nacrtati novo ali prirediti obatojeco celico. Nacrtovalec mora zato znati uporabljati analogni simulator Spice. Načrtovanje ae začne z vnoaotn logičnega oz. funkcionalnega opisa vezja v računalnik. Ta je povsem enak kot pri logičnih mreZah. Tudi tu se po vnosu podatkov menjavajo simulacije in popravki. Preverjen logičen opis zatem prenesemo na VAX, kjer vezje ponovno simuliramo a prograraon SIMAD. Ta simulacija je samo dodatna kontrola, izhodne datoteke, ki jih dobimo, pa je mozno z drugim programom pretvoriti v testne vzorce za avtomatsko testno napravo. Vezja iz standardnih celic so vcasih kompleksnejša kot logične mreZe, ki so omejene z največjim modelom, ki ga izdelujemo (t.j, 1200 ekvivalentnih vrat). Vnos logike in izdelava potrebne dokumentacije vzame naCrtovalcu en do tri tedne. Ko amo z simulacijo logičnega oz. funkcionalnega opisa zadovoljni, je treba namestiti in povezati celice. Za to imamo dve metodi. Prva je rocno nameščanje in povezovanje na osebnem računalniku, druga pa je avtomatično ' nameščanje in povezovanje na miniracunalniku. Za avtomatičen postopek uporabljamo program Cipar iz paketa programov Cipar. S poittoejo optimizatorja Timberwolf se izboljša izkoriščenost površine silicija. Vhodni podatki za program so obstoječe datoteke z logičnim oz. funkcionalnim opisom vezja. Program sam postavi in poveZe celice integriranega vezja. Obdeluje jih kot pravokotnike, ki jih postavi paroma v vrste in jih poveze v kanalih med vrstami. Dodatni programi iz paketa Cipar omogočijo izris geometrije na elektrostatičnem risalniku in pretvorbo geometrije v pravo geometrično bazo podatkov, med katero program nadomesti pravokotnike 2 njihovo vsebino, povezave pa s pravokotniki. Izdelava geometrije vzame en do dva dni. Boljšo izkoriščenost površine silicija dosežemo z grafičnim urejevalnikom iz paketa programov SCEPTRC na osebnem računalniku. Razlika v površini integriranega vezja je med 10% in 30%. Program dovoljuje nameščanje celic in povezav na mrezo, katere vozlišča ao dovolj oddaljena drugo od drugega, da ni mogoCe kršiti nacrtovalskih pravil. SCEPTRE omogoča tudi primerjavo med izdelano geometrijo in logičnim opisom. Ko je doseženo ujemanje med geometrijo in logičnim opisom, podatke s posebnim t>ro9raiiiom prenesemo v obliki tekatovne datoteke po terminalski liniji na VAX, kjer drug program celice nadomesti z njihovo vsebino, povezave pa zamenja z ustreznimi pravokotniki. Kadaljni postopek za izdelavo trakov za generator vzorcev je enak kot pri logičnih mrežah. Izurjen načrtovalec potrebuje za celoten proces vnosa logičnega oz. funkcionalnega opisa en do tri tedne. Načrtovalec geotnerije mask potrebuje za rocno nameščanje in povezovanje celic en do dva tedna. Izdelava mask traja nekaj dni. Rezine z vezji nacrtanimi po metodi standardnih celic morajo skozi celoten proces, kar zaradi množice različnih poatopkov traja približno en mesec. Z dobro časovno usklajenostjo posameznih postopkov je tako pri standardnih celicah »ozno priti od logične sheme do vezja v dveh do treh nesecih. 3.4 Načrtovanje naročniških vezij Načrtovanje naročniških (full custom} vezij je najdolgotrajnejsi postopek. S to metodo dosežemo najboljši izkoristek, kar ae pri zelo velikih serijah seveda izplaCa. Rezultat načrtovanja so maske za vse nivoje. Pri naSih standardnih osem in devet nivojakih procesih traja procesiranje približno en mesec. Ta metoda ne pride v naaih razmerah velikokrat v postev, saj so serije vezij, ki jih pri nas naročajo razna podjetja ponavadi premajhne, da bi cena posameznega vezja prenesla razvojne atroske. Naročnik mora potrebovati vsaj 100.000 vezij, da se mu to izplača. Tudi ta metoda omogoča izdelavo logičnih in analognih vezij. Načrtovanje se zaCne z vnoaom logičnega oz. funkcionalnega opisa vezja v računalnik. Ta postopek je povsem enak kot pri logičnih lareiah in standardnih celicah. Tudi tu se po vnosu podatkov menjavajo simulacije in popravki. Preverjen logičen opis zatem prenesemo na VAX, kjer vezje ponovno simuliramo a programom SIMAD. Ta aimulacija je samo dodatna kontrola, izhodne datoteke, ki jih dobimo, pa je mozno z drugim programom pretvoriti v testne vzorce za avtomatsko testno napravo. Kompleksnost naročniških vezij je podobna kot je kompleksnost vezij s standardnimi celicami. Vnos logike in izdelava potrebne dokumentacije vzame nacrtovalcu en do tri tedne. Pri naročniških vezjih ae tu delo Sele zaCne. Sedaj je treba posamezne logične oz. funkcionalne bloke Izdelati tako, da zavzamejo cita mànj površine na siliciju. Vsako celico je potrebno električno aißulirati in optimizirati za dano meato v vezju. To delo je dolgotrajen poatopek, ki zahteva izkušenega načrtovalca. Ko je geometrija poaameznih blokov narejena, jih je treba namestiti Čimbolj skupaj in povezati. Med nameSCanjeia in povezovanjem je včasih potrebno katerega od blokov spremeniti. Geometrijo načrtujemo na ^seraigraficnih barvnih terminalih s pomočjo programa Sidsed. Ko je geometrija gotova s programoma Sdrc in Strace preverin», ce je vezje nacrtano po nacrtovalskih pravilih in električno skladnost simboličnega opisa. Strace nam izloči tudi velikosti tranzistorjev in povezav med njimi iz simboličnega opisa. S programom Compare nazadnje primerjamo velikosti tranzistorjev in povezav med njimi, ki jih dobimo iz logičnega' in iz simboličnega opisa. Vse to preverjanj« zagotavlja, da nacrtano vezje nima napak. Zadnji program Iz paketa SIDS Stp nam pretvori simbolični opis v mnogokotnike in jih zapiae v geometrično bazo podatkov. To je moc izrisati na elektrostatični risalnik. tzurjen nacrtovalec potrebuje za celoten proces vnosa loglCnga 02. funkcionalnega opisa en do tri tedne. Skupaj z načrtovalcem geomerlje mask potrebuje izdelavo blokov in za roCno nameščanje in povezovanje le teh nekaj mesecev. Ostali postopki trajajo toliko Casa kot pri metodi standardnih celic, kar da skupaj vec kot tri mesece. Viri i 1. Power MOSFETs; Power for the aOs, Duncan Grant, Allan Tregidga, Solid State Technology, Nov. 1985 3. Mixed process chips are about to hit the big time, Bernard Conrad Cole, Electronics, March 3, 1986 3, 1, »ola za načrtovanje mikroelektronsklh vezij v Iskri; interno gradivo , Nov. 198S 4. Stretching the limits of software, Bernard Conrad Cole, Electronics, June 23, 1966 POVEZOVALNE MREŽE VEČPROCESORSKIH SISTEMOV INFORMATICA 4/86 UDK: 681.324 Slavko Mavric, Branko MihoHovfč, Pater Kolbezan Institut Jožef Stefan, LJubljana tlsnek predstavlja lünkcijc povezovalne mreJe v veiiprocesorsKera sistemu in spregovori o njenih bistvenih lastnostih. Opisane So pomembnejSe topologije tnosLoperijshih iri večstopenjskih povfiov a 1 ni h ore? in narejena kvalitativna priiTierjava med njimi. Na koncj je podan primer sistema na osnovi skupnega v cjü i i a. In tue article the functiđn and the basic properties of the irterconnection network in a multiprocessor system are presented, Ue describe the principal topologies of singelstage and multistage ' interconnection networks. Also, the qualitative comparition between them is made. Finally, we present an etjinple cf global bus based system. 1 . UVOD Sodobna eleKtransKa tennologija oaogoäa gradnjo paralelnih računalniških si&temov, hi jih sestavlja na stotine ali celo na tisotiine procesorjev. Eden izmed največjih problemov pri gradnji takih paraialnih sistemov je v izbiri prave povezovalne «ireže za učinkovito medsebojno povezavo procesorjev, pomnilnietdh modulov in dcugih raprav. Optimalna izbira povezovalne mreJe za nek sistem zavisi predvsem od namembnosti sistema tap1 i kaci je J , velikosti sistema, zahtevane hitrosti, cenovnih omejitev... Z gotovostjo lahko reCeitiD, da Sele prava povezovalna mreia omogoCi priCakovano učinkovitost celotnega sistema. 2. VL06A POVEZOVALNE MRESE V - logiC!nea smislu predstavlja povezovalna nreJfa zakljuCeno enoto i M vhodi in N ijhodi ter lastno p res 1 i kov a Ino (unkcijo, ki opisuje povezovalne lastnosti mrele. StatiCno presliko-valno funkcijo najlaie podamo v obliki matrike z H vrsticami in N stolpci. Element matrike li) je enak 1, Ce mreSa omogoCa povezavo med vhodom i in izhodom j, sicer pa je enak 0. Statitìna presiinovalna funkcija govori o povezovalnih lastnostih "prazne" povezovalne («reSe, kar pomeni, da v trenutku, ko ocenjujemo moinost po-ve:ane i., j ie ne obstaja nobena povezava v ■re2i. Maloga povezovalne mreSe veCprocesorskega sistena je ta, da omogoCa povezavo med mnoiico procesorjev in einoiiico pomn i i n iäk ih modulov sistema. Pri tem obstajata dva osnovna pristopa. Pri prvem pristopu tvori vsak procesor skupaj s pripadajočim lokalni« pomnilnikom procesni element (PE). Ti procesni elementi so medsebojno povezani preti povezovalne mreiie tako, da ;6 vsak procesni element prikSJuäen na vhodno m izhodno linijo povezovalne mreie. Imenujmo tak naetn povezave PE-na-PE pristop (Slika 1). Drug pristop postavlja povezovalno ereSo med mnolico procesorjev in mnoitlco pomnilniäkih enot. Imenujmo ga P-na-M pristop (Slika 21. Glavna prednost prvega pristopa je v hitrem dostopu do lohalnegs pomnilnika, medte« ho Je prednost drugega pristopa v tem, da si procesorji delijo pristop do obseinih podatkovnih blokov in da je obseg po«nilnika, ki pnpsOa posameznemu procesorju spremenljiv. Moüna je tudi kombinacija obeh pristopov, pri kateri se procesni elementi povejujejo prekc mcaHe med seboj, kot tudi z globalnimi ponnil-niähimi enotami (PE-na-M pristop). 13 cSi a po**iO«*ln* inrcti Slika 1s PE-na-PE pristop Slika 2: P-nđ-M pristop 3. OSNOVNE ZNAtìlLNOSTl POVEZOVALNIH MREÌ Na a;tìor arhitekture soveiovalnih mrež vplivajo predvsem naslednji dejavnikit delavni nsein, strategija krnUjenja, metoda preklapljanja in topologija mreže. Glede na delavni naCin razlikujemo tsed ainhfono in asinhrono kois>unikacljo. Pri prvi se komunikacijske poti vzpostavljajo sinhrono & lunkcijanii manipulacije 5 podatki in posredovanjem podatkov in instrukciji medtem ko se pri druge« naCinu zahteve za komunikacijo posredujejo dinamitlno. Sistem je lahko zasnovan tako, da predvideva sinhrone in asinhrono pracesira-nje, tako da govorimo pravzaprav o treh delovnih naeinth povezovalnih ir.re!;s sinhrcni, asinhroni in kombinirani delovni natìin. Ker tipiCna povezav preklopnih elem nikacija med dvema vo z odgovacjajaCi« krmi ■tov, pri. Eeoier sta sp stopa. Prvi pristop vseh preklopnih elea^ ku, «edtem ko je pri Säeno posaffleiniiii prek Ine «rete. V prvem p nsm, v drugem primer 1 jenju. alna itreža sestoji i: mno-entov in povezav, se komu-zlištiema sistema vzpostavi ljenjem preklopnih eleaen-loSno uporabljana dva pri-zdruSuje krmilne tunkcije ntov v centralnem krmilni-drugem krmiljenje prepii-lopnili elementom poveiova-rimeru govorimo o centralu pa o porazdeljenem kriai- Dve glasni metodologiji preklapljanja sta apar&turno in paketno preklapljanje. Pri prvem se v Casu koisunic ir an j a /ipostavi liiiüna put' med iivoroin in ponorom. Pri paketnem prekla-pljajanju pa podatki, organizirani v pakete, potujejo skozi povezovalno mreSo brez vzpostavljene seldtne poti. Velja, da je aparaturno preklapljanje bolj primerno za veliko mnoStino pcdstkov, medteii: ko je paketno preklapljanje pri^ernajSe za krajSa sporotiila. Tretja metodologija, integrirano preklapljanje, :dru2uje lastnosti obeh, tako da lahko govorimo o treh metodologijah; aparaturno, paketno in integrirano preklapljanje. Topologija povezovalne nreSc je lahko predstavljena J gralom, kjer voilisäa predstavljajo elemente mreüe, povezave grafa pa ponazarjajo koaunikacijske povezave međ njimi. Topologije lahko k 1 as i t ic Iraino v dve glavni skupini, to so eno in veCstopenjske. Enostopenjske povezovalne mra?e sestoje iz le ene stopnje preklopnih elementov, ki ji sledi nek povezovalni vzorec. Pri večstopenjskih povezovalnih mreišh pa sretiamo mnoSico stopenj preklopnih elementov in povezovalnih vzorcev, tako da pot med poljubnim vho-oon in izhodom mreie vodi skozi vse stopnje. Kartezični produkt navedenih dejavnikov oblikuje prostor povezovalnih mre? vetìprocesorskih sistemov. Seveda vsebuje ta prostor nekaj neza- ninivih toök, vendar nas izbiranje prioerne arhitekture o«eji na podprostor primernih reSi-tev za postavljene zahteve. Topolgija areie Je klJuCneq» posena pri dolo-äanju primerne arhitekture, zato se bono v nadaljevanju posvetili topologija« povezovalnih mre?. a. enostopenjske povezovalne hreite Bistveno za to skupino «res; je, da sestoje 12 le ene stopnje preklopnih elementov, kar pomeni., da je la polje H procesnih elementov potrebno polje N preklopnih elementov, Mreüo tega tipa je mogode enostavno razdeliti tako, da se posamezni preklopni elementi pridružijo' aparaturni opremi pripadajofie prdoesne enote. Enostopenjske mreie lahko klasiJiciramo v dve skupini, to so statiäne in dinamitine nrefe. Pri statičnih mreZah so povezave pasivne, kar pooe-ni, da je iiziCna povezava med dvema procesnima elementoma fiksna in je ni ood preusmeriti za koounikaci jo z drugim procesnim elementom. Pri dinamičnih mreiah pa se komunikacijske poti lahko rekon! Igurirajo s Vtrmil Jen jen preklopnih elementov povezovalne nreüe. Ker statitine enostopenjske povezovaLne mreie v sploSnen ne omogočajo vseh povezav direktno ampak iterativno, mora v sploSnem nek podatek n« poti od izvora dd ponora vetikrat potovati skozi nreüo. Opisali bomo nakaj topologij enostopenjskih mreì's tem, da bomo delihirali funkcije areü-nih preklopnih elementov z njihovo presliko-valno lunkoijo, oziroma naborom preslikav, ki jih le ti lahko generirajo. Imejmo N vozliBC in jih označimo v vrstnem redu od O do M-1. Neka preslikava Pc») = y nam pove, da obstaja povezava od vozlišlia k k voz-liStü y. 5t ^t lane enostgpen.is k e , i»Ea.i!e ObroC hreZo definira premikalna preslikava, »od N +1 - promikalna preslikava To je najpreprostejCa nreiTa, ki sestoji iz obreda procesnih elementov, tok podatkov pa Je enosmeren,(slika 3.) Slika 3i Obroft N-ij.—. ■ -— o —I Slika Mreia sosedstva 46 Hreiä sosedstva Predstavlja enostavno e-azBirltev obroCa tako, Qa onogofia dvasneren toK inlarnscij. Senerira dve preslikave: mod N = mod N +1 - prenlkalna preslikava -1 - premikalna preslikava Obroč in mreia sosedstva sta primerna za relativno majhno število procesnih elementov, saj la pqvpreCni Ca« potovanja podatkov (Td> pri obroCu velja Tp=CN/2;Td prf nreSi sosedstva pa Tp = CN/<) =K-1 mod « P,^«)=K+n aod N P.n< *> = »-" «bd N + 1 - presnikalna preslikava -1 - premikalna preslikava +n - premikalna preslikava -n - preoikalna preslikava in Ce Je M popolen kvadrat (M » n« 1, dobimo lUiac areKo, ki je uporabljena v sistetnu Illiac IV, V tej arelti Je vsak procesni element povezan s svojim severnim, juSnia, vzhodnim in zahodni* sosedom, kot prikazuje slika 5. Slika 6t Hreiia hipcr-kooka ) . V prvem pri-iiiect] omogotìa mreSa vse preslikave tipa eden-na-eden, v drugem primeru pa tudi eden~na-veti. Stika Papalno stikalno polje Poudarimo 8e enkrat, da zahteva «tstiCna ano-, stopenjska arela Iterativen prenos podatHov skoznjo za dosego poljubne prasllkave. I it«ca-tivnoetjo «islimo na dejstvo, da «ora nek poda-, tek, poslan t izvornega procesnega elenenta proti ponornenu elementu, na svoji poti obiskati neko mnoitioo vmesnih azlroaa posredovalnih elementov in nekajkrat potovati skozi povezovalno «reio. lato Je za noko mre«o bistvenefl« pomena podatek s Številu potrebnih iteraoij za dosego po) Jifbne preslikave. 2 namenom primerJa~ ve predstavljenih mrel vpeljimo pojea razdalje. Razdalja med dveoa elementoma 1 in J Je enaka številu potrebnih iteraoij za dosego preslikave i -> j. Povezovalne mrele bomo primerjali po dveh kri-terijihi kriteriju maksimalno oddaljenosti In kriteriju diatrlliueije. Kriterij maksimalne razdalje podaja n«Jv«(iJo raidaljo med dvema elementom« mreZe, «edte« ko kriterij distribucije opisuje razdaljo potrebno za posredovanje neke intoreactje vfien elementam v mrefi, oziroma je enak Številu zaporednih gr>jp paralelnih preslikav potrebnih za dosego tega cilja, s tem, da so znotraj neke grupe vse preslikave istega tip«. Oba kriterija predstavljata neKakSno merilo uCinkovltaati (kosanezne mrefe. Za opisane povezovalne mrefe sta podana v spodnji tabeli. Pov. mreiia I Maks. razdalja I Pistribuoija Slika 1Da'. Preklopna celica z dvemi stanji I ObroC ! ! t t M,sosedstva i 1 . I 1 llllae \ \ I t Hiper-hocka I 1 I I Pop. maBanJe I I I tSkupno vodilo ) I I IPop.st.pDlje 1 I 1 M-1 N/2 Vn-1 log N 21og N-1 1 1 N-1 M-1 log N 21og N-1 M-1 log N 5. VteSTOPENJSKE POVEZOVALNE «REIE Ta tip povezovalne «reie omogoä« vse preslikave vhodov na izhoda direktno. Oobljan Je i rekuezivno dekompozicijo popolnega stikalnega polja (cross» bar) do preklopnih elementov velikosti 2 X 2. Večstopenjske povezovalne mrela torej sestoje iz veC stopenj preklopnih slemen- Slika lOb: Preklopna celica s štirimi stanji Topologijo mr»*e predstavlja uporabljen povezovalni vžoreo med nabačo« vhodnih in izhodnih linij - povétovalrie Ni»ra*«VeUstopenJsko mrelfo sestavlja N.V-stopenj s po. N/2 preklopnih celic, hjsr KysVJ*. log N * « 4 ZlogH r 1 kjer je N snak Številu vhodnih oziroaa izhodnih linij povezpvslne . ara»«i,, Xz t«ga Je razvidno, da kompleksnost pòveiovalna'«rete raste s faktorjem otNlog N) , kac j« v,, primerjani, z 0(H») kompleksnostjo popotnog* pcaklopnega polja pre-cejften prihranek predvseit pri velikih vrednostih N. veästopenjske sreie so torej najbolj primerne za sisteme » vaVlkl» «tevilom procesnih elementov. ■ " Kar zadeva strategijo krall Jenja in metodo preklapljanja sreeaoo pri večstopenjskih povezovalnih mretah centralno In porazdeljeno krmiljenje, kot tudi apareturno in paketno preklapljanje. Izbrani koncept doloBa Izgled preklopne celice, saj mora le-ta upo»t«*lfel i protokol, ki ga doloCata strategija krmiljenja in metoda preklapljanj». Opisali bo»o topologija najbolj uporabljanih vedstopenjskih povezovalnih mre«. MreiTa osnovine lini.la CBasellng) Sestavlja jo iog'H stopénj .katerih vsaka ima H/2 preklopnih oello .■t X PripiBino mreil sledetie oznaket stopnje naj bodo oštevilčene od leve proti desni s Številkami od O do log N-1, povezovalna vioroe otnaClmo v isti smeri od O do log N. Preklopnim celloan posamezne stopnje pripiftlsp vrednosti od O do N/2-1 v smeri od zgoraj navzdol, prav tako pa otnaelao posamezne povezave znotraj vsakega poveibvalnega vzorca od O do N-1. Preslikava podana v obllklt PCtPH3; e CR)j s povezavo C9Ì pomeni, d» obstaja povezava sad preklopnim eia-, mentom P stopnje i in preklopnim elemntoa ft stopnja J in da j« to povezava 9. f, R in «. bodo nastopali v obliki dypji«kega zapisa. .; Tüpolc'jiJo csnavne linije pcdajđta nđS- ìednji pravili! ......'ì'i^ = ^^ ■= povsiivo ■■•^Q) Oii j = (p p •il "i-t n-2 ■ pO; "i 1+1 6 povezavo . . .p^O) 04i 1 1 1 Pop.st. 1 H 1 <1 1 1 1 N/i, 1 2N t N/(N*8) 1 1 1 n-kocka 1 M/I' i logN 1 1 1 NIQ9M/2 \ i 1 N+MloqM 1 N/(logK(Z+3lD9H)) 1 i ] Senes 1 1 N l2lagN-1 i 1 INlogN-N/21 1 1 2NlogN 1 1 2N/<<2lDgN-1)(61ogN-1)) 1 1 6. OCENA KVALITETE RRES Predätavili. smo topologije pomembnejših pove-i:ovèlnìh mi-s»,- ki so se pojavile v paralelnih r=:jnalniSkih sistemih. Poudarili smo ?e, da je itbir'ò povezovalne nireie odvisna od vet para-jietrov, med katerimi je najpomembnejši Število pi-oc&snih eleoentov. Število procesnih elementa» doloCa fisiCno kompleksnost mreSe in njene funkcionalne lastnosti. FiiiBna kompleksnost mre^e se izraüa v številu preklopnih elementov in «tevilu fiiiCnih povesav, o funkcionalnih lastnostih pa govori maks ima 1 no število sotias-r,ih ive; v ijireSi in pa podatek o Ca^u, potrebne» la prenos paVeta podatkov skozi roreio. Vpeljlna pajea kvalitete mreSe, ki nasi bo slu-Sila kot kriterij pri doloäanju primerne mrežne topwlogije za dalotìeno Število procesnih ele-,1,ir,tov. Kvaliteto mreže definira naslednja ena-cbä! K = NP/(T(E + L; ) N.........Število procesnih elementov sistema P.........isaksifflalno Število sottasnih zvez T.........tìas prehoöa sKozi (iireJo E .........Stav i lo preklopnih elementov mrete L.........Število fiziCnih povezav mreie V qcrnji taoeli smo podali posamezne parametre in kvaliteto nekaj mreS. Izmed statiänih eno-atùpenjakih ore? smo izbrali obroC, izmed večstopenjskih z M=lag N pa lareio posredne n-koc-ke. Lahko ÖL se preprläali, da je kvaliteta ostalih itatienih enostopenjskih mre? istega reda kot kvaliteta obroda, kvaliteta vedstopenjsk i h isre? 2 M=lag N pa istega reda kot kvaliteta posredne n-kocke, li diagrama na sliki 15. lahko vidiao, da Je za aajhno Število procesnih ele-isentov najboljša reSltuv popolno stikalno polje, dobra po sta tudi obroC in skupna vodilo. ;a »te kct ts. prgoetriih ele.nentov pa sta kvalitetnejši fij^i'tftlna n-kooka in Benesova mrera. V/l enote IzaDA PEI Q - vodilo krmi Inik dia •IMI dim Slika 1&: Arhitekture sisteoa na B-vodilu 7, ZAKLJUČEK Naj namesto zakljubka predstavimo arhitektura eksperimentalnega vetiprocesorskega sistema s skupnim vodilo«, ki nastaja na naSe« institutu. Arhitekturo sisteaa prikazuje elika 16, Uporabljeno je asinhrono DEC-ovo Q vodilo. Funkcijo arbitrala skupnega vadila prevzena procesor LSI 11/23, ki je hkrati tudi skupni vmesnik masovnega pomnilnika; vsak procesor sistena lahko posega po masovnem ponnitnikvi le preko LSI 11/23. Trenutno Je procesni element (PE> zasnovan na mikropraoesarju IBQA. Vsebuje zlogov lokalnega pomnilnika. Z zunanjim svetom ga povezuje 8 nadzorno/statusnih besed (lOCSfit, Vsak izied procesnih elementov lahko posega neposre- dno po ivojea lokalnem pooinllniku, po skupnen paanllniku in po nadzorno/Etatusnih besedah drugega procasnega elenenta. Ker iaa S~vodllo ■otnost 22 bltn«ga naslavljanja, lahko v siste-■u uporabilo do AH zlogov skupnega pa»nilnika. 8. LITERATURA C11 R.H.Kockney, C.R.Jesshopei Parallel Computers, Adam Hilger Ltd, Bristol 1981 C23 Tse-Yun-Feng: A Survey □! Interconnection Networks, Cooputer, Deceabsr 1981 pp.12-27 C31 Chuan-Lin-Wu, Tse-yun-Feng: On a Claas of Multistage Interconnection Networks, I£EE Transactions on Computers, August 1980 pp. 694-702 H.J.Siegel: Interconnection Networks for SIKO Machines, Computer, Junij 1979 pp. 5765 CB3 H.J.Siegelt A Model of SIMO Machines and a Comparivon of Various Interconnection Networks, IEEE Transactions on Coaputers, PeoElber 1979, pp. 907-917 C61 H.J.Siegel) The Multistage CubetA Versatile Interconnection Network, Cooputer, December 1981, pp. 65-76 C7] Chin-Yuan-Chin, Kal-Hwang: Connection Principles lor Hultipath Paoket Switching Networks, The 11th Anual International Syoposiuii of Conputer Architecture, June 1984, pp. 99-108 ca:] P.Srajaki Paralelno procesiranje: arhitektura 90-tih godina, Zbornik jugoslavenskog savjetovanja c novla generacijsoa raCunala, MIPRO 86, Maj 1986, pp, 33- Jami matematično laije izraziti. Zato v ladjedelnicah vršijo račune volumnov in sistemnih teftišč ladijskih prostorov z numerično integracijo v glavnem v vzdolini smeri ladje. Tako so izračunane funkcije oddaljenosti prijenališča vzgona od sredine ladja, višina metacantra ter druge za argument vgreza ladje, volunni .in pološaji sletemnlh teilšč tankov aa argunenta sonde in trina, volumni in poloiajl sistemnih teiiič aa tovorna skladišča pa glede na poBSmezne vrste tovorov. V tovornih skladiščih Je ts vrednosti potrebno popraviti, če ao skladišča a tovorom le delno zapolnjena. Vsa te funkcije za navedene argumenta izdelajo v ladjedelnicah v obliki grafov. Grafi niso natančni, delo 3 nJlnl pa Je aanudno. Zato so onenjene funkcije v novejšen času ustrezneje prikazane s tabelanl. Hnošica tabeliranih funkcij za doloieno ladjo je abrana v 'Knjiqi stabilnosti'. Knjiga stabilnosti Je danes s strani pomorskih uradov edini priznani dokunant za pravilno tovorjenje ladje. Ko smo dobili is Knjige stabilnosti vse potrebne podatka^ nam kontno ostane àe zadnji^ tretji del izraSuna vidoline In prečne stabilnosti. Ostalo nan Je obilo nnoienj sa Izrafun tei in monentov, seStevanJ te* aa izračun celotne teie ladje, ter konžno nekaj daljenj in odštevanj. Ti zadnji algoritmi za tovorjenje ladij zahtevajo torej le Atirl osnovne računske operaciJb. Poglejmo sedaj, kako je s tovorjenjem ladje s pomočjo računalnika. Ce naj računalniški sistem za tovorjenje ladij opraviči avoj namen, nora Izračune izvrševati hitro in točno. To pa izključuje zamudno uporabo grafov ali tabel. Računalniški sistem mora biti torej avtonomen, vBs izračune mora izvrievati sam. Operater dala samo I računalnikom in pri delu z nJim na uporablja Knjige stabilnosti. Zahteva po avtononnosti računalniškega sistena za tovorjenje ladij postavlja Izvedbi sistena nalogo ponavljanja ladjedelnliklh izračunov. Zato moramo poznati matematične izraiave oblik ladje v prečni ali vodoravni ravnini v funkciji argumenta v vzdolini ali navpični osi. Le tako lahko izvrilBO nuaierične integracije a ustreznim korakom argumenta. Tako dobljeni rezultati bi ladoièall zahtevi točnosti sistema. lakaie pa se, da taka računalniška numerična integracija v zankah še zdaleč ne aadoiča zahtevi dela v realnsn času tudi pri delu s httrisi in večjimi računalniki. Na sadanji stopnji razvoja računalniških sistemov za tovorjenje ladij pravzaprav mnogo hitreje Izvriujeno račune, katere danes vriino na osnovi podatkov ia tabel Knjige stabilnosti. Na tej stopnji se nam ponuja moAnost pridobitve veliko hitrejših računalniških algoritmov. Ce bi si ogledali grafe funkcij pripadajočih arguisentov v Knjigi stabilnosti, bi najprej opazili, da so vse te funkcije avezne. Končno bi opazili, da so te funkcije večinoma monotono naraščajoča funkcije, le izjemoma so to monotono naraščajoče in padajoče funkcije ali obratno. Prva BOinost, ki Jo sadaj imamo, je ta, da funkcije iz Knjige stabilnosti vnesemo s prograoo» v pomnilnik računalnika. Pri tem funkcijske vrednosti tvorijo člene seznama. Korak argumenta maramo izbrati tako, da zadostimo prostorski učinkovitosti in točnosti algoritma. Pri vnosu funkcijskih vrednosti za konstantan korak argumenta ,dobivamo funkcijske vrednosti za tabelirane In netabellrane vrednosti argumentov z linearno interpolacijo. Ta algoritem je torej računalniška inačica sedanjih tabelaričnih postopkov računa stabilnosti. Tudi pri njih iščemo funkcijsko vrednost za netabeliran argument z linearno interpolaci jo. Drugo »oinost Izražave takih zveznih monotonih funkcij nudijo statistične metoda. Učinkovita se Izkaie metoda najmanjših kvadratov. Tako lahko večino funkcij iz Knjige stabilnosti izrazimo z regres 1Jski mi polinomi, le malo pa z rogresiJsklmi eksponentnimi funkcijami. Koeficiente regresijsksga polinoma izračunamo iz vrednosti koordinat točk funkcije. Zahtevi točnosti algoritma zadostlno, če iaračunaso koeficijente regresiJskega polinoma iz zadostnega Števila koordinat in z izbiro ustrezne stopnje po 1 i noma. Izkaia se, da so algoritmi na osnovi regraeij- skih polinomov časovno učlnkovltajil od algoritmov na osnovi seznasov. Oboji pa zadoičajo zahtevi o' delu v realnem času. Potrebno Je pripomniti, da so funkcijska vrednosti v Knjigi stabilnosti xaokroiene na zadnjem mestu. To povzroča zaokroiitvano napako pri izračunanih vrednostih, računanlh z obemi algoritmi. Tako ianaia napaka na zadnjem mastu pri seznamih do -»1, pri regresijskih polinomih p« med -1 in Omenjene napaka bi bilo moino odpraviti, če bi bile funkcijske vrednosti v Knjigi stabilnosti podane na dve decimalni mesti več. Za današnjo stopnjo raavoja računalniških sistemov za tovorjenje ladje smo na ta način dosegli dvojei -Prvič smo dobili časovno in prostorsko učinkovite algoritme. -Kot drugo pa so ti algoritmi zasnovani na vrednostih la Knjiga stabilnosti. Tako ni vzroka, da bi tako narejen sistem pomorski uradi ne priznali. Pri tako Izvedenem računalniškem sistemu za tovorjenje Vadlj bo v blilnjl bodočnosti dobila Knjiga stabilnosti isti pomen, katerega imata danes magnetni kompas In astronomska metoda. Knjigo stabilnosti bomo >a tovorjenje ladij uporabljali samo v slučaju okvare računalnika. Na vliji stopnji razvoja računalnlikih sistemov za tovorjenje ladij na potrebujemo le funkcij iz knjige stabilnosti za argument trlma, tamvač tudi sa argument prečnega nagiba (llst-a). Prad algoritma na osnovi saznam« »11 regresije ce tu na postavlja vprašanje časovne, temveč prostorske učinkovitosti. Postavlja se vprašanje, če ne bi bile na tej stopnji prostorsko učinkovitejše metode numerična Integracije. Trdimo lahko le, da bi bile časovno nsučlnkovi-te. časovno učinkovitost pa bi dosegli a integraci jami na kratkih intervalih pri poznanih funkcijskih vrednostih na spodnjem delu Intervala. To pa Je zopet v ikodo prostorska učinkovitosti. Rešitve tega problema ta članek na obravnava. 6.5. Učinkovitost algoritmov V tem poglavju bomo funkcija la Knjiga stabilnosti na kratko Imenovali funkcije. V prejšnjem poglavju smo omenili, da so regresijski polinomi fissovno najučinkovitejši algorltmi. Posamezno funkcijo Je pri zahtevani točnosti večkrat moina Izraziti a enim regrealjskim polinomom do 10 stopnje. Ce v računalniškem programu zapišemo polinom v obliki n-i f (*) n-1 se bo pri visokih stopnjah polinoma računalniški čas bliial zgornji meji realnega časa. To pa zato, ker za en argument izračunavamo več funkcijskih vrednosti, katere so izraione s takim zapisom polinomov. He pa v programu zapišemo polinoma v obliki f(K) = ((..(a a ) n-1 ) n-2 0 nam računalniški čas ne bo delal tešav. Prvi zapis polinoma ima namreč kvadratno čaaovno učinkovitost v primerjavi z drugim zapisom, ki ima linearno časovno učinkovitost. Zaradi časovne uà 1 tiJcovl tost i «sto v progranlh naSelno .zaplsuj«do pollnoDe v drugI obliki. Prostorsko učinkovitost programskega zapisa polinoma iz-boljiaoo tako, da deciaalke njegovih koeficientov okrajiaiso do seje, katera aadoiCa sahtevani toinostl iaraAunanlh funkcijskih vrednosti. Ce ina funkcija singoiarne tofike all toike obraiajev. Je ni molno Izraziti a zahtevano ta£noBtJo z enla regresijskim polinonoD, £etudl bi bila njegova stopnja vlija od desete. V takih primerih s pogojnimi stavki v programu funkcijo med amenJenlsl toSkami izrazimo odsekoma, v većini primerov polinomi niijih stopenj. Pogojni stavki in po'l inani niijlh stopenj poveSaJo fasovno učinkovitost. Prostorska učinkovitost ae seveda zmanjka, vendar ne presega prostora v pomnilniku, katerega bi zavzela ista funkcija, ie bi Jo zapisali v obliki seznama. Kadar funkcijo rü moreno izraziti z regresij-skin pollnonoD, ali Je ne noreao Izrasitl z zahtevana točnostjo. Jo izrazltio s seznamon. S seznami pa izraiaao tudi tiste funkcije, pri katerih je potrebna pri računu stabilnosti visoka točnost. V prejdnjem poglavju smo namreč videli, da napaka zaokrožitve vpliva na izračun funkcijske vrednosti manj, če je funkcija Izraiena s seznamom. Pri čitanju kratkih seznamov je računalniški čas aadovoljiv. Pri čitanju dolgih seznamov pa precej presele realni čas. V taken primeru moramo seznam razdeliti na podsezname. S pogojnimi stavki v programu pri določeni vrednosti argumenta računalnik čita samo en podaeznaa. Na ta način časovna učinkovitost nastavimo na poljuben čas. Omenjeni postopek pa seveda zmanJAuJe prostorsko učinkovitost. Ker so funkcijske vrednosti večinoma racionalna itevlla z enakim Številom decimalnih mest. Jih vpiiemo v seznane kot cela itevi la tako, da Jih predhodno poanoiimo a ustrezno potenco Števila 10. Tako BO v seznamu prikazana z označeno točnostjo INTEGER in ne SHORT, Kar izboljja prostorsko učinkovitost. Časovna učinkovitost pri tem nI zmanjiana, saj samo rezultat delimo z ustrezno potenco itevi la 10. Kot bomo videli v naslednjem poglavju je uporabniški program računalniškega sistema za tovorjenje ladje sestavljen iz glavnega programa in podprogramov. Podprogrami pa so sestavljeni iz modulov. Velikost modula-določa velikost strani zaslona ali zahtevana hitrost Izvajanja izračunov. Izberimo sedaj stran zaslona, na katero vnaiauo n argumentov. Ob vnosu vsakega argumenta delni podprogram izračuna temu argumentu pripadajoče fukcljske vrednosti. Privzemimo, da so v delnih podprogramih funkcije izraiene s seznani, katerih časovna učinkovitost Je na meji realnega časa. Sedaj ielimo Spremeniti le n-ti argument in s tem nJemu pripadajoče funkcijske vrednosti. Predno ta argument dosežemo s kurzorjem, smo zapravili n-L sekund. Uvedlno sedaj v delne podprograme majhne spremembe. Pred začetkom vsakega delnega podprograma dodajmo novo spremenljivko, katera naj dobi vrednost starega argumenta. Nato vneslmo novi argument. Delnim podprogramom dodajmo sedaj pogojni stavek. Ta naj predpise brezpogojni preskok preko delnega podprograma v primeru, da sta stara In nova vrednost argumenta enaki. Na ta način smo prihranili D-i dragocenih sekund računalniškega časa, prostorsko učinkovitost programa pa smo le neznatna zmanjkali. Opisali SBo nekaj načinov izboljiav časovne in prostorske učinkovitosti algoritmov. Pripom- nimo, da mejo mad Dba»a učinkovitostLu določa predpisani realni čas ter tip aparaturne opreme in njenega operacijskega sistema. Ponovimo ie, da ao algoritmi na osnovi regresijskih polinomov hitrejši, algoritmi na osnovi seznamov pa počasnejii, toda točnejil. takale pa se, da Je pri najbolj zahtevnih funkcijah za oba tipa algoritmov prostorska učinkovitost enaka. S.e. Opis shene prograna Uporabniiki program računalniškega sistema za tovorjenje ladij mora izpolniti vso zahteve, katere so navedene v poglavju 5.2. Pri izdelavi programa dajemo do maje dela v realnem "času popolno prednost časovni učinkovitosti programa. fiele nato posvetimo vso pozornost njegovi prostorski učinkovitosti. Iskaie se, kot bomo videli v naslednjem poglavju, da so taki programi zelo obširni. Da bi bil program časovno učinkovit, ne zadostuje, da vsebuje samo časovno učinkovite algoritme. Program mora biti tudi ustrezno strukturiran. Zato Je sestavljen iz glavnega programa, podprogramov s noduli in datotek. S.E.l. Glavni program Sestavljata ga glava In telo programa. Glavo programa sestavljajo globalni ukazi, naslov programa, označitev točnosti spremenljivk s čimer povečamo prostorsko učinkovitost in glavni nenu. Henu nora biti prijazen do uporabnika. Ob vnosu nepravilnega argumenta dobino zvočno in pisana opozorilo, kursor pa se vrne na mesto nepravilno vneàenega argumenta. S tem je onemogočen premik teksta menu-Ja po saslonu. Pri tovorjenju ladje velikokrat vnaiamo ali spreminjamo le neko značilno grupo podatkov in takoj preidemo k zaključnenu računu stabilnosti. Tako značilno grupo podatkov vsebuje podprogram. Nanen glavnega menu-Ja je, da omogoča hiter dostop do takih podprogramov. Foleg tega na» glavni menu prikaie osnovne ladijske podatke, odpira in briie datoteke, ter vna£a v datoteke začetne vrednosti spremenljivk. V telesu programa se nahajajo rutine za izvajanje operacij katere se večkrat ponavljajo in modul z delnimi podprogrami, kateri omogočajo iavajanje nenu-ja. 5.6.2. Podprogrami Ločimo dve vrsti podprogramov. Prvo grupo podprogramov tvorijo tisti podprogrami, v katerih posamezen podprogran zdruluje značilno grupo podatkov. To so podprogrami za tovor, goriva, maziva, balast in pitno vodo. Drugo grupo podprogramov tvorijo podprogran aa zaključni račun stabilnosti, podprogram za izpis podatkov in podprogran za risanje plana tovora. Vsaka grupa podprogranov ina svojo snačilno strukturo programa. Kot primer strukturiranosti prve grupe podprogramov si oglejmo podprogram tovor. Glavo podprogran» tvorijo lokalni ukazi, označitev točnosti spremenljivk in menu podprograma, Henu podprograma omogoča izbiro strani Kašlona. Število strani In vsebino vpisov na njih določata itevllo vrstic na zaslonu in ieljena hitrost Izvajanja računskih operacij. Tako Ina podprogran aa tovor tri strani. To so strani za tovor na krovu, tovor v medkrovju in tovor v spodnjih skladiščih ladje. Nadalje menu omogoča Izvrievanje posebnih operacij. Te predstavljajo rastovorJen je vsake od teh treh skupin tovorov z enim ukazom. To povečuje časovno učinkovitost dela s programom. Siedl ukaz za povratsk v glavni Benu> Talo podprograma sestavljajo rutine aa ponav-Ljajoie ae operacije in noduli. Vsaki strani zaslona In vsaki posebni operaciji pripada iastan aodul. Moduli so konino sestavljeni Is delnih podprogranov. Vsakeaiu argunentu pripada lastan delni podprogram. Moduli, ki pripadajo razni> stranem podprograma, iaajo enako strukturo. Majprej se iz datotek isvrji éltanje zaietnih ali ie vnaienih arguaentov. Sledi vnos novih argumentov ali spramenba posameznega ter procesiranje pripadoJoSih funkcijskih vrednosti. Sledita Izpis argumentov in rezultatov v datoteke, ter povratak v menu podprograma. Pri modulih za posebne operacije čitanje odpade, procesiranje Ln izpis v datoteko pa se vrii ob zadanem pogoju z enim ukazom. Tsko zasnovani moduli so avtonomni. Avtonomnost modulov in struktur iranost programa omogočata, da lahko spremenimo samo en argument na poljubni strani. Po zakljufitvl te strani so vsi podatki takoj dostopni za zaključni račun EtabiInostl. Kot primer struktur iranosti druge grupe podprogramov si oglejmo podprogram za zakljuinl ra£un stabilnosti. Glavo programa tvorijo izpis naslova programa, lokalni uka«i in označitev točnosti spremenljivk. Telo programa tvorijo trije moduli. Program prvega modula prečita Iz datotek podatke, kateri so potrebni za račun stabilnosti. Sledi modul s programom postopkovno usmerjenega tipa, s katerim računamo stabilnost. V tretjem modulu se nahajajo delni podprogrami za opozorila v primerih nepravilnega tovorjenja ladje. Takemu opozorilu aladl abort podprograma in povratek v glavni program, izpis dokumentacije pa Je onemogočen. Robni pogoji Sale na tem mestu lahko dokončno odgovorimo na vpraianja o problemu robnih pogojev. Ss funkcije i« Knjige stabilnosti, katere so podane za argument sonde, bt na to vpraJianJa lahka odgovorili ie praj. funkcijske vrednosti teh funkcij so na krajličih Intervalov točno definirane. Drugače pa Je pri funkcijah, katere so podane za argument vgreza. Ta se namreč nahajajo v podprogramu za zaključni račun stabilnosti. Funkcijske vrednosti le teh so na spodnjem krajišču intervala točno določene z vgrazom, ki pripada lahki ladji. Problemi pa bi lahko nastopili v zgornjem delu intervala. Te robne probleme pa reSuje zgoraj opisani modul za opozorila pri nepravilnem tovorjenju ladje, katerim sledi abort podprograma. V tako zasnovanem programu ni več opaziti problemov robnih pogojev. 5.6.4. Datoteke Glavni program odpira datoteke zs značilne grupe podatkov. To so datoteke za shranjevanje argumentov, izračunanih tei in ročic, vrednosti svobodnih povrčln in rezultatov naključnega računa. Začetne vrednosti vpisuje v datoteke glavni program. Spremenjena vrednosti vpisujemo v datoteke z noduli. Podatki iz datotek so vedno dostopni za zaključni račun, ispis dokumentacije ali risanje plana tovora. Tako strukturiran program za računalniško tovorjenje ladje omogoča hitro, operativno in varno tovorjenje ladje. 6.7. Velikost sistema Poskusni uporabniiki program za računalniiko tovorjenje ladje Je bil izdelan za ladjo tipa Concord C. Te ladje imajo nosilnost 16.000 ton, osem skladiščnih prostorov in 20 tankov sa goriva, maziva, balast in pitno vodo. T* itevila uvrščajo ta tip ladij v spodnji srednji velikostni razred IsdlJ. Ladij tega tipa ima podjetje Splošna plovba Piran pet. Poskusni program Ispolnjujs vse zahteva, katera so za računalniško tovorjenje ladij opisane v poglavju S.2. Program Je strukturiran in vsebuje avtonomne module. Na osnovi tega poskusnega progrs»a in ekstrapolacije lahko ocenimo velikost in' hitrost delovanja računalniškega sistema sa tovorjenje ladij. S stališča prostorske učinkovitosti programske opreme zavzema program za ladjo na ravni kobilici, tovorjenje generalnega tovora in izračune vzdolšne in aačetne prečne stabilnosti 34 kB ponnllnlškega prostora. Cs programiramo funkcijske vrednosti Ša sa argument tri»», se program poveča na 100 kB. Časovna učinkovitost takega programa Ja dvajsetkrat večja od sedanjih tabelaričnih postopkov. Ker so funkcije podane sa argument sonde in trlma. Je n« računalniški sistem moino priklopiti sensorje. Z nJlml bi bila časovna učinkovitost sistema glede na tabelarične postopke povečana do pedesetkrat. Pravilna nastavitev senzorjev pa bi povečala prostorsko učinkovitost. Cb programu dodamo program za tovorjenje razsutih tovorov, se le ta poveča za dodatnih IG kB. Ce dodamo še program za krivuljo stabilnosti in izpis podatkov, potrebujemo dodatnih 17 kB programa. S temi dodatnimi programi ostane Časovna učinkovitost celotnega programa ista. Program za tovorjenje kontejnerjev bi zahteval dodatnih 17 kB. Pri tem pa bi časovna učinkovitost celotnega programa padla izpod zgoraj omenjenih časovnih učinkovitosti. Bistveno pa Je, da Je računalniški čaa tovorjenja kontejnerjev manjši od realnega časa za dejansko tovorjenja kontejnerjev na ladjo, česar tabelarični postopki ne omogočajo. Vsi zgoraj navedeni programi bi tvorili program velikosti ISO kB. Program te velikosti bi avtonomno Isvajal vse Izračune, katere lahko za ladjo tipa Concord C danes vršimo na osnovi Knjige stabilnosti in tabel sondai, razen računov upoglbnih momentov in strišnih sil. Zgoraj omenjeni programski oprami bi morala pripadati ustrezna aparaturna oprema, hparatur-na oprama bi morala zadoščati tudi zahtevam za delovanje na ladji, katera smo opisali v poglavju i. Pripadajoči tiskalnik bi moral izpisovati dokumente na formatu A4 s hitrostjo 80 znakov v sekundi. Opisani računalniški sistem za tovorjenje ladje predstavlja sistem srednjega razreda za ladjo srednja velikosti. Velikost sistema pa *• spremeni glede na drugačno velikost ladje ali ielje naročnika. Večinoma se danes nahajajo na ladjah manjši sistemi. Vgrajeni pa so tudi veliko večji sistemi. Nahajajo se na velikih tankerjih, kjer Je tovorjenje in iztovorjanje tekočih tovorov v celoti računalniška krmiljeno. Progranska oprana velikih slstaiiov vsebuje že druge programe. Ce dodamo prograne funkcij ta arguBsnt lista, le ti sami lahko dOBsieJo velikost do E00 kS. Dodati moramo programe za raiun upoglbnlh nonentov, gtrliinih ali, grafline prikaza v barvah, raiunalnliko krnll-jBOje tovorjsnja, programe sa ukrepe v primeru prodora vode in progra&e aa optimisacljo tovorjenja. Tako lahko programsko opremo velikih sistemov ocenimo na red velikosti HS. Pripadajoča aparaturna oprema aahteva zaslone visoke grafićne ločljivosti, risalnike za format A3, A/D pretvornike in dobro senzorsko tehnologijo. 6. ZAKLJUČEK Članek Je opisal liroko uporabo informacijskih in računalniških sistemov v sodobnem pomorsken prometu in ladjedelništvu. Prikazano Je sedanje stanje in naie Edinosti za vključitev v razvoj in Izdelavo tovrstne sodobne tehnologije. Naie motnosti so na področju ie obstoječe komunikacijske tehnologije in nadalnjem razvijanju meteorološkega informacijskega sistema na Jadranu. Veliko zanimanje za nadaljevanje razvijanja komercialno-operativnega informacijskega sistema v podjetju za kontejnersko sluibo je sedaj pri slovenskem ladjarju. Imamo moinost razvoja ekspertnega sistema >a nego bolnika na ladji* Velike motnosti pa imamo za izdelavo ladijskih informacijskih podsistemov, kateri zahtevajo le računalniiko tehnologijo. To so podalsteai za administracijo, saloge, upravno In pravni, tar podsistem za tovor. Kot primer ponovimo primerjalne prednosti, katere imamo pred tujini proizvajalci pri izdelavi opisanega računalniškega sistema za tovorjenja ladij. Domači ladjar ali ladjedelnica določita, ' na katero ladjo bo sistem postavljen in kakšna bo njegova velikost. Za kontajnersko ladjo bi račun verjetno pokazal, da se inviastlclja za uvošen sistem isplača v enem letu. Hadalnjl račun bi pokazal, da je programska oprema takega tip« sistema doma petkrat cenejša kot v tujini. Poleg tega Je cena dinarska. Tu Imamo torej dve prednosti. Prva je prihranek pri nabavi oprene za ladjarje in ladjedelnice. Druga pa Je prodor in prodaja naiaga znanja na domače In tuje tržišče. Po uveljavitvi naših proiavodov na domačem in tujem triišču, bi > razumno politiko cen ustvarili akumulacijo *a nadalnji razvoj In razširjeno reprodukcijo. PARALELNI SUSTAV ZA RAZPOZNAVANJE ZNAKOVA INFORMATICA 4/86 UDK: 681.3.05 Izv. prof. dr. Nikola Paveätö, dipl. ing. Fakulteta za elektrotehniko v Ljubljani Izv. prof. dr. Slolradan RIbarić, dipl. ing. VVTŠKoVJNA, Zagreb u čUnku je opisana izvedba paralelnog sustava 2a raspoznavanje rukom pisanih numeriCkih znakova. Sustav se temelji na teoriji dvodimenzionalnih prilagodbenih filtera 1 primjeni procesora viših hijerarhijskih razina, U prvom dijelu članka dane su teorijske osnove dvodimenzionalnih prilagodjenih filtera i izvorne definicije procesora različitih hijerarhijskih razina, U drugom dijelu članka opisana je izvedba visokoparalenog sustava za raspoznavanje koji za osnovu ima procesore hijerarhijske razine Hj i Hi. TH£ PARALLEL CHARACTER RECOGNITION SYSTEM: In this paper we describe realization of the parallel system for the recognition of handwritten numerical characters. The system is based on the theory of two-dimensional matched filters and application of processors from higher hierarchicai ìeveìs. In the first part of the paper we desribe theoretical aspects of two-dimensional matched filters and we give original definitions of processors frooi different hierarchical levels. In the second part of the paper the realization of highly parallel pattern recognition system is presented. The system has processors from hierarchical levels Hi and H2 as the basic elements. The experimental results are given. 1. UVOD U posljednjih desetak godina Interes za područje digitalne obrade i raspoznavanje slika u stalnom je porastu. Taj Interes je usmjeren u dva glavna pravca [i]: a) poboljšanje vizualnog izgleda slike, odnosno pretvaranje slike u pogodniji oblik za Interpretaciju od strane čovjeka, b) obrada i pretvaranje slike u oblik pogodan za automatsku percepciju i strojnu interpretaciju. Pravac istraživanja opisan pod b) bio je uvjetovan prodorons računala u poslovne i industrijske sredine i prouzrokovao Je razvoj uredjaja koji se obično nazivaju zajedničkim imenom - uredjaji za izravni unos podataka s dokumenata ili optički čitači znakova (OCR -Optical Characters Reader), Prema složenosti uredjaji OCR mogu se razvrstati u tri razreda a) jednostavni uredjaji za čitanje kodova (npr. bar code) ili zapisa s magnetnom tintom, b) uredjaji srednje razine složenosti koji se upotrebljavaju za izravan unos podataka s dokumenata, čekova, liječničkih recepata i si. Skup ulaznih znakova Je tipiziran C3D. c) Sloieni uredjaji za raspoznavanje rukom pisanog teksta {npr. brojeva, brojčano-slovčanih znakova, Kata-kana znakova i si. C3J). / / /lA-tf/™^ OlV-t^à/- Irav^tJ Slika J, Blok-ahema tipičnog guatava za raspoznaVciTiJe snakova Slika 1 prikazuje blok-shemu tipičnog sustava za raspoznavanje znakova. On se sastoji od: . jedinice za unos i digitalizaciju slike, . podsustava za lociranje i segmentaciju znakova, . pretprocesora, . podsustava za izlučivanje osnovnih značajki, . podsustava za klasifikaciju. Složenost pojedinih komponenti sustava zavisi od njegove namjene: u jednostavnim uredjajima OCR sa malim skupom tipiziranih ulaznih znakova neke komponente (npr. pretprocesor) mogu biti izostavljene, dok u složenim sustavima za raspoznavanje pojedine komponente su izvedene tako da imaju bazu znanja 1 mehanizam za zakljuCi-vanje> odnosno predstavljaju ekspertne sustave C43,CS]. Upotreba sklopova izvedenih u tehnologiji visokog stupnja integracije (LSI) u konstrukciji uredjaja OCR poboljiala je omjer performansa/cijena i omogućila primjenu egzaktnijih metoda u postupku raspoznavanja. U Članku je opisana izvedba paralelnog sustava za raspoznavanje rukom pisanih znakova. Postupak raspoznavanja temelji se na primjeni dvodimenzionalnih prilagodjenih filtera. 2. DVODIMENZIONALNI PRILAGODJENI FILTERI H.C. Andrews Cć] je teoriju L.G, Tunna 171 0 jednodimenzionalnim prilagodjenim filterima proširio na dvodi-demzionalne prilagodjene filtere. Osnovna karakteristika tih filtera je prijenosna funkcija koja u odredjenoj točki izlazne funkcije linearnog sustava maksimizira omjer signal-šum (S/N). U ovom odjeljku izvest čemo prijenosnu funkciju za dvodimenzionalni prilagodjeni filter u slučaju kada se ulazna funkcija sastoji od signala fjlx.y) kojem je aditivro primje5an Sum nj(x,y); 9]C*.y) = f[(x,y) t nj(x,y). (1) Izlazna funkcija g^tx,/) sastoji se od signala fgtx.y), koji je prouzrokovan signalom fj(x,y) prisutnim na ulazu u sustav, i od iuma np(x,y) koji je posljedica Suma "jl^^y) prisutnog na ulazu u sustav. Pretpostavimo da je Sum proces koji je stacionaran i ergodiCki u autokorelaciji (t,T) sa spektralnoro gustoćom: 'I S (Z) gdje je i^Fourierov operator. Izlazna spektralna gustoća sluCajnog Suma n^(x,y) dana je izrazom: (u,v) • |H(u,v)|' dudv. (3) gdje je H(u,v) prijenosna funkcija linearnog sustava. Ako je Fj(u,v} = ^Cf](x,y))3 tada je Fourierova trans- formacija izlazne funkcije f^(x,y): i^Cfj(x.y)D ■ H(u,v). Sto u vremenskom prostoru odgovara konvoluciji; fpC^.y) = fi{x,y)® h(x.y). Energija signala S u toćki (£,n) dana je sa: S ' ìf^U.nf {4) ■'II F (u,v) exp (j(uC+vri)) dudv|® (5) |^Fj(u,v) H(u,v) exp {j(uC+vn)} dudv[ fikaciju procesora s obzirom na broj koraka koji su potrebni za računanje aritmetičkih 1 logičkih izraza, Aritmetički izraz E možemo definirati kao pravilno tvoren niz sastavljen najmanje iz jedne Od četiri aritmetičke operacije (+, -,*,/), lijevih 1 desnih zagrada (ukoliko su potrebne) i atoma koji su konstante il1 varijable CS]. Aritmetički izraz sastavljen od n atoma označavat ćemo sa E. Logički izraz L je pravilno tvoren niz sastavljen najmanje iz jedne logičke operacije, lijevih i desnih zagrada (ukoliko su potrebne) i atoma koji su logičke varijable ili konstante. Logički izraz L sastavljen od n atoma označavat Ćecno sa L. Od izvedbe procesora zavisi broj koraka T koji je potreban za računanje aritmetičkih E i logičkih L izraza. 3,1 Procesor hijerarhijske razine H^ fvifdrtja 1 Primjenom potrebnog broja procesora sa ulazima samo za dva atoma (procesor izvodi binarne i unarne operacije) aritmetički izraz E može se izračunati u TCE]> 'log2n"^ koraka. {3} gdje '"x"' označava gornju cjelobrojnu vrijednost broja x. Dokaz tvrdnje 1 je trivijalan tS]. Tvrdnja 2 Broj potrebnih koraka za računanje logičkog izraza L pomoću procesora s ulazima za samo dva atoma je TCL]> logi n (9) Upotrebom jednadžbe (5) i (3) dobivamo omjer signal--ium koji se treba maksimizirati : JJfj{u,v) H(u,v) exp {j{u?+vn)> dudv| IK (6) (u,v) |H(u,v)|' dudv Pomoću Schwarzove nejednadibe slijedi da je omjer (6) maksimalan [6] ako je F,(u,v) exp {-j(u^+vn)) .K-^-- , (7) gdje je K proizvoljna kompleksna konstanta i Fj{u,¥) konjugirano kompleksna vrijednost spektra signala ulazne funkcije. Jednadžba (7) predstavlja optimalnu prijenosnu funkciju koja maksimizira omjer S/N u točki 3. HIJERAHIJA PROCESORA Procesori su važna komponenta digitalnog sustava za raspoznavanje. Oni gotovo izravno utječu na performansu' sustava. U ovom dijelu članka predlažemo izvornu klasi- Definicija 2 Procesor koji izvrSava osnovne aritmetičke i logičke operacije, te ima ulaze za dva operanda i zadovoljava tvrdnje 1 i 2 naziva se ppooesor Pg ili procesor hiiei-urhijalce vazine Procesor p^ je komponenta većine danainjih računal-ski h sustava i predstavlja jednu od osnovnih značajki arhitekture računala koja se zasniva na von Neuinannovom modelu računala. Paralelno računanje nekog aritmetičkog izraza primjenom potrebnog broja procesora razine p^^ obično se prikazuje tzv. stablom redukcije po razinama. Na primjer, slika 2 prikazuje računanje izraza E<9> = a»b*c + + d*c*f + g*h*i. $Uka 2, Stablo redukoije po positiama sa E ue pcmađ prooeeora p^ 62 3.2 Procesor hijerarhijske razine Hi Jednovrsni aritmetički izraz E|j je pravilno tvoreni niz sastavljen samo od jedne vrste aritmetičkih operacija (ili +, ili —, 111 *, ili /), lijevih i desnih zagrada (ukoliko su potrebne) i n atoma koji su konstante 11i varijable. Na slićan naćin maiemo definirati jednovrsni logički izraz; Ly je pravilna tvoren niz sastavljen od jedne vrste logičkih operacija, lijevih 1 desnih zagrada {ukoliko su potrebne) 1 n atoma koji su logičke konstante ili varijable. Tvrdnja J Procesor pj neWa je takav da.ima m ulaza; (m > 2) i izvodi m-arne operacije. Upotrebom potrebnog broja procesora pi jednovrsni aritmetički izraz izračunava se u: n" koraka. (10) T^nMja 4 Broj koraka za računanje jednovrsnog logičkog izraza L^ pamoCu potrebnog broja procesor^ pi je; TCL^]>'iog^ n"'. {11} Definicija 2 Procesor koji izvodi jednovrsne aritmetičke 1 logičke operacije 1 ima m > 2 ulaza za atome (izvodi m-arne operacije), te zadovoljava tvrdnje 3 i naziva se prooeear pi 111 pTOceaor hijerarhijske razine Hi. Primjeri izvedbe procesora hijerarhijske razine Hi prikazan je u radu N. Konvarasa, gdje je opisan procesor za istovremeno zbrajanje m n-bitnih podataka I9j. Slika 3 prikazuje primjer računanja aritmetičkog Izraza E<9> = a*b*c + d*e«fi-g*h»i, gdje se a*b«c, d*e»f ig*h*i mogu promatrati kao tri jednovrsna aritmetička izraza , E^^ i E^^, a njihovi rezultati kao operandi za jednovrsni aritmetički izraz sastavljen od tri atoma. ______________ slika 3. Računanje f uz pomođ proaesopa pi 3.3 Procesor hijerarhijske razine Hj Procesor hijerarhijske razine Ha predstavlja neku vrstu „računskog demona". Namjerno smo upotrijebili izraz koji je koristio O.G. Selfridge za opisivanje postupka učenja u sustavima za raspoznavanje uzoraka 1103. jer se procesor u hijerarhijskoj razini Hj korjenito razlikuje od onoga Sto pod izrazom „procesor" podrazumijevamo u računalskim znanostiina. Na primjer, slika 4 prikazuje inačicu procesora koji se djelotvorno upotrebljava u sustavu za obradu slika RADIUS (tvrtka Kyghes Research), lako ovaj procesor nema sve značajke procesora hijerarhijske razine Hj može nam poslužiti kao dobra ilustracija u kojoj mjeri procesori mogu odstupati od onoga ito pod tim izrazom podrazumijevamo. Procesor (si, 4] upotrebljava simbolički naCin predstavljanja brojeva (tzv. residualni brojevni sustav). Ulazni podatak se jednoznačno predstavlja kao ostatak dijeljenja sa bazama 81, B2, B3 1 B4 gdje su baze izabrane kao prim brojevi (BI = 31, B2 = 29, B3 23 1 B4 = 19). Točnost predstavljanja brojeva je Bi-Bj-Bj-B, Z"'*, Središnji dio procesora je memorija RAM koja se upotrebljava kao "look up" tablica za uračunanje" funkcija f(a,b), gdje su a 1 b ulazni podaci. Procesor je „pro-gramabilan", odnosno računala domačin puni tablicu u zavisnosti od tipa funkcije f. f a,J t^wtitt rtoro mi) fio» u; Aooe* as) = a«b*c+d*e*f + g*h*i pomoču procesora p2. <7» Ò*C + uz poaiod proaeaopa pj Procesori u razinama Ho, Hi i H2 imaju takve značajke da vrijedi slijedeće: Ako neki procesor p ima svojstva hijerarhijske razine Hj, tada taj procesor ima i svojstva procesora razina Hl i Hj, Neka je procesor p iz razine Hz, Ograničimo funkciju U samo na jednovrsne operacije i neka je m > 2. Tada procesor poprima značajke procesora razine Hi. Ako uvedemo i oodatno ograničenje m = 2 dobivamo procesor hijerarhijske razine H« (u skladu s definicijama 1-3). 4. ORGANIZACIJA SUSTAVA ZA RASPOZNAVANJE Sustav za raspoznavanje rukom pisanih numeričkih znakova oblikovan je pomoću deset dvodimenzionalnih prilagodbenih fi Itera. Svakom razredu uzoraka u^ì i = 0*1« .,.,9 priredjena je prijenosna funkcija H^(u,v). Slika 6 prikazuje organizaciju sustava. Svi prilagodjeni filter! imaju zajednički ulaz koji je ujedno i ulaz u sustav za raspoznavanje. Izlazi iz dvodimenzionalnih pri-lagodjenih filtera su spojeni s jedinicom za detekciju maksimalne vrijednosti. Ulazni podaci - rukosti pisane brojke - ispisani su na posebnim obrascima (si, 7), Znakovi su napisani u kvadratima označenim svjetloplavim okvirima dimenzija 7 X 10 mm i u medjusobnoj udaljenosti dva milimetrai 0 0 .0 ::/ 'l-f ■'/ /'l -'i 2 Slika 7. Ulazni podaci napisani u ohs^aima TV kamera s odgovarajućim upravljačkim sklopovima pretvara sliku u analogni signal, a digitalizator upravljan računalom pretvara sliku u matricu dimenzija 16 " 16 slikovnih elemenata. Analizom spektra i odredjivanjem graničnih frekvencija signala utvrdjeno je da dimenzije matrice 16 * 16 zadovoljavaju i da se u skladu sa Shan-nonovim teoremom ulazni signal može rekonstruirati C16]. Mnoge baze podataka sustava za raspoznavanje imaju slične dimenzije ulaznih uzoraka (npr. Highleymanova baza podataka ima matricu dimenzija 12 * 12 C3], a neki komercijalni sustavi imaju i manje dimenzije (npr. 9*7 CU])). Digitalizator kvantizira svaki slikovni element u 256 razina (8 bita). Analiza histograma pokazala je da su oni bimodalni, te su za opis uzoraka rukotn pisanih znakova dovoljne samo dvije razine. Binarnu sliku dobili smo postupkom usporedjivanja s pragom p, gdje je prag p zavisan od osvjetijenosti slike, vrste i boje pisaljke te vrste i boje podloge. Slike smo binarizirali u odnosu na prag p koji se nalazi na minimumu izmedju dva vrha histograma [15], Histogrami su dobiveni uz pomoć ulaznih uzoraka iz skupa za učenje. Slika 8 prikazuje binarizirane matrice ulaznih uzoraka. xutui KX IHK äX XKIItl IKXXXJIXXX H **J IXI 1 I» II* IX iti m KXX NAX^XXXl 1 "IX X] XA 1 X XX4 XX tti XXIXK XXXIIKX «II ■ IX XIX XXltd Jbr w "iCi-J M < .JJ Slika 6. Orqaniiùai^a euetaua za faeposnavanje ■ »XXXIXX II< xxxixx XXXAIX *« mi XAX IIX II XXXI m xm IXXUXX XXX II IXX IIIXXXXI XAIXXXA tr. xxxx - IXXXXI II XX IXXI XlIX I-t IX'tKI KIXXXXI I x«< XXXIXXXXI IIIXIX ItIXXXN XX XXf IXX IIIXXX m xxi XXX XXX XllXX XX »III XXIIKAX III XXI XXXI SHka 8. Sinariaipane matpiae ulaznih uzoraka 64 Da bismo provjerili djelotvornost sustava za raspoznavanje, sustav smo simulirali na računalu CYBER 72/24. Simulacijski programi su napisani u Fortranu i sastoje se od devet nezavisnih modula tako da. naffl omogućava djelotvorno mijenjanje i eksperimentiranje sa sustavom za raspoznavanje C163. Kao ulaz u simulator upotrebljeni su tiinariiirani uzorci. Simulacija je podijeljena u dvije faze. Prva faza, koja odgovara fazi učenja sustava za raspoznavanje, izvršava se pomoću sedam programskih modula. Ti moduli određjuju signalnu komponentu spektra ulazne funkcije, spektralnu gustoću Suma i prijenosne funkcije filtera, Zbog jednostavnosti simulacije prijenosne funkcije se odredjuju u frekventnom prostoru primjenom brze Fouri-erove transformacije (FFT). 4,1 Odredjivanje signalne komponente ulazne funkcije Pomoću skupa uzoraka za učenje [gj(x,y)) odredili smo skup statističkih funkcija: St-(x.y) = Pj(gj(n,y) = tluj). (13) za X =■ 0,1,2.....15 i y = 0,1,2..... 15, gdje je Uj e{0,1,2.....9} razred uzoraka. Primjer funkcije St(,(x,y) prikazan je na slici 9 i predstavlja vjerojatnost (u postocima) pojavljivanja jedinice u pojedinim elementima matrice uzorka 0. Skup funkcija St.,(x,y) se preslikava u skup signala f[j(x>y) pomoću slijedeće relacije; fli('<.y) = < ako je St.(x,y)>q. i fj^{x,y) = 0 ako Je St^(x,y} i 0 0 0 a C • •1 HOJO D A 0 C 0 u 0 0 il C i • n a fi 0 0 9 0 1) « 9 c 0 u 0 D Ü <, 0 • M fi 0 U 0 0 6 11 23 > 0 II 0 0 u u 0 • - ■: 0 0 IJ IJ diluii V3 S« ti 33 U 0 C 9 • • :) 0 eoitoiso 66 ib Jt. ti T3 93 li 0 11 ti • ■ 1 £ü]Oü)fiü S3 a f) » 0 6« »3 So ss u i» 0 • » * II i6!0D i a 0 0 0 «0 80 »3 a i C D • » » lì >0100 16 0 0 fi 0 0 40 ai 06 li t t 0 • 3 Ì610U 93 !D 0 n 0 >3 »010» 66 i) D 0 0 • » !) t Una ao 4o la 33 a» li 6 0 0 0 • P » n 0 « 53 SOJJJIOQIUJ 9J le 0 0 0 El 0 • w stika 9. Prtmjep funkoije Stt(si,y) [zraz [17] računamo primjenom brzih postupaka za odredjivanje autokorelacijske funkcije C203,C21]. Za svaki razred uzoraka i - 0,1.....9 možemo sada odrediti prijenosnu funkciju dvodimenzionalnog pri-lagodjenog filtra: (C ' n = 0): FjiCJ.v) "li (19) Time je postupak učenja sustava la raspoznavanje završen. 4,3 Rezultati raspoznavanja 4.2 Odredjivanje spektralne gustoće 5uma Sum za pojedini ulazni uzorak odredjujemo kao razliku; (16) k = 1.2.....H-, H^ je broj uzoraka za učenje u razredu Wj ; i = 0,1,2,... ..., 9. Spektralnu gustoću računamo pomoću izraza; , "i I i t-l Pojedine funkcije n]|^(x,y) smo umnožili s Hammingo-voffl funkcijom [17] zato da bismo umanjili Gibbonov utjecaj [18], Pomoću Huangovog teorema C19] možemo Hamningovu funkciju napisati u obliku: Druga faza simulacije odgovara procesu raspoznavanja. Na ulazu sustava dovodi se nepoznati uzorak. Preostala dva programska modula daju odziv filtera i razvrstavaju uzorak na temelju maksimalne vrijednosti odziva. Opisani sustav za raspoznavanje smo testirali na četiri zbirke rukom pisanih numeričkih znakova. Pokus 1 Prva zbirka sastoji se iz ISO numeričkih znakova. Brojke su pisane tušem i tehničkim pismom (si. 10). Sustav je bez greSke pravilno razvrstao uzorke. Pokus H Druga zbirka sastoji se iz 50 numeričkih znakova koji su napisani kemijskom olovkom i „normalnim" pismom (si. 11). Rezultati raspoznavanja su i u ovom slučaju 1005Ì pravilno razvrstani. 00 0 000000000 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 ì 1 122222 2 2 2222 2 22233333333333 333 3 4 444 4 44444 444-4455 5555535 555355666656 6 6 666666677777 7 7 77777 7 770ÖÜ0GÖ 88883888893999 9999999999 Slihì 10. Brojke pisane tušem i tehničkim pismom i0i;0;,0,0 0^1111222 Ì8j|8j:8|i8!^ii3::9||s?i;3::9i i: i Slika 11. Zbirka ulaznih podataka sa drugi pokus o!|üilcjioiioi;o:.ci;;'/i;'yi 7 'ih^ 1 i\ 2|i2si?:^2;:2 2 ..3 J .3 \b |7||7ÌÌ7Ìjr'l7>i'7:TÌ:7!:7!7'7': " : ie||6i|8:;8:8 8:.8 s-s e e 8 " s::?:;?: s 9 g Slika IZ. Dio »birke uU»nih podataka sa Setvpti pokue 5. SINTEZA SUSTAVA ZA RASPOZNAVANJE Slika 14 prikazuje blok dijagram sustava za raspoznavanje. Izvedba gore opisanog sustava za raspoznavanje jednostavnija je ako se zadatak raspoznavanja izvodi u vremenskom prostoru. Na tenielju gore opisanog postupka simulacije - u prvoj fazi odredjene su prijenosne funkcije filtera H^(u,v) u frekventnom prostoru. !8;i8||K!:8i;8::ö::8:;9i:g 9::9 9 9 9' Slika 12. Oio zbirke ulasnih podataka sa treói pokus Pofcus III Sastavili smo zbirku Iz 77 rukom pisanih numeričkih znakova. Znaci su pisani kef»1jskom olovkom. Neki od znakova nisu bili zakljuCenl (npr. 0 ili 9) (si. 12). I u ovom slučaju rezultat raspoznavanja bio je 100%. Pokus IV Sastavili smo zbirku iz 132 znaka. Znakove smo pisali tako da smo dozvolili 20% promjene u visini i äi-rini znakova (si. 13). U ovom sluCaju točno razvrstanih znakova bilo je 86,64%. Slika li. Blok-dijagram sustava sa raspoznavanje Vrijednosti izlazne funkcije dvodimenzionalnih pri- lagodjenih filtera g^^, 1 ° 0,1.2.....9 u točki (OtO) su odredjene izrazom: 9oi gii(x.y). (20) «-0 V-D gdje.^' označava Inverznu Fourlerovu transformaciju, a H.j(u,v) -konjugirano kompleksnu vrijednost prijenosne funkcije H.(u,v}1 N -.16. 66 Jednadžba (20) predstavlja, u stvari, konvoluciju h(x.y)®9n(>(.y) u točki {0.0). Računalo domačin (CYBER 72/24) u fazi inicijaliza-cije sustava za raspoznavanje prosljedjuje vrijednosti komponenata prijenosnih funkcija filtera sustava za raspoznavanje (si. 14), Sustav siože biti tako oblikovan da su komponente prijenosne funkcije h za pojedine filtere čvrsto upisane (PROM memorija). Medjutim, primjenom veze računalo do2), n--bitnih brojeva opisana je u radu N. Konvarasa et al. Slika 16 prikazuje organizaciju dvodimenzionalnog prilagodjenog filtera koji je realiziran u dva segmenta pomoču procesora ps i pi■ Ocijenimo kapacitet "look-up" tablica sustava za raspoznavanje znakova na bazi dvodi- »m menzìonalnih prilagodjenih filter«. Ukupni kapacitet: memorije C potreban za izvedbu potrebnog broja procesora Pj u sustavu li raspoznavanje je; C = Cp • Hp • M • d [bita], gdje je: Cp - broj riječi memorije jednog procesora pi koji računa djelnu sumu produkta «p - broj procesora potrebnih za izvedbu jednog prilago- ri j enog filtra, M - broj razreda uzoraka (broj dvodimenzionalnih prilagodjenih filtera), d - duljina rijeii Izražena u bitovima. Za sustav opisan u ovom radu C je: C = 256 X 32 X 1D X 16 = 10 « Z" bita (24) odnosno 84920 riječi duljine šesnaest bita. Selektor maksimuma rjeSava se programski ili primjenom integriranih sklopova s tom funkcijcm [233. 6. ZAKLJUČAK U radu smo pokazali kako se teorija dvodimenzionalnih prilagodjenih filtera može primijeniti u izvedbi sustava za raspoznavanje znakova. Simulacija sustava za raspoznavanje pokazala je da je sustav djelotvoran posebna za tipizirane znakove ili rukom pisane znakove čije Su varijacije po visini i iirini manje od 205!. Upotrebom procesora iz viSih hijerarhijskih razina prikazali smo model sustava koji je sačuvao visoki stupanj paralelizma svojstven ovom načinu raspoznavanja. U završnom dijelu članka prikazali smo putove praktične izvedbe paralelnog sustava upotrebom LSI komponenti. ?. LITERATURA' !. E.C, Lyons, Digital Image Processing: An Overview, Computer, Vol. 10, No. 8, August 1977, str. 12-H. 2. L.D, Harmon, Automatic Recognition of Printand Script, Proc. of the IEEE, Vol. 60, No. 10, October 1972, str. 1165-1176. 3. C.Y, Suen, et al.. Automatic Recognition of Handprinted Characters - The State of the Art, Proc. of the IEEE, Vol. 68, No. 4, April 1980, str. 469-487. 4. O.A. Rosenthal, R. Baycsy, Visual and Conceptual Hierarchy; A Paradigm for Studies of Automated Generation of Recognition Strategies, IEEE Trans, on PAH], Vol. PAf1I-6, No. 3, Hay 1984, str. 319-325. 5. A.M. Nazif, M.D, Levine, Low Level Image' Segmentation: An Expert System, IEEE Trans, on PAHI, Vol. PAMl-6, No, S, Septeraber 1984, str. 555-577, 6. H.C. Andrews et al,, Computer Techniques in Image Processing, Academic Press, 1970. 7. L.G. Turin, An Introduction to Matched Filters, IRE Trans, on Information Theory, June 1960, str. 311-329. 8. D,J. Kuck, A Survey of Parallel Kachine Organization and Programming, ACH Computing Surveys, Vol, 9, March 1977, str. 29-60. 9. N. Konvaras et al., A Digital System for Simultaneous Addition of Several Binary Numbers, IEEE Trans, on Computers, Vol. C-17, October 1968, str. 992-997. 10. O.G, Sel fridge, Pandemonium: A Paradigm fof Learning, u Pattern Recognition (ed, L. Uhr), J. Mlley & Sons, New Vork, 1966, 11. G.R. Nudd, Concurrent Systems for Image Analysis,' u VLSI for Pattern Recognition and Image Processing, (ed. K.S, Fu), Springer-Verlag, Berlin, 1984, str. 107-132. 12. P.L. Gardner, Functional Memory and Its Microprogramming, Implications, IEEE Trans, on Computers, Vol, C-20, No. 7. 13. R,M, Laugheed et al., Cytocomputers: Architectures for Parallel Image Processing, Proc, Workshop Picture Data Descr. and Management, Pacific Grove Calif, August 27-28, 1980, str. 281-286. 14. S.T. Tou, U.C. Gonzales, Pattern Recognition Principles, Addison-Nesley. Pub, Com., 1974. 15. A. Rosenfeld, A. Kak, Digital Picture Processing, Academic Press, New rork, 1976. 16. N. Pavešič, L, Gyergyek, Character Recognition System Based on Two-Dimens1ona1 Hatched Filters, Elec-trotechnical Review, Vol. 41, No. 3-4, 1974, p. 13-16. 17. B. Gold, C.M. Rader, Digital Processing of Signals, McGraw Hill, New York, 1969. 18. A. Papoulis, The Fourier Integral and its Applications, McGraw Hill, New York, 1962, str, 30-31. 19. T.S. Huang: Two-Dimensional Windows, IEEE Trans, on Audio and Electroacoustlcs, AU-20, No. 1, March 1972, str. 88-90. za. H,C. Andrews, A High Speed Algorithm for the Computers, C-17. No. 4, 1968, str. 373. 21. T.G, Stockham, High-Speed Convolution and Correlation, 1966 Spring Joint Computer Conf. AFIPS Conf. Proc., str. 229-233. 22. B.G. Batchelor (ed.). Pattern Recognition, Ideas in Practice, Plenum Press. New York, 1978. 23. S. Ribarič, N, PaveSić, Mikroprocesorski klasifikator numeričkih znakova s mrežom memorijskih komponenti LSI, Informatica Z/3, 1983, str. 162-167. PLOT 5 - JEDAN JEDNOSTAVNI PROGRAMSKI SISTEM ZA GRAFIČKE TERMINALE I KOORDINATNE CRTAČE UDK: 681.3.022.06 PLOT 5 Jozo J. Dujmović I Mlodrag Levnalć Elektrotehnički fakultet Beograd U radu se opisuj« FL0T5 - jedan jednostavni Biste« prograuke podr&ke za grafičke terminale i koordinatne crtače. Slsten je projektovan za potrebe inienjerskih aplikacija kod kojih au tabtevl za. 9r&fikoa ograničeni na jednostavna 1 efikasno crtanje linijskih crteta. Osnovni zahtev koji je postavljen xa PLOTS je bio da ae korisnik aaie u najkraće« vremenu osposobiti sa njegovo koritćenje, a da IstovreHeno Mote sa njia da proizvodi najsloženije linijske crtete ukljućujući faallije krivih, dvodlBenzlonalne 1 trodimenzionalne objekte. PL0T5 je napisan na FOKIRAN-u 1 lako je prenosiv. iHpleaentlran je na raćunariiia VAJi/VHS 1 trenutno podržava sinultoni rad sa graflćkl« teralnallaa tipa Tektronix serije 4110 i koordinatnim crtaćim tipa CAI^OHP 81. PLOTS - A SIMPLE SOFIMARE FOR GRAPHIC IGRMIHALS AND PLOTTERS. The paper presents PLOTS - a simple software system supporting graphic terminals and plotters. The system Is designed for general engineering user« Interested In simple and efficient production Of line drawings. The basic reguirenent fulfilled by PLOTS Is to enable Its user to guickly learn how to use the systeM for produclng^ complex line drawings (e.g. families of curves, two-dlMnslonal, and three-dimensional objects). PLOTS is written in FORIRAN, and it is highly portable. It is implemented on VAX/VMS systena and it currently simultaneously supports graphic terminals Teztronlx 4110 series, and CALCOMP 81 plotters. 1. ÜVOD Frvl sistemi za graflćkl prikaz rezultata inienjerskih proraćuna pojavili su se poćetkom šezdesetih godina. Na primer, popularni raćunarl za naućno-tebnlćke primene kao ito su IBM 1620 1 kasnije IBM 1130 korlatill su koordinatni crtač 1627 koji je omogućavao crtanje linijskih crteta Cn. Crtanje je redovno realizovano iz FORTAN programa pozivajući skup od 5 potprograma (SCALE, (>RID, CHAR, PLOT, 1 POINT) ćija je ramena bila uvodjenje faktora razdere, crtanje koordinatnih osa. Ispisivanje tekstova, crtanje linijskog segmenta 1 crtanje markera C23. HajznaCajnlja osobina ovog grafićkog sistema bila je njegova jednostavnost i efikasnosti korisnici su mogli da nauće osnovno programiranje rađa sa crtačem za prlblltno 60 Minuta. ECasnljl razvoj kretao se doninantno u pravcu usavrèavanja Interaktivne računarske grafike £3,43. Pri toHe je doAlo do razvoja velikog broja nekompatibilnih graflćklh uredjaja 1 do brojnih jednako nekompatibilnih osnovnih softverskih slsteu za njihovu podrAku. Naravno, na taj način je softver koji koristi grafičke uredjaje postao neprenosiv, pa se pojavila hi trta potreba za standardizacijom u ovoj oblasti tS]. D ulozi standarda za aada se pojavljuje GK3 t6,7] koji definire preko 100 osnovnih standardnih funkcija koje omogućavaju ftiroki spektar najrazličitijIh graflćklh prlaena. Nažalost, univerzalnost GKS-a je dobljena po cenu gubitka jednostavnosti. Tako korisnik za crtanje najprostije krive nora da pozove od 10 do 30 raznih GKS funkcija, a priručnik za GKS uzima znatno vlAe od 100 strana. Prena tome, korisnici koji tele da prlmenjuju (3C3 Moraju uložiti značajan napor da njime ovladaju i za veći broj korisnika koji nisu specijalisti za računarsku grafiku, već povremeno koriste grafičke uredjaje za prikaz odredjenlh rezultata, ovakav prilaz moie da bude neefikasan. Imajući u vidu navedene probleme u ovom radu Je predložen jedan efikasan slstea za linijsku grafiku čija se upotreba moie savladati u roku od 2 sata. Sistea je razvijen kao generalizacija grafičkog sistema za IBM 1130 1 u početku je imao za cilj da omogući jednostavan prelaz korisnicima sa IBM 1130 na VAX/VMS sisteme. Baziran je na 5 osnovnih potprograma i odatle naziv PLOTS. Ovi potprogrami se mogu pozivati iz FORHIAN programa, a takodje i iz drugih jezika koji omogućavaju isti način prenosa argumenata. Pri razvoju PLOTS sistema učinjen je pokubaj da se, zadržavajući jednostavnost u rukovanju, u sistea ipak ugradi «to vlAe savremenih osobina koje omogućavaju moderni grafički raster ternlnali i crtači u boji. Nadalje, posvećena je posebna patnja efikasnosti implementacije čije su bitne odlike sleđećei 1. Nezavisnost od grafičkog uredjaja koja se ogleda u tome dm se uredJaj bira jednim jedinim identifikatorom u programu i prelai m uredjaja na uredjaj moža se obaviti bez prekidanja rada. 2. Automatsko odsecanje svih delova crteta van zadate prikazne povrUne čime je omomćena Bakaimalna upotrebljivost slike u svim uslovlma. 3. Realizacija sistema u vidu dellmično povezanog "reentrant" aodula. Cime su svedeni na mlnlaua kako utroAak ■eaorijskog prostora za IzvrAne verzije programa, tako i vreme povezivanja sa korisnlčkla programima. Trenutno je PLOTS sistem Implementiran na grafičkim terminalima serije TEinsONIX 4110 i koordinatni« crtaćima tipa CALCOKP 81, a u toku su iBpleaentacije za nekoliko drugih graflćtclh uredjaja. R&d aa grafičkim uredjajlna se obavlja tako da se osnovne funkcije ^raflćko? prikazivanja podataka reallzuju korlaćenjem pet PLOTS potprograaa sa aledećon nauenom 1. Inlcljalizaclja . grafičkog uredjaja i definicija paranetara preslikavanja. 2. Crtanje koordinatnih osa i arete aa kotiran jen. 3. Crtanje tačaka 1 drugih oznaka na željenom ■estu ekrana. 4. Crtanje prave linije od trenutne tačke do odredišne tačke. 5. Ispisivanje tekstova uz crtet. Detaljan opis ovih funkcija sledi u nastavku. korisnikov prostor povrilnu. I I I YMÄX + I I I YMIN + I I 0 +----- 0 se preslikava na aktivnu I korisnikov | I I I prostor I I I _l ___ __ I XHIH XHMC ----> X Slika 2. 2. FRIKAZHA POVRtINA, AKTIVNA POVRAINA I KORISNIKOV FROSTDS Ekran grafičkog ternlnala i pr lica zna povrftlna koordlnatnog crtača au pravougaonici različitih fizičkih dimenzija. Pri realizaciji prograiuke podrike za grafičke uredjaje uobičajeno je da se "prlkazna povrtlna" ("display") meri u normallzovanlm jedinicama, tako da je uvek 0<"x<»*dim<"l 1 0<"y<«ydlm<«i. Pri tone sa podrazumeva da vali jedna od dve ■ogučnostli 111 xdla < ydlB ydia < xdim 1. 1. U slučaju grafičkih uredjaja rEXTROHIX 4105 1 CALCOMP 81 vati zdlm'l pri čemu jet ydlm ■ 0.765 za grafički terminal TEX 4105 1 za kopir aparat TQ( 4695 ° 0.8284 za koordinatni crtač Calconp 61. Veličine pravougaone prlkazne povrAlne su 200*153 ma za grafički terminal i kopir aparat 1 338x260 sn za koordinatni crtač Calconp 61 . Prlkazna površina grafičkog uredjaja data je na slici 1. Redovno korisnik ne koristi celu prlkaznu površinu. Pod "alstìXEiaB Egvràinaa" ("viewport") podrazuaeva se onaj deo prlkazne povrAlne na koji korisnik nanerava da ograniči svoj crtež. ydla py PRIKAZNA POVRŠINA I aktivna | ay \ I I površina 1 I ax I -+ ! I P* —+ xdlRi > 1 Slika 1. Sa druge strane, -koriaMltov prggtgr" ("window") je u opitem slučaju pravougla oblast u korisnikovom koordinatnem sistemu koja obuhvata sve ono &to korisnik namerava da posmatra (slika 2.) Korisnikov prostor se po X osi protele od XMIN do XMAX a po y 03l od YMIM do YHAX, gde su XMIN, XMAX, YMIN, 1 YMAX zadati u korlanlkovlm jedinicama 1 prema tome predstavljaju proizvoljne racionalne brojeve. Kod prikazivanja na grafičkim uredjaj ima Dimenzije aktivne povrilne (sx i sy) kao 1 koordinate njenog levog donjeg ugla (px 1 py) zadaju se u koordinatama jediničnog kvadrata pa prema toae «oraju da zadovolje uslove 0 < 0 < ' p* < 1, px+sx <■ 0 <■ py < ydlm, O < py+sy <■ ydlm Na primer, korisnik mote da nacrta kvadratnu sliku najvećeg formata birajući px-py-O, az>By«ydim. Prema tome, celokupno grafičko preslikavanje mole se deflnlsatl sa skupom od sledečih 10 parametara■ xdln,yđlm p*,py,ax.sy XMIN,XMAX,YHIN,YMAX ■ parametri prlkazne povrAlne (fiksno deflnlsan za svaki konkretni uredjaj) parametri aktivne povrAlne paramterl korisničkog prostora Delovl crteža mogu da izadju 1 van okvira aktivne povrAlne a 1 van okvira prlkazne povržine. Ha crtačima 1 na grafičkim terminalima se delovl crteža van prlkazne povržlne uvek automatski odsecaju bez bilo kakvih posledica na deo crteža koji sa nalazi na prlkaznoj povriinl. Delovl crteža van. aktivne povrilne mogu se takodje automatski odsecatl, ali samo na eksplicitan zahtev korisnika dat u potprogramu SCALE. 3. BOJE, PISALJKE I KOPIRANJE CSIEIA Grafički terminal radi sa 8 boja koje su kodirane brojevima 0,1,..,,7. Sistem PL0T5 daje ovio brojevima, prema standardu TEKTRONIX-a, sledeče početne vrednosti« O ■ - crno 4 - tamno plavo 1, - belo 5 - svetlo plavo 2 - crveno 6 - ljubičasto 3 - zeleno 7 - žuto Navedene vrednosti mogu se po potrebi menjati korIsteči "setup" proceduru terminala all u svakom momentu broj prisutnih boja koje terminal slnultono prikazuje ne note biti večl od e. Prema tome, u svim programima koji slede pod pojmom "boj^a" podrazumeva se jedna cifra clja je interpretacija defInisana gornjom tabelom. Pri tome terminal podrazumeva da Je boja pozadine crteža početno definìsana sa kodom O pa je stoga pozadina uvek crna (neosvetljena). Ako ae želi to izmenitl onda se mora Intervenlsati u "setup" proceduri sa kojom se može kodu 0 dodeliti proizvoljna boja. 111 odrediti da boji pozadine ne odgovara kod 0, več neki drugi od postojećih kodova. Crtei ae aa ekrana noie direktno kopirati na papir, pri teou ae koristi kopir aparat TEK 4695. Kopiranje traje oko 4 minuta, pa. ga treba koristiti sa «eron i to uvek saao za konaćne rezultate. Koordinatni crtaC ina 8 pozicija za pisaljke koje mogu biti u raznim bojama l/lli u t-ajnlm debljlnaina. Pronena pisaljke programski je ekvivalentna prometti boje na graflćkoa temlnalu. Početni razmeitaj pisaljki u 8 raspoloživih kućiita obavlja se pre početka rada ručno od strane operatora. Naravno, pisaljke se mogu menjati 1 u toku rada ako se za to predvidi odgovarajuća pauza. 4. INICIJALIZACIJA UREDJAJA I DETIKISANJE PARAMETARA PRESLIKAVANJA Da bi se korisniku olakšalo programiranje svi E'LOTS potprogroml za rad a& grafičkim uredjajima su Isti za sve uredjaje. Naravno, fizičke osobine uredjaja 1 način komuniciranja sa njima se međjusobno razlikuju. Stoga je na početku rada neophodno defInisati ured jaj sa kojim se namerava raditi, izvriitl inlclJalizaciju uredjaja 1 uvesti parametre preslikavanja. To se postite pozivom potprograma dimenzije prlkazne povriine (horizontalna dimenzija HH i vertikalna dimenzija W1 konstantne su 1 zavlae od uredjaja. Korlanik takodje redovno teli da njegova slika ima donju (horizontalnu) marginu 1 levu (vertikalnu» marginu čije su dimenzije HM 1 VM reapektivno. Koristeći zadate veličine H, V, HH, W, HH i VM mogu se direktno Izračunati parametri aktivne površine. Ako je xdlm»! ovi parametri sui px = VM/HH, py = HM/HH s* = H/HH, sy » V/HH 1 mogu ae direktno unetl SCALE. u poziv potprograma Potprogram SCALE definlie trenutno korlićeni uredjaj koji ae mote tokom rada menjati. Tako če, na primer, pozivom CALL 3CALE(I,...) biti korisniku dodeljen grafički terminal na koga če se odnositi svi naredni PLOTS potprogrami. Ako se u istom programu zatim Izvrtl potlv CALL SCALE(2,...) onda če se grafitki terminal osloboditi 1 korisniku dodeliti crtač na koga če se zatim primenjlvatl preostali potprogrami. Novi poziv CALL SCALEd,,..) oalobadja crtač (1 drugi korisnici ga mogu odmah koristiti) 1 opet zauzima grafički terminal. Treba napomenuti da se pri promenl grafičkog uredjaja po pravilu aenjaju parametri prlkazne 1 aktivne povrilne u potprogramu SCALE, ali pozivi svih ostalih potprograma ostaju nelzmenjenl. CALL SCALE ( ID, px,py, sx,ey, XMIN.XMAX, YHIN,YMAX ) pri čemu Je ID Identifikator grafičkog uredjaja .1 načina odaecanja: I ID za. grafički terminal TEK 4105 za koordinatni crtač Calcomp 81. Ako Je ID>0 onda ae odsecanje obavlja na granici prlkazne povrSine, 8 ako je ID<0 onda se odsecanje obavlja na granici aktivne povrilne. Smisao veličina px,py, sx,sy, XMIN.XMAX, YMIH,YHAX je Jasan sa slika 112. Pri tome ponavljano da su px,py,ax,ay Izratenl u delovima jediničnog kvadrata (tj. u normalizovanlm koordinatama), dok su XMIN.XHAX, YHIH,YHAX Ixraìenl u korisnikovim jedinicama koje će se isključivo koristiti u ostalim PLOTS potprogramlma. Korisnikov prostor obuhvata pravougaonlk XMIN <« YMIN <= X <« XMÄX y <» YHAX pri čemu XHIN, XMAX, YHIN, i YMAX mogu biti proizvoljne pozitivne, nulte ili negativne veličine, čime ae odredJuJe gde će biti koordinatni početak (vidljiv unutar ili na rubu slike, ili nevidljiv izvan alike). To znači da se tačka korisnikovog prostora sa koordinatama XHIN.YMIN preslikava u tačku sa koordinatama px,py prlkazne povriine (tj. u levi donji ugao aktivne povrilne). Prilikom crtanja na koordlnatnom crtaću (a 1 na drugim grafičkim uredjajima) najćeiće se polazi od željenih dimenzija slike koje se zadaju u dutlnsklm Jedinicama (cm ill mm). To aut H = horizontalna dimenzija (iirlna) slike V > vertikalna dimenzija (visina) alike. Veličine HIV odredjuju flzićke dimenzije aktivne površine. Sa druge strane, fizičke 5. CRTANJE KOORDIMAIHIH OSA I HREtE SA KOTIRANJEM Ova funkcija ae obavlja pozivom CALL GRID ( DX, NX, OY, NT, ID ) gde su D« 1 DY veličine Jednog podeok» (t.J. razmak iznedju dve susedne linije koordinatne mrete) po z 1 y koordinati izratene u korisnlkovlB Jedlnlcoaa, NX 1 NY predstavljaju broj označenih podintervala na koje je izdelJen svaki podeok (ako nema podintervala onda Je NX=NY=1», a ID je četvorocifrenl Identifikator n&čina crtanja definlaan sa četiri cifre, okmb. sledećeg značenjai o • pravougaonl okvir korisnikove slike (O • bez okvira, 1 ■ sa olcviroa slike) k 3 kotirane ose (O ° bez osa, 1 • sa os&aa i kotiranjem) m = mreta (O • bez mreže, 1 ■ mreža od punih linija, 2 • mreta od duzlh crtica, 3 • mreža od kraClh crtica Cna grafičkom terminalu to au tačkicelr «to je veča vrednost za m to Je rad crtača sporiji) b " boja (kodirano sa identlfikatorom boje O,,...7) Ako ose ne prolaze kroz korisnikovu slDcu onda se u slučaju ID»11Ob automatski kotiraju sve četiri strane okvira, a u slučaju ID-OlOb se crtaju one dve kotirane strane okvira koje su najbliže koordinatnim osama. U slučaj^ tD'lOmb nema kotiranja, pa vrednosti NX i KY nemaju utlcaja. Kad god se trati mreta automatski se crta 1 (kotirani 111 neRctlroni) okvir. 6. CSTAHJE TACAXA I DRUGIH OZHAKA HA tELJEKOM MESTU PRIXAZNE POVRAINE Ispisivanje željene oznake u tački X,y (izraženo u korisničkim koordinatama) realizuje se pozivom CALL POINT ( X, ID ) gde Identifikator ID definlse tip oznake sa dve ill tri cifre pri «eau zadnja cifra (b) oznatava boju oznake t 4105 1 BI lb 2b 3b 4b Sb &b + (nali plua> + (veći plüa) X (veći Iks) veći kvadrat A poCetak več u odnosu na trenutni položaj). Tip linije 1 boja (b> su odredjenl apsolutnom' vrednotCu Identifikator» ID na sledećl naćlni lb - ponak bez crtanja linije 2b ■ _ I koordinatne 9b - ' I ose i oznake 10b = V I taćaka lib = ¥ 12b = mali Ispunjeni kvadrat 13b " mali neispunjeni kvad. 14b = X (isanji iks) e. ISPISIVANJE TEKSTOVA UZ CSTEl Na korisnikovoj slici Boguće je Ispisivati proizvoljne tekstove pomoću potprograma CALL TEXT ( X, Y, DAXA, P, ID ) Sano 4105 ISb ° 0 (nula) l&b kvadrat sa t&ćkom unutra 17b = ispunjeni kvadrat 18b = romb 19b = ispunjeni romb Identifikator ID moie biti 1 negativan. U ton slućaju X i Y su u korianikovin jedinicama izraiene vellćlne RELATIVNOG POMAKA iz date polazne, taćke (t.j. X i Y se ne Izražavaju u odnosu na koordinatni poćetak veC u odnosu na trenutni poloiaj iikazatelja ekrana). Tip oznake odredjen je apsolutnom vrednoiću identifikatora ID, na naćln prikazan gornjom tabelom. U slućaju grafićkog terminala potprogra» POIIfl se može primenlti i za brisanje ekrana, Sto se reallzuje pomoću IdentlfIkatora ID-0. U ton slučaju X oznaćava broj sekundi ćekanja pre brisanja ekrana a V oznaćava broj sekundi ćelcanja posle brisanja ekrana. Stoga, na poćetku prograna, u većini alućajeva treba primenitl poziv CALL POINT(0.,0.,0); crtać na ovo ne reaguje. pri ćeau argumenti interpretaci ju i imaju sledeću 7. CRTAMJE PRAVE LINIJE OD TRHaflJTNE TAĆKE DO ODREDIANE TAĆKE U svakom aoaentu pisaljka crtaća 111 ukazatelj ekrana grafićkog terminala se nalaze u nekoj taćki prlkazne povrćine. Ovu taćku nazivamo trenutna pozlcUa 1 označavamo sa A. Neka su X,y koordinate proizvoljne odredišne taćke B. Taćke A i B nogu se spojiti pravom linijom pònoCu poziva CALL LINE ( X, Y, ID ) pri ćemu su X 1 Y izraženi u korisnikovim jedinicina. Ako je ID>0 onda su X 1 Y apsolutne koordinate u odnosu na koordinatni poćetak. Ako Je ID<0 onda su X 1 ¥ u korisnikovim jedinicama Izražene velićlne relativnog poina)ca Iz polazne taćke A (t.j. XI Y se ne Izražavaju u odnosu na koordinatni X,Y koordinate levog donjeg ugla teksta Izražene u korisnikovim jedinicama. DATA - podatak koji se ispisuje: note biti znakovnog, celobrojnog ili racionalnog tipa. vellćina koja oznaćava ispisivanja na sledećl naćlnt foruat ID F ° , ako je DATA niz znakova 111 ceo broj F = ., za slućaj da je DATA racionalan broj. C-3uvl>Bt (identifikator, do 7 cif ara) kojim se odredjuje nagib slova, ugao Unije teksta, vellćina slova, boja, sner, 1 tip teksta na sledeći naćln: Negativan identifikator oznaćava za CALCOMP ei slova nagiba 75 stepeni, a pozitivan identifikator slova nagiba 90 stepeni (kod grafićkog terminala nagib slova je uvek 90 stepeni). u = ugao Unije teksta sa -t-x osom dat u stepenima (1 do 3 cifre, pri ćemu je u >= 0). Koordinatni crtać ovaj ugao moie da taćno prikaže, dok graflćki terminal vrèl zaokruživanje zadatog ugla na najbliži multlpl od 90 stepeni. V • oznaka vellćlne slova Iz skupa (0,1.....9) kojom se odredjuje èirina slova prena sledećoj tabeli i äirlna slova u mm. 4-BBsEBB3zBSBttKigssBBBB3saaaBaaaassaBBBBBSssBSBsea + |v 10 1 2 3 4 5 6 7 B 9| I TEK I 2.1 2.1 4.2 6.3 8.4 10 12.6 14 16.S 19| I CAL I 1.2 1.8 2.4 3.0 3.6 4.2 7.2 12.6 20 30| Za. koordinatni crtać CALCOMP 81 visina Aova se odredjuje automatski 1 iznosi 3/2 «irlne. Za TEKTRONIX 4105 visina slova Je 7/5 Širine. b - boja teksta (0,1,...,7) a • aver Ispisivanja Iz skupa od 4 snera u odnosu na liniju Icoju definire odabrani ugao u < O°deano, logore, 2'levo, 3>dole ). t - tip teksta koji» se odredjuja Ata ae ispisuje, na sledeći naćint t • 1, ako Je DATA celobrojno? tipa t • 2, ako je DATA racionalno? tipa t ° 3, ako je DATA znakovnog tipa 9. IMPLJEKEIITACIJA PLOTS SISTEIU. GraflCkl sistemi koji nude nogućnoatl kao PLOTS, u tipltnoB sluCaJu se sastoje od stotlnak potprograaa 1 prevedeni Hogu zauzimati od 50KB na vite. To znaCl da bi praktiCno svaki grafitkl program morao obuhvatiti celokupan proces povezivanja i da bi Izvrftna verzija svakog programa blia opterećena sa celokupnim softverom grafitkog sistema. Ha taj naćln se pored gubitka vremena dolazi do potpuno neprihvatljive situacije u kojoj se na diskovima nalazi onoliko koplja celokupnog grafičkog softvera, koliko Ima graflćklh programa. U uslovlua velikog broja korisnika 1 velikog broja malih graflCklh prograna ovo mole da bude izuzetno ozbiljan problem. Zbog toga je neophodno da Implementacija grafičkog softvera zadovolji dva fundamentalna zahtevat 1. Parcijalno povezivanje svih grafičkih potprograma sa izuzetkom najvišeg nivoa čime se formira bazični grafički modul 2. Fiksno 1 jednokratno Instaliranje bazičnog grafičkog modula u memoriju računara tako da Je Istovremeno dostupan svim korisničkim grafičkim programima. PL0T5 sistem zadovoljava navedena dva zahteva. Parcijalnim povezivanjem su potprogrami SCALE, GRID, FOIMT, LIKE i TEXT Jednom za uvek povezani sa svim potprogramima koji se dalje lančano pozivaju 1 tako Je formiran bazični grafički modul. Proces povezivanja korisničkog programa sa bazičnim grafičkim modulom Je tada vecma bri Jer se svodi na realizaciju sama onoliko veza koliko u korisničkom programu Ima poziva osnovnih PLOTS potprograma. 3a druge strane, izvrtni programi su veoma mali jer obuhvataju jedino korisničke instrukcije i veze sa bazičnim grafičkim modulom. Naravno, za ovakav način implementacije neophodna je 1 odgovarajuća podrika operativnog sistema koja Je u slučaju VMS-a raspoloživa. 10. PRIMBII PRIHEHE PLOTS SISTEMA Verovatno najčeftčl primer priaene grafičkih sistema Je crtanje familija krivih. Stoga je u nastavku prikazan jedan opiti program za Ispitivanje osobina familije krivih prema sledečim zahtevima; (1) Korisnik prikazuje familiju krivih na grafičkom terminalu zadajučl interaktivno koordinate korisničkog prostora XMIN, XHAX, YMIN, YHAX čime bira 1 proizvoljno uvečava deo XV ravni koji teli da poamatra.. Cc C C" C C C C C C C C C C C C C-- COTANJE FAMILIJE KRIVIH KA lamillALU I I KOORDIKAINOM CRTACU 1 ------------------------------------------- HH,W - Dimenzije prlkazne površine u mm H ,V - Željene veličine aktivne površine (veličina crteža) u mm HM,VM - Širine horizontalne i vertikalne margine u mm SS - Dimenzije slrlne slova u mm 131 - Ident. željene širine slova (kote) 132 « Id. željene slrlne slova (naslov) «X,(iy « Broj kotiranih podeoka duz osa UK > Opseg u kome se kreće parametar familije krivih X t-NK <• K <> NX) N3BC - Broj linijskih segmenata po krivoj C— C C---- DIMEH3I0H HH(2), W(2), H(2), V<2), * HM<2), VM(2). 33(0(9,2). 131(2). IS2C2) CHAIiACTER*30 NASLOV I Naslov slike DATA HH, W /200., 338., 153., 280./, A H, V /110,. 102., 110., 102. / DATA S3 / *2.1,2.I,4.2,6.3.8.4,10.,12.6,14.,Ifi.5,19. 1.2,1.8.3.4,3,,3.6,4.2,7.2,12.6,20.,30./ DATA ISl/1,1/, 132/2,4/, HX,Hy/10,10/, * NK/S/, HM,VH/36.,e0.,45.,30./, NSECaSO/ C---- Familija krivih sa parametrom K F(X,K) - 4*3IN(0.9*K) + (X-2*K)**2 NA3L0V - 'Primer familije parabola' DO WILE ( .TRUE. ) 1 Početak glavne petlje C---- Unos parametara I izbor uredjaja PRINT *, 'XMXH,XHAX,YMIN,YMAX, Tip', * ' uredjaja (1-terminal, 2-plotter) 7 ' READ XMIN, XMÄX, THIN, YMAX, ID IF (ID .LT. 1 .OR. ID .GT. 2) STOP - Inicljallzacija uredjaja 1 definlsanje parametara preslikavanja CALL SCUaE;( ID, * VM{ID)/HH(rD>, HM)>(XMAX-XMIN)/H{ID) I Dim slova u VIS - 1.5*S*(YMAX-YMIH)/V CALL SCÄLE(-ID> l Promena granice odsec. DX - (XMAX - XMIN) / NSGG 00 K - -inc.NX I K - Parametar krive CALL LINE( XMIN, F(XMIH,K), 11) DO IX ° l,N3Bß I Petlja za crta- X - XMIN + DX*IX I nje jedne krive CALL LINE( X, r(X,K), 21 ) END DO END DO CALL LINE ( XMIN, YMIM, 11 ) t Povratak Q® DO I na granicu STOP OID aktivne površine na kraju rada (2) PLOTS progra«! vràe automatsko laplslvanje odgovarajućih vrednosti koordinata uz ose. (3) Kada ae Interaktivno korlsnitki prostor prikazuje na crtatu. odabere pogodan onda se slika Ovakav rad je omogućen ćlnjenlcom da PLOTS automatski odseca đelove familije krivih van aktivne povràlne 1 automatski postavlja koordinatni sistem na odgovarajuće mesto na aktivnoj povrSinl. Prikazani progran je pisan tako da sluil kao paradigma primene PLOTS al3te»a. Može se univerzalno koristiti za prikazivanje familija krivih 1 atoga koristi niz parametara definlsanlh u DATA specifikacijama. HodlfIkadjom ovih parametara program se moie lako prilagoditi drugim prlmenana. I pored jednostavnosti (samo tridesetak instrukcija) ovaj program prikazuje koordinatni sistem, koordlnatnu mrežu, kotiranje x i y oaa, ispisivanje naslova alike, crtanje niza krivih i podeàavanje proizvoljne veličine crteia uz simultani interaktivni rad na dva grafička uredjaja 1 efekte zumlranja. Ovakvim programom ae omogućava svestrana analiza osobina familija krivih i njihov kvalitetan grafički prikaz. U poredjenju sa univerzalnim grafićklm sistemima navedeni PLOTS program je znatno kompaktniji i lakSl «a korlićenje, PLOTS sistem se moie uspeäno koristiti i u slućaju programa za realizaciju slotenijIh linijskih crteža. Jedan takav primer primane PLOTS sistema llustruje slika 5. Pr i mer f ami1 i je parabola Slika 5. Pr i/^er f am i 1 i .je parabo La .0 -7.0 -6.0 -6.0 -1.0 -'5.0 -z. p Slika. 4. 0.0 1.D i.D REfEBEDCE C13 IBM, "IBM 1627 Plotter', (GA26-5710>. C2] IBM, "IBM 1130/1Q00 Plotter Subroutines", (GCZ6-3755t. C33 Nevroan, W,M, and R.F. Sproull, "Principles of Interactive Computer Graphics". Second £;đltion, McGraw-Hill, 1981. t4] Foley, J.D. and A. Van Dam, "Fundamentals of Interactive Computer Graphics". Add!son-Hesley, 1983. C5J ACM 3IGGRAPH Committee, "Status Report of the Graphics Standards Committee*, Computer Graphics 13(3), August 1979. C63 Hopgood, F.R.A., D.A. Duce, J.R. Gallop, and D,C Sutcllffe, "Introduction to the Graphical Kernel System (GKS)". Academic Press, 1983. C73 Enderle. G., K. Kanay, and G. Pfaff, "Computer Graphics ProgrojiBlng / GKS - The Graphics Standard". Springer-Verlag 1984. PROCESOR S PODATKOVNO PRETOKOVNO ARHITEKTURO Institut Jožef Stefan, Ljubljana UDK: 681.3.02 Jurij Šile, Borut Robič Članek predstavlja prvi procesor « podatkovno pretokovno «rhitekturo. Notranja kroina pipeline organizacija, ki tenelji na podatkavnea vodenju, daje procesorju veliko «oB. öogat nabor ukazov je prirejen tako, da je procesor zelo uporaben za hitro obdelavo slikovnih in govornih signalov. Potreba po takSnih obdelavah se pojavlja v raäunalnikih pete generacije. Data flou Architecture Based Processor - A neu data flou architecture based processor described. The processor employs token based data flow and pipelined architecture to achieve a very high throughput rate in the reals of digital image and speech processing. 1. UVOD Pri načrtovanju «isteaov z« obdelavo slik smo obiCaJno prisiljeni poiskati komproiiiis Hd hitrostjo in fleksibilnostjo slstena. Okornost in počasnost sisteaa, ki ga sestavljata ainlra-fiunalnih tu obdelava slike in nasovni poanllnik za njeno shranjevanje, sta neepreJe«lJivl za delo v realneo Času. I dodatkoa posebne aateri-alna opreee se hitrost obdelave povefii, toda Zal na raBun neksibllnosti, eaj vsaka sprensa-ba programske opreme narekuje spreaesbo «aterl-alns oprema. Oacnjsnl razkorak med hltroctjo In (lekaibilno^tjo sistema Je ooC omiliti z uporabo prograoabilnega slikovnega procesorja, ki se odlikuje s podatkovno vodeno arhitekturo. 1. POOATKQWO PSETOKOVMl PROCESOB V nasprotju s von Neumannovimi procMorJi, ki delujćjo na podlagi dostave ukazov, t«a«ljl cfelo podftko'.no pretokovnega procasorja na zbi-rsnju in obdeiavi paketov (tokensJ. 7.^. ^^novn^ propp^prU Podatkovno pretokovni procesor ne rabi dostave ukaza. Namesto tega vsebuje grafni pomnilnik (tabeli povezav in toCk)« v katerega kb pred priCetkom izvrševanja vpifie prograacki podiral. Pretok podatkov se vrlii s pa«a72S1 Priner podatkovno pretokovnega procesorja ja NEC )iPD72ai, katerega »ofi teaeljl na krotno 'organizirani pipeline arhitekturi ter bogate« naboru ukazov. )iPD7281 J« prvi VLSI fiipi ki deluje po nadellh podatkovno pretokovn« arhitekture t33. Ta ooogofla vafijo učinkovitost prace-eorja v nnoglh veSprooesorsklh aplikaoijaht kot sta procesiranje slik ter razpoznavanje vzorcev na podroäju unetne Inteligence, kjer se uporabljajo algoritmi za dvodoaenzionalno konvoluol-Jo, poveeavo, poeanjftavo In rotacijo. Njegova učinkovitost postane oCltna predvsen pri procesiranju slik v realnea Času, kjer dodobra Izko-rlStfa vsebovane vzporednosti uporabljenih «Igo-ritaov. PPD72S1 ni uporaben le pri procesiranju slik, tenveO tudi pri zahtevnih nuaerlBnlh izraCunih, kot eo natritlno eatrltino anoZenJe, oatrläno vektorsko nnolenje, aritaetika s pla-vajodo vejico ter izraCuni transcendentnih funkcij v realne« Času. 3.1. Pipeline oroanizacHa orocesor.la Kot Je prikazano n« Sliki k sestavlja procesor deset funkcionalnih «noti vhodni krallnlk CIO, izhodni krallnik COC), tabela povazav (LT), tabela toSk (FT), paketni poanllnlk (OH), vrsta (9), prooesna enota CPU), Izhodna vrsta COQ>, generator naslovov in krallnik pretoka CA6tFC) ter oaveüevalnl krallnik (AC>. . ICi vhodni krmilnik (Input Controller) 0C( izhodni krmilnik (Output Controller) LT: tabela povezav (Link Table) FTi tabela toBk (Function Table) Dni paketni pomnilnik (Data Memory) (J: vrsta (Oueue) PU; procesna enota (Processing Unit) OQ: vihodna vrsta (Output Queue) AGiFCs generator naslovov (Address Senerator) In krmilnik pretoka (Flow Controller) RC: osveSevalni krmilnih (Refresh Controller) Slika 3! Podatkovno pretokovni gral za E = 'š<> v OC. Pakete taksnih oblik i«enuJeso PASS paketi. Be ps se naslova ujeaata, se tIN polje izloCi in tako spremenjen paket poSlje v LT. IC hkrati ugotavlja, Ce je v procesorju prostor za novi paket In ga po potrebi zadt-Zi. OC poSilja 32 bitne Izhodne paket«, katerih oblika je enaka vhodnia paketon (Slika S). Izhodni paketi so bodisi podatkovni paketi iz 09, statusni paketi, ki jih generira OC v priaeru napak, dump paketi ali tuji vhodni paketi, dobljeni iz IC, ki se tu imenujejo PASSD paketi. Tuj na vhodu tvh. paket PASS): 1 hH' 1 a 1 Ib rCTULIl podatki 1 Tu u paket na izhodu (izh. paket PASSD): 1 M«' ! a 1 10 ICTRLM podatki 1 Opomba: MN' se ne ujema z mn danega procesorja. 3.2.1. NaCini delovanja: Procesor lahko deluje v treh nafiinihi nor-• alneta (Noriial) , testnem (Test) in prekinitve-nea (Break) nad inu. Po hardverske« rešetu Je procesor v nortialne« nadinu delovanja. V tea naCinu poteka vpie, branje in izvrševanje pod-grafa, V testnea naCinu delovanja je oaogofieno testiranje izvrSevanJa. Procesor preide v testni naCin, ko sprejme vhodni paket SETBRK, Ce med delovanjem pride do nasiCenja vrste DO «li GS, preide procesor v prekinitveno delovanje, opisana i vhodnim paketom SEThO. V prehlnitveni naCin lahko preide procesor tudi iz testnega näfiina, tako da dobi paket CBRK. V prekinitvnem nadinu delovanja je amogoCeno dunpanje. Iz obeh nadinov se vrne v normalni naöin po sprejetju vhodnega paketa CRESET, Prehod iliTT v testni naCin (vh. paket BETflBK); TTT ID I011QII H(1) CountdS) Opoaba: n=1 prekini izvrševanje po Count ciklih prekini po Count dostopih do LT lokacije, naslovljene z 10 Prehod v prekinitveni naCin (vh. paket CSRK)! lOODOlO! ' ~roiöon' — Vrsta prekinitvenega natiina (vh. paket SETHD) t |- HtJ lOr- ---lOlflTTT par.'"ia prefc.' n'ittlöl Opomba: Parametri za prekinitveni naCin dolofia-jo stopnjo vhodnih omejitev ter njihova trajanje. Sporočilo o napaki (izh. paket ERR):_ IGQDaiOl aODaOQO IQIODIlWN(A)M0DE(4)0D0ST(S)l Programski reset (vh. paket CRESET): I W IP' IDi&on □ Opomba: Programski reset povzrotii le nadaljevanje izvrševanja v normalnem natfinu, za razliko od hardverskega, ki resetira tabele ter' dodeli naslove procesorjem. ì'mm Vni'adrT v LT nipoìl podatki za v LT i Vpis toBke v FTB (vh. paket SETFTR): I KN iPI adr. v FT ntOllI podatki za v FTR > Vpis todke v FTL (vh. paket SETFTL):__ I HN 101 adr. v FT I HIPI I Dodatki za v FTL I Vpis toUke v FTT (vh. paket SETFTT);_ I" Hn 101 adr. v Ft m111ii podatki za v ftt i 3.2.3. Izpis podgrala: Vsebino LT in FT lahko bereao s poaoejo paketov RDLT, RDFTR, RĐFTL in RĐFTT, ki poaenljD zahtevo po branju. Prebrana vsebina lokacij v LT in FT pa se nahaja v izhodnih paketih LTflDD, FTRRDD, FTLROO ìn FTTRDO. 1 hn idi adr. v'lY HÜbDIl 1 Prebrani podatki iz lt (izh. paket ltrdd)> lOOOOtOl adr. v lt MOOdI1 podatki it lt 1 lahtEva za branje iz FTR (vh. paket RDFTB)I 1 UN 10 1 adr. v FT 1100111 1 Prebrani podatki iz FTR (izh. paket FTRRDD)t 10000101 adr. v FT MODIII podatki il FTR 1 Zahteva za branje Iz ftl dobioot DUnPCSl duiipani podatki 000 x SQ 011 «(3) u 1D<7) K C S C S .100 FTL8 X 60 bitni dinaaiCni RAM, ki sluZi kot FIFO pomnilnik. Paketi, ki vstopajo v S, nastanejo iz DM paketa tako, da se DMA polje izlotji in nadomesti z vsebino lokacije DM na katero j« prej kazalo polje DMA (prvi operand). G zadasno hrani pakete, naaenjene v PU ali 09. a je razdeljen v dva FIFO ponnilnikas 32 X 60 bitno podatkovno vrsto in 16 X 60 bitno generatcrsko vrsto (GS). DQ je naaenjen ukazoa tipa PU, OUT in AG/FC in hrani pakete, ki so namenjeni v PU ali 09, Vrsta 6G pa je naaenjena le ukazom tipa GE, ki generirajo nove pakete. Vrsta DO zadrifujs izhodne pakete, tie je izhodna vrsta oa polna. Podobno DQ zadrluje pakete, namenjene v PU, Ce je le-ta zasedena. NskritiSno pošiljanje paketov v krofni obtok bi lahko privedlo do nasiOenJa vrste O, zato je delovanja « omejeno s slededo zahtevo) tie se v DS nahaja osem ali ved paketov, Je branje iz Gfl oneaogo-Ceno, Ce pa Je v DQ aanj kot osaa paketov, iaa branje iz 60 vitljo prioriteta od branja ii Dtt. Dc nasitienja vrste S bi lahko privilo 8« v primeru, ko bi bila hitrost procesiranja aanjit« od hitrosti prihajanja novih vhodnih paketov v procesor. Zato v priaeru, ko «e v 0Q nahaja veO kot 23 paketov, prooasor preide v prekinitvam naCin delovanja, s «iaer se Izogne nasičenju S. 78 3.8. jihqdn^ yr^ta Q^. 08 je B * 32 bilni statiäni RA«, organiii-ran kot FIFO pomnilnik. Sluüi laäasneoiu shranjevanju ishođnih paketov, prispelih iz 08, ki se nato preko OC pošljejo na izhodno podatkovno vodilo. Ce je 0Q poln, pošlje ustrezen signal v ĐS, ter preneha sprejenatl pakete. OS paket se ujena s Q paketom. 3.9, Procesna enota PU PU izvršuje ukaze tipa PU in GE. Koda PU ukaia se nahaja v polju FTL PU paketa. Ukaii tipa GE se uporabljajo za generiranje novih pa-ki^tov, kopiranje posameznih ali skupin paketov in spreminjanja vsebine CTLF polja, de potrebuje PU ja izvršitev ukaza ved kot en cikej , podije signal vrsti O in IC, ki ladrJfi njuno delovanje, PU paket je po obliki enak 9 paketu. 3.10. Osveievalni črnilnik RC RC avtomatično generira pakete za osve2eva-nje vseh dinaniBnih RAHov v procesorju. Paket, ki ga generira RC, vstopi v IC, ter nato po vrsti Se v LT, FT, DK in 9 in vsakokrat poviro-ÜL osvežitev ustreznega RAMa. Po prihodu v fi gb osveiitveni paket uniCi. 3,11. Nabor ukazov Kot smo omenili v poglavju 3.4. obstajajo Štirje tipi ukazovs AS/FC, PU, QE in OUT. 3,11.1. Ukazi tipa AG/FC: Tip AG/FC vsebuje 16 ukazov, ki jih razde-liiiù v tri skupine: AG, FC in A6/FC tip. Ukazi tipa AS so: RDCYCS, RDCYCL, MRCYCS, MRCYCL, RDUR in RDIDX. Ukazi tipa FC so: PICKUP, COUNT, CUT, DIVCYC, OIV, DIST, CONVO, SAVE in CNT6E. Oka? tiUEUE pa je tipa AG/FC. Ukazi tipa AG/FC so opisani v FTR polju tabele FT, kjer zgornji Štirje biti predstavljajo operacijsko kodo. Ostali del polja FTR in polje FTT pa vsebujejo ostale parametre AS/FC ukazov. Poipeni ukazov tipa AG/FC so; - SUEUEi shrani prvi prispeli operand dvonest-nega ukaza v Dh. - RDCYC5: ciktiäno branje podatkov iz izbranega podroäja v OM, kjer je največja dolüina pod-roCja li lokacij. - ROCYCL: enako kot RDCVCS, le da Je najvsöja doäXina podroöja 256 lokacij. - URCYC5; ciVIiäno vpisovanje podatkov v izbra" no podredje v OH, kjer je najveäja doltin« podroSja 16 lokacij. - URCYCL: enako kot HRCYCS, le da j« naJveCja doJiiina podredja 256 lokacij. - RDUR: branje ali vpisovanje v DH. Z bitoo FTRC izbiraoo bodisi branje ali vpis. - RD10X: branje iz DM. - PICKUP: izloCi vsak n-ti paket in nu priredi 10 + 1, - COUNT: podvoji vsak n-ti paket in »u priredi ID + 1 . - DIVCYCì na vsakih n paketov izlodi prvih « aed njimi in jim priredi ID + 1. - DIV: po vsaken prihodu, paketa s FTRC » 1 se naslednjim n paketom 10 ne spremeni, ostelia pa se priredi 10+1 (paket s FTRC » 1 se uniCi). - OIST; zaporedje vhodnih paketov vsebuje pakete s FTRC O ali 1. Po prihodu J-tega paketa s FTRC = 1 se vsea nadaljni» paketen, ki i»*~ jo FTRC = 0 in naslednjemu paketu s FTRC » 1, priredi 10 + (j MOD k). - SAVE: uporablja se pri nastavljanju ID polj«. - CUT; po vsakem prihodu paketa s FTRC « 1 se se ta paket skupaj z naslednjini n paketi uniäi, ostali pa ostanejo nespremenjeni. - CONVOi uporablja se za komulativno raCunanje, npr. vsot in produktov. - CNTGE: uporablja se pri generiranju vefi kot 16 kopij danega paketa (skupaj z ukazom COPYBK tipa GE, ki je Opisan Spodaj). Konstante k, m in n so podane v FTT polju. 3.11.2. Ukazi tipa PU: Ukazi tipa PU so shranjeni v FTL polju tabele FT. Uporabnih Je le 12 spodnjih bitov, med katerimi so biti O do 4 operacijska kod« ukaza, preostali biti pa «e uporabljajo la dodatno intarmaci jo o Številu opsrandov (eden ali dva), legi operandov pri nekoautttlvnih operacijah, Številu rezultatov (eden ali dva) ter tipu primerjave, podanim z biti PNZ (EB, LT, LE, GT, 6E in NEI. Ukazi tipa PU soi - Logični: OR, AND, EXOR, AKDNOT in KOT. - Aritmetični! ADD, SUB, HUL, INC, DEC, NOR in ADOSC, 8UBSC, nULSC ter NOPSC. Ufcazl *SC najprej izračunajo operacijo • in vrnejo lego skrajnega levega setiranega bita. - Premlkalnii SHL in SHB ter SHLBfiV in SHRBRV, t11) rik.i) J_t QUEUE MUL b(l) J_ QUEUE u " 0)iCk) + du(k) , kjer so A, b, c in d usrezne «atrike in vektorji. Prograoi bi se v priaeru, ko «o aatrike In vektorji enodiaenzionalni, glasili EQUATE HOST = Q, MODULE PROCI " li INPUT PI, P2 ;,P3,P*,PS,P6; OUTPUT P13 LINK P7 S T1 CP1 , P2) t LINK pa a T2 CP3, P*) ì LINK P9 ■ i T3 (P4, Pbi 1 LINK P11 s ■ TS (PT, P8) ! LIKK P12 ' = i T6 tP?, PIO) 1 LINK P13 1 — i T7 in desni Clzraüun y(k)) del grafa izvršujeta vzparednc, iato levi dol prirediBo procesorju PROCI, decni del pa procesorju PR0C2. Ustrezna prograaa, ki sta v tet priaeru zelo podobna, sta podana na Sliki 13. Razlika med njiaa Je le v ten, da PROCI pošilja rezultat procesorju PR0C2, nedte« ko procesor PflOC2 poSlIja rezultat glavneau procesorju HOST. 80 EGUATE nODULE INPUT OUTPUT LINK LINK LINK LINK FUNCTION FUNCTION FUNCTION FUNCTION HEMORY MEMORY MEMORY PR0C2 = 2j PR0C1 = 1j P1,P2,P3,P<,i P13i P7 = T1 (P1, P2) ; P8 = T2 (P3, P4)i P11 = TS (P7, PS)) P13 = T7 (P11, )j T1 = MUL,QUEUe(Q1,1)) T2 = MUL,aOEUE(Q2,1)J T5 = ADD,SUEUE(QS,1) | T7 = OUTn tPR0C2,0)i tì1 = AREAd) j 62 = AflEAtl)J as = AREAd); E8UATE HOST - 0( MODULE PR0C2 = 2| INPUT P2,P4,PS,PÒ| OUTPUT PUj LINK P9 - T3 CP2, PS)) LINK PIO - T4 1 FUNCTION T3 1 nUL,aUEUE(Q3,1)t FUNCTION T4 ■ «UL,8UEUE AREAd) ! Sllha 13: Realizacija digitalnega filtra v prostoru stanj. Pri veČini prograaskih grafov Je daloCanje viporedno izvršljivih podgrafov zahtevno, kar nirekuje razvoj netod za avtoaatiCno iskanje vzporednosti ter optimizacijo glede na Stavilo uporabljenih procesorjev CA]. Zelo dobrodoSel bi bil grafiCni zbirnik za generiranje kode neposredna iz progra(n5kega grafa ter pascalski ali C prevajalnik generiranje in optinizaci-jo prograaskih grafov. je v vsen procesorjih cel prograoski 9t»l, v»nj pa vstopajo le podatki o prlpadajotii podsliki. Razbitje glede na graf V splo~ Bneni se Cas obdelave eksponentno zaanjftuje z veCanJe« Števila uporabljenih procesorjev, lal pa rte neoneJeno, saj se pri vet!jen Številu procesorjev pojavijo zastoji pri pretoku vhodno-iihodnih paketov med pracesorji, lato je odvisna od sane aplikacije, ali Jo bomo razbili glede na podatke ali na programski graf. Vieaiao npr. obdelava sliket ki obsega naloge kot so premik, noralranje, rotacija itd, de se odlafii-mo za razbitje glede na podatke, razbijemo slika na padslike, tako da se vsaka podslika istočasno obdala v svoje« procesorju. Te poaeni, da 5. LITERATURA tl13 Chang V.H. i Data Flou Chip Optinlia« laage PrnceBSing, Coaauter Design. Oct. 15, 198*, pp.97-103 1:23 Jetfery T,: The pP072ai Processor, November 19as, pp.237-246 mil £31 PPĐ72S1 laage Pipelined Processor, NEC Electronics, February 1985 Robi« D., J.Siici On Choosing a Plan lor the Execution of Oata Flou Progra« 6raph, Informatica l/6b es: Ohba N., T.Saito, Y.Hoshiko: Signal Processing on a Data-Flow Processor, Micpooroeas-"^cropFJaFaHHÄM. U,1964, pp.17-27 TRANSPUTER - OSNOVNI GRADNIK VEČPROCESORSKIH SISTEMOV U DK: 681.3-181.4 Branko Mihollovič, Slavko Mavrič, Peter Kolbezen Institut »Jožef Stefan«, Ljubljana Tr^neputer je osnavni VLSI matèriaìni gradnik vefiprocesarskih sistemov, ki za povezovanje i ostalimi transputer ji v sistenu koristi "point-to-point" komunikacijske povezave. Jezik OCCAM je osnovni programski gradnik veötr ansputerskega sisteoia (VTS) . 5 tam jezikan opiSeito VTS kot 2bir procesov, hi se izvajajo soCasno in ned seboj komunicirajo na nivoju sporočil preko definiranih kamunikacijshih kanatov. TRÄNSPUTER-THE BASIC COKPONENT OF MULTIPROCESSOR SYSTEMS - The Transputer is a basic VLSI hardware component of multlproceasor eyetens with coiDunication links for point-to-point connection to other transputers. Occam is a language that enable a multiprocessor system to be described as » collection of processes that operate concurrently and QOtnnunicate using ■essag«s passing via named channels. 1. Uvod Danes Je popolnooa jasno, da tudi ekonomsifih preprek ni ved, ki bi zavirale gradnja "modnih" računalniških sistemov; in sicer takSnih, ki v sebi zdruSujeja naprimer 1Q00 sottasno dalujoCih procesorjev. TakSen rafiunalnik je preprosta "prilagojen" aplikaciji v smislu popolne iikoriSüenosti inherentnih soäasnoBti, Takäno gledanje je vodilo tudi strokovnjake firme INMOS pri načrtovanju transputerja. tìemu so transputerji in tudi njim podobne koaiponente namenjene? - Namenjene so naSrtovanju standardnih raöunal-nifikih produktov v SBislu laJfjega programifa-nja in uporabe le-teh, - pridobivanju kar najveCje učinkovitosti s tesi komponentaiai zgrajenih sistemov, koriSCenju tehnologiji druJin, novih razvojnih smeri v VLSI in sicer znotraj kompatibilnih - načrtovanju takSnih pragramabiSnih kampanent a pomofijo katerih bi gradili sistene e velikim Številom sodasno delujoBlh računalniških sistemov. Transputer, ki je zaSBiteno ime za mikraraCu-nalnik ( mikroprocesor), je po velikosti In funkcijah primerljiv z mikroprocesorji kot sta NS 1ÌQ32 ali I 80286, vendar je pri njem uporabljena povseo drugačna teoretska osnova pri načrtovanju velikih radunalnifikih sistemov. Transputer je zgrajen tako, da Je lahko povezan z ostalimi transputerji v takaimenovani ■reüi paralelnih procesov,Vsak od transputerjev iivaja toCno doloCeno opravilo (proces) z minimalno izguba procesnega Casa in minimalnim balastom, ki se tanko pojavi v fiziCni povezavi ned transputerJi> Pri raCunalnikih, ki potrebujejo velike podatkovne baze, ki so programirani v naravnih jezikih in onogoCaJo tudi druge "inteligentne" aktivnosti, predstavlja soCasno procesiranje eno od bistvenih lastnosti takfinih raduna 1nlkov. Ge Selimo to dosetìl z «ledsebojnim povezovanjem konvencionalnih procesorjev, naletimo na praktično nerešljive probleme varnega dodeljevanja virov, sinhronizacije pri takoimenovanih paralelnih vodilih in podobno. V transputerski arhitekturi koristimo visoko stopnjo soCasneg« izvajanja procesov. Ta je zagotovljena preko takolnenovdnaga decentraliziranega ra&unalnlSkega modela. Lokalni procesi se izvajajo nad lokalnimi podatki, med seboj pa takSni procesi koBunlclraJo preko hitrih komunikaciJskih kanalov z Izmenjava sporoöil. Tako Izbran naCln lokalnega procesiranja in komuniciranja narekuje temeljite spremembe v konceptu programiranja in natJrtovanJu novih algoritmov. SoCasno z razvojem transputerja, je potekal razvoj na majhnem (22 rezerviranih besedJ, Iztirane« jeziku, Imenovanem OCCAM. Namenjen Je programiranju transputerjev, odnosno je njihov zbirni jezik. Osnovna lastnost (in prednost) tega jezika je ta, da je ' ustvarjen zà programiranje soCasnih aktivnosti v veCtransputerskem sistemu; to je za uClnkovito Implementacijo transputerskega sistema. 2. Z g d d b a s i. s t @ m đ Na tem Zgradba mestu Je potrebna povdaritl naslednje; tako samega transputerjđ kot tr«nsputerskega sistetna Je deClnicana z OCCAM-o«. S tem, d« smo arhitekturo definirali na tem nivoju pomeni, da lahko na eni strani transputar&ki sistem zgradioa : razliüniai, danes Za standardnimi hoiiponentaffli i na drugi strani pa lahko tak sistem optiiniziramo za railiCne aplikacije. Glavna sestavna dala transputerja sta 12 bitni RISC Creduced instruction set computer) in zelo hiter RAH pomnilnik UK besed). Cip Je narejen v 2. slkronski CMOS tehnologiji. SHHi. ura «u oiogocaida izvrSi 10 milionov instrukcij na sekundo, kar zdaleä presega zmolfnosti današnjih nikrorafiunaìnikov, Blok shemo transputerja prikazuje slika 1. Transputerji standardne Von-Neuinannove strukture se povezujejo med seboj s poraoBJo etirih komunikaoijskih povezav in tako tvorijo siiten, katerega lahko pogledamo z dveh strani. Prvi, logiCni pogled naa pove, kako je sistem Ded seboj povezanih transputerjev naCrtovan in prograairan, Orugi pogled, iiiienovan (iiiCni, na* pove, kako so VLSI komponente aed seboj povezane in krmiljene. m n a £ 1 " m l IF ALTatnalO* P) P1 pogoji Vtlodl P2 P2 Pi PI P3 1 1 1 1 1 1 peeoj a pz 1 I Vhodi PS I i) h) 0 SLIKA z Izvrtev«nje vsdkega naslednjega procesa se zaCne takrat) ko je predhodni kon&an. V prineru paralelnega konstrukta ( slika 2b) se vsi procesi izvajaja soBasno, konstrukt pa se zaključi takrat, ko so konCani vsi procesi. Veljavnost pogoja 1 je pogoj "za izvrševanje procesa PI (slika 2o). V primeru na sliki 2d pa ba proces P1 laCel z izvrševanjem takrat, ko se bo izvrSit vhodni proces 1. Tako kot v sekventinih jezikih, poznano tudi tu tipe, deklariranje, polja, posebnost pa predstavlja takoinenavanc oblikovanje occanskega programa. V occaou zapisan program se lahko izvaja na enen ali veC transputerjih, lato nora biti ustrezna temu pravilno oblikovan. Razvojni sisten namreS umogaCa, da se program, ki se bu izvajal na vetiih transputer jih, tudi pravilno "porazdeli" mednje. Oblikovanje programa C oonfLguration oi occan progran > ne upliva na logiäno zasnovo programa. Ì konstruktom PLACED PAR se nanreC zagotovi, da sa bo vsak proces, podan v paralelne« konstruktu, lahko izvajal na svojem transputer ju. OCCAU REGISTRI USTA PROCESOV program naslova pounilniSke besede ter kazalca zloga znotraj pomnilni&ke besede. Posebni instrukciji C load local painter, word subscript ) podrobnejše opisujeta strukturo poanilniSke besede. Procesor je organiziran tako, da koristi pri izvajanju sekvenCnih procesov Sest registrov. S poBoCjo treh registrov lahko oblikuje skladi' shranjuje operande, odnosno paranetre klicanih podprogramov. Eden od registrov je namenjen shranjevanju kazalca na vsebino delovnega poanilnika, drugi pa hrani kazalec naslednje instrukcije, ki se bo izvrSila. IzhodiSCe za procesorsko nultipleksiranje, odnosno dodeljevanje procesorskega Saea Je podano v nultiprograaskea jedru. Aktiven proces 0aka na izvršitev poteo, ko je uvrSöen na listo aktivnih procesov (slika 3). Dodeljevanje procesorskega öasa ned procese Je v nultiprogranskere jadru definirana z doloEeno prioriteto (fixed priority). Z accanskim konstruktom PRI PAR, tieaur sledi lista procesov, doloüimo prioriteto prccescn, £e se le-ti izvajajo na enea transputer ju.. Procesor pozna dva prioritetna nivoja. Procesi z niijo prioriteto se izvajajo sano Ce ni procesov z vi«jD prloritsto} njihovi krajci deli (opravila) pa se izvrSujeJo v periodično dodeljevanih Časovnih rezinah. Proces z vifjo prioriteto lahko prekine proces i niZjo prioriteto, vendar najveB za dollino ene tlasovne razine. Slika 3 SLIKA4 2.3. Transputer Procesor z naboros instrukcij je zasnovan taka, da omcgoBa» ~ učinkovito uporabo Jezika OCCAM, .posebno pri izvajanju veCjega števila procesov, ° . '.. i „. 3..,.1 * » ^ , ■ , , .0 PODATEK POTRDITEV - enostavno prevajanje programa, pri vsem tem pa ni potrebno definirati arhitekture na niZjea nivoju, - izvajanje prograsov na procesorjih z različnimi dot^inani besed, in sicer brez predhodnega dodatnega prevajanja, - lociranje programa in delovnega pomnilniSkega prostora kjerkoli v pomnilniku transputerja, .Na učinkovitost celotnega transputerskega Bitteaa pa vplivate vglavnen dva Činitelja: Število besed v celotne» programu in hitro izvajanje le-tega. Posebna skrb je pasvedena ravno drugeiu Èinitelju, saj se tako poenilniCke kot aritmetiCrto-logiđne operacije IzvrSijo v enem ali kvečjemu dveh ciklih. Procesor koristi za naslavljanje pomnitnifiklh lokacij linearni adresni prostor,pri tem pa ne razlikuje med notranjim delovnim pcnnilnikom in dodanim zunanji« pomnilnikom. Osnovni element linearnega adresnega prostora je kazalec, ki je sestavljen iz dveh delov; Vse instrukcije iaajo enak tormat iiBt.r.tJtJi..titi.gaflv■ Naredimo te kratek pregled možnih ekspertnih sistemov v okviru teleinformatikei - testiranje nove ciiroma popravljane programska opreme v PBX, - načrtovanje konfiguracij PBX oentral oiiro-aa privatnih onrellj na osnovi PBX oentral tretja ali četrte generacije t materialnega in programskega stalitča glede na potreba kupoa tar hkratna določitev arhitekture in celotnega designa tega sistema, - načrtovanja uporabnitko prijaznih vmesnikov v teh sistemih, - nadzor nad stanjem kablov v omrežju in odkrivanje ter sporočanje okvar, - diagnostioiranje izpadov napajanja v elektronskih PBX, - upravljanje z Informaoijami (inteligentne podatkovne baze), - vzdrževanja oprema, - razpoznava In interpretacija različnih signalizacij (pomembno pri motnjah, zakasnitvah , .., ), - razvrtčanje in dodeljevanja resursev za talekonferenoe, - diagnostiolranje izpadov satelitskega prenosa in delovanja, - zasledovanje in navigaoija satelitov, itd. Seveda zadnja dva primera la nas Žal te nista primerna. a. et aija Na kratko preglejmo CCITT priporočila, s poudarkom na serijah V, X, I in T. Serija v se ukvarja s podatkovnimi kcmunikaci-Jani preko telefonskega omrežja. Serija X se ukvarja z omrežji za prenos podatkov« - zmožnosti I - vmesniki) - prenos, signalizacija in preklapljanje( - vidiki omrežjai - vzdrževanje! - ost (odprti sistemi povezovanja)i - medsebojno sodelovanje) - HHS (sistemi za prenos in obdelavo sporočil). Sarija I vsebuje prlparaAlla la ISDMi l.tOOt splQini pregled Cokvirna igndba i.n terninologlja) opis ISDN; aplofina ne' tode obllkovanjat =»eri razvoja)( 1.200: znatnostl storitev (vidiki storitev-t prenasne storitve; teleatoritve); 1.3Q0t spioSni vidiki in funkcije oarežja Cfunkcianalni principi ararsijai refe-renÈni modeli (protokoli in funkcionalna arhitektura modela, hipotetične referenčne povezave); principi oštevilčenja, naslavljanja in usaerjanjai tipi povezav; zahtevana lastnosti (povezovanje s ponoAjo tokokrogavnega ali paketnaga preklapljanja); l.'iOD: vnesniki nad uporahniko» in otnrežjaa (sploSni vidiki vmesnikov med uporabnikom in omreljem (referenčne konfiguracije, struktura kanalov in imoinosti dostopa)} aplikacije vmesnikov med u-porabnikoo in omretJen| priporočila nivoja 1 ivmaaniki za bazično in za primarno hitrost)) priporočila nivoja 2 (LAPO); priporočila nivoja 3) nut-tiplBksiranjo , priVagajanja hitrosti, podpora obstoječih priporočil (X.21, X.21 bis, *.25, serija V. S6K bps)); 1.SQ0: vnesniki med centralami v omreijui I.&ODi principi vzdrlavanja Cprinoipi na uporabnika nanašajočega se testiranja in vzdrievanja) . Serija T se ukvarja e terminali la izvajanje telematskih storitev. Omenimo ie standarnizacijo računalniških mrež (LAN). Majbolj odmevna s tega področja je serija standardov IEEE a02, ki se ukvarjajo predvsem z načinom dostopa do prenosnega medija i - a02.1 tehnična rdeča niti odnos med stan- dardi in ISO OSI referenčnim modelom - KQ2.2 logični nadzor linijet ULC-1 - brezpovezavni LLC-2 - povezavno usmerjeni - 802.3 vodilo z dostopom CSHA/CD (Ethernet) - aa2.^ vodilo z letonom - 802.5 obroč z letonom - Ba2.& mestna omrelja V Evropi Je (vsaj v univerzitetnih krogih) precej priljubljena lokalna računalnitka mreta Cambridge Ring. Standardizirana je v okviru ISO z dokumentom OP 8802.6 (alotted ring>. Pričakovana standardiiaoi ta v »vetu irt y Juatt.-alavi iii v svetu se standardi izredno hitro razvijajo (dopolnjevanje standardov zrn ISOM, standardi z* eirokopasavni I6DH, za pisarniška avtomatizacijo in te za mnogo drugih področij),' pri nas pa se na področju standardizacije podatkovnih omretij ne dogaja skoraj nič. Eden od prvih korakov pri nas v tej smeri bo verjetno standardizacija postopkov, uporabljenih v Jupaku (](.25, itd.). Vsaj za upočasnitev zaostajanja na tem področju je treba dele takoj zelo intenzivirati. 7. Literatura International Teleoomnuniaation Union, CCITT, Red Book, Vili th Plenary Assembly, 1984 (Geneva 19BS) Serija standardov ANSI/IEEE B02.n (Standard for Local Area Network»), n = 1, 2,..., 6 ISO standardi 1 DP 8802.6 - Slatted Hing 015 7498 --Open Systems Interoonneotion Datapro Reports on Data Communications, Datapro Researoh Corporation, Delran, NJ (monthly updated) IEEE Spectrum, Special issuei Teleoommunicati-ons. Volume 22, november 1985 M. J. Bevani Image Processing May Causa Future Problems with Hetwork Loading, Data Communications, march 1986 R. C. Hawki The Integrated Vciae/Data Option, Conferenoe Transcript of "Vcioa/Oata Integration Conference", Oye* Saientifio and Technical Servioes, London, dmommber 1983 P. Kahli A Review of CCITT Standardization to Djte, IEEE Journal on Seleotad Area In Canu-nications, may 1966, Vol. 8AC-V, Ho.3 U. Karavatcsi The Fourth Generation of PABXs. Conference Transcript of "3rd and tth Ganara-tion PABX* Ccnfarenoe", Oyai Saientifio and Technical Servioes, London, fabruary t9&S. W. B. Rauoh-Hlndini Upper Level Network Protocols, Electronic Design, march 1983 A. S. Tanenbaumi Computer Networks, Prentice Hall, Englawood Cliffs, HJ, 1981 90 ADVANCED MICROPROCESSORS AND HIGH-LEVEL LANGUAGE COMPUTER ARCHITECTURE Vtis o knjlql si najhltraja uttvariao > pragl«-doB kazala knjige, hi podaja polsg naslovov vcBh dlankov tudi strukturo knjiga In razdali-tev VBBbina v posanezna dala in poglavja. K Kn no tsn BO nan Knjiga z naslovoa ADVANCED HICROPROCESSORS AND HISH-LEVEL LANGUAGE COnPUTER ARCKITECTURE Je zbirka n«JponambnaJtlih Ölankov, poroSll in ekspertiz, ki Jih Ja zbral in uredil avtor Veljko nilutinović za potrebe paueavtnja prad-■et« z enakia naslovoa na Purdue University v ZDA. Knjiga Je uäbenik za Ktudente ter hkrati tudi dober priponsodek naCrtova 1 cen novih raCunalniil kih sisteaov in vodjan razvoja, ki potrebujejo znanje o sodobnih trendih v ratiuna In i Bk ih arhitekturah. Knjiga sestoji it 3? Olankov, ki so razdeljeni v 7 delov vn 14 poglavij ter ima skupna skoraj iiOO strani. Knjiga govori o arhitekturah, ki tanetjijo na visakaprogranskih Jezikih, to Je o HLL (High Levai Language) raäuna1 nitk Ih arhitekturah. Avtor deli HLL raCunalniVke arhitekture na dve osnovni skupini! - arhitekture z indirektnim izvajanjem ter - arhitekture z direktnim izvajanjem. Pri arhitekturah z indirektni« izvajanj«« Jb i« izvajanje programa potrebna izvorni kod prevesti v izvajalni kod. Pri arhitekturah z direktnim izvajanjem p« radunalnik lahko direktno izvaja izvorni kod. Kadaljs dali Milutinovi« arhitekture z indirak-tnim izvajanjem v dva podrazdradat - reducirana arhijtektura in - kompleksna arhitektur«. Kompleksna arhitekture se nadalje delijo v - Jezikovno vodene arhitektur« in - Jezikovno odvisne arhitektura. Jezikovna vodena arhitekture lahko delinirano kot arhitekture, kjer se prolijo konstrukcije strojnega jezika na rilativno visokem nivoju toda na na nivoju HLL sintaks«. Pri Jaiikovno odvisnih arhitekturah pa Inamo diraktno «nolia no odvisnost med HLL konstrukcijo in konstrukcijo strojnega Jezika. Ha koncu so razdeljena Jezikovno odvisn« arhitekture «e VI - arhitektura s programskimi prevajalniki ter - arhitekture s strojnimi prevajalniki. Slika 1 kala razdelitev HLL arhitektur. KIL AtchUKUira \ ludiiset FnftlMi OInct EiKiitlon AtcMUcUin ^ \ «ickluctin ^ \ LawwgiOliMttd X \ il«8«ftwin «satltnuInHarimn Slika i: Razdelitev HLL arhitektur. Tabla af Content* Praiace........................................ Aoknowledgeaants..............................v Part I — Introduotion Chapter liEssential Issues....................2 Directions and Issues in Architecture and Languages........3 n.J,Flynn Postpass Code Optimisation of Pipeline Constraints........................................246 J.L.HsnneGsey and T.R.Grass} Ridge 32 Architecture - A RISC Variation....2B6 E.easart and'D.Folger(Proceedings of ICCD'BS, Ootobec 1963,pages 31S-318> Reduced'1netruot ion-Set nulti-Microcoaputer System......................................290 L.FDti,Đ.En9liah,R.P.Hapkins,D.J.Kinninent, P.C,Treleaven,and H.L,Mang C Proceedings of the NCC.July 19S4,pages 69-75) Applying RISC Theory to a Large Computer...,297 R, Ragan-Ksl ley' and R. Clark (Conputer Design, Noveaber 1963) Part ilf — Language-Directed Architectures Chapter 7iStack hachines....................304 Stack ConputsrsiAn Introduction.............30S D.n.Bui nan(Computer,nay 1977,pages 18-28) Exploring a Stack Architecture..............315 R.P.BIakBCCoBpufcer.Hay 1977,pages 3D-39) Twenty Years of Burroughs High'Level Language Machines.............................. ..«.32S E.D.Earnest(Proceedings of the International Uorkahop on High-Level Language Conputer Architecture,June 1960,pages 64-71) leplications of Structured Prcgranning for Machine Architecture........................333 A.S.TanenbauiB se osredotoda na pro-bleae, ki so povezani s programsko inpleaenta-oijD aritmetike c plavajodo vejico za MIPS mikroprocesorje. Pel izbiri reduciransg* nabora ukazov se pojavlja vprašanje, kako Je tak reduciran nabor prinersn za aritmetiko plavajoče vejlG* in za aritmetiko na «ploh. Nabor ukazov za MIPS arhitekturo vsebuje ukaz, ki ustreza »noitenju po Booth algoritmu, kar js dalo relativna dobre performanse. ladnji eianak ,v petem poglavju <7 ^4-blL ioctl «adriii) Slika «I.I Zgradba R1MM8 mikroračunalnika z 2SS procesorji. Vsak mikroračunalnik Ima preprost prooesor in 256 zlogov lokalnega pomnilnika. T« »ikroprooasar ima skrajno reduciran nabor ukazov In je namenjen uporabi v nultimikropro-casorekem okolju. Zato bo posebno pozornost posvetili strojni paCunalnitkl podpori za med-prooesorsko komunlkaoijo. Vodilo sestoji iz 16 bitnega naslova, 16 bitnega podatka in dodatnih bitov za delo s pomnilnikom, kar omogoCa izvajanje NO-OP posega po pomnilniku. Slika 5 kaite organizacijo in kontrolo vodila ter pomnilnika za RIHMS mikroradunalnlk. Data Sua C aijìtbsb yr: [El CM H A Isoua] 0») CÜ i It 6 tilts 7iw« Fuoctloa Slika 6.1 ÌAPX 432 Kultipraoesorski «iste« in njegova parforaanee kot (unkoija «tevita procesorjev. Beyers v svojaa članku podaja notranjo organi-zaoijo prooasirja HP-F0CU3. HcEragor s sode-lavoi obravnava bistvane znaSllnosti notoroli-nega procesorja nC6aC20. Hateoaian opisuje glavne znaäilneatl proBeeorj« NS32032 proizvajalca National Sealoonduotor. Na koncu poglavja pa je Patel podal pregled Zilogovaga procesorja zea,000. Vel ti člankl so zgolj pregledni Olanhl. Deveto poglavje podaja nekaj zgodnjih poskusov na področju HLL arhitektur s prograashiai prevajalniki. To so arhitekture z naboroa strojnih ukazov, ki Je v enoUanl (edan proti eneau) zvezi z ukazi značilnega visokoprograBskega Jezika. Prevajanje Je izvrtano programsko. Pogosto te arhitekture iaenujeao jezikovno skladne arhitekture s prograaskia prevajanjea. Zanimanja za te arhitekture se Ja zadalo la leta 1760, ho se je pojavila potreba pa računalniku, la katerega bi bilo laüje pisati sistsnski in uporabni«kl kod. Slavni problaa tega pristopa pa je kcapleksnost aaterialne raCunalniVke opreme. To poglavje vsebuje 2 članka. Prvi, katerega avtor Je Hassit et al., opisuje enega prvih tovrstnih akeperiaentav pri IBM. Rezultat tega HksperUienta je bil računalnik, ki ja bil namenjen za jezik APL. To je bit pravzaprav računalnik IBM S/360 M/25, ki je bil mihropro- gr«BÌran in Je generlral APL kod. Osnovni r«ilog ZA ta razvoj Je bila Kelja razviti učinkovito •rhitakturno podporo za Jszika kot so APL ali SNOBOL. Ti Jeziki ponavadi potc-ebu-JeJo interpreter in konvancionalen priatap ina lahko za posledico znatno znanj«anje hitrosti izvajanja prograaa. arhitekturah uporablajno za prograniranje običajen visokaprogranehi Jellk. 8 predprooeilra-nje* izvornega koda se preveda izvorni prograe v DEL obliko, kar Je optimalni vmesnik med posameznim visokoprogramskie Jezikom in iiva-Jalnim raSunalnikom (Slika 7>. Nielsen predstavlja v drugam Slanku devetega poglavja glavne rezultate «tudije, katere oilj Ja bil naCrt radunalnifike arhitekture in programskega Jezika 2« vesoljska aplikacije. Oba Članka iz tega poglavja podajata rezultate eksperimenta. Radunalnika, ki sta pri tem nastala sta danes zastarsLai Dmenjeria pa sta v tej knjigi lato, ker sta s svojimi idejami in eksparimentalnimi rezultati vplivala na sodobna tokove pri zasnovi novih radunalnifikih arhitektur. Dosato poglavje opisuje nekatere sodobne raziskave na MIT. Vsebuje dva älankai ki se navezujeta na jezikovno skladna arhitekture. Te so tanLuive tako z gladilCa VLSI nafirtovanja veiij, kot tudi z gledititia nikr oprog rani ran Ja. VeČina računalnikov, ki tamelji na tem pristopu vsebuje nikroprogran za podpora konstrukoij visokoprogramskega jezika. Trenutno stanje razvoja VLSI lahko uäinkovito podpira velike ROK pomnilnike za aikroprogran na (iipu. Vemo pa, da Je VLSI tehnologija premalo moCna za podporo kompleksnih visokoprogranskih jezikov na popolni enolidni korespondenoi. Torej lahko z VLBI tehnologijo podpiramo bodisi samo izbrano pod-mnolico visokoprogramskega jezik» ali pa uporabimo tehnologijo, ki ni VLSI in podpiramo celotni visokoprogramski Jezik. Prvi älanek, katerega avtor je Sussman s sodelavci, opisuje zasnovo in implementacijo mikroračunalnika na enem vezju, ki direktno interpretira 5cheme-79, to Je dialekt Jezika Lisp. Skupina na NIT Je razvila interpreter v obliki mikrokoda, ki so ga realizirali v strojni raCunalnitki oprani. Pri tem so uporabili dodatne in nekonvencionalne hardverske pripomoü ke tar s tem poveCali uOinkavitost raöunalnika. Orugi Članek desetega poglavja, katerega avtor Je Batali at al., opisuje vezje Saheme-Bl, ki je naslednik vezja Scheme-79. Scehme-Bl Je namenjen za okolja, kjar so računalniki specializirani in kjer velike skupine računalnikov sodalujejo pri reševanju posamezne zahtevne naloge. V 11. poglavju je govora o dveh zanimivih eksperimentih. Prvi izhaja iz Šestdesetih lat in opisuje Symbol raöunalnittki sistem, to je računalnik, ki ima nekonvencionalno arhitekturo in o katerem je bilo v preteklosti veliko diskusij. Symbol Je računalnik, ki ima sptoten programski jezik in time-sharing operacijski sistem implementiran v materialni računalniški opremi. Vzpodbuda za tak eksperiment temelji na dejstvu, da so sčasoma postali prevajalniki zapleteni in Jih Je bilo teXko napisati. Po drugi strani je cena materialne raCunalnitke apreme padala, kompleksnost načrtovalnih orodij za razvoj vezij pa se Je boljtala. Drugi Članek enajstega poglavja (Burkle) predstavlja laboratorijski eksperiment, ki Je rezultira! v računalnik z imenom Abacus. Abacus ja nastal pod vplivom računalnika Symbol, ima pa vrsto originalnih novih reSitev kot na primer kontrolo poslov daje pregled raziskav s podraäja raüunalnikklh arhitektur v Evropi. Otaanjeni bo doseXki s podroä ja reducirnih arhltaktur z University of Kant, univerze v Bonnu in Gesellsohaft fur Nathaaatik und Datenverarbeitung, S podatkovno vodeniai arhitekturami se ukvarjajo n« University of Manchester, Kathlliake Universiteit Lauven in na univerzi v Dortmundu. I reduoiranimi arhitekturami as ukvarjajo na University of Beading. Jozikovno vodene arhitekture razvijajo no Tehnläni univerzi Berlin in na Univerzi Dortmund. HLL arhitekture razvijajo na univerzi Paul Sabatier v Toulouse tar na univerzah v Dortmundu, Frankfurta tar Kaiserslautern. Arhitekture za direktno izvajanje razvijajo na «vedskem in v Freno!ji, Bevada je centrov, kjer raziskujejo in razvijajo HLL radunalnilke arhitekture v Evropi «a nnogo veS, v tam Članku ja izbranih samo nekaj najbolj zanimivih. Na konou je prlloltan «a spisek evropskih revij in simpozijev > podroöja HLL rafiunalni« kih arhitektur. Slika S( Organizacija računalnika la direktno izvajanje. Pripravili S« Pisna bralcev Odgovor urednika! poitovani đr, Jalesnlkar O broju Vaàeg fiasaplsa "Informatica", ko- jeg lna£e sa aadavoljstvoa pratim 1 neoblEno cenln, objavili ste flanak autora Vilfana, Hah-nlča. 1 Mohorlfiai "Ocana programskih orođlj IDA'.. Iako znan da nije praksa VaSeg Sasopisa da prenosi polemike u vezi sa InformatiSkliD te-nana Ipak osjećam potrebu da na ovaj ilanak na nski način reagiram. Hi u Jađroagento u Rijeci korlatino IDA alate a posebno IDA-Baau od samih njihovih podataka tako da aao dosta detaljno upoinatl sa njiaa pa nas Jb posebno zanimalo Jedno,strujno mliljenjs pogotovo kada ono dolasi sa fakulteta aa elek-trorahnlku li Ljubljane i to ia Laboratorija sa programsku opremu kako su se autori potpisali. Idaja da sa uame u struäno rasoatranje Jedan programski praiavod Ja Izuaetno aanlDlJiva pogotovo kada sa radi o IDA-Baal prolavodom Iskra -Delte is Ljubljane aa koju noieno alobodno reći da Je prvi Jogos1avenskl sistem sa upravljanje basom podataka koji Ja naiao svoj put do triiéta. Joè 'i : MJvstv: ......... : DUBROVNIK/CAVTAT.; HOTEL CROATIA i Organizator: ...... .....: i ..j : . ■ 5VEUÖILISNI RAjCUNSKI C6NTAR, ZAOREBi -- i .....-i-- . 4 - I • INFORMATIKA 1 OBRAZOVANJE ! ' ! i i • R AĆUNAR3Kr SISTE M IT MRE ŽE, PSOB NA ACUN AUA "" I " j" -•■SOFTWARG-SKOINŽINJERSTVO, -i r ■ - INFORMACIJSKI.SISTEM I I e A2 E.PODATAKA. :. . I , .. ANAU2A PODATAKA, STATISTIKA M STATISTIČKI SOFTWARE > MODELIRANJE, eiMUtACIJAl OPTIMIZACIJA :- ' ! ; !' [ DIZAJN I PROIZVODNJA POMOĆU RADUNALA KCAO/CAM) i . .UMJETNA !^4T.EUGENCtJA l:EKSPEBTN! SISTEMI i. ; I ;. • PRIMJENA INffORMATiCKtH SREDSTAVA I METODA U PRIF — i DRUŠTVENIM ZNANOSTIMA t -t ^ ' " T ' • DRUSTVEMl l PRAVNI ASPEKTI INFORMATIKE ■ 1 Rok za šaittktti'2 stranice): ' l ' J is: STUDENI 1986. . . . - r I • I im' •Obairiiest o prihnian/ui 15, PftpSiNAC 19W, . "fìók ža ndove': 15; VELJAĆE 1987. .Sttvktura smpozija:..... PREDAVANJA, POSTER SEKCIJEi PREZENTACIJE HAROWARE-A I SOFTWARE PANEL IprSKUSIJEriZLOÌBE.......■........ ' ' " ' ■ ^ ' 'jnfomteapi, \ . , . , iSikréiirÉw'sIitjpoiija'' ^ SVEUČILIŠNI RAČUNSKI CENTAR, 41000 ^galsav« b.b., Jugosbvija •■Tel.;-04lÌ51tW)&9;;Tta-.:!!l8rV- ■■ -'^•-■T^ I I " ; f , -A, .-i -i I r • t i -i. Ì-. : ■r- r r- ! ... i. 4 1 r r 1. , .. ; j...: 11 -i. i M- ]- s i CALL FOR PAPERS-' •,VnU. 4b t-.-^.'-tlti-a'K^rtOtis .1 ^ Ifflfic ; : imT ÄWrtl.'i'MÄ' v.* ■'J^ ■•»• '«».v -h'^rTl IfV U ialmudonl ^ìiiE^mmùùm . Iflr Aprll'.l ivi J tJ Munich ^ . Fed. Rep. of Oen^eny ' - iiftji»',] •s»»!;^. 'J nrA "i. '.ü-i» L-^v tv : HP ' .iMti* QmliHlH4t'nr«fM«iiMUk T« SImnM] ojip.n liOnchn n TRIGLAV TRETJI VRH RAZVOJA ISKRE DELTE Računalniški sistem TRIGLAV lahko deluje na treh procesnih enotah. Z enostavno menjavo procesorskih modulov in operacijskih sistemov je družina TRIGI_AV kompatibilna z družinama mikro in miniračunalnikov vodilnih svetovnih proizvajalcev in seveda z računalniki In s programsko opremo ISKRE DELTE. Sistem TRIGLAV je zasnovan za uporabo v: - vodenju proizvodnje - - - avtomatizaciji procesov - robotizaciji - kot grafično delovno mesto za projektiranje - kot večuporabniški poslovni sistem - kot komunikacijska enota Iskra Delta proizvodnja računalniških sistemov In Inženiring, p.o. 61000 Ljubljana, Parmova41 telefon: (061) 312-988 Tiskma Kreslia