ö'o informat ca SISTEM ZA ŠALTERSKO POSLOVANJE V BANKAH IN NA POŠTAH ® sistemi delte Sistem za šaltersko postovauije je sodobna računalniška qarema za d^ v bsmkah in na poštah, opremtjen z ustreaio programsko opr^rro. Sistem (»nogoča samostojno ažurno (Kjstovanje - od posa-meznili oparatìvntii del na šalterjiii do zajema podatkov za nadaljnjo otideia^«. Deluje lahko povsem samos^no ati v povezavi z glavnim računalnikom (pwenos informaaj je rm^oč prek stalno n^yetih ali navadnih telefonskih linij). Delovanje sistema tudi ni flodCar, Ljubljana; B. «orvat, Hsrlbor; Handild, Sarajevo; S. Mlballđ, VarsSdln; 8. Turk, Zagreb Slavni in odgovorni uredniki prof. dr. Anton F. Seleanlkar TahniAni uradniki dr. Rudolf Murn EaloSniAkl sveti T. Banovee, Zavod SR Slovenije ta Btatlstlko, Voiarakl pot 12, 61000 Ljubljana; h. Jersan-Blali«, DO Iskra Delta, Pamova 41, 61000 Ljubljana; B. Klenenöl«, Iskra Telanatlka, 64000 Kranj; S. Saksida, Institut >a sociologijo' Universe Bdvarda Kardelja, 61000 Ljubljana; J. Vlrant, Pakultata aa elektrotehniko, Triaika 25, 61000 Ljubljana. Uredniitvo in uprava■ Infornatlca, Parnova 41, 61000 Ljubljana, telefon (061) 312 988; teleks 31366 Y0 Delta. Letna naročnina se delovna organlaacije anaSa 5900 din, sa aaaabne naročnika 1590 din, sa Studente 490 din; posaaesna ItaviIka 2000 din. Številka Uro ra&unat 60101-678-51841 Pel financiranju Sasoplsa sodeluje Rasiskovalna skupnost Slovenije Na podlagi nnenja Republiškega koniteja sa in> foriDiranja it. ?3-eS, s dna 29. 1. 1986, je öasopla oproifien temeljnega davka bd prosata prolsvodov Tisk« Tiskarna Kreslja, Ljubljana SraflSna oprema! Resto Kirn A'.P.žalesnikar B. Furht V.Hllutlnavld J.Sabjek-Dolinéak D.Patkovid A.Ruj 14 A.Klofutar H.Halekovlii V 8 E B I H A 3 Overlapping' A Paradig» of Parallel and Sequential Processing 18 A Survesr of Hlcroprocassor Architectures for Henory Kanagament 37 Operativno nefrtovanjt) gibanj« vlakov 45 Optinal Code Qenaration for Sose Special Classes of Machines 48 Praglad paralelnega progra-Diraiija 60 t^rinjeita uahaniSkog dokaii* vanja teorema u rjeiavanju iapllkacionog problems sa t-savisnosti u . relaclonin basama podataka 68 Nova raSunalniSke generacije ei Kovice in asninlvostl B2 Avtorsko abecedno kasalo časopisa Informatica, letnik 9 (1986) informatica Publlihad ,b]F Informatika, Slovan* Soelaty for InforaatlcB, l^araova 41, 61000 Ljubljana, Yu-Boalavla VOLUME 10,19^ - No. 2 Editorial Board t T. Alakald,. Baogra«; D. Bltrakov, Skopja; P. Đragojlovid, Dijaka; 8. Hodlar, Ljubljana; B. Horvat, Narlbor; A. Kandiid, Sar«Javo; B. Nihal id, Varaidin; S. Turk, iagrab Bditor-ln-Chiaft ■aaeutiva Editori Dr. Rudolf Hurn Publiahln« Council t t. Banovac, tavod SR Slovanija la atatiatiko, Voiaraki pot 12, 610*0 Ljubljana; X. Jaruin-BlaliS, DO lakra Dalta, Paraova 41, 6Ì000 Ljubljana; B. Klasanfite, lakra Talaaatlka, 64000 Kranj; 8. Bakaida, Inatltut la sociologijo Onivara* Edvarda Kardalja, 61000 Ljubljana; J. Viraht, rakultsta aa olaktrotahniko, trlaika 2S, 61000 Ljubljana. Haadguartarai Inforaatica, Paraova 41, 61000 Ljubljana, Yugo-alavia. Phonat 61 31 29 8S. Tala«t. 31366 yu delta Annual Subscription Ratei U6$ 22 for coapanies, and 089 10 for Individuals Opiniona aapraaaad in the contributions are not nscGaaarily charad by tha Editorial Board Printed byi tiskarna Kreaijs, Ljubljana Daaignt RaatO Kirn C 0 TENT k.P.Salssnikar B.Furbt V.Hilutlnovid J.Sabjak> Doliniek D.Patkovid A.Rulid A.Klofutar R.Halekovld IB 37 46 48 60 66 SI B2 Overlapping« A Paradigm of Parallel and Sequential Procaaaing A Survey of HtcreprocasBor Architectures for Memory Hanagamant Operative Planning of Train HovaDent Optlnal Code Generation for Some Special Claesea of Machines Developaent Prograoming of Concurrent Application of Mechanical Theorem Proving to tnpllca-tion Problem Solving for t-Dapendencies in Relational Data Bases New Computer Generations News Author Index of Inforaatica 9 (1986) OVERLAPPING: A PARADIGM OF PARALLEL AND SEQUENTIAL PROCESSING (*) Anton P. Železni kar Iskra Delta, Ljubljana UDK: 681.3:519.712 Abstract* rn this article a philosophy of the so-called overlapping approach basically derived from,the nation of overlapping algorithm [1, 2) Is presented. In the framework ot this approach two basic constructs are defined; ' the overlapping (0AM) and the metaoverlapping abstract niachine (MOAM)* These constructs represent parallel-sequential problem solvers. Several formal definitions concerning the 0AM and MOAM are given (23 deftnlttons) and from these theorems are deduced (13 theorems). It is shown how an 0AM Impalements a sequence of parallel, actions (processes) and how by an MOAM the parallelism can be "Increased." OAM's and MOAM's can be easily modeled by some well-known parallel architectures (hypercube, bus, switching system) and also by a parallel progranming language. Keywords. Abstract machine, action pattern, action pattern transition, action set, arbiter, grid processor, left .state pattern, library ot logical schemes, logical scheme, metaaction, metaoverlapping abstact machine, metaoverlapping rule, metastate, . parallel processing,, pattern domain, pattern shape, problem solver, • process diagram, processor grid (multidimensional), processor space, processor subspace, overlapping, overlapping rule, overlapping rule base, overlapping signal, overlapping step, overlapping subrule, right state pattern, state set, stat,e pattern, state pattern transition, subrule set, wait state. 1. Introduction This article deals with the notion termed overlapping as a systematic (algorithmic) approach how to master problems in s processor array (grid) environment. Problems can probably be decomposed in sequences ot parallel processes. Overlapping approach solves the problem decomposition in a specific, particular way>and can put the capabilities of emerging-VLSI technology into effective function. Overlapping approach can be faaily adapted to be performed on various parallel architectures like hypercube, bus, systolic, shuttle netwoi^k, four nearest neighbors, cross-bar switch, etc. The overlapping approach basicly derived Crom overlapping algorithms [1, Z) shows some promise ' for realizing massive paral lei i sm and it can be viewed as a method for' designing special processor arrays. This approach can lead to an. algorithm design and also to programming methodology. Parallel logic progransnlng (parallel Prolog, guarded Horn clauses) can be used to program overlapping models efficiently. Under limi tedi conditions overlapping models can be simulated by von-Neumann computers, using highlevel programming languages. (*) The manuscript of this article was prepared as author's lecture at the Hokkaido University, Sapporo, Japan, held on November 6, 1885. This article proposes a framework for realizing the potential, termed overlapping. Overlapping needs a machine, a processor array where node processors have some memories which can be down-loaded for particular (unctions. Several appropriate consDerclally avalble and non-commercial (universities. Institutes) multiprocessor systems exist by which' the overlapping approach could be realized (3). In this phase of Investigation overlapping is viewed' as a hardware-oriented methodology for constructing special-purpose processors. It can also comprise an abstract machine, algo~ rithn.development methodology etc. 2. Philosophy or the Overlapping Approach (1) There exists a grid (array, space) of processors which constitute an abstract (unlimited) processor space (multidilnensfonai, In general). (2) In the processor space there Is a subspace (mechanism) dedicated for control purposes. (.3) There exists a problem (user, Input problem) which will be solved by the activity In the processor space. Constructively, there Is not clear yet in which way the problem will be solved by means of processor space. (4) For the givun ppoblfni. some kijid oi' jni-ttnl state p:)!tern ovftv the pruopssov space Is iiCPiU'd- This pnttern will !>« gpnerated for a given p poti I cm by a specinl, initial opnraltir (sec Inter, in the lORlcal Sf heriKs I. (5> The tcnn pattern has to be pxp)a i ned. Geno-rally, a pattern is a non-eomplfte array of entitios which is se !fgovern inp, but it can t>e rnapptd also onto processor space. In sotno way, indiccs of array entilips and indices of processors in a processor space do eorresponrt. Entities of a pattern array can bo dirfctly mapped Uilo processors 4 registers, memories). (6) There wi 1 i be spvnrnl Iflnds of pftttern entities as states onrl .ictions. In the processor space there will be state and action patterns, in overlapping suUruies only state patterns. The so-cali ed.arbi ter funclion will guncrate actions as consequences of state subsets causing action pattern in the processor space. Pattern entities wi U be symbols represent i risj spe-cKiti (problem solving) states and actions. (7) A problem (3» will be solved constructively and the way of constructive solution will be c.iiled the overlapping approach. For tills approach additional constructs are needed. (8) ]n (S) stale and action patterns were explained and In (1) the processor space was introduced. In (5) and,(6) the correspondence of patterns to processor space was explained. [ly means of state and action patterns the overlapping process in the processor space will be conducted step by step. (3) For a stepwise conduction of the overlapping process the notion of a particular rule (similaf to rules in expert systems) is necessary; such a rule is called the overlappins; .rule. In the next paragraphs the mechanism of the overlapping rule will be developed. (10) The over l,ippt ng rule (OR for short) will be , defined pa.i'1 by part. An OR will consist of two parts: a non-enspty subrule set and an arbi ter. (Ill Subrule i6 a rule ot the torm IF state pattern THiJN ■ OVERLAr_BY state_pattern Subrule is an overlapping rule; it is a preactlon rule, where actions will be performed later after using the arbiter. The execution of a subrule represents an overlapping operation, 'described in the next paragraph. (12) A subrule has a left state and a right state pattern (noncompleto arr^iy of states). Üy a subrule execution lusagc) all of left state patterns included in a processor space will be scarchnd and each of the founfi left state patterns of the subrule will be overlapped by the rigiit state pattern of the subrule In the processor space «e.g. (n processor memory). Here,, overlapping is not a replacctiicnl. The states of the rifttit s t fit o |ia!li:rri ivi li be stored ( aüciiiiiu 1 ii I fit ) in tlio hit'inur i t'S ">' pal tern cor rispondi n(! procossors. Ti)o result of a sulirule cxocutinn ( npp 1 I fa l I o;i) over tlie processor spin'ff is iiccuini) in t I on of some states in some processor of the procf'ssor space. Kii'iiuj r I es (!3> In thf! siktne systeinatK: way as appi lea t ion of a subrule was defined, an ap() 1 I en t ion of a subrule set over the processor spnjt-can be defined. For each subrulp in a subrule set the procedure desuribiMl in (12) has to be executed, ily this, additional states are accuniu I a ted (stored) in some memfirif'S of the processor spupe. (14) Dy overlapping 'applying subruHis) sonic processors in the grid have accumula t od more than one state (includiriK the original processor state befope ove r 1 ajjp 1 iij ) and in these processors ttf.ler termi na t i tij; overlapping <13) an arbitration has to be performed to decide which action in itie processors with more than one acr-'umu 1 a I ed Slate will occur. For this purpo^ji.-, lo each suhrule set an arbitration futiction is defined, calird the arbiter. An arbilei-win produce a single action i-n the processor havtrit; more than one aceuimi ta t ed stato. This action (its symbol) will be Stored and executed to produce a problem function, n^sel tSip acouiuu 1 a I od staios and ger>erate a problem dependent now pt-'ji'cssor slate. Actions being performed in a parallel way in different processors can cosrmiu-nlcalc among eaci\ other; these aco the well-iiriown corimiun i ea t i on probi eni", among parallel processes. (15) Arbiter is a function being defined over a set of state subsets producing n nction symbol belonging to tlie aclioii set. (IG) A subrule set and an arbiter assoeiJiied to this subrule set const i tute a pair called the overlapping rule. Procedures described In (11) to (14) represenl the so-called overlapping rule application. C17> Overlapping rule application will be termed also overlapping step. A problem (3) will be solved by several overlapping steps. (18) A problem solver has a base of overlapping rules (e.g. rules of knowledge etc,) and can use the processor grid for solving problems. In this case, the definition of a program for overlapping rules application (logical sahertie) v\;i 11 be necGssary. All overlapping rules needed to s"lvfi a problem by a particular sequence of overlapping rules are elements ot the so-called rule base or briefly baso. (19) L(ät us define the so-called logical schemc for applying overlapping rules wlieii. solving H problem. Operators in the logical scheme are synibols (names) ropre-sentlng overlapping rules in tin- rule base. Rule symbol In the logical scheme represents the rule call, I.e., the application (execution) of the overlapping rule. In the loffical scheme ther« is an initialisation operator at its beginning, there »re rule calls, ff statements and labels (as described later); (20) All left slate patterns of subrules, tic-longing to a subrule set of nn overlapping rule arc travelling tniowinK) through ttie processor space. The travet I ing procc.ss is systematic and starts ut some "hpg i tin i nt; edge" of Iht.- processor sp.ice. Tho processors of 'the space are signalling wIk/ii a patloni state is bcconH nt; equal lo I lie processor origlimi slute. Plieso signals are a 11 r I Im t by tlu* pus it ion i cd'H-d l-nates, Indieesi nf tlii; signalling pruees- sor In the s()<)(;«. A limiiitür processor in the p roe; p s sor suljsitnci? ^iittiuls l!ic iiiclu-siòn 0 1 a.loft st.itc ji.Htf.-rrs i ri ihu processor stat« p.-ittPi-n and in Ulis cas« the cor rtsponii i ng rigtit stale pattern is stori'd ( » t'l'ijpnu i a t nd J in lh It hp sl] over lapi> ing_rul e_ca 11 to_rule_attributed_i f_statomont , (24) Logical scheme is also a program for processor allocations to-parallel actions in the processor space. A rule call in the scheme represents severe;! inherent and probleiri solving operations being the following: (a) searching for all left state patterns of the subrule set in- the instantaneous processor state pattern; (b) overlapping of each in the instantaneous processor state pattern occurlJig left state patterns of subrule set by the corrcspoi'ii ng rlRiit state pattern; (c) parallel arbitrating In processors having accumulaii>d muro than one stale after overlapping by transforming these states to actions; (d* parallel execution of problem solving actions from (c), reseting the accumulated states and de t ermi nig the new processor state. '25i Actions rtfsulting by arbitration In a rule call reprosenl p.'i ra I I e 1 prohiefn solving processes or pnr:illel sijì)[)ro(;pnnis and have to In: problem (usor) dofined. (2GI Sumo rciiuu'ks to tiic initial stale (laltern genofation in tlie profinssor space sir?? necessary. Ho fore the abstfict inaclune t>ii-glns to apply ovcrlappi nt; rules accorili:ig to logica! solieine, the proficssor initial state piittern has to be gtMierat.ed otherwise the rules can hot be applied. This pa L turn is pu1 into the prueessur spu.usr ijy a special operator at t tie beg inn inf.; of the logical scliomc. This first operator can . also clear the processor (state) space put Ing all the processors in the wait state 'W and then Sni t iali s ing ths proper processoi^s with corresponding states. (27) The state initialization operator is nut an overlapping rule and in the logi.c.il seherne.-it is recognized as such. Thase of overiappiiig rules; (f) logical sc'hcnie for overlapping rule application and i n i t i A] i za i I oti of processor space (logical scheme is a processor subspace driven pr^i;ratio. We say' that a problem will be solved the overlapping approach. by (29) Let (IS explain-.the—overlapping opproacti for solving a problem as a seri a I-para11 e 1 processing. For this purpose, the processors. in the processor space are named (numbered, indexed) and a process in a processor is denoted by a(il; here, 'a'-rienotcs a problem solving action as described previously and 'i' is the processor Index. Actions a[i) can comnunicate among each other in tJic framework, of i»n overlapping step, A logio.il scheine represents a sequence of parallel processes groups where parallel processes occur within the overlapping rule call. So, for example, we obtain the process diagram shown In Flg.. 1 (numbers in llie scheme atn BEGIN Init I allZi I «(13! atl) i 0(2) a[3] END --------- ...............: ft[ioi I a[13| . : all5] F!g. 1..Process (aelion) r! i a grain wš I. h pro-' cesser indices li) lu'i tig 1! oc.-i l I'd represent Kie processor Indices in the processor grid). Here, aciloris a(ll, ft(l2!, and atlìl can communicate among each otlier In thf first' Overlap|>f rig step; in the second overlnp-ping step such communication Is possit)le among actions a[2|, aC3], atiO], a[13], and a[15]. (30i Example: Adding two binary numbers by overlapfiins approach. Let « pröoessor grid represented by processor wait states bo given: w w w w w w W W w w w w w w w w w w w w w w w w Let a processor subspaee for control purposes be given. The set of states has three elements: w, 0, 1 (where 0 and t represent binary ciphers). The set of actions has three eleroentsi w, m. r (where w Is wait action, m is action for replacing the initial wait states w (jy 0 an'isr's (for oxecMting loffical schi-me, s I gnx ! I i ut:. ctimmitn I cn t i on.s I'tfr.); this griil i .s po t en i i 1-ly »Ì1U milfoil; eivoli p l'oc t>s so v has » Uh'.'i 1 BEO IN ni(2,21 mi .ì , 5 ] ; (Inìt) rl2,2) rl2,41 1 : rts.ll i • l w » •• J ' r[3.31 ; r[3,4.1 : , t r[2,! 1 rtI.Sj : r(3,l.l rl3.2] ; r[3,3) ; r [ 2 , 2 J M 2,. 4) P13.41 r(.2,3) i ■ ria,SI ; rt3,21 ; p [3,'4 1 : p(3,51 END Flg. 2. Parali (.'1-sćfjuont i fl 1 process diagram result Ing•trom Ihe example of adding two binary nuiubcrs rtiemory and can oxecuie actions (problem solving subprograms t ; processors In the grid ape we 11-conned(,'d fn some respcct so they can ensure basic machine (inherent) operations; tor instance, processors are at>le to search Ic/t state patterns of a rule throughout the processor space; they arc able to perform overlapping of states In each particular processor; tiicy are able to execute arbitration in each particular processor (I.e. deternitnlne actions in dependence of the overlapped, states); S is a state set; the set cardinality has to consider s^ufficient number of distinguished states to solve a problem; states are symbols of the so-called stale type; this set is potentially unlimited; A is an action set; this sot represents an ordered library of action subprograms dedicated to pgrforin partial functions needed in the processes of problem solving! set A is potent lai]y uni imi ted; B is ati overlapping rule base; overlapping rules can be exprèssed as particular information type structures adequate for storing and usage; base B is potentially unlimited; L is ä library of logical schumes; a scheme calls overlapping rules when,solving a particular problem; a logical scheme conducts a problem solution by rule calling; library L is potentially unlimited. Sets S and A, Ijase B, and library L nr« generative sets, nuring their life cycles these sets will be modified; the cardi mil ity of these sets wilt be variable; sel eiomonts will tie added rtiid deprivotcd In tiopendencc of problem envi-rotiinent rcqui ri'monls ■ fAM is oiiviousiy a problem solvfr. Willi leitrnhin ctipabi 1 It I esWmprov i ng its solving powtfr tlirouifti its ill"« cycl k factors, where 1 is the set of all integers, and let S be a finite non-empty set of states. A mapping sp(k) (sp denotes a state pattern) of a set M{k) into a set S, i.e.. 3p(k) = { can be omitted. An empty pat tern is a set■ D e f 1 and {(*, w) ; X EL M{k)i n i t 1 o n 2. If sp(k) Is a pattern sp(a, k) = !(*■'«, y) : (x(l)»a(l>, (X, y) EL split) ft -,.. , xik)*a(k))1, where a KL Kk) and k - .1 . 1.....then sp«». k) is the so-called a-dlsplacement of I li'* ti-rn sp(k) . Definition 3> Two statf? pjittcrtis and sq .= sp(a, k) where '.=' is the relation ai slate pattern ftjii i va 1 enee. Obviouslyj each a-ci i sjjlacemen t of a patterti Is equlvaleot to this iJattern. Definition 4. A pattern sp(k) Is said to be incJuded In a pattern sqik) if EX a EX n(sp(a, k) .INCL sq(k)> iV EX btspik) .[NCI. sq(b, k)) where '< = >' is the logicai ctjuivalcnce symbol, is true. 3.2.2. Pattern Domains Definition 5. Let ♦ N'0'r_EL S, where 'Ntyi'^EL' denotes 'being not element of; then the pattern r(*, k) = l(x, 7,> ; X EL MU) & z = *\ , k Si 1, 2, ... , will be enllod the k-diniensi ona 1 pattern shape or briefly the shape. Thus, cacti shape is ■ a pattern in I*I or in !w, '*f. Let a pattern sp(k) in S and lei tiie sot ( : (y EL S N {K\ A Z = *) V ( y = w Üt K = ) ) , where 'V represents the logical 'or' operation, bo given; thoil the set coniposition fr+> COMP sp(k), i.e., sp(*, k) = [(X, 2) ; EX yisp(k, x( = y A- f(*, y) = E)ä will be called the shape of a given patiern sp(k). A pattern «;ri(k) tias the shape kl if and only if sp(*, k) .= r(*, k). IVo patterns sp(k) snd Sfjik) have the same shape if and only i f sp(*, k) .= sq(*, k) Definition 6. Let »(*, k) be ft finite non-empty set of k-dIniensi ona 1 pattern shapes. The det;,a I j. D(1;, OAM) of an O.Wl witl be called a set of k-dimensi ona ! patterns In S, i.e., D(k, OA.M) = isp(k) : sp(k! IN s 4 sp(*, a, k) EL B(*, k) & a EL I(k > ), where. sp(*, a, k) is an a-d i splacenient ol' the shapf sp(*, k»; here, 'IN' is the relation 'being in'. Thus the domain D(k, OAMi will be generated by a pair (S, B(*, kj). gptierally, sp(k| and sqik) do not iiuvf: iniiiivM-lenl shapes. The pattern sp(k) Is siiid to In; the- left and the pntiürti s(|(kj the right state pattern of Sil. Two subrulus KH 1 ^ isp l(k), sq_Uk)) and S!4_ 2 = (sp_2(k>, sq.SlkiT are equivalent H and only if EX a(a EL I(k) & sp l(k) = sp 2(a, k) & sq_l, i.e.. SHS = ISRtll, SKt2|, ... , SKtmif. will be called the suhrule set. The application of a given subrulc set to a state pattern sp(k) is defined as follows. Let (t be SRI U EL SRS, where S!i( I 1 - UeftflKk), i-ight ( i j (k l ) and lut sp{k) he a state paticrn. To each -SRI 1 ] atid sp : (x, y) EL r(ghi[ij(a, k) if leftllHft, k> INTL sp(k) & n EL H k ) I can be constructed. Hence, Sl'liJIJ:) 1 nel tides pairs (X, y) with equal elements x and can also be an empty set. -Vow wo construct to a given SRS » iSHtl), ... , SRiinii and to a stat.-pattern sp(k; a set l=ni SV = splkJ V U SPtUfk), i-1 where 'tJ' represents the union operation and inlrodunc tiic equivalence relation 'tQ' dofitied in SV by = OSV From OSV, which is a state subset pattern r hrii^fSy, sulirulc Sil, will ho a p;i i r f^ip'k), sipki^ tif li-il ii.ii-ns 1 ini;i i s \ h 1 o poSW^'iis III S, iviitiri' ,S is till' .set i)f fUu! whiTf, arbeite, (X, y)); C El. powcr_.sot ( H) ^ y EL A Sr X ■ y() ML S .V (X, y I iirt.(t"> ■ - where A is an action set, Is called ths overlapping arbiter or briefly arbiter. The arbiter 13 said to be generally dt'flned In a state set S if arb(zero) = (w, w.) (zero dcnole*s an empty set», ftrb<[zt) = (z, w) whflre y EL S, and w EL C & arb = art) arb = arblC-^-lwO where C EL power„set m 2,3, , , x[mi), by which the possibility of defining arblx, x) etc. Is achieved. Kiirther, arb can be determined by some kind of automaton calculating the new state always when the second state by overlapping was accurmilat.ed . This approach i educes the nuinber of memory state ipcatlons in local memories to Definition 10. A pair (SRS, arb), where SRS is an overlapping subrule set and arb an overlapping arbiter, is called the overlapping rule OH OP briefly the rul.fei The application of a rule OR - (SRS, arb) to a state pattern sp(k( is determined by the tra,nsforma-tion SRSlsplk)) » CSV and the compos i t'i on àrb COMP OSV = spi (k) when OR maps a state pattern 3p Into s new state pattern sp(l)(k). We define ORt sp sp(i](k) = arb COMP StlS(sp(k)) A procedure OP; sp(k) ;-- sp(l](k> is called the overlaping step and is performed by an overlapping rule call 'or' in the logical scheme. Definition 11. Different overlapping rules conform the so-caJled base of overlapping rules, briefly B; this base Is ade-quatly structured. So, B is a structured set of OR's. i.2,4, Logical Scheme According to paragraphs (18) to (27) In Chapter 2 we have the Collowing: Dellnitlon 12. Is a program (algorithm) LS : LSdni t, or[ 1 ]., .. . o_sig(11, Logical scheme LS ort-r], . , o_slg[rn, whore init Is the state pattern ini t i a U za tfan operator, orili (I = 1.....r) arc overlapping rule calls for rules belonßing to rule base B, and ossigli I are overlapping signals as described in'paragraphs (22) and (23) In Section a. Schematicallyj tor an LS we have the following segmentai. init; segui; seglll; : seRtr); wliuro for segur(i = I.....r ' tliorels possible labe][i): orli); IF o_sig(i] THEN ...... (iiull : (GOTO, possible labeltpl)). else' - . • (null : (GOTO possible labellql))-ENUIF; If a segment Is at the end of LS or if for a segment scg[j I we have posslble_labelt jl: or.ljl IF o_slg(j! THEN GOTO ond of LS; ELSE . ~ " (nun ; (CiOTO possible label(cj))); ENDIF; then this segment is called the terminal segment of an LS. In the upper two segments of LS M'.and ')' are mctaparentheses, null is a" null statement, ; ' is the alternati"'ve sign, and p, q » 1, .... , r- . • There exists a library Lot logical schemes of type LS within the OAM; this,library Is adequately structured. By Def. I to Def. 12 the construct of overlapping .abst.act machine In Def. O ls completely determined. 4. Basic Theorems for the Overlapping Abstract Machine Application Definition 13- The application of an OAM = (P, S, A, B, L) is defined follows. For the given processo.r grid P a logical schemc LS from library L Is selected. Tii i s scheme rcprosents processes needed for a problem solution'. By initializing operator init of the schcme the processor grid.is state Initialized. Further, logical schemc calJ-s the over-, lapping rules belonging to the base B for execution and controls by means of overlapping signals the further overlapping rule calls. By arbitration within the overlapping rules problem solving actions belonf^ing to A are executed. At the end of the logical scheme the OAM problem solving process Is sloped and OAM is ready to solve another problem. D e [ i n i t i o -n 1 4. ; First, let i«s define the value of a logical schcme within an OA!« application. The value of a legi sal schc^.c in an.0^ application Is the sequence of overlapping signals which In the problem solving process have became the true value. This sequence represents the actual application of corresponding overlapping rules when some left pattern of a subrule of an overlapping rule was Included in the processor state pailern. Now, we have the.following Instances of logical scheme values; ! 1 ) The value of an LS is à finite (possibly empty) sequence of true overlapping signals where the end of LS was attained. (2) The value of an LS is an infinite sequence of true overlapping signals where the end of LS oannot be attained. (3) The value of an LS is a finite (possibly empty) sequence of true overlapping signals where the end of LS cannot be attained. WG say that an application of an OAM is resul- tative in case (1), and non-resuitat i ve in cases ( 2 ) and ( ."ì ) . Definition 15. At t lu? beg inn i 11« m' an OAM - (H, S, A, M, L) application all t hi.' grid processors are In the wait state; this State pattprn caJlPci the wait pattern. After execution of the initialising operator in the selected logical scheme LS the initial pattern ts mapped into the grid state pattern. If execution of the LS has attained Its end and the value, of LS is empty (no overlapping rule could be applied), we write OAM: lsp(lt> "T where lsp ) ) ... ). Now, let :—ntjll denote the overlapping step corresponding to the overlapping rule OR(i(j]1, and let ;==(Ji denote J single sequential overlapping steps. So, the overlapping chain, or briefly the chain, will be introduced by OAM: sp[Ql(k> lUn) spilHk) 11(211 .... ; —(Itjil sp(jUk) n.= i < = > & isp(mHlt) = arbUlmJl comp (n=l SRS(itm]l(sp(in-ll(k))l, where sp(0](k) = sp(k), and spfJKlt) Is called the simple imag^ of sp(k> mapped by OAM. instead of the upper chain we denote briefly OAM(LS): sp(01(ki :== spljHk) or also CAM: sp[0](k) ;==ljl spiJKk) We read ttt For the selected LS the OAM translates the Initial stale pattern sp[ai(k) by j overlapping steps freely Into the state pattern sptJHk). Definition 16. Let over a processai- grid state pattern sp[n-lHk) a terminal segment seg[i[nll of LS (Def. 12! be applied, where -o^sigli[n|1 is true. Here, overlapping rule 0nfi[ii]] is applied lo spi ii~ 1 ) ( k ) , mapping It into state pattern sp[nl arb-ilnj) COMP Kits I i ( n ] I ( spf n-1 ] ( k ) 4 segl1 in)j Is terminal l' applied to spfk) and lot the value of an LS bi' a secjuonce o.sigtKlH, o_sig(i(2n: a terminal LS segment. In this case OAMi sp ;='|nl . sp[nl{k); sp[n)(k) Is called a terminal . image of sp(k> mapped by OAM in n overlapping steps. Deflnttton 17.■ Let over a' processor grid state pattern sp(n-lj(kt a non-tennl-nal segment seglllnl) of LS be applied, where o_signinll is true. Now, 0»(ilnll will be applied to sp[n-ll(k), mapping it imo spini (le); afterward, let the end of LS bo atained without applying an OR of I,S In sptnj(k). In this case we write OBIi(nil: spin-l) If o_s!e[!tin, o_slg(l!2U.....0_sSg{![nn is the LS value, and if OAM was applied to sp(k), then OAM: sp(k) ;==!rj-ll spJn-JKk) & ■ORH[nll: sp[n-l|(k) 1— sp[nHk) ~T This is denoted by OAM: sp(k) :==)n-l] sp(n-ii(k) sp[nj(k) ~T, or briefly by OAM: sp) = sp(k), OAM: sp(k) l== . sp(nl(k), and DAM! sp(k) ; = = . sptnj(k> where sp if OAM: sp ;-- spinoci (5) Xhe value of LS EL L Is empty and the end . ol LS cannot be attdined Proof. In the sense of Def. 14, the application of an 0AM to a state pattern can be elttier resultative or not. [f the application ot an OAM to sp£k) Is resu1tat i veonly ono of the possibilities {1> - <4) Is true. This means that the first overlapping step either exists (in- cases U) - <4))-or noi (in case <1)1. Evidently, in the resultativc case no other possibility exists. if the application of 0A.\1 to sp(k) is non-resuI la t ivo, only one of the possibilities (2) and (5) -is valid. This means that the first overlapping step either exists <2> or not (5).- Evidently, In the non-resulta-tlvo case, there does not exist any other possibility. Thus Theorem 1 is prov(^d. THEOREM 2. If OMW = ( P, S, A., B, L) and for initial state pattern sp(k) for selected LS there is sp(k) EL D(k, OAM), one of the following equi va iences is valid; OA.M: sp(k) ;==|J1 sp(jl(k> & J > 1 < = > EX! spi ]-lMk)(OAM: sp(k) :='U-ll sp[j-!|(k) :— spi j 1 (k) ) : OAM: sp(k) d«=|nl . spSnHk) & n > I < = > EX! sp|n-l|(k)(OAIH: sp(k> ;==(n-ll spin-lKlt) ;— . -sp(n) 1 < = >■ EX! spl-n-l XkXOAM: sp , where 'EX!' means 'there exists exatly one'. Proof, Obvlosly, the validity of equivalences in Theorem Ì follows from Dcfs. 13, 15, 17, and 18. THEOREM 3. If OAM = (H, S, A, B, L) and for initial state pattern sp(k) for selected LS there is sp(k) EL D(k, OA^i) , the following iinpi i cat i Otis arc valid: OAM: sp(l<) = ■ sp( i ] (k) sp[i + jt OA1«; sp(k) : = = sp( i +j l(k) ; OAM! sp(k) :== sp[jl(k) 1== . sp(nl(k> ==> OAM; sp(k) . sp(nj(k); OAM; sp(k) i== sp(i!(k) sp[n)(k) ~T =-> OAM: sp(k) sp(n)(k) ~T. Proof. These implications follow directly from Dels. 15, 16, and 17. ' THEOREM 4. If OAM ^ (P, S, A, B, L) and for initial state pattern sp(k> for selected LS there is sp(k) EL D(k, OAAt), the following implications are valid: OAM: sp(k) spdKk) i OAM: sp(k> ;»=|jl spiiSik) & j > 1 =«>■ OAM; sp ;==IJ-1I sp£Jl(k>i OAJVli sp(k) ;— spll](k) fi OAM; sp n > 1 ^ OAM; sp(k-> spdKk) ;-=ln-ll . sp[n|(k)i O^VVt; sp(k> ;-- spM i(k) A 0;\M; sp(k).;-=ln( spjnl(k) = = > n > 1 & OAM: splki splU(k) ■ sp(n)(k) ; P r o o f. These impJ i ca tlon s follow at once from Tliforejris I and 3. THEOREM 5. , if,. OAM = ( I', S, A, R, L) and for initial state pattern si>(kj l'or selected LS there is sp(k> EL 0(k, OAM), the rol lowing Intpl i cat i on cai, bt- deduced from Def. 18, Theorem 2, and Dcfs. 15, 16, anö i7: OAM;. sp(k) :== splj 1 (k) & OAM(sp(k)) = sp|n)(k) - ==> (OAM: spfk) ;== spijKk) :== . sp[n|(k) <=/=> OAM; sp1 is the sign of logical non-equivftJence. 5. Primitive Overlapping Absttoct Machine (POAM) !n this section we shall deal with a particular ease of OAM having a special type of tiic logical selicnie. TJiiì, LS is, lylUitPul hii i n i l i h 1 i v;u-tlon operator and the Initial stale patlorn can be mapped Into tiie processor grid state pattern by a separate operator before the POAM application. Definition 19. I'he primitive overlapping abstract machine POAM = (P, S, A, B, . PL) is an OAM, where P, S, . A, and B are elements of OAM, and PL is a šdbset of L. Primitive library PL is an adequately structured set o£ the so-called primitive tt)Bical schemes & rOAM: 5pim-l] ćt POAM: sptm-Jt lUtiilJ sp[m)(k) m^l & POAiM: isplti-l](k) ;^-tlln]l . sp[nl(k)^ POAM: spio](k) [idJt spjljtfc) ;--[i[2JJ : —(l[n)J sp(iij & POAM: sp(rn-l){k) :--tI[nill sp[ml(k) [rt= 1 at POAM: sp(n-ll(k) ;-*(i[n]l sp[n|(k) Proof- The ■ validity of Theorem 6 follows from Def. 19, and from the previous definitions and thcor«ins. THEORKM 7. If POAM = (P, S, A, B, PL) and sp(k) EL D(k, POAW), then POAM: sp POAM: splnHk) ~T. Proof. Evidently, t!\e pfoperty of a POAM described In Theorem 7 can be deduced from Def. 19 and Tlieorpni 6. THEOREM S. If POAM = (P, S, A, B, PL> and sp 1 <=> FX! splj-l] (kXPOAM: sp(k) ;==(J-1J spU-lHk) & POAM: sptj-lMk) sp(iMk)); POAM: Sp(k) ;==(nl . sp[nl(k) 4 n > 1 <»} EXt spf n-l I (kXPOAM; sp(k) ;==|n-l| sp(n-l](k) & POAM: sp[il-lj = splnHl!2.~~ & n > 1 < = > EX! sp[ n-:3 I (k MPOAM; spik) ;==|n-l| sptifj-Kk) & POAM: srp(n-l](k) I— sp|n){fc) ~T). The proof Is similar to that of Theoreni 2. The methods of proof of Theorenis 3, 4, and S yield, in order, the following three theorems. THEOREM 9. If POAM = (P, S, A, B, PL) and sp(k) EL D(k, POAM), then POAM: sp(k) ;== sp[U POAM: sp(k) spH ] (k) & POi\M: spdXk) ;== sp(t + Ji(k)i POAM: sp(k) ;=•= sp[i](ki 1'= . sp[n](k) < = > POfW! sp(k) sptiKk) Ä FOAM: sp(il(k) l== . spln](k); POAM: sp(k) :== sp[i](k) sp[nl POAMi sp & POAM: sp(tl EL D(k, POAM), then POAM: sp 1 = = > POAM: spUKk) ■,==ij-i| spUHk); rOAM: sp(k) ;'==Sni5 sp(in)(k) it POAM; sp(k> ;==fnl . spfnXk) = = > n > tti & PO.\M; sptmKk) ;==(n-niä . sp(nl(k)| POAM: sp :==1ml splmKk) & POAM! 3p n > ni & POAM: sp[nil(k> ;==!n-mi sp|nl{k) "T THEORKM 11. If POAM = (P, S, A, B. PL) and sp(k) EL D(k, POAM), then POAM: sp(k) spi IJ(k) & H(JAM POAMere P, S, A, and B aro clfiiients of P0A.\1, and NL Is a subset of i ü. Normal library NL is an adequately structured set of the so-callud normal logical schemes (NLS). An NLS has the following properties: <1) In ni,S there Is not an initial operator named Ini t (like In LS); operator ini t in MLS is an empty Inforiiin t Ion bases in tho so-callfd overlapping-abstract machine. mfjla- (4) Kor a pi von complex sur i al-parallel problem somt initial metastalč patttrn civt?f proees- - sor nielaspace is needed,' This metapnttern will be generateli for a eiven input problem by a special, iniial nietaopera.tor. (see later, in the metaloglcal scheme). (5) Oeneraity, a r-'Mapattfirn Is ä non-coirrplete array of melaslates or metaactlons. Meta-patterns are oecuring tn metaovcrlapping rules anrt tn melaspaco, where metastatc is a presentati ve ot a processor subspace. In some way, indices of moiaarray entities (states or actions) and indices of subspaces In a mctaspace do correspond. Entities of a inetapattern array can be directly mapped into subspaces (into registers or memories,* which represent the corrcspon~ ding subspacps)., (6) There win be two kinds of nietapattern entities: mctasta'tes and metaactlons.. In the mrtaspacc there will "be metastate ' and metaaction patterns tbriefly metapatterns), in mctaoverlapplng rules (briefly metarules) only metastate patterns. The .so-called metaarbiter function will generate metaactions as consequcnces of metastate subsets causing metaaction pattern in (or on the level of> metnspaee. Metapattern entities will be symbols representing specific, (complex ser lai-para 11 el problem solving) metastates and metaactlons. (7) A complex serial-parallel problem (3) will be solved constructively on the levci-of a processor melaspacc through the levels of its processor";., su h space s and the way of this cons t riict i ve solution will be called the metaoverlapping ■ approach. For this approach additional constructs to the existing ones are needed, (8) In (5) metastate and metaaction patterns were explained and in (1), the processor ■ nictaspace was Introduced. In (5) and <6) the correspondence of mo t apa 11 cms to meta. space was explained. By means ot metastate and metaaction patterns the inetaovor1ap-ping process in the metaspace wHI be conducted step by step. (9) For the stepwise conduction of the motao-verlapping process the notion of metarule (metaoverlapping rule) Is necessary. (10) The metaoverlapplng rule (MOH for short) consists of two parts: a non-empty meta-subrule set and a metaarblter. (11) A metasubrule Is a rule of the form IF meta_state_pattcrn THEN OVEHLAP_BY meta_state_pa11ern Metasubrule Is an overlapping rulej it Is a metapreacti on rule, where metaactlons. will be performed later after using the metaarbiter. The execution of a metasubrule represents a metaoverlapping operation, described In the next paragraph. (lì) A met.isubrule has a 1 right metastate pattern ■ of me t as tatest. By a mc (usage, appiication) al patterns included in me in particular subspace (on the meta level) and left nictnstnte patterns win bo ov<.'P 1 ;\()pe(i by pal torn of I he tin.'1 s uh spact; In mouiory o eft motastatc and a (non-cop I et e array tasubrulc execution 1 of left inetastate taspace (niet;ista tes s) will be senrehod each of the found of I hi.! iiictasubrulr tho right nictastnt'! culo 111 tin; inf tall uiftaspace Ifvrl). The metastates of the right melhslate pattern will be stored ( aecumu 1 a t «<ì ) in the memories of pattern corresponding sub-■ spaces. .Thf result of a nictasuhruln execution (ffivitaappl ieat Ion ) over the Hiylaspace is accumulation of some niotastates in some subspace memories of the mctaspaće. (13) In the same systematic way as metauppli-cation of a metasubrule was defined, n metaapplicatIon of a metasubrule set over the metaspace can be defined. For each metasubrule In a metasubrule set the procedure described In (12) has to be executed. By this, additional metastates are. accumulated (stored) in some subspace memories. (14) By metaoverlapplng (applying metasubrul es )"" some subspacei! In the fuetagrld have accumulated more than one metastate (inclu- - ding- the original subspace metastate before metaoverlapping) and in these subspaces after terminating, metaoverlapping (13)- a metaarbltrat ion has to be periortned to decide wh.ieh mctaaction in - the subspaces with more' than one accumiilated metastate will occur. For this purpose, to each ntotasubrul'e set a me t aa rb 11 ra t i on function Is defined, called, the metaarblter. A metaarblter will produce a single ■ ■ metaaction in the subspace having more than one accumulated metastate. This mctaaction (Its symbol).will, be stored rt n<) executed to produce a. first level Uitjicai; scheme fmu'tion, reset the aceumul n t eii metastates and generate a metaprohleni dependent.new subspace metastate. Metaactlons being performed In a parallel way In different subspaccs can communicate among each other these are the communI cat i on problems among parallel processes on the second level of parallelism. (15) A metaarblter Is a function being defined over a set of metastate subsets producing ä, metaaction belonging to the metaaction set. (16) A metasubrule set and a metaarblter associated to this metasubrule s«t constitute a pair called the metaoverlapplng rule. Procedures described in (11) to 04) represent the socalied metaoverlapplng rule, application (metaaplicat i on). The metaoverlapplng rule application will be also termed a metaoverlapplng step (briefly mctastep). A complex serial-parallel problem (3) will bo solved by several metaoverlapping steps. (18) A complex problem solver has a metabase of metaoverlapplng rules (e.g. rules of problem solving co-ordination on the second level of parallelism) and can use the subspace grid for solving complex problems. In this case, the definition of a program for metaoverlapplng rules application (metaloglcal scheme) will be necessary. All metaoverlapplng rules neodetl to solve a complex problem .by ' a parti<;ular sequence of metaoverlapplng rules aro elements of the so-called metarule base or briefly metabase. . (tS) We can now define the so-called metaloglcal schijmo if or applying motaover l.'ipp 1 ria rules when "solving a coinpSe* probh^iii. Operators of the meta logi c« I schi-mc ar« symbols ( iiic ta names ) n.-prcsenl i ng moifiovor-lapping riiU's in the mr.t.-inile base. Mi.'tn-rule symbol in tho mo ni 1 oij I ca 1 so!i.-i;i<' represLMits the meUirulo call, i . f . , Ilio nK.'tnap.U i-n 1 t tsn (niotnoxocu 1 I on ) of Ki'; ...... taovcrl riß rule. ! ti the rnetaloglcal Sfjltemc Vhert» is an inalai ni t I a 1 i 7.a t i on operator mp'tn_lnit at Its beginning, ttiere are mctaruio calls, melo if statements and metalabels las described later). (20) All left metastate patterns of metasub-rules, Itoignging to a metasubrule set of an metftoverlapping rule are Iravelling (moving) throu|;h the metaspace (space of subsftttCt's ). The travelling protuss is systematic atiil starts at some "metabegln-nlng pdge" of the metaspace. The subspaces of the mctaspace are signalling wh(.>n a rnctapattcrri metastatc Is Lieeoining equal to the subspoce original metjistate. These signals arc attributed by the position (metacoordi nates , mota I tuJ 1 ct-s ) of the sig-naillngf subspace l>i the nietaspace. (21) Each motasubrule in the metasubru!e set can have its own monitoring subspace, so, the metaovorlapping thrtiugh the metaspace Is carried out as fast as possible. When the nietaovcrlapping process has reached the so-called "me t a e nd I iiu edge" of the metaspace the metarule metaarbiter function in the subspaces having accumulated more' than one motastato is perforinod, generating mctaactlons. Here, metaactions roprffscnt also execution of particular logicai schpnics from library L, The metaac-11 on pattern In the subspace metaspace re-pres^'nts a d 1 s t r t bu t i o;i of parallel logical schcrr.ti executions to corresponding subspaces. Üy this, the metaovcrlapping step (motaaplylng of a mctaoverlapping rule) Is terminated. (22) A particular sitbspace in the metaspace is slgnTtlling if a meiaovor Lappi ng rule was real.Jy applied. Applifiatlon of a metaover-lappiing rule means that at least one over-la pp'ing of a lefi me tastate pattern in the mete-space metastate pattern by right mel?-stalc patiern was performert. The notion of the wotarule application register is im-porS.isnt at the (urtticr contruetion of the metaiogical scheme. (23) A metalogical scheme is a sequence of meta o rar lappi ng rule call statements, mctalf sta i.cnients, and metalabels. Metalogical scheide MLS is a program (algorithm) of the form MLS =MLS(m_init, m_orni.....m_or[rI, 'n_o_sig(l).....m_o_s!g;[r|), where m_lnlt Is the motastate pattern Initialization operator, m_or(i) (i = 1, ... , r) arp mctaoverlapping rule calls for metarules belonging to metarule base MB, and m_.o_slg[ll are me tao ver lapp i ng signals as described in (23) above. Sohe, matically, for an MLS we have the following segments! m_liilt; ni_seg[l]i m_segt21; ■ . • ; ni_seg[r]; where for m segLll t\ metalogical scheme is u program for subspace allocations to parallel mptttftctions In the subspace metaspace. A metarule call In the nie t a scheme represents several Irihe-rent and coinplex probtorii solving metaope-ratlons being the following'. Ca) searching " Col? all left motastate patterns of the ' riietasubrule stìt in the instantaneuos subspace metastale pattern; (b) overlapping of each in the Instanta,-neous subspace motastate pattern oc-curtng left metastate patterns of me-tasubrule set by the corresponding right metastate pattern; (c) paratici nnc taa rb i t ra t I ng In subspaces having acouniulated more than one motastate after overlapping by transforming these metastat'es to metaactlons; (d) parallel execution ol metaa'ct i uns from-(c), rcsetlng the accumulated nieta-states and determinine the new subspace metastate. (25) Metaactlons, resulting by tnetaarbitrat i on In a metarule call rep^est'nt complex parallel problem solving processes or parallel usage of subspaces. I.e., overlapping abstract machines with selected logical schemes. Here, logical schemes of cxccu-tlng OAM's represent subpi'oblcm actions. (26) Some remarks to the initial motastate pattern in the metaspace and Initial operators of OAM Logical schemes are necessary. OAM's in the problem solving must ignore their initial operators (first level parallelism) and act over the resulting state patterns from the previous OAJVi executions. We conclude, that in sequential problem compositions only the very first OAAi's are using LS's with Initialization operator»! in all following LS applications by OAM's initialization operators are ignored. Definition 2 1. The metaoverlapping abstract machine (briefly MOM!) is a fjuiniuple MOAM = (MP, MS, MA, rm, ML), where: MP 1 s a multidimensional processor subspace grid, called mctagrld, with a subspace for metacontrol purposes; each grid subspace has the properties of the OAM (Def. 0); each OAMtposi t Ion] Sn the metagrid is a quintuple OAMCposltlonl = (P[posttionl, S, A, B, L), where Ptpositlonl represents the processor subspace having the corresponding position index; elements S, A, B, L are common for all OAM's in the metagrid and their meaning is described in Oof. 0; MS is a metastate set simil.ar to state set S; metastates are d i s t igui shai)l e from stalps and their role is to control coniplc>c ppohloin solving' In the metagrid (metaspace); S can be seen as a subset of the set MS; by this, niotastates are elements of the set MS N S; MA Is a motn.i ct i on set similar to action sot A; but actions and mc tàac t i ons aro sein,-in t i ca It y different; »et Ions uro proltlpm solving hijIi-l»rot?rains, Keneratiiig a p.'vrt nf soUilin" itti (,(OAM[gl: 3p( j,g,01(k)- "T) <=/-> e=last[J] & g'flrstl ] ] (OAMlglt 3p[J,g,0t(k) ;==ln[j,gn . sp! j.g.ntglKk)) & q > 0 h=q g=last[hl & ( & ( (OAMlh.g): sp[h,g,OJ(k) 1) h=l g^firsKhl <=/=> r-(iAM coiimnni Icn-tlón). tlip pi'ohlenr is how !n (ionoroposc . I hf input probi ntii into parallel siiliprobl cms , und how to ü(fdom(iosB cacti siibpi'oblein into parallel basic actions. The extremely sequential case (only sequential •processes) ciin be aehlt'Vtd by an MOAM, where in each mctaoverlappitig stc'Pi there is active at most one OAM (there Is always only ono iiiotaac-tlon), and ■ each aotiiigOAM has over Lipping steps with at most one action, (n Throrpm 13, this case Is within limits h = I, ... , q and g = firsKh]. All other cases are parallel-sequential or secjuonl i aS-pa rallel . . 7. Conclusion Computer design philosophy has entered tlio age of parallelism, and it will never go baelt. Rut current (jfogramiiiing languiiires a-re totally in-aclc((uate fur parallel proi'Ciss i ng. To use ihe overlapping approAch efficiently an adequate proBroiriinlng language Is necessary. There will List of Used Symbols be a 5 1 ng.- long way from serial to pitrallel proces- Parallel processing proaeli within it is problem. Parallel p for many years. Now to split proliloins processing. For In problt'iiiK to run on sors; they run I i neu done. Till: problem i parallel processit»;; today wii undcrs tanti nature. and the overlapping apa solution looking for n roccssing 1ü been developed the researchers arc trying to tit thcin into parallel stanco, payrolls are not several hundreds of proces-rly until Ilio paycheoiis are s to find p rob Ictus to which can be applied, because problems as being linear by Overlapping seems to be a natural operation on multidimensional arrays of objects as substitution (ma themiit i CS ) and replaccincnt (normal algorithms, grammars) are natural operations on linear arrays (strings, words). The overlapping .approach covers, tor example, the well-known overlapping of I/O with arithmetic and logic unit and also another important paraiiellsm cal 1 ed pi pel I nIng. References 11) Zcleznikar, A. P., "Overlapping Algorithms," Mathematical Systems Theory, Vol. 1, No. 4, pp. 325-345, 1907 (Springer-Verlag, New York). (31 Zeleznlkar, A. P., "Some Algorithm Theory and Its Applicability," Per i odi cum Malh.-Phys.-Astr., vol 18, pp, )41-)58, 1963 (Zagreb, Yugoslavia). 131 Llneback, J. R. , "Parallel Process Ing: Why a Shakeout Nears," Electronics, Oct 28, 1985, pp. 32-34. [41 Serlln, O., "Parallel Processing: Fact or Fancy?" Datamation, Dec 1, 1985, pp. 93105. Symbol : A arb U BC,k) cavip IX k,CAM) FL EX IN INCL Isp(k) Kk) - leftt 1 Hk) LS Nf. NLS NOAM MA MB meta. . . Ml. MÜAM MOR MP MS M(k) NOT_EL OAM OR o_sig p PL PLS POA.VI right;i 1(k) r<*,k) S sp(a,k) sp[j] i I ; inni ; —f 1J M = M J) M ■es Del'. 4: i'attern incliìsion Terminal stale pattern Def. 3i Stato pattern (.■qij i va 1 erioe Logical ec|ij i va I enne Logi oa 1 noti-ey Rn 0.\M. Prekrivanje; VKo/ec sa paralelno in zaporedno procesiranje Povzetek, v tor« Oäanku jo prlkaz;in koncept tako iinenovanpga prekrivanja, ki Je bil pravr.aprav izpeljan Iz pojma prekrivnoga algoritma iGlöj referenci 1 In . V okviru tega konoepla sta definì ran;t dva osnovri:! kon s I r u k t a T r ek r i v n i (0^31» in nio t a p rok r I v n l abstrakuii stroj (ViOMii. Ta dva konstrukta sta v bistvu paralol-no-2aporedna problemska rcSevulnika. v olanku Je navedenih veO forniainlii definielj, ki opredeljujejo prekrlvni in iiie taprukr i vni abstraktni stroj (23 dc f i ti i e i j 1 , iz It'h definicij pa so izpeljiuii Ir.rekl (13 izrekov). Pokarano je, kako laliko prekrivni abstrak.tni stroj t?.vaja zaporedje paralelnih akcij iprocesovt in kako je mogoče r. uporabo me taprekrivncga■ abstraktnega stroj» papaieliaem SG "povečevati,"' Prekrivni in metaprekrivni abstraktni stroji se lahko enostavno modelirajo z uporatio ?.iianih paralelnih arhitek^ tur, kot so npr. hiperkocka, vodilo in preklopzii sistem In tudi uporabo paralelnih programirnih jezikov, kol je npr. paralelni Prolog In uporaba varovalnih Hornovili klavzul. A SURVEY OF MICROPROCESSOR ARCHITECTURES INFORMATICA 2/86 FOR MEMORY MANAGEMENT 8. Furht Department of Electrical and Computer Engineering University o1 Miami, Coral Cables, florida 33124 V. Milutinović School of Electrical Engines ing UDK: 681^^25.6.08 Purdue University, West Lafayette, Indiana 47907 Thw .paptr prtitnlt en ovcrvtett) of turrtKl micTapnccu«T anhiUeivrea tufciVA tvp' port rntmoTy màii«gement. Bagic regninmenti for a procutor tc sopporl tKt tttCtftOfJf managtmml. art dtjintd, and ike kierarchicdt]/ orfaniiti memor]/ » intri^dueed. Several addrtit Irnnilofto» icfceme*, mth u pafing, «e^tnlafioR, end tombintd paging/»tgmetUetien are ditcriied, and their impitmtntation in current ttiicroproeeuort it diecutieđ. A sptcial emphaeia u given to the appiitalion of the agaociaiivt eaehe «•«morjr. Sinf(e-/enel and mWli-Iettc/ addrett mapping uhtmti ore anatiized and compared. Furthermore, the paper dittnuet the eapaiitiliei of evrrenl mitroproeu$ort to tupparl virtual memory, whieh ineludet ahUifiet to reeogni:e an addret» fatđt, to abori the ezecuiion of the eurrenf ttulraetion and tave necettttry information, and the ahäitg to rettore the taved ttalt and rettime normal proceeting. Two metkodt to restart the inter-rupttd inttruetion, inatnetion restart and inttmetion eontinaalion, are evaluated, and their mplmentstion m eurrènt mieroprotetior» it diteutied. Protetlion and teenrilp re^irementt-are defined, and tiDO proteetion tehemet, hierirehical and nan-hierarchical, are tvalùated. 1. INTRODUCTION New gcDcratioD IS-bit and 33'bit microprocessors are extensively used in multiuser and multitasking environments. Therefore, there is on incresMd demaiid for the support of memory management. Furthermore, as sbown in Figure 1, tlie capacity of prima^ ud secondary memories id advanced microprocessors is increasing, whieh in tarn requires an increased virtual memory space, as well as more sophisticated virtu»! nemory maDagement mechanisms. Id the 16-bit micropt««essor arena, the techniques applied to solve memory management problems are relatively inadequate, and inefficient. At the ä2-bit level, a more standardized approach can be found, and significantly more sophisticated aTchir tectures for memory management have been designed. The paper evaluates various architertures for memory management and virtual memoiy support, and thàr imple-mentatiobs in existing microprocessors. Several important issues are addressed, such as nlection of a virtual memoiy organization, malti-jevel memory mapping schemes, associative cache memories appli^ tó address trandation, virtual memory support techniques, dynaiuic; tnemory. allocation algorithms, as Well as protection and security tech' niques. The implementation of these techniques in current 16-bit and 3Z-bit naieroproces-sons, such as Intel 286, 366, rad 432, Motorola 68010 and «8010, National 32032, and Zilog 1^,000, is discussed. The paper is organized in eight sections. The Section 2 discusses the reqfuirements for a pmessor to support memory management. Two inain stratepes applied in current microproceswrs are presented: memory management unit (MMU) ón-the-CPÙ chip versus off-the-CPU-chip, Two memory addressing schemes, linear and augmented, are evaluated. .S^tion" 3 deals with, the various address trabslation techniques, such' as paging, segmentation'and coinbined paging/segment ation;-and their implementations to cunrat microprocessors.' Both single^level uid mulli-level address mapping schemes are evaluated. Techniques to support virtual address mechanism are presented in Sertion •1. The impl^tneatations of two methods, which resume operalion after en address fault is dft?cted and corrected, are discussed. Section ó describes the security and protection I' chniqiios applied in current microproc';ssors. t»T 10T ir tOM 100 ia lOOM IM tU PVwtRTVAL AMK« IPÄCt REAL ADORE SI SPACE _L »IfOČ !Ttll ■ 1 _J ■ «ii^mn : riw«» • I ^ o:iK TtcvMOLoar »__< 1SB4 ISiC ÌK9 Figure 1, Addressing range needs [S-l] 2. MEMORY MANAGEMENT REQUIREMENTS AdvahceiJ microprocessor system arcliitecturcj which is ahls to support memory runagenient, uses the hierarchically structured in'-'.'nory system, as shown in Figure 2. The memory system consists of three levels aad involves the maiDtäining of a large address spacc based on a.hierarchy of rnemory dcvices, which differ in memory capacity, speed, and cost. At the first level is the high-speed cache m»mory, which is the most expensive and, therefore of the lowest capacity. At Ibt second level is the real (primary) memory, which is slower, but, less cxpausive than the cache memory. The ET^ W5H-acHE WAIN BACXINO MEMonr STORE fHTSKX A30BESS third level consists of large capacity storage devices, such as disks, hold the pro- grams and data that cannot fit ia the first two levels. Vhcc a process is to be run, its code and data are brocght into primary or cache memory,-where cache memory alway.s holds the most rcc:!ntly used code or data. In this hierarchical memory structure, the basic requirements of tbo memory management system can be specified as follows: 1. ability to translate addresses and support dynatnif memory allocation, 2. ability to support \irl'Jal memory, and 3. p.bility to provide memory protection and security. There are two basic strategics in creating the microprocessor system architecture for memory management: . 1. memory management unit is on the CPU chip, and 2. memory management unit off the CPU chip. Both strategies, as well fis the list of microprocessor systems which apply them, are indicated ia Figure 3, CPU VERSUS CPU nnu MMU Intel 286, 386 Intel 432 Zilog 280,000 Zilog ZOOO MC68000/I0 IÌC68020 Z8001 Z8003 N'S 16000 HCR/32 WE32I00 nC5845l MC6805I Z8010 Z8015 NS16082 NCR/32101 VVE32101 Figure 2. Microprocessor system architecture with three levels of Werarchically organized memory to support memory manfgemeat [3G] Figure 3. On-chip versus off-chip memory macìgement unit The main advantages of having the memory maaagcmeot oD the CPU chip are; 1. . access time improvement, because there is no ofif-chtp MMl.!-related delays, 2. maximum portability of operating system aod art'if^lioo programs, and 3. parts-count reduction. On the other hand, the memory mMagimeat oo the CPU chip requires additional transistor count, which could be invested iato oth-jr more frequcntiy used resouroes. For example, the Motorola 68020, which applies memory management off the CPU chip, uses the saved transistor count to implement the instruction cache on the chip, Another important issue related to memory management is selection of the memory organiiation scheme. Basically, there are two tyj'es of memory organization schemes; Sicear asid segmeoted. Id the linear addressing schemes, addresses typically start from zero, and proceed linearly. The memory may later be structured, by software, at the level of address translation. In the segmented addressing sehemes, the programs are not written as a linear sequence of instructions and data, but rather ss modules of code and data. The logical address space is broken into several linear address spaces, each of the'specified length. A£ eSTcctive logical address b compui-cd as a combioatioo of the segment number, which is a pointer to a block in niemory, and the segment «'ffjet, which defines the displacement within the segmenl. Table 1 shows memory addressing schemes applied in various advanced microprocessors. Note that Intel and Zilog olTer both segmented and linear addressing on their 32bit processors iSOSSG and Z80,000, respectively, as software programmable options. In general, a linear addressing scheme is better suited for the applications that mai)ip*il:itf large data stiuctures, while the segmented addressing scheme facilitates programming,-enabling (be programmer to structure software into segments, la addition, the segmented addrcs-^ing scheme simplifies protection and relocation of objects in memory. As an example ofthc segmented addressing scheme, Intel's iSOSC processor contains fou^ IG-bit segment registers, which point lo four objects in the memory: code, stack, data, and extra segment (alternate data}, as shown in Figure 4a. The address calculation mechanism, which produces 20-bit physical address for the iSOSb, b shown in Fig. Jb. 3. ADDRESS TRANSLATION TECHMQUEE Regardless of the memory organization scheme, the processor must have aa address translation mechanism to handle virtual memory. The address translatjoD mcchatiism also provides a method of protecting memory objects. -•"'.dress traoslation is a process of mapping logical to physical memory TABLE 1 Memory addressing schemes in advanced microprocessors PSOCtSt Oli» Bi.(ie> PROCESSORS ADDRESSING SCMT-Sn; Linear Segmented Intel g0S6,S02SB,432 80386 É * * Nfoiorola 6S000, 68010. 68020 < National 16032, 32032 • Zilog ZSOOO family zso.ooo » « • ATiiT \VE32I00 * NCR NCR/32 6 S JOffSET AMIACSS StSUEKT ooes SECUEHT address \ aooeb / M-eiT fHVSlC«. WCHaqyADDRESS ] Figure 4 Segmentation end address caicutatioa a. Segmented addressing scheme of the iSOSO [2Sj b. Address calculation in the ÌS0S5 pSj addresses. The address translation mechanism divides the meniory into biocks, and .then performs mapping of a biock of logical addresses into a block of physical memory addresses. U allows programs to be relocated to the piimary*m»mory. It also provides the base for virtual memory system design, where the logical address space caa be larger than the physical address space. The virtual memory mechanism allows prey-grams to execute even when only few biocks of a program are in the primary memory, while the rest of the program is ia the secondary memory (on the disk). The other important processor requirements for virtual memory support arc discussed in Section 4. Three basic address translation schemes are; 1. paging . 2.. segmentai ion, and 3. combined paging/segmentation. Il the paging systems, the primary memory is divided into fixed-size blocks (pages), .while in the segmentation systems, the blocks are of various size (segments), as shown ID Figure 5. Generally, the segments can overlap, while pages cannot, so pages are usually of a relatively small size, compared to lota! memory. Typical page size is between 25$ and 20-48 bytes, while segments can be 64K bytes or more. The pftging/riegmentatioQ systems combine the features of both paging and segmentation addressing schemes. The segmentatioti part of th» scheme manages virtual space by dividing the programs into segments, while the paging part manages physical memory, which is divided into pages. Each segment consists of a number of pages, as shown Id Figure 6. . Selection of the address translation mechanism has a crucial impact on the memory managomeat techoiques, which have to be implemeiited by the operating system, to handle page or segment fetching, placement, and replacement. For example, the paging address trarj-jation syslem is well suited for pari? phccmcnt arid replacement, because all pages are of uniform size, while the segmea'.ation system needs more complicated placement and replacement algorithms to match incoming segmeots with available memory space in the segmentation systems, a segm«5t must reside entirely in physical (primary) memory in order to be executed, because it» minimum unit that can be swapped is the segment itself. The available memory sp-ace becomes theo fragmented into many small pieces, and there is not enough contiguous memory for storing one large segment. Because of the fragmentation problem ajiocialed with the segmentation. systems, the paging systems ate more eìTicient with r^^pect to mumory utilization, In the paging systems, all pages ari- of equa! size, tb-:. pag« c.in be swapped without-leaving unusable fragmented spac«s. Also, if is aoi accessary to swap in alt pages of a program at once, in order to execute it, hut only the pages required ^''demand paging'). This significantly reduces the swapping t1.-:ie. For all these reasons, the demand paging address trinslation system seems to be VIRTUAL CSEtÄOTAfirj riEnORY PAGE. MAPPfNU KECHANISn PROORAM-l PR0(jRAM-2 B. Paging system PflOeiiAn-l PBOORAtl-Z b. Sfgrnerljlion syslsm SEOMENT MAPPING MECHANfSri PRfMARr fIfMOftr 1 pAse 0 V. PAGE FRAME 0 1 . PACL 1 PAOt FRAHE I 1 PA6E 2 A PA6t FRAflE 2 Il PAGE 0 PAGE FRAre 3 PA6t 1 -- PAGE ffiAHE 4 PA6E 2 / PACE FRAnt 5 PA6E 3 h / PA6E FRAME 6 SES.1CKT A \ SEGMENT B SESnENT 8 1 SESnENT A SfGnEMT A SEGMENT B BEOMENT C' SESriEMI C / Figure 5. Address translation schemes a. paging ■b. segmentation- VIRTUAL (SECOKOARY) MfMORr MAPPING MECHANISM PRIMAFlY MEMORY RE5I PENCE ACCESS RIGHTS SUPPORT FOR PHYSICU ADDRESS BIT & PftOTECTIO.^ REPlACEHZS'T PAGE FRAME 0 PAOr FRAME Ì PAGE FRAME 3 ?AeE FfiAME PAGE FRAME 5 1 1 PAGE 6 1 PAGE FI'/,M£ 7 ? Š PAOE FfAME S 1 n Figure 6 Address translation by combiDed paging and segmentation {pagiiig/segnjcntatioii) Ilio way to go. Ai 4 nialter of fact, a!l advanced ;;2-bit prowssors, as well as sever.il !f>bit processors, fully support demand pajiag techniqut, which may become ft stnadard address trauslation mech&nisra io future mieroproces^ifs. Furthermore, when one selects the address translation »cbeme (paging, segmeotft-tion, or combined system), there are two additional issues which should be addressed: 1, implcm^'Dtation of the selected address translation mcchanism, and sekctioQ of the number of mappiiiE levck 3.1 Implementation of the address tranalatton schemes Regardless of the address translation organizatipn, tie implementation method is always bised on translation tables located ia prlinary memory: page map tables (PMT) io the pacing systems, and segment map tables (SMTJ in the scgmentalioa systems []0,i;,i4,lGj- The table entries contain information to trsEsIate the logical into the physical address, as well as additional dala for protection purposes, and to support p','i'cm?nt and replacement algorithms. A typical furmat tf a translation table entry is fhowa in Figure 7. Ai an eiarnj>le of the address translntion impt'imt-nt»ti'jn, the virtual address of the proceiior consiits of a pair: segment selector and dL^placcment v=(s,d). The Fisurc 7. Typirc! format of a page or segment latSe entry segment selector points to the segment descriptor in the segment map table, as shown in Figure 8. The s-egment descr ptor contains the primnry me! iory address s", at which the segment begins. The displacement d is added, to s' forming the real physical address, r=d+s'i corresponding to the virtu.i! add/ess v. Figure 8, Address translation mechanism of the i286 [28] The described address tranflation implementation metboJ is tnown as direct mapping. Translating a logical address to a physical address, usiig direct mappitig, requires an additio.iat memory acces.« operation to obtain segment (or page) base address, and therefore tlie use of direct nsapping can cause the computer run progr.ims at lower speed. There are several solutions applied in modern microprocessor nrchitectures to overcome this problem. These solutions arc discusscd bek-vi. Id the lotel's iSSß processor standard, four segment rejUicrs are extended with the corrf5potiding four ■IS'-bit segment descriptor cache registers, as shown in Figure 0 |ZD,281. Segment registers ere loaded by the program, while the CPU toads the explicit cache registers, which are invisible to programs, Explicit c»-be speeds up the operation by eliminating the need to refer to a descriptor table for every memory rcfcrcüce instruction. Loadin? the explicit cache is performed in four steps; SeOMENTSElfCTOBS ACCESS SEOMEWT SfOMEnT RIGHTS BAS£AD9 l> N u Figure 10. Address translation mechanism using the tssociative cache memory [10| A number of simulation studies have proven that the small a.ssociative cache signiEcantly speeds up (he system operation, because the bil ratio of finding the address in the cache riches Many rcceat processors, (such as Mo'torola 5S000 family ^ith its NiCóS.j.'il MNfL', lete! 80386, Zilog ZSOOO family and Zj:0,000, National NSlGOOO family with its NS100S2 .MMU, and others) have impiemect^d the address translation scheme by using the TLB method [5,33,34,35,37,50,51,51]. Although translation mechanisms ba^cd on the TLB method vary in complexity, they can be cl.xssified in (wo basic groups: addross-accessable TLBs, and content-addressable TLDs. In the address-accessabSe TL15 approach, a logical address field identifies the register in the TLB that holds the physical base address. As an example of this terhniqnc, the ZSOO with on-chip S!.\ir is shoun in Figure 1! [.Ì3|. The virlu;il address consists of a 4-bit TLB pointer, and a I2-bil otTsol. The TI.Ü pointer 5il"cls one of fh'- Ifi translation registers of the TLB. Then, the 2J-bil physical LOGtCAL ADDRESS 16 PAGE BASE ADDRESS REGISTERS —j REGiSrER INDEX | PAGE OFFSET 4 tms 12 bits !5 -1 3 15 PAGE FRAME ADDRESS PROTECTION FIELD „ 25 PHYSICAL ADDRESS PHYSICAL MEMORY «-BYTE PACE PACE FRAME ADDRESS OFFSET Figure II. The Z800 address translation based on the address-accessable TLB [33] LOGICAL ADDRESS 1 16 bits j 7 bits f 32 coment sOdressable regisiers tent-j iable/ I- msr: ...Ifö] -Delermfnes segment si^e ASSOCIATIVE LOOKUP I 1 •••lo SEOMEhr BASE ADDSÌ35 COnPARiSON BITS SfenENI BASr ADO^fSS Figure 12. Conienl-addressable TLB in the MC58451 MXfU |44] address is formed, as a selccied 12-bit page base address from the TLB, tonratenated with the 32-hit olTfct. The address-acfcssable TLB technique b not practica! for large systems, because accesfing the TLB by addresses requires a segmeot register for each logical segment or page that can be relocated. The conteEt-addrcssable TLB is more suitable for large sysiems. This method has been applied in several microprocessors, such as the XfC6Sl5l \LMU ZMIS PNtMU Intel S03S6. and NS 16032 NiNR.'. To illustrate this method, Figu« 12 shows the content-addressable TLF, applied in the MC6S-151 MNfU. PBooftwi Rtoursrs «et« ^ rOA5E3?1En; tPAX) J tósatis KWiSiAT!« sr usma iH£ itóLts IM mifivir tijnosf M Fig\)re 13. The nov.vehart of a pasing virtual memory system with ao associative cache memory The iVfMU receives a logical address (23 bits), and the tpask register magics the low order bits (o determine the segment size. Thea, the MNfl' compares the rest or Ihe most signiScant bits, with the comparison Seid values of 32 conteat-addressabte registers. If a match is found, the NINiU performs address transUtion. If there is do match, (he XtNR.' generates a fault condiiion, and aeüvales a trap routine. The trap routine will update the TLB from.translation tables stored in primarv memory. The flow-chart in Figure 13 illustrates the ne:cssary operations iti a paging-based virtual memory system with an associative cache memory for recently used pages. The virtual memory is activated wheaever program re^^J^sls aa access to a page. The flow-chart in Figure ]3 indicates three different control paths: 1. when (lie page descriptor is found ia the associative cache, 2. when the page descriptor is not found in the cache ('cache miss'), but the page is in the primary merriory, and 3. when the page descriptor is not foiind in the associative cache, aud the page is not in the primary memory ('page miss'). Tb?n,,(he address fault handling routine is activated. Ia addition to address translation mechanistn, the MCCS15I, XLNfü supports dyn.nmic memory allocation. The dynamic memory allocation mechanism is able to allocate the memory to a process, while it is running. The Binary Buddy system, an algorithm for dynamic memory allcjcation, is implemented in the .\fC6845I. The algorithm divides the entire physical address space into buffers, the size of which varies fro.-n 256 bytes So 250K bytes (in the MC6S4S1), The algoriibin maintains these bufTers by using the buffer lists for all sets of buffer;; of the same size, as wel! as butler descriptors for cach buITer independently j52j. When a memory request is received, the algorithm searches through (he list of available buffer.'; in order to find the best fitted buffer. If the best-fitted buffer is not available, the search process is continued for the next larger size buffer. The flow-chart of the Binary.Buddy algorithm is shown in Figure 14. ■ A detailed description of the algorithm, as well as additional issues related to it, are discussed in j4ò,48,52). 3.2 Singie-lcvet versus multt-Ievel address mapping The second issue closcly related to address translation architectures is dealing with the nunnber of mapping levels in address translation schemes. The coDventioDal address tnapping scheme consists of just one mapping level, such as in most of the IG-bit processors (Ì28G, ZSOlO, and ZSOIS ^öfUs). Oli the other hand," almost alt 32-bit processors use multi-level mapping schemes, which brings some new features in the tnemory management. The basic advantages of multi-Ieve! mapping schemes versus siugU^lcvel mapping, schemes can be summarized as follows: S Figure 14. Binary Buddy algorithm for dyLamic memory allocation UailCNT SELECTOR iCCtsjstienifTos SCQUiNTDtSCKIprOH Figvre 15. Two-level address mapping scheme in (he i43? processor [27j 1. tbey provide more sophisticated protectioa mečbacism, 2. they are able to accommodate largtr address space, and 3. they provide page sharing. Several multi-lcve] mapping schemes are evaluated below, Intel's Ì432 processor uses two-Ievei mapping in order lo provide more sophisticated protectioD mechanism, as shown in Figure IS 127,40,47]. The segment selector register points to ^an entry or the ace^ segment, where the access rights are stored and are thus associated \i'itb prograrTi modules. The ftccfss descriptor contains the pointer to the segment tabic, and finally the srenieiit Jigfrifitör contains a pointer to the beginning of the selected segment in the primary meniory. Because the access rights are stored independently of the scEm''nt descriptors, several modules can share the same segment, each with different accesi-rights to it. Fn Figure I 'l, the module A can write and read the selected segment, w hile the module B can only Figure IB. Paging system architecture in the i33S processor \Ó4] read the segment. In addition, the two-level mapping scheme makes it possible to restrict the number of segments accessable by à given program. Id single-level mapping systems, such as Ì286, any program may address any segment in memory, simjily by pointing to it through the segment table. The two-level sc heme of the i432 also enables fewer address bits to point to a particular segment. The Intel's Ì38G prövides two options, which are user sslectable: segmentation system (same as in the Ì280), or paging system. The paging system architecture uses two-Iévc! map[>!hg srhcnie, along with a translation lookaside buffer, designed as a cache memory. The complete architecture is shown in Figure 16. The linear virtual address consists of three fields {director)-, table, offset), and address translation is performed in the following steps: ° 1. first, (he address is searched through the TLB. If the address is found, the translation js performed in the TLB, and the primary memory is accessed directly. 2. if the address is not found in the TLB, the miss signal is generated, and the translation is performed through the two-level mappiog built on the CPU chip, as shown in Figure i5. The two-level on-chip mapping scheme enables fast address'translation, and page tables can be shared and/or swapped. A similar two-level mappinf scheme has been ImplemecieJ in the .\'SI6082 MMU j6.25,3S]. The total physical address space is divided into 33,768 fixed pages of 512 bytes each. The virtual address consist of 24 bits divided icto three fields; index-l and inde3t-2 of the page selector, and the offset, as shown in Figure 17. LOGICAL ADDRESS U/S S BITS r BITS éOANK RESERVED 1st IMD£}( OBITS 2nd INDEX 2SS PTEs IS BYTE ADDRESS IIS PTEs 9 (PAGE A00RESSV512 PROT. & USE PACE PTE (32 BITS) MEMORy Figure 17. Two-level mapping scheme of the NS360S2 .MMU J3S) S The ißdtx-l (8 bits) of the page selector is used to iorite one of fise 256 entries of Ibe page table. The conleots of the page table PT&l point; to the beginning of one of £50 pointer tables, each of which contains 128 entries; Tlit-a. the pointer to the pointer table is combined with the index-2 (7 bits) of the page selector, to locate one of the entries within the ^jointer table. The selected entry contains the actual page namber in primary memory. Tlie offset field is then used to locate data within the page. The NS 160S2 MNiU contains the associative cache to hold 32 recently used page address entries, as well. The ZSO.COO processor uses three-level mapping scheme bajjid Ofl tli? Si't Cif three translation tables located la primary, memory [2,33,53]. it also .."ijntahsg aii ssso^iaiiva tr.omoiy for the TLB, where 16 most recently referenced pages are stored. The CPU automatic-ally loads the TLB from translation tables, when a logica! address is missing. The NCR/32 processor uses an address translation chip (ATC) for address translation based on paging system with one-level mapping [22]. The chip contains 16 associative memories for recently used pajes. The ZSOlO which is used with' the ZSOOl procejpr, applies one-level seg- mentation system, based on 64 content-addressable segment descriptor registers. For more details see [33,50], The ZS015 MMU differs from the Z8010 MMU in that the logical address is translated into page frames rather than segments. It applies one-level mapping scheme and uses. 6i page descriptor registers, which are also content-addressable [33,5GJ. The WIt32100 32-bit processor uses off-chip ÓSlOl.MNIU, which supports both demand paging and segmentation systems, which are user Selectable [15, 17, 18]. The .M\nj "con:a:ns an on-chip cache mcniory: a 32-entry segment d'jscripior cache, and a frl-enlry page descriptor cache, to hold recently used segment and page descriptors, respectiveiy. Table 2 summarizes address translation features of some 16- and 32-bit micropro-cesfors. 4. VIRTUAL ADDRESS SUPPORT TECHNIQUES A virtual memory system allows the user to execute programs on a very large memory of virtual address space, much larger than the actual physical memory. This is accomplished by the capability of a microprocessor to detcct access to memory pages (or scgfrnnts) which are not present in the physical memory. When the virtual memory system detects such a reference, it will fetch' the required page from the secondary memory into the primary memory. In order to support virtual memory capabilities, besides the address translation, a microprocessor must provide the following attributes: 1. to recognize a page or segment fault, if the page or segment is not present in the primary memory. The memory manager must then inform the processor so that the missing page or segment can be fetched from the secondary memory, and eventualJy one of the current pages or segments can be- « Ä Z z l-J r-j fM S S t—t „ m tn (/1 00 oa ao 3C o n n s 9 s iji ^ C O cz o> C Ol r* rt r* O rv fsi » O C co cc 00 O fS ttf n M o C o Cl o s o r- H- cr. O w tJ o tsi krt o m O ♦ fNt rv o * ♦ o D o 00 o X- OS O V) O + + t-' rv: * * t>J « X Ol CD £ n C! s ^^ Vrt o- cr rr: 5S e» K- - o CB ^ o a> ^ - rj fsj DO lA r^ M O O 3: c: g g S — — cz I-' ' »-• t-i A e. CS o- o- oc cr o C> m > Cl S S 3 S Cl 2 S Cl SE > = r- w p; Crt < tn i o M A A t-* :sj en ei O Cl '..ei C. o -0 C Cl H H Cl ^ -3 c: > >■ n r- m -3 D — s C K C -B > > > > > > > tn cc Ui > o Cl Cl in Cl Cl Cft cr n! ra Cl cn cn o »—( t-.« —^ < t—1 — rs :B » rH m rri ■z. s Z z z z' Cl Cl o m o Ci Cl Cl Cl C; in v> tn Cl - S S Crtül o. m ra ra m m cr rr C/5 '—v ,—^ t—s z t- M c- (r. z z m ■a ■o •o ■u mJ r: ra CT! ra H H S H o 3E a> u M u IR u QĐ » m > -j 3 q n Cl S' 5 ^ i? m ff n O <» n > > 1 I = z O C5 53 65 Z O o u> H in in VI Ü1 m z c- —■ S -i Z z- r- > M' u. bH cn c= > > H N N f-J N H H r> n> B «J <1 H-1 O U « 0 1 O O ■z, . « r.j a; z T-'S" cn > < U IV» VI : H- hi IS» m IS r- tn z Cl Cri Ld ts> J». o> tM ■ > Ch A rvJ 1 u tv) > u > wt -A > n n Cl n tu -0 Ul O r>; O ut ut U1 co P 3 tn o ifl a. a> a O 0- o o o n> r* r» tn 3 o c. K K s 3 B o O BO o o •H 1 0 rt o H a rf r» r* 4 • 3 >o -< n O • ■ • (t O » n o " D * G. S 9 O n 3 = > -o in r* (1 » n n r* rt rt tu » rt n: H I» B t et O VI 0 1 1 S- o H-1 ra n M- Dl - n n n 3 B U m 3* Q. < B a < Cl. 3" (t 1 r» C. o. a. ti a (S m (f (5 Irt ■ D CL o. M o, a. •I 3 1 •H •f H -J O (S ti 3 • -i n' * • • c- 1 re r- o- n ■ ep a) • rt n o n H-» K S) 1 1 H "1 1 1 0 «> n H- t. a n m (t ►1 Cl M n » r* s- 1 rt -1 • * • * Cl f n n (5 a CT Cl tn » T H er * u> O « ■ n 1 ft 1 a. " if m n-s f o to replaced, 2. to abort execution of tbe current instruction (inetrvction ebort capabilily), 3. to save necessary ioformatioQ needed later to recover from the fault, 4. to cali and execute the fault service routine in th» operating system, which will swap the required page(s) or seEmcnts(s), from secoddary memory to primary memory, 5. to provide necessary information for the opcraiing system, in order to sup-■ port page (or segment) placement" and replacement, aSgotitbms (indication o} access activities), and 6. to restore tbe saved state and resume the normal processing (inilTueiion reitart capahiUlitt). Although very different in complexity, all advanced microprocessors provide instruction abort and restart capabilities. Some solutions are presented below. Recognizing the access fault can be performed internally only, if the MNfU is on the CPU chip, or both internally and externally, if the is off tbe CPU chip. When an access is made to an instruction or data wlsiih is not present in primary memory, an address error is iaternally detected, and it iniliates the address error fault handling routine (inUrnalty deteefed faiill). If the off-chip NCVH.' detects a fault situa-lioo, it v,i!! send a signal to the CPU, which v.'ilt in turn activate tbe fault bandliog routine (eiternally dtlecitd fault). When the CPU recognizes an access fault, it saves the state information needed to recover from the fault. The information is usually saved od the stack. The typical information which must be saved in the program counter (rtarting address of tbe instruction), the status register, the fault address, the trap-^pcci^c parsmelers, the access type, the internal temporary registers, various internal statuses, etc. For illustration, tbe MC6S010 processor which supports virtual memory, saves 2C words versus the .\iC6S000 process, which saves only seven words, which is not enough to provide the user with the state of the machine after the. fault haj; been occurred. Figure 18 shovis the information saved on the stack for these two procery is on. The operating system may reset this bit to keep track of tbe access hbtory. 3. the inodtfitd bit • which is set by any write operation to the corresponding STATUS SEDISI Eft fROCRAM COUNTEB KICK 02 mOWU COUKTER LCTiV M FcwnivftiDsp'fsrt OS S?£C:AL SIAlUiwaHB FAULT M0R[5E HICH » FAULT ADDRESS LOW ec HEEERVEO CE [15,1A OUTPUT SUffES IP ftESEP.l'ED « DATA l\«UJ easFES KESESVtO iwrn inpiij BuFfER Iem, and are discussed below: 1. The processor may postpone the modiDcatioo of t-er-visible resowic« (such as rarry bit); until the end of the instruclioD. Thfn, if the address fault has Dot occurred, the resources will be updated- 2. Ail modificai ions of the user-visible resources will be recorded by the processor if the address fault occurs. On the basis of this ÌDfortnatioD, the processor wiSI be able to restore the original values of the modified resources. 3. The processor maintains the copies of alt user-vii;b!e resources, that are modified. Because the copy always eoDtaios the origiaal value, if the address fauU occurs, it will be easy to restore the original state. ♦ - 4.2. Instruction continuation method In the instructioQ continuation method, when the address error routine has been completed, the machine instruction will oot. be resumed from the beginning, but from the same location within the instruction at which the execution was suspended. The execution of the same sequence of microinstructions 1ml, m2, m3, m4), in the case of the continuation method, is shown in Figure 21- The address fault was detected in the microinstruction ra2, and the control was transferred to the address error handiing routine. After the roulitie has been competed, the processor will resume operation, jy exef uting thf microinstruction m3. The FAULT SEQUENCE FAULT continuation method is analogous to an interrupt operation at the microinstruction level. In order to support the instruction continuation method, the processor must be able to save the entire state of the machine, when an address fault is delected. Therefore, the processors which apply this method usually have a lirge address error stack, to save all accessary information (e.g. MC6S010). Regardless Of this requirement, another problem with the continuation method is related to the instructions that require execution without interruption. In addition, this metbc-d requires the additiooal time and silicon resources for saving and restoring the complete statof the machine. The instruciion coBtinuation method has been implemented in the MCOSOIO and the .MC6S020 professors only |35,36j, while all other advanced processors use the instruction restart method. The NS160S2 SRfU sends an abort signal to the CPU (NS 10032 or 32032), which will stop the execution and will return the CPU iato the state before the aborted instrucnoD. Then, all needed information (contained in program counter, machine status, stack pointer, and several other registers) is automstically saved. When the address fault routine b completed, a returo-from-trap icstruction is executed, which will resume the aborted instruction from the beginDiBg |3SJ. Zilog processors also implement the instruction restart method. The ZS001/ZS015 system conlains a special data couot register which counts the number of successful data accesses before an address fault. This inforraatioD b used to restore the machine state, which existed before the address fault. The 280,000 and ZSOO processors, which have the KiNil" on the CPU chip, apply an improved itsstruetion" restart method compatible with their pipelining architecture. The Zs0,000 executes instructions by using six-stage pipetining. and therefore the page fault can be detected before memory access. The address translation is performed in the third stage of the pipeline, and if an address fault is detected, the execution stage will be suspended, before any change of register contents is made |33,3S]. The Z800 applies a similar technique, because it has a three stage pipeline allowing the instruction suspension, before 'any register is changed. Intel processors Ì2S6 and Ì38I> apply the instruction restart method, as well |25,2S,Sj]. They are also able to detect an address fault before executing instruction, ■ and thus faulted instruction restart becomes simple. After completing the execution of the address fault handling routine, the CPU places the address of the interrupted instruction into the instruction pointer, and resumes the program execution. 6. PROTECTION AND SECURITY TECHNIQUES In multitasking and multiuser environments, it is required from processor architecture to support protection and security, ia order to increa-'e system performance and simplify system iiYiplemcntatioa. Basically, protection aod security issues can be divided into the following topics: S Figure 21. Microinstruction execution - the instruction « ontinuation method [3E] J. memory protection. 2. program protection, 3. «ser protection, and 4. information security, A/tmorjf proleetion mechanitm should delect any addressing error before it caused damage. Each instruction should be checked to verify that it performs the intended operation- The ^L\^U unit performs this check, and if (here is aa address error detected, it generates an address fault. The address fault handling routine is then activated, which analyies the address error, eventually Exes it, aoc returns to the interrupted program. Program proUcdon tnichanism should prevent application program from making illegal modifications of the operating system. It also should control the transfer between system modules to achieve total reliability. Var prclcdion mtchaaism should protect users against tach other. Stcurily mechanism should provide limited access lo information- Two basic architectures that provide program and user protection are; 1. hierarchical protection system, or f»nj profecfi'on and 2, noD-hierarchical protection system, or ca'pakility-hascd fTottct\on lyitem. These two systems are discussed in the following paragraphs. Hierarchical protection system conskts of a hierarchy of protection levels, or rings, starting from the most privileged to the least privileged. Basic principles of the ring system are; RINO 0 RINO t RINO 2 RINO 2 ■ RIMS O RING 1 Figure 22, Principles of ring protection system (2Ésf ft. control transfer between programs b. data access 1. A program may access only data that reside on the same ring, or a less privileged ring, 2. A program may cal services that reside on the same, or a more privileged ring. These two proteclioa approaches are illustraied in Figure 22. The ring syptem ha,'; been implemented in the i2S6 and the i3S6 processors (21,26,28,5-jl. Their ring protection system consists of four privilege rings, a5 shown in Figure 23. Different priorities are assigned to different, programs (segments) within the system. Greater privilegi is/assigned to more important programs. Typically, the operating system occupies the most-privileged ring, thus it. is protected from the application programs. The programs nfiay access the OS with a high-speed call instruction, rather than using the context SM'itching technique, which is the trsditional w:iy to implement the call of OS services. Second and third rings are typically used for jvitem services and custom extensions, respectively, white the application program; are usually located at the least-privileged ring. The Ì285/Ì3S6 protection model also provides task isolation, by having separate descriptor tables. The entire isolation between rings is provided by a separate stack for each ring. In non-hierarchical protection systems (or capability-ba.r>000, the ZSOOO, and the XS 16000 processors have two operating modes (or privilege levels) of the CPU; supervisor aode, and user mode. In the supervisor mode, the GPU can execute the complocc set of instructions, while in the user ruode, only a subset of instructions can be used. In Ziloj processors, these two modes are called system and normal. Typically, the opera!tng system functions are placed at tbo supervisor level, while application programs cxecute al the user level, thus the operating system is proteeted from the application proErams. The supervisor level typically has access to all of the processor resources, as well as to all esternai resources, such as memory and I/O. This enables the operating system to control both processor and external (unctions. In addition, (he NSlGOOO processors provide separate address spaces for each running process, thus protecting one user from another. The MCeS020 inipk'ments a concept of multiple access levels, which provides expansion on up to 25B hierarchical levels, which present a superset of ring architecture. Security refers to the limited access to information. The basic principle is to allow a program to access only what it needs to know. For example, Linden suggests that "...almost every procedure should run in a protection domain that gives it an access to exactly what it needs to accomplish its function, and nothing more [32]." The security is provided by giving each process certain access rights to a page or a segment. The most commonly used access rights are: 1. read access: a process may obtain any mformatioo from the page or the segment, 2. tiT!(e aetess: a process may modify the page or the segment, and may place additional information in it. The process may destroy all of the informatson in the page or the segment. 3. execute -access: a process may run the page or the segment as a program. Execute access is given to pages or segments which are programs, and denied to data pages oi' segments. Current processors typically store the access rights in page or segment descriptors Beforf the prncwsor acccss?,s .i page or a segrnppt, it firft checks its access rights, ann if they are verified, il may access the selected page or segment. The diagram in Figure 24 illustrates the described mt-cbsnism, based on access rights stored in the page or segment descriptors. The character N indicates that the corresponding page or segment cannot be accessed a; all. The segmenti! ion virtual memory system provides a more natural security system in a paging system. The logical address space is divided into pages, and the described mechanism cannot protect the program modules precisely. It cither protects too little or too much. !a the segmentation system, each segment is of speciGc length, and the way to protect segments by using access rights is more natural. Regardless of the imphmented virtual memory system, the drawback of the described security mechanism is that all users have the same access rights to common pages or segments, because the access rights are afforiated with the pages or the segments, and not with the users. This problem can be solved by using two-level mapping schcrae, as described in Section 3.2, for the case of she i432 processor j2Tj. In this two-level mapping schcme, the access rights are stored independently of the seginent (or page) descriptors, and are associated with the users, and not with the segments (or pages). U M o HOACCfSiTOf 0« . BnaccrssiOMoe . t>slIt/R[»0iC«SS10P"0i Figure 24. Security technique based on access rights stored in the page or segment descriptor« [27] 6. DISCUSSION AND CONCLUSION We have discussed in this paper several issues retaled to memory maDagement ia advaoced microprocessors. All these concepts are not new; they are known for years from lb e operating system's theory and practice, however the approaches are sometimes modified, and implemeatatioii tecboiqucs may be different, ia comparison with the minicomputer and maiorrame eQvironmeDls, The processor architect, must make several crucial decisions related to the processor architecture, >vbich bave to support memory management and virtual memory. The maiD decisions to be made are listed in Figure 25. The on-chip MMU versus off-chip MMU is one of the basic decisions which has to be made. Both concepts have advaatages, a; we!! as drawbacks. These have beea.discussed in the paper. In addition, the on-chip MMU has aa advantage over the off-chip MNHJ which b related to cache meniory design. An external MMU requires logical address caches to bypass the MMU delay, while the internal Xttfl.' implements the physical address cache. The logical address cache requires special address tag hardware, targe operating system overhead on task switch, and flush cache when sharing data. The issue related to virtual memory system: pagiDg versus segmentation, is of crucial importance. Again, some microprocessors support paging, other pj-ocessors support Seemen!at ion, while few microprocessors support both systems, ia which case the mode is user selectable. Aayhow, it seems that the paging system has advantages over' the segmentation system, and almost all 32-bit microprocessors support it. The next two questions are related to the IropltmeDtation of the'address translation mechanism: levels of mapping and use of ao associative cache memory. Both multi-level mapping and a small associative cache memory significantly improve system performance, and thus they should be built into an advanced microprocessor arcbitpclure. Practically, all 32-bit microprocessors have implemented these two concepts in their architecture. hMU ON-CHIP versus MMU OFF-CHIP PÄGiNß. versus SEGMENTATION 4 ONE-STAGE MAP P INO versus MULTI-STAgE flAPPlNO CACHE MEnORY-YES versus CACHE MEMORY-NO (NSTRUCTION RESTART versus INSTRUCTION CONTINUATtOM PROTECTÌON BUILT-IN versus PRoWlON IN SOFTWARE Figure 25. A list of questions for the processor architect Techniques to support the virtual meniory system, specially the (boice of the techaiques to implement resume operation, after an address fault is detected and corrected, is also ail important decision for the architect. The instruction restart method seems to be moro elTicicnt than the instructioa coiitÌDujtion method, especially if the MNfT.' is on the CPU chip. Then, due to pipelined nature of architectures in modern nijcroproccfsors, the address fault can be detected before a memory access. This significanlly simplifies the restart of the faulted instruction. Finally, the protection mechanism built in the architecture (such as the ring system in the Ì2S0/Ì386 proces.'ors) provides a powerful tool for an operating system designer, and reduces software overhead. On the other hand, because the protection system is already defined ia the archilecture, there is no choice for Ihe OS designer, but to implement the avaihbie mechanism, whether he (she) likes it or not. The other approach, in which the processor provides some basic protection elements, but not the whole protection system (such af supervisor/user modes and access concepts in the MCG8020), requires from the OS designer to create the protection system in-software, thus increasing the sofiw:ate overhead. However, this approach is more flexible. We may conclude that the memory management architectures in current ■ microprocessors are coming of age. However, one of the mosl challeoging aspects of future processor design will be to provide more elegant solutions to all these problems, as well as to enable a more complete integration of memory management and virtual memory support. S r. ACKNOWLEDGEMENT The authors are thankful to Jeff Fridmore and Walt Helbtg, of RCA, for their comments. 8, REFERENCES 1. Aho, A.V,, Denning, P.J., and Uilman, J.D., "Principles of Optimal Page Replacement," JACM.No). IS, No. J, January 1071, pp. 8t>-03 2. Alpert, D., "Powerful 32-bit AJiero Includes hJemory ^^aDagement,'' pvttr Dtsiin, October J9S3, pp. 213-220, Cam- 3. Alpert, D., Carberyy, D.. Vamamura, M., Chow, V., and Mak, P., "32-bit Processor Chip Integrates Major System Functions," Eleelronitt, July 14, 1083, pp. lja-110. 4. "An Archilcflural Contrail: The M6S000 Mirroproeefaor Famlli/ and the S0S6/ÌAPX Motorola Corp., November 19S3. s. Andrews, R., "The ZS0,000 Processor Chip Integrate; Major System Fudc-tjods," Proeetdfngs of Me IEEE Mini/Micro Seuiheasl, Orlando, Florida, January 1084, pp. 5.2.1-S.2.7. 6. Bai, S„ et'al, "Tbe NSIÈOOO Family - Advant» ju''Archilectarc and Hardware,' IEEE Computer, June 1082, pp. 58-67. 7. Beyers, J.W., et al, "A 32-bit VLSI CPU Chip." IEEE Jovma! of Solid-Stale Circw'U, Vol. 16, October 1B81, pp. 537-S41. 8. Chamberlin, D-D., Fuller, S.H., and Lin, L., "An Analysis of Page Allocation Strategies for ^'irtual Memory Systems," IBM Jovmal ofReD, Vol. 17, 1073, pp. 404-412. e. Chu, W.W., apd Opderbecfc, H., "Program Behaviour and the Paje-FauH-Frequency Replacement Algorithm," IEEE ComptiUr, November 1076, pp. 20-38. 10. Deitel, H.M., "An Introduction to Operaliitj Syttems," Addison-Wesley Pub-lishiog Company, 1984. H. Denning. P.J., "Virtual Memory," ACM Computins Surveys, Vol. 2, No. 3, September 1ĐT0, pp. I53-1S9. Denning, P.J., "Working Sets Past and Present," IEEE Trantactiona on SoftiL-arc Engineering, ^'ol. 6, No. J, January 1980, pp. 64-84. 13. Denning, P.J., and Schwarti, S., "Properties of the Working-Set Model," Communications of the ACM, Vol. IS, No. 3, March 19872, pp. 10M98. 14. Dennis, J.B., "Segmentation and the Design of Multiprojrammed Computer Systems," JACM, Vol. 12, No. 4, October 1965, pp. 589-602. 15. Diodato, P.W., et al, "CAD Construction of a \XSI Memory Management Unit," Proccedinji cf the ICC AD, 1083, 16. Doran, R.W., "Virtual Memory," IEEE Computer, October 1076, pp. 27-37. .17. Goksel, A.K., et al, "A Memory Management Unit foi a Second Generation Kficroprocessor," Proceedings of the Compcont 1984. 18. Goksel, A.K., et at, "A VLSI Memory Management Chip; Design Considera- tions and Experience," IEEE Journal on Solid-Slatt Circuits, Vol. 19, No. 3, June 1084. 10. Gupta, A., and Toong," ILD.,. "An Architectursl Comparison of 32-bit Microprocessors," IEEE Mitro, Vot. 3, No. 1, Februiry 19S3, pp. 0-22. i 20. Hansen, D.J., "Programming Motorola's 32-bit Kticroprocessor the'68010," Proceedings of the IEEE MiniJMicro Southtasl, Orlando, Florida, January 1984, pp. 4.1.1-4.1.9. 21. Heller, P., "The Intel L-VPX 286 Microprocessor," Proctcdings of the H'ijfon, lOSl, pp. 1.3.1-1.3.4. 22. Heller, P., Childs, R., and Slager, J., "Memory Protection Moves Onto J6-bil . Microprocessor Chip," Bedronies, Vol. SS, Feb. 24, 1982, pp. 133-137. 23. Hirschberg, S.D., "A Class of Dynamic Nfemory Allocation Algertthms," 'Communications of the ACM, Vol. 16, No. 10, October 1073, pp. 615-618. 24. Hoeschene, H.A., et at, "A Second Generation 32'bil CMOS Microprocessor," Proceedings of the Compcon, WB4. Si 25. Hunter, C.B., and Farqjhar, E., "Introduction to tbe ;iS16000 Architecture," IEEE Micro, April IBS^, pp. 2(>-47. ' ^ 26. "lAPX 2S6 Operating Sj/sttma Writer's Guide," Intel Corporation, Santa Clara, 1983. 27. "Introduction to the iAPX 432 Architeelure,' Intel Corporation, Santa Clara, 1931. 28. "Inlroductiori to the iAPX SSS,' Intel Corporation, «anta Clara. 1082. 20. Kaminker, A., et al, "A 32-bìl Microprocessor with Virtual Memory Support," IEEE Jotirrtal of Solid-Stale Circuits, October 1981, pp. 230-231. 30, Kaowlton, K.C., "A Fast Storage Allocator." Communicalions of the ACM, Vol. 8, No. 10, October 1065, pp. 623-625. 31. Levy, H.M., and Lipman, P.H., "Virtual Memory Management in the VAX/\'MS Operating System," IEEE Computer, .March 1082, pp. 35-41. 32. Lißden, T.A., "Operating System Struftures to Support Security and Reliable Software," ACM Computing SuTvty», Vol. 8, No. 4, Dec. 1976, pp. 410. 33. Look, H., "Virtual Memory for Zilog's 8-, 16-, and 32-bit Microprocessors," Proetedtngf of Ikt IEEE Mini/Micro Soiitkeail. Orlando, Florida, January ieS4, paper 3.3. 34. MacGregor, D., "Hardware and Software Stra).?gies for the MC68020," EDN, Juce 20, 1085, pp. 80-08. 35. MacGregor,- D., Motbersole, D., and Mover, B.. "The Motorola MC68020," /£££:jl/icro, August 1084,. pp. 101-118. 36. MacGregor, D., andMothersoIe, D.S., "Virtual Memory and the MC68010," IEEE Micro, Jure 1983, pp. 24-38. 37. Martin, G,, "Virtual Memory Nianagement Expands Microprocessors," Com-ptj(-tems. Las Vegas, Nevada, September 19S1, pp. 48-51. . 56. Walters, S., "Memory Management Made Easy with the ZSOOO," Proceedingi of the M'escati, mi, p;i. 9.3.1-9.3.9. 9. ABOUT THE AUTHORS Dr. B. P. Furht is on the faculty of the Department of Elcctrical and Computer Eoginccrmg. University of Miami, Cora) Cabte. Florida., He has published over 60 technical papers, and 2 books. He is the author of Mieroprotessor Inter-fating tnd Communicotion (Rcstoü 1985), and cocdilor of Ibe Tvtofia! on AJvanrtd Tòpica in Cojupaler Arehitectvre (IEEE Press, lOSi). His current tw.afch. activities include higb-level language computer architectures, multiprocessor systems, end architectures for virtual memory management. He presented over 30 invited lectures in Europe, North, and Latin America on various topics related to computer architcctute. He has been involved in consulting activities fot a Dumber of companies such as NASA, RCA, Cordis, HoDcywell, and others. He is a member of the IEEE, and a chief editor of the Irilernational Journal of Mini and Microcomputers, Dt. V. M. Milutinovi^ is on the faculty of the School of ElecUical Engineering, Purdue University, He has published over 60 technical papers, 3 original books, and 4 edited books. His research papfs have been published in IEEE Transactions, lEE F'rocw-dings, lEIEE Computer, and other reforeed Journals. One of bis books hüf. been republished (in various forms) in stveral langunges. He is the editor of the If-Eli Press Tutorial pn Advanced Mirroproctmors and fligk'Ltvcl Language Compuler Arthileciure, and (he coedilor of (Le IEEE Press Taloriai on Adionttd Topics in Cctnpultr ArtkiUcturt. He is (he editor and the contributing author for tuo muHiauthor books on computer architecture. His pioneering paper on Oa.\s computer architecture for M^Sl has been scheduled to appear in (he September i-ssue of IEEE Computer. He presented over 40 invited lectures in Europe, North, and Latin Atnerira. His currcnt iutcresis include MjSI computer architecture for GeAs, high-level language computer architecture, and microprocessor systems for AI. His currcnt research support is equal to about $250k per year, predominantly in the area of \XS1 compuler architecture for Ga.\s. He has consulted for a number of high-tech companies, including Intel, Honeywell, NASA, RCA, and others. He is currently involved in (he industrial Implementation of a 32'bit VLSI microprocessor in the Ga.As technolog;', with responsibilities in the microarchitecture domain. He is a member of the IEEE, and is on the EUROMICRO Board of Directors. OPERATIVNO NAČRTOVANJE GIBANJA VLAKOV INFORMATICA 2/86 Janja Žabjek-DolinSek Iskra Avtomatika, Ljubljana UOK: 519.852 Operativno ntiertovftn]e gibanj« vlakov ealitcva v bakaj alnutah lBd«l*v« naertov ea dve do itlrl ure vnapreJ,po katersB-^naj-bl le cibali na optimalno moten naein.KrlterlJ optlmalnoatl je najaanjla Icguba « erllerlon of optinality Is the smallest loss of train tlàé amltlplled by the eoeffleient of train price.The problem of determining opfimal deelelone belong* to multivariate combinatori ce. I.ÜVC») v avtomat i zaci]t ZeleznlSkega prometa Igra pomembno vlogo daljinsko vodenj« vlakov.Sistemi,ki se danes uporabljajo za dayinsko vodenje in nadeor eeleznllkega prometa v realnem «asu ,so zelo veliki In kompleksni,sa] morajo opravljati zahtevne funkcije za jemanja,prenosa,obdelave In predstavitve podatkov,kot tudi funkcije povezave operater-sIstem. V preteklosti so se tovrstni sistemi za manj sahtevne aplikacije praviloma realizirali samo s klasldrilmi telemehanskiinl napravami,ki so za zahtevnejše naloge vodenja neprimerni. 8 prodorom sodobne tehnologije in cenenih mikroprocesorskih enot,pa se na tem področju vse bolj uveljavljajo mikrorašunalnisitl teleinformaciJskl sistemi,iti v kombinaciji s Blstecni vlakovnih številk in avtomatskim postavljanjem voznih poti omogočajo enostavno in racionalno, reševanje v^eh nalog daljinskega vodenja SelezniSkega prometa. Nadgradnja tega celotnega sistema daljinskega vodenja vlakov pa je avtomatsko razreševanje konfliktnih situaci j.oziroma operativno planiranje gibanja vlakov,ki mora biti brezkonfliktno in optimalno.To delo zdaj opravlja elovek-dispeeer• Dokler vlaki vozijo po voznem redu,nima dlspeCer' nobenega delateim pa eden od vlakov zamuja,lahko , pride do konfliktne situacije z ostalimi vlaki na odseku proge.Tedaj Je potrebna pomoc dispečer Ja,da naStale konfliktne situacije resi. V trenutku.ke vlaki odstopajo od vosneg« reda,Je treba hitro najti retitev » novo gibanj« vteh vlakov v novih,spremenjenih pogoji h. Vendar p« v prlneru goatega proMta In pri eadanjlh hitrostih vlakov «lovek ne emore v«e dela v realnes easu bres poaoei raeunalnika.obetaja vrsta naelnov In algoritmov za racretevanje takih konfliktnifi situaci J,Ideja pa Je v tem,da poiteeso najoptlmalnejlo retitev. Uporaba nudernlh iMtod matenwt I «ne optimizacije ni iMgoea brez Matenatlfine . opredelitve posameanlh nalog,ki nastopajo pri gibanju vlakov.Za nastale,konfliktne situacije torej konstruirano m* tema t i eni model. S.BCliPLIirniE SITUACIJE so: -srečanje vlakov -prehitevanje vlakov -zaeasen izpad odsekov ali sprememba dvotirne proge v enotirno -prepoved postanka vlaka na postaji -Ae Je na postaji veC vlakov kot tirov -£e sta na Istem odseku proge dva ali veC vlakov.(To pomeni ,ee je pri prihodih in odhodih vlakov premajhen časovni presledek.) Take konfliktne situacije lahko matemat icnlm. inodelom.Pa zafnimo. opišemo z Torej Je delo dlspeCerja na železniški orientirano predvsem na vozni. red. progi 3.METODE REŠEVANJA! -Ol oba Ino optimalno reSltev metodo DISJUNKTNEGA PBOaEUMIAANJA. po i seeiDO z LINEARNBOA 38 -Lokalno rnSttev pa doljiino a pomočjo empiričnih inctoto(J j (i . t. i. 'rnetüda raKć 1 nii j eno vezanih reSjtev',ki smo Jo rflzs(ri 1 i , tako da je uporabna tudi v primeru,ko gre za dvotirno magistralno progo 7. APB odseki in dodatnimi tehno 1 usk iirii omejitvami. Članek opisuje prvo metodo. 4.KONSTRUKCIJA MATEMATIČNEGA MODELA Opisiino najprej spremeni J 1vke,fcI nastopajo v ma tema 11 Snom modolu: NPOS ...stevjlo vseh postaj na odseku progö KrOS-I ...število odsekov med postajami NVLAJi ...Slevi io vlakov na odseku proge J'HfHd ,J). ..Cas prihoda vlaka J iift postajo I ODHOD!1,JI,.eas odhoda vlaka J s postaje [ P ..prUiod.ki vsebuje prisilne postanke t (t ,n o t (1,1) TV : a)eas prihoda vlaka I na postajo i 1-1 . ' P I t (I,Y) ali o o t (1,1) < t-4.IU.Y) (7) (8) Po drugi strani pa velja naslednje; 2>ee se jo vlak Y odpravil s postaje i»l in zavzeriia odsek I,Je potrebno: -da se vlak I v tem času nahaja na postaji i'^l al i -da so vlak ! v tem easu ne sine odpraviti s postaje i To pomeni v neenaObah: o p t (i-^i ,y) >= t (i-i,!) ali o o t (-l-H.Y) < t (1,1) O) (10> Ce v neenaebah (7).....(D) upoštevamo cnaCt>e (1J,...,(4> in Jih preuredimo tako,da so n.eznane količine,to so prisilni postanki vlakov X(I,J), na levi strani neenaob.dob imo i NPOS T~X(k,l)- ^ X(k,Y) > PRlH(i,Y) - ODHli.n k = i<-l (11) i ' NPOS ODn(1,1) ^X(k,n- ^ ■x(k,Y) < ODH{iM,Y) -k^^ I ( 12) NPOS (4) ^X(k,y)- 5^X(k,l) > PHIH( i 41 , 1 )-OD11( i * 1 ,Y) irn*! ( - ^XU.V) 'k^* I In P i ?Hin(i,i) = t: (i.n -ZI x(k;n i k = J ODH(l,I) = t (i,l) - V X(k,l) kH (16) <17 ) (18) Co analiziramo onacbe ( 11 ) , , . . , ( 1 4 ) v i d inio., <1a jfi [jogo] (!3) ostrejši od (12) in (lit ostrejši od (l'4),znto uppsIfiViiTiio sflino (111 in (ISt.i'ogoj ea njfispvotnosm<;rnfi vtakp je 1 KPQS ^X(k,T)- 5_ >:(k ,Y) > PnilK 1 , Y>-ODH( 1 , I ) ifn k=iM (JO) al i NTOS 1 -^X(k,Y)+ 71 X(k,n <-PRlM(l^l,!)+ODH(i-^l,Y) irn-3 k=-i (20) PoEoj za tìftSi>rol (losmerne vlak« pa lahko iaiJISenio ludi takole: o o p P t (1,1) <= t (1,J)»T t (l+l.I)<-t ali o o , P P t (i,J) <= t I (i + ),J)< = i b)lSTOSMERNI VLAKI MORAJO KA ODSEKU UPOŠTEVATI DOLOČENI PKESLEDEK V GIBANJU l)pogoil za istosraerni pr i ho= r(J) (23) ali P P t {i + 1,1) - t (1-^1,J) >= Td) (24) Dpogojl za tstosmern! odhod vlakov s postaje o o t ( 1 , J) - t (i , 1) >= T(J) al 1 o o I (1,1) - t (1,J) >= T(I) (25) (26) UpoStevsrao enaCUl (1) in (2) i t> dobimo: il f R ( H ( H 1 , I ) --PHIH(i+1,J) * T(J) (27 i I I • ^X(k, n-^X(k..I) . >= PRIHd'l.J) - -I'ltnn i , I > ' T( n (•■'.8 I k=l ODHfI,I)-OnH(1,J)+ t.T{J) (29) l i 5~x(k, 1 )-^X(k, J) >= oDH( 1, J)-onH( i, n + Én (fn +T(I) (30) Ce je vlak J na odseku I .preO vlakom 1,lore j TV(1,1) > TV(1,J),Rta inocnejsa pogoja (27) in (30). Ce pa jq vlak I na odseku, i. pred vlakom J,torej TV(i,J> > TV(i,J>,sta močnejša pogoja (28) in (29). Torej a)TV(i,J) > TV(i,J) . b)TV((,J) > TV((,[) < -PRIH(itl,I >PBIH(i »1,J)-T(J) ali >= ODilf i., J>-ODH( i , 1 M *T( I ) <3i) 1 i 1) - pHUK i*l,.J)--PRl^^ i 11,]}*T(1 ) ) ^ Rli < ODH( i , I )-ODI]( i , J)--T(J) <32) Ce Biìu 1 i i rsmo /.gornji ncenaob i-, v i d imo ; Ce prej odpravimo hi tre jS i vUik.je zato nio?-no orinraviti posasnf.'jsl . vlak,np da bt čakali nu iztek intervala T,v nasprotnem primeru pa ttga ne moremo storiti,ker bs sicer prišlo do. konfliktne s 1 tuac i j e , zato poCakasno.da so Interval T IzteCe. Pogoje lohko eapisemo tudi takole: o ^ o p o 't (1,1! < t (i + l,Y) ="> t (i + l,n < t (ltl,Y) (33) al i o o P o t ( H 1 ,Y) < t ( 1 . I ) =' = > t ( I ,Y) < t (1,1) (34) Vemo,da se nekateri vlaki v datiih sitùaqljat* lahko gibljejo po fiksnem voznem redu .t)o . ' t»ke situacije lahko pride,fic nekateri tovorni vlaki odstopajo od fiksnega voznega reda,torej zamujajo.V takem sluoaju pa po tnisklm.vlakom ni potrebno spreminjati voznega reda. Naj Snia vtak s fiksnim voznim redom indeks I,vlak,ki ne vozi po fiksnem votnem redu pa indeks J,ozi roma Y.Potem neenacba (32) preide v -ix(k,J) k=l >-T(ntPRiH( i + 1, j)-Friii:(id, t > al 1 <-T( J) <-ODH( S , 1 )-ODH( 1 , J) NeenaCbl (19) In (20) pa preldeta v NPOS PRIH( i (Y)-ODEl( I , O - X(k,Y)J ali ! < = -FRllI( 1 + 1 , I )^ODH( i+ 1 ,Y) (35) .(3G) C»RAZREŠITEV KONFLIKTNE SITUACIJE PRI SREČANJU VLAKOV Vlaka I In Y üe srečata na postaji' 1 < = > veljata neonaebi: o p t ( i , 1 ) > = t ( I , Y ) ► T 40 p o t ( I ,1 ) -f T <= t (1 Cc upoštevamo enaObe (1),,..,(4),dobimo 1 <38) NTOS , I )- >=ODH(l,I) ™iH(l.y)*T (39) 1-1 (40) 5~X(k, 10- T_X(k,Y,' ■ PR!H( f , t)-ODH( I .Y)-T To so ntenaCöe «a srečanje vlakov.- tDRAZRESFTEV KONFLIKTNE SITUACIJE PRI PREHITEVANJU VLAKOV • . VlAk J prehiti vlak ! na postaji i <=> ko vcljn: P P t (i,J) - t (1,1) >= T= T( 1 ) (41 ) <42) Loelmo dvo možnosti: Mvlakn vozita v smeri----> 2)vlaka vozita v smeri <---- V prvem primeru sta ncenacbl ÖlK.J) >= T(J)-I>IllH( 1 ,J)*PRim I ,! ) (43) k= I al 1 X(k, I )-^X= T( n-ODH( 1 , I )+OOH( 1 k=l (44) kjer smo v neenaöbah (37) In (38) upoštevali pogoje I 1 ),... , <41. V drugem primeru pa sta neenaöbl 1 <= ODH((,I) ali <= P'RIH(i + l,T) Linearni program se potem glasi takole: (iC) določiti ie tralitt vrednosti spremenljivk X(1 ,J),1=1.....NP0S,J-1.....NVLAIf.ki zatloSCAjo pogojem nenegativnostl X(I,J) >^0,1=S,,..,NPOS, Js 1 ,, ,. .NVLAK In 1 i iiearnlin ncenaflbam: -pogojem naspi'otnosinern Ih vlakov <19,20) -pogojem Istosinornlh vlakov (31,3'5) -pogojem srocanja vlakov (35,36) -pogojem prehitevanja vlakov (39.....42) -pogoju zaprtosti odseka (45) tako,da (ma namanska funkcija NPOS NVLAK m K = . operacija Oe-potcm (Implikacija, ali NPOS (45) (46) X(k.n- X(k,.T) >» T(l) - ODH(i,I) k=l +OOH{i,J) To so neenacbe prehitevanje vlakov. e>RAZRESITEV KC>:rL]>lTNE SITUACI JE, CE JE EN ODSEK PROGE ZAPRT ZA PROMET Odsek 1 je lahko v Intervalu (tl,t2) zaprt za vlake.V tem primeru moramo upoštevati dod.itne pogoje, Cas odhoda vlaka I s postaje I mora biti veCJi 0(1 12: el^v 1 val entna d i s junkc I j I ,ker je (A => B) (A V B).V splošnem je disjunktni program problem ob!i ke: {min cx.Ax >- ao ,x >« 0,x£L| je < = > (DP) (51) kjer je A matrika m j< n,ao vektor dimenzije m In L ronoJ.lca logi dni h pogojev. Obstaja veö oblik dlsjunktnega linearnega programa.Na j bol j znani sta dve: n DP je v "dlsjunktnl normalni obliki",ee so pogoji dlsJunkclJe,kl ne vsebujejo naprej novih disjunkci]. . h hI A X >= ao * >= O V h e Q (51) t (1,1) >= t2 (47) ali pa mora biti e».s prihoda vlaka I na postajo (l'I) manjši od ti : 11) DP Je v "kon junk t i vn i normalni obliki",^».' so pogoji kon juiike I je I ne vsebujejo naprej nov i li kon j unkc i j. t ( I M , I ) <= ti ril v nr.Mi.Tf'bi,!, f4:n in (44l uf.oS t (rViimo .•ti:f('t>i 'M Iti ri) .ilobimo p(>i;oj Ax >= ao X >= O I V ( d X > ^ d ) ■ j € ICQ io J 1 r.3) ali Ax > » a o\ i i & < (d X >= d ))&...&( (cl if >= = O lo i^Q lo ' J H 1 (54) kjer jc d vektor dliiicnzlje n,d Je skalar,Q,Q 10 j In S pa so lahko kontno ali heskonftne. Zve^^a ln<>d obema ot> L i knni:i Je y tem,da ima vsaka dlsjunkeljft d) med (rn'n) tieena(ibsmi sistema Ax> = ao,x>"Ü na tanku eno iiciinaCbo i d X >= d , 1 £ q lo J . (55) Iz vsaki! disjunkcije (ii) In da so vsi razliCnt sistemi h h A*>-ao,x>=0 (56) s to lastnostjo,v itiojrih (1).Torej,ec jc Q( In hkrati, vsi Q konficn, [>01 em jc |Q| ÌTTqI . j € S.fcjer Jc n karlezieni produkt.Ker sta operaciji In In ali di ü t r i hu 11 utt 1 , 1 ahko vsak logični pogoj,ki vsebuje ti dve opcrac 1 j 1 . zapi Semo v prvi !ill d rupi ^.naćiinl obliki np.SploSha definicija d i sjuiiktnega llriearnc[^a programa se glas I : po i <>£ luio vektor X,pri katerem linearna foiina L(X> doseZe minimalni omejitvah n z: a X j=l IJ n = ^ C X ^ J 1 ml nini mlnlnium pri = b I ) i i (57) naslednj1 h <58) kjer Jc 1=1,...,m,j=1,..,,n,b < b , c >= O, /i 11 j X 0. Takoj laiiko iigolov Imo ,da so pogoji' K-i. navedeni dlsjunktni linearni program v konjunktivni nortiiaini obi Ik I , toro j se dajo zapisati kot konjunkclja samih disjunkclj. Definicijsko. obtiioOJe C naloge v n-dirnenzionalnem prostoru dobimo z unijo posameznih obmocij m 2 n C = U C t-:« t/ kjer JD n m C = {x,Ax >= B , K O ,t = l,2....,2 J t t Problem rs>sujenio 7. nictodo dihotomije (kar pomeni " razdeljenost na dvoje " ), katere i do j a j C v 7.(vpo letini delitvi mno7. le«; podroClJ. def Ini riinost I naloge na dva dela, tako da Izpustimo iz nada 1 J neg« računan j a listo poJüvico.ki lit- vsebuje ekstrema linearne n forum.Vsako delno območje C ,k i ga dobimo z t vektorjem onie j i lev, iitia v slučaji) omejitve nav/iOol dano rciilfv M .N.iJ bo minimalni lak t ml nI milili in M -- i n f I M \ , S 1 , 'i.....2 ■ m t Pri tem M je kriterijska funkcija m . na jriian j fia .00 i (no je; da 7. naraščajočim m pridemo do pruvellkegi Števila kombinacij. ZapiSlirio p&KoJ omejitve tal(o,dà uvedemo fl , pri O -i 1 . pri 1 i Poleni je pogoj om= b H J=1 Ij j 1 (59) n H-S a X b IJ J .11 (60) Nalogo s tem pogojem omejitve oznanimo kot iiulugo (!). Definirajmo Se dualno nalogo! 1 scemo ntlnimalnì maksimum linearnega programa oz 1 roma b(Y) I' y i =1 il ni. JAY) ^^(-b )y m i i i pr! nasl.ednjili omejitvah (6) ) (62) 1) m 5_ü« y =0 i (63) Ce uvedemo n dopolnilnih nencgatlvnih spremeni J i vk " l>2l a y * y = e ,J=l,...,n rn IJ 1 n+j J 2)y >= O, 1 To nalogo pa imenujemo naloga 2. n n Ker je C 11 C - 0,tl Ä t2,iie obstaja splošen ti t2 algoritem za obe podro<>jl rtef I ii I ranost i naloge I.Nasprotno pa delna področja naloge 2 vzajemno vključujejo drugo drugega in za to nalogo obstaja spioSen algoritem. V (m+1) razseznem prostoru Z razširjeni vektorski prostori Z presekajo mno7.ico m+1 konveksnih poliedrov : m+1 ■ C =lZ,AZ+BZ >=O.Z>=Ol t t ni+1 m t=l,2,...,2 f65) Vektor omejllve v tem prostoru oplSemo s l> rem i so c=iz,z=cl (06) de r I n i C I j sko obinoftje deSise nalofo v prostoru Z oplftemo s presckoiii III'- ] C n C t (67 Po drugi strani Je en« mejna ploiikc;v,td ju p!oskt-v,ki je def!nlrnn:i z ono t s k i uri vr.^ktorji • A ,.•., A ,s(;up(ia za vso (>u 1 1 «dre .Tn m* I ni'n plosk(;v Ima pozitivno iis^ie r j pnos t. v prostoru dlineiizljp rri In soka p retri i co C,kjer jo e > = Q, j Od totl s led i, da se dof inici jsk.i obrnuCja (67) pojavljajo kot urojcnc iiitioJ Itfc, k i vza.I<;tTina vkl jii('iijcjo dniga drugo.Zu nalogo 2 obstaja s J gor i t I'm, k i letiielji na zu pove s t nem i Kbol jfievjiri j M rcsitvc in jo podohnn aSfforitmu zapovrstti(!fvi izboljševanja rešitve pri klasični metodi llntafnega piograiìi«. Pos tO(<<;ii J« I terat i vfti. Ker je bj la v nalogo 2 uvfd<;nCe pu uvedemo v bazo vektor P in od,s t ran Imo k vektor i' .dobimo vrednosti, r '(r) kjer je " tr) A i A ^ -e- . A I r k 't II It A - ^ . A i r k (76) 'Mr) • ' I • ^ = "(z /z ) r i p kr (77 ) (78) Naj bo Iteraci j»,v kateri smo z uvedbo vektorja I I 1 P .zadnja,pri kateri P in P na kakršenkoli k k k naCiii vplivata na prirast linearne forme.Torej od zdaj naprej uvedemo v bazo samo tak vektor,ki daje pri dani iteracijl manjii prirast,V tem primeru jc splošni prirast v druE'i iri vseh nasiednjlli iteracijah ,min L(P P ) ,pri uvedl>i P k i p (73) (P>- A < o v druj^em za AL(P ) k I I Anp > k (10) (71) V bazo uvedemo vektor,ki da pri dani iteraclji manjši ptirast linearni t'ormi.Naj bo 1 II AL(P ) > AL,(P ) k k <72> potom je smiselno pri dani iteraclji neobhodno f ! uvesti v bil K o vektor P .V(»iirtar to vplivu tuiM a ' ' ' »« A '"A , zarati i Cesar inornrno ü« i dodatno xaiiìcn j t i vektorje v ha/, i . I.a liko p;i iiisiiipri tnili l'nkt.or [lovv.roci ilodatni pririiül llMi'iiriK» r " rnic , IIeim k prosili s I ck vri ju in ^ 'I id_min L(P P ) ,pri uvedbi r k 1 r (60) Aj < ® Označimo (79) 7. fl tn (60) k f2.Potem volja t It Ce Al(P ) t n < Al(P ) * fJ .potem slodi: k k I Je treba v baüo uvesti P in odstraniti P . k p I ! I Ce Al(P ) ' n > Al(P i * (2 ,potem sledil k k t t je treba v itaKii uvesti P in otlstraniti P . k r Ta kriterij ostane v veljavi tudi v s i mM ) 1 h . ko vek tli r j i , k I Jih jo t ri'h.-i ' uves t i . vpl i v,i jo iinij iiH prlriisi llni'.T.riin formi' v i torru-i j:ih, K i « 1 ^^d 1 Jo.Kcr ìiiki naloga 1! /jiOettiu muc t ni) I>m'/ii,ji' . --a, U U "i J i («1 ) Sie k II ry. i V ne ntiaCtx» za nalogo 2 t>a so nüsl«dnjc: "M I)ee z u m cu jamo vcklgr P z vektor jtiiii P P k .(p) I I t t z - (K a )/•/. I] i j kj ip kp ) X k "(p) '(p) ^ = tJ 2 IJ kjer Je I ij ,1- / ^ - Qy. Ij ! Ij z K y K I k \k kp Mp) '(p) e T. Q K ik ik t t 2jee zanicii jniiio vcktur P z vektorjem H r k (82) (83) ' ' {D a t z U Ij iz z ) / a , j / k <8T> kj ir -kr " ( r ) ' ( r ) z ^ U z ■ / k Sj i Ij itr) f 1 > 1 I z " z r z = z z' (J z ik i k ki' i k k kr "(rl ' »ivedeitio v bazo vektor P .Levo i i apuduj pa jf' vsuta vrednosti nianjsih prirastov i tt linearnu follile pri dani bazi. V zafeini tabeli j(; vrednost linearne forme L(Y) = O ni (92) V postev za uvedbo, v bazo pridejo samo vek.lorj i ,prl katerih je < 0 in I I r A < O I Vektor,ki ga uvedemo, i zraćunaino iz izraza ni lil (7. / a ) jo kj .z > O kJ (93) (94) (95) k-Jcr jo z - z pri uvedi)! P in z = C) ^ kj kj k k k kj I « ■ uvedbi P .Potfni v skladu s prej navrdrjnimi k rekurzivniini fovmutuiiii Si'S t a v i iiio dve tabeli: l)l>rvo,pri kateri v bazi zaineiijano vektor i' z P vekloi'jem P k Z)dr!Jgo,pri kateri v bazi zamen j amo vektor P 7, ' ' r vektorjem F k Ko v obeh tabelah zapolnimo z.'^alnji vre t i ci , pr ImtT jarno najmanjše priraste In linearne foi-iiii? pri no v Iti bazah.Manjsa vsota določa, kater i vektor je treba uvest i.Po doloCit.vi nove baze iz nadaljnjega raOiinanja j ud i Ilio ena tabelo,drugo tabelo pa kot zafetno uporabimo pri naslednji I terair i j i . 7 , Z.M5LJUCF.K Ta pristop za .operativno naćr t ù , i r.J e dajo globalno optimalno reS1tev,vendar pa v praksi ni upor abt II, kt-1' pri vecjeiu Slevilu ("ustaj in vlakov,. naliteva pi-evc(> raCunu i n i 5 kaga Casa.Algori tem se zato uporablja samo za Ir.h-sra tori jsko proučevanje in r.aortovaii jc Cibanja vlakov na manjsili primerih,ko je Število v lil k II v nia j lino ( npr . 5 ) In Število postaj tudi niajhnofnpr).Argument i,k i kažejo na to,da tnk algoriteiii no ustreza praksi,so tned drugim; l)pojiavadl podatki niso znani toliko vnaprej,da bi imel globalni optiitiurn prednos t i .Doßodk i na progi se nariireG stalno spreminjajo. 2U'elIk čas računanja zaradi Ze omenjenega prevclikoffa stevii^i kombinacij 3) nekatere tehnološke omejitve je te?.ko vključiti v niudei i. npr .ome j I t ev ,da na postaji ne sme biti več vlakr^v kot tirov) 4)lokalni m i n i rnuii: je bll7.Jl realnemu gibanju vlakov na pro^'i." Zato so v pr:ilisi bolj (ipor.iijiii a i K" i'i'm i . k i proi)l(;!ii rešujejo ! ok a 1 no , ka r [tuhUMi i , da ri'Mi j o ju konflikti.' na liia/i J s eiti ume J riicin oljuir»!''j i: nr|.-» j postaj naprej I fi nekaj na/.aj le liidl dvema v I a kiiiii'i . dve rfioini vrednosti za kopf 1 C i t'iUü 1 Infame forniD I . I 1 I f -b ..-b 1 i .-b baanl vektor j i p 0 P 1 p m P m+1 P ns' n P ! m+l 7. m+l ,0 z 1 ,ni»I Z in,m+1 l 1 • * 5 ! ! • • P in + n Z m' z 1 ,m^n Z ini)n+n 1 Lta v Iskri avlomafiku (Tt.Hnihvny Safety Coiicrnä and Au I OKia t t on tüwnrds the 21 tli Cen t ii ry , London , 1 a 84 OPTIMAL CODE GENERATION FOR SOME SPECIAL CLASSES OF MACHINES OuSan Petković Siemens AG, Mtthchen, F. R. Germany UDK:681.3^25.6 ABSTRACT. Kameda and Abdel-wahab [s] investigated the problem of generation of min imuTO-length code foj: a wide class of machines. They establish an attainable lower bound on the number of "load"-instructioins, as well as an attainable lower bound on the number of "štore"-instructions. However, they did not succeed to reach the main goal: to minimize the total sura of "load"- ànd "store"- instructions, because of interaction between these two types of instructions. In this paper we show the optimal code generation for some Special classes of machines given by Kameda and Abdel-Hahab. OPTIMJILNO GENEEISftNJE KODA ZA SEKE SPECIJALNE KLASE MAŠIHA - Kameda i Abđel-Vfahab [5] su ispitivali problem generisanja koda minimalne dužine za jednu širu klasu mažina, Ü svome radu oni su pokazali da broj "loađ"-naredbi i "store"- naredbi je minimalan za tu klasu maSina. Medjutim, nije im uspelo da dokažu da se suma "load"- i "store"- naredbi može mir nimizirati, zbog postojanja interakcije izmedju ova dva tipa naredbi za datu klasu mašina. Ü ovom radu ćemo pokazati optimalno generisanje koda za neke specijalne klase mašina koje su obuhvaćene klasom mašina datoj u radu Kamede i Abdel-Wahaba. 1. IMTRODOCTIQN Code generation: is a part of compiler const-: ruction which has been getting increasing at-; tention. In his paper Nakata [fij considered the problem of minimizing the number of general purpose registers needed to evaluate an arithmetic expression. Redziejowski [l] showed later that Nakata's algorithm gives the minimum number of. registers when only commutative operators + and * are considered. Sethi and Oilman fqj developed an algorithm which generalized all previous results; their algorithm minimizes the number of instructions needed to evaluate an arithmetic expression when there is a ' fixed number of registers. All these algorithms are fast, because of a restriction that each subexpression will be used exactly once, Bruno and Sethi [ij showed that the problem of generating a shortest code for expressions containing common subexpressions is NP- complete even for a one-register machine. Carter showed the best algorithm (until now( for generating code for one-register machine for expressions with common subexpressions. In all these papers it is assumed that the result of an operation appears in a register and "store"- Instruction is the only instruction that can change the Content of memory locations. Kameda and Abdel-Wahab [y relaxed this restriction and allow register-to-memory Instructions other than "store'.', and also memory-to-memory instruction. Under such assumptions they defined a class of machines and tried to find an optimal solution for code generation for that class of machines. Unfortunately, they failed tö reach that goal, because of Interaction between "load"- and "store"-instructions . In this paper we investigate some special classes of siachines which belong to the wider class of machines defined by Kameda ćind Abdel- Wahab, and show optimal code generation for them. In part 2 of this paper we give all definitions needed, and definition of the general class of machines. In the part 3 and 4 we show optimal code generation for two special classes of machines defined In part 2. ■2. DEFIKITIQNS AMP A GEHEBAL MODEL OF MACHINE In this paper we adopt definitions given in [Sj . An arithmetic expression is given as an expression tree whose leaves correspond to variables and/or constants, and whose interior nodes Correspond to operations. If there is a downward path from a node v to another node w (we assume that, a root is at the top), we say V is ancestor of w (similarly, we say w is descendent of v ). A direct descendent will be called; son. Thus, node representing a binary operation has two sons, left son and right son, A node and all its descendents comprise a subtree. The value of a node is defined to be the value of the subexpression represented by the subtree rooted at that node. The value of a tree is defined to be that of its root. We call a downward path in an expression tree leftmost, iff each binary node in it, if any, which is not the last node of the path, is followed by its left son. Level-one node is a node both of whose sons are leaves. Level-n node is a node one of whose sons is level-(n-1) node and the level of the other node is £n-1 . If the root of a. tree is lavel-r node, we say that r is a depth of that tree. We shall now give a general definition of a machine model for which prograi® P has to be written (P evaluates a given expression tree!. 46 The inachinc has NV 1 general rcfjlsters atid a countablü liücjuiiiiice of nemory locations. The-in-sLructions are r'«-!!! "load"- ills L ruction, M"-!: "store "-instruction, and tolloviny binary instrvicclonn: iiij.<- III. op nij m i-tn op r r op r, . r r op m . r denotes a register and m denotes a raernory lo- ■ cation. He assume that the type inctruction Is dotermined by the; operation it imploments. If a binary operation recjuires its first operand to be in rcgisiter, tiie corrnr.ijon-ding instruction is said to be of a type /i., antì if a binary instruction requires its second operand to bo in a reg Later, thy corresponding in.itruction is said to bo of a ty[je /3,. Analogous to that, a binary insttactioti that does not require its first (sQcoiiJ) operand to be in a register is .<;aid to be of a type '/- 2' ' h binary in^jtruction may be of ä type: ' • Pi • 'V-'? ' A.■ particular machine may have only a subset oC thc.se types. For instance, the Sethi-ülliiian iiiachine model [8] is of the type /J.A/J,- Our goal is to find a panoram which evaluates a given cxpretsion trco for a special machine model ill the minimum time, MfiClllNE; MOtir.L The set of instructions for this machine model is: m^ m^l op iTij , r *— ni and HI *— r. The following algorithm is the basis for the optimal evaluation of a given expression tree. Algorithm Ì. Step Ì. Find each subtree of the given expression tree T, vrhose both sons are leaves. Evaluate all. these subtrees (sequence of evaluation is irrelevant! . If evtsry subtree is evaluated, go to step 2. Step 2. Replace every subtree from step V with a leaf and let the new subtree beT|. If T consists only of the root of T, terminate, tf not, apply step 1 to the tree T^. Now, we prove some Lemmas, which hold for this machine model. Lemma 1. If every leaf of a given expression tree T is in memoj.y, than "store"- and "load"-instructions are superflous in evaluating T. Proof. If every leaf is in the ruemory, than the result of evaluating every internal node (with op-instruction) will also be in the'memory. ■ Under conditions of lemma 1 this machine model has only ona instruction: m^ m^ op m^ • I.cmnia 2. Every level-one node I of a given expression tree can be immediately evaluated. Further, the result of that evaluation replaces the value of the left son of l in the memory. Proof. Directly from tlie definition of tho machine model. Lemma_3. The number of instructions of the program which optimaIVy gonC5vatoa code for a given o>:ijrcr;:; i on tree- is equal to tlic number of intornal nod..'.'; of that trco. Proof■ We have to show how to evaluate every internal node of a given expression tree with only one instruction. E.et I bo the incernai node with left iion and right son I , and let Ij) and I be levox-one nodes. Applying leirana 2 to Ir and I we can evaluate each of them with one instruction. Also, the values of and 1 are now in memory, ilenc«, we can evaluate I ilso with one instruction a..d the value of 1 will be in memoryProceeding that way for all internal nodes we can evaluate every internal node of a given expression tree with one instruction. Theorem 1. Algorithm 1 produces program which optimally generates code for a given expression tree and the value of the root of the trco wj]l repJnce the value of the left son of the leftmost downward path starting at the coot, Further, algorithm 1 produces that program in linear time. Proof. The first part of the theorem follows directly from lemma 2 and loirmia J, To show that algorithm can be constructed in linear time vie traverse given expression tree and mark all subtree,"5 from step 1. Th^s can bo done in linear time. Step 1 v^ill be executed d times, whf^rc d is the dopth of given expression tree. V.'e need one instruction for cvaVuMtion of every subttEse. Thtitefore, the algorithm can be performed in linear time. A . /0. A - M AC ; 11N E MODEL The set of instructions for this machine model is: m*-m op r , r<- tn and m<-r. Algorithm 2. Find each subtree of the given expression tree T, whose both sons are leaves.■ For every such subtree S first "load" the right son of S and evaluate S immediately after that (the sequence of evaluation of subtrees is irrelevant), If every subtree is evaluated, go to step 2. fieplace every subtree from step 1 with a loaf and let the now tree be T.. If T, consists only of the root of T, terminate. If ...jL, apply step 1 to the tree T^ . W(j sliall show that algorithm 2 generates optimal code for a given expression tree and the given machine model. For that purpose we proof some Isminas which hold for t^.ic machine model. Lemma 4. If every leaf of a given expression tree T is in memory than "store"-instruc-tion is superflous in evaluating T. Proof. To evaluate any internal node, every left operand has to be in a memory and every right Operand in a register. After evaluation, every internal node will bo in memory. Therefore, "load"- Instruction is only instruction we need, besides op- instruction. Under condition of lemma 4 the machinr model has than following two instructions; and m op r r <5— m. Lemma 5. The number of op-Jnstructionf required in an optimal code generation of a <|i-ven oxprcr.iiion trs'c; T i;; equal lo the numinu of intornai riodoi; of T. Proof. Trivial. 1,0mino 6. Th« number of "loađ"-instructions icquired in an optimal code yunertitiori of a given expression tr(;e T with the given machine niodcl, is etjual to tho numtior of internal nodes •of T. Proof■ To evaluate any lovcl-cnc node of T wo need one "load"-instruction for his right soft. After evaluating all level-one nodes we ' can, in the same manner, evaluate all level-two nodes and so on. Theorem 2. Algorithm 2 produces program P which optimally generates code for a given expression tree and the value of the root will replace the value of the left son of the leftmost downward path starting at the root, further, the construction of program P is linear in time. Proof■ In lemma 4 we show that "load"- and Qp-iiistructions are only instructions needed to evaluate a given expression tree. Lemma 5 and leirjna 6 give the fRimber of op- and "load-instructions. needed to generate optimal code for a tree. Algorithm 1 evaluates all expression trees cxactly in ;':*n steps, whore n is a number of internal nodes of the tree. Therefore from lemma S and le;ama 6 alyor^ithn 2 produces program which optimally generates code for a given expression tree. The proof of the second part of the theorem is similar to the proof of the second part of theorem 1. 5. CONCI,UDIHC: REMARKS. Our final objective is to minimize the total number of "load"- and "store"-in3tructions for the class of machines defined in [Sj . We still do not have a solution of that problem, but we are hope full that one will be found. 6. REFERENCES [lj Aho,A.V. and Johnson,S.C. - Optimal Code Generation for E.xpression Trees, Journal ■ of ACM, Vol.23, No.3, (1976t, p.488-501. [2] Bruno,J.L. and Sethi,R. - Code Generation for One-Register Machine, Journal of ACM, Vol.23, Mo.3, (1976), p.502-510. [3} Carter,L.R. - Further Analysis or Code Generation for a Single Register Machine, Acta informatica. Vol.IS, (19S2), p.135-47 [4} Garey,M.R. and Johnson,D.S,'- Computers and Intractability, Freeman and Co, 1979. 5] Kameđa,T. and Abdel-Wahab,H.M. - Optimal Code Generation for Machines with Different Types of Insturctions, in: Gilchrist, B.(ed.t - Information Processing, IFIP Congress, Proc. of 1977,North Holland. [6] Nakata,!. - On Compiling Algorithms for Arithmetic Expressions, Comm. ACM, Vol.10, No.8, (1967) , p.492-494. [7| Redziejowslci ,R. R.' - On Arithmetic Expressions and Trees, Comm. ACM, Vol.12, No.2, (1909) , p.81-84, [el Sethi.,R and Ullnian,J.D. - The Generation of Optimal Code for Arithmetic Expressions Journal of ACM,Vol.17,No.4, (iy70),p.715-28 [9] Ullman,J.D. - Thi; Comploxity of Code Generation, in: Tj.-iUib ,J . D. (t:d. ) - Alyor i.l.llWH and Complexity, Academic Press, 1076. PREGLED PARALELNEGA PROGRAMIRANJA INFORMATICA 2/86 Anton Ružić, AleS Klofutar Inititut Jožef Stefan, LJubljana UDK: 681^26 v članku podajan» pregled paralelnega prograaiiranja. V uvodu opisujeno prednosti in potrebe po uporabi netoa paralelnoga programiranja ter načine doseganja paralelnega Izvajanja. Ha to opisujemo paralelno programiranje s prikazom razvoja tega področja. Ta Je potekal akozi nezanesljivost začetne tovrstne programske opreBje, postavljanje konceptualnih temeljev do ražvoja programskih Jezikov, (d. vključujejo postavljene koncepte. THE DEVELOIHENT Of OONCURREWT PROGRAfMIHG. In this article we describe concurrMt programnlng. The methods and techniques are Introduced through overvlewing of the development of concurrent programnlngv Ihis went through several stages.- the Initial development of cocpllcated and unreliable software sjrstess, the search for abstract concepts that s^llfled understanding and the incorporating of these oonoepts into new programming languages. 1 Ovod let. Začetni motiv Je bil Izkoriščanje možnosti, M. Jih Je nudila nova materialna oprema. Z nazivom paralelno programiranje zajamen» programske zapise In tehnike, ki izražajo možndst paralelnega Izvajanja In ki omi^ocajo reSevanJe rezultlrajočih sinhronlzacijsklh in komunikacijskih probl^»v. Posamezne programske enote, ki se paralelno izvajajo, Imenujemo procesi, ünan» lahko navidezno In dejansko paralelnost. Navidezno paraleinost Imamo, če tečejo vsi procesi na enem procesorju in Je vsakemu procesu dodeljen določen čas. Dejansko paralelnost dosežemo, če uporabimo več procesorjev in vsak prevzame en ali veo procesov. Paralelni program anogoča, da računalnik izvaja več nalo® istočasno. S peralelnim prograniranjem zvečamo računalnikovo učinkovitost In enostavnejše obvladujemo okoaja, v Icaterlh se računalnik hkrati posveča različnim opravilotE, V prvem delu na kratko opisujemo prednosti, ki nara Jih oasoBOČa uporaba paralelnesga programiranja pri izgradnji programskih sistemov. Podajamo možne načine za uvajanje paralelnostl In probleme, ki Jih moramo pri tem rešiti. V nadaljevanju šlrle opisujemo možne . načine za predstavljanje paralelnih dejavnosti (procesov) In mažne načine za l®munikaoiJo In sinhronizacijo med procesi. Posamezne načine opisujemo skoei pregled razvoja paralelnega programiranja. Razvoj se Je začel kmec 60. Področja uporabe Paralelno programiranje se uporablja predvs«! pri operacijskih sistemih In v sistemih za delo v realnem času. Pri operacijskih slsteniih lahko Izboljšamo izkoristek materialne če- imamo v poomilniku veS programov hkrati. Medtem ko en program čaka na izvedbo vhodne ali izhodne operacije s počasno periferno enoto, procesor računalnika izvaja nek drug program, naložen v ponBillnlku. V tem primeru se procesor preklaplja med različne programe, M. se izvajajo navidezno istočasno. Več uporabnikov lahko hkrati dela na računalniku in uporablja vse računalnikove resurse. Uporaba paralelnega programiranja je posebej koristna, če' ne skoraj nujna, pri vgnezdenih sistemih za delo v realnem času, kot so na primer procesni sistemi. Pri teh je delitev globalne naloge na več procesov motivirana predvsem z enostavnejlia reševanjem . naloge. Računalnik mora pravočasno sprejemati signale z različnih neračunalnišklh ali računalniških naprav in jih ustrezno krmiliti. Zahteve po sprejemanju in krmiljenju se v splošnem lahko pojavijo v različnih časovnih trenutkih. saj Je to pogojerw z di^a-rdko slsteir»v. ftaäunalnlk ir^ra hkrati obravnavati in obdelovati podatke a številnih-vhodov in. Izhodov. V tem prlffleru upraviJalsko naloco, erjoütavricje in narevnoje rešimo, če Jo razdolimo na več delov, ki so paralelno i:;vaJiiJo. Paralelno, prcgrariranje uporabimo tudi zato, da zvečaroa yjTOKljivost ran'jnalnlka in skrajšano čas ìzvfijanja' neke nnloEO. Naraesto enoproceiiorike/^s vzamemo večprocesorskj. računalniški sistem. Celotno nalogo razdelimo na podr^loge, ki se paralelno izvajajo na poMuneznih procesorskih elerisntih. Delitev naloge na dele, ki sfi lahko p.'^r^-.l el no l7.v?.iaJo Pri ZEraJevanJu sistema, ki uporablja paralelno programiranje, inorarro riajprej ugotoviti, katere aktivnosti se laiiko opravljajo paralelrio. Celotna naloga, ki Jo rešujecso, je l.ihko postavljena tako, da Jo eno;;t;ivria razdelimo na pai-raUjlne-akl^ivr.osti. irViii^r je krmiljenje določenega števila periTertiih naprav. Pri nekaterih nalogah je ta proMem bolj zapleLert in se ne d.1 r-adcvoljivo rešiti z uporabo "ad hoc" načinov. Takšen prirr.er so nekateri mateinatićni izračuni, kjer iRoramo identificirati delne izračune, ki se lahko istočasno Izvajajo, preden se. ir..rorijajo vitesni ' rezultati Izračunov. Paralelno preračunavanje moranw optimizirati pri oiaejitvah earadi serljsko-paralelrilh prednostnih razmerij. napi senso vcčposlovni izvrčevalnik. Td Je pravzaprav inačica .Jedra pri tnjltiprcgranskih operacijskih sistemih. Celotno nalogo razdelimo na procese in jih skupaj 7. izvr.ševalnikom naložimo v poimilnik. Izvrševalnik skrbi za iz.renjevanje izvajanja poslov na procesorju (procEsom, ki so del enega uporabniškega pros-^ama, lahko rečen» posli, angl. "task-s"). V izvrševalnik vgradimo tudi semaforje ali druge mehaniziM za Icoinunikricljo In sinhronizacijo. Pri Bill ti pro;':ram3 kein ali večpoglovr.cm operaoijskeir. sistertu uporabitio za doseganje paralelnega izvajanja propraTOv sisteiraki izvrševalnik in druge funkcije, ki Jih nudi operacijski sistem. V tem prinaru posairjezne procese zapišen» kot posle ali samostojne prograr® v prinrernera progr.irf.ketn -jeziku. S si .stems ki n:i ukazi sprožimo paralelno izvajanje posameznih programov.' Takšni operacijski sistemi podpirajo tudi nek način medprocesno komunikacije. To so lahko' semaforji, ■dogodkovne zastavice, poštni predali in podobno. Nazadnje inaino možnost, da uporabimo prograir^ske Je?.lke, ki i■odt;lr^J':l p'ir -l el [•'"^fTa*;;! Osnova tf'h jc7.1kov jedro, ki oniogoča paral eno izvajanje modulov in interakcijo med procesi. Te možnosti uporabljamo s primerniBl stavki jezika. V to kategorijo lahko postavimo jezike PEARL, Concurrent Pascal, MoùJla, Edison, Ada in dru£;e. Vključitev paralelnosti z uporabo^ takšnih Jezikov je zelo primerna,"saj se v ten: primeru bolj posveti.iao reševanju naloge in ne impler.entaciji mehanizmov, paralelnosti. Pcmenibno merilo za uspešnost delitve jc čim večja neodvi.^nost procesov. V idealnem primeru so procesi popolnoma samostojni in operirajo le nad svojini podatki. Ponavadi pa posamezni procesi opravljajo neko skupno nalogo, potrebujejo iste resurse ali kako drugače sodelujejo. Zato Je potrebno, da procesi med sabo komunicirajo ali pa se v določenih točkah sinhronizlrajo. Pote;;;, ko sn» razdelili nalogo na logične enote, moracno izbirati način za izražanje paralelnega izvajanja posameznih procesov in izbrati orodja ozirona načine, ki bodo oniogočili nadzorovano in pravilno interakcijo procesov. Te načine širše opisujeiro v naslednjem poglavju. Načini paralelnega izvajanja 2 Pregled razvoja in opis načinov in orodij paralelnega program.! ran Ja V prejšnjem poglavju smo pokazali, kako uporabljamo paralelno ' programiranje za učinkovito izkoriščanje računalnikovih zmogljivosti, zvečevanje i'aòunanikove zmogljivosti . in za uspešno obvladovanje okolij, v katerih se mora računalnik . hkrati posvečati različnim dogodkom. Paralelni sistemi so pri takšnih sisteniih koristni in potrebni, Izdelava pravilnih in zanesljivih •programov pa je zahtevna. Najmanjša napaka, lahko povzroči, da se paralelni program izvaja nepravilno in neponovljivo, kar onemogoča,testiranje programa. Opisali bomo, kako so programski Inženirji postopoma reševali ta problem. Nazadnje -le moramo pri 'takšruh sistemifi odločiti za primeren način paralejlnegi i^yajnnja in sJ.nhronizjct.je tsr koniunik.-ij i je mod (irocegt. čc nlrnnjo nobenega . prlr)i<':rrK':Tn ot-odja, feralelno prosraruranje so uvedli, da bi izkoristili dosezkE na področju traterialne opreme. Po začetnem poskušanju so procramcrji ob ponvmjkl Jivcm znnnju izdelali zapletene sisteme. Ti sistemi no zato bili Uiko nezanealjivl, da so. sami račrtov.ilci ujx)rnbili i'/.r.ir. "kt-i-/,.i prcw.rnnslif opreme", Račiinalnjški Lmanst vcnl ki spoznali po.Ten problem in zaceli iskali abatraktne koncepte, s katerimi so poenostavili razurnevanje paralelnih programov. Ko so razumeli bistvo problema, so postavili znpis za osnovne koncepte in jih definirali tako preoizt», da so jih lahko vključili v nove progransko jezik». Jezikovni zapis Je omogočil rapredek pri for'~:ilnem raz'jmevanju probl^^ra, V tem poglavju • bon» opisali razvoj paralelnega prograra.r&nJa. Ob tem:bOTO obravnavali-načine izražanja paralelnega izvajanja procesov in načine za komunikacijo in sinhronizacijo med procesi. načinu iman» istočasno v pojtaiilniku več poslov s pripadajočimi podatki. Časovnik v enako-uernih časovnih preslèdkih. prekinja trenutno Izvajani posel in sproži iEvaJanJe naslednjega posla. V kratkem času se izmenjajo vsi posli, tako da se izvajajo navidezno istočasno. Trenutno aktivni posel se ustavi tudi takrat, ko sproži izvajanje vhodne ali izhodne operacije s periferno enoto.' Medtem ko se vhodna ali izhjodna operacija Izvaja Cna primer zapisovanje na disk), se na procesorju Izmenjujejo drugi posli. Ko periferna naprava konča operacijo, s prekinitvijo Javi da se.pripadajoči posel lahko nadaljuje. 2.1 Razvoj finteria Ine opreire Paralelno procrainit'anje se Je začelo razvijati pri reševanju prc^lemov pri operacijskih sistemih, ki so sledili razvoju naterialrte oprenre. Pozneje so takšne multiprogramske sisteme za paketno obdelavo dopolnili tako, da Je lahko več uporabnikov hkrati interaktivno delalo z računalnjkom preko terniinalov. Takšne sisteme imenujeiro operacijšVri siste.iii s časovnim prepletanjem (angl. "time sharing operating system"). Prvi, enoj^oslovni operacijski si s tend. so bili zelo primitivni In so naenki'at izvajali le en posel (uporabnikovo nalogo, an£;i. "single Job"). Tipična vhodna enota je bila čitaleo kartic in tipična izhodna enota Je bila vrstični tiökalnik. Obe napravi sta bili veliko počasnejši od procesorja. Zaradi čakanja na počasnejše naprave Je bil procesor veliko časa neizkoriščen. Poleg tega so bili prvi sistemi občutljivi na prograinerjeve napake, ker ni imel zaščitnih mehaniznmvi Z razvojen; hitrejših porcnllnišklh perifernih naprav so Izdelali operacijske sisteme za paketno obdelavo (angl. "batch processing"). Ka nanjših računalnikih .■;o večje število poslov posneli s počasnejših čitalcev kartic na-hitrejši KEgnetnl trak ali disk. Sistem je potem s teh hitrejših poicrjilniških enot zaporedno bral ' in izvajal posle, rezultate pa Je zapisoval na hitrejše pomnilniške enote. Ko Je bila Obdelava končana, so rezultate natisnili. Sistemi za paketno obdelavo so bili boljši od prejšnjih, so pa še vedno zaporedno izvajali posle, gezultati posaiKsnih poslov so bili dostopni, ko so bili izvedeni vsi posli. Zato so resultati krajših in daljših poslov bili dostopni ob istem času. Naslednjo izboljšavo operacijskih sistemov je omogočila uvedbä oziroma uporaba prekinitev, a katerimi so presegli sekvenčno naravo računalnika in dosegli delitev procesorjevoga časa med različne prosrame. Pripadajoče tehnike, ki podpirajo takšno paralelno Izvajanje programov Unt-nujemo "multiprof:r.-jmiranjo". Tu se je začel razvoj paralelnega programiranja. Kultiprot;ramiranje ^o uvedli 7.it'J, da bi bil procesor in vhodno ishodne enote čira bolj izkorlšcenl.. FY1 osnovnem 2.2 te'/.aner.l j-ivDfit j-ror'xaTr.'ikr! opre-rr« Možnost istočasnega izvajanja večjega števila programov na enem računalniku, ki so jo omogočili prvi multiprogramski sistemi, je želo zvečala zmogljivosti računalnikov, povečala pa se je zapletenost. Pri teh sistemih je namreč zelo pomembno, da se posamezni programi pri izvajanju' ne motijo in da potekajo na pravilen način. Programske napake so povzročile, da se Je paralelen!- program obnašal nepravilno in časovno odvisno. Ker so bile posledice napak različne od priinera do-primera, celo pri enakih vhodnih podatkih, jih Je bilo zelo težto odkriti. Zaradi omenjenih težav paralelnosti je bilo pomembno, da se uporabniku omogoči enostaven, zaporeden pria top sSo stroja..Operacijske sisteme so zgradili zato, da bi bili računalniški si.odi mli in postalo je dvomljivo ali rcGničiio omp^;očaJo uc'ir,kovlto in zrinesljivo delo raču^ilnlka, ftìstalo je Jiir.no, rta takšue òijséine prograiHi ' til mogoče Iz'Jclati brez' določenih konceptualriih ten:olj^;v, ki bi oro^očil.! boljše razuriMvanje. RaSur.alniaki znanstveniki,, ki set pri svojsin delu prav tako uporabljali računalnike, so ugotovili pOJTiembnost operacijskih sistcn-.ov ;in začeli delo na tem področju. 3 Konceptualni temelji cikli tO . ti , t? t3 . tt t5 prvi proces .lnona enako (ponovljivo) vsakič, ko bo pogtian z enakiFi podatki. Procesi, ki si delijo računalniške resurse ali pa delajo na skupnih nalogah .xorajo biti stnožni pravilne interakcije, ki Jo liKenujesro procesna konTunikacija ali procesna sinhronizacija. Taksne procese deliTO glede na tiiedsebojno razmerje do nekesi ' resursa na tekmovalne procese, ki tekiajjejo za neke stalne resurse (tračna enota, tiskalnik, spretrenljiv'ke itd.) in takšne, ki so v razmerju proizvajalca in potrošnika začasnih ali potrošnih resursov ' (sporočila, signali itd.), česi proizvajalci in potrošniki IziiBnujeJo sporočila, jih itnenujemo komunicirajoči procesi, če pa si izmenjujejo sinhronizacljske signale. Jih imenujemo sodelujoči procesi. Kritične sekcije Dijkstra Je ugotovil, da koinunlkaoljo ined procesi lahl® prevedemo na izvrScvanJe operacij na podatkih, ki so skupni večiBi procesorji. PoneT.buo je, da naenkrat le en proces izvaja določene operacije na nekem skupnem podatku, ker sicer lahko nastopijo nepredvidljive posledice. Vzrok je v tem, da nobede>i od prooesov ne ve, kakšne operacije izvajajo ostali procesi v isten času nad skupnimi podatki. Pripadajoče napake so časovno neodvisne in različne odvisno od tega, kako se procesi pri izvajanju prekrivajo. Nazoren primer je, ko si dva procesa delita navadno spremenljivko, ki je števce dosodkovi.. če se prekrije povečevanje števca dobimo:' Po dvojnem povečanju vrednosti smo iz n=3 dobili 0114 namesto n=5. Tiste dele procesov, ki vi'šijo operacije r^ skupnih spremani J i vkah, je Dijkstra iicenoval kritične sekcije. Potrebno Je zagotoviti, da bo san» en proces naenkrat izvajal kritično sekcijo; kar imenu jeitio problem vaajcT-nesa Izključevanja izvajanja kritične sekcije. Vzajemno izključevanje zagotoviitoj če proces sestavimo tako: neodvisni del vstopni protokol kritična sekcija iistopni protokol neodvisni del Vsak proces pred kritično sekcijo izvede nek vstopni "protokol. Ta bo dovolil nadaljevanje samo taki-at, kadar noben drug proces ne izvaja kritične sekcije. Ka koncu kritične sekcije proces Izvede izstopni protokol, ki omogoči, da v kritično sekcijo vstopijo drugi procesi. Najbolj znan Je Dekkerjev algoritem za zagotavljanje vzajemnega Izključevanja. Algoritem za dva procesa, ki. ^ predstavimo v višjem progranakem jeziku poteka tako:' program Dekker; var turn : integer; c1,c2: integer; procedure pi ; begin repeat c1:=0| Vjhlle c2=0 do if tu)'ii:2 then («prvi proces») («neodvisni del«) («vstopni protokol«) begin while turns? do; cl:=0 end; oriti; («kritlofia sekoljci«) turn: =2; C*lzstopril protokol«) c1:=1; .....................(»neodvisni delo) forever procedure p2\ bef^ln repeat while e 1-0 do If tum=1 then begin while turn:1 do (»drugi proces»J (»neodvisni delo) (»vstopni protokol») c3:=0 end; crltS; turn;=1; c2;=1; forever (»kritična sekcija») (»izstopni protokol«) (»neodvisni dola) (»glavni progratno) ' (»paralelno izvajanje p1 In p2») begin Cl:=1; tutT);=1; cobegln pi;p2 coend end. V programu smo uporabili paralelni stavek cobegin -coend, ki ga bomo podrobneje .opisali naslednjem poglavju. Vstop v kritično sekcijo proces p1 (,p2) naznani z nastavljanjem ol (c2) na 0. če p2 (pl) hkrati lEvaja vstopni protokol, spremenljivka turn odloča, kateri proces bo vstopil v kritično sekcijo. Algoritmi za vzajemno izključevanje več kot dveh procesov so precej zapleteni, zato so neprlKerni za praktično uporabo. Druga slabost takšnih algoritmov je v zaporednem testiranju vstopnefra pofjoja, kadar želi več procesov hkrati i?;vf3jnti isto kritično sekcijo. To Vidin» iz stavkii: jvhilo p0i;0j_(to'(« nič •). KeciLem ko en proces vstopi v kritično sekcijo, drugi proccsi zapravlJ:iJo računalnliiki ' č.ia a preverj:jnjem, ali jc sekciju prosttT (tinfi;!. "bir;;y wni tiiiß"). Se-iaforjt Dijkstra Je uvedel podatkovni tip sena for, ki je primeren za prenašanje sinhronlzacijsklh signalov (1963). Seiiafor lahko uporablnio tudi pri reševanju ostalih problemov paralelnega programiranja. Na priiner, z nJim enostavno rešin» problem vaaJetrnega Izključevanja. Nad aprernenljivko s tipa semafor sta definirani dve operaciji: walt(s)'. če 5>0 tedaj s:=s-1 sicer se izvajanje procesa, ki je klical wait{s) ustavi in proces se postavi v čakalno vrsto, signal (s): če je bil nek drugI proces P z of-iracljo waitCs) nad tem semaforjem ustavljen In postavljen v.vrsto ga zbudi in izvajaj, sicer s:=s+l Operaciji "wait" in "signal" morata biti implementirani kot primitivni operaciji, torej se nedeljivo izvajata. Ko nek proces izvaja semaforsko instrukcijo, počakajo vsi ostali procesi, ki v tem času tudi zahtevajo Izvajanje scmaforske instrukcije. Semaforje, ki lahko aavzatnejo poljubno pozitivno vrednost iicenujen» splošni semaforji, če dovolimo, da zavzamejo samo vrednosti O in 1, iinenujemo takšne semaforje binarne semaforje. Rešitev sinhronizacije dveh procesov s semaforji je preprosta: program synchronlsatioti; var s: semaphore; procedure pi; bej^n walt(sJ;. (»čakanje na sinhronizacijo s p1«J end; procedure begin signaKs); (»sprožanje sinhronizacijskega signala«) (amain programa) end; begin- cobcuiii (»paralelno iJ.vnjanje pl in p2») p1;p2 2 oi>ei-aciJo "signal" prooes preko semafor'ske sprersenljivke odda slrihro'-.lzacijski r.lr.:ial driigcnu procesu, ki oddani signal aprejns: z "wait" operacijo. V paralelnem sistemu progrnir^r ne irore predvideti relativne hitrosti • niinhranih procesov. t!e cnremo vedeti, če bo proces poslal signal preden gi bo drugi procesor pripravljen sprejeti. Senatorske operacije so definirane tako, da ni pKirnercbrjo v kakšnem vi'Stnem redu se S?.všiJajo. Proces, ki poslojia sprsjetl sinhronlzfieijski signal Se preden Je ta oddan, se postavi v čakalno vrsto in zakasni, dokler nek druK proce.9 ne bo oddal' ustreznega s j gnala, če se signali oddajajo hitreje, kot se sprejemajo, se enostavno shranijo v semaforski spretr:cnl jivki, dokler ne bodo uporabljeni. Zaradi ko::a2tativnosti seTaforskih operacij postane slnhroni'/aol ja procesov časovno neodvisna. Rešitev navadne sinhronizacije s senaforji je enostavna, drugi problemi pa lahko žahtovajo bolj zapletene rešitve. Slabost serraforjev je tudi v tem, da sé lahko sistem, zgrajen s sciMforji, podre. Če pozabiiro na eno san» serraforsko operacijo. iinplerr.entaoija In da prevajalnik preverja, da so pravila gled»; koncepta, zadovoljena. Uporabljeni koncept irora omogočati programerju predvideti -hitrost in velikost programa. Paralelni stavek Dljkstra Je uvedel zapis paralelnega stavka, ki določi, da se več sekvenčnih stavkov izvaja paralelno. Paralelni stavek se zaključi, ko se zaključijo vsi cckvsnčni stavki. Primer paralelnega stavka Je; var this, next: line; eobegin consume(this); input(next) coend Dljkstrin multi programirni sistem THE (1968) je uvedel večino konceptov r-a katerih temelji današnje razumevanje paralelnega prograrrlranja. Njepov sistem je bil hierarhično zgrajen is več prograirjskih plaati, ki so fizični stroj postopoira pretvarjali v prijaznejši abstraktni stroj, ki je lahko izvajal številne procese. Ti so si delili obsežen honwgen pomnilnik in številne virtualne naprave. Pri sistemih, pri katenn paralelni procesi uporabljajo iste resurse so začeli raziskovati tudi načine urejanja zahtev po zaseganju resursov In prenašanja sporočil, da se preprečijo smrtni objemi (angl. "deadlock"). To Je pojav, ko vsak izmed dveh ali več procesov zaseda nek resurs in čaka na resurs, ki ga zaseda drug proces. Mapačna rešitev tega problema povzroči neskončno čakanje procesov. Medtem ko stavek consume porablja vrstico this, stavek input sprejema naslednjo vrstico next. Paralelni stavek ima predvldijiv učinek samo v primeru, če posatnezni pripadajoči' stavki, ki predstavljajo, paralelne procese operirajo . nad različnimi spremeniJivkaml (v našem primeru this in next) , če več stavkov operira nad istinil spremenijivkarai, bo učinek paralelnega stavka časovno odvisten. Da bi preprečili časovno odvisne progratnskfi napakt: inora prevajalnik razpoznavati privatne"spremenljivke procesa, ki morajo biti nedostopne drugim procesom. Kritične sekcije in pogojne kritične sekcije Razvoj jezikov z elementi za paralelno programiranje čeprav Je bistveno, da so nekatere sprfjTsnlJivke dostopne sajrra enim procesom, je v primeru sodelovanja in komunikacije med procesi potrebno, da si procesi delijo nekatere spremenljivke. Okoli 1970. leta so raziskovalci začeli jezikovne zapise za opis novih konceptov. razvijati Koncept progranskega jezika mor'a predstavljati splošno Idejo, ki se pogosto uporablja. Pomen In pravila koncepta progrcimskefji Jezika morata, biti n-itarčno definirani. Pt'cdstavljen .wi-a biti s ki'atktn-____In Jedrnatim znpisom, ki o(?:of,ciča eii0;-5tavn0 apoxri.ivanjo ele.T.enl;ov koncoptn in njiliovo mod;-!obojno o'Ivi . PoiKcmbno je tucii, ü'.t Ju možiia vjrn--; .In t.;i Hoare in Brlnch Hansen sta leta 197^ predlagala zapis za. prirejanje deljene spremenljivke' kritičnim sekcijam, ki operirajo 2 njo. Za primer lahko definirana deljeno spremenljivko, ki jo uporabljamo kot uro: var clock: _shnrcđ Integer Procesi inkreir.entlrajo in čitajo to spremenljivko s' aledečlml sUvki: ftonltorji tick: region clock do clock: = (cIocif+1) mod nax readC*); region clock do x:=olock Deljena spremenljivka so lahko uporablja saEi» znotraj kritičnih sekcij (region), kar preverja prevajalnik. Kritične sekalje so tako implementirane, da Je zagotovljeno, da se posamezne sekcije izvajajo brez prepletanja, ena za'drugo. Hoare in Brinch ilansco sta postavila tudi koncept in zapis po;;ojne kritične sekcije. Izvajanje sekcije se odlaša, dokler deljena spremenljivka ne izpolni nekega pogoja. Kot primer ]ahko prikažemo izravnalnik za sporočila, Vi se sestoji iz vrstice "slot" in boolean vrednosti "Aill", ki kaže ali je vrstica polna: Dijkstra je predlagal, da v en programski modul zajaicemo vse operacije nad deljenicrd. podatkovni strukturami, narnesto da jih raztresen» po celotnem programu. S tem se poveča jasnost interakcij med procesi. Brindi Hansen je predlagal zapis jezika za ta koncept nanitorja (1973) Hoatre je c^isal monitorski koncept in podal primere (197t).. Za Ilustracijo vzemimo izravnalnik za sporočila z operacijami zapisovanja in čitanja, ki ga zpradlfn z monitorjem. jnonitor buffer; var slot: line; full: boolean; (•laonitorjeve spremenljivke») var buffer; shared record slot:line; full:boolean end procedure send(m; line); when not full do begin slot;=[r.; full:rtrue end; procedure recelve(var m; line); when full _do begin m;=3lot; fiillrsfalse end; C«proceduri monitorja*) V izravnalnik pišemo san», ko je prazen in čitamo samo, ko je poln: begin full:=false end; (etelo monltorja-inicializacija») send(ra); region buffer when not full do begin slot:sin; full:;true end reoelveodatkl ' prenesejo in procesa nadaljujeta izvajanje. I'a princip rer]dezv(xia-ja je izbran pri programskem Je^.iku Ada, za katerega so 1980 leta izdali standardni priročnik, Ada [iudi bogate Biožnosti za določanje in obvladovanje paralelnega izvajanja. Da dobir/» predstavo o glavnih idejah, bofoo v tea poglavju opisali nekatere irožnosti. Zararll jasnosti bomo ponekoil podali saT.o nekatere oblike stavkov. Za pojasnitev borao vr.rli prirKr oi.ejenega iaravnalnika za celoštevilčne podatke. procedure PRODUCEfiCOf-ßn-iER is —specifikacija procesa izravualnika task BOUNDEDBUl'FER Is entry APPEfJD(V: in IhTčTrER); —deklai-aeija procesnih entriß TAKEfV: out INTEGER); —vhodov s paranjetri end &0UNDEDDL'FFF:S; —konec specifikacije end TAKE; 0UTF1-R: = {0LrrPTR<-1) nad SIZE; end select —Sconec izbirnega stavka end loop; end f)OUfJDt:DEUFFER; — telo procesa, ki pise v izravnalriik task body PRODUCEfi is am: ItfftEEf!;-begin loop PRODUCE(ELEM}; APPENL1( F.LF>1) -, end loop; end PfiODUCEfi; —telo procesa, ki cita iz iiravr.alnilca task body COfJSUMER is EI.EK: irrrEGBR; begin loop TA KECKEM); C0hBUh2(ELEH)-end loop; end CONSUMER; —giavtil program begin null; end PRODUCERCONSUMER; —specifikacija procesa, ki pise v izravnalriik task PRODUCER; —specifikacija procesa, ki cita iz izravnalnika task COtßUWCR: —telo procesa izravnalnika task body BOUNDEDBUFfER is SIZE: constant:= B: array(0..SIZE) of IIJTEGER; INPTil,aJTPTR: IKTEGCr,, N: INTEGER; begin Nr=0; IHPTR:=Oj OUTPTR::0; —inicializaeija loop —omajenegn izravnalnika —izbirni stavek select when N <= SIZE => —pogoj (varovalo) accept APPEt®(V: in INTEGER) do —prejemni st. B(INPTR):rV; —zapisovanje v izravn. end APPEND; N:-ff*l; IMPrH:r(INnR+l) nod SIZo; or when N > 0 i> —pof^oj accept TAKfXV: out INTEGEfiJ do —pre.icmiii st. V;- B(Oirrm); —olt^iD.lđ clo;r..:'riLT iz.rvw. Prenos jiodatkov pri rendezvous-ju poteka preko parametrov in ne preko izravnalnika. Prenos podatkov med dvema asinhronima procesoma Cv našem priffieru PRODUCER in CONSUMER) zato izvedeno z uporabo dodatnega procesa CEOüNDEDBUFFER), v katerem programiraiw omejeni izravnalnik. Rešitev s pasivnim monitorjem, ki se izvaja samo ko je klican, tu nadomestimo s procesom. Procesi v Adi so programske enote, ki se izvajajo piiialelno (task). Sestavljeni so iz specifikacije procesa in telesa procesa. EVocesi se začnejo izvajati takoj po deklaraciji. Zato je v našem premeru glavni program lainko "null" {Ada uporablja "glavno proceduro" kot Pascal glavni prograir.). Komunikacija med procesi se izvaja na nadzorovan način preko procesnih vhodov (entry). V Adi Je Implementiran asimetričen rendezvous, pri katerem lahko ločino kličoči proces (pri nas sta to PRODUCER in CO^EU^ffiR) in klicani proces (BOUNDEDBUFFER). Bistvo asimetričnosti je v tem, da v točkah rendezvous-ja sairjo kličoči proces navoja klicani proces oziroma njegovo procesne vhode (APPEND, TAKE). Klicani proceii ne navaja, kdo ga kliče, temveò. izvede prejcmnl st.ivf-k (aoccpt) na svoje vhode (APPFMD, TAKE). Cgiejit» si obliko deklaracij iti stavköv. Procesni vhodi, so deklarirani v specifikaciji klicanega procesa: erjtry identifikator t[jaraitK;tri_vbodal ; Pri tem so lahko paransetri vhoda vhodni (in) ali izhodni (out). select iVheii poßoj i>J alternativa s prejeirniE stavkom or . [when pogoj alternativa s projertiilm stavkom V točki rendezvous-ja kličoei procesi navedejo inie vhoda klicanega procesa: [else stavki] end select J iiRe_vhDda [ ( de Ja n3ki_parame tri )) ; klicani proces pa navede prejemrsi stavek (accept): acce pt iiije_vhioda [pai •aiiiiiL r-i_vhoda] • Cdo stavki eriđ [identifikatorjih tollte tri čnost ornogoča, da procese rar.dellmo oa uporabniške Ckličoče) in servisne {klicane). Uporabniški procesi morajo poznati vhode servisnih procesov, ki jih kličejo. Servisnim procesom ni potrebno poznati uporabniških procesov. Frejemni stavek servisnega procesa nami'eč ne navaja irrena uporabnika. Zato lahko zgradimo knjižnice servisnih procesov, ki jih lahko uporabljajo vsi uporabniki. UporabniškiiE procesom zaradi njihove narave lahko rečemo tudi aktivni procesi, servisnim pa pasivni procesi. Ada inia na tem področju še dodatno prednost; ker ima klic vhoda enako sintakso i:ot klic procedure, Je lahko-klicana operaci.ia izvedena kot proces ali kot navadna sekvenčno procedura. Na primeru izravnalnika vidimo, da nora Irtietl proces možnost rendezvous-ja na različnih vhodih, pri tem pa ne pozna vrstnega reda ' klicanja posameznih vhodov. Ne moremo üiamrec vnaprej predvideti zaporedja pisanja v izravnalnik in čitanja Iz izravnalnika. Potrebujetno možnost nedeterralnistlčneaa prenosa podatkov. V Adi nam to Božj-jost nudi iztiirni stavek (select), id. omogoča alternativno izbiro med različnimi prejemnimi stavki. Problem predstavlja tudi omejena velikost izr-avtinlnika. če Je izravnalnik poln, ne more sprejeti novega elementa, če je prazen, ne more oddati elementa. Zato pred posamezno alternativo v izbirnctn stavku kot varovala postavimo poRoje (when). Takšen izbirni ütavek z varov.'ili in ' izbirami med .alterrjativnimi priijuiinimi stavki inn obliko: Ob izvajanju izbirnega stavka se najprej ovrednotijo vsi noffojl in tako določijo odprte alternative, če je klican nek prejemni stavek v odprtih alternativah, se reridezvous izvede, če ni odprte alternative ali ni klicanih prejemnih stavkov odprtih alternativ in obstaja stavek else, se izvedejo pripadajoči stavki. če obstajajo.òdprte alternative, noben pripadajoči prejemni stavek pa nI klican in ni stavka else, proces počaka na zahtevo po randezvous-Ju. če pa ni odprte alternative ne stavka else nastopi napaka; 2a raznovrstne probleme paralelnega programiranja mehanizem rendezvous-ja ■ nudi prim&wwjse rešitve -od (nehanizmov na osnovi vzajemnega iz ključev^ ja (kritične sekcije, semaforji, (tionitorji), ki so bolj prilagojeni reševanju določenih problemov, Rendezvous je primeren za implementacijo na enoprocesorskih pistemih, multiprocesorskih sistemih s skupnim pomnilnikom in ' distribuiranih nultiprocesorskih sistemih. Ugotovimo, da rešitve z uporabo rendezvcws-Ja ponavadi zahtevajo več procesov, kot pri uporabi drugih mejnanizmov. Procesi se zato pogosteje izmenjujejo, za kar se porabi določen Ü.3. Pri našem primeru proizvajalca in potrošnika smo tako namesto izravnalnika, J.mplementlranega s pasivnim monitorjem, pri uporabi rendezvous-ja vstavili servisni proces, ki vrši funkcijo izravnalnil^a. Pri uporabi, novejših procesorjev je čas preklopa med procesi tako hiter, da ni kritičen. 3.6 Zaščitni mehanizmi Videli smo, da monitor lahko definiramo kot abstraktni podatkovni tip. V monitorju so opisane podatkovne strukture Jn procedure, ki so edine dovoljene- operacije nad podatki, V procedurah Je zajeta tudi pravilna sinhronizacija ried procesi. Procesi kličejo procedure rbnitorja, pri- -tem pa nimajo vpliva in Jih tudi ne zanimii tianln izvaj.n-ij.^t operticlj, temveč Kifno učinek operacij na pixlatkovne predmete. Vidiniu, mraiitor deluje kol nekakšna zaščita podatkovnega predn.eta. Pri' uporabi izrnzov za opif. poti smo videli, kako laJiko definìrarno tudi dovoljeno zaporedje izvajanja operacij nad podatkovnini predcietl. posameznem rendevous-ju izvedle različne operacljc nad podatkovnim predine lom. Razvoj jezikovnih konccptov ^o je nadaljevnl v smeri abstrakcije pcdatl:ovr;lfi predmetov. DeflnlrsTO lahko splošni BiehrinlEŠin za zaščito. Zaščitni mehanizem podatkovnega predmeta Je proces, sestavljen iz skupine podatkov, ki jih ščiti in množice procedur za dostop do teh podatkov. Drugi procesi lahko Izvajajo operacije nad podatki 3 kJ-lcanjem procedvir procesa 7AŠčitnega mehaniznia preko njegovih procesnih vhodov. Pri uporabi zaščitnega mehanlzro lahko prevajalnik ugotavlja, ali procesi izvajajo rad podatkovno strukturo samo tl.^te operacije, ki jih mehanizem dovoljuje. Med izvajanjem progrania zaščitni ii;chanizein izvede, zakasni ali zavrne opftraolje, ki niso takoj Izvedljive saradl dinamike celotnega aistema. Vsak mehanizem za komunikacijo in sinhronizacijo med procesi, na primer conitor, izvaja ali zakasni zahtevane operacije. Ensk mcritorskl klic bo vedno sprožil izvajanje enake procedure. Zaščitni mehanizenj lahko izvaja tudi aktivno filtriranje vhodnih kllcov. Proces zaščitnega nehanizisa izvaja nek program in inia lahko tudi lastne spremenljivke za shranjevanje stanja sisteina, V različnih točkah pronrara sprejema klice ostalih procesov na procesnih vhodih. Pri sprejeiiu klicev pa zaščitni mehanizem lahko izvede različne operacije nad podatkovnim predmetov, odvisno od tega, v katerem delu programa je klic sprejet in v odvisnosti od stanja sistema. Pri uporabi jezika Ada lahko z elementi Jezika zgradimo zaščitni m.ehanizem nekega podatkovnega predmeta na popoln način, tako đa za ta namen ne potrebujeino kakšnega posebnega jezika. Kot primer lahko vzamen» implementacijo omejenega izravnalnika, ki sn» ga podali pri opisu rendezvous-ja. Formirali smo servisni proces C BOUNDEDBUFFER)-, v katerem smo programirali omejeni izravnalnik, ki ga uporabljamo 'za prenos podatkov med dvema asinhrotüma procesoma. Ta servisni proces je hkrati zaščitni mehanizem omejenega Izravnalnika, Program procesa je neskončrsa zanka, v kateri se izvaja izbirni stavek {select). Znotraj izbirnega stavka se. lahko izvedeta dva prejetma stavka (APPEND, T/IKE) z rendezvous-jem. Ta^prejemna stavka sta procesna vhoda. Pri rendezvous-ju na nekem procesnem vhodu ustreznj prcJeirjjl stavek izvede določeno operacijo nad onejenlm i^ravn^ilnikom. To je edini način dostopa clruclh procesov do izravnalnika, če bi bilo potrebno, bi '.motr;>j secvisncF.a proc.c;--a r.npisnli emk prcjcmtil f.tavek na različnih niestlh prof^rarr.-i, pri čemer bi .'jo ob 3 Zaključek Paralelno profiramlranje uvedemo zato, da enostavneje in hitreje rešimo neko nalogo, ki ima inožnost paralelnega izvajanja In da zvečamo Izkoriščenost slsterua. če paralelni procesi med sabo sodelujejo, naratno zacotoviti pravilen način interakcije ised procesi. Uporabinra lahko več ustreznih primi tlvov, kot so kritične sekcije, semaforji, monitorji., rendezvous-ji itd. Več jezikov vsebuje Jezikovna konstrukte za deklariranje procesov in meoprocesno komunikacijo in sinhronizacijo z opisanimi primitivi. Večina taksnih jezikov odraza stanje materialne opreme v času razvoja in podpira primitive (semaforji, kritične sekcije, pogojne kritične sokolje, jBonltorjl), primerne za implementacijo na enoproeesorskih sistemih ali večprocesorskih sistemih s skupnim pomnilniko-Ti, Takšl Jeziki so na primer Concurrent Pascal in Modula. Pri distribuiranih večprocesorskih sistemih, pri katerih so posarticzni procesorji povezani preko vhodno-izhodnih .Unij, pa je nastal problem implecentacije teh primi ti vov. \l novejšem Jeziku ftda so komunikacijo in sinhronizacijo med procesi povezali v mehanizmu rendezvous-ja, lei ga lahko enostavno implementiramo tudi v distribuiranih sistemih. Uporaba višjih programskih jezikov poenostavi In skrajša čas razvoja programov. Pri tem nastopi problem učinkovitosti prevedene kode. Večina današnjih arhitektur ne podpira učinkovito abstraktne jezike v primerjavi s strojno kodo. Pri programih, ki morajo delati v realnem času sn» zato soočeni z izbiro med učinkovitostjo, ceno in zanesljivostjo. Zato je prisoten trend razvijanja računalniških arhitektur, ki direktno podpirajo koncepte programskih jezikov. V procesorskih eictr^Htih se z materialno opremo oziroiia itiikroprogrami implementirajo specifične funkcije Jezikov za paralelno izvajanje procesov-, preklapanje procesorja med procesi, medprocesna komunikacija in sinhronizacija in podobne. S tem se občutno zveča hitrost izvajanja teh funkcij. Takšne funkcije ima na primer VAX procesor. Po drugi strani razvijajo sisteme z več procesorji, pri katerih posamezni procesi tečejo na lastnih procesorjih, s čem.er se zveča hitrost izvajanja paralelnih programov. Takšno izvajanje na primer podpira arhitektura sistema ÌAPX JJ32. Lahko povzamemo, da so nam danes na razpolaf;o Jeziki z jezikovnimi elenienti, primernimi za paralelno prof^raiiil ranje, r,izvija jo pa se arhitekture, ki poflfiirajo učinkovito implciiio[ilncljq jezikov sistemih r. več procesorskimi clc!i;cntt. Pri obravnavanju računalniških jezikov šn» v članku upoštevali 1 Imperativne jezike. PrograrJ. v funkoicmalnih ■Jezikih vsebujejo visoko stopnjo ' inherentne^, paralelnoali, načine autOBiiLakefja izkoc-iščarija In učinkovite icipleirentaeije te paraleln03ti na večprocosofskih sistemih pa so raziskujejo. Literatura /1/ M. Ben-Ari, "Irlnclplés of Concurrent Profraißning"■ ■ Prentice/HaU International, London, 1982 /2/ R.C. Holt, C.S. Grahaiü, E.D. t^r.owska, K.A. Scott, . "Structured Concurrent Progranftlns with 0;>sratlng Systems Applications", Addison-!-,'eslcy, fteadine; Mass., 197'B ty P. Hrinch Rinsen, "A Keynote Address on Concurrent Proprarrjiiing", IEEE Computer, tey 1979, pp. 50-56 /'1/ D.A. Anderson, "Operating; Systems", ItEE Ccwiputer, June 1901, PP- 69-8? /5/ S.J. Young, "Peal Tìirc LanjTuages: Design and Develos'incnt", J-hele su tiplovl elementi od r , a stapol aa Imeinovani atributima Is R . Slijeđeni lubl-Sajenu notaciju u teeilji basa podataka, je-dnoliSan skup 1a) piSemo kao A , uniju skupova. ZUY, kao ZIC, a knmplement skupa Z u odnosu na R , HSZ, kao X • 2. T-2avisnostl 0 ovoj sekciji karakteriziramo Ol-zavlanostl, Pridružimo svakom AeR , ealm , 1 akup d' apstraktnih simbola. Skup D^ zovemo aps- SM. traktna domena. Pretpostavljamo, D'^^n sa A^B. Definicija Neke Je D» u K*. . TD-element je . , A€R ^ funkcija v:R-»D sa svojstvom vCA)cD^VA.cR T' defininijf^ vidimo da Je TT)-element aiialop;on tipla. tleka Je ' CD Tj^tv^CA],) v(A2)..v^(Aj,), i=l,..,n+l5 f-dje Jc R=-(Aj^.Ag,.. , a v^^ Je TD-elc- ment. Definicija T-;-.avjsnosf Je i:TU7. oblika t: (rj^,.. t Je ime T-zavisnosti, hipoteke, a Je zaklJuSak. Identifikacijom TD-clementa v^ i feđa r^, i=l,..,n+l (1) pišemo u obliku (2) i=l,..,n+l . . T-?.avlsnost ^ ; (r^,.. predstavljamo tabelom čiji cu redovi ' * ® ci su iinenoTfiai atributima \z R . Posljednji red Je zaključni TD-element. Neka Je T-zavianost nad R. .Uvcdimo skupove ' J) = fA c E/ rj^CA)=rjCA)Ì , i,J=l,..,n+l . Uočimo da Je , ,i) Vi, J e {l,,. ,Ti+li, te Victl...,n+li . Definicija Neka Je ^: (r^, . . T-zavisnost nad R . Kažemo da rclaciJa (ri,r) zadovoljava t , ili da t vrijedi u Cti,r), ako i saiDO ako (5) Vti,..>t^er[Vi,Jc fl,..,nlE3 (i U formuli C3), Eg ^ isnači Jednako- st''tiplova t^ i tj na skupu atributa'S^Ci,J). Iskaaana definicija kaže da r zadovoljava TD-zavisnost (''ii • • »^n^'^'^n+l i samo ako vrijedi; kad god su liipoteze od t (poslije proizvoljnog preimenovanja) u r , onda Je i zaključak od t (poslije ode^ovara-JiićeR proširenja ovog preimenovanja) također u r . .Skolemova standardna forma za T-xavisnòsti U ovoj sekciji reprezentiramo T-zavisnost u standardnoj formi. U sfkctji 2, smo rekli da T-r.avisnoct t; (r^ ,., vrijedi-u rela- ciji r gko inamo oko vrijedi (J) . Ako sa A Kr, f. jiCt. ,t.) or,nočimo konjunk-i,J=l 1 J üiju formula E^ ^ po Rvim parovi- ma. i.Je f l,.,,fsi /foriiU)].'! (3) poprimi oblik r n Ako, interpretirajući tipl-varijable na r , (4) postane istinita propozicija, onda kažemo da ('f) vrijedi u r , odnosno da Je r model aa C») O/naSavaJući sa V Ej, tt đisjunk- ciju formula Eg ^ ^^^^ P^^o'^i"^®' ifj^fl,..!«] 1 te etandardieacijom formule (t) nalazimo Skolemovu standardnu formu za T-zavisnost. t ; Dalje, negirajući (4) , te stadardizacijom dobivamo standardnu formu za ..«t : E("t): E 4. Točnost fonaalnoß BÌstema za T-zavisnosti U ovoj sekciji, dokazujemo točnost formalnog . sistema za T-zavisaosti predloženog u [12J . Dokazi se baziraju na rješavan^ju implikacionih problema za pravila formalnog sistema. -r' Točnost formalnog sistema se karakterizira preko logičke konzetevence. Definicija Neka Je C skup zavisnosti za re-lacionu šeau R , Neka Je c pojedinačna ■ srA^i snoat. Kažemo da Je .c logička .konzekvenca od G , ili da C logički implicira c , u ' oznaci , ako i samo ako svaki primjer (relacija) od R koji zadovoljava C također zadovoljava i c . Kažemo, dalje, da primjer r od E zadovoljava skup zavisnosti C za R ako i sojno ako r zadovoljava svaku zavisnost iz C . . ' Formalni aistem teorije zavisnosti se sastoji od pravila (aksioma) koja oraogpićaju izvo'denje novih zovienoflti Iz andanih zftvißnoeti, Dnfinicjja Wokn Je formalni,a ist em, C i C kao u prošloj dcfinlciji. Kaf.emo da C dokazuje C oko i samo rsko je nio^,iićc upotroborn nknioma is P^ na zavisnosti i 7, C izvor: t i 62 zavisnost c . Pofeazivost c iz C u fomal-nom sistemu Fjj oznaćovat ćemo sa Ct^o . Slijedi definicija toČnoafci fomialnoi^ ulatcma Definicija Za formalni cistom Pj^ IcnSesno da je točan ako i snmo ako za "bilo koji nkup zavisnosti C i aa bilo koju pojedinnćnu zavisnost C -vrijedi Cl—c ^ . '» t Formalni nistcra an T-aavionißti, u ornaci F^.p, ce sastoji 0(1 slijedećih pravila: ■ i-i-l-.i.uìO äfida ha dokrtz točnosti navedenih pravila. Dokaz za TDl: Trebamo dokoaatl - t'j (g(r^),.. Fidje ß ima svojstva (a) i (i)) u TDl . Standardizacijom t^ (-i) dobivamo skup ra6e-nica S ! . ____S____■ TDl! t;C(T . Stablo dokaza je dano na slici 1. Dùkaa za TD2; Trebamo dokazati Standardizacijom t a. «t* nalazimo skup rečenica S: • _______§_______ (ri-I) Cn+5) Koz, po nz a.^t. (1) Rez. (1) redom sa reSenicama ia (V) t I " /Cit.-) Je da pokaScmo da vrijedi (5)j A Tvg (j^+j^ jjCf Cn^,.. / RcČenica (3) 30 ekvivalentna r>a (V) VA V'j [ J)CA) ,.., a^) . Sadfi pokazujemo dn .je logička kùnzekvoncft od pravila (B) tj. rečenica (n+4) i (n+5) . Nebiran j r;ni rečenice ('0 dobivamo Standardizacijom iz «.(V) nalnzinio; (6*) )) -o * " "o Sodo naiatavljanio rezoluciju ; Ej^(f(B^,..,aj^),a^)] . Sada ćemo pokazati da (5*) slijedi iz pravila (0) tj. rečenica (n+'t) i (n+5), te reSenica (5) i (o+l)- Trebamo pokazati da je skup S= {,(5), (n+'0, (n+5), C?), (n+l)i kontradiktoran. /v (5): (b) «Ej^ o Dokaz kontradiktornoRti skupa S" je kao Sto slijedi: (a) (n+'0 (n+5) Definicija skupa (8) S^,(n+l,f(A^)KA^)l • Iz (3) (lo) Ej^ ^^f^i'-'i^n^'^fCA (12) Ej^ o (7) Definicija skupa ■(9) S^Cf(A^),o)(A^) Iz (n+1) (11) E^ (ftj.^^ ^a^j) tranz. za E^ Dokazali smo da vrijedi . Slijedi kompletiranje dokaza. (4) Pravilo unije (n+2) Rez. (n+2) redom aa reEenicama iz (15) po uz C SI. ^ " Prelazimo na doka/, pravila TD? .t,1. dokazu,-Jetno Staiidardizaol.lom fonimi e tA nalazimo skiip :Ì3 vrijedi: t: (r-^i • • rečenica .S:. (n.l) ^ A Cn.2) Wa osnovi zadanih zavisnosti t it'., odnosno na omovi sivojatava prealiknvan,ia p , imamo dva pravila: i Pl: , S^;(n+l,.1)cS^.(n+l,d) , d=l,..,n . 7z- pravila Fl nalazimo rečenicu: (n.3) ^ Iz pravila P2 dobivamo reSenicu; StaMo doka'?,a kontradiktomosti .sknpa . s'=SU[(n+3), (nH4)J, dano je na slici 5. (n+1) (n+3) Rez. po ^s^'Citj) [Cl), (n)l Rez. (1*) redom sa reSenicama (l),..,(n), po uz (n+2) Rez. po Eg^.f^^^L.d) ' ''«n^-^Vl M.1 kraju ove sekcije , dokazujemo pravilo t.rnnzitivnosti : Tf,., ; ^ ^ = C . .. . ; t^: f r^ ,. ■. r^ Transformiramo t^A t2Ai«'t u standardnu formu te dobi.vntno stcup rpčenica S : 66 1,3=1 T;, 1 1J «= I. Cn Cp (n') SJcup S dopundu.lema pravilom: no Jednaki kad god su definirani. Dokaz je dan P: S. (i,J) i a. Ci,J) Bu popar- na slici , kao Sto sli.ledi: 1 2 Is pravila P 1 rečenlcc (l") dotivnsno n-l (3") V ®s fi n-1 . / J-i «J n-1 [(l),,.,fn-l)] Rez. (5") redom sa rečenicama (l),..,Cn-l) C'^") . A^ Eg^ ' • •j ^ ^^ pravila Fi rečenice ) naltiaimo: (5") A r jv(f(a,,..,a„ , a iz pravila P i rečenice (1 ) doliivano: n-1 •O'i^ Uzoznake w^^Sj, -., (a^^,.. iz (5") i (6") i)J-1 tp po pravilu unijo slijedi: n (7") A Ep, •• ,w.) Dalje, nastavljamo dokaz: f(l'),..,(n')] Rez. (7") redom sa reSenlcsras Iz pravila P- imamo (n+1 ,k)=Sj.(n-il,k), k=l,..,n-l , pa is (8") dobivamo: n-1 (9") Konačno, (9") C2") Rez. po Eg^^^^j^jj uz- SI. 5. Zskljdčftk U. ovom radu, razmatrali smo T-z.ayisnostl u relaciouim baspjno podataka. Rješavajući impli-kacione probleme, za pravila formalnog sistema predlo£enOf^'u[12] dokaaali Rmo točnost navedenog formalnoij. sistema. Koo i u ranijim rodovima, koji se odjQor,e na funkcionalne, viSeanačne 1 podskup znvisnoati, i ovdje, metod rjcŠHva-nja se bazira na primjoal rczolucijskih procedura dokazivanja. Navedenim radovima, pokazali fimoi BOf^ućnOđt tretiranja iEplikficionog problema, zft skoro sve najvažnije aavisnosti u rola-eiOTiin bazama podotaka, u okviru jedinatvonoc; konooptiialrioo; aparata koji daje teorija meha-niSkog dokozivanja»teorema. Kuda dalje? Sintetizirajući formule koje. reprezentiraju sporaemite zavisnosti i pravila koja àmo upotrebljavali u proširenju skupa S, pravila koja karakteriziraju pojedine zavisnosti, možemo dobiti dednktivnu bazu podataka koja bi moc;]» prodstftvljati podršku u autcma-tizaciji dizajna relacionih. r,ema, kao Sto oe razmatra u 16]- Database Theory, II. Gallairs, J. Minker, and Nicolas, Eds, Plenum PressNew York, 1981., lol-llit, 9. Kendelzon, A.O.; On axlomatiRinf; multivalued dependencies in relation«! databases. J. ACn 26.1 (Jan. -19?9), 57-''^. 10. Paredaons, J., end Jannsens, D,: Decompo-Bitions of relations: A coiiipr^hensive approach. In Advances in Database Theory, H. Galloirc, J. Minker, and J.M. Nicolas, Eds. Plenura Press, New York, 1981. .lol-ll'l-. 11. Sclorff, E. A complete axiomatizations of -full join dependencies. J, ACM 29.2(Apr. 1982), 575-595. . 12. Sadri, F., and Ullman, J.D.: Template Dependfinoios; A large CIrss of Dependencies in Relational Databases and its Complete Axiomatization. J. ACtl 29, 2(Apr. 1982), 565-575. 15. Ullman, J. D.: Prineiplee of database' Systemfli Computer Scienco Press, Potomac, Hd.. 1930. Literatura 1. Aho, A, v., Beeri, C., Ullman, J.D.: The theory of joins in relational databases, ACM Trans, Database, Syst. 4,5 (Sept. 1979), 297-51'V. 2. ArniHtronE!, W.U., Delobel, G.; DccompoKitio- ns and functional dependencies in relations. ACM Trans. Database Sy:3t. (Dec. l98o), 4o4-45o. ?-.. Beeri, C., Vardi, M.Y.s A proof procedure for data dependencies. J. ACM 51,'» Oct. 1984), 718-7't-l. ' " ' 4.Chan3,C,L., Lea, R.C.T;: Symbolic Logic and Mechanical Theorem Proving, Corapt, Sci, Apll. Math. Academic Press, 1973. 5. Fa<5in, R. Horn clauses and databese depen- dencies. J, ACM 29.^(0ct. 1982),. 952985. 6. Gallaire, H., Minker, J,, Nicolas, J.M.: Advances in Data Base Theory, vol.1, " . Plenum Press, New York, 1981. ?. Haier, D., Mendelzon, A.O. and Sa(^iv, Y.: Testinf^ implications of. data dependencies ACM Trans. Database Syst". 4.4(Dcc, 1979) 445-')69. 8. Maier, D., Mendel?:on, A.O., Sndri, F.,, nnd Ullman, J. D,: Adequacy of decompositions of relational dntahnneo. In Advances in Od Sappora do Tokia nazaj v LJubljano Anton P. ielesnikar Xrl no nlchl kuKio no mine -yorl tBuauklken (Kobayashl Issa) Mravljične s-teaa se spuiia z daljnjih vrhov oblakov 1. Uvod Pred nekako dcuätlml leti, ko Je postala nesposobnost £e premisa In organizacija ansstveno-raaiskovalnega dqla, sem lasno obiutll potrebo, da bi se odpravil na Japonsko. KJen gospodarski napredek kot posledica raslskovalnorazvojne in tehnološke sposobnosti se mi Je zdel vreden posebne pozornosti Od kje in zakaj so se Japonci zavihteli na tehnoloikl vrh? KakSno Je bilo in ie vedno Je ozadje nenehnega vzpenjanja, ki vznemirja sklerotiäno zadržano Evropo in kapi' talno vladajoie ZDA? Na Japonskem sen imel enega samega znanca še iz časov moje dejavnosti v Generalni skupičinl IFTP konec Šestdesetih in v za£etku sedemdesetih let: profesorja Eiichija Gotoja s tokijske univerze; ial sam v oseisdese-tih letih na to dobro in prijateljsko znanctvo skorajda pohabil. Prof. E. Goto Je bil vendar podpredsednik IFIPa v äasu kongresa IFIP v LJubljani leta 1971. Iz te moje pozabljivosti se Je kasneje izcinilla kar občutna organizacijska škoda. Se v poletju igSB in morda še prej so me začeli prijatelji vzpodbujati nekako takole: "Odpravite se vendar na Japonsko in naveilte stike z Japonskimi univerzami in inštituti pa tudi^ s tistiitil JaponEKlmi podjetji, ki bi bila primerna za sodelovanje a nami.' Tako je bila oblikovana ekspedlclJska skupina in v sredini septembra sprejeta, dokončna odločitev, da se na Japonsko odpravimo 1. novembra 1985 in da nekako v dobrem tednu opravimo čimveč tega, kar Je bilo a načrtom določeno. Ob tem se Je pojavila tudi zahteva, da tnoraia za obisk na Hokkaido univerzi v Sapporu prlptavlti "protokolarno" predavanje, Tako so se dejanske organizacijska in moje strokovne priprave za razgledovanje in obiskovanje na Japonskem lahko začele. 2. Priprava na zahtevno pot Inazuma nI eatoranp hito no totosa yo o naiteta prc-bl bjna-tlke laboratorija medseboj organsko povezane. To povezanost ■ bom Opisal na. osnovi nekaterih razlskovaltilh dosežkov oziroma razvojnih produktov tega laboratorija, ki so bili predani v proizvodnjo raznovrstni japonski industriji. Prof. Ellchl Goto vodi tudi laboratorij sa računalniško znanosti na tokijski univerzi; problematiki obeh njegovih laboratorijev sta prepleteni in soodvisni. V obeh Gotovih laboratorijih se raziskuje vrhunska nikroelektronska In raćunalnlika tehnologija, ki Je neposredno prednset novih rakuna In 1 £k 1 h generacij {prof.. Goto poudarja, da Je vsaka nova generacija samo /enostavno/ zadnja generacija, kar je v bistvu v nasprotju b.pojmovanjem prihodnje /zlasti pete/ genoraclje, ki Je ne priznava). V preteklih 10 letih je laboratorij razvil litografski, sistem z elektronskim curkom, s katerim je moč realizirati 0,l-oikronsko tehnologijo, Elektronsko leäje te naprave so preračunavali več let in rešitev poljskih enačb Je lahko bila najdena iele s pomočjo močnega iis-povskega stroja. Pokazali so polinom ležja v simbolni obliki z dolžino približno osemdesetih strani (listing) in takšen polinom je bil lahko izpeljan samo z dovolj zmogljivim strojem za J^zlk Lisp. Litografski sistem ima naslednje zmogljivosti! -- proizvodnja mask J 10 ravnin na uro; proizvodnja mrežic (retiklov); 8 do 13 ravnin na uro; -- neposredna pisanje: m rezin na uro; -- natančnost obsega vzorca: ß,l mikrona; — natančnost prepletanja (stitching): 0,1 mikrona; -- medpIa»tria natančnost; 0, iE mikrona; -- plastna (overlay) natančnoct: 0,15 mikrona; ■ — vzorčna dodelitev! v 0,aB-mikrDnekih segmentih. Ta naprava je bistveno prispevala k razvoju 2S6kb dlnaoifinih RAMpv in k fil2kb ROHov, uporablja pa se tudi pri razvoju tehnologije največjih gostot. Naprava se danes proizvaja serij-eI lečja. Za ogled laboratorijske Tabela 1 Ime CDR Logika Celični Cashe ' Mlkro- stroja kodiranje pomniInik pomniInlk cikel . CADR 2 bita TTL 16 H nima 180 ns Dolphin 9 bitov TTL 16 M nima 200 ns Dorado 8 bitov ECL 16 M 120 ns 60 ns 3600 2 bita TTL 64 M 200 ns- . 200 ns ELIS il i ma TTL 15 M nima 180 ns EVLIS nima TTL 64 k nima 100 ns ALPS2 n Ima TTL .500 k nima 300 ns Kobe nima TTL 64 k nima 300 ns FLATS 2 bita ECL . 32 H B0 ns S0 ns proizvodnje Jocephcoiiovlh epojev jti ial zmnai-kalo časa. Gaj se Je ura pomaknila io v poano sobotno popoldne. Za konoc snio se s sodelavci laboratorija tudi «likali in dObila ova spooln-Eka posnetka. A B ociacija v povozsvl s oblBkDDi v RIKENu Ichiban nI Kagashi wo taosu nouakl kana (Horikauo Kjroroku) Kot prvo Ja podrl« EtraSllo josencka nevihta Pri ogledu laboratorija v RIKENu je ostalo odprtih ve£ vprašanj, ki zadevajo Japonsko/clo-vensko in b1ovansko/Japonsko projekcijo. če primerjamo, kaj so naredili podobni Instituti pri nae pri prlbliino enaki kadrovski In razi-skovalnl strukturi In knj BO fdiitirall v ilršo reprodukcijo .v določenen) razdobju,. J^ vredno ifikati odejovoce. Motivacija japonskih razlako-valcov Je posledica vlEokooposobnlh kadrov, ki E« utKiaelJuje n težnjo, da je potrebno prisvajati najboljše na svatu. Imeti najboljše, naj-lirioglJlvtiJie, najhltrejào je osnovni Imperativ, ki temelji seveda na viBokeu Intelektuali raziskovalnih In vodilnih kadrov. Izgleda, kot da Je pri nas necposobno^tna kadrovska selekcija izniaila raziskovalno sposobnost In intelek-tualiseisi, ki Bta osnovna faktorja raziskovalnega in Elcerinjega napredka določena populacija. Pri tom nam Jo ostala kot oedatlv le inteligenca (nelntelektualIzem,' pfločenost, nesposobno-Btna prilagodljivost), ki Js znoina I« ie ne-sposobnoBtnega pr 11 acja Jan Ja in drsenja v neper-Bpektivni razkroj. Taksna naravnanost domačih znanstvenih Institucij Je še pose be J""^! dna v njihovih domala mrtvlčnlh In neustrezno sesta-vl.jenih managementlh-In seveda tudi v razlsko-valcih, ki za svojo funkcijo v medna rodnem snanstvenom prostoru niso več usposobljeni. Kako Je sicer mogoča, da Je skupina 6 ljudi v RIKENu v desetih letih prispevala več v svetovni tehnološki prostor kot nai 600 članski Institut, ki bi nazadnje lahko raziskoval tudi za potrebe razvitega sveta (pri deklarirani sposobnosti znanstvenega menažmenta in raziskovalcev)? S. Kamakura, sveti kraj Japoncev Hana chiru ya garan no hltsugi otoshl yuku (Boncho) Cvetje odpada -zapira vrata hrama in odhaja V nedeljo 10. H. amo obiskali sveti kraj v bli£inl Tokia z itnanoiii Kamakura. Tu se nahaja mnoSica Budhovih templjev. Izlet je hll zanimiv zaradi opazovanja in raziskovanja Japonske mentalitete In običajev In njihove projekclJe'na naie navade. Povzpeli smo se tuđi na sveto goro (kot je naša Šmarna gora) In se vrnili na pacifiško obalo. Tako smo si nabrali še nekaj potrebne kondicije za obiske v ponedeljek In torek. Japonska verska zbrano.st Je temeljita In kaže na"sposobnost micelne koncentracije v valujoči mnoilcl In okoliškem hrupu. Značilna jo tudi japonska dekoncentracija, ki se kaže v zaspanosti ob vsaki, aa to primerni priloinostl. Japonec spi oziroma dremlja skorajda v vt-akom EGdečera poloiaju, čo so od njega na pričakuje delovni učinek. Tokijska podzemska železnica Je slika spečih Japoncev. Mati, ki pripcJJe otroka v trgovino z igračami, v trenutku zaklnka ria stolčku. Odkrito aehajočl Japonci na tokijskih ulicah Eo obiäajnn pojav. Japonska zaspanost Jb kot počitek pred velikimi napori, ki co za preživetje japonske populacije nujni. Na tokijakih ulicah je mogoče razumevati občutje Japonske ogroionosti. To Jb ogroicnost zaradi prenaseljenosti, ki pogojuje občutke revno-' sti (nBzadostnoctl iivljeneklh virov), katastrof alnoctl (potresov, tajfunov, povodnjl) in nerazvitosti (tudi najsodobnejša tehnologija in vrhunska delovna usposobljenost na zagotavljata več golega preživetja). Delovna sposobnost Je za Japonca Imperativ, Iz katerega izvira tudi Izreden smisel In pripravljenost za »edsebojno. pomoč In za skupinske podvige. Japonska zavest Je prepojena o prepričanjem, da sposobnost ni sano nujnost, marveč mora biti in ostati osnovna potreba. Zadovoljevanje te potrebe- je pripomoček, ki zagotavlja preilvetje, za daljše razdobje. Japonska ustrel1Jivost in pripravljenost za pomoč se kaže tudi v stikih s tujci. Ta pripravljenost jo tem večjo, na čin vlfijom poloiaju je Japonec. Ker je japonska upravljavska hierarhija izrazito sposobnostna (čim višji položaj tem večja sposo Ijnoct ), je komunikacija najlažja In najustreznejša pri vrhu. t j e Api.'r I <; ra 1 f.'d Procf'ssors Ozti.ika Moijpi 10 ntiit'iufi ! r '.'"!' ■; ' ■ - 1 Ì ? ^ - 1 " ■ s ii s i;-- ! J ■ , £ - ' t t i - - : - = - - - r r -. C(>n;i Pap.ilel Up.h Povezanost Pormi i 1 ri ! k S880I1D 4 do X2 skupin rckonflgu- nI podatkov s po 8 AL!-; rahlltia - f r r -s-T n .- Pfoctisor rti podatkov A.I 1 i ani Conipulpr Sys t t'ifjs l'.XJ 8 S7 O Ü ü ü do 20 vodi io Ploljuliii do 64 MiilfiKüV ini . CMOS^ (»Ol Jo vr;it I Aìn(> I e k i t.'otiipu ter I----------- Ho t t , lici-aTiPk A Kowina ti ays I «Ml! 14 S 7 5ÜU0 16 do aiü il) već h)pi:rkocka lokalni", do iC-bllni, 256 Mi'-lohov È0a«G>B02'87 GuU'rf ly S'4(lOÜÜ in Vf;o 1 do 256 prrkloiinl sisi Oli» deljeni ir lokalni i 6-bi tni, MC ü« .«00 IJüriül cor HEP 1 ilmll (lo tSmil 7,;i Ir.vri. tiiodul l do IC i zvrs i 1 II i 11 TDOflU) ov dvosKioriia tiireJft globalni 64-t)i ini , ECL Kl.KSl Kncroro Compii ter flpxihie c;o!n^.ii t r r G400 Mil.t t i (nix rirx-33 S600000 $ I I 4 O O O tisoooo I n veÄ iHi VLSI Saxpy Compu ter Sa.Kpy-lM s 2 mil 32 paralelno s i s toli ena' del jeni, do 513 kzlogov 32-hitiU , po naroČilu Sequent Computer Syslem Balance 8000 S60000 do 12 vodi lo global ni, do 28 Mzlogov 32-bUni , NS 32032 Sequoia Systems Sequo i a System S2000ÜO do 64 vodilo globalni , do 252 Malogov IG-biIni. MC G8010 Thi nk i ng Mach Ines = t: = ^ = = S ft £ =: Connection nl podat-Machine kov ss.-. = = = = = = = = 64000 do 1000000 hi perkocka glob,") 1 nl , 500 Mzlu^ov = = 1 T, r = v s r 1-bitnj. po naročilu Danes torej äe nI Xovalni standardi do trino ùspeinl pomnilniki v voz naključna (sgolj bi lahko preživel nljsKem tehnoloä podjetja (Cray) litt-.teroö a deljeni Jasno, kateri paralelno obde-bodo prelivali. Verjetno bo-paralelni siBtenl n iokaliiini liiiih. Hiperkocka Jo preveS kombinatoma) arhitektura, da a (rafiVlta Je bila n;i kallfor-ktiiii Institutu CIT). Nokatora pr 1 jirov 1 Ja jo mu 111 p rcicecorskn tn gLob;)lnlm nIctemukltn poninll- nlkom. Tu naj bi priili do lara2a programi e sinbronizaciJsklai osnovnimi funkcijami (v bistvu Je to Etar«Jii sistem z znanl.nl pomanj-kljlvostol). Za različne aplikacije pa bodo kot vssloj najbolj primerni posebni paralelni sistemi. faraleini sistemi bodo morali biti bolj nataniiio prilagojeni problemom realnega sveta. Kot doslej ne bo mogoče sgraditi paralelnega slutema, Stl bi bil prlmejren za vakršnjo uporabo oairoma aa veaktrinjo trilžtc. Paralelno .procesiranje: 'rBcnlfnoEt ali fantazija? Paralelno procesiranje je kot zaklad, ki ja «e globoko zakopan v nail podzavesti. Ta zaklad obljublja mof.fie režltve tletlh problEinov, ki jih v. dannlnjo računalnlilko tehnologijo nI «lo-go6e razrešiti, obljublja pa tudi reiovalno hitrost, ki JQ za nekaj veillkostnlh razredov vetja od danes annnth^reievalnih hitrosti.. KomercialIsaclja aamisli paralelnega procesiranja se Je še aaiela. Tako eo npr. podjetja Intol, Rnetek Computer in NCube uresničila tki», koncept s CITjevo hlporkocko (gloj prcji-njo novico). Podjetje Bolt, Boranok t Newman ie dotiavlja . svoj oioteni Cuterfly. Podjetje Thinking Machines ie vedno razvija "drohnOKrnati" BiRtei» k 6đ(j00 procesor j 1 . HasBlvely Paralisi ProcCEEOr podjetja Goodyear Aerospace, kl ina 163B4 procesorjev, je v uporabi pri NASA že od lota 1903. MaraiÉa Jof e itevilo isavadnlh raćurva I i 6l'.lh proizvajalcev, kot so Eequont- Computer Systems, ELXSI iti Perklri-Elciiei , äe tr.od i f J c 1 r a Jo svoje navadne HiiltlprocesoiKke sisteme za uporabo pri paralelnem procesiranju. RaalEkovaJnti napore na področju paralelnega procec 1 ran ja financirata tudi DARPA in . Konec avgusta 1905 je celo podjetje IBM napovedalo realizacijo svojega sistema s 512 procesorjI z ImenoH RP3. faelEtem temelji na rezultatih projekta ultraračunalnika neuyorske universe. IBM raüvlja že Sest drugih razlièic sa paralelno procesiranji:!. Številni drugI raziskovalni projekti ae izvajajo v okviru akademskih inetituclj na podroäju podatkovnopretoćnih je-Bikov in strojev, ki naj bi se alternativno uporabljali v okviru paralt:lnega procesiranja. Dve Eil i ucmerjata pohudo v okviru paralelnega procesiranja. Prva je ugotovitev, da se amog-Ijivosti običajnih arhitektur npr. v okviru VLSI tehnologij f.e približujejo svoji končni točki in da nadaljn» arhitekturne Izboljšave ne dajejo več bistvunlh prispevkov. Sama VLSI tehnologija pa je sprqiila tudi povsem drugačen pristop. Dobavljivost zmogljivih 32-bltnih mi-kropracesorjev pa je navedla načrtovalce na zamisel, da ižčejo procesorje s Ekromnejiimi ukaznimi zalogami, Na ta način je mogoče, dobiti cenene In hitre 32-bitne mikroprocesorje, ki so primerni za masovno uporabo v paralelnem proce-Giranju. V najiiräeiB seiaantičnem smislu Je paralelno procesiranje prisotno praktično v vnakl raču-nslni£kl arhitekturi, npr. pri prekrivanju V/I z aritmetičnimi in logičnimi operacijami. Druga pomembna oblika paralelizma je Cevenje (pipelining) ali prekrivanje Izvajanja ukaza v aritmetični in logični enoti z doseganjem in dekodiranjem naslednjega ukaza v posebni ukazni enoti. Cevenje je bilo uporabljeno v računalniku IBK 7030 Stretch ie v letu 1961. V mrežnih (array) proceijarjlh so lahko uporabljajo sploinejže sheae covenja in v teh shemah se itevilne operacije prekrivajo v tkim, scml-avtonomnih materialnih elementih. Te sheme podpirajo navadno tudi vektorske operacije, ki jih najdemo v računalnikih podjetja Cray, v super-računalnlklh In v novem valu Crayet (npr. Convex In Alllatit Computers). Tod-i cevenje se upo- . rablja tudi v večini niipermlni jbv (npr. v OECo- vem VAXu In ORBR, v DGjovih MV, v PfirkinK-El- merjcvoift 3SriClXP) In ^^o^3t,-lJ^l tiatid.-irdno tudi v novfcm valu 32-bitiilh mi kropt ocosor jev . Ctiviinjfi v nekam ručuriaInIku tako ie riè pomeni avtomatično, da je t» računalnik žo paralelni sistem. Trenutno poudarjanje paralelnega procesiranja je usmerjeno ie posebej na uporabe multlproce-sorske (KP) in multImlkroprocesorske (HMP) teh-nologijfi za namene paralelnega procesiranja. Ker uporabljajo praktično vsi paralelni proce-Borjl MP all HHP tehnologija, pa ni vsak MP all HHP avtomatično tuđi paralelni procesorski sistem. NekateiB multlprocenorske sisteme je moč modificirati, da zmorejo nekatera bremena paralelnega procesiranja. Sistem FX/8 podjetja Acton (Mass) je prvi računalnik, kl združuje moinost-l HHP in paralelne procesorske tt:hnolo-gjje. m enostavno določiti, ali je sis'tem "navadni" MP ali -pravi- paralelni sistem. Klasifikacija po namenu. Bistvena razlika v razpoznavanju splošnega multi procesorskega sistema (SHP) od pravega paralelnega Elstema je tale! SHP sistem izboljšuje aietemEki pretok s prekri vanjep izvajanja ato-vilnih, medsebojno neodvisnih opravil v ranlič-n (los t opiMi !ii!pi)!i riMlno :> I i skr.cf.i ali vci» ppoocsor jov ; li i pci-kodkü ji' ^n.nii.i tiifli pod inieiioiH kov.iiii c-iim ; pri d iriiiMi/. i I i IMi jc STr'Viin procosnr jcv v hI pL-rkiick i t>!iiii:[j''J '-in. Ekega 6aea, ko clpullra vezja z več sto aH ti--Eoi procesorskimi elementi. Spice. od 1 ično podpira Batnega sehe pel pa ra 1 e 11 zac 1 j i , saj je étEvilo modulov glede nà itevllo procesor-eklh enot majhno, pa tijri.i onote niso kompleksno povezane In podatkovno odvisne. ELXSI In Alllant poroÈata • o uopeÄnl parale J i zaciJ i b prograifiom Splce ie po nekajdnevni uporabi, ko BO bile doseženo bistvene Izboljšave sistemskih zmogljivosti. Podjetje Shiva Hultisyctema (Mountain V^®"» Ca) je ubralo drugo pot. Za.svojega glavnega Jezdeca Jo proglasilo PowerSplce, tjd vezja, ki.je razdeljeno na podvezja, ki so med eeboj relativno ilbko povezana. Ta podvezja raareäujejo paralelni? (hkrati) določene probleme v multi-procesorfiken BiBtemu; tu Be npr. opravlja podni 1 1 sekundna sinhronizacija. Tako lahko Shiva vBtavl Bvojo programsko opremo v Sequent stroje, ko BO ti stroji opremljeni ie b tkim. Atomic Lock Memory, kl .je v bistvu materializi-ranl hitri prlpomotek za sinhronizacijo. Globalni in lokalni pomnilnik. Na£ln uporabe pomnilnika v pa-ralel/iih sistemih Je ključna značilnost za razlikovanje in vcebino' paralelizma. Pri porazdoljenem ali lokalnem pomnilniku ce predpostavlja, da Ima vsak procBsor svoj lastni lokalni pomnilnik in da se sporazumeva z drugimi procesorji 3 uporabo mreie.. Sheme z arhitekturo hlporkocke pripadajo temu tipu. Kadar je.pomnilnik globalen, torej deljeni vir, imamo'podobne razmere kot pri spložnlh multiprocesor-ckih sistemih; primer takšne arhitekture Je ul-traračuiialnik newyoräke univerze. V IBKovam RP3 in v Butterflyju (Bolt, Beranek & Newman) sta tia voljß'obe vrsti pomnilnika: globalni in lokalni'; pomnilnik Je tako dodan vsakemu vozliiS-nemu procesorju In tudi vsak procesor lahko dostopa v nekatere dele drugih pomnilnikov. Glavna prednost modela z globalnim pomnilnikom je možnost le enkratne. naložitve podatkov (npr., s diska); različni procesorji lahko potem pošiljajo podatke in uporabljajo pomnilnik za medsebojno sporočanje. V Eisterolh s porazdeljenim pomnilnikom uporabijo procesorji več. časa za Bprej&msnje začetnih podatkov In z medsebojnim^ razpošil Jan jem vmesnih rezultatov. Porazdeljeni (zasebni) pomnilnifki sistemi lahko enostavno oskrbujejo veliko žtevilo procesorjev; v sistemih z globalnim pomnilnikom je itevllo procesorjev fclKtveno odvisno od značilnosti medprocesorskega povezovalnega vezja. P ov e z ov alni sistem. Praktično uporabljajo vsi splošni mu 11Iprocesorski sistemi neke vrste skupno vodilo aa medsebojnf povezavo procesorjev ' in poninilnega sistema. Vodila BO seveda zelo draga in tako Je navadno žtevilo procesorjev omejeno na 23. Tudi kroB-bar stikala so nad tem otsvilom procesorjev neprimerna zaradi visoke cene. Paral e 1 n 1 s 1 stem 1, kl imajo 100 ali 1000 procesorjev tako ne morejo uporabljati skupnega vodila aH krosbar stikala. Na prizorišču paralelnih sisteinov sta se uveljavili dve povezovalni shemi. Prva je večstopenjska mreJa, ki Jo najdemo v ultraračunalni-ku, . v riP3. in v Butterflyju; ta mreža povezuje vsak procesor z.vsakim pomnilnim modulom, in Eicer tako, da vGtavl dve ali več ravnin vmesnih preklopnih vozlišč. Podobno kot v telefonski mreži Je število takih vozHiS majhno v primerjavi s številom moiiiih oddajnikov (procesorjev) in spejeanikov (pomnilnikov); s primerno Izbiro tsedvozlločnih povezav Je moč doseči, da obstaja vsaj ena pot med oddajnikom in spra-Jesinlkora. Druga shema se uporablja v hiperkocki in v njej • so povezovalni členi mod procesorji kar procesorji sami (glej sliko 1). Vsak procesor Je povezan samo 2 določenim številom sosedov. Komunikacija z oddaljenimi' ( ne sosed sh i m i ) procesorji Je mogoča le skozi eno ali več voaliič a načinom "shrani in pošlji naprej." Tretja povezovalna shema Je drevesna in se uporablja v Columbia University NonVon, v projektu r.LrmiLab's Advanced Computer in v podatkovno-baznem stroju Teradata. Privlačnost te povezovalne različice je omejena zaradi majhnega števila računalnih procedur, ki jih Je Kiogoče u-činkovlto preslikati na ta model. Kratek pregled dosežkov pralolnega procesiranja, V prejšnjl'novici' šmo v tabeli I prikazali dosežke na področju mrežnih (vektorskih) računalnikov. Tu dodajmo in dopolnimo prejšnje podatke.' Ultraračunalnik neuyorike univerze ima klasifikacijo HHP/VUVP/globalnl pomn11 niški s iston z medsebojno procesorsko povezovalno' mrežo tipa omega. Za razvoj tega računalnike je bila samo v letu' 1965 dodeljena dotacija $2,6 >.'.1, razvijali pa so ga 5 let v Courantovem institutu newyorške univerze. Doslej so zgradili osemvoz-llSčni prototip, v vozliščih pa so uporabili procesorje HC6e010. Do leta 1990 naj hi zgradili na tej osnovi. 4096 vozliščni sistem. Projekt vodita profesorja. Allan Gottii.cb in Malvin Kalos. Značilnost ultra računa 1niške povezovalne mreže je možnost razvrščanja paketov s konf1Iktniai zahtevami; tj. tistih, ki so prispeli na enaka iiuücjna vrata. Pri mrežah brez vmesnikov so posledice takih konfliktov ponovno pošiljanje paketov in znižanje učinkovitosti. Eden najpomembnejših dosežkov ultraračunalni-ške povezovalne mreže je mehanizem za sinhronizacijo pomni)niškega dostopa, ki se imenuje vaemi-ln-dodaj (fetch-and-add ali F&R). Ta mehanizem Je posplošenje atomarnih (neprekin1 j i-vlh) operacij tipa preizkusl-in-postavi (test-and-set),' ki se navadno uporabljajo za manipulacijo . v pomnilniku nameSčeni»* semaforjev pri koordinaciji dostopa k deljejiim- podatkovnim strukturam ali v kritičnih ukaznih območjih, F&A vrne prejšnjo vrednost celoštevi1ske spremenljivke In prišteje k njej nek inkrement v r.akem atonarnem zaporedju. F.&A se lahko uporablja neposredno za samodejno razvrščanje več procesorjev, ko se ti indeksirajo v skupni izvajalni vrsti. V avgustu "1985 je IB^^ formalno napovedal raziskovalni projekt paralelnega procesorja. IBH poudarja, da Je RP3 samo raziskovalni pripomoček in da ni vključen v noben trenutni proizvodni načrt, da pa bodo dosežki te raziskave vprjetno upoštevani v komercialno dobavljivih izdelkih podjetja. . Nova lastnost BP3 v primerjavi z u 1 tra računal-nikom je v tem, da ima IBMov sistem v vozliščih pomnilnike z obsegom do 4 Mzloge. Ti pomnilniki so uporabljivi kot lokalni, globalni ali kot obojevrstni pomnilniki, njihova delitev pa se določa dinamično v izvajalnem času. To naj bi raziskovalcem omogočilo ocenjevanje amogljivo-stl sistema pri različnih pristopih. Povezovalna Vreža v RP3 1ma dva podsistema, in sicer mrežo tipa banlan, ki se uporablja pri nalaganju In shranjevanje in mrežo tipa omega, ki vsebuje logiko in pomnilnik za oporncljcko kombiniranje. Računalniška vozlišča v RP3 bodo uporabi ja 1 a.poseben riscovski procesor, ki ga Je razvil IBM v FET tehnologiji. -Cilj trenutne- ga proiekta je razvoj 6'(-vozli Sćnega podeisto-ma 5Ì2-vosllèinega slcteira. IBM ocenjuje, da bo 512-voalièinl RP3 dosegel hitrost 1,3 milijarde ukazov na sekundo in 803 Hfiops.' 19 pomembnih aplikacij L-e äe uspoino If.vaja na RP3 in aS konverzijo programov jo potrebnih le nekaj dni. Druga aanlolva arhitektura je hlperkocka (tudi koztiilčna kocka). Ta ar hI tek tu ra - temei j 1 na ilb-ko poveaanlh VUVP alBtemih, kjer Ima vaako voz-lli£é «veij zatij^bni pomnilnik, ki je dostopen tudi la neposredne EiD&ede prfek dvosmerne secij-eke poveziive. Obstaja pa tudi globalni kanal, po katrticüh dobivajo vosllAč;» svoje progratne od. krmilnega računalnika in po katerem vračajo svoje resultate. Ta koncept jo bil prvotno raa-' vit v Pasodeni na CIT. Arhitektura Je. dobila Bvoja laie po nafinu .voz 1 ifiine povezave (glej Bilko 1). Dva hiperkockaeta modela ata bila doslej zgrajena na CIT, uporabljata pa procesorje e{)B6. Tretji model je bil zgrajen v Fasaden! v Jet Propulslon Laboratory z voali ihčni ni procesorji 6602«). Intlov iPSC (okrajšava za Intel Personal Supercomputer) je vodi Ini' komercialni Izdelek z arhitekturo hlperkockii,. V vsakem vozliäöu 1PSC se nahaja procesor 60206 s koproceeorjem D0287, uporablja pa ee taktna frekvenca 0 MHz. Medvoz* lli£no kotnunlkaciJe so dvostnerne In bitnoserij-Eke pri hitrosti nad 10 Hbit/s in sa Izvajajo e pomočjo Ethernet veaja S26S6 v vsakem vozlišču. Intlovl preizkusi H.iiejo, da zmore vsako vozli-iče hitrosti med 35 kflops do B0 kflops. IPSC Je dobavljiv v iavedbah z 32, 54 in 128 vozlišči, njihove cene pa eo SI60000, $276000 in $520000. Intel uporablja tri take sisteme, 14 pa jih Je bilo dobavljenih voliklin naročnikom. Drugi cietero s hlparkocko proizvaja Atnetek Computer (Arkadla, Ca). Tudi ta sistem uporablja kombinacijo procesorjev 60280/267 v voalličih in se Izdeluje v izpeljankah s IG, 32, 64, 128 in 256 vozlišči. Vsako vozlišče lahko ima do IMzlog pomnilnika, ima pa tudi £e procesor 80166, ki je namenjen medvoaližčni povezavi in protokolom. Cene se nekoliko nlšje kot pri Intlu. Omeniti velja žc non-vonskl projekt kolumbijske univerze, ki temelji na velikih procesirnlh elementih, ki se nahajajo v vmesnih korenih binarnega drevesa, kjer so binarna drevesa majhnih procesirnlh elementov. Tkim. velika vozlišča im.ijo zasebne pomnilnike In V/I zmogljivosti; ta vozlišča 00 medsebojno povezana in so kontrolirana z račuiralnikon VAX 11/780. Majhni • procesirni elementi so sestavljeni iz 4-bltnlh procesorjev in RAMa s samo 64 zlogi in delujejo kot Inteligentni poinnilnl stroji. Splošna operacijska zamisel tega sistema Je., da delujejo veliki procesirni oletaenti kot VUVP sistemi, ki usmerjajo ukazrie tokova k majhnlio proceslrnitn eleinentoi»; ti pa delujejo kot EUVP sistemi. Tako se lahko številna binarna iskali Ja, ki so značilna za umetno Inteligenco, izvajajo paralelno. Bostonsko podjetje Bolt Beranek & Newman dobavlja paralelni procesni sistem Butterfly, ki je namenjen uporabi v umetni inteligenci. Sistem ima 256 vozlišč, ki so povezana s tkim. metulj-tno mrešo, ki ja izpeljanka mreie tipa banlan. V vozliščih se nahajajo procesorji 66020 s pomnilniki od 1 do 4 Mzlognv. Ti pORinllnlki so lahko doEtoparsi lokalno lu globalno. Vsak procesor lavaja pont-bno kopijo jedra operacijskega alstriin;i, ki se nahaja Izven lokalnega dela njegovega pomnilniki». DobIoJ jo bilo Insta- liranih 2Ü teh sistemov, 45 pa je èe naročenih. Po.djetje Connection Wachine prodaja drobnosrna-ti sistem, katerega arhitektura naj bi bila primerna za lispovski stroj; vsebuje nr-o- cesorjBV oziroma vlozllgò oziroma natančneje inteligentnih pomnilnih vozHSi, ki so enobitni procesorji s poisnllnlkom 384 bitov. Poveaovalno vezje je tipa n-kocke (hlperkocka), metoda sporočanja pa jo drugačna. Projekt Cedar' illinolške univerze lavira iz prevajalnika Parafraso, ki lahko strukturlra fortrancki program v "usmerjene krmilne grafe," kjet"5i-Je vsako vozlišče grafa opravilo, ki bo Izvajano, vejltvc pa nakazujejo prednostna ro-lacij:; in podatkovne odvisnosti. Namen projekta Cedar je gradnja mul t iprocesorske konfigurscije za paralelno izvajanje vozlišč dobljenega grafa. Projekt vodi prof. David Kuck. MITJeva raziskovalca (J. Dennis in Rrvind) sta začetnika dela na področju računanja z modeli podatkovnega pretoka. Tskčen model omogoča paralelno izvajanje drobnozrnatih ofavll pri uporabi posebnoga funkcionalnega ali aplikativnega Jezika, ki Je visoko strukturiran In veliko bolj omfijen kot visoki Imperativni jezik Fortran. ParalelIzem se doseie s konverzijo programa v usmerjeni podatkovnopretočni graf, katt^rega voziibüü so «člsLe funkcijt^ (biez stranskih učinkov) in katerega poti (loki) prikazujejo podatkovne odvisnosti. Konversjlja se doseie z jezlkovnliri prevajalnikom In uporabniško sodelovanje ni potrebno. Podatkovnopretočni računalnik ima več izvajalnih enot različnih tipov (npr. za seštevanje, odštevanje, isnoìenje} in programsko krmiljeni procesor. Izhe^i vseh Izvajalnih enot se lahko povežejo na njihove vhodn s preklopno povezovalno mreio. Program, ki poganja krmilni procesor, Je določena predstavitev podatkovnopretoč-nega grafa. To ni sekvenčni program: ukaz postane izvršljiv, kakorhltro so prisotne vse vhodne vrednosti na izhodih ustreznih izvajalnih enot. V tej točki se ukaz lahko priredi Izvajalni enoti s povezavo Izhodov na vhode te enote. Veliko ukazov se lahko Izvaja paralelno v različnih izvajalnih enotah. Trenutno je v raavoju več podatkovnopretočni h računalnikov; takšen stroj se razvija na MIT', pri NTT-(japonsko podjetje) pa Sigma Razvi- tih Je bilo tudi več podatkovnopretočnih pro-gramlrnlh jezikov. Najbolj kritično vprašanje paralelnega procesiranja je, ali Je mogoče podatkovnopretočne metode uspešno uporabiti pri reSevanJu potreb komercialne obdelave podatkov. Naključne raziskave kaiejo npr., da bi bila priprava plačilnih list Idealna za paralelno procesi ranje i plača kakega zaposlenega se namreč računa neodvisno od drugega zaposlenega; ti Izr^čur' bi tako lahko potekali paralelno na voč procesorjih. Vendar se tudi pri paralelnem procesiranju lahko pojavi problem zasedenosti V/I virov.' Ce preveč procesorjev čaka na V/I, postano veliko število procesorjev nesmiselno. Podoben je problem pri paralelnem sortiranju zbirki sortiranje Je lahko paralelno, bralni čas zbirke pa Je predolg In tako Je paralellzero brez pravega pomena. Celo pri znanstvenih in tehničnih prohlfs-mlh, kjer Je obilo paralelizma, obstaja gornja meja izboljšanja zmogljivosti. Ce jo v programu mogoče paralel la t cat i njegovih 96% In ontano le 5% serijskega dela programa, bo pohltritev s ■ paralelnim Izračunom lahko kvečjemu 20-kratna neglede na Število profesorjov In njihovo hitrost. Vendar je navadno mogoče paraluliz irati le 20% do 30% programa. Navadno Jo potrebno pisati progrf.iu'i v obliki. la katere je razvidna pclsotnoEit veé procesorjev, kar Kicer dodajanje ali odvzemanje procesorjev (voBlliii) nI transparentrio. Navadno je nCMOcgofie opraviti rauitlprofjrarni ran jp,:j . dina-inlÉno delitev komplekaa za paralelno .Izvajanje OKlroma na neodvisna opravila. Vendar ce n.ičr-■tuje, da bo z RP3, Butterflyjcm in hlperkockani mogoče pokazati, da je taka dlnamlina delitev moina. Večkrat paralelni procesorji ne morejo delovati neodvlEno, saj se obravnavajo kot periferne naprave glede na gost 1 tes 1 Jsk 1 rnčunal-'nlk, ki razdeljuje programe in. podatke po voz-llüiih tnreie In zbira rezultate. Glavna ovira v napredovanju paralelnega proco-Biranja je ponanjkanj e oSlnkovltlh uporabniških razvojnih orodij in pomanjkanje paralelnih popravljalnih (debugging) sistemov. fodaLkuvuù-pretočni sistemi obljubljajo nekaj v tej cmeri, vendar so ti■olsterni drugače omejeni (prepis obstoječih programöv'v nov jezik). Mehanično Je mogoče paralelIzlratl fórtranske programe, vendar je to paralel lasci ja na niski ravni. A. P. Zeleznlksr BSSaSBBBSstSSB ZDA In Japonska ukinjata carine Quo vadie Austro-Chlp? ~ - — = - ^ ■ - - ■ f- r: r_ u r. ■• t " : - - :: t; -■ r- r ■ . r — r ZDA in Japonska sta podpisali sporazum', s katerim se ukinjajo carine na področju računalniit-va, 7DA ee obvoaujajo, da i.lfinjajn carine (na t!%) za računalniško komponente r, izjemo prikazovalnih elektronk. Kot protluslugo ukinja Japonska carine sa računalnlike komponente, periferno naprave in centralne enote. Pred tem sporazumom so bile carine sa te izdelke na obeh straneh v območju 4,6 do 6%, ' " Siemens se hitro razvija = s= = = aaaaB = tsa=aBE = tesst = s=:t = e=:=: = = = = c = = =: = = t = = = s: = = = = V preteklem poslovnem letu 190Ì/B5 javlja podjetje Siemens prihodek 61,7 »lUjard («) DH (plus 7%). Doma so naročila narasla aa 2% na 23,9 MDH, sa inOKemstvo pa za 12% na 27,8 HDM. Nadpovprečna rast prihodka je bila dosežena v. energetski in avtomat i zaci j ski .tehniki, komunikacijski in pòdfltkovnl tehniki kot tudi v medl-cinekl tehniki. 3BBSSB?SBaESBSäBBaaBeE3a:±£:a = = = saas:z V izdelavi je superračuna1n1 k z gigaflops s.s: ^ ;= = = ? s - B B a t = s Ka princetonskl univerzi razvijajo superraču-nalnlk, ki naj bi bil naJ smog 1 J i vejš1 na svetu. Ta raćunalnik naj bi Imel 128 voz 1 iäin. naj bi dosegel hitrost 61,4 milijard operacij v plavajoči vejici na sekundo (gigaflops) In trajno zmogljivost 51,2 gigaflops. Povezava med vozll-£čl temelji na tkim. arhltoktorl tipa cosmic cube, ki je bila razvita na kalifornijske» tehnološkem Institutu. Doslej so razvili hitro 16-krat-l6-krat-32-linijsko mrežo za prenos podatkov med vozlišči. Ta mreža rie zahteva dodatne podpore (no overhead) pri medprocesorskih komunikacijah. V vozlišču bo uporabljenih do 24 32-bltnlh procesorjev tipa Am29325 ieroltorsko sklopljeni procesorji za operacije v plavajoči vejici) s' taktno frekvenco 20 MHa. Vsako, voz-llSče bo imeio trajno zmogljivost 400 Mflops in vrhunsko zmogljlvosit 480 Mflops (to Je trikrat več kot sistem Cray-l). Minilo je le B let, ko so v centrali podjetja Voest v [.Inzi.i Klovesnn najavil!, ria vstopajo ns področje mlkroe1ektronike• Danes pa se avstrijski politiki, gospodarstveniki In tnajhni davkoplačevalci ustavljajo ob ruievlnah diverzlflka-cijske strategi je.'.največjega avctr i Jskega koncerna: mlkroalektröns.ka aktivnost tega koncema izkazuje velike izgube. Vstop podržavljenega jeklarskega koncema v pol prevodnifko tehnologijo Je bil žc na samem začuLku problematičen. Poslovni in Lehiioložki partner American Microsystems je bil že pred ■otvoritvijo skupnega obrata v Unterpremstaetten pri Grazu absorbiran v podjetje Gould. Austria Hikrosysteme životari že od samega začetka, medtein pa je tudi podjetje Gould zašlo v rdeče številke.- Pri tem veija poudariti, di se tržl-žče vezij po naročilu, ki je bilo domena amecl-žkega partnerja, stalno povečuje. Vzroke neuspeha torej nI mogoče iskati na tržl£fiu. Podjetje Siemens je opozarjalo že na samem Ka-četku, da naj se Jeklokuharji nikar ne lotevajo stvari, ki Jih ne razumejo. Vendar je aažsl v težave tudi Biemensov beljaäkl po 1 prevodn1äk1 □brat. V trenutku, ko so odprli "256-k-obrat," ..t: je podrlo- svetovno pomnilnifiko tržišče. Glavni OEM partner IBM Je občutno amanjšal.svoja naročila In rezultat je bil znan: Siemeiis j« v Beljaku uvedel skrajšani delovni čas. Direktor in soustanovitelj tega obrata se je takoj praselil v Braunschwelg, .seveda iz fö.-aiein osebnih razlogov. Ob tem se patetično postavlja vprašanje, ali je Austro-Chlp res pred Izumrtjem. V podjetju Voest Je položaj mikroelektronskega obrata povsem nejasen tudi zaradi Izgub tega podjetja v drugih njegovih branžah. Podjetje Siemens lahko reši finančno položaj svojega beljaškega obrata le z "modrim očesom." Vendar so pri Sleniensu ie vidni znaki umika s področja pomnilničkiti vezij na proizvodnjo vezij tipa Teiecom In ASIC. Avtorsko abecedno kazalo časopisa Informatica, letnik 9 (1905) eiankl hlatlč B., K. Jcsernlk: Računalniško podprto TiaSrtovanje pulanlh usmernikov. Informatica 9 <1965), «t. ctr. 240-260. Alolclo G.; The Rest Module; Computer Simulation ot the Control Unit. Informatica 9 (1965), it. 4, ctr. 82-88. ApCiB.tolova Mirjana, V. Trajkovski: Metodolofki prSctap vo planicöiijGto no tnCotmacioni eleteiul vo uprava. Informatica 9 (1965), it. t, str. 167-172. Arbutlnn Jovid Mirjana, E. Crnovri anini Meteo» roloikl informacior. I elstem. Informatica 9 (1986), it. i, Gtr. 22}stcskl dlBkt z vdelanimi krmilniki jt _ ■ = l=B* = s* = p= = B5t: = = = = »= = ?; = = = = = *B=* = = B = = = = = = = = = = s = sB PicBko Jele,n8, X. P.. Soleanlkar! Besedilni ob-llkovalnik v Jeziku E'ascal. Informatica 9 (190&), St. 3, Btrt 71-86. železnlkar A. P.i Ma^lSnl kvadrati Eiode in lihe stopnje. OP 19. Informatica 9.(1985), it. 1, Btr. 7S-7B. Seleznlkar A. P.: Marshal lov a Igo ri Len. UP 20. Informatica 9 ( 19S5 ), it. 2, str. 86-87. Seleanlkar,A. P.: Položaj točke glade na innogo-kotnik. UP 21. Informatica 9 (198!;), it. 2, str. 60-90. Kove ra£unalnlike generacije Seleznlkar A. P.t üvod k novi' rubriki časopisa Inforoatlca. fit. 2, str. 72-73. ialesnlkar A. P.i Doslej objavljene novice in pciEpevkl s področja novih tačunainižklh 'geno-raclj v časopisu Informatica. St. 2, str. 73. ' f ieleznlkar A. P.: Izveden'likl sistemi, ki temeljijo na znanju I. St. 2, str. 73-83. aeleznikar A. P,: Bibliografija g področja novih računalnliklh generacij I. et. Z, str. 8386. Dva ameriška proizvajalca sta začela v svoje visokozmoglJive ■ 5-I/J-co 1ske vinčestrska diskovne enptc vgrajevati tudi krmilnike in sta tako dosegla tklm. SCSI 1mpleoentaciJo. Ta proizvajalca sta Maxtor Corp. in Priam Corp. Iz San Jose Ja v. Kaliforniji. Maxtor jeva družina z oznako XT-3(100 Ima pomnilni obseg 170 aH 28Ö-Malog s poprečnim časom dostopa. 30 ns. Cena teh« enot bo prlbiifno 10? na Hzlog. Prlamov model 725 ima obseg 255 Mzlog In čas dostopa 20 ms. Cena teh .enoz' bo $2185 pri .1000 kosih; Svetovni hitrostni rekord v Bel.lovih IciLioiaLor I jih gradijo tranzlsLor š časom preklopa 5,8 ps. Ta hitrost Je za 32% nl-ija od hitrosti 2,7 ps, ki ei jo Jani dosegli pri podjetju Koneyuell. TI tranzistorji so izdelani v Sans In AlGaAs tehnologiji. Ta hitrost je bila doseiena pri nizki temparaturl 77 stopinj Kelvlna. Pri sobni temporatur1 znaia preklopna hitrost tranalstorja ie 10,2 ps. Iz-gubna moč pa 1,83 mW. Seleinlkar A. P.: Mednarodna konferenca o raču-nalnlikih aistemih pete geneiracije v Tokiu. Informatica 9 (1985), it, 3, str. 68-70. Saleznlkar A. P.i MProlog, jazik aa uaetno pamet. Informatica 9 (1985), it. 3, str. 70. Poleatka ieleznlkar A. P.i Ometna inteligenca: polenični siapls. Informatica 9 (1,985), it. 3, str^ 87-89. Kovice In zanimivosti Blatnik B., A. P, Seleanlkar: Stopnjevanje studijskih programov računalnliklh ananoetl. St.-2, str. 91-92. Blatnik B.t Podjnlotnskl itudlj računalnlitva na ameciikl univerzi. St. 2, str. 93-96. Seleznikaf A. P..: Jezik Lisp za mikroračunalnike.. et. 1, ste. 79, Seleznikar A. P.: Kaj pomeni ibmovski osebni računalnik? St. 1, str. 79-82. Seleznikar A. P,:' Kako si zgradite ibmovskl PC? et, 1, str. 82-84. ìeleznlkar A. P.: Ibmov PC AI..St. 1, str. 84- . 85, ieleznlkar A. ?,; Saljivo in tragično, ét. 3, sttf. 90. Seleznikar A. P.i Nove knjige. St. 3, str. 90. PRVO OBVESTILO O Sf^INAPJU "MIKROFILM V PRAKSI", KI BO V LJUBLJAMI NA GOSPODARSKEM RAZSTAVIŠČU 19. IN 2o/4-1983 1. dan: Skupne teme: - Mikrofilm v informacijskih sistemih - Vrste mikrofiliriov in njihova uporaba - Razvoj inikrofilmK v svetu in pri nas - Mirkofilra kot sredstvo organizacije in racionalizacije poslovanja z dokumentacijo - Arhivska trajnost dokumentacije r;a papirju - Pravni vidik mikrofilma in možnosti ponarejanja in poneverjanja mikrofilma 2. dan: Skupna taija: Povezava računalnika In mikrofilma Seminar A: Uporaba mikrofilma v splošni poslovrii in dr^ugi dokumentaciji - Uporaba mikrofilm?; v komerciali^ splošnih službali, kadrovski evidenci, računovodstvu ipd. - Uporaba mikr-ofilma v javrd. upr^avi, arhivih in delovrdh organizacijah ter ustanovah, ki imajo trajno dokumentacijo - Uporaba mikrofilma v bančništvu, SDK in podobnih dejavnostih - Ogled mikrofilmskega centra Seminar B: Uporaba mi.krofilma. v tehrjični dokmentaciji ■ - Uporaba mikrofilme, v tehnični dokumentaciji - Priprava dokumentacije 2a mikrofilmsko obdelavo - Mikrofilm.ska obdelava tehnične dokumentacije, razmnoževanja in s]užba sprememb - Praktični prika?. uvedbe 35 tmi filma v poslovanje s ogledom tniki-ofj.lmskega centra Seminar C: Računalniški Izhod na mikrofilm - Uporaba COM sistema za izhodno enoto računalnika - Priprava in organÌ2ac.ija dokumentacije za prehod na računalniško-mikrofi]m£j<-o obdelavo - Racionalizacija poslovanja s CDM-om in razvoj COM sistanov - Praktični prikaz uporabe računalniško - mikrofilmske povezave z ogledom mikrofilmskega centra Za vse informacije o seminarju se obrnite r.a tov. ČUFER Stanka, RSNZ SRS Kidričeva 2, Ljubljana, tel. 325-361.