65 informatica 1 YU ISSN 0350-5596 ISKRA DELTA Tržno komuniciranie Parmova 41 iriformatica JOURNAL OF COMPUTING AND INFORMATICS Published by INFORMATIKA, Slovene Society for Informatics, Parmova 41, 61Ö00 Ljubljana, Yugoslavia EDITORIAL BOARD: T. Aleksid, Beogradj D. Bitrakov, Skopjej P. Dragojlovid, Rijeka; S. Hodžar, Ljubljana; E. Horvat, Maribor; A.. Mandžič, Sarajevo; S. Mihali<5, Varaždin; S. Turk, Zagreb EDITOR-IN-CHTEF: Anton P. Železhikar TECHNICAL DEPARTMENTS EDITORS: V. Batagelj, D. Vi.tas — Progranuning I. Bratko — Artificial Intelligence D. Ćećez-Kecmanovlć — Information Systems M. Exel — Operating Systems E. Džonova-Jerman-Blažič — Meetings L. Lenart — Process Informatics D. Novak — Microcomputers Neda Papić — Editor's Assistant L. Pipan — Terminology V. Rajkovič — Education M.. Špegel, M. Vukobratović — Robotics P. Tancig — Computing in Humanities and Social Sciences S. Turk — Computer Hardware A. Gorup — Editor in SOZD Gorenje EXECUTIVE EDITOR: Rudolf Murn PUBLISHING COUNCIL: T. Banovec, Zavod SR Slovenije za statistiko, Vožarski pot 12, Ljubljana A. Jerman-Blažič, DO Iskra Delta, Parmova 4.1, Ljubljana B. Klemenčič, Iskra Telematika, Kranj S. Saksida, Institut za sociologijo Univerze Edvarda Kardelja, Ljubljana J. Virant, Fakulteta za elektrotehniko. Tržaška 25, Ljubljana HEADQUARTERS: Informatica, Parmova 41, 61000 Ljubljana, Yugoslavia Phone: 61-312-988; Telex: 31366 YU DELTA ANNUAL SUBSCRIPTION RATE: US? 22 for companies, and US$ 10 for individuals Opinions expressed in the contributions are not necessarily shared by the Editorial Board PRINTED BY: Tiskarna Kresija, Ljubljana DESIGN: Rasto Kirn YU ISSN 0350-5596 VOLUME 9, 1985- No. 1 T.Damij J.Grad CONTENTS Reduction of the Simplex Tableau within the General Simplex Method A.P.Železnikar 9 K.Steblovnik 19 et All S.J.Djordjević 31 V.Batagelj 34 B.Sovdat 39 M.Germ H.Nežić V.Starle P.Kolbezen et All 48 52' 61 67 73 79 Petra - An IBM-like Personal Compute.r II An Advanced Logic Controller for Paka 3000 Terminal Index Levels Optimization in' Indexed Files Graph Coloring The 32-bit Microprocessor NS 32032 Computational Geometry Sructured Programming in Assembly Language Copies Test Methodology of Magnetic Bubbles Memories Programming Quickies News informatica časopis izdaja Slovensko društvo INFORMATIKA., 61000 Ljubljana, Parmova 41, Jugoslavija UREDNIŠKI ODBOR: T. Aleksid, Beograd; D. Bltrakov, Skopje; P. Dragojlovid, Rijeka; S. Hodžar, Ljubljana; B. Horvat, Maribor; A. Mandžić, Sarajevo; S. Mlhalić, Varaždin; S. Turk, Zagreb GLAVNI IN ODGOVORNI UREDNIK: Anton P. Soleznikar TEHNIČNI ODBOR:' V. Batagelj, D.Vitas — programiranje I. Bratko — umetna inteligenca D. Ćećez-Kecmanovid — informacijski sistemi M. Exel — operacijski sistemi B. Džonova-Jerman-Blažič — srečanja L. Lenart — procesna informatika D. Novak — mikroračunalniki Neda Papid — pomočnik glavnega urednika L. Pipan — terminologija V. Rajkovič — vzgoja in izobraževanje M. Špegel, M. Vukobratovid — robotika P. Tancig — računalništvo v humanističnih in družbenih vedah S. Turk — materialna oprema A. Gorup — urednik v SOZD Gorenje TEHNIČNI UREDNIK: Rudolf Murn ZALOŽNIŠKI SVET: T. Banovec, Zavod SR Slovenije za statistiku, Vožarski pot 12, Ljubljana A. Jerman-Blažič, DO Iskra Delta, Parmova 41, Ljubljana B. Klemenčič, Iskra Telematika, Kranj S. Saksida, Institut za sociologijo Univerze Edvarda Kardelja, Ljubljana J. Virant, Fakulteta za elektrotehniko, Trža- ke. 25, Ljubljana UREDNIŠTi'0 IN UPRAVA: Informatica, Parmova 41, 61000 Ljubljana; telefon (061) 312-988; teleks 31366 YU Delta LETNA NAROČNINA za delovne organizacije znaša 1900 din, za redne člane 490 din, za študente 190 din; posamezna številk?. 590 din,-ŽIRO PAČUN: 50101-678-51841 Pri financiranju časopisa sodeluje Raziskovalna skupnost Slovenije. Na podlagi mnenja Republiškega sekretariata za prosveto in kulturo št. 4210-44/79, z dne 1.2.1979, je časopis oproščen temeljnega davka od prometa proizvodov TISK: Tiskarna Kresija, Ljubljana GRAFIČNA OPREMA: Rasto Kirn ČASOPIS ZA TEHNOLOGIJO RAČUNALNIŠTVA IN PROBLEME INFORMATIKE ČASOPIS ZA RAČUNARSKU TEHNOLOGIJU I PROBLEME INFORMATIKE SPISANIE ZA TEHNOLOGIJA NA SMETANJETO I PROBLEMI OD OBLASTA NA INFORMATI KATA YU ISSN 0350-5596 LETNIK 9, 1985-št. 1 VSEBINA T.Damij. 3 J.Grad A.P.Železnikar 9 K.Steblovnik 19 V.Lončarič A.Križnik S.J.DJordjević 31 V.Batagelj 34 B.Sovdat 39 M.Germ H.Nežić V.Starlo P.Kolbezen in drugi 48 52 61 67 73 79 Reducic'anje simpleksne tabele splošne metode simpleksov Ibmovski osebni računalnik Petra II Napredna logična kartica terminala Paka 3000 Optimizacija nivoa indeksa u Indeksnim datotekama Barvanja točk grafov 32-bitni mikroprocesor NS 32032 Računska geometrija Strukturirano programiranje u asembleru Komunikacijsko usmerjen informacijski sist. IBM Copies Metodologija testiranja magnetnih mehurčnih pomnilnikov Uporabni programi Novice in zanimivosti REDUCIRANJE SIMPLEKSNE TABELE SPLOŠNE METODE S IM P L E K S O V TALIB DAMIJ JANEZ GRAD UDK: 519.852.61 ISKRA DELTA, LJUBLJANA, UNIVERZA EDVARDA KARDELJA V LJUBLJANI, EKONOMSKA FAKULTETA BORISA KIDRIČA, LJUBLJANA Metoda simpleksov je iteracij ski postopek, ki se odlikuje po enostavnosti in hitrosti, vendar pa je velik porabnik pomnilnika. V našem članku opiäemo, kako je možno postopek simpléksov modificirati ter s tem zmanjšati zahteve po pomnilniku samo na prostor, ki ga potrebuje vhodna matrika neenaSb. . REDUCTION OF THE SIMPLEX TABLEAU WITHIN THE GENERAL SIMPLEX METHOD. The general simplex method is known as a simple and fast iterative process but it as also known as a hig computer storage consumer. In our paper we describe the necessary modifications of this method which enable us to reduce the size of simplex tableau to the size of the input matrix of the set of linear unequations. 1. UVOD 2. SPLOŠNA METODA SIMPLEKSOV Metoda simpleksov je najbolj splošna metoda za numerično reševanje problemov linearnega programiranja; z njo lahko rešimo sleherni linearni program, kar je izrednega pomena za njeno uporabo pri različnih-problemih optimizacije v gospodarstvu. Metoda simpleksov je v bistvu iteracij ski postopek, pri katerem v okviru vsakega iteracij-skega koraka iz že znane bazne možne rešitve iščemo novo optimalnejšo možno rešitev. Odlikuje se po tem, da je zelo primerna za računalniško obdelavo, vendar pa je pri velikih sistemih tudi velik porabnik pomnilnika. Za metodo je namreč značilno, da temelji na tako Imenovani simpleksni tabeli, v katero morajo biti razvrščene vse spremenljivke ter da je potrebno na vsakem koraku izračunati in shraniti v pomnilniku celotno tabelo. Tak način' dela pa zahteva precej računalniškega pomnilnika, kar predstavlja osnovni problem uporabe te metode. To je tudi pomemben razlog, zaradi katerega se uporabniki raje odločajo za uporabo drugih metod, kot na primer revidirane metode simpleksov, ki so sicer bolj zapletene, vendar pa so manjši porabniki pomnilnika. V tem prispevku opišemo, kako je možno postor pek simpleksov modificirati ter s tem zmanjšati zahteve po pomnilniku samo na prostor, ki ga potrebuje vhodna matrika neenačb. Pri tem podajamo metodo simpleksov le toliko, kolikor je potrebno za spremljanje razvoja postopka reduciranja simpleksne tabele, podroben opis teo-ret-.ćnih osnov te metode pa je opisan na pri-rn'-r v 2] in |'3| . 2.1. Definicija linearnega programa Splošni problem linearnega programiranja za minimum namenske funkcije definiramo v matematični obliki takole: dol.očiti je treba vred- nosti spremenljivk gojem nenegativnosti Xj^ > O in linearnim pogojem , ,x , ki zadoščajo po- (i=li ,s) a„,x, + ... + a^^x^ > b^ ml 1 ms s — m tako, da ima namenska funkcija +,... + c^xg minimum. Vsi koeficienti so realna števila. Zgornji zapis linearnega programa ni uporaben za numerično reševanje, ker nastopajo v obliki neenačb. Take pogoje spremenimo v enačbe s .privzemom dopolnilnih spremenljivk. Če odštejemo spremenljivke '^g+i » • • •'''g+m zaporedoma od levih strani neenačb, preidejo té neenačbe'v enačbe. Dopolnilne spremenljivke upoštevamo tudi v namenski funkciji, kjer je "s+l "s+m = 0.- Da bi omogočili začetek numeričnega reševanja, vrinemo v vsako pogojno enačbo še po eno umetno spremenljivko, torej k levi strani enačb prištejemo zaporedoma spremenljivke *s+m+l ' ■ ■ ■'*s+2m' spremenljivke upošte- vamo tudi v namenski funkciji, kjer je c_ "s+m+1 = =s+2m = Tako dopolnjen Mnenrnl procjram lahko zapišemo v matrični obliki takole: potrebno je izratunatl vektor x, ki zadošča ne-enačbl x >_ O In enačbi Ax " b tako, da lina namenska funkcija cx minimum. 1'rl tem boi A = '11 in I ^in b = a b mn m kjer je n ■= 8+2m. Problem linearnecja programiranja zapišemo lahko v vektorski obliki tudi takole: potrebno je izračunati vektor x, ki zadošča necnačbi x > O in enačbi XjP^ + ... n O tako, da ima namenska funkcija cx minimum. Pri tem aoi 1 I hn mn 0 1 s s+1 „8+m Vektorji P,P,...,P(P P pS+ra+1^ ... p" 8o vektorji m-dimenzionalnega vektorskega prostora V™. Med njimi sestavlja zadnjih m vektorjev sistem m linearno neodvisnih vektorskih enot. To ao vektorji s+m+l (1, O, 0) , ■= (0,0, 1) 2.2. Določitev začetne baze Dogovorimo se, da začetno bazo vektorskega prostora V"" določimo iz vektorjev umetnih spremenljivk ter vektorjev dopolnilnih spremenljivk, ki so vektorske enote. TI vektorji torej sestavljajo bazno matriko B, ostali vektorji dopolnilnih spremenljivk pa naj sestavljajo matriko, ki jo označimo z D. Potem lahko matriko A napišemo koti A |>, D, [;] (1) Struktura vektorjev bazne matrike B je znana, saj je sestavljena iz vektorskih enot. Koeficienti baznih vektorjev v namenski funkciji so ravno tako znani in sicer so enaki M (kjer je M primerno velika vrednost) za umetno spremenljivke in O za dopolnilne spremenljivke. Isto velja za matriko D, saj ima vsak vektor te matrike samo en element različen od nič in sicer (-1). Koeficienti vektorjev matrike D v namenski funkciji pa so enaki 0. Iz tega slpdl, da je struktura vektorjev, ki so v matrikah D In B ter njihovi kocficlenti v namenski funkciji že vnaprej določeni s predpisanimi oblikami pogojnih enačb In neenačb linearnega programa. Ce najdemo način, s katerim lahko na začetku reševanja linearnega programa ugotovimo, kateri vektorji pridejo v sestavo začetne baze ter v ustreznem trenutku reSevanja, kateri vektor matrike D je potrebno transformirati, potem lahko opustimo formiranje matrik D in D ter omejimo reševanje linearnega problema samo na matriko dimenzije m x s. Z raču/ialniškega vidika pomeni tako zmanjSanje dimenzije aim|)lok-sne tabele zadostno zmanjSanje računalniškega pomnilnika, potrebnega za izvajanje programov, ki rešujejo probleme linearnega programiranja z uporabo splošne metode simpleksov. V ta namen naj bo q vektor reda m, ki ima za svoje elemente simbole relacij v pogojnih enačbah in neenačbah obravnavanega linearnega programa (>, = , . Ta vektor ima odločilno vlogo v modificiranem postopku, kajti s pomočjo tega vektorja lahko določimo vektorje matrik D in B ter njihove koeficiente v namenski funkciji. Za določitev začetne baze je potrebno ugotoviti indekse baznih vektorjev ter njihovo koeficiente v namenski funkciji. Zato definlrajno naslednje vrednostii g^ naj bo število, ki nam pove, koliko je pogojnih neenačb v linearnem programu (t ' i) i gq naj bo število pogojnih neenačb ali enačb oblike (>) ali (=)i d naj bo število vhodnih in dopolnilnih spremenljivk v sestavi matrike A) to vrednost dobimo kot d = s + gl n je število vseh spremenljivk matriko ^^ to vrednost dobimo kot n = s + gl + gq Z njimi moremo določiti indekse baznih vektorjev ter njihove koeficiente v namenski funkciji brez oblikovanja matrik D in B. Nadalje definirajmo še naslednja vektorja reda mi □ C , ki vsebuje koeficiente baznih vektorjev v namenski funkciji in n V , ki ima za elemente Indekse bassnlh vektor- jev. Postopek kreiranja začetne baze je takle: A) Izračunajo se vrednosti gl, gq, d in n. B) Glede na vrednost elementa q,, 1 = l,...,m, se Izračuna Indeks i-tega baznega vektorja in njegov koeficient v namenski funkciji z naslednjim algoritmom: 1) i = 1 2) q^^ ima vrednost i potem je «.rq = gl = gl-1 ° n-gq o;»« 3) q^ Ima vrednost (O> potem jo gl - gl-1 v" = d-gl o® = O 4) Ima vrednost j potem je gq = gq-l ..B n-gq 0° " M 5) i - 1+1 6) Če je 1 < m, se postopek nadaljuje na tofikl 2). " . S takim postopkom kreiranja zaöetne baze eliminiramo oblikovanje matrike B, kajti vse značilnosti te matrike so dosegljive z uporabo vektorjev c® in v®. Razlika med prvotno in novo vrednostjo namenske funkcije^je tem vefija, 6im večja je diferenca Zy^ - o^. Ker Selimo to razliko povečati, da dobimo čim boljSo rtovo možno.reSitev, uvedemo v novo bazo tisti vektor pJ, ki mu ustreza največja pozitivna diferenca z. - c^. Vzemimo, da ustreza vektorju p*^ največja diferenca ^k - °k max (Za - Ci) j J "j' (2) kjer je z^ - c^ > O In j = 1,...,a. če nobena od diferenc ni pozitivna, òbatojeCè reäitve ni mogoče več izboljäati, zato je to 2è optimalna reSitev. 2.4. Zamenjava baze V bazo uvedemo tisti vektor p'', pri katerem ima izraz (2) največjo vrednost, iz baze pa odstranimo vektor p"^, ki ga določimo tako, da vsako komponento p® delimo s homologno komponento vektorja pl', pri tem pa uppStevamo samo pozitivne komponente vektorja p*, najmanjSi od teh ulomkov določa vektor p^^i ' 2,3. Izboljšanje možne reäitve V izrazu (1) je A matrika dimenzije m x n. : Vendar zaradi zgoraj prikazanega postopka eliminacije matrike B ter zaradi postopka eliminacije matrike D, katerega opis je podan v naslednjem, velja, da je A matrika dimenzije m X s, kar označimo « A- g. Kljub temu pa mora matrika A ohraniti vse značilnosti oelot-: ne slmpleksne tabele, potrebne za reSevanje i linearnega programa. V ta namen definirajmo naslednja vektorjai A C naj bo vektor reda a, ki ima za svoje elemente koeficiente vektorjev matrike A v namenski funkciji, . v^ pa naj bo vektor reda s; ki Ima za svoje elémente indékse vektorjev matrike A_ . m,s Iz prvotne baze dobimo novo bazo tako, da kak njen vektor zamenjamo s kakim drugim vektorjem, ki ga Se ni v bazi. Vzemimo, da odstranimo iz baze vektor p'^ in ga zamenjamo z vektorjem p*. Za vsako možno rešitev ima namenska funkcija določeno vrednost. Pri prehodu iz prvotne v novo možno reSitev se vrednost namenske funk-cijè Izboljša. Definirajmo sledeče količlnei e = min kjer zj pomeni vrednost vektorja p^, izraže-i. nega z ba is n imi vektorji, in kjer Zq pomeni vrednost namenske funkcije, ki ustreza prvotni bazi', V matriko A vpeljemo (m+1) vrstico, katero koeficienti a^+j^j so definirani-z . . Zj - Cj, J = i,..,,s .1 "ik i«jer a^jj > O, Ce noben koeficient a Sitev neomejena. °rk za 1 < 1 < m. Ik ni večji od O, je ré- Vrstlco (m+l) vpeljemo tudi za. vektor p ,. katerega koeficient je definiran s pj+i >■ Vse koeficiente v slmpleksnl tabeli (koeficienti vektorja pP in matrike A ) transfor- m+l, s mlramo po naslednjem transformacijskem zakonui a) b) »rk kjer J = *r a. (3) "i - ä rk 'rk 'ik 'ik kjer je 1 =1,...,m+l j - l,...,s. L ^ r in Uvedba vektorja p v bazo in odstranitev vektorja p"^ iz baze se izvrSl tako, da se v v® vnese vrednost iz v? (indeks vektorja p''), v ■ B ' a c_ pa se vnese vrednost Iz c^ (koeficient vek-k ' tprja p*^ V namenski funkciji) i P»votnl vrednosti komponent v® In c® se predhodno shranita v postavkah, ki ju označimo z vbr in cbr. To, rej jei vbr cbr ■m+l, j 'J 2.5. Zamenjava vektorjev matrike A Matrika A ima na začetku numeriönega reševanja isto strukturo kot matrika F, torej predstavlja matriko vektorjev vhodnih spremenljivk. Prav tako pa sta na začetku numeričnega reše- A A ' Vanja v in c vektorja indeksov vhodnih spremenljivk oziroma njihovih koeficientov v namenski funkciji. V matriki A in v vektorjih A A V ter C se v dani Iteraciji vräi zamenjava vektorjev, njihovih indeksov ter koeficientov v namenski funkciji. Smisel zamenjave vektorjev matrike A je v naslednjem i Ir 1) izkoriščanje prostora vektorja p v matriki A, saj postane vektor p'' po uvedbi v bazo vektorska enota; 2) ohranitev značilnosti vektorjev dopolnilnih spremenljivk v simpleksni tabeli tako, da ob določenih pogojih dane iteracije uvedemo ustrezni dopolnilni vektor namesto vektorja p'^ v matriko Aj 3) ohranitev značilnosti vektorja p*^, ki ga odstranimo iz baze z uvedbo tega vektorja v matriko A na mesto vektorja p)^ zaradi njegove možne vrnitve v bazo. Izvršitev zamenjave vektorjev matrike A je odvisna od vektorjev q In c^. S pomočjo teh vektorjev lahko sklepamo, če je potrebno izvršiti zamenjavo, poleg tega pa, kateri vektor je treba v dani iteraciji uvesti v matriko A. Definirajmo vrednost-ql, ki naj pove, koliko pogojnih enačb je v prvih r enačbah ali nee-načbah linearnega programa. To vrednost potrebujemo za ugotavljanje Indeksa ustreznega dopolnilnega vektorja, ki ga moramo uvesti v matriko A. Preden realiziramo postopek zamenjave vektorjev matrike A, moramo zaradi degeneracije in zamenjave vektorjev shraniti značilnosti vektorjev matrike A, ki imajo po odstranitvi iz baze možnost ponovne vrnitve v bazo. To so vektorji vhodnih in dopolnilnih spremenljivk. V ta namen vpeljemo vektor v reda d, ki ima za svoje elemente značilnosti teh vektorjev. Vrednost elementa v j (j «> 1, .. ., d) mora zagotavljati hitro dgotavljanje mesta In strukture vektorja p3 v dani iteraciji. Postopek oblikovanja vektorja v: A) Za j = 1, .,., s velja Vj = 3 Gre za vektorje vhodnih spremenljivk, ki aešt.avljajo matriko A na začetku numeričnega reševanja. p^ je vektor j-te vhodne spremenljivke, njegove komponente pa so shranjene v j-tem stolpcu matrike A. B) Za j = 3 + 1.....d 1. j = s , r = O 2. j = j + 1 3. r = r + 1 4. ima vrednost ; potem je 'j d + r p^ vektorska enota, katere.r-ti element je enak 1 in se trenutno nahaja na r-tem mestu v bazi. 5. ima vrednost (>) potem je 'j -(s + r) negativna vrednost elementa v. pomeni, da je pj nebazni vektor dopolnilne spremenljivke X., njegov r-ti element pa je enak -1. ^ 6. q Ima vrednost (=)> če r < m,se postopek nadaljuje na točki 3, sicer pa se konča. 7. če je j < d, se postopek nadaljuje na toč- Hi 2. 8. konec postopka. Postopek zamenjave vektorjev matrike A: A) Vrednost q je in vrednost cbr (vred- Đ r nost c^ pred zamenjavo) je enaka M. Iz tega sledi, da je p"^ umetni vektor, zato ga po odstranitvi iz baze zanemarimo, ker nima nobene možnosti vrnitve v bazo, namesto trans formiranega vektorja p"^ uvedemo ustrezni dopolnilni vektor pd. Vsi elementi vektorja p"^ so enaki nič, razen r-tega elementa, ki je enak (-1). Koeficient p^^j pa je definiran s ^m+1 - Cj. (vrednost pred zamenjavo). Za uvedbo p° v matriko A je potrebno - shraniti vrednost vektorja p*^; za ta namen definirajmo vektor p reda (m+1), kjer 'ik^ pri i = 1, m+1 - uvesti vektor p v k-ti stolpec matrike A, kjer "ik ^k O -1 za 1 = 1, 1 fi r - cbr taka vrednost elementa v^ pomeni, da je "m+1,k - za r Izračunati ql - ugotoviti indeks vektorja p*^ in njegov koeficient v namenski funkciji ter ažurirati vektor v s tem, da u = s + r - ql = O v„ = k v^ = d+r B) Vrednost q je (=) in vrednost cbr (vred-ß r nost Cj. pred zamenjavo) je enaka M. V tèm primeru ne izvršimo nobene zamenjave, ker je p"^ umetni vektor, poleg tega pa ne obstoji v tej situaciji kak ustrezni dopolnilni vektor. If Za uvedbo vektorja p v bazo je treba ažurirati vektor v s tem, da u = vj^ V.. = d+r C) Za vse druge moinosti moramo ugotoviti na; slednje I 1. vektor p"^ ja v sestavi matrike'Aj potem se zadovoljimo z ažuriranjem vektorja v s.tem, da ^(vbr) " 2. izvršiti moramo zamenjavo vektorjev, tako da uvedemo namesto vektorja pl^ v matriko A vektor p'^ zaradi možnosti njegove ponovne vrnitve v bazo. ■ Vektor p^ kot bazni vektor ima strukturo vektorske enote, katere r-ta komponenta je enaka 1, koeficient p^^j pa je enak niö. Za uvedbo p"^ v matriko A je potrebnoi k - shraniti vrednost vektorja p , kjer Pi "" ®ik ' ^ - uvesti vektor p"^ v matriko A s tem, da postavimo °ik " ° ' i = ...,m, ij'r «rk - ^ - ugotoviti indeks vektorja p*^ in njegov koeficient v namenski funkciji ter ažurirati vektor v s tem, da J = "k vbr c^ = cbr (vbr) Vj = d+r 2.6. Degeneracija število e oziroma p"^ določimo z najmanjšim izmed ulomkov (Sj^j^ * 0) • Ce je teh najmanjših ulomkov več, dobimo novo možno rešitev, ki ima manj kot m pozitivnih komponent in je zato degenerirana, V primeru degeneracije ni enolično določen vektor p»^, ki ga odstranimo iz baze. Denimo, da pridemo v linearnem programu do degeneracije in sicer zato, ker sta vsaj dva od navedenih ulomkov enaka. Vzemimo, da sta enaka ulomka Xj^'^rk *s''®sk' Primerjamo druga dva ulomka aj-i/a^it ^sl^'^sk' njima izberemo tistega, ki je najmanjši. Če sta pa tudi ta dva ulomka enaka, Se ne pridemo do odločitve In naprej primerjamo še naslednja dva ulomka a^^j/a^j^ In ®B2''''sk izberemo tistega:, ki je manjši. Če Se ne pridemo do odločitve, nadaljujemo primerjanje, dokler ne pridemo do nje. Denimo, da ugotovimo s takim primerjanjem, da je ulomek y^/a^j^ manjši od ulomka Vg/^ak' vilo r določa zato enolično vektor p'^, ki ga odstranimo iz baze |2{, Zaradi postopka zamenjave vektorjev, je potrebno v primeru degeneracije uporabiti vektor v, kjer element v^ (j l,...,d) rabi za ugotovitev značilnosti (indeks, struktura in mesto) vektorja pji - indeks elementa Vj predstavlja indeks vektorja pj, J - vrednost elementa Vj pa omogoča ugotoviti J strukturo in pozicijo vektorja p-* s tem, da a) če Vj > d pomeni, da se vektor p-* nahaja v bazi, njegov r-tl element je enak 1 in vrednost indeksa r dobimo z r " Vj - d b) če Vj <. s In Vj k pomeni, da je vektor p^ v sestavi matrike A, njegova struktura pa daje v^rti stolpec matrike A c) če Vj < O pomeni, da je p^ vektor dopolnilne spremenljivke Xj, njegov r-tl element enak - in vrednost indeksa r dobimo z r = -(Vj + s) 3, POSTOPEK REŠEVANJA Z METODO SIMPLEKSOV Postopek reševanja linearnega programa z metodo slmpleksov obsega naslednje korake: 1) - Določitev začetne baze vektorskega prosto- ra V» z vključitvijo postopka kreiranja začetne baze (podpoglavje 2.2.) - Vstavitev začetnih vrednosti vektorjev c^ in v^ 2) Vključitev postopka oblikovanja vektorja v (podpoglavje 2.5.) 3) Izračun naslednjih vrednosti) z. = C® a,^ + ... + c^ a^j , za j - 1, 'j - ."1 "IJ " n ' R o m+1 1 1 mm ■= C® b, + ... + c® b„ - p° , 11 mm 1 4) Določitev vektorja p'^ oziroma indeksa ki "v- " ■■ max (Zj - Cj) , za Zj - Cj > O J - J V primeru, da Je z^ - c^ ^ e, kjer je t primerno majhno vnaprej predpisano pozitivno število, je obstoječa možna rešitev optimalna in iteracljski postopek se konča. 5) če so vse vrednosti a^^j^ < O, (i «> l,...,m), se Iteracljski postopek konča in rešitev je neomejena. 6) Določitev vektorja p*^ oziroma indeksa r« O < e o r^ = min (x./a..), za a.. > O rk l 1 >- 00 - a. \X> 00 o 00 90 SO VA -i- «L IS VO 0« .5- 00 » rt c< «1 rt ff) K) > ih lo 2 O tn it < 5 0 1 § i <0 T- «M S cH eo M d iGt T* J»- -V ■O. m Oo VO «N 00 n m Ui s i «) •» -"i >- ui > a 2 a.«. M. : «I m X- Q<: «/» < O; O C £ C o ^ s s > o f vo » rH ^ 0^ > n 00 ro as r~ rt -I CM o/IN fg 00 \o in r- CO 827'2A prek dela rezidentnega podatkovnega vodila (4 biti), krmilnik za izbiro diskovnih, smeri , koraka in ostalih signalov, ki prihajajo in odhajajo iz diskovnega krmilnika 8272A, nadalje vezje za oblikovanje DNiA zahteve in kombinirani krmilnik, časovnik in RAM pomnilnik 8155H-2. Na tem listu se nahajajo tudi sheme priključnic IMI, P12, Pl6, P17 in napajalne p ri k 1 jučni ce. Na sliki 7 je prikazaVia blokovna shema logičnega vezja na listu 6r Diskovno vmesno vezje vsebuje tri krmilne linije za vključevanje in izključevanje motorjev, in sicer MOTOR ON 0-, MOTOR ON 1- in MOTOR ON 2- (priključnica Pil, sponke U, 4 in 2 na listu 6). Ti signali se oblikujejo v registrskem vezju tipa D (15, 74 LS 173). Štirje registri v tem vezju se naslovijo kot V-1 naprava z heksa-" decimalnim naslovom OAOH. Izhod Q0 vezja 16 krmili linijo MOTOR ON 0. Za vključitev motorja se v Q0 vpiše logična enica, za izključitev pa logična ničla. Podobno krmilita izhoda Q1 in Q2 vezja 16 liniji MOTOR ON 1 in MOTOR ON 2. Linija MOTOR ON O- končuje na sponki 16 priključnic Pil in P12. Uporaba tega signala za vključevanje in izključevanje motorja prek te sponke je standardna. Ostali dve krmilni liniji pa nista standardni in omogočata dodatno krmiljenje, če se pojavi potreba. Običajna uporaba teh linij je npr. linija MOTOR ON O- za diskovno enoto A, linija MOTOR ON 1- za diékovno eno- ' to B in linija MOTOR ON 2- za diskovni enoti C in Di Za vse tri linije obstajajo skakači, ki omogočajo aktiviranje teh linij po potrebi. Vmesniško krmilno vezje vsebuje vso vhodno in izhodno logiko z izjemo opisanih signalov za vključevanje in izključevanje motorjev; vsi ti signali prihajajo iz ali odhajajo v diskovni krmilnik 8272A. Vsi izhodni signali se ojačuje-jo v močnostnih invertorjih tipa 7406 iri v ojačevalnikih tipa 7407 z odprtimi kolektorji. Vse vhodne signalne linije so zaključene z upori vrednosti 150 Ohm na napajalno napetost +5 V in oblikovani z vezji 74 LS 14 (Schmittovi prožil-niki). Linija RW- SEEK krmilnika 8272A na listu 5 se -uporablja za mul tIpleksiranje osmih vmesnih signalov na Sliri sponkć krmilnika 8272A. Ko je krmilnik 8272A v i skalnem načinu (signal RW-SEEK Je nizek), ima nožica 19 vezja 122 na listu 5 nizko vrednost. To povzroči, da signala TRACKO- in TW0S1DED- dosežeta nožici 33 in 34 krmilnika 8272A na listu 5 in signala DIRECTION- in STEP- z nožic 38 in 37 se oddata' v d i skovne enot e . Krmilnik 8272A daje dva krmilna signala za izbiro 4 diskovnih enot; to sta signala USO in USI na nožicah 29 in 28, Ta dva signala se pošiljata na demultipleksor 126 (74 LS 139, list 6), ki je tipa 2iv-4. Vezje_;126 izbere ustrezno diskovno enotò z nizkim signalom na liniji DRIVESEL n-. Signal'a USO in USI pa prihajata še v drugi del demult ipleksorj a in povzročata ustrezen nastanek signalov HEADLOAÜ n- (priključ-nica P12 na listu 6 za 8 eolske diskovne enote) . ^ . ' Izhod HD (izbira glave) krmilnika 8272A nu no-; žici 27 se uporablja pri dvostranskih diskovnih enotah. Ta signal se lahko uporabi za izbiro ene izmed obeh glav (pri dvostranskih enotah). Pri ibmovskih računalnikih so v uporabi tako eno- kot dvostranske diskovne enote kot tudi dve gostoti stez, in sicer 48 in 96 tpi. Za načine ■ zapisa pi velja v vseh primerih dvojna' gost ot a zapi sa . Vhodna signala READY- in INDEX- se oblikujeta v vezju 74 LS 14 in prihajata na nožici 35 in 17 krmilnika 8272A. Linija READY- se lahko s skakačem SK18-6 ozemlji, če uporabljena diskovna enota nima tega signala. Indeksni impulz pa se pojavi pri vsakem zavrtljaju diskete. Vezje za oblikovanje posebne ( osveževal ne ) DMA zahteve Je prikazano na listu 6. Ta DMA kanal (z indeksom nič) se uporablja za generiranje zahteve DMARQSTO. Časovnik 8155H-2 je programI sko^^ tako ini cial i zi ran , da v dovolj kratkih časovnih presledkih (vsakih 15,1 us) generira signal TIMER OUT na nožici' 6 vezja 147 (list 6). Ta taktni imjiulz sproži ' hastanek signala DMARQSTO, ki se posreduje dWi krmilniku (8237A-5, 148, nožica 19, list 2) Vezje 8155H-2 na listu 6 vsebuje dvoje V-1 vrat, 14-bitni števnik-časovnik in 256 zlogov RAM pomnilnika; ta pomnilnik se seveda lahko uporabi za posebne namene, npr. s posebnim uporabniškim programom. Dvoje 11-bitnih vrat (priključnici Pl6 in P17, Ust 6) se lahko po potrebi uporabi za komuniciranje z okolico. Uporaba teh vrat jo odvisna od programske ini-cializacije vezja 8155H-2. Končno imamo na listu 6 še napajalno priključ-nico in napetostni stabilizator 7905. Pri tem velja opozorilo, da smemo Imeti na kontaktno nožico naj več J o. tokovno obremenitev 2,5 A. Tako smemo imeti v našem primeru obremenitev 12,5 A za napetost +5 V. 10. Logična shema lista 7 Ko Je krmilnik 8272A v načinu branJa-pisanJ a • (signal RW- SEEK Je visok), ima nožica 1 obr-nitvenega vmesnika 122 na listu 5 nizko vrednost, To omogoči signaloma WRITE PROTECT- in FAULT-, da dosežeta nožici 33 in 34 krmilnika 8272A in signaloma FAULT RESET- in LOW CURRENT- z nožic 37 in 38 krmilnika 8272A, da se oddata v diskovne enote. Poseben upor R37 na liniji ST- (list 5) zagotavlja, da se ne pojavi napačen ukaz STEP- na diskovnih enotah. Slika 8 prikazuje v blokovni obliki logično vezje na listu 7. To vezje Je sestavljeno i,z osnovnega oscilatorja s frekvenco 4,1952 MHz, ki generira dve derivaciji: ena se uporablja kot vhodni takt za časovnik.8253-5, druga pa kot vhodni takt za vezji tipa USAKT (82;jlA); nadalje imamo dve vezji USART z vhodnimi in izhodnimi vmesniki na prlključnici tipa RS-232 (P13 in P14), časovnik 8253-5 in V-1 paialilni krmilnik 8255A-5 z vmesnikom na p r i k Ij učji i co tipa Centronix in a kon I'i gu ra c i J sk i m stikalom. rezidentno podatkovno vodilo, sistemsko naslovno vodilo,' sistemsko-krmilno vodilo 4,9152 MHz oscilator . ;2 P13 R S 2 3 2 P14 R S 2 3 2 :4 vhodni vmesnik CSTIMER; (list 2) CSSIOO (list 2) vhodni vmesnik CSSIOl (list 2) časovnik 8255-5 OUTl OUTO TIMERINTR (list 1). CLK USART B251A CLK USART 8251A (i.'si -r) SIOIÄRXRDY SIO0TXRDY izh. vmèa PIO 8255At5 SI01RXRDY SI01TXRDY vmes P15 c e n t r 0 n 1 X PRINTRDY (kist 1) konfiguraciJ-sko stikalo CSPIO/i (list 2) —•H izh. vmes ________ Jt.i. Slika 8. Ta-slika prikazuje v blokovni obliki logično, vezje na listu 7. Tò vezje sestavl jajo tale pódvezja.in priklJuCnioe; oscilator z osnovno frekvenco 4,9152 MHz in odvodoma :2 in :4, časovnik 8253-5 za generiranje taktov (dva USARTa in prekinitev), dva USARTa z vmesniki in PIO 8255A-5 s konfiguracijskim stikalom (za nastavitev konfiguracije) in dve priključnioi tipa RS-232 in priključnica tipa Centronix. Računalnik Petra ima dva neodvisna asinhrona serijska V-1 kanala (standard RS-232C). Ta kanala omogočata med drugim uporabo, prikazoval-nih terminalov. Eden izmed kanalov (kanal 0) se lahko opredeli kot konzolna V-1 vrata za operacijski sistem CP M-86. Drugi kanal (kanal 1) Je namenjen prosti uporabniški izbiri. Serijska kanala uporabljata. vezje USART (8251A), ki lahko istočasno oddaj a - in sprejema signala z različnima taktnima razmerjema. Vezje na listvi 7 predvideva uporabo enakega takta sa sprejemni in oddajni kanal istega vezja USART. Pri tem se generi rata dva prekinitveria signala za vsak USART, in sicer SlOxRXRDY in SIOxTXRDY , (x - O, 1). Ti štirje signali se vodijo k pre-kinitvenemu procesorju 8259A (162, list 1) na vhodne sponke IRO, IRl, IR2 in IR3 (nožice 18, 19, 20, 21. vezja 162, ki j e pomočnik moj st ra- -krmilnika 135). Prekinitvi kanala O imata prednost pred prekinitvama kanala 1, in sprejemni kanal ima prednost pred oddajnim. Signali za preklnitveno zahtevo sov aktivnem stanju visoki. Zahteva SlOxRXRDY javlja glavnemu procesorju, da j e b 11 sprejet zunanji znak in da Je bil pretvorjen iz serijske v paralelno obliko. Podobno se z zahtevo SIOxTXRDY Javlja glavnemu procesorju, da se lahko poSljè v vezje USART znak za oddajo v okolico. Programirljivi Stevnik-časovnik 8253-5 ima tri kanale s l6-bitnimi vezji. Ti Stevniki se lahko uporabijo na 6 različnih načinovi kot generatorji za prekinitveni signal po štetju, kot programirani generator z enim samim Izhodnim impulzom, kot taktni generator^ kot generator pravokotne oblike, kot s programom prožen impulzni generator in kot z zunanjimi logičnimi vezji prožen impulzni generator. Vsi trije časovniški-števniSki kanali so uporabljeni in vezje 161 se programsko inicializira ob vklopu računalnika s posebnim programom, tako da delujejo v načinu 3 (generatorji pravokotnih impulzov). Oscilatorsko vezje regenerira Signal z osnovno frekvenco 4,9152 MHz. Z delitvijo te frekvence se dobita dva signala, in sicer 1,2288.MHz za dva USARTa in 2,4576 MHz za vezje 8253-5 (161). Prvi Stevnik časovnlka 8253-5 je programirani taktni generator, ki proizvaja signal BAUDO. Podobno proizvede drugo števniško vezje taktni signal BAUDl. Pri vključitvi računalnika je taktna frekvenca obeh signalov enaka 9600 bns (bitov na sekundo ali Baudov) pomnoženo s Ì6 (delitev s faktorjem 16 se opravi' v USARTih). Računalniški program iniciaVizira taktno frekvenco serijskega kanala O, ko uporabnik vtipka znak RETURN. Pri drugačni vhodni taktni frekvenci znaka RETURN se časovnik 8253-5 spro-gramira 9prilagodi) na novo taktno frekvenco. tretji časovnik-št evnik vezj Ija kot ura realnega časa funkcije. Ta ura ime po ini 10 ms (100 Hz). Ta signal se mojstrskega p rek in i t venega (135. list 1) in ima najvišj maskirnega prek i ni t venega si lahko postane zelo koristna so odvisne od prekinitev in časa. a 8253-5 se uporab-ali za zakasnilne cializaciji periodo vodi na sponko IRO krmilnika ' 8259A o prednost v okviru s t ema . Ta lastnost pri api i kaci j ah , ki v procesih realnega Vezje 8255A-5 (160, list 7) ima dvoje V-lvrat. Ena vrata se uporabljajo med inicialt zaci j o za branje nastavitev kon f igu rac i j sk ega stikala ST (1 - 8). Osem stikal določa signale za vhodna vrata A vezja 8255A-5. Položaj stikal določa trenutno konfiguracijo sistema pri heksadeci-malnem naslovu vrat OlAOH. Druga paralelna vrata so tipa Centronix za uporabo paralelnega ti- skalnika. Ta druga vrata se lahko uporabijo tudi kot splošna 15-bitna vrata z 10 izhodnimi in 5 vhodnimi linijami. Vseh 15 linij je ločenih od priključnice P15 z ojačevalniki tipa 7407. Pet vhodnih linij je ločenih z ojačevalniki tipa 74 LS U (176, 177). vhodi pa so karakteristično zaključeni z upori 150 Ohm na napetost +5 V. ' ■ , ■ • 11. Sklep k drugemu deVu V prvih dveh nadaljevanjih članka smo skoraj v: celoti opisali materialno zgradbo procesorja (matične plošče) ibmovskega računalnika Petra. S tem smo opravili šele lažji del naloge. Glavni poudarek v nada 1 j evanj i h bo namenjen oživ-.' Ijanju sistema in uporabi operacijskega sistemai tu pa nas čaka Se obilo eksperimentalnega in programi rnega dela . . SI ovstvo ((11)) A.P.Železnikar: Ibmovski osebni računalnik Petra 1. Informatica 8 (1984), št. 4. str. 55 - 67. Dodatek V tem dodatku bo zbrani, naslovi V_I vrat v perifernih krmilnikih (integriranih vezjih) listov' 1 do 7. Ti naslovi so nam potrebni pri programiranju začetnega monitorja, s katerim bomo začeli oživljati mikroračunalnik Petra. Spočetka bo ta monitor enostaven, postopoma pa bo postajal vse bolj in bolj zapleten. Ko bomo končno ugotovili, da delujejo vsa vezja in podsistemi Petre ustrezno in zanesljivo, bomo monitor izločili in bomo začeli preizkušati posamezne segmente BlÒSa, ki nam bo potreben za dani operacijski sistem (npr. za PC-DOS ali za CP M-ae). Imamo tole razpredelnico naslovov in pomenov : njihovih CSDMA- OGOH OOIH Naslovi V_I vrat 152 (74 LS 154) PHOGRAMMABLE DMA CONTROLLER 152-1(12) na 148-11(12) (8237A-5) Channel O: base and current addres channel O: base and current word count 002H 003H 004H 005H 006H 007H channel 1 : channel 1 : channel 2: channel 2: channel 3: channel 3: base and base and count base and base and count base and base and count current address current word current address current word current address quirent word CSFDC- 020H 021H FLOPPY DISK CONTROLLER 152-2(12) na 121-4(15) (8272A) read main status register read-write from-lnto data register DMA PAGE 0_1 LATCH CSDMAPG0_1- 152-3(12) na I42-10(12)(74LS173) 040H CSDMAPG2-060H DMA page 0 and page 1 select ssssBSSssssrsassssasBsasBsssaBSB DMA PAGE 2 LATCH 152-4(12) na 141-10(12) (74LS173) DMA page 2 select ločenim mikroprocesorjem Intel 80?^). liaz|J0j'čd tipk ustreza VT 100 standardu. Bilka 1. Zgradba terminala PAK-A 3000. 2. ZGHADBA MATKRIALNK OPWlNK Poenostavljena zgradba materialne opreme logične kartice KL'1'-T je narisana na Bliki 2. aistemsko vodilo mikroprocesorja IN'i'EL 8085 združuje vse osnovne module značilne za mikroračunalniški sistem, ki emulira zaslonski terminal. Signali sistemskega vodila so povezani na zunanji konfektor KI in kartico lahko (od zunaj) razširimo s prograinakim pontiilnikom (EPROM) in delovnim pomnilnikom (liAM), kakor tudi z vhodno/izhodnimi napravami. CPt 8085 je zelo ugoden za našo aplikacijo zaradi primerne prekinitvene zgradbe, liazen tega ima še posebno serijsko vhodno (SID) in izhodno (SOD) linijo. Da ti dve liniji lahko preko zelo enostavnega vmesnika priključimo serijsko tipkovnico,' Prikazovalni podsistem smo zgradili na osnovi dveh najnovejših integriranih vezij z ze].o visoko stopnjo integracije (AVDC in CMAC) ameriške firmo Signetics-. AVDC (Advanced Video Display Controller) generira osnovne časovne signale potrebne za naslavljanje video pomnilnika in znakovnega generatorja (osve-ževanje -s:! ike). CMAC (Color Moncirroiue Attribute Cojilj'oller) sestavi Iz atributnih, znakovnih in r.in-hroni.zaoi jski h s ljjnalov ter kazni ca, videosignal- za krmiljenje zatilunske elektronike. Kot komun ikačijski krmilnik :jmo uporabili fcnano vezje Z.80 SIO, 'ki. omogoča tako sinhrono kot asinlirono komunikacijo preko dveh serij-skili kanalov. Koraunikacijsiti 1'izični vmesniki za povezavo z računalnikom so ali HS 232 C ali tokovna zanka ali posebni poldupleksni vmesnik, za povezavo s tiskalnikom pa je fiü 232 C vmesiiik. S posebnim prograiuabilnira na-sovhikom lahko programsko spreminjamo komu-nikacijiUco uro SIO krmilnika. Vključili smo še nepozabljajoči pomnilnik z naključni.m dostopom, v katei'ega shranimo nekatere parametre terminala, ki jih lahko siirerol-njamo, vendar jih zelino ohraniti ob izklopu terminala. Na kartici je tudi register svetlobnega peresa, i'reko posebne logike za odčitavanje lahko na KI.T-T priključimo svetlobo pero, ki se uporablja v nekaterih IBM-ovih terrai.nnl ih in naka-terih industrijskih aplikacijah. Paralelni vmesnik je'dvosraeiTii in oseinbjtnii uporabimo pa ga lahko za priključitev zunanjega gx'a f.'i čnega procesorja, ki je samostojna naprava, zgrajena tako, da komunicira z računalnikom posredno preko KLT-T in omenjenega paralelnega viiiesnika. Video ii'hoda znakovnega dela in grs^fičnega dela terminala sta povezana v en sestavljeni, video izhod, ki Icj'mi 1 i skupni zaslon. Tako sestavljena naprava predstavlja grafični terminal. 2.1. PliOCESOliSKI DEI, KIA'-T Ta del kartice sestavljajo: Intclov Diikroproceeor 8085 - 8 do }2 k programskega EPUOH pomnilnika - 2 do 6 k delovnega KAM pomnilnika in - vmesnik za tipkovnico. Na sliki tri je narisana bločna zgradba, na listu 1 v dodatku pa logična shema procesorskega dela KLT-T. Procesorskega dela ne bomo natančno opisovali', saj predstavlja zelo običajno roikj'oračunal-nisko vezje. Opozorimo naj samo na nekatere značilnosti. Na serijski^ vhod in serijski izhod procesorja 8085 (IC 5) smo priključili vhodni (KSEHOlJT) in izhodni signal KßEfdN tipkovnice. Izhodni signal vsebuje posebne sinhronizacijske impulze, ki jih izločilno s pomočjo zapaha (IC2). Tako izločeni impulzi predstavljajo prekini tveni signal (iiBDINT), ki je povezan na prekinitveni vhod HH'1' 6,5 mikroprocesorja. procesor I I______I računalnik tiskalnik Slika 2. Zgradba materialne opreme KLT-T. KSERIN j^EROUT 8 db0-đb7 "T" abo-ab10 IL abh-abis Z: MEMW^ ^ ^Mza iz: IL Logika Izbira EPfKM teo_ E8/10 I £10(20 i eprom eprom eprom epron 0 1 2 3 ZS -c5 E20/30 g db0-db7 IL ram ram 1 Logika izbira RAMa »»OOP r8800 iL ram 2 r9000 _ramen^ Slika: 5. Zgradba procesorskega àela logične kartice Vsak zfifik iz tipkovnico nciitovlos^in liorjj-ako kodÌj;(ini II bi.l,ov. Tipkovnica .iili počlje v KL'i'-T tfiko, dij sie vüak bil Kačne a linhroiii-aiicijukira impulzom. Zjičetok znaka cioJoća •/.iičeLni , koiioi; zn;ikii pa končni ira])Lilz. Prot';ruraF,ki pomnilnik fjiiio roalizii-ali s šLi-ri.mi 0,1,? iii 5 (ICil, ICl.?, ICJJ in LCl'O- öpoi':il;imo lahko naBledn.jo lipe tPKOH-ov: :"/Uy, Z'/^?., P-Vbt in 27128. Pi-ove-•/.avü PI in PP moramo povnzati uporabi jonisiiiu t,PHOfl-u iii!t;r(;/.no. o ßiBiialoma HOHEN in HAi'ihN lahko proi^r-amnko i./.kiopimo proßi'aiiiKki ozLr-oiiia delovni pomnilnik nn KLT-T in ga seveda na-doiiKiiitirno z /.nnnnjim pomnilnikom. uiMLemiiko vodilo pi'oconor.ja jo povc.'zano na koiioktof KI. Vsi t; i telali so ojačani preko vmesnikov. ?.2. ridKAZOVALNI Ut.l., KLT-T Ta dol 1op;ične kartice določa prikazovalne znač i J noiit i terminala, ki jih moramo pazl.jivo izbrati, saj po^ojn jejo (polo(j; komunikacijski li značilnosti.) zd rnf.l ji vosi terminala z računalnikom, na kateT'ei;a ga priključimo. Kealiüiraii smo naslednje prikazovalne znar č ilnosti, ki. nst;rczajo VT 100 standardu: - format zasilna je vr.':tic x ■ .".O stolp, i v ali c!'i vrstic X 132 s(.ol.pc.iiv; - pi'iKazovalni atributi so: oliiutni video, utri[)ajoč, povečana svetlost, podci-lani in kombinacija vseh nii:'iteti Ir, !- pomik vsebine zaslona ji: lahko: nav/.c.ui', navzdol, delni, skokovit (vi-stica za vrstico) in gladek (linija za linijoj - vrstico z dvojno .širino ali visino :'./iaHov; - nabori, posebni.h znakov (linijske (iji'afiki-, semigra rike in n;icionolnih abece-ii)- - znaki za zaslon so sestavljeni iz točk tako, da je matrika velika'/ x 'j točk, znotraj bloka velikega 'j x 1:'; o<;m i r.ra I'i-čni znaki zapolnjujejo colutili blok, - znaki ao poudarjeni. Zadnji dve značilnosti stu predvsem pomi'rabni za uporabnikovo udobnost in povečata č i (. i j i-vost znakov. Z naštetimi in rekoliko jiri i-e,|( ni mi prikazovalnimi značilnostmi lahko emu!i ramo tudi večino ilrugili tipov teiwninaiov. Zgradba prikazovalnega d(;la je narisana na sliki 'I, iogična shema i)a i>a listu ? v doda tkii. A V DC (1C.27), pro[;i'amabi in i CUT krmilnik, (jene ri ra vertikalne in hori zon ta I nc časovni, sipiiiale za iirikazuvanje podatkov na zas.lonu Logika iibli* laatha video pomnilni- iitiJtó FXXt Finn -OS i>H MEMW MEMft Logika libila Vil naprav •STO— '1. /igradba lika 'I. /,(';r;niba p r i k azo v.-i 1 n e'ga dela logične kai-tic- moni Lorjü. Zuponidiio- nyn.lavljn vidòo püinn i In j k iruiüfli'.OT'Ujc; nji.-tiovo rfoaogjiiijo ti uCjtuiI pr'üctjüoi— jn. Pi-oi.r,fiimr.ko Itjliko ixbofomo tri. i'a/.l i.čru! nfičine (lolovuiija, J'ormnt zanloiia In ol)l iko čijijovnih uit^nalov zu osvozovanjo. Znaki, kl uu prikuzii,jejo na zaslonu, so v A^CII kodi zapi tieni v znakovnem delu vidoo pomniIniko (IC 52 in IC 55) atributi pa v (jtrihutnom dolu (IC ''/V in IC 3^). V času os-vežovnnja zaiilon» AVDC krjnilnik zaporedno naslavlja vidoo pomnilnik z naßlovniini. linijami UADO do DAÜ13. Znako dostavlja po VCHOÜ -VClllj7 linijah na vhod ztiakovnoga generatorja, atribute pn po linijah VATUO - VAÜD7 na vhod atributnega krmilnika CMAC (IC 47), Procesor prograrariko dosoßa AVDG krmilnik preko kontrolnih d/OUli/,I/U'WB/ in AVÜC/), treh naslovnih (Al(0-Aß,?) in podatkovnili (U11Ü-UB7) linij, a uifjnulom AVÜCIWT zahteva ki'milnik servi sirtin je v realnem času. AVÜC ki-milnik deluje v t, i. neodvisnem načinu, kjer je videopomnilnik ločen od sistem-nken;"» Pj'oceuor ßa lahko dosega surao posredno pfcko AVUC. Hkrati smo izkoristili Se sposobnost krmilnika, do si cam dostavlja v notranje rcgistj'o začetno naslove vrstic iz video pomnilnika s pomočjo vezja za kontrolo dostave video tabelo (IC 2Ü in IC 5A) in signala H'i'h'/ i>reko vmesnika za dostavo taijele (IC P.?). Procesor dosega video pomnilnik preko dvosmernega zapaha za vpis oziroma čitanje znakov in atributov (IC 2H, IC 29, IC 30 in IC 51). Zapahi so postavljeni na pomnilniške naslove i'XXU in KXX1 (IC 25). Postopek vpisa enega znaka in hki'ati atributa (vpijeta se paralelno) je naslednji: - v zapah vpišemo znak in trenutno vrednost atributu (ukaz i^lILD FXXü); - v AVUC krmilnik vpišemo ukaz: "ZAP1ÙI NA NÄlüV KAZALCA"; - AVilC izvrši ukaz v čaau, ko ne osvežuje zaslona, B pomočjo signalov WÜB/ in AüiV. Znaki oziroma vsebina videopomnilnika s« v času ooveževanja zaporedno dostavljajo na vhod znakovnega generatorja (IC 5),,kjer/ne prekodirajo v obliko, zaenkrat šo paralelno, primei'no za prikaz na zas Ionu-moni to rjo.' Izhod iz znakovnega generatorja ne paralelno vpiše v serijski pomnilni register ČMAC krmilnika. Na njegov vhod ne zaporedno dostavljajo šo signali atributov, ki ot; v CHAC ki'fflilniku prišti'i-iiuM'ii cum I 111: I Ji' Dl-.C VI' I uO t.c i-iii i nii I a. ijluMiiJil,-iiko Jo ]>()iiH'.',ii 1'Jm iilikd 11. 1'i'i iDiórt.ovimJu pro-{i;i'(iiiUiki: ojiriMiii' iuiio pi-nlviirin l.ii.Vili k iiji'ii i i: i m lionl i,Hliii>J:'i i inolili I a riioiii. i', iiiij Hum t,(ikr.na •/.^';r-ii(l-bii (iinOfijaùd onont.iivno ii|irriiii iijiiiijo I a;iLiior.t, i tdniilmilii Cpfi lii|';ajiiiiji' L i pii , ki j';n mm I i ramo) . Niul'/.oriio ,)i'(li'i. tia omj.ivì v n il iio:'I. i i! i iit.i'iiiiik i h i.ipi'i!mi'n I ,j i vk lUuli'IJuJf provrr.oraki' ■/.iiioi'; I ,) i vor ilti ponMiiii';',n i m raviiMlniiii pi'ii|i, raiiioin. liaviniliii pi'0|';raiii i !'.o iiH-ilficho Jno iidoilv i iwii i koiimii i (; i i'a Jo jM'oko m i ali'iiiiik I h iipriüiicii I J i vk in virioiinili pomn i 1 ti i kov . l'ri iipr'av I Jan Ju u poiui-iii07,iiiini inoiluli aparal.ui'iH- opi'iMiii' klićojo i-nv-iialni ,)iro|';ram i oiifiuva i'Ja Jo." i! knniliiii ]ii'in';i'aiiii'. Nckal.ori kiMiilliii pr'oi'.i'aiiii lahko pi-rko jii'iiki-iiil.vi'iir r. L i'uk tli PI' nciiiiiiloiiia '/.alU'.l i'Jo pi'iu'ajio i'nko '/,mO|': I J i vor. L i i ii po po(.i'i'l)i n i\pi'i'iji i n Jan.li'in t; i ül.i'iiir.k i li (ipi-oiiioa I J i vk /.ahi.cva Jo iik l'opaii Ju 1'avnaliiili prof.i'aiiiov . S»0 A a § pomnilnik ülikn G. Zgradba programBko opreme Nalogo pouameznih progrumakih modulov so na-Blednjc! ■ ■ havnalnl program za komunikacijo b tipkovnico nadzira delovanje intoligontno tipkovnice in vtipkano znake dostavlja glode nn atanje terminala (lokalno/ on-lino, dupleka/poldu-ploku) v ojDroJemni vrnoani pomnilnik in/ali v oddajni vmesni pomnilnik. Nadzorno jedro v prvem primeru aktivira ravnalni program zu razpoznavo in prikaz znakov, v drugem primeru pa za koinunikaoiJo a računalnikom. Ka.viinlni pi'ògram za razpoznavo in prikaz zapiSo znak v video pomnilnik, vpliva na oblikovanje zualo-na ali spremeni aiatemake nprcmenlJivko tako, da nadzorno Jedro aktivi ru ravnalni program za komunikacijo o tiskalnikom ali za nastavitev lastnoati terminala. Havnalni program zn komunikacijo z računalnikom oddaja znake iz oddajnega vmeanoga pomnilnika k računalniku. Kadar sprejme znak od računalnika, ga zapiše v sprejemni vmesni pomnilnik, Nadaljno obdelavo pa, kot v primeru vtipkanega znaka, prevzame ravnalni program za razpoznavo in prikaz znakov. Havnalni program za komunikacijo s tlskalnikOB nadzira prenos znakov iz nprojemnega vmeanega pomnilnika ali iz video pomnilnika k tiakal-niku. Havnalni program za nastavitev lastnostj. terminala omogoča izbiranje in spreminjanje komunikacijakih in prikazovalnih lastnosti ter-ittlniilü ter luBtnoati tipkovnico. Spreminja tuđi aifitemske siiremonljivke in s tem vpliva na delovanje ostalih ravnalnih programov. V primeru emulaci je drugih tipov terminalov oiitnnojo krmilni programi noaproinenjeni. Spremeniti moramo ravnalni program za razpoznavo in prikaz i?.naküv, redkeje še za komunikacijo z računalnikom ali a tinkalnikom, zelo rodko , j)a tudi v,li komunikacijo a tipkovnico ali za nuijtavi tuv . 1 iiii tnijiili to rminol a. 26 'f. Üpiu i'fizvojriijtlii 0!'0(lj;i ÜliiCtiJno oroil,)!' V.II rfr'.voj m i k i-o.r'ncunn 1 ni Tiko-C't !ji.!:i<-mii (kat. je n.pr. K1,T-'J) jr: r/r/.vojni uiillijin y. uiiiu I II Lu i'Ji'm /.a ni i I'. i'0()r-0cc:u)r , n;i k;i- I.iMTiii Jo x.iir.nnviiii. V imiŠimii |it'ini(;i'u üinn u|>i)fa-l)il.i livojnki nii'.l.cMi, kat,('i'i'|':a -/.iii'adba ,jo iiar-i- II,-1 tili tili u I i k i (j. fLoaiĆNi I i analizator i I_____i U RAČUNALNIK R8«00 all CP/M KLT-T MKRORAĆU-- NALNIK POVEZOVALNI TERMINAL J I— ■tipkovnica i ijlika h. /,(';ivmIIjii niulcme, na razvoj pru(';raiiiHk(j in npa fa tu i'lu! ojii'cmiiij HL'i'-'l'. V K1jT-T limo vi'.T'ad i 1 L moii i toriiki in'Oiyara, ki opr'^vLJa riiiik(;i,J(; pot-iailjin; za Li-a ti punj e jifOL';i'a(ankii in tml i apii l'fi l.u I'ik; o[iroma mikt-ot-a-fiiinii 1 n i fiki.'iia iJ i. Il tornii (Kl/l'-'l') : nastavi Lov upüi-iilnii kov Ui i'0|i;Liitrov (mi k i'oprucojiiorja huh;;)) 1 pi'i!|;;l ju in npi'ciuinjanjo pomni l- ni nk i h lokacij, p()|';iinJanjc pi'ogr'iuuov rio pi'O-ki.iiitvono točk«; in konično, olu'ntni zbifnlk HÜUÜ, .... Lojilčni anali i'.atnr ujìorab.imo Ka tcntiranji; ainiratiii'nc opr'ciiii! in roal nočanov-nlli ili.'lov prokramiik«! opr'tìiiic. Vhodno izhodna enoto moni toi'iike(;a pi'Otr^paina jo pov<"zovalni terminal, ki Jo Ludi tofiiiinal pačuna Liiika'-lUiMÜÜ nil Cl'/n mi kroi'iičuna I n i kn. Na tom i'üöu-nainikii ■/, diukovnim oporac i J iik i m niiituinoin kroi,['amo izvorno prooircame lii jih provajarao v ohjoktno kodo, ki jo i; ixiinoiijo povo/.ova 1 neii;» tormina la pronarinmo v KLT-T. I'oiiolini prooni nnlat);alnik inon i tori!kot';a j)ro|';rama KLT-'l' nnlo/.i objoktni jH-ogi'iiiii na v niiproj rloiočoiii dol poninilnika. Naložen pro^rram lahko uedaj tonti ramo. (Računalnik HC .800 jo voóujioralm i .'li-, I in lahko nanj proko vuójo(';a rit<-;vila jiovir/ova 1 n i h tor-ininalov [iri ki jur. i mo voč KL'l'-'l'. Uporabi J,iti pii moiamo pro'vino pror.raranko oproino (prcónl /.Ini— Il i k Hüf',0). Ci'/M mikroraòurialnik Jo o non porabil i l'k i vcndai' na njiMii ni jiOtrobno uporabljati prodno pi'O-l^i'amskc opromo. V priworu, da i ina mikroračunalnik vključon prikazovalni krmilnik, ne po t ri:bu jomo po vozova 1 riofi:a terminala, par pa ;io na K1,.T-T priključim neponrodno preko poraožnoj^a lili C vmonnikn. /.AKI..I1JČ1'.K V zač(;tku novombra urno v üoi'onju izdelali začotno aorijo potdooet kooov KLT-T. Uoziiitnti tentiranj torminalov PAKA 5Ü0Ü bo zolo ut.',odni. LITLKATUHA 1. K. ütoblovnik, Povezovalni torminnl - dol liintoma zu raavijnnjo Q|)nrnLuj'no in pro-fjramnko oproino, Mipi-o ÜP; P. K. litoblovnik, hmulolor i^u riizvijaiijo in toBtij'iin Je mikroi'ačuna In iöki li uioboiiiov , Mi pro B}; 3. K. ütoblovnik. A, Križnik, Upin pro(';raratiko opromo torininula B pomočjo tooorijo o vzorčno vodenih ßtatomihj Mipro H'i j 't. K. iJt,ob] ovnik, D, Vi-hovno, Uiiitom za tiMiti-ranjo mlkrornfiunoininkih moilulov, Hijiro H'l i b. INThL, Componont Uota CutoLoK l'JHJj tS. INThL, The MCÜ - aO/H5 i-'aml ly Uiioi''« Maiiual 7. PllIljilWüKiNhTICIj, MicroprocoBoro, micro computorß und poriphorul circuitry; H. üGü, 280 UJO toclinicul munuiil. OPTIMIZACIJA NIVOA INDEKSA U INDEKSNIM DATOTEKAMA SINIŠA J. DJORDJEVIC UDK; 681.3.016 Nivoi indeksiran,1a posmatraju se u zavisnosti od srednoeg broja prist\ipa, vremena tražen;ja i zauzeća memorije. Za svaki od ovih kriteri.ima odredju;je se na.ipovoljni.ii broj nivoa indeksa čime se stvaraju uslovi za optimizaciju nivoa indeksa u indeksnim datotekama u celini. IHDBC LEVELS OPTIMIZATION IN THE INDEXED FILES: This paner presents optimal number of index levels- for each criterion, main number of probes, time searchine and memory occupine;. 1. Uvod Bro.i nivoa indeksa posmatra se sa tri aspekta značajna za efikasnost indeksnih datoteka. To su srednji broj pristupa, vreme traženja i zauzeće memorije. Sve tri navedene veličine zavise od broja nivoa u indeksnim datotekama i na odKOvarajuči način utiču na efikasnost. Dobijeni rezultati važe ako je primenjeno sukcesivno traženje i po indeksima i u datoteci. Ovo nije veliko ograničenje jer se,sa stanovišta praktične organizacije traženja u indeksnim datotekama sukcesivno traženje najčešće primenjuje. Ò2,/= 1/2 - ... N? ... dz/= 1/P - ... Nj^ ... N^ Na osnovu <3Z/= ... ^Z/ = 0 dobi ja se: Q = N^ i.. Hj^ ... Njj dz/ dN. 2. Minimizacija aproksimiranog izraza za srednji broj pristupa ... iq ... Kjj ... (1) U sekveneijalnoj datoteci sa Q slogova gde svaki slog ima podjednaku verovatnoću traženja srednji broj Dristupa za sukcesivno traženje dat je izrazom: Z = Co+l)/2 . Uz pretpostavku 0»l , ovi su uslovi u praksi vrlo česti, izraz za srednji broj pristupa postaje: Z = Q/2 . Na osnovu posledije relacije, izraz za srednji broj pristupa u indeksnoj datoteci sa jednim nivoom indeksa ima oblik: 0/2N, gde je N, broj upisa u prvi indeks. Prema /2/ , diferenciranjem ovog izraza po N, i izjednačavanjem sa nulom dobijenoK rezultata debija se da je srednji broj pristupa minimalan kada .ie: N^ = \/Q Takodje nrema /2/, za dva nivoa indeksa: Z = H'j_/2 + N2/2 0/2N3_Hp gđe~je Hg broj upisa u druKom nivou indeksa. Istim postunkom dobije se da je srenji broi Dristupa minimalan ako je N,=Np x/^ . Za n nivoa indeksa ima se: Stav: Srednji broj t>ristupa za n nivoa indeksa jé minimalan ako je isDunjen uslov: Kj^ - ... = N^ - ... = Njj = '^"'■i/T" Doka'^. : Z = H^/2 + + "/2N. V2 dz/_ aN, 1/2 - + ... • "n Ni .. ^ «n/2 Q = ... ... N^ Deljenjem i-te jednačine sistema (1) lako se dobija: Nj^ = ... = N^ = ... = '""yö" Eobijeni rezultat znači da u indeksnoj datoteci sa n nivoa indeksa za minimalni srednji broj pristupa broj upisa po svakom nivou treba da bude jednak i da iznosi n+1 q Sada izraz za srednji broj pristupa ima oblik: = 1( ... .. što daje: 2 ...^^yo" z - iCn+DQ'^^-^l 2 dn 2 n+1 •na \z dZ/dn ,= 0 sledi: n = InCQ) - 1 Za broj upisa po svakom nivou indeksa dobija se. N = e a na osnovu: jj ^ f,l/ln(CO 6a stanovišta minimalnog srednjeg broja pristuna broj nivoa indeksa je ln(0) - 1 a bro.i upisa po indeksu je e . 32 Sobljonl rozultatl moraju se shvatiti us-lovno. Srednji broj pristupa u sekvenci,jalnoj datoteci sa Q slogova opisuje se lerazom Zm (Q'fl)/2 a aproksloacija Z - Q/2 moze se usvojiti sa Q >>1 . Ako se posle takve aprok-sinaclje dobije da je Q - e cela analiza se dovodi u pitanje. 3o Ninlmizaoija bez aproksimacije Izraz za srednji broj pristupa sada ima oblik« M, + 1 a . -i- ii„ + 1 2 N, + 1) Diferenciranjem se opet dobija sistem jed-na^ina (1) Sime zaključak: - n+1. i dalje važi. Time izraz za srednji broj pristupa posta-jes _1_ i - n + 1 + 2 Btav! Kada n raste Z. opada. Sa bi se stav dokazao potrebno je dokazati da is n2< nj^ sledi Z(n2)<>Z(n-|^) . Sokazs 1 1 n2+l. - Q (ng+l) < ng - nj^ J Hg - 0 pa se dobija* 1 , +1 ng+l n^+l Q ^^ 1 Ì < 1 I Sto dalje daje: ^ spi °2 <°1 iz 2ega neposredno sledi Vrednost Z je manja kada n raste. B druge strane, može se postaviti pitanjei J i je maksimalan broj nivoa indeksa koji se e ostvariti, odnosno koji je minimalan broj upisa po indeksu? Kao što je već pokazano, veza izmedju bro- Ja nivoa indeksa i broja upisa po Indeksu na oblik: M - "^i/V ..0 (2) fde je M broj upisa po svakom od n nivoa in-eksa. foSto se radi o celobrojnlm vrednostima relacija (2) se mora modifIkovatii N -p^tyq] + 1 , »♦yö" -ai jo ceo M - o^yo" + 1 , -ceo broj Relacijom f«! dobija se prirodni broj m takav da važi m £ a uz uslov da ne postoji prirodni broj m, koji Ispunjava uslov m nije ceo broj za N~2 dobija se: n » loggQ - 1 To znaSl da Je minimalan broj upisa po in- za n > I0K2Q N-2 dobija se: deksu 2 i da nema smisla n povećavati vi. še od logpQ - 1 čime su dobljene vrednosti za broj nivOa indeksa i broj upisa po indeksu takve da srednji broj pristupa bude minimalan. Primetimo da nema smisla uzimati da broj upisa po indeksu bude 1 (čime je moguće proizvoljno povećavati broj nivoa indeksa) jer se onda redi o direktnim datotekama ili in-vertnim listama a to izlazi iz okvira problematike koja se ovde obradjuje. To bi trebalo da bude predmet posebne analize. Sobijene rezultate ne bi trebalo dovoditi u vezu sa binarnim traženjem u sekvencijalnim datotekama, jer binarno traženje u sekvenoi-jalnim datotekama, po mehanizmu, pripada drugoj problematici. 4. Vreme traženja Neka je t^ ^ vreme prelaska sa jednog nivoa indeksa * na drugi i €.(1,...in+1;* Neka je t upisa na 2,i,j vreme prelaska sa Jednog drugi u istom nivou indeksa j e.(2,...,H). t, ^ - Je vreme prelaska sa jednog sloga na drugi u datoteci, k g. (2,...,Q/N®). Srednje vreme traženja dato Je izrazom: t_ - n+1 UTA IX M^ S " i s s '2.Ì.J ^ Q/N*^ ^2 k (3) *2.il,j"^2,i2,J Kako se može uzeti da je to relacija (3) postaje: n+1 1 N 1 Q/»"* VZ! ^l.i^S«»!! i-1 j-2 k-2 6 druge strane, kod traćenja podataka u svakom sistemu možemo definlsati dominantno vreme. Ovo vreme, u oznaci t^ , predstavlja vreme potrebno da se pre dje sa jedne hardverske celine na drugu a da se pri tome izvrši i mehaničko kretanje glava za čitanje i pisanje. Ima se: - t. 'M t. - vreme orelaska sa jedne fizičke rečenioe (sloga) na drugu (uzima ae da ovo vreme ne zavisi od dužine fizičke rečenioe) r-i - indeksi za ona vremena ti koja su Jed-^ naka t^ . - 1 u u S\inkcijom r(r]^) dobija se broj vremena t, koja imaju indeks r . ^ Važi: r(rj^) + r(r^) - n , Kako je u praksi najčešće: ■ const. j " oonst. " » ^d » <^0 relacija (3) postaje: tg - r(r^)t^ + ^(r2)t^ + r(rj)t^ Drugi član zbira Jednak je nuli, r(r2)-0, er se indeksi uvek mogu organizovati ■ ipi " . :..... nalaze na istoj hardverskoj celini. i ako da se svi upisi po jednom nivou indeksa Prama toma: t, - ♦ r(r3)t^ Sto anači da 8re l(-2 - i)t; • 2 2 j,n t„ - (n+Dt- + InCQ"^^ - Dt' + t4(n . 1 . t^ - const. öime Je pokazano da t zavisi od n na isti način kao i Z . ^ , Ovo dalje znači da za izračunato n (u delu koji se odnosi na srednji broj pristupa) i t ima minimalnu vrednost u direktnim me-dijuiima. Zauzeće memorije ; Nekä Je f dužina sloga bez ključa u ba-Jtovima i K. dužina kljuca na osnovu kojeg se vrši inde ksiranje^ Neka Je B dužina adrese Ćelije memorije u bajtovima (u svaku Ćeli, Ju se smetta po Jedan slog datoteke). Zauzeće memoriJskbg prostora za ri nivoa indeksa (područje u koje su smeiteni slogovi datoteke sa ključevima ne uzima se u obzir) dato Je izrazom: n+1 ; ^ Bft " : ■»■ t B rn i ßjj - ukupno zauzeće memorije po indeksima B^;. ACQ - (^ntl) ,/ - i) . ; . s; - Aisifi) cjn+i .- q-i ' : . . ^, Sa porastom h raste i funkcija , .Funkcija nema ekstremum. ,, ; " - Za 11=2 odnosno n-loggQ " 1 dobij«» A(0 - 2) Za Q>>1 dobi Ja se: ftj AQ Neka Jn : A - (f + K^)/h .Za S se onda dobila: S_ gde Je a. mèmoriJski prostor za datoteku bea indeksa." U praksi Je B najčešće oko 5 što znači da Je za indekse potreban memorijski prostor u iznosu 20^ od prostora za samu datoteku. B i veličina datoteke determinièu nivo indeksa sa stanovišta memorijskog prostora. I ako danas memorijski prostor nije problem, prema uštedi memorijskog proutora trebalo bi smanjivati nivo indeksa. UticaJ hardverskih celina memorije na zauzeće memorije nije razmatran Jer na njega mnogo više utiče aama organizacija datoteke odnosno rasporedjivanje indeksa i slotrova datotek» po hardverukiffl celinama. Ovo rasporedjivanje može imati i bitniJi uticaJ na zauzeće memorije od uticaja broja nivoa indeksa. 6. Zaključak Sa aspekta organizovanja područja prekoračenja može izgledati da Je indeksiranje sa brojem nivoa indeksa i brojem upisa po indeksu koji ne zavise od hardverskih celina neprihvatljivo, Ovaj zaključak nije tačan a odgovarajući dokaz Je izvan okvira ovog teksta. Pròlaz na područje prekoračenja a i samo područje prekoračenja mogu se takodje organitovati na više načinai. Izmedju ostalog moguće Je i područje prekoračenja indeksirati prema dolazu slogova 8 tim da u datoteci ne bi bilo nikakvog pome-ranja slogova a tirae ni ažuriranja indeksa. U osnovnom kontekstu indeksnih 4o'toteka iznešena analiza ima opravdanja kod datoteka sa niskom frekvencijom dodavanja slogova. Iz analize se moglo videti da Je za opti-mizaciju,nivoa indeksa potrebno slediti krito-rijume koji daju dve protivurečne vrednosti,. Prema srednjem broju pristupa i prema srednjem vremenu traženja potrebno je da Je broj nivoa indeksa što veci odnosno da granično bude n n logoQ - 1 dok je prema uštedi memorijskog prostora potrebno da taj broj bude što manji (odnosno da Je nula kada nema dodatnog zauzeća memorije). I ako memorija, danas, ne pi'edstavlja problem moguće je na osnovu iznešenih'formula formirati individualne kriterijume i težinske funkcije na osnovu kojih je dalje moguće problem optimizacije nivoa indeksa rešiti na osnovu sopatvenih uslova. Indeksiranje treba shvatiti šire, i izvan konteksta indeks sokvenoijalnih datoteka. Indeksiranje predstavlja oblik formiranja Veza ' izmedju podataka te se tako primenjuje u goto-, VÒ svakoj organizaciji podataJca. Kezultati dé-finisani u ovom tekstu u tom smislu mogu da unaprede organizaciju indeksiranja;- Ovo potvrdjuju i organizacije podataika preko sekundarnih ključeva za koje, po veličini 1 u orgnizacionom smislu, nisu neophodne banke podataka (ili nisu ni dostupne zbog softverske . podrške)Ovakve orRanizaciJe podataka predpostavi j a ju upravo dodatna, različita, indeksiranja. 7» Literatura . 1./ J. Martin, GOMPUTKK DATA - ÜAÜE OHGA-NlZA'i^ION, second edition, PHlMTICü -HALL,. iiWGLKWüOÜ ÜLIi'Kü, MEW JJirtßKf 07632, . 2./ H. Wedekind,, ORQANIZACaJA PODATAKA, ZAK. BARVAiSIJA TOCK GRAFOV VLADIMIR BAT AG EU UDK: 519.174 UNIVERZA EDVARDA KARDELJA V LJUBLJANI FAKULTETA ZA NARAVOSLOVJE IN TEHNOLOGIJO VTO MATEMATIKA IN MEHANIKA v sestavku je podan pregled najpomembnejših rezultatov o teoretičnih in algoritraičnih vidikih problema barvanja grafov. Na koncu je podan postopek, ki združuje trenutno najuspešnejša hevristična postopka za barvanje grafov: Szekeres-Wilfov in Bržlazov postopek. GRAPH COLORING in the paper a survey of the mist important results on theoretic and algorithmic aspects of the graph coloring problem is given. A heuristic procedure which combines the Szekeres-Wilf and Brelaz coloring procedures is presented at the end. Math.Subj.Class.(1980): 05C15 NEKAJ PRIMEROV PREVEDBE PROBLEMOV NA NALOGO O BARVANJU TOČK GRAFA Nalogo o barvanju točk grafa zastavimo takole: Dan Je graf G = ( V,E ) . Pobarvaj točke grafa G tako, da ne bo noben par sosednjih točk pobarvan z isto barvo. Običajno zahtevamo še: Pri tem uporabi čim manjše število različnih barv. Naloga o barvanju točk grafa sodi v seznam "osnovnih" (kanonskih) korabinatoričnih nalog, saj lahko nanjo prevedemo celo vrsto, navidez neprimerljivih, nalog. Poglejmo si nekaj primerov: 1. Badijski oddajniki Radijska oddajnika lahko motita eden drugega, če sta si preblizu. Kako razdeliti valovne dolžine dani množici oddajnikov, tako da se ne bodo medsebojno motili? Koliko najmanj valovnih dolžin je za to potrebnih? Prevod: TOČKE GRAFA: oddajniki POVEZAVE: oddajnika sta sosednja (povezana), če .sta si preblizu (lahko motita eden drugega) BARVE: valovne dolžine 2. Turistični vodiči Turistična agencija namerava organizirati n izletov. Za vsak izlet i poznamo datum njegovega začetka Z^ in datum njegovega konca K^ . Koliko (najmanj) vodičev je potrebnih za izvedbo teh Izletov? Katere Izlete' bo vodil posamezni vodič? Prevod: TOČKE GRAFA: izleti (oziroma skupine, če je za isti izlet predvidenih več vodičev) POVEZAVE: izlet 1 Je povezan z izletom j natanko takrat, ko je: ( Z^ )/H ( Z, ,K. ) ii (J. BARVE: vodiči 3. Optimizacija porabe pomnilnika Naj bo X = ^ i množica spremenljivk (istega tipa, da ne bo težav), ki nastopajo v nekem programu. Nekaj prostora prihranimo, če nekaterim spremenljivkam priredimo isti prostor; seveda tako, da dobimo ekvivalenten program. Koliko najmanj prostora je potrebnega? Katerim spremenljivkam pripada isti prostor? Prevod: TOČKE GRAFA: spremenljivke POVEZAVE: točki sta povezani, če sta ustrezni spremenljivki lahko istočasno aktivni BARVE: prostor v pomnilniku Morda ne bo odveč, če malo natančneje opišemo, kako določimo povezanost (Istočasno aktivnost) dveh spremenljivk: Sestavimo shemo programa in v njej povsod zamenjamo akcije z ustreznimi: lise X - vrednost spremenljivke X Je bila uporabljena oziroma Def X - vrednost spremenljivke X je bila spremenjena V pravilno sestavljenem programu moru biti na vsaki poti po shemi programa od. začetka do nekega Use X vselej vsaj en Def X . TočVi X in Y sta povezani natako takrat, . 1(0 lahko v aheoil programa najdemo pot z začetkom v Del' Y In končen v Use X , kl ne vsebuje nobene točke -l oznako Def X . 4. Smaforjl Na danem križišču so predvidene določene smeri vožnje. Na primer križišče (Ajdovščina v Ljubljani): d a Sestavi režim delovanja semaforjev na križišču (določi Istočasne smeri) z najkrajšim ciklusom Prevod : TOCkE CRAFAi omari vožnje . POVEZAVE: smeri sta. povezani, če se v križišču sekata (lahko pride do trčenja) BARVE; Taze semarorske^a režima V našem primeru dobimo naslednji graf, ki ga lahko pobarvamo 8 Stirimi barvami {1,2,3|1)! In določa naslednji režim: BARVANJA TOCK GRAFOV - OSNOVNI POJHI Naj bo dan graf 0 » ( V,E ) , množica barv C In "barva" nepobarvano a ^ C . Vpeljlmo še okrajšavo ^a " lidaj Imenujemo delno barvanje točk grafa Q vsako preslikavo ■ c V —♦ c^-ki zadošča pogoju , Vu,v£v .: ( (u:v)£e/Vvo(u) = o(v) c(u) = i ), Delno barvanje. Je barvanje natanko takrat, ko Je c(V)SC . Torej vsako barvanje zadošča-pogoju Vu.v^V : ( (u:v)^E č(u) min C(v/c) do o S(vimln C(v/c) / o); Vpeijimo funkcijo C)(c) = . " Za vrednosti funkcije O" veija ocena , kjer Je pa cBrd(V) . Ker se na vsakem koraku postopka vrednost CCc) zmanjša, se mora postopek v končno korakih izteči. Dobljeno končno barvanje označimo s o^^^ in mu pravimo reducirano barvanje. Danemu barvanju c v splošnem pripada več reduciranih barvanj (odvisnih od zaporedja redukcij). Za vsa pa velja ocena ^ )^(C/c) in naslednja lastnost Vvév.Vk€0..c ( (u:v)éE ) Torej Je c^^^ Qrundyeva funkcija grafa G is Jaatnoatl 0 v vsakem barvanju točka u imela barvo drugačno od vseh drugih točk. P2. če v grafu obstajata točki u in v , taki da si val sosedi točke u tudi sosedi točke v , potem uostaja minimalno barvanje grafa, v katerem sta obe točki, enako pobarvani. Obe pravili omogočata, da točko u "izločimo" iz grafa -nadaljnjega pregledovanja. Nekoliko drugačen pristop Je ubral Christofides, ki Je pokazal, da Je Jf-barvan graf mogoče pobarvati s X barvami tako, da najprej pobarvamo maksimalno neodvisno množico V N(a) s prvo barvo, nato z drugo barvo Vj . N(C(VSV,)) , ... Seveda moramo tudi tu pregledati vae možne maksimalne neodvisne množice. pobarvamo maksimalno neodvisno množico - Podrobneje so tovrstni algoritmi opisani v (Godec, 1983). Kaj pa, če Je graf prevelik ali pa Je cena za iskanje minimalnega barvanja s postopkom prebpra prevelika? Tedaj ae moramo zateči k hevristlčnim postopkom barvanja in se e tem odpovedati zagotovilu, da Je dobljeno barvanje minimalndi čeprav lahko slednje včasih pokažemo, tako da najdemo polni podgraf na )((Q) točkah. Stvar Je ie hujša. Carey in Johnson (1976) ata pokazala naslednje: Naj A(Ó) označuje IteVllo barv, a katerimi pobarva postopek A dani graf G . Potem najbrž (zaradi NP-polnostl) ne obstaja polinomsko omejeni postopek, ki bi zagotavljal, da Je A(Q) / 7C(G) ^ r < 2 Trenutno nista znana nobena konstanta r>0 in polinomsko omejeni postopek A , za katera bi veljalo ■ A(G) / X(0) < Najboljša meja Je reda p / log p . Večina hevrističnih postopkov za barvanje . točk , grafa zadošča shemi postopkov zaporednega barvanja: uhlla 3 v : c(v) • ■ do izberi barvo aćC(v/c) o :» S(via/o) Zato, da bi opisani postopek vedno tekel, mora biti vseakozl C(v/o) ^ O . Za to zadostuje, če Je caru(C) = i^(C) + 1 . Postopki zaporednega barvanja se' med seboj razlikujejo po pravilu izbire naslednjega kandidata za barvanje in po načinu izbire barve, s katero ga pobarvamo. Preden nadaljujemo omenimo "v tolažbo In vzpodbudo"'nekaj verjetnostnih rezultatov o postopkih zaporednega barvanja (Erdös, Grimmett, HcDiarmld): . Naj bo G{n,p) slučajni graf na n točkah, v katerem nastopa posamezna povezava z verjetnostjo p . S X(n,p) in '2^(n,p) pa označimo slučajni spremenljivki la barvnost oziroma število barv dobljenih z. zaporednim' barvanjem grafa G(n,p) . Tedaj veljata skoraj za vaak graf oceni: X(n,p) > (1 - £ ) 5 log^ q'' in n.p) ^ (1 *£) n.logj, kjer Je qi1-p, p41 in ĆX>« Iz zgornjega razberemo, da velja •Z?(n,p) / X(n.P) < 2 ♦ £ Torej zaporedna barvanja v povprečju le niso tako slaba. Povrnimo se k postopkom zaporednega barvanja. Kako lahko izberemo prosto barvo? Običajno ne razmetavamo z barvami in Jih zato raje po potrebi dodajamo. Torej: - če za dano točko obstaja prosta barva, izberemo eno izmed njih: najmanjšo, kar da reducirano barvanje) ali slučajno, kar omogoča večkratno poskušanje; ali pa najmanjkrat uporabljeno, kar da razmeroma enakomerno pobarvan graf) - če ima točka sosede vseh dotedaj uporabljenih barv, dopolnimo množico barv z novo barvo. Včasih se temu lahko izognemo,.tako da s Kempejevlmi zamenami sprostimo neko barvo na sosedih dane točke. Vsakemu zaporednemu barvanju ustreza zaporedje izbir točk, ki popisuje vrstni red barvanja. To zaporedje Je v bistvu permutacija točk. Za vsak graf G obataja taka permutacija točk OT , da da zaporedno barvanje točk v zaporedju, ki ga določa ^ , pri čemer vselej izbiramo najmanjšo prosto barvo, minimalno barvanje grafa O . V to se prepričamo takole: Naj bó c reducirano minimalno barvanje grafa G . Uredimo' točke grafa po naraščajočih vrednostih pripadajočih barv. Dobljeno zaporedje točk določa Iskano permUtaclJo (JT . Torej Je osnovno vprašanje pri zaporednih postopkih barvanja: Kako najti "la pravo" permutadijo - določiti pravi vrstni red barvanja? Poglejmo si nekaj možnosti: Welah-Pouallov postopek: temelji na naslednjem receptu: permutacija IT Je določena s padajočim vrstnim redom stopenj dj točk grafa G . Za WP-postopek Je mogoča pokazati oceno: Naj bo d^,^ dj ... d padajoče zaporedje stopenj točk grafa G , potem Je X(0) WP(G) < ma* { i : i < dj ♦ 1 J Dreveani poatopki: temelje na drevesnih permutacljah: permutacija X Je drevesna natanko takrat, ko za vsak léO-.lO velja: {u : (v^:u)£Ej f) {v^ : k^Ov-l-Qi * « TI poatopki imajo naslednjo lepo lastnost Drevesni zsporednl postopki barvanja se eksaktni za dvodelne grare. Primer drevesnega postopka je Brelazov postopek. Tu Je pernutaclja "ST takole doloSona: vse tožke Imajo vrednost O , toSkl. m Ima najveèjo stopnjo, postavi vrednost na 1 for i Q 1,2, ... ,p do •}r/] i H^wj} If d^v^ > Bu then val val ♦ r | sh ;» d[w]I «ndir ! d°£v3 :« vel i W :. W S {v} ( for u€ext(star(v)) n» «lo d[u2 d[ul - 1 ondfor andfor ; W t» V 1 for 1 1 to p do v :o ergraaxjd [vj : wCuJ | ool£vJ selectcolor ; w :. w \{vj i fop uéEXT(STAR(v)) Ow do d®£u3 :. d®Cu3 ♦ s andfop «ndfop ( Gornji postopek nam pri r • O in s / O da Brelazov postopek; pri r ^ O In s o O pa SW-postopek| zanimive pa so tudi njune kombinacije pri neničelnlh r In s . Postopek učinkovito sprogramiramo tako, da organiziramo d In d" v kopico (lahko celo Isto). Ka računalniku DEC-10, Univerze v Ljubljani Je postopek vgrajen v progrein COLORS programskega paketa za delo z grafi GRAPH. Program COLORS v zmernem času določi dobra barvanja grafov na do tisoč točkah in nekaj tisoč povezavami. LITERATURA fllAho A.V., Hopcroft J.E., Ullman J.D.: The design ijid analysis of computer algorithms. Addison Wesley, Reading, Mass. 197'' f2] BatagelJ V.: Barvanja točk grafov. Seminar ca numerlčno in računalniško matematiko IMFH-201, Ljubljana, november I960 [3] Berge C.: Oraphes et Hypergraphes (2. ed.). Dunod, Paris 1973 £4] Brélaz D.: New methods to color the vertices of a graph. CACM, 22(1979)1, 251-256. [5] Carri B.: Graphs and networks. Clarendon Press, Oxford 1979. [6] Catlin R.A.: Brooks' graphl..t liu.i.lt.. t m;.. Slika 3 nam prikazuje programiakl mod(;il procoHOrja. Vidimo, da ima 16 rscjiistrov, od katerih jo oisam naimifnakih (dedlcatei:!) in oEiem ufjorabniSkih (general purpotse) . Uporabniški fse uporabljajo za ishran jii.-s'an je 2:,ii(::,.HKin.i h «prcimBnl Ji vk in naiilovoy. ter ra operacije nad njimi. Vffil ■ uporabni iBkl registri iüo doliine Z.?. bitov. Imamo iSe oeem nameniikih regisitrov in «iceri - programiBkl «tnfvec PC - prekinitveni likladovni kazalec (interrupt iBtack: polntc-.'r) BPO in upor akini fiki skladovni litack pointer-) SPI. V t(?Qa v k: a k iS nem naiüiciu proceiior (uporabniški ali doüi'topi-in tidiari od teh dvish J» procesor v uporabniškem načinu delovanja je dotstopeii upor ahni i\iki «klad, na katerega lui.ie nkladovni kazalec SPI. V uporabni iSkem lüldadu 'so Tirani Hairisisno podatke ali vr-nitvene narslova podprogramov, V primeru pa, d,11 jKi procei-ior v nadiiarntüra natrinu (supervisor mode), p;* jt; dcnii.opon kazalec: (user odvisnosti od delovanja je nadzorni), je skladov, Ki->dar - riagisiter 8B (static ba^e) viiebuje naslov zaCetka globalnih «premenijivk programskega modula, ki je,' v Uvajanju. • - register INTBAGE (interrupt base) vsebuj» naslov zaCatka ta(:)a,le zunanjih priakinlttsv in programskih ali trap prekinitev. MCJI) (module) regiinter vsebuj« naslov glavnih podatkov programskega modula, kt j» v Izvajanju, ^ - statusni register PSiR (processor statua' regiiüter) visebuje statu'iino betsedo teg« procesiorja. Celotna beseda je dostopna iia/iio v nadiornem načinu delovan.ja. Vili namenski registri razen MOD in PSR acj 32 bitni. Zgornjih oacm bitov teh roglistrov j« zmeraj nič, registra MOD in PöR pa utn 16 bitna. Imamo pa fta en fttiribitni register. To j« konf Iguracl jski (conf i gur ati on) raglatiar, vjäetmje informacijo o prisotnosti nekaterih enot v sami liardware-aki konfiguraciji, mikroraiiunalnika. V pr'lmeru prisotnosti enot« liietiramo ustrezni bit v konf 1 gur.sci j«kom raglBtru, TI biti oe nonaftajcj na prelànitveni -(Interrupt» kontrolor, na raCunipko enoto f-l=LI, n« onoto ra nadzor nac) pomnilnikom Ip za c?noto, ki jO dmklđirirji sam uporabnik (cuatom) . V primeru odeotnoiitl prekinitventsga Itontrolerja ae tzva.j« nca-vsktoriiiki način prekinitev, ki bo opliian pozneje. V kolikor pa je rasetiran katsfri od ostalih treh bitcDv konfigurai^ljslcecia r«giotrn, ki ae nanaöajo na raCunsko enoto, onoto I« nadzor nad pomnilnikom ali pa uporabni.aie ahriini v siklac) iSe MOD reiglBiter (liS bitni) In vrnitvena adr creu-i (tekoCl PO. Nnto pride clo uliolta ha ustrezno (iieista priükinitvatriB! tiabela, ki ja de-f i ni rano z INTBASE reyiiìtrom in vektorjem. 1.5 Vrste prekinitev V priakinitveni tabeli nóihaj.s 31"! bitna vrednost, kt pomaga pri določitvi vseh potrebnih' parametriDv prekinitvenega program/n. !6 bitov iz to tabele se naloži v MOD r(aQÌffitiiir , ki kaie na vrh tabcale (mcidule table entry), kjer lio nhranjeni glavni podatki praki ni tvianiag.H programa. Iz tsi tabele s« prebere podatek o začetku programukega dela (program basi» pointer), ki ickupaj z ostalimi 16 biti iH prekinitvene tabelo (offset) določa vhodni naijilov v prek ini tvioni program. Vrnitev li prekinitvonega programa se izvede z ukazom RETT (riaturn from trap). Obnovijo se viaobine programokega Atevca, «tatiisnega rtagi istra, MDC) riagistra in SE) rogiiatra. Vso t.ci JO prikazano, na iiliki 6. Za vrnitev iz maskirane pri-ih:] n i t va pa aiT«TU« I MOOUU (K*>| IMTEHRUrr •M« WOOUtI TABLI INTHf •tanciaupomtu .-> , UN« t*>l pointir nioaiuu g*u kintik (riurvid) 1 ataik bau ^^ 1 VIAIHi SMBV tladar MHU icproii abortiranju dol o^ianega ul aia, sf? po izvededbl «bort prekinitve lahko abortirani . ukaz ponovno izvedffl, i.i.gi«ter. Vektorja ne ne upohteva, • ker je v konf i guracl jmkeiii rmgiistru r u-àmt i ran bit, ki kaSe na prleotnout preklnitvenega kontrolorja. C 1. l k ii 1 iNooriNTtiMun" MMCfCLS MTiRRUn COOTROl UMT J Lu.i; 1. (.11 Ljl. J. ti J 1. v i. vektorski načini v t«m načinu lahko sprfi'jemaiiio do K» rd.'lii!n.ih prwklnitHV. Vektor- je pozitivno 7 bitno (itevi lo. ka'okadni nafini ta 'nafin nam cimiiigni^a uprtjjemati do 256 različnih prekinitev. Prekini tveni konlrolorji ibci k.uMk.sdno povezani. Vtjktor je nesgativno fttnvilo od -16 do - I. V tabeli, ki jo naalovl jena m tmri^ vejktorjera, pa «e nahaja naslov, od koder CPU prehHir(» končni vektor. l.S.4 Proarflim«l(e nil trop prekinitve Tcj »o prekinitve, 1<1 se ptJjav.ljo kot rezultat Izvajanj« dalpČKinega ukasa In niso vezane na iimnnje clogocike. Vrnltvenl naslov vseh trap prekinitev ra^on tr.ap(TRC) jo naslov safetka ukaz«, pri kateri ce je preklnit6?v pojavila. lN!n320:52 pDzna nasltadnjo trap prsiklnltvet trnp(FPlJ) oo pojiivl zarndl detekcrl je n.apakei v račiunsikl enoti FPU. CPU apre^jiiie to obveiitllo hkrati i rezultati Iz raCunnke lanoto. trap(ILL) označuje nedovoljeno operacijo, to BBi j:gadl v primeru, da . je tekoči ukaz prlvlliglran (»e . lahko izvaja turna v nadzarncam naClnu delovanja), procesor pia ja v uporabnifiketn naClnu delovanja, ^ trapCSVC) («b (jtinerlra zaradi zahteva tekof.eoa ukaz« po «premembl naClna delovanja Iz upor abni«kega, v nadzorni . - traptatu»necja registra (BOtiran. Ce jo ta bit resetiran cie ta preklnltjjv ne «proSi. V kolikor se; med trap iil I «»tlovni m kacalc-em SP lahka vpi ai i ji.-ino alt l.ii-nt imuo pociatMo 2 ukozomn ■ PUEjH in F'OP, «Il pa zamenjujemo vrodnoiüt z i.ilüajijiii 1101) IF V, 2un.)nje (e»t«rnal) na!>l avl jon.ie; V l"lt)l) registru dob.iino nauilov fUJD t abi;-!». V j tabeli je na določenem moutu n.isilov LtNK tatael«, v katiarl me n.iiha j,i\ja naslovi ZLinnnjih podatkov. K nawlovu i: LINI tat.elej SB prliStojis !ii.') naslavljanjem, ali že t. onim naslavljanjem u skalnimi indeksi. Nafiiov operanda pri li-.'ih nafilnu S(? Izračuna tako, da «e k obstojccomu naslovi.i prliViti-f.jiH vsebino onu'qa upor .jbili'ti t'i,ja registra, pomnoženo z vrednostjo Hl.alnt.'ya indelitia. SIsalni Indeika lahlo ..iv.-;iiiioi vrednoiitl 1, 2, 4 ali £3. F'rlmer taloya nasi avl jan j« j« prikazan na iiilik.i 11. Effective Address [RIsD] /C-: I « /i / / z / / / / / / / / / Memory slilo 11: u.u. I .1 / I jijh ji: u I .limili i jikj... 11. 1 Memory till,.» Vi •;;p-.im iiisl.ü relcjl. i viio iia.= 1 avl juu 1.8 Preoled uk.nzov Mod Table LUtazi so po podobnosti grupirani v naolifdnje logična skupi nei l.B.l Pr-omi kl V tf'j grupi Imamo iä ukazov, katerih vsak lahko, upor abimo ;ra vse naSitiotm načina n.ii'sliiwl jan ja. 7! njimi lahko realiziramo premike ali zamonjavej vsebin mi-id registri, med rHMjititri I n^ pamniIni I om ali mßd različnimi pomn11nIfil i ml lakai:ijami. Lahko izvedi-jmu tudi premika manjdih blokov [lodatkov. li.i! .-.uii.ui.ji-' iK^isl.jvl j.uij'.' a. s. 2 Call Q$t vi .1 luka .uri tmotl ka 1.0.9 Večdimianzionalna polja. (To skupina - setstinv] ja 14 ukazov, k:i s» uporabljajo za omenjene načine naslavljanja. Imama ukaze za celoStovi liska iBiaStovan je in' C'däteviinje, » prenoHom ali brez njecj<>, potem negiranje, i::(bi pStovi i ®ko mnoiianje in deljenje-!, iatmcjlintno vrefdnost: Števila, oistanek pri Idei jen ju in drucja. ; Iz te grupe imamo dva ukaza. Prvi tastira IndakHB in ugotovi oli so v deklnriranem podroiiju, drugi pa modelu je pri izračunu nziCneoa naslova podatkov, ki «o podani z! i ndeksi pol j«. I.e.10 ZanCne operacije 1,8.3 Operacije z BCD étevili V tej skupini imamo dva. ukaza in sicer za odttitevanje in i!iO!»tevanje BCD 'itevi 1, I.B.4 Celoéteviloko primerjanje W«» voljo imamo äast ukazov, kl ponavljajo [izvajanje neke aperaci je v odvisnosti od niaketjo I cigi.énega pogoja nil fttevca, ki éteje Števi lo 'ponavljanj. V to skupino spadajo tudi. ukaz i :: a premikanje blokov F'."tl®tkov, za primer janje.j oziroma iiskanje dolciCons vrcadnosti v bloku podatkov, ter skoki na doloCeha mesta v! odvisnoiäti cid vrednosti, ki. j:ih zavzame n®h:a sprcjmenl ji vka. iZaatopano je « tremi ukazi, ki opravljajo jfunkclju pri mer j an ja dveh operandov. Rezultat 'toh operacij je nastiivitev ustreznih bitov v jotatufflnHm regi istru. Eden izmed ukazov omogòfia ti.idi. primerjavo bloka podatkov. l.a.S LogiCne operacijo IV to skupino sodi sedem ukazov, med njimi AND, PR, X[)R, COMPl-EMENT in fte nekateri drugi. jl.B.ll SSkoki, klici in vrnltveni ukazi: Tt-ii skupina je zastopana z 18 ukaz I. Skoki »o absolutni in relativni. Imamo tudi ukaz, ki Ima pbdobno nalogo kot paskaliikl CASSE stavek. Izmed^ klicev Imamo klice podprogramov in zunanji If pcidprcjgramòv, klic nadzornega naClna izvajanja, kl ic vhoda v podpr ogram in izhoda i :c podprograma. Vrni.tveni Ukazi se uporabljajo za vrnitve iz podprogramov, zunanjih podprogramov, iz trap prekinitev in zunanjih prekinitev. 1,0,6 Pomikanje in.vrtenje 1..0. II! Manipulaci ja z registri CPU . Ta grupia je «eStavJ jena Iz treh ukazov in elceri logläni pomik v. levo ali desno za N mest, aritmetični pomik v levo ali desno za N kiKS-t Iri rotacija v levo ali desno za N mest. 1.0.7 Manipulacija is posameznimi biti' To skupino imamo zastopano z osmi mi ukazi ,: Dmogoeiajo nam shranitev vsebine registrov y| sklad ali vpis vsebine iz sklada v registriH,! Imamo tudi. možnost postavitve posamernlh bttov| statusnega registra, tiar nastavitven posameznih! bitov konf iguracl jskega registra, ki VBebujej !l n-formaci JD 'o fizični prisotnosti nekaterih' leriDt v sistemu. W ,tej skupini imamo sedem ukazov. Naslisvl janja posameznih bitov je realizirano na ta način, da jiiaslov kaio na prvi (LBB) bit naslovljenega pyti». Ostali biti pa so naslovljeni z odmikom od začetnega. Operacije, ki jih izvajajo ukasi tK skupine pa soi testiranje bitov, testiranje in sat i ran jB bitov, testi ran .je; in reseti ran je bitciv, testiranju In setiranje z zaklepanjem (interlock), testiranje In resetiranje z z.iklepanjem, testiranje in invertiran je ter liiiikanja prvega postavljenega bita. i,B.13 Mešani ukazi V tej skupini imamo tri ukaze. Ukaz NOP (no operation) ohrani stanje, ki je bilo pred njeno izvršitvijo. Ukaz WAIT postavi procesor v istanje, v, katerem čaka na prekinitev. Ostane ifca 'ukaz DIA, ki je diagnostični ukaz in, se 'uporablja pri testiranju sistema. i.B.8 «kuplne bitov poljubnih dolSin 1.B.14 Ukazi podrejenih (slave) procesorjev tlkazi za operacije » skupinami bitov poljubnihi . dal žin,nam omogoča memori zaci jo .zapisov,: katlirih doi.'iin« ni mnogokratnik osem, ne da bi tastala v jaomnilniku 'prazna' mesta. Imamo pet ukazov, ki nam. omogočajo vpisovanje besed, različnih , doliin v spomin . ali izV njeg?» in prenose teh: bosečl med spominskimi lokacijami. i, jUttä.zi te grupe se - delijo na tri skupine In |i3icor glede na enote (slave procesorji), ki h nadzorujejo. To so računska enota, FPU, enota z»; nadzor, nad pomnilnikom (MMU) in uporabniško definirana enota. V teh treh skupinah imamo 43 jukazov, ki omogočajo popolrr nadzor,h.'«d terni enotami. Uporabi jajo se lahko samo ukazi za, enoto, ■ za katero . js bit v konfiguracijskam registru postavljen. ' 46 i2. podrejeni (si..avk) procesorji 2.1 Enota i.» nisdjor n.Kd pomnilnikom --MMU e: U sa sz SE S C: S3 &3 S3 a s: n = iToi mnata iiraiii omogoiV:« avfcom.ati!iko prevedbo virtualnih naiilovov v •flzifinn preko tabel v Biiinii mnotl ali v penimi 1 nIku. Imiaino ti.idl možnoist lalB'ditl poteku proor<»mn, postavitve br«akpolnt| IniS'iilovov In i.aSiiiJto ioljfönlh delov pcimnl 1 nI kia. ' Pr«veelb« virtualnih naslovov v fizične T« pr-ovedbn nam omogodta pod.Htkav, ki iso ishran.jenl podobnem medi ju, kot tistih, ki pomnilniku. Toni podatkom pr:i pl iSiaitio enako obravnavanje na disku aH drugem uo v nek virtualni naolov. Kadar zahtevamo podatke na nakism vlr,tualnem natal ovu, pride do avtoriiatriiko prS'Vedbe vlrtualnetja nanlova v flziünl, te bo ti piadatkl v pomni 1 nI ku, V kolikor pa tc-ih poclatitov ni . v pomnilniku, potem mora operacijski isiluiti-^in poüikrbetl ^^a prenos podatkov iz zunari.jega pomni Inifikega medij« v glavni pomnilnik. Ko je to opravljeno, lahko prida do pretvorbe vlrtualnetja naslova v fizič:,!. V ta namen podat.kcs razdelimo na strani , ki Ima.jO (Icil.'ìlno s12 bytov. NaCin prevedbe virtualnih naiiilovov v fl2liV:n(a pa nam kaže alik.a 12. Sä n Sa I« Js: r1 t I Ji 1.i:iit.> 'V i 1- 11.11 ri i 11 "Ja «lil'i 1? vidimo, da ji» vtrfinlnj nnsilov, l i 1 iiii'^ dol ? ino '.■'4 tiltov, i7H!"flt avi ji-^ri I ;r t i'ii'h di'-lovi dveh tndelnnih vrednoiitt INDFX! In TNDF^i^' in odmil a ai"l"'!"-iET. tndoksni "ri-Minci'-it i 1 ri'.H t- stran, odmi (i pa naülovt uiitrfmi hyte rnotr^j Istrani. Majprwj i-ii-' ir PTfl (p.iiji!' tahlr' h,ii;4f»t rtKji «jtra in vrctdnost ) INOFXl 1? vi r ♦ u i ) netj.i naslova «le'-itavl naalov t .'ibi-.-l i" "itrflnl prvcg« Indeküa (Indexl pstje tablo!, Vreilnont, H <>(' jo di:ibi i a tB t.-ibelo, n.-im tvnri i^.l iip.--» j r vrednostjo TNDFX?, nnaUiv 1 nbfl e «tr-jni driujwja i ndcflü-ia, Vr (•■dnoint, ki "iP jo dnht i? lir- driiiju tabele, pa tvori, ;skiipaj ? odmikom (rj virti.ia! npr|fl na'slnva, -flrifno lailrfp.n pndr.itl j, M J63 bil naslovljen 7 virtualnim na'ilovom. Tabele, ki jih piotrK'bii jemo i r ans fnr (ihtr ( jO, Bn r-hranjene v pomnilniku. ta namen MMIJ pirIÌIVZanie nadvror nad vodili in jtrii-lM'ire 11» t.^ilm'le ti'"arHì-f armaci J vredncT^st flrlčns'tj.* nar,lova poiiitavl na vodila. MMI.I pa I Hhlu tud t '^ìuna uhrani nćnsilove ntijliolj ujjrir'.iti] jeni h «Ip'ani v lair.ten pomnilnik In is tem pnvir'f ..i hitro';,t prevc-jdha virtualnih nasslnvov v firtPno. 2.1. S Iskanj® pcitel-:.-! prograrik-i Potel programa ri!'kDni;;trui ramci tako, da ugotovimo raporedje i.il-n7ov, ki «c izvedejo pred inc'kim breakpol nt nagilovom. N^iilriv vmtIctji ntHiekvc-nfnerja uk;r/« an ishrani v ponr^hr-n register, v Stmver pa 'j.>dRjo predan i>ei pojavi naslednji neriok vcni^nl ul. ir. MMLI 1/|i.-i dv.ü reKjiiitra naslovov, netnok venSn i h ida.-ov in dvn, 'litevca nai;-. t irivov isiekvr-ru^'nl ti i.ik:a:rov. Pri vs.rilciTi naslednjem nesekventnem ukaru ^'e nanlov iprejiSnjega premakne v dri.igl rtigl ü-r, r •■ivno t -d!o ise tudi število sekvcnCnih Mka::ov itiod njima prifmakni-:! 1? prveij-n i-itnvca v dri.igt. Pri prehodu 'skosi breàkpoi nt naslov imamo v (ir v(>m registru naralnv zadnjega ni:MnFil vK'nčnfg.,* iila-n, v drutjem recjl stru narilov prod? v prvem ètevci.i fStiavilo sel'veiniJnl h ulsaL'iiv med hriiial pnlnt nil Sil ovom in radnji m nesokve^nčni m ukazom in v drugem i'itevcu število inipkverif ni h uka;.'nv med ciiioma neskvončnima ukazoma. MHU Ima (iiri?no?:t al'tivjranja dvi-nh brsakpnlnt na'iilnvov, Il iti l.ihki> virtualna ali firifna. 2.1.3 TaiSeita podatkov v pomnilniku jMMU i:»iiagoi';a turli a'.HiXffi to priüd I ji'iii mi iptjsecji v pomnilnik. > Zaščita obsega posnmejnt; japiRe dnlžlriB ene iirtranl (SI? hyliiv). Imamo ätiri nivoje lalirttte. BazliCen dostop j» Vimogoi: en tudi v odvi isinoTitl nd tega -ill .jit' 'procreflor v nad?ornem ali uporabni «Skem n"<činu dniovanja. To odvliünomt nam kaì'e naiiilr-rtnj^ tatiel a. NIVO o i 1 Z A « C I T E i T! 1 -I- -I- -I- N uporab I nI 1 ni I siamo I pnpnln ft niškl Tdostopa Idntstopa I branje I dostop 1 nad- I samo I popoln I popoln I popolp M irorni I hran je I doislop I dnir.top I dnir.tiip V prlmoru,d.'» hnSe procenor prekoračiti naftin' do'.'ol jcnei:;.:! dositopa piodatkov 1? pniiin 1 1 n 11 .'i, epotn MHU takoj abortira tekoSi uka? « tr>m, da piriKt :ivi iii: tri'rM'i.i pr'Licciiaor jev vhod v t ivno s I; -iri j C. Rni'tiin'šlo «not;» FPU (floalincj poi r]t , an i t; ) T.;, onot-a nam omogoCa lr,vajanjC o^iriovnih Štirih VriCunaklh operaci j 2 realnimi žtevi 11 , In si cur !t n?.v.-.rfno prer.B7ljo «-.-.spie dolžine bJtov» Vrl i i I dvojno priace?! jO (yapts do.l f-inp 61 bitDv). Na« In obeh aoptoov ronln'fg? «»-.evi I « ^ vidimo na slil::i 13. / 7 .;lrM;:ln Ni.tioniil bom) concliift or'. il i«? I ü del 31 i' to ,1i'u>ini:i, pravijo, ■ rta .i» '' ra.rvojc.i nov.:-ra^(in«l'r» enoti». H ho i>ol»»') rmnola- s» o';;t.;ile ratitnsik:»- . cioprarl ih- «porifnri ran 1«. irrfxliin »-.rt «jwiornetr icnih ♦<«»>»■(:» j. trn«, (■:'lfiii:iol:irii;H-ii rio it.inrc i .le in driiri i h > . fìeference; M." "" □zrn SInsI* Pfteltlon II10 ti n_ h: I T— Doubl* Pracltlon II -i-« M = !::■! ^.jpi^; rö6lne/a4 sitoivLla v enojni. in. (.IvCijiii pi-liM.-e:; :i .ji , 1. National üemicioncUictor Corfjor ;)t: i on : MS lAOOO databookt 19B3 2. National Semiconductor Corporation« The NS U.000 microprocessor family - TehnicaJ f..aininar. S Boffin decries KSI »01 rffvrliiplnii Iht aiknKumpultrhsscdnpcrt iy«tnn Invinlcd by Uonotd Mlchk Michie expert system builder goes bust By Jenny Mill H*p«T« Suhwafc Inlcinalion-al (i-:SI). (he iompiiiiy kcI up Ut iniirkci Piofcxsiir" Doniild Michic's l''x|)crt-E:usc puck* a^c, hus HUipped tnidiug und suspended its 23 employees without piiy. 'liic company's directors applied (or volunttiry liquidation lust week after its bunk iiccount was frozen at the be);innin}{ uf September. A provisional liquidator has been appointed to protect the asset» i)/ liSI until an official liquidator is appointed in Ihe next two weeks. by John Riley A 111(111 iiroptiriion of éommer» eial, companies lituking lor c*|X'ri lyvitms arc wasiinu their time. That is ihc view of l>i.nald Mi. chic, liiiher ul Uritiih ariilkial in. ttlligence researth and ihr fotm-der and heud of the new Turing Insliiute, which aims to develop commercially viable eiperi lyMems. Speaking to the SIM. Interna» lionaJ Ofth gencruiion conkpiiiing confttence in London this week, he said; "The problem iit, lum is it aller II) years ol expert »y^ieni^» that very lew - less »ban 10 - arc actually doing a proiiiable iub. The maiority of commercial t»rga* nis;iti(>ns are energetically and es-pensively snriing ihrouuh a . |in»fusitm of discarded acadenuc , prototypes. "EveryMy agrees thai ihc problem is transplanting human know-how in lo the machine, l'hai is hard if the expert dX'eslinghouse. the Kadian (4iiporation and the US Army (*/(»rpi of Kngineers. Filth seneraiion programs in the US, la^un and Ivurupe will be tun on the buck of the Innu» Transputer chips. 'liuM is ihe view of Phil Tieiedicn, hcutl ol compu: ter arvhitiviiire at Ki-;iditig Uni-versiiv, who h^is sivni several D>onihs wiih the Japanese project. S}ieukiiig HI the Conien-IKC, he wid-. "A Uu ul piujiMs in the US,. Murpite and Jap.in plan ti» use In-nios chi|>s tor ili«-ii lifih generation pninranutw». There is no alternative Rulution." Japan's parallel infeience machine currently under development, which will merge the infetence maihitie and knowledge-based machine and which will Il ave Ihe power ol 1,01)0 niikntcotnputns, he said, will probably use the chips. I releaven, who has alrted that the country i^ (onnulating a nilli generation plan lu l>e based in ihe Korean Advanced Institute ol ScK-nce and IVchnologv, It will probably, take the Alvcv programme as iis main model. lite company was developing ibe inicuH:omputt:f-based expert system invented by Michie at Edinburgli University. Its failure was the result o( 'a series of small problems over (he last three nionlhs which led to (he adchtional funding it hud been expecting becoming ; unavailable»' according to an official of liquidator Arthur Yoiing McClelland Mmire. r.Sl was hoping for a cash injeclion of be(ween il.'SO.lMIU (o £2.S0.(XXi from its existing investors, the Scot- tish Development Agency (SUA). Muriay Technv>logy and llambros Advanced Technology. S<»me of the investors decided not to go ahead with (he. funding and the company was unable to continue trading. I1ie company's managing! director and founder, Sandiej Blackie, is in California.! where he was se((ing up a US! office for USI, and according, to s(>urces close (o the company he is 'left stranded'. The marketing rights to Uxpert-Gusc are owned by the SDA. ^ RAČUNSKA GEOMETRIJA MIROGERM UDK: 681.3:514.1 ISKRA DELTA, LJUBLJANA Članek sovori o zahtevah in načinu poaa.ian.ia oblike ter poda pnesled metod. V mehaniki je oblika - geometrija osnova tako analize kot izdelave z numerićno vodenimi stroji. Računska geometrija Je področje uporabne matematike/ ki ee ukvarja s problemi oblike in je teoretična osnova CAD/CAD programov. Computational seometra The article describes demands and ways of definins the shape and gives an overview of the methods. In mecnanical enaineerins is the shape < iseometra ) fundamental as well in analysis as in NC production. Computational geometru is a field of applied mathematics which deals with problems of defining the shape and is theoretical background of CAD/CAM programs. UVOD Računalniška strojna, programska ter grafična oprema osvobodijo uporabnika od omejitev risalne deske in pospeiijo celoten proces oblikovanja ali konstruiranja. Uporabnik lahko enostavno opisuje ploskve in telesa iz enostavnejših elementov, kot so točke in krivulje, dobi nov model s popravljanjem v bazi shranjenega podobneaa modela itd. Uspešno uporabljanje tega orodja zahteva poznavanje matematičnih principov podajanja krivulj in ploskev brez poglobljenega znanja računalniiitva. Konstrukter ali oblikovalec mora poznati le program, ki mu je orodje pri njegovem delu, in pa seveda svoje delo, ne pa tudi detaljno delovanje računalnika. Začetnik tesa področja je bil v Šestdesetih letih S.A.Coons, Nove matematične metode so poimenovali računska (numerična) geometrija za razliko od opisne geometrije, katero so uporabjali prej npr. pri izdelavi letal. Algoritmi računske geometrije omogočajo enostavno in hitro podajanje oblike, kar pomeni pocenitev proizvodnje. Poleg matematičnih osnov, potrebujemo že nadomestek za risalno desko, ki takoj odgovarja ukazom. To funkcijo opravlja grafični terminal, kjer se po spreminjanju vhodnih podatkov, npr.s premikanjem peresnega držala na tablici, ustrezna krivulja ali Ploskev brez večjesa časovnega zaostanka narise na zaslon. V zadnjem desetletju so geometrijsko modeliranje, interaktivna računalniška grafika in Proizvodja z numerično vodenimi stroji ali roboti zelo napredovali. Vse to omogoča proizvodnjo izdelkov zapletenih oblik. Medtem ko je včasih težko podati obliko telesa na risalni deski-, je računalniški opis dokaj enostaven in primeren. Prava prednost računalniškega modela je .rjifiunan je določenih lastnosti telesa, ■ preden je ta fizično Proizveden (npr. trdnostna analiza, analiza prenosa toplote, analiza n-ihanja itd.), in avtomatična izdelava programov za NC stroje ter vizualna kontrola poti orodij. Čas med začetno idejo in koncem - izdelkom je občutno skrajžan, ravno tako je izbolJžana natančnost izdelave. Npr. natančna izdelava lopatice turbine z numerično vodenim strojem zahteva vec 10 000 interpolacijskih točk; Verjetno je iluzorno pričakovati, da bi tehnolog vse te točke v 3 dimenzijah podal ročno. .1. Način podajanja oblike Algoritmi računske geometrije so osnova CAIVCAM programov. UspeSnost uporabe teh programov pa je odvisna od razumevanja matematičnih osnov algoritmov. "Computer Aided Design' ali CAD se ukvarja le z obliko ali geometrijo telesa, ki je osnova tehničnih izračunov. Konstrukter uporablja računalnik za enostavno podajanje oblike z vnosom točk in numeričnih parametrov, kot so vrednost odvodov, zvitosti, ukrivljenosti, ki so rezultat izračuna ali meritev in ki vplivajo na obliko telesa. Tako podano obliko 'telesa lahko uporablja tudi v kasnejših fazah dela, pri analizi obnaSanja modela, proizvodnji dokumentacije in izračunu poti orodij za numerično vodene stroje. Drusa skupina uporabnikov so oblikovalci. Te zanima oblika telesa predvsem iz estetskih in vizualnih kriterijev. Od konstrukterja se razlikujejo po načinu, kako obravnavajo obliko. Manj se zanaSajo na navajanje numeričnih parametrov, zanima jih le vpliv teh količin na obliko. Njihove kriterije je težko matematično opisati. Npr. avtomobilcikemu' ii>tillstu> oblikovalcu polil&tvar iaraCr ^araf ičnemu umt:>tnil pomeni uporaba računalnika i.n ;(iiutomatlCnei)a moiJola v začetni fazi preclvaem ipocBivitev produUciitir iskanóe večih alternativ jv enakem časovnem obdob.iur vizualizaci jo ibodof.eua izdelka, iz različni kotov» v različnih •barvah itd. 2. Zahteve pri podajanju oblike ,Matematični model krivulj ali ploiikev »plodnih oblik mor« zadofičati vtjčkrat nasprotnim željam. Začetna oblika mora biti opiiiiana na na jenositavrieJài način z naJmanJfiim. Številom 'karakteri'jitičnih podatkov. Oblikaf scnerirana s sii!>te:mom> mora biti čimbolj j« mosuče blizu zamiSlJenl obliki. Grafični ßiiätem mora iomoaočati enotitavno določitev prave oblike in .nadaljne apremembe. F'odaJanJe uiprememb naj bo ■lokalnüF da ni potrebno pri iipremin Jan ju izračunati celotno obliku fie enkrat. itinačbe krivulj in ploskev morajo zadostiti 'določenim matematičnim zahtevam kot zveznosti > iv večini ' primerov tudi • zveznosti odvoda in često zvetznosti ukrivljenosti. Običajno ni potrebnor da bi uporabnik sistema podajal ■vrednost odvoda ali ukrivljenosti numerično» kar je zelo težkoj vendar mora proaram • omouočati tudi to možnost. jTak računalniški prouram mora biti visoko jinteraktiven r upoštevati mora zadnJe dosežke» o jkomunikaci Ji mEid računa Inikom. in človekom. iModel mora omoaočati matematično Jasnoi-it definicije in izračun vseh aeometriJskih Iftstnotiitl r ki določajo obliko. še več» detaljna ur-afična dokumeiUac.lJa in trakovi za Nt; stro Je mora Jo biti oener Irani hitro in enostavno... Večina CAIi/CAM proaramov uporablja parametrične 'kubične krivulje. Parametrične metode imajo jObčutne prednosti pred ostalimi metodami. Z .matematičneaa in računalniškeaa stalifiča so lenostavne tako v dveh kut v treh dimenziJaht niso omejene na enolične funkcije. izoanemo se problemom neskonCneaa prevoJa; so invariantne za linearne transformacije koordinatneaa ^sistema itd, p'roarami pol inome. uporabljajo, največkrat kubične Polinomi viAJih iiitoponJ ImaJo lahko nezaželJena nihanja in potrebujejo : obilo parametrov za definicijo. . Na druai strani pa kompleksne oblike , > potrebii jejo določene prostosti za. , ópìs. ' . ParametiVične / kublčnfr> krivulje. kar. so Je pokazalo v Številnih CAD/CAM sistemih». sii dober kompromis mfd komplt^ksnostjo in enostavnostjo. Npr. odsekoma kubičen krivulJni segment ima fttlri' prostostne otopnje. tako krajevni in tatiaentni vektorji" enolično določajo obliko. Prvi in druai odvadi so zvezni, kar zadofiča večini uporab v praksi. odsekoma s, lokalnosti. ■Iiefiniran Je krivulj in ploskev .segmenti ali krpami ima prednost pri vsakem nadalnJem spreminjanju Je potrebno, popraviti le lokalne parametre. Vendar začetna Jdoločitev prevoJev. predvsem velikosti tanaentnih vektorjev. povzroča rosne težave predvsem pri Ploskvah. Te pomanklJivosti so povzročile uvedbo sestavljene Oblike. Uporabnik PodaJa le nekaj točk za interpolacijo in nekaj, robnih póuoJev. Oblika, ki Jo dobimo s PomočJo alaoritma. ima avtomatično zvezen prevoJ ali zvezen prevoJ in ukrivljenost. Pri kubičnihj krivuljah to pomeni ■ izračun tan!3«ntnih vektorjev. Pri ploskvah pa Je potreben zaradi' enolične definicije tudi izračun vektorjev, zvit Ja. Točke in robni tiouoJi določajo neskončno množico zvètznih krivulj (ploskev), f'redpisani PoaoJi zveznosti zmanJSaJo Ètevllo' možnih otilik. Tanaetnl postopek sestavljanja Izbere en element iz te množice. aledo na računske ali uporabnikove . zahteve. !ii postavljanjem točk se oblike razlikujejo ena ud druae lé v tanaentnih vektorjih seameritov (krp). . , Alaoritml so Številni, lahko so lokalni ali slobalhi. ena metoda zahteva zvezno ukrivljenost, druae pa ' ima Jo spet druaačne zahtevei Nekateri algoritmi izhaJaJo iz. fizikalnih, druai iz aeometriJskih lastnosti. Najbolj razširjene in upreJet« metode za aeneraciJü krivulj in ploskev so Ferausonova. Coonsova. tiezierova, - ulomljene kubično krivulje, zlepki ter bazni in beta zlepki. Ne obstaja univerzalna metoda t različne zahteve uporabe zahteva Jo' različne alaoritme. j Osnovni princip. ki -PovezuJe te metode, so. tanaentni parametri, ki so določeni direktno, ali izračunani na enostaven način. , V primeru,' ploskev lahko določimo tanaentne parametre »i tanaentnimi vektorji v obeh parametričnih smereh in z vektorji zvitosti. Analiza problema podajanja oblike pokaže, da se' ne razlikujejo samo alaoritmi. ampak sta tudi vrednotenje in spréJemlJivost dobljene oblike precej različna. Začetna oblika Je v večini primerih blizu želJene. vendar so včasih' potrebni, tudi popravki. Vzrok zato «o predvsem' ■estetski kriteriji, ki Jih ne moremo Izraziti z, matematičnim orodJem. Estetske in funkcionalne, zahteve so stvar intuicije, izurjenosti ini izkuSenJ uporabnika. . kar . zahteva visoko interaktivnost takih prosramov. 3. Pregled metod za podajanje ploskev lip funkcije za opIi» ploskev Je lahko < .Eksplicitni ■ ■.,■•' z «' f ( * , u > ( X. u ) • I l ■Implicitni ■; • . ■ ■■ .. ■ ■ . F< x.a.z > » O < x.u)éri Parametrični X " )(( u. v ) ( u, v >« Il j , . u u( u . v ) z z( U. V ) ■ kJer sta u in v neodvisni spremenljivki ali parametra. Krožnica • ' Implicitni opis f ( . w > X* + a^ - 1 . O jParametrični opio P* so v raCunalniSkl srafiki prevladujejo parametrični opisir katerih predposti so na&lednie ' - oblika toloBa Jo neodviisna od koordinatnega iiiliätema> zato na J bi bila taka tudi matematična predstavitev, farametriCne metode zadofečaJo tamu pofloJu po definiciji. - pri parametričnih metodah ni težav pri neBnoličnlh funkcijah. Koordinate točke na ploskvi so izračunane neodvisno kot funkciJe parametr ov u in v. Vsak par < U'^. v^ ) določa natančno eno točko. - uporabnik lahko definira del Ploskve enostavno z izbiro območja za u in v a < u < b < u^,^ C < ,y < d < v^,, ). Če se oblika Ploskve ne da Izraziti analitično kot npr. sfera- valj itd.r moramo uporabiti konstrukcijski način. To pomeni» da moramo funkcijo dveh spremenljivk u in v memtaviti iz enostavnej6ih podatkov npr. iz točk. tanaentnih vektorjev (konstante) ali krivulj (funkcije ene spremenljivke). Obstajajo trije osnovni načini. s katerimi definiramo ploskev iz zaornjih podatkov i ali Q< u> . v ) =» ] * F < u. Vj ) v ) Ta metoda uporablja več informacij za definiranje ploskve» krivulje namesto točk» zato ima tudi oblikovalec ali konstrukter več možnosti kontrole oblike clonkve, vendar eri večJi kompleksnosti računanja kot tenzorski produkt. - transfinitne metode . ---->>7 12} - ploskve, dobljene s tenzorskim produkte;.; Q( u,v ) v ; ) U ( u ) V, v > J i»« il*» kjer vektor F'(u,v) =• (X Je ustrezna ploskev izračunana iz teh podatkov. I . '' točke ali >0 interpolirani z uporabo Iiiskretni podatki Pfujj tanaentnt vektorji» so utežnih funkciJ ali interpolant U|,«,(u), yj,i, oblikovali tako» da so definirali vzporedne preseke na vzdolžnih lokacijah. Ko so Jih določili» so tvorili vzdolžne krivulje. ki so Jih povezovale v eno samo tridimenzionalno obliko. Običajno so jih delali v naravnem merilu. Prostor v ladjedelnicah. k Jer so to delali» se Je imenoval 'loft'» zato so imenovali ta postopek povezave "loftinu". To Je bila bolj umetnost kot znanoiit» ker ni bilo (se danes Je ni) količinske mere» a katero bi merili zadovolJivost oblice. Odločitev Je individualna. Za definiranje ploskev uporabimo eno parametričnih krivulj i družino «(u. v) i P( U' v ) u ) Gl( u . v ) " P(ur »v > U. u ) > ' im t F ( u . vj ) U^^^ ( v ) - P< u ; I»» Transfinitne metode obliko kot podprte tenzorskeaa produkta» obsežnosti račnanJa. podamo več podatkov» želJeno obliko. Rezultat alsoritmov so ima^ večJo kontrolo nad ploskve ali Ploskve vedar pri 6e več J i Z.a opiu ploskve lahko ki natančneje določajo zvezne ploskve ali pa tudi enkrat ali dvakrat zvezno odvedljive ploskve. Pri prvih Je potrebno, podati le robne krivulJe» pri druaih pa tudi vrednosti odvodov ter meSanih odvodov (vektorje zvitosti). Za ploskve» dobljene s tenzorskim produktom» smo kot podatke uporabili le točke,j pri podprtih ploskvah pa smo podali krivulje, ki so podpiralo ploskve, IdeJa transfinitnih metod Je tvorba Etoolove vsote podprtih Ploskev v obeh parametričnih smereh. Ime so dobilo po "transfinitni ■ interpolaci ji » saJ lahko interpoliramo vsako točko podanih krivulj. Kriteriji presieda metod so bili hitrost odziva in enostavnost matematične predstavitve» zato Je bila na Prvem mestu metoda tenzorskeaa produkta. Osnovni podatki za to predstaiv-itev so točke. katerih Podajanje je seveda enostavneJSo kot POdaJanJe krivulj in tudi računsko Je metoda hitreJSa. kar Jo pomembno pri interaktivnem delu. Ostali dve ^todi pa imata več kontrole nad obliko in natančnejšo aproksimacijo. F'opolnl opiiü ■ TrantifInitrii ooìb Podprta ploiìkev Tenzoroki produkt 4. ZakJuCek F'b/navan,je raCunsk« ueümetri.je Jis pomembno ne liiamo Ita izdelovalce CAD/CAM proaramiike opreme, ampak tudi za uporabnike» da bodo za reftevanJe Bvojih problemov nabayl.Ì;L uiàtrezhe prosrame.' LITERATURA « >> <(2, <<3. C <<4, )) >> (d,)) I.ri.Faux M.J.fratti ' Computational ,' ' > Geometru for .Detiian and Manufacture» John Ulilea Sons, J979, ,, C.de Boor« A Pi-acticai' Guide " to Rplines. Sprinaei.....Verlau, 19713. RiE.Eiirnhill W.r.(oehm (edö)t Surfaces in Computer Aided - Cieometric [letiianr North-Hollandr 19ti:5. . FC.E.Barnhiil . R.F iRieisenfeld ( eds)«" ' Computer Aided Geometric Heciian, Academic F'réctiii». 19/4. <) U.Bòhm .G. Far in t . Surface Iiooiari r Eur oar ap hie Or 19133, ' <<6. >> W..!l.tìordon. • FV-eè. - Form Surface Interpolation thròuah Curve. Networksr General Motora Research Laboratoriem, } 1909. . ■■ <<7.>) a.Turk • Računarska arafikà, Školska; knJiaa - Zaareb. , < Siaaraph ■ ' ■ , ■ i (<9. >> W. J.Gordon « The. Mathematical Basis of' Coonti and Related Technique« for Free' - Form Surface Itefinitionr. Siaaraph 134. ■ . <) R.H.Kartell» J.C.Beatti; B.A.Barsiku ' s An Introduction to the Use of Splines in Computer Graphics, Siaaraph B4. <(11. >> S.Divjakt . Ra£unalni(tka ' urafika, Fakulteta za elektrotehniko, 1980. STRUKTURIRANO U ASEMBLERU PROGRAMIRANJE UDK: 519.682.8 HRVOJE NE2IC ELEKTROTEHNIČKI INSTITUT „RADE KONČAR", ZAGREB u radu je opisan način na koji se i u jeziku niskog nivo« - asembleru, može programirati strukturirano, tj. bez korištenja JUMP naredbi u izvornom tekstu. Za to je dovoljno imati makroaseinbler koji ima znakovne varijable i mogućnost supstitucije teksta. Strukturiranje programa izvodi se pomoću makroinstrukcija koje su slične instrukcijama grananja i ponavljanja u ADI i PASCALU. STRUCTUBED PROGRAMMING IN ASSEMBLY LANGDAGE The paper describes the way in which one can create structured programs, i. e. programs without JUMP instructions, even in low level language - assembly language. It suffices to have a macroassembler which includes character variables and text supstitution possibility. Structuring of the program is perform«!by macroinstructions which resembles branch and repetition instructions of ADA and PASCAL. 1. UVOD Prednosti strukturiranog programiranja u odnosu na nestrukturirano, u kojem se gotovo sva grananja i ponavljanja izvode korištenjem GOTO naredbi," so ožite. U nestrukturiranim programima obiSno postoji mnogo labe-la i mnogo medjusobno isprepletenih instrukcija skokova na te labele. Programirati na taj način vrlo je zamorno, jer je potrebno pratiti mnoi^e outeve grananja programa koji su medjusobno isorepleteni; programi su nečitki, nepregledni i nerazumljivi, kako za onoga tko ih je pisao, tako i za druge, što znači da ih je potrebno vrlo oosežno komentirati i dokumentirati. Osim toga,greške se vrlo lako pojavljuju i teško otkrivaju. Nasuprot tome, instrukcije grananja i ponavljanja u strukturiranom programiranju omogućuju pisanje programa bez korištenja GOTO naredbi. Time je izbjegnuta isprepletenost putova grananja u izvornim programima i postignuta čitljivost i preglednost, te lakoća programiranja i razumljivost programa. Takve konstrukcije grananja i ponavljanja slične su jezičnim konstrukcijama koje upotrebljavamo u svakodnevnom govoru, što znači da su bliske i prihvatljive čovjeku. Nestrukturirani program obično ima oblik niza instrukcija u kojem je vrlo teško uočiti pojedine dijelove koji predstavljaju logičke cjeline za sebe, dok su strukturirani programi podijeljeni na dijelove koje već na prvi pogled uočavamo, tako da odmah vidimo osnovnu strukturu programa (npr. dijelove koji se ponavljaju uvjetno, dijelov.koji se ponavljaju bezuvjetno itd). Primjeri viših jezika u kojima uglavnom nije mpgu-re strukturirano nrop-ra-niranje su BASIC i FORTRAN, dok su PASCAL, a pogotovo ADA .primjeri jezika koji vrlo dobro podržavaju strukturirano programiranje. Ipak, u većini dijalekata BASIC-a i PORTRAN-a moguća je bar minimalna strukturiranost, jer postoji osnovna IF ... THEN konstrukcija, kao i POR, odnosno DO petlja. Nasuprot tome, u asemblerskim jezicima strukturira-rio programiranje gotovo uopće nije moguće - obično postoje samo instrukcije bezuvjetnog grananja (JP adresa) koje izvršavaju skolc na odredjenu adresu i instrukcije uvjetnog grananja (JP uvjet, adresa) koje izvršavaju skok na specificiranu adresu samo ako je ispunjen odred jen uvjet, dok se inače izvodjenje programa nastavlja sa slijedećom instrukcijom (instrukcije uvjetnog grananja u asembleru ekvivalentne sa instrukcijama if uvjet then goto adresa u višim jezicima). Danas postoji prirodna težnja da se viši, odnosno srednji jezici koriste za razvoj programske podrške u što više područja, pa tako i u onim za koje se je donedavno upotrebljavao samo asembler. Anlikacioni programi pišu se gotovo isključivo u višim jezicima. Od pojave PASCALA i jezika srednjeg nivoa kao sto su 0 i KiRTH, visi i srednji jezici sve više prodiru i u područje sistemskih programa kao i u procesne primjene. Ipak, u tim područjima su viši jezici ponekad nedovoljno efikasni, pogotovo u procesnim primjenama u kojima se traži velika brzina rada ili zgusnutost koda. 0 takvim slučajevima je overhead koji unose viši jezici neprihvatljiv i nužno je korištenje aeemblera, a slično je i u sistemskim programima, gdje se obično baroa dio koda nora napisati u aaemblaru. Ukratko, upotreba aseablara joS uvijak ja dosta rasproatranjana unatoS tandancijl za aoanjivanjen. Kao éto Ja r»é ukasano, programiranja u asembleru ja gotoTO poava nastrukturirano. Valikin dijalon zbog toga rasvoj takvih programa ja zanoran i apor. Hakro-cBeablari «natno olakšavaju programiranje, ali sami po sebi obiino na pruiaju mogućnosti strukturiranog programiranja. 2. OSNOVNE IDEJE STROKTURIRAllOO PHOaRAMIBAllJA 0 HAKROASEHBLEBU Ovaj rad opisu ja iiaSin na .koji se strukturirano programiranja u asembleru moie postići upotrebom ma-kroasenblera koji podriava znakovne varijable i ima mogućnost supstltuaije teksta. Ta avojstva nisu baS uobiSajena za makròaseoblere, no takvi nakroasembleri ipak postoje. Jedan primjer je makroasembler za mikroprocesor ZS0 koji se nalazi u sklopu sistemsk* programske podrške Tektronixovog vièekorisniikog razvojnog sistema za mikroprocesore - sistema 8300. Ovdje ćemo ukratko opisati njegova svojstva koja . sa mogu iskoristiti, za strukturirano programiranje. Najvainije svojstvo je mogućnost dinamiike supstltu-oije teksta bilo gdje unutar bilo koje izvorno linija sa vrijeme asembliranja. Supstitucija teksta še vrši posredstvom znakovnih varijabli, tako da se ime znakovne varijable stavi pod, dvostruke navodne znakove (npr. "IME"). Kada asembler naidje na takvu pojavu u tekstu, on je zamjenjuje sa tekstom koji trenutno sadri! dotlSna znakovna varijable. Za vrijeme obrade neke linije teksta asembler najprije provodi sve naznaćene supstitucije teksta, a tek onda ispituje anaienje tako dobivenog teksta. Dlnamlćka supstitucija teksta omogućuje da se i eimbollćke adrese (liibele) kao i uvjetni i bezuvjetni skokovi na te labele generiraju dinainićki, tj. automatski, a da se uopće ne moraju nalaziti u izvornom tekstu programa. Razrada ove osnovne ideje pruia mogućnost strukturiranog programiranja u asembleru. Instrukcija stràkturiranog programiranja u izvornoo programu sa izvode kao makroinstrukcije, a pripadne ' aakroekšpanzije provode generiranje svih potrebnih labels i skokova..Hakroekspanzije. generiraju nove linija u tekstu. Neke od takvih linija sadrié samo labe-lu. Sto asembler dozvoljava. Da bi bilo moguće umetanje jedne konstrukcije grananja ili ponavljanja unutar druge 1 to ne samo na dva nego na više nivoa, potrebno je voditi neke nuoe-riSka varijable (npr. broj trenutnog nivoa). Asembler omogućava pretvorbu numerlćkih u znakovne vrijednosti, tako da ja moguća znakovne ekvivalante takvih varijabli ugraditi u generirane labele. Na kraju aponenimo svojstvo àsemblera da bilo koji -oakropozlv moie inati proizvoljan broj argumenata, jer pripadna makrodafinioijk nikad na aadr^ spaoifikaelju broja argumenata. Ovo avcijstvo koristi s« kod jadna ma-kroinstrukcija strokturiroaja. 5. PREGLED INSTROKCIJA STRURTOBIBAHOO PBOOHAMIHAWJA Ovdje odabrana lukroinstrukelja atrukturlraaog programiranja slišna su odgovarajućia inatrukoijaaa u ADI odnosno PASCALD. Da bi ae ta instrukolja razlikovala ed asamblorskih direktiva uvjetnog i ponavljanog asaabli-ranja koje su takodjer sliine, one imaju na kraju tri znaka >' , To ujedno pridonosi preglednosti programa, jar se makroinstrukoija atrukturiranja lAko razlikuju od aaemblerskih instrukcija. 3.1 Struktura IF ' Osnovna struktura grananja ima ovakav obliki «»j«». - . ! ELSETEST WHEN___uvjet KLSETEST VfflEN___uvjet ELSE . ENDir___ i slićna ja konstrukciji if ... then elsif ... then elsif ... then •la* CASE ond if n tSZ, pri fianu oakroinBtrukclj* ELSETTEST WHEH___Trijadnoat 1, TrlJ.doost 2, HHIM___u»J«t odgovaraju inatrukeiji «Islf ...... th*n. Xnotrukoiju IP___moì» «lUtditi proiBToljm broj paravo ELSETEST___, WHEN___(ili nij«d»n), lcoJ> Esoäa (ali ne mor«) alijtditi inetrukci J« ELSE___, Aogumoat u iMkroinotrukoiJa«« IF___1 ViHEd _ _ _ ooèo psprlaiti slijtdté* vrijadnostit Z, NZ, C, NC, P, H, EQ, NE, LI, QE. Moaiianioi Z, HZ, C, NC, P i M Jadoaki eà mnamoniciaa uvjata u instrukcijama aikroprocaaora ZR0 i osnajavaju stanja pojsdinih bitova o status registru, dok su ostali akvivalantni nakina od njih. Tako su akviTalantoi EQ («quel) i Z, NE (not aqual) i NZ, LT (lass than) i C, QE (groatar or aqual) i NC. Dio koda isa IF ___ instrukcija izvoditi ia sa samo ako je iopunjan specificirani uvjat, tj. ako aa odra-djsni bit statue registra nalaei u odredjenom stanju. Makroinetrukcija IF ___ generira uvjetni skok na dio koda koji poSinje sa ELSETEST ___ (odnosno ELSE ___ odnosno ENDIF ___) instrukcijom. Na taj dio koda aa akaio ako uvjet u IF ___ instrukciji nije ispunjen. Ako se u programu Seli Ispitati neki uvjet i ovisno o tome nsdto uraditi, potrebno je najprije isvriiti neophodne instrukcije CP, OR, AND, XCR, BIT itd, koje utjeiu na statua registar mikroprocesora, a isa njih postavlja a« Instrukcija If _ _ _ koja samo testira ođrodjoni bit status registra. Ako uvjot u IF _ _ . instrukciji nije Ispunjen iavođl 80 dio programa iansd ju ELBETEST___i W11EN _ _ _ instrukcija (naravno, samo ako one postoje). Toj dio koda obavlja testiranje nekog uvjeta, odnosno obnavljanje ntatus registra, a WHEN _ _ _ instrukcija tsotira odredjeni bit statua registra - ako je uvjet ispunjen isvodi se dio koda koji slijedi. WJEH ___ vrijadnoat I, vrijadnoat 2, .. WHEN__ OTHERS ENDCASE ___ Inatrukoi ju CASE___mCa ali Jediti proitvoljan broj ___instrukcija, pri Sam ae kao poaljadnja od njih aote pojaviti instrukcija WHEN___OTHERS. O ari« oatalla WHEK___naradbaoa aota aa Baiatiti prolevoljan broj argumenata (all baraa Jadan). Struktura CASE ___ provodi grananja ovlano o aadrlaju A ragiatra, sa kojia ae usporedjuju vrijednoati tadana u WHEN _ ^ _ naredbama. Zato aa prije CASE___, m ismedju CASE___1 prva WHIN___laatrukeija aorat. ju nalaslti naredbe koje pune A regiatar aa ialJeaoB vrijednoiiu. Arguaenti u inatrukcijaaa WHBI aocu inati numeriiku vrijadnoat koja na prelul 8 bita, Ili anakovBU vrljednoat od jedno; anaka. 3.3 Strukture ponavUanla Predvidjene su.. 1» atruktura ponavljanja i toi LOOP EXITL___uvjet 3.2 Struktura CASE Druga atruktura grananja takodjer ima oblik sličan analognoj atrukturi u jeziku ADAt EXm___uvjot ENĐLOOP BEPEAT EXITR ESITR DNTIL u»J«t . _ u»J»t, BXAHIHE ___ WHIU:___ uvj.t EXIW___ttvj»t EXIW uvjtt ENDWHIUS _ — * «HI1®1 _ __ Bxrrwii _ _ _ uvjet EXITWQ _ _ _ u»Jet IMDWHILBJ ___ ?rT« o4 Bjlh > atruktura bccuvjatnog poMtvlJaal», dok Je kod ostalih poMTlJanj« uvjatno. U Bvta OTia strukturana Isias Is patiJi onoguiuju pripađna OČIT naredba, kojih unutar avak« etruktura noZa biti preisvoljan broj (ili nijedna). Ovdje cu predvidjene dvije konstrukcije koje odgovaraju uobiSajenoj WHILE strukturi u vtSia jesieina. Kfad prve od njih naredbe ismedju EXAMINE _ _ _ i KHILB _ _ isvriavaju iapitivanje nekog uvjeta, tj. obnavljanje statuo registra, a sama WHIIÜ ___ instrukcija generira uvjetni akok na kraj petlje. Pri- ton instrukcija EHDVffllLB___generira besuvjetni skok na kod isa BXAMIHE ___ naredbe. Sto snaSi da se svaki put prilikom ponovnog ispitivanja uvjeta isvrfta-vaju dvije instrukcije skoka. Da bi se to isbjeglo, a u cilju i^atisanja ito véie efikasnosti koda,dodana Je fietvrta struktura (umeDonik: quick while), kod koje Instrukcija WHILES ___generira naredbu uvjetnog skoka na kraj koja se iitvodi sano pri prvoa prolasu, a ENDVffllLBl___generira uvjetni akok na poSatak, koji se isvodi nakoa svakisg prolasa. Hedjutia, abog toga ae kod koji ispituje uvjet aora nalasiti i prlja WHILE!} _ _ _ i prije ENDWHILBQ _ _ _ instrukcije. Ovime smo savriili predstavljanje makroinatrukcija ta strukturirano programiranje. Sada prelasiao na . opis realitaoije, tj. na detaljniji opis najina generiranja labela, skokova i ostalih instrukcija (u CASE___strukturi potrebno je osin labels i skokova generirati i COMPARE instrukcije). 1». QENEHIBAHJE UBH.A. SKOKOVA I OSTALIH IMSTRTOCIJA Najprije ćemo promatrati generiranje labela i oko- . kova unutar samo jedne konstrukcije, ne uzimajući.u ob» sir činjenicu da u programu moie biti viie konstrukcija Istog tipa, te da se konstrukcije oogu gntjezditi jed- ' na unutar druge. Ovdje je odabrano da automatski generirane labele mogu imati najmanje 't, a najviše 8 sna-kova. Naiin generiranja prva dva cnaka labela ilustriran je slikama 1 do 9, na kojima su prikazane sve konstrukcije (konstrukcija IF___, ENDIF _ _ dana Je u varijante) , kao i prva dva cnaka generiranih labela, ts generirani skokovi. Bezuvjetni skokovi prikazani eu punim, a uvjetni crtkanim linijama sa atrelicama. Prva dva znaka labele su potpuno ili djelomiino mnemo-niSka (npr. ÈT ima znaSonje"End then" ). Ostali znakovi labele ovise, izmedju ostalog li o nivou na kojem je dotiSna konstrukcija ugnijeidena u izvornom progre-' mu. 3ve labele koje au prikazane na olikama zapravo nije neophodno potrebno generirati Jer se na njih ne ska-Se (takve labele au npr. IF, WT, Wl, XI, X2, WH), no one mogu biti doata korisne u fazi ispitivanja programa. . Osim toga, neke instrukcije u nekim sluSajevima mogu generirati dvije labele, koje se odnose na Istu aeao-rijsku adresu. Tako je npr. na slici 1 labela ET potrebna zbog generiranja skoka na nju, a labela ti , (aneoonik "End if" ) generira se zbog boljeg pregleda pri ispitivanju prograoa. Ovdje ieno za strukturu I' _ _ _ , ENDIF _ _ _ detaljno opisati naSin generiranje avih labela i skokova, dok iemo za oatalo strukture oaao ukratko prikasati speoifiSnosti. 56 IF ET El IF---— ENOIF___ _______^ Silk» 1 IF ET El IF — I I I I ELSE ___ I I ENOIF _„ Slika 2 IF ET WT El Wl E2 EI IF. ELSETEST___ WHEN_______, ELSE TEST___ j -----' WHEN--- ----. I ELSE... ENDIF ... Slik« 3 IF ET WT El El IF... ______ I ELSE TEST I - WHEN ... ENDIF... I».! Struktur« IF Ako J« U¥j«t u inatriikoiji IF___ ispunjtn 1»= vođi ae dio programa koji slijedi, a ako nija tada o« izvodjenje nastavlja na labali ES (pripadnu labela ET generira prva od instrukcija ELSETEST___, ili ENĐIF ___ na istom nivou). Zato nakrolnatrukolja IF ___ najprije mora odraditi uvjet koji je suprotan speciflclranon uvjetu (apr. suprotni uvjeti eu Z 1 NZ, C i NC itd,) i tada generirati instrukciju alljadečeg oblika JP suprotan uvjet, ET Prva od instrukcija ELSETEST___ili ELSE___na istom nivou (ako postoji) stvorit £e slljcdaie dvije linije koda: JP EI ET Prva linija provodi bezuvjetni skok na labelu EI, tj. na zavréetak konstrukcije, jer nakon 6to sa itvede kod iamedju IF___i ELSETEST___odnosno ELSE___ naredbe, nastavak programa tMra slijediti na instrukciji iza GNDIF __ _ naredbe. Druga ELSETESI oarodba stvara labelu El, tre&a labelu b2 ltd., sve do labels E9. (odabrano je do parova ELSETEST ___, WIEN _ _ „ moie biti najviSe Svaka WHEN _ _ _ naredba stvara labelu 5ije je prvo slovo W, a drugo slovo jednako je drugom slovu labele koju je stvorila pripadna (a to znači prethodna) ELSETEST ___ naredba, te generira uvjetni skok (sa uvjetom suprotnim speclficlranoa uvjetu) na prvu sli jedeiu ELSETEST _ _ _ naredbu ako ona postoji. Ako je pripadna ELSBIEST___naredba ujedno 1 posljednja, tada WHEN ___ naredba geherlta skok na kod iza ELSE _ _ odnosno ENDIF___ naredb«. Da bi se to ostvarilo potrebno Je voditi varijablu KLST koju IF ___ instrukcija inioijallzira u 0, a svaka WHEN ___ instrukcija Je povečaVa ta 1. Kada je potrebno ta varijabla moie se it nuoarlSkog pretvoriti u sna-kovnl oblik (npr. u varijablu If) i tada se odgovarajute labele (ako je varijabla ve£a od 0) generiraju na slijedeći najin: ■Onjesto "Ili" tnakroasemblur uvritava u tekat trenutni sadržaj znakovne varijable TJt. Dok prva ELSETEST ___ instrukcija uvritava linije JP EI ET sve slijedeće stvaraju linije slijadećeg obllkai Slika U JP EI «"TIT" InstrukoljB WHI»___najprlj« geaerir« Ub.lu M"t0", catlB pevsf« ELST sa 1 1 obnovi 10, te generira liniju JP »uprotni uvjat, E'T^!" . Ako J8 ELST B 0 instrukcija ELSE ___ ganerira labelu ET, a inaia gsnarira labalu t'Tf". Inotrukeija ENDIF ___ ganerira labelu u oTisnoati o postojanju naredbi ELSETEST ___i ELSE ___. Zato ja potrebno voditi i varijablu ELS koju instrukcija IF____postavlja u 0, a ELSE___u 1. Ako.je ELS ■ 1 tada ENĐIF ___ stvara sano labelu EI, ako ja ELS a 0, ELST « 0, stvaraju se labele ET, EI, a U Blu«aju ELS - 0, ELBT > 0 labele E "TjS", EI. LP XI X2 EL LOOP... " I I EXITL .. EXITL ... I I ENOLOOP Slika 6 <».3. Struktura CASE CA W) CI CASE___ WHEN L. , I 10,21,235 ... RE XI UN repeat ... EXITR ... EXITR ... UNTIL I W2 C2 w3 c3 w« W5 EC WHEN... - WHEN ... WHEN... ENDCASE... 255,12 OTHERS I j ____y ....J .....J EX. WH XI X2 EW Slika 7 examine ... WHILE ... EXITW... Ex'lTW... ENDWHILE. ; I Slika 3 Siabolüke adresa i ovdje se stvaraju na naüin analogan onone koji je detaljno prikaaan kod pratr hodn« strukture. Za ovu strukturu je specififna upotreba COMPARE naredbi. Za svaki od svojih argumenata . osia aa sadnji, instrukcija WHEN ___ stvara naredbe CP vrijednost JP Z, Ci dok sa sadnji ar^ment stvara linije CP JP vrijednost nz, Ci fflja je i strukture, a broj VfflEN___ naredbe od poSetka j « 1 ♦ 1 . WO WL xi x2 Slika 8 WHILEQ ... I I EXITWQ ... I EXITWQ EO ENDWHILEQ II Slika q 68 I»,3. Strulctur« pon«»1.1an3« Polito es 1 kod ovih struktur« akokovl 1 labal« stvaraju na naSin analogan opiaanojn, ukratko ćemo opisati eamp tfHILB?___strukturu. Uvjet iadan u tffllLEQ ___ instrukciji ispituje se dvaput; jednom □a poietku, a drugi put na kraju konstrukcijo. Haredba WHILB?___stvara linije HQ JP supruvj, EQ HL a naredba ENDWHILEQ . - -JP uvj, WL pri Jeniu se uvjet ii VfHILEQ___naredbi pamti u jednoj varijabli, da bi ga mogla upotrijebiti i naredba EHDVIHILEtJ___. 5, RJEŽAVANJE PROBLEMA KORIŠTENJA VIŠE KONSTÜDKCIJA ISTOQ TIPA I PROBLEMA CiNIJEŽDJfJlJA Osneriranjo labela 1 skokova unutar samo jedne konstrukcije (koja se promatra kao cjelina sa sebe, aasevlsna od ostalih) Sto ja opisano u prethodnom tekstu, u suStini je priliüno jednostavno. Hedjutla, samo rježenje tog problema ne pruia mogućnost koristenja viSe konstrukcija istog tipa u iivor-nom proflramu, kao ni medjusobno gnijeidjenje konstrukcija jer u takvim sluJajevima labele Benerirane istim na-kroinstrukcijama na raznim mjestima u programu moraju biti ratliJlte i prema tome takvo rjeSenje samo sa sebe bilo bi od male koristi. Pretpostavimo ta trenutak da se ne dozvoljava gnijeidjenje, već da se konstrukcije u programu pojavljuju samo sekvencijalno jedna iza druge. 0 tom slućaju problem so moie jednostavno rijeSiti uvodjenjem varijable koja predstavlja redni broj odredjene konstrukcije poSevöi od poćetkB programa i uvrštavanjem znakovnog oblika ts varijable u sve generirane labele 1 skokove. Na po-Setku programa se ta varijabla postavlja u -1, a catla Je svaka instrukcija koja predstavlja poSetak odredjene konstrukcije povećava za 1. Sada svaka generirana labela pored već opisana prva do znaka sadrii-joS dva znaka - znakovni ekvivalent spomenute varijable. Npr. ako se u program najprije pojavljuje konstrukcija IF ___, UroiF___ona će generirati kbele IJ1(J0, ET0f> itd. Preostaja JoS rijeSiti problem gniježdjenja.Đa bismo ga riješili uvodimo varijablu NIVO koja otnaSava trenutni nivo fjiijeJdjenja u program. Na poietku prograna se postavlja NIVO • -1, a nakon toga poietna instrukcija svake konstrukcije povećava NIVO za 1, dok ga savrSna instrukcija svake konstrukcije smanjuje za 1. Prema tome, ako je trenutni nivo nà nekom mjestu u programu j»dnak -1, to znaJi da su do tog mjesta sve sapoćote konstrukcije i zavržene, ili da ih joS uopće nij® bilo. Ekvivalnnt varijable NIVO takodjer se uvritava u generirane labele x skokova i u taj oajlo se razlikuju labele generirane istim instrukeijaoa na raznim nivoima (iznimka je nivo 0 za koji Je ovdje odabrano da se broj nivoa zbog preglednosti as uneć« u labelu), Hedjutim, ni sa uvodjenjam varijable NIVO nismo u potpunosti riJeSili probleo. Jer unutar svakog nivoa «ole postojati viSe raznih konstrukcija koje as niiu sekvencijalno Jedna za drugom. Zbog toga za svaki nivo aora postojati varijabla koja broji konstrukcije na tom al-vou. Oznaćimo te varijable sa BR0, BRI, ... , BR9 (odabrano ja da nivoa moie biti najvläe 10). Zbog preglednosti odabiremo da se brojanje konstrukcija izvodi oa slijedeći naćin. Varijabla BR0, kako Je već prije opisano, broji konstrukcije na nivou 0 od poietka program. Za razliku od toga, preostale varijable broje konstrukcije na viSim nivoima samo od poietka pripadne konstrukcije na nultom nivou. Završetak svake konstrukcije na nultom nivou ponovo postavlja sve varijable BRI do BR9 u -1. PoSetna makrolnstrukcija svake konstrukcije povećava varijablu NIVO za 1, odredjuje njen znakovni ekvivalent N^ i obnavlja brojilo konstrukcije na trenutnoa at-vou naredbom AS£T BR"N^" t 1 . Labela se u općem sluüaju sastoji od slijedaćih polja (ispod svakog polja napisan je broj znakova}) Broj Trenutni Mnemonik konstrukcija na nivou 21 • nivo Broj konstrukcije na trenutnom nivou Peti znak (toćka) upotrebljava se zbog preglednosti. Ako je NIVO » 0 tada se Ubala sastoji samo od prva znaka, a ako Je NIVO > 0 «11 je broj konstrukcije na trenutnom nivou jednak 0 labela se sastoji samo od prvih 6 znakova. Takav naSin generiranja labela Je takodjer odabran zbog preglednosti. Dio labele od trećeg do osmog znaka raJednlSki Je sa sve labele stvorene od instrukcija iste konstrukcije. Taj dio ćemo nazivati ekatenzijon labele odnosno eks-tenzijom adrese. Ekstenzlju adrese Izraiunava poietna instrukcija koa-strukcije i sprema je u Jadnu varijablu (zbog aoguć-nosti gniježijeivjii konstrukcija mora postojati posebna varijabla za svaki nivo) da bi je mogli koristiti i ostali dijelovi konstrukcije. Napomenimo na ovom mjestu da takodjer zbog gnijeidjenja umjesto svake od prije opisanih varijabli EL6 1 ELST mora postojati po 10 varijabli - posebna varijabla za svaki nivo. Varijabl« koj» saidria «katueij* adreM oznažavuio' a» AEXTlS, ... , AEXT9- 8t« tnatrukelj» atrukturiranja ge-oarlrtkju label* i akokowt' tato da vastjabliii AEX1 pri-druia vrljadnoat «katanKij» adree« na. trenutnom nlinoui:: AEXT AßET' ABX®"N/J"' 1 satlD ST« labsl« obüiikuijw na> awbji nailn: Mnemonik "AEXT". Na kraju naponenisio da prlje btl«' kojl« makrolnstruk-elje strukturiranja u prograoui mon» do6i instrukcija BJXIIH___koja postavlja varijaDl» NIVO, BR0.....BB9 jednakim -1. 6. ZAKIJnČAK Opisani naSin strukturiranog programiranja u aseo-bleru realiziran ja na Tektronixovom sistemu Strukturirano programiranje omogućuje skup od 28 mak-rodeflnicije sa oko 31^ linija koda (korisnički programi direktno mogu za strukturiranje upotrebljavati 21 nakrolnstrukciju). Ovakav naSin strukturiranog programiranja, naravno, povećava vrijeme asembliranja programa u odnosu na nestrukturirano programiranje, jer se simbolićke adrese i skokovi stvaraju za vri^me asembliranja a zà to je potrebno odredjeno vrijeme (svaka makrodefinieija strukturiranja sadrži viSe naredbi). To je naravno Jedna od mana ovog naSina, no autoru se £ini da su koristi mnogostruko veie, o iemu je već bilo govora u uvodu. Realizacija pomoću makrolnstrukcija, odnosno ma-kroasemblera nije jedini naćin na koji se opisani model strukturiranog programiranja u asembleru moie realizirati. Najprirodnija mogućnost je realizacija unutar samog asemblera, pri iemu bi instrukcije strukturiranja imale oblik asemblerskih direktiva, a moguća je i realizacija pomoću programa napisanog npr. u nekom vlRem Jeziku, koji bi instrukcije strukturiranja u izvornom tekstu zamfienio labelama i skokovima i na taj način formirao novu datoteku iiji je sadržaj prihvatljiv i« asembier. Instrukcije strukturiranog programiranja oslobadja-Ju programera od zadataka stvaranja labela i skokova, pri iemu on i dalje ima potpunu slobodu u koriStenJu Instrukcija asemblera za stvaranje efikasnih programa. Ipak, opisana realizacija ne pruia jednaku efikasnost koda kao kod direktnog programiranja u asembleru, jer sa u aekin sluSaJevioa (primjer-slika 10) prijenos kontrole programa na odredjeao mjesto vrii sa viSe skokova, umjesto sOi samo J^dnla skokom ill RETT instnikcijom. W W Boir ELSE DTOir___ Slika lit Medjutim, u pobòlJSaneJ raalisaoljl •vi pvottU*- mi mogu rljediti 1 na taj naSia ganeriraai kedi boS* biti Jednako efikasan kao oàaj proistMdieai dtoaktiw u> asembleru. LITERATORA 1. - I 8500 Nodular HDIi soria* assembler eon users naaual for B^ series aaseablers, Tektronix, lac. Beavertda, Oregon, 1985. 2. P. Wegaeri Programing with ADA<„ Englewood Cliffs, N. .«^ntioe Hail, 1980. DOPATAlt tr dodatku rad«, Imo iluatraoije, dan j* kratki pot-{Togram sa daolMln« binarnu pratrorbu 8-bitnog broja. Majprijs je dan lavorai oblik, a satla oblik aa autoBatski geaerlranlfl labalaoa 1 akokorloa, koji □tvGra aakroaecabler. BBCBIH BEOIH___ LO C,02 ID BL, BIN U) A, , A,D 08 A Btm___Z DBC C SNDLOOP ___ DBX; 0 SXITL___Z RED ENDLOOP ___ RET EVOO.l CP UK ir___OE IFOO.IOl JP C.KIOO.lOl SOB 06 ENDir ___ ETOO.lOl EIOO.lOl 8BĐ LD A,D OB A EXITL___Z XlOO JP Z,EUX) DBC C EMDLOOP ___ JP LPOO EU» LOOP___ LPOl DSC C EXITL___Z XlOl JP Z.ELOl BSD EHDU»P___ JP LPOl SLOl Bsr DBCBIM BEQIH ___ Ut c,02 U> HL.BIN LD A.(BROJ) LOOP___ IfOO LD D.OO EXAMINE ___ SXOO.l . CP 16H WHILE___QE WHOO.l JP C.EWOO.l SOB 16B DAA INC D SNDWHILE ___ JP EXOOa KOMUNIKACIJSKO USMERJEN INFORMACIJSKI SISTEM ZA UPRAVLJANJE S , P R O I Z V O D N J O - I B M CO P.l CS VLADO STARIČ UDK: 681.3:007 IMV, NOVO MESTO COPICS pirEjdstavlJa način reševanja k omun i kac: i Jsl< i h problemov v proizvodni delovni organizaciji. COPICS koncepti so usmerjeni na izdelovanje , in povezovanje proizvodnih aplikacij. Niso pa neposredno povezani z drugimi področji itvami ) - implementiranje (izdelava podrobnejših Planov glede na glavni plan) -■- nadziranje (nadzor izvajanja planov in avtomatično opozarjanje odgovorne službe na odstopanja ) 2.1. F' 1 a n i r a n j e. F'lanirarjje se deli na strateško in takt.ično. COPICS se s strateèkim planiranjem ne ukvarja. Pri taktičnem planiranju pa pomaga pri vsakodnevnih odločitvah ( raz-poreditev delavne sile, proizvodni plan, določanje zalog itd.). C'elika pomoč pri planiranju je simulacija. Na ta način lahko dobiiyio odgovore na vprašanja kot so 5 — Kako vpliva sprememba :i. zdelka na str 0'like? — Za koliko bo nova strojna oprema znižala proizvodne stroške ? — Za koliko se zmanjša cc^loten i zdel o va liii ' čas, če zmanjšamo zasedenost določenega stroja ? Simulacija pomaga reševati tudi probleme pri spremembi proizvodnega p!l.ana. . Planer dobi rezultate simulacije že v ' nekaj minutah. Prikazani so lahko številčno ali v obliki diagramov. določenega proizvodne uva Jan de tehnoloških 2.2. Implementacija Med uvaJanJorn plana nastonljo razne spremembe. Informacije o teh spremembah moraJo čim hitre^cie priti do odgovornih delavcev. COPICS nudi pri implementaciji 'eledečo pomoč« - Ümo£9aCa prealed vplivov delovnesa naloaa na zmoalJivoBti. - ZasotavlJa pravočasno konstrukcijskih in sprememb. - Omosoča kontrolo potrebneaa materiala in orodij. - Prikazuje prealed delavnih obveznouti in proizvodnih aktivnosti. - Omoaoča pisanje delovnih nalosov. 2.3. Nadziranje Bistem nadzira planirane aktivnosti in odkriva nepravilnosti, kot bo« - Na naročilu za nabavo Je napačen datum dostave materiala. - Nastopil Je zamtpj v proizvodnji. - Količina izmeta Je povečana. Sistem reSuJe nepravilnosti na sledeči način« - V računalni&kem spominu so shranjene vrednosti vseh nadziranaih veličin. Glede na razliko med predpisanimi in dejanskimi vrednostmi se sistem odloča. COPICS nudi tudi Pomoč pri razfiiritvi predpisanih vrednosti. - V spominu so shranjeni tudi ukrepi v slučaju nepravilnosti. Sporočila o ukrepih PoftilJa odsovornim osebam preko terminalnih enot. 3. GL.AWN1 CILJI SISTEMA - prilaaodlJivost spremembam - zmanJfianJe zakasnitev - učinkovito upravljanje 3.1. Prilagodljivost sistema Info, sistem Ja tako oblikovanr da sa Je moaoče prilasaJati zunanJim spremembam. Vzroki za spremembo Sistema so lahko« - spremembe na trliiču - uvaJanJe novih proizvodov - sprememba oraanizaciJs podJetJa - sprememba zasedenosti delavnih mest in s tem druaačen način dela COPICS vse podatke shranJuJe v banke podatkov. T» banke so tako organizirane, da niso odvisne od uporabniških računelniftkih proaramov. Odpravljena Je dvojnost podatkov in s tem zmanJAan čas pristopa do podatkov. RoorsanizaciJe banke podatkov zaradi novih uporabniških proaramov ne vplivaJo na stare proarame. 3.2. ZmanJfianJe zakasnitev COPICS doseaa ta cilJ na dva načina« - obdelava podatkov v realnem času - mrežna obdelava sprememb Obdvlava podatkov v realnem času pomeni« - Podatki potuJeJo med terminalno enoto in računalnikom po telefoski liniJi ali koaksialnem kablu, podatke lahko preko računalnika poftilJamo tudi od ene do druae terminalne enote. Tako podatkov ni potrebno več pisati na papir in prenaitati ročno. - Spremembe vne&ene preko terminalne enoto ao takoJ zabeleiene v računalniškem spominu. Aturirani podatki so stalno na razpolaao na masnetnih spominskih enotah. -- Sistem posreduje informacije preko terminalnih enot brez običajnih zamud zaradi prenaSanJa dokumentov. Mrežna obdelava «prememb« - iäpremebe podatkov» ki so nastal« v katerikoli točki sistema, COFICS takoj obdela. Prilasodltvo Planov se lahko na ta način Izvedejo v vsakem trenutku. 3,3. Učinkovito uoravlJanJe COPICS powasa pri vodenJu proizvodnje na sledeče načine« - SmulaciJa končnih učinkov sprememb, - l.)odilniffl delavcem omoaoča prwaladen nadzor, - Možen Je hiter vpooled v banko podatkov, Mnoso setankov in telefonskih posovorov ni več potrebnih. 4, PODROČJA UPORAßE Celoten COPICS informacijski sistem i» razdeljen na 13 modulov, ki so namenjeni različnim službam v delovni oraanizaciJi, 4,1, Upravljanje s tehnično-tehnoloikimi podatki V proizvodnih delavnih oraanizaciJah J> zelo važno, da so ažurni podatki v sestavnicah dostopni v vsakem trenutku. Pri uva JanJu noveaa proizvoda, ki Je podoben kateremu od obstoječih, nastopi problem kopiranJa, sestavnice obstoJečeaa proizvoda. Taka probleme pomaaa reSevati COPICS. CilJi« - Kreirati in vzdrževati tahnlčno tehnološke podatke. - Hožnost dostopa do podatkov za vb» službe v vsakem trenutku. FunkclJe« - Kreiranje in spreminjanje banke podtkov preko ekrana in paketno. - Prikazovanje sestavnic (na ekranu ali izpisano na paoirJu) t - modularno (prikaz samo tistih delov, ki so varaJeni v določen sklop v eni proizvodni stopnJi> - strukturno (prikaz strukturo proizvoda i vsemi deli preko v«i»h stopenj > - količinsko (prikaz vaakeaa dela samo enkrat s skupno količino za določen proizvod) - vsi naSteti prikazi z uporabo izbirnih poaoJev ~ Prealed potreb (na ekranu ali izpisano na papir Ju > « - modularno (prikaz vseh komponenot v keterih Je določen del neposredno vara Jen ) - strukturna (prikaz stopenJ varadnJtt vseh komponent v kater* >e del vara Ju Je > - količinsko (prikaz skupn» potrebne količine vseh komponent v kater« a» del varaJuJe) - vsi naSteti prikazi z uporabo izbirnih PoaoJev - Za vsako sestavnico Je možno shrenitl več variant. - Kontrola pravilnosti podatkov in »topn.lu vsradnJe. - Kopiranje sestavnic. - Prealed stanJa tehničnih spramemb »u datumu, statusu itd. - Prikaz matičnih podatkov o Materialih« 4.2. Naročila kupcev TržiftćB ceni poles uotrezne.kvalitete ih usodne cene tudi efcktivnoet pri obravnavanju naročil. V/eliko kupcev dodatno PoistavlJa zahteve slede prejemnika, cene. dobavnih PosoJev, Plačilnih posojev itd. T« prosramoki modul omogoča obdelavo naročil o centralno kontrolo v vsaki fazi obdelave in vposled v trenutne podatke. Cildl» ■ , - Omogočiti, hiter odaovor na vpraSanJa v zvezi a Standern naročila'. Funkcije« - interaktivno dodaJanJe.. vzdrževanje in • vposled v podatke o kupcth. izdelkih in naročilih. — Interaktivno doda Jan Je. vzdrževanje in vpogled v »tandardne tekotualne podatke in pozicije v naročilu. - Ekranaki prikaz podatkov ó kupcih in izdelkih izbranih po določenem kriterijih.. - Ekraneki prikaz mtanJa • naročila po 4tevllki naročila, oznaki kuPca ali : izdelka. ' . ^ - . ■/ -- - Paketno kreiran Je . banke: po'datkovt - kupcev ' - naročil - izdelkov ■ — tekstov " - Paketno vzdržeVanJe bank . podatkov o izdelkih in naročilih. - Analiza otanJa naročil po različnih kriterijih. ; •^ - Avtomatsko d.odaJanJe Številke naročila. - Obdelava ötirih tipov naročil« . - posamična - pogodbena. - odpoklici iz pogodbenih naročil - ponudbe - Obdelava.dveh tipov dobavi , - takoJàna dobava - dobava v prihodnoKti 4.3. Napovedi Vse proizvodne delovne /organizacije ^ se ukvarja Jo z različnimi metodami napovedovanja bodočih dogodkov. "ČOPICS-ov programski modul za izdelavo napovedi analizira pretekla povpraševanja in.določa model za napovedi CilJi« -V': - .Glede na tor da napovedi ne nioreJo (biti nezmotljive. Je cilJ tega. programske»«,: modula vsaJ izboljšati napovedi glede na "trenutno uporabljeno tehniko ih določiti tudi meJe natančnosti napovedi, .. Funkcije« ' ' . - Pretvarjanje podatkov v obliko primerno za izbor modela.' - Spremljanje odstppanJa podatkov povpraševanja .od izračunane. povprečne vrednosti in . opozàpJanJe , ha nenormalnosti. ■ - Po želJi izračunavanje vrednosti prometa materiala. - Izpisovanje liste izračiinanih rezultatov za ugotavlfanJo potrebnih korekcij. :. - Izračunavanje vrednosti ; prvesa in. drugega 1 zgla Jevan Ja .'• - Izračunavanje baznih indeksov za sezoske ■ artikle,. ■ - Izpisovanje napovedi v obliki tabele ali ■ diagrama./ 4.4. Glavni plan proizvodnje Glavni Plan proizvodnje! vsebuje Planirane količine izdelkov datumsko porazdeljene. CÖPICS omogoča tudi korekcije Plana ih pomankanJe določenega materiala. V ' večini delovnih organizacij delovni nalog največ časa čaka na pb.delavo. CilJl« - Cim Hirtii.ifto vmeene za lose med dvema delovnima operacijama. - ZmanJ6anj» Izdelovalnih £air>ov, - Ćlm vnt'-M i/kopÌEitek sitroJr»? opreme, FunkciJet - Planiranje potrebnih zmooljivoati - interaktivno doloćenJe datumov laiüetka operaci.! - usjotavlJanJe vièkov ali manjkov /moalJivoati ~ izpiiii PoroCil o zaBtìdenooti /moaljivouil - izpio poroCil o »tanJu delovnih naloauv - Planiranje razpisia delovnih nalosov - doloCanJe prioritete delovnih nalosov in datumov razpiea - ocenjevanje Casa zaklJučitve delovnih nalosov - kreiranje banke podatkov o Planiranem vrotnem redu razpidia na i oaov - liimuliranJe »prememb zmoslJivooti in razporeditve nalosov ~ TerminiranJe delovnih operacij - izraCun prioritete delovnih operacij - kreiranje banke podatkov o vr»them redu delovnih operacij - prikaz Planiranega i^.poredJa operacij na ekranu in Izpia na papir preko ekran«>ke»a terminala ali pa Js rac':i.inalnif.ki spomon povezan b CNC obdelovalnim str o Jem, Cil J« - ZasotavlJanJe Planirane proizvodnje. - BolJža koordinacija med proizvodnim in" planerekim delom. - Povečanje učinkovitosti proizvodnje i nepoörednim nadzorom In računalniftki« krmiljenjem otroJev. Funkcije« - ZapiaovanJe vseh premikov delovne «ilo v obratu. ~ Interaktivno aiuriranJ» potreb po materialur dostave in izdaj» iz skladiAč. - Elkranaki prealed in sprememb» dokumentacije. - Interaktivno opreminJanJe razporeditve dela . - PoftilJanJe oporoCil delavcev preko ekrana (zmanjkalo materiala^ ni električne enersiJer delo uispeAno opraviJeno ). - Interaktiven doutop do navodil r.a izvajanje kontrole in rezultatov kontroliranja, - Avtomatsko opreJemanJe podatkov o stanJu otro Ja preko senzorjev na »troJvj. y olučaJu uporabe CNC otroJev p« tudi računalnidiko krmilJenJe. A,7, Odpiranje in razpia delovnih nalosov Prosramuki modul za razpits delovni nalosov povezuJe uistem Planiranja d siiiitemom izvràevanJa. Delovne nalooe Je potrebno odpreti in nato èo razpiiaati. Rezultat odpiranja Je rezervacija materialov. katerih potrebo usatovi Prosram na podlasi «eutavnice. V' trenutku razpisa pa kontrolira razpolotlJivost materialov in tiska delovno dokumentacijo. CilJi« ~ Poskrbeti Je porebnor da se vsak delovni nalog razpiäe na planirani datum. ~ Prekontrolirati razpoložljivost potrebnega materiala. orodij in delavniäkiti risb za razpisani nalos. Funkcije« - Kreiranje in vzdrievanJe banke podatkov o delovnih nalosih. ~ Identificiranje delovnih nalos. ki Jih Je potrebno razpisati. ~ Odpiranje nalosov preko ekranskesa terminala. - Razpis delovnih nalosov s kontrolo razpodoilJivosti materialov. - Priprava delavniSke dokumentacije. - Interaktivno vzdrievanJe razpisne dokumentacije (količina.' datum, lokacija, brisanje, zapiranje). - Interaktivna odsovori na vpraftania o statusu delovnega nalosa. 4.<3. Nadzor in upravlJanJe z obrati hnoso teiav v obratu nastane zaradi nepravilnega ali zakasnelega planiranja. Uooraba COPICS modulov za planiranje proizvodnje in razpis delovnih nalosov zmanJèa to tetave. Vendar klJub dobremu planiranju lahko nastopi Jo teiave v proizvodnji (napaka na strojni opremi, nepredviden, izmet). Vse naütete teiave pa povzročijo zakasnitev zaključka delovnega naloga. CUPICS-ov modul -Nadzor in upravlJanJe z obrati- zmanJ&uJe te zakasnitve o pomočJo povratnih informacij iz proizvodnje. Te informacije vnafta delavec 4,9. Vzdrževanje strojne opreme Proizvodne delovne organizacije veliko sredstev vlasaJo v stroJno opremo, C0PICÌ3 pomaaa podaljševati iivlJensko dobo in razpoložljivost' BtroJne opreme. Na ta način Pa se zmanJöuJeJo tudi proizvodni stroAki, CilJi« - Cim bolj zmanJftati fttevilo okvar «troJn« opremo s čim nižJiml utroèki vzdrževanja, Funkcije« ~ Pomoč pri izdelavi standardnih postopkov za vzdrževanje otroJev, - Avtomatska izdelava časovne razporeditve preventivnega vzdrževanja (čim manJ okvar s čim manJ4i(di «troiki vzdrževanja ). ~ Priprava delovnih nalosov za vzdrževanje. ~ Vzdrževanje banke podatkov o r»ze»rvnih delih. - Vrednotenje vzdrževanja in izsub zaradi neuporabnosti strojne opremo v času popravila. - Poročila o vzdrževanju (oznaka in naziv stroJa. čas. opis poravila. rezervni deli ), 4.10. Nabava in prevzem Mnoge delovne organizacije ne pobvečajo dovolJ pozornosti nabavi in prevzemu. Kompleksnost in zahtevnost Planiranja in krmilJenJa proizvodnjo Jo velika bolj očitna. Vendar pa nastane veliko problemov v proizvodnji prav zaradi zakasnele dobave ali neustrezne kvaliteta materiala. CUPICS pomasa zagotavljati potrebna količino in kvaliteto materiala ob pravem času, CilJi) - Seznaniti nabavo z vsemi podatki o dobaviteljih. ~ Popis vsesa preJetesa materiala. - Zbiranje podatkov o kontroli prvvzetesa materiala. Funkcije« - Kreiranje in vposled v banko Podatkov o dobaviteljih In materialih» kl Jih ti ponuJaJo.' - Izbiranje dobaviteljev alede na nJlhove karakteristike . - Ekranski nadzor« - naClnov nabave - zahtevkov ponudb - naroČil prl doloCeno« partnerju " - materialov v konslanaclJi - IiPl» naroČil nabave, zahtevkov za ponudbe, statistik in PoroCil. - Paketno brluanJe neaktualnih podatkov z možnostjo shranjevanja na masnetnl trak. - Ekranski vnos podatkov o prejemu. - Kreiranje in vposled v banko podatkov o kontrolnih zahtevkih pri prevzemu. - Zasledovanje glbanJa prejetega materiala do konCneaa vskladifiCenJa. 4.11. Upravljanje a skladidCi Ta COPICS-ov prosram oe -ukvarja problemi skladiftCenJa (določanje nove materiale, evidenca razmestitve, iskanJe materiala). s fizičnimi prostora za prostorske CllJli - VzdrlevanJe kontrole nad vsemi zalosaml v delovni oraanizaclJi. - ZmanJAanJe sibanJa : materiala med skladiiSCi. - ZmanJiSanJe strofckov okladlftčen Ja. Funkcije« - Kreiranje banke skladlACnih podatkov p materialih. - Ekransko beletenJe vsakesa premika ma t er1a 1a . - Izpl» liste Iskanih PoziciJ (material, lokaclJa.i količina),na osnovi ekranokesa vnosa naloaa za dvig materiala. - Avtomatsko doloCanJe prostora za nòve materiale. - Kontrola stanJa ' na- skladldCu preko ekranskega terminala. 4.12. Planiranje in upravlJanJe s stroftkl Za pravilne finančne ' odMčltve Je potrebna dobra analiza stroftko.v proizvodnje. Odsovoriti Jo potrebno na vpraöanJe, kollkftni so bili . in kollkftnl bodo stroèki za vsak izdelek ter kJe se poJavlJaJu nepravilnosti In kako Jih odpraviti. Pomoč Prl odsovorlh na ta vpraöanJa nudi COPICS. . . ' • CilJi» ■ . ■ - Pomoč finančnim službam pirl izračunu stroitkov proizvodnje In pri odločanju. Funkcije« - Shranjevanje stroAkov (materiali delo, retiJa) po nivoJih v skladu s sestavnic o. - Obračuni planiranih in stvarnih stroikov Interaktivno In paketno. .- Interaktivno in paketno vzdrževanje podatkov o «troikih. - Ekranska simulacija predvidenih sprememb In obračuna. ' . ■ - Interaktivni presiedi sibartJa strofikov ter primerjava Planiranih in stvarnih stroikov. prenos sporočil. OmoaoCa prenos podatkov med uporabniki in računalniškimi uroar'ami, mh?d posameznimi uporabniki ali med posameznimi prosrami. Ta proaramskl prol/vod ni omeJen samo na COPICS proarame, ampak sa lahko vključujemo tudi v nove uporabnlžke proarame. CilJi« - F'ospefievatl Izmenjavo informacij z uporabo terminalnih enot in brez prenaftanJa dokumentov. - ZmanJÄanJe naporov in materialnih stroškov pri spremlnJanu sporočil. Funkcije« - Kreiranje, prikaz, spreminjanje in poöllJanJe sporočil preko terminalnih enot. - Usmerjanje sporočil med uporabniki. ~ Povezovanje z interaktivnimi prosrami za obdelavo nekeaa sporočila. - Aktiviranje uporabniškega programa alede na vnaprej določen doabdek (časovna točka, časovni . interval, dosea podatkov ). sporočil In na zahtevo ekranu po datumu in - Shranjevanje prikaz na prioriteti., - OnemoaočanJe dostopa do sporočil nepooblaščenim osebam. 5. POOOJI ZA UVEriBÜ COPICS SISTEMA Za uspešno uporabo komunikacijsko usmerJeneaa sistema COPICS moraJo biti izpolnjeni določeni poaoJi. To Je še toliko bolj pomembno za tiste uporabnike, ki se prvič sreCuJeJo z obdelavo podatkov v realnem času. 5.1. Vodilni delavci Uspešnost računalniško podprteaa sistema Je odvisna od teaa kako vodilni In vodstveni delavci sodeluJeJo pri definiranju, uvaJanJu in uporabi sistema. Od nJih se zahteva« . ~ poznavanje načina obdelave podatkov v realnem času - sodelovanje pri definiranju cllJev sistema - zasotavlJanJe dovolJ velikih zmogljivosti delovne oraanizaclJe za dosesanJe predvidenih cllJev - organiziranje učinkovitesa .uvaJanJa računalniško podprteaa informacijskega sistema S.2. Izobraževanje Zelo važno Je, da so vsi uporabniki seznanjeni z možnostmi sistema in načinom uporabe. Izobraževanje vodilnih ' delavcev nà'J vodlJo. delavci iz računalniške obdelave podatkov ali zunanji sodelavci. Vodilni delavci pa na J potem predstavijo sistem svojim podrejenim. Potrebno Je tudi seznaniti vse uporabnike z načini oporabe terminalnih enot (ekran, tastatura, pisalnik >. S.3. Strojna računalniška uprema . Računalniki za Paketno obdelavo podatkov se lahko z dodatnimi enotami za kontrolo llniJ, razširjenimi zmoalJlvostmi spomina in terminalnimi enotami UPorablJaJo za delo v realnem času. . 4.13. prenos sporočil to Je COPICS~ov proaramtiki modul, ki omogoča - Terminali Pitrebni so za vnos podatkov In prikaz rezultatov računalniških obdelav. 2« vnoQ ao rifimerne taistaturer maanetne karticts In avt?llobna nereoa. Za prikaz pa ekrani in matrični piBalniki za izpie «lanjiJih količin podatkov. - Spomin Razi&iritev alavnoa« spomina .ie potrebna zaradi dodatnih krmilnih programov in več uporabniških proaramov. ki ae iB'toČBno izvajajo. Ker mora biti veliko 6tevilo podatkov dostopnih v viuakem trenutkur moraJo biti ti podatki shranjeni na magnetnih diskih. - Računalnik V CÜP1CS oiotemu ni potrebno, da oo vsi podatki fihranJeni na centralnem mestu, lliel podatkov in funkcij Je lahko razporejenih po manJfiih računalnikih, ki so preko komunikacijski lin i J povezani s centralnim. Ti računalniki so uoorabni tudi za direktno krmiljenje obdelovalnih »troJev. - Ali mora biti obdelava v . realne« čai»u centralizirana? To vpraäanJe se poJavlJa pri opravlJanJg določenih obdelav za lokacijsko ločene obrate. F'otrebno Ja analizirati otroèke za komunikacijske liniJe. dodatno računalniško opremo in primerjati hitrosti obdelav. UvaJanJe določene»* informacijskega suatema Je lat Je. £e Je računalnik na lokaciji uporabnika s i st e-ima . - Kolika časa traja uvaJanJe? Motno Je uvaJat.i več moduloV/ COf'ICS-a istočasno, '.'endar pa uva Jan Je vseeno tra Ja neka J let. Oevada pa sistem ni dokončen. Z UPorabo novih načinov dela in izpopolnjevanjem opreme moramo spremeniti tudi informacijski sistem. Ö.4. F'rouramuka oprema Sistemi za delo v realnem času zahtevajo bolJ zapleteno sistemsko prosramsko opremo kot Raketno orientirani sistemi. Podatki se prenaftaJo med enotami brez računalnifikesa operaterja. F'odpora sistemakih proaramov Je Potrebna na naslednjih področJih« - Operacijski sistem mora omogočiti istočasno izvaJanJe več poslov. Napake pri vnosu podatkov Je potrebno uuotoviti in po možnosti odpraviti avtomatsko. Potrebna Je tudi statistika zasedesti računalnika. - Banke podatkov tU/l (Data Lansuase) sistemski proizvod Je potreben za sestavo in vzdrževanje bank podatkov. Sprememba orsanizaciJe banke podatkov v okviru eneaa uporabni&keaa proiarama ne vpliva na definicijo drusih proaramov. - Komunikacije Za vzdrževanje komunikacij med posameznimi terminalnimi enotami in računalnikom Je potreben sistemski proizvod CICS/VS (Customcjr Information Control Sistem / Virtual Storaae), Omosoča ponovno vspostavlJanJe komunikacij v primeru prekinitve in preprečuje dostop do podatkov nepooblailčenim delavcem. S.S. UvaJanJe CCJPICB-a Pri uvaJanJu CÙPICS informaciJskeaa sistema se navadno po Javi nakaJ vprafianJ. -- Ali Je potrebno uPorabniSke proarame naJpreJ izvajati v paketni obliki potem pa Aele v realnem času? Tehnike proaramiranJa là paketne obdelave in obdelave v realnem času se med seboJ zelo razllkuJeJo. Težko Je pretvarjati proerame iz ene oblike v druao, Večinoma Je naJbolJe'. da se takoJ uporablja prouramcs v realnem času. Za obdelave. kJer Je količina vhodnih podatkov velika, rezultati pa niso potrebni v ' nekaJ sekundah. Je primernejša paketna obdelava. naslednje 6. 0CE:NA UPDF 1 iiitvi-f J' C iiT^rr« t'out»—. • tìiTllVi»--! „i;ra.nir..l iniij . __ IJIU^-'-l-Ti n;.rrr--1 Ipi.il.l« A I 1—1 ___, I- —— —*^Shi7l.clo bui.l.k' C—Ocl.U. in(..|-tjii. k"- Ui't JI:__ I i-—[ìilù.uut. Slikil S. Ojačevalnik lii ol)l Ikovaliiik poilal.kuv (ival iv.ifan ■/, JiiLclovim 7.?.\"l l''SÄ) "boot-loop register"'ima pomembno nalogo pri obojestranem prenosu podatkov med gostitelJ-skim računalnikom in pomnilnikom. 160 bitni' register C7D vsebuje Informacijo, ki natanCno podaja konfiguracijo dobrih In slabih zank v ustreznem kanalu vsakega MMP, Vsakemu bitu registra odgovarja daloCena minor zanka v pomnilnlSkem Clpu (npr. v Intelo-vem eipu 71U s kapaciteto 4 Mbitov). Pri prenosih podatkov skozi vhodno/1zhodne registre MMP se med tiitanjem s pomoöjo vsebine "boot-loop registra" upoštevajo slabe zanke. Med vpisovanjem v MMP element se nanireC vpisujejo nitSle na vse tiste lokacije bitov, ki odgovarjajo slabim zankam. Tedaj, ko je omo-goäena korekcija napake, vsebuje "boot-loop register"^ natanko 135 enic pri 270 dobrih zankah na' kanal mehurBnega pomnilnika. V bloku korekcije napak je uporabljena posebna 1A-bitna "goreöa koda", ki Je namenjena detekciji in korekciji napak, fle upor.ibnik o-mogoCi proces detekcije in korekcije, poBHbno vezje za korekcijo napak doda na koncu vsakega 25<) bitnega bloka, ki med vpisovanjem potuje skozi FIFO register,. Se omenjeno 1A bitno kodo. Med operacijo äitanjii p>i ve^Je za korekcijo napak pregleduje blok pod.itkov in preko zastavce ERR FLAG sporoBä pomnilniku. Ce se v podatkovnem bloku pojavi kakšna -napaka. Na ukaz "read MBM data" FSA Cita podatke Iz MMP. PreCitani podatki so na osnovi vsebine "boot-loop registra" selektirani tako, da se v FIFO registre FB ojačevalnikov vpisujejo le tisti podatki, ki prihajajo Iz dobrih zank. V primeru korekcije napak, se podatek prt^bere na poseben naCin. Tedaj mora biti blok podatkov (to je 270 bitov) v celoti preneSen v FIFO, Se predno se kateri bit prebere I'.: FIFO registra. Le na ta naöln lahko vezje za korekcijo napak le-te odkrije In s programsko prekinitvijo krmilnika pravcflasno prepreöi nadaljni prenos podatkov. V primeru, da napak ni, se 270-bitnl blok prebere iz FIFO registra v krmilnik, a v FIFO register se med tem üe vpiSe naslednji blok. Ukaz "Internally correct d at a" prIs 111 FS o-JaCevalnlk, da v notranjem ci k 1 u ojaCeva1nlka podatki potujejo skozi vezje za korekcijo napak, ne da bi bil kateri oil njih poslan krmilniku. Na koncu te operacije poälje ojačevalnik CORRERR ali UNCORRERR hit, v sLotu&ni register krmilnika. Be je napaka popravljiva, pribne krmilnik izvajati ukaz "read corrected data". V ciklu izvajanja ukaza "read currect data" potujejo podatki skozi ECCve^je. Nato se vseh 256 bitov prenese nazaj v krmilnik. FSA status register ozriaöuje prisotnost napake, ki Je lahko popravljiva ali ne. Gornji ukaz se pojavi tudi tedaj, ko so podatki predhodno popravljeni z ukazom "internally correct data". Oba ukaza zdruifeno omogotiata tri nivoj-skl ECC, ki je natanBneje opisan v delu C73. 6. ZAKLJDBEK Delo Jä nastala v okviru sodelovanja Instltu-> ta "Jofet Stefan" z Iskra-Telematiko, Kranj. Razvit Je bil osnovni modul magnetnega me-hurBnega pomnilnika kapacitete 128, 256 ali 512 kilozlogov. Zasnovan pa je tudi ekspan-zljski modul, ki povetìuje kapaolteto pomnilnika na en megazlog. V prvih treh razdelkih smo obravnavali problematiko odkrivanja In doloBanja vrste napak v delovanju magnetnega mehurBnega pomnilni- Skega modula na tako Imenovanem prve« makro nivoju. Obravnavana netodologiJa testiranja na tem nivoju Je uporabljiva pri razvoju in vgrajevanju «MP v uporabniški sistem; Proiz-vajalou MMP elementa omogoöa zanesljivo odkrivanje slabih zank. Odpravljanje posledlo le-teh v pomnilniSkem älpu pa smo obravnavali v razdelku 5.4, Zakljutilmo lahko, da Je za uporabnika mehurö-nsga pomniInlSkega medija bistven prvi nivo testiranja. To Je testiranje na nivoju tiskanega vezja, pri Čemer uporabnik izvaja funkcionalno testiranje z rabo obravnavane metodologije testiranja na tem nivoju. V dodatku Je podan opis programa funkcionalnega testiranja 0,5 megazloinega oehurCnega pomnilnika na ploSCl tiskanega vezja, ki Je bil najpreje testiran na Intelleooven razvojnem sistemu, po preproJektlranJu in prilagoditvi vodila pa Se na gastltelJskem 16-bitneffl mikro računalniku TK 680G0. 7. LITERATURA C13 P.Kolbazen.R.Trobec, J.Silo, B.nihovllo-vlo! MehurCnl pomnilniki, IJS Ljubljana, Raziskovalna Studija,. Ut.pogodbe: 03-BR-PK-1224/81, Junij 1981. C23 Allna Deutsch, John D.Maokay, Mark H «ryder, Mitchell S. Cohen, Arnold Halperln, Fred M. Stukeyi Magnetic Bubble Memory EMerclser,IEEE Transaotions on magnetics, V01.MA5-16, No.2, March 1980. C33 Joe E. Neuhauseri Oscilloscope Technique for Checking Bubble Memories, Eleotronios Test, pp. 10-11, «ay 1979. CA] Dan Harmoni Test strategies find faults in user's bubble memories, Electronias, pp. 1A5-1Aa, June 2, 1981. CSI John E. Davles: The 7110, A One Megabit Magnetic Bubble Memory, Intel Magnetlos, Reallbllity Report. [63 J.E.Davles: Reallbllity Considerations in the Design of One-megabit Bubble Memory Chips, IEEE Transactions on Magnetlos, Vol.MAG-16, No. 5, pp. 1106-1110, September 1980. C71 D.Dossetter, H.Uashburn, S.Nloollno and O.Pierce: New bubble memory packs in AM bits, Part two, Electronlo Engineering, pp. 47-53, January 1983. DODATEK Testiran.le mehurflneaa pomnl 1 ni en a elementa 17110 na mikroraäunalnlSkem sistemu Intellfc MDS in sistemu TK 68000, Testni (program je napisan v zbirnem jeziku Intel 8080 In Motorola 6800. Algoritem testiranja: beain iniciallzacija pomnilnidkega sistema | stanje := O i {trengtno stanje: testiranje > page := O j < trenutno testirana stran ) stnapak 1= O { < Število napak > sttestov := O j< Število testov > repeat case stanje at < generiranje testnih vzorcev 0,55h, aah, ffh > O« begin generiranje testensg* vzoro« | stanje := 1 ) SM I < vpis testnih vzoroev iz RAMa v mehurtlni pomnilnik > 11 beoln vpis testenega vzoroa na stran page | ii BMCstatus then feefliü il page = 4096 then kegln sttestov ì" sttestov -f 4096 | page O | stanje := 2 j sM : alse page page ♦ 1 | end i else status := 4 | end j { branje testnih vzorcev iz mehurCnega pomnilnika v RAM > 2: begin branje testnega vzoroa iz strani page | IX BMCstatus then stanje := 3 | else stanje := 4 | end I < primerjava vpisanih in branih testnih vzorcev > 3: begin komparacija vpisanega in branega testenega vzoroa | 11 razlika ÌMq äsflin stnapak := stnapak + 1 | urite ( stnapak ) | end I iX page = 4096 then stanje :■ O j £lse begin page page * 1 | stanje 1= 2 ; SM I éM i < nasilna prekinitev > 4i feealn nasilna prekinitev | programski reset | stanje := 0 eni I SM I UQtü koneo ) snli. UPORABNI PROGRAMI Prilagodljivo numeriCno integriranje % Informatica UP 18 % % Adaptive Numerical Integration % % oktober 1984 % % pripravil Vladimir Batageli % % sistem DEC-10 % POSTOPKI ZA PRIUGODLJIVO NUMERIČNO INTEGRIRANJE Vladimir BatagelJ VTOZD Matematika in mehanika Univerza E. Kardelja v Ljubljani Namen tega sestavka je opozoriti na postopke za prilagodljivo (adaptivno) numerično integriranje in na vire I 2, t, 5, 6j , kjer so podrobneje opisani. Postopki za prilagodljivo numerično integriranje so področje, na katerem se uspešno prepletata numerična analiza in računalništvo, natančneje, načrtovanje in analiza algoritmov. Tako je na primer v numerični knjižnici NAG podprogram DOUGA/F, ki temelji na Oliverjevi prilagodljivi metodi, priporočen kot najboljši splošni integracijski podprogram. Če želimo pri' običajnih postopkih za numerično integriranje C 1 J povečati natančnost izračuna, povečujemo število n točk ali vozlov, ki jih upoštevamo pri' izračunu. S tem sicer zmanjšamo napako metode, žal pa se nam pri tem zaradi večanja števila operacij večata zaokrožitvena napaka in čas (cena) računanja. Zato se obnaša celotna napaka tako, kot prikazuje slika: napaka Pri prilagodljivih postopkih pa drobimo interval samo tam, kjer je treba. Zato običajno za. dosego željene natačnostl potrebujejo manj korakov - pri (skoraj) isti napaki metode bo manjša zaokrožitvena napaka ps ' tudi postopek Je hitrejši in s tem bolj dconcolčen. Osnovna zamisel prilagodljivih postopkov numeričnega integriranja je znana v računalništvu kot pristop "deli in vladaj". Recimo, da želimo izračunati vrednost P(a,b,eps) integrala: b I(a,b) = j f(x) dx a pri čemer dopuščamo napako eps . Naj bo še S(a,b) ena izmed kvadraturnih formul, ki jih poznamo iz numerične analize , in dajejo oceno za vrednost I(a,b) . Določimo oceno S^ = S(a,b) za neznani I(a,b) . Nato razpolovimo interval [aibl a točko m = (a+b)/2 in izračunamo še oceno Sj = S(a,m) + S(m,b) . Če se oceni razlikujeta za manj kot eps , vzamemo S^ za P(a,b,eps) . Sicer isti postopek rekurzivno ponovimo na obeh podintervalih £a,m] in [m,b] , pri čemer pa na vsakem podinte^alu dopuščamo le pol manjšo napako eps/2 . Ko enkrat poznamo P(a,m,eps/2) in P(m,b,eps/2) , lahko izračunamo tudi P(a,b,eps) = P(a,m,eps/2) + P(m,b,eps/2) V praksi se izkaže, da je zmanjšanje dovoljene napake na eps/2 pri rekurzivni ponovitvi postopka preveč pesimistično. Zato v postopek vpeljemo nov parameter q , 1 <2 in dovoljujemo napako eps/q . Izkaže se ESD, da je čisto v redu že q = 1.4 . V tem sestavku je opisani postopek razdelan za primer, ko oceno vrednosti Integrala na intervalu [Ja,b] računamo po Simpsonovetn obrazcu: S(a,b) = ^ ( f(aO i).f(^) f(b) ) Treba pa Je takoj pripomnil, da podprogrami iz numeričnih knjižnic uporabljajo veliko bolj "zvite" ocene in tudi sam postopek Je še nadalje izpopolnjen. Za primerjavo Je dodan še navadni postopek za numerično integriranje po Simpsonu. V obeh programih se nahajajo spremenljivke, za merjenje posameznih značilnih količin: i - zaporedna številka countf - število izračunanih funkcijskih vrednosti depth - globina rekurzije Te spremenljivke in stavki, ki jih vsebujejo, ne vplivajo na samo računanje, zato Jih lahko tudi izločimo. Za to, da bodo prednosti prilagodljivega postopka očitne, Je bila primerjava narejena na integralu (ploščina I četrtine enotskega kroga) : i /777'ä. o ki Je za navadni postopek neugoden. Njegova štirikratna vrednost Je število pi . Priloženi tabeli govorita sami zase. Omenimo le pomen , posameznih stolpcev: NAVADNO: zaporedna številka, izračunana vrednost integrala, dejanska napaka, število Izračunanih funkcijskih vrednosti; PRILAGODLJIVO: zaporedna številka, izračunana vrednost integrala, dovoljena napaka, de.lanska napaka, število Izračunanih AinkclJskXh vrednosti, največja globina rekurzije. Izračuni so bili opravljeni na računalniku DEC-10 , Univerze v Ljubljani. PROGRAM sloipsonCoutput); CONST pi = 3. 1592653589793 ; ernnin = 0.00000005 { VAR error, int : real; 1, n, countf : Integer; FUNCTION f( x: real ): real ( BEGIN countf :s countf ♦ 1 j f sqrt(abs(l-sqr(x))) END (if«); FUNCTION Integral ( FUNCTION f:reali a,b:real; n:integer ); real; VAR h, p, X : real ; o, i : Integer i BEGIN h (b - a)/(2«n) ; p := f(a) + f{b); X := a J o := ; POR 1 1 TO 2»n-1 DO BEGIN X X + h ; p ;= p + c»f(x) j o := 6 - C END; integral ;= h«p/3 END (h Integral ») ; BEGIN writelnC 5,'NAVADNO INTEGRIRANJE PO SIMPSONU •); wrlteln; n 1j i := O i REPEAT countf := O ; i :s 1 + 1 ; int := 1»integral(f,0,1,n) ; error := pi - int; writeln( 1:7, int, error, countf:8 ); n :: 2in UNTIL abs( error ) <= errtnln END. NAVADNO INTEGRIRANJE PO SIMPSONU 1 2.976Ü68E+00 2 3.0tì3595E-»00 3 3.1211Ö9E+00 << 3.13'(39ÖE+00 5 3.139052E+00 6 3.1i)0695E+00 7 3.1it1276Et00 8 3.imiltìlEt00 9 3.1H1553E+00 10 3. l'(1579E+00 11 3.11)1588E+00 12 3.1'41591E+00 13 3.1it1592EtOO m 3.1'41592Et00 15 s.imsgsE+oo 16 3.1'(1592E+00 17 3.111593E+00 18 3.141591E-.Ó0 19 3.1t1593E+00 20 3.1'(1601E+00 1.6552^-01 3 5.799752E-02 5 2.0U03'<7E-02 9 7.19')966E-03 17 2.5'<0'(39E-03 33 8.975565E-01 65 3.17186IE-OIJ 129 1.121l63E-0t 257 3.978610E-05 513 1.385808E-05 1025 i).917383E-06 . 201)9 1.758337E-06 i<097 5.662t')1E-07 8193 2.980232E-07 16385 i(.172325E-07 32769 5.066395E-07 65537 -8.9'l0697E-08 131073 1.8l79t2E-06 262 T<5 -8.9t0697E-08 521289 -8.il3')057E-06 101(8577 PROGRAM 3lnip3on{output); CONST pi = 3.111592653589793 i errniin = 0.00000001 | VAR error, int : reals 1> countf, depth FUNCTION f( x: real ): real ; BEGIN countf := countf ♦ ) ; f := sqrt(abs(1-3<}r(x))) END (afa); FUNCTION integral ( FUNCTION f:real; a,b,error:real ): real; VAR m, o, fa, fm, fb : real ; d : Integer j FUNCTION Irec ( a, m, b, fa, fta, fb, estimate, error:real CONST q = 1.5 ; VAR c, ma, mb, BEGIN d Dia Bib c integer; ): real; fina, fmb, està, estb, newest : real ; := d + 1 ; IF d > depth THEN depth := d ; := (a + (n)/2 ; fma := f(ma) ; := (m + b)/2 ; Jinb :s f(mb) ; := (b - a)/12 ; està := c a ( fa + ifaHna + fm ) ; estb := c a ( fra + lafmb + fb ) ; newest := està + estb ; IF abs(estimate-newest) > error THEN Irec := lreo(a,ma,ro,fa,fliia,fte,esta,error/q) + irec(m,mb,b,fm,fmb,fb,estb,error/q) ELSE irec := newest ; d:= d - 1 END (a irec a) ; BEGIN d := 0 ; m := (a + b)/2 ; o := (b - a)/6 ; fa := f(a) ; fin := f(m) ; fb := f(b) ; integral := lrec(a,m,b,fa,nn,fb,ca(fa+1afin+fb),error) END (a Integral a) ; BEGIN wrlteC ':15); wrltelnCPRILAGODLJIVO INTEGRIRANJE PO SIMPSONU'); writeln ; error 1 ; i := O ; WHILE error > errmin DO BEGIN countf := 0 ; depth := 0 ; i :s 1 + 1 ; Int := taintegraKf.0,1,error) ; writelnd.int, error, pi -int, count f:6,depth:6)i error := error / 2 END END. PRILAGODLJIVO INTEGRIRANJE PO SIMPSONU 1 3.083595E+00 1.000000E+00 5.799752E-02 5 2 3.O83595E+OO 5.000000E-01 5.799752E-02 5 3 3.083595E+00 2.5ÜÜO00E-O1 5.799752E-02 5 ^ 3.083595E+00 1.250000E-01 5.799752E-02 5 5 3.O83595E+OO 6.250000E-02 5.799752E-02 5 6 3.083595E+00 3.125000E-02 5.799752E-02 5 7 3.1211Ö9E+00 1.5b2500E-02 2.0103bOE-02 9 2 8 3.131383E+00 7.8I25OOE-O3 7.209718E-03 13 3 9 3.139032E+00 3.9Ü6250E-03 2.560167E-03 17 1 10 3.111253E+00 1.953125E-03 3.397763E-01 25 6 11 3.ini58EtOO 9.765625E-01 1.318853E-01 29 7 12 3.II153OE+OO 1.8Ö2Ö13E-01 6.216567E-05 33 8 13 3.111556E+00 2.111106E-Ü1 3.686517E-05 37 9 11 3.111565E+00 1.220703E-01 2.783537E-05 11 10 15 3.111583E+00 6.IO3516E-O5 9.891371E-06 19 11 16 3.1115öaE+00 3.051758E-05 1.110711E-06 57 12 17 3.III59OE+OO 1.52587 9E-05 2.533197E-06 65 13 18 3.11t691E+00 7.629395E-06 1.817711E-06 73 11 19 3.111592E+00 3.811697E-06 9.238720E-07 85 15 20 3.111592E+00 1.907319E-O6 3.576279E-Ü7 105 17 21 3.111592E+00 9.536713E-07 2.682209E-07 117 18 22 3.111593E+00 1.76Ö372B-07 1.190n6E-07 133 19 23 3.111593E+00 2.38IIÖ6E-O7 8.910697E-08 153 20 21 3.111593E+00 1.192093E-07 2.9a0232E-08 185 21 25 3.111593E+00 5.960161E-08 O.OOOOOOE4OO 213 22 26 3. 111593E+00 2.98O232E-O8 O.OOOOOOE+00 253 23 27 3.1't1593E+00 1.1901I6B-O8 O.OOOOOOEtOO 285 21 LITERATURA: [il Bohte Z.: Numerične metode, (v I. Vldav: Vlàja mateinatika III). Ljubljana, 1973 [2I De Boor C.: CADRE: an algorithm for numerical quadrature, (v Mathematical software, J.R.Rice, ed.). Academlo Presa, New York, Il17-1t9 [3].Dennis J.E. Jr., More J.J.: Computer solution of natheasatlcal problems. ( v Conway R., Cries D. : An Intraductlon to Progranmlng). Winthrop, Cambridge, Mass., 1975, 358-366 [ij] Kahaner D.K.! Comparlslon of numerical quadrature fontulaa. (v Mathematical software, J.R.Hioe, ed.). Academic Press, New York, 229-259 [^S'] NAG fortran library manual, mark 6. NAG Ltd., 1977 [6] Oliver J. : A doubly-adaptive Clenshaw-Curtis quadrature method. The Computer Journal, 15(1972), 141-117 Vsa literatura Je dosegljiva v Matematični knjižnici. Jadranska 19, Ljubljana. Procedura maglcodd v listi 1 oblikuje magični kvadrat podobno kot procedura maglceven, le da Je stopnja n matrike x liha In ni manjša od 3. Funkcija maglcterra v listi 1 Izračuna element B(i,j) magičnega kvadrata a(l ,, n, 1 .. n) za liho vrednost n, ki ni.manjša od 3. Lista 1 vsebuje še procedur za izpis magičnega kvadrata kvadr_izpi8 In proceduro za preizkušanje magičnosti kvadrata magic_teat, ki najprej določi magično vsoto in nato preizkusi na to vsoto vse vrstice, vse stolpce In vse diagonale. - Z glavnim preizkusnim programom liste 1 se uporabijo zadevne procedure in funkcija (maglce-' ven, maglcodd in magicterm) z izpisom magičnih matrik in njihovim testiranjem. 3. izvajanje programa MAGIČNI KVADRATI SODE IN LIHE STOPNJE sa&sssss %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % % % Informatica UP 19 Magic Squares of Even and Odd Degree september 1984 priredil Anton P, Železnikar sistem CP-M, Delta Partner prevajalnik Janus-Ada, verzija 1.5.0 * % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1. Področje uporabe Problematika magičnih kvadratov sodi v področje matematične In programlrne rekreacije. Tu al je mogoče izmišljati različne algoritme za določevanje magičnih kvadratov sode in lihe stopnje. 2. Opis programa Procedura maglceven v listi 1 določa: ' za kvadratno matriko n krat n' elemente z vrednostmi od> 1 do n krat n in Jih razmeŠča v leksiko-grafskem zaporedju v polje x(l .. n; 1 .. n), ko Je n sodo celo število, ki nI manjše od 4 in oblikuje na ta način tklm. magični kvadrat. V magičnem kvadratu so vsote elementov poljubne vrstice, poljubnega stolpca in poljubne diagonale medseboj enake. Lista 2 prikazuje Izvajanje programa. Magični kvadrata 1 in 2 sta posledici uporabe procedure maglceven za n = 4 in za n = 6. Magična kvadrata 3 in 4 nastaneta z uporabo procedure maglcodd za n =3 in za n = 5.- Magični kvadrat 5 se pojavi z uporabo funkcije magicterm za n = 5. Magični kvadrat 6 je rezultat uporabe procedure maglceven za n = 16 in magični kvadrat 7 je rezultat uporabe procedure maglcodd za n = 17. . Masičnl kvadrati sode In in lihe stopnde WITH util» PACKAGE BODY maaicl 18 n« CONSTANT t- 17» V SUBTYPE d IS inteser RANDE i .. n> TYPE stolpec IS ARRAY 18 ar br n2> nn> i« integerl^ p» q» n Boolean»-/ PROCEDURE alpha ( p, q. a« IN intesor» h» IN Boolean ) 18 hh« Boolean» , BEGIN - hh «- h» , FOR i IN p .. q LOOP hh «-NOT hh» . IF hh THEN x IS hh« Boolean! BEI3IN hh h» FOR i IN p .. « LOOP hh NUT hh» if hh THEN x( i )< a ) 9'= a»n + 1 - i » ELSE x< i X a ) J" nn - a*n + 1» END IF» ENÖ LOOP! END beta» PROCEDURE gamma ^ p. q. a« IN inteaer» h« IN Boolean > IS hhi Boolean» BEOIN hh h» FOR i IN P .. > n2 n/;j» nri n«n( p I»» »4>> q «m p» r j» true» FOR a IN 1 .. n2-l LOOP beta< 1 rs-l »a rr )» alpha( a,n2-l .a.true )» IF q THEN x(a> nn - a«n + n2» end IF» alpha(n24-l.n.arN0T q >» q e = NOT q » r • NOT r • END LOOP» alpha< l,n2-l.n2,N0T P )» alpha( n2-<-2rnrn2rfalQe >» oammaC 1 .n2--l .n2+l rP )» 9amma( n2<'2rn»n2+l .true )» q »o PS r true» FOR a IN n2+2 n LOOP beta< 1 rn-a ra »q >» x a»n - a + 1» beta< n-a+2.n2-l ra rtruo >» IF NOT r THEN x nn - a*n + n2» x» q s= not q» r •» not r» end loop» FOR a IN n2 .. n2+l LOOP FOR b IN n2 .. n2+l LOOP IF p IHEN x< b X a > »•" a»n - n + b» ELSE x(b> «» nn - a»n +n - b +1» END IF» END LOOP» END LOOP» IF NOT i> THEN FOR a IN n2 .. n2+l LOOP x•- n*n2 - 2«n + b» END LOOP» END IF» END Masiceven» -*«««»**»»«»*«*««««*»»«»»««»»*»•»«»«»««»»*««»* - Tudi ta procedura Je predmet naèe pozornosti (masiCni kvadrat lihe etopncie) PROCEDURE maaicodd < n* IN inteuer» *• OUT polJe ) IS ir it k t inteaer» BEOIN FOR i IN I .. n LOOP FOR J IN 1 .. n LOOP x< i )< j ) »» O» END LOOP» END LOOP» i S" i + n» END IF» IF j < 1 THEN d J + n» END IF» END IF» x(i>(J) «o k» i •<« i '«- 1» IF i > n THEN i I" i - n» END IF» J t» 4 + 1» IF j > n THEN j «- J - n» END IF» END LOOP» END masicodd» Tudi ta -funkcija Je predmet naée pozornosti (masićni £lcn za kvadrat lihe stoPnJe) FUNCTION masicterm < i. J, n« IN inteser ) RETURN intpser IS br c< integer» BEOIN b J - i + /'2» C «» 2*i ~ i» If b >» n THEN b »= b - n» ELSIF b < O THEN b «= b + n» END IF» IF C > n THEN C C - n» ELSIF C <- O THEN C s« C + n» END IF» RETURN b»n C» END masicterm» PROCEDURE kvadr_iipis IS k> p» integer» BEGIN neM-Iine» put< "Hasiini kvadrat")» put< i,2)» put< • - • >» new-line» put< '-------------------' )» neiu-Iine» FOR k IN 1 .. n LOOP FOR p IN 1 . . n LOOP' put( x< k )(p >>S>» IF p n THEN ne«i_line» END IF» END LOOP» END LOOP» new-line» END kvadr-izPia» Usta 1. (Nadaljevanje s prejänje in na naslednjo stran). Bistvene procedure te liste ao magiceven, magloodd In magicterm, pomožni (oziroma preizkusni) proceduri pa sta kvadr_lzpl8 in maglc_test. PROCEDURE maslc_t«»t < 1. n« IN Inteaerl X« polie) I,S «ér bb/ c. d» ö« Inteaep» BEOIN aa »■0» —---------Določitev masiihe vsote —-------- FOR C IN i .. n LOOP aa aa + x< 1 )< c )» END LOOPI ----------^ Prelzku« vrstićnlh voot -------•POR C IN 1 ,. n LOOP bb O» POR d IN 1 .. n LOOP bb bb + x(d>» . END LOOP» IF bb /" aa 'THEN PUt< "Kvadrat nI ttiaslCen I * )• new_line» GOTO fin» END IF» END LÒOP» --------Preizkus stolpnih voot ----------- FOR C IN 1 .. n LÒÒP bb O» FOR d IN !.. n LOOP bb 1=» bb + *< d )( C )» END LOOP» IF bb /» aa THEN' put< "Kvadrat ni maslCenl" )» new_line» OOTO fin» ■ END IF» END LOOP» --------• Preizkus diagonalnih vsot -—----- bb «= Ot e O» FOR d IN 1 ,, n LOOP bb «" bb + x» o e + x» END LOOP» . IF bb aa DR e V- aa THEN Rut< 'Kvadrat ni nasičen I ' )» new-line» GOTO fin» END IF» put< 'Hasična vsota kvadrata')» put(l>2>»: put< " Je " >». put( aa>S )» neÌM_l iho» <> null» END magic-test»' -------- Glavni preizkusni prosram X» PolJe» r. s« inteaer» BEGIN . masiceven < 4r x )» kvadr-izpis (1, 4. x )» . masic-test ( 1 r 4r x)» «laaicevén < Är x >» . kvadr.izpis <2» A. x )» maaic-test <2r ór x>» masicodd < 3» x >» kvadr-izpis <3r 3. x )» ' masic.test <3. 3. x )» maalcodd < 5. x )» kvadr.izpis ( 4r 5r x>» magić-test (4> Sr x>» FOR r IN 1 . . . 5 LOOP j='OR s IN 1 .. S LOOP ■ x» END LOOP» END LOOP» kvadr-izpis » Biaaic-teat » maaicoven < 16. x )» kvadr-izpis < Ar 16r x >» maaic_teet .<6r 16r x >» masicodd < 17r x )» kvadr^izpis < 7, 17r x >» ma9ic_teat <7r 17. x )» END «laaicl» Lièta li (Nadaljevanje s prejšnjih dveh strani) Glavni preizkusni program kliče deklarirane procedure In funkcijo màgicterm in izpiSe rezultate v obliki liete 2. - MaaiCni kvadrat 1 ■ ■ 1 ■ ■ ■ 1 ■ ■ ' 12 8 13 •■..15 6 10 3 .. 14 7 11 2 4 9 5 16 ' , '. 1 " ■ Masična vsota kvadrata 1 Jo 34' Maaični kvadrat 2 " , ! !- ■i-'- 12 , 13 24 30 ■31-- ! 35 8 17 23 26 2 . ■ 33 28 22 16 9 3 ■ ■ ■■4 ■ 27 21 15 10 34 32 11 20 14 29 5 ■ , 6 25 IB 19 7 ■36-'; Mašična vsota kvadrata 2 Je ■ . 111 ■ ' .; ' Manični kvadrat 3 " 4 " 3 8 • • j ' . ' ■ " ■ 9 S -.1 , 2 ■ 7 6 Maaična vsota kvadrata 15 ■ . Lista 2. Ta rezultatna lista, ki se nadaljuje na naslednji strani, prikazuje prvih pet magičnih kvadratov, ko imamo n = 4,'6, 3, 5, 5. Četrti In peti kvadrat sta dobi jena z različnima procedurama m rabita za primerjavo. Ob vsakem kvadratu se izpläe tudi magična vsota. Masični kvadrat 4 11 18 25. 2 9 10 4 23 17 12 6 : 5 24 19 13 7 1 21 20 14 8 3 22 16 15 Hasična vsota kvadrata 4 Je Haaični- kvadrat'S «■ 11 IB 25 2 9 10 12 19 21 3 4 6 13 20 22 23 S ■ 7-' 14 17 24 1 8 IŠ Haaična vsota kvadrata S-Jo 6S 65 Maalčni kvadrat 6 => 1 32 209 64 177 96 145 144 128 97 176 65 208 33 240 241 25f5 IB 47 194 79 162 111 114 143 139 82 191 50 223 226 2 3 238 35 62 179 94 147 142 126 99 174 67 206 211 19 254 2S3 20 221 52 77 164 109 116 141 1S7 84 189 196 36 237 4 S 236 37 204 69 92 149 140 124 101 172 181 S3 220 21 2S2 231 22 219 54 187 86 107 118 139 ISS 166 70 203 38 235 6 7 234 39 202 71 170 103 138 122 151 87 186 35 218 23 250 249 232 217 200 185 168 153 120 136 105 88 73 56 41 24 9 248 25 216 57 184 89 152 121 137 104 169 72 201 40 233 e 10 231 42 199 74 167 106 135 119 154 90 183 58 215 26 247 246 27 214 59 182 91 150 123 134 102 171 75 198 43 230 11 12 229 44 197 76 163 108 133 117 156 85 188 60 213 28 245 244 27 212 61 180 93 148 125 132 100 173 68 205 45 22B 13 14 227 46 195 78 163 110 131 115 158 83 190 51 222 30 243 242 31 210 63 178 95 146 127 130 98 175 66 207 34 239 15 16 225 48 193 80 161 112 129 113 160 81 192 49 , 224 17 256 Maslfina vsota kvadrata 6 ie 205A MaaiCnl kvadrat 7 « 137 136 118 100 82 64 46 28 10 281 263 245 227 209 191 173 155 15A 138 120 119 101 83 65 47 29 11 282 264 246 22R 210 193 174 175 157 139 121 103 102 84 66 48 30 12 283 265 247 229 211 193 194 176 158 140 122 104 86 85 67 49 31 13 284 266 248 230 212 19F. 177 159 141 123 lOH 87 69 68 50 32 14 2R5 267 249 231 214 196 178 160 142 124 106 88 70 52 51 33 15 286 268 250 2B1 233 213 197 179 161 143 125 107 89 71 53 35 34 16 287 269 270 252 234 216 198 180 .162 144 126 108 90 72 54 36 18 17 288 2139 271 253 235 217 199 181 163 145 127 109 91 73 55 37 19 1 2 273 272 254 236 218 200 182 164 146 128 110 92 74 56 38 20 21 3 274 256 255 237 219 201 183 165 147 129 111 93 75 57 39 40 2? 4 275 257 239 23« 220 202 184 166 148 130 112 94 76 58 59 41 23 5 276 258 240 222 221 203 185 167 149 131 113 95 77 7B 60 42 24 6 277 259 241 223 205 204 186 168 150 132 114 96 97 79 61 43 25 7 278 260 242 224 206 188 187 169 151 133 lis 11Ä 98 80 62 44 26 8 279 261 243 225 207 189 171 170 152 134 135 117 99 81 63 45 27 9 280 262 244 226 208 190 172 134 153 Maglfoa vsota kvadrata 7 .io 24A5 Lista 2. (Nadaljevanje s prejšnje strani) Ta del liste prikazuje Se primera mnglönlh kvadratov za n = 16, 17. Iz teh kvadratov Je razvidna metoda razmeSčanja elementov kot zaporednih vrednosti od 1 do n X n. Ta razmeSčevalna metoda Je razllSna za aodl In lihi primer. NOVICE IN ZANIMIVOSTI Jezik Lisp za mikroračunalnike (pravzaprav nu)? približujejo računalnik ibraovske- Podjetje Microsoft je napovedalo prvo izvedenko jezika Lisp za svoj operacijski sistem MS-DOS. To pa pomeni, da bo mogoče probleme umetne inteligence (področje izvedenskih sistemov in prevajanje naravnih jezikov) reševati tudi z mikroračunalniki, kot so IBM PC in njemu podobni. Novi paket bo imel oznako muLisp-82 Artificial Intelligence Development System in bo naslednik paketa muLisp-80 za osembitne mikroračunalnike. Podobno kot so omejene obstoječe izvedenke za uporabo jezika Prolog na mikroračunalnikih v okviru problematike umetne inteligence, tako bo omejena tudi izvedenka muLisp-82 v svoji zmogljivosti. Tako bo muLj.sp-82 v glavnem zanimiv za univerze in raziskovalna podjetja. Vendar se bo z uporabo tega jezika lahko znatno razširila metodologija umetne inteligence med strokovnjaki in amaterji. Podjetje Microsoft se je dokončno odločilo, da začne osvajati tržišče umetne inteligence s svojimi programskimi izdelki. Zato se dogovarja z drugimi podjetji za izdelavo in pravice na področju razpredelničnih pol pri razvoju izvedenskih sistemov (paket ExpertEase podjetja Export Software). Paket ExpertEase je programski generator za gradnjo malih izvedenskih sistemov na 16-bitnih mikroračunalnikih. Ta paket naj bi bil namenjen predvsem poslovnežem in manj akademikom, torej tistim, ki delajo na področju finančnega inženiringa in finančnega poslovanja. Paket ExpertEasy je mogoče uporabiti na ibmov-skih osebnih računalnikih, njegova cena pa je 1500 funtov. Podjetje Export Software bo kmalu izdalo demonstracijski paket s ceno 100 funtov. Pri vsem tem pa je bilo precej dvomov, da bi se tak paket lahko uporabljal na računalnikih tipa IBM PC. A.P.Železnlkar S pojavom računalnikov tipa IBM PC in IBM XT je nastal industrijski standard, ki se mu poskušajo prilagoditi številni proizvajalci (posnemovalci ibmovskih sistemov). V primerih približevanja standardom se vselej vprašujemo, kako in v kakšni meri so,posnetki združljivi z IBM PC. Odgovor na to vprašanje je določena materialna in programska oprema, ki obstaja za določen ibmovski posnetek. Podjetje Award Software v ZDA je razvilo posebne programe, s katerimi se ugotavlja stopnja združljivosti z IBM PC. Slika 1 prikazuje arhitektonski model za IBM PC in IBM XT. Ta model je sestavljen iz štirih ravnin : -- materialne opreme — nižjih podpornih rutin (ROM BIOS) — programskih vmesnikov za VI naprave sistema PC-DOS (ibmov BIO.COM) -- operacijskega sistema PC-DOS (ibmov (DOS.COM) Če je materialna (aparaturna) oprema popolnoma ibmovsko združljiva, je mogoče na računalniku uporabljati ibmove ROMe in ibmov DOS. Vendar je z avtorskimi pravicami podjetja IBM ta metoda prepovedana in posnemovalci ibmovskih osebnih računalnikov morajo imeti svoj ROM BIOS (osnovni VI sistem v ROMu), ki se mora dovolj razlikovati od ibmovega, hkrati pa mora zagotavljati identično povezavo kot ibmov ROM BIOS. Tako je mogoče implementirati modul-IO.SYS za operacijski sistem MS-DOS, ki pa mora biti dovolj različen in mora zagotavljati povezave, ki so identične za PC-DOS. Tri področja združljivosti so tako bistvena: materialna oprema, ROM BIOS in povezave za PC-DOS. Materialna oprema mora biti sestavljena iž določenih komponent (integrirana vezja 8088, 8259, 8255, NEC 765 itd.), VI vrat in povezav med integriranimi vezji. ROM BIOS združuje osnovne programske rutine za VI in organizira materialno opremo v ustrezno upravljano obliko. ROM BIOS za IBM PC in za IBM XT je enoopravilni in enouporabniški pripomoček za VI. Čeprav se uporablja prekinitveni mehanizem, se hkrati izvaja en sam proces (edina izjema se pojavi pri časovniški prekinitvi). PC-DOS je ibmova izvedenka Microsoftovega MS-DOSa. Kaj pomeni ibmovski osebni računalnik ? Na trgu je vrsta mikroračunalnikov, ki imajo izredno dobro materialno in programsko združljivost z IBM PC. Ti proizvodi so: Kdaj smemo reči, da je osebni računalnik ibmovski, da je podoben osebnemu računalniku IBM PC, da ima zdr užljivost z IBM PC? Katera so.minimalna merila, ki to združljivost zagotavljajo Columbia Compaq Corona Eagle Mitsubishi Stearns Seequa prekinitve za diskovni operacijski sistem (DOS), naslovi 020H do 027H programski vmesniki za diskovne naprave krmilnik upogljivega in krmilnik trdnega diska programski vmesniki za tipkovnico in prikazovalnik video pomnilnik, video krmilnik, vrata tipkovnice programski vmesniki za komunikacije, tiskalnik in uro : i::::::. Sasovnik, serijska In paralelna vrata diskovni operacijski sistem (DOS) Je lahko zbirka IBMDOS.COM ali zbirka MSDOS.SYS naprave diskovnega operacijskega sistema so zbirka IBMBIO.COM ali zbirka XO.SYS podsistemi materialne opreme Slika 1. Arhitektonski model osebnega računalnika IBM PO in IBM XT Tabela 1. Glavne materialne komponente osebnega računalnika IBM PC Uporaba Integrirano vezje VI naslovi Intel 8086, 8086 NEC 765 3F4H , 3r5H Vmesnik 74LS 3F2H Intel 8255 60H do 63H Intel 8253 40H : do 4 3H Intel 8237 ODH 1 do OFH Vmesniki 74LS 80H do 83H Intel 8259 20H, 21H Vmesnik 74LS OAOH do OAFH Trdni disk 320H do 32FH Intel 8255 378H do 37AH 3BCH do 3BEH 278H do 27AH National 6250 2F8H do 2FEH 3FBH do 3FEH Vmesniki za 3D0H do 3DFH Motorola 6645 Vmesniki za 3B0H do 3BFH Motorola 6845 Osrednji procesor Krmilnik upogljivega diska Sekundarno krmiljenje upogljivega diska VI vrata za zvoSnlk, tipkovnico, za konfiguriranje računalnika, za usposobitev preizkusa parnoatl RAMa Ura realnega čas.a, Sasovnlka zvočnika, zahteva za DMA pomnilnlSko osveSevanJe DMA krmilnik Registri strani pri DMA Preklnitveni krmilnik Krmiljenje NMI Krmilnik trdnega diska (vlnčestrski disk) Tiskalniški krmilniki Serijsko komunikacijsko vezje Barvnigrafični krmilnik Krmilnik za monokromatlčno prikazovanje Preizkus materialne združljivosti Pri ugotavljanju združljivosti moramo preizkusiti, kakäna so uporabljena integrirana vezja In uporabljeni naslovi VI vrat. Tabela 1 prikazuje podatke za IBM PO,in IBM XT. Materialna združljivost z IBM PC zahteva, da obstajata monokromatični In grafični pomnilnik na ustreznih naslovih In da imata znakovni in atributski (pixel) pomnilnik identično organi-|ZaciJo. Pri tem Je potrebno preveriti operacije iz integriranih vezij, tako da Je ustrezno integrirano vezje prisotno na ustreznem VI na- slovu. Prikazovalni pomnilnik se preizkusi tako, da se ustrezni vzorec vstavi neposredno v video pomnilnik in se opazuje. Kadar želimo uporabljati preklnltveno delujoče operacijske sisteme za IBM PC, kot so npr. ONX, Concurrent CPM-86 itd., mora biti gornji preizkus veljaven, ker Je sicer potrebno dobiti posebne Izvedbe teh operacijskih sistemov. VI (sistemsko) vodilo In časovne oblike na tem vodilu se lahko preizkusijo z uporabo koaercl-alno dobavljivih vtlčnlh plo8č, ko se ugotavlja njihovo delovanje. Razen tega bi lahko opazovali časovne signalne slike tudi z logičnim analizatorjem ter Jih primerjali • signalnimi slikami na IBM PC all IBM XT. Združljivost ROM BlOSa V ROM. BIOSu Imamo dva tipa povezav. Najbolj pogost na£ln povezave (in tudi naJbolJSl) Je z uporabo programski h prek in i te v. DriTgi tip povezavo Je.z nepqarednlm nas lav 1 JanJ em"11 s tega.dela RAMa, ki ga uporablja ROM BIOS (to pa ni priporočljivo). Z izključno uporabo programskih prekinitev dobimo računalni sistem, ki bo pravilno deloval za zelo Širok spekter programske opreme. Veliko Število poanemovalnih računalnikov za IBM PC deluje na ta način uspeSno celo pri drugačni VI organizaciji in z drugačnimi integriranimi vezji, kot Jih ima IBM PC. Tabela 2 vsebuje seznam .programskih prekinitev, ki so predvidene, za ROM BIOS v IBM PC. Te programske prekinitve so v registre posredovani parametri ali pa se uporabijo preklnitveni vektorji za druge parametre. Glavne funkcije v ROM BIOSu, ki j 1 h,uporabi j aJ o programski paketi, so prekinitve za video, disk, tiskalnik, komunikaci J e, tipkovhlco, ča-sovnik in ža druge naprave. Te povezava >io opisane v dokumentaciji IBM Personal Computer in v XT Technical Reference Manual (tam Je llet» za ROM BIOS v dodatku A ) . Video prekinitev (hoksadecimalno 10), fBSPolaga s 15 funkcijami, ki so namenjene zaslonskemu/ prikazovanju, naslavljanju kurzorja, povratni povezavi sve 11obnega peresa , pomikanju, teleprinterskemu Izhodu, znakovnemu in atributivne-mu branjupisanju, grafičnemu branJ up i sanJ u In paletni in barvni izbiri. Večina proizvajalcev posnetkov IBM i^C je te probleme zadovoljivo razreS ila. Diskovna prek initev {heksadeci maino,13 ) razpolaga s 5 funkcijami za upogljive diske in à 14 funkcijami za trdne d iske . Funkči J e od 9 do 14 za trdne, d i Bke ' uporab 1 j a IBM v proizvodnji in pri diagnostičnemu pre izkuSanj u, tako da te funkcijo nlBo vključene v sploSne programske pakete. Prekinitve za upog1J 1 ve in trdne diske uporabljajo .parametrične tabele pri preklnit-venih vektorjih lEH In 41H.' To sb kazalci v tabele , ki se nahajajo v- ROMu . al i v HAMu In kjer. se nahajajo podatki za pogon motorjev, ..o Številu sektorjev na stez 1, ätövilu atez na disku. itd. . . . • ... :■; Bistvena nezdružljivost računalnika z IBM PC: lahko' izvira iz povečanih pomnilnih obsegov upogljivih diskov (v primerjavi z IBM PC).. Taki • sistemi imajo kvojey časovne ob 1 i ke i n odgovarjajo drugače kot IBM PCj zato se npr. lahko zgodi, da preneha delovati ibmov • zaSčitn 1 meha-" nizom za kc(piranje zbirk, ki velja za IBM PC. Drugo bistveno področje .nezdružlJ ivosti ' Je sporočanje napak. .Kopirno zaBČltni mehanizmi-povzročajo kode napak, ki se sporočajo na IBM, PC, na drugih sistemih pa so ta sporočila drugačna. Tiskalniška prekinitev ( heksadec inia 1 no 17) raz-'' polaga a 3 funkcijami za tri paraTelna vrata. Komunikacijska prekinitev {14H) ima 4 funkcije Tabela .K. Uporaba prekinitev za ROM BIOS računalniku IBM PC pri prekinitev uporaba . - 0 Deljenje z ničlo Iz 80888086 1 : ...' Enojni korak (pri DEBUG) 2- ■ ■ - Nemasklrna parnoatna napaka 3 , : Točka prekinitve (pri. DEBUG) 4 . Pres top 5 Pisanje na zaslon - 6-7 , . Rezervirano 8-OFH Prekinitev iz 8259 lOH Video prekinitev, 15 funkcij IIH Preslikava za naprave 12H Obseg pomnilnika 13H Diskovna preklnitév, 16 funkcij za upogljivi in 14 funkcij za .trdni disk 14H . : , Komunikaci Jaka.prek ini tov , , 4 funkcije . ■ 15H ■ Kaseta 16H Tlpkovnična prekinitev, 3 funk- . cije ,. 17H . . ■ Tiskalniška prekinitev, 3 futikr^ ciJe- 18H Osnovni vstop v ROM 19H : Navèzovalhl nalagainlk : lAH Prekinitev časa dneva, 2 funk- ■ . Ciji - ' ; .... .' IBH Prekinitev zar adi prekinjene tipkovnice ICH : CasovnlBka prekl n 1 te v ( bi t J o ) IDH Kazalec v parametričen aeznam za video inicializacijo . lEH Kazalec v seznam diskovnih para- , metrov IFH : Kazalec za grafični znakovni vzorec . 20H-3FH ■ Prekinitve DOS 40H. Preusmeritev diskovne prekinitve -za sisteme s trdnimi diski 41H . Kazalec v seznam parametrov za trdni disk - 42H-FFH . Rezervirano ail uporabljeno za prekinitve DOSa, Basica ali za za dvojo serijskih komunikacijskih vrat. Področjis z' največjim odstopanjem mikroračunalnikov od .IBM PC. je prekinitev za obdelavo . tipkovnice (i6H):. Tu ao pomembna notranja pomikal-na stanja in vrnjeni kodi. Prekinitve naprav (IIH In 12H) sporočajo tip naprave In obseg razpoložljivega pomnilnika. i ČasovniSke prekinitve (ICH), nastajajo zaradi bitja ure (tiktakanje). Drugi preklnitveni Vf9k-torji se uporabljajo V povezavi s krmilnikom 8259; 1 potem, so tu Se.prek 1nitve zaradi pasti, za enojni korak (po ukazih), pri deljenju z ničlo in ža zaslonski zapiš. Preizkus združljivosti s PC-OOS ■ Večina programskih paketov, ki ne naslavlja neposredno zaslona ali ne uporablja ANSI Izogibo-valnih (escape) zaporedij za naslavijarijo zaslona, uporablja standardne funkcijske klice za- MS-DOS. Ce paket ne uporablja funkcijskih tipk, se verjetno lahko izvaja na vsakem MS-DOS stroju (rafiunalniku) . Vendar veSina, paketov za IBM PC potrebuje zaslonsko naslavljanje in kode funkcijskih tipk. Ti paketi uporabljajo video programsko prekinitev kot najnižjo obliko povezave {s preizkusom naprave) in uporabljajo standardne MS-DOS klice. Če posnemovalni računalnik podpira video povezavo, znakovno zaslonsko abecedo in kode funkcijskih tipk, potem bo lahko izvajano na posnemovalnera računalniku veliko Število programskih paketov za IBM PC. Potencialno področje nezdružljivosti Je lahko nesposobnost branja in zapisovanja na upogljive diske z ibmovim formatom. Ti formati imajo 48 stez na colo (mera Je tpi in pomeni tracks per inch), so eno- im dvostranski in z osmimi in devetimi sektorji na stezi. Ta nezdružljivost se lahko pojavi zaradi diskov s 96 tpi, ko ni mogoče zapisovati na diske z 48 tp,i ali zaradi nesposobnosti branja 8-aektorskega formata. Nadaljna nezdružljivost se lahko pojavi pri trdnih diskih, ki imajo drugačno delitev diska kot Je pri IBM XT. IBM XT dovoljuje največ 4 različne navezi J ive diskovne delitve (partici-Je). Vsak operacijski sistem lahko uporablja eno samo delitev. Tako lahko trdni disk vsebuje particije za DOS, CPM-66 inali Concurrent CPM-86. o Preizkus zaslona temelji na znakih, ki Jih najdemo v IBM Technical Reference Manual, dodatek C . A.P.Železnikar■ Kako si zgradite ibmovski PC7 Podjetje Handwell Corp, 4962 El Camino Real, Los Altos, CA 94022 nudi vrsto modulov za aamo-gradnjo ibmovskega PC. Matična tiskana ploSča ima tele značilnosti: — procesorja 8088 in 8087 — prekinitveni krmilnik 8259A — DMA krmilnik 8237 -- dva 20-noŽična ROMa -- osnm razSlritvenih vtičnih ploBč -- na matični ploSči ni RAMa Cena gole (prazne) ploSče Je $ 69, cena ploSČe s pricinjenimi podnožji za Integrirana vezja, upori, kondenzatorji, pri k 1 Jučn1cami, kristali in tranzistorji pa ^ 199. Cena pripadajočih integriranih vezij Je i 199, preizkuSena tiskana ploSča z integriranimi vezji brez ROMov pa i ma ceno $ 399. K matični ploSči Je mogoče dokupiti Se vtične ploSče. Za osnovno konfiguracijo Je potreben RAM, VI vrata, krmilnik upogljivega dlaka, napajalnik in Se kaj. Vse te in druge module Je mogoče dokupiti po relativno zmernih cenah, in sicer: do 256k RAM + 2 serijskih vrat + 1 para- lelna vrata t ura realnega čaea (cena f 249); krmilnik za upogljive diske (cena ^169); krmilnik za trdni disk (^ 299); modul za barvno grafiko (^ 219); monokromatični, barvni in grafični modul If 329); 100W napajalnik (^ 169); barvni RGB monitor (f 449). A.P.Železnikar = = =:esBSi = = 3=Jcjs:e Ali Je peta računalniška generacija 2e pred vrati ? Da bo stvar JasneJSa že na samem začetku: Peta računalniška generacija Je nova tehnoloSka generacija DanaSnJe aplikacije umetne inteligence na računalnikih četrte generacije nimajo bistvenega vpliva na razvoj osnovne tehnologijo pete generacije. SploSna zabloda Je, da bo sama metodologija umetne Inteligence razreSlla bistvene probleme nove tehnoloBke generacije. Če Je pri razvoju nove generacije potrebna nova človekova Inteligenca, to Se ne pomeni, da Je to prav umetna Inteligenca in samo te vrste inteligenca. Kaj pa Je z novimi fizikalnimi in tehnološkimi proizvodnimi procesi, ki bodo potrebni za izdelavo novih Integriranih komponent 7 Kaj Je pri tem bistveno, zakaj In kako 7 Američani se jezijo, da so Jim Japonci vzeli idejo pete generacije In da Jo Jim zdaj spremenjeno' prodajajo nazaj. Američanom izgleda, da se zgodovina ponavlja: to kar so doživeli na področju televizijske, stereo in avtomobilske tehnike, se sedaj ponavlja z računalniško tehniko. Pojem računalniških generacij je atar In enostavno razumljiv. Prvi računalniki bo bili narejeni z elektromehaničnlrai releji In elektronkami. Konec petdeaetlh let so se pojavili tranzlstorski računalniki in računalniki z elektronkami so postali zastareli In nesodobni. Ti stari računalniki so tako postali prva računalniška generacija, tranzlstorski računalniki pa druga generacija. Sredi Šestdesetih let so se tranzistorji začeli umikati prvim Integriranim vezjem In Ibmovl sistemi 360 so bili glasniki tretje računalniška generacije, Znatno povečana integracija vezij je Imela za posledico pojav četrte računalniške generacije (npr. sistemi IBM 370, mikroprocesorji, mikrokrmi1ni k I, pomnilna vezja). Po četrti računalniški generaciji pa Je bila najavljena na dokaj umeten način peta računalniška generacija, torej nekaj, kar se ie ni pojavilo in za kar se niti natančno Se nI vedelo, kaj naj bi to bilo. Ko 80 Japonci začeli akcijo za razvoj pete generacije, je bilo Jasno, da Je bila tehnoloSka generacijska veriga na določen način prekinjena. V deklaracijo pete generacije Je vstopil« kot najbolj bistvena komponenta umetna Inteligenca, vpraSanJe nove tehnologije pa j» ostalo 'nekako obrobno in samo po sebi razumljivo: tako Je prevladala ideologija inteligence in prihajajoča generacija Jo dejansko postala neke vrsto ideološka generacija. Prehodi iz ene raJünalniäke generacije v drugo naj bi bili na določen način revolucionarni, torej taki, da se z njimi de facto prekine dotedanja evolucija. Prehod med prvo in drugo generacijo Je bil revolucionaren predvsem zaradi pojava tranzistorja' (volumen, energija, operacijska hitrost, zanesljivost). Prehod iz tranzistorja na integrirano vezje Je bil vsekakor manj revolucionaren (volumen, zanesljivost; reproducibilnost) kot pri prvem prehodu. Prehod med tretjo in četrto generacijo pa Je bil izrazito èvolucionarén in je omogočal Se dolgo življenje tretje generacije ob četrti. Evolucija četrte generacije traja Se danes in peta generacija se äe ni pojavila. Ali pa so morda vendarle že vidne nekatere.spremembe, s katerimi bi bilo mogoče najaviti prihod pete generacije? Američani zlobno namigujejo, da so bili Japonci predvsem pozórni opazovale i, ki so preprosto znali ätetl do pet in so tako opazili, da obstaja oznaka (kot programska labels) z Imenom ,+peta gòneracija+. To ime so tako zapisali na Isvojo zastavo iti hkra t i r azglas i 1 i , d» pomeni peta generacija umetno inteligenco, govoreče, posluSaJoče, videče. sklepajoče, rčbotične in Se kake računalnike. Ta pristop pa Je dejansko bližji ideološki kot tehnoloSki metodi in kaže prej nà obnaSanjé nesposobnega kot sposobnega. Tako . se jé rodila In nastala dariaSnJa termino-, lóigijai pete računa 1 n 1 Bke generac IJ e . Vse dosedanje računalniške generacije so temeljile na tehnologiji vezij in ne' na aplikacijah. Bolj učinkovite in inteligentne aplikacije so možne le z. zmogljiveJSb tehnologi jo. ' Realnost pete generacije Péta generacija pomeni nove m ikro p r o -c e sòr j o I Do. nedavnega Je ta izjava zbujala smeh pri uporabnikih velikih (kabinetnih) računalnikov In prevladovalo Je mnenje, da mlkroračunalrilki sploh niso pravi računalniki , ln da .sé iz ,njih. né .more razviti nekaj, ..kar bi bilo, podobno pBti generaciji. To bi vsakakor lahko . bilo res, Č0 bi se razvoj ustavil pri procesorjih 6502 ali 8088. Vendar je npr. IBM PC Xt37Ò (osebni računalnik) pravi računalnik, z močnim operacijskim sistemom, virtualnim pomnilnikom In zapletenimi programi. Mikroprocesorji šo i ntegri rana vezJà z ! v isoko stopnjo integracije (LSI),, ki. so dejansko spremenili prej veljavni koncept računalnika. Toda s kakSno. utemeljitvijo bi; lahko trdili ; da je ,Xt37Ö že primerek i z pe t e , račiina Ih IS ke generacije? XT370 postavlja mikroprocesorje neposredno . v . svet velikih računainikov; z njimi vdira v tà svet.in dokazuje, kako je to mogoče; ■ ta sistem ni več nekakSna igrača z močno sistemsko programsko opremo., s hitrimi komunikacijami.' Ih z' možnostjo, : da Je integralni,, del: , velikega, računalni.ka.- KmalU;, bodo XT370 pove,za-, nI v, mreže medoperacljsklh sistemov, z Izredno hitrimi kpmunikaci.jaml , kjer bodo zbirke drugih sistemov lahko dostopane na enak način in z enako hitrostjo kot lokalne zbirke. Pri tem bodo veljali standardni zaSčitni • mehanizmi in lastnosti večkratnega dostopa kot v virtualnih sistemih (VM). To pa .'so že lastnosti, ki vsaj; deltio zadovoljujejo zahteve pp računalniški zmogljivosti pete generacije. Argument proti gornjemu utemeljevanju -je, da XT370 Se ni mikroprocesor (Se ni Izdelan v enem samem inegriranem vezju). XT370 uporablja tri mikroprocesorje in Se en koprpcesor. Ti mikroprocesorji delujejo kot dva sodelujoča računalnika in oblikujejo združen sistem. Tu je procesor 8088 na matični ploSči le Se računalniški pomočnik in je namenjen VI obdelavam. \ Njegova funkcija je nadzor tipkovnice, zaslona, diskov In kpmunlkaclJake opreme. Glavni, dodatek Je nova emulacijska ploSča za 3277, ki omogoča, hitre komunikacije z Ibmovsklml gostitelji. • . ■ Dva druga tnlkroprocésor ja in koprocèsor ( dva 68000 in èn 8087) oblikujejo centralni procesor sistema XT37p. Ukazne mno.žlce namreč ni mogoče realizirati z enim samim mikroprocesorjem zaradi že nekoliko zastarele tehnologije (procesor 68000 pripada letniku 1982). V Xt370 je ukazna, množica razdeljena nà tri dele in vsak od treh procesorjev nosi svoj delež. Prvi del ukazne' množice se Izvaja na modificiranem mikroprocesorju 68000. S spremembo mikrokPda v tem pro^ cesorju se dobijo ukazni Vodi sistema 370. Modificirani Intelov procesor 8087 Izvaja matematične ukaze. Modificirano vezje ' uporablja ibniov . standard In ne standard IEEE (kot pravi procesor 8087) Tako. pro I zva J a XT370 numerlčhe : rezultate z eiiako natančnostjo kot veliki , ibmovl, računalniki. ; Zadnji od treh_ procesorjev (68000) se uporablja za dokaj redko uporabljane ukaze in Je počasr. nejSl,. ■ . ■ Teorija In praksa Trije procesorj 1 sestavi j aj o.osrednjoprocesno enoto namiznega računalnika XT370 in na njemu se lahko izvajajo praktično vsi programi velikega računalnika 370. Glavne omejitve Izvirajo : Iz pomniIniSkega naslavljanja, saj znaSa obseg pomnilnika v XT370 512k zlogov. ; Ko v glavnem pomnilniku nI več prostora, poskrbi procesor 8088 za prostor na disku; tako je mogoče nasloviti 4M zloge. Veliki sistem 370 pa . ima 16M zlogov virtualnoga pomnilnika Ih zato večji-programi od 4M zlogov na XT370 hlsb Izvedljivi. IBM PC XT370 Je prvi kabl netnl s Is tem , ki ga lahko postavimo na mizo (namizni računalnik). Tudi' DEC pripravlja namizno Izvedbo VAXa. IBM pripravlja novo družino vezij sistema. .370 z najnovejšo tehnologijo (370 v Integriranih ve--zjlh). Ti novi računalniki pa bodo (gledano tehnoloSko) prvi predstavniki pete računalniške' generacije. . Teorija pete generacije predvideva znatno povečanje paralelnih procesov v sletemü. To povečar' nje naj; bi znaSalo več velikostnih razredov vi primerjavi z danaSnJimi računalniki In mikrora-l 84 čunalnlkl. Le na ta način bi bilo mogoče reSe-vatl kompleksne probleme dovolj hitro, s hitrostmi, ki imajo praktično vrednost;. V tem pa ae skrivajo novi tehnoloSkl problemi, za katere ne obstajajo danes niti zadovoljivi algoritmi (razbijanje procesov v dovolj veliko Število paralelnih procesov in njihovo sestavljanje). A.P.Železnlkar Ibmov PC AT Ko bo na razpolago več podatkov, bomo v eni od naslednjih številk časopisa Informatica podrobneje opisali osebni računalnik PC AT. Zaenkrat si oglejmo le njegove osnovne specifikacije. Tri leta po uvedbi računalnika IBM PC se je pojavila njegova izboljšava z oznako AT (Advanced Technology). Ta računalnik vsebuje mikroprocesor 80286 (s taktom 6 MHz in z 2- do 3-krat višjo zmogljivostjo kot PC), diskovno enoto z upogljivim diskom za 1,2 M zloga, vin-čostrski disk za 20 M zlogov (kot opcijo), izboljšano in razširjeno vodilo, ki je združljivo s starim vodilom (dve priključnici za vsako vtično tiskano ploščoi ena za staro in dve za ploščo novega tipa), bolj uporabno novo tipkovnico itd. IBM je najavil tudi novo izvedenko operacijskega sistema PC DOS 3.0 z manjšimi izboljšavami in z mrežno podporo, vendar brez lastnosti večopravilnosti (multitasking). V prvi četrtini leta 1985 bo IBM uvedel TopView, tj. operacijsko okolje, ki omogoča večopravil-nost za ceno $ 149 in posebno izvedenko operacijskega sistema Xenix (Unix System 3) za procesor 80286 z zmogljivostjo večopravilnosti in večuporabnosti (multiuser). Cene teh novih izdelkov so izredno konkurančne. Osnovna cena za IBM PC AT brez vinčestrskega diska je ? 3995. Delovni sistem v tkim. Byte konfiguraciji (dve diskovni enoti, 256 k zlogov RAMa, prikazovalnik, barvna podpora, vmesniki in DOS) ima ceno okoli $ 5700. Za standardno Byte konfiguracijo z vinčestrskim diskom za 20 M zlogov pa je cena okoli $ 6700. Sistemska enota Sistemska enota, je za kakšno colo (2,54 cm) debelejša od PCja. Diskovne enote imajo polovično višino in so sivkasto rjave barve. Na sprednji strani je tudi vključitveni ključavnica (kot pri avtomobilu). Bistvene spremembe so v notranjosti sistema. Najprej je tu mikroprocesor 80286 s taktno frekvenco 6 MHz. Ta procesor je pravi 16-bitni procesor in ima napredne zmogljivosti za upravljanje pomnilnika do 1 G zloga (G za giga). Procesor 80286 lako deluje v dveh načinih. Z operacijskim sistemom PC-DOS deluje v "realnem naslovnem" načinu, v katerem emulira tako procesor 8086 kot 8088 ibmovega PC. V tem načinu ima 80286 le' neposreden dostop do sistemskega oomnilnika z obsegom 640 k zlogov. V drugem na-Sinu z operacijskim sistemom Xenix pa ima 80286 dostop do 16 M zlogov fizičnega pomnilnika. IBM zagotavlja, da je AT 2- do 3-krat hitrejši od PCja. Glede na taktno frekvenco je ta sistem dejansko hitrejši za 25%, nadaljno 40%-no povečanje pa nastane zaradi 16-bitnega podatkovnega vodila. Konkreten preizkus je pokazal pohitri-tev za 150%, kar je 2,5-krat hitreje kot PC. Minimalni obseg pomnilnika je 256 k zlogov, maksimalni pa 3 M zloge (pri uporabi petih razSi-ritvenih vtičnig plošč s po 512 k zlogi). Diskovne enote AT uporablja nov tip diskovnih enot s po 1,2 M zloga. Te polvisoke enote dosežejo to gostoto s posebnimi diski pri 96 tpi (tpi je track per inch, tj. število stez na colo) v primerjavi z 48 tpi pri PCju in s 15 sektorji na stezo namesto z 9 sektorji na stezo pri PC-DOS 2.0. Te enote lahko preberejo standardne 360 k zlogovne diske. V ATju je dovolj prostora za dve takšni enoti. Zaradi združljivosti s PC je mogočo instalirati standardno 360 k zlogovno diskovno enoto namesto druge diskovne enote. K dvema diskovnima enotama za upogljive diske je mogoče dodati vinčestrski disk obsega 20 M zlogov. Ker je višina te enote polovična, jo Je mogoče instalirati namesto enote za upogljivi disk v sistemsko ohišje. Druga materialna oprema Razširitveno vodilo v AT omogoča določeno združljivost z vodilom PCja, hkrati pa se lahko uporabijo tudi razSiritvene vtično plošče, ki uporabljajo dodatne podatkovno in naslovno linije procesorja 80286. Novo vodilo jo povezano na dve ločeni priključnici, in sicer na 62-no-žično (IBM PC) in dodatno 36-nožično za 6 vti-čnih plošč. Dve vtični plošči pa lahko imata le po eno 62-nožlčno priključnico. AT je mogoče na sprednji strani zakleniti (izključiti in vključiti) s ključem. Tako se zaklene tudi tipkovnica, med tem pa se lahko izvaja dolg program ali pa je sistem vključen v mrežo. AT ima serijske in paralelno vmesnike na vtičnih ■ ploščah. Ima tudi uro in koledar (v CMOS vezjih). Posebno stikalo na matični plošči pove sistemu, kakšen prikazovalnik jo priključen. Operacijski sistem PC-DOS 3.0 PC AT deluje z Izboljšanim operacijskim sistemom PC-DOS, ki nosi oznako 3.0 in upošteva arhitekturo ATja. Pri prvi uporabi sistema s PC-DOS 3.0 se mora uporabiti začetna (zagonska) rutina, prek katere se definira število diskovnih enot, obseg pomnilnika itd. in ta informacija se shrani v posebnem CMOS pomnilniku (ki je trajno vključen podobno kot ura) . Ti podatki se upoštevaju pri vsaki vključitvi računalnika. PC DOS 3.0 podpira visoko zmogljive enote za upogljivi disk (1,2 M zlogov na enoto) za standardne eno in dvostranske diskete ter enega ali dva vlnčestrska diska. Ti diski se lahko uporabljajo v različnih kombinacijah. Visoko zmogljive disketne enote shranijo 600 k zlogov na eno stran diskete, in sicer na 80 stezah s 15 sektorji na stezo, štirje novi ukazi (Format, Backup, Dlskcomp In Diskcopy) podpirajo te vl-sokozmogljive enote. Ukaz Backup omogoča selektivno shranjevanje v treh kategorijah: — shranjevanje zbirk, modificiranih po zadnjem shranjevanju — dodajanje novih zbirk na shranjevalni disk in — shranjevanje zbirk, modificiranih po določenem datumu Eden najprlvlačnejšlh novih ukazov je Device, ki omogoča Instalacijo virtualnih diskov. Takšnih 24 virtualnih diskov, ki se Imenujejo tudi gorenje Zaslonski terminal PAKA 3000 je računalnišl Cena tega paketa bo ?! 149 in z njo naj bi IBM konkuriral operaci j skemi.i sistemu Concurrent PC-DOS (Concurrent CP/M-86 Version 3.1 z émulacijo sistèma PC-DOS) podjetja Digital Research, ki ima podobne zmogljivosti in cono. Seveda pa se lahko na Concurrent PC-DOSu izvajajo tudi vse aplikacije sistema CP/M-86. . • Napovedani operaćijski sistem Xenix za AT se bo podobno kot TopVlew pojavil šele v prvem četrtletju leta 1985.. Ta sistem je omejen na tri u-pórabnlkó, saj ima AT lo.dvoje serijskih vrat. Xenix ima prijazno uporabniško lupino, ki je podobna Multlplanu, trenutno edinemu aplikacijskemu paketu, ki ga ima IBM za Xenix. PCjòvska nezdružljivost IBM opozarja, da naslednji, materialni moduli PCja ne delujejo v povezavi: z ATjemi — Standardna' PC tipkovnica . -, . — paralelnotiskalniška vtična plošča ^ — pomnllniška plošča za 64 do 256 k. zlogov — plošča za asinhrono komunikacijo (serijska vrata) in • razširitvena enota Zelo verjetno je, -.da tudi vrsta proizvodov dosedanjih proizva jalcev vtičnlh :plošč. ne bo delovala v PC ATju., IBM opozarja tudi na programske pakete, AT niso uporabni! — BPI System Accounting 1.0 — Peachtroc Accounting 1.0 ~ EasyWriter 1.0 — pfs: File and Koport 1,0 ' T- VlslCallc 1.0 in 1.1 — Basic l.X in 2.x --' Flight Simulator (Microsoft) ki na Danes deluje,AT le v načinu realnih naslovov s sltemom DOS 3.0. V tem načinu je operacijska hitrost ATja 2,5-krat večja od hitrosti TPCja. AT je zanimiv za obdelave, kot je zbiranje podatkov, saj ima.16 prekinitvenih ravnin in 7 DMA kanalov. DMA krmilnik uporablja takt 3 MHz, kar je dokaj hitro. DMA kanali O, 1, 2, 3 podpirajo 8-bltni prenos v okviru 16 M-zložnega fizičnega naslovnega prostora v 64 k-zložnih blokih. Kanali 5, 6, 7 podpirajo 16-bitni prenos v 128 k-zložhih blokih. Kanal 4 se uporablja kot kaskada kanalov O, 1, 2, 3 k procesorju 80286. IBM je dokumentiral DMA krmiln.lk za AT v priročniku. PC AT je sicer zanimiv računalnik, vendar njegova glavna uporaba Sele prihaja z učinkovitim večuporabnišklm operacijskim sistemom, kot je -Unix.. Bolj izčrpne ocenitev ATja bo možna šele, ■kp bo zanj dobavljiv tudi Xenix. .Zbirni podatki za IBM PC AT Izđelovaleci, IBM Entry System Division POB 1328 Boca Raton, FL 33432, USA Procesori Pomnilniki 16/16-bitni Intel 80286, takt 6 MHz 256 k do 3 M zlogov , Diskovne enotei , enota, za upogljivi disk premera 5,25 cole, 1,2 M zlogov trdni disk:za 20 M zlogov kot izbirna možnost enota za upogljivi disk premera 5,25 cole, 360 k zlogov kot izbirna možnost Operacijski sistem: IBM PC-DOS 3.0 V prihodnosti dobavijlvai DOS 3.1 in Xenix Programska oprema: IBM PC Basic 3.0 Cenai Ž diskovno enoto li2 M zlogov ■ ' ■■ , , ■■■...; : 3995 Kot zgoraj in z monokromatičnim prikazom, barvno grafiko, drugim diskom (360 k) in DOSom ... $ 5469 Z diskom 1,2 M, trdnim diskom 29 M zlogov, 512 k pomnilnikom - ... $ 5795 Kot zgoraj in z monokromatičnim : ■ prikazom,, barvno grafiko in DOSoiii ... $ 6694 i A. P. Železnikar OOHACA GRAFIČNA OPREKA SNOVANJE, PREDSTAVITEV IN IZRI80VANJE CRNOBELIH BLIK V Odseku za računalništvo in informatiko Instituta Jožef Stefan v Ljubljani ob podpori Raziskovalne skupnosti Slovenije razvijamo, implementiramo in prototipno izdelujemo grafično aparaturno in programsko opremo za programiranje, predstavitev in izrisovanje örnobelih slik na družini računalnikov Iskra-Delta ter DEC pod operacijskimi sistemi RT-11, RSX-11, VMS ter njihovimi domačimi izvedbami« Na sedanji stopnji razvoja lahko ponudimo končnim uparabnlkom ter računalniškim proizvajalcem paket grafične aparaturne in programske opreme, ki obsega: - standardni grafični programski paket GKS za računalnike pod operacijskim sistemom VMS; - grafični procesor kot dodatek za videoterminal KOPA 1000 oziroma DEC VTIOO} - grafični dodatek za risanje na matričnem pisalniku DEC LA-12Q{ - grafični vmesnik za risanje na matričnem pisalniku FACIT AS^Oj V bližnji prihodnosti pa bo dokončan razvoj naslednje grafične opreme s - digitalizacijska tablica; - grafični procesor za videnterminal Gor¥?njèj - programska knjižnica programiranje grafike na miniračunalnikih tipa DEC PDP-11 in LSl-11 in podobnih računalnikih Iskra-Delta ter na podobnem računalniku IJS PMP-11; 6RAF-100 GRAFIČNI PROCESOR ZA VIDEOTERMINAL KOPA 1000 (VTIOO) Institut Jožef Stefan je razvil in izdeluje grafični procesor GRAF-IDO za vgradnjo v videoterminal Kopa 1000 oziroma VTIOO. S tem dodatkom pridobi Videoterminal zmožnosti grafičnega terminala z ločljivostjo 650 X 240 svetlobnih točk ter pri tem ohrani vse lastne zmožnosti alfanumeričnega terminala. Bistvena prednost tega grafičnega procesorja pred uvoženimi procesorji tega tipa je v velikem številu (16) nivojev svetlobne intenzivnosti posamezne točke. To zmožnost procesor GRAF-100 izrablja za navidezno dvakratno■povečanje ločljivosti s pomočno operacij za odpravo stopničenja (anti-aliasing) - zmožnost, ki so jo doslej omogočali le grafični procesorji najvišjega cenovnega razreda. Zmožnost risanja z velikim Številom poltonov med črno in belo barvo omogoča uporabo tega grafičnega terminala za upodabljanje prostorskih objektov v strojništvu, gradbeništvu, lesarstvu, elektroniki in drugod, LAGRAF-120 GRAFIČNI DODATEK ZA RISANJE NA MATRIČNEM PISALNIKU DEC LA-120 Grafični dodatek LAGRAF-120 omogoča uporabo matričnega pisalnika DEC LA-120 za rastrsko risanje z visoko ločljivostjo. Pri tem tiskalnik ohrani vse svoje zmožnosti za alfanumerično tiskanje. Dodatek LAGRAF-120 omogoča risanje z ustreznimi ukaznimi nabori, ki so kompatibilni z DECwriter IV-RA. Velikost in poraba električne energije sta manjši v primerjavi s podobnim dodatkom Selanar SG-120. Vgradnja plošče je zelo enostavna, tako da jo lahko izvede vsak brez posebnega orodja v nekaj minutah. « * institut "jožef Stefan" ljubljana, Jugoslavija » gorenje Gorenje Procesna opr&ma, n: sol. o. Celjska 5 a . ' : S3320 Titovo Velenje Jugoslavija. ■ : v Telefon: (063) 853321 > . Telex: 33547 yu tgove ■ Zaslonski terminal PÀKA 3000 Model TP 103 ' : ■ • ■ ' ' y -.rf -' v r /s' j- •.^fr- ' ■ . ' . , ^ ' < Ekranski terminal PAKA 3000 Model TP 103 ' ' " 1 Ž" j: i f . v v « t r ft ' ' rt - il 'i > ■r ' "ž ^ H ' À ^ ^ v . 'J v ■> - ■/S v 4 •> i' y' 1 / t gorenje HP- ona Tehnične specifikacije Tehniči