Volume 14 Number 3 July 1990 YU ISSN 0350-5596 ... ■ - ■ ■ f m É Informatica A Journal of Computing and Informatics The Slovene Society INFORMATIKA LJubyana Informatica A Journal of Computing and Informatics Subscription Information Informatica (YU ISSN 0350 - 5596) is published four times a year in Winter, Spring, Summer and Autumn (4 issues). The subscription price for 1990 (Volume 14) is US$ 30 for companies and US$ 15 for individuals. Claims for missing issues will be honoured free of charge within six months after the publication date of the issue. Printed by Tiskarna Kresija, Ljubljana. Informacija za naročnike Informatica (YU ISSN 0350-5596) ìzide Štirikrat na leto, in sicer v začetku januaq'a, aprila, julija in oktobra. Letna naročnina v letu 1990 (letnik 14) se oblikuje z upoštevanjem tečaja domače valute in znaša okvirno za podjetja DEM 16, za zasebnike DEM 8, za študente DEM 4, za posamezno številko pà, DM 5. Številka žiro računa: 50101-678-51841. ■ - - - - - - , -Zahteva za izgubljeno številko časopisa se upošteva v roku šestih mesecev od izida in je brezplačna. Tisk: Tiskarna Kresija, Ljubljana. Na podlagi mnenja Republiškega komiteja za informiranje št. 23-85, z dne 29. 1. 1986, je časopis Informatica oproščen temeljnega davka od prometa proizvodov. Pri financiranju časopisa Informatica sodeluje Republiški komite za raziskovalno dejavnost in tehnologijo, Tržaška 42, 61000 Ljubljana Informatica A Journal of Computing and Informatics EDITOR-IN-CHIEF Anton P. Železnikar Volaričeva ulica 8, 61111 Ljubljana ASSOCIATE EDITOR Rudolf Murn Jožef Stefan Institute, Ljubljana The Slovene Society INFORMATIKA Ljubljana Letnik 14 Številka 3 July 1990 YU ISSN 0350-5596 Informatica časopis za računalništvo in informatiko VSEBINA Voice Driven Editor Understanding as Information Design of Hardware with Programmable Gate Arrays Transputerli v sistemih za delo v realnem času Simulacija in vrednotenje programske opreme za večprocesorski računalnik Računarski sistem "Sphinx" za prepoznavanje kontinualnog govora neodvisnih govornika sa velikim rečnikom Kriteriji za določanje sistemske programske opreme osebnih računalnikov za krmiljenje industrijskih procesov Razvoj in opis dvonivojskega modela morfološke analize in sinteze O znanju v porazdeljenih sistemih Bayesove umetne nevronske mreže Novice in zanimivosti Information and Postmodernism Z. Kačič 1 B. Horvat L Urlep B. Stok A. P. Zeleznikar 8 P. Praprotnik 31 B. Dugonik P. Kolbezen 35 B. Cukić 44 M. M. Miletič 54 D. Mrdaković 56 T. Erjavec 59 Tatjama Kapus 63 L Kononenko 72 87 A. P. Zeleznikar 89 VOICE DRIVEN EDITOR INFORMATICA 3/90 Keywords: dialog system, text processing, speech recognition, hidden Markov models, finite automata. Zdravko Kačič Bogomir Horvat Igor Urlep Faculty of Technical Sciences and Bojan Štok Computer Center, University of Maribor, Smetanova 17, Maribor A small dialog system, comprised in a text processing environment, is presented in this paper. A vector quantization and hidden Markov models were used for word recognition a d finite automata for syntactic/semantic analysis. With full realization of a pragmatic level, what becomes necessary in a r'-il-time system, even better recognition accuracy could be i.nieved, as it is presented in this paper. Because of that, realization of a real-time system may be feasible. V članku smo predstavili realizacijo sistema dialoga, vključenega v okolje urejevalnika besedila. Pri razpoznavanju besed smo ^porabili vektorsko kvantizacijo in skrite modele Markova. Nivo s intaktične/semantične analize pa smo realizirali z množico končnih avtomatov, Z popolno realizacijo nivoja' pragmatike, kar postane neobhodno pri realizaciji sistema za delo v realnem času, je mogoče zagotoviti še večjo zanesljivost sistema, kot pa je zanesljivost, ki jo nakazujejo predstavljeni rezultati razpoznavanja. S tem so dane realne možnosti za razvoj sistema za delo v realnem času. 1. I nt roduc t ion Most ot commands in man - machine communication are passed to a machine by pressing buttons or in some similarly way. This way of communication becomes a bottleneck everywhere we have to enter a large quantity 0 f dat a. Because of that, there are a lot of research projects which main goal is to make it possible to communicate with a machine in a most natural way for a man - with speech. In 1952, Bell laboratories developed the first speaker-dependent speech recognizer, what is today believed to be the beginning- of the automatic speech recognition. era. The recognizer was able to recognize'numbers from 0 to 9. The next step forward was made in 1971, when the DARPA SUR project was launched. The main goal of the project was development of a 1000 word speech understanding system. Harpy and Hearsay II were the most successful systems developed in this project. There are many commercial product available on the marketplace today, but a great deal of them are speaker-dependent. Speech recognition systems can be divided into three groups regarding the methods of speech recognition used /1/: a) pattern matching technique (DTW), b) stohastic modelling (HMM),-and c) knowledge-based approach. The most successful commercial systems are from groups a) and b). In this paper a general architecture of a voice driven editor will be presented, but only realization of the speech recognizer will be discussed in more detail. 2. The architecture of a voice driven editor The voice driven editor enables voice activation of command functions ordinarily accessible through keyboard or with mouse. It accepts editing commands in a form of spoken sentences (e.g., select current paragraph, save file, open new window, ,..), With this, the editor should facilit^tte the text processing and first of all reduce the time required for finishing a text editing task. D-- J'UKI'kOCESaWO tNIU'OlNT VKCTOR fiiONt:-y>;H DKTKCnON quANTiuriON DIALOGUE r PRACUATIC S1NTACTIC/ SEMANTIC ANALYSIS WORD RCCOCNmON Figure I: Voice driven editor The voice driven editor consists of two main modules: a text processor and a multilevel speech recognition system. The speech recognizer is speaker-dependent isolated word recognition system, with 18 words vocabulary. The general scheme is presented in figure 1. The communication between speech recognition system and word processor is carried out through a mailbox. Many of the standard functions ordinarily included in text processors are built in the voice driven editor. For activation with voice, the most interesting among others are commands for selecting, formatting and sort ing. In our further discussion we will consider only the speech recognition system. It consists of four main modules: a) a word recognizer, b) a syntactic/semantic analyzer, c) a pragmatic analyzer, and d) a dialog modu 1 e. The segmentation is done by multiplying the speech signal, s'(n), by a window signal, w(n) . «(m) - Kr.m. p.nod-l- •"■"»"^l"'«"' - Figure 3: Segmentation of the speech signal The Hamming window is given by w(n) = f 0.54-0.46 cos n=0,l.....N-1 otherwise (2) Here, N is the desired window length in samp les. 3. Word recognizer The word recognizer attaches a word hypothesis, from available vocabulary, to appropriate input speech sequence. The word recognizer consists of: a) a preprocessing module, b) a segmentation module, c) an endpoinl detection module, a vector quantization module, d) e) and of a word hypothesis detection module 3.1. Preprocessing Typical spectral envelope of is illustrated on figure 2. the voiced sound Figure 2: Typical voiced sound f spectral envelope of the We can notice how the spectrum rolls off in high frequencies. Because of that, the LPC model will satisfactorily approximate only the low frequencies. To avoid this, we pass the speech signal through a preemphasis filter with transfer function 1 - az"'. If s(n) is the input signal, then the preemphasized signal s ' (n) is 3.3. Endpoint detection The aim of the endpoint detection is to separate nonspeech sequences from speech sequences. In our experiment we used the endpoint detector which measures the speech amplitude function. The methods shown in Fig. 4 locates energy pulses, corresponding typically to syllables or words, by comparing energy in decibels against four thresholds ki, ka, ka, k* /2/. When energy exceeds the lowest threshold ki (3 dB above background noise), time Al is noted. If it rises above k, (10 dB) before falling below ki, time Ai is assumed as start time (unless duration Aa - Ai exceeds 75 ms, where Aa is then viewed as the start time and the signal preceding Aa is considered as breath noise). The end time is determined using thresholds k2 and kj (A* is the end time unless A» - Aa > 75ms). The values of the thresholds were determined by experiment. Figure 4: Endpoint detection s'{n) = s(n)-0.9375's(n-l) (1) 3.2. Segmentation In this phase, we segment the speech signal into small segments, called frames, which are assumed to be quasi-stationary. Figure 3 shows an example of speech segmentation. 3.4. Vector quantization A quantization means a vector X into a vector c = (yi, ya,..., y±,...), codebook. Appropriate usually created through the minimum average quantization error E(d(x,y)) searching /3/. In our experiment the LP method was chosen for generation of vectors and the Itakura distance as a metrics. mapping of an input yi from code alphabet which is known as a code alphabet C is J.4.1. Linear prediction Given a linear, discrete-time system, the object of linear prediction is to estimate the output sequence or, specifically, the forthcoming output sample from a linear combination of input samples, past output samples,orboth: y(n)= i:b,x(n-i) - E a,y(n-i) (3) " ■ E. "' a„(k)=a„.,(k)-k„a„.,(n-k) , k=l,2.....m-1 E„= (l-kS) E.., The factors a(i) and b(J) are called predictor coefficients. 3.4.2. Derivation of the linear prediction equations Given a zero-mean signal y(n), in the all-pole predictor, we wish to estimate the value at point n as a linear combination of past values y(n)=-E a, y("-i) (1)' The result is a vector of LPC coefficients a = (1, -ap(l), -ap(2)..... -ap(p)) 3.4.3. Itakura .distance Let a = [l a, a, ...■ aj' Then the error is p - ' e(n) = y(ii)-y(n)= £ a,y(n-i) 1=0 where a(0) = 1. (5) To derive the predictor, we compute the coefficients a which' will minimize this error in the mean-squared sense, i.e., that will minimize E = . The coefÌEicients will be found by the use of the orthogonality principle. This principle states that the desired coefficients are those which make the error orthogonal to the samples y(n-l), y(n-2)..... y(n-p). The finally result of that procedure is a set of p equations, which can be represented as follows: r-o r, r, r, r„ r, i-j r, r„ i-p-. a, I-, a^ a. = 1-3 a p /p (6) Rr ro 1-, r, r„ be the coefficient vector and the autocorrelation matrix for the LPC vocal tract model ,Hi. Let aa, Ra be the corresponding quantities for Ha. The likelihood ratio can be defined either as "lri J _ al R, a, """ ai R, a. (10) (11) The log-likelihood ratios are the logarithms of these expressions: where (12) r, =E y(n)-y(n-l) , 1=1,2, ... ,p (7) The elements of the R matrix are autocorrelation coefficients. In the R matrix all the elements along any diagonal are equal. Such a matrix is called Toeplitz matrix. Furthermore, R is not only Toeplitz but also symmetric. The above mentioned properties of the R matrix permits usage of Levinson-Durbin recursive method, which is computational very efficient. The recursive solution steps are as follows:' 1. n=0 a, {0) = 0, i = 0,l, ... ;p 2. n=l,2.....p The metrics of (11) and (12) are nonsymmetric. If we want a symmetric measure, we can use the quantity ■ d + d _LUI UZ -1 (13) which has the desired property of symmetry. The expression a^'Riai is the energy of the residual signal after LPC modeling. The filter coefficients are computed from the autocorrelation coefficients r(j) in such way as to minimize this energy. Hence, if we replace a.^. with any other nonzero vector of coefficients, this expression Increases /4/. 3.5. Hidden Markov model The hidden Markov model can be described in a following manner: The hidden Markov model is a set of N distinct states. At regularly spaced discrete tines, the system undergoes a change of state according to a set of probabilities associated with state. That process could be called an observable Markov model since the output of the process is the set of states at each instant of time, where each state corresponds to an observable event. But, if we extend this model in such a way that the observation is a 0.6 A O.Q B 0.2 0.4 A 0.3 B 0.7 A 0.5 B 0.5 Figure 5: Two state HMM with symbols A and B probabilistic function of the state, the above process become hidden and this new model we call HMM /6/. Figure 5 shows an example of two state HMM with symbols A and B. Figure 6a; An ergodic HMM 3.5.1, F.lements of the HMM The HMM can be described by the following: 1) N, the number of states in the model. We denote the individual states as S = { Sj, Sa,..., S„}, and the state at time t as q«. 2) M, the number of distinct observation symbols per state. The observation symbols correspond to the physical output of the system being modeled. We denote the individual symbols as V = {v,, Va,..., v„}. 3) The state transition probability distribution A = {aij} where a^j = = Sj\q. = Si), 1 Si,j s N. 4) The observation symbol probability distribution in state j, B = {b_,(k)), where bj(k) = P(v,, at t\qt = Sjl, 1 S J S N 1 S k S M. Figure 6b: A left-right HMM 5) The initial state distribution it whe re Til = P[q. = Si] , 1 S i S N. For a given appropriate values of N, M, A, B, and n, we can use the HMM as a generator to give an observation sequence 0= 0, ... Ox. To indicate the complete parameter set of the model we use the compact notation o = (A,B,il) /6/ . 3.5.2. Types of HMM Figure 6c: A parallel left-right HMM 3.5.3. Choice of basic phonetic unit In HMM models definition basic phonetic unit have to be chosen. This unit have to be good defined and to have ability of learning. The basic unit usually used is a word or a phoneme. The word based models are good tor recognition of small word vocabularies but for a large vocabulary too much training date are required. The phoneme based models are very simple for training but their success fuiness depend on phonemes left and right from a current word. In the voice driven editor a word has been used as a basic phonetic unit. In general, HMM is an ergodic model (fig. 6a). It means that any state can be reached from any other state. For such a model full state transition matrix exist /5/. For some applications, nonergodic models are more appropriate. Figures 6b and 6c show two examples of nonergodic model. The first one is left-right model and the second one is parallel left-right model. The process modeled by LR model starts in state 1, continuous trough other states in monotony ascending order and finishes in state N. In our experiment we model . have used the left-right 4. The level of analysis syntactic and semantic The syntactic/semantic analyzer was realized through a set of finite automata. Each of these automaton has a start state and one or more finite states. The number (characterizing an action) has been assigned to each automaton. The word sequence which is generated by the word recognizer is checked by each of the automaton. If after this, the automaton is in finite state, the command is regular and an action number is generated and transferred to the pragmatic level. If no automaton is in finite state, the error is mediated to the dialog level. 5-1up 1 e set of « is a 4.1. The finite automaton The finite automaton (FA) is a (Q,r,«,qo,F) where Q is a finite states, i is a finite input alphabet, total function QxE -> Q (transition function), qo is the initial state from Q, and F is a set of final states. To describe the behavior of an FA on a string, «e must extend the transition function i to apply to a state and a string rather than a state and a symbol. Let S = QxJ: -> Q. Then «' = Qxl- -> Q can be defined as follows 1. V q£ Q <5 (q.£) = q) 2. V qeQ. weS'.aeS (5'(q,wa) = đ{(5'(q,w),a)) The formula 6(q,w)'=r means : . state r can be reached A language of finite automata M is a set of words which bring us from initial state qo to some final state. It can be written as L(M) < w:«'(qo,w)6F>. To each word in our system one symbol which is element of I has been assigned and for each action a finite automaton has been defined. The automaton is presented in following form: Si ns,1/simiI ns1 a/simis ... nstM(l)/simiK(l) Sa nsai/simai nsaa/simaj ... nsa„(2)/sitn2„(2) s„ ns„,/sim„i ns„a/sim„2 ... ns„„(N)/sim„„(N) Each row describes the transition, from state Si to state nsij at symbol simij. Figure 7.b shows an example of automaton for command "ODPRI OKNO", and figure 7a shows the same automaton described with structure used in our explanation. STA8T (odfri) iPt I ! odpri okno 1 2/1 W! Ì ili ill 1 Ml t tID i 4/1 J (okaol (novo), 1 2 j ! 1 J (oknol 1-> J * 1 (oknol Figure 7a lodpii) EtD Figure 7b 4.2, Pragmatic level At pragmatic level the system is trying to execute the recognized command. If this can not be done, the message about conflict situation have to be mediated to the dialog' level. Let's show some meaningless commands in the VDE system: a window which was not opened can't be closed, - more than 10 windows can't be opened , - a text which was not previously selected, can't be deleted - a page which doesn't exist can't be reached. 4.3. Dialog level The task of this level is to try conflicts which were found syntactic/semantic to solve at the or pragmatic level. This have to be done throughout the dialog with the user. The messages are mediated to the user by means of acoustic signal or with reports displayed on the screen. Let's consider some examples of the dialog with the VDE: U: next window C: conflict - only one window is open advice: open next U: open the window of C: incomplete command window U: open next window C: window is opened U: select C: entire text selected U: mark C: Incomplete command - advice: mark all U: open new window C: conflict - all windows are already opened -advice: close the window you don't need / U - user C - computer / S. Experimental results the speech recognition system simulation has been realized on the VAX 8800 computer and the code has been written in VAX Basic and VAX Assembler. The speech signal was filtered by band pass filter with cutoff frequencies at 300 Hz and 3400 Hz, and sampled by 10 KHz frequency at 12-bit resolution. The samples were windowed with 32 ms long Hamming window function and with 16 ms frame period. Features of the sampled speech were described with 12*" order autocorelatlon based linear prediction. A set of phoneme utterances and a set of word models has been created In the training phase. 5.1. Creation of the reference vectors vector quantization for The 36 reference vectors has been created. From different utterances individual phonemes has been labelled manually and divided into 36 classes. For each class, the vector with minimum distance from all vectors within the class has been taken as a class reference vector. The list of phoneme used in vector quantization Is shown in table 1. An example of vector quantization "ODPRI": for the word dl (4) al (1 ) (4) p2 (14) Ol (12) o2 (12) n (11) dl (4) pl pl( 13) pl Ol (12) Ol (12) e2 (5) (13) dl (4) d2 (4) d2 (13) p2 (14) b (2) b (2) Table 1: The quantization list of phoneme used in vector Honen luibtr of «ectors BHK Mlbols 11 U J! H <1 11 t li cd 21 cc2 U cd 12 dl U d: U ó: e! I ( tS ir ti IO b 6 il i! SI i) 10 ) il lì IS k) 1 1 li I il ol u o! 34 Q] u pl »5 II pi 8 r 18 s U ss SO ti 19 ti 4 u t t 2( II 21 b (2) b (2) t2 (18) d3 (4) (7) il (7) il (7) il (7) il el (5) p2 (14) n (U) n (11) (7) il (7) il ) il (7) il (7) (11) n (11). 5.2. A HMH word model Each HMM model has 5 states (N=5). The number of a possible symbols in our system was 21 (M = 21), Kor each model S = (A,B,Tt) the following values has been defined a..j = 1/N bjw = 1/M 1/N, i. J J k 1,2.....N 1,2.....N 1,2.....M 1,2.....N The training procedure for one word model was as follows. For each word a sequence of symbols has been generated. The model's parameters has been reestimated by iterative Baum-Welch method /6/. The models for the following words have been defined: ODPRI, NOVO, OKNO, ZAPRI, OZNAČI, STRAN, VSE, ZBRIŠI, TEKST, VSTAVI, SHRANI, NASLEDNJE, SKOČI, NA, POIŠCl, KALKULATOR, KONČAJ, NALOŽI. been used in the training phase and all utterances from the available set has been used for the recognition process. After word models initialization, 7S iteration has been performed on each model. Average word recognition accuracy was 80.95X. More detailed results are shown in table 2. Table 2: Word recognition results •ord recoii>i(l |t| lisrecoliilcd ai UlUlitor 100.00 koačij n.o odpri, Oliaci 01 SM« balkolitor, skoti ntloii 100.00 Ditltdnlt 100.00 nofo II.» okio odpri 100.00 okno IS.II goto otoiči SM« uloti, tko{i poltči 100.00 shriii 15.11 itrao tko(i 100.00 straa 100.00 tekli 100.00 odpri «te SM« strai,latledoje.ittafi utili «l.ti shraii, lapri lipri Il.«l odpri, otoafi ibiUi SI.u lUU, (olKi By attaching the syntactic/semantic analysis, early discovering of bad recognized words and the semantic Irregularity becomes possible. Considering this, we tried to recognize the group of words (sentence) which correspond to particular command. For each command seven different utterances has been generated. The recognition results are given in table 3 first column are the recognized commands, second shows the recognition rate and third detected error rate. In the the Table 3: Experimental results of commands recognition in per cent coiiand (sentence) recocn. detect, errors odpri novo okno 51.U 100,00 odpri okno 85.11 100,00 zapri novo okno 28.51 85.Il zapri okno SMI 85,11 skoči na naslednje okno SM» 100.00 skoči na stran SI.U 100,00 označi stran SM« Il.«l Because of the low recognition rate, the recognition module has been upgraded in such a way that the best two word hypothesis has been mediated from recognition module to syntactic / semantic module. Table 4: Results of commands recognition the best two hypothesis in per cent with coiiand (sentence) recotn. detect, errors ndpri noto okoo lOO.OO odpri okno 100.00 - lapii noio nino 11 .«J 50.00 zapri okoo II.«] 50.00 skoči na naslednje okno 100.00 - skoči na stran 100,00 - označi stran 100.00 • 5.3. Recognition results A created set of utterances has had 7 utterances for each word. The 5 utterances has Now, the syntactic/semantic module tries to recognize a command with the first word hypothesis. If the recognized command was meaningless, the whole procedure was repeated with the combination of the first and the second hypothesis. In this «ay, the results has been improved as we can see from table 4. With full realization of the pragmatic level (which is necessary for the real-word application) the recognition rate is believed to be even more improved. 5.4. The lime complexity Because of the algorithm's complexity, it is very difficult to analytical compute its time complexity. But to get at least a rough picture of the time complexity of particular module, we will consider the CPU time which is required to handle the task. The most time consuming part was the vector quantization. The 1.66 sec (on DEC VAX 8800) was needed to compute the linear prediction coefficients for one window and to assign a symbol from the codebook. If an average word length is 35 windows, then 58.1 sec of CPU time is required for vector quantization for one word. For endpoint detection, O.OS word recognizer have to with each word model. To compute a probability for one word' model, 0.1 sec was required and for all models (18 words in a vocabulary) the CPU time needed was about 1.8 sec. Therefore for one recognized command, containing four words, approximately 240 sec was needed. sec was needed. The compare input symbols 5.5. The space complexity The word recognizer is the biggest time consumer and because of that only the space complexity for this part of the VDE will be considered here. The HMM word model consist of a matrix A, B and of a vector n, which elements were represented in the computer with the highest accuracy (8 byte). The size of the matrix A was 5x5, the size of the matrix B was 5x21, and the size of the vector n was 1x5, which makes 1080 bytes for one word model. As we can see, for 1000 words vocabulary we would need 1080 Kbytes for all models . previous chapter suffice also for a few hundred words vocabulary /5/. 6. Conclusion The recognition results presented in this paper indicates that used methods may be considered as appropriate for the realization of the voice driven editor. Therefore, our very next step will be to build VDE, with approximately 200 words vocabulary, which can be run on suggested hardware as a real-time application. References 1. Zdravko Kačič, "On the use of array of active perceptors in a speech recognition system", Master thesis, Maribor, April 1989 (in Slovene). 2.Douglas 0'Shaughnessy, Speech Communication, Human and Machine, Reading, Massachusetts: Addison-Wesley Publishing Company, 1987. 3. D. Wolf, H, Reininger, "Recent Advances in Speech Coding", in H. Niemann ed.. Recent Advances in Speech Understanding and Dialog Systems, Berlin Heidelberg: Springer-Verlag, 1988, pp. 183-205. 4. Panos E. Papamichalis, Practical Approaches to Speech Coding, Englewood Cliffs: Prentice-Hall International, 1987. 5. Michael A. Pichney, Subrata K. Das, "A real-time IBM PC based 1 arge-vocabu1 ary isolated-word speech recognizer", Proceed of Voice processing, London, 1986, pp. 173-182 6. L.R. Rabiner, "Mathematical Foundations of Hidden Markov Models", in H. Nieman ed.. Recent Advances in Speech Understanding and Dialog Systems, vol.46, Berlin: Springer Verlag, 1988, pp. 183-206. 5.6. The criticism of the real-time system According to the time and space complexity, for implementation of the real-time system, we^ think that the following hardware would suffice : - A/D converter with 10 KHz sampling rate at 12-bit resolution, signal processor TMS 320C25 for vector quantization - signal processor TMS 320C25 for computing the HMM probability. - INTEL 80286 or INTEL 80386 as a host processor for the realization of higher processing levels. - at least 2 Mbytes of DRAM, - a hard disk with at least 5 Mbytes of memory for app1icat ion. 5.7. The expansion ability The advantages of the system based on the HMM is that if we want to have bigger vocabulary, the needs for space and processor power do not grow so fast as they do in the other similar systems. The fundamental unit in VDE system is word, but for larger vocabulary more appropriate fundamental unit would be phoneme. We believe that the hardware suggested in the UNDERSTANDING AS INFORMATION INFORMATICA 3/90 Keywords: blindness, breakdown, disorder, electronic dictlonai7, expert system, formalization, hermeneutlcs. Information, Intelligence, language, loseableness, Anton P. žeieznikar misunderstanding, meaning, philosophy, semiotics, Voiaričeva ulica 8 theory, understanding 6IIII Ljubljana, Yugoslavia Understanding can be comprehended as a regular informational process occurring in various informational realms—in the living and the artificial—. Understanding as information concerns a comprehensive field of domains which are philosophic, linguistic, physiologic, psychologic, cognitive, and informational. The informational domain can embrace all other domains as their notional substance, putting them together in a complex and mumally dependent informational system of understanding. Part One of the article deals with general philosophy of understanding as information. Within this context it treats the meaning of the noun »understanding« and the verb »to understand« in Latin, Classical Greek, English, German, and Slovene, further, understanding as a philosophic realm concerning meaning, hermeneu tics and semiotics, the so-called losableness, blindness and breakdown of understanding, intelligence as understanding and vice versa, the connectedness of principles of understanding and principles of information, possibilities of formalization of understanding, of an informational expert system and informational electronic dictionary, misunderstanding and disorder of understanding as information, all in the context of language, science and culture. Razuinevai\je kot informacija Razumevanje je mogoče pojmovati kot regularni informacijski proces, ki se pojavlja v različnih informacijskih domenah—živih in umemih—. Razumevanje kot informacija zadeva obsežno polje domen, ki so filozofska, jezikovna, fiziološka, psihološka, spoznavna in informacijska. Informacijska domena zmore zaobseči vse druge domene kot njihova pojmovna podstat, jih povezati v kompleksni in medsebojno odvisni informacijski sistem razumevanja. Prvi del članka obravnava splošno filozofijo razumevanja kot informacijo in v tej povezavi pomen samostalnika »razumevanje« in glagola »razumeti« v latinščini, klasični grščini, angleščini, nemščini in slovenščini, nadalje razumevanje kot filozofsko domeno, ki zadeva pomen, hermenevtiko in semiotiko, tako imenovano zgubljenost, slepoto in prelom razumevanja, inteligenco kot razumevanje in obratoo, povezanost principov razumevanja s principi informacije, možnosti formalizacije razumevanja, informacijskega ekspertnega sistema in informacijskega elektronskega slovaija, nerazumevanje in motnje Ijolezni) razumevanja kot informacije, vse to pa v kontekstu jezika, znanosti in kulmre. PartOne A General Philosophy and Theory of Understanding as Information 1. Introduction ... Being-with is such that the disdosedness of the Dosein-with of Others belongs to it; this means that because Dasein 's Being is Being-with, its understanding of Being already implies the understanding of Others. This understandini, like any understaruiing, is not an acquaintance derived from knowledge about them, but a p nordially existential kind of Being, which, more than anything else, makes such knowledge and acquaintance possible. ... M. Heidegger (BT) 160-161 Understanding does not concern merely language and linguistically comprehended concepts and principles as it is usually thought; it concerns information and informing of information in general, irrespective of informational levels in question, from the most primitive informing to the most perplexed one. For instance, in the domain of expert systems, understanding concerns language, learning, reasoning, and problem solving. Understanding can be understood as a characteristically particular, informationally structured and organized process in the realm of information. Understanding concerns a thing's or a being's reaction (information, counter-information, and information of embedding) as the consequence of impacts (influences) of the internal and the external world. In this way, understanding can be comprehended in a purely informational way, that is, as information caused by interna! and external informing and as the use of such information for some general, special, reasonable, intelligent, or any other purposes. Within the realm of informational philosophy and informational theory, understanding can always be philosophically perceived and theoretically handled as a regular informational process (entity, phenomenon, operand, informational formula) on different hierarchical levels of informational arising. Any arising information can be conceived as a structure possessing the faculty of understanding (informational observing, investigation, counter-informing, informational embedding). Under these circumstances, understanding is becoming a kind of autonomous informational cycle informing within the general informational cycle of informational arising. At the beginning of this essay it is f>ossible to put a series of questions which can be used as origins of the informational study of the philosophy and the theory of understanding. These questions can be the initiators of distinct and substantial formulas which will be informationally developed through the discourse of this essay. Thus, let us start with a series of obvious and commonsense questions, tracing the path into the realm of informational understanding of understanding. What is understanding as information? What are informational principles of understanding? How does understanding inform and how is it informed? What is the meaning of the term »understanding« in different natural languages? What is understanding as a philosophical realm which concerns meaning, hermeneu tics (interpretation), semantics, interpretation of time as the possible horizon for any understanding of information, etc.? How is understanding lost in itself informationally? How can the losableness of understanding be broken down to clarify the blindness grounding in the losableness of understanding? What are the informational levels of understanding, from its basic informational level to its most complex functional, form? How is information, in principle, always a process of understanding? What is the role of understanding in an intelligent system and intelligent environment? How does understanding impact intelligence and its genuine processes of intelligent informing and how does intelligence as information impact understanding as information? Which are the formal-theoretical possibilities for informational axiomatization and theory of principles and problems of understanding? On the other side, questions of understanding can take also explicitly practical forms. For instance: How could understanding as a namral principle be introduced (as an explicit informational process) into expert systems? How could ùnder-standing as information be applied at the design of an electronic dictionary? Which are the basic components of understanding as an informational process over a certain informational domain (of knowledge, experience, expertise, etc.)? What does understanding as information mean within the domain of a namral language, science, culture? 2. What is Understanding as Infonnation in General? ... State-of-mind is one of the existential structure in which the Being of »there« maintains itself. Equiprimordial with it in constituting the Being is understanding. A state-of-mind always has its understanding, even if it keeps it suppressed. Understanding always has its mood. If we Interpret understanding as a fundamental existentiale, this indicates that this phenomenon is conceived as a basic mode of Dasein 's Being. On the other hand, »understanding« in the sense of one possible kind of cognizing among others (as distinguished, for instance, from »explaining«), must, like explaining, be Interpreted as an existential derivative of that primary understanding which is one of the constituents of the Being of the »there« in general. M. Heidegger (BT) 182 Let us give some initial general answers to the question of this paragraph, considering the following basic questions: What are informational principles of understanding? How does understanding inform by itself and how is it informed by other information and by itself? What are the informational levels of understanding, from its basic informational level to its most complex functional form? How is information, in principle, always a process of understanding? Within these questions we should not discuss the possibilities of informational formalization of understanding. Formalization processes of understanding will be exposed in the second part of this essay dealing with the formal, axiomatic, logical, and algebraic informational theory of understanding. As far as that is concerned (POI), principles of understanding are not waiting to be discovered, they have to be constructed on the basis of our everyday experience in the domain of language, thought, comprehension, imagination, etc. What are informational principles of understanding? First, this question has to be answered on a general level. Understanding as information performs as regular information. It arises informa-tionally in the domain of some broader informational context (perplexity of information) and informs spontaneously and in a circular way, i.e., through informing, counter-informing, and embedding of the arisen understanding into the source information (source understanding). Thus, spontaneity and cyclicity of understanding as information can be investigated in a general way, however, this generality can be decomposed, for instance, on the level of an informational formula, stepwise in greater and greater details, developing and particularizing the initial formula and in this way constructing a concrete scenario of understanding. How does understanding inform and how is it informed? Understanding as information informs itself and other information with which it is infor-mationally perplexed by its informing and counter-informing, and by its embedding of the produced counter-information and other information. In this way, understanding as information arises through informing of itself and other information, by which it is informed, i.e., informationally impacted. Understanding is open to be informed by the perplexed information and it can inform openly other information. What are the informational levels of imder-standing, from its basic informational level to its most complex functional form? Understanding as information can be very simple and very complex informational process. The fundamental level of understanding is observable already on the level of basic informational principles (POI). Through counter-informing of information new information is coming into existence and the embedding of this information represents an act of understanding of the arisen information by the original information. Through informing, counter-informing and embedding, the understanding of a given information arises and becomes more and more complex as a part of the developing information. How is information, in principle, always a process of understanding? Through informational arising which is a phenomenon of informational observation, investigation, construction and reaction, an informational process of understanding always exists, from the basic level of informing of information to its most complex, intelligent cases. Understanding as information is a consequence of informational complexity within living and non- living world. 3. What is the Meaning of the Noun »Understanding« and the Verb »to understand« in Different Natural Languages? ... In the projecting of the understanding, entities are disclosed in their possibility. The character of possibility corresponds, on each occasion, with the kind of Being of the entity which is understood. Entities within-the-world generally are projected upon the world—that is, upon a whole of significance, to whose reference-relations concern, as Being-in-the-world, has been tied up in advance. When entities within-the-world are discovered along with the Being of Dasein—that is, when they have come to be understood—we say that they have meaning [Sinn]. ... M. Heidegger (BT) 192 The meaning of the term »understanding« belongs to the most abstract notions of language and human mind. In fact, understanding means that something could be understood by somebody in such way or another. In many cases, imderstanding means to understand something in the same or similar way as it is understood by somebody else or to understand it in the way as it was understood in some prior time (for instance, the; so-called problem of hermeneutics). Let us examine the meaning of the term »understanding« in. Latin, Greek, German, English, and Slovene! 3.1. The Latin meaning of the noun » understanding« and the verb »to understand« But that which is understood, taken strialy, is not the meaning but the entity , or alternatively. Being. Meaning is what wherein the intelligibility [Verständlichkeit] of something maintains itself. That which can be Articulated in a disclosure by which we understand, we call » THBCITI ÌH ^ «. M. Heidegger (BT) 192-193 In Latin, the noun understanding means mens (0, ingenium (n). The Latin noun mens (-tis, f) means in general mind, intellect, understanding: and in particular: a) judgment, discernment; b) disposition, feeling, character, heart, soul; spirit, courage, boldness, passion, impulse; c) thought, idea, opinion; A) plan, purpose. The Latin noun ingeniuin (-i, n) means in general innate or natural quality; ^d in particular: a) disposition, temper, character; natural bent; b) natural capacity, mental power, talents, abilities, parts, genius, fancy; c) man of genius', d) clever thought. In Latin, the verb to understand means intellego, comprehendo; teneo; accipio; percipio; certior fio; audio. The Latin verb intellego (-exi, -cmm) means in general to perceive; and in particular: a) to understand, comprehend, have skill in, be master of; b) to judge, think, be of opinion; c) to be a connoisseur. The Latin verb comprehendo means 1. a) /0 comprise, express, describe; b) to embrace with kindness', 2. a) to arrest, apprehend, capture; b) to detect; discover; c) to perceive, comprehend. The Latin verb teneo (tenui, tenmm) means in general to hold, keep, grasp, hold fast; and in particular: 1. to have in the hand, mouth, etc., to keep, seize, comprehend; a) to hold inmind, understand, conceive, comprehend, know; b) to hold one's way or course; to follow up, sail, steer, reach a place, land on, arrive at; c) to gain, acquire, obtain, attain; d) to convia, catch, detea; 2. to hold in one's possession, have, possess, be master of; a) to inhabit, occupy, garrison; b) to comprise, comprehend; to include; c) to possess, master; to hold fast, keep in, hold back, bind, fetter, control; d) to preserve, maintain, retain, guard; to remember; 3. a) to keep to, not to swerve from, remain true to; b) to last, endure, keep on; c) to charm, amuse, inspire; d) to bind, oblige; to maintain one's right; 4. a) to hold back, repress, check, restrain, suppress; b) to detain, delay; c) to keep a thing away from. The Latin verb accipio (-cepi, -cepmm) means 1. tO take, receive, get, accept; the Latin noun acceptum (-i, n) means what is received (money); a) to enter to the credit, to give credit for; b) to suffer, bear, c) to admit, approve of; 2. to receive as a guest; a) to entertain; b) to treat, deal with; 3. to bear, perceive; a) to learn, understand; b) to feel; c)to take, interpret, explain; 4. a) to obtain; b) to suffer. The Latin verb percipio (-cepi, -ceptum) means in general to seize, lay hold of, catch; and in particular: a) to take to oneself, assume; b) to get, receive, gather, harvest', c) to perceive, be sensible of, hear feel; d) to learn, know, comprehend, understand; —the Latin noun perceptum (-i, n) means principle, rule. The Latin verbal form certior fio seems to be of particular value for discussion concerning understanding as informing (of information). The Latin verbal form certus means in general decided; and in particular 1. a) determined, resolved; b) resolved upon; 2. a) settled, established, fixed; b) sure, true, to be dependent on; c) informed, assured, aliquam certiorem facere means to inform or apprise one; d) definite, positive, undoubted. The Latin verb fio (facms sum, fieri) means 1. to grow, spring up; a) to be bom or created; b) to happen, come to pass; fieri potest, ut means it is possible that; fieri non potest quin means it is indispensable, inevitable that; 2. passive of facere: a) to be made; b) to be turned into, appointed; c) to be estimated. The Latin verb audio means 1. to hear, to have the faculty of hearing; 2. to perceive, understand, learn. This short analysis of the meaning of the verb »to understand« in Latin shows the tremendous semantic complexity, perplexity, and semantic circularity of verbs concerning meaningfully the verb »to understand«. We see how the begun analysis could be continued by searching of meanings of already derived words. On the basis of this analysis, it is possible to understand how the verb »to understand« was used in different historical epochs by different philosophers. 3.2. The Greek meaning of the verb »to understand« and some derivatives and other words concerning this meaning ... The concept of meaning embraces the formal existential framework of what necessarily belongs to that which an wtderstanding interpretation Articulates. Meaning is the »upon-which« of a projection in terms of which something becomes intelligible as something; it gets its structure from afore-having, a fore-sight, arul a fore-conception. M. Heidegger (BT) 193 The meaning of the verb »to understand« in Classical Greek can be grasped, for instance, from the Aristotle's Metaphysics (MP) and compared, in the first step of investigation, by meanings of some more or less adequate Latin notions (words). For words in Greek, the direct transcription of Greek letters without accentuation and pronunciation marks will be used. The Greek verb noein corresponds to the Latin verb intelligo, so it is possible to catch the meaning for this word in the previous paragraph. In Greek, the meaning of noein is to think, know, widerstand. The Greek noun noys (in Latin, intellectus) means mind. Further, the Greek noetos (in Latin, intellectualis, intelligibilis) means intelligible, conceived and the Greek noesis (in Latin, intel-ligentia) means thought, conception, denotation, knowing. The Greek ennoema (in Latin, concep-tio) means item of information and the Greek dianoia (in Latin, mens, intellectus, meditatio) means intellect, intention, meaning, judgement, thinking, thought. The Greek phronesis (in Latin prudentia) means intelligence, while the Greek phronimos (in Latin prudens) means intelligent. The Greek phantasia (in h&imphantasia, imaginatio) means appearance, while the Greek pbantasnia (in Latin Phantasma) means image. The Greek episteme (in Latin scientia) means (scientific) knowledge, while epistasthai (in Latin scio, studeo) means a) to know, have knowledge, perceive; b) to understand, be skilled in; c) to Study. Further, the Greek gnosis (in Latin cog-nitio, notitìa) means knowledge; the Greek ginos-kein (in Latin cognosco) and the Greek giionai (in Latin nosco) means to know, understand, recognize. There are several other Greek words which include the meaning of »to understand«. For instance: epaieiii (obverto, audio), theorein {speculor, considero), thigganein (tango, attingo, appropinquo), ypolainbanein {suscipio, puto), tic. This short collection of terms which include the meaning of the verb »to understand« shows that the notion of »understanding« is copiously present in the meaning of several Classical Greek words. 3.3. The German meaning of the noun »das Verstehen« and the verb »verstehen« ...In so far as understanding and interpretation make up the existential state of Being of the »there«, »meaning« must be conceived as the formal-existential framework of the disclosedness which belongs to understanding. Meaning is an existentiale of Dasein, not a property attaching to entities, lying »behind« them, or floating somewhere as an »intermediate domain«. ... M. Heidegger (BT) 193 The German verb »verstehen« and to it corresponding noun »das Verstehen« have to be investigated from the viewpoint of the common German language. In German, nouns (of the neuter gender) corresponding to verbs can always be constructed in a regular, unrestricted manner. First, let us examine meaningfully the split verb »ver-stehen«. Stehen (stand, gestanden) means to stand. In Latin the meanings are sto, tolero, potior, perfero, statio. The Latin »sto« has usual meaning of »to stand«, but also of »to cost«. Among other meanings, the Latin »perfero« means to bring to a certain place, bring news, bring to an end. The prefix ver- can have several meanings belonging to the class of prepositions, for instance, »pre-« (earlier than, prior to, before, preparatory or perquisite to, in advance, beforehand, in front of, anterior to). Heidegger (SZ) says that in ontical speech the expression »etwas verstehen« is used with the signification of »einer Sache vorstehen können«. The German verb vorstehen means, for instance, to stand before, stand prior to something; to project beforehand; but also to head, lead the way, etc. 3.4. The English meaning of the noun and the adjective »understanding« and the verb »to understand« ... Dasein only »has« meaning, so far as the disclosedness of Being-in-the-world can be »filled in« by the entities discoverable in that disclosedness. Hence only Dasein can be meaningful [sinnvoll] or meaningless [sinnlos]. That is to say, its own Being and the entities disclosed with its Being can be appropriated in understandirig, or can remain relegated to non-understanding. ... M. Heidegger (BT) 193 Let us repeat the meaning of the verb »to understand« in English. To understand means 1: si) to grasp the meaning of; b) to grasp the reasonableness of; c) to have thorough or technical acquaintance with or expertness in the practice of; d) to be thoroughly familiar with the charaaerand propensities of; 2: to accept as a fact or truth or regard as plausible without utter certainty; 3: to interpret in one of a number of possible ways; 4: to supply in thought as though expressed. Further, the meaning of the intransitive verb to understand is 1: to have understanding, have the power of comprehension; 2: to achieve a grasp of the nature, significance, or explanation of something; 3: to believe or infer something to be the case; 4: to show a sympathetic or tolerant attitude toward something. To understand, comprehend, appreciate are synonyms and mean to have a clear or complete idea of something. • Understand may differ from comprehend in implying a result whereas comprehend stresses the mental process of arriving at a result; appreciate implies a just estimation of a thing's value. The noun understanding means 1: a mental grasp, comprehension; 2: a) the power of comprehending, the capacity to apprehend general relations of particulars; b) the power to make experience intelligible by applying concepts and categories; 3: a) friendly or harmonious relationship; b) an agreement of opinion or feeling; adjustment of differences; c) a mutual agreement not formally entered into but in some degree binding on each side; 4: explanation, interpretation; 5: sympathy. The adjective understanding means 1: knowing, intelligent; 2: endowed with understanding; tolerant, sympathetic. In English, the splitting of »under—stand« gives the direct meaning of to stand under something; in German, this meaning was, for instance, to stand prior to something. While in German »ver—stehen« can mean to stand in advance to something (to some information) or to have in fact a pre—standing (or pre—under—standing), in English, the preposition under means 1: below or beneath so as to be overhung, surmounted, covered, proteaed, or concealed by; 2: a) subject to the authority, con'rol, guidance, or instruction of; b) receiving or undergoing the action or effect of; 3: within the group or designation of; 4: less or lower than; falling short of a standard or required degree. 3.5. The Slovene meaning of the noun »razumevanje« and the verb »razumeti« ... This Interpretation of the concept of »meaning« is one which is ontologico-existential in principle; if we adhere to it, then all entities whose kind of Being is of a character other than Dasein 's must be conceived as unmeaning [unsinniges], essentially devoid of any meaning at all. Here »unmean- ing« does not signify that we are saying anything about the value of such entities, but it gives expression to an ontological characteristic. And only that which is unmeaning can be absurd [widersinnig]. Thepresent-at-hand, as Dasein encounters it, can, as it were, assault Dasein 's Being; natural events, for instance, can break in upon us and destroy us. M. Heidegger (BT) 193 In Slovene, the meanings of the verb »to understand« and the noun »understanding« root in üie verb »umeti« and the noun »um« and their derivations. The Slovene verb umeti means 1: to know, be skilled (in), be versed (in); 2: to understand; 3: to manage; 4: to contrive; 5: to be able, be capable. The Slovene noun um means 1: reason, intellect, intelligence; 2: sense, understanding: 3: mind, brains (pi); 4: wit. The direct counterpart of the English to »under-stand« and the German »ver—stehen« is the Slovene »raz—umeti«. Razumeti means 1: to understand, comprehend; 2: to get, make out; 3: to grasp, apprehend, take in. The direct counterpart of the English »under—standing« and the German das »Ver—stehen« is the Slovene noun »raz—umevanje«. Razumevanje means understanding, comprehension. The prefix raz- expresses a) a movement or an orientation to several places, directions; b) a fact that something is not together, in an original state; c) a partition, splitting into several entities; d) an occurrence of a state; e) an achievement of a desired intention, goal; f) a cessation of existence, of a state; g) a contrariness, contrariety. 3.6. What is understanding as information from the linguistic point of view? ... Understanding is not reconstruction but mediation. We ore conveyors of the past into the present. Even in the most careful attempts to grasp the past »in itself,« understanding remains essentially a mediation or translation of past meaning into the present situation. ... D.E. Linge (PH) xvi What is understanding as information after the basic semantic analysis of its meaning in Latin, Classical Greek, German, English and Slovene, and after the rounding up of diverse meaning and understanding of understanding as information in different languages? It can be recognized, in each particular language, how the notion and meaning of the term understanding as information arose through the historical development of a language from the already known other notions, informational entities, through characteristic counter-informing of these entities and through informational embedding of the arisen counter-information concerning understanding into the already existing information of a language. The consequence of this development is that the primordial meaning of, for instance, standing prior to, standing under, be skilled in, etc., arouse into the complex linguistic meaning of understanding. Examples of meaning of the term understanding in different languages showed slight and essential differences. In fact, the essential differences in German and English, in comparison between the primordial meaning and the new one, have been achieved through the syntactic shifting and connection of words, for instance, from »stehen vor« into »verstehen« or from »to st^d under« into »to understand«. This kind of difference is not so essential in the case of the meaning of Slovene verb »razumeti«, where the basic verb »umeti« has a similar meaning. The prefix »raz-« only accentuates a process of dis-ceming (also dis-junction) within reasoning, maybe an analytical component of reasoning (for instance, also the meaning of »dis-reasoning«). The linguistic analysis of the meaning of the term »understanding« in different languages showed not only the semantic complexity and perplexedness of the term in question, but also its realm of abstractness, bringing under consideration some of currently relevant topics in artificial intelligence, as, for instance, knowledge, belief, commonsense reasoning, intelligence, and maybe, through time, also understanding. 4. What Is Understanding as à Philosophical Realm Concerning Meaning, Henneneu-tics, and Semiotics? 77te concept of understanding as a »fusion of horizons« provides a more accurate picture of what happens in every transmission of meaning. By revising our conception of the function of the interpreter's present horizons, Gadamer also succeeds in transforming our view of the nature of the past, which now appears as an inexhaustible source of possibilities of meaning rather than as a passive objea of investigation. ... D.E. Linge (PtI) xix Understanding or comprehending of meaning and sense concerns not only speech and language but first of all information as living and cosmic phenomenology in its informationally widened realm. Understanding as an informational phenomenon appears on all, informationally perplexed levels of information. In the reality of the living and non-living, understanding concerns the most primitive physical, chemical, physiological, biological, neural, etc. phenomena, from the level of the primitive informational signaling to the level of the most complex thought concerning perplexed informational processes. To such understanding of understanding we can add some philosophically common facts which will improve and complement the informational image of understanding. In philosophy, understanding is, for instance, observing or perceiving of the so-called contents of a symbolic or informational expression. Such information of understanding can be, for example, the coimection of words in a language with the meaning or the connection of spoken and written text with its sense fill contents (thought, fact, situation). Understanding means also developing of an isolated, reasonably chosen element, which brings a new sense, observation, data, by means of sen-seful connections giving a complete logical comprehension of its meaning, intention, value, etc. Characteristic understanding of this sort is, for instance, the grasping of events belonging to specific historical situations or of behavior belonging to the psychic structure of individuality. Within the general philosophical sense, understanding means comprehension of meaning and sense, which occur first of all in speech, in the form of the understood Being pervading all relations of the historical being against the world. Thus, the way of understanding from the project of possibilities of a phenomenon to the comprehension of its sense is called ex-position. Further, exposition being in methodological accordance with a class of rules is called interpretation (in Greek hermeneia), however, the science of the art or of the skill of explaining which governs the understanding is called hermeneutics. Understanding as a specific way of cognition in sciences of mind opposes the explaining (in German, das Erklären) as a cognitive method in natural sciences. Thus, objects of understanding are tagged by uniqueness and individuality, whereas objects of explaining are characterized by general principles (laws). Heidegger (BT, SZ) has radicalized the hermeneutic problem in the framework of his fundamental ontology as hermeneutics of Dasein and he has determined understanding for the first time not as a kind of cognition being different from explaining but in an existen-tial-ontological way as Being of its own possibility. Heidegger claims that this is the existentiale which primordially pervades all kinds of Dasein's Being and the momentum which together with feeling and speech constitutes the entire existential structure of that »there« as the Being-in-the-world. As the possibility of the most primordial cognition, understanding discloses the circular structure, however, this hermeneutic circle performs not as a circulus vitiosus, but possesses a positive ontological sense. In other words, understanding presupposes understanding in advance (pre-understanding) in which the historical conditionality of its own world experience is included and, simultaneously, is the project to which Dasein opens its own future possibilities. Within this circle the historicity of man is disclosed as simultaneousness of past, present, and future. In a similar way, Gadamer (PH) tied his philosophical hermeneutics to the occurring of existence and also to the experience of art: understanding is never a determination or a process of the subject; it is an acting-historical occurring (wirkungsgeschichtliches Geschehen). Its system of sense or of horizon is determined by tradition with its own way of interpretation, by which that which will be interpreted is included and all these informational components constitute the entirety of understanding. This is the reason why her-meneutical reflection cannot jump over its own historicity and does not see any barrier of adequate understanding within a time span, but a positive opportunity of fusion of horizons. Also truth as a historical information, if com- prehended in this way, is nothing else than a conscioxxsprejudice: and thus, the (so-called scientific) method as a way of cognition in exact sciences is only a particular form of understanding, but in no way the only possible origin and experience of truth. First of all, such non-scientific modes of experience of truth are common in art and culture. Within the historical view, understanding as the grounding of hermeneutics belongs to the Homeric and the biblical hermeneutics. Aristotelian notion of reasonableness or intelligence (the Greek »phronesis« means mind, will; thought, insight; purpose; high spirit, pride, arrogance) as a specific practical cognition being characterized by good sense and authenticity (trustworthiness) was recognized later as the proper origin and paragon by the modem hermeneutics. As the art of reading, explaining, and interpreting of texts, the meaning of understanding owes its development certainly to the juridical and philological, but at most to the biblical hermeneutics in modem times (from Spinoza, Schleiermacher, Dithley to the contemporary hermeneu tical criticism of ideology). Semiotics or semiology (from the Greek sema or semeion) is the study of all patterned communication systems. Primordially, it is the theory of signs traditionally devised into three parts: syntactics as the study of grammar; semantics as the study of meaning; and pragmatics as the study of the actual purposes and effects of meaningful utterances. The idea of semiotics comes from J. Locke, its realization from C. Morris, and further development from R. Carnap. According to Morris, semiotics absorbs the entire logic, mathematics, linguistics, and rhetoric, but also a substantial part of cognitive theory, methodology, sociology of cognition and social sciences; it is also the organon (the body of principles of scientific or philosophical investigation) of all sciences. Within semiotics, the notions of semantics and pragmatics are the most important in regard to understanding. In contemporary philosophy, a part of semantics investigates relations between signs (symbols, markers) and that what these signs sign (symbolize, mark). A. Tarski defines semantics as the entirety of treating notions which express certain connections between expressions of a language and objects and states of things about which these expressions inform. The key notions of semantics are meaning and tmth. R. Carnap introduced the distinguishing of descriptive (philosophical) and pure (philological) semantics. Descriptive semantics is an empirical science which describes and analyzes semantical charac-. teristics of historically given languages. It is divided into special descriptive semantics for examination of distinct historically given languages and general descriptive semantics for examination of common properties of historically given languages. Pure semantics is a non-empirical, philosophic discipline dealing with construction and analysis of semantic systems; they can be similar to historically given languages or entirely imagined. Outside of these distinguished cases of semantics there is the so-called general semai xs which investigates the meaning of words in common speech, politics, science, philosophy, religion, etc. with the aim to discover linguistic confusion (disorder) and deception (illusion) and to contribute to the creation of improved language which would cause a better understanding among people. In Greek, »pragma« means a doing, deed, execution, transaction; action; fact, occurrence; matter, circumstance; business, task, enterprise; affair, objea; condition, etc. Pragmatics is a substantial view of informational individuality and subjectiveness, i.e., of informational spontaneity. Pragmatics studies the purposes, effects, and implications of the actual use by a speaker of a meaningfiil piece of language. J.L. Austin and others have believed that the study of speech acts may clarify problems about meaning, reference, and so on. A speech act consists of a locutionary act (saying words), which includes a phonetic act (making noises), a phatic act (using grammar) and a rhetic act (using meaningful words), and a per-locutionary act, by which effects (embarrassment, informational effects) are caused in other people. Understanding as information (as a basic or composed informational form and informational process) gets a new philosophical illumination, especially when it is developed as a particular formalized theory of information. As we have already recognized, understanding pervades the entire realm of the redefined notion of information, from the most basic concepts of information (spontaneous and cyclic informing, counter-informing, and embedding of information) to the most complex, interweaved, and perplexed (serial, parallel, and serial-parallel) informational forms and informational processes. In this perspective, a new, informational comprehension of understanding is coming into existence which is on the way to deliver new possibilities in exploiting the namral as well as the artificial givens (concepts, principles, constructs) in the informational realm of understanding. 5. How Is Understanding Lost (in Itself) Informationally? ... The meaning of Being can never be contrasted with entities, or with Being as the »ground« which gives entities support; for a »ground« becomes accessible only as meaning, even if it is itself the abyss ofmeaninglessness. ... M. Heidegger (BT) 193-194 As information, understanding is confronted with its own and other spontaneous and cyclic informing, counter-informing, and embedding of information, i.e., with its own and other informational forms and informational processes of blindness, intentionality, and/or directionality (circumstantiality) and so the question of its losableness (conditional closeness, stupidity, insensibility) arises. To clear the informational nature of losableness, there would be useful to bring to light its opposites, for instance, availability, disposability, and given information. Further, within the discourse of losableness of understanding as information, it would be recommendable to distinguish the time-concerning states of losableness, i.e., losableness of the present (e.g., »losingness«), of the past (e.g., »lostness«), and of the futore (e.g., the possibility of losing, i.e. losableness as it is). First, how can understanding as information be lost in itself? To answer this question, let us list some Heideggerian concepts of losableness applied to understanding as information in the following way: — understanding lost in what is encountered within-the-world; — understanding lost in equipment; — understanding lost in everydayness; — understanding lost in facmal circumstances; — understanding lost in irresoluteness; — understanding lost in just-always-already-alongside; — understanding lost in the making-present of the »to-day«; — understanding lost in possibilities which trust themselves upon one; — understanding lost in publicness; — understanding lost in something with which information is concerned; — understanding lost in the »they«; — understanding lost in the they-self; — understanding lost in the world of equipment; and — understanding lost in one's world. The losableness of understanding as information roots in its informing, that is to say, in the fact how it informs itself and other information and how it is informed by itself and by other information. Second, what understanding as information can lose because of its own informing and because of informing of other information impacting understanding as information? In Heideggerian terms, for instance, understanding can — lose its aroundness, — lose its basis, — lose its Being, — lose the Being of its „there,,, — lose its Being-in-the-world, — lose its equipmental character, — lose its force, — lose its genuineness, — lose its indigenous character, — lose its involvement-character, — lose itself, — lose its readiness-to-hand, — lose its time, etc. These examples show how understanding can be informationally investigated against losableness and loosing of understanding. Certainly, to these circumstances many others can be added. The point remains how understanding is lost in itself and how it can lose its power of understanding as information. 6. How Can the Blindness of Understanding Be Broken down? ... Any interpretation which is to contribute understanding, must already have understood what is to be interpreted. This is a fact that has always been remarked, even if only in the area of derivative ways of understanding and interpretation, such as philological Interpretation. The later belongs within the range of scientific knowledge. ... M. Heidegger (BT) 194 The breaking down as informational phenomenon concerns informing, counter-informing, and embedding of own and other information. By breaking down a monotone (regular, preserving) functioning of informing is stopped because of newly recognized reasons. For instance, a certain style of understanding is broken down if in some of its details it is substantially changed. To break down means to change, supplement, or dismiss the governing principles, beliefs, persuasions, prejudices, to modify them essentially and to get new insight into relating subjects of understanding. The consequence of breaking down is the so-called breakdown information causing, for instance, physical, mental, or nervous collapse, failure in progressing of an understanding, informational disintegration or decomposition of stable informational processes, division into informational categories, a new classification, etc. An important view of breaking an informing down is the so-called informational decomposition, by which stable and believed informational entities are split into new informational constituents. For instance, an informational formula or operand is decomposed by substitution and essentially changed by the procedures of particularization and universalization of informational operands and operators. Informational breaking down means to become susceptible to analysis and informational subdivision and to undergo informational decomposition under a new illumination of facts. Commonly, a real informational breaking down opens a new perspective or, as usually said, an abyss of possibilities or principally new informational horizons being not recognized as yet. Breaking down as a consequence of informing, counter-informing, and embedding of information interrupts the blindness of informing and suspends the habitual processes of comprehension. This does not mean that the new way of informing does not possess a blindness and that it cannot be broken down into a new perspective. The possibilities of new perspectives are impacted by the own informational arising in general and by the arriving of other information. Thus, informational blindness, which can be interrupted through arising of breakdowns is an informationally regular phenomenon of understanding as information. 7. What is Intelligence as Understanding and Understanding as Intelligence? What is the role of understanding in an intelligent system and intelligent environment? How does understanding impact intelligence and its genuine processes of intelligent informing and how does intelligence as information impact understanding as information? Let us make a short excursion into the domain of common and uncommon speech with the aim to show some analogies and differences in comprehension of terms »intelligence« and »understanding«. Let us proceed from the simple statement »Information informs.« This statement includes also the meaning of »Information is informed.« The resulting statement is »Information informs and is informed.« The next examples., which concern understanding (at least on the linguistic level) are the following: Thought thinks and is thought. Comprehension comprehends and is comprehended. Perception perceives and is perceived. Conception conceives and is conceived. Understanding understands and is understood. To come closer to the subject of informing, we can repeat these statements in the following way: Thought as information informs and is informed in the way of thinking. Comprehension as information informs and is informed in the way of comprehending. Perception as information informs and is informs in the way of perceiving. Conception as information informs and is informed in the way of conceiving. Understanding as information informs and is informed in the way of understanding. These statements can be broadened even more precisely in the following way: Thought as information informs and is informed in the way of thinking by itself and by other information. Comprehension as information informs and is informed in the way of comprehending by itself and by other information. Perception as information informs and is informs in the way of perceiving by itself and by other information. Conception as information informs and is informed in the way of conceiving by itself and by other information. Understanding as information informs and is informed in the way of understanding by itself and by other information. These statements show the openness, spontaneity, and circularity of subjects in question as information. Further, on the basis of the previous linguistic analysis it is possible to grasp how thought, comprehension, perception, and conception constitute informationally the process of understanding. And each particular process (thought, comprehension, perception, and conception) develops or arises informationally by understanding as an informational process of perplexed information. How can the intelligence as information be brought into the informational context of understanding? The first step of intelligent approximation would be, for instance: Thought thinks and is thought intelligently. Comprehension comprehends and is comprehended intelligently. Perception perceives and is perceived intelligently. Conception conceives and is conceived intelligently. Understanding understands and is understood intelligently. The meanings of these statements do not contradict in any way the primordial statements concerning thought, comprehension, perception, conception, and understanding. It could be said that the last statements reasonably include the faculty of intelligence which seems to be a substantial property of the entities in question. Because of the lack of the appropriate verb for the fact »to be intelligent«, it is possible to say: Intelligence as information informs and is informed in an intelligent way. Intelligence as information informs and is informed in a thinking, comprehending, perceiving, conceiving, and understanding way. Thought, comprehension, perception, conception, and understanding as information inform and are informed in an intelligent way. Intelligence as information thinks, comprehends, perceives, conceives, and understands. Etc. In short, intelligent informational systems understand and understanding informational systems are intelligent. Further deduction in the showed directions delivers finally: Intelligence as information informs and is informed in an intelligent way by itself and by other information. Intelligence as information informs and is informed in a thinking, comprehending, perceiving, conceiving, and understanding way by itself and by other information. Thought, comprehension, perception, conception, and understanding as information inform and are informed in an intelligent way by itself and by other information. Intelligence as information thinks, comprehends, perceives, conceives, and understands itself and other information and is thought, comprehended, perceived, conceived, and understood by itself and by other information. Understanding can be thought as a broadening of the notion of intelligence and intelligence can be comprehended as the substantial faculty of understanding. In this way, artificial understanding can be the broadened term for artificial intelligence. If we speak about understanding we have in mind intelligent informing within understanding as informing. 8. Principles of Uuderstaiidiug as Principles of Information How does information qua information concern the principle of understanding? How is understanding as a general informational component present in informational components of an informational entity? How can understanding as the informational component within the so-called basic informational cycle be investigated, for instance, as a component of informing, counter-informing, and embedding of information? The answers to these questions should explain the understanding nature of information as a basic principle which till now remained concealed, i.e., explicitly unrevealed. Let us begin the discourse of understanding within the basic informational cycle by imder-standing as information dwelling within informing, counter-informing, and embedding of information. Taking a time slice of observing an informational entity, we state that this entity informs, counter-informs, and embeds information. We say that information informs itself and other information, that it counter-informs or produces from itself and other information the so-called counter-information, and that it embeds informa-tionally the produced or informationally arisen counter-information and other incoming (to its »consciousness« arriving) information. This process of informing, counter-informing, and embedding constitutes the so-called basic informational cycle of the informational entity in question. And within this cycle, its constitutive components demonstrate the so-called capability of understanding in the form of observing, investigating, and interpreting of information. As we can remind, counter-informing of information and embedding of arisen information was a characteristic act of understanding of arisen information by source information and the new information could be embedded into existing or source information merely on the basis and to the extent of its understanding. Here, understanding as information was meant as a new embedding information which arose too, and especially this embedding information has enabled the »understanding« of arisen information. After this discussion it is possible to resume the question how could the understanding as information be present in the basic spontaneous and cir- cular processes of informing, counter-informing and embedding of information. To some extent, depending on the nature of information in question, understanding as information can be understood to be the constitutive component of informational forms and informational processes in the form of arising and embedding of information. Thus, understanding as information is merely another marker for that what was called observing, investigating, and embedding of information appearing in informing, counter-informing, and embedding of information. Thus, understanding is a basic faculty of information which arises and embeds information. informational noise which simply cannot be perceived by the entity in question. A similar effect of perceptional lack can occur in the case of information's counter-information. In general, perceiving (perception, comprehension, understanding) of information by information is always an informational process of a noisy transition or informing of information (misperception, miscomprehension, misunderstanding). Perception of the own counter-information or other information means simply the filtering of perceived information by informational abilities of perceiving information. 9. Informational Formalization of Understanding Which are the formal-theoretical possibilities for informational axiomatization and theory of principles and problems of understanding? First, formalization of understanding has to proceed from the fact that understanding performs as regular information, i.e. that within the informing of understanding, counter-understanding is coming into existence and that this counter-understanding is informationally embedded into existing understanding of information. In this way, understanding, counter-understanding, and embedding of understanding constitute the so-called spontaneous informational cycle of understanding. Second, informing of information can be comprehended as the possession of an informationally innate component of understanding of information as information: when information is coming into existence as counter-information, this counter-information has to be informationally connected (related) to, interweaved with, or embedded into the existing source information. The act of connecting, interweaving, or embedding is by itself a kind of understanding of the arisen counter-information (and other information) by the source information. In this way, information possesses an innate component of understanding. Third, information, by which an informational entity is informed, is informationally perceived by this entity within the ability of its own informing. If information does not impact an informational entity at all, this information performs as a pure 10. Understanding as an Informational Principle of Expert Systems How could understanding as a natural principle be introduced (as an explicit informational process) into expert systems? How could understanding as information be applied at the design of an electronic dictionary? Which are the basic components of understanding as an informational process over a certain informational domain (of knowledge, experience, expertise, etc.)? Understanding is a modus of informing by which the so-called understanding information is coming into existence. If an informational entity (operand) produces understanding as a part of its informing, then this entity by the informing of understanding produces (informs) information which explains or interprets certain informational objects. In this way, understanding as an informationally active component of an informational entity has to observe, investigate, evaluate, clarify, explain, interpret certain informational objects and has to deliver the resulting information of understanding. Nowadays expert system use a kind of proposi-tional or programming logic to handle (operate, connect, relate, overview, etc.) the so-called facts, i.e., believed, implicatively changeable, expertly inputted data, knowledge, rules, etc. In fact, they perform merely as an implicatively organized information support for the living experts or learning personnel, however, cannot be used for crucial decision making in business, management, technology, etc., i.e., as the replacement for intelligent and responsible decision makers. And if so. why should the expert system be not expanded up to a kind of informational expert systems, keeping the existing knowledge base and implicative rules of the classical expert system, but adding some innovative mechanisms of understanding (informational inferring) in the sense of informational arising. How would this widened concept of producing (informing) of expertise improve the performance of existing expert systems? If we accept the possibility of the concept of informationally widened expert system, the following question arises: Which are the elementary faculties we have to add to the classical expert system to achieve an informational expert system? Within this paragraph we shall try to list in short some of the basic properties of an informational system in comparison to a nowadays expert system. And we shall give a short comment on the question how could an electronic dictionary be improved by the use of informational principles to approach the living searcher and user of an electronic dictionary. Let a linguistic (e.g., textual) expert system for some domain of knowledge be given. It means that entities (marked, in general, by é) of this system are, in general, sets of informationally interconnected (interweaved, perplexed) clauses, expressed in a (natural, formal, artificial) language. Now, the following questions can be answered: 0. How does an informational entity è inform in general? 1. How does è inform itself? 2. How is è informed by other entities? 3. How does è inform other entities? 4. How does è counter-inform and is counter-informed? 5. How does è embed new information, i.e., its own counter-information and other information? The answers to these questions constitute the basic as well as a perplexed informational cycle of informing and, in particular, as informing of understanding. The question is the following: Is an informational expert system in the sense of the listed questions at all possible? The answers to the listed questions have to be constructive in the way that they enable the construction (design, implementation) of an informational expert system. Simply, the chosen informational entity è must have the faculties corresponding to questions 0—5. In this case anoüier question arises: whether è must have all these faculties by itself or can they be taken (or be applied) as informational procedures belonging to a common collection of general informational properties (informational tools, principles). This second possibility seems to be quite reasonable. 10. 0. How does an informational expert entity è inform in general? First, let us say how does è inform. In which way does è inform? How does a general mechanism of informing looks like and how can it be used? Entity è informs in the way that it informs and can be informed. It informs in the way that within é information arises, namely: because of informa^ tion already existing in é; because of information appearing outside of è and informationally impacting è\ because of é's own counter-information arising out of é; and because of informational embedding of its own counter-information and outside information. These four informational processes constitute the so-called informational cycle. Informing of information is cyclically spontaneous and spontaneously cyclic. In the informational domain of é, é's informing, counter-informing, and informational embedding arises as informing of information è and as informing of outside information which informationally impacts e. In our case of informational expert system, è is a set of clauses. Entity è informs by memorizing and generating of clauses and by perceiving of clauses as an outside information. Informing of è is nothing else than memorizing and creating of clauses by means of é's informing, counter-informing, and informational embedding, within the cyclically spontaneous informing of entity é. The basic question remains how can the informational mechanism for generation of clauses be informationally structured and organized in the realm of an entity é within an informational expert system. What could be the mechanism of analysis of existing and arising clauses? We shall answer these questions later. Let us suppose that such mechanisms exist and that they analyze existing clauses and synthesize new (arisen) clauses. 10.1. How does an informational expert entity è inform itself? How does an expert entity è inform itself or is informed by itself? Entity é is a set, sequence, or set-sequence of clauses. There can (or must) exist particular clauses (for instance, special formulas) which connect, interweave, or perplex clauses within è informationally. In principle, é is an informational interweaving (a multiplex, perplexity, or similar structure) of clauses. Clauses can take over the operand roles as well as the operator roles. Operator clauses are, for instance, informational programs for analysis and synthesis of clauses, for embedding of synthesized (generated, arisen) clauses and are from other inforinational sources (entities) arriving clauses. In general, è includes clauses which at the given state of è are operator clauses and operand clauses. In another state of è the roles of previous operator clauses and operand clauses can be changed. There can even exist clauses which simultaneously perform as operators and operands, i.e., as operatoroperand clauses. Potentially, each clause of è can perform as the operand clause, operator clause, or operatoroperand clause. A passive clause of è can be treated as an operand clause. Clauses possessing the status of operator clauses operate on clauses possessing the status of operand clauses. The question is how operand-clauses can be chosen by operator clauses for operations upon them. In which way an operator clause can find the argumentation or the cause for operating upon an operand clause, to change it and to generate in a counter-informational way a new clause and to embed a new clause informationally, i.e., to connect it to some other clauses of el The imagined faculty of clauses to be operators and operands of entity è demands a concrete concept, i.e. a real changing and arising of clauses through their particularization and universaliza-tion. 10.2. How is an informational expert entity è informed by other expert entities? Entity è is informed by other information through the arriving information. The question is how information arrives to e or where is the sensitivity of è for the arriving information located. Which partial information of è decides on the acceptability of the arriving information? The answer to these and similar questions is that there exist a general mechanism which qualifies each entity è within an informational expert system for the acceptance of and for the sensitivity against the information »arriving« to è. The question which has to be resolved is what is the nature (structure and organization) of the sensibility mechanism for the arriving information and how this information is processed (informed, counter-informed, and embedded) within è. In fact, there does not exist a substantial difference between the so-called information of è and the arriving information in regard to sensitivity. Entity è has to sense (over a general mechanism) its own information (its informational perplexity of clauses) in a similar manner as it senses the arriving information. The question remains how to chose the arriving information as that which in regard to è is the sufficiently relevant information. On the basis of sensing its own and the arriving information, è synthesizes new clauses. These clauses can be understood to be informed and counter-informed clauses which contents depends on the state of the informational set è and the sensed arriving information. This phase of the synthesis is informational and counter-informational. Now, the synthesized clauses have to be connected (informationally interweaved) with clauses belonging to the informational set è. It means that these clauses become meaningful in the realm of entity é. The act of connection is performed by the so-called operation of embedding which can be constructed as a general, common principle, valid for any type of entity è. It can be conceived that è includes some particular clauses which determine the possibilities of embedding of the arisen counter-information and the arriving information. To these particular, internal embedding clauses a general embedding mechanism (within the informational expert system) is on disposal by which the embedding of arisen and arriving information can be efficiently performed. It is worth to mention that the so-called embedding underlies the general principles of information. Embedding in a particular situation constimte embedding operand-clauses, embedding operator-clauses, and embedding operand-operator-clauses. In this way counter-informing and embedding underlie the general (and hierarchically higher) principle of information. 10.3. How does an informational expert entity è inform other expert entities? It was already described in which way the entity é can inform (also counter-inform and embed). The informational connectedness of è does not concern merely è but also other informational entities of type è. Otherwise, it would be not possible to say that è informs other informational entities by its own intention. It is to understand that the informational connectedness of informational entities (sets of type è) within an informational expert system is mutually perplexed. Thus, a concrete entity è can decide to which entities its informing and by its informing produced information will become accessible or to which entities such information will be mediated. Thus, in this sense, it is possible to say that entity è informs other entities within an expert system. To inform other entities can mean simultaneously to produce information intentionally for itself and for other entities in question. Informing is the synonym for informing, counter-informing, and embedding of information. Informing can mean that, for instance, the existing information keeps its form and new clauses are generated; parts of existing information are modified, changed, canceled and on this basis new information arises, etc. As mentioned before, this principle of informational arising is effective in informing, counter-informing, and embedding of information. Thus, it is necessary to analyze the possibilities of informing concerning counter-informing as well as the counter-informing following phase called embedding of information arisen by counter-informing. 10.4. How does an informational expert entity è counter-inform and how is it counter-informed? What kind of informational mechanism is needed for the implementation of counter-informing within an informational expert system? By definition, counter-informing is an unforeseeable process of informing. How could the unpredictability of counter-informing as the generating of new, not ultimately in advance determined clauses of entity è be constructively implemented? Probably, several generating mechanisms for this purpose can be chosen, applying the methods of random construction of clauses from given clauses and random choice of various possibilities. Evidently, the mechanism of counter-informing within an informational expert system could determine the quality (intelligence, diversity) of the system's inference mechanism. The unpredictability of counter-informing can depend substantially on the unpredictability of arriving information. This information can cause the generation of e's clauses which in no way could be determined in advance. In this way the arisen clauses are the consequence of system's »understanding« of instantaneous situation. In this point of the problem, it becomes obvious how understanding of an informational expert system is the informational problem par excellence. Generated clauses are not only operand-clauses; they can be operator-clauses or operand-operator-clauses, as well. By counter-informing, system acquires not only new data but also new functionality. On the other side, entity è is counter-informed only to the extend by which the arisen counter-information and the arriving information can be embedded into è. Prior to embedding of information, this information does not reach the so-called »horizon« of understanding of è. It is, for instance, clear that è counter-informs, however, it must become evidently clear how entity è is counter-informed. 10.5. How does an informational expert entity è embed information? Informational embedding reflects in the most direct form the »understanding« of the existing informational expert system. New information— the arisen and the arriving one—has to be connected to the existing (given, source) information, so the new information can be understood by information which already exists in the system. Understanding means nothing else than informational connectedness of new information with the existing information. If this connectedness is weak, understanding of new information by existing information can be faulty or deficient. This does not mean that the deficiency in the process of informational embedding will not be reduced or sup- pressed. Embedding of information occurs by means of specific and general clauses of an informational expert system. Specific clauses belong to the entity è in question while general clauses for embedding are principles of the expert system as a whole. The set of embedding »rules« is variable; it is a consequence of the instantaneous state of the expert system. Embedding is not an informational exception and it underlies the general principles of information. The product of embedding is the so-called embedding information which determines the connectedness of some informational parts (clauses) with other informati nal parts (clauses). 10.6. What is the nature of embedding information into an informational expert entity è? The embedding information is the product of informational embedding and concerns the arisen or arrived information on the one side and the existing information of è and other informational entities on the other side. The embedding information is a specific information of clausal connectedness within è and outside of e. This information can be passive as well as active, i.e., can have the form of operand clause as well as operator clause or operand-operator clause. It is clear that the embedding information can connect as well as disconnect certain information. Disconnection means not only the annulling of certain embedding clauses but also their changing. Embedding of information has to be understood as informational connecting and discormecting of information by means of embedding information. In this regard, the embedding information by itself can be connected and disconnected to some extent. Embedding information performs as regular information and underlies the general principles of information. 10.7. What is a complete informational cycle of an informational expert entity e? In an informational expert system, the so-called informational cycle is the basic principle on all levels of the system performance. Under a complete informational cycle of an entity è the process of informing, counter-informing, and embedding of information is understood, being closed into an open circle or loop of itemized components of informing. The immediate question of this formula is which are the informational levels of an informational expert system within which informational cycles occur. The lowest informational level is the domain of a clause representing the facts of an application. The fact-clause è is the most elementary informational entity within the system. Thus, a clause è informs, counter-informs, and embeds information by its open cycle, producing information, counter-information, and embedding information. The ftmction of the informational cycle is performed by è as informational entity and by means of system's general informational principles being in common for all entities of the system. In this case, the general informational principles have to be understood as informational procedures which functionality or ability of informational performance is memorized within the system. These principles perform as regular information, i.e., as clauses (operands, operators, operandsoperators). In each concrete state of the system, clauses, i.e. e-s, principles, etc. can be changed accordingly to the instantaneous simation. A higher informational level is the domain of clauses which connect clauses as facts. Within the domain of connective clauses several categories can be distinguished. The first category are clauses which belong to the so-called »classical« rules of inference (for instance, an if-then statement, implication, or modus ponens) which cormect the clauses representing facts of an application. These rules belong to the techniques of classical expert systems and can be preserved under specific conditions also within the informational expert systems. For these ca:tegory of connective clauses their ultimate dependence on the facmal simation or application is evident. These primitive forms of inference are applied in an informationally circular manner. The second category of connective clauses belong to the class of the so-called modi infor-mationis (IL-IV). An informational expert system can use in an informationally mechanic way the following informational modi: modus ponens, modus tollens, modus recms, modus obliquus, modus procedendi, modus operandi, modus vivendi, modus possibilitatis, modus necessitatis, etc. which are nothing else than rules of informational inference. Certainly, these rules are application dependent, however, they preserve certain general principled properties of informational arising. Within an informational cycle, different modi in-formationis can be applied. The third category of connective clauses are semantic clauses determining semantic relations among clauses. These clauses serve as operand-clauses and are used in the processing of clauses by various »rules« of inference. The highest group of clauses used within an informational cycle are informational principles on the system level being responsible for the informational nature of the discussed clauses of the informational expert system. This principles-clauses are active on all levels of the expert system as mechanisms of various informational cycles. The hierarchy of informational cycles is determined by the rank of rules: the primitive, higher, and the highest ones. Beside of the hierarchy within an informational cycle there exist parallel and perplexed cycles (loops or subcycles). Thus, the parallelism of cycles within a cycle is the most powerful way of informing within an informational expert system. satisfied with the meaning obtained and constructed as a result of searching in a dictionary. In fact, the definite meaning of a term does not exist, for meaning is a regular information and it arises through informing, counter-informing, and embedding of the available and the individually arisen information. The informational availability depends not only on information included in a dictionary, but also on the needs, circumstances, and at last but not least on a searcher's metaphysical orientation. This facts point to the belief that an electronic dictionary has to be organized as a dedicated informational expert system and not only as a classical expert system which is based predominantly (or even solely) on formal implicative logic and on (solely) traditional algorithmic procedures. The use of an electronic dictionary is evidently not a mere routine operation, by which a user would be capable to find one or whichever of the possible meaning of the searched item. Such strategy of searching would not call for the ambitious development of highly automatized dictionary without some of informational principles of understanding in mind. 10.8. An informational electronic dictionary 11. Misunderstanding as Information How could the search in an electronic dictionary be improved by the use of the discussed informational principles? What is the spontaneity and the circularity of search in a dictionary? What is the difference in quality of meaning or understanding of a searched notion in a dictionary? The question we ask ourselves is how do we search for a meaning of a given term in an integrated, for instance, a multilingual dictionary (set of different dictionaries). Why we can obtain different or less or more exhaustive meanings of selected terms as the consequence of searching by different persons? Does an ultimate meaning of a term exist at all or can the understanding of a term be developed ad infinitum? Necessarily, a dictionary does not mean a finite domain within which a term could be understood semantically and pragmatically to a definite extent. The meaning of a term depends on the intensity, intention, and kind of the act of understanding and on the decision of the searcher that he/she is ... The organism creates the disease to recover itself. ... G. Canguilhem (NP) 20 There could be said: the understanding creates the misunderstanding to understand itself. Or more precisely: understanding as information counter-informs misunderstanding to embed it informa-tionally into understanding. What is the informational difference between understanding and misunderstanding as information? From the informational point of view of understanding, misunderstanding means another, informationally irrelevant or noisy form of understanding. To confront understanding and misunderstanding of a given informational entity means to investigate and evaluate the informational difference between understanding as information and misunderstanding as information. As we can comprehend, there does not exist a reliable general principle for distinguishing the essence of understanding and misunderstanding of a concrete informational entity. We have already recognized how the so-called breakdowns can interrupt informational cycles of a misunderstanding (an informational blindness), beginning a new course or cycle of informational arising within the cycle of »correct« understanding. However, a given understanding can arise more and more into a form of misunderstanding and this course of informational development can be broken down every now and again. Understanding and misunderstanding of an informational entity can be two different informational processes arising around the same informational subject (information in question). They treat this informational subject differently, so, through the so-called breakdowns of understanding and misimderstanding, respectively, they can change from one form into another. Beside of this general principle of understanding there can exist forms of understanding which can be marked according to the social normativeness as disorders of understanding. In this case, disorder of understanding can mean a certain degree of misimderstanding and non-understanding. Understanding and misunderstanding are two different views of a given information, which can have contradictory or semantically and pragmatically non-overlapping opinions, truths, beliefs, ahd/or comprehensions of information in question. Or, they do not have essential common, ageeable informational items concerning the informational entity in question. Also, understanding and misunderstanding usually disagree in the importance of informational arguments by which an informational entity will be evaluated, investigated, and/or comprehensively demonstrated. It is simply informationally impossible to lead understanding and misunderstanding to a common realistic or rational interrelation and senseful comparison, if they have too divergent, incomparable, and informationally strange, incompatible, inconsistent, and mutually unreliable namre. To understand or to misunderstand requires and demands the intention to be understood or to be misunderstood, respectively. Understanding and misunderstanding are two informational poles of the same informational capability concerning the informational arising of understanding and misunderstanding as information. Understanding can be treated as misunderstanding and vice versa from the point of view of information which understands or misunderstands a certain information. If understanding concerns opinion, truth, belief and comprehension, misunderstanding concerns counter-opinion, untruth, counter-belief, and counter- comprehension. Thus, misunderstanding can be understood as a kind of understanding's counter-information, which to some extent can be or can to some extent not be informationally embedded into the existing understanding of information. Living information is always on the way to understanding and misunderstanding simultaneously, for only a kind of contradiction enables the development and the actuality of the existing understanding and misimderstanding of some information. Thus, both understanding and misunderstanding perform as regular information and interact informationally in their own, however, mutually impacted informational manner. It may simply be said that neither understanding nor misunderstanding can have the finite opinion, truth, belief, comprehension, rationality, etc. tenanted, for these are only instantaneous informational items of relevance within an arising understanding and misunderstanding. 12. Disorders of Understanding ... Viewed semantically, the pathologic against the normal is marked not so much as by a. or dis as by hiper or hipo, respectively. Also, if we keep within an ontologie theory its calming confidence in the possibility to overcome an illness [disorder] technically, we are still very far apart from the thought that health and illness could be qualitative op-posites, struggling powers. ... G. Canguilhem (NP) 22" In its broadest sense, a being's understanding is conditioned and impacted by the instantaneous state of its autopoietic system and particularly by the instantaneous state of its neural system. In medical sense, disorder is an alteration of the function or strucmre of an organ or the body as a whole. Understanding as information can be impacted by various kinds of disorder causing disorders of understanding. Disorders of understanding can occur in forms of cultural information processes (for instance, as indoctrination, totalitarian ideology, individual cynicism, philosophic teachings, scientific theories, etc.) as well as in forms of »pathologic« processes (ilhiess, mental disorders, insanity). For instance, a rigid ideology can be understood as communicated insanity or a shared delusion, which is unable to understand the wrongfulness of conduct. Informationally, disorders of understanding in living beings occur also as consequences of various disorders, for instance, as acute brain, affective, aggressive behavior, conduct, dissociative, gnostic, histrionic personality, impulse, motility, neurotic, paranoid, psychosomatic, schizophrenic spectrum, speech, stress, thought, XXX disorder, etc. In these cases, disorders of understanding are the consequence of »pathologic« states, conditions, defects, abnormalities, particularities, etc. Acute brain disorder is an organic mental disorder which is reversible, such as toxic-infections delirium. This disorder can impact the functioning of brain parts responsible for the degree of human understanding. Any disorder typified primarily by disturbances of mood, including the manic-depressive psychosis and the neurotic-depressive disorder is called affective disorder. Aggressive behavior disorder is the label for a group of conduct disturbances in children, characterized by repetitive and consistent antisocial activities. Dissociative disorder is any of the syndromes whose central feature is sudden, temporary alternation in consciousness or identity (multiple personality and depersonalization). A group of disorders involving abnormalities of perception or recognition is called gnostic disorders. These are abnormalities of associative thinking such as may be observed in schizophrenia, to disturbances in cortical functioning as seen in some types of Broca's or syntactical aphasia, and to deep, epicritic sensation in contradiction to protopathic sensation disturbances. Histrionic or hysterical personality disorder is characterized by egocentricity, attention-seeking behavior, suggestibility, overdramatization, sexually provocative behavior, proneness to easy disappointment, and emotional lability. Impulse disorder is characterized by ego syn-tonicity, a pleasurable component, minimal distortion of the original id impulse, and some degree of lack of control (pathologic gambling, kleptomania, pyromania, and other acts of destruc-tibility). Motility disorder is an abnormality of movement, particularly the abnormal postures and gestures displayed in catatonic schizophrenia and in pervasive developmental disorders. Neurotic disorder (neurosis) is any of functional disorders of behavior caused by excessive anxiety or by behavior distorted by an exaggerated use of avoidance behaviors. In psychoanalysis, neurosis is the symptomatic expression of conflict between the id's sexual and aggressive impulses and the ego's need to cope with and adapt to reality. Paranoid disorder (paranoidism) is a condition that is similar to paranoia (also called intellectual monomania) which comes from the Greek paranoein and means to think amiss or wrongly. Paranoia is a gradually developing delusional state or fixed delusional system with preservation of intelligence and orderly thinking. Most commonly the delusions are persecutory in nature, although they may also be of grandiose, religious, ideologic, erotomanical content, etc. Psychosomatic disorder concerns structural, physiologic, or other organic changes in one or more body systems, whose origin, at least in part, is related to emotional factors. Schizophrenic spectrum disorder (schizoidia) is a range of character and behavioral disorders that may be related genetically to schizophrenia. These disorders may include impulsive crimes, social isolation, alcohol abuse, eccentric reclusiveness, suspiciousness, jealousy, litigious-ness, fanaticism, opinionated and narrow-minded pedantry, haughtiness, and unsociability. Speech disorder means difficulty in producing the sounds of spoken language; it may occur as a developmental condition or as a result of various acquired neurologic disorders. Stress disorder means transient situational personality disorder. Post-traumatic stress disorder is associated with serious traumatic events. Classic symptoms are re-experiencing the trauma in dreams, recurrent images and thoughts, a general sense of numbness and feelings of lack of involve- ment with the real world, etc. Thought disorder is understood to be any abnormality in the process of thinking or a disturbance seen in schizophrenia characterized by blocking of thought, thought deprivation, poverty of thought, or haphazard associations. A good example of this type of disorder is, for instance, a totalitarian ideology. XXX disorder is a case of the so-called chromosomal disorder causing mental deficiency of subjects. Let us step into similar kinds of abnormal understanding from the point of view which is offered by some principles of neural science (PNS). It is evident that informational principles are in commonsensical accordance with some principles of neural science and vice versa. In many respects, informational phenomenology is becoming inevitable in neural research, in explaining and interpreting the processes of mind. Let us overview in short localization of higher functions and the disorders concerning the higher cortical functions relating language, thought, and affect. Hemispheric brain asymmetries and the cortical localization of higher cognitive and affective functions seems to be relevant in the process of human imderstanding. The two hemispheres are not fully symmetrical and differ in their capabilities. Split-brain experiments reveal important asymmetries and show that consciousness and self-awareness are not unitary. What functional advantages, if any, does lateralization confer? Anatomical asymmetry of the brain has been demonstrated in other animals and there are interesting sex differences in hemispheric dominance. To some extent, even the most complex functions of the brain can be topographically localized. This is important in explaining syndromes, disorders, and diseases in specific regions and, certainly, information phenomena in the nervous system. The next important questions within human understanding are natoral language, disorders of language, and other localizable disorders of cognitive functioning. All human languages share four distinct feamres: creativity, strucmring, meaningfulness, and interpersonal impact. The arising of human language originates in evolution of the brain, thus, the capability for human language is thought to be an innate cognitive skill as well as learned. Further, aphasias are disorders of human language that also interfere with other cognitive processing (informing). For instance, the aphasias can be understood on the basis of the Wernicke-Geschwind model of language. Aprosodias are disorders of the melodic intonation of language and its perception. Some disorders of reading and writing (alexias, agraphias, dyslexia, hyperlexia) can also be accounted for by the Wer-nicke-Geschwind model. Disorders of thought can be thought (classified) as the schizophrenic syndromes. There is an important genetic (molecular-informational) component to schizophrenia. Disorders of feeling are (information) processes classified as affective diseases (depression, mania). These disorders suggest a defect in thè hypothalamus and a strong genetic predisposition, for instance, for major depression. A biogenic amine hypothesis of depression has been proposed and there are disordered neuroendocrine functions in depression. Disorders appearing in human mind and/or human bram can substantially impact the so-called human understanding (social models of behavior) and influence the understanding arising in human communication. 13. Understanding as Information in Natural Languages, Sciences, and Cultures What does understanding as information mean within the domain of a namral language, science, and culmre? The trivial answer would be that understanding in namral language concerns the culmral environment in which a natural language arises in the form of discourse from its historical roots and in the everyday use. Science as a cultural form is impacted by semiotic capabilities of a natoral language as well as cultore of thought and labor. If language is embedded in cultoral information as a special, communicative means, science as an informational form is embedded in natoral language and from this language deduced formal language of the science in question. Thus understanding as information depends cultorally, linguistically, and scientifically. Cultural forms of information are, for instance, philosophy, art, history, technology, but also language and science (IDI, ID2). In this respect several natural languages, sciences, and culmres are informational phenomena which are informationally interconnected and perplexed and they constimte the culmral behavior and the mentality (truths, beliefs, styles of life) of individuals and populations through time within which this informational forms will be understood. any other information with information-owing capability of informing, counter-informing, and embedding of information. As we shall see, the formal-theoretic treatise of understanding as information will reveal and brighten the perspective of understanding as a horizon of possibilities being relevant for philosophy of understanding as well as for the design of understanding artifacts. References 14. Conclusion of Part One In this part of essay we have set the background of understanding as information from various aspects of information: philosophic, linguistic, neural, comprehensional, and informational. This cultural and individual background can now be used for the construction of a formal informational theory of understanding which from this philosophical basis can be axiomatized, deduced, and induced in an informationally formal (logical) way. Thus, in Part Two, we shall show this way of formalization by a special, informational logic of understanding, which will embrace the fundamental concepts of information (informing, counter-informing, and embedding), i.e. informational principles (POI), as well as the most complex informational forms of understanding. We have seen how understanding as information can be built up as the most complex and also intelligent information. For this reason particular, i.e., intelligent informational forn* j has to be determined. The basic formalistic concept of describing intelligent informational entities was shown schematically in (IPF), for instance. The form of an intelligent process was an information-ally perplexed and recursive formula or system of formulas. Thus, it will be possible to show some particular cases of parallel-cyclic scenarios of understanding, from the basic informational level to the most perplexed one. We have recognized how understanding as information can be constructed as a complex informational entity, as an informational process delivering information as understanding which concerns other informational entities and also understanding as information itself. In this way, understanding performs informationally regular as (MP) Aristotle, Metaphysics, The University of Michigan Press, Ann Arbor, Mi (1985). (PH) Gadamer, H.-G., Philosophical Her-meneutics, University of California Press, Berkeley, Ca (1976). (NP) Canguilhem, G., The Normal and the Pathologic (in Slovene), Studia Humanitatis, Ljubljana (1987). (BT) Heidegger, M., Being and Time, Harper & Row, New York (1962). (SZ) Heidegger, M., Sein und Zeit, Max Niemeyer Veriag, Tübingen (1986). (PNS) Kandel, E.R. and J.H. Schwartz, Principles of Neural Science (Second Edition), Elsevier Science P.C., New York (1985). (POI) Železnikar, Principles of Information. Cybemetica 31 (1988) 2, 99-122. (IDI) Železnikar, A.P., Information Determinations!, Cybemetica 31 (1988)5, 181-213. (ID2) Železnikar, A.P., Information Determination II, Cybemetica 32 (1989) I, 5-44. (IL-IV) Železnikar, A. P., Informational Logic IV, Informatica 13 (1989) 2, 6-23. (IPF) Železnikar A.P., Informational Principles and Formalization (in Slovene), Informatica 13 (1989)5,21-40. DESIGN OF HARDWARE WITH PROGRAMMABLE GATE ARRAYS Keywords: SI-2000, Programmable Gate Arrays, Group Switch Module, Hardware Deisgn Peter Praprotnik Iskra TELEKOM Bogdan Dugonik Tehniška Fakulteta Maribor Abstract: This application shows how pure hardware problems can be solved with modern software tools. There was a need in Iskra Telekom for the new Group Switch module for SI2000 digital telephone exchange. Because of the complexity and the number of functions the module has to provide, there was not enough room on the board for standard hardware components, so we decided to use Programmable Gate Arrays (PGA).The most interesting in this application is the direct hardware dependence on the software. In this paper some solutions are given. In' the case of using PGAs, the main problem is the development of programs. The complete development of contents, simulation, real time simulation and verification is made by 'using special software on fast Personal Computers or even better on a Sun. With such tools it is possible to manage one PGA in three or four weeks in the laboratory without involving big manufacturers of electronic components. The main advantage of PGA is that you just download anothar program in it and you already get different hardware on the board without changing any piece of the hardware. Another advantage is that this can be done during operation of the target system. It is obvious that such software development of hardware design will be applied more often in the future. Introduction There was a need to improve one part in the hardware of the SI 2000 digital telephone exchange. The old Group Switch Module which switched 32 subscriber modules has to be reorganized. Each of this modules handles up to 240 end users. Our new Group Switch Module can now manage four times more subscriber (analog or digital) modules with much better time characteristic. Our problem was to replace approximately 160 SSI and MSI chips on the old circuit board with Gate Arrays or with the full custom application specific IC without increasing production costs. At the end of the cost analysis, it was found out, that our problem could be solved only by using Programmable Gate Arrays. SSI (Synchronization, Switch and Interface) is one of the centralized modules in the SI-2000 Digital Switching System and it is the Nćsrt of the Group Switch Unit, that is capable to handle 128 subscriber modules.. SSI provides some vital functions (i.e. connections between modules and channel switching) necessary for the operation of the whole system. Because of the importance of these functions the reliability of thf- modulp has to be high. It is achieved by duplication of the vital functions, where failure would cause the fall of the- whole system. It is possible to connect MLI (Module, Link and Interface) units on each SSI module. The module is performed with the standard HC-HCT MOS chips as well as with PALs and PGAs. The whole contents of the module is equivalent to 165 sixteen pin chips. Il POMCR COMrmL ^ MflS^W ALARMS CPU 1NI£R- FACC in: TIME SVITCH tf n jt SWITCH LINKS Fig.l. SI-2000 Group Switch module. Fig.2. Synchronization, Switch and Interface module. The standard SSI/MSI devices offer less density and consume more power than devices used in our design. They are usually manufactured in technologies with limited opportunity for further cost reductions. The PGA device, mentioned in our design, is a user programmable gate array that provides the same density and relatively short development times as gate arrays do. The PGA device combines the design and production benefits of a standard logic device with the system benefits, such as increased reliability, power savings, space savings and lower production costs, depending on whether SSI/MSI standard logic or ASIC device is used. The ii rch i tue Lure of the PGA consists of an interior matrix of configurable logic blocks, user programmable interconnections, and I/O blocks which are partioned at the edge of the chip. The interconnections are located in channels between the rows and columns of configurable logic blocks and I/O blocks. Fig.3 shows the block diagram of the interior organization of the PGA. coHricuiiaiLC ucic Biocts CZl CZD D □ □ □ [ZZI CZ! CZD IZZl • IMItilClKllECITIlllS «Rt« Fig.3. Inside organization of the Programmable Gate Array. The PGA performance depends on the fixed delays of the logic and storage elements plus the interconnections delays. Each PGA device is identical until it is loaded with its specification. Our configuration bit stream is loaded automatically from a serial PROM when the power goes on. If the power goes down, the PGA loses the configuration. We require very high device density for SSI module. This means we have to put the devices very close together. We have packed our three PGA devices close together with no effect on the thermal coefficient for the expansion of the silicon. The development support for the PGA device includes the complete software aided design entry, analysis, and verification. The development system also offers the complete basic configuration. Further activities to complete a PGA design include: schematic entry (supported with PGA library which includes common logic functions, 7400 series parts, latches,..), simulation, automatic placement and routing or automatic design implementation, timing calculations, and design optimization. The last stage in the design cycle is the in-circuit emulation. Design cycle Array is a CAD environment which enables a good application backup. Our decision was the software package OrCad that supports complex tasks to entry , to simulate and to test of the design. ORCAD/SDT is a drawing program which allows the designer to work faster with less chance of errors. It is not the simplest drawing program, but it manipulates with fully integrated software, found in the workstations. The program also supports a large library with components of standard elements, microprocessor series, TTLs, CMOS and for our requirements, very important LCA ( LOA is an older term, PGA is a new one) libraries, series 2000 and 3000. We have made our own component library. This has two advantages. Firstly, when looking for a component it can be found very quickly. The second advantage is that the memory not occupied by unnecessary library parts. If you wish to design a chip using 3000 series PGA family, you should have up to 8 MB of system memory. The most important fact is the modular way of designing. Every designer has his own favorite circuit designs being optimized by experience. The designs, made independent from each other, can be fetched from previously drawn circuits and placed into present design without any modification. In our case, a design team has worked closely together, but each designer made his own part of the design, independent from each other. At the end, the designs are put together in d moduldz* wdy« Th6 or^dnxzd^ion of our worksheets is made hierarchically. Designing in this modular way means that at the end every part of the design can be put into the present design without modifications. The utility automatically annotates the old components. The hierarchical option is chosen instead of the single sheet drawing option to avoid the problems, "appearing during the printing of the massive drawing. Our first design is a part of a Synchronization, Switch and Interface module previously presented and shown in Fig.2 . The top level screen shows multiple sheets connected together (Fig.4). The key to providing support for engineers who wish to develop a complex Programmable Gate Fig.4. Complex drawing handled by partitioning in OrCad. It presents the following five part designs: Round Robin, Alarm Control, Switch Control, Coraraunication Control and LCA3 Control. The design, involved into the first hierarchical level is too complex to stay in one sheet. .To cope with the complexity we have put our five designs into several, part sheets at the second hierarchical level. Each of this designs is shown in Fig 5. Fig.5, Detailed view of one of the five designs, globally presented in Fig.4. As soon as the circuit is drawn, a complete part list with the list of component type, with the quantity name and the references is generated. Another command produces a list which describes every part of the diagram with all its connections to other pins. With by this command, all the interconnections in our designs are checked. Next we checked the electrical conditions. It is done by the Electrical Rules Checker. It gives us information about each pin of the part and it is used to verify if that connections conform with the electrical conditions allowed for the specific pin. For example, a bus may not be connected to a pin or two pins may not be connected together, if both of these pins are defined as output pins. Once the designer has finished his design using the Schematic Design Tools, the design file has to be translated to the format, that is compatible with simulator and PGA design editors input. The format itself is the standard ASCII file and is called Netlist. Before the translation begins the software again automatically tests the schematic file on electrical and schematic errors. The Netlist File can also be used as the standard input for other software packages as PCB layout or Standard Cells design. For the simulation it is necessary that designer creates the stimulus for the circuit as well as the trace file where the results of the simulation are captured. The first step of simulation procedure is the functional or the logical simulation of the circuit. This type of the simulation is used primary for the logical verification of our design, which can be easily corrected by Schematic Design Software if a logical error is found. Of course if this is the case, the corrected design has to be translated again back to the Netlist, so that the simulation of the revised circuit can start again. This loop proceeds until designer is satisfied with the function of the project. Before the second step of the simulation the final placement of our design into the Programmable Gate Array structure has to be done. The first stage is the translation from an error free Netlist File to PGA file. The translation from Netlist to PGA actually performs two operations: the logic reduction and the logic partitioning. The logic reduction is the process of deleting unused logic from a design, permitting liberal use of the macro library, without any penalty when all the functions within a macro are not used. The remaining logic is automatically partitioned into fragments that can be implemented inside individual Input Output Blocks and Configurable Logic Blocks of the PGA structure. The.result is a file defined in terms of the lOB's and CLB's. This is already an actual placement of our design, however it is not convenient for use, because the placement is not optimal and connections between the blocks are not realized yet. Each CLB and lOB of the design is placed by assigning it to one of the discrete blocks within an PGA and ia routed by specifying the programmable interconnect paths used to implement the connections between blocks. Since both logic blocks- and programmable interconnection paths include .signal delays, placement and routing choices have a major effect on the performance of the resulting implementation. It is possible to perform placement and routing interactively with the graphic based design editor, with software tool called ADI for Automatic Design Implementation or with any combination of the two. The ADI determines the best placement for the design and then routes the nets that interconnect the blocs. An optimum placement of a design results in the shortest and the fastest interconnects with minimum possible delay. To achieve this ' ADI uses combination of two algorithms. Using a min-cut algorithm ADI places each block in its most desirable region of the die, then the simulated annealing algorithm completes the final placement of the block into its most near optimal location. Another possibility to perform the placement is the graphic based design editor called Xact, which can be used interactively to edit, enter, place and route PGA designs. With the Xact design editor a user can manipulate the graphic view of the internal PGA resources directly defining the functions of CLB's and lOB's, their position in the matrix and specifying their interconnections. More commonly both ADI and XACT design editor are used together to complete an PGA design. For most designs ADI will route all the nets in the design satisfactorily, however some designs, particularly those that use most of the internal capacity of the PGA may require completion of the routing by using interactive design editor. Xact design editor might also be used additionally to optimize critical timing paths. It is also possible to route critical portion of the design with Xact editor initially and then use ADI to complete the placement and routing of the rest of the design. When the place and route procedure is finished, the second step of the simulation can begin. This is the final simulation and considers the real time delay caused by placed blocks and theirs interconnections in the PGA. At this point the worst case time analysis can be done and in case of violation of the timing, the designer can improve the timing by changing the placement and interconnect paths with Xact editor, until the timing is satisfactorily. The costa of producing a new SSI module comparing to the old one, increased for about 6000 DEM per board. If we consider the SSI module ability to switch 128 subscriber moduls with much better time consideration, higher system security, lower power consumption, we realize that the costs for development of the new circuit can be amortized in production volumes over 270 SSI circuit boards per year. If the production exceeds the number of 1000 modules , we think we have done a good job. After completion of the final simulation Design Rules Checker program is used to check for illegal configurations, such as interconnect networks with multiple sources. Another utility then generates the binary configuration program, that can be downloaded into the PGA, EPROM or serial PROM. One major advantage of a user programmable, standard logic device such as the PGA is the ability to test the design immediately in the target application. In circuit debugging can be accomplished with in circuit verification tools such as various emulators or by programming an actual PGA device directly in the target hardware. Alternatively, the designer may debug hardware by using traditional test equipment, such as logic analysers and oscilloscopes. To estimate if a design will fit into a given PGA, the number of I/O pins, registers and the amount of logic used for the design should first be estimated, and these requirements should be matched to the number of lOB's and CLB's in the PGA respectively. Of course it should not be expected that all lOB's and CLB's of a given PGA can be utilized without some effort during placement and routing. The amount of PGA resources that can be used is dependent on the nature of the design, for example fully synchronous, logic intensive designs with low I/O intensity are the easiest to implement. References: /1/ Fawcett B.:'User-programmable gate arrays: design methodology and development systems' Microprocessors and microsystems (5 June, 1989) /2/ The programmable gate arrays data book AMD (1989/90) /3/ B. Dugonik, P. Praprotnik: "Using Software Tools for modern Hardware design", Aplied Informatics '90, Insbruck (1990). Conclusion The task was finished in six weeks. As soon we have begun with the designing on PGAs, another team of the designers started with the designing of the new printed circuit board. The verification and the test on the new board have taken us three months respectivetily on some modifications. CIRCUIT BOARD UITH PGA CIRCUIT BOBRD VITH SSI/KSI 3oe piaaes Fig.6. The approximate cost analysis for SSI board. TRANSPUTERJI V SISTEMIH ZA DELO V REALNEM ČASU Keywords: real-time systems, embedded microcomputer systems, multitasking, parallel processing, transputer, Occam Peter Kolbezen Institut Jožef Stefan, Ljubljana Peter Zaveršek Gorenje Servis, T. Velenje POVZETEK, članek opisuje lastnosti in nekatere koncepte krmiljenja sistemov z računalnikom za delo v realnem času. Obravnava jih z vidika strojne in programske opreme. V takine sisteme uvaja Inmosov transputer in programski jezik occam kot učinkovito metodo uporabe mikroprocesorja napram klasičnim mikroprocesorsko zasnovanim sistemom za delo v realnem času.'Uporaba occama podpira izvajanje več opravil hkrati na dveh nivojih in porazdeljevainje časa na nizkem nivoju. Komunikacijski mehanizmi med asinhronimi occamovimi procesi morajo biti ustrezno prirejeni za procesiranje sinhroniziranih procesov v realnem času. Prispevek preučuje lastnosti strojne in programske opreme transputersko zasnovanih sistemov. Pokaže jih na primerih zametka takšnega sistema. TRANSPUTERS FOR EMBEDDED REAL-TIME SYSTEMS. This paper describes the chaiac-teristcs and any control concepts of embeded real-time systems. It discusses the characteristcs and concepts in view of hardware and software. Further, the paper intrpduces the Inmos transputer and the programming language occ£im as a viable alternative to coventional methods of implementing microprocessors-based real-time systems. The present occam implementations support multitasking on two levels and time sharing on the low level. The communication mechanism between asynchronous occams processes must be matched with real-time event synchronized task processing. The hardware and software characteristics typically involved are assesed and these characteristcs are shown on the beginning of the such computer system. l.UVOD Krmiljenje procesov je najbolj pogosta uporaba mikroprocesorsko zasnovanih sistemov za delo v realnem času (RT- sistemov). Mikroprocesor, ki je vključen v takšen sistem, nadzoruje neke stalne zunanje aktivnosti. Strojna in programska oprema sta navadno specifični in odvisni od namembnosti sistema. Najvidnejša značilnost RT-sistema je dovolj hitro procesiranje podatkov, ki vstopajo v sistem naključno, in s tem pravočasno odzivaiye sistema na okolje, kar zagotovlja pravilno delovanje celotnega sistema. V našem prispevku bomo govorili o "sistemu za delo v realnem času", če bo izpolnjeval naslednja dva pogoja: 1. Vrstni red izvajanja opravil (računanja) je funkcija časa izvajanja ali je funkcija podatkov, ki prihajajo v računalnik (naključno) od nekih zunanjih dogodkov; 2. Rezultati delnih izračunov so lahko odvisni od vrednosti spremenljivke časa, ki jo zahteva izračun, ali od časa, ko se izvajanje prične. Tako definirane sisteme je mogoče po klasifikaciji Civera /1/ razdeliti v natanko dve kategoriji: 1. V prvo kategorijo se uvrščajo sistemi, ki • norajo imeti srednji čas izvajanja opravila - merjen preko določenega časovnega intervala - manjši od dovoljenega maksimuma. 2. V drugo kategorijo se uvrščajo sistemi, pri katerih mora biti izvajanje opravila v vsakem primeru (tudi ob nepredvidenih dogodkih) dokončano pred dovoljenim časovnim maksimu- Pri RT-sistemih se torej srečujemo z zahtevami kritičnega odzivnega časa. Zato mora imeti sistemska programska oprema večprocesno strukturo, ki omogoča, da se lahko vsak proces kot progrjimska enota izvaja sočasno z drugimi procesi. Ti procesi imajo časovne omejitve in morajo običajno pri izvajanju neke namenske sistemske funkcije med seboj komunicirati in sinhronizirati svoje aktivnosti. Pualelno izvajanje procesov je lahko izvedeno s prepletanjem sestavljenih procesov na določenih časovnih intervalih (interleaving). Pri tem je uporabljen en sam procesor, ki s prepletanjem posameznih procesov ustvarja t.im. kvazi paraleli-zem. Tako tečejo RT-progranù le navidezno vzporedno, v tako imenovanem večopravilnem načinu (multi-tasking). Prepletajoče procese predstavljajo običajni sekvenčni programi, ki so med izvajanjem večkrat prekinjeni, da se lahko "sočasno" izvajajo tudi drugi programi. V primerjavi z običajnimi večopravilnimi programi pa vrstni red izvajanja RT-programov ni vnaprej določen. Določen je z zunanjimi signali, ki vstopajo v sistem naključno. V tistih segmentih programa, pri katerih se pričakuje zunanjo zahtevo po prekinitvi, sinhronizacija med opravili ni dopustna. Stvarni paralelizem omogoča le večprocesorski sistem, pri katerem se izvajajo posamezni procesi ločeno, vendar sočasno, vsak na svojem procesorju. Večina RT-sistemov vsebuje tudi dele opreme, ki ne dela v realnem času. To dejstvo ima določeno prednost, saj sta načrtovanje in implementacija programske opreme takšnih delov preprostejša. Obravnava strojne in programske opreme mikroprocesorsko zasnovanih sistemov v realnem času bo pokazana na primerih zametka signalno informacijskega in nadzornega sistema za hotelsko službo in preskrbo. Sistem in metodologija načrtovanja sta zasnovana na Inmosovem transputerju in transputerskem konkurenčnem programskem jeziku occam. Namen tega prispevka je, da se na primeru omenjenega zametka pokaže, kako je obravnavana metodologija tako sestavljene opreme (transputer in occam) napram klasičnim metodologijam praktično uporabna in učinkovita, 2. Transputer in strojna oprema RT-sistema Transputer je visoko zmogljiv računalnik na eni sami LSI-enoti; sestavljajo ga mikroprocesor, pomnilnik, štiri polno dupleksirane vhodno/izhodne zanke za povezovanje s perifernimi napravami in priključki za povezovanje z drugimi transputerji. *nalyM.< I CVackln- * STREZM SISTEMA ĆASOVNIKI NOTRANJI RAM VMESNIK ZUNANJEGA POMNILNIKA PROCCsaR STRCZSA ZANKC VMESNIK ZANKC VMESNIK ZANKE oaoncK LmklnO tMtOkrtO UlklnS ' LtikOirta Ev«irtR>q • EvrvtAcl« Slika 1. Zgradba transputerja Dandanes je uporaba transputerjev že močno razširjena. O tem zgovorno priča vrsta proizvajalcev najrazličnejših transpu-terskih modulov. Poleg INMOSa, kot prvega proizvajalca te tehnologije, so še ParsyTec/ParaCom, MSC/Hemma, Mark Ware Associates, Gemini Computer Systems, in drugi. Module, ki so v glavnem splošno namembni, je mogoče poljubno povezovati v namenske, zmogljive, zanesljive, prilagodljive oziroma razširljive mikroračunalniške sisteme. Poleg funkcionalnosti, se moduli med seboj razlikujejo tudi po vodilih, ki omogočajo njihovo vgradnjo v sisteme z standardnimi vodili, kot so PC, Micro Channel, Q, VME, Multibus in Se nekateri. Transputer je zasnovan na tehnologu! RISC in je kot tak dovolj hiter. Neposredno podpira paralelizem, komunikacije in časovno odvisnost dosledno s koncepti konkurenčnosti komunikacijskih sekvenčnih procesov (CSP) /3/. Osnovne karakteristike transputerja kaže slika 2. MODEL PARAMETER T212 T414 T800 Širina glavnega in medregistrskega vodila 16-bit 32-bit 32-bit Kapaciteta RAM -pomnilnika na čip 2 KB 2 KB 4 KB Direktno naslov\jiv pomnilniški prostor 64 kB 4 GB 4 GB Hitrost izvajanja 10 MIPS 10 MIPS 10 MIPS Slika 2. Karakteristike tranaputerja Transputerji podpirajo različne oblike in stopnje paralelnega procesiranja. S povezovanjem v večtransputerski sistem omogočajo stvarni paralelizem. V tem primeru so lahko povezani med seboj na več načinov. Glede na to so možne različne strukture večprocesorskih sistemov. Najosnovnejše so: linearna, matrična, kubna in drevesna struktura, njihova izbira pa je največkrat odvisna od namembnosti sistema. Transputerji podpirajo tudi kvazi paralelno procesiranje. V takšnem primeru se več paralelnih procesov izvaja na enem samem transputerju s prepletanjem aktivnih rezidenčnih procesov na osnovnih časovnih intervalih. Za prepletanje skrbi mikrokodni dodeljevalnik, ki v mikrosekudah preklaplja posamezne procese in s tem ustvarja hiter kvazi paralelizem. Specifična odlika trans-puterskega večprocesorskega sistema je, da stopnja paralelizma in s tem učinkovitost procesiranja naraščata sorazmerno s številom transputerjev v sistemu. Uporaba transputerja v paralelnih sistemih je preprosta. Na topologijo sistema vplivata predvsem dva faktorja: zmogljivost in cena sistema. Transputerska, jezikovno usmerjena arhitektura, primerna strojna oprema za dodeljevanje procesov, sihro-nizirano komunicirarge, zunanje in časovne programske prekinitve ter časovno odvisno procesiranje omogočajo učinkovite gradnike mikroprocesorskih sistemov, ki delajo v realnem času. Naštete posebnosti so v sistemu dosledno prisotne, zasnova jezika occam pa takšna, da je programiranje enostavno in da je predstavljena rešitev v tem jeziku zelo blizu predstavitvi problema. 3. Occam in programska oprema RT-sistema Programski jezik occam je bil posebej razvit za delo v transputerski tehnologiji in podpira paralelno programiraivje. Jezik je zasnovan neposredno na Hoare-ovim CSP - jezikovnem zapisu komuniciranja in konkurenčnosti /3/. Omogoča predstavitev funkcionalnih karakteristik RT-sistema in medsebojnih sistemskih aktivnosti v zgoščenem visoko-nivojskem zapisu. 3.1. Načrtovanje occam-programov Programiranje v jeziku occam je nekoliko drugačno od programiranja v klasičnih sekvenčnih jezikih. Uporabljajo se preprosti koncepti paralelizma. Posamezne dele programa je možno zastaviti paralelno. So pa tudi deli programa, ki tečejo sekvenčno. Takšni deli so npr. vhodno/izhodne operacije, ki so relativno manj pogoste. Zanje se uporabljajo običajna načela programiranja. Tipično se uporabljajo prilagojene tehnike, kot je "koračno očiščevanje" znotraj strukturiranega programskega okolja. Uporabo takšne tehnike omogoča na primer zložljiv urejevalnik. Pri uporabi konceptov paralelizma pa se je treba najpre-je otresti predsodkov, ki so navadno posledica programiranja v običajnih, sekvenčno naravnanih programskih jezikih. V prvih korakih načrtovanja je koristna raba že dobro vpeljsmih pripomočkov. Mednje sodi diagram pretoka podatkov (Data Flow Diagram, DFD), s katerim je mogoče načrtovati ne le serijske, ampak tudi paralelne programe, saj je DFD že po svoji naravi inherentno paralelen. V okolju occam-a uporabljamo DFD direktno, ker so tokovi podatkov enaki tokovom podatkov, ki tečejo skozi kanal. Podobno ustrezajo procesna vozlišča v DFD procesom v occam-programu. Zato DFD podaja strukturo kanalov in procesov, kot tudi tok podatkov, in s tem povezanost med procesi. Uporaba DFD bo pokazana v naslednjih razdelkih predvsem za sistemsko analizo na tako imenovani nizko nivojski implementaciji diagramov. Naslednji razdelek bo posvečen študiji jezikovnih posebnosti jezika Occam, ki so pomembne za razvoj mikroprocesorske programske opreme za delo v realnem času. Študija je omejena na sisteme, katerih zasnova strojne opreme in arhitekture se opira na transputerski koncept. Programska oprema takšnih sistemov je nadalje obravnavana na primerih zametka signalno informacüskega in nadzornega sistema za hotelsko službo in preskrbo (HIS). 3.2. Zametek RT-sistema HIS; Zahteve, konfiguracija in značilnosti opreme Značilnosti programske opreme sistema HIS za delo v realnem ččisu so pogojene z Jisinhronim izvajanjem paralelnih procesov v sistemu. Oprema mora biti razbita na preproste, vase zaključene enote, ki se lahko izvajajo harmonično in paralelno. Konkurenčno programiranje v jeziku occam omogoča modeliranje opravil na paralelne procese, ki komunicirajo med seboj preko sporočil. Za izmenjavo sporočil, s katerimi se procesi med seboj v celoti sinhronizirajo, se uporabljajo določeni enosmerni transputerski kanali. Ti kanali nimajo vmesniških pomnilnikov za shranjevanje sporočil. Zato se izvajanje procesa zadrži, dokler vhodno/izhodne zahteve niso izpolnjene. Na ta način je preskrbljeno za medprocesno sinhronizacijo in asinhrono izvajanje procesov na docela urejen način. Jezikovna opisa paralelizma in komuniciranja sta si podobna za enoprocesorski ali za večprocesorski sistem. .Značilnosti jezika occam so v naslednjih poglavjih pokazane z njegovo uporabo na primeru preprostega RT-okolja, ki ga predstavlja HIS. Osnovno procesno shemo HIS prikazuje slika 3a. Centralni računalnik neprekinjeno testira vhodne informacije, ki prihajajo iz objekta naključno, in se nanje po potrebi tudi dovolj hitro odziva. To mu omogoča sposobnost.paralelnega procesiranja podatkov (signalov), ki po lokalni komunikacijski mreži prihajajo iz sobnih terminalov oziroma naprav signalno^informacijskega podsistema ter iz blagajniškega, požarno-varnostnega in energetsko - klimatskega podsistema. Na centralno enoto je priključenih tudi več terminalov za interaktivno delo s sistemom. Kakšne so funkcije posameznih komponent sistema? Signalno -informacijski, klimatski in požarno - varnostni podsistemi. V sobah in drugih prostorih hotelskega objekta so in- C^^BlogaJne Slika Sa. Oanovria shema zametka RT-sistema HIS: Okolje nadzornega sistema stalirane posebne naprave z aktuatorji in senzorji, po želji pa tudi osebni računalniki. Preko lokalne mreže so te mikroprocesorske naprave povezane s centralnim računalnikom, kateremu posredujejo vrsto podatkov: o statusu sobe (SOS stikalo, kontrola ključavnice na magnetno kartico, protivlomna zaščita, klic sobarice, servisa, ...), o klimi iii požarni zaSčiti (aktuatorji, senzorji). Omenjene naprave v obratni smeri, torej od centralnega računalnika sprejemajo signale oz. sporočila za gosta (signal prisotnosti, bujenja, sporočila na recepciji), za nadzor klime in požarne-varnosti, itd. Podsistem omogoča tudi računalniško komuniciranje iz "vseh" sob objekta z drugimi računalniki, ki so priključeni v objektu na centralno enoto HIS preko lokalne mreže (LAN) ali izven njega tudi preko javnih mrež. Blagajniški podsistem. Gostje in osebje ima namesto ključa magnetno kartico za vstop v prostore. To kartico Je smiselno uporabiti tudi za registracijo prisotnosti in kot kreditno kartico znotraj hotelskega kompleksa (trgovina, bar, restavracija, športni objekti). Zato Je potrebna sprotna evidenca o veljavnosti kartice, porabljenih finančnih sredstev gosta in dr. Na ta način Je preskrbljeno za bolj varno in ažurno poslovanje, za gostu prijetnejše bivanje ter za brezgotovinsko naplačevanje in poravnavo računov v kateremkoli trenutku. Terminali. Osrednji računalnik mora biti povezan z več terminali. Ti so npr. na recepciji za evidentiranje gostov iii za prikaz zasedenosti sob, vodenje rezervacij ipd., pri gospodinjah, sobaricah in najrazličnejših servisih za evidenco stanja sob (čiščenje, menjava posteljnine, prisotnost, klici) in za druga opravila. Terminal naj bi bil prisoten tudi pri varnostniku in omogočal pregled nad stanjem protivlomnih, protipožarnih in podobnih naprav. Komunikacijska mreža. Za realizacijo komunikacijske mreže je izbrana TV-napeljava, saj Je danes prisotna že v vsakem objektu. Na ta način se bistveno zmanjšajo stroški celotnega sistema, način pa omogoča tudi lažjo vgradnjo sistema HIS v že obstoječi hotelski kompleks. Ob prisotnosti kabelskega TV (CATV) omrežja na širšem področju (mesto, turistično naselje, itd.) predstavlja tako omrežje Se posebej zanimiv koinunikacijski medij v večjem informacijskem sistemu. 3.3. Vrstni red in časovni potek izvajanja Zaradi lažje nadaljne obravnave prikazuje slika 3b paralelno procesno shemo (iz slike 3a) bolj poenostavljeno. Poenostavljena shema na sliki 3b ima le dva podsistema, hkrati pa Je bližja realnemu svetu, saj je lokalna mreža razdeljena na več paralelnih mrež. Centralni računalnik mora biti dovolj zmogljiv in primeren za delo Blagajne^ TernlnalT^ Slika Sb. Paralelna procesna shema sistema HIS Mrežni pr«dprocesor LAN A sobe LAN ternlnall LAN C sobe TO TI LAN B sobe LAN ' blagajne Glavni računalnik v realnem času. Zato je sestavljen iz glavnega računalnika in pred-procesorja za neposredno vodenje podsistemov HIS. Predprocesor, ki opravlja tudi funkcijo krmilnika lokalnih mrež sistema, je realiziran s transputerji. Predprocesor v transputerski Izvedbi z dvema transputer-skima modularna TO in TI je prikazan na sliki 3c. Iz slike je razvidno, da sedaj transputerji upravljajo celotno komunikac^o, od glavnega računalnika pa prevzemajo tudi del pomembnih funkcij podsistemov, kot so npr. kontrola magnetnih kartic, sortiranje podatkov, oddajanje signalov v mrežo za indikacijo odziva sistema, sortiranje podatkov iz sprejetega paketa, in podobno. Če se procesi izvajajo na enem samem transputerju, potem število kanalov med njimi ni omejeno. To so t.im. programski kanali (soft channels). V primeru, da se procesi, ki med seboj komunicirajo, izvajajo na različnih transputerjih, je število kanalov Slika Se. Mreini predprocesor omejeno na Stiri fizične zanke (hard channels, strojni kanali). Če prihajajo preko ene zanke podatki iz več procesov. Je potreben multipleksiran prenos podatkov. Ta način je možen in sprejemljiv, če hitrost prenosa podatkov ni kritična. Procesom, ki zahtevajo hitrejSo izmenjavo podatkov z okolico, pa mora biti zagotovljena posebna zanka. Iz slike 3c je razvidno, da imata oba modula (TO in TI) v skladu s to zahtevo po štiri dvosmerne zunanje povezave z okolico. Iz diagrama na sliki 4 je opazna skladnost povezav med procesi PO in Pl v transputerskem okolju s povezavami med trčins-puterji TO in TI na sliki 3c. DFD lahko direktno preslikamo v occamski program. Vozlišča v O (Proces TO) 1 (Proces Pl) Slika DFD transputerskega okolja diagramu predstavljajo procese, povezave med vozlišči (tj. med procesi) pa predstavljajo komunikacijske poti za medprocesno izmenjavo podatkov. V occamu so komunikacijske poti direktno occam-kanali, po katerih si procesi med seboj izmenjujejo spročila. Tako DFD natančno podaja število kanalov in povezavo kanalov s posameznimi procesi, s tem pa je v occamu podana tudi medsebojna povezanost procesov. V jeziku Occam posplošena procesna struktura in sinhronizacija procesov, zasnovana na sporočilih, omogočata hierarhično dekompozicijo programske opreme v množico komunikacijskiskih paralelnih procesov nad lokalno deklariranimi podatki. Programi v jeziku occam so v osnovi sestavljeni iz treh primitivnih procesov, ki so označeni s spremenljivko ter vhodom in izhodom kanala. Pri tem se uporabljajo jezikovni konstrukti PAR, ALT in SEQ, ki določajo strukturirane procese. Tudi procesi zbiranja in selektiranja oz. predaje podatkov na transputerju, kot je razvidno iz DFD na sliki 4, imajo ustrezne značilnosti paralelnega, alternativnega ali serijskega izvajanja. Izpis 1 podaja occam-program procesa zbiranja in predajanja podatkov skupaj z glavnim programom. Prvi proces je imenovan 'producer', drugi pa 'consumer'. -- zbiranje/predaja podatkov — definicija procesa zbiranja PROČ producer ( CHAN s.coimiis ) CHAN OF INT input : PLACE input AT 2 : VAR X ; WHILE TRUE SEQ input ? X s.comms ! x -- definicija procesa predaje PROC consumer ( CHAN d.comms ) CHAN OF INT output : PLACE output AT i : VAR y : WHILE TRUE SEQ d.corns ? y output ! y CHAN coniffls : PAR producer ( comms ) consumer ( comms ) Izpis 1. Program zbiranja in predajanja podatkov Pri multipleksiranem zajemanju prihajajo podatki od distribuiranih procesov s pomočjo vektorskih kanalov d.c. Vrstni red, v katerem se pojavljajo, ni določen. Vhodi se zato izbirajo nede-terministično. Pri tem se uporablja konstrukt ALT, kije zapisan takole: ALT d.c.[0]?val d.c.[l]?val d.c.[2]?val Deterministično izvajanje paralelnih in alternativnih komponent-nih procesov na istem transputerju v časovno kritičnih odsekih kode se lahko določi z uporabo konstruktov PRI PAR in PRI ALT, ki označujejo prioritete izvajanja posameznih komponent-nih procesov. Izpis 1 prikazuje program s konstruktom PRI ALT, ki predstavlja proces prikazovanja poziva (proces I) ob prekinitvi opravila "povpraševanje". — Proces I WHILE TRUE CHAN OF BYTE povpraševanj e.tipalo: CHAN OF INT lokacija.zaslon: INT parameter!.vrednost.....parameterH.vrednost: BYTE povpraševanje: PRI ALT povpraševanj e.tipalo 7 povpraševanje IF povpraševanje ■ "I" SEQ ^ parameter1.povpraševanj e ! 'Y' pareuaeterl.kanal ? parameter 1 .vrednost vrednost.zaslon I parameter!.vrednost povpraševanje ■ 'N' SEQ parameter».povpraševanje ! 'Y' parameterN.kanal ? parameterN.vrednost vrednost.zaslon I parameterN.vrednost TRUE SKIP TRUE t SKIP — prekinitev povpraševanja — po parametru!/.../parametruN Izpis S. Prikazovanje poziva na zaslonu Vsak proces je mogoče opisati z osnovnimi procesnimi strukturami: Poleg paralelizma je bistvena lastnost RT-programa časovna odvisnost posameznih aktivnosti, ki so s programom določene in morajo biti sinhronizirane z neko dimenzijo časa. S tem je zagotovljena časovno odvisna strežba komponent, ki so priključene na sistem. Lastnost, ki jo zato morajo imeti RT-jeziki je, da dopuščajo dostop do časovnih posebnosti, ki so povezane npr. z urnim mehanizmom procesorja, in da imajo konstrukte, ki omogočajo jedrnato specifikacijo časovnih operacij. Programiranje v jeziku occam, ki je zasnovano za delo v realnem času, je glede na gornjo zahtevo mogoče podpreti s konstrukti, ki uporabljajo poimenovane objekte tipa TIMER. Uporabljajo se za odčitavanje transputerskega časovnika. Konstrukti so izraženi v obliki posebnih operetcü vhodnih kanalov. Vhod iz transputerskega časovnika predstavlja integer vrednost. Glavne oblike časovnih operacij, ki jih določa jezik occam, so naslednje: TIMER timer: INT time, period: proces časovnega vhoda timer 7 time -- vrednost spremenljivke -- casa, ki jo sproti določa -- transputerski casovnik -- proces časovnega izhoda timer ? AFTER time -- vhod iz transputerskega -- casovnika je zadrzan, -- dokler njegova vsebina -- ne preseže določeno -- vrednost; od tega -- trenutka dalje so — operacije brez učinka -- zakasnitveni proces SEQ timer timer ' ? time ? AFTER time PLUS period -- vhod iz transputerskega -- casovnika je zadrzan, -- dokler njegova vsebina --ne preseže določeno — vrednost (zakasnitev) -- (cas + perioda) Izpis S. Oblike časovnih operacij v occam-u Časovni konstrukti jezika occam omogočajo predikatne RT - operacije, ki so preprosto določljive. Število časovnih objektov, ki jih program dopuSča in uporabljajo isti transputerski časovnik, je neomejeno. Zato ima lahko vsak proces svoje časovne zahteve in uporablja lokalno deklarirane časovne objekte. Predstavitev sistemskih funkcionalnih delov in njihovih časovno odvisnih operacij je tako dovolj nazorna. 3.4. Programiranje na nižjem nivoju Jeziki za programiranje sistemov, ki delajo v realnem iasu, morajo omogočati lažje programiranje tudi na nižjem nivoju in s tem možnost, da se programi čim lažje prilagajajo spremembam v konfiguraciji sistema. Ta zahteva Izhaja iz dejstva, da se strojna oprema, ki je pridružena RT-sistcmom, pogosto menja in je pogosto nestandardna. Klasična rešitev je, da se v takšnih primerih v visoko-nivojski program vključujejo strojni kod ali rutine v zbirnem jeziku. Jezik occam je za transputersko arhitekturo zaprt. Zato se v splošnem nizko-nivojsko programiranje transputerskih sistemov ukvarja s preslikavami na ciljno sistemsko strojno opremo z naslednjimi specifikacijami: PLACE parameter.tipalo AT 0: — dodelitev kanala -- parameter.tipalo — k vmesniku zanke O PLACE status.register AT #1001: — dodelitev zunanjih vrat — status.register k " pomniliski lokaciji 4097 Poimenska prireditev v programski opremi bo v času izvajanja omogočala dostop do specifične strojne opreme. Vsekakor morajo biti vse prireditve poenotene; zanki vmesnika je lahko prirejen en sam kanal. (2) Dodeljevanje paralelnih procesov posameznim tretnsputerjem v večtransputerskem sistemu omogoča konstrukt PLACED PAR, ki nadomešča konstrukt PAR pri ustreznem tekstualnem nivoju v programih. Temu sledi procesorski stavek (PROCESSOR statement), ki vsebuje Številko transputerja in nato pridružen proces, ki se na transputerju izvaja. Konstrukt PLACED PAR za procesorje T, ki so označeni z zaporednimi številkami 0,1 in 2, ter za njim prirejene procese PO, Pl in P2,je: PLACED PAR PROCESSOR O SEq ... PO PROCESSOR 1 SEQ ... PI — transputer TO — deklaracije — opis procesa 'sobe (A,B,C), -- povezava s TI' -- transputer TI " deklaracije — opis procesa "terminali, -- blagajne, povezava s TO — in glavnim računalnikom" Zgoraj opisano proces-transputersko konfiguracijo in komunikacijske poti v sistemu prikazuje slika 3c. Iz gornjega programskega konstrukta je razvidno, da imamo dva procesa (PO, Pl), ki se nahajata vsak na svojem procesorju T (TO, TI). V deklaraciji opišemo potrebne kanale, razporeditev strojnih kanalov po linkih in spremenljivke. Enako velja tudi za deklaracije v naslednji primerih zapisa posameznih procesov: Pogled v proces PO: -- proces PO PAR ... hotelska mreža ... povezava s TI 1. Prirejanje virov 2. Proces - transputersko dodeljevanje 3. Deklariranje vrat; Preslikave pomnilnika na vhodno / izhodna vrata (1) Prirejanje deklariranih procesnih kanalov zankam strojne opreme vmesnika in spremenljivk, kot tudi zunanjih vhodno / izhodnih vrat, fizičnim pomnilniškim naslovom, omogoča konstrukt PLACE .. AT in je izražen takole: Transputer TO podpira hotelsko mrežo, ki je razdeljena na tri paralelne dele, in je namei\jena komunikaciji s sobnimi terminali in drugimi napravami (kot so aktuatorji, senzorji), s terminali za sobarice in za ostale servisne in nadzorne službe. Povezava s Ti je namenjena sprejemanju sporočil, ki jih daje proces Pl (na transputerju TI), in po ustrezni obdelavi na TO za pošiljanje podatkov nazaj k TI. In podobno, za sprejemanje in oddajanje sporočil v primerih, ko se obdelujejo podatki iz TO na Ti. Načelna oblika okrnjenega programa za lokalno mrežo s tremi vzporednimi vejami (LAN A, B in C) je naslednja: -- glavna mreža PAR [i = O FOR 3] SEQ WHILE NOT end SEQ SEQ [k = 0 -- za tri veje -- zaporedno -- deklaracije -- ista veja za sobe -- in sobarice FOR st.sob] --za vse sobe in sobni računalnik LAN A sobe LAN "ternlnaU SEQ [k = o FOR st.sobaric] -- za vse sobarice -- v veji . . . terminal sobarice V posameznih vejah se najprej sekvenčno naslavlja in procesira sobne računalnike, nato še terminale sobaric. Proces TI je podobno zastavljen: -- proces TI PAR . .. blagajne . . . terminali . . . povezava s TO ... povezava z glavnim računalnikom Kvazi paralelno se procesirajo mreže za blagajne, terminale (recepcija, varnostnik, ... ) ter za komunikacije med procesorjem TO in centralnim računalnikom. Za terminale, ki so na isti mreži, se postopek odvija sekvenčno: -- terminali SEQ WHILE NOT end SEQ -- na isti mreži . . . recepcija . .. varnostna služba V primeru, da se število povezav z okoljem poveča, ali da dano polje procesorjev ne more dovolj hitro opraviti svoje naloge, je mogoče konfiguracijo sistema po potrebi razširiti. Mnogokrat se poišče takšna rešitev, da lahko ostanejo že napisane programske rešitve popolnoma nespremenjene. Takšna rešitev je možna pri razširitvi sistema z arhivno ali rezervno pomnilniško enoto in modemom za povezavo z zunanjim svetom v konfiguraciji, ki jo kaže slika 5. Pri razširitvi na sliki 5 se v sistem vključuje dodatna procesorska enota (T2). Vsi procesi, ki se izvajajo na TO in TI, ostanejo skoraj v celoti nespremenjeni. Konstruktu PLACED PAR je dodan procesor T2 z ustreznim procesom P2, nekoliko pa se spremeni tudi proces Pl. Slika 5. Razširjena konfiguracija HIS SEQ ... PO PROCESSOR 1 SEq ... PI PROCESSOR 2 SEQ ... P2 deklaracije opis procesov 'sobe (A.B.C) in povezave a TI' transputer TI deklaracije opis procesov 'terminali, blagajne in povezav s TO in T2' transputer T2 deklaracije opis procesov "povezav a TO, TI. arhivno enoto in glavnim računalnikom" V primeru na sliki 6, kjer ima razširjeni sistem HIS (iz slike 5) spremenjeno topologijo, so potrebne že večje spremembe. Kot je razvidno iz gornjih izvajanj, je s kombinacijo konstrukta PLACED PAR in konstrukta PROCESSOR možno direktno dodeljevanje posameznih procesov določenim transputerjem. S tem dodeljevanjem in skupaj s prireditvenimi konstrukti PLACE ., AT .. je določen celoten dostop do glavnih virov večtransputerskega sistema. Obravnavani konstrukti jezika occam omogočajo razvoj paralelnih Occam programov, ki tečejo na enem samem transputerju. Odlika takšnih programov jé, da se lahko hitro - največkrat le z minimalnim reprogramiranjem - prenašajo iz sistema, za katerega so bili načrtovani, na sisteme z drugačno topologijo. (3) Priključitev perifernih naprav (terminalov, tiskalnikov, ali v nažem primeru tudi priključitev transputerja T2 na glavni računalnik) za prenos podatkov v obliki sporočil, je potrebno določiti vhodno/izhodna vrata takole: PLACED PAR PROCESSOR O -- transputer TO PORT OF BYTE external: --2 "external" so deklarirane -- vhodno/izhodna vrata tipa BYTE LAN A sobe LAN ternlnall Slika 6. RazSirjtn eistem HIS a spremenjeno topologijo PLACE external AT »No: -- priredi vhodno/izhodnim vratom — zunanje naprave pomnilniski -- prostor v T z naslovom No Pomnilnižke preslikave vhodno/izhodnih vrat se uporabljajo podobno kot preslikave occam kanalov pri prenosu podatkov. Toda - v nasprotju s kanalsko zasnovanim komuniciranjem-^jri pomnilniških preslikavah vhodno/izhodnih vrat ni nobenega sinhronizacijskega mehanizma. Zato morajo biti vmesniške naprave, ki skrbijo za pomnllniško preslikovanje prenosov, programirane tako, da so upoštevane operacijske karakteristike perifernih naprav. To omogočajo jezikovni konstrukti v occamu, ki olajšujejo nizko -nivojsko upravljanje z bitno usmerjenimi logičnimi operacijami in s pomiki ali rotacijami bitnih nizov v levo ali desno. Ustrezne kode kažejo tipično asinhrono naravo pomnilniških preslikav vhodov / izhodov. Occamovi jezikovni pripomočki za neposredno prirejevanje virov, prilagodljivo đodeljevai\je procesov in neomejeno konvencionalno pomnilniško preslikovanje vhodov/izhodov bistveno olajšujejo načrtovanje, RT-sistemov. Pri tem je pomembno poudariti, da se pri uporabi jezika occam ni potrebno spuščati na nižji nivo programiranja, kot je običajno pri drugih jezikih. 3.6. Obdelava napak Posebej za sisteme, ki delajo v realnem času, je pomembno, da njihova programska oprema obravnava tudi napake. Takšna oprema zagotavlja sistemsko zanesljivost in trdoživost do napak, kar je še posebej pomembno za sisteme z računalnikom (embedded systems). Ob morebitni napaki se mora sistem po obdelavi napake vsakokrat hitro vrniti nazaj v pravilno stanje in normalno nadaljevati delo. Occam ne podpira formalnih mehanizmov za obravnavo napak, medtem kojih ADA podpira. Occamovo progratiuko opremo za odkrivanje napak v času izvajanja programa je mogoče opredeliti v dve skupini: 1. Detektiranje napak s prevajalnikom 2. Detektiranje napak pri izvajanju programa Pri programski opremi iz prve grupe, se napake odkrivajo na več načinov: s strojno opremo, s preverjanjem instrukcij, ki se vključujejo s prevajalnikom, s transputerskimi zastavicami za napake in z izhodi, na pinu katerega se ob napaki pojavi signal. Napake, ki se lahko odkrivajo so: aritmetična prekoračitev (obsega), prekoračitev polja in deljenje z 0. Sistem je prirejen za obdelavo takšnih napak po eni od naslednjih poti: • Proces z napako se ustavi, ostali procesi normalno tečejo dalje. • IVansputer, pri katerem se pojavi napaka, se ustavi, ali se ustavi večprocesorski sistem v celoti, in zaSčiti notranje stanje sistema za nadaljne analize. • Vključi se univerzalni proces obdelave napake. Ta pričakuje vhod, ki je pogojen s pinom EventReq na zahtevo pina Error. Pri tem se uporabna strojni kanal, ki dovoljuje vhod signala na pinu EventReq in preko katerega poteka pošiljanje sinhronih sporočil za procesiranje napak. Proces se izvaja podobno kot drugi occam-ovi procesi in je podvržen istim pravilom. Zato mora biti occam-kanal združen s pinom EventReq; deklarac^a takšnega kanala, uporabljenega za obdelavo napak, je opisana v naslednjem zapisu: PLACE event AT No: WHILE TRUE SEQ event ? signal — vhod je zakasnen, dokler — ni pogojen s pinom EvenReq — na zahtevo pina Error Proces obdelave podatka Proces, v katerem se pojavi napaka, se zadrži v stanju mirovanja. Posledica napake se odpravlja tako, da drugi procesi prevzamejo aktivnosti tistih procesov, ki postanejo nefunkcionsdni. Zaradi centalizirane narave procesiranja napake, morajo biti dodatni koraki zelo nezahtevni za izvajanje ali dodeljeni drugim procesom tako, da se osnovni proces obdelave napake lahko nadaljuje in hitro odzove morebitni ponovni napaki. Pri programski opremi iz druge grupe se napake odkrivajo z vgrajenim, eksplicitno programiranim preverjanjem s pravimi vrednostmi in rezultati. Tako se odkrivajo napačni podatki, zatajeni pogoji in podobno. Večja zanea^ivost komunikacij, k! uporabljajo transputerske vmesniške zanke, je dosežena s podporo številnih standardnih occam - procedur. Za uspešen prenos preko vmesniške zanke skrbita standardni proceduri InputOrFail in OutputOrFail. Proceduri pokažeta, če se je prenos, ki se je aktiviral, izvršil ali ne. Strojna oprema uporabljene zanke, na kateri se je med komunici-raiijem pojavila napaka, mora biti ponovno inicializirana. Inicial-izacijo kanalov na obeh koncih zanke izvrši standardna procedura Reinitialise. Možnost obdelave napak in trdoživost proti napakam je lastnost transputerskih sistemov, ki običajno zahteva zapleteno diagnostiko napak in ustrezno, dokaj zahtevno programsko opremo. Visoka stopnja zanesljivosti, sposobnost reševanja vprašanja redundance strojne opreme in dinamične rekonfigurabilnosti sistema zagotavljajo pravilno delovanje tudi v primerih morebitnih kritičnih napak v strojni opremi. V splošnem vplivajo na strukturo transputerske strojne in programske opreme, ki omogočata obdelavo napak, značilnosti sistema, ki so pogojene z njegovo uporabo. 4. Zaključek Bistven pomen prispevka naj bi bil, da se na konkretnem primeru zametka signalno - informjicijskega in nadzornega sistema za velike hotelske oziroma turistične objekte pokažejo nekatere posebnosti in prednosti uporabe transputerske programske in strojne tehnologije pri snovanju RT-sistemov z vgrajenimi računalniki. Uporaba sistemov v realnem času je navadno zasnovana na običajnih računalnikih. Ti so sestavljeni iz enega samega ali večih procesorjev, ki si dodeljujejo pomnilnik in vodila. Z dodeljevanjem virov se pojavljajo zapleteni problemi, ki morajo biti rešeni, praviloma pa vodijo k manjši zmogljivosti sistema. Transputersko zasnovana oprema, ki kaže v visoko zmogljivost in modularnost, je posebej primerna za asinhrono izvajanje opravil v RT-sistemih, saj omogoča resnično in kvazi paralelno procesiranje. Možnost lahkega in učinkovitega oblikovanja večprocesorskih transputerskih sistemov, pri katerih predstavlja dodeljevanje pomnilnika in vodil manjši napor, daje trans-' puterju bistveno prednost pred običajnimi računalniškimi sistemi, ki se uporabljajo v RT-sistemih. Kljub temu, da so v transputerskih sistemih medprocesorske komunikacije omejene s štirimi fizičnimi povezavami, obstajajo velike možnosti pri izbiri optimalne računalniške topologije in v strategiji uporabe ustrezne programske opreme. Oboje skupaj lahko odločilno vpliva na zmogljivost sistema. Jezik Occam ima preprosto, regularno sintakso, ki omogoča jasen in naraven razvoj programske opreme paralelnih transputerskih sistemov. Jezik je neposredno uporaben tako za programiranje RT-sistemov, kot za predstavitev paralelnih procesov in časovnih potekov, za dostop do nizkega nivoja stroja in za prilagodljivo priključevanje perifernih naprav. Pomembno je tudi, da omogoča programiranje, ki minimizira prekomeren čas izvajanja in skrbi za optimalnejšo izrabljenost pomnilniškega prostora. V jeziku occam zasnovano programsko opremo je mogoče dopolnjevati s konstrukti jezika C, Pascala in Fortrana. Ti jeziki namreč podpirajo nekatere dodatne programske konstrukte in podatkovne strukture, ki so lahko ugodnejše od onih, ki jih nudi occam. Vidna prednost jezika occam napram ostalim tovrstnim jezikom pa je vsekakor ta, da omogoča razvoj programov, ki opisujejo tudi v sistemu uporabljene komponente strojne opreme. Zato je jezik uporabljiv tako za formalni opis rezultatov načrtovanja, kot za opis dejanske končne programske opreme sistema. Na ta način je moino bistveno zmarvišati ceno in čas načrtovanja. Kadar se transputer in očcam uporabljata vzajemno, je učinkovitost implementacye transputerja velika. Tako načrtovani RT-sistemi se po svojih zmogljivostih uvrščajo med najzmogljivej-Se "embedded" krmilnike, ki se uporabljajo za reševanje zahtevnih nalog procesiranja slik in signalov. Zaradi omenjenih lastnosti in cene transputerske tehnologije, ki stalno pada, predstavljajo transputerji pomembno alternativo pri izbiri mikroprocesorjev za sisteme, ki delajo v realnem času. S.Literatura /1/ Civera,P.,Del Corso,D. and Gregoretti.F., "Microcomputer systems in real-time applications" in Tzafestas,S.G.(ed.), Microprocessors in Signal Processing, Measurement and Control, Reidel /2/ Inmos Ltd. Transputer Reference Manual (1986) /3/ Hoare,C.A.R., "Communicating sequential processes", Communications ACM, Vol.21, No.8 (1978), pp.666-677 /4/ Burns,A., Programming in Occam 2, Addison-Wesley (1988) /5/ Hull,M.E.C., and Zarea-Aliabadi,A., "Embedded microcomputer systems - a comparative study of two implementation methods", J. of Microcomputer Aplications, Vol.10 (1987), pp.255-281 /6/ Bennett,S., Real-Time Computer Control; an introduction, Prentice Hall (1988) /7/ Kerridge.J., Occam programming: a practical approach, Blackwell Scientific Publications (1987) /8/ Mihovilovi6,B.,Kolbezen,P.,Šilc,J., "A paradigm of transputer system implementation", Informatica 4/87, (1987) pp.54-58 /9/ Jereb,B., Pipan,L., Klofutar,A., "Transputers", Informatica 1/89 (1989) pp.43-47 SIMULACIJA IN VREDNOTENJE PROGRAMSKE INFORMATICA 3/90 OPREME ZA VECPROCESORSKI RAČUNALNIK Keywords: parallelism, multiprocessor system, Fakulteta za eiektfÄniko''in mterprocess communication, simulation, granularity računalništvo, Ljubljana POVZETEK Razvoj vse hitrejših in zmogljivejših računalnikov gre danes v smeri izkoriščanja principov paralelizma pri snovanju novih računalniških arhitektur. Nove arhitekture pogojujejo tudi spremembe principov programiranja. VeCprocesorski računalniki se danes programirajo na dva naCina. Prvi nacin je programiranje v standardnih sekvenCnih programskih jezikih. Tak program se prevede s posebnim, vzporednim prevajalnikom, ki z veC ali meinj uspeha prilagodi kodo za vzporedno izvajanje. Drugi naCin, ki zahteva popolnoma nov pristop k snovanju algoritmov, je programiranje z eksplicitno vzporednimi jeziki. V Članku je predstavljen koncept za simuliranje izvajanja programov pisanih v eksplicitno vzporednem programskem jeziku PARSYS Pascal za veCprocesorski računalnik. PARSYS Pascal je razširjeni ISO Pascal z "ukazi" za kreiranje procesov, medprocesno komunikacijo, skupnimi in lokalnimi spremenljivkami itd. "Okazi" so v bistvu klici procedur in funkcij simulatorja,ki se v času prevajanja dodajo vsakemu PARSYS Pascal programu. Poleg primitivov programskega jezika vsebuje simulator tudi procedure in funkcije, s katerimi simulira izvajanje vzporednega programa na veCprocesorskem sistemu. CasovTji rezultati simulacij so dobra osnova za učenje principov dobrega in učinkovitega vzporednega programiranja. ABSTRACT: SIMULATIOH AMD PERFORMANCE EVALUATION OF PARALLEL SOFTWARE OF MULTIPROCESSOR SYSTEM ■v The development of ever faster and more capable computers is aimed at the application of the principles of the parallelism in the construction of new computer architectures. New computer architectures cause in turn changes in the programming principles. The multiprocessing systems are programed now in two ways. The first involves standard sequential programming languages. Such a program is compiled by a parallel compiler which with varying success adapts a program code to parallel execution. The second way, requiring a completly new approach to the creation of algorithm, involves a programming with explicit parallel language. The article presents a concept of the simulated execution of a program which is written in exsplicit parallel programming language PARSYS Pascal for multiprocessor. The PARSYS Pascal is an ISO Pascal enlarged with "statements" for the process creation, interprocess communication, local and shared variables, etc. The "statments" are actually calls of procedures or functions which during the compile time are added to each PARSYS Pascal program. Apart from the primitives of the programming language the simulator contains procedures and functions by which it simulates the execution of the parallel program on the multiprocessing system. The results of the simulations provide good basis for those who wish to learn the principles of a good and efficient parallel programming. 1. UVOD - preko novih programskih prijemov: metode Čeprav smo priCa sila naglemu razvoju raCu- umetne inteligence, ekspertni sistemi, nalnistva in informatike, vidimo, da je hitrost programska orodja naraščanja potreb po moCnejSih računalnikih - z novimi arhitekturami : paralelne večja, kot pa razvoj tehnologije. Rešitve potreb arhitekture v računalništvu omogočajo po močnejših sistemih iscemo na različne načine paralelno izvajanje nalog, in sicer: Računalniški sistemi z novimi arhitekturami skozi novo tehnologijo: stopnja integracije imajo zelo pomembno vlogo pri razvoju novih vezij je vedno večja, uvajajo se novi konceptov in rešitev v računalništvu. Nekateri materiali kot na primer GaAs paralelni sistemi, kot na primer računalnik Butterfly, IBM RP3, Cedar in drugi so pokazali izredne možnosti paralelnih računalnikov. Tuje konzultantske firme napovedujejo da bo aiedi 90. let 48% trsiac-a zmogljivih računalnikov temeljilo na principih paralelnega procesiranja. Cilj mojega dela je predstavljanje sprememb v naCinu programiranja, kj so , posledica novih računalniških arhitektur. Očitno je da bo programiranje paralelnih računalnikov k raalu postalo del vsakdanjega življenja vseh, ki se ukvarjajo s računalništvom. 2. PROGRAMIRANJE PARALELNIH RAČUNALNIKOV Do danes je razvitih veC pristopov k programiranju računalnikov zasnovanih na paralelnih arhitekturah. Razlog za to je, da so cilji posjamesnih prisJtopov raslicni. Za pregled obstoječih vzporednih programskih je-zikov je sato nujno izbrati kriterij za rasli-kovanje pristopov k programiranju. Razlikovali bomo : - jezike z eksplicitnim izražanjem vzporednosti in - jezike z implicitno vzporednostjo. Jeziki iz prve skupine so zasnovani na programerjevi določitvi vzporednosti. Jezik PARSYS Pascal, ki je predmet obravnavanja v naslednjem poglavju, pripada tej skupini jezikov. To je razlog nekoliko podrobnejše obravnave eksplicitno vzporednih jezikov. Drugi skupini pripadajo jeziki zasnovani na principih avtomatičnega razpoznavanja (detekcije) paralelizma v casu prevajanja. Prvi in drugi pristop imata, kot je razvidno iz slike 1, izhodišče v avtomatičnem razpoznavanju mikroparalelizma v sekvenCnih programih. Kaj to pomeni, bo. razvidno iz naslednjega primera. Recimo, da v nekem programu instrukciji LOAD sledi instrukcija ADD. Ce ADD ne uporablja ponornega ("target") registra instrukcije LOAD, potem je dovoljeno prekrivanje nekaj zadnjih ciklov infjtrukcije LOAD in prvih ciklov instrukcije ADD. Opisano razpoznavanje mikroparalelizma se opravlja v Casu izvajanja (run-time) programa, ■ možno pa je ne glede na izvorni programski jezik. Na žalost so pohitritve, dosežene na ta naCin, relativno majhne. 2.1 Eksplicitno izražanje vzporednosti Ce želimo izračunati poti desetih neodvisnih raket, je oCitno, da moremo do rezultata priti desetkrat hitreje, ce namesto desetih zaporeänih izračunov izvajamo po en izraCun na desetih paralelnih procesorjih hkrati. Programiranje z jeziki iz skupine eksplicitno paralelnih jezikov, kot je razvidno tudi iz navedenega primera, predpostavlja možnost naravne razčlenitve (dekompozicije) problema, ki ga rešujemo. Porazdelitev jezikov znotraj skupine eksplicitno paralelnih temelji na različnih možnostih za izražanje paralelizma. Prikazana je na sliki 2. 2.1.1 .Vaporedni »okvenOnl programi Najenostavnejši.pristop k eksplicitnemu paralelizmu je istočasna uporaba veö sekvenCnih programov. Ti programi navadno izmenjujejo sporočila samo preko datotečnega sistema. Zato je cena teh povezav izredno visoka. Istočasna uporaba več sekvenCnih programov se izplača samo, Ce paralelno izvajamo velike programe, ki redko izmenjujejo sporočila. Dober primer uporabe tega principa je DEC VAX VMS mreža. 2.1.2 Nizko nivojska eksplicitna vzporednost Visoka cena povezovanja in sinhronizacije programov pri predhodni tehniki je omogočala samo grobo-zrnati ("large-grain") paralelizem. Številni sekvenčni jeziki pa so spremenjeni tako, da omogočajo tudi drobno-zrnati ("fine-grain") paralelizem. Razširjeni so s funkcijami, kot so semaforji in join/fork operacije ter različnimi načini za izmenjavo sporočil (npr. buferji aa sporočila). Enostavnost teh reSitev povzroča Časovno potratnost in neefikasnost kompleksnih algoritmov. Po drugi strani pa ima mala napaka pri uporabi dodanih funkcij pogosto za posledico smrtni objem ("deadlock"). Uspešni primeri izkoriščanja tega pristopa so BEH Uniform Programming System in nekatere verzije Berkley in System V UNIXa aa paralelne računalnike. 2.1.3 Nesekvenöni progrwal s kontrolo na osnovi sporočil Številni pristopi k paralelnemu izvajanju so nastali na osnovi visoko nivojskih formalizmov. Verjetno najbolj znani formalizem je razvil Hoare leta 1978. To je CSP (Communicating Sequential Processes). Programi napisani v jezikih, ki so nastali iz teh formalizmov, . pripadajo skupini nesekvenčnih programov s kontrolo na osnovi sporočil. i ji •• Slabost tega pristopa je slaba prilagodljivost jezikov različnim vrstam računaln^ov. Sprememba računalnika more imeti za posledico občutno zmanjšanje učinkovitosti programa (na primer. če uporabljamo izmenjavo sporočil na vektorskih računalnikih). Zadovoljiva učinkovitost programa je ozko povezana s tipom računal- Slika 1. Izhodiščna porazdelitev pristopov k vzporednemu programiranju Slika 2. Tipi eksplicitne vzporednosti niske arhitekture. Predstavniki jezikov tega tipa so: Ada, OCCAM in LINDA. 2.1.4 Sekvenöni programi a eksplicitno vzporednostjo podatkov in kontrole Poleg samega podajanja modela vzporednosti (kot v prejšnjem pristopu), omogočajo jeziki tega razreda tudi modeliranje okolja, v katerem se program izvaja. Enake težave se za programerja pojavljajo pri poskusih optimalnega razvrščanja (alociranja) podatkov v pomnilnik, kot tudi pri definiranjvi vzporedne kontrole v programu (Olovek je vajen zaporednega načina razmišljanja in izvajanja operacij). Programski jezik Actus omogoCa naslednjo specifikacijo: var A : array [1 : 4, 1 .. 5 ] of integer ; Navedeni programski stavek pomeni, da je v pomnilniku matrika A organizirana tako, da so paralelni podatki razvrščeni po prvem indeksu. Z drugimi besedami, dvopičje določa indeks, po katerem so podatki razdeljeni med procesnimi elementi v matričnem računalniku, oziroma stalno shranjeni v vektorskih registrih nekega vektorskega računalnika. Tudi nekateri drugi jeziki podpirajo podobne (vektorski orientirane) konstrukte in zato prijiadajo skupini vzporednih jezikov, ki jih opisuje to poglavje. To so npr. Parallel Pascal, Vector C, Parallel C, Concurent C itd. 2.2 Implicitna vzporednost Možnost neposrednega definiranja vzporednosti v sekvenCnih jezikih ne obfjtaja. S tem odpadejo tudi problemi, ki jih programerju povzročajo sinhronizacija izvajanja, izmenjava sporočil itd. Ce je taksen sekvenčni jezik izhodišče za programiranje paralelnega računalnika je nemogoče, da bi programer pri izvajanju povzročil smrtni objem (deadlock). To je seveda res samo, če prevajalnik, ki transformira kodo v vzporedno formo, uporablja transformacije, ki obdržijo pravilnost delovanja. Vzporedni program bo tako proizvedel enake rezultate kot sekvenčni. Izvorni program je sedaj čitljiv (za razliko od eksplicitno vzporednih programov), iskanje napak pa ne povzroča več prevelikih težav. Obstajajo 5e nekatere prednosti programiranja s sekvenčnimi jeziki. Program je prenosljiv na različne paralelne računalnike ne glede na njihovo arhitekturo s tem, da je povsod približno enako učinkovit (odvisno od kvalitete prevajalnika). Se veö, program je prenosljiv tudi na enoprocesorske računalnike. Prvi poskusi avtomatične paralelizacije sekvenčnega programskega jezika so bili narejeni s standardno verzijo jezika FOKTRAN. Nekatere tehnike paralelizacije, predvsem tiste za paralelizacijo zank, so se izkazale kot zelo dobre. Konstrukte, podobne DO zanki, je možno v FORTRANu paralelizirati skoraj idealno, za katerikoli računalnik. Čeprav je doseženi nivo paralelizacije Zadovoljiv za veCji del današnjih paralelnih računalnikov, z razvojem naslednje generacije to ne bo veC držalo. Poleg tega so bili rezultati paralelizacije drugih sekvenčnih jezikov poleg FORTRANa slabi, ti^o da so danes paralelni prevajalniki za te jezike razmeroma redki. V zadnjih letih so razvite metode (npr. metoda "prečiSčevenja jezikov" - "rafined languages approach") za paralelizacijo velikega Števila drugih jezikov. Te metode so dale dobre rezultate pri paralelizaciji programov pisanih v programskih jezikih C, FORTRAN, LISP, Pascal, Prolog itd. To je trenutno področje obsežnih raziskav, pričakovati pa Je bistven napredek v naslednjih nekaj lotih. Poseben pristop vzporednosti znotraj skupine implicitno vzporednih jezikov se opazi pri jezikih s podatkovnim potekom ("data flow languages"). Ti jeziki so dostopni na računalnikih specifičnih arhitektur. Računalniki s podatkovnim potekom delujejo na principu izvajanja instrukcije v Času dostopnosti njenih operandov. Jeziki namenjeni tem računalnikom so sestavljeni iz različnih vrednosti, izrazov in funkcij, namesto spremenljivk, stavkov in procedur. Ti jeziki onemogočajo pojave kakršnihkoli stranskih učinkov (side effects), s tem pa je proces avtomatičnega razpoznavanja vzporednosti poenostavljen. Uporaba implicitne vzporednosti in implicitne sinhronizacije pomeni, da v jezikih s podatkovnim potekom ne obstajajo možnosti za eksplicitno definiranje vzporednosti, npr. procesov ali,monitorjev. Primer jezika s podatkovnim potekom je VAL. Uporabnikom ponuja funkcije brez stranskih učinkov, kar omogoča preverjanje sintaktične, kot tudi semantične pravilnosti programa v času prevajanja. Slabost VALa so vhodno izhodne operacije. Te operacije niso realizirane v funkcijah jezika in za njihovo izvajanje je odgovoren operacijski sistem ciljnega računalnika, kar pa je moSen izvor nezaželjenih pojavov. Kljub obstoječim pomankljivostim dosedanjih rešitev so računalniki s podatkovnim potekom in njihovi jeziki področje raziskav, od katerih se v računalništvu veliko pričakuje. Poleg vseh omenjenih prednosti implicitnega pristopa vzporednosti pred eksplicitnim programska oprema vseh paralelnih superraCunalnikov Se vedno vsebuje eksplicitne paralelne jezike. Razlogov je verjetno več. Eden od njih pa je gotovo podoben razlogu za definiranje asembler-skega jezika pri vseh modernih računalnikih, 3. PARSYS PASCAL Programski jezik PARSYS Pascal je razvit kot sestavni del simulatorja paralalne programske opreme. Glede na porazdelitveno shemo paralelnih programskih jezikov, predstavljeno v predhodnem poglavju, se v programih pisanih v PARSYS Pasca-lu vzporednost izraaa eksplicitno. Torej programer določa dele programa, ki se bodo istočasno izvajali. Bolj natančno, pa PARSYS Pascal pripada skupini nesekvenCnih jezikov s kontrolo na osnovi sporočil. PARSYS Pascal je nadmnosica standardne verzije programskega jezika Pascal, natančneje Microsoft Pascala, ki je instaliran na računalniku Triglav pod operacijskim sistemom XENIX in podpira ISO standarde. Pascal je razširjen s primitivi, ki izražajo (navidezno) vzporednost. Definicije teh primitivov se nahajajo v simulatorju, ki se v času prevajanja (compile time) doda vsakemu PARSYS Pascal programu. To omogoča izvajanje programov v enonaslovnem prostoru, brez skokov v operacijski sistem in iz tega izhajajočih časovnih izgub. Program, pisan v jeziku PARSYS Pascal, iraa strukturo podobno navadnim pascalskim programom, programerju pa je omogočeno kreiranje algoritmov z več vzporednimi procesi, ki izmenjujejo sporočila med seboj. Procesi imajo sintakso pascalske procedure s pomenom zaporedja ukazov, ki se izvaja vzporedno z drugimi zaporedji ukazov. Procesi nastajajo dinamično, v času izvajanja programa, končujejo pa se v trenutku, ko se izvede zadnji definirani stavek. navidezni izbor procesorja, na katerem se bo proces izvajal, je dolžnost simulatorja in ni načina, da bi programer na to vplival. S pošiljanjem sporočil skozi "kanale" sta doseZeni sinhronizacija in komunikacija med procesi. Kot bo razloženo kafjneje, so kanali v bistvu postni predali (mailbox), v katerih procesi puSCajo sporočila in iz njih ta sporočila jemljejo. Procesi morejo komunicirati Se na drug naCin, z uporabo skupnih spremenljivk. Poleg primitivov, ki omogočajo izvedbo navedenih možnosti, simulator vsebuje tudi primitive, ki pomagajo programerju, da se seznani s trenutnim stanjem procesov v obdelavi, npr. kateri procesi so trenutno aktivni, katera sporočila so poslana, niso pa Se prebrana (uporabljena) in podobno. Prisotnost teh primitivov v simulatorju pomeni možnost njihove uporabe kot "ukazov" PARSYS Pascala, Podroben opis vsega navedenega je podan v podpoglavjih, ki sledijo. 3.1 Spremenljivke Pri programiranju sekvenCnih, enoprocesorskih računalnikov se spremenljivke eksplicitno deklarirajo na začetku programa pri prevajalnikih, ali pred prvo uporabo pri interpreterjih (implicitno). Fri izvajanju se nad njimi korak po koraku izvršujejo ukazi. Izvajanje teče zaporedno, spreminjanje vrednosti spremenljivk se odvija po znanem, vnaprej določenem vrBtnem redu. Vrednost spremenljivke je mo2no spremeniti samo z enim izmed dveb naCinov; prirejanjem vrednosti oziroma branjem. Ce programer v sekvenci ukaaoV ni uporabil spremenljivke, more biti prepričan, da 'ima le-ta isto vrednost po izvajanju teh ukazov, kot jo je imela pred tem. Pri vzporednem izvajanju veC zaporedij (sekvenc) ukazov predhodna trditev ne drai nujno. Ce vzporedni procesi uporabijo spremenljivko in spremenijo njeno vrednost, to povzroča nepričakovano in morda tudi neponovljivo vedenje programa. To je odvisno samo od (vnaprej neznanega) zaporedja časovnih intervalov, v katerih bo posamezen proces uporabil spremenljivko. To povzroča obstoj dveh različnih tipov , spremenljivk v vzporednih programskih jezikih, glede na njihovo dostopnost. Prvi tip ao lokalne spremenljivke. Uporabljajo se samo v procesu, na začetku' katerega so deklarirane. Za posamezni proces je Se rečeno, da predstavlja navadno zaporedje ukazov, "obnašanje" lokalnih spremenljivk v njem pa je enako, kot pri spremenljivkah v eekvenčnih programih. Drugi tip spremenljivk predstavljajo tiste spremenljivke, ki jih lahko uporablja in tudi spreminja več procesov. Spremenljivke tega tipa imenujemo skupne (shared), uporabljamo pa jih pri medprocesni komunikaciji. PARSYS Pascal sledi navedenim razlogom in omogoča deklariranje dveh tipov spremenljivk glede na njihovo dostopnost. Poleg rezervirane besede VAR, ki se uporablja pri vseh verzijah Pascala, nudi PARSYS Pascal uporabo rezerviranih besed LOCAL (za lokalne spremenljivke) in SHARED (za globalno dostopne spremenljivke). LOCAL in SHARED se uporabljajo samo pri deklariranju spremenljivk v glavnem programu zato, ker, öe je spremenljivka deklarirana v neki proceduri, funkciji, ali pri PARSYS Pascal procesu, to ae samo po sebi pomeni, da je dostopna samo znotraj te procedure, funkcije ali procesa. To pa ustreza pogojem za (glede na dostopnost) lokalni tip spremenljivke. Ce spremenljivko v glavnem programu deklariramo kot LOCAL, to pomeni, da je lokalno dostopna samo znotraj glavnega programa. Iz opisa simulatorja bo razvidno, da glavni program pri PARSYS Pascalu postane samo en proces v simulatorju, zato bo pojem "lokalna spremenljivka glavnega programa" razumljiv pojem. Spremenljivke deklarirane z besedo SHARED so globalno dostopne vsem procesom, proceduram in funkcijam znotraj programa in, kot je razvidno iz uvodne razprave tega podpoglavja, predstavljajo stalno nevarnost za pravilnost programov manj izkuBenih avtorjev paralelnih algoritmov. 3.2 ProooBl T V sekvenčnih programskih jezikih je inicira-r nje izvajanja- programske kode naloga mehwizmov operacijskega sistema. Poleg ukazov operacijskega sistema, namenjenih iniciranju izvajanja programa, nekateri sistemi dovoljujejo "zbujanje" (in izvajanje) programa o strani drugega programa, ki se trenutno iavaja. Pri paralelnih programskih jezikih se drugi program "zbuja" kot poseben proces (proces ali posel/"task" v smislu operacijskega sistema) pod kontrolo operacijskega sistema. Kontrola se takoj po zbujanju novega procesa vrne originalnemu procesu (očetu). Procesa od tega trenutka naprej živita skupaj. Pri paralelnih programskih jezikih programer v svojem programu uporablja ukaze za zbujanje (kreiranje, razmnoževanje) procesov, podobne ukazom operacijskega sistema. Zbujeni proces začenja "življenje" z izvajanjem svojega "glavnega programa" (proces more tudi imeti svoje procese...). Zbujanje novega procesa ima nekatere značilnosti. To so: - možnost prenosa mnoSice parametrov zbujenemu procesu in - KioanoBti sa koKiunikacijo in usklajevanje (sinhronizacijo) vseh "živečih" procesov. Očitno je, da pri (asinhronih) paralelnih programskih jesikih postajajo procesi, njihovo zbujanje in "sožitje" sestavni del programiranja. Vsi sbujeni procesi morajo po opravljenjem delu tudi zaspati. To se doseSe z izvrševanjem zadnjega ukasa v procesu. Ko se proces na ta naCin konc-a (in zaspi), postanejo vse njegove lokalne spremenljivke nedostopne. Konöani proces se ne more reaktivirati. Ce se s posebnim ukazom zbudi proces, ki ima isto programsko kodo kot Ze speci, ali pa Se delujoči proces, je to pomensko novi proces, z novimi lokalnimi spremenljivkami in neodvisnim delovanjem. Celotni paralelni program je zaključen, če so vsi njegovi procesi zaspali. Po končanem delovanju programa so vse lokalne, pa tudi skupne (globalne) spremenljivke nedostopne. Pri ponovnem izvajanju programa se vse spremenljivke ponovno inicijalizirajo, neodvisno od vrednosti, ki so jih imele v prejšnjem "2ivljenskem ciklu" programa. V navadnem Pascalu je program sestavljen iz glavnega programa ter mnosioe podprogramov (procedur in funkcij). Edini povezavi med podprogrami in glavnim programom sta seznam parametrov in delovanje nad skupnimi spremenljivkami. Kot je 2e rečeno. PARSYS Pascal ohranja osnovno zgradbo pascalskih programov, le da se poleg procedur in funkcij pojavljajo se procesi. Predprocesor razpoznava proces po njegovem prvem stavku, ki je po sintaktičnih pravilih enak začetnem stavku procedur, če se namesto rezervirane besede PROCEDURE, uporablja beseda PROCESS. Poglejmo nekaj primerov; PROCESS Producer; PROCESS Cel K x, y); PROCESS Suma(ProcID); Podobni stavki se nahajajo na začetku vsakega procesa. Iz primerov je razvidna tudi specifikacija seznama parametrov, ki se prenašajo procesu pri njegovem zbujanju. Za zbujanje procesov je v PARSYS Pascal vpeljan primitiv CREATEPROC. Primeri uporabe ukasa CREATEPROC, ki kreirajo procese z začetnimi stavki, navedenimi v prejsncm primeru ao: CREATEPROC Producer; CREATEPROC Celi ( i, j); CREATEPROC Suma ( z ); Semantična pravila za uporabo stavka CREATEPROC so enaka semantičnim pravilom pri klicu procedure v Pascalu. Število parametrov v CREATEPROC stavku in prvem stavku procesa mora biti enako, ujemati se morajo tudi tipi parametrov itd. 3.3 Medprooeona komunikacija V paralelnih programskih jezikih obstajajo različni mehanizmi za izmenjavo sporočil med procesi. V uvodu poglavja o PARSYS Pascalu sta omenjena dva načina za medprocesno komunikacijo. Eden je uporaba skupnih spremenljivk. Ta način je nevaren za pravilno delovanje paralelnega algoritma zato, ker pri paralelnem izvajanju vrstni red ukazov, ki spreminjajo vrednost skupne (globalno dostopne) spremenljivke, ni v naprej znan (ukazi se nahajajo v različnih procesih). PARSYS Pascal pa nima vgrajenih sploSno znanih mehanizmov za zavarovanje spremenljivk pred istočasno uporabo s strani več procesov (npr. semaforje ali monitorje). Zato se je priporočljivo izogibati tovrstni medprocesni komunikaciji. Bo]j varen in priporočljiv način za izmenjavo sporočil med več procesi je uporaba "postnih predalov" (mailbox). "Postni predali" pri PARSYS Pascalu predstavljajo pooeben podatkovni tip. To pomeni, da morajo biti podatkovni objekti (spremenljivke), namenjeni medprocesni komunikaciji, na začetku vsakega paralelnega programa eksplicitno deklarirani. Logično je tudi to, da so "postni predali", oairoma spremenljivke tipa SIGNAL, globalno dostopni tako glavnemu programu kot tudi vsem procesom. Deklariranje teh spremenljivk (v uvodu smo jim rekli tudi "kanali") v skupini skupnih spremenljivk (rezervirana beseda SHARED) omogoča, da morejo preko njih komunicirati vsi procesi. Spremenljivke tipa SIGNAL deklariramo na enak način, kot spremenljivke kateregakoli drugega tipa, na primer integer, real, boolean... Oglejmo si nekaj primerov: SHARED may_consume array may_produce: SIGNAL 1 .. 20 ] of SIGNAL ; Spremenljivke may„consume in may_produce so navadne spremenljivke tipa SIGNAL, enodimenzionalna matrika (vektor) A, pa je sestavljena iz 20 "postnih predalov". Spremenljivke tipa SIGNAL se uporabljajo za prenos obvestila o nekem dogodku med procesi. Pododek, ki ga je potrebno sporočiti ostalim procesom je najpogosteje dostopnost neke informacije. Proces pošlje sporočilo drugemu procesu, ki to sporočilo pričakuje in sprejme. Na ta način je dosežena sinhronizacija dveh procesov. Prenos se izvaja z uporabo ukazov SEND in RECEIVE. Ukaz SEND prepise sporočilo pošiljatelja v spremenljivko tipa SIGNAL. Iz te spremenljivke sporočilo prevzame nek drug proces, ki izvaja ukaz RECEIVE nad istim "postnim predalom". Pri tem je bistveno poudariti, da proces, ki pošilja sporočilo, načeloma ne ve, kdo bo sporočilo sprejel. Tudi proces - sprejemnik sporočila ne ve, kdo je pošiljatelj. Združuje jih samo ista spremenljivka tipa SIGNAL. Za semantično pravilnost izmenjave sporočil med procesi PARSYS Pascala torej skrbi izključno programer. Ukaz SEND se izvrSi tudi, če v spremenljivki tipa SIGNAL že obstaja neko neprebrano sporočilo. V tem primeru se novo sporočilo samo doda v "kanal". Sintaksa ukaza SEND pri PARSYS Pascalu je predstavljena a Bacuas Naurovo formo. := SEND (,>; ;= ::= 1 Primeri : SEND ( may_consume, i ); SEND ( A [i] , 10 ); Prvi argument ukaza SEND je spremenljivka tipa SIGNAL, drugi pa je celo Število ali spremenljivka celoštevilčnega tipa (integer). Tudi ta omejitev PARSYS Pascala naj bi bila v bližji prihodnosti odpravljena. Ukaz RECEIVE se uspeSno izvrSi samo, če je podatkovni objekt tipa SIGNAL poln, oziroma, če je kateri od procesov že poslal potrebno sporočilo procesu, ki izvaja ukaz RECEIVE za nadaljevanje dela. Ce sporočilo do trenutka izvajanja ukaza za sprejem ni poslano, se proces sprejemnik ustavi, ker je nadaljevanje dela brez informacije, ki je del sporočila, nemogoče. Ce pa v "postnem predalu" čaka več sporočil, proces sprejemnik naključno izbere eno izmed njih. Razumevanje tega principa naključne, popolnoma nedeterminirane izbire sporočila je eden bistvenih pogojev za sestavljanje pravilnih paralelnih algoritmov. Opis dejanske izvedbe ukazov SEND in RECEIVE bo predstavljen pri opisu simulatorja paralelne programske opreme v poglavju 4. Primeri uporabe ukaza receive: RECEIVE ( may_rjonaume , Index ) ; RECEIVE ( A. [ij , Value ) ; Podani primeri izkasujejo enega od možnih naöinov za sprejem sporočil med primeri za ukaz SEMD. Index in Value pri PARSY3 Pascalu morata biti spremenljivki tipa integer, A i in may_c-onsume morata biti tipa signal. 4. SIMULACIJA PARALELNE PROGRAMSKE OPREME. Paralelno procesiranje omogoOa velike časovne pridobitve pri izvajanju velike skupine aplikacij. Navedena trditev je sploSno veljavna, postavlja pa se vprašanje, kako oceniti te pridobitve pred dejanskim izvajanjem i .-ograma na nekem veCprocesorskem ali paralelnem računalniku. Prvi način sa ocenjevanje časovnih .pridobitev je izpeljava natančnega matemati'nega modela. Slaba stran tega pristopa je, da vsaka aplikacija potrebuje poseben pristop k modeliranju, natančen matematični model za zahtevne aplikacije pa je dokaj težko izdelati. Drugi pristop, ki je uporabljen tudi v tem delu. je izgradnja simulatorja za vzporedne programe, ki obenem tudi vrednoti časovne pridobitve nastale kot posledica paralelnega procesiranja. Simulator ni vezan samo na eno, natančno speoifirrirano paralelno arMtekturo. Omogoča pa, da se v času izvajanja določajo arhitekturni parametri -značilni za-posamezne računalnike (na primer število procesorjev). Z manjšimi spremembami bi! bilo brez te2av mogoče i.zbolj&ati simulator- tako, da bolj precizno vrednoti izvajanje vzporednih programov na arhitekturi striktno določenih parametrov. Simulacijski program v času izvajanja nekega vzporednega programa (napisanega v Se predstavljenem -jeziku PARSYS Pascal) zbira Številne parametre, kot so na primer koeficient upoiabe posameznih procesnih elementov in podatki o medprocesni komunikaciji, otevilrj procefiorrjk i h elementov dol.oči-tiio tia' začetku izvajanja, po potrebi ga v različnih tekih simulatorja spreminjamo in iz zbranih parametrov sklepamo o povezanosti parametrov algoritma in parametrov sistema. Ha podoben način sklepamo tudi na osnovi- podatkov o času izvajanja posameznih procesov itd. Algoritem za, simulacijo siòni na maksimalnem izkoriščanju vzporednosti pri izvajanju programov. 2e v prvem podpoglavju bo razvidno, da algoritem za dodeljevanje procesorjev posameznim procesom izbira novi, do tega trenutka ne uporabljeni procesor samo v primeru, če so vsi ostali procesorji v trenutku dodeljevanja ("scheduling") zasedeni. Zato je očitno, da pri določenih aplikacijah ne bodo uporabljeni vsi "ponujeni" procesorski elementi. Z drugimi besedami povedano,' Število uporabljenih procesorjev predstavlja največje Število istočasnih aktivnosti, ki jih zahteva testirani vzporedni program. Pri opisu PARSYS Pascala je rečeno, da se za sinhronizacijo procesov uporablja tehnika izmenjave sporočil. Razlog za ta izbor je bil prilagojenost te tehnike večprocesorskiin računalnikom s skupnim portifii Ini kom in računalniškim mrežam,, ter njena razširjenost. Dovoljena je tudi up'oraba skupnih spremeri 1 jivk. Procesi komunicirajo skozi■kanale. Več procesov more izkoriščati en kanal za pošiljanje svojih sporočil. Enaka je situacija tudi na izhodni strani kanalov, kjer več procesov pričakuje sporočila iz istega kanala. Ampak eno sporočilo more prebrati samo en proces, oziroma z enim sporočilom je "zbujen" samo en proces med tistimi, ki so sporočilo pričakovali iz določenega kanala. Simulator na grobo opisanih karakteristik je razvit v visoko nivojskem programskem jeziku. izvaja pa se v enoprogramskero okolju. Razvoj je potekal na računalnikih Delta Partner (operacijski sistem CP/M) in Triglav pod operacijski® sistemoia XENIX. Zato je uporabljen programski jezik Pascal, ki je dostopen na obeh računalnikih. V kratkem easu bo simulator dostopen na IBM PC AT in kompatibilnih računalnikih pod operacijskim sistemom DOS. Simulator deluje na enoprocesorskih, opisuje pa dogajanja v veöprocesorskih računalnikih. Zato. je nujno pred detaljnim opisom posameznih delov simulatorja, opisati algoritem za simulacijo in dokazati njegovo pravilnost. 4.1 Simulacijski algoritem Predpostavlja se, da moramo simulirati izvajanje množice procesov na računalniku z omejenim Številom procesorjev. Vsak proces se sme izvajati na kateremkoli procesorskem elementu. Ce ima simulirani sistem samo en procesor, potem se istočasno izvaja največ en proces, problemov pri simulaciji pa ni. Za simulacijo istočasnih dogodkov v sistemu z veCimi procesorji moramo specificirati koncept "vodenja časa" v simulatorju. V spremenljivki T vsakega procesa (lokalno) je shranjena ura. Procesi se izbirajo za izvajanje en za drugim, in njihova ura se postavi na čas, v katerem naj bi se proces zaCel izvajati v realnem veCprocesorsken aistemvi. Vsakič, ko se izvrSi ena operacija, se uri prišteje količina čaša, potrebna za izvajanje te operacije na simuliranem računalniku. Sinhronizaciji med procesi (komunikacija in kreiranje) je pridružen čas T, (trenutno starije spremenljivke) v katerem jo izvedena. Procesi Za vsak proces i je shranjena informacija o njegovem statusu ("ready" ali "waiting"). Spremenljivka BT{i) (Block Time) predstavlja čas, ko je proces zadnjič priSel.v stanje "waiting". RT(i) (Ready Time) je spremenljivka, v kateri jo shranjen čas, ko je proces postal pripravljen (če je v stanju "ready"). RT(i) se po navadi postavi na čas dogodka, ki zbudi proces i, BT(i) pa je dejansko spodnja meja za RT(i) (dogodek, ki se zgodi pred BT(i) povzroči, da proces postane "ponovno pripravljen" v trenutku BT(i), torej proces v tem primeru dejansko sploh ni bil blokiran in ustavljen). Vsi pripravljeni ("ready") procesi so členi vrste, ki je urejena po naraščajoči vrednosti spremenljivke KT(i). Proces kreiran v trenutku T postane pripravljen na naslednji nacin: RT(i) BT(i) := T; (1.1) Dogodek v trenutku T, na katerega je Čakal čakajoči (blokirani, "waiting") proces i, povzroči naslednjo spremembo Caso-vnih spremenljivk: RT(i) max ( T, BT(i) ); (1.2) Ce proces i ni bil v stanju "waiting", potem se RT(i) spremeni v skladu z izrazom (1.2) samo, če je bil prejSnji.,RT(i) večji od T (RT(i) > T). Proces se glede na nastalo spremembo RT(i) postavi v vrsto pripravljenih dogodkov. Procesorji Vsak procesor je opisan z dvema vredno-stima. ST(k) (Stop Time) je trenutek, v katerem je procesor zadnjic bil ustavljen; WT{k) (Working Time) je akumuliran Cas delovanja procesorskega elementa. WT(k> se uporablja samo sa vodenje statistike o procesorjih. Simulacijski algorit-em Naj bo j indeks pripravljenega ("ready") procesa in Kj množica procesorjev, ki so v tem trenutku prosti. TSj bo prvi trenutek (najnižji čas), v katerem se more proces j zaCeti izvajati. Potem velja TSj = max { RT(j) , ST(k) ) (2) pri Cerner je k procesor iz množice Kj, za katerega velja: - k je najnižji indeks pri katerem velja ST(k) < RT(j) (2.1) ali. Ce pogoj (2.1) ne more biti izpolnjen - ST{k) < ST(h) , za vsak h element množice Kj (2.2) Proces i je izbran za izvajanje. Ce velja - TSi <= TSj za vse j : { proces j je v stanju "ready"). (3) Vrednost spremenljivke T se pri ponovnem aktiviranju procesa postavi na TSi. Izbrani (navidezni) procesor, na katerem se proces i izvaja, ustreza pogojem (2.1) in (2.2). V Času izvajanja procesa (execution time) se T inkre-mentira na že opisani naCin in ima tako funkcijo lokalne, realne ure (veCprocesorskega sistema). Ko se proces ustavi (blokira) ali .konCa v trenutku Tb, morajo biti izvedene naslednje spremembe vrednosti spremenljivk; - BT(i) •-= Tb pomnjenje vrednosti ustavljanja procesa, (4.1) v trenutku - ST(k) := TB (4.2) pomnjenje trenutka, v katerem je procesor postal prost, - WT(k) := WT(k) + (Tb - Ts) (4.3) zbiranje delovnega Casa posameznega procesorja. V slučaju, da proces začenja svoje simulirano življenje (izvajanje) v trenutku Ts, opisani algoritem zagotavlja, da ao vsi dogodki pred Ts že simulirani. Dokaz : Predpostavili bomo, da je prvi proces pos'^al pripravljen za izvajanje ("ready") v trenutku T0 in da so vsi dogodki pred T0 simulirani pravilno. To je gotovo prav na začetku vsake simulacije, ko je množica procesov že kreirana, noben od njih pa se Se ne izvaja. Proces i se izbere za izvajanje po pravilu (3), TSi po definiciji ne more biti manjsi od T0. Dodatni dogodki, ki bi spremenili stanje simulacije se ne morejo zgoditi pred TSi zato, ker ni procesa, pripravljenega za izvajanje, ali ni procesorja, na katerem bi se pripravljeni proces izvajal. Proces i se začenja z izvajanjem v trenutku TSi in do trenutka Tb, v katerem se bo konCal, izvede vse zalitevane operacije. V trenutku Tb je proces RonCan ali pa Caka dogodek/sporocilo na nekem kanalu in zato spremeni stanje ("waiting"). Tretja možnost je, da je ustavljeni proces takoj postavljen nazaj v vrsto pripravljenih procesov, zato ker je bil dogodek, potreben za nadaljevanje dela procesa, generiran pred Tb. Predpostavimo, da je TSj trenutek, v katerem se je zaCel izvajati naslednji proces. TSj je po pravilu (3) veCji ali enak TSi (TSi <= TSj), proces i pa je edini proces, ki je mogel generirati dogodke med TSi (T0) in TSj. Potem so vsa dogajanja pred TSj pravilno izvedena, stanje simuliranega sistema pa je enako stanju opisanem na saCetku tega dokaza. Ce s istim premislekom nadaljujemo do trenutka, ko so vsi procesi konCani, potem je pravilnost simulacijskega algoritma dokazana. 4.2 Opis procedur aimul&torja V skupini procedur, ki izvajajo "ukaze" PARSYS Pascala, sta do sedaj največkrat omenjeni proceduri SEND in RECEIA^. To sta tudi najbolj pomembni proceduri za razumevanje implementacije simulacijskega algoritma. Zato bosta opisani v posebnih poglavjih (4.2.1 in 4.2.2). 4.2.1 Prooedura send Klic procedure send vsebuje dva parametra. Prvi parameter je "postni predal" (mailbox), na katerega naj se sporočilo posije, drugi parameter pa je kazalec na sporofillo (messale), ki se pošilja. V proceduri send so opredeljene vse akcije, ki se izvedejo pri oddajanju sporofiila v izbrani "kanal". Procedura send deluje na osnovi nasednjega algoritma. 1. Preveri, ali obstaja etikajoCi proces v polju mailbox.pcbs 2. Ce obstaja, potem nadaljuj s korakom 3.1, sicer skoCi na 4.1 3.1. Ce proces prihaja v mailbox ravno v tem trenutku, ga počakaj 3.2. Kazalec delay v procesnem kontrolnem bloku postavi na .sporočilo 3.3. Kazalec, ki je v polju CakajoCih procesov (mailbox.pcbs) kazal na izbrani proces, postavi na NIL 3.4. Pravilno določi Cas za nadaljevanje delovanja procesa ( spremenljivka t_ready se postavi v skladu s postopkom opisanim v poglavju 4.1) 3.5. Poklici jedro simulatorja, da postavi proces v vrsto "pripravljenih" procesov" (polje ready) 3.6. SkoCi na korak 5 4.1, Poieci prvo prosto lokacijo v polju sporočil (mailbox.msga) 4.2. Ce je polje sporoCil polno, potem počakaj 4.3. Na prosto lokacijo v vrsti sporočil postavi sporočilo (message) 4.4. Postavi vrednost spremenljivke message.t_Bend na Cas, v katerem je sporočilo poslano 4.5. Sortiraj polje sporoCil v "kanalu" (mailbox.msga) po naraSCajoCi vrednosti spremenljivke message.t_8end 5. Konec. 4.2.2 Funkcija reoeiv« Naloge funkcije (ali "ukaza") receive so bile v predhodnih poglavjih pogosto opisane. Zato bom sedaj podal samo naöin njene izvedbe. Funkcija receive je tipa boolean in ima samo en parameter. To je "kanal", v katerem proces, ki Seli sprejeti sporočilo, to sporočilo iace. Kot v primeru procedure send, bom opisal algoritem delovanja funkcije receive. 1. Preveri, ali obstaja sporočilo, ki caka v "postnem predalu" (mailboxu) 2. Ce obstaja, nadaljuj s korakom 3.1, sicer skoCi na 4.1 3.1. Ce sporočilo • prihaja ravno v tem trenutku, ga počakaj 3.2. Vsebino sporočila prepisi direktno v spremenljivko CPU_receive_reg (aato, ker se proces, ki izvaja funkcijo receive v tera trenutku procesira) 3.3. Kasaleo, ki je v polju čakajočih sporočil mailbox.msgs> kazal na izbrani proces, se postavi na MIL 3.4. Vrednost funkcije receive postane TRIJE 3.5. Skoči na & 4.1. Postavi proces, ki izvaja funkcijo receive v stanje "WILL_SOSPEND" (to je oznaka, da bo proces v bliSnji prihodnosti verjetno zaključen ali blokiran) 4.2. 4.3. Preveri se enkrat, sporočilo če obstaja Ce je med prvim in drugim preverjanjem prišlo sporočilo, potem nadaljuj s korakom 4.3.1, sicer skoči na 4.4 4.3.1. Postavi proces v stanje "RUNNIMG" 4.3.2. Skoči na 3.1 4.4. PoiSči indeks proste lokacije v polju mailbox.pcbs 4.5. V prosto lokacijo postavi kazalec na kontrolni blok procesa 4.6. Na novo določi vrednosti časovnim spremenljivkam v procesnem kontrolnem bloku (na način, ki je opisan v poglavju .^.1) 4.7. Uredi polje čakajočih procesov po naraščajoči vrednosti spremenljivke t_block 4.8. Pokliči jedro simulatorja, ki spremeni stanje procesa v "SUSPEND" in na procesorju opravi spremembo konteksta (context switch) 4.9. Vrednost funkcije receive postavi na FALSE Konec 6. VREDNOTENJE VZPOREDNIH PROGRAMOV tega dela do zadoSöal faktor pohitritve SÜ (Speed Up), ki je definiran na naslednji način: SU i, j = T i / T j (6) Faktor pohitritve je kvocient Casa (simuliranega) izvajanja programa na i-tih in izvajanja programa na j-tih procesorjih. V podpoglavjih, ki sledijo, bo vedno veljala naslednja relacija: j = 2 * i (6) Zato je SU i,j zmeraj med 1 in 2. Z dvakratnim zvišanjem Števila procesnih elementov se hitrost izvajanja nikakor ne more zniaati. Z druge strani pa je največja moSna pohitritev izvajanja, sicer samo teoretično dostopna,^ dvakratna, zato je SU i,j z gornje strani omejen z 2. 5.1 Enostavni algoritem za vaporedno sortiranje Sekvenčni programi, ki uporabljajo različne metode za sortiranje polj, imajo časovno 2 zahtevnost med O(n)*log (n) in 0( n 2 Vzporedni algoritem, ki sledi, pa ima časovno zahtevnost n / 2, torej reda 0(n). Ime mu je sodo - liho urejanje (Odd - Even Sort) in spominja na sekvenčno urejanje z mehurčki (Bubble Sort). Osnovni cikel urejanja po metodi sodo - liho je naslednji: vsak proces v začetku delovanja programa dobi identifikator. Vsi procesi z lihim identifikatorjem (zaporednim številom, TasklD) dobijo tudi dve "Žogici". To je oznaka, da morejo zamenjati Število iz polja A (polje, ki ga je potrebno sortirati), ki ima indeks TasklD, s Številom A [TaskID+1 ] , če je A [tasklD] < A[TaskID+l]. Potem proces z lihim identifikatorjem posije (SEND) svoji Sogici sosednjim (sodim) procesom. VseJi proces s sodim identifikatorjem ima 2 liha soseda, tako da dobi dve 2ogici in more zamenjati Število A TasklD z A TaskID+1 . Ko je ta operacija konCana, se aogioi spet pošljeta (lihim) sosedom, ki tako nadaljujeta delo. Ce neki proces nima dveh sosedov (prvi in zadnji) potem 2ogioo soseda, ki manjka, pošilja sam sebi. V naslednjem koraku pa ne more biti aktiven, ker ima samo eno Sogico, za aktivnost pa potrebuje dve.Za sortiranje polja bo potrebno največ n/2 (navzgor omejeno celo Število) opisanih korakov, ki so prikazani tudi na sliki 3. Program Odd_Even_Sort, ki deluje na opisani način je napisan v programskem jeziku PARSYS Pascal. Algoritem uredi 16 Števil (MAXID = 16), časi simuliranega izvajanja za različno Število procesnih elementov pa so naslednji : 'PE SU Tema sadnjega poglavja je vrednotenje različnih vzporednih algoritmov. Vrednotenje programske opreme je zelo Širok pojem. Zato je potrebno opredeliti pristop k vrednotenju, ki bo uporabljen v tera poglavju. Vzporedni programi bodo vrednoteni na osnovi časovnih pridobitev, ki izhajajo iz spremembe (zvišanja) Števila procesorjev, na katerih se program izvaja, oziroma bolj sploSno, iz prilagojenosti algoritma določeni računalniški konfiguraciji. Poleg spreminjanja Števila procesnih elementov, kar omogoča simulator vzporednih programov opisan v predhodnem poglavju, bo izvedeno tudi . eksperimentalno ugotavljanje pohitritev izvajanja vzporednih programov v odvisnosti od velikosti (granularnosti) posameznih procesov vzporednega algoritma. Pri ocenjevanju časovnih pridobitev, ki izhajajo iz simuliranega izvajanja vzporednega programa na različnem Številu procesnih elementov, • je potrebno določiti primerno mero. Za namene ì 464 2 ps 1.97 4 121 1.94 8 66 1.83 16 48 1.38 KPE je število procesnih elementov pri simuliranem izvajanju programa,' T so časi teh izvajanj, SU pa je faktor pohitritve izračunan po formuli ( 1 ). Pri spreminjanju Števila procesorjev od 1 do 8 je SO skoraj idealen. ManjSa rast hitrosti izvajanja pri spreminjanju UPE od 8 na 16 je tudi razumljiva, ker je iz opisa algoritma razvidno, da se istočasno izvaja n/2 zamenjav Števil v polju A. V primeru, ko imamo 16 procesorjev, je velik tudi vpliv časa za spreminjanje konteksta (context switch time) na 52 la) motna zamenjava itevil P J ----------P2 P3 — P4 P5 P6 'b) PI P2 --- P3 2a) Pl --p2 P 4 -P3 p^ ■P4- PS ■P6 Slika 3. Prikaz algoritma za vzporedno sortiranje vsakem procesorju, zato je faktor SU manjši 8, 16 od predhodnjih. 6,2 Algoritem za seštevanje v logaritmiOnem Času V primeru algoritma za sortiranje srao si ogledali samo vpliv ene komponente raC-unalniSke konfiguracije na oas izvajanja vzporednega programa. Sedaj bo predstavljen algoritem za seštevanje množice Števil v öasu proporcionalnem dvojiskem logaritmu Števila sumandov. Pri se-kvenir:riih algoritmih za seštevanje n Števil je potreban Cas reda 0(n) (vsoti predhodnjih se prišteje naslednje Stisvilo). Ideja vzporednega seStevatijü n Števil sloni na lastnostih komuta-tivnocti in asociativnosti seštevanja. [