fìS informatica 2 • YU ISSN 0350-5596 VELIKA KAPACITETA MALEGA MIKRORAČUNALNIKA »PARTNER Centralna procesna enota 128 KB pomnilnika Diskovna enota Winchester, zmogljivosti 10 MB Disketna enota, zmogljivost 1 MB Serijski vmesnik za tiskalnik Operacijski sistem CP/M PLUS^ Uporabniška dokumentacija ISKRA DELTA Tržno komuniciranje Parmova 41 a Iskra Delta into r matica JOURNAL OF COMPUTING AND INFORMATICS Published by INFORMATIKA, Slovene Society for Informatics, Parmova 41, 61000 Ljubljana, Yugoslavia EDITORIAL BOARD : T. Aleksić, Beograd; D. Bltrakov, Skopje; P. Dragojlovlć, Rijeka; S. Hodžar, Ljubljana; B. Horvat, Maribor; A. MandžicS, Sarajevo; S. Mihalić, Varaždin; S. Turk, Zagreb EDITOR;-IN-CHTEF! Anton P. Železnikar TECHNICAL DEPARTMENTS EDITORS: V. Batagelj, D. Vitas — Programming I. Bratko — Artificial Intelligence D. ćečez-Kecmanović — Information Systems M. Exel — Operating Systems B, Džonova-Jerman-Blažič — Meetings L. Lenart — Process Informatics D. Novak — Microcomputers Neda Papid — Editor's Assistant L. Pipan — Terminology V. Rajkòvie — Education M. Špegel, M. Vukobratović — Robotics P. Tancig — Computing in Humanities and Social Sciences S. Turk — Computer Hardware A. Gorup — Editor in SOZD Gorenje EXECUTIVE EDITOR: Rudolf Murn PUBLISHING COUNCIL: T. Banovec, Zavod SR Slovenije za statistiko, Vožarski pot 12, Ljubljana A. Jerman-Blažič, DO Iskra Delta, Parmova 41, Ljubljana B, KlemenöicS, Iskra Telematika, Kranj- S. Saksida, Institut za sociologijo Univerze Edvarda Kardelja, Ljubljana J. Vlrant, Fakulteta za elektrotehniko. Tržaška 25, Ljubljana HEADQUARTERS: Informatica, Parmova 41, 61000 Ljubljana, Yugoslavia Phone: 61-312-988; Telex: 31366 YU DELTA ANNUAL SUBSCRIPTION RATE: ÜS0 22 for companies, and US0 10 for individuals Opinions expressed In the contributions are not necessarily shared by the Editorial Board PRINTED BY: TIskarna Kresija, Ljubljana DESIGN: Rasto Kirn YU ISSN 0350-5596 V O L U M E 9, 1985 - NO. 2 C 0 N T E N T S B. Blatnik 3 Modeling and Analysis of Com- munication Protocols and Com- puter Networks Using Petri Nets J. Šilo 10 Basic Principles of Data Flow B. Roblč Systems G. Štrklć 16 Concurrent Programming Langu- D. Novosel ages far Control System .. . N. Mitlć 19 An Extension of LispKit Lisp V.Stojkovlč Language by Explode and ... D. Petkovlč 26 Analysis of Code Generation for a Commutative .. . A. P.Želez- 30 Petra - An IBM-Like Personal nikar Computer III Z.VukaJlović 39 Nonintegrated Pascal Environ- ment G. Štrkić 42 Scheduling Analysis in a Mul- D. Novosel tiprogramming System ... B.Mihovilović 48 Multiprocessor Systems P. Kolbezen K. Jovanoskl 52 Classical Algorithms for Fin- ding Minimum Spanning Trees D. MUjan 56 Machine-Man Communication By J. Šile Voice S. Zorman 63 Application of a Digital In-, oremetal Encoder ... M. Kukrlka 66 An Example of Dynamic Task Scheduling in a Real-Time ... 72 New Computer Generations 86 Programming Quickies 91 News iriforriiatica časopis izdaja Slovensko društvo INFORMATIl»., 61000 Ljubljana, Parmova 41, Jugoslavija UREDNIŠKI ODBOR: T. Aleksić, Beograd} D. Bitrakov, Skopje? P. Dragojlovid, Rijeka; vSV Hođžar, Ljubljana; B. Horvat, Maribor; A. . Manđžić, Sarajevo; S. Mihalić, Varaždin; S. Turk, Zagreb GLAVNI IN ODGOVORNI UREDNIK: Anton P. Železnikar TEHNIČNI ODBOR: V. Batagelj, D.Vitas—programiranje I. Bratko — umetna inteligenca D. Ćećez-Kecmanovitf — informacijski sistemi M. Exel — operacijski sistemi B. Džonova-Jerman-Blažič — srečanja L. Lenart — procesna informatika 0. Novak — mikroračunalniki Neda Papié — pomočnik glavnega urednika L. Pipan — terminologija V. Rajkovič — vzgoja in izobraževanje M. špegel, M. Vukobratovid — robotika P, Tancig — računalništvo v humanističnih in družbenih vedah S, Turk — materialna oprema A. Gorup — urednik v SOZD Gorenje TEHNIČNI UREDNIK: Rudolf Murn ZALOŽNIŠKI SVET: T. Banovec, Zavod SR Slovenije za statistiko, Vožarski pot 12, Ljubljana A. Jerman-Blažič, DO Iskra Delta, Parmova 41, Ljubljana B. Klemenčič, Iskra Telematika, Kranj S. Saksida, Institut za sociologijo Univerze Edvarda Kardelja, Ljubljana J. Virant, Fakulteta za elektrotehniko, Tržar ka 25, Ljubljana UREDNIŠT\'0 IN UPRAVA: ^Informatica, Parmova 41, 61000 Ljubljana; telefon (061) 312-988; teleks aiae'e to Delta LETNA NAROČNINA za delovne organizacije znaša 1900 din, za redne člane 490 din, za študente 190 din; posamezna številke. 590 din. ŽIRO RAČUN: 50101-678-51841 Pri financiranju časopisa sodeluje Raziskovalna skupnost Slovenije, Na podlagi mnenja Republiškega sekretariata za prosveto in kulturo št. 4210-44/79, z dne 1.2.1979, je časopis oproščen temeljnega davka od prometa proizvodov TISK: Tiskarna Kresija, Ljubljana GRAFIČNA OPREMA.: Rasto Kirn ČASOPIS ZA TEHNOLOGIJO RAČUNALNIŠTVA IN PROBLEME INFORMATIKE ČASOPIS ZA RAČUNARSKU TEHNOLOGIJU I PROBLEME INFORMATIKE SPISANI E ZA TEHNOLOGIJA NA SMETANJETO I PROBLEMI OD OBLASTA NA INFORMATIKATA YU ISSN 0350-5596 LETNIK 9, 1985 - ŠT. 2 V S E B I N A B. Blatnik 3 Modeling -and Analysis of .Communicaton Protocols •J. Šile 10 Osnovna načela DF sistemov B. Rob i 5 G. Štrklč 16 0 jezicima za konkurentno D. Novosel programiranje N. Mitič 19 Proširenje LlspKit Lisp je- V. Stojković zika funkcijama Explode i Implode D. Petković 26 Analysis of Generation for a Commutative One-Regi- ster Machine A. P.Železnikar 30 Ibmovski osebni računalnik Petra III Z.Vukajlović 39 Neintegrisano okruženje pro- gramskog Jezika Pascal G. Štrkič 42 Analiza razporedjivanja za- D. Novosel dataka u multiprogramskom sistemu B. Mihovilović 48 Večprocesorski sistemi P. Kolbezen K. Jovanoski 52 Klasični algoritmi za iska- nje minimalnih dreves D. Miljan 56 Govor V komunikaciji med J. Šile strojem in človekom S. Zorman 63 Uporaba digitalnega inkre- mentalnega kota ... M. Kukrika 66 Primjer dinamičkog raspore- djivanja zadataka ... 72 Nove računalniške generacije 86 Uporabni progami 91 Novice in zanimivosti MODELING AND ANALYSIS OF COMMUNICATION PROTOCOLS AND COMPUTER NETWORKS USING PETRI NETS BOŽIDAR BLATNIK UDK: 681.3:007 DO ISKRA DELTA, LJUBLJANA Abstract. Communication protocols Intrinsically involve parallelism and therefore fall Into the class of problems for which Petri nets have been defined. The methods developed for the specification, design and analysis of communication protocols using Petri nets are briefly discussed in this paper. A survey of work done in this area in the recent years is presented and referred to. MODELIRANJE IN ANALIZA KOMUNIKACIJSKIH PROTOKOLOV IN RAČUNALNIŠKIH MREŽ S PETRIJEVIMI MREŽAMI. Petrijeve mreže so u£inkovito orodje za modeliranje in analizo paralelnih sistetnov. V članku so opisane nekatere metode iz teorije Petrijevih mrež, ki se uporabljajo za specifikacijo, načrtovanje in analizo komunikacijskih protokolov in računalniških mrež. Podan je pregled do sedaj opravljenega dela na tem področju in možne smernice za nadaljnje raziskave in razvoj. 1. Introduction Petri nets are a class of mathematical models of the structure and dynsimic behavior of nondeterministic systems. In a relatively short space of years Petri nets have become the dominant model of concurrency and parallelism in computer systems. They have been applied to many different areas of practical interest, in computer science, including the design and analysis of pipelined hardware and the deadlock analysis of operating systems, inspired by the work of Hack et al on the Information System Theory Project during 1968 to 1971 and of Denrjis et al on the Computation Structures Group of Project MAC during the same period'. The original motivation for Petri nets was, however, to provide a rigorous basis for the study of communications. Petri nets were first formulated and investigated by Carl Adam Petri in his 1962 'doctoral dissertation ((1)). His opening paragraphs well-state his orientation in the project: "This work is conoèrned with the conceptual foundations of a theory of communication. It shall be the task of thiš theory to describe in a consistent and exact manner as many as possible of the phenomena that occur in the transmission and transformation of information. . Petri net theory has developed considerably since its beginrUngs'in 1962. However, much of the work is hard to obtain, being available only as reports and dissertations scattered among many sources. The major parts of Petri net theory are brought together in a concise and consistent manner in ((2)). It is becoming expected that every computer scientist know some basics. It has only been in the last ten years that Petri nets have actually been applied to the verification of communication and network protocols, corresponding no doubt to the greatly increased importance of these areas during this time, e.g. ((3)), ((4)), ((5)). The distinction between Petri net models of communication protocols and network protocols and, thence, other applications is centered around the importance of time. In Petri's original critique of automata theory, the presupposition of the synchrony of deterministic automata was isolated as a fundamental stumbling block to their application to communications. Insisting that the automata must map to reality, he deduced that not only is communication a nondeterministic process but that the time delay in propagation of state transitions was considerable and that an automaton fundamentally dependent on synchrony could not model the process he was examining. Therefore, the basic principle on which he would reconstruct automata theory would be that synchronization decisions must be made purely locally at each state. Basic Petri nets are purely time-independent. Petri nets used in network protocol applications are weakly-. Hocally time-dependent, usually only presupposing the existence of a 'time-out* . timer which may be started when a. state Is. entered and which will cause a transition to an 'error* state If no other transition has occurred by the time the timer turns over. Communication protocol applications are locally time-dependent, usually presupposing a minimum-time-to-transltion concept. It has been demonstrated that these concepts together with the Intrinsic interpretation of Petri nets as logical state space diagrams can be profitably used to analyze protocols from the data link layer to the application layer in a network architecture. Petri net models are used in two basic modes; simulation modeling and analytic modeling. These two modes will be discussed in the following two sections, focussing primarily on analytic modeling. The final section of this paper will briefly discuss possible directions for future study. 2. Simulation Modeling Petri net simulation systems, are suites of software tools which allow the Input-output, manual manipulation, automatic execution, and partial automated analysis of Petri net models. The first known such system was implemented at •the University of Washington by Noe et al. ((6)). This system consisted mainly of a graphics editor for the input-output of Petri nets and the firing of enabled transitions input by the user. More sophisticated systems are under development at various institutions in France . and Germany. It is convenient to discuss the nature of Petri net modeling in this context. A Petri net model consists of three components: à static substructure, a dynamic substructure, and an analytic substructure. The static substructure of a Petri net model is represented by a Petri net graph which represents the a priori relationships between the various states of the system being modeled. It is a bipartite directed graph. The two classes of nodes are called places and transitions, represented by circles and bars, respectively. The arcs of the digraph are restricted to join . place-transition or transition-place pairs only. An example of such a construction representing a simple protocol for a transmitter (left side) and a receiver (right side) is given in Figure 1. The most frequent interpretation of these digraphs in net theory is to consider the places as all pertinent predicates or states which can hold In the system and the transitions as all pertinent events which can occur in the system. The input places of a transition are the preconditions which must hold for the event to occur, and the output places of a transition are the postconditions which will hold after the event occurs. Events are viewed as logical state transformers. When an event occurs, under the standard interpretation, the postconditions come-to-hold while the preconditions, simultaneously, cease-to-hold. This ebb and flow of the states of the system is regulated by the dynamic substructure. The dynamic substructure of a Petri net defines the idea of a marking of the places of the Petri net graph and defines' a firing rule to govern the behavior of the transitions. A marking is an assignment of tokens, represented by dots, to places. The absence of a token in a place Indicates that the corresponding predicate does not currently hold, while the presence of a token indicates that the predicate does currently hold. The canonical firing rule for Petri nets states that the firing of a .transition subtracts one token from each of its input places and deposits one token into each of Its output places. The only transitions which may be fired, however, are those which are enabled by having at least one token In each of its Input places. If several ready to send ready (buf aval) /'^'nsg ( ) rec'd ack OK ack rec'd O ready .0-ree msg Figure 1. Petri net model of a simple transmitter-receiver protocol. , itransltions are enabled, then one is chosen at irandotn, for normal Petri nets. jThe Petri nets used for protocol analysis, ihowever, are not normal Petri nets. They are a ispecial class of nets usually called time nets. fMerlin was the first to do work on evaluating jcotnmunlpation protocols using Petri nets ((7)). :Hia work concentrated on physical telephone iprotocols and is an example of locally tlme-Idependent nets;. In this model, each transition 'has associated with it two times, tX=t2. He ■postulates a local timer for each transition which starts when all the input places for the transition contain at least one token. The transition becomes enabled and fireable after time ti has elapsed and must fire before time t2 .^.as elapsed, all of which assuming that at least one token remains in all the input places throughout. It not, the timer is reset and stopped. Other variations on tj.me nets have been proposed. Cpolahan and Roussopoulos ((8)) describe a variant not unlike Merlins but only distinguish tl. This model is more analyzable than Merlin's, and Coolahan and Roussopoulos sketch their proof procedures, but still this technique remains basically a simulation model. In a different vein, Molloy suggests that allowing the transition delay time tl for each transition to be exponentially distributed is of interest. For an interesting subclass of Petri net graphs, he shows that such exponential time nets are equivalent to ergodic Markov chains. Within this'domain, the nets are analyzable by standard techniques and are easier to formulate in their Petri net form than in a Markov process form. Outside this form, however, recourse is made to simulation (O)). , The last component of a Petri net model is the analytic substructure. This consists of the definitions of the properties of the model which are to be decided or quantified and the properties which are to be preserved under any net morphism which is applied to simplify the net. The three classic predicates of Petri net theory, namely ' liveness, safeness, and reachabpity, also have application to protocol models. A Petri net is live iff it cannot deadlock, i.e. iff for all reachable markings from some initial, marking at .least one transition is enabled. A net is safe at level k iff for all reachable markings from some initial marking the maximum number of tokens in any place is less than or equal to k. This property becomes Important when it is realized that places may represent message buffers of finite capacity (if k is exceeded, then messages have been lost or overwritten) or when a place has a one-to-one correspondence to a message currently being processed (in which case, bookkeeping information about the message has been confused with the message following). A marking of a Petri net is reachable from a given initial marking iff there exists a sequence of enabled transitions whose firing would produce the marking. Reachability considerations become important when determining whether normal and exception states can ever be reached. For example, can the message transmitted ever be received using the protocol being studied? The properties to be preserved under a net morphism ((10)) are varied and may be particular to an application. They include the properties above (liveness, safeness, reachability) as well as certain special ones defined by Merlin for protocol models. These latter properties are considered by Merlin to be necessary for all well-behaved protocol models. They are: the number of states is finite, from any marking reachable from the initial marking the initial marking is itself reachable (always cycle back to the' initial marking), there is no direct loop 'from an exceptional state to an exceptional state (the protocol does not get lost on error conditions), and when one party in" the communication -link returns to an idle state then the other will return to its idle state within a finite amount of time (i.e. back to the initial state). Certain other quantities to be computed have been defined by Molloy ((11)) and Ramamoorthy and Ho ((12)). These include: mean time in state, mean cycle time through the net, expected exception rates, and mean throughput. Although these authors demonstrate analytic techniques for deriving this information for special case nets, for . the .general cases simulation is still resorted . to. Such simulation systems must include mechanisms to encompass the static and dynamic substructures of the Petri net model and should include automated tests, at minimum, for the failure of. the properties just discussed. Ideally, though, tools which actually decide these properties should be included^ These tools would be based, on the techniques of the next section. 3. Analytic Modeling The goal of analytic modeling is to. develop finite deterministic decision procedures for the predicates of the analytic substructure which are effective. Petri net models for any practical-sized problem are of a complexity that Is generally unreasonable to expect that the analysis will be cai'ried through by human computation. Therefore, if the techniques are not automable, they are. useless. This, is so, though, with the understanding that several of the most interesting problems are provably NP-space-hard ((13)) or NP-complete ((12))-. The authors who have proposed time net models Just discussed have included in their results analytic findings and in some cases have given proof methodologies to find the quantities or decide the predicates enumerated above. But,; these techniques have been ad hoc, rather, brute-force approaches automable. only with the use of a general theorem prover. Recent advances ^.n net theory have demonstrated the; real utlli);y of a linear algebraic approach ' to| Petri , netlanalysis, e.g. ((14)). It is this theory which will be briefly discussed here. ■ Tho basis of this technique is the incidence matrix for the Petri net graph and linear invariants for this matrix. To b^gin, this theory applies to self-loop-free graphs, i.e. Petri net graphs where no place can be both an input place for a particular transition and an output place for that transition. For the purposes of modeling protocols, this is not a severe restriction. The incidence matrix N for I a net is a p by t matrix where the i.j entry of ,N is 0 iff there is no arc from the i-th place to the J-th transition or from the J-th transition to the 1-th place and is the difference between the number of i,j arcs and the number of j,i arcs otherwise, where p and t are . the number of places and number of transitions, respectively. A marking m is a p by 1 vector representing the number of tokens in each place. A transition vector x is a t by 1 vector indicating which transitions are to be fired. The firing rule for Petri nets which produces a new marking rf IS, then, m' = m + Nx . write (WW), writing (W), reading (R), and synchronizing (S). ] The incidence matrix, initial invariants are shown in Table 1. marking and ti t2 t3 t4 t5 t6 mO 11 12 13 LP -1 -1 1 1 n -1 WR 1 -1 -1 WW 1 -1 -1 R 1 -1 1 1 W 1 -1 1 n (n-1) S -1 -n 1 n n 1 1 Table 1. The Incidence matrix, initial marking and invariants for the example in Figure 2. The set of places consists of LP, WR, WW, H. W, and Si the set of transitions . consists of tX.....t6; mO Is the Initial marking; H, i2, and 13 are invariants. An Invariant (place invariant) v is defined the solution to the matrix equation vN = The central that theorem of this technique states Applying the fundamental theorem invariant, we derive the equations: for each (11) m'{LP)+ti/(WR)+m'(WW)+m1;R)+m'(W) = n (12) m'(R) + nm'(W) + m'(S) = n (13) m'(LP)+m'(WR)+m'(WW) = (n-1 )m'(W)+m'(S), The proof is as follows: v(m + = vm + = vm . Nx) Ox The use of invariants is very lucidly presented by Jensen ((15)) using the classic readers-writers problem. In Figure 2, the states indicate local processing (LP), waiting to where ni(X) is the number of tokens in the X-th place of marking m'and the right-hand sides are the results of vmO. It follows from 11, that the number of processes is invariant. It can be deduced form 12, that if one process Is writing, then no other process is writing or reading. From 13, however, little of immediate use is derivable since 13 is a linear combination of il and 12. Figure 2. Petri net model for the readers-writers problem. Figure .3., The conned and disconnect phases of the ECMA transport protocol standard (consonant with ISO standards). The proof of the llveness of the net is- as follows: 11 arid 12 admit the possibility that m'(LP), in'(R), and ni'(W) are nonzero. If so, then they enable tr and ta, tü, and te, respectively If not ..then iii'(WH ) + UAWW) = n r and in'lS) .= n. which enables either' tO oj; t4 .or both.,. At least one' ti'ansition la always enabled, therefore, the iiet la live. .Proofs of iäafeness. and other properties are substantially similar. Berthelob and.Terrat have applied these same techniques to validate the European' Couiputer Manufacturers Asiaociatlon (ECMA) transport protocol standai'd which la cpiisonant with ISO standards ((16)). Thè connect and disconnect, phases óf this protocol are represented in "ttié net .in Figure j. , ■ '' ' ' ' ' . . ' ' Ah additional technique they use la tliat óf net reductions. First, trivially, like labeled places are. coalesced into, one place, ■ thus bringing the two halves of the net together as one connected graph. Then, since there Is one token In P2 iff there is one tolten ih RC' and CC, P2 Is redundant and may be removed. Since transitions DC. AC', and CA are serially fired, they can coalesced into AC* thus elimlnatlng ttie need for Rc'and CC. These net reductions .were defined and studied by 'Berthelot, Roucalrol, and Valk ((17) ) and , their application here provides an interesting demonstration of how Petri net analysis can improve a protocol speoificatiqn. The reduced net, transition inatrlx, initial marking and invariants are given in Figure, 4 and Table 2. 11 i s shown in their paper that,this net is live, . safe at, level 1, and that .the , lhltlal marking la a home-state, i.e. is reachable from evei'y ma,i'king ' reachable, from the initiai-marking. Thus, this protocol is well behaved in the sense which Merlin defined. . Figure 4. A result of applying the net reductions technique: improved ECMA protocol specification. AC' DD pi / -1 P4 P5 RD CD PI' P4' P 5' RD' CD' -1 1 -1 1 ad 1 -1 -1 fd 1 -1 -1 DA 1 -1 -1 dd' -1 1 AD' I 1 -1 -1 fd' pa' 1 -1 -1 \ -1 -1 / ii 12 13 14 1 Table 2. The incidence matrix and Invariants for the reduced net in Figure 4. 4. Research Directions Berthelot and Terrat actually ran into some difficulty in modeling the other two phases of the ECMA protocol. They fabricated a solution to one of the problems by recourse to another form of the net called a predicate-transition net ((16)) which is capable of behaving as a fixed capacity queue which recognizes a finite set of message identifiers during the message transmission phase. The notation and analysis of predicate-transition nets is a little cumbersome, Jensen has done some work to bring this concept of the recognition of different tokens back within the fold of traditional net theory by formulating colored Petri net ((15)). This concept deserves more study in general and for its application to the present area of interest. Significantly, his paper includes an example of the design of a pi'otocol for a distributed database system. ■Also of interest Is a further investigation of the matrix approach for the regular time nets !0f section 2. With the exception of Molloy, none of the authors raentloned there use a linear algebraic approach, and yet this Is the single most useful analytic technique yet applied to Petri nets. One inherent prohlt-ici in the canonical formulation of Petri nets which stands in the way of even greater usage of linear algebra is that the Incidence matrix of the net is not square. The more powerful half ^of the matrix theory is concerned only with square matrices: the theory of determinants and eigenvectors. In so far as the eigenvectors of ia matrix represent, in some sense, the optimal ■flows through the system, they could be of great interest for the present application area. Finally, the 'pi'Otnise of general net simuiatlon 'and analysis systems needs to be realized. In ;thi3 direction, more work needs to be done on the general category of Petri nets so that ! different net variants can also be defined. As ■our knowledge of tool and environment ; construction matures along with general net theory, this should become a realizable dream. ((11)) Molloyj Integration of Delay and Througliput Measures In Distributed Processing Models, UCLA technical report, 1982. ((12)) Raiiiamoorthy and Ho: Performance Analysis of Asynchronous Concurrent Systems Using Petri Nets, IEEE Transactions on Software Engineering, A, 5. p.440-449, 1980. ((13)) Lipton: The Keachability Problem Requires Exponential Space, Yale University technical report, 1976. . ((14)) Sifakls: Structural Properties of Petri Nets, Lecture Notes in Computer Science, 64, p.474-483, Springer, 1978. , . ((15)) Jensen; Colored Petri Nete and the Invariant Method, Theoretical Computer Soience, 14, 3, p.317-336. ((16)) Berthelot, Terrat: Petri Net Theory fpr the Correctness of Protocols, IEEE Transaotions on Communications, 30, 12. p,2497-2505. 5. References ((17)) Berthelot, Reductions of Nets Lecture Notes in Spi'inger, 1980. Rpupairol, and Valk; and Parallel Programe, Computer Scienpe, 84; (.(!)) Petri:' Communication with Automata, : Information Systems Theory Project, technical report, 1965. ((2)) Peterson: Petri Net Theory and the Modeling of Systems, Prent'ice Hall, 19Ö1. ((3)) Jennings and Härtel: Petri Net Simulations of Communication Networks, Naval Postgraduate School technical report, 1980. ((4)) Smart: Analytic Performance Modeling of Concurrent Computer Systejns by Stochastic Petri Nets, Naval . Postgraduate School techical report, 1981. ((5)) Sunshine: Formal Modeling of Communication Protocols, USC technical report, 1981. ((6)) Noe, Crowley, and Anderson : Tlie Design of an.Interactive Graphical Net Editor, University of Washington technical report, 1974, ((7) ) Merlin! A Methodology for the Design and-Implementation of Communication Protocols, IEEE! Transactions on Conimunicationa, 24, 6. p.614r-621, 1976. :((8)) Coolahan and Roussopoulos: Timing ■Requirements for Time-Driven Systems Uslqg Augmented Petri Nets, IEEE Tt'anaac tl ons on Software Engineering, '9, 5. p.603-616, 1983. j((9))' Molloy: Perforinance Analysis Using 'Stochastic ■ Petri Nets, IEEE. Transactions on Computers, 31, 9. p.913-917, 1982. (do)) Genrlcri, Lautenbach, and Thlagarajan: Elements of Genei'al Net Theory, Lecture Notes in Computer Science, 84, Springer, 19Ü0, OSNOVNA NAČELA D F SISTEMOV J. SILCINB. ROBIC UDK: 681.519.7 INSTITUT „JOŽEF STEFAN' LJUBLJANA Koncept krmiljenja s tokom podatkov predstavlja bistven?) spremembo v naBinu izvajanja instrukcij napram klasičnemu sekvenCnemu izvajanju. Ti sistemi ne delujejo na podlagi krmilnega toka, zato tudi ne potrebujejo programskega Števca in pomnilnika s klasiCno funkcijo. V DF računalnikih postanejo instrukcije izvräljive v trenutku, ko prispe zadnji med zahtevanimi operandi, kar omogoBa vzporedno izvrševanje instrukcij. LogiCna posledica tega je visoka stopnja izkoriSCenosti inherentne paralelnosti, prisotne v algoritmih. Basic Principles ol Pata Flow systems. The data flow concepts is a fundamentally different way of looking at instruction execution in machinelevel programs - an alternative to sequential instruction execution. In a data flow computer an instruction is ready for execution when its operands have arrived. There is no concept of control flow, and data flow computers do not have program location counters. A consequence of data - activated instruction execution is that many instructions of a data flow program may be available for execution at once. Thus, highly concurrent computation is a natural consequence of the data flow concept. Uvod Vse von Neumannove arhitekture raöunalni-äkih sistemov imajo dve pomembni karakteristiki. Prvie, imajo globalni naslovljivi pomnilnik, ki pomni programe ter podatke in katerega vsebina se v skladu s programskimi instrukci-jarai pogosto aiurira. In drugifl, vsebujejo programski Števec, katerega vsebina Je naslov naslednje instrukcije, ki naj se izvrSi. Programski Števec se bodisi Implicitno ali eksplicitno aüurira in s tem doloCa sekvence instrukcij, ki se izvajajo. TakSno krmiljenje poteka programa je temeljna omejitev von Neu-mannovlh arhitektur, Se posebno pri vzporednem procesiranju. DF raKunalniki tdata flow computers) nimajo nobene od obeh zgoraj omenjenih značilnosti. Prvie, njihova struktura je zasnovana tako, da poteka procesiranje na osnovi vrednosti in ne naslovov spremenljivk, kar pomeni, da ni potreben globalni naslovljivi pomnilnik, saj ni nikakršnega naslavljanja. DrugiC, v DF sistemih ni niCesar, kar bi bilo podobno programskemu Števcu. Torej temeljijo ti sistemi na naCelih asinhronosti in funkcionalnosti, ki pravita, da so vse operacije funkcije (funkcionalnost), ki postanejo izvrSljive takoj, ko 50 na volje vrednosti vseh vhodnih operandov (asinhronost). Iz naCela funkcionalnosti sledi, da se katerikoli operaciji, ki sta izvršljivi, lahko izvrSita po kakršnemkoli zaporedju ali konkurenčno. Zgornji naCeli logiCno vodita do programskega grafa (data flow program graph), v katerem toCke ponazarjajo operacije, usmerjene povezave pa so nosilke vrednosti vhodnih operandov ter vCasih Se dodatnih informacij o delih izračunov, katerim pripadajo operandi. Programskemu grafu, ki je rezultat prevajanja programa v viSjem DF jeziku (data flow language), se dinamično prilagodi materialna oprema (data flow hardware), ki je sposobna izvajanja vsega inherentnega paralelizma, opisanega s tem grafom , kar ponazarja slika 1 CID. ° Raziskavo financira RSS po pogodbi C2-ai2A-106-8A Slika 1. p 1. rt am 1. üm .a v z p o e e ci np s t^ Veliko število algoritmov (npr. pri NP problemih) vsebuje inherentni paralellzem, ki pa v van Neumannovlh arhitekturah ni izrabljen v najveeji moiini meri. Arhitekture, ki bi to omogočale, bi npr. vse NP probleme prevedle na P,probleme, kar pomeni, da bi se eksponentna Časovna kompleksnost zniSala na polinomsko. Zakaj 7 Eksponentna'ea'sövnä ' kompleksnost d>-terministiSnih algoritmov za refievanje nekaterih NP problemov izvira Iz Števila potencialnih reSitev, katere mora algoritem sekvenflno generirati in preveriti. S paralelnimi arhitekturami pa bi bilo moC realizirati nedeter-ministiCne algoritme, ki bi bili sposobni sočasnega jgeneriranja potencialnih reSltev in izbire najustreznejše med njimi. V ta namen je potrebno definirati programski jezik, ki bi dovolj eksplicitno izra-Xal inherentno paralelnost algoritma, delini-ratl strukturo (strojni jezik), ki ja rezultat prevajanja programa v tem jeziku in ki omogoöa dovolj enostavno realizacijo z. materialno opremoj predvsem pa naj ohranja vso inherentno paralelnost algoritma. Oglejmo si segment programa, zapisanega v enem od von Neumannovih jezikov. nivo 0 1 1 nivo 1 I 2,3 nivo 2 1 A,5 nivo 3 s 6. Zaporedje izvrševanja stavkov 1,C2,33,C4, 53,6 izkoriäCa Inherentno paralelnost v največji meri. Operacije, ki so na istem nivoju, lahko kljub temu postanejo izvrSljive v različnih Časih - tedaj, ko so na voljo vrednosti vseh vhodnih operandov. Predpostavimo, da trajata Dperaoijl seštevanja In odštevanja po eno, množenja dve in deljenja tri Časovne enote. Čeprav sta operaciji 4 In 5 na istem nivoju, torej se lahko Izvajata,paralelno, bo postala operacija 'r izvršljiva pp Štirih, operacija 5 pa üe po treh Časovnih enotah. Torej Je Izvajanje programskega grafa popolnoma asinhrono. Pri cikličnih grafih lahko nastanejo dodatne teüave. Kadar v posamezni ponovitvi zanke naletimo na podatkovne odvisnosti med operacijami, to ne ustavi nadaljnih ponovitev, dasiravno predhodna ponovitev ni popolnoma konCana, saj so vrednosti vhodnih operandov akumulirane v doloöenih vejah grafa. Oglejmo si primer intuitivno konstruiranega cikličnega programskega grafa za IzraCun funkcije f(i) = 1! (slika 3). 1) 2) 3) A) 5) 6) P '= x+y i q 1= p/y J r i= x*p ) 6 1= r-q i t 1= r*p 5 rez 1= s/t J Standardni prevajalniki generirajo kodo, ki ustreza zaporednemu izvajanju stavkov segmenta, torej 1,2,3,A,5,6 , Vendar pa se lahko nekateri med njimi izvrSljo paralelno, npr. 1 ,C2,33,.4,5,6, kjer z Č2,3] opiSemp paralelno izvršitev stavkov 2 in 3. VpraSamo se, ali je to vsa inherentna paralelnost zgornjega segmenta. Oeitno je, da je Iz sekvenCnega zapisa pàralelnast te^ko razvidna, zato se poslužujemo programskih grafov. Programski graf, ki ustreza zgornjemu segmentu, je prikazan na sliki 2. frez = s/O Slika 2. TaCke programskega grafa ponazarjajo stavke (operaolje), usmerjene povezave pa sovpadajo 6 prehajanjem vrednosti operandov. Ker Je graf na sliki 1 aolkllCen, se lahko operacije, ki so na Istem nivoju, izvajajo pa^^" lelno. Operacija u je na nivoju 1, Ce je delilna najdaljše poti od zaCetne operacije do operacije w enaka 1. V programskem grafu na sliki 1 so operacije porazdeljene po nivojih na sledeC naCln; Slika 3. Poseben selekcijski mehanizem poskrbi, da se ob prvi IzvrSitvi blokov A In B uporabita povezavi a in ß ,ob vsaki naslednji pa namesto njiju povezavi y In i. Blok A inkrementlra vrednost operanda za 1, s katerim nato blok B pomnoüi prejSnji rezultat. Predpostavimo, da je za operacijo kopiranja (copy) potrebno pol, operacijo seštevanja ena in za operacijo mnoüenja dve Časovni enoti. Tedaj bi bile funkcijske vrednosti v toöki f zaporedoma 1! I 2! , 4! ... Vzrok za Izostanek rezultata 3! je v tem, da se zaradi hitrejšega izvajanja bloka A vrednost vhodnega operanda v povezavi e prekrije z novo vrednostjo, ne da bi blok B uporabil predhodno vrednost. V primeru, ko bi se blok B izvajal hitreje kot blok A, pa bi se ista vrednost vhodnega operanda v povezavi e uporabila veCkrat, kar bi Imelo za posledico, da bi se nekatere funkcijske vrednosti v toCkl f ponavljale, npr. 1(, 2! , 2! , 31 ... 12 Tako nI mogciBe s prisotnostjo katerekoli vrednosti vhodnega operanda deklarirati vozVi-Böa kot izvršljivega, saj lahko pripadajo vrednosti vhodnih operandov popolnoma razlitìnim delom izraäuna. Obstaja nekaj razliänih reäi-tev nastalega problema oziroma natiinov realizacije DF sistema C23. (i) CikliBni programski grat transformiramo v aoiklifini tako, da vsako ponovitev opi-Semo z aoiklitSniiD podgrafom. Tako transformiran grat iz slike 3 ima obliko kot je prikazana na sliki Ta reöitav zahteva velike koliCine programskega pomnilnika, zahteva pa tudi dinamično generiranje koda v primeru, ko je pogoj za izstop iz zanke izratiunan fiele v tlasu njenega Izvajanja. Obe zahtevi se odraüata kot pomembna pomankljivost v praktiCnih sistemih. nosilka vrednosti operanda _____nosilk^ potrditvenega signala Slika 5. Slika (ii> Ponovitve opiäemo z enim grafom, vendar se lahko ponovitev priCne äele tedaj, ko Je predhodna konöana. Taksna reöitev ne dovoljuje vzporednosti med ponovitvami in zahteva posebne ukaze ali posebno isaterlalno opremo, ki testira koneo ponovitve. (iii> Uporaba grafov je omejena tako, da je v veji grafa prisotna istočasno samo ena vrednost operanda C33. To pomeni, da se operacija lahko izvpäi le tedaj, ko so prisotne vrednosti vseh vhodnih operandov in ni v izhodni veji nobene vrednosti. Torej vrednost spremenljivega operanda v neki povezavi ne sme biti spremenjena vse dokler ni uporabljenA. Ko pa je enkrat uporabljena, mora postati neuporabljiva. Kljub sekvenönosti izvajanja je prednost tega naCina pred prvima dvema v moünl izrabi cevljenja (pipelining). Vsaka operacija po svoji izvršitvi obvesti svoje "starSe", da je pripravljena od njih sprejeti naslednje vrednosti vhodnih operandov. To stori s pomočjo dodatnih povezav - nosilk potrditvenih (akncwledge) signalov, kar kaüe primer na sliki 5. Z uvedbo potrditvenih signalov se Btevilo povezav, in s tem promet v grafu, podvoji. (iv) Poleg vrednosti operandov nosijo povezave Se dodatna informacijo o delih izratiu-nov, katerim pripadajo operandi C43. Pravimo, da e.o povezave nosilke znakov (token). Znaki imajo dodatne labele, ki vsebujejo indeks in nivo ponovitve. Te labele obiCaJno imenujemo barva. Operacije se lahko IzvrSi le tedaj, ko imajo vsi vhodni znaki enako barvo. Ta metoda uporablja popolnoma statiöno generiran kod in omogoöa maksimalno vzporednost izvajanja. Takäna reSitev zahteva poveBan pretok informacij po grafu in dodatna vozliÖCa za spreminjanje ter primerjanje label, kar ima za posledico bodisi dodaten fias za izradun label ali pa uporabo posebne materialne opreme. (v) Tudi tu so povezave nosilke znakov, poleg tega pa opravljajo Se funkcijo vrst (queue), kar pomeni, da so v njih znaki razvr-Söeni v istem vrstnem redu, kot so vanje prihajali. Povezava e s slike 3 ima tedaj obliko, kot jo prikazuje slika 6. C i + 2 1 + 2 i + 1 i 1 t Slika 6. Ta reSitev omcgoda enako stopnjo vzporednosti kot pri labaliranju, zahtava pa flakalne vrste, ki so prostorsko zahtevne. Programski graf, zgrajen po eneo od zgornjih naöel, Je struktura, ki utSifikovlto povezuju visok programski jezik z materialno opremo in popolnoma ohranja inherentno paralel-nast (slikia 1). Primerjavo opisanih petih realizacij DF si:iteina si oglejmo na primeru naslednjega programa i input d,e,f cCD3 = Q for i from 1 to 8 dp beo In aCi] = dCi] / eCi3 bCn = aCi3 * i Ci3 cCi3 = hči] + cCi-n eni output a,b,c Predpostavimo, da zahteva deljenje tri, množenje dye in seštevanje eno Časovno enoto. Namišljeni OF računalnik riaj ima Stiri procesne enote PI, P2, P3 in P C. C, G C. C, C, P.' b, Ò, b, ft a A b, o, o„ ■ 0, ■ O —L. Slika 8 oierja. Le-ta z njihovo uporabo olajSa delo prevajalniku pri odkrivanju paralelnosti. VeČina teh Jezikov pa Je nenaravnih v smislu, da v preveliki meri odraiajo arhitekturo, na podlagi katere so oblikovani, manj pa naßin, ria katerega prügramer razmišlja pri reSevanJu nekega problema.. Tako kot ostale oblike paralelnih računalnikov zahtevajo tudi OF računalniki (zaradi CimboljSe izrabe svojih lastnosti) posebne visoke programske jezike, t.i. ĐF jezike, ki pa ne sodijo med von Neumannove Jezike C53. Za razliko od konvencionalnih jezikov, kateri delujejo nad podatki s pomoCJo stranskih uCinkov, ĐF jeziki le-teh ne poznajo. Znana Je namreC zveza med učinkovitim paralelnim raCunanJero in odsotnostjo stranskih uCinkov. To lastnost imajo funkcionalni jeziki, ki delujejo izkljuCno na podlagi uporab funkcij nad vrednostni SledeCa lastnost, katero imajo DF jeziki, Je lokalnost uCinka, kar pomeni, da ukazi nimajo nepotrebnih, daleC segajoCih podatkovnih odvisnosti. Omejitve glede izvajanja ukazov temeljijo izkljuCno na 'podatkovnih odvisnostih. Posledica te zahteve je, da Je vsa informaoija, potrebna za izvajanje programa, vsebovana v programskem grafu. DF jeziki imajo v sintaksnem smislu veliko skupnih lastnosti s konvencial nini jeziki, saj uporabljajo podobne programske konstrukte, kot so prireditev, aritmetiCne izraze, pogojne stavke, iteracije in rekurzijo. Bistvena pa ^^ razlikujejo v semantiki. Za razliko od konvefi-oionainih jezikov, pri katerih identifikatcijp predstavlja naslovijivo enoto pomnilnika, p^ pr.i OF Jezikih predstavlja povezavo. Posledici takSne semantike OF Jezikov Je, da se lahko nekemu identifikatorju priredi vrednost samo enkrat, kar imenujemo pravilo o enkratni prireditvi. 8 preimenovanjem identifikatorjev lahko v neiterativnih deHh prograna problem večkratne prireditve uspeSno reSimo. Težave pa lahko nastopijo v zankah. Zato je potrebno pri definiranju zanke navesti <1) vhodne vrednosti vseh zanCnih identifikatorjev, (2) pogoj ustavljanja, (3) vrednost, ki naj bo rezultat ob koncu izvajanja zanke in (4) pravila po katerih se zanCnim identifikatorjem (ob vsaki izvršitvi telesa zanke) priredijo nove vrednosti. Za ilustracija si oglejmo primer algoritma za izraCun n!, zapisanega v DF jezikih VAL ( Value-oriented Algorithmic Language ) iac j,k > do if j = then = n,1 i O k gnd else iter j,k := j-1,k*J i end in ID CS3 1 J ni k while j O Q do neu J J-1 t Qea k k»j| k) (1) (2) (3) (A) (1) (2) (A) (3) A ic i t e K t ui C» a PF OF računalniki nimajo centralnega procesorja, temveC imajo procesni del, ki ga sestavlja mnoüica nekaj deset, sto ali tisoC procesnih enot. Vsaka procesna enota je enaka enostavni aritmetično logiCni enoti ali vhodno/izhodnemu procesorju. Nimajo niti pomnilnika, kakršnega uporabljajo von Neumannove arhitekture, zato pa imajo pomnilniäki del, ki ima potencialno veliko Število pomnilniSkih celic, v katerih se nehajojo vsi podatki o programskem grafu. Za DF raCunalnike je značilno tudi to, da ne uporabljajo sinhroniza-cijeke ure, programskega Števca in registrov. Zato pa ima arbitrarno vezje, ki usmerja izhode iz celic pomniIniSkega dela v ustrezna procesne enote procesnega dela in distribucijsko vezje, ki povezuje procesne enote s poo-nilniSkimi celicami. Arhitektura DF sistema j« prikazana na sliki 9 C7J. («oajm UL ntOCCIHA EMOTA PKOCIttlA MSTA mmnu-mJki ml puTumucij, «j PoriMn.. cetic» --fOMNIl.. CFIIC* AUiTa/tina vezjt Slika 9. Arbitrarno vezje ugotovi, katere operacije so godne za izvršitev in jih posreduje procesnemu delu. Le-ta Jih izvrgi in poSlJe delne rezultate distribucijskemu vezju. To vezje pa ugotovi katere operacije iz pomnilnifikega dela Čakajo na dobljene rezultate in Jim jih posreduje v obliki vhodnih operandov. SadaJ zopet nastopi arbitrarno vezje s Cimer se cikel ponovi. Z a k 1 j e e k Osnovne ideje, na katerih temelji DF koncept, segajo v pozna Šestdeseta Jeta. Z razvojem sodobne VLSI tehnologije je postala obstoječa (von Neumannova) arhitektura glavna ovira pri izkoriščanju paralelnosti v algoritmih. VLSI tehnologija pa je omogoCila smiselno uporabo materialne opreme v arhitekturah non-von (ne von Neumannovih) sistemov. DF koncept Šestdesetih let Je tako postal uresničljiv, saj omagoCa ta tehnologija izdelavo integriranih vezij s celo 100 noüioami. TisoC takih vezij, ki opravljajo usmerJevalno-povezovalno funkcijo (router), omogoCa uporabo celo 512 procesnih enot ali celiCnih blokov (celi block). Ce vsaka od procesnih enot izvrili milijon instrukcij v sekundi, potem nove arhitekture (ob pravilni izrabi paralelizmov) oao-goCajo skoraj milijardo inätrukoij v sekundi. VeCji OF projekti v .svetu potekajo t - na tllT, kjer skupina pod vodstvom J.Oennisa razvija OF sistem z rezinastimi procesorji tipa Am2903, - tudi na MIT, kjer skupina pod Arvindovim vodstvom gradi VLSI 6A procesorski OF računalnik z labeliranimi znaki (tagged-token), - na univerzi Utah deluje skupina pod vodstvo« A.Davisa, ki je sestavil prvi delujoCi OF raCunalni k, - na CERT v Toulousu, kjer deluje skupina pod vodstvom J.C.Syra na projektu LAU,, - na univerzi v Manchesteru gradijo eksperimentalni fflultiprocesorki DF Eisten z labeli-ranlitii znaki pod vodstvoo J.6urda in I. Uatsona in r- na univerzi Tokyo, raCunalnik Topstar, pod vodstvom T.Suzukija in J.Hotooke. Analize učinkovitosti, ki so jih izvršili na realiziranih OF sistemih, so pokazale ob-Butno Bastjvno izboljšanje pri reševanju nekaterih znanih algorltmoVi kot sta FFT (40i1) in Saussova eliminacijska - metoda (80:1). Ker so ti sistemi Sele v razvoju, obstaja tudi nekaj nereSenih problemov, kot sta problema vhodno/izhodnih aktivnosti in zadasnega pom-nenja C52. Ce3 p.D.Gajski, O.A.Padua, D.J.Kuck S R.H. Kuhn I 'A Second Opinion on Data Flow Machines and Languages', Computer,VoI.IS, No.2, Feb.1982, pp.58-69 ca3 J.B.Dennis t 'Data Flow Supercomputers', Computer,Vol.13,No.11,Nov.1980, pp.'r8-S6 CH3 I.Watson, J.Gurd I 'A Praotioal Data Flow Computer', Computer,Vol.15,No.2,Feb.1982, pp.51-57 C51 U.B.Ackerman i 'Data Flow Languages', Computer,Vol.15,No.2,Feb.1982, pp.15-25 Cbl J.Backus : 'Can Programming Be Liberated Irom the von Neumann Style? A Functional Style and Its Algebra of Programs', Comm. of the ACM, Vol.21,No.5,Aug.1978, pp.613641 C1.1 sT.Ageruala, Arvind i 'Data Flow Systems', Computer, Vol.IS, No.2,Feb.1982, pp.10-13 C73 J.B.Dennis, H.Y.-P.Lia & U.B.Ackerman : 'The «IT Data Flow Engineering Model', Information Processing 83, R.E.A.Mason (ed.), Elsevier Science Publishers B.V. (North-Holland), pp.553-560 O JEZICIMA ZA KONKURENTNO PROGRAMIRANJE KAO SREDSTVU ZA PROJ E KTO V ANJ E UPRAVLJAČKIH SISTEMA GOJO ŠTRKIĆ, DAVORIN NOVOSEL UDK: 681.326.7 ELEKTROTEHNIČKI FAKULTET BANJALUKA SADRŽAJ - U radu je dat osvrt na jezike za konkurentno programiranje kao sredstvo za projektovanje manjih upravljačkih sistema implementiranih na digitalnim procesorima (npr. mikroprocesorima). U analizu je uzet konkurentni paskal kao prvi takav jezik i jezici modula i edison kao manje glomazni jezici podesniji za manje sisteme. ABSTRACT - This paper gives analysis of concurrent programming languages as the tool for design of less complex control systems Implemented on digital processors (e.g. microprocessors). The analysis treats concurrent pascal as such first language and modula and edison as smaller languages more convenient for less complex systems. 1. uvod Upravljački sistem implementiran na digitalnom procesoru (npr. mikroprocesoru) se može shvatiti kao skup labavo povezanih procesa (zadataka) od kojih je svaki odgovoran za po jednu funkciju ili grupu odgovarajudih upravljačkih funkcija. Da bi opsluživao i upravljao sa više periferala upravljački sistem mora biti u sta-ž nju da istovremeno izvodi više procesa. Sa jed» nim procesorcTO prava Je paralelnost, naravno, nemogui?« pošto procesor može u Jednoir trenutku da izvodi samo jednu instrukciju. Zbog toga se zahtijevaju neki mehanizmi za alociranje proce-sorskog vremena za potrebe procesa kao i za upravljanje i sinhronizaciju istih. Pored toga upravljački sistem može imati zahtjeve da se opslužuje asinhroni ulaz/izlaz i da se odgovara na dogadjaje koji su vremenski uslovljeni (zahtjevi realnog vremena). Upravljačka logika može biti ugradjena u sam program i isti direktno implementiran na procesor. Medjutim, kod kompleksnijih sistema (koji sadrže vetfi broj procesa) najbolje je upravljačke funkcije ugraditi u poseban dio, tzv. kernel sistema, koji se može projektovati pomo-(5u Jezika za konkurentno programiranje |9{ . 2. uopSteno o konkurentnim jezicima Razvoj jezika za konkurentno programiranje Je joS uvijek u eksperimentalnoj fazi iako je relativno mnogo vremena prošlo kad se pojavio konkurentni paskal kao prvi jezik za konkurentno programiranje |4|. Začeci konkurentnog programiranja 'datira- ju iz vremena kada Je program izdijeljen i sek-vencljalne cjeline nazvane procesima koje su se mogle izvoditi asinhrono. Ako je svaki proces operirao na svojim sopstvenim podacima onda se uz pomod hardverskih mehanizama zaštite sistem od više procesa ponašao na sasvim predvidiv način. Medjutim, problemi su nastali kada je zatrebalo da procesi saradjuju oko dijeljenja nekih zajedničkih nedjeljivih resursa ili kada Je trebalo da «nrmđjnju na nekom za-jedničkosn zadatku. Za razumijevanje ovih problema pronadjeni su koncepti kritičnih regiona i semafora |7|. Dijkstra |l| je projektovao jedan multl-programski sistem koji se može shvatiti kao prvi primjer kako treba sistematski organizovati softver. Njegov multiprogramskl sistem je orga-nizovan kao jedna cjelina sastavljena od nekoliko hijerarhijski postavljenih slojeva koji fizičku mašinu pretvaraju u jednu virtualnu apstraktnu mašinu koja pruža značajne prednosti kako prilikom upotrebe tako i prilikom projek-tovanja iste. Ove osnovne ideje ugradjIvane su kasnije u gotovo sve jezike za konkurentno programiranje. Osnova na kojoj su jezici za konkurentno programiranje projektovani je da se išlo na odabiranje minimalnog broja osnovnih struktura koje bi bile dovoljne da programer pomoću njih može jednostavno i pouzdano graditi svoje programe. Kod svih programskih Jezika za konkurentno programiranje mogu se nadi tri zajedničke osobine a to su: 1. moguiSnost za predstavljanje konkurentnih aktivnosti (procesi, zadaci), moguđnoBt za ostvarivanje komunikacije i sinhronizacije izmedju tih konkurentnih aktivnosti, 3. mogućnost za obavljanje U/I aktivnosti u kojima su odradjeni problemi koji se javljaju sakriveni od programera korisnika. Svi jezici za konkurentno programiranje baziraju se na jednom rezidentnom programu često zvanom kernel ili nukleus datog jezika. Kernel jezika za konkurentno programiranje podržava implementaciju procesa, sinhronizacije i U/I aktivnosti. Dakle, on obavlja veoma bitne operacije upravljačkog sistema te na taj način odredjuje propusnost, efikasnost 1 pouzdanost upravljačkog sistema projektovanog pomodu datog jezika. Prema tome analiza multiprograraskog dijela jednog jezika za konkurentno programiranje veoma je bitna za analizu multiprogramskog dijela upravljačkog sistema. 3. KOMPARATIVNA ANALIZA JEZIKA: KONKURENTNI PASKAL, MODULA I EDISON Za analizu ćemo odabrati nekoliko jezika za konkurentno programiranje 1 razmatraćamo njihov profil prema potrebama projektovanja upravljačkih sistema implementiranih na digitalnim procesorima, Osvrnudemo se na konkurenr tni paskal, jezik modula |8| i jezik edison |6| jer svaki od njih sa sobom nosi neke nove koncepcijske postavke bilo da eu te postavke rezultirale iz iskustva nastalog na osnovu poznavanja prethodnih jezika za konkurentno i sistemsko pfogrćuniranje bilo da su ono uzrokovane tehnološkim napredkom koji je omogućio implementaciju odredjenih poznatih koncepata. Nesumnjivo je da je pronalazak apstraktnog tipa podataka bio osnova na kojoj su se bazirali viäi programski jezici za sekvencijal-no i konkurentno programiranje. Naime, došlo se do mogućnosti da se pomoću odredjenih sintaktičkih struktura opišu odredjeni podaci kao i operacije koja je moguće obaviti nad istim a da se to može izdvojiti u Jednu nezavisnu cjelinu koju je moguće nezavisno projekto-vati i testirati. Ta strukture pomoću kojih sa opisuju apstraktni tipovi podataka su različite u različitim programskim jezicima kako sekvanciJalnim tako i u konkurentnim. Kako mi ovdje vršimo osvrt na jezike za konkurentno programiranje to ćemo ovdje spomenuti jedino apstraktne struktura karakteristične za ove jezika. To su monitori, procesi i klase u ko- nkurentnom paskalu a moduli u jezicima modula i edison. Ako se kritički osvrnemo na konkurentni paskal može sa reći da je njegov koncept jedna dosta kompleksna tvorevina sastavljena od zajedničkih varijabli, procedura, rasporedj Ivanj a procesa i modularnosti. Poznato ja da monitor kao jedan od temelja konkurentnog paskala apstraktni tip podataka na kom se sve operacije obavljaju pomoću procedura koje pozivaju konkurentni procesi. U slučaju da više procesa istovremeno pozove monitorsku proceduru oni đa stati u listu čekanja i izvoditi se striktno jedan iza drugoga. Iako se koncept monitora jezika modula nešto razlikuje od koncepta monitora konkurentnog paskala on je u suštini isti s tim da su imena monitor i varijabla čekanja (queue) zamijenjeni sa Imenima vezni modul (interface module) i signal. Kod jezika edison pošlo se od jednog praktičnog Iskustva da je kod većine dobro izvedenih sistema takav slučaj da svaki proces potroši veći dio svog vremena na lokalnim podacima a manji dio vremena na izmjeni podataka sa drugim procesima i sinhronizaciji sa istim. Kad se toma doda činjenica da je tehnološki napredak omogućio implementaciju kritičnog regiona kog je mnogo ranije predložio Hoare |7| onda nije slučajno što je u edisouu izostavljen koncept monitora. Monitor se u edIsonu gradi programiranjem pomoću jednostavnijih koncepata kao što su varijable, moduli, procedure 1 WHEN iskazi. Prije pojave jezika edison u jezicima za konkurentno programiranje bila su poznata dva osnovna pristupa u implementaciji procesa. Jedan pristup je da se svaki proces nezavisno može pojaviti 1 nestati |3| a drugi je da proces poslije kreiranja stalno egzistira |5|. Pošto je i jedan i drugi pristup imao svoje nedostatke onda se pokušalo napraviti treći pristup u koji bi se ugradili elementi iz prethodna dva pristupa koji su se dobro pokazali u praksi. Na taj način su procesi u edisonu kao iiovijam jeziku za konkurentno progjramlra-nja prikazani pomoću konkurentnih iskaza cobegin ] do SLI also 2 do Sl2 also n do SLn end Kod ovog pristupa procasi se mogu dinamički pojaviti 1 nestati ali svi istovremeno. (Drojevi u gornjim iskazima služe zato da se svaki proces može dodijolitl posebnom procesoru ili pak da se npr. nieraorijski prostor može podjednako podijeliti madju procesima. Sa SL jo označena lista Iskaza). Za razliku od eđiaona kod Jezika konkurentnog paskala 1 modula procesi se opisuju pom-o Navedene funkcije se ne mosu definisati kao korisničke funk ciJe. Oriäinalna proärBinska implementacija Je izvršena aodifikaciJomtv - prevodioca LispKit Lisp Jezika na mažinski Jezik SECD mažine i - proširenjem simulatora SECD maiine. Rad se završava navođenjem nekih primena navedenih funkcija. An extension of LispKit Lisp lanauaäe ba EXPLODE and IMPLODE functionst Implementation and application. An extension of LispKit Lisp lanäuaäe [IJba EXPLODE and IMPLODE functions [S^iC^l ^^ described in this uork. The mentioned can not be defined as user's function.The oriainal program implementation is done hat - a modification of the compiler of LispKit Lisp lanäuaae into lanäuaae of SECD machinei and - an extension of the simulator of SECD machine. The work is finished ba aivinä some applications of mentioned functions. 1. Funkcionalni Jezici PosledtiJih nekoliko aodina smo svedoci naaloa porasta interesovahJa zs funkcionalne (aplikativne) jezike. Razvoj proaramskih Jezika baziran na strukturnom programiranju niJe dao ofcekivane rezultate. RazloS relativnoS neuspeha strukturnoa proaramiranJs lezi u tome što nije došlo do potpunoa raskida sa principima na kojima POČivaJu konvencionalni proaramski Jezici (FORTRAN i COBOL). Imperativni Jezicii kako oni stariJea tako i oni noviJea datuma(PASCAL>ADA) i imaJu osobinu da ne moau na relativno Jednostavan nafin ds opišu postojeće (poznate) matematičke strukture i obrstnof poseduJu strukture podataka i nare-dt>e koJe se ne JavlJaJu u matematici. Tako na primer ne postoJi matematićki ekvivalent poziva procedure (funkcije) koJi daJe razlifite vrednosti za iste vrednosti parametara. U matematici funkcija Je uređen par (x>F(x)) ade se svaki put z3 isto F i isto x dobija ista vrednost funkcije F(x). U matematici promenlJi-ve ne,moau da menJaJu vrednost» dok se izraz koristi samo da označi vrednost i u istom kontekstu isti izrazi imaju istu vrednost. Nedostaci imperativnih programskih Jezika proizlaze iž samoa nJihovoä koncepta. Imperativni proarami se izvršavaju na računarima Von Neumannovoa tipa. Von Neumann Je 1740 aodine dao model računsra koJi se sastoJi iz dva osnovna dfila! pasivne memorije i aktivnos procesora. U čisto funkcionalnim proarsmskim Jezicima navedeni nedostaci su otklonjeni. Funkcije se karakteriiu isključivo svoJim vrednostima. Ne postoJi bočni efekat a samim tim nema ni menJanJa vrednosti promenlJivih. Neposredno se realizuJu funkciJe višea reda (tj, funkcije čiJi su araument'i druae funkcije) kao i kompo-novanJe funkcija (vrednost rezultata zavisi isključivo od vrednosti aräumenata). Proaram Je funkcija čiJa Je vrednost rezultat izvršavanja proarama. 2. SECD mašina i EXECUTE funkcija SECD mašina Je model računara ne Von Neumann-ovoa tipa. Ime SECD potiče od imena četiri đlavna resistraj S - stack. Sadrži međurezultate izračunavanja vrednosti funkci Je(proarama) E - environment. Sadrži vrednosti dodeljene_ promenlJivim za vreme izračunavanja vrednosti funkcije C - control. Koristi se za čuvanje funkcija čiJa se vrednost izračunava» tJ. proarama na mašinskom Jeziku koJi se izvršava D - dump. Koristi se kao stek (maäazinska memorija) za' čuvanje vrednosti ostalih reaistara pri pozivu (računanju vrednosti) nove funkcije. Proaram napisan na LispKit Lisp Jeziku ili na mašinskom Jeziku SECD mašine Je valjani S-izraz tJ. S-izraz koJi ima vrednost. Ulazni i izlazni podaci proarama su S-izrazi. SECD mašina se može zadati kao funkcija EXEC. Definišino funkciju EXEC na sledeči način* EXEC(f*i3)=3PPla(f,a) Araumenti funkciJe EXEC su' - f I prevod funkcije f na mašinski Jezik SECD mašine i - a t araument funkciJe f. Vrednost funkcije EXEC Je S-izraz ciJa Je vrednost rezultat primene funkcije f na araument a. Funkcija EXEC> tJ. proaramska implementacija SECD msšinei može se definisati na sledeči načinCna Jednom Jeziku alaololikoa tipa)! exac t proc(friiar3s) t beälri (« vrše SB ifiiciJalizaćiJe Vi cucle t case ivslue(c3r(c)) of beäin 1 ... 2t... 3. Prevodilac t COMPILE funkcija Prevodilac LispKlt Liap Jezika na oašinsKl Jezik SECD mašine se noža zadati Kao funkcija COMPILE. DeflnišittO funkciju COMPILE na sledeči način! COMPILE:ec Je osnovna tunkciJa proära-mskoa siaiulatora SECO mas Ine . Pa raoiet ri funkcije B>;oc BU) - fnl pokazivač prevoda funkciJa f na inaiinsKi Jeziki arast pak3;:ivač liste sraumenata funkcije zadiite u obliku S-izraza. Vrednost funkcije exec Je pokazivač prvoa elementa steka S (rezultat izračunavanja), prevodilac automatski dodaje dve naredbe I AP (applu) - mašinski kSd 4 i STOP - oiaäinski kod 21. F Je korisnička funkcija napisana na LispKit Lisp Jc::iku. F* Je prevod funkcije F (napisane na LispKit Lisp Jeziku) na aašinski Jezik BECIi mašine. FunkciJa COMPILE moie se definlsati na LispKit Lisp Jeziku na sledeči načini (letrec coniPile (campile lambda(e) (cooip e (Quote nil) (ouote (4 21)>>) (comp laobda (e n c> (if (atom e) ...... (if (ea (car e> (ouote Quote)) ( ........) (if (ea (car o) (ouote add)) ( ........) (if (ea (car e) (auote sub)) ( ........) (if (ea (car e) (auote letrec)) ( ........) 2.1 Specifičnosti proaramske implementacije Implementacija Je izvršena na proaramskom Jeziku PL/1 računara IBM 370/3031 «epubličkoa zavoda zs statistiku SR Srbije u Beoaradu. Implementacija Je pojednostavljena zahvalJuJuči sledeči!» osobinama PL/1 Jezika; ~ Jednostavno manipulisanJe raznim tipovima podataka ~ moaučnost redefin i sanJa p romeniJiv ih. Na taJ način se lako dobiJaJu cifre broJa koJi Ja character tipal - koriščenje promenlJivih promen1 Ji ve duzine ~ moaučnost konkatenac i Je podataka characlt'r tipa i broJava u PICTURE formatu. Neki detalji implementacije. ■• celi brojevi su oblika binaru flHedCil.O) (riä duiini 32 bita). Smcsteni su u nizu ivaluo koJi Je istos tips kao i broJsvi - character promenlJive su uiaksimalne dutine 15 ( tiP chBracter( 15) Visryina ) i smettene su redom u niz strinastort- istoa tipa - niz lvalue moie da sadrži tri tii.i nodalaka 1 ) ceo broJ 2) indeks character promenlJive u nizu St r inastore 3) cele brojeve koJi su kodovi pojedinih na redbi - memoriju tine pet nizova I i va lueicar>cdri i satom»isnumb. Car i cdr su istoa tipa kao i lvalue dok su PoslednJa dva tipa bit(l) tJ< sluie kao indlKatort - vrednosti nizova car i cdr su pokazivati na elemente lista u memoriji - niz isatom Je indikator da li Je objekat na koati PokazuJu car ili cdr atom ~ niz isnumb Je indikator ds li Je obJekat na koaa pokazuJu car ili cdr broJ - podaci se prikazuju na sledeči način 1 - broj 1 isato«! & isnuiub (broJ Je numerički atom) - character 1 isčitom & "isnumb (character Je simbolički atom) - lista I "isatom I " isnumb - svi pokazivači su tipa binaru fi«ed(31iü) - skupljat otpadaka(aarbaae collector) Je tipa mark and collect. 3.1 Specifičnosti proaramske implementacije prevodilac LispKit Lisp Jezika na mašinski Jezik SECD mašine napisan Je kao korisnička funkcija LispKit Lisp Jezika. Ovakav način konstrukcije prevodioca poseduJe sledeče dobre osobine ! - proaram za prevodenJe Je Jako kratak - omoa^čeno Je Jednostavno uvođenje novih funkcija (u LispKit Lisp) i odaovaraJučih naredbi u proaram za prevolenJe - paJednostavl.^uJe se otkrivanje i ispravljanje äreiaka u tako dobiJenom prevodiocu. Prevodilac koJi se kunstruižo Je Jedna korisnička funkcija (označimo Je sa compilel). Preve-dimo dobi Jenu funkciju compilai! compi 1 e ( compi le 1 ) = comp i 1 el*^ compilel* Je prevod funkcije comp i 1el(p rus ire-noa prevodioca) na rndsifitki Jezik SECD macine. Umesto funkciJe compile uzn.imo coon-ilal 1 ponovimo istu operaciju. «■ ** comPl lei (cod.p ilei ) = eomp i U »lucjJu da Je konstruirani (prošireni) prevo-dil.-ic i^sr-javan nJeaovi prevodi coinpilel*" i compilel * nornJu biti i dent Ićni(keo dva prevoda iste funkei.U» cuuipilel). Da bi -iprovali ovakvu proceduru na početku luoramo da poseduJemo već prevedenu tačnu verziJ'i ^l^•vodloCrf (makisr i minimalnu) na mašlnskl Jezik, SECD mašine kaJa če biti osnova za dalJa praSlrenJa, 1. Funkcije EXPLODE i IMPLODE Sastavni dea atoma duzine fi (u oznaci Siv in>5l) Je nisi-H od n slovsi cifar« ili specijalnih znakova tako da t>c! atom može prikazati u obliku aS^b adi; su d i b niske od m^ .m^ znakova ili praline uiike. 4.1 Definicije funkcija EXPI ODE i IMPl.ODE EXPLORE Je unai-na funic; i Ja. Araument jo vslJani S-izraz. Dozvoljena vredno'-t araumentti Je simbolički atom ili neneaativan numerički atom pri ct^mu se zriak f» alo postoJii ianoriše. Vredfiost 1'üiikciJö Je lista svih sastavnih (Jelova vrodnotti ar'lumenta dužine 1. Primer ! explode((primer))= (f rimer) eKPiorle(< 132451) =(1 3 2 4 5) ewPlodt<(+99675)) =(9 9 Ć 7 3) IHPLGDE Je unarna funkcija, Argument Je vslJsni S-lzrs2, DozvolJeris vrednost aiäumehta Je lista nenesativnih numeričkih atoma ili lista atoma čiJi Je prvi eleoient simbolički atoDi I a ostali elementi su sioibolićki ili neneaativni numerički atomi. Vrednost funkcije Je atom Jednak kònkatenaciJi redom svih oleme-nata vrednosti aräuoientai Primer I implode()=FL/1 4.2 Materaatićku osobine funkcija EXPLODE i IMPLODE Neka Je Važi 1) 2) 3) 4) 5) 6) A = {>i ! K Je atom} L = {y ! a Je lista ćiJi su €■ 1 ementi sastavni delovi stoma duzine I ) L'= ,{z 1 2 Je lista ćiJi Je poslednJi element atom nil} L c L' BKPlode 1 A ,--> L implode i L' --> A na dati m. skupovima ( A i L ) e>!plode .i implode su biJekciJe eKPlode i implode su inverzne funkcije u oblasti definissnosti t Y« t A S Yz L.' vazi implode ( e>ip lode ( K )) i eKPlode )-i = 2 . Npr. . explode ( implode (( ma ma))>-i=(ma ma) 4.3 Proaramska implementacija funkcija EXPLODE i IMPLODE 4.3.1 Prevod na mašinski Jezik Definisimo prevod funkciJs LispKit Lisp Jezika na mašinski Jezik. Neka Je n lista imena promenlJivih» a e valjani S-iaraz. Obeležimo sa e»n prevod S-izraza e za datu listu imena pro-menlJivih n. Ra2motrimo izraz. (EXPLOPE^e) on ima tzv. osobinu cistoä rezultata [l3• Prvo se izražuna vrednost S-izraza i upisuJe na vrh steka S.Zatim se na nJu primeriJuJe expl naredba BECD maäine i dobi Jenom vrednosću zamenJuJe vrednost na vrhu steka S. Na taJ način se menJa saijo sadržaj steka S tJ. funkcija ne produkuJe bočni efekat. Izrazu (EXPLODE e) oddovara sledeči maŽinski kodi , (EXPLODE e)»n = e»n I (evipl) t Je oznaka za konkatenaciJu. Analoanoi (IMPLODE e)»n = e»n I (impl) . Izraz (IMPLODE e) takocfe ima osobinu čistoa rezultata. Naredbe e«pl i impl se izvräavaJu na sledBĆi liaiin) E (eHpl(a),s) E C D (a. 6) E (impl.C) D --> (impl(a).s) E C D 4.3.2 Modifikacija Prevodioca i SEED mašine Prevodilac LispKit LisP Jezika na mašinski Jesik SECD maline Je proiiren sledećim seämentom t . (if (eo (car e) (Quote explode)) ( comp (car (cdr a) ) n (cons (ouote 33) c) ) (if (ea (car e) (auote implode)) ( comp (car (cdr e) ) n (cons (uuote 34> c) ) 4.3.3 Modifikacija SECD mašino Procedura exec se prosiruJf blokovima narwdbi koJi odsovaraJu novouvederiim oxpI i iiiipl n.j)-e-dbama SECD msSine. Pl;/1 prosram koji realizuJe takvu SECD mašinu Je sledećea oblika! exec i proc returns( binara fixed(3lF0) >) l = sambol > lvalue(t)»sto re(true)> f = s«mbol i iv3lue(f)=atoro(f3lse)l 6 = con5 ( a rsis I ni I ) ) e = rii I ) d==nii: c = fn» rep^nili /* dodelJivanJe početne vrednosti rt-aistrima SECD mašine i specijalnim atomima t (true) i f (false) »/ do until ivaiue(car(c)>=21)( 6elect(ivalue(car(c>))i kihen(l> beai ni end) /* Id */ when(21) I /« stop */ . when(33) beSinJ /* expl */ if is3tom(c8r(s) ) then doi s-cons(explode(car(s))icdr(s))i' c-c.il(c)i end i e 1 s e -do i /» poruka o a relic i */ stop! end i when(34> beaini /» impl */ if "isatoi!i(car(s) ) then, do f s = cons(i mplode(ca r(s))icd r(s))> C'cd r(c ) ( e n d f else dot /* poruka o arešci */ . StOPÌ endt end F other beain» /» poruka o aresci »/ stop! 33 i 34 mašine i su kodovi expl l'impl naredbi SECD end! end» /» select end) /* do until */ retu rn(ca r(s >)i end! /* exec, Explode i implode su realizovane kao funkciJe. Parametar funkcija explode i implode ja adresa vrednosti araumonta, Vrednost funkcija Je adresa i z raciina te vrednosti. U slučaju funkciji' explode! - Ako Je vrednost ar-iumefita simbolički atom po-, stupak Je sledeči. a) izračunava se duzina simboličkođ atoma b) konstruiše se listo čiJi su elementi sastavni delovi dužine 1 ton «tomai - Ako Je vrednost aräuments numerički atom konstruiši; su liüta čiJi su elem.inti castavni delovi duJ.ine 1 ( cifre ). e^iplode ! proc(ni) returnsCbinaru f i>:e 0) ) ( dcclsre m binsra fi»edt31>O)■ ^ /% adresa arduiuenta »/ poK binaftì fi>:ed(31iO). /* »dresa aräumenta koJi se dodaJe listi »/ povratak binsira f inedt 3110 ) i /* adresa rezultata funKciJe »/ J ' binara f i>ied< 15»0) i len binara f i>;e /t sadrži dužinu simbol iòKotl atonia */ sta character(15) var» /% sadrii siabolitKi atom */ prora . character*15) i /* bazs iz koJe se dobiJaJu delovi atoma */ pronil character* 15) van služi kod dodavanja eleoienata tipa char -oni su tipa char(15) var kao èto Je napomenuto t/ broJ pic '(14)z9' def prom pos<1) • /% za dobiJanJe cifara numerićkoa atoma t/ znakdS) char(l) def prom posd) » /» za izdvajanje sastavnih delova araumenta. Ako su sastavni delovi cifre konverzija če biti automatski izvrSena pri dodeli broJevnoJ promenlJivoJ t/ if issambol(m) then do) sta-strinästore(Iv3lue0) i dobiJanJe dekadnih cifara.BroJ Je oblika ' v!>!>iM>iKM« ' đde >;-ovi prikazuju cifre broJaippomenJiv broj K~ova u zavisnosti od vslifine arsumenta $/ rep=nil» do J = 15 to 1 ba -1 whi le < znak ( J ) "= ' ')» pok-number) /» vrednost araumenta Je broJ »/ lvalue*pok>=znak(J)> /» dodelJuJe mu se vrednost »/ rep=cons(pok » rep> I /« dodaJa se na poćetak liste ♦/ endt povratak=repi rep=nil> return(povratak)) end( endI /* eHpiode */ Funkcije sambol i number vrie zauzimanje nove memorlJske lokacije postavljajući istovremeno odaovaraJuću bit kombinaciju nizova isatom i isnumb« u tom trenutku nema slobodnih memo- riJskih loksclJa poziva se skuplJac otpadaka koJi može da unirti do sada konätruisanu listu. Za eliminlsanJe ove mogućnosti služi promenlJi-va rep. Ona Je alobalna za e>'.ec (dakle dcklari-S3na u alavnoJ proceduri) i markira se pre poziva skupljača otpadaka. Na taJ način do sada konstruisana lista ostaJe ntpromenJena. F'olto nam niJe potrebna za druae svrhe van funkciJe explode ona ima vrednost nil. U slucaJu funkcije implode postupak se aasttiJi u konkatenaciJi elemenata arauiiient liste. implode 1 proc(iii) returns(binara f i>;od ( 3110) ) { declare m binara f i!0 ) i /* adresa arđumenta */ rez characterOO) var Initial*'')» inici Jal izuJena rezultat kao praznu nisku */ help binara fiütd*31.0). /» adresa rezultata funkcije */ broJ binara f i>:ed(31 • 0) > /» numerlCka vrednost rezul . »/ J binara f i>:ed ( 151 0 ) i len binara flxeddSiO) def rez posd)» /* sadrii dužinu rezultata.Automatski se postsvlJa */ rezi Pie '*14)z9' , /* za dobiJanJe cifsra numerićkoa atoma */ polJed5) chsT(l) def rezi poSd) i /t za izdvajanje cifsra araumenta ako Je ori numerički atom niJe_ntl bitd) init*'l'b)i /t indikator da 11 se dolio do poslednJea atoma ( koji treba da Je nil ) t/ if issamboltm) I isnumb(m) then if issaubol(m) then if strinastore*ivalue*B))= Etrinastore*ivalue(ni1) then return(nil)) /* imp 1 ode(ni 1) = ni1 */ . else dot /» poruka o slrescl »/ stop i end» else dot /« poruka o areici »/ stop f end) else if iscons(car(iii) ) then doi /* poruka o areici «/ StOPt end» else if, issamboKcsrtm)) /* rezultat Je simbollikl atooi »/ then dol do Mhile(niJe.nil t len<=15)> /» Ispitivanje uslova iscons(C3r(«)) i ako niJe nsstavlJa se t/ if issambol* car(m)) then re2=rezll strinastore* i va lue(car*m)))i /t 3ko Je element si«bol nJeaa konkateniramo na rezultat »/ else if izpoz*C8r(ra)) then . do» ■ rezl=ivalue(cer(m))l /t raspakuJemo as t/ do J=1 to 151 if polJe*J)" = ' ' then rez=rezl(poljo*J)i /» konKateniramo cifre »/ end I end» e 1 se dol /* poruka o areici »/ EtopI end» ii=cdr*m)l /* sledeči element liste */ if iseamboKa) I isnumb*«) then if issanboKa) then if StrInastorelivalue *■))-strinastore*i va lue(nil) then niJe_nil='0'l;>l else dol /» Poruka o drežci »/ stüpi end! ülse düi - /* porukii o >)re'lcl */ stop» end i end) /* do while */ if len>15 then dot - /* poruka o areici */ stop I end! else dui helP = symtiol > /» simbolički atom */ iv3lue(help>=storei /% vrednost */ return(he Ìp)i end! end» else dot do while(niJe_nil l lenClS) /* ako Je car0)i return( iva lue ( n > ) =3bs < i va lue ( n > ) )!, end! /* izpoz */. end! /» implode */ Ovakav način inplementaci Je IhF'LODE bio Je u&lovlJen moaucim araumentima funkciJe. ftko Je aräument IMPLODE rezultat funkciJe EXPtOHE koJa Je za svoj arsiument imala numeri čki atoi» loaično Je da i rezultat bude takav. Međutim bilo koJa operacija nad rezultatom EXPLOJDE ne menJa tip podatka.Tako Je IMF'LOBE (cdr (EXPLODE ) ) (REVERSE LAMBDft(X) (REV X (QUOTE NIL) > ) (REV LAMBDA(X Y) ( IF (Ell X (QUOTE NIL) ) Y (REV (CDR X) (CONS (CAR X) Y) ) ) ) (EQUAL LAMBDA(X Y) ( IF (ATOM X) (EQ X Y) (IF (ATOM Y) (EQ X Y) (IF (EQUAL (CAR X) (CAR Y) ) (EQUAL (CDR X) (CDR Y) ) (QUOTE F) ) ) ) ) > Primer 2, Definisati unarnu funkciJu KONT. Vrednost araumenta Je numerički atom. Vrednost funkciJe Je .t ako vrednost araumenta sadrži naJmanJe dve iste cifrei a f u suprotnom. N a p r i m e r . KONT(1232567)=t N0NT(-723269)=t KtlNT(-7234&9) = f K0NT(8723469)=f üadatal'. ćemo resiti na dva načina! a) Primenom EXPLODE funkcije: (LETREC KONT (KONT LAMBDA ( X ) , (IF (LEO X (QUOTE O) ) . (ISPITAJ (EXPLODE (SUB (QUOTE 0) X))) (ISPITAJ (EXPLODE X) ) ) ) (ISPITAJ LAMBDA ( NEISPITANO > (IF (EQ NEISPITANO NIL) (QUOTE F> (IF (MEMBER (CAR NEISPITANO) (CDR NEISPITANO) ) (QUOTE T) (ISPITAJ (CUR NEISPITANO)•) ) ) ) (meheier lambda (t n> Definitati unarnu funKclJu MARK. Vrednost aräuments Je lista atoma koJa može.da sadrži iste specijalne atone - markore. Vrednost funkcije Je prazna lista ili lista atoma dobljenih konkatenaciJonè atoma kbji ee nalaze izmerful - po5etk3 liste i prvoä oarkerai - dva sueedna markerar - poslednJea markera i kraJa listet - poćetks i kraja liste (ako liste na sadrii marke r)• Markeri se izostavljaju. Za marker uzeti t, NA primeri nARK((3 23*12*« 12 «as d« a*»« i)>° (a23 12 12 asd»a »*i) HARK((PRI MER « 3 « FUNK CI JA « HARK « ))' ( PRIMER 3 FUNKCIJA MARK ) Sledeći proäram Je režonJs zadatka! (LETREC MARK (MARK LAMBDA(X) (REVERSE (IZBACI NIL X NIL) )) (IZBACI LAMBDA (ARO X REZ) (IF (EQ X NIL) (IF (EQ ARO NIL) RE2 . (CONS (IMPLODE (REVERSE ARU)) REZ) ) (IF (EQ (CAR X) (QUOTE »)) (IF (EQ ARO NIL) (IZBACI NIL (CDR X) REZ) (IZBACI NIL (CDR X) (CONS (IMPLODE (REVERSE ARC)) REZ))) (IZBACI (CONS (CAR X) ARO) (CDR X) REZ ) ))) (REVERSE LA^!BDA(X) (REV X (QUOTE NIL) ) ) (REV LAMBDA(X V) (IF (EQ X (QUOTE NIL) ) i (REV (CDR X) (CONS (CAR X) Y) ) ) ) ) Primer 4. Defiriisati unarnu funkciju FIND, Vrednost araumerita Je lista atoma. Vr&dnost funkciJi3 Je lista nei zmenjenih atoma izuzev onih diJi su prvi sastavni delovi duiine 1 simboli < ili > . Ovi atomi se dele na dva atoma: < (ili >) i ostatak atoma (funkcija FIND ina primenu kod složenih MATCH funkcija), Na prlojerl FIND((ad6Bf a fhan >> sdf> rfC ><<<))= (adssf a < aasd > fhän > > sdf> rf< > <<<)) FINĐ(( beoarad >ssv3 sava < dunav avala ) Sledeči proäram Je resenJe zadatka! (LETREC PINO (FIND LAMBDA(X) (FLATTEN (REVERSE (IZBACI X (QUOTE NIL)))) ) (IZBACI LAMBDA(ULAZ IZLAZ) (IF (EQ ULAZ (QUOTE NIL) ) IZLAZ (IF (NUHBERP (CAR ULAZ) ) (IZBACI (CDR ULAZ) (CONS (CAR ULAZ) IZLAZ) ) (LET (IF (AND (OR (EQ (CAR PKVI) (QUOTE -f)) (EQ (CAR PRVI) (QUOTE V))> (NOT (EQ (CDR PRVI) (QUOTE NIL)))) (IZBACI (CDR ULAZ) (CONS (CONS (CAR PRVI) (CONS (IMPLODE (CDR PRVI)) (QUOTE NIL))) IZLAZ)) (IZBACI (CDR ULAZ) (CONS (CAR ULAZ) IZLAZ))) (PRVI EXPLODE (CAR ULAZ) ) ) ) ) ) (FLATTEN LAMBDA(X) (IF (EQ X (QUOTE NIL) ) (QUOTE NIL) (IF (ATOM (CAR X)) (CONS (CAR X) (FLATTEN (CDR X))) (APPEND (FLATTEN (CAR X)) (FLATTEN (CDR X)) ) ) ) ) (APPEND LAMBDA(X Y) (IF (EQ X (QUOTE NIL)) Y (CONS (CAR X) (APPEND (CDR X) Y)))) (REVERSE LAMBDA(X) (REV X (QUOTE NIL) ) ) (REV LAMBDA(X Y) (IF (EQ X (QUOTE NIL) ) Y (REV (CDR X) (CONS (CAR X) Y) ) )) (NUHBERP LAMBDA(X) (EQ X (ADD X (QUOTE 0) ) ) )) 6. Zaključak PoJam atom ozna&ava nedeljiv objekat, Hedutimf uvo(JenJem funkcija EXPLODE i IMPLODE, izvr&en Je prodor u strukturu atoma. Atom Je postao delJiv do na dužinu 1. Atomi dužine 1 Bu nedeljivi. Ovo Je od posebnoä znažaJa za simboličke atome Jer su se numerliki atomi pomoću celobroJnoa delJenJa mođli i ranlJe rastavljati na sastavne delove (cifre). Navedene funkcije imaJu veliku primenu u obradi teksta. One ss ne' mosu reali&ovatl kao korisničko funkcije već Isključivo kao uöraciene funkcije na nivou SECD mašine. 2e Literatura fi] Peter Hendersor. Functional Proäraaioiina ! application arni iaiplementation Prentice-Hall Internationalf ine.i Londoni 1980. fa'! Patrick Henru Uinston t •• Berthold Klaus Paul Horn Lisp Addi&on-Uesleu Publishina Coaipanuf Readinäi Massachusetter 1981. fsl Patrick Henra Uinston Artificial into 11 iaence Addison-Wesle« Publishina Coiiipanu» Readinđt Massachusetts! 1977< pij J. Uarlinatori.P. Hertd«r(>eri>A,. Turner Functional proärsdiiiiiria and its. application Cambridge Università Press.» Caoibridäei 1982. j^a] V. StoJković i drudi Lisi-Kit Lisp Jezik»verziJd AKL Bilten za nauku i informatiku SAPV» 1984, Zahvaljujemo se koleđinici Mariji Külas iz Instituta za matemat iku u Novom Sadu na suäestiJama. informatica i:i5 Vabilo k sodelovanju Posvetovanje in seminarji Informatica '85 Nova Gorica, 24.-27. soptemtier 1985 Posvetovanje 18. jugoslovansko mednarodno posvetovanje za raiunalniško teiinologijo in uporabo Nova Gorica, 24.-27. september 1985 Seminarji Izbrana poglavja iz računalniške tehnologije in uporabe Razstava Razstava računalniške tehnologije, uporabe, literature In drugih računalniških naprav, z mednarodno udeležbo Roki . 1. april 1985 Zadnji rok za sprejem lormularja 8 prijavo in 2 izvodov razširjanega povzetka 15. Julij 1985 Zadnji rok za sprejem končnega teksta prispevka Symposium and Seminars Informatica "85 Nova Gorica, September 24th-27th, 1985 Conference 18th Yugoslav internaUonal Conference on Computer Technology and Usage Seminars Selected Topics in Computer Technology and Usage Nova Gorica, September 24th-271h. 1985 Exhibition Exhibition Ol Computer Technology, Usage, Literature and Other Computer Equipment with International Participalion Nova Gorica, September 24lh-27th, 1985 Deadlines April 1, 1985 Submission of the application form and 2 copies of the extended summary July 15, 1985 Submission ot the fulUaxt of contribution ANALYSIS OF CODE GENERATION FOR A COMMUTATIVE ONE-REGISTER MACHINE UDK: 681.3.325.6 DUŠAN PETKOVIĆ SIEMENS ÀG, MÜNCHEN, F. R. GERMANY ABSTRACT. This paper presents a development of the analysis of code generation for the set of expressions with conunon subexpressions for the conunutative one-register machine. A heuristic based on this development is shown to produce code size better than 3/2 that of an optimal coding for any expression. This result underestimates the results known in the literature. ANALIZA GENERISANJA KODA ZA KOMUTATIVNU MAŠINU SA JEDNIM REGISTROM - U radu je data analiza gene- . risanja koda za skup izraza sa zajedničkim podizrazima za komutativnu mašinu sa jednim registrom. Heuristika zasnovana na ovom razvoju daje kod čiji količnik u odnosu na optimalan kod je bolji od 3/2. Tako dobijeni rezultat predstavlja poboljšanje u odnosu na rezultate dobijene u drugim radovima. 1. introduction We consider the problem ef generating optimal code for a set of expressions. If the set of expressions has no common subexpressions then a number of efficient optimal cods generation algorithms are known (Sethi, Ullman (1970) and Aho, Johnson (1976)). Howevér, generating optimal code for expressions with common subexpressions for a one-register machine has been shown to be NP- complete by Bruno and Sethi (1970). Aho, Johnson and Ullman (1976) have shown that the problem remairfl NP- complete even for simple expressions. They also developed a heuristic which has a worst case- ratio of 3/2 for one-register (noncommu-tative)machine. In the same paper they discussed code generation for commutative machines and showed that 3/2 is a worst case ratio for the generalized top-down greedy algorithm for a commutative one-register machine. At the end of that paper Aho, Johnson and Ullman proposed some open questions, and one of these open questions is: how closely can a polynomial time heuristic approximate optimal code generation problem on a commutative one-register machine? This paper presents a uniform development of a linear algorithms for the commutative one-register machine along with an analysis of bounds. A heuristic based on this development is shown to produce code size better than 3/2 that of an optimal coding, using only optimal number of computational and store instructions. 2. BACKGROUNDS AND DEFINITIONS In translating a source program into machine language most compilers first translate the source program into an intermediate form,which is then subsequently transformed into the final object program. The intermediate code represents a flow graph where each node represents straight line block (basic block). within a basic block the flow of control is sequential. Each basic block in a flow graph can be represented by a DAG (directed acyclic graph - Aho, Oilman (1971)). Figure 1 shows a basic block and its corresponding DAG. + e n^^-b + c leaf. A Interi-A tree has We call node n^ a right child of node ng, and a left child of node n.. Accordingly, we call node n^ a right parent of node n, and node n^ a left parent of node n,. A node with no children is^called a node with no parents is called a root, or nodes are nodes that are not leaves, is a DAG, where each node (except roots) always only one parent (left or right). A machine program is a sequence of instructions. The length of a program is the number of instructions it contains. One-register (noncommutative) machine is limited to three basic types of instructions: r-<-m (load instruction) , r<-r op m (op- instruction) and m-^r (store instruction) , where r is register, and m is any memory location. (a noncommutative machine has the left operand always in register and the right operand is always in memory). A generalization of this machine is a commutative one-register machine. Commutative one register machine is one where, for each instruction of the form r*— r op m, there is also an instruction of the form r m op r. That means, the order of the children of any node is permutable, as far as code generation is concerned, although the operator itself may not be commutative. 3. HEURISTIC TECHNIQUE The following, assumptions are made: 1. Code generation is limited to that for a commutative one-register machine. 2. All generators produce no useless instructions, i. e, instructions which can be deleted without changing the value of the program., 3. All generators never store the same value more than once. 4. Input to the code generators is a DAG,with possible multiple roots, each of which has to be stored. 5. Commutativity and associativity of expressions are not conserned in this paper. Assumptions 2. and 3. restrict the class of all programs which evaluate any DAG. This restriction serves only to eliminate very inefficient programs. From any program P we can easily construct an equivalent program which fulfilles the assumptions 2. and 3. (in the time proportional to the length of P). Theorem 1. The function f: A-»B, where A is a set of all computational Instructions re^iui-red in an optimal coding of a particular DAG, and B is a set of all internal nodes of the same DAG, is bijective. stored in generating optimal code for the tree with commutative operators. Using the result of that paper we can state the following Algorithm IB. Step 1. Take à tree t from the algorithm lA (there must be at least one such tree, if the particular basic block has common subexpressions) , Go to step 2. Step 2. If t. is a worm, go to step 3. If t^^ is not a, worm, apply algorithm 2 from Sethi and Ullman (1970) to the tree t to get all internal nodes which have to be stored. Mark those nodes. Prune each marked node from his parent node. Each resulting sub-tree t^ is à unique left chain. Go to step 3. j Step 3. Take a next tree t, from the algo- , rithm 1A and apply step 2. If there is no such tree end. Algorithm IB gives us a second subset of nodes which has to be stored in an optimal coding. From the discussion above we can state following theorem: Theorem 2. The number of store instructions required in an optimal coding of a particular DAG for the commutative one-register machine is the sum of: a) all roots; b) all internal nodes with multiple parents; c) all marked nodes by the algorithm IB. Figure 2 shows pruning DAG D, first using algorithm 1A and afterwards using algorithm IB (2a shows a DAG D, 2b shows the pruned sub-DACs t, after applying algorithm 2A to DAG D, and 2c shows the pruned sub-trees t. after applying algorithm 2B to sub-DAG t|. j Proof. Directly from the assumption 2 above. Before we state the theorem about the number of- store instructions, required in an optimal coding, we need further definitions and algorithms. Definition 1. A left chain is a tree with following property; each interior node of a tree has always a leaf as a right child. Definition 2. A worm is a tree with following property: each interior node of a tree has at least one leaf as a child. Each left chain is a worm, but each worm must not be left chain. Algorithm 1A. Given a DAG D, a forest of trees T may be constructed by pruning all interior nodes with multiple parents from eacli of thoir parent node in the DAG. Each resulting tree t;, is labeled, identifying the leaves that replace the pruned sub-DAGs. The forest of trees from a given DAG is unique. Algorithm 1A gives us a subset of all nodes which has to be stored in an optimal coding (it is obvious that all internal nodes with multiple parents has to be stored). Besides there, we need to store some nodes of a pruned trees. If the pruned tree t, is a worm we need not to store any node of t^at tree. If the pruned tree is not a worm we need to store at least one internal node of that tree. Further, the commutative machine allows us to think of all operators to be commutative. Sethi and Ullman (1970)showed (in Algorithm 2 of that paper) which internal nodes has to be 2b) 2c) 28 From now on, we use the results of Carter (1982) to get the wishing heuristic.' That means the rest of this paper is equivalent to the paper of Carter, however we concern the conunuta-tive one-register machine instead of nonconmiu-tative one. Definition 3. A Data Flow Dependency graph (DFDEP) is constructed from the forest W of worms derived from a DAG D after applying the algorithms 1A and IB. The vertices of the DFDEP graph correspond to the worms of W. An arc from vertex w^ to vertex w. specifies that the worm w. uses the resulti of the worm w. as an operand. J Theorem 3. The DFDEP graph from a forest W of worms derived from a DAG D is itself a DAG. Proof. Since D is DAG, and the forest W only groups directly connected nodes of D into worms without introducing new arcs, the DFDEP graph must be. acyclic. Definition 4. A Data Flow Ready set (DFREADY) is the set of vertices from the DFDEP graph with no outward arcs. The elements of the DFREADY set correspond to those worms whose operands have already been coded or were leaves in the original DAG D and are therefore ready to be coded. By the acyclic nature of the DFDEP graph, the DFREADY set will always have at least one member, as long as there is at least one worm to be coded. The process of coding a DAG may be viewed as a multi-step algorithms. First, a forest of worms is ccaistructed from the DAG. Second, a DFDEP graph is constructed, and a DFREADY set from it. The final step is an iterative coding. A member of the DFREADY set is removed along with the corresponding vertex in the DFDEP graph. , All inward arcs are also removed from that vertex. Any vertices now without outward arcs are added to the DFREADY set, and the worm corresponding to the removed DFREADY element is coded, ending with the store operation. This iteration continues until the DFREADY set is empty meaning that the DAG is coded. The DFDEP graph and DFREADY set should be viewed as dynamic data structures, which "are modified during the course of code generation. A code generation could be characterized by the algorithm it uses in constructing the forest of. worms, and the transformations it performs on the DFDEP graph. (The DFREADY set is, always derivable from the current DFDEP graph so it is not required as part of characterization.) Let C be a class of code generators which produce code when forest W is constructed by algorithm 1A and algorithm 1B, the. DFDEP graph and the DFREADY set. Tfie difference between members of the class is the method which is used to select from the DFREADY set. the order of selection determines the number of load instructions for internal nodes required in the coding. (The number of leaf loads can be easily shown to be the number of worms whose left operand is a leaf in the original DAG D.) Lenuna 1. Given a DAG D, it is possible to construct the forest W (as specified in the algorithms lA and IB), and the DFDEP graph in linear time. Proof. For the construction of trees t. (as output of algorithm lA), we need only two transversals of DAG D, first marking all vertices with multiple parents and building trees tj second. Building treés is similar to a left-to-^right, depth-first DAG copy, where marked vertices indicate where to create new trees. Once created, the marked vertex is flagged to prevent creation of multiple copies of shared sub- DAGs. The construction of second subset of nodes with algorithm IB and the construction of the DFDEP graph is similar. Theorem 4. All of the code generators in C produce code which is better than 3/2 the size of an optimal coding of any DAG D, and at least one generator runs in linear time. Proof. This proof shows the bound, and the existence of the linear time code generator. Let S, be the number of internal nodes in each worm w, , where S, > 1 / and n is the number of worms. The result of each worm must be stored, so the number of computational instructions and store instructions is: n 5 To maximize the ratio of generated code to optimal code, assume that optimal coding requires only one load instruction for each worm: SIZE(Cj^(D) ) SIZE(Optimal(D)) tl s (S^+1) + 1 it (S.+1)t1+n-1 k=1 n-1 EI (S +1) + 1 = 1 k = 1 S 'V^- <1 n-1 2n+1 < Lemma 1 showsthat DFDEP graph construction can be done in linear time. DFREADY set construction and selection can be simulated by using worms in a post-order encounter during a depth-first traversal of the DFDEP graph. Therefore, there is at least one code generator in e which runs in linear time. The result is code, which uses the optimal number of computational and store instructions, thereby insuring object code better than 3/2 the size of an optimal coding. 4. CONCLUSIONS This paper shows a first step to the uniform development of the analysis of code generation for a commutative one-register machine. First, we showed the theorem which gives us the number of computational instructions, required in an optimal coding of a particular DAG with commutative one-register machine. After that, we showed the theorem which gives us the number of store Instructions required in an optimal coding of a particular DAG with commutative one-register machine. This theorem is based on two algorithms, algorithms 1A an^ IB. These two algorithms are dependent from each other; that means, the output of algorithm 1A is the input of algorithm IB. Then, using the results of Carter we showed the final theorem, which gives us the wishing result. This analysis of code generation for a commutative one-register machine uses only optimal number of computational and store instructions. In this paper we did not concern at all optimizing of load instructions. If the load instructions would be optimized, we would get a heuristic, which gives us better results than this one. To get a better heuristic will be the aim of the future work. PARER/SHORT PAPER/ TECHNICAL REPORT REGISTRATION 5. REFERENCES This appltcalion should be typewritten 1) Aho, A.V. and Ullman, J.U; - Optimization of Straight Line Programs, SIAI4 Journal of Computing, Vol. 1,,NO. 1,pp. 1-19, 1972 . 2) Aho, A.V. and Ullman, J.D. - The Theory of Parsing, Translation and Compiling, Vol. II: Compiling, Prentice Hall, 1973. 3) Aho, A.V., Hopcroft, J.E. and Ullman, J.D.-The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974. 4) Aho, A.V. and Johnson, S.C. - Optimal Code Generation for Expression Trees, Journal of ACM, Vol. 23, No. 3, pp. 488-501, 1976. 5) Aho, A.V., Johnson, S.C. and Ullman, J.D. -Code Generation for Expressions with Common Subexpressions, Journal of ACM, Vol. 24, No. 1 , pp.- 146-160, 1977. 6) Aho, A.V. and Ullman, J.D, - Principles of Compiler Design, Addison-Wesley, 1977. 7) Aho, A.V. and Sethi, R. - How Hard is Compiler Code Generation, in: Salomaa, A. and Steinby, M. - Automata, Languages, Programming, Lecture Notes in Compiler Sciences, No. 52, pp. 1-15, 1977. 8) Anderson, J.P. - A Note on Some Compiling Algorithms, Comm. of ACM, Vol. 7, No. 3, pp. 149-150, 1964. 9) Bruno, J. and Sethi, R. - Code Generation for a One-register Machine, Journal of ACM, Vol. 23, No. 3, pp. 502-510, 1976. 10) Carter, L.R. - Further Analysis of Code Generation for a Single Register Machine, Acta Informatica, Vol. 18, pt. 135-147,1982. 11) Nakata, I. - On Compiling Algorithms for Arithmetic Expressions^ Comm. of ACM, Vol. 10, No. 8, pp. 492-494, 1967. 12) Redziejowski, R.R. - On Arithmetic Expressions and Trees, Comm. of ACM, Vol. 2, pp. 81-84, 1969. 13) Sethi, R. and Ullman, J.D. - The Generation of Optimal Code for Arithmetic Expressions, Journal of ACM, Vol. 17, No. 4, pp. 715-28, 1970. 14) Stockhausen, P.P. - Adapting Optimal Code Generation for AritJimetic Expressions to the Instruction Sets Availablé on Present-Day Computers, Comm. of ACM, Vol. 16. No 6, pp. 353-354, 1973. 15) Waite, W.M. - Optimization, in Bauer, F.L. and Eickel, J. (ed.) - Compiler Construe-' tion: An Advanced Course, Springer Verlaci. pp. 549-602, 1974. n t or ma U 'J 1. TiUa ot the Paper: ...................................................... 2. EKtended suiranaty (approximately 1000 words) should tje enclosed. 3. Program Category ol the Paper (circle appropriate choice) 1. Survey ot Technology and/or Usage 2. System Architecture 3. Process Control 4. Systems Development Tools 5. Small Business Systems 6. Usage in Education 7. Personalcomputers 8. CAD/CAM Systems 9. Anilicial Intelligence and Robots 10. Computer Networks 11. Filth Computer Generation 4. Classilication of the Paper (circle appropriate choice) 1. Paper 2. Short paper 3. Technical report 5, Author(s): ................................................................... Organization: .............................................................. Street: ......................................................................... Postal Code:.......................City: .................;............ Country: ...........................................................'......... Dale:...................................Signature: ..................... This application form together vyith two copies ol extended summary must reach the following address before April 1. 1985: Informatica 85, 61116 Ljubljana, p.p. 2, Yugoslavia PRIJAVA REFERATA t KRATKEGA REFERATA / STROKOVNEGA POROČILA INFORIvlATICA 85 61116 Ljubljana, p.p. 2 JUGOSLAVIJA Prijavo izpolnite s pisalnim strojem 1. Naslov referata ........................................................... 2. Razširjeni povzetek (približno 1000 besed) priložite prijavi. 3. Programsko področje referata (obkrožite ustrezno številko) t. Pregled tehnologije in uporatje 2. Arhitektura in zgradba računalniških sistemov 3. Upravljanje procesov 4. Sistemski razvojni pripomočki 5. Mali poslovni sistemi 6. Uporaba pri izobraževanju 7. Osebni računalniki 8. CAD/CAM mikrosistemi 9. Umetna inteligenca in rotjoti 10. Računalniške mreže 11. Peta računalniška generacija 4. Razvrstitev referata (obkrožile) 1. referat (pomembnejše delo) 2. kratek referat 3. ix)ročilo 5. Avtorji: .........................-. Delovna organizacija: ....................... Ulica: ................................................ Poštna Številka:...................Kraj: ... Država: ............................................. Datum:................................Podpis: Prijavnica, skupaj z dvema kopijama razširjenega povzetka. mora prispeti najkasneje do i. aprila 1905 na naslov: Inlormatica '85. 61116 Ljubljana, p.p. 2 INFORMATICA 2/85 IBMOVSKI OSEBNI RAČUNALNIK PETRA III UOK: 681.3.06 Petr« III ANTON p. ŽELEZNIKAR Ta del eianka opisuje začetno preizkušanje računalnika Petra, pomen začetnih nastavitev konflguracijskih stikal, začetne nastavitve skakačev, nastavitev frekvence VCO za krmilnik upogljivih diskov in osnovni V_I sistem (ROM BIOS) za ibmovski mikroračunalnik (z nekaterimi podatki o operacijskem sistemu MS-DOS). Petra - An IBM-like Personal Computer III This part of the article deals with initial testing of Petra computer, with meaning of configuring switches, with initial jumper settings, tuning of VCO frequency for floppy disk controller and with basic I_0 system (ROM BIOS) for an IBM-like computer (describing some basic concepts of MS-DOS). 11. Začetno preizkušanje Ko smo ploščo (ali plošče, če jih Je več) z integriranimi vezji do konca povezali (izdelali, ožlčlll, pospajkall), jo (ali jih) začnemo preizkušati v temle zaporedju: (1) Izmerimo vse napajalne napetosti z voltmetrom, . merimo pa tudi šum (ki je lahko posledica slabega filtriranja) na napajalnih sponkah posameznih integriranih vezij z osciloskopom. (2) Preverimo delovanje vseh oscilatorjev, in sicer na sponkah 8 (sysclkO), 12 (sysclkl) in 2 (sysclk2) vezja I 34 (8284A, list 1), na sponki 8 vezja I 10 (M1116-6M, list 5) in na sponkah 10 (1,2288 Mhz) in 11 (uart-clk) vezja I 69 (74 LS 393, list 7). (3) Preverimo delovanje resetiranja in vgradimo dodatno tipko, kot prikazuje slika 9. Na sistemskem naslovnem vodilu preverimo vse naslovne vode. In sicer na sponkah O vezij I 44, I 38 in I 50 (list 1). Pri resetira-nju se posamezni registri nastavijo takole: register IP (ukazni kazalec) CS (kodni segment) DS (podatkovni segment) SS (skladovnl segment) ES (posebni segment) statusni register vsebina OOOOh Offffh OOOOh OOOOh OOOOh resetiran S-4k -CZ)— iNUlifS •f X3«- C10 M HES- T T r/PAfA ZA, J:.Ž. Slika 9. Dograditev tipke za resetlranje, tako da je omogočeno začetno preozkušanje sistema in ročno resetlranje sistema, kadar sistem "obvisi". Na naslovnem vodilu se tako takoj po rese-tiranju skladno s stanjem IP in ps v razpredelnici pojavi naslov OffffOh ali 1111_1111_1111_1111_0000 ki ga preizkusimo z osciloskopom na posameznih naslovnih vodih (dvajsetih), tako da jponavljarno pritiskanje na resetirno tipko. (4) Po preizkusih točk (1), (2) in (3) začnemo inicializlrati posamezne krmilnike, ko vpisujemo različne programe v ROM. Ta ROM vstavimo v I 85 in na pomnilni lokaciji OffffOh (oziroma CS:IP = ffff:0000) imamo (Intersegmentni) skok na začetek Iniolali-zacijskega programa (o tem kasneje). številka stikala nastavitev stikala funkcija stikala 1 1 nastavitev števila di- 2 i 1 ■ . skovnih enot: 1 enota 3 1 diskovna enota 8 col 4 ■ 1 enojna zapisna gostota 5 1 tlpkovničnl_video' vmes 6 1 barvni vmesnik tipa 7 0 80 X 20 8 0 neuporabljeno 12. Začetne nastavitve konfiguraoljskih stikal Za konfiguracijska stikala ST na listu 7 naj tako velja tole: Nastavitev konfiguracijskih stikal pod oznako ST na listu 7 moramo predpisati (definirati). Tako bo s položajem posameznih stikal oločena uporaba enega, dveh, treh ali štirih diskovnih enot dimenzij 5,25 ali 8 col, V_I hitrosti (izražene v baudih), uporaba vgrajenih konzolnih kanalov ali posebnih vtičnih enot (ibmovska tipkovnica in ibmovskl monokromatični ali barvni vmesnik). Pri izdelavi tkim. ROM BlOSa (Basic I_0 System) ločimo dve osnovni možnosti nastavitev konfiguracijskih stikal, in sicer: - Imamo sistem z vgrajenim kónzolnim kanalom (kanal O s prlključnico tipa RS-232 in z uz-nako . P 13 na listu 7 prek vezja tipa USART 8251A, tj. I 70 na listu 7). - Imamo sistem z ibmovskim tipkovničnim vmesni-^ kom in z video vmesnikom (to sta posebni tiskani ploSčl, ki ju vtaknemo v proste pri-ključnio0 P 1, ... P 9 na listu 2). Tako dobimo prvi primer nastavitve oljskih stikal v tabeli 1. Tabela 1 konfigura- Številka stikala nastavitev stikala funkcija stikala ■ 1 2 0 . ■ ■'1 . ■ nastavitev števila diskovnih enot: 2 epoti 3 0 enota 5,25 cole (ne 8) . 4 ■ 0 dvojna zapisna gostota ■ . . s; 0 vgrajeni kanal RS-232 6 7 8 ■ ■ ■ , ■ o;. ■ 0 .. ■ 0 nastavitev hitrosti termlnalskega kanala, in sicer 9600 baud STl, ST2 ST3 ST4 ST5 ST6, ST7 ST8 število uporabljenih diskovnih enot diskovna enota 5,25 cole ali 8 col enojna ali dvojna zapisna gostota terminal tipa RS-232 ali tipkovnl- čni_video vmesnik i pomen nastavitve teh stikal je od- -Visen od nastavitve ST5; če je ST5 = O (izključeno), določajo ST6, ST7 in ST8 kanalski takt od 110 do 9600 baud terminala tipa RS-232i če je ST5 = 1 (vključeno), določata ST6 in ST7 video način, ST8 pa ni uporabljeno Podrobne stikalne funkcije pa so tele: Stikali STI in 3T2 določata število diskovnih enot;! STI ST2 število diskovnih enot 1 1 . 1 0 1 2 1 0 3 . 0 0 4 Stikalo ST3 določa dimenzijo diska: ST3 dimenzija diska 0 5,25 cole 1 8 col- Stikalo ST4 določa zapisno gostoto: ST4 O, 1 zapisna gostota dvojna gostota (disk 5,25 cole) enojna gostota (disk 8 col) Drugi primer nastavitve konfiguracijskih stikal je prikazan v tabeli 2. Stikalo ST5 določa termlnalski tip: ST5 0 1 termlnalski tip ' konzola RS-232 (navadni terminal) tlpkovnični in video vmesnik Stikali ST6 in ST7 določata pri ST5 = 1 video način (vtične plošče za tipkovnico,^ monokroma-tični in ali barvni monitor): ST6 ST7 0 1 0 1 video način monokromatični vmesnik 80 X barvni vmesnik 40 X 26 barvni vmesnik 80 X 25 neveljavno 25 Stikala S'f6, ST7 in ST8 določajo pri ST5 takt kanalskega tipa RS-232: ST6 ST7 ST8 kanalska hitrost (baud) 0 0 0 9600 1 0 0 4800 0 1 0 2400 1 1 0 1200 0 0 1 600 1 0 1 300 0 1 1 150 111 110 13. Začetne nastavive skakačev Tabela -3 Skakač list pomen nastavitev EPROMov 182,83,84,85: 2k 4k 8k 16k SKI SK2 SK3 SK4 SK5 SK6 SK7 3 3 3 3 3 3 3 1.0 0 0 0,1 1 1 11 0 0 0 0 1 1 10 0 0 0 1, 1 1 omogočltev uporabe ROMa; nastavitev čakalnega stanja SK15A SK8 5 5 taktna frekvenca, disk 5,25 cole taktna frekvenca, disk 8 col SK9 3K10 5 5 časovna konstanta, disk 8 col časovna konstanta,disk 5,25 cole SKll SK12 5 5 časovna konstanta, disk 8 col časovna konstanta,disk 5,25 cole SKI 3 SK14 5 5 taktna frekvenca, disk 5,25 cole taktna frekvenca, disk 8 col SK15 SK16 5 5 regulacijska nap, disk 8 col regulacijska nap, disk 5,25 cole SK16A SK17 5 5 taktna frekvenca, disk 5,25 cole t ktna frekvenca, disk 8 col SK18-1 SKie-2 SK18-3 SK18-4 SK18-5 SK18-6 SK18-7 SK18-8 SK18-9 6 6 6 6 6 6 6 6 uporaba motorjev št. 2 in 3 eno_dvostranska diskovna enota, uporaba motorja št, 1 uporaba motorja št, 0 uporaba glave št. 0 konstanten signal READY-uporaba glave št. 1 uporaba glave št. 2 uporaba glave št. 3 SK20 SK21 R14 5 5 5 prednastavitev VCO frekvence, disk 8 col prednastavitev VCO frekvence, disk 5,25 cole natančna nastavitev VCO frekven. Oglejmo si najprej preglednico vseh skakačev, ko imamo tabelo 3. Oglejmo si nastavitve skakačev pri uporabi ep-romskih vezij za 4 k zloge, brez čakalnega stanja in pri uporabi diskov 5,25 cole. Najprej imamo: SKl SK2 SK3 SK4 SK5 SK6 SK7 0 1 1 0 0 1 0 kjer pomeni 1 stik in O prekinitev. Nadalje Je: SK8 SK15A SK9 SKIO SKll SK12 SK13 SK14 0 1 0 1 0 1 1 0 SK15 SK16 SK16A SK17 SK20 SK21 0 1 1 0 0 1 SK18-1 -2 -3 -4 -5 -6 -7 -8 -9 X 0 X 1 0 1 0 0 0 X pomeni O ali 1 v odvisnosti od možnosti. 14. Nastavitev frekvence za VCO S potenciometrom R 14 (list 5) moramo nastaviti nominalno frekvenco 8 MHz za VCO (vezje I 4, list 5). To nastavitev opravimo pri neaktivnem signalu VCOSYNC (ta nastaja v vefcju I 21, nožica 24, list 5 in se poäilja v vezje I 8, nožica 5, list 5j), ko Je vrednost napetosti na nožici 2 vezja I list 5 (to vezje je napetostno krmiljeni oscilator 74 S 124 ali 74 LS 629.) približno 3,2 V. Potenclometer R 14, list 5 se v tem stanju nastavi na frekvenco 8 MHz in to frekvenco merimo na nožici 7 vezja I 4 s frekvenčnim merilnikom. Predhodno smo ustrezno nastavili tudi skakače in konflguraoljska stikala, kot je bilo opisano. 15. Osnovni V_I sistem (BIOS) za ibmovski mikroračunalnik 15.1. U v o d Operacijski sistem MS-DOS (wlcrosoft Disk Operating System) je mogoče namestiti praktično na vsak mikroračunalniški sistem, ki uporablja mikroprocesor 8988 ali 8086. Tudi različni ibmovski operacijski sistemi Japonskih, ameriških in evropskih proizvajalcev temeljijo na licenci sistema MS-DOS (vključno s podjetjem IBM). MŠ-DOS je zgrajen tako, da je del tega sistema dostopen proizvajalcu ali uporabniku mikroraču-nalniškega sistema in ta del se imenuje BIOS (Basic Input Output System) all natančneje ROM BIOS (BIOS V ROMu). IBM Je določil svoj ROM BIOS, kl ga je seveda avtorsko zaščitil..S to zaščito naj bi med drugimi zaščitami dosegel, da bi bili zakoniti konkurenčni posnetki računalnikov tipa IBM PC drugačni, manj konkurenčni, predvsem pa čimbolj sistemsko in programsko nezdružljivi z IBM PC. Vendar je s to zaščito IBjM dosegel le to, da samo nekateri njegovi storitveni in aplikativni programi niso izvršiJivi,-na konkurenčnih posnetkih, vsi drugi programi in bistveni poslovni in tehnični informacijski sistemi pa se lahko izvajajo na konkurenčnih sistemih dostikrat hitreje in bolj optimalno kot na ibmovem izvirniku. Pri razvoju ROM BlOSa moramo upoštevati strukturo ibmovskega ROM BlOSa, za katerega imamo .zbrane osnovne podatke o programskih prekinitvah (rutinah) v tabeli 4. Prekinitev tipa INT kk kk 0 1 2 3 4 5 6-7 8-OFH lOH IIH 12H 13H - 14H 15H 16H 17H 18H 19H lAH IBH ICH IDH lEH IFH 20H-3FH 40H 41H 42H-FFH Uporaba posameznih .'subrutin Del jenje z ničlo'iz^ 8088, 8086 Enojni korak (pri DEBUG) Nemaskirna parnostna napaka Točka prekinitve 1:pri, DEBUG) Prestop . . '' . . Pisanje na zaslon Rezervirano ' Prekinitev iz 8259 ;'-Video prekinitev, 15 funkcij Preslikava za naprave Obseg pomnilnika' / Diskovna prekinitev,-.le funkcij za upogljivi in 14/funkcij za trdni disk ■ ;r : • ' Komun Ikacljska prek ini t,è v, 4 funkcije .i S' Kaseta , ■ : Tlpkovnična prekinitev, 3 funk-: cije Tiskalniška prekinitev, .3 funkcije Osnovni vstop v ROM. Navezovalni nalagalnlk Prekinitev časa dneva, 2 funkciji ■ Prekinitev zaradi prekinjene tipkovnice Časovniška prekinitev (bitje) Kazalec v parametričen seznam za video inicializacijo Kazalec v seznam diskovnih parametrov Kazalec za grafični znakovni vzorec Prekinitve DOS Preusmeritev diskovne prekinitve za sisteme s trdnimi diski ' Kazalec v seznam parametrov za trdni disk Rezervirano ali uporabljeno za prekinitve DOSa, Basica ali za uporabniške prekinitve 15.2. Programske prekinitve tipa INT procesorja, 8 0 8 8 . , , Ukaza, povezana s programsko prekinitvijo in podatki o njiju so zbrani v tabeli 5. Ukaz programske prekinitve se lahko uporabi v ■dva namena, in sicer: - v programih, ki se testirajo: Ulaz programske prekinitve, ki ima dolžino enega zloga (mne-monika tega ukaza Je INT brez operanda, kar ustreza tudi INT 3; njegov strojni kod oziroma zlog je Occhi za INT 3 pa dobimo Iz tabele 5_operaoije pri kk = 3 naslov odmičnega dela 12, tj. Och in naslov seginentnega dela 14, tj. Oeh), pokliče rutino, katere naslov začenja • na lokaciji 0000:000c (glej tabelo 5, operacije). Ta rutina je navadno del testlr-nega paketa (DEBUG) in se uporablja za obdelavo točk prekinitve v programih, ki Jih testiramo. Iz tabele 4 vidimo, da ta semantika ustreza ibmovskemu ROM BIOSu. - za klicanje subrutin, katerih naslovi se nahajajo v prvih 1024 zlogih pomnilnika: Pri uporabi dvozložnih ukazov INT kk (kk =0, 1, 2, .... Ofeh, Offh) za programske prekinitve lahko pokličemo katerokoli subrutiho od 256 subrutin, katerih naslovi se skladno , s shemo CS:IP (kodni segment ; ukazni kazalec = 2 zloga : 2 zloga) nahajajo v prvih 1024 zlogih pomnilnika na lokacijah O, 4, 8, Och, lOh, 14h, 18h, Ich, ... , ÓfDh, Of4h, Ofah, Ofch. Ukazi programske prekinitve imajo to dobro lastnost, da'uporabijo le en al i dva zloga programskega pomnilnika v primerjavi s petimi zlogi medsegmentnega- klica tipa CALL. Razen tega mnemo-nika objektni kod Število zlogov status I T operacije INT 1100 llOv 0 0 (SP):=(SP)-2; ((SP)):=(zastavice); v = Ò: (I):=0! T:=Oj cch; 1. (SP):=(SP)-2; ((SP)):=(CS); v = 1: (SP):=(SP)-2; ((SP)):=(IP)! Ocdh; ■ 2 (CS):=(vektor(segmentnl_del)); (IP):=(vektor(odmlčni__del))i IF v = 0 THEN vektor(odmlčni_del):=(Och); vektor(segmentni_del):=(Oeh); END IF; IF v = 1 THEN vektor(odmični__del) :=((kk 4)h); ktor(segmentnl del):= ((kk 4+2)h); END IF; IRET Ocfh 1] X X (IP):=((SP)); (SP):=(SP)+2; (CS):=((SP)); (SP):=(SP)+2; (zastavice):=((SP)) (SP): = (SP)^-2; Vrnitev iz prekinitvene servisne rutine Tu je (x) vsebina registra x, ((SP)) Je vsebina lokacije (SP), ((y)h) Je vsebina heksadecimalne lokacije y, kk pa Je operand ukaza INT, se pri teh ukazih avtomatiSno reSiJo v sklad vse zastavice. Klici tipa INT imajo obvezno vrnitev z ukazom IRET (tabela 5, operacije). Zapiälmo zaporedje operacij, ukazom INT: ki se sprožijo z 1. Vsebina zastavic se kopira v sklad. 2. Zastavici IF in TF se anulirata (= O). 3. Vsebina registra CS se kopira v sklad, 4. Vsebini lokacije-na naslovih OOxxx (petmestni heksadecimalnl naslov) in OOxxx + 1 se preneseta v register CS (glej sliko 10). Naslov OOxxx Je doloSen z najnižjim (ničtim) bitom operacijskega koda (zloga) ukaza INT ali pa z drugim zlogom ukaza kk (npr. INT kk, kjer Je kk drugi zlog)..Tu velja: IF niati_bit = O THEN OOxxx ;= Oeh; ELSE OOxxx END IF; (4*kk)+2j 5. Vsebina registra IP se kopira v sklad. 6. Vsebini lokacij na naslovih OOvvv (petmestni heksadecimalnl kod) in OOvvv + 1 se preneseta v register IP (glej sliko 10). Naslov f^Ovvv Je določen z najnižjim (nl5tim) bitom operacijskega koda (zloga) ukaza INT ali pa z drugim zlogom ukaza kk (npr, INT kk, kjer Je kk drugi zlog). Tu velja: IF ničtl_bit = O THEN OOvvv := Och; ELSE OOvvv 4*kki END IF; Imamo tole sliko: ukaz INT kk llOOllOb tip kk ------Ta zlog obstaja samo pri b=l b=0: in se uporablja za izračun naslov naslova prekinitvenega vek- preklnlt- torja, ki Je 4 *kk venega vektorja je OCH 15.3. NavzdolnJl razvoj ROM BlOSa Po ročnem ali vklopnera resetiranju procesorja 6088 imamo S : IP = Offffh : OOOOh To pomeni, da moramo imeti na naslovu OffffOh v ROMu prvi ukaz, katerega oblika bo vobče JMP kodni_segmant:odmi5nl_naslov all v strojnem kodu z uporabo povratnega zbirnika (zbirka DEBUG.COM) SP ss ss BP SI DI IP mm mm CS nn nn DS SS tt tt ES PSW zasrvl zas-nl Podatkovni segment CD lA ppppm pppprn+l Kod ukaza INT kk je v našem primeru CD lA Slika 10. Ponazoritev delovanja ukaza INT kk Ta ukaz opravi vrsto operacij: shrani zastavice v sklad, postavi zastavici IF in TF na vrednost O, naloži CS v sklad, naloži besedo iz ustreznega naslova pomnilnika v register CS, naloži register IP v sklad in vstavi besedo iz ustreznega naslova pomnilnika v register IP. ffff:0000 eaSbeOOOfO JMP f000:e05b Pri odmičnem naslovu OeOBbh sektorja OfOOOh pa bo npr. tale ukaz: f000:e05b ea40e300f0 JMP f000:e340 Tako bodo začenjali nadaljnji ukazi ROM na lokaciji f0p0:e340 = Cfe340h. BlOSa Naplšimo načrt izdelave ROM BlOSa v psevdokodu ((13, 14)), ko imamo navzdolnji razvoj tega programa. Pri- tem moramo upoštevati več globalnih elementov, kot so npr. inicializacija vseh perifernih krmilnikov Petre (listi 1.....7 in še posebej Dodatek v ((12)), kjer sp zbrani naslovi V_I vrat perifernih krmilnikov Petre), subrutine Ibmovskega ROM BlOSa (tabela 4), na-lagalnik za naložitev sistemskega nalagalnika (glej kasneje) itn. Preden začnemo s pisanjem načrta za ROM BIOS, navedimo še nekaj bistvenih ugotovitev o ibmov-skemu diskovnemu operacijskemu sistemu (kratko DOS). 15.3.1. Struktura DOS in njegova inicializaci J a Ibmovski DOS sestavljajo 4 deli: 1. Nalagalni zapis (sistemski nalagalnik) se nahaja na diskovni stezi O, v sektorju 1 in na diskovni strani O (dvostranska disketa), in to na vsakem disku, ki je bil formatlran z ukazom FORMAT. Nalagalni zapis je na vsakem disku, tako da lahko izda sporočilo o napaki, kadar se želi pognati sistem z disketo, ki ne vsebuje DOS v diskovni enoti A. Pri vinčestrskem disku se ta zapis nahaja~v prvem sektorju (sektor 1, glava O) prvega obroča DOS particije. 2. Povezovalni modul je posebna zbirka (z imenom IOSYS.COM pri Microsoftu ali IBMBIO. COM pri IBM), ki povezuje DOS na spodnji (najnižji) ravnini s perifernimi In drugimi rutinami v ROM BIOSu. Zaradi tega ROM BIOS ,ne more biti poljuben in mora zadoščati os- novnim pogojem ibmovskega ROM BlOSa. Povezovalni modul IOSYS.COM Je skrita ?blrka (ni vidna z ukazom DIR). 3. Operacijski sistetn (zbirka MSDOS.COM ali IBMDOS.COM pri IBM), povezuje DOS na zgornji (najvišji) ravnini z uporabniškimi programi. DOS sestavljajo rutine za upravljanje zbirk, podatkovno bloklranJe_deblokiranJe diskovnih rutin in še vrsta vgrajenih funkcij, v katere Je moč enostavno doatopati iz uporabniških programov. Ko se te funkcijske rutine pokličejo iz uporabniških programov, sprejmejo visoko informacijo prek registrov in vsebin krmilnih blokov, nato pa prevedejo te zahteve v enega ali več klicev k IOSYS, kjer se zahteve dopolnijo. MSDOS.COM je skrita zbirka. 4. Zadnji modul Je ukazni procesor, ki Je odkrita zbirka COMMAND.COM. To, kar moramo pri razvoju programa ROM BIOS razumeti. Je inicializacija DOSa. Ko računalnik Petra zaženemo (z uporabo tipke za resetiranje ali pri vklopu računalnika, ko Je v diskovno enoto A vstavljena sistemska disketa), se mora najprej prebrati nalagalni zapis iz steze O, sektorja 1, strani O v hitri pomnilnik (RAM) in ta zapis (nalagalni modul) ae mora nato začeti Izvajati. Nalagalni modul z diskete pogleda najprej v imenik in preveri, ali sta kot prvi v nJem navedeni zbirki IOSYS.COM in MSDOS.COM (natanko v tem zaporedju). Če to ni res, se takoj izda sporočilo o zadevni napaki. Nato se ti dve zbirki prebereta z diska v pomnilnik. IOSys.COM je prva zbirka v imeniku in njeni sektorji morajo biti strnjeni (ne razpršeni). Iniciallzacijski kod zbirke IOSYS.COM opredeli status naprav, resetira diskovni sistem, inici-alizira priključene naprave, naloži periferne vmesnike In postavi prekinitvene vektorje v nizkem delu pomnilnika; nato pomakne kod prebrane zbirke MSDOS.COM navzdol po pomnilniku in pokliče prvi zlog operacijskega sistema. Podobno kot IOSYS.COM vsebuje tudi DOS skok v svoj inicializaciJski kod; ta kod bo kasneje prekrit s podatkovnim območjem in z ukaznim procesorjem (COMMAND.COM). Tako DOS inicializi-ra svoje notranje delovne tabele, prekinitvene vektorje (za rutine INT 20h do INT 27h) in zgradi prefiks programskega segmenta za zbirko COMMAND.COM V najnižjem prostem segmentu; nato Se nastopi vrnitev v kod IOSYS.COM. Zadnje opravilo inicializacije v programu IOSYS.COM Je naložitev zbirke COMMAND.COM na lokacije, ki so bile v ta namen pripravljene z DOS iniclalizacijo. Program IOSYS.COM je tako svojo halogo, opravil in prenese izvajanje na prvi zlog ukaznega modula COMMAND. 15.3.2. črt ROM BlOSa S podatki, ki smo jih zbrali o zahtevah združljivosti z IBM PC in na osnovi logičnega vezja mikroračunalnika Petra (listi 1, ... , 7 in dodatek vslovstvu pod nave.dbo ((12)) ), lahko začnemo pisati psevdokod za t.l. ROM BIOS. Osnovna naloga ROM BlOSa bo, da se pri vkjluči-tvl računalnika Petra ali ob njegovem reseti-ranju inicializirajo vsi njegovi V_I krmilniki v odvisnosti od nastavitev konfiguraciJskih stikal in da se po tej inicializaciJi začne izvajati preprost nalagalnik in ROM BlOSa, katerega naloga Je, da iz diskete v diskovni enoti A prebere nalagalni modul (glej prejšnji opis operacijskega sistema) iz steze O, sektorja 1, strani O v RAM in prenese izvajanje na ta modul. Pri tem mora ROM BIOS vsebovati še različne ibmovske subrutine za klice tipa INT lOH do INT IFH (glej tabelo 4) in ustrezno ibmovsko preslikavo (vektorsko tabelo 6 za te subrutine), ki bo prebrana (pomaknjena) na ustrezno mesto v spodnji del RAMa. V ROM BIOSu bomo tako imeli ibmovsko tabelo prekinitvenih vektorjev, ki je prikazana absolutno s tabelo 6. Ta tabela se bo preslikala v RAM, začenši z lokacijo 40H. Del RAMa od lokacije OH navzgor si bomo kasneje lahko izpisali z uporabo storitvenega programa DEBUG.COM in njegoveha ukaza d (d pomeni dump). Tabela 6 je bila seveda dobljena potem, ko smo v ROM BIOSu že do potankosti aprogramirali vse njene prekinitvene subrutine (tj. subrutine, ki se kličejo z zbirnlškim ukazom INT). Programiranje teh subrutin (njihove deklaracije) bomo nakazali tudi kasneje v psevdokodu. Napišimo si načrt programa v ROM BIOSu v obliki psevdokoda. Imamo tale zapis: PROGRAM rom_bios IS INCLUDE začetne_deklaracije; COMMENT Začetek koda, ki bo rezidenten v ROMu; Določitev začetke programa (ukaz tipa ORG); Onemogočitev prekinitve (ukaz tipa CLI); Omogočitev niznih operacij (ukaz tipa CLD); Inicializacija segmentnih registrov procesorja 8088; Inicializacija perifernih krmilnikov; Inicializacija krmilnika 8255; Inicializacija krmilnika 8155 (tudi za os- veževanje RAMa); Inicializacija DMA krmilnika 8237; Inicializacija obeh prekinitvenih krmilnikov 8259 (mojstra in pomočnika); Inicializacija časovnika 8253; Določitev obsega instaliranega pomnilnika tipa RAM; Brisanje pomnilnika tipa RAM (vpis OOh na vse lokacije); Inicializacija dela prekinitvene vektorske tabele: Prekinitve tipa NMI; Prekinitev pisanja na zaslon; Programske prekinitve; Trdne prekinitve; Itd. ; Tabelni Naslov Subrutlna Pomen (ibmovsko zdržljlve naslov subrutine INT kk prekinltvene subrutine) =============== sssssis: ============================== fOOOh:ffl3h f000h:f065h INT lOh Video prekinltvenl vmesnik :ffl7h ;f84dh INT lih Ibmovske periferne naprave :fflbh :f841h INT I2h Preizkus obsega pomnilnika :fflfh :ec59h INT 13h Diskovni vhod_lzhod' :ff23h :e739h INT 14h Vhod_izhöd standarda RS-232 :ff27h :e5fch INT 15h Kasetni vhod_izhod :ff2bh ;e82eh INT 16h Vhod_lzhod za tipkovnico :ff2fh :efd2h INT 17h , Vhod_izhod za tiskalnik ;ff33h ;e5fch INT 18h Osnovni vstop v ROM :ff37h :e6f2h INT 19h ,Navezovalni nalalagalnlk :ff3bh :fe6eh INT lah Čas dneva ; f f3fh :e5fch INT Ibh Prepis v RAMu bo; 60h:61h :ff43h :e5fch INT Ich Utripanje (bitje) časovnlka :ff47h ;e206h INT Idh Kazalec k video parametru :ff4bh :efc7h INT leh Kazalec k disk. parametrom :ff4fh :e5fo INT Ifh Kazalec k video razširitvi —■----:—------- ---------------— ------- —----- ________________________________ Branje stanj konfiguraoijskih stikal In nastavitev parametrov; Preizkus instaliranosti IbmoVskih serijskih in paralelnih perifernih naprav; CALL navezovalni_halàgalnlk; END PROGRAM rotti bios; V prograitiii rotn_bios navedene akcije in subruti-ne uporabljajo seveda še vrsto drugih subrutin. To so dejansko subrutine progratnskih prekinitev INT lOh do INT Ifh, ki jih uporablja tudi operacijski sistetn. Te subrutine se pravtako nahajajo v rezidentnem delu fiOM BlOSa. Opišimo najprej še segment z itnenom zà5etne_deklaracije. Imamo; SEGMENT zaaetne_deklaracije IS EnaCbe tipa EQU za naslove vrat perifernih • krmilnikov (8155, 8255, 8259, 8259, 8253, 8251, 8251, 8237, 8272A itd.); Enačbe tipa EQU za stanja v diskovnih V_I rutinah (iztek_časa, operacija_iskanja_neu-speäna, krmilnik_8272A_je_slàb, CRC_napaka, DMA_meja, DMA_prestop, zapis_ni_bil_najden, zapl3na_zaSčita, slaba_naslovna_znamka, slab_ukaz, vrata_DMA_strani, vrata_motor- ■ - ja);" Deklariranje tipa ÈXTRN možnih zunanjih rutin (tistih, ki ne bodo deklarirane v tem programu, zaradi možnosti ločenega, modularnega razvoja oziroma prevajanja); Deklariranje tipa EXTRN zunanjih prekinltve-nih lokacij (npr.: prekinitveni_vektor_0, NMI_vektor; IBM_prekinitveni_vektor, dis-kovnl_kazalec, kazaleo_za__video_parametre, : Itd.); . Deklariranje zaßetnega skladovnega segmenta (zaCetek sklada in njegov dopustni obseg); Deklariranje rezerviranega podatkovnega območja (zastavlca_naprave, obseg_pomnilnlka, Časovniška beseda, časovnlška zastavica. 3tanje_motorja, §tevilo_motòrjev, diskov-ni_status, diskovna_zastavica, prekinitve-na_zastavlca, zastavica_realnega_čaaa, baza V I vrat, serijska_baza, itd.); END SEGMENT začetne_deklaracije ; V ROM BIOSu imamo še subrutinske deklaracije za rutine iz tabele 6, in sicer v mešanem zaporedju: SUBROUTINE navezovalni_nalagalnik IS COMMENT To je subrutlna INT19h, ki začenja skladno s tabelo 6 na lokaciji Oe6f2 ROM BlOSa (psevdoukaz ORG Oe6f2h). Ta rutina je enostavni nalagalnlk, ki mora prebrati stezo O, sektor 1, stran O diskovne, enote A v pomnilnik tipa RAM, in sicer na lokacijo OOOOh; 7c00h in v to točko se potem prenese tudi izvajanje programa. Če branje nI uspešno, se izvajanje nadaljuje v monitorski točki OfcOOh: OOOOh.; Uporabi podatkovni segment BlOSa; Inicializaclja krmilnika upogljivega diska; Bralna zanka: Preizkus za 8 ali 5,25 eolsko disketo; Nastavitev števila sektorjev; Branje sektorja 1 steze O (CALL dlskovnl_V_I,) ; Tiskanje sporočila pri napaki in vrnitev v monitor; END SUBROUTINE navezovalnl_nalagalnlk; SUBROUTINE čas_dneva IS COMMENT To Je subrutlna INT lah, ki začenja z psevdoukazom ORG Ofe6eh Bralni del ; , Pisalni del; ■ ' END SUBROUTINE čas dneva; COMMENT Ostale subrutine; Definicija tabele programskih prekinitvenih vektorjev od INT lOh do INT Ifh; Definicija trdnih prekinitev (ORG Pe2fOh) od INT 40h do INT 4fh; Definicija diskovne baze, ki Jo uporablja sub-rutina INT 13h; Definicija prenosnih hitrosti serijskih kanalov; S tem smo končali načrtovanje ROM BlOSa v psev-dokodu in tako lahko začnemo s programiranjem v zbirnem Jeziku procesorja 8088. Podrobnejäi zblrniški programi bodo morda prikazani v drugem prispevku." 16. Sklep k tretjemu delu Med pisanjem tega nadaljevanja so bile na mikroračunalniku Petra uspešno preizkušene nekatere izvedenke operacijskih sistemov, in sicer: CPM-86, MS-DOS 1.1, MS-DOS 2.0 in nazadnje tudi CCPM. Pri tem.so bile uspešno preizkušene tudi nekatere vtične enote za IBM PC (ibmovska tastatura, monokromatični zaslon)- Preizkus raznih aplikativnih in sistemskih programskih paketov Je v teku (npr. Lotus 1-2-3, Wordstar, Basic, Prolog, Ada, C, mal^rozbirnik). Na koncu tega projekta časopisa Informatica bi se želel zahvaliti številnim prijateljem in sodelavcem, ki so s svojo iznajdljivostjo in s svojim delom omogočili uspešno izvedbo projekta. Slovstvo intornia Vabilo k sodelovanju Posvetovanje In seminarji Informatica '85 Nova Gorica, 24.-27. september 1985 Posvetovanje 18. jugoslovansko mednarodno posvetovanje za računalniško tehnologijo in uporabo Nova Gorica, 24.- 27. september 1985 Seminarji Izbrana poglavja Iz raCunalnižke tehnologije In uporabe Razstava Razstava računalniške tehnologije, uporabe, literature in drugih računalniških naprav, z mednarodno udeležbo Roki 1. aprili 985 Zadnji rok za sprejem formularla s prijavo in 2 Izvodov razširjenega povzetka 15. julij 1985 Zadnji rok za sprejem končnega teksta prispevka tic . o C ci ub Call for Papers ((12)) A.P.Železnlkar: Ibmovskl osebni raču-. nalnik Petra Ili Informatica 9 (1985), Št. 1, str. 9-18. ((13)) A.P.Železnlkart ksa in uporaba. 43 (1976), str. Psevdokodiranje: slnta-Elektrotehniški vestnlk 213. ((14)) A.P.Železnlkar: Mikroračunalnlški operacijski sistemi. 5 Jugoslavenski seminar o primjeni mikroprocesora MIPRO-82 (zbornik), str. A2-1 do A2-210, Rijeka, 25 - 28 svibnja 1982. ((15)) R.A.King: The MS-DOS Handbook. Sybex, Berkeley 1985. Symposium and Seminars Informatica 'BS Nova Gorica, September 24lh-27lh, 1985 Conference 18th Yugoslav Inlernalional Conference on Computer Technology and Usage Seminars Selected Topics In Con;puter Technology and Usage Nova Gorica, September 24th-27th, 1985 Exhibition Exhibition Ol Computer Technology, Usage, Literature and Other Computer Equipment with Inlernalional Participation Nova Gorica, September 241h-271h, 1985 INFORMATICA '85 61116 Ljubljana, p.p. 2 JUGOSLAVIJA Deadlines April 1, 1985 Submission ot the application lorm ' and 2 copies of the extended summary July 15, 1985 Sutjmisslon of the lull text of contribution N E I N T E G R I S A IM O OKRUŽENJE PROGRAMSKOG JEZIKA PASCAL^ VUKAJLOVIC ZLATIBOR UDK: 519.682.8 ELEKTROTEHNIČKI FAKULTET SARAJEVO U radu je opsano neintegriaano okruženje za programski jezik Pascal. Ono je ilustrativan primjer svojevrsnog pristupa problematici projektovanja i realizacije prevodilaca, pristupa koji je prvi korak ka projektovanju i realizaciji Integrisanog okruženja programskog jezika. NONINTEGRATED PROGRAMMING LANGUAGE PASCAL ENVIRONMENT: In this paper is described nonintegrated programming language Pascal environment, which is illustrativ example of specific admission to problems of designing and realisation of compilers, as first step on the way of designing and realisation of integrated programming language environment. 1. UVOD U se obraduje integrisano okruženje programskog jezika visokog nivoa. Izvjesno je da realizacija takvog ^okruženja traži znatne resurse, kako sa stanovišta centralne memorije, tako i sa stanovišta eksternih memorijskih uređaja sa mogućnošću direktnog memorijskog pristupa. Za sisteme "siromašnijih" resursa Je stoga opravdano (i neophodno) izvršiti dezintegraciju integrisanog okruženja i formirati skup neovisnih programa, koji obavljaju funkcije pojedinih modula integrisanog okruženja. Takvo jedno neintegrisano okruženje se može predsataviti na način prikazan na slici: Može se uočiti da, za razliku od integrisanog okruženja programskog Jezika, neintegrisano nema mogućnost (modul) inkrementalnog prevođenja, odnosno^ izmjene prelazne forme. Razlozi za ovo su višestruki: 1. Generator prelazne forme Je lakše realizovati od inkrementalnog prevodioca, koji ima mogućnost izmjene prelazne forme, a prilikom njegove realizacije se mogu steći dragocjena iskustva, koja će biti korisna kod realizacije integrisanog programskog okruženja. 2. Slogovi tabele koda se znatno rédukuju (sa stanovišta njihove dužine), a djelimično se redukuju i slogovi tabele simbola i tabele teksta, pa stoga datoteke sa ovakvim slogovima zauzimaju znatno manje prostora. 3. Generator objektnog koda i interpreter sa jezički orijentisanim simboličkim kontrolno testnim programom su praktično identični odgovarajućim modulima integrisanog okruženja, pa stoga, trud uložen u njihovu realizaciju neće biti uzaludan. (Potrebno je izvršiti modifikaciju u cilju prilagodenja prelaznoj formi integrisanog okruženja, koja Je opštija.) U ovom radu se opisuje koncept neintegrisanog okruženja za programski Jezik Pascal, koji, neosporno, posjeduje znatne kvalitete. Pored opisa prelazne forme u širem smislu, ukratko su komentarisani moduli generatora prelazne forme i generatora objektnog koda, a nešto Sire modul interpreterà. Za dobro razumjevanje rada, korisno bi bilo da se čitalac upozna sa referencom [ll . Napomenimo, da se pod pojmom pokazivač podrazumjeva referenciranje na neki podatak, a ne pokazivač kao tip (u Pascal-u). 2. OPIS PRELAZNE FORME Prelaznu formu u širem.smislu čine tri tabele: tabela koda, tabela simbola i tabela teksta, a organizovene su kao datoteke sa direktnim pristupom. Sam program se, u tabeli koda, predstavlja strukturom drveta, u čijim se čvorovima nalaze instrukcije virtualne mašine vrlo visokog nivoa, a koje omogućuju: interpretiranje Jezički orijentisanim simboličkim kontrolno testnim programom, sa jedne, i genćrisanje vrlo efikasnog koda, sa druge strane. Različiti se tipovi čvorova mogu pojaviti u drvetu. Tako " postoji čvor koji odgovara proceduri (tijelu procedure), čvorovi koji odgovaraju pojedinim iskazima Jezika (iskaz pridruživanja, iskaz poziva procedure, selektivnom iskazu GASE OF, uslovnom iskazu IF THEN LELSEl,repetitivnim iskazima: VfHILE DO, REPEAT UNTIL 1 FOR, iskazu bezuslovnog grananja GOTO, složenom iskazu, WITH iskazu i lažnom iskazu), čvorovi koji odgovaraju operatorima svojstvenim jeziku (razni binarni, unarni, funkcionalni 1 adresni operatori), te čvorovi koji odgovaraju operandlma (konstante, varijable 1 različiti parametri). U čvoru koji odgovara tijelu, od strane programera definisanih procedura (funkcija), nalaze se podaci o dužinama varijabli i parametara, pokazivači na ugnježdene procedure (funkcije) i procedure (funkcije) istog statičkog nivoa ugnježdenja, te pokazivač na odgovarajuće Iskaze, kao 1 pokazivač na tabelu simbola. Čvorovi koji odgovaraju iskazima Jezika sadrže podatke: o tipu Iskaza, pokazivač na tabelu teksta (gdje se nalazi tekst koji odgovara datom iskazu), kao i pokazivač na slijedeći Iskaz istog statičkog nivoa ugnježdenja. Ostali podaci zavise od tipa Iskaza, a to su (sumarno): pokazivači na ugnježdene iskaze 1 različite operande (konstante, varijable, parametre), statički nivoi ugnježdenja pozivajuče i pozvane procedure 1 si. Čvorovi unarnih 1 binarnih operatora sadrže podatke o operaciji i reference na odgovarajuće operande, a čvorovi koji odgovaraju funkcionalnim operatorima: pokazivač na parametre, statičke nivoe ugnježdenja pozivajuče 1 pozvane procedure 1 pokazivač na tijelo funkcije. Adresni operatori Undeksiranja, pomaka 1 indlrekcije), pored pokazivača koji omogućava izračunavanje bazične adrese, sadrži i podatke (zavisno od tipa) o donjoj i gornjoj granici Indeksa, pokazivač na poddrvo kojim se vrijednost Izraza Izračunava, dužinu elementa niza, odnosno relativan položaj polja u odnosu na početak sloga. Čvorovi operanada sadrže podatke o vrsti (konstanta, varijabla, pazllčltl parametri) i tipu operanda, te podatke o vrijednosti (konstanti), odnosno podatke koji omogućuje izračunavanje adrese (varijabli i različitih parametara). Date informacije su, ustvari, sadržane 1 u tabeli simbola, a ovdje se multipliciraju zbog toga što se očekuje da će im se, u tom slučaju, brže pristupati. Naime, slogovi tabele koda su duplo kraći, a velika Je vjerovatnoća da će se nalaziti u bloku u kojem su i čvorovi Iz kojih se vrši referenclranje na njih. Pored nabrojanih, postoje i čvorovi koji odgovaraju gornjoj (donjoj) granici FOR TO (DOWNTO) Iskaza, čvorovi odgovarajućih labela CASE iskaza, čvorovi različitih parametara (uz pozive procedura,odnosno funkcija), čvor konstruktora skupa, te čvorovi različitih konstanti koje nisu skalarnog tipa. Izuzev činjenice da su joj, zbog direktnog pristupa, slogovi fiksne dužine, u organizaciji tabele simbola nema posebnih specifičnosti. Tabela teksta Je takode datoteka sa direktnim pristupom 1 sa slogovima fiksne dužine. Svaki slog sadrži podatke o dužini teksta koji odgovara iskazu iz kojeg se vrši referenclranje na dati slog, broju vodećih blanko znakova i sam tekst. Ukoliko je tekst duži od sloga, nastavlja se u slijedećem slogu tabele teksta. 3. OPIS MODULA NEINTEGRISANOG OKRUŽENJA Od već spomenuta tri modula neintegrlsanog okruženja, svakako je najkompleksniji i za realizaciju najteži modul generatora prelazne forme. To Je ustvari prevodilac izabranog programskog jezika (Pascal), koji generlše kod virtualne mašine (čije su instrukcije - čvorovi napred opisani). Dodatni zahtjev na prevodilac je zahtjev za formiranje tabele teksta, odnosno "logičnih" linija, za svaki iskaz iz programa po Jednu 111 više. Ovaj modul se, kao 1 ostali, može reallzovatl u jeziku visokog nivoa (npr. u Pascal-u). Modul jezički orijentisanog simboličkog kontrolno testnog programa Interpretira generisani kod virtualne mašine koristeći određeni skup procedura 1 fuknkcija. Podaci nad kojima se operiše, nalaze se na steku, koji se definiše kao niz karaktera po imenu STACK. Za dokučivanje sa steka podataka različitih skalarnlh 1 realnog tipa postoji skup funkcija, koje za konstantni parametar Imaju početnu adresu , odnosno vrijednost Indeksa iz tabele STACK, a rezultat funkcije je odgovarajući podatak. U realizaciji datlh funkcija se koristi varijabilan slog. Npr., ako cjelobrojni podatak ima dužinu identičnu dužini dvaju karaktera, odgovarajuća funkcija ima oblik: FUNCTION lntegerfeteh(a:lnteger)rlnteger; VAR xrREICORD CASE karakterni_obllk:boolean OF true: x11,x12:charj false: x2:Integer END END; BEGIN x.karakterni_oblik:=true; x.xl1:=STACK a ;x.x12:=STACK a+1 ; x.karakternl_oblik:=false; Integerfetch:rx.x2 END; Za smještanje podataka različitih skalarnlh 1 realnog tipa, postoji skup odgovarajućih procedura, koje imaju dva konstanta parametra: sam podatak 1 adresu na kojeg se isti smješta, a realizuju se na način sličan realizaciji funkcija za dokučivanje podataka sa steka. Za Izračunavanje adrese nekog objekta (varijable, parametra ili rezultata funkcije), koristi se procedura čije zaglavlje Ima oblik: FUNCTION addre3s(x:Integer):Integer ; Ova funkcija Izračunava adresu objekta, čiji je opis dat u čvoru operanda na kojeg x pokazuje, a rezultat funkcije Je odgovarajuća adresa (Indeks iz tabele STACK). Za izračunavanje vrijednosti izraza odgovarajućeg tipa, koristi se odgovarajuća iz skupa funkcija za aritmetiku. Npr. za cjelobrojnu aritmetiku, zaglavlje funkcije ima oblik: FUNCTION Intval(x,y:integer): integer ; Konstantni ^parametar označava način na koji se Izraz Izračunava, a naznačuje da li Je Izraz konstanta, neki drugi operand ili Izraz predstavljen drvetom u čijem se korijenu nalazi binarni, unarni Ili funkcionalni operator. Drugi parametar označava 111 samu konstantu ili pokazivač na odgovarajući čvor tabele koda. Data funkcija može rekurzivno pozivati samu sebe, funkciju za dokučivanje (odgovarajućeg) operanda sa steka ili pak aktivirati funkcije definlsane od strane programera (koje su dio tabele koda). Kod realizacije Iskaza pridruživanja, koji operiše nad objektima komponentnog tipa, koristi se procedura čije je zaglavlje oblika: PROCEDURE moveblock(x,y,z:integer); gdje X i y označava izvornu, odnosno odredišnu adresu, a z dužinu bloka podataka. Slično datoj, postoji i procedura koja na odredišnu adresu smješta konstanu zapisanu u tabeli koda. Za ispis teksta izvornog programa odgovarajućeg iskaza, koristi se procedura čije Je zaglavlje oblika: PROCEDURE line(x:integer); gdje Je X pokazivač u tabelu teksta. Ova procedura ae poziva na početku Interpretiranja svakog Iskaza, a Ispis ae vrši samo ako je Izabran odgovarajući način rada .1.,odnosno ako Je data linija označena kao trag ili prekidna tačka. Za ispisivanje rezultata izračunavanja skalarnog ili realnog tipa pojedinih iskaza, koristi se odgovarajuća iz skupa procedura. Npr. zaglavlje procedure za iapis podatka bulovog tipa ima oblik: PROCEDURE writebooKx:boolean); Ispis se vrši ako Je izabran koračni način rada ili ako je izabran, iskazni način rada i ako pokazivač na zaglavlje skupa lokalnih objekata ima odgovarajuću vrijednost (zavisno od toga da li se koristi rastuća ili opadajuća varijanta steka). Za ispis promjenjivih (konstanti) čiji tip nije predefiniaan (predefinisani au npr. integer, real, char, ...), odgovarajuća procedura sadrži, kao konstantne parametre adresu podatka i pokazivač na opis tipau tabeli simbola, što omogućuje da se iati ispiše u simboličkom obliku. Nakon ispisa rezultata Izračunavanja, proces interpretiranja se prekida. Interpretiranje ae^ nastavlja zadavanjem komande kojom ae definiše novi način rada. Najzad, tu Je i procedura koja interpretira pojedine iskaze, odnosno procedura čije je zaglavlje oblika: PROCEDURE code(p,pl,al:integer)j gdje p pokazuje na odgovarajući čvor Iskaza, dok au pl i al statički nivoi ugnježndenja procedure, odnosno iskaza (unutar procedure).Poslednja dva se koriste da bi se, nakon bezuslovnog grananja na iskaz nižeg statičkog nivoa ugnježdenja unutar date procedure, odnosno prvi nivo statičkog nivoa ugrnjezdenja kod grananja izvan iste, mogla korektno prebaciti kontrola izvršenja iskaza. Oni, takode, omogućlju formatizirani ispis teksta izvornog programa. "Kostur" procedure za interpretaciju Iskaza ima oblik: VAjJ cvor:element_tabele_koda; BEGIN WHILE pO DO IF lift THEN BEGIN IF {plgotopl)OR{plgoto=pl) AND(slslgoto) THEN pi=0 ELSE BEGIN lift:=fal3e;p:=PC0T0 END END . ELSE BEGIN ( Ako Je zadana nova komanda, interpretiraj je; Dokuči p-ti element tabele koda i amjeati ga u promjenjivu cvorj Pozovi proceduru za ispia linije (sa odgovarajućim parametrom); j Interpretiraj dati čvor na odgovarajući način ) Je, zbog pojednoatavljenja, deflnlaan. samo opisno Kod interpretacije nekih nekih čvorova (iskaza) Jezika, procedura code rekurzivno poziva samu sebe.. Npr. čvor koji odgovara REPEAT UNTIL Iskazu, interpretira se na način: REPEAT ( predhodno Je ispiaan tekst iakaza ) code(cvor.ostO,pl,sl+1) ( u cvor.ostO je pokazivač na ugnježdene iakaze ) llne(ovor.03t1) (linija sa UNTIL ); b:=boolval(cvor.o3t2,cvor.oat3) ( b Je pomoćna varijabla, a pomoću cvor.o3t2 i cvor.ostS se izračunava vrijednost uslova ); uritebool(b) UNTIL b; Dakle iskaz ae Interpretira pomoću samog sebe. Na sličan način se interpretiraju atandardne procedure i funkcije, a 1 ostali Iskazi. Iz kostura interpretacije Je zadana nova i interpretira, trenutku test tragovnom ill i nastaviti komandom. ae može uočiti da ae, kod avakog iskaza provjerava da li komanda,^te se, ako Jeste, ista To omogućuje da se u bilo kojem iranja programa izvršavanje u normalnom načinu može prekinuti, aa načinom deflnlsanim novoin Da bi se mogao istovremeno izvršavati ispis na ekran 1 čitati znak sa tastature (unositi komande) terminal mora da radi u punom dupleks načinu , a što operativni sistemi računara dozvoljavaju. Međutim, ovaj zahtjev, kao 1 potreba za datotekama sa direktnim pristupom, može dovesti do toga, da ae, Jedan manji dio koda, piše u nekom drugom (prvenatveno asemblerskora) jeziku. t. ZAKLJUČAK Neintegrlaano okruženje programakog jezika ima za cilj uvođenje jedne (nove) prakse u projektovanju 1 realizaciji prevodilaca. Ovakav prlatup ima svoje odredene prednosti, najviše aa stanovišta prenoaivoatl i udobnosti testiranja programa. Moduli generatora prelazne forme i interpreterà su veoma prenoalvi. Modifikacije je potrebno Izvršiti zbog različitih dužina predefInlaanih tipova na pojedinim računarlma, a što ne izaziva neke bitne probleme. Nešto veći problemi nastaju objektnog koda, pri čemu će iakustva stečena na Jednom računaru, biti veoma korisna kod realizacije na drugom. Bitno Je napomenuti, da struktura drveta izabrana za predstavljanje koda omogućuje generlaanje vrlo (objektnog) koda. Nadalje, prilikom prevodioca, programer neće biti različitim detaljima ciljne mašine, neintegrisano okruženje može biti realizovano od strane više ljudi, čiji au poslovi praktično nezavisni. tabele efikasnog pisanja opterećen Konačno, Interpretiranje u procesu testiranja, čiji je nedostatak relativno mala brzina Izvršenja, ma koliko aporo, opravdano Je Iz razloga što brzina izvršeftja (kod testiranja) nije presudan faktor. p:=cvor.slijedeći lakaz END ~ END; Lift Je varijabla koja se na vrijednost "true" poatavlja u procesu Izvršenja GOTO Iskaza, kada se definlšu i vrijednosti varijabli plgoto, slgoto i PGOTO, a na osnovu podataka sadržanih u Inatrukciji grananja. Oatali dio "kostura" 5. LITERATURA: Z. Vukajlović: Integriaano okruženje programakog jezika - alat za udobno 1 efikasno programiranje ANALIZA RASPOREDJIVANJA ZADATAKA U M U LT I P ROG R AMS KOM SISTEMU (MRS-u) KORIŠTENJEM SIMULACIJE U PASKALU GOJO ŠTRKIČ, DAVORIN NOVOSEL UDK: 681.3.012 ELEKTROTEHNIČKI FAKULTET BANJALUKA SADRŽAJ - U radu je definisan problem rasporedjivanja u MPS-u, Zatim se uz elementarne termine iz simulacije date osnovne osobine simulacionih jezika kao i način kako su iste riješene u paskalu. Dat je model MPS-a i na osnovu njega su u paskalu simulirana tri, po kompleksnosti različita, algoritma. Rezultati sitaulacije ukazuju da na performanse sistem utiču kako način dodjeljivanja prioriteta tako i način podjele resursa. ABSTRACT - In this paper is defined problem of scheduling in multiprograjimed system (MPS). Beside elementary simulation terms here are given basic features of simulation languages as well as ways of solution these features in pascal.Model of MPS is given and in pascal are simulated three, in complexity different, algorithms based on the model. Results of the symulation show that on perfonnances of MPS influence have both way priority assin.^ment and way of assignment of resources. 1. UVOD Multiprogramski sistem kar^kteriše konkurentno iz-vodjenje više zadataka. Kada broj zadataka prijedje od-redjeni limit onda se selektuju samo oni zadaci koji nogu nastaviti izvodjenje a ostali moraju čekati. Operaciju selektovanja zadataka (scheduling) u operacionom sistemu izvodi poseban modul koji se zove rasporedjivač (scheduler). Poznato je da se koristeći opšti algoritam baziran na prioritetima zadataka mogu implementirati različite strategije rasporedjivanja |4,5|. Pored toga raspo-redjivanje se može podijeliti u dvije posebne funkcije: funkciju dodjeljivanja prioriteta i funkciju dodjeljivanja resursa. Mi smo koristili simulacione modele kako bi razmatrali osobine algoritama rasporedjivača. Prilikom izbora jezika u kom bi izveli simulaciju imali smo u vidu da se za simulaciju može koristiti bilo koji jezik opšte namjene a postoje i posebni, simulacioni jezici, u koje su ugradjene osobine za prikupljanje statistike kao i za manipulaciju diskretnim dogadjajima. U literaturi postoji niz analiza (na pr. |2|) u kojima je imjuči u vidu neke parametre kao što su pode-snost za simulaciju, fleksibilnost, zahtjevi za memorij-skim prostorom i procesorskim vremenom, poredjeno više jezika kako simulacicnih tako i jezika opšte namjene. Ishod ovih analiza je pokazao da su, ako se izuzmu simulacioni jezici (koji takodje inaju svoje nedostatke), strukture paskala dovoljne za simulaciju računarskih sistema. 2. UOPSTE 0 MPS-u I MODELU MPS-a Usvojićemo model računarskog sistema onako kako je to prikazano na sl.l. kompletiranje Sl.l. Stanje zadataka Rad sistema opisan ovim modelari može se objasniti tokom zadataka. 2;adaci koji pristižu mogu zahtijevati isključiv pristup na resurse kao što su nagnetske trake i diskovi. U slučaju da ovi resursi nisu raspoloživi dati zadaci moraju čekati. Kad resursi postanu raspoloživi zadaci postaju spremni za aktiviranje. Mi smo usvojili da zadatak postaje aktivan kad mu se dodijeli virtualni processor i potreban blok iremorije. Razmatrali smo i mDguSnost da aktivni zadatak može biti oreenptiran iz alctivnog stanja čime on oslobadja svoj blok glavne memorije i svoj virtualni procesor i ponovo se pridružuje skupu spremnih zadataka. Preenptirani zadaci mogu biti reaktivirani i nastaviti izvodjenje od tačke preenptiranja na bilo kcm procesoru i u bilo kan bloku glavne memorije. Isto tako, zadatak može kompletirati izvodjenje i završiti. Analizirana je i mogućnost da aktivni zadaci nogu zahtijevati dodatne resurse (na pr. dodatnu niemoriju). Ako ovakav sistem podržava preefnjrti-vno rvTspoiedjivanje tada dati zadaci niogu biti preeinpti-rani u stanje čekanja ili spremno stanje zavisno od raspoloživosti zafitijevanih resursa (vidjeti sl.l.). Sve tri algoritma koje sirß razmatrali predpaitavljaju da se zadaci nalaze na listana koje su poredarie po prloritetinö. Zadatak ivtsporedji.vaća .je da preti-aži listu spremnih zadataka i selektuje za aktiviranje neke od zadataka. Zavisno od raspoloživih resura, rasporedji-vač ponekad preenptira aktivne zadatke i vrača ih u spremno stćinje. Analiza je vršena na osnovu nekih pojmova koji zahtijevaju objašnjenje. Naime, ako zadatak stiže u trenutku t^p a zšava se'(odlazi) u trenutku to tada je t^o -t.p vr-'ijeiir? protoka datog zadatka. Za skup zadataka (Zp , i=l,.,.,n; sa vreitenima pristizanja tp i vremenima odlaska to, vri jene završavanja za {Zi) je a prosječno vrijeme protoka je , ' n ■ , 1 I (t.o - t p) . n.izl - 1 3. STRATEGIJE RASPOREDJIVANJA I PRIORITETI Prioriteti se mogu dodijeliti izvana a postoji i alternativa da sistem sračunava prioritete na osnovu nekih atributa zadataka kao što su trenutni zahtjevi za memorijan, predvidjeno vrijeme procesiranja, vrijeme pristizanja i slično. Mi smo vršili analizu na osnovu slijedećih strvategija r^poredjivanja. Korištene strategije rasporedjivanja strategija , željeni efekat NkVP Najkraće vrijene Minimizirva vrij .prxxesiranja . procesiranja NdVP Najduže vri jene ^anjuje ukupno vrijeme procesiranja NmZM Najmanji zahtjevi Zadaci se izvode po važnosti tiemcrije Vanjski prioriteti tt. SIMULACIJA U PASKAIU ' Prvo ćemo uz osnovne osobine simulacionili jezika dati i eleiriintama objašnjenja nekili pojmova koji se koriste u simulaciji, a zatim ćemo u toni svjetlu iskomenta-risati odgovarajuće osobine paskala. 1U literaturi se osnovni elenent modula sistema često naziva entitet a osobine entiteta se nazivaju atributima, gimulacioni jezici. |K)sjoduju mogućnosti da se pomoću njih mogu opisivati entiteti i njiliovi, atributi. S obziran da èntiteti ne nogu biti opsluženi, u momentu kad se pojave to simulacioni jezik mora inati ncgu-ćnost za manipulacijom repovinva (listama) čekanja. Svaki simulacioni jezik ima mogućnost da se parioću njega u simulator' sistenui može ugraiJiti si.muJacioni sat na kan se vt>ijene uvećava nakon sv>ike proiijene stanja , . sistena. • . Ako se prihvati da su dogadjaji pixaiijene u ;st;uiju sisteiie onda je aa očekivati da svaki, sijriulacioni jezik posjeduje iiogućnost za opis i raspored j i van je dogadjaja. Simulacioni jezici, iiiaju mogućnost za piùkupljanje statistike generisane simulacijaii. Kod simulacije račuiieu^skih sistejna .uobičajeno je da se radno opterećenje računara opisuje ijtaoionaini.m tli.s-tribucijajiia vjerovaCnoće bez obzira na to koji se piog-i^iinski jezik koristi kao sredstvo za simulacij u. Mi smo u tu svrhu koristili generator slučajnih, bri-)-jeva (unifoniria raspodjela) koji ina na račurjaru VAX 11/780 VMS, Gledano sa stanovišta simulacije, ono što paskal čini. podesnim je pokazivački tip podataka (pointer type) i, odgovarajuća dinaiaička varijabla. Na. pr. ,iskaz . type Tp = TT . ■ ukazuje da su vri jednosti pokazivaćkog tipa Tp ustvai\i pokazivači za podatke tipa T. Uz pokazivdički tip idu i dvije standardne procedui^e new() i dispòse( ) za koje ćemo dati slijedeće objašnjenje.. Ako je P pokaži vačka vari j alila tipa Tp onda procedii-ra new (P) zapravo aloci.ra varijaiilu tipa T, generiše . . pokazivački tip Tp koji referencira novu^arijablu i pridružuje mu vrijednost P. Inverzna procedura od new() je dispose( ) koja os.lobadja inemorijski prostor zauzet ' odgovarajućom dinamičkom varijablom. Sada ćemo ilustrovati kako se atributi entiteta opisuju panoću paskala. Na sličan način je definisan zadatak i njegovi atributi u podnaslovu 5. Naine, pokazivač zadatka pokazuje na varijablu zadatak koja je tipa zadatak _rec, atributi varijable zadatak specificiraju se paitóéu polja tipa RECORD. WPE zadatak =Tzadatak_i^c zadatak_rec = RECORD. pr; integer; sljedeći: zadatak ENOi VAR proceszadatak; Kreiranje zadatka vrši se iskazom new(proces); ' ' . a dodjela atributa nože se vršiti na sijedeći način;. procesT.prioritet : = 10; Manipulaciju listama čekanja ilustrovati ćemo panoću j^rx»-cedurvi l'NSIiRT koja preira prioritetu ubacuje zadatak na . listu spremnih zadataka. Ova prxicedura može poslužiti kao primjer kal pomsljT .jii-) tl)en begin nZT ,sljedeći::poiiiT.sljedeći; paiiT. sljedeći =n/S; (ft zadatak ubačen na listu ubačen = trvie end else begin pan := ponit.sljedeći end C* panijeia se na sljedeći elenent END end END f>ID; ' 5. RASPOREIUrVflNJE ZAUAT/\KA Sada ćeino opisati, tri algoritiia za selekciju zadataka i ruxiiotiùti inf>likaoije koje nastaju povećavanjem kaiipleksnosti algori tàiia. Za detaljan uvid u algoritme pogledati ixxinaslov 8, U podnaslovu 3. je spaiKnuto više korište.uh sttutegija raspored j ivan ja s tim da je je-: dino data prooedui-a aa ubacivanje na listu prene vrijednosti prioriteta dodijoil.jenih izvana. Na isti način se vräi (lodavcuije na odj'pvarajuču listu ptenia veličini bilo kog atributa. UzinvTiije sa liste vräi se sa čela bez djzirvi kćiko je na istu utiacivano. Svaki od algor'itčinia moru .inviti slijedeće osoljine; 1. Aktiviivinje z.iddtkči najvišeg prioriteta koji će so zadovoljiti raspoloživiin renuruinia. 2. Osigiiranje efika'inog korižtenja sistuiiiikih leau-rsa (virtualnih proccsorva i glavno nenorije). U sva tri algoritna aktivni i sprenni /.adaei su na listi portHiani od najviäeg do najnižeg prioriteta, Pro zadatak_status :»akt ivan_Z ; VPt.VP_Status :=preenptivan_VPv (* ako procesor ~ može preuzeti zadatak višeg prioriteta «) ili VP.VP_status :=nepreenptivan_VP; C u suprcf- tnom '■) . 3. Zadatak zad završava pnseniptiranje virtualnog procesora VP zadtÄadatak_status : =sprximan_Z; (ft Uvećaj broj VP za jedan *•) Raspoloživa ncm ;= Raspoloživa meni *■ zadatakt. Zahtjnemj ~ VPf. status : :alobodan_VP -, (ft vrati procesor u skup nezauzetih VP ft) INICTJAUZIKAJ (Rasporedjtvač) v H, Zadatak zad se završava na virtualJiom procesora zad+.statu-s : =konpletiran_Z ; (ft Uvećaj broj VP za jedan ft) Raspoloživajiem :=Raspoloživajnem + zadatokf, Zahtjnem; (• Izbaci zadatak žad Iz Uste aVtlvnih (sprom- nlh> z^atalca.*) . VPf, status nlobodan_VP C ui>aoi VP u listu.nezauzutih procosor.i ft) .rNTCfJ AIJZTRAJ ( Raspored j ivnč ) ; ,S1.2. (Vidjeti podnaslov 8.) I Algoritam 1 ina osobinu da aktivirvi spremne zadatke i to od najvišeg prioriteta do najnižeg. VP Kai-'akteristika mu je da vrlo slabo. isi^orištava resurse sistema. Kao najjednostavniji rasporedjivač'zadataka on pretražuje listu spremih zadataka i dodjeljuje zadatke virtualnim procesorima sve dok ne naidje na prvi zadatak koji nije spreman. Samo se po sebi naneće da bi rasporedjivač bio bolji kada bi pretraživao, čitavu listu tražeći zadatke koji se zadovoljavaju sa raspoloživaii neniorijom. To je posti, gnuto Algoritman 2. Njegove karakteristike u poredjenju sa algoritiican 1 su: . - povećan liizik da će zadatak biti raspored] en van strogog držanja prioriteta, , - povećana potencijalna efikasnost rasporedjivanja. Poboljšajije perfontansi Algorltiie 2 može se postići uvo-djenjem preemptivnih osobina koje dozvoljavaju aktivnim zadacima da budu deaktivirani i vraćeni u listu spremnih zadataka. Ovi preen^itirani zadaci nvDgu biti reaktivirani na bilo kan virtualnom "pipcesoru i u bilo kojoj tački u glavnoj memoriji. Intencije Algoritma 3 su: - da drži aktivnim zadatak sa najvišim prioritetan koji će zadovoljiti ograničenja resursa, da omogući da zadaci nižeg prioriteta budu pree-nptii'ani kako bi, u slučaju potrebe, oslobodili resurse za zadatke višeg prioriteta. ; Pored liste spremnih i aktivnih zadataka postoji lista aktivnih virtualnili procesora poredana u obrnutom redoslijedu prioriteta pripadnih aktivnih zadataka. Počev od ćela ove liste vrši se pretraživanje da bi se našli zadaci koje treba preemptirati. Stanje procesora na ovoj listi označava se sa preenptivan VP ako je procesor preemptivan ili. nepreemptivan_VP u supr-otnora. Status nepreejnpti.van_VP se koristi i u slučaju kad procesor mi' jenja staiije kako bi niogao bez prekida izvesti operaciju ndjenjanja stanja. U algoritmu figuriraju i varijable Bi^VP_n=ispol_ža_ra3por i Mem_ra3pol_za_raspor, koje označavaju raspoloživi broj virtualnih procesora i velići-, nu raspoložive rrEmorije respektivno. lY^eba imati u vidu da u vrijednosti ovili vai-'ijabli ulaze i oni resursi koji : su u posjedu nekiJi zadataJ nil) DO BEGIN ■ IF l_sp_ZT.status = spreinan_Z THEN ■ BEGIN IF l.sp.ZT.Zaht_mem<= Raspoloživa.mein IVIEN .BEGIN l.sl.VP :=l_sl_VPt.sljedeći Raspoloživa.mem; =Raspoloživajiiem-l.sp,ZT,Zaht. nem; l-sp_Z.status :=a)ctivan_Z; AKTIVIRAJ(l.sp_Z, Ì.S1.VP '0 END • , ELSE GOTO 999 1 sp_Z :=i_sp_Zr.Bljedeći; 99y:END; ■ END. Algoritan 2 ■ . progr^ alppritaraci ( input .output ) ; ' 'lYPE zadatak,8tatus=(spreraan_Z,aktivan.Z,konpletirwi_Z); zadatak = 2adatak_rec; zadatak.rec = RECORD zadatak.ID: integer; pri'oritet» integer; Zaht.mem: integer; status: zadatak_status; sljedeći: zadatak; END; VPi^status = (aktivan_VP,slobodan_VP); Virt J'roc =tVirt.Proc_rec; Vi.rt_Prxx:_rec = RECORD Virt..Proc JD: integer; , status; VE.status; sljedeći: Virt_Proc . END; VAR Kaspoloživajreni: integer; lista.spremiìiti.zadataka.i-sp.Z; zadatak; lista^lcbo<3nih_VP,l,sl.VP: Virt.Pixjc; BEGIN 1 _sp_Z;:lista.spreninih zadataka; lista j=lobodnih_VP: =l.sl_VP; WllILE(l_sp_Z < ^ nil) AND (l_sl_VP <> nil) DO BEGIN IF (l.sp.Zf.stdtus = spreman^Z) AND (l;sp_ZT.2aht_iißm<= Raspoloživa iienOlTCN BEGIN ' Raspoloživa irem: =Raspoloživa.inein-l_sp_Z T. Zahtjnein l.sp_7T.statuü;=aktivan Z; (ft AKTIVIRAJ (l.sp.Z,1.3l.VP l.sl.VP:=l..i5l VPt/sljedeći END; l_sp_Z:=:i_sp_Zl. slijedeći; END; AlgOT'itaiii 3 ■ prognan algoritara_3 (input.output); lYPE zadatak status=(prt:emtivan_Z,yptxäinan_Z,aktivan_Z, aktivirwje_Z.u-toku, preera.Z.ü jtoku, kanpletiian_Z) ; zadatak = zadatak zadatak,rec = RECOia) zadatak_ID: integer; prioritet : integer; Zalit_meni, integer; status: zadatak.status; sljedeći; zadatak; . END; VP status = (preeiiptivan.VP, nepreeinptivan_VP, aktivan _VP, slobodaii_VP); Virt Proc =TVirt.Pixx:_reo; Virt3Proc_rec = RECORD Virt_Pi'OC_ID: integer; status: VP_statu3; aktivni_zadatak: zadatak.rec; sljedeći: Virt_Proc END; VAR Tren_Mem_raspol_za.raspor; integer; (* u nju ne ulazi neinorija koju zauzimaju preenpti-vni zadaci Suni_Mem_raspol_za_raspor: integer; (.'< u nju ulazi iie- morija koju zauzimaju preempti-vni zadaci ■'') Tren_br_VP_raspol_za_ra3por:integer; (* u njih ne ulaze VP aktivni na preemptivnim za-daci-iia ) Sumj3r_VP_raspol_za_raspor:integer; (* u njih ulaze W aktivni na preeniptivnim zadacima *) lista_aktivnlhJ/P: Virt^Proc; (* lista aktivnili VP-a na kojoj su VP poredani prema prioritetu aktivnih zadataka na nji-na i to od najnižeg do najviäeg nivoa prioriteta listai.spremnih_zadataka: zadatak; C* lista spreimih , zadataka. pore- danih po pri.orite-tu)A) Preem_mem, Preem_VP; integer; Mem_zä_k9juJe_preeni_u_toku, Br_VP_za_koje_je.preeir. u ^toku; integer; ~ ~ Sum_zaht mem: integer; Zaht_br_VPr integer'; Sum_nem, Tren_nEm, Sum_VP,'rren_yP: integer; l_aJ/P, l_sl_VP: V,irt_proc; l_sp_Z,l_a_Z: zadatak; BEGIN Tren_Mem_r^spol za_r'aspor ;=100; Tren_br_VP_raspQl_za_raspor :=S; l_a_VP :=iista_aktivnih_VP; 1 _sl_VP : : li3ta_s lobodni.li_VP ; Sum_nem: =Sum_Memjnaspol_?^_raspor; IVenjnem ; =Tren_Mem_raspoÌ__za_va3por ; Sum_VP ;=Sum_Br_VP_raspoCzaj:Qspor; Tren_VP ,; =Tren_Br_VP_ra3pol_za_raspor; W1IIU" l_a_VP <> nil DO BEGIN IF 1 a VPT.status = nepreeimtivan VP 'IHEN BEGIN Sun;_Mem :=Sum Meiirl a_VPt .aktivni zadatak.Zaht mem; Sum_VP :=Suffl VP-1; " - - END ELSE . BEGIN II' l_a_VPT.status = preeniirtivan_VP 'IVlfJN . l_a-_VPT.aktivni_zadatak.status :=prEemtivan Z FJvlD; 1 a VP ;=1 a VPt.sljedeći; I^JD; pretraži listu spremnih zadataka.'^) Mem_za_kojuJe_preem_u_toku ; = 0; Br_VP_za_koje_je.preem_u_toku : =0 ; Sum_zaht_ 11*3111 ; =0 ; . wiiiiJ: ( <> iii J ) (Sujii_vp > 0) iw .liixirM , IF Uip_7.T,'.'..itil- nt;m <= Simi_Hciii 'riCN lilKIN , Tl' l_.':;p_Zt.-'itatu;! - prc-.viiil;lvaii_7, 'IHIJ'l lilBIN ' : .;juiIi_v1'-:=Suiii_v1't1 ; .öüiii_Mtiiii : =SunrMuiir1 •iip_-'/.T. '^itjieiii; 1 S); /.1,1; tat IE : i:nd ~ i:tói; _ ('■' .:iko jo ■igr<-jni Broj_«Ieiii_u_J isti '(Lista), ft) , : Tivin.Vl' ::Brai.f,-leMi...u Jlsti ( l_Gl_VP) TI KI i VP :='ri t!ri Vl '-l ; l.-Kl.VP : = l_sl,VFl.;il]tì(J<3Ói; ,,Suin.Meiii :. = SuirrMfiiir. .LipJ/t.Zijlitjiemi (>'•■ fiko it;surHÌ rtföpolozivi IF (1 rip_7,-r,Za)iU_fjieiii <= Tren. Mem) ANI) CTVtiriJP > 0) .'tllFN Hi;cnN ■ ~ • . ■ J_sl_VK :?l_3l.VPf. slioitól ■ 'IVvüi Vl> ;.='l'i«ii_VP-l V • ''rren>te.iti:='lVenJfcm-i:.sp_Zt. Zahtjieii» 1 •spJZt.status-- : =akt'lvitvanje_Z ji Jroku; . iliil. Vi' :=lista_slob«iii,ih_S/Pi 1 JrLJ/l' : =l_:Jl_VPt.sljedećii J ;!l Vn.statuE! ; =nepreeniptivan_VP; C' Akdvinq zadatak sa tela i_8p_'Z na pixi-ceGoni Ba čela l_sl_VP paiioću ponioóne procedur« AKi'lVlRAJ (1.8p.Z, 1.8l_VP) '•) ' - t:Ni) ■ . . ■ - KUÌF : (>'• iiko Kl) lesursi nüiU rtispoloživi ''') BIKIN . . -■ : 7.;iht_br_VP ; =ZalirJ)r_VP + 1 ; ; =:;uiii'_zćilil: jiem + l_sp_Zt. 7«3ht ' ' ■ r:wD ■ ■ " ™d. ... FLSI": U' ako je preenptiranje z.;idataka u toku ''■) .I F l.»p_SJ.i3 tatua - pnsem Z u toku 'IVIEN BL'GIN , ■ ■ Br_VP_/.aJlen:jj Jiatl .0 j3l_VP) Ptoi.'in„VP :='rrun VP -f Bi-_VP za^koje Je.pi'e.em u.toku-, WIII U; (l.a_VP nil) ANI) ((Prcem in;m» l'rVM:.-iiipi:irvi) SKlatak sa etila l .ste 1 a VP pa(io>?u pumx'no pi/utem Sinnilatioii. in Pascal", . Softwart-Pj'actic:e .md i:xi>erienoe,. 12 7V7-78i| (1982). ■ M) M. Kusohitzka and K.l'aljry, A unifying aiipioacfi to' ... scheduling",. CAlI-1, 2Ü, No.7, mi9-M77, (1977). . b) J.latiiiouCh. Sclieduling fot' share of the madiine, Sottwaie - Practice ouK-l experience, b, No. 1, 2y-i|9 (197S). . ■ . ti) VAX 11/7B0 VMS Pascal i\.-fei\ince manual, I)T0;1TA1,. PfllJAVA REFERATA / KRATKEGA REFERATA / STROKOVNEGA POROČILA Prljavo izpolnile s pisalnim slro|ein 1. Naslov relerala ........................................................... 2. Razširjeni povzetek (pribllino 1000 besed) priložite prijavi. 3. Programsko področje referata (obkrožite ustrezno Številko) 1. Pregled tehnologije in uporabe 2. Arhitektura In zgradba računalniških sistemov 3. Upravljanje procesov 4. Sistemski razvojni pripomočki 5. Mali poslovni sistemi e. Uporaba pri Izobraževanju 7. Osebni računalniki e. CAD/CAM mikrosistemi g. Umetna Inteligenca In roboti 10. Računalniška mreže t i. Peta računalniška generacija 4. Razvrstitev referata (obkrožite) t. reterai (pomembnejše delo) 2. kratek referat 3. poročita S. Avtorji: ............ Delovna organizacija: ....................... Ulica: ............................................. Poštna Številka:................... Kraj: ... Država:.............................................. Datum:............. ...............Podpis: Prijavnica, skupaj z dvema kopijama razširjenega povzetka, mora prispeti najkasneje do 1: aprila 1985 na naslov: Informatica 85, 61116 Ljubljana, p.p. 2 VECPROCESORSKI SISTEMI BRANKO MIHOVILOVIC, PETER KOLBEZEIM UDK: 681.519.7 UNIVERZA EDVARDA KARDELJA, LJUBLJANA INSTITUT JOŽEF STEFAN, LJUBLJANA Multiprooasiranje in pomnilniki zelo velikih kapacitet predstavljajo osnovo superrafiunalnikov. Enostaven Ware-ov model veCprocesorskih sistemov . V konceptu obstajajo majhne razlike med alBtansko programsko opremo VP sistema in Blfitena, ki uporablja multiprogramiranje. Operaoijska sistema obeh sistemov vsebujeta naslednje> -Razporeditev virov in upravljanje -Varovanje podatkovne osnove -Preprečevanje sistemskih deadlock-ov -Prekinjevanje izvajanja nenormalnih procesov -PrerazporeJanje vhodno/izhodnih bremen -Prerazporejanje obremenjevanja procesorjev -Rekonfiguracija sistema. Zadnje tri navedbe so speoiliCne, njihova Izvedba pa je zelo pomembna za OS VP sistemov, kajti preko njih se zrcali zahtevana velika učinkovitost OS VP sistemov. Razlikujemo vglavnem tri organizacije OS VP sistemov. To soi master-slave, loäeno izvrševanje za vsak procesor,simetrična porazdelitev med procesorje. Najbolj priaprosta organizacija OS Je vsekakor prva, saj jo lahko od vseh treh vrst OS najenostavneje realiziramo. V bistvu gre za razširitev OS enoprooesorskega sistema na ta naCin, da je v polni meri uporabljeno fflultiprograniranje. Karakteristike tega OS so naslednjei Programe OS izvrSuje vselej samo eden za to namenjen procesor, ki krmili ostale procesorje v sistemu. Na ta naCin je delno reSen problem konfliktnih situacij v sistemu, vendar izpad master enot pomeni popoln izpad oelotnega sistema. Sistem je dokaj nefleksibilen, v slave delu sistema pa lahko pride do preoeJSne izgube Casa in Čakalnih vrst. Sicer pa je lahko tako materialna kot programska oprema dokaj preprosta, sistem pa je lahko zelo uCinkovit v tistih aplikacijah, kjer Je. delo slave procesorjev popolnoma definirano. Iffle za drugo vrsto OS Je nekoliko nerodno, pomeni pa, da imajo vsi procesorji enake lastne OB. Vsak procesor ima lahko svoje vhodno/izhodne elemente, masovne pomnilnike, podatkovno osnovo ali pa je slednja vsem skupna. Pri vsem tem pa obstaja možnost pojava konfliktnih situacij v sistemu. Sistem ni občutljiv na katastrofalne napake, vendar zaradi v/i elementov ni primeren za morebitno rekonfiguraciJo, Tretja vrsta OS Je do neke mere izpeljanka predhodne, predstavlja pa za realizacijo najteüavneJSo vrsto. Pri tej vrsti govorimo o takoimenovanem plavajoCem nadzoru, kar pomeni, da lahko katerikoli procesor prevzame vlogo nadzornega modula v sistemu. Tako je lahko zagotovljena enakomernejSa obremenitev virov sistema. Konfliktne situacije se reSujejo z metodo prioritet, ki je v sistem vneBena statiCno, ali pa se le-ta dinamiCrio spreminja. No, prednost te vrste OS Je moÄnost reduciranja sistema do uporabne velikosti vodno kadar s tem zagotovimo bolJSo izkoriščenost reduoiranega sistema, odnosno posameznih virov. Na(nest:.o z a l< 1 J lj C3 k a- Na koncu opozorimo 8e na dva klJuCna problema, ki se pojavita pri medsebojnem povezovanju veCJega Števila procesorjev. PrviC, s tem, da smo pridobili na "procesni aoCl" sistema, se zastavlja vpraSanJe, kako uporabiti VP sistem pri reSevanju "enojnih"problemov| in drugiC, kako zagotoviti ustrezne- komunikaoije med procesorji in pomnilniki. Reüitev prvega problema zahteva prestrukturiranje programov ali algoritmov, kar naj bi v idealnem primeru potekalo avtomatsko. Drug problem naj bi navidezno resili ite s samo zgradbo VP sistema, vendar to ne zadostuje. Komunikacije med samimi procesorji ter procesorji in pomnilniki morajo, biti tako grajene, da se učinkovito odraSajo na delo, ki ga VP sistem opravlja. To pomeni, da tako naCrtovalec materialne kot naCrtovalec sistemske programske opreme ne moreta reševati koBunikacljskih problemov loCeno, temveC Je potrebno kompleksen problem komunikacij reSevati na tak naCin, da se zagotovi Clm veCja učinkovitost VP sistema. C13 P. H. Enslow Jr. Multiprocessor Organi zation-A Survey Computing Surveys, Vol.9, No.1, Mareo 1977 CB3 S. I. Kartashev, S. P. Kartashev Dynamic Architectures! Problems and Solutions. Computer, Julij 1978 C33 D. Highberger Intelligent computing era takes off Computer Design, September 1984, CM] J, «ilo, B. RoblC Osnovna naCela DF sistemov Informatica 1, Januar 19aS. CS3 N. Hokhoff Parallelism makes strong bid (or next generation computers Computer Design, September 1984. Cb] B. Buzbee Parallel processing makes tough demands Computer Design, September 1984. C73 B. Mihovilovie, P. Kolbezen Paralelno izvajanje opravil v VP Eistemu, 1. del Informatica 3, 198«.. C63 B, nihoviloviö, P. Kolbezen Paralelno izvajanje opravil v VP sistemu, 2. del Informatioa 3, 1984. IdCl O KLASIČNI ALGORITMI ZA ISKANJE MINIMALNIH DREVES KRSTE JOVANOSKI UDK: 519.698 ELEKTROINŠTITUT „MILAN VIDMAR' LJUBLJANA v Članku Je obrsvnavsn problea iakanJa ainiaalnih vpetih dreves. Podana sta dva klasiefna slsoritM ( Prlaov in Kruskalov) za isksnJe ainiaalnih vpetih dreves povezaneaa đrafa. Poles tesa Je podana a naliza Časovna koapleksnosti oaenJenih alaoritaov. NsvaJaao naJbolJ preproste alSoritaet ki reCuJeJ o zaornJi problea. Podsns Je tudi ocena učinkovitosti alaoritas v odvisnosti od ( Stavila toCk in « tevila povezav > arafa» ter praktični nasveti za nJuno uporabo. Med druaia Je opisana «e «trateaiJa za naCrtovsnJe alaoritaov znana pod iaenoa poSreSna aetoda. CLASSICAL AL00RITHEM8 FOR FINDING «INIMUH SPANNIN8 TREES. The paper is concerned with th* Problea o f findina the ainiaua spsnnina tree in the connected araph. Two alaoritheas are aiven (the Pria's a nd the Kruskal's) tor findina ainiaua spannina trees. Analysis of the tiae coaplexitu of the discus sed alaorithas is also aiven. The siaples alaorithas» applicable for solvina the problea« are outli ned. Estiaation of efficienca of the procedure as a function of the araph (nuaber of vertices and n uaber of edaes) alona with practical advices reaardina their application is also presented. The aut hor tackles also the Question of strateau knoun as 'areedu aethod*. Kot zaled za uporabo rainiaalneaa vpeteaa dreves 3 si nislimo reSevanJe problenov povezanih elek triCnih ( raCunalniSkihf telefonskih« daljnovod nihi televizijskih)« cestnih« železniških« vodo vodnih« Plinskih ali toplovodnih oareSJih. ReSi tev zaornJeas problena« naa lahko da naJbolJ va rCno investicijo. ZaCniao kar z definicijo prob lena. Def.: Naj bo G=(V«I c 5 P —> R Naj bo T PovezE iniaalno vsoto Bin( ^ c) eeE(T) potea praviBo T-Ju ainiaalno vpeto drevo. ZaornJi problea boao refievali s PoSreßno metodo . PožreSna aetoda Je preprosta strateaiJa« ki o biCaJno vodi v učinkovit postopek. IneJno množico z n eleaenti ali kazalci nanJe« -C aCil i ieJ > « Jc< i«2>3«....«n > « ki zadoSCa dania zahtevaa in optiaizira krite riJsko funkcijo f. PodanoSici« ki zadoSCa za htevaa« reCeao dopustna. Dopustna anoSica« ki optiaizira kriterijsko funkcijo« Je OPtiaalna. Osnovna nisel strateaiJe Jet ReSitev aradiao po stopoaa. Na tekoCea koraku poiSCeao eleaent« za katereaa bi bila naJbolJ navdufiena kriterijska funkcija. SpreJaeao aa le« Ce Je tudi s tea eie aentoB razSirJena nnoSica dopustna. Problea ain iaalneäa vpeteaa drevesa boao reSevali« tako da boao izbirali postopoaa povezavo za povezavo. NaJ bo D podanoSica povezav oareSJa O« ki sao J o zaradili do daneaa koraka. NaJ bo D' anoSica povezav« tako da Je D'= D U

p!= nova bo dopustna « Ce v D' ni cikla. Za vrstni red i zbiranja uporabiao vrednost povezave. Postopek« ki aradi reCitev« tako« da Je reSitev vseskozi dravo laenUuJe»o Prlaov poštopek» Postop«k> ki tfradi ratfitevf.tskor da Ja réfiitav vseskozi aoz df ki le na koncu preraste v drevo laenJuJeao Kruskalov« . 1. Prlaov alđorltea Vektor r bo vseboval indeks naJblitJed» soseda. r{ V -> M _ O JeV J l-> r£J3»" I ^ l_ t Bin < cCJrll > c£J>t3 ieW Refltav aradiao kot drevo» TekoCi kandidat Je p ovezavar ki veta vozliflCe drevesa z vozlieCeaf ki Se ni v drevesu in iaa ainiaalno vrednost» ozimea drafa O na tekoCea koraku rsspadeJo na dva disJunktni anoSicir na vozlifitia tekoCeaa dr evesa D in preostanek. Povezava» ki Jo privzsae Bor iaa eno voziisee v drevesu» drudo pa v preo Stanku grafa. Za dano vozliCee vriE pride v t •koCaa koraku v izbor naJkrsJSa od povezav» ki sa zaCno v vozlfseu v in konCaJo v katereakoli vozliHeu tekoCeda drevesa. Torej Je povsaa dovolJ» da poznaao k vozliseu v najbližje vozliSCe v tekoCea drevesu D> Ce le 1 ahko od tod doloCiao dolZino povezave v konstan tnea Času. PotrebuJeao naslednje operacije Časovna zahtevnost postopka Je 0( n > saJ sta dve n korakov doldi zanki vdraJeni druda v drua o. 2. Kruskalov aldoriten RazviJeao fie drudi postopek. Po privzetku dradi bo dozd in tekoCo nsJceneJtSo povezavo privzaaem or Co ne naredi zanke. To pa bo natanko tedaj> ko obe vozlieei povezave nista v iste» d revesu» v isti koBPonenti. Operaciji» ki Ju potrebuJeao sta 1) Ali Je vozli«ee 2a v D T 2) Katero vozll«(!e drevesa D Je k v naJbliSJe ■ T ■ , t 3k Popravi tekoCo reSitev D. Braf boso predstavili z aatriko c. cCitJlt" vrednost povezave z kraJieei v in v . i J 1) Uaotovi zli«t!e. 2) SpoJi I/o. Preden izpolJeao postopek» si Se izbsriBO preds tavitev drsfa. Postopek zahteva» da povezave ur ediao po nepadaJoCih vrednostih. Povezave Srafa in nJihove vrednosti nafiteJoBO v saznaBU a s koBponentani. procedure ainisalno vpeto drevo po Priau < n»c»vrednoet»drevo )l < procedura poiSCe v drafu z n vozlifiCi in z'vrednostai povezav cCitJl >" O» 1»J a l>2>...>n - 1 in vrednostjo vrednost. Ce drevesa ni BoaoCe poiskati» Je vrednost neskonCno.> eeain ;°> povezava z Biniaalno vrednostjo t vrednost t> cCi>kl> ( drevoCi» 13»drevoCl»21 t» (k>l>> for i t» 1 to n do Bedin poisei J i 1 <• J <°n »tako da Je vCJl i« O in c[J»rtJ}3 ainiaalna t ( drevoCi»!] » drevoCi»23 <» vrednost t» vrednost + cCJtrCJIl) » rCJJ »- O I for k t» 1 to n do if r[K3 ^ O and cCk»r[k33 > ci:k»J3 then r[k3t°J End (liJtcCitJl) CU I 1 - lt2f...iait kJ*r J« • - IPI. o vozlKCt J« 0> - 0(n « lo«(n>> It > ■lad« na vradnoati povazav» Pri izbiri aalsai a pradatavitva lca r 2-3 dravor naJbolJ la o dravor lid«> bo ta zahtavnoai 0<* • loa(a>)> ■IPI« Koaponania takoCa raSitva vodiao kot ano Ica toek. Ca ai Izbaraao učinkovito pradstavit v za anoSicat boat« oparaciJi polKCi In uniJa raktitfno takll v konatantnaa Caau» toraJ k cel ti rrinaall kvaCaau 0(a)• ~ Izrak t Kruakalov PostoFak ------ .ti 0(a > lqa> in Izrak t PraJtnJi alaorita* poiiea ainiaalno Dokaz t Na J bo O povazanot nauaaarJan Mrafr D. ------- anoSica povazav ärafai ki aa konatruira poatopak» D' i* D pa anoSica povazav ainiaalnaaa ilJa Za arafp ki Ja polni Ja IDI - II 0) - 0( n loa(n>> ToraJ lahko poiteaao povazavo p« ki iaa aad v«a ai povezavaai oaD in oéD' ainiaalno cano« Vstav procadura ainiaalno vpeto drevo po Kruskalu ( n> a> vrednostf drevo)I < Procedura sestavi ainiaalno vpeto drevo po Kuskalu« Braf Je podan kot vrst a s prednostjo a> v kateri so nsSteti podatki (itJrcCitJ) in iaa naJkr aJfla povezava prednost» KonCno drevo sestavlja seznaa zaCetnih in konCni h vozliče veJ drevesa ( drevoCirll« drevoi:ir2]> i " l>2>.>.>n - If in Je vrednost vrednosti. Ce drevesa ni aodoea sestaviti Je vrednost t- neskonCno > Beain for i t- 1 to n do oCeCil t- -1 t < vozliCea so na zaCetku vsako v svoJi koaponenti > k t« O t vrednost t" O I While k < n - 1 and not prazna poicei (oCa t up > VP>I it up M vp than Beain < Nova povezava na naredi cikla > k «» k ♦ 1 I (drevoCkil3>drevoCki2]) I- (utv)» vrednost i- vrednost f ctuivll < BpoJiao koaponantii ki Ju (utv) PovazuJe. } uniJa( oCe p up > vp ) End End t if k > n-1 then vrednost t« neskonCno lao p v D'I V D' doblao natanko en clkelt podsn o na prlaer z zaporedje» povezav tl Dokaz Je konCan> p f pC13i tpCr3, ZAKLJUČEK V teB zaporedju Je vsaj ena povezava* recino pCJ]> ki nI v Dr saJ bi druäaCe D vseboval cike 1. Trdiaò f da Je ctptJ3D i clp3. Resi po izbiri p < p Je nsJkraJfia povezava! > » o vse povezave z BanJSo ceno. cCol < cCp] I oeD' Poleä klasiCnih postopkov za reCevsnJe probleaa o BininalneB vpetih dreves« obstajajo «e bolJ u Cinkoviti postopki z u^odneJSo Časovno zahtevno stJo. UporablJaJo bolJ koaplicirane strukture p odatkov in njihova analiza Je bolj zapletena. Z aradi teaa eea se odloČil predstaviti sano klas iCne aldoritoie. V zadnjih letih sreCaao Se para lelne aläoritae. Uporaba se bo uveljavila z upe IJavo aoCnih veCprocesorskih sisteaov. v D natanko tedaJ kot v O'< Toda vse povezave o čCoKcCplf oeD' ne tvoriJo cikla s pCJI in pCJl« ki bi prifila p reJ nc vrsto kot p» Ce bi velJalo cCpCJ13 < cCp}. ZAHVALA Na koncu se zahvaljuje* vsear ki so ai poaaaali in ae spodbujali pri realizaciji teäa eianka. P osebeJ se zahvalJuJea Dr. R.E.TarJanu za korist ne suaestiJe» Dr. J. Kozakur Drt T. Pisanskeau in V. BataaelJu. SaatBViao novo drevo D*i I D*I»D' U

- « LITERATURA vr«dnoet(0*> i vradno*t<Đ')» Drevo D* sd v eni povezavi veC uJeaa z D. Posto pek PonavlJaao toliko Casar da optiaalno drevo prevedeao na drevo> ki naa aa da Kruskalov post OPekr ne da bi pri te* poveCali nJeaovo vrednos 1. J.B. Kruskalr Jr.r On the shortest spannine subtree of a araph and the traveling salesaa n problear Proc. Aaer. Hath. Boc.f 7r pp. 1389-1401 3. R.E.TarJan < Privatno sodelovanj« ). Posvetovanje in seminarji Informatica '85 Nova Gorica, 24.-27, september 1985 Posvetovanje 18. jugoslovansko mednarodno posvetovanje za računalniško tehnologijo in uporabo Nova Gorica, 24.-27. september 1985 Seminar)! Izbrana poglavja iz računalniške tehnologije in uporabo Razstava Razstava računalniške tehnologije, uporabe, literature in drugih računalniških naprav, z mednarodno udeležbo Symposium and Seminars informatica '85 Nova Gorica, September 24th-27th. 1985 Conference 18lh Yugoslav International Conference on Computer Technology and Usage Semlna-s Selected Topics in Computer Technology and Usage Nova Gorica. September 24lh-271h, 1986 Exhibition Exhibilion ol Computer Technology, Usage, Literature and Other Computer Equipment w/ilii International Participation Nova Gorica, September 24th-27th, 1985 Rokl 1.apnl1985 Zadnji lok za sprejem formularla ■ s prijavo in 2 izvodov razširjenega povzetka 15. julij 1985 Zadnji rok za sprejem končnega leksta prispevka. Deadlines April 1, 1985 Submission of lha application form and 2 copies o( the extended summary July 15, 1985 Submission ol the full text of contribution GOVOR V STROJEM KOMUNI KACI JI MED IN ČLOVEKOM DAVOR MILJAN IN JURIJ ŠILC UDK: 681.3:007 INSTITUT „JOŽEF STEFAN' LJUBLJANA Podan je zgodovinski razvoj in danaSnje stanje na podroCju analognih in digitalnih govornih sistemov. Narejen je pregled nekaterih najbolj pogosto uporabljenih metod za sintezo govore iz skupine kodirnikov/dekodirnikov signalne krivulje ( PCM, DPCM, ADPCM, DM in CVSD metoda) in iz skupine vokoderjev kot so LPC, formantna in kanalna metoda. Machine - Wan Comunication by Voice Historical evolution and state at art of analog and digital speech systems is given. Ue have rewiewed some most used methods for speech synthesis from grup of waveform coders (PCM, AOPCM DM and CVSD method) and vocoders i Postopek, po katerem so zgrajeni digitalni govorni sistemi prikazuje Slika 2. OCitna je velika podobnost z analognim sistemom, ki ga prikazuje Slika 1. Vhodna in izhodna stopnja digitalnega sistema sta A/D in O/A pretvornika, osrednji del pa je popolnoma digitalen. Digitaliziran naravni govor (digitalno zapisan besednjak) se hrani v digitalnem pomnilniku. Naloga sistema za sestavljanje sporoCil Je izbiranje digitalno zapisanih enot govora (glas, zlog, beseda, fraza) iz pomnilnika in generiranje poljubnih novih sestavljenih enot (beseda, fraza, stavek). ' Postopek- digitalnega shranjevanja in generiranja govora, kot Je prikazan v sploSnem diagramu, dopuSCa zelo razliCne postopke načrtovanja digitalnega govornega sistema. KljuCni faktor je v naCinu digitalnega shranjevanja govornih enot, ki sestavljajo besednjak. Izbira kodirnega postopka, zelo upliva na kvaliteto generiranega govora in velikost digitalnega pomnilnika, ki je potreben za shranjevanje besednjaka. GOVOR _ (vhod) A/D=> sistem za pripravo besednjaka :0 digitalni pomnilnik zahteva _ sporoC i 1 a sistem za sestavi janje sporoCi1 H D/A T GOVOR (izhod) Slika 2: Digitalni govorni siste Obstajata dva osnovna naCina digitalne predstavitve naravnega govora. PrviC neposredno kodiranje govorne valne oblike in drugiC, analiza govorne krivulje, s katero se dobijo parametri, ki opisujejo analiziran govor in so v sploSnem parametri za krmiljenje modela govornega trakta. Objektivni kriteriji za vrednotenje digitalnih govornih sistemov Se niso institucionalno standardizirani in rabijo le kot smernice naörtovalcem tak«nih sistemov. V C323 so podani nekateri merljivi parametri,, ki temeljijo na razliCnih S/N (signal to noise) razmerjih. Ocenjevanje kvalitete govornih naprav je v veliki meri subjektivno in se izvaja na Ctevilnih poskusih v obliki poslušanja strojno generiranega govora. ' Pri tem so v pomoC množice "standardnih" stavkov, ki so tako izbrani, da vsebujejo vse fonarne nekega Jezika v raznih kombinacijah. Pomembni so trije kriteriji: razumljivost in kvaliteta produciranega govora ter cena sistema. Elementarni pogoj je razumljivost, ki pa mora biti pri velikem Številu aplikacij veC kot samo razumljivost. Kvaliteta govora ni v neposredni zvezi z razumljivostjo. Je zgol 1 subjektivna ocena, . ki pravi, da Je viLko kvaliteten govor najbolj podoben naravnemu govoru, nekvaliteten pa je metalni - robotski govor V cava so _,elinirane Stiri stopnje kvalitete govornih sišteroovi " R^i dosežemo frekvenäno Območje med O Hz in 7 KHz ob minimalnih popaCitvahj -telefonska, v katero sodijo sistemi, ki qSb 2 in''!»"?"''"" obmoCje mad 200 - 3200 Hz, SNR i 30 dB ter popaCitev signala i 2-3 X ; - komunikacijska, ki Se ohranja visoko razumljivost ob obCutno slabSi kvaliteti In veCjih popaCitvahj - sintGtiCna, kl Jo dobimo pri t.l. vokoderjih ko govorni signal Izgublja naravnf ivok in deluje metalno-robotsko. Ko doseife sistem zadovoljivo stopnjo razumljivosti, preostane načrtovatcem Se izbira komproinisne reSitvc glede cene In kvalitete . govora, ob upoštevanju tipa aplikacije. Tako Je na primer, pri banCnih avtomatih zaieljen zelo kvaliteten, naravnemu govoru podoben zvok, za razliko od govornih sistemov pri video in igralnih avtomatih, kp aetatni zvok ne moti, ali je celo zaiieljen. Natanäna reprodukci j Robotski zvok PCM CVSt grt^gonalni pfšovM Fc rmanti i' 10 100 1k 10k 10Qk zasedenost pomnilnika CbitQv/sec3 Slika 3i Kvaliteta govora v odvisnosti od pretoka informaoije. V sploSnera lahko reCerao, da je cena govornega sistema sorazmerna ceni ipomni Inik a . Razlitini postopki kodiranja ali parametriziranja govora narekujejo razliöne velikosti pomnilnikov in razliäne kvalitete govora. Razmerja med temi parametri prikazuje diagram na sliki 3. CI], A n «a 1 i. z a i n s i n t ei' i: g o v o IT . 2e prej sta bila omenjena dva osnovna naöina delovanja analizatorjev in 'sintetizatorjev govora. Prvega imenujemo "kodiranje signalne krivulje" in kot Jfe naziv pove, teifimo pri tem naäinu k öimbolj natanäni reprodukciji govornega signala. Neobčutljivost takSnih sistemov na Številne govorCeve lastosti in na vpliv Suma ter manjSa kompleksnost izvedbe je dosejfena z vedjlm pretokom podatkov (bit rate). Kodirniki signalne krivulje se lahko optimizirajo glede pretoka podatkov ter se ob upoštevanju statističnih rezultatov pri obdelavi govornih vzorcev, Se bolj prilagodijo karakteristikam govornega signala. Drugi natiin kodiranja temelji na skopem opisu parametrov govora, ki izhajajo iz ugotovitev o tem, kake govor nastaja. Taksne govorne Bistome imenujemo ' vokoder ti (voice coder). da je mehanizem nastajanja na dva loCena delai izvor trakt, ki oblikuje zvok v da izvor zvoka oddaja periodiBen zven in Sum, ki ga ustvarja zraCni tok ter, da govorni trakt lahko simuliramo s spremenljivimi filtri. S Številnimi meritvami lahko doBBÜemo optimalne vrednosti krmilnih parametrov in s tem tudi dobro kvaliteto govorai . kar v praksi ni vedno izvedljivo. Vokoderji obitìajno generiraju manj kvaliteten (sintetični) govor ob minimalnem pretoku in in kanalnih, ki sodijo med frekvenCne vokoderje. Slika 5i LPC generator govora. Formantni vokoderji Formantni generatorji govora so po materialni opremi zelo podobni LPC sintetizatorjem (Slika _Ó). Razlika je v tem, da se pri tej metodi uporabljajo podatki o poziciji srediääa in pasovnih Širin formantnih frekvenc. ki so rezultat predhodne analize govora. Formanti so področja z visoko govorno energijo C33, ki so prisotna na razliCnih frekvencah govornega signala in so v bistvu resonanöne frekvence govornega trakta. FO 50 . . 250 Hz Fl 200 . . 900 Hz F2 600 . . 2500 Hz F3 1500 . . 3000 Hz F-; 3000 . . 4000 Hz F5 ...... • •••(•■ . • * Sum 3000 . .>8000 Hz LPC vokoderji Osnovna ideja linearne predpostavka, da Ce ugo informacije vsebujejo o predhodni vzorci, priöakujemo, njimi do doloöene mere napoved Govor se analizira tako, govorni signal najprej vzorCi a in 10 KHz. Iz analize vzo vrednosti krmilnih paramet filtra, doloCa se ali je zvok osnovna frekvenca ter amplitud predikcije je tovimo, koliko i-tem vzorcu, da bomo lahka z ali i-ti vzorec, da se analogni s hitrostjo med rcev se doloCijo cov digitalnega zvenek ali ni in a govora. Btevilo krmilnih parametrov digitalnega filtra je odvisno od željene kvalitete govora in znaBa med 10 pri slabSi Kvaliteti do 12 pri dobri kvaliteti reproduciranega govora. Pretok informacije je pri tej metodi med 3000 in 1000 bitov/s, kar se doseSe z dodatnim krüenjem shranjenih podatkov. V primerih, ko se zahteva samo razumljivost govornega sistema pade pretok informacij med 1000 in 20 bitov/s. Sinteza govora z LPC metodo je razdeljena na dva osnovna delaj krmiljenje vhodnega signala in krmiljenje digitalnega filtra (Slik.i 5). Vhodni signal (zvok) ima dva vira. Generator psevdo naključnega Buma omogotSa nastajanje nezvenetiih glasov. Generator tistega .:vena (pravilni periodični signal) omogoCa nastajanje zveneCih glasov npr. samoglasnikov. Govor nastane tako, da se vhodni signal (Bura ali periodični signal doloCene frekvence) doloCene amplitude oblikuje skozi N-polni LPC digitalni filter, ki predstavlja model Človeškega govornega sistema. Tabela 2i Področja formantnih frekveno za moSki glas. OblCajno so tri ali Stiri formantne frekvence, ki se gibljejo za moSki glas med vrednostmi, ki so prikazane v tabeli 2. Formantne frekvence ženskega glasu so približno 25r. viSJe. Pasovne Širine posameznih formantnih frekvenc se doloCajo algoritmiCno pri sintezi, ker v sploBnem, natanCno doloBanje pasovnih Sirln ne upliva direktno na kvaliteto generiranega govora. Opisana metoda omogofia Se manjSi pretok informacije, ki se giblje med 600 in 800 bitov/s za kvaliteten govor. Slika 6i Formantni generator govora. Z a k 1 Juäe k Litejratut- Posebno podroCje pri govorni komuniKaciji med strojem in eiovekoiii predstavljajo sistemi za pretvorbo teksta v govor, Vi se poyosto uporabljajo pri govoreCih terminalih ali pisalnih strojih in so v veliko pomofi vidno prizadetim osebam. Pri teh sistemih predstavlja posebnost dovolj bogata banka znanja o prevajanju pisanih besed v govor Clt, 173. ObiCajno se vhodni tekst z rattunalnikom prevede v foneme ali zloge, ki se potem s pomoCjo ene od zgoraj omenjenih metod oblikuje v govor. V zadnjih letih se pri generiranju govora uporabljajo sploSni, ali posebno za govor zgrajeni, hitri signalni procesorji. Zaradi hitrosti procesiranja omogoCajo izvajanje algoritmov s katerimi simulirajo posamezne dele analognih vezij, ki gradijo LPC ali tormantne digitalne filtre CIS,11,50: . Tako LPC kot formantne generatorje govora lahko te nekaj let kupimo na tr^iSäu v obliki integriranih vezij, kompletov integriranih vezij na tiskani ploäöi ali govornih sistemov. Lahko naštejemo nekaj proizvajalcev: American' Microsystems (LPC 1A00 bitov/s). General Instruments (LPC vezja in ploSCe), Centigram (PMC metoda podobna LPC, '.SOO bitov/s), EGiG Retioon (signal procesorji), E-Systems (LPC, 2AOO bitov/š). Mimic Electronics (vezja in ploööe), ITT Semiconductors, Matsushita, National Semiconductor, Nippon Electronic , Sharp, Telesensory Systems, Texas Instruments, Toshiba, Triangle Digital Services (ploeöe, 650-65QO bitov/s), Votrax, Yahara (govorni sistemi) in mnogi drugi. Poaroöja uporabe opisanih govornih sistemov so razliäna. Izbira metode in postopka je odvisna od zatitevanu kvalitete in cene izdelka. Znani bo govorni sistemi za raöunalniSho generiranje oüiöevalnih list, za telefonifino sporotianje razliönih podatkov in informacij o telefonskih nabojnikih in vremenskih podatkih ter podatkih o oenah proizvodov ter za sporoöanje podatkov o letalskih poletih. Poleg velikih sistemov obstajajo in Se nastajajo rieStete manjSe aplikacije ob privatnih raBunalnikih, za alarmna sporočila, za navodila pri uporabi razliCnih proizvodov in podobno. V prispevku smo podali pregled zgodovine in sodobnega stanja na podroöju raöunalniBKe sinteze govorjenega naravnega jezika. Glede na aktualnost in uporabnost podredja (pri tem naj zlasti omenimo generiranje govora iz odprtega teksta/sporodi1/podatkov) in glede na dejstvo, da bo moral vsak (vsaj majhen) narod sam poskrbeti za osnovne raziskave -brez katerih ni mogoba kvalitetna aplikacija danaSnjih tehniönih moZnosti - na podroBju morfofonoloSkih znafiilnosti svojega jezika, je smiselna napovedati naslednji prispevek s sledeCo vsebinol - pregled dosedanjega dela in doseKenih rezultatov pri nas na podroöju matematičnih in tehniönih osnov (materialna in programska oprema) na podroöju sinteze govora} - oris pristopa k osnovnim raziskavam posebnosti slovenfiöine, ki jih moramo obvladati, te naj naSi sintetizatorJi govorijo slovensko in ne ameriSko slovenščino; - pristop k ustvarjanju ustreznega materialnega in programskega okolja za osnovne in aplikativne raziskave sinteza slovenSöine, C13 Voice Input/Output sistem and devices, Electronic Engineering, May 1982, page 76-101 C23 James L. Flanagan i Computers that Talk and Listeni Man - Machine Comunication by Voice, Proceedings of the IEEE, April 1V67, page ".OS - «,15 C33 Laurence R. Rabiner, Ronald W. Schäfer: Digital Tehniques for Computer Voice Response Implementations and Applications, Proceedings of the IEEE, April 1V67, page 416 - 432 CM3 Raymond Steele : Chip delta modulators revive designer's interest, Electronics, October 13, 1977, page 86, - 93 CS3 Earle West : IC trio simplifies speech synthesis, Electronic Design, October 26, 1982, page 175 - 178 Ct3 FX-209 Analogue / Digital Converter, Product Information,Consumer Microcircuits Limeted C7] Steve Carcia : Use ADPCM for Highly Intelligibile Speech Synthesis, Byte, June 1983, page 35 - 49 can Cecil H. Coker i A Model of Articulatory Dynamics and Control, Proceedings of the IEEE, April 1967, page 452 - 474 CI] Computing Power Boosts Speech Quality, Digital Design, May 1982, page 44 - 50 CIO] Gene Helms t, Steve Petersen : Portable speech development system creates linear predictive codes, Electronics,September 8, 1982, page 151 - 156 Cll] Speech synthesis! devioe and applications, Electronic Engineering, January 1981, page 41-57 C12D Roger J. Godina ! Voice input output : a special report. Electronics, April 21, 1983, page 126 - 143 C13] R. Pickvace : Speech synthesisj the new frontiers, Electronic Engineering, Juli 1980, page 37-52 cm] Kathryn Pons and Tim Gargaliano : Articulate Automata: An Overview of Voice Synthesis, Byte, February 1981, page 164-187, C15] Noriko Umeda ; Linguistic Rules for Text - to - Speech Syntheses, Proceedings of the IEEE, April 1967, page 443 - 451 Clb] A. Yatagai : Limited and unlimited vocabulary speech synthesis systems, Electronic Engineering, November 1980, page 31-41 C17] Jonathan Allen : Synthesis of Speech from Unrestricted Text, Proceedings of the IEEE, April 1967, page 433 - 442 CIS] Edward Bruckert, Martin Minow and Walter Tetshner I Three-tiered software and VLSI aid developmental system to read text aloud. Electronics, April 21, 19B3 , page 133 - 138 Cn] M.E.Hoff and Matt Townsend i Single-chip NMOS microcomputer processes signals in real time, Electronioa, March 1, 1979, page 105 - 110 CEO] M.E.Hoff and Haillace Li i Software makes a big talker out of the 2920 microcomputer, Electronics, January 31, 1980, ^age 102 - 107 C51] Veljko' Zgaga t Sinteza govora u mikroraöunarskim sistemima. Zbornik Informafica 77, Bled 1977, 2 212 CE2] James Ć. Anderson : An Extremely Low-Cost Computer Voice Response System, Byte, February 1981, page 36 - 43 • Zaradi pomanjkanja domaČih prispevkov o tet temi Je podan obseÜneJSi spisek tujih prispevkov, ki obravanavajo podrotìje' sinteze govora. C333 Tomihlro Matsumurai Future hlonjpraaassor Trends, Intormation Processing 83, R.E.A.MasonCed.) page 213 - 217 CSM3 Bruce LeBossj Speech I/O is making itself heard, Eleotc-onics, May 22, 1?&0, page 95-105 C5S] Hlchaet U. Hutchins and Lee Dusek : Hau Vocabulary Is Generated Determines Speech Quality, Computer Design, February 198'!, page 89 - 96 C2t3 Single Silicon chip synthesizes speech in ♦SO learning aid. Electronics, June 22, 1978 Ca73 James L. Flanagan, Manfred R. Schroder, Bishnu S. Atal, Ronald E. Crochiere, Nuggehally S. Jayant, Jose M. Tribolet ; Speech Coding, IEEE Transaction on Comrnuniaations Vol. C0I1-27, No. A, April 1979, page 710 - 735 C2a3 R.E.Crochiere,S.A.Webber and J.L.Flanagan Digital Coding of Speech in Sub-bands, The Bell System Technical Journal, Vol 55 No 8, October 197i, page 10t9 - 1085 C21] O.J.6oadman,B.J.ncDcrmot and L.H.Nafcatani; Subjective Evaluation of PCM Coded speech. The Bell System Technical Journal, Vol 55 No 8, October 1976, page 1087 - 1109 C3D3 N.S.Jayant t Pitch-Adptive OPCM Coding of Speech Ulth Tuo-Bit Quantization and Fixed Spectrum Prediction, The Bell System Technical Journal, Vol 56, No 3, March 1977, page A39 -45A C313 L.R.Rabiner, C.E.Schmidt and B.S.Atal i Evaluatin of Statistical Approach to Voiced - Unvoiced - Silence Analysis for Telephcne-Suality Speech, The Bell System Technical Journal, Vol 56, No 3, March 77 page 455 -A82 caa3 D.J.Goodman, C.Scagliola, L.R.Rabiner and J.Goodman Subjective Performance Connections of Waveform LPC Vocoder, The Bel 1 R.E.Crochiere, I Objective and of Tandem Coders with an System Teohnioal Journal, Vol 58, No 3, March 1979, page 601 - 629. C33] J.J.Dubnowski and R.E.Crochieres Variable Rate Coding of Speech, The Bell System Technical Journal, Vol 58, No 3, March 79 page 577 - 600 C3M3 N.S.Jayant and S.W.ChriStensen i Adaptive Aperture Coding for Speech Waveforms - I, The Bell System Technical Journal, Vol 58 No 7, September 1979, page 1631 -16',5 C3S3 J.L.Flanagan, J.D.Johnston, J.W.Upton i Digital Voice Storage in a Microprocestior, IEEE Transac. on communicat. Vol COM-30, No 2, February 1982, page 336 - S'^S informatica «35 Vabilo k sodelovanju Call for Papers Posvetovanja In seminarli Informatica '85 Nova Gorica, 24.-27. september 1985 Posvetovanje 18. jugoslovansko mednarodno posvetovanje za računalniško tehnologijo in uporabo Nova Gorica, 24.-27. september 1986 Seminarji Izbrana poglavja iz računalniške tehnologije in uporabe Razstava Razstava računalniške tehnologije, uporabe, litera-luio in drugih računalniških naprav, z mednarodno udeležbo Symposium and Seminars Iniormatica '85 Nova Gorica, September 24th-27lh. 1985 Conterence 18th Yugoslav International Conference on Computer Technology and Usage Seminars Selected Topics in Computer Technology and Usage Nova Gorica, September 24th-27th, 1985 Exhibition Exhibition ol Computer Technology, Usage, Literature and Other Computer Equipment v^ilh International Participation Nova Gorica, September 24lh-27th, 1985 Roki 1. april 1985 Zadnji rok za sprejem lormularja s prijavo in 2 izvodov razširjenega povzetka 15. julij 1985 Zadnji rok za sprejem končnega teksta prispevka Deadlines Aprii 1, 1985 Submission of the application form and 2 copies of the extended summary July 15, 1985 Submission ol the lull text ol contribution UPORABA DIGITALNEGA I N KR E IVI E N TA L N E G A DAJALNIKA KOTA V Ml KRORAČUNALIMISKEM KRMILJU INDUSTRIJSKEGA RO B O T A S. ZORMAN UDK: 681.3:51 INSTITUT JOŽEF STEFAN, LJUBLJANA članek podaja princip delovanja digitalnega inkrementalnega dajalnika kota, ter opisuje potrebno dodatno logiko, pri njegovi uporabi v mikroračunalniškem krmilju industrijskega robota. APPLICATION OF A DIGITAL INCREMENTAL ENCODER ON A MICROCOMPUTER CONTROL SYSTEM FOR INDUSTRIAL ROBOTS This paper describes the principle of operation of a digital incremental encoder and the supplementary logic which is necessary for its application on a microcomputer control system for industrial robots. 1. UVOD Linearne in rotacijske premike v zglobih industrijskega robota lahko merimo z analognimi ali digitalnimi merilniki. Doslej smo pri robotih, ki smo jih razvili na Institutu Jožef Stefan, uporabljali za merjenje lege analogne servopotenciometre. Merjenje lege s servopotenciometri ima svoje dobre in slabe strani. Dobro je, da je informacija o legi dana absolutno, kar pomeni, da poznamo pravo lego tudi takoj po zagonu sistema. Po drugi strani je analogni signal servopotenciometra podvrže» motnjam. Na informacijo o legi vpliva linearnost po1tenqioti»tra, potrebna pa je tudi analogno/digitalna (A/D ceiroma digitalno/analogna (D/A) pretvorba, če naj bi izmerjeno lego primerjali z želeno. Zato, da bi se izognili vplivu motenj in potrebi po A/D oziroma D/A pretvorbi, smo namesto servopotencio-metrov uporabili kot merilnike lege digitalne inkremen-talne dajalnike kota. Üporaba digitalnih inkrementalnih dajalnikov kota ima za posledico težave z zagonom sistema, ker ob zagonu nimamo veljavne informacije o legah segmentov robota. S primernim postopkom ob zago-nii sistema postane ta pomanjkljivost nepomembna. Prednosti, ki jih nudi ta način merjenja lege, so zmanjšana verjetnost vpliva motenj, izognemo se potrebi po A/D oziroma D/A pretvorbi in poveča se točnost meritev. Namen članka je, da nas seznani z možnostjo uporabe digitalnega inkrementalnega dajalnika kota kot merilnika lege v mikroračunalniškem krmilju industrijskega robota. 2. PRINCIP DELOVANJA DIGITALNEGA INKREMENTALNEGA DAJALNIKA KOTA Digitalni inkrementalni dajalnik kota (SI. 1), v nadaljevanju dajalnik kota, je sestavljen iz ohišja, v katerem je v ležaj vpeta os, na katero je pritrjen disk z režami. V ohišju je poleg že naštetega še svetlobni vir, fiksno nameščen zaslon z režami ter elektronika s svetlobnimi detektorji. Disk, ki je pritrjen na os je izdelan tako, da je za svetlobo iz svetlobnega vira nepropusten povsod, razen na svojem obodu. Na obodu diska so izdelane reže, skozi katere prodira svetloba iz svetlobnega vira. Reže imajo radialno smer in so vse enake, dolžine, razen ene, ki je podaljšana. Svetlobni vir je nameščen na eni strani diska, na drugi strani diska pa se nahaja zaslon z režami in za njim svetlobni detektorji. Reže na zaslonu so razporejene v dve skupini in eno osamljeno režo. Zaslon je nameščen tako, da se reže na zaslonu precizno ujemajo z režami na disku. Skupini rež na zaslonu sta med seboj tako zamaknjeni, da če zavrtimo disk v tak položaj, da se reže prve skupine ujemajo z režami na disku, so reže druge skupine samo do polovice ujete z režami na disku. Na vsakega od detektorjev svetlobe pada svetloba le skpži eno od skupin oziroma osamljeno režo zaslona. Tako dobimo tri električne signale (SI. 2), ki so potrebni, da je mogoče slediti legi osi dajalnika kota. S pomočjo vseh treh signalov dajalnika kota in zunanje dodatne logike je mogoče slediti legi osi dajalnika kota. 3. DODATNA LOGIKA Naloga dodatne logike je, da iz signalov dajalnika kota izlušči informacijo o legi in jo posreduje računalniku krmilja na njegovo zahtevo. Bločno shemo dodatne logike prikazuje slika 3. Signali dajalnika kota vstopajo v blok z vhodnimi ojačevalniki in invertorji (blok 1. ), ki so potrebni zato, da je mogoče preko enake dodatne logike priključiti dajalnike kotov različnih proizvajalcev. Elementi tega bloka nam dobro služijo tudi za definiranje pozitivne oziroma nega- ' tivne smeri vrtenja. Kakšoii najmanjši proniik jo potreten, da se nam spro-rnuni slanjo sii-nacijo loijićnih nlvojuv ialiodniti signalov dajalnika kota, V priinoru, da ima ilajalnik kota rož na obodu diska, tedaj je tijeijovo os v idealnem primeru potrebno zasukati za 0.03r> kolne stopinjo, da l)i so njocjovo izhodno stanje spremenilo. S tem je ptxiana tudi maksimaltia ločljivost premika sorjmenta robota, ki je spol z danim ilajalniKom kot;i. Zato, da bi se navedena ločljivost dosegla, je potrebno dotoktirali vsako spromombo stanja dajalnika kola. Ob vsaki detoktirani spremembi jo potrebno prožili števni impulz za števec in določili smer štetja, ki mora ustrezati smeri vrtenja osi dajalnika kota. Vezjo z vloyo yenciratorja števnili impulzov (blok 2) jo preprosto logično vezjo, sostavljeno iz dveh liXOH vrat in zakasnilne(ja l(C člena (sl.l). Na isti sliki je prikazana tudi medsebojna odvisnost vseh signalov vozja. Vhodna signala za «joneralor številih impulzov sta signala A, U, ki imata obliko vlakov imulzov, če se os dajalnika kota vrti. Vozjo na sliki 4. ob vsaki spremembi logičnih nivojev enega ali drugega vhotlnccja signala, na izhodu generira kratek impulz, katoroga širina je definirana a časovno konsianlo RlCl. Naloga števca (blok 7) je, da ob prihajajočih števnih impulzili svojo vsebino povečuje ali zmanjšuje po ena, odvisno od smeri vrtenja osi dajalnika kota. Informacija o smeri, ki jo dobiva števec, mora biti točna le tedaj, ko pride do števca šlevni impulz, sicer pa to ni nujno potrebno. Informacijo o smori gibanja osi dajalnika kola izluščimo Iz islili dveh signalov, ki služita tudi za generiranje števnih impulzov. Signala sla fazno zamaknjena. Kateri izmed olxjh prehiteva drugega Ju odvisno od smeri vrtenja. Vezje, ki izlušči informacijo o smeri vrtenja (blok 3), je še preprostejše kot listo za generirati je števnili impulzov. 1'rikazano je na sliki 5. lidina zahteva v zvezi s tem vezjem je, da sla uli in C:a izbrana tako, da je »2C2 konstanta tega vezja vočja od lUCl kojislanlo vezja za generiranje števnili impulzov. Na sliki 5. je tJoIog vezja pmlan tudi časovni diagram signalov iz katerega jo i-azvidno, da se šlevni im|3ulzi v primeru vtrl>;nja v ono smer generirajo, ko jo signal smeri SM v logično visokem slanju. Ko so smer vrtenja obrne, se zamenja ludi logični nivo, pri katerem so generirajo številni imiuilzi. Signal SM določa smer štetja števca. '/. invertiranjem enega od obeh vhoHlaven način tioločili katera smer vrtenja pomeni vrtenje v [lozitivnem oz. nogativnem smislu. Do sedaj opisano vezje skupaj /. dvosmernim števcem, zailostuje za poznavanje lege gh.vle na nek začetni položaj, ki pa v splošnem ob zagonu sistema ni ilefiniran. fri robotu je poliebno poznali leg(; posameznih segmentov g!e lege posameznih segmentov glede na njihove releienčno lego. Zato, da računalnik lahko pride do veljavnih |)oilalkov o legi v vsakem trenutku, jo potrebno med števec in podat-kovo vodilo računalnika postaviti So register (blok 5). Na ta način se prepreči s|5reminjanje podfitka o legi v času čilanja, hkrati pa so omogoči neprekinjeno tlolovanje števca. Za prenos podatka med števcem in registrom poskrbi osvežovaiiiik vsebino registra (blok 5). l^<-ta poskrbi,da so na zahtevo računalnika prenose v register vsebina števca, venilar šolo tedaj, ko jo vsebina števca stabilna. Osvežovalnik vsebine registra v primeru, ko se zahteva pronos iz števca v register v času, ko je prisoten Slovni impulz, prenos zakasni za toliko, da se vsebina števca laliko ustali. Uajalnik kola in dodatna logika predstavljata za računalnik periferno enoto. Kot taka mora imeli svoj naslov, preko katerega je računalniku dosegljiva. IJekodirna logika (blok 8) jo sestavni dol dodatne logike, ki služi dekodiranju tega naslova in na ta način omogoča odzivanje dodatne logiko na klice računalnika. 4. ZAKUUČliK Sam digitalni iiikromontalni dajalnik kota ni zadosten za podajanje loge. Potrebno mu jo dodali logiko, ki iz signalov dajalnika kola izlušči informacijo o legi in ji nadene številčno podobo. Na Institutu Jožef Stefan smo potrebno dodatno locjiko razvili in jo tudi us|K!Šno preizkusili. 1'ri lom smo uporabljali dajalnik kola proizvajalca Tlü.DIX model 702 Sli - 2540. Uporabljen dajalnik daje 2540 impulzov na ol)rat, kar ()0-metii, da lahko zasuk osi dajalnika kota določimo na Ü.035 kotno stopinje natančno, čo predpostavimo, da jo dajalnik idealen. Zaiadi odstojjanj od idealnih razmer, kar jo posledica omejitev |iri izdelavi diska in zaslona dajalnika, sa točnost izmerjenega kola zmanjša na 0.053 kotne stopinjo. 0.053 kotno stopinje jo torej pogrešek a katerim lahko merimo kote med O in 360 stopinjami. Za primerjavo si poglejmo So na kakšen pogrešek moramo računali v primeru, da za merjenje loge segmentov robota uporabljamo servopotonciomelro. Vzemimo, da je električni kot poionciomotra 2G0 kotnih stopinj in da imamo na voljo deset bitno A/i) pretvorbo. 1'redpostavimo šo, da fila polenciomeler in A/l) pretvorba idealno litu,-arna in da ni nobenih motenj, ki bi lahko vfilivale na A/l) pretvorbo. Skratka vzemimo pod lupo idoaliai primer. Pogrošok na kalerega moramo računali je 0.25-1 kotne stopinje, l'ri (em se moramo zavedati, da lahko s takim pogreškom merimo lo koto, ki niso večji od 200 kolnih stopinj. iMKislaven račun nam pokaže, ila jo faktor izboljšanja žo v primeru, čo primerjamo realno pričakovan pogr I 1 iLBj I_r~Lj" i , . , 1 i ' i i . i i cj|a tievnlh impulio» ■ iaaovnlm polskom »Iflnalov. --CU- R* SM CJ;. . a i I tXJ I I I I I 1 ' rr OBRAT : SMERI I ! ' ^ ! I I I 1 • lil I I J7l I III I I II II I 1,111 I I I I I I rT~L III ' II ' I r 11 IJLIL JUl J-'IIlJLJLJUIUIJII^ • I 1,1 11 , I Tfi , , lil ,, 81 . 6 Vtij» delektoria šimil gibanja oil dal^lnlka kola • iau»nlm polakom signalov. PRIMJER DINAMIČKOG R ASPO R E D J I V AN JA ZADATAKA U VIŠERAČUNARSKIM SISTEMIMA SA RADOM U STVARNOM VREMENU KUKRIKA MILAN UDK: 681.324 ELEKTROTEHNIČKI FAKULTET BANJALUKA SAŽETAK - Raspodijeljeni sistani tod tojih je ostvareno dinaniii^lco pridjeljivanje zadataka računalima mogli bi se u pogledu brzine odziva, iskoristivosti i cijene pokazati boljijra od kanv^ionalnih sistena. Predložena konfiguracija sastoji se od skupa radnih računala i mreže kanunikacijskih računala koja predstavljaju spregu radnih računala_ i linije za povezivanje sa drugm računalina. Sistem je koncipiran tako da se zahtjevi za izračuravanjiua koji prevazi-laze nogućnosti odredjenog računala, ili koja degradiraju njegove performanse, pr^se ostalim slobodnim računalima u sistemu. Zadaću pronalaženja optinalnog dinamičkog pridjeljivanja zadataka, u cilju izjednačavanja opterećenja u sistemu, tada preuzina globalni rasporedjivač. GlobaJm raspored j ivač se sastoji od ski?>a identičnih algoritama ko]e izvode komunikacijska računala. ABSTRACT - AN EXAMPLE OF DnJAMIC TASK SCHEDLOJHG IN A REAL-TIME MULTICOMPUTER SYSTfflS. A distributed systens which supports the dynamic assignnent of tasks between svjnetrical oonputers is offering a significant vantage in respo-iv-e speed, use and cost-efective perfoniBnce than the conventional systems. This paper presents a distributed systeni as a" collection of autoncmous host carputers networked together with a ccBinunioation conputers. System is designed so that the demands for computations whifch exceed the resource bounds of the computer, or which degrade its performance may be asigned to a another systems conputers. It is the task of the global scheduler to find an optinal dynamic assignment of tasks, so that a load balancing in system is achieved. Glciial scheduler consists of a set of replicated algorithms, each residing and running in the coranunication coiputer. 1. UVOD Glavne prednosti raspodijeljenih sistema u odnosu na druge računarske strukture, toji motiviraju daljnja istraživanja u oblasti njihovog projektiranja i izgradnje su modularnost, pouzdanost, propusnost sistema, brzina, efikasnost rada, mogućnosti proäirenja, raspoloživost, prihvatljive cijene i druge. To su i osnovni ciljevi koje bi trebalo postići izgradnjan takvog sistema, a njihovo ostvarenje bitno ovisi od kvaliteta sistemske programske podrške. S druge strane prednosti koje uvodi uporedno izvrgavanje zadataka u raspodijeljenim sistemima ograničene su složenošću realizacije sistemske programske podrške. Mnoga rješenja toja su se pokazala dobrim kod multipro-gramskih i višeprocesorskih sistena ne daju se jednostavno preslikati i na raspodijeljene sisterae. Pretposta\A® od kòjih se mora poći pri kreiranju sistemske programske podrške su množina ciljeva (zahtjeva) i oskudnost sredstava potrebnih da bi se ti zahtjevi jls-punili. Dijeljenje sredstava izmedju više procesa je posljedica situacije u tojoj bb oskudijeva u si m) odluka o rasporedjivanju zadataka po računalima, kao i odredjivanje redoslijeda njihovog izvršavanja u svakom od računala može bitno utjecati na performanse raspodijeljenog sistema. Stoga se postavlja zadatak da se za svato zadano stanje sisten-a i okoline nadje i realizira ta3cva raspodjela zadataka po pirocesorima pri tojoj će kriterijum efikasnosti funkcicniranja sistema poprimiti najpovoljniju vrijednost. .2. STRATEGIJE RASPOREEIJIVAMJA Kod sistena sa radom u stvamom vremenu pojedine aktivnosti (zadaci) odvijaju se pod uticajem otoline i njihov redoslijed se re nože u potpunosti unaprijed predskazati. Zadaci u sistemu moraju stopa biti povezani ria takav na-ćin da ispravno sumdjuju u obavljanju predvidjenog posla u svim dinajničkim uvjetima koje nameće okolina. Stoga je za optiiiiir.aci ju rada raspodijeljenili.sistem od najveće važnosti prdstup raspodjeli zadataka. Kod sistena sa statičkim pridjeljivanjem zadataka funkcije pojedinih računala su unaprijed tačho odredjene. Tine je i sistejiiska programska podrška jednostavnija, jer su jednostavnije i fome komunikacije, Medjutim, intuitivno možemo zaključiti da je takva struktura neefikasna, jer se može dogoditi da se u nekim računal;inQ fonnira i'ep spremnili zadataka dok su druge neopterećene. Kiad brze i nepredvidljive promjene sistemi sa strukturalnem negdredjenošću se pokazuju boljùra od statičkih sistena. Kod sistejia sa diriandčkini pridjeljivanjem zadataka pojedini zadaci nogu biti izvrženi od više, ili čak od svih računala u sititeir.u. Sistenislca piogramska podrška je bitno složenija nego u prethodnan slučaju, ali očekujemo, poboljšan je u odnosu na prethodni pristup jer će zadcjtak kraće čekati na izvršenje, pošto će biti pridijeljen najnvuije opterećenom računalu. Početak izvršavanja svakog od zadataka zavisi od prirode samog zadatka, pa nožemo razlikovati: a) - zadčitke koji su pernanentno aktivni; b) - zadstke koji se periodično izvode, uglavnom na poticaj sata stvarnog vrenena; c) - zadčitke koji se izvode na osnovu zahtjeva za pi^ekidom koje u slučajnim trenucima vremena postavlja vanjska okolina. , Treća skupina je ujedno i najnasovnija, a karakterizirana je time da se zahtjev mara ispuniti u stvarnom vretrenu, Rasporedjivanje zadataka bi zavisno o tipu zadatka tr"«balo vršiti u različitim vremenijia: - za zadatke navedene pod a) unaprijed - u fazi projektiranja sistema, tj. rasporedjivanje je statičko\ - za zadatke navedene pod b) i c) pogodnije bi bilo u fazi rada sistema, tj. rasporedjivanje je dinamičko. Zadatak bi trebalo da bude pridijeljen izabranom računalu tako da se ostvari rajbolji uticaj na ponašanje cjelokupnog sisteira (minimalno vrijeme kašnjenja, minimalno vrijeirB izvršavanja, naksinalna propusnost sistema itd.). Dinandčko rasporedjivanje bi trebalo uticati pozitivno na osobiiie sistena. Frena funkcijaim koje podriSavaju zadatke možemo podijeliti na: . - zadatke koji obavljaju izlazno/ulazne transakcije i koji se izvode samo na odredjenijn računalirra u sistemu, te zbog fieriferije uz koju su vezani nogu biti ra-sporedjeni isključivo statički; - zadatake koji manipuliraju nekim sredstvima i koji s se takodjer izvode samo na cdredjc-nim računalima u sis- temu, te zbog periferije uz koju su vezani mq;',u biti ra-sporedjeni isključivo statički; - zadatke koji tranipuliraju nekim aredstviiia i koji se takodjer izvode sano na odredjenim računaliiia u sistemu, ali može postojati više zadataka koji obavljaju istovjetne funkcije (na pr. procesiranje teksta, aritmetika u tekućem zarezu etc.); - zadatke koji vrše odredjena izračunavanja i koji se nogu izvoditi na bilo kojem cd računala u sisteniu. Posljednje dvije t^rupe zadataka mogu biti dinandčki rasporedjene. Rasporedjivane ulazno/izlaznih zadataka se provodi u fazi ki^eiranja sistena (1) i dalje se u ovom radu neće razmatrati. 3. PRIJFJ3LjOG RASPOREĐIVANJA ZADATAKA U SISTEMU U literaturi se može naći više pristupa rvispor'edji-vanju zadataka u višeprocesorskijii i yišeračunarskim si-stemina. Svi oni su ekvivalentni u tan smislu da se sa logičkog stanovišta svaki od njih može ujxitrebiti za »rješavanje pixjizvoljnog problema raspored j i vanja. Za dati problem, medjutim, neki od njih vode složenijim i neefi-kasnijim programiira nego ostali. Dakle, sa praktičnog stanovišta oni očigledno nisu ekvivalentni. Nijedan od autoru dostupnih algoritana za rasporedjivanje zadataka u sistendna sa više procesora nije eksplicitno uzeo u obzir dva veona bitna faktora; - medjuovisnosti zadataka koji se izvode na različitim mjestina u sistemu i koji kariuniciraju izmjenom po-r\ika da bi obavili postavljene zadaće; - ovisnosti topologije mreže (prsten, zvijezda, linija itd.) na ukupno koinunikacijsko opterećenje. Ako se pridržavano definicije raspodijeljenih sistema date u (2,3) ignoriranje nedjuovisnosti zadataké: koji se izvode na različitim mjestina u sistemu vodi do veona loših osobina takvih sistema, pa algoritnd za rasporedjivanje zadataka koji ne uzinaju obzir nedjuovisnosti zadataka nisu realistični, te njihova primjena neće poboljšati performnse sistena. Stoga algoritmi za rasporedjivanje zadataka koji ne uzi traju u obzir medjuovisnosti zadataka nisu realistični, te njiJiova primjena neće jKjbo-Ijšati perfomansc sistena. A].goritnd za lokalno i globalno rasporedjivanje koji SU definirani u ("4,5) za razliku od sličnih postojećih algoritana uzimaju u obzir nedjuzavisnosti zadataka koji se izvode na pojedinijii računalina. Pošto su odluke o raspored j ivan j u zadataka ovisne i o sklopovoskoj gradj 1 sistena, kao i o realizaciji programske podrško trebalo je prije nego se pristupi kreiranju algoritana za raspo-rt,djivanje prethodno definirati model raspodijeljenog sistena. Prvi zadatak pri tome je bio da se pojmu pro<;esa da frecizr.o značenje, t j. da se uvede nedvosmislena termi- ncl.ogija kojem se definira Sta je proces i kako se on idealizira u pojedinom računalu. Slijede(5i korvjk je da se odaberu osnovne opemcije za sinhronizacij u i prenos podataka izmedju medjuzavisnih procesa (6). Na osnovu usvojenih komunikacijskih i sinhronizaci-jßkih mshajiizana bilo je mogućno definii'ati algoritam za lokalno rasporedjivanje (5). Pošto je komunikacija zsnovana na izmjeni poruka znatno opterećenje komunikacijske mreže može do'/esti do veara loäih osobim sistema. Kao äto je u (7) pokazano ea poiastoin nivoa problena ietovremeno iBste i potTeba za obavještavanjem, te eventualnim učežćera ostalih dijelova sistema u njegovom rjeäavanju. Stog^ je za definiranje algoritaiiB za gJobalno rasporedjivanje od najvećeg značaja probleitBtika izbora topoloRÌje komunikacijske mreže koja bi ti^ebalo da obezbijedi pouzdan i hrz prenos infoimacija nedju računalima (7,8). U Cl) je predstavljen deteiTninistički dinamički algoritam za rasporedjivanje zadataka u konkretnoj prstenastoj strukturi. Prstenasta topologija sistena izabrana je pod pretpostavkom da bi visoka iskoristivost veza i strukturna jednostavnost prenosa poruka mogla zadovoljiti alredjenu skupinu korisnika koji ne postavljaju prevelike zatitjeve na brzinu komuniciranja. Kod ovog metoda globalni rasporedjivač će na osnovu proračuna minimiziranja dodatnog komunikacijskog opterećenja Ckoje uvodi novi zadatak) iz skupa alternativa izabrati ono rješenje koje će u okviru zacrtanom algoritmom iraksinalno zadovoljiti [xstavljene kriterije. Naime, medjuovisnost pojedinih zadataka je razlog da neki cd njih ostaju duže u stanju čekanja. Pregled nad tan medjuovisnošću se dobija skupljanjem infontacija o lokacijaim konunikacijskih partnera i opterećenosti račuRsla na koji/ra se oni nalaze. Nedostatak predloženog algoritma je u toirie Sto sa porastom složenosti pronatrane konfiguracije raste i dodatno neproduktivno vrijeme potrebno da se sakupe sve informacije. Stoga je u rastavku definiran brži ali nanje precizan al.goritam za koji se neće tražiti optitralno već samo zadovoljavajuće rješenja problena. 3.1. Detalji realizacije U ovdje predloženom algoritmu infoniiacije o nedju-ovicnof-ti zadataka, tj. o lokaciji i imenima partnera zadatka dobijaju se na osnovu procjene (pogadjanja), uzimajući u obzir odredjena paraiiiotre koji^ indii'ektno po-k J) IHEN , ; BEGIN . s: = i; C*" s je ozna)ačunalina na putu od "i" ka "j" kašnjenje :=0 ; IF (bnl = ABS *et-nih vrijednosti *) selćkcioni_faktor : =r(i^imer; - faktori izvrSnop, i komuniJcacijskcg opterećenja ovise o dužini repova unutar radnog i komunikacijskog računala. Ažuriranje stanja računala jezgro obavlja jednostavno i brzo svaki put kada je pozvano i dodatno neproduktivno vrijeme je veotna naleno; • - ciklične porSuiko koje sadrže infornaclje o stanju ostalih računala u bistemu.su minimale duìine (sajio jedna vrijednost po računalu). Stoga one ne predstavljaju ozbiljno opterečenje komunikacijskog sistema, te nogu biti obradjene sa najvišim prioritetan^ , ■ , NecJostaci su u tone ßto algorit^ ne uzima u obzir Icikacije na kojima ae nalaze medjuovisni zadaci sa kojima se komunicira, nego cJonosi odluku eairc na osnovu procjene opterećenja pojedinih računala, Oojena predloženog metoda data je na osnovu analitičkog postupka, a ovdje će se zbog oj;raničenog prostora sairo nauBčiti. Primjenom metoda nasovnog posluživanja opisuje se členiti proces posluživanja-preko funkcija ulazaka, posluživanja i čekanja. Pri ocjeni iTDdelaiP®®^!%e od slijedećih pretpostavki: - dolazno vrijeme je raspodijeljeno po Poissonovom ZćJcor.ui - zadaci 8e izvode po pravilu "prvi dolazi -prvi poslu?en"i' - vrijeme pošluilvanja ima ekspaiencijalnu razdiobu. Na osnovu ovih pretpostavki priirdjenjen je modificirani M/g/m model koji je općenito karakteriziran Poisso-novim procesom ulazaka sa srednjom vrijednošću i sa ra-spcdjelan vremena posluživanja oblika H(Es), koja ima s. srednju vrijednost vremena posluživanja E(s) i k-ti itome-nt E(s). Uz pretpostavke da su vremena iniciranja zadataka Poissonov proces i vrijeme usluživanja zadataka eksponencijalno rasporedjeno, pretpostavlja se da je intenzitet ulaznog toka zadataka takav da su sva računala optereće- "t j • pixjmatrtìn je sistem pod jakim opterećanjem. Teorijska osnova za ovakav pristup je data u radovima (10-17). Procjena minimalnog broja računala koja bi nogla zadovoljiti postavljene zahtjeve data je u radu (15). Srednja dužina repa i srednje vrijeme boravka u sistemu izračunati su na osnovu Pollaczek-Khlncihinove relacije date u radu (16). U (17) je dat progr'am i predstavljeni rezultati simulacije na računalu VAX 780/11 koji se podudaraju sa ovako ddibijenim vrijedncstina. 5. ZAKLJUČAK Problematika primjene raspodijeljenih sistema u vo-djenju složenih procesa je od velikog teorijskog i praktičnog žračaja. Za cptimizaciju rada ovakvih eisteira od najveće važnosti je pristup rasporedjivanju zadataka po računaliiia. U radu je izložena osnovna ideja i način razmišljanja vezan uz taj problem sa ciljem da se ukaže rva nedostatke postojećih rješenja i poboljšanja koja bi se iiDgia uvesti. Suštinska razlika u odnosu na druge, autoru poznate pristupe je u tórre 2to se predlaže da u kriznim situacijama, kacfa je opterećenje sistena rvijveće izvodjenje zadatka koji vrši odredjena izračunavanja preuzite ono računalo koje je sa sistemskog stanovišta u tan trenutku najpodobnije. Time se (po principu Bjxjjenih posuda) ukupno opterećenje r^isporedjuje jednoliko ha sve učesnike, a jednoliko opterećen sistem je i sistem naksimalne pouzdanosti i raspoloživosti. Sistem je deterministički - kreiran je za unaprijed definirane ciljeve, ali je i dinamički, jer se sve do inicijalizacije zadatka ostavija-ot-vorcnim pitanje koje od računala će ga izvesti. Slobalni rasporedjivač se sastoji od skupa identičnih algoriteuna koje izvode komunikacijska računala. Algoritam dcnosi odluku o izboru najpogodnijeg računala na osnovu preračunavanja izvršnog opterećenje i vremena čekanja u repu svakog računala. Infornaci je o niedjuovisno-sti zadataka, tj. o lokacijama haituni)mblnlra Le negotove količine In določa faktor varnosti (zanesljivosti) med vrednostma -I In il za vsako potencialno diagnozo. Za vsako diagnozo, ki preseže vrednost varnostnega faktorja 0,2, oblikuje vr'talnl nadzornik načrt re.^llve trenutnega problema In mlnlmlzlra verjetnost pi-oblem-skega vračanja. Vrtalni nadzornik deluje trenutno v programskem oluilju, ki ga sestavljata KS3Ü0 In Inter-llsp, ki Je osnovni programlrnl si stem; nadzornik se Izvaja na računalnikih podjetij DEC In Xerox pod ustreznimi operacijskimi sistemi. - Hazvojno okolje Je setavljeno iz orodij, vsebovanih v KS300 In ta pomagajo tehnikom znanja in Izvedencem, da doseže sl-stera Izvedeniško znanje. Pri tem se uporablja angleški Jezik In okrajšani zapis za prikazovanje in vnos pravil, za brskanje po bazi znanja, za strukturo, urejevanje, knjižnice primerov in za avtomatično preizkušanje, V tečaju za razvoj sistema so se tudi eksperti naučili uporabe orodij, tako da so lahko vplivali na kasnejše zbiranje znanja In na vzdrževanje baze znanja. Vsakokrat ko Izvedenec ali vzdrževalec bazo znanja spremeni pravilo, potrdi sistem KS30U avtomatično veljavnost sistema znanja, tako da opravi preizkus korektnosti za dani primer. Končno pa sistem znanja sodeluje z vrtalnim nadzornikom v naravnem Jeziku, ko avtomatično prevaja, zbira In formatlra ustrezne tekstovne fragmente, ki so povezani z elementi baze znanja. Povezovalna orodja omogočajo sistemu znanja, da proizvaja smiseln In pameten dialog z uporabo kratkih opisnih fraz, povezanih z vrtalnimi parametri, ki so bili Izvedeniško predvideni. Vrtalni nadzornik tudi grafično prikazuje več ključnih dejavnikov, vključno z verjetnimi zalakn I tveni-ml problemi, kameni timi sloji In z razineraiiil na koncu vrtine. S standardnimi orodji paketa KS 300 se dinamično prikazujejo alternativne reakcije, vmesni sklepi In hevrlstlčna pj'avlla, kl so trenutno v središču pozornosti. 6. Temelji tehnike znanja Tudi TZ ima svojo teorijo In prakso. Tu lahko zasledimo tri glavne smeri. Sistemi znanja rešujejo probleme, ki bi sicer zahtevali človekovo pamet; to reševanje.je luhko umetno ali naravno Inteligentno. Organizacija In oblikovanje danega sistema znanja morata upoštevati tip Jn zapletenost problema, pa tudi moč In obliko izkustvenega znanja, ki je za reševanje na voljo; čeprav Je žlvljenska dolja TZ kratka, se je vendarle razvila v smeri organiziranja sistemov znanja za različne pi-lmere. Znanje vsebuje sposobnost Inteligentnega delovanja, toda običajno ne razpolaga s pripomočki za Izkoriščanje in organizacijo tega potenciala; pri gradnji sistemov znanja mora tehnik znanja to znanje šele razviti In ga pretvoi-ltl v uporabno obliko. 0-pišlmo osnove takega razvoja. 6.1., Osnovne Idej 'e . Ko govorimo o znanju v povezavi s tehniko znanja, mislimo na take podatke, ki bi lahko izboljšali uSinkovltost problemskega reševalnlka. Trije glavni tipi znanja uztrezajo temu opisu: fakti, ki izražajo veljavne izjave; prepričanja, ki izražajo verjetne izjave in hevrlstlka (Izkustvo), ki izraža pravila dobre presoje položajev, za katere vobče ne obstajajo zanesljivi algoritmi. Izvedenci,se medseboj razlikujejo po, kakovosti In količini znanja, ki ga imajo; vedo več in to, kar vedo, zvišuje njihovo učinkovitost. Veliko človeških strokovnjakov opravlja naloge, ki zahtevajo veščinsko, samozavestno (trdllno) in informirano presojo. Te zahteve se pojavljajo zaradi zapletenosti, dvoumnosti ali nezanesljivosti razpoložljivih podatkov in problemsko reševalnih metod, V nasprotju z navadnimi aplikacijami obdelave podatkov deluje večina sistemov znanja v pogojih, ki ne zagotavljajo optimalnih ali pravilnih rešitev, V takih primerih mora problemski reševalnik uravnotežiti kakovost proizvedenega odgovora in napor, ki Je pri tem potreben. Izvedenec najde navadno najboljši kompromis tako, da spregleda način, kako najti sprejemljiv odgovor s primerno porabo razpoložljivih virov. S takšno pragmatično usmeritvijo zmogljivosti pridobijo pametni problemski reSevalnlki lastnost izboljšane učinkovitosti. Še posebej lahko izboljšave v hitrosti in izbiri producirajo sprejemljive rešitve bolj lahkotno In prispevajo k temu, da najde problemski reševalnik boljše rešitve v razpoložljivem času In reši še dodatne probleme. Na kakšen način lahko pameten .problemski reševalnik (PPR) Izboljša svojo učinkovitost? (1) PPR poseduje znanje, ki se često uporablja, izoglblje se napakam, zmore pa tudi ločevati pomembne razlike med diverznlml položaj-nimi tipi. (2) PPR hitro izloča raziskovalne smeri, ki so dokončno nekoristne. Tako oklestl dovolj zgodaj i;slepe drevorede+ In pridobi čas, ki bi bil potreben za odločanje o brezplodnih razredih možnosti iz prejšnjih raziskav. (3) PPR izloča redundanco z enkratnim Izračunom reči in uporablja kasneje rezultate, če je to potrebno. (4) PPR pospešuje svoje Izračunavanje, kar pomeni v primeru sistema znanja, da povečuje kakovost svojega prevajanja in uporablja hitrejše (zmogljivejše) računalnike. (5) PPR izrablja tista dlverzna telesa znanja, ki bi lahko kaj prispevala k rešitvi problema. Tako uporablja neodvisna Izvedeniška telesa pri redukciji večuinnosti in Izloča šumne vire, aH pa uporablja baze znanja kompleiiientarnlh področij In uporablja katerekoli tehnike in hevrlstlčne obdelave, ki so za rešitev danega problema najustreznejše. : (6) PPR analizira problem na več načinov, od visoke, abstraktne ravnine do nizke, specifične ravnine. ■ '' ■ Pri večini zapletenih problemov se mora problemski reševalnik gibati po abstraktnih ravninah; te ravnine lahko omogočajo vpogled na poljubno ravnino z obsežno^dodatno analizo. Primeri takega vpogleda vključujejo npr. razpozna-nje, da ima trenutni problem enako obliko kot Jo je imel preje reševanl, zaznavanje, da neka problemska zahteva izloča iz obravnave vse kandidate razen dveh, ali, predočbo, da vsebuje slika pravokotne, vodoravne In navpične linijske segmente, ki predlaga, da gre za objekt, ki ga Je naredil človek. Težavnost naloge problemskega reševanja narašča na štiri načine: (1) Problemski reševalnik ne razpolaga z natančnimi podatkovnimi viri ali znanjem,. ki bi lahko delovalo brez napak. Te pomanjkljivosti lahko povzročijo raziskavo velikega števila nepravilnih poti. "(2) Problemski reševalnik mora pospeševati svoje obnašanje, ko se podatki spreminjajo dinamično, utemeljevati mora svoje odločitve na pričakovanjih prihodnosti in popravljati mora svoje odločitve, ko trenutni podatki kažejo na nepravilnost prejšnjih predpostavk. (3) Naloga Je seveda težja, če Je treba upoštevati več možnosti. Vendar Je v vrsti uporab težko vnaprej ovrednotiti obseg Iskalnega prostora in poiskati alternat]vne formulacije Iskalnega prostora, ki bi kar najbolj poenostavile problem. (4) Problemski reševalnik, ki mora uporabljati zapletene In časovno zamudne, metode pri izločanju alternativ iz obravnave, deluje manj učinkovito od reševalnlka, ki ima enako učinkovita toda enostavnejša in cenejša merila (merjenja). 6.2. O rganizacija in o likovanje sistema znanja b - Za razliko od navadnih aplikacij obdelave podatkov pa sodobni sistemi znanja ne poznajo takih specifičnih modelov, kot so oblike tipičnih obnavljalnlh mojstrskih zbirk ali oblik vhod-pbdelava-izhod, ki so pogostne v komercialni obdelavi podatkov. Področje tehnike znanja tudi ne pozna skupnih shem za karakterizacijo svojega oblikovanja in.sistemov. Pri oblikovanju sistemov znanja se izkušeni tehniki znanja trdno držijo nekaterih splošnih načel, ki določajo visoke arhitekturno lastnosti sistemov znanja in ki omogočajo, dn bo opravljanje njihovih nalog učinkovito. Pri določanju primernega oblikovanja sistemov znanja postavljajo ta načela vprašanja o vrsti zapletenosti problemskega reševanja neke naloge in o vrsti razpoložljivega znanja za hevristlčno problemsko reševanje. Slika 3 prlkazujr vrsto najbolje obvladanlh načel oblikovanja. BO mall iBkalnl prostor velik fahte- rlrnl lakalni prostor PHOBUMSKE ZNAČILNOSTI podatki in enanje, eaneeljlvo in fikano nesaneeljlvl podatki aU neüanecil jlvo enanje fiaaovno apretnenlJlvl podatki nI ocenjevanja ca delno relltev neflkalrano >apor»đ> Je podprobUmev interakolja psdpro-blemov . ...----- I « «■ a BW « Mk uötnkavtto ugibanj« j«Ipotrebno •na vrata aklepanj* J« preltbka •'"T-"" en aam vir ananja Je preillbak I metada predatavitve Je premalo uStnkovt-ta , OPIS OBLIKOVANJA leSrpno Iskanje, monotono ' sklapanje,,ena vrstloa sklepanja sestavljanje evidence Is ve6 virov, verjetnostni modeli, mehki modeli, natanfinl modo» 11 pričakovanja, ki se proAlJo s stanji hlerarhlfino, generiranja in prelakulanje fiksno caporedje abatraktnlh korakov -<*• abstraktni Aakalnl preitor Urjenj« om«Jlt«Vt o najmanjlam obnalanj« mattano u« kanj« a d^lttn^ uglai«(\« steuktu« pe«gl«d tlvna lUk« I. Amt«ktur^ ni ßNd^tai »» gNtinjd tnan^ft« BVlka 3 raaüell aplikativne probl«iw« ai6t«i«&v ftnanjui ki karakterizirani « malimi in v«li> klml lakalniMi proat«»rii na dva ^la. prikaSe VHako diveh oanovnik^ kategorij a naltevanj«» ^«idatnih pri^evkav» ki tudi lahke karakt«rlBiraJe problem. Npr, pri pr«bl«nit\ malih pr««tarov raalikuje trt prekrivajoče ^oä« kate&arij«» ki tt^meljljo na vrati (podatkov» ki Jlh'aietem šnanja mora obdelati, S« iagleda» da «o ti pddatki aaneaUlvi in atalni in da dülujo «ietemako ananj« aanealjivot prodpiauj« alika ä najbolj tipiSno arhitekturo aiatoma ananja» ta« ko, ki epravlja iaSrpno iakanjo in aaaUduj« «no sklepanja hkrati, kot Je npr, ilo« bina«prvo naaaj&nj« v«rill«hjo, Predpiaani ai> etem ae lahke abnaSa monot»\at. no pott<«buJe na aa^etku (^r«kuliranih ugibanj» ki bi Jih bilo potrebno kaaneje umakniti, V drugi akrajnoati ßf^lkatttja auka I ksi^Utena pfaèìaia a va» Ukini fakfearirhini tHkalanljmMi^ àakalniHi pi^atsri, v kata^ih ana vi^llaa akla^anja aa daiuja kanalalantna ÌA ^uAl ana tala lAanja ni«^ »a aa ralavanja vaah aaAavnth pipaaianav aiata«a ananja in ja aafeataa aaitka »raöataviti« va ananja i»ra«aia uSinkavlUt da lahka daaa&ana ^airatoa aviagUtvaalAa ravfklAa, @bUkavalni ^riaaij^i »rad^iaujaja vaS adravll, iiatam ananja Mara taka raatakavati tn i«avUa> ti va« a^tavAttv anarà aklaiMnja» «aklai^ na »Mdabi va« gatavaali a dajanakt ralltvt. 81« ata« ananja naj vaa^uja vat naadvlantK l^adaiatanavt ad kataMh vaak »i^lpapava k adla« «anju na a^artuhiatilni aaivavi. NajvtIjI, aiata« ananja naj vadi »M ta» »railad aai^lanth tvl« rnim ^daiat««»aklh akalj, ki abataja najvaljt doprinos k razvi jajoči se reši tvi i ■ Sistem znanja-, bo sledil spreirienijivemu Stevilü ihkrat-nih, ,medsc>boJ tekmujočih alternativnih' reSitve-nih poti, kjer dejansko šlevi]o v vsaki točki odraža- trenutno negotovost o +naJboljšl+ poti. Sistemi znanja naj bi uporabljali različne napredne tehnike Ka izboljšanje avoje učinkovitosti.-, S(3l0snö potrebujejo te tehnike neko vrsto transfòrfiiaoi Je k , začetni predstavi tvi ■. znan Ja in k stroju-' sklepanja. Ta i transformacija ; lahko vključuje prilagoditev podatkovn4h- struktur tipom sklepan Ja, prevajanju znanja v novo strukturo (tako, kot je mreža ali drevo), ki omogoča hitro iskanje ali uporabo dinamičnih metod pri lovljenju.vmesnih rezultatov. Današnji principi oblikovanja sistemov znanja razpolagajo z dovolj visokimi napotki za oblikovalca.' Podobni so arhitekturnim principom za gradnjo stavb in komercialno konstrukcijo. Ti principi predlagajo široka izhodišča pri konstrukcijskih nalogah brez specifikacije podrobnosti. Sistemi znanja, ki se gradijo skladno s principi slike 3, bodo dobro prilagojeni svojim okoljem, toda se bodo lahko bistveno razlikovali v svoji nadrobni zgradbi. 6.3. -P r o J e k t i r a n o znanje Vidik projektiranja (načrtovanja, izdelave, razvoja), znanja je lahko hkrati jasen (razumljiv, očiten) in težaven (subtilen, domiseln, pi'enlkav,. premeten). To, kar se dozdeva jasno, je v, tem, .da tehnik znanja prevzema znanje od izvedencev in ga integriraiv arhitekturo sistema znanja. Torej obstajajo tehniki, ki gradijo sisteme.na temelju komponent znanja. To kar Je pri tem težavno, je način, kako sistem znanja uporablja znanje pri reševanju problemov, ta način pa Je neposredno odvisen od tega, kako tehnik znanja izbira, predstavlja in integrira znanje v .sistem. Znanje se seveda ne dobiva na lahek način, v gotovih paketih, že pripravljeno za uporabo. Znanje Je le beseda, ki Jo uporabljamo za vrsto fragmentov razumevanja, ki omogoča ljudem in strojem,, da opravljajo zahtevne naloge smotrno in dobro. Npr.' razumevanje tehnološkega prenosa omogoča tehničnemu direktorju, da sklepa na različne načine o razitčnih.namenih. Pri oblikovanju programa za tehnoioški prenos mora tak d 1 rektor .izoBtri t i in uporabiti znanje na način, ki Je drugačen od načina, s katerim bi ocenjeval nek drug program, oceniti mora potrebna sredstva, napovedati rezultate in analizirati podobnost s prejšnjimi uspešnimi ali neuspešnimi programi. Izgleda, Ua ima človek splošno razumevanje delovanja reči in današnji sistemi znanja lahko vključujejo znatne količine človekovegik znanja pri elektronskem reševanju problemov, kar bi sVčer zahtevalo človekovo pamet. Sistemi znanja uporabljajo splošno organizacijo, ki je skladna z visokimi oblikovalnijni pi'edpisi in potem uporabljajo v tem okviru znanje reševati ja- problemov. 7. Gradnja sistemov .znanja Pri, gradnji ; sisbewtóv .-znanjao. oprav.i Ja tehni;k znanja -štiri : funkCiljfl:, , ki i J ijiii. ,p/"l kazuje si Ika 4 ; te funkcije so.iizkopavanji^, ( Iskanje ) , ullva-nje (modeliranje, , oblikovanje:, . upodabljanje), zbiranje (sestavljanje) In..,či.^čenje (rafiniranje). Ti izrazi i so,., i zbrani i i z.; slovar Ja obde lave redkih kovin,; ioiippaazarJčjiJo-. postopke 'izbire znanja in nJegove,p|rolzvodnJ.e.. SI ika A prikazuje tudi tehnične termine za štiri primarne graditeljske aktivnosti in označuje ključne produkte posameznih faz. Naloge , obdelave znanja Tehnične aktivnosti ■Tehnični , produkti Izkopavanje Pridobivanje znanja Koncepti in pravila Ulivanje Obi ikovanje sistema znanja Predstavitev znanja in okvir Sestavljanje Programiranje znanja Baza znanja in stroj za sklepanje Čiščenje Čiščenje zna- ja Popravljeni koncepti in pravila Slika 4. Ključne naloge pri razvoju sistemov znanja Znanje Je podobno kot redka kovina skrito (speče, mirujoče) in nečisto pod površino zavesti, Ko Je enkrat izvlečeno, morajo biti njegovi deli tako transformirani, da dobijo komercialno vrednost. Izvlačenje obsega izvabljanje osnovnih konceptov iz problemske domene pri i.zveden-cih ali iz knjig, ko se ugotavljajo členi za opis problemskih stanj in za hevristiko reševanja problemov. Iz te začetne točke se izvla-čevanje znanja ali zbiralni postopek nadaljuje, dokler ni izvabljenega toliko znanja za reševanje problemov, da je dosežena t.i. izvedeniška zmogljivost. Hevristična pravila sestavljajo ključni proizvod te dejavnosti. Oblikovanje sistema znanja producira okvir ali arhitekturo sistema znanja, kot Je bilo nakazano. Oblikovalec si stemà znanja izbere primerno' shemo za predstavitev problemskoreSevàlnega znanja. Predstavitvene možnosti vključujejo formalno logiko, semantične mreže, hierarhične okvire, aktivne objekte, pravila in procedure, od katerih je vsalja podpirala vsaj enega od prejšiiij,il)i, naporov razvoja 3is;tema, žnEinja, Ko so , tehniki znanja Izbrali okvir la predstavitev znanja, se lahko začne progratniicajije. Ont potem transfoi'ml ra jo človekovo izkustvo v bazo zibanja, ki bo napajala stroj za sklepanje. S človekom razvijajoči današnj,i sistemi znapj.a privzemajo obstoječa orodja telii.iii.ike znanja, ki vključujejo vnaprej definirani stroj sklepan,Ja, tako da mora programiranje znanJis producirati, 82 le še bazo znanja. Postopek člšSenja znanja v bazi se nadaljuje dotlej, ko je sistemska zmogljivost dosegla primerno stopnjo. Pri transformaciji nenatančnega razumevanja Izvedeniškega obnaäanja v hevrlstlčna pravila se motita tako Izvedenec kot tehnik znanja. Pri tem napačno pojmujeta abstraktne koncepte, nepravilno Izražata palčna (prstna) pravila In zanemarjata vrsto podrobnosti, ki pogojujejo veljavnost pravil baze znanja. Splošno velja, da deluje sistem znanja nezadovoljivo na svojem začetku. Ta zmogljivost ne pomeni slabega dela tehnikov; izvedenci opravljajo svoje naloge dobro, ker uporabljajo primerno količino znanja in ne zato, ker morajo razmišljati, kako bi to znanje ver-ballzlrali. S pomočjo tehnike znanja se lahko izvajajo z znanjem Intenzivne dejavnosti, ki omogočajo kodificiranje in potrjevanje znanja. Pred pojavom TZ izvedencem nI bilo mogoče izraziti učinkovito njihovega izkustva (znanja) In tako niso mogli določati (ceniti, ocenjevati) znanja empirično. Sistemi znanja pa so oiiio-gočlli neposredno preizkušanje delovanja znanja in osvetlitev njegovih slabosti in poranaj-klivostl. Z odpravo teh pomanjkljivosti lahko Izvedenec hitro IzboljSa bazo znanja. Ta evolu-cionaren razvoj se najprej približa ravninam človekovih zmogljivosti in jih potem nasplošno preseže. Slika 5 prikazuje prenos izvedeniškega razumevanja v sistem znanja tehnika znanja, kar predstavlja ključni vidik zbiranja znanja. Ta prenos potrebuje dvosmerno komunikacijo. Najprej se tehnik znanja posvetuje z izvedencem o načinu, kako izvedenec rešuje posamezne probleme in razmišlja o zadevnih predmetih in relacijah (slika označuje te komponente razumevanja kot znanje sveta In znanje naloge). Izvedenec odkrije (odgrhe, razodene) nekaj tega znanja pri opisovanju problemskoreševalne naloge, in ga predaja tehniku znanja. Orodja TZ Sistem znanja opis = model Svet (okolje) Naloga Tehnik znanja ...... Izvedeniški opis naloge ziz: Izvedenec Slika 5. Zbiranje znanja: ob svetovanju izvedenca razvija tehnik znanja sistem znanja za reševanje nalogovnospecifi-čnlh problemov. Tehnik znanja posluša opis Izvedenca, da bi slišal o elementih reševanja problema. Tako kot sistemski analitik oblikuje algoritem za reSl-tev uporabniškega problema, poskuša tehnik znanja dojeti metodo za reševanje obstoječega problema. Zato izbere orodje TZ in poskuša prilagajati fragmente ekspertize strukturi orodja. Tako mora najprej oblikovati opis načina razmišljanja izvedenca o reševanju problema v dani domeni. Ta opis ponazarja (posnema) ekspertizo izvedenca. Ko je to končno vstavljeno v sistem znanja, začne ta model generirati problemskore-ševalno obnašanje, ki ga izvedenec lahko kritizira in Izboljšuje. Ta postopek često izboljšuje razumevanje izvedenca o njegovih lastnih izvedeniških zmogljivostih. IDENTIFIKACIJA KONCEPTUA-LIZACIJA Odkriva- Iskanje nje pro- --------- konceptov blemskih Zahteve. za pred- značil- stavitev nosti znanja - Koncepti FORMALIZACIJA Oblikovanje strukture za organizacijo znanja Struktura prečlščevanje preoblikovanje preformuli ranje Potrjevanje pravil, ki organizirajo znanje PREIZKUŠANJE Pravila Formuliranje pravil, ki vsebujejo znanje IMPLEMENTACIJA Slika 6. Stanja razvoja sistema znanja. Slika 6 upodablja ponavljajoči, evolucionarnl postopek razvoja sistema znanja z osvetljevanjem načinov preizkušanja povratnih povezav sistema znanja k prejšnjim stanjem njegove konstrukcije. Kot kaže slika, lahko preizkušanje izkazuje pomanjkljivosti prejšnjih stanj. In ko napreduje razvoj, je moč opaziti spremembe zahtev, konceptov, organizacijskih struktur in pravil. (Se nadaljuje v naslednji številki časopisa Informatica) (12) L.D. Erman, P.E. London, S.F. Fickas: The Design and an Example Use of Heai-say III i Proc. IJCAI 7 (1981), pp. 409 - 415. .. (13) H.P. Nil. N. Aiello: AGE: A Knowledge-Base Program for Building Knowledge-Based Programs. Proc. IJCAI 6 (1979), pp. 645 - 655 • A. P. Železnikar Slovstvo (0) F. Hayes-Roth: The Knowledge-Based Expert System: A Tutorial. Computer 17 (1984), No. 9, pp. 11 - 28. (1) F. Hayes-Roth, D.A.Waterman, D.B.Lenat; Building Expert Systems. Addlson-Wesley, 1983 (2) A.Barr, E.A.Feigenbaum: The Handbook of Artificial Intelligence. William Kaufman, Menlo Park, Ca, Vol. 1 (1981), Vol. 2 (1982). (3) H.K. Lindsay et al.: Applications of Artificial Intelligence for Organic Chemistry: ■ The Dendral Project. McGraw-Hill, New York, 1980. (4) W.A, Martin, R.J. Fateman: The Macsyma System. Proc. Second Symp. Symbolic and Algebraic Manipulation, 1971, pp. 59 - 75. (5) E.H Shortliffe: Computer-Based Medical Consultation; Mycin. American Elsvier, New York, 1976. (6) L.D. Erman et al.: Hearsay II Speech-Understanding System: Integrating Knowledge to , Resolve Uncertainty. Computing Surveys, Vol. 12 (1980), No. 2, pp. 231- 253. (7) J. McDermott: Rl: An Expert in the Computer Systems Domain. Proc. First Annual Nat. Conf. Artificial Intelligence, 1981, pp. 269,- 271. (8) H.E. Pople, J.D. Myers, R.A. Miller: Dialog Internist: A Model of Diagnostic Logic for Internal Medicine. Proc. IJCAI 4 (1975), pp. 849 855. (9) R. Greiner, D. Lenat: A Representation Language Language. Proc. First Annual Nat. Conf. Artificial Intelligence, Vol. 1, 1980, pp. 165 - 169. (10) H.P. Nil et al.: Signal-to-Symbol Transformation: HASP_3IAP Case Study. Al Magazine, Vol; 3 (1982), No. 2. (11) R. Brooks, R. Greiner, T. Binford: The Acronym Model-Based Vision System. Proc. IJCAI 79 (1979), pp. 105 - 113. Bibliografija s področja novih računalniških gerieraćij I Pod tem naslovom bomo objavljali bibliografske vire, ki obravnavajo'problematiko, povezano tako ali drugače z novimi računalniškimi generacijami. Pri tem bomo vpeljali osnovne klaslfi-katorje za posamezna področja, in sicei-: (Ann) Vodilni dokumenti. Navajali bomo dokumente vlad, združenj, podjetij, razne usraeritvene in splošne prispevke. (Bnn) Pregledni in ozadnji dokumenti (družbeno oklje, jutrišnje perspektive). (Cnn) Povezava človek_računalnik. (Dnn) Paralelno procesiranje, nove arhitekture in VLSI. (Enn) Logično in funkcionalno progranili'an Je. (Fnn) Izvedeniški sistemi in umetna pamet. (Gnn) Mreže. (Hnn) Referenčni (bibliografski) vlrJ. Pri tem bo nn vsakokratna, zaporedna številka bibliografske navedbe. Navedbi bomo dodali kratek povzetek, na koncu pa bomo napisali še ključne besede, ki jih je moč uporabiti pri Iskanju dokumentov v različnih podatkovnih bazah po svetu. Te ključne besede bodo zapisane v angleškem Jeziku. Pa začnimol A. Vodilni dokumenti (Al) Jones K. Sparck: Intelligent Knowledge Based Systems; Papers for the Alvey Committee. University of Cambridge Coinputer Laboratory (June 1982). Ti članki so bill pripravljeni kot podlaga za Alveyev odbor na zahtevo enega od članov odbora. Ti članki obravnavajo pametne sisteme znanja v petih poglavjih: potreba, definicija, stanje, program in i-ezultat. Predlaga se desetletno raziskovanje in razvoj pametnih sistemov znanja, s skupnimi izdatki 67 milijonov funtov, kot sestavni del t.l. Alveyevega programa. Predlog vsebuje dve fazi: uvodno, ki naj pripravi osnovno infrastrukturo za raziskave in razvoj in glavno fazo, ki naj srednjeročno in dolgoročno oblikuje in oceni akademske programe in primerne demonstacljske projekte. Ključne besede; Alvey programme, ted Kingdom. ^ IKBS, Unl- (A2) Research Reports in Japan: a Collection of Recent Research Reports Related to thè R and D of the Fifth Generation Computer Systems. Japan Information Processing Development Center (Fall 1981). To je zbirka 38 poročil z naslednjo problematiko: izpelava formalne specifikacije problema Iz njegovega opisa v naravnem Jeziku; izpeljava programa iz njegove formalne specifikacije; vidiki logičnega programiranja (12 člankov); strojna arhitektura O' člankov); razpoznavanje govora (2 članka); jeziki za predstavitev znanja; .strojno prevajanje; mrežno Usmerjeni operacijski sistemi. Ključne besede: Collection of Papers, FCGS Project, Japan. (A3) T. Moto-Oka (Editor): Fifth Generation Computer Systems: Prceedings of the International Conference on Fifth Generation Computer Systems. Tokyo, Japan, October 19-22, 1981. North Holland Publishing Co. (1982). To Je zbornik mednarodne konference, kl Je bila v Toklju od 19. do 22. oktobra 1981, organiziral pa jo je Japan Information Processing Development Center (JIPDEC). Na tej konferenci je bil objavljen program japonske pete računalniške generacije. Zbornik vsebuje 18 člankov, ki so razvrščeni pod naslovi Uvodni govor, Pregledno poročilo. Načrt raziskav informacijske obdelave znanja. Načrt raziskav arhitekture. Povabljeni referati - Informacijska obdelava znanja in Povabljeni referati - arhitektura. Ključne besede: Project, Japan. Collection of Papers, FGCS (A4) G.G. Scarott (Editor): The Fifth Generation Computer Project: State of the Art Report. Pergamon Infotech Ltd. (1983). To poročilo Je razdeljeno na tri dele: povabljeni referati, analiza in bibliografija. Povabljeni referati preučujejo različne vidike projekta pete genei'aclje računalnikov. Sekcija za analizo obravnava bistvene prednosti projekta pete generacije in podaja uravnoteženo analizo stanja napredovanja pete generacije. Analiza se začenja z upoštevanjem pomena informacije v človekovih dejavnostih in prikazuje stanje informacijske tehnike. Nave- dena bibliografija je skrbno izbran pregled objavljenih del s področja pete generacije. Ključne besede: Bibliogreiphy, Collection of Papers, FGCS Project, Japan. Social Context (A5) Intelligent Knowledge Based Systems: A Programme for Action in the UK. Alvey Directorate (August 1983). Poročilo sestavljajo trije deli in je intenzivna študija posebne komisije Alveyevega programa vlade ZK. Študija je akademska in industrijska ekspertiza in je bila na določen način upoštevana v strategiji Alveyevega programa za področje sistemov, ki temeljijo na znanju. Prvi del je glavno poročilo in oblikuje strategijo predloženega programa. Drugi del vsebuje vrsto poročil za posamezna podpodročja. Preostali del poročila vsebuje dodatke k prvemu deli poročila. Ključne besede: Alvey Programme, IKBS, United Kingdom. (A6) Outline of Research and Development Plans for Fifth Generation Computer Systems. ICOT - Institute for New Generation Computer Technology, Tokyo (May 1982). To poročilo je povzetek japonskih raziskovalnih in razvojnih načrtov za projekt pete računalniške generacije, ki obravnava socialno in tehhično ozadje projekta, raziskovalna področja In cilje, splošne raziskovalne in razvojne načrte ' in pripadajočo filozofijo za mednarodno sodelovanje. Ključne besede: FGCS Project, International Relations, Japan, Social Context. (A7) Outline of Research and Development Plans for Fifth Generation Computer Systems (Second Edition). ICOT - Institute for New Generation Computer Technology, Tokyo (April 1983, with Supplement dated September 1983). Ta prispevek je druga izdaja (A6) z bistveno spremenjeno vsebino. Prikazuje se sklepanje o napredovanju projekta pete računalniške generacije, identificirajo se funkcije takega sistema, kot sta npr. reševanje problemov in sklepanje, baza znanja, pametna povezava in pametno programiranje in seveda inovativna materialna (aparaturna) arhitektura in programska oprema za doseganje opisanih funkcij. Opisani so načrti za splošno in začetno fazo, 2a doseganje projektnih ciljev. Dodatek nosi naslov Report of RGCS Projects Research Activities, 1982 in Je zbirnik projektnih dejavnosti za leto 1982. KlJuSné besede: Architecture, FGCS Project, Inference, Intelligent Interface, Japan, Knowledge Base, Problem Solving. (A8) Proceedings of Research Area Rawiev Meeting in Intelligent Knowledge-Based System. Science and Engineering Research Council (1982). Vabilo k sodelovanju Zbornik Je pregled dvodnevnega londonskega srečanja v septembru 1982, na katerem se je razpraviJajlo o predlogu posebnega programa sistemov, ki temeljijo na znanju. Zbornik prinaša poročila razprav o predstavitvi znanja, sklepanju, naravnem jeziku, vidni in objektni manipulaciji, povezavi človek-stroj, Izvedeniških sistemih, strojih in programiranju, skupni bazi, raziskovalnih programih in projektih, infrastrukturnih zahtevah, šolanju itd. Ključne besede: Education and Training Implications, Expert Systems, IKBS, Inference, Knowledge Representation, Man-Machine Interface, Natural Language, UK, Vision. Posvetovan|e in seminarli Informatica '85 Nova Gorica. 24.-27. september 1985 Posvetovanje 18. jugoslovansko mednarodno posvetovanje za računalniSIa računalniških sistemov 3. Upravljanje procesov 4. Sistemski razvojni pripomočki 5. Mali poslovni sistemi 6. Uporaba pri izobraževanju • 7. Osebni računalniki 8. CAD/CAM mikrosistemi 9. Umetna Inteligenca in roboti 10. Računalniške mreže 11. Peta računalniška generacija 4. Razvrstitev referata (otJkrožite) 1. referat (pomembnejše delo) 2. kratek referat 3. poročilo 1. Title o( the Paper: ..................................................... 2. Extended summary (appioximately 1000 words) should be enclosed. 3. Program Category of the Paper (circle appropriate chok») 1. Survey of Technok>gy and/or Usage 2. System Architecture 3. Process Control 4. Systems Development Tools 6. Small Business Systems 6. Usage in Education 7. Personal Computers B. CAD/CAM Systems 9. Artiticial Intelligence and Robots 10. Computer Netvvorks 11. Fifth Computer Generation 4 Classification of the Paper (circle appropriate choice) 1. Paper 2. Short paper 3. Technical report 6. Avtorji: ........................................... Dek>vna organizacija: ...................... Ulica: .............................................. Poštna številka: ...................Kraj: .. Država: ......................................... Datum:................................Podpis: Prijavnica, skupaj z dvema kopijama razširjenega povzetka, mora prispeli najkasneje do 1. aprila 1985 na naslov: Informatica 85, 6t 116 Ljubljana, p p 2 5, Aumot(s): .............................................. Organization: ........................................ Street: ................................................... Postal Code:.......................Oily: ......... Countiy: ................................................. Dale:..................................Signature: Tins appiicalion lorin logelfier with two copies ut extended summary must reach Ihe following address before /\pril 1, 1985: Inlormatica '85, 61116 Ljubljana, p p. 2, Yugoslavia 86 UPORABNI PROGRAMI Warshallov algoritem. Informatica UP 20 : Prevajalniki - vaje % Marshall's Algorithm % oktober 1984 % priredil Anton P. Železnikar % sistem CP_M, Delta Partner % prevajalnik Janus_Ada, verzija 1.5.0 96 1. Področje uporabe Matematične relacije lahko predstavimo z Boolo-vlmi matrikami. Elementi teh matrik imajo vrednost O ali 1 ali pa tudi false ali true. Vobče bomo imeli kvadratne Boolove matrike razsežnosti n X n. Seštevanje dveh Boolovih matrik temelji na operaciji OR (ali) med Istoležnimi e-lementl obeh matrik. Element d(l)(j) vsote matrik d = b + C je določen z adovskim priredil-nlm stavkom d(i)(j) := b(i)(j) OR c(l)(j); ali pri številski predstavitvi (O, 1) Boolovih matrik z adovskim programskim segmentom IF b(i)(j) = 1 THEN d(i)(j) := 1; ELSE d(l)(J) := c(i)(J); END IF; Člen d(i)(j) ločen z produkta D=BCje do- d(l)(j) := b(l)(l) AND o(l)(j) OR b(l)(2) AND c(2)(j) OR ..........OR b(i)(n) AND c(n)(j); Preizkus Ularehallovesa algoritma Prevajalniki - vaje UITH util« PACKAGE BODY tes^iplus IS ns CONSTANT 9= 50? TYPE stolpec IS ARRAY <1 .. n ) OF Boolean» TYPE Boole-polje IS ARRAY <1 n) OF stolpec» — Ta procedura Je predmet nade pozornosti« PROCEDURE b-Plus < b» IN Boole-Polje» a» OUT Boole-Polje) IS — Ta procedura predstavlja Uarshallov al- goritem i. j F k« integer » — 'n' je globalna spremenljivka BEGIN FOR i IN 1 .. n LOOP FOR J IN 1 n LOOP a f b(i)< j)» END LOOP» END LOOP» — < i > i s» 1» — <2) WHILE i <= n LOOP FOR j IN 1 .. n LOOP IF a( j X i > = true THEN FOR k IN 1 .. n LOOP a< j )< k ) S" a< j K k > OR a( i )( k )» END LOOP» END IF» END LOOP» — <3) i 8= i + 1» — <4) END LOOP» — <5) END b_plus» PROCEDURE matr-izp < m.K IN integer« e» IN Boole-PolJe > IS i. j« integer» BEGIN neiM-line» put< "Boolova matrika ' )» put» new-line» FOR i IN 1 .. m LOOP FOR j IN 1 M LOOP IF e< i >< 0 ) = true THEN put( ' 1' )» ELSE put< " O' )» END IF» END LOOP» new-line» END LOOP» new-line» END matr-izp» ir J» integer» Cr d» Boole-PolJe» BEGIN FOR i IN 1 .. n LOOP FOR o IN 1 .. n LOOP cCiXj) 4= false» d »= false» END LOOP» END LOOP» — Inicializacija vzorćne matrike s ctlXl) 8= true» c(l)<2) «= true» c<2)<4) «= true» c< 3 )( 5 ) «= true» c<4)(2> s= true» b-PlUS» matr-izp1. Odtod dobimo z indukcijo po n, da Boolova matrika b" predstavlja relacijo r" . Tako dobimo tale izrek: Lista 2. Ta lista nastane z izvršitvijo programa testplus, ■ opisanega v listi I. Prva Boolova matrika predstavlja dano relacijo, druga matrika pa njeno tranzitivno zaprtje. Obe matriki se izpišeta šele potem, ko Je bila izračunana matrika zaprtja (glej listo 1 na njenem koncu). 13A>testPlus Puolova matrika li 110 0 0 0 0 0 1 0 0 0 0 0 1 0 10 0 0 0 0 0 0 0 Boolova matrika 2' 110 10 0 10 10 0 0 0 0 1 O 1 0 10 0 0 0 0 0 Bodi B Boolova matrika razsežnosti n X n, pt'edstavl JaJoč relacijo R nad dano abecedo. Tedaj Boolova matrika B^ = B + BB + BBB + ... + B" predstavlja tranzitivno zapr tje R"*" relacije R. Uporaba relacij in njihovih predstavitev z Boploviml matrikami nam omogoča programsko določevanje novih relacijskih (parovnih) množic. Z Warshalovim algoritmom pa določamo množice tipa B"*" . Z gramatikami prograrairriih jezikov Je povezanih več relacij, ki se uporabljajo za preizkušanje določenih gramatičnih lastnosti in zlasti pri navzgornji sintakani analizi. Takšne relacije so npr. PRVI, PHVI ^ , ZADNJI, ZADNJI"*" , ZNOTRAJ, ZNOTRAJ ZNAK, ZNAK . prednostne relacije , ^ in > , PRVITERM, ZADNJITERM, relacije operatorske prednosti Ss. , in ^ itn. (glej slovstvo ((1))). 2. Opis programa a(J)(k) := a{J)(k) OR a(i)(k); (4) PrišteJ 1 k i. (5) Če Je J manjše ali enako n, nadaljuj s korakom (3), sicer pa se ustavi. (Glej vajo 3 podpoglavja 3.7.2 na strani 22 slovstva (d))). V listi 1 Imamo paket testplus za preizkus procedure b_plus, ki predstavlja Warshallov algoritem. S proceduro matr_izp izpisujemo Boolove matrike.'S preizkusnim programom najprej inlcl-aliziramo matriki c in d, potem pa v matriko c vstavimo za.ustrezne njene elemente vrednosti true. Proceduro b_plus uporabimo potem na matrikah c in d, ki ju nato izpišemo. 3. Izvajanje programa Rezultati izvajanja programa testplus so prikazani v listi 2, kjer imamo obe Boolovi matriki. Prva matrika ponazarja neko relacijo, druga matrika pa tranzitivno zaprtje te relacije. Slovstvo Warshall je razvil učinkovit algoritem za računanje tranzitivnega zaprtja B"*" Boolove matrike B. Koraki tega algoritma so tile: U) Postavi A := B; (A Je BooJova matrika). (2) Postavi 1 :.= I ; . (3) Za vse J, če Je a(J)(l) = true (all pri številski pi-edstavi tvl = J), potem za k = 1, 2, 3.....n postavi (d)) A.P.ieleznikar: Prevajalniki. Univerza Edvarda Kardelja v LJubljani, Fakulteta za elektrotehniko. Ljubljana 1980 (ponatis). 88 Položaj točke glede na mnogokotnik % Informatica UP 21 % Position of a Point Concerning to the % Given Polygon % november 1984 % priredil Anton P. Železnlkar % sistem CP_M, Delta Partner % prevajalnik Janus Ada, verzija 1.5.0 % % % % % % 1. Področje uporabe Položaj točke glede na dani mnogokotnik (poligon) je mogoče ugotavljati v povezavi z različnimi geodetskimi, geometričnimi in matematičnimi nalogami. Pri tem gre za odgovor na vprašanje, ali je dana točka v danem poligonu ali ni. IV|H.(3:[N iiew_l ines put< 'Votavi àtevilo Pollsunskih osljiées aet; 3et» new.-line> FOR i IN 1 ,. k LOOP put< 'Vstavi koordinati ' )> Put aet(aa)i new,I ine» IF aa = 1 THEN polaaon« n , X ru )» END IF» put( 'Ali želiž vütaviti totke ; put< "/fie=0 ) ? " ); 3et(sa)f new-line; IF aa! = 1 THEN ■ put( ' OslJièda mnosokot.nika sos'); new„iiii6!J line< 43, ' ~ ' )! PUt( ' x< i ) pijt( "y< i.) ' new_.line; line(43r'-I-OR i INI . . n LOOP floatiu-.PuK x( i )); PuL( ' ' )! fioatto.PUt( »< i >)» msi»_.line> ENti LOOF'i 1 ine( ' = ' )s new-line; p\jt< ■ Poloiaj t.o^k alede na put( mno.yükotnik ; >; neu(_liniT)! line< 53,'=■■' ); put( " u< i ) v( i )' >; pu t< " rezultat " new_line; linfs( 53,'--'); FOft i :I;N 1 - . k L.OOP f 1 oat io ,put< u< i ) )f put( " " ); floatio,Put( v< i )); put< " " ); IF PointPoK n, X ,y ,u( i ), vt i ) ) THEN put( 'znotraj * >> ELSE PUt( ' zunaj" >i ENB IF; niiw-line; . liNli 1.00I-; line( 53,.); nt>w-lint.:'> fvüiO start; EHD IF; <> null; FND point; . , ToSke s koordinatami x(i) in y(1) (1 = 1, ... , n) naj bodo ogljišča prostega, zaključenega mnogokotnlka, pri čemer so ogljišča oštevilčena v krožnem zaporedju. Naj bosta xO, yO koordinati točke, ki ne iežl na kateri od stranic mnogokotnlka, V tem primeru opredeljuje funkcija pointpol na listi 1 lego točke (xO, yO) glede na notranjost (oziroma zunanjost) mnogokotnlka. Polji X in y fiinkcije pointpol morata imeti območje 1 .. n 1. Glavna procedura programskega paketa liste 1 Je boolovska funkcija pointpol, katere vrednost Je true, če leži točka v notranjosti mnogokotnlka. S proceduro polygon se preberejo koordinate pollgonskih (mnogokotnišklh) ogljlšč, s proceduro e_polnt pa koordinate vseh tistih točk, katerih lege glede na mnogokotnik želimo ugotavljati. V glavnem preizkusnem programu imamo še segment, ki inlciallzira enotin trikotnik kot dani mnogokotnik in dve poskusni točki, katerih lego želimo ugotavljati (glej poglavje o izvajanju programa). Temu segmentu sledi še dialognl segment s klici ustreznih procedur. Usta 2 (se nadaljuje na naslednji strani). Ta lista prikazuje izvajanje programa Iz liste 1 za dva primera. V prvem primeru se uporabi v programu definirani trikotnik kot poligon in v programu definirani točki. 13A>pòii»t Ali preizkušali lfc?3o toCJ< alede na : mnoaiikotni k i d;i='l/nfc.--0 ) ? 1. Ali iellè vstaviti koordinate 03ljii?ič rtiiioaokotnika < da-l/rie--O ) ? O Ali ieliž vstaviti točke < da= l/ne'---0 ) ? O, Ali ielià preizkus < da--l/ne-O ) ? 1 Cii-jlji^ča mnoj.)okott^ika so^ x( i ) u< i ) O. oooooooooooooo£::to 1.OOOOOOOOOOOOOOFMO o. oooooüoooooooot;: io . o. OOOOOOOOOOOOOOli. 4 o o,ooooooüoüoooooe 10 I,OOOOOOOOOOOOÓOE t o polužaJ točk 3lfc;de na mniiaokotriik-u(,i ) v< i ) rezultat S.OOOOOOOOOOOOOOE-l 4.9999V9'/V'/V00ü0E-l znotraj O.OOOOOOOOOOOOOOE-iO ■■ 1 .OOOOÜOOÜOOOOOIE+O zunaj Ali ž&liž pr ei z kui!>a t i leyo tot^.k aletje na ftinowokotnik ( da-l/ne-^O ) V i Ali it-liš vstaviti koordinate oaljižč mno.aokotriika ( ila--l/n<>:=0 > ? 1 Viätavi žtt;.'vilo ol i>ni;ik i li 4 '.''.itavi koordinati oul.jliSiia 1. xl - O ■. l ^^^^ O Vstavi koordinati ouljièCd ■=• 2 u2 ==0 Vstavi koordinat i . oul j ižča 3= x3 2 = 1 Vstavi koordinati ouljiiSča 4; x4 ~ 1 ;j4 = 1 Ali ieliž vstaviti točke u5 = 1.9 v'5 M 0.999999999999999 Vstavi koordinati 6! u6 = 2 vA = 1 90 Ali želiž preizkus lese f v- ' ' rm * -h.A f1~ ^.rrrr") tlMivu< s)slan' e 9 «uUlana 0 jugòslavlja S tem pris|)8vkom bi ruüi obvustill bruita tuviju Inloritmiicu o inožnusli, du se udeležijo suniiiiurja "Tuhnoluyijii unioino inlejiymi-cc". Seminur oryuniziru Odsuk 2u rj£üniiliilSlvu in iiilorniutiku Insll luta Jožut Stefan v sodeluvunju s Slovonskini druälvoni Inluirnaliiia. Pütekul bo od 8. do Ì2. aprila tOSö v prostorih Instituta Jotuf Stefan. Seminar bo obravnaval sodobne teme umetne inteligence B poudarkom na tekoćih projektih umeliw intuliijuiicu v svetu ter na možnostifi uporabe orodij umelne intelicjence za i/delavo konkretnih aplikacij v naäem razvojnem, proizvodnem, poslovnem in upravnem okolju. Seminar bo podal tudi vpoyied v projekt 5. generacija računalnikov in na programski jezik prolog, ki je izbran tu jezik ta generacije. Umetna inteligenca in njeni produkti so 2e dalj ćasa predmet 21 vega zanimanja raziskovalcev In industrije na Japonskem, v ZDA in Zahodni Evropi, pa tudi pri nas. K razvoju lah znanj v svatu ia vrsto let enakopravno prispevata Skupina za umetno inteligenco na Odseku za računalništvu in Informatiko Instituta Jo2ef Stefan in rta Fakulteti za elektrotehniko Univerzo E. Kardelja v Ljubljani. Program seminarja Celotni program seminarja bo razdeljen v osnovni program in dodatni program. Osnovni program bodo sestavljale strokovne predstavitve sodobnih tem umelne inteligence. Dodatni program pa bo voden v obliki Sola programiranja v programskem jeziku prolog, ki je izbran kot proyramski jezik 5. generacija računalnikov. Pri praktičnem delu bo poudarek na aplikacijah v ekspertnih sistemih. ' Osnovni program bo potekal pretaino dopoldne, dodatni pa popoldne v prostorih Instituta JoJef Stefan. Znanstveno - tahnoloSki seminar TEHNOLÖQIJA UIVIEtNE INTELIGENCE 8.-12. april 1985 Institut Joiat Stafan, Ljubljana Osnovni program, sodobne teme umetne Inteligenca - H/letode in tehnike umetne inteligenca - Ekspertni sistemi ~ Tekoči projekti v svetu - Nekateri) aplikacije umetne inteligenca - Projekt 5. generacije računalnikov - Oprema, potrebna za razvoj ekspertnih sistemov - Programirni pripomočki za umetno inteligenco Iprogramskl ježikl, okolja in orodja) - Programski jezik prolog - Vloga umetne inteligence in jezikov 4. generacije v Informacijskih sistemih - Metode umetna Inteligence v odločanju - Predstavitev projektov umetna inteligence pri na» - Demonstracija delujočih programskih paketov. PRIJAVNICA ZA SEMINAR "TEHNOLOGIJA UMETNI: INTELIGENCE" 8. - 12. april 1985, Institut Joiaf Stefan, Jamova 39, Ljubljana Ima in priimek; Naslov delovne organizacija; Telefonska Številka; Prijavljam se za (označite ustrezno okenca); I I celotni program j | osnovni program Sem sodelavec akademske institucije (označita ustrezno okenca); M da I I ne Sem sodalavac sponzprske institucija (označita ustrezno okence); I I da I I na Kotizacijo v znesku (označite ustrezno okence); I I 35,000 din ( I 30.000 din || 25,000 din | | 20.000 din bom poravnal na 2R Instituta Joial Stefan 60101-603-50272 najkasneje do 1. aprila 1085. Dodatna Informacija; Udeleženci seminarja bodo predvidoma lahko kosili v menzi Instituta Jožef Stefan (doplačilo ob registraciji). Prosimo vas za informacijo, če ste kandidat za kosila na IJS (označite ustrezno okence); I j da I I ne Podpis; Dodatni program: Sola programiranja v prologu Sula programiranju v prologu bo omogočala udeležencem učenje programiranja v prologu na računalnil