Informatica
A Journal of Computing and Informatics
The Slovene Society ÌNFORMATIK4 Ljubljana
A Journal of Computing and Informatics
\ :
Subscription Information
Informatica (ISSN 0350-5596) is published four times a year in Winter, Spring, Summer and Autumn (4 issues).
The subscription price for 1992 (Volume 16) 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 Tomi Pretnar, Bratov Kemel 52, Ljubljana.
Informacija za naročnike
Informatica'(ISSN 0350 - 5596) izide štirikrat na leto, in sicer v začetku marca, junija, avgusta in novembra.
Letna naročnina v letu 1992 (letnik 16) se oblikuje z upoštevanjem tečaja domače valute in znaša okvirno za podjetja DEM 30, za zasebnike DEM 15, za študente DEM 8, za posamezno številko pa DEM 10.
Številka žiro računa: 50101-678 - 51841.
Zahteva za izgubljeno številko časopisa se upošteva v roku šestih mesecev od inda in je brezplačna.
Tisk: Tiskarna Tomi Pretnar, Bratov Komel 52, Ljubljana.
Na podlagi mnenja Ministrstva za informiranje št. 23/216 - 92, z dne 27.3.1992, šteje znanstveni časopis Informatica med proizvode informativnega značaja iz točke 13 tarifne šte\alke 3, za katere se plačuje davek od prometa proizvodov po stopnji 5%.
Pri financiranju časopisa Informatica sodeluje Ministrstvo za znanost in tehnologijo, Slovenska 50, 61000 Ljubljana, Slovenija
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 16 Številka 3 Avgust 1992
ISSN 0350-5596
Informatica
časopis za računalništvo in informatiko
VSEBINA		
Basic Informational Axioms	A.P. Železnikar	1
Integrity in the Relational Data Model	M. Radovan	17
Understandability of the Software Engineering Method as an Important Factor for Selecting a CASE Tool	I. Rozman J. Gyorkos K Rizman	25
O preslikavi HADFG na TAS	P. Zaveršek P. Kolbezen	29
Predvidljivo dinamični princip razvrščanja opravil v realnem času	Barbara Koroušić P. Kolbezen	36
Sinhronizirana podatkovno pretokovna računalniška arhitektura II	J. Šile L. Gyergyek	46
An Informational Approach of Being-there as Understanding III	A.P. Železnikar	64
Novice in zanimivosti: Različne novice Compulog NoE ... Statut Slovenskega društva Informatika	Nada Lavrač	76 76 78 81
BASIC INFORMATIONAL AXIOMS*
INFORMATICA 3/92
Keywords: axiomatization, circularity, externalism, functionalism, informational axioms, intelligent informational entity, internalism, metaphysics, parallelism, phenomenalism
Anton R Železnikar Volaričeva ulica 8, 61111 Ljubljana
Slovenia
This essay brings an approach to the possibilities of axiomatization in the realm of the informational. The axiomatization begins from the informatio prima which says that entities inform or, formally, a (=. This primary postulate causes logical consequences which are comprehended as extensions of the primary axiom of informing of enti ties (informing as extemalism, informedness as internalism, circularity as metaphysics, and informational openness as phenomenalism). A consequent axiomatic deduction (together with operational particularization) is shown for general, alternative, negative, alternative negative, functional, metaphysical, parallel, and intelligent informational cases. Informational axiomatization is a part of the informational logic in which the notion of information is extended to the phenomenal extremity. Axioms are expressed by the formalized symbolism which considers the concept of the informing/informedness (active/passive, subjective/objective, operand/operator) nature of informational entities [TIL].
Osnovni informacijski aksiomi
Ta spis prinaša nekatere možnosti aksiomatizacije v domeni informacijskega. Postopek aksiomatiziranja se začenja pri t.i. informatio prima, ki govori, da bivajoče informira, ali formalno a \=. Ta prvi postulat povzroča logične posledice, ki jih razumemo kot razširitve prvotnega aksioma informiranja bivajočega (informiranje kot eksternalizem, informiranost kot intemalizem, cirkulamost kot metafizika in informacijska odprtost kot fenomenalizem). Pokazana je dosledna aksiomatska dedukcija (skupaj z operacijsko partikularizacijo) za splošni, alternativni, negativni, alternativno negativni, funkcijski, metafizični, paralelni in inteligentni informacijski primer. Informacijska aksiomatizacija je le del informacijske logike, kjer je pojem informacije razširjen do skrajnih pojavnih meja. Aksiomi so izraženi s formaliziranimi simboli, ki upoštevajo koncept informiranja/informiranosti (aktivne/pasivne, subjektivne/objektivne, opernadne/operatorske) narave informacijskih entitet [TIL].
*This essay is a private author's work and no part of it may be used, reproduced or translated in any manner whatsoever without written permission except in the case of brief quotations embodied in critical articles.
0. Introduction
...das Mathematische will sich selbst, im Sinne seiner eigenen inneren Forderung, begründen; es will sich selbst ausdrücklich als Maßstab allen Denkens herausstellen und die daraus entspringenden Regeln aufstellen.
—Martin Heidegger [FND] 78
Nowadays, the background of informational reasoning seems to be more or less forgotten, fallen into oblivion, but also unrevealed and still subconscious. The broadened notion of information [Owi] was the initial step to this recognition in which formal principles and their consequences have been brought to the reader's consciousness.
To develop a broadened and complete theory of information and informational phenomenology,
an exhaustive axiomatic background of informing of entities is needed, on which the arising phenomenalism, scenery, processibility and, lastly, formalism can be built up. This step is necessary not only with the aim to broaden the scope of informational cognition, but also to prepare the basis for-the future development of that what we call the informational machine. The reader must be aware that informational axiomatization, in opposition to the known mathematical one, is a continuum in which a new axiom or theorem can always arise between two already existing ones. Informational continuum appears as an infinitesimal realm of information and an informational theory is never developed to an end, staying open for further change, improvement, and broadening. In this essay we shall discuss these assertions among several others.
Axioms are formal principles which arise from the principal position and attitude of the logical mind. Informational axioms—among others, for instance, mathematical ones—are the most general and can absorb any thinkable axiomatic concept and include it appropriately into the observed informational system. This is a hypothetical assertion which can always be proven from one concrete case to another. The informational seems, at best, to be the most adequate principle of the universe. We shall try to give a principled explanation of this assertion at the end of the essay.
Our way to the realm of axiomatic scenery of the informational must begin with some very basic assertion, which could be called ìnformatìo pnma.. Afterwards, axioms, logical consequences, and theorems can arise in a logically spontaneous, however, systematized way. Let us open this realm of cognition in the next section of the essay.
1. Basic Axioms
Der Grundzug muß in jenem bestehen, was die Grundbewegung der Wissenschaft als solcher gleichursprünglich maßgebend durchherrscht: es ist der Arbeitsumgang mit den Dingen und der metaphysische Entwurf der Dingheit der Dinge. Wie sollen wir diesen Grundzug fassen?
—Martin Heidegger [FND] 52
As in any axiomatic system, some basic questions prevail: Where is the origin of the informational
axiomatic system? Which is the first, most nauiral axiom, from which other axioms and consequences arise in a possible, logical, and systematic way?
As the so-called informatio prima of any logic the following could be asserted: Entities inform. If something (an entity figuring as the operand) is marked by a, we can say that oc informs. This statement, consciously or unconsciously, pri-mordially constitutes the first principle of any theory and can be expressed symbolically by
(1)

This axiom is informatio prima and pertains to any entity, that is, operand, marked by a. The axiom is expressed in the implicative form, using informational operator of implication, which is read as »implies (that)« from the left to the right, and as »is implied by« from the right to the left of formula (1). In the same way, operator \= is read »informs« in the one, and »is informed by« in the other direction. Thus, for formula (1) we have the following explanations: Entity a implies that it informs. Entity a implies that something (the empty place on the right of operator [=) is informed by it. Anytime and anywhere we have or there is an entity a, it informs (oc
One of the very essential comments to axiom
(1)	is that its formula is circular in respect to entity a. (operand a. occurs on the left and on the right side of operator The other comment is, that a. as an informing entity, transmits (operator on the right of operand a) its phenomenality into the informational universe.
The first axiom induces consequences which can still be understood as axiomatic. Namely, if we adopt the fact of this axiom, that »if a, then a informs«, then probably something—some other or the same entity—must and can be informed. To inform without to be informed would not have any particular sense in the realm of the informational which is the universe of informing (phenomenaliz-ing) of information (phenomena). Thus, the second most fundamental axiom is coming to the surface, as
(2)
We can show the basic way to this axiom from the first axiom and vice versa by the following asser-
tion: if a informs, then something (a, ß, ...) would be informed. This fact yields
(3)

which is a consequence of axiomatic character. Further by a similar logical reasoning, which says, that if something is informed, there exists, sometime and somewhere, an informing entity a, thus,
(4)

The last two axiomatic consequences can be certainly interpreted more universally, by introduction of different entity markers a, ß, y, ... . So,
(3')	•••)
(4') (t=a)^(a,ß,r,-N)
These consequences explicate the openness of the informational universe in respect to the informing and informedness of an entity a, where it can inform and be informed by several entities (operands), simultaneously.
To remain strictly consequent, axiom (2) follows from axiom (1) in the way
(5)
(a (a \=)) ^ (t= a)
or logically, even more exactly, (6)
As already mentioned, in axiom (1) and its consequences the property of a's circularity is hidden. Formula (1) is evidently implicatively circular in respect to a, since operand a stands on the left and on the right side of operator Together with formula (1), also formulas (2) to (6) are perplexedly a-circular. This circularity is of especial interest in case of formulas (3) and (4), since they enable to conclude on a's particular informing which we call metaphysics of entity a. The initial state of a's metaphysics is expressed by formula
(7)
a (a 1= a)
This formula reads: a implies that a informs a and is informed by a. Or, in general, an entity informs (impacts) itself and is informed (impacted) by it-
self. Formula (7) is a consequence of both formulas (3) and (4), that is,
(8)

where the so-called metaphysics follows from the circularly tied informing and informedness of a and
(9)
where metaphysics is a consequence of simultaneous, cyclically tied informedness and informing of a. Last two formulas conceptualize the circular or cyclic nature of an informational entity (operand, also informational formula) a.
The next essential consequence in the framework of informatio prima follows directly from both axioms (1) and (2). This consequence speaks that an entity informs and is informed simultaneously, that it is the informational system of an entity's informing and informedness. Thus, at the end of such concluding, there is,
(10)	a[=(a^;^a)
This formula is not only the most general, but also the most open expression pertaining to entity a and its environment, to a's phenomenality in space and time. It makes evident that a will inform some, yet unidentified entities and itself in the form a [= and that it will be informed by some, yet unidentified entities and itself in the form [= a. It is evident that both formulas a and a are completely open, having the operand empty place on the right and on the left side of operator [=, consequently.
The next question concerns the informational spontaneity of an informing entity. How does spontaneity concern the basic axioms?
Within a\=, entity a informs in a spontaneous way. Spontaneity is the axiomatic property of operand a as well as operator Informing of any informational entity a is spontaneous within the a's -informational cycle which is constituted by informing, counter-informing, and embedding of information. Further, in a operator \= is particularized in a concrete case and marks only different possibilities of a's operating potentiality.
Formulas a \= and (= a depict phenomenalit-ies of one and the same entity a. They express
possibilities of a's informational impacting and impactedness, that is, to impact the world and to be impacted by the world. The impacting and impactedness of an entity is spontaneous, uncertain and, in general, indeterminable. The spontaneity of a's informing can be understood through its metaphysics, a\=oc, which can be informationally decomposed by different observers in different (spontaneous) ways.
After this discussion we can summarize the four basic implicative axioms {informatìo prima) pertaining to an informational entity a, as follows:
(11)	(1°)	«=>(«(=) [extemalism of a] (2°)	a ([= a) [intemalism of a] (3°)	a (od 1= a) [metaphysics of a] (4°)	a (a 1= a) [phenomenalism
of a]
Let us have the following dictionary of the primary four informational cases of informing:
(12)	(1 °) a [=: external informing of a;
a's informational impacting; a's informing (informingness) (2°) 1= a: internal informing of a; a's informational impactedness; a's informedness (3°) a 1= a: metaphysical informing of a;
a's metaphysical circularity; a's informational metaphysicalness (4°) a }=; t= a: phenomenal informing and informedness of a; a's informing and informedness phenomenality; a's complex phenomenalism
There are different modes of general informing and it is possible to make a rough classification in the following sense:
general informing: operator \=; alternative general informing: operator negative general informing: operator alternative negative general informing:
parallel general informing: operator |[=; parallel alternative general informing: operator =11;
parallel negative general informing: operator
parallel alternative negative general informing: operator
cyclic general informing: operator f—; cyclic alternative general informing:
operator -|; cyclic negative general informing: operator
cyclic alternative negative general informing: operator
parallel-cyclic general informing:
operator |[-; parallel-cyclic alternative general
informing: operator -j|; parallel-cyclic negative general informing:
operator |(/; parallel-cyclic alternative negative general informing: operator /||
To all these cases the so-called subscribed informational operators can be added. A subscript (for instance, subs) means an operational particulariza-tion or universalization. Thus, such operators are:
Nsubs> Hsubs' Msubs' ?Nsubs' INsubs» HIsubs» It^^subs' ?1lsubs' h~subs' Hsubs' f/subs' /Hsubs» ll~subs> Hlsubs» il/subs' /llsubs
and, certainly various operators of the type
'—subs' —Jsubs' 'subs» I subs» '^siibs' ^siibs» ""'subS' ^subs' *^subs» *^subs' =subs> ?^subs» —subS' ^subs» ^subs> ^subs' "subs» ^subs' ^subs' '-subs' ^suos' ^subs> °subs'
etc. with particular meanings.
We may not forget that all operators (arbitrarily universalized or particularized) used within informational logic are informational. Informational operators are attributes (properties, phenomenalities, happenings, predicates) belonging to the informing and informed entities (operands, formulas, formulas within formulas) and connecting them informationally. The direction (operational orientation or directionality) of operators depends on the verbal definition of a particular informational operator. For instance, in their
simple present tense, some verbal forms as »informs«, »inclüde«, »operates«, etc. are oriented from the left to the right operand, while others, for instance, »observes«, »understand«, »conceives«, etc. are oriented from the right to the left operand. Thus, we can distinguish externally and internally oriented operators as determined by simple present tense of verbs. Operands are marked informational entities which are single Greek or Frakmr symbols or formulas composed of operands, operators, parentheses, commas, and semicolons. We shall show the syntactic structure of informational formulas later on.
2. Alternative Basic Axioms
Zum Wesen des Mathematischen als Entwurf gehört das Axiomatische, die Ansetzung von Grundsätzen, aus denen alles Weitere in einsichtiger Folge gründet. Wenn das Mathematische in Sinne einer mathesis universalis das gesamte Wissen begründen und gestalten soll, dann bedarf es der Aufstellung ausgezeichneter Axiome.
—Martin Heidegger [FND] 79
We are interested to have explicit alternative possibilities to the discussed basic axioms with the aim to be able expressing explicitly the possible alternatives in each particular case as well as'on the most general level. Alternative axiomatic alternatives pertain also to the principle of informational spontaneity and to other possibilities of informing, for instance, to negative informing or non-informing, parallel, serial, cyclic, parallel-cyclic informing, etc. How it is possible to express alternative informing in cases of the most general and particular informing?
The alternative possibility of informing speaks in favor of the ability to express simultaneously the case of basic (in general |=-opera-tional) and alternative (^^-operational) informing. We say that an entity informs in one (basic or general) or another (alternatively basic or general) way. How to mark the so-called other case?
In general, entity a informs and is informed in this and that way. It informs alternatively and such simation can be expressed symbolically
The differences between formula (1) and (1 ) are the following:
(i)	Operators and =| are counter-oriented, for instance, operator \= is the left-right and operator =1 the right-left symbol. Through this we can read formula a as a informs and formula =1 a.as a informs alternatively (in respect to the case a (=).
(ii)	Simultaneously, operators \= and =] are dual to each other in the sense of informing and informedness of an entity. For instance, if a means a informs, then <x would mean a is informed (alternatively). We can read operators (or formulas) strictly from the left to the right side. This possibility of reading is important for the distinguishing of verbal cases in which something impacts (is impacting) something informationally and something is impacted by something informationally. The following meanings of informational operator duality can be used:
operator type ^	operator type
informs	is_informed(_by)
is informing	is_being_informed(_by)
informed	has/have_been_
	_informedCby)
has/have_been_	has/have_been_
„informing	„informed (by)
was/werejnforming	had_been_informed(_by)
will/shall_inform	will/shall_be_
	_informed(_by)
etc. In short, the left side of operator and the right side of operator =\ behave as informing entities irrespective of the tenses. On contrary, the right side of operator \= and the left side of operator =\ behave as informed entities irrespective of the tenses.
A
(iii) In regard to formula (1 ), to be alternatively consequent, one could introduce the alternative basic implicative axiom in the form
(1^') i=\oc)
a
(1^
a :
i=\oc)
This formula is read from the left to the right as: =} (X is implied alternatively by a. From the right to the left, this formula can be read »normally«, that is, a implies alternatively =\ oc. The complete possibility of meaning is the following: »a informs
alternatively« is implied alternatively by a. In the opposite direction one can read: a implies alternatively that OL informs alternatively.
As we see, the alternative axioms can now be obtained automatically from the basic, non-alternative ones, that is.
(2^)
(10^) (11^
(12^)
oc=^(pc=\)
(a zi^ (=j a)) (a (oc 4» a	a)
a (=1 a; a
(1	(=1 a) [alternative
extemalism of a] (2°) a (a =D [alternative
intemalism of a] (3°) a (a a) [alternative
metaphysics of a] (4°) a a; a =0 [alternative
phenomenalism of a] (1 =\ ot: alternative external informing of a; a's alternative informational impacting;
a's alternative informing (informingness) (2°) a alternative internal informing of a; a's alternative informational impactedness;
a's alternative informedness (3°) a H a: alternative metaphysical informing of a; a's alternative metaphysical circularity;
a's alternative informational metaphysicalness (4°) =\a\a=\: alternative phenomenal informing and informedness of a; a's alternative informing and informedness phenomenality; a's alternatively complex phenomenalism
In regard to the informational, the alternative informational means to have (possess) another pos-
sibility of informing to the already existing or identified one. Informational altemativeness is one of the basic principles of informational spontaneity, where in each particular case of informing an unforeseen, uncertain, indeterminable alternative possibility can arise and come into existence.
3. Axioms of Negative and Negative
Alternative Informing
Negative (negating, negational) informing, called also non-informing, is an alternative mode of informing in comparison to basic and alternative basic informing of an entity. Negative informing is, for instance, from the observer's point of view, something which is missing informationally in the informing activity of an entity. On the other side, the informing entity can inform by itself the deficiency of its certain informational impacting and, in this way, cannot influence the informationally tied entity in some other way. Negative informing belongs to the oldest cultural forms of communication and language. Within this tradition a clear distinction between informing (or informedness) and non-informing (or non-informedness) of entities is possible and senseful.
In general case, where [= marks the (positive) informing, the negative case is marked by [t^ with the meaning »does or do not inform« or, on the other hand, »is or are not informed (by)«.
For any imagined entity it can be said that it does not inform in a certain (particular) way. This seem to be a natural situation of things which certainly cannot inform in all possible ways. The assertion »entity a does not inform« is expressed symbolically
d")
a

N
Axiom (1 ) is a particular case of informatio prima, is in the realm of non-informing of entity a. And certainly, if a does not inform in a certain way, then something cannot be informed in a certain way. According to axiom (2) for informing of an entity, we have the negative axiom

a :
(M«)
This axiom reads: if a is an entity, then it is not informed in a way. As we recognize, the negative axioms can now be obtained automatically from the basic, non-alternative ones, that is.
(10^ (11^)
(12^)
(a	ay,
a);
(1°) a => (a [negative
extemalism of a] (2°) a Ot^ a) [negative
intemalism of a] (3°) a (a [t^ a) [negative
metaphysics of a] (4°) a (a a) [negative
phenomenalism of a] (1°) oc [t^: negative external informing of a; a ' s negative informational impacting;
a's negative informing (informingness) (2°) a: negative internal informing of a; a's negative informational impactedness; oc's negative informedness (3°) a ^ a: negative metaphysical informing of a; a's negative metaphysical circularity;
a's negative informational metaphysicalness (4°) a a: negative phenomenal informing and informedness of a; a's negative informing and informedness phenomenality; a's negative complex phenomenalism
The negative informational in regard to the informational means the lack of certain possibility of informing in regard to already existing or identified one. Informational negativism is one of the basic principles of informational spontaneity,
where in each particular case of informing a negative unforeseen, uncertain, indeterminable possibility can arise and come into existence.
The altemativeness of the negative informing can be expressed explicitly. It is important to have the possibility of alternative negative informing and informedness on a univei-sal and particular level. Thus, we can repeat the entire system of formal expressiveness and its meaning for alternative negative informing as follows:
AN (2AN
(3AN
(4AN) 5AN
(ll^S

(a	«);
a); a; a
(1	a) [alternative negative
extemalism of a] (2°) a (a [alternative negative
intemalism of a] (3°) a ^ (a a) [alternative negative
metaphysics of a] (4°)	[altemative
negative phenomenalism of a] (1 a: altemative negative extemal informing of a; . a's altemative negative informational impacting; a's altemative negative informing (informingness) (2°) [t^ a: altemative negative intemal informing of a; a's altemative negative informational impactedness; a's altemative negative informedness (3°) a a: altemative negative metaphysical informing of a; a's altemative negative metaphysical circularity; a's altemative negative informational metaphysicalness (4°) a; a altemative negative phenomenal informing and informedness of a;
a's alternative negative informing and informedness phenomenality;
a's alternative negative complex phenomenalism
4. Axioms of Basic and Basic Alternative Parallelism
Parallelism belongs to the most significant philosophical and technological approaches of modem-ism. Communication and cooperation among parallel processes constimte the kernel of mastering of complex computing machinery which architecture is built-up in a massively parallel strucmre and organization together with signal processing and networking. And this is the reason why we shall strictly repeat the scenario of axiomatization for the case of parallel and alternative parallel informing.
Informational parallelism means that entities inform freely, that is, spontaneously and circularly in parallel ways. An operand as an informationally open entity (phenomenalism) informs unforeseea-bly parallel and is in this way informed. It means that from the informational point of view, there are no limits for a concrete parallelism: it can be extended or suppressed in case of any informational entity (operand) in question. So, let us discuss this particular situation in some axiomatic details.
For any imagined entity it can be said that it informs in a parallel way, that its »signals« are spread (broadcasted) in space and time where they can impact entities physically, observationally, or in other ways. This seem to be a natural situation of things which inform in all possible ways to different places and sites. The assertion »entity a informs in parallel« is expressed symbolically

a
(INo)
d")
a
(«N
u
Axiom (1 ) is the parallel case of infonnatioprima, is in the realm of the parallel informing of entity a.. And certainly, if a informs in parallel ways, then entities are informed in parallel. According to axiom (2) for informedness of an entity, we have the parallel axiom
This axiom reads: if a is an entity, then it is and can be informed by several (parallel) entities simultaneously. From this point on, the parallel axioms can be produced automatically from the basic ones, that is.
(3)
(4p)
(8^
(lop (11^)
(12^)
(«IN) (IN«)
(oc=>{a\\=))
(IN«); («IN);
(IN«);
(a (a 1^))	oc));
« (« IN «);
a (a ||=; ||= a); (1°) a (a 1^) [parallel
extemalism of a] (2°) a d^ a) [parallel
intemalism of a] (3°) a (a |(= a) [parallel
metaphysics of a] (4°) a ^ (a ||=; a) [parallel
phenomenalism of a] (1°) a \=: parallel external informing of a; a's parallel informational impacting;
a's parallel informing (informingness) (2°) 11= a: parallel internal informing of a; a's parallel informational impactedness; a's parallel informedness (3°) a |t= a: parallel metaphysical informing of a; a's parallel metaphysical circularity;
a's parallel informational metaphysicalness (4°) a |t=; |t= a: parallel phenomenal informing and informedness of a; a's parallel informing and informedness phenomenality; a's parallel complex phenomenalism
The parallel informational in regard to the informational means the possibility of informing addi-
tionally in regard to already existing or identified modes, that is, simultaneously in many different modes. Informational parallelism is one of the basic principles of informational spontaneity, where in each particular case of informing a parallel unforeseen, uncertain, indeterminable possibility can arise and come into existence.
The altemativeness of the parallel informing can be expressed explicitly. It is important to have the possibility of alternative parallel informing and informedness on a universal and particular level. Thus, we can repeat the entire system of formal expressiveness and its meaning for alternative parallel informing as follows:
O O
(lO^h
a^(aHI) (Hi HD;
a (a HI a);

a (HI ol; a HD;
(1 a (HI a) [alternative parallel
extemalism of a] (2°) a (a HD [alternative parallel
intemalism of a] (3 ?) (a HI a) [alternative paralel
metaphysics of a] (4°) a ^ (HI a; a HD [alternative parallel phenomenalism of a] (1°) HI alternative parallel external informing of a; a's alternative parallel informational impacting; a's alternative parallel informing (informingness) (2°) 11= a: alternative parallel internal informing of a; a's alternative parallel informational impactedness; / a's alternative parallel informedness (3°) a HI oc- alternative parallel metaphysical informing of a; a's alternative parallel metaphysical circularity; a's alternative parallel
informational metaphysicalness (4°) HI =\\' alternative parallel phenomenal
informing and informedness of a; a's alternative parallel informing and informedness phenomenality;
a's alternative parallel complex phenomenalism
The parallel informational phenomenality concerns the most sophisticated metaphysical and intelligent conceptuality (phenomenology) of the informational (mathematical, mathetical in the sense of the Greek mathesis). In an informational situation, parallel informational phenomena pertaining to this situation can come into existence. The general and particular operators of informational parallelism (|1=, HI. T^D express this faculty of parallel phenomenality in a positive or negative way. Therefore, the following parallel circularity can be considered as the most significant in the context of parallel informational system
composition and decomposition: p
(13 ) jParallel circular extemalism:
(a H ^ (a [=;...; a H; Parallel circular intemalism: (^ a)	a);
^{=:a)^(^=a; ... ;{=a); Parallel circular metaphysics:
(a N «) (« IN a);
(a 11= a) =>(a 1= a; ...;a\= a); Parallel circular phenomenalism: (a |=; t= a) ^ (a |t=; a); (a it= a) (a [=; 1= a; ... ; a [=; [= a)
As one can understand, informational parallelism brings into the focus the so-called parallel circular mode of informational arising of entities, systems, formulas, etc.
5. Axioms of Informational Function
Wir bringen diesen gesuchten Grundcharakter der neuzeitlichen Wissenshaltung auf einen Titel, wenn wir sagen: Der neue Wissensanspruch ist der mathematische. Von Kant stammt der oft angeführte, aber noch wenig begriffene Satz: »Ich
behaupte aber, daß in jeder besonderen Naturlehre nur so viel eigentliche Wissenschaft angetroffen werden könne, als darin Mathematik anzutreffen ist.«
—Martin Heidegger [FND] 52
A function (p is an acting or producing informational entity in the realm of several, the function concerning entities. Therefore, it is senseful to speak about a functional scheme in which different entities can be involved when functional activity is coming into existence. It means that the functional scheme should retain sufficiently general perquisites enabling it to be embedded and connected into and with distinguished and essentially different mformational entities, respectively.
In general, a function is never something without its roots from where it arose or is still arising. Several essential and general questions can come into the discourse before we list the axioms pertaining to informational function 9. Let us start with some basic questions.
(1)	Which entity (informational operand) ({) produces (p?
(2)	For which purposes, marked by n, function <p is intended when produced by
The last two questions can be united by the following formula:
(13)
Since entity ({) with its purposes tc is the main constructor of (p, process (13) is recursive in respect to ({), that is, (()-circular. This fact yields
(14)	(((l)|=7t)^=<p)f=(J)
The last formula can be particularized in an operand and operator way, that is.
(15)
c_prod Nwith (^purpose Nconsider '^sensc "^significance» '■intention)) Nproduce 'Pfiinction) Nrefer 4'func_prod
The operand and operator entities of the last formula have the following particular meanings: •I^func_prod is a functional producer; Ttp^rpose marks purposes which consider (operator t=consider) operand entities as agense» CTsignificance» and t intention; these purposes are with (operator |=with) entity
^fimc.prod; "ow, the functional producer with its purposes produces (operator t=produce) function ^function the whole process is in reference to (operator l=refer) ^^e functional producer 4'func_prod- ^^ this way, the function arises cyclically, influencing backwards its producer with certain purposes.
The next question is: (3) From which distinguished informational domain ^ does function (p depend and how does it produce a result p for purposes n?
Through this axiomatic question, function (p becomes together with domain ^ the producer of result p. In this point we introduce a shortened form of formal expression of »function (p of domain that is
(16)
where |=of reads »inform(s)_of«, »in-form(s)_on_the_basis_of«, »depends_on/upon«, etc. Since both entities 9 and ^ can be composed formulas, the expression can also be understood in the fimctional sense. For instance, functional form ci(ß [= y) means that a is a function of entity ß [= Ti further, functional form (a \= ß)(Y [= 5) would mean that entity a [= ß is a function of y = S. In fact, these functional expressions are shortcuts of both formulas a. [=of (ß (= t) and (a |= ß)
Nof(TN5).
Question (3) can now be formally expanded in the following basic and general way:
(17)	N
((^ N <P) h ((P N N I{>))
The particularized form of the last formula is
(18)	<Pfunction(^doniain) ^
((^oniain Ninfluence 'Pfunction) Nproduce ((presult Nfor ^purpose) f^of 'J^func_prod))
In the last formula, one can see how the result of the function and its domain within certain purposes become a function of the functional producer as well. It seems that the functional producer predetermines, in the realm of its own purposes, not only the function which it produces, but also to some informational extent the functional result itself. This comment may concern specifically any con-
struction of the so-called scientific functional dependencies, where the role of the functional producer is left to the scientist.
The next question pertains to the functional domain: (4) To which informational domain a. a functional domain ^ does belong and by which selecting entity ß it is identified as a significant domain of the function 9?
As one may expect, there is an entity ß somewhere, clearly identified or unconscious, which performs the selection of an adequate informational functional domain ^ out of a broader informational realm a. in the way to satisfy the producer purposes of producing of 9. The initial formula of selection is, for instance,
(19)
The particularized form of this formula is, for instance,
(20)	ßselector Nselects ((domain ^ °^fimc_domain)
Nfor (9fimction(^oniain))
The next question concerns the How of selector ß: (5) Is ß an autonomous selector of domain ^ which selects ^ out of the realm a by its own strategy •^strategy •
The strategy of selector is by itself an informational function, that is, ^strategy(ßselector)- Thus the entity which selects is embedded in the selector, and formula (20) can be expressed more precisely as
(20-)
(ßselector Nby "^strategy) Nselects ((domain ^ '^func_domain) Nfor (9function(^oinain))
Additional questions to the preceding ones may be the following:
(6) Is the domain (realm) a. already clearly distinguished, identified, so it can serve as a background in producing funaional domain ^ by selector ß?
(J) How does function 9 as entity (jpf^ produce a purposely oriented result p?
(8)	To which informational domains does p belong, for instance, p C a, ß, tt, cp, (j)?
(9)	How can the functional scheme 9 be expressed explicitly (in a predicating way, operationally), for instance.
9\=ofK' a. ß. 'I'; pNof<p(0
etc. and what is the form of the hierarchy, if specifically possible (linear, circularly inter-weaved) among entities?
(10) What does the functional scheme of a recursive character, that is, 9i(92(---'Pn(^n) - ), mean?
Questions (1) to (10) spread the possibilities of the functional axiomatization enormously. In concrete cases, different axioms pertaining to specific situations and attitudes come to the surface.
At the end of this section, let us mention the following evident example of a recursive informational functional structure: the mind is a function of a concrete living brain; a thought is a function of the mind; a distinguished thought item is a function of the thought; the distinguished thought item, the thought, and the mind impact the arising of the brain, for instance, the appearance of new neurons and neuronal interconnections; thus, the brain is a function of its own phenomenality, that is, of thought items, thoughts, and the mind in its entirety; etc.
Further, the functional expression 9(^ means that, in general, the functional structure and organization as an informational phenomenon, which is an acting entity, is sketched in a framing (intuitive, approximate) form and not determined yet too precisely. In case of a precise formulation of functional phenomenality, expression 9(^ can imply various predicative, that is, operational forms of functional construction, for instance, 9 Nof ^ Nwith 9. 9 Nin etc. As we have seen, the functional phenomenality can take into consideration many parallel formulas which impact in-formationally the basic functional entity 9(^.
6. Axioms of Basic Metaphysical Informing
Informational metaphysics concerns a thing in itself, that what an entity is by its own internal structure and organization, form and process, as it exists in itself. This view offers a more complex comprehension than that of philosophia prima or supernatural imagery.
The initial metaphysical situation of entity a is given by four metaphysical cases marking the basic, alternative basic, negative, and alternative negative informing of entity a in itself:
a [= a; a =1 a; oc ^ oc; o£ a
We shall limit our examination to case a [= a. In fact, this case will be decomposed axiomatically with the intention to give the basic starting points for further, that is, concrete decomposition (metaphysical projection).
Within metaphysics of operand a we are confronted with three basic phenomena: informing of entity a, marked by counter-informing Š of entity oc, marked by S(a); and informational embedding © of entity a, marked by ®(a). These are three basic metaphysical functions of informing of a. Three groups of basic parallel metaphysical axioms can be posited:
(21)	Informing axioms: (a|=a)=>S(a); S(a)^((oc|=S(a))|=a);
Counter-informing axioms:
(tNT) <=(«[= a); S(a)CS(a);
(a 1= a, Y1= Y) ^
((e(a)|=a,T)N<S(a)); Embedding axioms:
(a|=a,TNT.st=s)=»®(a);
(s }= s) C (a (= a); e(a)CS(a);
®(a) ((a, T. s f= ®(a)) |= a, y, s); (a 1= a, Y 1= Y, s 1= s) ^ mioc)\=a, y,B)\=(S(a))
In this system a marks the basic entity (operand, thing), Y is used as the marker of a's counter-informational component, and s as the marker of a's embedding component, by which the arisen component Y and other information is connected to a. The last parallel system of axioms pertaining to metaphysics a\=a results systematically into
(22)	Metaphysical informing: (oc 1= a) ^(a);
(a 1= a, Y N T) <S;(oc); (a a, Y N T. s [= £) ^ ®(a); Metaphysical hierarchy: (Y N T» s N s) C (a ^ oc); m), ®(oc)CS(a); Decomposition of a, y, and s;
S(a)=»((oct=S(«))N«); S(a)=»((a, ^ (£(«)) ^ a, Y); ®(a) ((a, Y, s N ®(a)) N T- s); Decomposition of^(ot), ^(a). and
(a [= a, Y N T)
((£(«) ^ a, Y)N<S(a));
(a t= a, Y N T. s N s)
m(ot)\=a, Y,s) h ®(oc))
To the parallel metaphysical axioms, the cyclic or serial axioms can be introduced in which the occurring components a, ;^(a), y, S(a), s, and ®(a) àre positioned into middle-long and long metaphysical cycles. One of the axioms pertaining to the long metaphysical cycle is, for instance,
(23) (a\=a)^
((((((oc N N T) N ®(a)) N s) l=(S(a))l=a)
Other long axioms can be obtained by the permuting of operand components in the last axiom.
6. Axioms of Informational Intelligence
Wo der Wurf des mathematischen Entwurfs gewagt wird, stellt sich der Werfer dieses Wurfes auf einen Boden, der allererst im Entwurf emtworfen wird. Im mathematischen Entwurf liegt nicht nur eine Befreiung, sondern zugleich eine neue Erfahrung und Gestalmng der Freiheit selbst, d.h. der selbstübernommenen Bindung. Im mathematischen Entwurf vollzieht sich die Bindung an die in ihm selbst geforderten Grundsätze.
—Martin Heidegger [FND] 75
Entities inform according to axiom (1) which represents informatio prima from which axiomatic consequences can follow in a mathematically projective way. How can entities inform intelligently and what are the perquisites of intelligent type of informing? Intelligence seems to be merely a pred-
icate (property, faculty) belonging to an informing entity. Thus, the way to intelligent informing of entities must proceed from the axiom (1) which has to be particularized for the case of intelligent informing.
An informational entity can have such or another intelligent position or attitude in the general and particular sense. The majority of readers would agree that an intelligent entity (IE) informs some of the facts, concepts, or fiction in the following six initial points:
(1)	IE informs (expresses, describes) something (an entity) in an evaluating, observing, or understanding way;
(2)	IE produces the so-called meaning, sense, spirit, and/or significance of something as information;
(3)	IE forecasts, analyses, and synthesizes information concerning something under dynamic, unforeseeable, uncertain, and indeterminate circumstances;
(4)	IE brings unknown, unconscious, invisible, impossible information concerning something to the surface;
(5)	IE is spontaneously and circularly oriented, intentional, and goal-directed when it observes itself and evaluates various possibilities for its own development;
(6)	IE behaves as a living entity in the world where it plays the struggle for its own benefit, delight, survival, etc.
Following the axiomatic route demonstrated for the general informing of entities (operator [=) in formulas (1) to (12), for an intelligently informing entity i. the following particular and significant axioms can be considered:
('j)
(2) (3;)-
(7") (10^ (ll"^)
^ (l- Nintelligent)' (^intelligent
.C"- Nintelligent) ^ (Nintelligent I-)» (Nintelligent	intelligent/'
I- ^ (l- Nintelligent >•); ^ ^ Nintelligent» Nintelligent '-)» (1°) L ZI» (i |=in,eiligem) [intelligent
extemalism of l] (2°) L (Nintelligent 0 [intelligent intemalism of t]
(3°) I ((, |=in,eiiigent 0 [intelligent metaphysics of t]
(4°) L (l Fintelligent! Fintelligent 0
[intelligent phenomenalism oft]
Let us have the following dictionary of the primary four informational cases of intelligent informing:
(I2V (1°) t ^^intelligent: intelligent external intelligent informing of i ; L 's intelligent informational impacting;
L 's intelligent informing (informingness) (2°) Nintelligent intelligent internal informing of i ; I's intelligent informational impactedness; I's intelligent informedness
(3°) t [^intelligent t :
intelligent metaphysical informing of (,;
L 's intelligent metaphysical circularity;
L 's intelligent informational metaphysicalness
(4°)
intelligent^ Nintelligent • intelligent phenomenal informing and informedness of i ; L 's intelligent informing and informedness phenomenality; L 's intelligent complex phenomenalism
There are different modes of intelligent general informing and it is possible to make a rough classification in the following sense:
intelligent general informing: operator
Nintelligent' intelligent alternative general informing:
operator ^intelligent; intelligent negative general informing:
operator ^intelligent; intelligent alternative negative general
informing: operator T^intelligent; intelligent parallel general informing:
operator i^^intelligent; intelligent parallel alternative general
informing: operator HUtelligent; intelligent parallel negative general informing: operator |}7^intelligent;
intelligent parallel alternative negative
general informing: operator ?Ì|intdligent; intelligent q^clic general informing:
operator [-intelligent; intelligent cyclic alternative general
informing: operator Hintelligent: intelligent cyclic negative general informing: operator b^intelligent; intelligent cyclic alternative negative
general informing: operator T^intdligent; intelligent parallel-cyclic general informing:
operator H-intelligent^ intelligent parallel-cyclic alternative
general informing: operator Hlimelligent; intelligent parallel-cyclic negative general
informing: operator Unintelligent; intelligent parallel-cyclic alternative negative general informing: operator /||intelligent
We see how intelligent informing of an entity i is nothing else than any other particular informing of this entity. Intelligence is merely a specific perquisite of the entity which produces »intelligent« information concerning something which this entity evaluates, observes, or understands. Thus, to the basic axiomatic system of an intelligently informing entity t the parallel system can be added, considering the previous six initial points (1) to (6) of intelligent informing. The markers and to them corresponding meanings of the Greek and Frakmr operands and operators are the following:
ßbenefit benefit
ßbenefit(^) something's own benefit; benefit of
something Tcircumst circumstance(s) ^delight delight
^delightC®) something's own delight; delight of something
^development
development
^dynamic dynamics
^dynamic(Tcircumst)
dynamic circumstances
"•indetenn indeterminacy
^ indetermCTcircumst)
indeterminate circumstances I	intelligently informing entity
something
impossible impossible, the
impossible(^)
impossible concerning something, the
invisible invisible, the
hnvisibleCc^)
invisible concerning something, the
Xjive liveliness
^live(^entity)
living entity
^meaning meaning
l^meaning(^)
meaning of something
^possibility possibility/possibilities
'^possibility^'' (^development))
possibility of intelligent entity
development
a	something (an arbitrary entity to be
»understood« by (,)
-•sense
sense
CTsense(^) sense of something ^significance
significance
^significanceC*^)
significance of something
^spirit
spirit
i(o)
entity intelligently concerning
aspirit(cr) spirit of something «^struggle struggle
•^survivaK^)» •••) struggle of something's own benefit, delight, survival, etc. «^survival survival '^survival(^)
something's own survival; survival of
something
^incertain uncertainty
^uncertain(Tcircunist)
uncertain circumstances
^unconscious
unconscious, the
^mconscious(^)
unconscious concerning something, the
^unforeseeable
unforeseeable, the
^unforeseeable(Tcircumst)
unforeseeable circumstances
^unknown unknown, the
^mknown(cf) unknown concerning something, the
2ßworld world
=analyze	analyze(s)
Nbehave	behave(s)
—circular	is/are_circular
Nevaluate	evaluate(s)
Nforecast	forecast(s)
Ngenerate	generate(s); bring(s)_to_the_surface
—goal_directed
is/are_gòal-directed is/are_in; inform(s)_in
Nintentional
is/are_intentional
Nobserve observe(s)
Nplay Play(s)
Nproduce produce(s)
Nspontaneous
is/are_spontaneous
Nsynthesize
synthesize(s)
Nunder is/are_under; inform(s)_under
Nunderstand
understand(s)
The six additional paragraphs pertaining to IE can now be formalized by the corresponding informational formulas as parts of the informational system of IE I. For the first sentence and its formula we have:
(13^1) IE informs (expresses, describes) something (an entity) in an evaluating, observing, or understanding way; (a [= (t, |=intelligent 0) ('' N^evaluate '' .Nobserve '' Nunderstand
In this formula, IE l , that is, its metaphysics i ^intelligent (-, is the intelligent observer of a, so, it evaluates, observes, and understands cr. The second sentence and its formula is:
(13^2) IE produces the so-called meaning, sense, spirit, and/or significance of something as information;
Nproduce ((^meaningCcf). c^sense(cf)' c^spiritC^)-'^significanceC'^))
The third sentence together with its formula is
(13^ 3) IE forecasts, analyses, and synthesizes information concerning something under dynamic, unforeseeable, uncertain, and indeterminate circumstances; —forecast	Nanalyze '•C'^)»
Nsynthesize ^ Niinder (^dynamic(Tcircumst) > ^inforeseeable(Tcircumst) > ^uncertain (Tcircumst) > '' indeterminate(Tcircunist))
The fourth sentence and formula are:
(13^.4) IE brings unknown, unconscious, invisible, impossible information concerning som£thing to the surface;
^ Ngenerate
(^inknown(^) > ^inconscious('^)' '' invisibleC'^) » impossible(^))
The fifth sentence and its forinula are
(13^5) IE is spontaneously and circularly
oriented, intentional, and goal-directed when it observes itself and evaluates various possibilities for its own development;
((th spontaneous' ^circular» Pintentional' Pgoal-directed) —observe '•) Nevaluate ^possibility C*" (^development))
The sixth sentence and its formula are
(13^6) IE behaves as a living entity in the world where it plays the struggle for its own benefit, delight, survival, etc.; (('' Nbehave ^live(^entity))
=in ®^world) Nplay C^struggleObenefit(c^). ödelight(^).
7. The Syntax of Informational Formulas
In this essay we have used various informational formulas from the beginning, in the most basic axioms. In parallel, we developed a foundation of the so-called operand-operator (0-0) theory which could be understood also outside the so-called informational realm as a mathematical theory. We
could simply speak about a self-sufficient operandoperator theory which does not concern only the so-called informational theory. This would mean to ignore the semantics pertaining to the informational phenomenality and introduce operand-operator objects as the only ones into the O-O theory. However, such theory would be nothing else than a particular case of an informational theory. The syntax delivering syntactically correct informational formulas is simple and straightforward. If a. represents any possible operand entity, the formation rules of well-formed informational formulas 9 are the following:
(24)
(1°) (2°) (3°) (4°) (5°) (6°) (7°) (8°) (9°) (10°) a: (11°) [=
(p: <p: 9:
<P <p:
(p:
■a;
(a';»;
'('(PT;
(9N;
? ^ (9 N 9);
<p a(9);
a=»(a|ß|T| ...a)|ai|58|6:| ... ß); '^subs'
(NNIMlTNIINNIIIb^MII
triniti r I •••)
(i2°)N=»Nsubs; (13°) Komp; (14°)Ncomp=>(N°NI'('t=°N')'l
In the last formula system we have marked symbols '(', ')', and'I'to avoid the ambiguity with the equally marked symbols appearing in syntactic system (xx). In formula (11°) operator entities appear as informational entities. Entity a is a simple operand, that is, operand marker in the sense of formulas (9°) and (10°).
folded this situation and attitude üirough the con-ceptualism of informational extemalism, intemal-ism, metaphysics, and phenomenalism which all can be accepted in a general and in every particular case. Thus, any other axiomatic approach can be derived from the informational as a specific axiomatic particularization. On the other hand, an informational (verbal and symbolic) language [TIL], that is, the new formalism, came into the foreground and made the progressing into the domain of the informational (intelligent) machine possible.
Various forms of the verb to inform obtained the power of the verb to be and the role of the most primordial (simple and composed) verbal forms. Thus, any operator connection between informational operands could be expressed dynamically in a general or particular way, widening the scope of the verbal phrase which includes informing to arbitrary other words and word groups with particular, composed meanings. The informational approached to that what we can call the understanding way of informing, living the atomized, strictly linguistically structured and organized conceptual-ism in the background, unconscious, however not excluded from the informational realm. In any case, the verb to inform became the central happening between entities and enabled to broaden the informational semantic scope to any dynamically understood relation, operation, and phenomenality, occurring between informational entities (operands).
On this way, the informational axiomatiza-tion can encounter the most problematic, semanti-cally complex, intelligent, and real situations, offering e new, flexible, and promising apparatus in the development of nowadays and future theories, systems, and machines.
References
Conclusion
The informational seems to be the most adequate principle of the universe. Things, entities, phenomena, information, minds, machines, and the entirety of the universe inform and are informed, that is, impact and are impacted phenomenally, perform as informational entities, as formations concerning formations; and, that is, speaking roughly, information. In the essay, we have un-
[FND] Heidegger, M., Die Frage nach dem Ding, Max Niemeyer Verlag, Tübingen (1987).
[Owi] Železnikar, A.P., On the Way to Information, The Slovene Society Informatika, Ljubljana (1990).
[TIL] Železnikar, A. P., Towards an Informational Language, Cybemetica35(1992) 2. 139-158.
INTEGRITY IN THE RELATIONAL DATA MODEL
Keywords: relational model, entity integrity, referential integrity, logic approach, consistency
Mario Radovan Fakultet ekonomije i turizma, Pula Inštitut »Jožef Stefan«, Ljubljana
The paper shows that the general integrity rules are simply "corollaries" of the (traditional) definitions of primary and foreign keys. Further, it is shown why (and how) the database-specific integrity rules should be treated as expressions of that knowledge which is contained, built-in in our "language, atitudes and measures". Such a conception of integrity allow us to reduce the (rather informal) concept of "correctness" of databeses to the request for its consistency (as a theory).
INTEGRITETA V RELACIJSKEM MODELU: Članek dokazuje, da so splošna pravila integritete preprosto korolarj i tradicionalnih definicij primarnega in zunanjega ključa. Dokaže tudi zakaj (in kako) bi pravila integritete specifična za dano bazo, morala biti obravnavana kot izrazi (zapisi) tistih znanj, ki so vsebovana (vgrajena) v našem "jeziku, stališčih (odnosih) in merilih". Tako pojmanje integritete nam omogoča da (precej neformalen) pojem "pravilnosti" baze podatkov zvedemo na zahtevo po njeni konsistentnosti (kot teorije).
1. Introduction
"We begin with a little philosophy", says Date, <Dat 90, p. 275>, at the beginning of the chapter on Relatinal Integrity Rules. In this article we begin in the same way; indeed, we also continue in this way because it
seems that the basic concepts concerning integrity in general are not yet defined suitably nor clearly enough.
Our discusion is concerned with the approach and definitions given in <Dat 90> because Date is not only one of the active Contibutors to the field od databases.
but also one of the most influen-tal writer on the topic. We are not speaking so much in terms of the "right" or "wrong" way of doing things as in terms of more or less suitable ways of conceiving and defining basic concepts in data modeling in general, and especialy of integrity constraints (rules).
2. The Logic Ap^>roach
A set of seminal ideas on the "logic approach" to data modeling was collected in <Gal 78>; among subsequent contributions, it seems that the most influental on the topic was <Rei 84>. An analysis and a proposal for (re)defining inference and integrity for knowledge bases, defined in terms of clausal logic and SLDNF-reso-lution, was given in <Rad 87>.
Generally speaking, the conceptual foundation of any "informal knowledge" always involves "some logic". Such a logic consists (at least) of a language (defined on the level of syntax (form) and semantics (interpretation, meaning)), and a (set of) inference rule(s) which allows us to infer consequences which follow from the given knowledge. Therefore, a "conceptual foundation" of any "knowledge" bring us to a "system" in whose language such a knowledge should be unam-bigously expressed, and by whose rules of inference (all and only) the consequencess of this knowledge could be inferred. What is known as "relational data model" is also such a "system".
The logic approach defines a way of conceiving "facts" and "knowledge", and a way of speaking about them. By "model" we
mean a set of facts (states, values), while a "theory" is a set of propositions (assertions, knowledge, ... ) concerning some model.
In accordance with such a conception, the content of a data/knowledge base is seen as a theory which expresses knowledge concerning some "world". If such a theory is correct and complete, it "tells the truth and only the truth" about the world, and we say that the world is its model. (Incidentally, in such a context, we would prefer to speak of the "relational system", rather than of the "relational model".)
3. The General Integrity Rules
In the relational data model (system) , the integrity rules are traditionaly divided into two clases: general and database-specific rul^s. The first class contains only two rules, known as the entity integrity rule and the referential integrity rule. Although there is much "theoretical debate" (not always very clear!) about these rules, their meaning is fairly simple and clear.
The entity integrity rule says that a thing about which we (want to) speak must be identified, while the referential integrity rule says that what we refer to must exist.
Although these rules are concerned with the relational data model (system), it seems that those requests should be a minimal condition of any "afirmative speech" to be considered inteli-gible! (Therefore, they should form a part of any system (language) , except those of poetry. Of course, hypotetical speech (in religion, politics, ... ) is
possible (and coitimonl) even without real identification and existence. )
3.1. The Entity Integrity Rule
In spite of the simplicity of the entity integrity rule, there seems to be much vagueness and disagreement concerning its meaning and definition than one would expect. In <Dat 90, p. 279>, Date states this rule as:
"No component of the primary key of a base relation is allowed to accept nulls".
He specifies (p. 280): "... we take 'null* to mean, simply, a value or representation that is understood by convention not to stand for any real value of the applicable atribute" (underlined M.R.). In fact, the same was stated on p. 251, where we find: "null is not a value".
To evaluate Date's conception of the entity integrity rule, it seems apropriate to cite his definition of candidate (ató primary) key also; in <Dat 90, p. 277> we find:
"Atribute K (possibly composite) of relation R is a candidate key for R if and only if it satisfies ...
1.	Uniqueness: At any given time, no two tuples of R have the same value for K.
2.	Minimality: If K is composite, then no component of K can be eliminated without destroying the uniqueness property".
Discusing the entity integrity rule. Date rightly emphasizes that "all kind of problems" arise if the key is (partially) null. Among other things, he stresses that in such a case we do not
even know (in general) whether the tuple with a null in its key "represents" some of the entities about which we already have a tuple in the relation.
However, a "kind of problem" also springs from Date's concluding fragment of the section on entity integrity; he says:
"... it is commonly but erroneously thought that the entity integrity rule says something along the lines of 'Primary key values must be unique' . It does not. That uniqueness requirement is a part of the basic definition of the primary key concept per se. ( under 1 ined M. R. ) The entity integrity rule says (to repeat) that primary keys in base relations must not contain any nulls".
In fact, it seems that there really are such "thoughts" as Date mentiones above; whether they are really "erroneous" or not, we will try to see in what follows. For example, in <Gro 90, p. 270> (a respectable book, in my opinion) Groff and Weinberg give the following definition:
"Entity integrity: The primary key of a table must contain a unique value in	each row
Evidently, this definition says exactly what Date denies! Now, which of the two (in fact, three) autors has an "erroneous thought"? And why, and where does the error come from? That is the question we shall try to answer now.
First of all, both positions seem to be coherent. Which one will then be the "loser"? We claim: The entity integrity rule itself!
For Groff and Weinberg, the
position is fairly clear: They give a definition, without much argumentation. The only objection which could be raised against their position is that such a definition makes the entity integrity rule superfluous. Namely, it only repeats what is already contained in the concept of uni-gueness in the very definition of kandidate key!
Date's position seems somehow different. However, it seems that the difference arises mainly from his imprecise definition of the candidate key given above. Namely, what does it in fact mean that "no two tuples of R have the same value for K"?
Let us try to understand it by means of an example. Let the sheme of the relation R be
R^A. B. ... ), and let two tuples from R be <al, null, ... > <al, null, ... >.
Now, does this pair of tuples violate the above unigueness reguest or not?
No, because according to Date, "null is not a value"! Therefore, it is impossible even to speak about the "same value" ! And in such a case, it seems necessary to have Date's definition of the entity integrity rule, so as to "expel1" the -nulls from the key! Namely, otherwise "all kind of problems" would arise: adressibi-lity of tuples, first of all ("null is not a value"!).
However, there was one more reguirement in the definition of candidate key: minimality! And this one warns us clearly enough that if we assign to the key atributes something that "is not a value", we must lose unigueness! And by that, we also deviate from the definition of the key (i.e., we lose even the key
itself!). Namely, even though by assigning null to an atribute which is a component of the key, the component is not really "eliminated", it is eliminated in a functional sense: it is not "in function" any more! (A component can guarantee (or support) the unigueness of the key only by being instantiated to a value -and not to something which is "not a value"!)
Therefore, we must once more conclude that the entity integrity rule (at least, as a rule!) is superfluous, because it only repeats what necessarily follows from the mere definition of the candidate key. Namely, a careful reading of the candidate key definition tells us that the candidate key atributes must not be null.
By the above claim of "imprecision" in Date's definition of the candidate key, we mean that with the expression "same value", Date should have really intended "a value"! Well, there is a legation in his definition of unigueness, and that always make things less clear. Namely, as we already stated, "not a value" in fact satisfies the reguest for "no . .. the same value"! However, it seems easy to escape this (rather sofistic) trap. We should only reformulate the uniqueness request, in perhaps the following a way:
"Any two (different) tuples of R must have different values for K."
Now, from "have different values" we should be allowed to infer "have value"! And then all additional rules concerning "nulls in key" become superfluous .
3.2. The Referential Integrity Rule
For discussing' the referential integrity rule we should first give a definition of foreign key. This concept is pretty clear, however it seems very "unsuitable" for being caught in an "elegant" definition. Date, <Dat 90, p. 282>, states it in the following way:
"Atribute FK (possibly composite) of base relation R2 is a foreign key if and only if it satisfies the following ...
1.	Each value of FK is either
wholly null or wholly nonnull. • • •
2.	There exists a base relation R1 with primary key PK such that each nonnull value of FK is identical to the value of PK in some tuple of Rl".
Now, the referential integrity rule. Date defines, <Dat 90, p. 284>, with the following words:
"The database must not contain any unmatched foreign key values".
Unfortunately, it séems that there are "some problems", even with this definition. Namely, according to the definition of foreign key, if some "nonnul value" i.e. "value" (all "values" are "nonnull", if null "is not a value"!) of a foreign key FK would be unmatched, it would not be a foreign key! (Read carefully clause (2) of the foreign key definition!) Therefore, in the context of the given definition of foreign key, the referential integrity rule seems to be superfluous (as was the entity integrity key in the context of the definition of candidate key).
With the above discussion, we
didn't mean to criticize Date's exposition; in fact, he himself says that "... the foreign key and referential integrity concepts are defined in terms of one another. That is, it is not possible to explain what a foreign key is without mentioning the idea of referential integrity (at least tacitly) ...", <Dat 90, p. 285>. Incidentally, we "feel" that the last sentence is too strong. For it is not very clear why it should not be posible to define a foreign key if (some of) its values would be simply (momentarily) unmatched.
Let us conclude the discusion on general integrity rules with a few remarks and estimates of their position and role in the relational data model (system).
First of all, we hold that there is an esential difference between the request for "uniqueness" (entity integrity) and the one for "matching" (referential integrity). Namely, it is very clear that uniqueness (adresibi-lity) is of an essential importance for the model. Therefore, it should be defined (included) at the level of the syntax of the language (system).
On the other hand, we hold that the referential integrity request is of no such importance on the theoretical level. Namely, what is in fact the (cognitive) difference between a null-valued foreign key and an unmatched one? Let as look at an example.
Let Rl and R2 be relations, and B be a foreign key of R2 in Rl:
Rl(A, ..., B, ... ) R2(B, ... ), and let
<al, ..., null, ... > f • • • f ]d2 f • • • ^ <a3, ..., b3, ... >
be tuples in Rl. Further, let the relation R2 contain a tuple
<b2, --->,
but not the tuple <b3, ... >.
Now, the first two tuples of Rl do not violate the referential integrity rule (the rule allows nulls), while the third one does. However, we think that there is not much difference among them, at least not at the theoretical level of the data model (system). Namely, the first tuple refers to "something unknown", while the third refers to "something unknown, designated as b3".
Of course, there is a difference between the first and the third tuple of Rl on the operative (practical) level. Perhaps by inserting null (instead of b3) in the third tuple above, we would not bring in much information about "the world": in fact, "the reality" would be "even more uknown"! However, this "even more" is useful, because - with it, expressed as null - we know that the "referred entity" is actually unknown. And that could be a useful information, not about "the world", but about our knowledge of it! For without a null, we could erroneously hold, in accordance with "common sense", that there is a tuple b3 in R2.
In accordance with what is stated above, we hold that the request for referential integrity is a problem which belongs (much) more to the level of implementation (software) than to the basic theoretical (conceptual) level of the model (system). Therefore, we put forward three possible ways of "theoretical treatment" of this rule, where our preference goes from the first downwards.
1. Referential integrity (as a
request for obligatory matching) could be ommited as an explicit rule, and as an implicit part of the foreign key definition.
2.	Referential integrity could be (and in fact actually is) stated inside (as an implicit part of) the definition of foreign key. In that case, "the problem" is raised on the level of syntax, and there is no more need of a special (explicit) theoretical treatment.
3.	Finaly, if we insist to keep referential integrity (as a rule) in the system, then a referential integrity violation should be reduced to the inconsistency of the database as a theory. To achieve this, we should simply define a rule as a "generally holding knowledge (truth)", in the following way:
"For every fk, such that fk is a value of a foreign key, there is (in the database) a primary key with value fk."
Such a rule would then be part of the (knowledge contained in) the database.
Now, if an "actual content" of the database (which is always finite) would allow us (or the DBMS) to infer (compute) that:
"There is such a value of an atribute(s) defined as a foreign key (in some relation) which is actually not a value (instance) of the refered primary key",
then such an inference (result) would contradict the integrity rule stated above, and show the inconsistency of the database content. Naturally, such a control (checking) should be performed before (every) update of a database.
4. Database-specific Integrity
According to Date, a database-specific integrity rule (constraint) "can be regarded as a condition that all correct states of the database are required to satisfy", <Dat 90,, p. 437>. Such an assertion immediately lead to the question: What does it mean for a state to be "correct"?
Earlier, in <Dat 90, p. 275>, we find: "... database consists of some configuration of data values, ... (which) ... is supposed to 'reflect reality' (i.e., it is supposed to be a model ... of some piece of the real world ... )". (As we already stated, it would be much more suitable to say that a database is a theory rather than a model. Namely, it is the theory we intend to "reflect reality"!)
"Now, some configurations of values simply do not make sense, in that they do not represent any possible state of the real world", continues Date.
All that sounds well; however, there are too many "critical" (not well Refined) concepts here: in addition to "correctness", we now also have "sense" and "possible states of the real world". Let us start with the last one.
Date says (same page) that "weights cannot be negative in the real world". Sounds wise. However, strangely enough, temperature can! Moreover, even the water level of a river can be negative! (I must confess that this "fact" perplexes me anew whenever I hear such a report. I always have an impression that a river somehow went underground!)
With these examples, we simply wanted to ilustrate that it is not suitable to speak in terms of
what "can" or "cannot" be, or what is " (im) possible" in the "real world" (which is itself not a very clear concept!). Therefore, we propose to move the discusion to the level of contradiction and (in)consistency, which are well defined concepts, and also "manipulable" in the computational sense.
Philosophically speaking, the first reason for such an approach would be that there is no such a thing as a "mere fact": Facts are always something already shaped in (or by means of) our language and measures! (Well, even if (at some "deep level") there is the True Reality, it is - by definition - indiscernible for us, because the "eyes" and the evaluation of the "seen" will always be ours!)
Now, (database-specific) integrity constraints would express that (relevant) knowledge which is already "built-in" (contained) in our language and measures. Such integrity constraints would not protect the database from "asserting impossible things" but would simply prevent such changes which would lead to contradiction with the knowledge which tacitly holds in the language and which is formally expressed by the database-specific integrity constraints. For exampile, a constraint concerning (our conception of!) weight could state (in some DDL of DBMS):
"There is no such a thing as a weight less than zero."
Now, if some update would lead to a state in which some value for the atribute WEIGHT would become "less than zero", it would mean that this update would make the database inconsistent! In such a way, the concepts of "cor-
rectness", "sense" and "(in)possibility" are reduced to the basic (and "most suitable") concept of consistency.
Inconsistent theory don't have a model; therefore, we can say with certainty that an inconsistent database would not speak of the "real world" (not even of an "ireal" one, at least not inteli-gibly). (Note that in such a "conceptual (data) system", integrity constraints are part of the database (theory), although they do not in general state "isolated facts" but "rules" which single facts must not contradict.)
Of course, it is not practically possible to prevent all possible errors in the database on the formal level. However, we hold that those preventive measures which are possible should be best done (defined) by means of (database-specific) integrity rules, where integrity is reduced to the concept of consistency.
base-specific integrity rules should be treated as expressions of that knoledge which is contained (built-in) in our language, measures and atitudes. Database-specific integrity rules are, in fact, general knowledge wich should be thought (and treated) as part of the database. Such a conception and role of the integrity allows us to reduce the concept of "database correctness" to its consistency (as a theory) . Of course, at the operative level (i.e., at the level of the DBMS) they would serve to prevent those updates which would bring the database to inconsistency.
REFERENCES
<Dat 90> Date, C.J.:
An Introduction to Database Systems. Vol. 1 (Fifth ed.), Addison-Wesley, 1990.
5. Conclusion
By discussing integrity rules in the relational data model, we tried to show and emphasize the suitability of the logic, proof-theoretic approach to the definition (or conceptual foundation) of data models in general.
By claiming that general integrity rules are "superfluous" we didn't mean that their content is irelevant, but that this content could be stated (expressed) within definitions of the primary and foreign key. In that case, general integrity rules (as defined e.g. in <Dat 90>) could be treated as simple "corollaries" (i.e., evident consequences) of those definitions.
On the other hand, the data-
<Gal 78> Gallaire, H., Minker, J. (eds):
Logic and Data Bases. Plenum Press, 1978.
<Gro 90> Groff, R.J., Weinberg, N.P.: Using SOL. McGraw-Hill, 1990.
<Rad 87> Radovan, M.:
"On Deduction and Consistency in Clausal Logic", Acta Analytica, No 3, 1987.
<Rei 84> Reiter, R,:
"Towards Logical Reconstruction of Relational Database Theory", in Bro-die, L.M. et all (eds): On Conceptual Modeling. Springer-Verlag, 1984.
UNDERSTANDABILITY OF THE SOFTWARE ENGINEERING METHOD AS AN IMPORTANT FACTOR FOR SELECTING A CASE TOOL
Keywords: CASE tool, engineers testing, learning properties, software engineering
I. Rozman, J. Györkös, K. Rizman University of Maribor Faculty of Technical Sciences Smetanova 17, 62000 Maribor, Slovenia
ABSTRACT — The article highlights the un-derstandability of a software engineering methodology as an important criterion for selecting a CASE tool. This aspect is treated through the comparison of learning properties for two very well known methodology on which the CASE tools are usually based on. The first one is SA-SD and the second one is JSD. In the purpose to compare both methodology a group of young engineers has been tested. Each of them wrote a seminar theme, answered a questionnaire and explained his observations. At the end of the paper, a general conclusion is presented.
1 Introduction
Computer - Aided Software Engineering ( CASE ) tools are coming into widespread use in the software engineering. These tools automate methods that can improve software development practice and help to improve the quality of a software product. Choosing a CASE tool can be a difficult ahd confusing task because the great number and variety of tools are on the market. Many potential user of the CASE tool base their selection upon literature from the vendors, perhaps with a trial period using a demo system.
In article [6] a method for selection a CASE tool is described as a six step process:
•	define the CASE requirements,
•	contact vendors for information,
•	select systems and vendors for in-dept evaluation,
•	require vendors to respond in writing to the CASE requirement and to loan demonstration copies of the system trial use arid evaluation,
•	if possible, visit vendors at their home sites,
•	select a CASE system for purchase.
In the first step, analysis and/or design methodologies which support the tool as an overall system requirement are expressed. It should be noted, that the tool
•	must have a full semantic understanding of the graphical and textual object comprising each analyses and design component,
•	must handle a minimum number of levels (e.g. 10 or 15) in hierarchical analyses or design methodologies, and a minimum number of components such as data dictionary entries, data-flow diagrams, or structure charts,
•	must support completeness and consistency checking across the analyses and design and through all levels of the analyses hierarchy.
But, the influence of methodology to be learned itself, is not observed in this article. Methodology is prerequisite and essential for using the CASE tool. The importance of this criterion, as an important criterion for characterizing the CASE tool, was factually not expresséd in last workshop CASE 90 [2]. But from our experience, we know that a full satisfaction with a CASE tool can be achieved only if users like to use them. A tool must be based on methodologies which are close to the way of the user's thinking and close to his/her experience in the past, or that it aids his/her existing knowledge.
In order to highlight the problem of friendliness of a CASE tool to the user, we have compared two formal methodologies.regarding to the user's capability to understand it and to learn how a particular method can be applied to the software development. The both chosen methodologies are taken from the two main groups and are quite different. These groups are:
•	Data Flow Oriented Methodologies and
•	Data Structure Oriented Methodologies.
From the first group the well known SA-SD methodology (Structured Analysis according to DeMarco [1] and Structured Design according to Yourdon and Con-stantine [5]) was chosen. From the second group the JSD methodology [4] (Jackson System Development, author is M. Jackson) was chosen, because this methodology is the most typical and in certain expert circles most widely used. And what has not the least importance, some authors classify this methodology near the object oriented ones (e.g. [3]).
Our comparison is based on an experiment in which we tested some engineers to find out which/methods are easier to learn.
2 Experiment description
Experiment hćts been applied to twelve person tested who learned the both mentioned methodologies during the post - graduate study. Eight of them are electrical engineers, two are mechanical engineers and two are civil engineers. With the aid of lectures attended (fifteen hours) and literature studied each of them had to solve a problem, approx. 3000 LOG, in the form of a seminar work and according to methodologies cited above. The problems to be solved were mainly procedural oriented, but some of them had important data component, too. If difficulties in individual design appeared consultations were given. When their work was finished they presented their results and answered the questionnaire given. At the samè time they passed the examination.
2.1 Questionnaire
The questionnaire is divided into two logical unit. The first two questions are general. The answers are expected to reflect the influence of previous skill of students for modelling a real world. The last four questions are expected to give an individual note of both methodologies and to show which methodology the young engineers are more familiar with. A descriptive manner of answering is foreseen for the last four questions. The narrowness of possible answers and their misguiding influence are avoided, but a descriptive treatment of the results of the questionnaire is needed. For the presentation in the last question the well known Osgood's Semantic Differential with four-level scale is used .
QUESTIONNAIRE
1.	Which programming language is most often used in your programming experience?
a)	FORTRAN
b)	Pascal
c)	Other
d)	None
2.	Your task is to model a part of the real world into a software system. When such task is given to you, do you think that you understand the required reality:
a)	Completely
b)	Only main aims are known; the details are unknown.
c)	The details axe known; their uniting into a system is unknown.
3.	If you don't understand the problem completely, the reason is as follows:
a) Ignorance of the skilled perspective of
reality.
b)	It is not known how to express the function of the problem ( It can only be "felt" )
c)	Others
4.	What do you think of a problem that should be solved?
a)	The model of reality is seen.
b)	The model is seen as a transformation of the input picture into the output picture.
5.	Which software formal developing method are you going to use with your future work?
a)	JSD
b)	SA-SD
c)	None
6.	Why čire you going to use the method marked under point 5?
a)
b) c)
(give at least two answers)
7. Why aure you not going to use the other method mentioned or even none of them?
a)
b) c)
(give at least two answers)
8. With the marks 0 (very bad), 1 (bad), 2 (good), 4 (very good) try to express the degree of satisfaction of paxticulair activities in the life cycle for both methods
A - assistance in formulation
of requirements B - quick detection of faults
C - surveyabiI i ty
D - simple maintenance of
end-product E - simple completion of end-product
JSD	SA-SD
	
	
	
	
	
Figure 1. Questionnaire
2.2 Interpretation of Answers
The answers to the first five questions are shown in the tabular form on the figure 2.
answer	1	2	3	4	5
a	10	2	7	3	1
b	2	8	2	10	11
c	0	2	3	X	0
d	0	X	X	X	X
Figure 2. Tabular presentation of answer to the first five questions
Most young engineers answered that they are familiar with the FORTRAN language. This is understood because the young engineers mostly learned this language during their regular education. To have only a skill about FORTRAN means that these people are "half ilhterate" as regards programming. It is sure that ignorance of data part of the program makes the understanding of any software development methodology difficult. In the SA-SD methodology this is seen from the difficult understanding of the data dictionary and data handling in the files as a data base. In the JSD methodology, where entity structure is dominant, ignorance of the data part of the program was undoubtedly one of the reasons for more difficult understan-dability.
The answers to the second question show that the tested persons tried to get the most abstract picture of all important functions. Two of them decided that they had known details but they had not had a clear perspective about uniting details into the system. The conversation in the experiment showed that in these two cases tested people were working on the problem long time and the seminar work done during the experiment was prolonging their continuous work.
The answers to the questions three and four show that in the most cases the functional decomposition was used as appropriate way of thinking for decomposing a problem into small pieces. The fifth question demanded a concrete decision regarding the methodology used in the future by the individual. The majority (eleven persons) decided to use the SA-SD methodology. Let us consider some most important arguments for preferring SA-SD methodology which were answered under question six:
•	methodology was easy to learn,
•	the philosophy of this methodology is close to my way of thinking,
•	a clear model is quickly reached and
•	the methodology is simple and efficient.
The JSD methodology was negatively appreciated (answers to question seven). The arguments are as follows:
•	it is difficult to learn,
•	analysis from the entity/action aspect is difficult to understand and
•	implementation is not simple.
The presented seminar works also showed worse understanding of the JSD methodology. Where usually had the tested people problems? In the first "entity action step" they were in doubt about boundary of the modelled system. They enumerated actions easier as they decided about entities. The second problem, which appeared, was the understanding what the entity is? They usually forgot that actions must appear on the entity what is not the same as the entity in the E-R (Entity-Relationship) diagram.
In the second "entity structure step" tested person had problems to understand that each structure in Jackson's diagram has only two levels. The first level is the structure's name and the second level form the parts of this structure, while in the Structure Chart each box represents a program module. In the "initial model step" - step three seems difficult to understand what really a process marked by zero and process marked by one means. In the beginning, it was not very clear to the students why the same object is treated as structure of entity in step two and as process in step three. This was the most repeated question which tested persons had during the working their seminar work.
When the first steps were understood the remaining three did not cause greater problems. We are surprised that the function of scheduler (implementation step) is quickly understandable, what means that testes had enough knowledge about concurrent programming. The essence of Jackson's pseudo cod is well accepted, too.
The answers to the eighth question are shown in a graphical form as a average values of collected" points of semantical differential. The result's are surprising. Despite of the negative attitude towards the usage of JSD methodology, both methodologies are relatively equally assessed; figure 3. Cumulation of points for question "E" is greater for JSD as for SA-SD. This means that young engineers decided correctly, accepted the essence of both methodologies, and assessed that JSD is moré appropriate for completion of end product than SA-SD.
»era^e
2.6 -
2.4 z.z 2 1.9 1.6 14 1.2 1
0sasd
□jsd
-	
	
1 i	
j i	
k	
Figure 3. Presentation of the answers to the eight question
3 Conclusion
It should be stressed that it is not our intention to compare all aspects of both methodologies used in the experiment but only to present that the learning aspect of a methodology is an important criterion which has to be taken into account in the process of selecting a CASE tool. To ćissess this criterion we suggest the usage of a questionnaire like this one, presented in our paper. We are aware of the fact that such exhaustive investigation the problem of the un-derstandability the methodology, as it is presented in the paper, is too time consuming. But however, some problems such £is: types of problems which are usually solved by the group, previous skill of group about modelling real world and programming, familiarity with software engineering methodologies, satisfaction with proposed methodology, should be answered by the questionnaire. The most time needed for questionnaire can be saved with reducing problems with which person are tested. In our experiment we intentionally have not used any CASE tool because we were observing only methodologies themselves. The usage of any tool would make our picture about methodology learning unclear. We have not evaluate the influence of the tool's teaching component. This is a very difficult task which demands additional investigation and it is valid for a particular tool only.
The results obtained speak in favour of the SA-SD methodology because it is more understandable to the group of engineers who represent, in our case, the potential user of selected CASE tools. Perhaps, we are wondering, why SA-SD is better assessed than JSD? Our opinion that we obtained such result is, that in engineering curriculums people have gotten much more skills about programming with procedural languages than programming with object-oriented languages. So, we can legitimately expect that those CASE tools which support data flow oriented methodology (like SA-SD) need a shorter training period for people with engineering education than those CASE tools which support other methodologies.
If we want to select a CASE tool for another group of users which have got more knowledge and skills in object-oriented programing it is possible that we achieve another fully opposite conclusion about the methodology supported.
References
[1]	T. DeMarco Structured Analysis and System specification, Prentice-Hall, 1979
[2]	R. J. Norman, R. V. Ghent. (Editor), CASE'90, Four Internal Workshop on Computer-aided Software Engineering, Irvine, CA (December, 1990).
[3]	B. Henderson-Sellers, J. M. Edwards, The Object - Oriented Systems Life Cycle, Communication of the ACM, vol. 33, no. 9, Sept. 1990, pp. 143-159
[4]	M.A. Jackson, System Development, Prentice-Hall, 1983
[5]	E. Yourdon, L.L. Constantine, Structured Design: Fundamentals of a Discipline of Computer Program and System Design, Prentice-Hall, 1979
[6]	L.Zucconi, Selecting a CASE Tool, ACM SI-GSOFT, vol. 14, no. 2 Apr 1989, pp. 42-44
O PRESLIKAVI HADFG NA TAS
INFORMATICA 3/92
Keywords: tree, network, allocation, network construction
Peter Zaveršek*, Peter Kolbezen** * VELCOM d.o.o., Foitova 8, Velenje Institut Jožef Stefan, Jamova 39, Ljubljana
POVZETEK. Delo obravnava preslikavo algoritma, ki je določen s hierarhičnim acikličnim grafom pretoka podatkov (HADFG), na drevesno avtomatno strukturo (TAS). Predlagani postopek preslikave upošteva prostorsko optimizacijo avtomata. Podana je primerjalna analiza med avtomatom z drevesno in avtomatom s toroidno strukturo. Na osnovi te analize so pokazane dobre in slabe strani obeh struktur avtomata.
ALLOCATION OF HADF GRAPHS ONTO A TREE STRUCTURE. Hierarchical acyclic data flow graph (HADFG) tree-shaping form encouraged us in investigating a possibility of their allocation onto a tree-like automat structure (TAS). Various approaches can be used in order to obtain an appropriate structure. The paper proposes an analytical space-optimizing approach towards the network construction. Further, execution results on such a network are compared to the ones obtained by a torus-like network and the behaviour of each of them is discussed.
1. Uvod
V delih [1, 2] je opisan večprocesorski sistem za učinkovito izvajanje hierarhičnih acikličnih grafov pretoka podatkov (HADFG). Sistem ima toroidno avtomatno strukturo. Preslikava HADFG na takšno strukturo je posredna. Mehanizem posredne preslikave s svojimi neželenimi vplivi podaljšuje čai izvajanja HADF grafov, ker zahteva zase del procesorskih zmogljivosti. Tako si lahko upravičeno zastavimo vprašanje uspešnosti neposredne preslikave HADFG na • avtomatno strukturo. Postopek preslikave, če naj bo uspešen, mora v povezavi z avtomatno strukturo čim manj obremenjevati procesorje. Preslikava naj bo zato neposredna, procesorji v strukturi pa statično povezani. Zaželena je avtomatna struktura, ki se povsem ujema s programskim grafom v času izvajanja grafa. Procesorji v dinamično rekonfigurabilnem polju, kot npr. [3] ali sistemi ParsyTec-a [6], bi poleg kompleksnej.še strojne opreme zahtevali dodatne procesorske zmogljivosti za povezovanje v času izvajanja. Omenjene sisteme bi lahko uporabili kot osnovo statičnim sistemom, če bi procesorje v njih ustrezno povezali pred začetkom izvajanja programskih grafov. Procesorji v statični strukturi, ki jo zahtevamo, bodo predvidoma manj izkoriščena kot tisti v toroidnem sistemu, ker se statična struktura ne more prilagajati trenutnim razmeram v sistemu (zasedenost, razpoložljivost procesorjev). S transformacijo DFG v HADFG dobimo drevesni program-
ski graf s korenom zgoraj, in vejami, ki se širijo od korena navzdol [1]. Kot je splošno znano, razlikujemo pri drevesnih grafih več tipov vozlišč. Koren grafa je vozlišče, ki nima predhodnika, in ima enega ali več naslednikov. Razvejišče je vozlišče, ki ima enega predhodnika in enega ali več naslednikov. Vozlišče grafa, ki ima le predhodnika in nima nobenega naslednika, imenujemo list grafa. Če poskušamo takšen graf čimbolj neposredno preslikati v avtomat, lahko sklepamo da bo imela tudi avtomatna struktura drevesno obliko. To nas je vzpodbudilo k primerjalni raziskavi drevesne avtomatne stuk-ture in že v delih [1, 2, 4] obravnavane toroidne strukture. Pričakujemo, da bo neposredna preslikava na drevesno avtomatno strukturo (TAS) ponudila boljše rezultate glede na čas izvajanja vsaj za neko družino HADF grafov. Družino HADFG, ki se bo uspešneje izvajala, želimo tudi identificirati. Zato poskušamo v tem delu odgovoriti, ali je za izvajanje alogritmov, ki so predstavljeni v obliki HADF grafov, učinkovitejši toroidni sistem ali TAS.
2. Drevo in torus
Predlagana toroidna struktura v delih [1, 2] je sestavljene. iz množice prepletenih zank (prstanov) trans-puterjev. Vsak transputer v avtomatni strukturi je fizično vezan na štiri sosede. Komunikacija med njimi je krožna po zankah, ki sestavljajo torus, in poteka eno-
smerno. Vsak procesor ima zato le dva logična soseda. Komunikacijske zanke ponujajo možnosti dvostranskih prenosov, ki jih izkoriščamo tako, da znotraj ene fizične zanke vzpostavimo dve logični komunikacijski zanki. Medtem, ko se po eni prena.šajo podatki, ima druga funkcijo prenosa krmilnih sporočil in ukazov. Zasnova sistema podpira dinamično, "run-time" razporejanje procesov glede na proste vire v polju. Izbrana arhitektura, podprta s preprostimi mehanizmi optimizacije razporejanja, omogoča skupaj z uporabljeno arhitekturo sorazmerno učinkovito preslikavo programskega grafa na statično povezano polje procesorjev.
Vsi procesorji v toroidnem polju imajo enako število sosedov, zato so si enakovredni ne glede na položaj v vezju. Ker imajo vsi procesorji logične naslednike, se polje navidezno nikjer ne zaključi. Izvajanje programskih algoritmov, ki so predstavljeni v obliki HADFG, je, zahvaljujoč virtualni razširljivosti toroidnega polja, učinkovito in uspešno tako pri manjšem, kot pri večjem številu procesorjev.
Drevesna struktura za razliko od toroidne ni virtualno razširljiva. Terminalni procesorji (listi drevesne avtomatne strukture) nimajo naslednikov. Širjenje HADF grafa po takšnem polju se zaustavi na terminalnih procesorjih, kjer se struktura zaključi. Zato drevo ne ponuja vsem procesorjem enakovrednega položaja v strukturi. Učinkovita preslikava HADF grafa na drevesno strukturo zahteva ustrezno razvejanost in globino strukture.
Drevo torej ni tako prilagodljivo, kot je torus. Če želimo izvajati programski graf na statično povezani drevesni avtomatni strukturi, moramo ustrezno strukturo praviloma zasnovati vnaprej. Struktura je lahko predvidena ali za vsak HADF graf posebej ali za neko natančno določeno družino HADF grafov.
3. Določitev drevesne strukture
Učinkovito izvajanje algoritma, ki ga predstavlja določen HADF graf, zahteva ustrezno drevesno av-tomatno strukturo. Razsežnost avtomata mora biti vsaj takšna, kot je razsežnost preslikave grafa. Globina avtomatne strukture mora biti vsaj enaka številu paralelnih nivojev HADF grafa, medtem ko mora širina na opazovanem delu ustrezati številu paralelnih vej v vozliščih grafa, ki se bodo preslikala na to avtomatno vozlišče.
Zahtevamo, da je avtomatna struktura splošna. Ustrezati mora vsakemu HADF grafu dane oblike in mora zagotavljati neomejeno širjenje procesorskih aktivnosti v njej, neodvisno od časov izvajanja posameznih procesov. Posledica pogoja takšne časovne neodvisnosti je, daje tudi rezultat optimizacije skromnejši. Primer optimiranja avtomatne strukture je npr. sekvenčno izvajanje dveh kratkih paralelnih procesov ob tretjem zelo dolgem, s čemer lahko prihranimo kakšen procesor. V nadaljevanju bomo nakazali možne poti, ki nas pripeljejo do ustreznega avtomata.
'I
ÖAÖ
/ I	/, \	/ I \	I \
Slika 1: Izhodiščni HADF graf 3.1 Prekrivanje
HADF graf natančno predpisuje način izvajanja posameznih vej v skladu s tipom veje (paralelna, sekvenčna). Možnost, ki se sama ponuja, je neposredna preslikava grafa v avtomatno strukturo. Glede na tip veje lahko zaključimo naslednje:
•	Paralelne veje: Vse paralelne veje, ki izhajajo iz istega (paralelnega) vozlišča, se izvajajo sočasno. Izvajanje ostalih paralelnih vej grafa glede na opazovano vejo je določeno z njihovo lego v grafu. Zaželeno je, da se paralelne veje znotraj enega paralelnega vozlišča, kot tudi vse njim paralelne veje drugod po grafu, izvajajo sočasno. Zajeti želimo ves ponujeni paralelizem in tako doseči največjo stopnjo paralelnosti izvajanja. S tem bo tudi hitrost izvajanja največja. Med izvajanjem moramo imeti vsak trenutek na razpolago zadostno število procesorjev, odgovarjajoče številu procesov, ki jih je v danem trenutku možno izvajati sočasno. Procesorji morajo biti medsebojno povezani tako, kot zahteva HADF graf, saj v nasprotnem primeru preslikava procesov nanje ne bi bila možna.
•	Sekvenčne veje: Sekvenčne veje se izvajajo druga za drugo. Pravimo, da so si tuje. Pri izvajanju izrabljajo isti del avtomatne strukture. Kaskado večih zaporednih sekvenčnih procesov lahko obravnavamo kot en sam proces. Vse procese, ki sestavljajo kaskado, preslikamo na isti procesor. Podobno obravnavamo podgrafe, ki si sledijo drug za drugim. Tudi te preslikamo na isti del avtomatne strukture. Zavedati se moramo pomembne razlike med procesi in pod-grafi. Posamezni procesi zasedejo le en procesor, medtem ko je razsežnost in oblika zahtevanega avtomatnega polja za podgraf določena s pripadajočo globino in širino podgrafa. Potrebno globino podavtomata določa število paralelnih nivojev najglobjega podgrafa. Število procesorjev na posameznem nivoju je enako številu paralelnih vej tistega peralelnega vozlišča nivoja, ki ima največje število vej.
Gornje ugotovitve strnimo v preprost postopek, poimenovan prekrivanje. Z njim je že mogoče določiti
avtomat. Postopek prekrivanja na primeru grafa iz slike 1 prikazuje slika 2 in poteka takole :
1.	postopek pričnemo izvajati na podgrafu, ki je določen s skrajnimi levimi sekvenčnimi vejami podgrafa (slika 2-1).
2.	Preslikamo vozlišča v procesorje po naslednjem pravilu:
•	sekvenčna vejišča se preslikajo v procesorje, povezave med procesorji pa določajo paralelne povezave grafa
•	procesi (listi HADFG drevesa) se preslikajo v procesorje
•	če v avtomatni struktruri na mestu, kjer bi moral biti procesor slednjega še ni, ga dodamo (temnejši proce.sorji na sliki 2)
•	če ima avtomatna struktura več procesorjev, kot je potrebno, jih ne odvzemamo
3.	Izberemo naslednjo sekvenčno vejo na najnižjem sekvenčnem nivoju (naslednji podgraf) in nadaljujemo od točke 2 dalje, dokler ni obdelan celoten graf (slike 2 II-IV).
Metoda prekrivanja avtomatne strukture z ustreznimi deli grafa, nam omogoča enostavno konstruiranje avtomatne strukture. Tako pridobljena avtomatna struktura popolnoma ustreza danemu grafu, vendar je v splošnem predimenzionirana.
Ugotovimo lahko, da je možno graf ustrezno preoblikovati in realizirati funkcionalno enakovredno strukturo z manjšim številom procesnih elementov.
3.2 Urejeno prekrivanje
HADF graf ima v splošnem nesimetrično obliko. Nesimetričnost se odraža v različnih globinah podgrafov istega nivoja, in v različnem številu vej, ki izhajajo iz posameznih paralelnih, vozlišč grafa. Vrstni red posameznih vej znotraj paralelnega vozlišča je funkcionalno nepomemben, saj se vse veje istega vozlišča izvajajo sočasno. Ta lastnost nam daje možnost, da veje med seboj kombinatorično permutiramo tako, da dosežemo kar najboljše prekrivanje nastajajoče drevesne avtomatne strukture z obravnavanim grafom. Originalni HADF najprej graf ustrezno preoblikujemo, nakar sestavimo avtomat z zgoraj opisanim prekrivanjem.
Uspešnost postopka se kaže v prostorski optimizaciji ATS in je neposredno odvisna od preoblikovanja grafa. Iterativne metode (npr. simulirano ohlajanje) bi lahko bile zelo uspešne, vendar potrebujejo za svoje izvajanje več časa. Analitični pristop je hitrejši in zaradi drevesne strukture enostavno izvedljiv, zato smo ga uporabili tudi mi.
Prvi korak do optimizacije je torej ureditev HADF grafa. Graf uredimo tako, da znotraj vseh paralelnih vozlišč razvrstimo skrajno levo najglobje in skrajno desno najplitvejše veje. V primeru enake globine

Slika 2: Postopek prekrivanja
dveh vej ima prednost tista, ki ima večje število procesov na najnižjem nivoju. Opisani postopek prevede drevo iz neurejene v urejeno strukturo, kar lahko shematično prikažemo na sliki 3.
3.2.1 Algoritem iirejenega prekrivanja
Algoritem deluje na principu utežitve vozlišč HADF grafa. Uteži, ki jih pripišemo vozliščem, so le računski pripomočki in nimajo nobene povezave s časovnimi utežmi grafa. Primerna utežitev nam olajša postopek urejanja grafa.
Predpostavke za HADF graf:
• začetno vozlišče HADF grafa je sekvenčno vozlišče, ki predstavlja ničti nivo v grafu (/ = 0). V nasprotnem primeru govorimo o večih grafih, ki se lahko izvajajo paralelno.
Neurejena struktura Urejena struktura Slika 3; Struktura grafa
•	na koncih vej, ki izhajajo iz korenskega vozlišča, se nahajajo procesi ali paralelna vejišča. To je prvi nivo v grafu (/ = 1).
•	ko se spuščamo po grafu navzdol, se izmenjujejo sekvenčni in paralelni nivoji. Nivo v grafu se poveča z vsakim naslednjim vozliščem za ena {li+i = li + 1).
Utežitev listov in vozlišč grafa ter urejanje Prvi, prioritetni kriterij pri urejanju grafa je globina. Širina predstavlja drugi kriterij. Utežitev vej mora zagotoviti globjim vejam večjo težo ne glede na širino primerjanih plitvejših vej. Uteži moramo izbirati tako, da ima utež na najnižjem nivoju večjo težo, kot je vsota vseh ostalih uteži na višjih nivojih.
n-l
9n > Y1
1=0
Predno začnemo uteževati posamezne liste, moramo določiti težo uteži za liste HADF grafa po posameznih nivojih. Največje število paralelnih vej N, ki izhajajo iz katerega koli paralelnega vozlišča v grafu, je v skladu z gornjo zahtevo in mora biti znano. Enakovredno bi ustrezalo tudi poznavanje največjega števila paralelnih vej po posameznih paralelnih nivojih, vendar zaradi poenostavitve postopka gledamo na HADF graf kot celoto.
Uteži določamo po naslednjem pravilu:
Utež 90 {I = 0)
90 • • • izberemo: go = O
Utež qi (/ = 1)
q\ ... izberemo: = 1 Utež 92 C = 2)
n
> 90
92 > ^ 9i = A^ • 9i = -(V
Najmanjša možna razlika za
92 > A' • ■ ■ 92 = /V -f 1
Utež 93 (/ = 3)
N
93
= N-q-i = N{N-\-\) = N- + N = ^^ _ ^^ -1
1 = 1
93 = 92
utež qk (/ = k)
= 92 -f 1 = N^ + iV + 1 =
N - 1
/V
qk > 9*^-1 = •'V • qk-i = i = l
=	+ N''-^ + . . . + at + 1)
= + N'"- + --- + N- + N =
Af* - 1 N - 1
- 1
9t = 92 + 1 = N"-' -I- + jW^- + N + l =
- 1 N - 1
Pripisovanje uteži procesom HADF grafa
Ko so uteži določene, utežimo z njimi liste grafa (procese) v skladu z njihovo lego v grafu. Paralelne in sekvenčne procese obravnavamo po ločenih kriterijih.
1=1
, f ,, ,
d^ (i) G) © (D (u) ^ è ^
Slika 4: Urejen HADF graf
Paralelni procesi
•	obsegajo liste grafa na nivojih / = 2ib ;/k = 1,2,...
•	iz posameznega vejišča izhaja največ N takšnih procesov
. utež 9„ =	= ^^^ =
Sekvenčni procesi
• obsegajo liste grafa na nivojih /= 2^-- 1 ;ifc = 1,2, ...
•	število vej iz posameznega vejišča ni omejeno
•	utež qr, =	=
Pripisovanje uteži razvejiščem grafa Paralelna razvejišča (I = 2k — 1) Paralelnemu razvejišča pripišemo vsoto uteži vseh vej, ki iz njega izhajajo:
m„<Af
1p
= Z

i=l
Sekvenčna razvejišča {I = 2k)
Sekvenčnemu razvejišču pripišemo utež najtežje veje sekvenčnega razvejišča.
q, = qi 1
Ko vsem vozliščem grafa pripišemo ustrezne uteži, uredimo veje znotraj vseh paralelnih vozlišč po utežeh, od veje z največjo (levo) do veje z najmanjšo težo (desno).
Avtomatno strukturo konstruiramo iz tako preoblikovanega grafa po enakem postopku kot prej, t.j. s prekrivanjem. Avtomatna struktura urejenega grafa je praviloma optimalnejša (manjše število procesorjev) kot tista, ki jo dobimo neposredno iz originalnega HADF grafa.
Rezultat generiranja avtomatne strukture s predhodnim urejanjem HADF grafa si oglejmo na primeru. Originalni par: neurejeni graf in pripadajoča avtomatna struktura je prikazan na sliki 2, urejeni par pa na sliki 4. Vidimo, da ima urejeni graf preprostejšo avtomatno strukturo.
Opisani algoritem urejenega prekrivanja je dokaj enostaven, vendar vselej ne zagotavlja optimalnih rezultatov. Kljub temu menimo, da je dovolj uporaben za procesorje z omejenim številom zunanjih povezav pri postavki, da nastopa v paralelnih vozliščih HADF grafov praviloma več vej, kot je možnih povezav na procesnem elementu. Algoritem ima v primerjavi z iterativnimi algoritmi tudi'manjšo kompleksnost in je zato cenejši.
Na sliki 5 si lahko ogledamo preprost primer grafa, pri katerem z opisanim postopkom urejanja ne dobimo idealne avtomatne strukture. Ugotovimo lahko, da bi bila ob zamenjavi paralelnih vej III in IV avtomatna struktura manjša za en procesor.
Funkcije posameznih procesorjev prikazuje slika 6. Iz slike je razvidno, da opravljajo vozliščni procesorji le funkcijo vmesnika in stikala, in so kot taki slabo izkoriščeni. Izkoriščenost le-teh povečamo, če enega izmed procesov (če obstaja) zadržimo v paralelnem vozlišču in ga izvajamo na vozliščnem procesorju. Takšen primer za že prej obravnavani HADF graf si oglejmo

Slika 5: Primer, kjer algoritem ni optimalen
a)
b)
Slika 6: Krčenje avtomatne strukture
na sliki 6a. Procesorja 1 in 2 opravljata le funkcijo razvejišča. Ker sta neizkoriščena, smemo nanju preslikati procesa, ki se sicer izvajata na procesorjih 5 in 7. Rezultat je dodatno skrčenje avtomatne strukture, ki je v tem primeru manjša za 2 procesorja (slika 6b). Pridobljena avtomatna struktura še vedno ne upošteva časovnih značilnosti posameznih procesov in zadošča splošnemu primeru grafa dane oblike.
4. Izvajanje grafov
Regularna (drevesna) avtomatna struktura in neposredna preslikava HADF grafa nanjo, nam omogočata analitično oceno časa izvajanja. Ocena, ki smo jo napravili, je poenostavljena in daje boljše rezultate, kot bi jih dobili na resničnem sistemu, saj ne upošteva zmanjšanja moči procesiranja zaradi prenosov. Prispevek te napake ocenjujemo kot majhen, ker je intenzivnost prometa nizka (samo lokalni prenosi). Graf se bločno (koračno) širi po drevesni strukturi navzdol tako, da se od višjega na nižji nivo najprej prenese celotno poddrevo; delitev grafa na nižje nivoje se nadaljuje šele v naslednjem koraku. Avtomatna struktura mora biti prilagojena obravnavanemu grafu, zato pri preslikavi ne pričakujemo mrtvih točk (blokad).
5. Rezultati
čas izvajanja. Pri opazovanju časov izvajanja posameznih grafov opazimo, da se lahko z obravnavanimi transformacijami drevesne strukture čas izvajanja HADF grafa izboljša v primerjavi s tistim časom, ki smo ga dosegli na toroidnem polju [2, 4]. Dosežena normirana povprečna pospešitev je prikazana na sliki 7. Sortirani grafi so prilagojeni za uspešnejše izvajanje na toroidnem polju [1] in ne vplivajo na potek izvajanja na drevesni strukturi avtomata. Eksperimentalno smo ugotovili, da so rezultati na drevesu boljši pri grafih, ki imajo močno poudarjen faktor širine. Pospešitev za primer takšnega grafa prikazuje slika 8. Drevesna avto-matna struktura je manj uspešna pri globokih grafih (slika 9). Največjo prednost drevesne strukture opazimo pri izvajanju popolnoma simetričnih grafov (slika 10). Grafi te vrste so simetrični tako po zgradbi, kot tudi po času prenosov in izvajanj posameznih procesov.
Ideòno Torus K Torus 9 Torus 16 Drevo
Slika 7: Primerjava drevesne in toroidne strukture
Torus i Torus 9 Torus 16 Drevo
Slika 8: Primerjava širokih grafov
Količnik prenosnega časa. Vrednost potrebnega količnika prenosnega časa se pri drevesni strukturi giblje okoli vrednosti 20, kar je več, kot je Veljalo za toroidno polje. Razmerje Ti^v/Tp smo kljub temu ohranili na vrednosti 10, da bi bili rezultati, ki smo jih dobili za
IdeoJno Torus 4 Torus 9 Torus 16 Drevo
Slika 9: Primerjava globokih grafov
Idealno Torus 4 Torus 9 Torus 16
Globoki gran Siroki yafi
Slika 10: Primerjava popolnoma simetričnih grafov
drevo primerljivi z rezultati, ki smo jih dobili za toroidni sistem. Ocenjujemo, da je povečanje količnika prenosnega časa posledica odsotnosti interakcije prenosov sporočil med procesorji. Značilnost drevesne avtomatne strukture je namreč lokalen prenos sporočil. Prenos se izvaja le med dvema procesorjema. Istočasne zahteve za prenos po isti poti, kot so možne pri torusu, pri drevesni strukturi ni.so možne.
6. Zaključek
Di-evesna oblika HADF grafov nam je pomenila izziv za raziskavo, ki naj bi dala odgovor na vprašanje o upravičenosti izvajanja algoritmov, ki so predstavljeni v obliki HADFG na drevesni avtomatni strukturi. Rezultate raziskave smo primerjali z rezultati raziskave toro-idnega polja [2, 4]. Ugotovili smo, daje drevesna struktura glede na čas izvajanja primernejša za razreda popolnoma simetričnih in širokih grafov.
Drevesna struktura je neprilagodljiva. Meje, ki jih predstavljajo terminalni procesorji, t.j. takšni procesorji, ki nimajo naslednikov, pomenijo meje širjenja grafa. Po.sledica je, da mora biti za neblokirano preslikavo grafa avtomatna struktura dovolj razvejana. Avtomat je tako lahko bodisi splošen (predimenzioniran), bodisi takšen, da ustreza družini izbranih HADF grafov
ali nekemu določenemu grafu. Splošna oblika avtomata je drevo zadostne širine in globine, da se lahko na njega preslika vsak želeni HADF graf. Povsem jćisno je, da je takšen avtomat občutno predimenzioniran. Bolj upravičena je konstrukcija avtomata, ki pokriva potrebe določene izbrane družine HADF grafov. Avtomat bo najverjetneje za večino grafov še vedno predimenzioniran, vendar v znatno manjši meri. Namenski avtomat za nek določen graf je cenovno najboljša rešitev saj potrebuje najmanjše število procesorjev. Ozka omejenost na en sam tip grafa pa je cena, ki jo moramo plačati za takšno rešitev.
Problemi, na katere naletimo ob povezovanju procesorjev v drevesne strukture, so predvsem tehnične narave in se jim lahko do določene mere izognemo ob uporabi rekonfigurabilnega polja procesorjev. Statična polja so manj uporabna in bi bila upavičena kvečjemu za neprestano izvajanje istega grafa ali iste družine grafov.
Naslednji problem predstavlja stopnja povezljivosti procesnih elementov, ki je tehnološko omejena, medtem koje število možnih naslednikov vožlišča v grafu neomejeno. Transputerji imajo npr. štiri povezave, kar ob enem predhodniku pogojuje le tri naslednike. Dinamično rekonfigurabilna polja omogočajo navidezno poljubno število naslednikov, vendar so tudi ta omejena z zmogljivostjo matričnih stikal.
Iz obravnavanega lahko zaključimo naslednje :
Toroidni sistem je najprimernejši za grafe, ki so nesimetrični po obliki in v katerih imajo procesi različne čase izvajanja. Dekompozicija grafa po korenskih procesorjih (glèj[2]) praviloma zagotavlja krajši skupni čas prenosov in izvajanja ter občutno manjše zahtevano število procesorjev, kot drevesna struktura. Toroid si predstavljamo kot vase zapognjeno drevo, ki se navidezno nikoli ne konča. Vsi procesorji prvega procesorskega nivoja[l] predstavljajo primarne, procesorji drugega nivoja pa sekundarne potencialne naslednike. Tu lahko potegnemo vzporednice s kompleksnejšo rekon-figurabilno strukturo. Navidezna neskončnost strukture pomeni hkrati tudi večjo univerzalnost.
Čeprav je število navideznih naslednikov procesorja veliko, lahko sočasno dostopamo le do dveh. Pri prenosu sporočil ima namreč vsak procesor v torusu le dva logična naslednika, kar omejuje komunikacijske zmožnosti. Kot vemo, se sporočila prenašajo krožno po zankah torusa. Ker prenos ni neposreden, so pri svojem delu dodatno moteni tako vsi posredniki, kot tudi prenosne poti. Posledica je, da takšen sistem zelo dobro deluje z nesimetričnimi HADF grafi, kjer so prenosi razdeljeni neenakomerno. Izvajanje širokih in popolnoma simetričnih grafov je manj uspešno, ker slednji zahtevajo za učinkovito delovanje simetrično in sočasno razporejanje.
Predstavljena transformacija HADF grafa v av-tomatno struktm-o je analitična in temelji na predpostavki, da imajo procesorji neomejene zmožnosti povezovanja, in je kot taka idealizirana. Transformacija v splošnem ne zagotavlja idealnih rezultatov, vendar menimo, daje glede na nizko stopnjo kompleksnosti dovolj uporabna. Nadalje menimo, da bo potrebno večino IIADF grafov ustrezno preoblikovati še predno skonstruiramo avtomatno strukturo in jih prilagoditi stopnji povezljivosti procesorjev. Preoblikovanje izvedemo tako, da odvečne paralelne veje, t.j. tiste, ki prekoračijo število razpoložljivih povezav, potisnemo na nižji nivo v grafu. Tako preoblikovan graf bo predvidoma na vseh višjih nivojih avtomatne strukture popolnoma povezan, zato se situacije, kot je podana na sliki 5, ne bodo pojavljale.
Idealizirane drevesne strukture so se pokazale kot primerne za popolnoma simetrične in široke HADF grafe. Takšni grafi so značilni za rekurzivne algoritme [5]. Naše nadalnje delo bo usmerjeno v raziskavo statičnih drevesnih struktur z realnimi procesorji, z možnostjo preslikav algoritma nanje in uspešnosti takšnih struktur. Pričakujemo, da se bodo rezultati po času izvajanja približali rezultatom, ki jih dosegamo na toroidnem polju, pri čemer dopuščamo slabšo učinkovitost drevesne strukture.
Literatura
[1]	P.Kolbezen, P.Zaveršek, A hierarchical multimicro-procéssor system. Informatica, A Journal of Computing and Informatics, The Slovene Society Informatika, Vol.15, Nr.l, Feb. 1991, 65-76.
[2]	P.Zaveršek, P.Kolbezen, Process allocation in the multitransputer network. Informatica, A Journal of Computing and Informatics, The Slovene Society Informatika, Vol.15, Nr.4, Nov. 1991, 43-52 .
[3]	M.Szturmovvicz, M.Tudruj, A multi-layer transputer network for efficient execution of OCCAM programs, North-Holland, Microprocessing and Microprogramming, Vol.28 (1989), 133-138.
[4]	P.Zaveršek, P.Kolbezen, Dynamic-allocation on the transputer network, Proceedings of the CONPAR 92-VAPP V, Lyon, France, 1992 (in print).
[5]	B.Buchberger, J.Fegerl, F.Lichtenberger, Computer trees: a concept for parallel processing, IPC Business Press, Microprocessors and Microsystems, Vol.3 No.6, 1979, 244-248.
[6]	Parsytec Transputer Modules, ParsyTec, Gesellschaft für Parallele Systemtechnik mbH,
PREDVIDLJIVO DINAMIČNI PRINCIP RAZVRŠČANJA OPRAVIL V REALNEM ČASU
Ključne besede: strogi namenski sistem, jedro OS za delo v realnem času, princip razvrščanja, časovne in logične prioritete opravil, idealna razvrstitev opravil, zaščita skupnih virov
Barbara Koroušić, Peter Kolbezen Laboratorij za računalniške arhitekture Inštitut Jožef Stefan, Ljubljana
Vloga operacijskih sistemov za delo v realnem času (OS) postaja pri namenskih računalniških sistemih vse pomembnejša. Programer se lahko posveti razvoju programske opreme na abstraktnem nivoju in prepusti odgovornost za upravljanje z opravili aplikacije sistemskim procesom jedra OS. V članku opisujemo takšen proces razvrščanja opravil, ki se istočasno potegujejo za vire računalnika. Podan je opis in analiza dinamičnega principa razvrščanja, ki dodeljuje prednost tistim opravilom, ki so za aplikacijo pomembnejša. Hkrati upošteva tudi časovno omejenost opravil in zagotavlja njihovo pravočasno izvršitev. Princip smo poimenovali predvidljivo dinamični, ker predvideva zavrnitev opravil takoj ob prihodu zahtev za njihovo izvajanje. O zavrnitvi govorimo, ko nabor pripravljenih opravil na procesorsko izvajanje ne omogoča pravočasne izvršitve opravila. Zavrnjeno opravilo lahko preusmerimo v drugo procesorsko vozlišče, če je namenski računalnik porazdeljeni ali večprocesorski sistem. Pomembna je čimprejšnja zavrnitev, tako da ima opravilo še dovolj časa za izvršitev vseh potrebnih operacij.
PREDICTABLE DYNAMIC TASK SCHEDULING IN HARD REAL-TIME - The essential feature of hard real-time systems is that the embedded computer must deliver its results correctly and on-time - otherwise malfunction may result. To assure software constructions of such systems a support of a real-time operating system is needed. We present a task scheduling and mutual exclusion protocol as one of real-time operating system structuring mechanisms. The protocol is applicable to aperiodic tasks having specific priority and timing characteristics.
1. Uvod
Računalniški sistem, ki je prilagojen okolju, v katerem izvaja nadzor, imenujemo namenski ali vloženi (embedded) sistem. Njegova osnovna naloga je spremljanje zunanjih dogodkov in odločanje o nadaljnem dogajanju v okolju. Ker je spreminjanje stanja v okolju dinamično in pogosto tudi nepredvidljivo, mora namenski računalnik delovati pod pogoji realnega časa:
Po obsegu okolja, nad katerim ima računalnik nadzor, so verjetno največji namenski sistemi v elektrarnah, kemijsko predelovalni industriji ali v upravljanju prometa. Manjši namenski sistemi so mobilni roboti, ki jih uporabljajo za opravljanje težaških, monotonih ali nevarnih opravil [3].
Razvoj programske opreme namenskih sistemov je bil do nedavnega prepuščen izkušenim programerjem, ki so imeli bogato znanje o strojni opremi sistema. Dandanes pa poznamo že vrsto
1.	Odločitve morajo biti logično in časovno pravilne.
2.	Sistem mora delovati varno tudi ob pojavitvi morebitnih napak.
Namenske računalnike delimo glede na stopnjo upoštevanja zahtev realnega časa na stroge (hard) in mehke (soft) sisteme [1].
Potniško letalo A-320 [2] je primer sistema, ki je pod nadzorom strogega namenskega računalnika.
•	operacijskih sistemov (npr. VRTX32, FlexOS
[4]),
•	visokonivojskih programskih jezikov (npr. Ada [5], Modula-2 [6], Real-Time Euclid [7]),
•	CASE (Computer Aided Software Engineering) orodij (npr. VRTXdesigner [8]),
ki so prilagojeni zahtevani realnega časa. Uporaba tovrstnih orodij poenostavi oblikovanje namenskih
sistemov in hkrati zagotavlja večjo učinkovitost razvite kode.
Uporaba CASE orodij vodi pblikovanje programske opreme iz definicije problema. Podatkovne in nadzorne strukture visokonivojskih jezikov za programiranje pod pogoji realnega časa omogočajo razbitje problema na abstraktnem nivoju. Sistemske funkcije jedra OS {real-time kernel) pa prevzamejo odgovornost za upravljanje z opravili, ki predstavljajo osnovne abstraktne enote programske aplikacije.
Eden najpomembnejših sistemskih procesov jedra je razvrščanje sočasnih opravil aplikacije računalniškega sistema. Dogodki v okolju namreč lahko zahtevajo sočasen odziv sistema, ne glede na vrstni red prihoda zahtev za izvajanje opravil. Naloga razvrščevalnika je spremljanje dogodkov v okolju in odločanje o vrstnem redu izvajanja prebujenih opravil, saj večina namenskih računalnikov ne omogoča istočasnega izvajanja vseh zahtevanih opravil.
Princip razvrščanja (scheduling policy) je pogojen z aplikacijo. V preprostih aplikacijah, kjer je celotno dogajanje v sistemu predvidljivo, so zelo učinkoviti statični principi, ki določajo vrstni red izvajanja opravil z upoštevanjem statičnih (nespremenljivih) lastnosti opravil. Večina namenskih aplikacij pa mora upoštevati dinamično spreminjanje lastnosti opravil. Takoimenovani dinamični principi razvrščanja določajo zaporedje izvajanja prebujenih opravil med samim izvajanjem aplikacije.
Razvrščevalnik lahko teži k idealnem {feasible) ali optimalnem razvrščanju opravil. V prvem primeru , je razvrstitev pripravljenih opravil čakajočih na procesor določena tako, da nobeno opravilo ne more preseči vnaprej določene časovne omejitve {deadline). Pri optimalni razvrstitvi pa so dovoljene minimalne zakasnitve.
V nadaljevanju bomo predstavili predvidljivo dinamični princip razvrščanja, ki določa prioritete prebujenih opravil z upoštevanjem njihove časovne omejenosti ter stopnje pomembnosti za celotno aplikacijo. Časovna omejenost in pomembnost opravil sta namreč kriterija, ki se lahko medsebojno izključujeta. Opravilo, ki je časovno kritično, ima lahko nizko stopnjo pomembnosti za aplikacijo in obratno. Princip teži k idealnem razvrščanju opravil.
2. Opis PD principa razvrščanja opravil
PD princip razvrščanja opravil temelji na sledečih predpostavkah:
1.	Stanje namenskega sistema se lahko spreminja tudi asinhrono.
2.	Odziv na dogodke je časovno omejen.
3.	Opravila aplikacije so različno pomembna za delovanje sistema.
4.	Dovoljeno je prekinjanje izvajanja opravil.
5.	Dostop do skupnih virov je zaščiten.
6.	Izvajanje namenske aplikacije mora biti robustno.
1.	Dogodki, ki sprožijo izvajanje opravil v računalniškem sistemu, se pojavljajo sinhrono ali asinhrono. Trenutek, v katerem sproži asinhroni dogodek izvajanje opravila, ni znan pred zagonom aplikacije. Asinhroni dogodki lahko sprožijo izvajanje periodičnih ali aperiodičnih opravil.
2.	Dogodki v sistemu zahtevajo pravočasen odziv. Vsako opravilo je časovno omejeno. Če računalniški sistem ne more zagotoviti odziva v predvidenem (odzivnem) času, je opravilo zavrnjeno.
3.	Prednost pri izvajanju imajo opravila, ki so bolj pomembna za aplikacijo. Če procesor ni zmožen pravočasno izvesti vseh prebujenih opravil, razvrščevalnik zavrne najprej opravila z najmanjšo stopnjo pomembnosti.
4.	Ker so dogodki večinoma asinhroni in opravila časovno omejena, mora princip podpirati prekinjanje opravil. Časovne lastnosti opravil se dinamično spreminjajo in tako se tudi prednost opravil pri dostopu do procesorja spreminja s časom izvajanja aplikacije. Prekinjanje izvajanja opravil je dovoljeno, če je prioriteta prebujenega opravila višja od prioritete opravila, ki se trenutno izvaja.
5.	Opravila lahko zahtevajo dostop do skupnih virov. Metoda medsebojnega izključevanja {mutual exclusion) z uporabo monitorja, zagotavlja zaščito skupnih virov [9]. Ker pa smo želeli zadostiti tudi zahtevi po možnosti prekinjanja opravil, smo princip monitorja razširili in ga priredili za uporabo v
strogih namenskih sistemih. Podrobnejši opis sledi v poglavju 2.1.
6. Robustnost izvajanja namenskih aplikacij smo želeli zagotoviti posredno s principom razvrščanja. Opravilo, ki poruši idealno razvrstitev prebujenih opravil, je zavrnjeno že ob prihodu dogodka, ki je sprožil izvajanje opravila. Če je namenski sistem večprocesorski, se lahko opravilo preusmeri v drugo procesorsko vozlišče. Zato je zelo pomembno, da je zavrnitev objavljena, ko ima opravilo še dovolj časa, da opravi vse operacije. Upoštevali smo tudi morebitne napake pri izračunu operacij opravil. Če ima opravilo še dovolj časa, lahko ob pojavitvi napake ponovi niz operacij z alternativnimi procedurami (razširjeni mehanizem okrevanja po napaki (recovery block programming) [1]).
Rezultati matematične in simulacijske analize, ki sta jih objavila Craig in Woodside [10], kažejo na učinkovitost dinamičnega principa prednosti časovno kritičnih opravil {Earliest Deadline /Is Soon As Possible) [1]. Princip dodeljuje prednost opravilom, ki so časovno bolj kritična. Ker princip ne upošteva pomembnosti opravil za aplikacijo, smo vgradili dodaten mehanizem „izločanja" manj pomembnih opravil v primeru nasičenja v vrsti pripravljenih opravil (ready queue). To je programska struktura, ki hrani zahteve za izvajanje prebujenih opravil v vrstnem redu, kot ga določa rćizvrščevalnik.
Ob prihodu nove zahteve za izvajanje opravila r^ razvrščevaJnik preveri pogoj:
{Td, -J^Tc,)>t,n<k< m, (1) i=l
ki zagotavlja idealno razvrstitev nabora m prebujenih aperiodičnih opravil. td,, predstavlja čas, do katerega se mora izvršiti opravilo Tk ter Tc^ predvideni čas izvajanja opravila r,. Indeksi opravil so določeni z njihovo časovno kritičnostjo, i < j pri pogoju To- < tdj- t je čas prihoda zahteve za izvajanje novega opravila r„ (slika 1).
Razvrščevalnik preveri pogoj (1) le za vrednosti indeksa k > n, saj je pri nižjih vrednostih indeksa zanesljivo izpolnjen.
Ce je pogoj izpolnjen, poteka razvrščanje opravil po principu prednosti časovno kritičnih opravil.
Slika 1: Časovne lastnosti in urejenost opravil
Prednost pri dostopu do procesorja ima opravilo, ki je časovno najljolj omejeno. V nasprotnem primeru pa se vključi mehanizem za "izločanje„ manj pomembnih opravil.
Recimo, da pogoj ni izpolnjen pri vrednosti indeksa k = j, n < j < m. Potem razvrščevalnik izloči iz vrste opravilo, katerega stopnja pomembnosti je najmanjša v podmnožici prebujenih opravil {ri,r2, ...Tj} ter ponovno preveri pogoj pri vrednosti indeksa k > j.
Biyabani in Stankovic [11] sta dokazala, da je princip izločanja najmanj pomembnih opravil najbolj učinkovit. Druga možnost je izločanje opravil, katerih časovna prioriteta je najmanjša in hkrati stopnja pomembnosti ne preseže stopnje pomembnosti opravila r^. V primerjavi s prvo možnostjo, ki smo jo označili kot najbolj učinkovito, je slednja časovno manj potratna. Postopek izločanja opravil se ponavlja, dokler pogoju (1) ni zadoščeno.
Ker so predvideni časi izvajanja opravil določeni za „najslabši" (najdaljši) primer, razvrščevalnik dejansko ne izloči opravil iz vrste prebujenih opravil, temveč jih prestavi na konec vrste in obvesti sistem o predvideni zakasnitvi odziva na dogodke, ki so sprožili zahteve za izvajanje teh opravil. Sistem lahko zahteva dejansko izločitev teh opravil iz vrste pripravljenih opravil. Če je dejanski čas izvajanja opravila krajši od predvidenega, razvrščevalnik ponovno preveri pogoj (1) po zaključenem izvajanju opravila.
Če je pogoju ( 1 ) zadoščeno, je zagotovljeno idealno razvrščanje opravil, četudi je procesor 100 %
zaseden:
Tom	Tom
(2)
saj je časovna meja Td^ zmeraj manjša od časa i in velja:
lim 1--
m^co Td„
= 1.
(3)
2.1 Mehanizem za zaščito skupnih virov
Pri opisu zahtev smo omenili, da monitor, kot mehanizem za zaščito skupnih virov, ne zagotavlja pravočasnega izvajanja namenskih aplikacij v realnem času, ker ne dopušča prekinjanja izvajanja opravil v kritičnih področjih [12], Izogniti se moramo tudi težavam, ki nastopijo ob blokiranju (časovno in logično) pomembnih opravil, zaradi zasedenosti kritičnih področij z manj pomembnimi opravili:
•	verižno blokiranje {chained blocking) izvajanja opravil,
•	problem mrtve zanke {deadlock).
Opravilo je blokirano, kadar čaka na nadaljevanje izvajanja operacij zaradi zasedenosti zahtevanega vira z manj pomembnim opravilom. Težave nastopijo, ko opravilo zahteva vstop v več kritičnih področij, ki so zasedene z manj pomembnimi opravili (verižno blokiranje). Kot primer podajmo situacijo, ko opravilo tc vstopi v kritično področje. Opravilo Tß, ki je bolj pomembno, prekine izvajanje opravila tq ter vstopi v drugo kritično področje. Opravilo ta, ki je še bolj pomembno, prekine izvajanje opravila tb- Ce zahteva opravilo r^ vstop v obe kritični področji, se njegovo izvajanje blokira, ker sta področji zasedeni z opravili tq in rg.
Problemu mrtve zanke pri potegovanju za skupni vir se lahko izognemo z uporabo semaforjev [9]. Mrtva zanka pa se lahko pojavi tudi po vstopu opravil v kritična področja, ko opravila navzkrižno zahtevajo dostop do skupnih virov, ki so že zasedeni.
Princip monitorja temelji na uporabi semaforjev za zaščito kritičnih področij in signalov za
sporazumevanje z opravili, ki zahtevajo uporabo skupnih virov [9]. Princip razširimo z dodatnim mehanizmom, ki omogoča varno prekinjanje izvajanja opravil v kritičnih področjih [12]. Poleg osnovnih lastnosti opravil, ki jih mora določiti programer pred zagonom aplikacije, zahteva mehanizem seznam semaforjev, katere mora opravilo upoštevati pred vstopom v kritična področja. Vsakemu kritičnemu področju določimo prioriteto, ki se med izvajanjem aplikacije dinamično spreminja. Prioriteta kritičnega področja je enaka najvišji prioriteti prebujenega opravila, ki lahko zahteva vstop v to kritično področje.
Mehanizem za varno prekinjanje izvajanja opravil v kritičnih področjih razdelimo v dva dela. Prvi del omogoča dinamično določanje prioritet opravil v kritičnih področjih. Opravilo, ki ima trenutno dostop do skupnega vira, lahko blokira izvajanje višje prioritetnih opravil. V takšnem primeru prevzame opravilo v kritičnem področju najvišjo prioriteto blokiranih opravil. Ko izstopi iz kritičnega področja, dobi ponovno "originalno„ prioriteto. Drugi del upravlja s kritičnimi področji. Opravilo, ki zahteva ključ za vstop v kritično področje, mora ustrezati pogoju, da je njegova prioriteta višja od vseh prioritet trenutno zasedenih kritičnih področij. Sicer razvrščevalnik blokira izvajanje opravila in čaka na vstop v zasedeno področje.
Opišimo dva možna načina blokiranja opravil, ki zahtevajo dostop do skupnih virov:
1.	Opravilo T zahteva ključ za vstop v kritično področje 5, vendar ga ne dobi; ker je njegova prioriteta nižja ali enaka najvišji prioriteti zasedenih področij, S'h- Opravilo r je blokirano, dokler se področje S'h ne sprosti, opravilo v Sh pa prevzame prioriteto opravila r, če je njegova prioriteta nižja.
2.	Opravilo r je blokirano, ker zahteva vstop v področje S in ima prioriteto nižjo ali enako najvišji prioriteti zasedenih področij, Sh- Če je opravilo v področju Sh že prevzelo višjo prioriteto od predhodnje blokiranega opravila, potem ostane njegova prioriteta nespremenjena.
Dokaz, da mehanizem onemogoča verižno blokiranje izvajanja opravil, temelji na sledečih lemah [12].
LEMA 1: Če opravilo t blokira izvajanje višje prioritetnega opravila Th, potem r zaseda vsaj eno kritično področje S s prioriteto višjo ali enako prioriteti Vk v času prihoda opravila Vh (t).
Dokaz: Predpostavimo, da je najvišja prioriteta kritičnih področij, ki jih zaseda r v času t, prioriteta področja Sh- Če je ta prioriteta nižja od prioritete opravila r^, potem lahko opravilo r prevzame le prioriteto, nižjo od prioritete opravila Th.. Drugače rečeno, dokler je opravilo t^ aktivno (prebujeno), opravilo T ne bo razvrščeno tako, da bi blokiralo r^. Torej obstaja vsaj eno področje, ki ga zaseda r, s prioriteto večjo ali enako prioriteti r/j, v času t A.
LEMA 2: V vsakem trenutku t obstaja največ eno kritično področje s prioriteto višjo ali enako P, ki ga zaseda opravilo z „originalno" prioriteto nižjo od P.
Dokaz: Predpostavimo, da lema ne velja. V času t sta področji 5,- in S j zasedeni in imata obe prioriteto višjo ali enako P. Dodatno predpostavimo, da je najprej opravilo Tp zasedlo področje Si v času tp in nato opravilo r, področje S j v času tg. Prioriteti opravil Tp in r, sta nižji od P. Upoštevajoč princip našega mehanizma mora biti prioriteta opravila r, višja od prioritete kateregakoli zasedenega področja v času tg. Ker pa zahtevamo, da je prioriteta opravila Tg zmeraj nižja od P in prioriteta področja Si višja ali enaka P, pridemo v nasprotje
S pomočjo lem smo dokazali, da lahko opravilo t blokirajo le opravila z nižjimi prioritetami, ki zasedajo področja, katerih prioritete so višje ali enake prioriteti opravila r (LEMA 1). V času prihoda opravila t je zasedeno največ eno kritično področje s prioriteto višjo od prioritete r, ki ga zaseda opravilo z nižjo prioriteto (LEMA 2). Tako smo dokazali, da lahko opravilo r blokira največ eno opravilo z nižjo prioriteto in pogoj za verižno blokiranje nikoli ni izpolnjen.
Pri izboru mehanizma za varno prekinjanje izvajanja opravil v kritičnih področjih, smo se želeli izogniti tudi mrtvim zankam. Pogoj za mrtvo zanko je navzkrižno čakanje opravil, ki zasedajo kritična področja, medtem ko čakajo na semaforje področij, ki jih zasedajo ostala opravila, sodelujoča v zanki.
Predpostavimo, da obstaja mrtva zanka in ima opravilo r najvišjo prioriteto med opravili v zanki.
r zaseda področje medtem, ko čaka na semafor področja, ki je zasedeno z drugim (nižje prioritetnim) opravilom iz zanke. Dokažemo pa lahko, da opravilo, ki zaseda področje, ne more biti blokirano z nobenim nižje prioritetnim opravilom [12] (LEMA 3). Tako pogoj za pojavitev mrtve zanke ne more biti izpolnjen.
LEMA 3: Opravilo je lahko blokirano le pred vstopom v prvo kritično področje.
Dokaz: Ko opravilo r vstopi v prvo kritično področje v času t, ima. najvi.šjo prioriteto med prebujenimi opravili. Ostala zasedena področja, ki jih zasedajo nižje prioritetna opravila v času t, označimo z množico 5'. Prioriteta opravila r je zagotovo višja od prioritet področij iz S. Predpostavimo, da bo izvajanje opravila r blokirano v času ti, ti > t, ko se bo začelo izvajati opravilo z nižjo prioriteto ti. Opravilo r/ bo začasno prevzelo prioriteto od opravila r. Upoštevajoč princip mehanizma lahko opravilo r/ zaklene področje S k, če je prioriteta opravila r nižja ali enaka prioriteti 5fc. Ker nobeno opravilo ni bilo razvrščeno v času med t in ži, je množica zasedenih področij v času il enaka S in Sk € S. Tako pridemo v nasprotje, saj nobeno področje iz S nima prioritete višje ali enake od prioritete opravila r
Razvrščevalnik mora preveriti pred vstopom opravila v kritično področje, ali je njegova prioriteta višja od najvišje prioritete zasedenih področij. Ker pa smo v zgornji lemi dokazali, da je opravilo lahko blokirano le pred vstopom v prvo kritično področje, moramo preveriti pogoj le pred vstopom v prvo področje. Nadaljne zahteve za dostop do skupnih virov izvaja razvrščevalnik brez preverjanja pogoja, ali je prioriteta opravila višja od najvišje prioritete zasedenih področij.
Predstavljeni mehanizem za zaščito skupnih virov opravil vpliva na potek izvajanja opravil. Blokiranje izvajanja opravil zaradi zasedenosti kritičnih področij vpliva na odzivni čas, kar moramo upoštevati pri preverjanju pogoja o idealni razvrstitvi prebujenih opravil. V pogoj (1) vpeljemo dodatni parameter Bk'.
(TD,-{J2Tc, + Bki]>t, l<k<m, (4) i = l
ki predstavlja najdaljši čas blokiranja izvajanja opravila r^. Za vsako opravilo t^ določimo množico Zk, ki vsebuje seznam kritičnih področij, do katerih imajo dostop nižje prioritetna opravila iii je njihova prioriteta, višja ali enaka prioriteti opravila Tjt. Drugače povedano, Z^ vsebuje vsa področja, ki jih lahko zasedejo nižje prioritetna opravila v trenutku zahteve opravila r^ ali opravila z višjo prioriteto za vstop v ta področja. Seznami Zk, k = l,...,Tn se spreminjajo s časom. Ker lahko opravila blokirajo opravila z nižjo prioriteto, moramo pogoj preveriti pri vseh vrednostih indeksa k. Pogoj zagotavlja idealno razvrščanje nabora prebujenih opravil.
PRIMER: Oglejmo si primer idealnega razvrščanja treh aperiodičnih opravil z lastnostmi:
opravilo	Ta	Tc	Td	kritičnost	semaforji
n	3	2	6	2	[51,52]
T2	1	2.5	7	1	[5I,53]
T-3	0	3	8	3	[52,53]
Bi = 0.5. To je čas zasedenosti področja S3, do katerega ima dostop tudi nižje prioritetno opravilo Tß. Ker je pogoju zadoščeno, preverimo pogoj pri vrednosti indeksa k = 2:
2
Td, - {'^Tc, + B2) = S- (2.5 + 2 + 0) > 1.
i=I
Vrednost indeksa 2 označuje lastnosti opravila T3 in 1 lastnosti T2. Opravilo r3 ima nižjo prioriteto, zato njegovega izvajanja ne more blokirati T2 (Bi — 0).
V času t = 3 se pojavi nova zahteva za izvajanje opravila n. RQ = [ri,r2,r3], ?X,ri) = 1, = 2 in p{t3) = 3, c(5i) = €(82) = Pir-i) = 1 in 0(53) = p(r2) = 2. Pogoju (4) ni zadoščeno pri vrednosti indeksa k = 3:
Td, - (TC, + Bi) = 6-(2+ 0.5) >3,
Td, - {Y.Tc, + 52) = 7 - (2.+ 1 + 0.5) > 3, i = \
Tabela 1: Lastnosti treh aperiodičnih opravil
kjer parameter Ta predstavlja čas prihoda zahteve za izvajanje opravila, Tc preostali izvajalni čas opravila in To trenutek, do katerega se mora opravilo zagotovo izvršiti, sicer je zavrnjeno.
Razvrščevalnik ureja prebujena opravila v vrsti pripravljenih opravil RQ po PD principu.
V času / = O, ob prihodu zahteve za izvajanje opravila rj,' je vsebina vrste RQ = [ra]. Opravilo se takoj prične izvajati, saj je procesor prost.
Ob prihodu nove zahteve za izvajanje opravila T2, v času f = 1, vsebuje vrsta RQ = [r2,r3], tako da ima opravilo T2 prioriteto p{t2) = 1 in p(r3) = 2. Opravilo p{t2) ima višjo prioriteto od ^(rs), ker je časovno bolj omejeno. Prioritete kritičnih področij, v katera imata opravili vstop med izvajanjem, so sledeče: c{Si) = 0(53) = p{t2) = 1 in CÌS2) = P{T3) — 2. Pogoj (4) preverimo najprej za prvo opravilo v vrsti RQ {T2):
TD, - (TC, + 5i) = 7 - (2.5 -f 0.5) > 1,
Td, - Tc, -f 53) = 8 - (2 + 1 -f 2.5 -f 0) < 3, t=i
zato je potrebno izločanje manj kritičnih opravil iz nabora prebujenih opravil {ri,r2,r3}. Vrednost indeksa i = 1 označuje parametre opravila ri, i = 2 opravila T2 in i = 3 opravila T3. Bi = 0.5, ker lahko izvajanje opravila rj blokira T2 v 5i za 0.5 časovne enote. B2 = 0.5, ker lahko izvajanje opravila T2 blokira T3 v ^3 za 0.5 časovne enote.
Slika 2 natančno prikazuje potek izvajanja opravil.
V času t = 1 prekine T2 izvajanje opravila T3. Ker se nahaja T3 v kritičnem področju S2 in T2 ne zahteva dostop do skupnega področja, se izvajanje Ts V S2 nadaljuje. Ko zahteva opravilo T2 v času t = 1.5 ključ za vstop v 53, ga dobi, ker ni zasedeno nobeno področje. Opravilo T2 se ob prihodu zahteve za izvajanje Ti nahaja v področju Si. Ker je c(5i) = p(ti) in p(ri) > p(t2), blokira opravilo T2 izvajanje ti in prevzame do izstopa iz ,S'i prioriteto 1.
pri čemer sta To^ in Tc^ časovna parametra opravila T2. Najdaljši možni čas blokiranja opravila T2
42
|5il N I \
	Taì TDÌ	
. , IS3I	1 S: 1 , , n '	7"2
TA,	T.	
i i S2 1 .	1	7-3
TA, 0 .1 .2	3 .4 .5 ,6 7 .8	tirne
ces). Prav tako so določeni tudi strežni in čakalni časi opravil z eksponentno porazdelitvijo. Hitrost prihoda zahtev je podana s parametrom A, srednja vrednost dolžine strežnih časov z /j ter čakalnih časov z 7. Opravilo zapusti sistem, ko opravi vse zahtevane operacije. Verjetnost, da je opravilo prekinjeno in se mora vrniti v čakalno vrsto pripravljenih opravil je določena s parametrom (1-a).
Slika 2: Primer PD razvrščanja
3. Primerjava PD principa z dinamičnimi principi razvrščanja
Osnovo PD principa razvrščanja predstavljata princip prednosti časovno kritičnih opravil (ED) in princip kritičnih opravil [Priority Scheduling -PS). Slednji dodeli prednost pri dostopu do procesorja opravilu, ki ima tisti trenutek najvišjo stopnjo pomembnosti v vrsti pripravljenih opravil. Stopnjo pomembnosti določi programer subjektivno in se le ta med izvajanjem aplikacije ne spreminja [1].
Pri snovanju PD principa razvrščanja smo težili k odpravi pomankljivosti ED in PS pristopov. Seveda pa smo želeli ohraniti tudi vse dobre lastnosti. V nadaljevanju bomo podali primerjalno analizo, ki je sestavljena iz dveh delov, matematičnega in simulacijskega. Matematični model je zahtevnejši za izpeljavo, vendar podaja zanesljive rezultate, ki temeljijo na primerjavi lastnosti posameznih principov pod enakimi pogoji. S pomočjo simulacije pa lahko preverimo rezultate matematične analize brez upoštevanja predpostavk, katere običajno uvedemo zaradi lažje izpeljave zahtevnega matematičnega modela.

<1 -C)
Slika 3: Sistem z vrsto
Izhodni parametri našega matematičnega modela so naslednji:
1.	Izkoriščenost procesorja.
2.	Verjetnost zavrnitve opravil.
3.	Lastnosti zavrnjenih opravil:
•	Preostali strežni čas.
•	Preostali čakalni čas.
1. Izkoriščenost procesorja [U = p) izračunamo s pomočjo dveh podatkov, povprečnega strežnega časa E{Tc) ter povprečnega čćisa W, ki ga opravilo preživi v sistemu [1]:
P =
E[Tc) w ■
(5)
Če upoštevamo, da so strežni in čakalni časi porazdeljeni eksponencialno:
3.1 Matematični model PD principa
Namenski računalniški sistem lahko predstavimo kot matematični model iz teorije vrst (slika 3). Okolje pošilja asinhrone zahteve za izvajanje opravil, ki se kopičijo v vrsti pripravljenih opravil. Zahteve so časovno neodvisne in časi med prihodi opravil so eksponentrio porazdeljeni {Markov pro-
g(x) = l(x) =
(6)
potem sledi izpeljava:
C(i) = fx9(x) f ^l{y)dydx, Jo	Jo
H (t) = fgix) f ^liy)dydx, (7) Jo Jo
W'{t) =
Poraidelit8v preostalega ćakalnsga Ćaaa
ix +
2(1-AC(0)2
ifx'g{x) f ^l(y)dyd2 Jo	Jo
rx'g{x)[l-H{x)]dx), (8) Jo
h = w'{t\	(9)
W{i) = W'{t) + W"{t).
(10)
W{t) je povprečni odzivni čas opravila, katerega predvideni odzivni čas je enak t. Povprečni čas opravila s poljubnim predvidenim odzivnim časom izračunamo s približkom vrednosti t s srednjo vrednostjo E{t):
Eit)= f°°th{t)dt.	(11)
Jo
2. - 3. Podrobnejši opis analize verjetnosti zavrnitve opravil ter njihovih lastnosti smo podali v prispevku [13] ter v nalogi [1]. Zato podajmo na tem mestu le grafično primerjavo rezultatov analize dinamičnih principov razvrščanja (graf 1, 2, 3).
16 14 12 10 8 e
4
2 O
Verjetnost lavrnltve (%)
i :		
— * EDtIm O PDsim -ED	— PD 1	
	1	
		
i '		
i		
i I		□
1	0 °	—-^—
D O	* *	»
a^^ '—'S -i. —r—i Ti , , , 1		i-1-1-1-1-
Graf 2: Porazdelitev preostalih čakalnih časov zavrnjenih opravil
0.8
0.6
0.4
0.2
Porazdelitev preostalega strežnega Eass
\					
X					
					
					
2	3
y
Graf 3: Porazdelitev preostalih strežnih časov zavrnjenih opravil
trenutku potegujeta za procesor največ dve opravili. Ker pa je procesorska izkoriščenost v strogih namenskih računalnikih nizka (največ 10 % [14]) in upoštevamo Markov proces prihoda zahtev za izvajanje opravil, rezultati analize ne odstopajo močno od dejanskih. To smo tudi potrdili s simulacijo, ki temelji na bolj realnih pogojih.
5	10	15
Procesorska izkoriščenost (%)
20
Graf 1: Verjetnost zavrnitve opravil
Pri analizi matematičnega modela smo privzeli zelo močno predpostavko, da se lahko v določenem
3.2 Simulacijslci model PD principa
Program, ki omogoča simulacijo principov razvrščanja opravil, smo razvili v programskem jezi-
ku SimScript II.5 za PC kompatibilni računalnik. Uporabnik lahko spreminja sledeče parametre simulacij:
•	razvrščevalni princip,
•	dolžino simulacij in
•	časovne parametre opravil (slika 4).
^ Info	B Input B flninatton B Run	^ Results J Quit	j
Simulation Parameters
□
Scheduling Policy
Itean of Interarrlual Tlnes	.•1B8|	Response Ti»es	2
tlean of Conputation Tlnes	.16B|	Sinple Round Robin fređictdble I>ynanlc	ö
nean ot Laxities	.bsb|		
Hean ot Context Sultching Tine«	.BBlI i	PređicUble Dynanic	
Ungth of Ti«e Slice Hunter of Rejected T&sks rtunbcr of S Imi Ut tons
C
3 i'^"" I 1 Continue 1
Slika 4: Vhodni simulacijski parametri ter spremlja rezultate:
•	verjetnost zavrnitve opravil pri določeni procesorski izkoriščenosti (graf 1),
•	lastnosti zavrnjenih opravil (graf 4),
•	uteženo verjetnost pravočasne izvršitve opravil (graf 5).
Mero utežene verjetnosti izvršitve opravil smo izračunali s pomočjo funkcije:
WGR C.
= 100
E.Cc.- I {rLei I) 1 I) '
= e
1-1
(12)
Množica {rj^g} vsebuje opravila s stopnjo pomembnosti i, ki so se pravočasno izvršila in {t^/J vsa prebujena opravüa z i-to stopnjo pomembnosti za aplikacijo. Nižja vrednost indeksa i pomeni višjo stopnjo pomembnosti opravila.
B	B Input B flnimtion J Run	^ Results B Quit	|
Rejected Tasks
1 - nost critical tasltJ IB - less critical tasks
(e.g., 5(3BX) neans that 3Bz of .tasks uith cr 11icalness 5 ucre rejected)
Graf 4: Lastnosti zavrnjenih opravil
100 99.S 99 98.S 98 97.5 97
VarlBtnost Izvršitve (*)
	'—- „ •	
	i \ i\	
	1	
		
		
	k	
	-EPalm -PO.lm 1	
	J_1_	
5	10 ^	15
Procesorska izkoriščenost (%)
20
Graf 5: .Utežena verjetnost izvršitve opravil
O.T 0.6	-:-i-1-!-	—r-:-1-;-:--
0.5 r		
0		
b a	/	
b		
i		
1 0.3 1	/ JJF ^	/ y
t	- / /7	too
p		
R		
0. 1	• 1 t	1 .1. f .1.
0.20.40.60.81 :.2i.<:.51.32 ratio
Graf 6: Verjetnost zavrnitve opravil
4. Zaključek
Predvidljivo dinamični princip razvrščanja opravil, na katerem temelji jedro OS za delo v strogem realnem času, upošteva zahteve realnega časa. To pomeni, da obravnava zahteve za izvajanje aperio-dičnih opravil, ki so časovno in logično različno zahtevna za programsko aplikacijo.
V primerjavi z ostalimi dinamičnimi principi razvrščanja opravil (graf 6 [10]) lahko povzamemo sledeče zaključke:
1.	Princip PD zagotavlja pri določeni procesorski izkoriščenosti večjo verjetnost zavrnitve manj pomembnih opravil.
2.	Verjetnost zavrnitve opravil z visoko stopnjo pomembnosti za aplikacijo je manjša.
3.	Ker princip temelji na predvidljivosti, so lastnosti zavrnjenih opravil ugodnejše. Razvrščevalnik lahko preusmeri opravilo v drugo procesorsko vozlišče porazdeljenega ali večprocesorskega namenskega sistema, če je preostali čakalni čas še dovolj velik.
Področje večprocesorskih in porazdeljenih namenskih sistemov odpira nove težave, s katerimi se je potrebno soočiti. Naše nadaljne delo bo usmerjeno v raziskavo topologij namenskih sistemov s porazdeljenimi vhodno-izhodnimi napravami, ki omogočajo hitro in zanesljivo zaznavanje zunanjih dogodkov ter komunikacijo med opravili.
[6]	A. Brodnik in M. Špegel in T. Lasbaher. Programiranje z modulo-2. Informatica, Ljubljana, (2):78-82, 1987.
[7]	E. Kligerman in À.D. Stoyenko. Real-time euclid: A language for reliable real-time systems. IEEE Transactions on Soßivare Engineering, 12(9):941-949, september 1986.
[8]	Real-time software. Micro Technology, december
1991.
[9]	J.E. Cooling. Sofiiuare Design for Real-Time Systems. Chapman and Hall, 1990. ISBN 0-412-341-
• 808.
[10]	D.W. Craig in C.M. Woodside. The rejection rate for tasks with random arrivals, deadlines, and preemptive scheduling. IEEE Transactions on Software Engineering, 16( 10), oktober 1990. .
[11]	.J.A. .Stankovic. Misconceptions about real-time computing. COMPUTER, :21{i0):10-19, oktober 1988.'
[12]	M.I. Chen in K..J. Lin. Dynamic priority ceilings: A concurrency control protocol for real-time systems. Real-Time Systems - The international journal of time-critical computing systems, 2(4):325-345, november 1990.
[13]	B. Koroušić in J.E. Cooling in P. Kolbezen. Predictable hard real-time scheduling. In Proceedings of the 4"* EUROMICRO Workshop on Real-Time, junij 1992.
[14]	C.J. Paul in A. Acharya in B. Black in J.K. Stros-nider. Reducing problem-solving variance to improve predictability. COMMUNICATIONS OF THE ACM, pages 81-93, avgust 1991.
Literatura
[1]	B. Koroušić. Jedro operacijskega sistema za delo v strogem realnem času (magistrska naloga). Univerza v Ljubljani, Fakulteta za elektrotehniko in računalništvo, april 1992.
[2]	M. Thaler. Nova tehnologija v pilotski kabini. KRILA, page 28, maj 1989.
[3]	L.S. McTamaney. Real-time intelligent control. IEEE Expert, 2(4):.55-68, 1987.
[4]	Operating systems in real time. .EXE Magazine, 4(7):72-77, 1989.
[5]	W.A. Halang. Evaluation of ada from the viewpoint of control engineering. IEEE, pages 8-13, 1986.
SINHRONIZIRANA PODATKOVNO PRETOKOVNA RAČUNALNIŠKA ARHITEKTURA II
Keywords: parallel processing, dataflow computing, scheduling, allocator, performance evaluation, parallel computer architecture
Jurij Šile
Laboratorij za računalniške arhitekture Inštitut Jožef Stefan, Ljubljana
Ludvik Gyergyek Fakulteta za elektrotehniko in računalništvo,
Ljubljana
Delo obravnava problem časovne optimizacije asinhronega procesiranja na omejenem številu procesorjev. Predlagamo izvirno rešitev, ki temelji na uvedbi nekaterih mehanizmov sinhronizacije v asinhrono računanje. Graf pretoka podatkov, ki opisuje asinhrono procesiranje, opremimo s časovno optimalno sprožitveno funkcijo, ki služi tako pri vlaganju grafa v računalnik, kakor tudi pri njegovem časovno optimalnejšem izvrševanju. V ta namen smo razvili hevristična algoritma pOptSinh in TOptSinh za konstrukcijo optimalnih sprožitvenih funkcij, ki po pesimistični oceni vračata optimalno rešitev v 80% primerov. Nadalje predlagamo algoritma za dodeljevanje MinGlDol in MinGlGor, ki temeljita na optimizaciji medprocesorskih komunikacij. V primerjavi z znanimi razvrščevalnimi algoritmi dobimo s predlaganima algoritmoma boljše rezultate, kar potrjujejo analizirani primeri algoritmov za izračun hitre Fourierjeve transformacije, dinamične analize scene in LU rjizcepa matrike. Končno podajamo tudi zasnovo hibridne vzporedne arhitekture računalnika, ki podpira predlagano preoblikovanje asinhronega računanja.
SYNCHRONOUS DATAFLOW COMPUTER ARCHITECTURE - We discuss the problem of time optimization of asynchronous processing on a limited number of processors. We present an original solution to the problem based on introduction of synchronization inechanisms into asynchronous processing. The dataflow graph describing asynchronous processing is associated with the corresponding time-optimal firing function. This function is used both for loading a dataflow graph into the computer and for time-optimal graph execution. In order to do this, we have developed two heuristic algorithms, pOptSinh and TOptSinh, which are used for optimal firing function construction. According to conservative estimates, these algorithms return optimal functions with 80% probability. Furthermore, we propose two scheduling algorithms, MinGlDol and MinGlGor, which are based on interprocessor communication minimization. These two algorithms give better results compared to some other well known scheduling algorithms. This fact is illustrated in Fast Fourier Transformation, Dynamic Scene Analysis, and LU matrix decomposition algorithms. Finally, \v„ present a design of hybrid parallel computer architecture capable of supporting modified asynchronous computing.
1. Asinhrono računanje
v nadaljevanju bomo opisali način asinhronega računanja, ki ga bomo opisali s pomočjo GPP. Formalizirali bomo problema minimizacije časa oziroma procesorjev. Uvedli bomo pojem sprožitvene funkcije, ki nam bo v nadaljevanju omogočil vpeljati nekatere mehanizme sinhronizacije v asinhrono računanje.
1.1 Graf pretoka podatkov
Graf G, ki ga sestavljata množici točk V in povezav £ C V x V, označimo z G{V,£). Število točk in povezav označimo z n = |V| oziroma m = \S\. Kadar je {u,v) G S, pravimo, da je točka v neposredni naslednik točke u, in to označimo z u I—> v. Kadar obstaja vsaj ena usmerjena pot iz točke u do točke v, pa pravimo, da je v nasled-
nik točke u, kar označimo z u
v. Relacija
je tranzitivna ovojnica relacije i—Graf G je
acikličen, če ne vsebuje točke v z lastnostjo v v. Če je G acikličen, je i—> relacija stroge delne urejenosti v V, saj je irefleksivna, asimetrična in tran-zitivna. Vhodnja stopnja d'^{v) točke v je število povezav, ki se stekajo v v, izhodnja stopnja d~{v) točke u pa je število povezav, ki točko v zapuščajo. Pravimo, daje G enostaven, če obstaja.med dvema točkama največ ena povezava v isti smeri.
Naj bo G{V,£) acikličen. Tedaj zapišemo V kot:
V = Vz U V;v U VA'.
Vz, Vjv-in Vk se imenujejo množica začetnih, notranjih oziroma končnih točk. Velja naslednje:
VveVz : d^{v) = 0/\d-{v)>0,
Vt;€Vjv : d+{v) > O A d-{v) > O,
Vu e Va' :	> O A d-{v) = 0.
Če sta Vz in Vk končni, neprazni in nevezani množici, potem v G ni nobene izolirane točke.
V nadaljevanju bomo obravnavali le grafe pretoka podatkov GPP, ki so v skladu s sledečo definicijo:
Definicija: Par	je graf pretoka po-
datkov, če velja:
(a)	G je usmerjen, enostaven in acikličen;
(b)	VznVK = 9-,
(c)	IN.	□
Če je r G V, pomeni t{v) čas izvrševanja točki v pridružene operacije^.
1.2 Najkrajši čas izvrševanja
Naj bodo dani GPP = {G,t) ter točki u in v. Če velja u v, obstaja iz točke u do t; vsaj ena pot p = wi,w2,... ,Wk, kjer je = u ter Wk = v. Tedaj definiramo dolžino poti p kot ^(p) — Z^Li K'^i)- Dolžino najdaljše poti iz točke u v točko v pa označimo z £{u, v). Pot iz množice točk H v množico točk VV je vsaka pot, ki se prične v eni od točk množice H in se konča v eni od točk množice W. Dolžino najdaljše poti med množicama in W pa označimo z C{U, VV). Če vsebuje kaka od množic ali VV en sam element, pišemo namesto množice kar sam element; na primer, če je = {u}, pišemo kar VV).
Seveda je. 1{Vz,Vk) najkrajši možni čas, v katerem se še more izvršiti GPP. Označimo ga s Too, ker se GPP izvrši v najkrajšem možnem času le ob zadosti velikem (praktično "neskončnem") številu procesorjev. Če je na voljo le en procesor (zaporedno izvrševanje), pa označimo najkrajši možni čas za izvršitev GPP s Ti. Seveda velja Ti = Evevtiv)-
1.3 Sprožitvena funkcija
Naj bodo dani GPP = {G, t), naravno število T > Too ter funkcija 5 : V —^ {0,1,...T}. Če je u G V, pišemo f{v) = s{v) t{v).
Definicija: Funkcijo s imenujemo sprožitvena funkcija, če velja:
(a)	f {v) <T, Vi; g V in
(b)	u\—> v ^ f{u) < s{v), Vu,uGV.	□
Sprožitvena funkcija s priredi vsaki točki v trenutek sprožitve s{v), v katerem točka v zajame vhodne podatke in prične izvrševanje pridružene operacije. Posredno je s tem natanko določen tudi trenutek izstrelitve f{v), v katerem točka v konča svoje izvrševanje in pošlje podatke vsem neposrednim naslednikom. Zgornja definicija zagotavlja, da vsaka točka izstreli svoje rezultate pred trenutkom T; poleg tega pa proženje ter izstre-Ijevanje spoštujeta relacijo i—»•. Za dani GPP v splošnem obstaja več različnih sprožitvenih funkcij. Množico vseh sprožitvenih funkcij danega GPP označimo z S (T). Vsaka s G S (T) porodi pravilo, po katerem poteka računanje GPP. Kadar bomo želeli to pravilo posebej poudariti, bomo k oznaki s dodali ustrezni indeks. Sprožitveno funkcijo s imenujemo požrešna, če velja
5(t;) = i{Vz,v) - t{v), za vsak u G V,
oziroma lena, če velja
5(u) = T - e(v, Vk), za vsak v e V.
Požrešno^ sprožitveno funkcijo bomo .označili s s^, leno^ pa s si. Prva opisuje podatkovno vodeno računanje, druga pa računanje vodeno z zahtevo.
^Operacij posebej ne navajamo, ker za samo analizo niso pomembne.
^Požrešno iz angl. "eager". ^Leno iz angl. "lazy".
1.4	Kritične točke
Naj bo dan GPP = {G, t). Poti z dolžino ^{Vz, Vk.) so najdaljše poti v GPP.
Definicija: Točko v imennjemo kritična, kadar se nahaja na kaki od najdaljših poti v GPP. Če je O < r < (-{V z,V K.), imenujemo točko v kritična na globini t, kadar je kritična in velja i{Vz, v) — t{v) =
t.	□
Množico kritičnih točk označimo s fC, množico kritičnih na globini r pa s JC{t). Kritičnost je torej značilnost GPP samega, saj je moč enostavno pokazati, da je kritična natanko tista točka v E V, za katero velja
e{Vz, v) - t{v) = i{Vz, Vk) - Kv, Vk).
v posebnem primeru smemo kritičnost točk opredeliti tudi z vidika sprožitvenih funkcij. Naj bo dan čas izvrševanja T. Opazimo, da je levi del zgornje enačbe enak Se{v). Desni del pa je enak	ven-
dar le, če je T = Too! V tem primeru je kritični točki možno prirediti le en in en sam trenutek za njeno sprožitev, neodvisno od izbrane sprožitvene funkcije s £ <S(Too)- Značilnost točk v € /C(r) pa je, da se sprožijo natanko v trenutku r, zato jih včasih imenujemo tudi kritične v trenutku r.
1.5	Zahteve po procesorjih
Naj bodo dani GPP = {G, t), naravno število T > Tcx> ter sprožitvena funkcija s G <S(T). Kadar je r G {0,1,..., T}, definiramo
PtA^) =\{vev\ s{v) <T< f{v) }
kar je število v trenutku r izvršujočih se točk GPP oz. število procesorjev, ki so zasedeni v trenutku r. Število procesorjev, ki so potrebni za nemoteno izvršitev GPP v času T, kot to narekuje sprožitvena funkcija s, je tedaj
PT,s =
Najmanjše število procesorjev, ki so potrebni za izvršitev GPP v času T pa je
PT =
Sprožitvene funkcije, ki minimizirajo zgornji izraz imenujemo procesorsko optimalne sprožitvene funkcije - okrajšano j9-optimalne. Iskanje p-optimalnih sprožitvenih funkcij je smiselno le za
T G [Too,Ti]. Posebej se bomo osredotočili na primer T = T^o, ki opisuje iskanje minimalnega števila procesorjev p^oo ^^ najhitrejšo izvršitev GPP.
1.5.1 Ocene spodnje meje
Sedaj predpostavljamo, da je T = Too. Kot smo že omenili je problem iskanja vrednosti pj^ NP-poln. Zato nadomestimo natančno računanje p-optimalne sprožitvene funkcije s hevristično konstrukcijo sprožitvene funkcije, ki pa je "zadosti blizu" p-optimalni. Pri hevrističnem konstruiranju sprožitvene funkcije je koristno poznati čim bolj natančno spodnjo mejo za p-r^. Zato bomo v nadaljevanju uvedli nekatere metode za računanje spodnje meje PT^. Kvaliteto metode določata: časovna zahtevnost računanja in natančnost px^, ki jo določa vrednost pj^ - px^.
Fernandez - Bussellova ocena. Zelo natančno oceno za pr^ podajata Fernandez in Bussell v [1]. To oceno določimo na sledeči način. Naj bo v poljubna točka iz GPP = {G, t). Interval I{v) = [5e(v),//(i;)] imenujemo interval izvrševanja točke v. Za nekritične točke, torej točke v £ V — /C, velja t{v) < ft{v) - Se{v), kar pomeni, da se sme njihovo izvrševanje "premikati" znotraj I {v). Naj bosta Ti in r2 poljubni naravni števili in naj velja O < ri < T2 < Too- Interval J{v,ti,T2) = I{v) n [t\,T2] imenujemo interval prekrivanja točke v glede na ri in T2. Kadar je J{v,ti,T2) 0, smemo premakniti izvrševanje nekritične točke v tako, da minimiziramo čas njenega izvrševanja znotraj J(v,ri,r2). Vsoto vseh tako minimiziranih časov, gledano po vseh u 6 V, označimo s K{t\,T2). Končno smemo zapisati oceno
PT^ = mj^
K{n,T2) r2 - Ti
v nadaljevanju bomo to oceno označevali s pt^^fb-Računanje Pt^o.FB zajema obravnavo Too(Tco-|-l)/2 intervalov [ri,r2], kar pomeni, da je časovna zahtevnost reda 0{T^). Vidimo, da ima računanje PTca,FB relativno veliko časovno zahtevnost, zato si bomo v nadaljevnaju ogledali še nekatere manj natančne toda hitrejše metode za izračun pj^.
Chen - Epleyeva ocena. V je vpeljana ocena zapT^, ki temelji na povprečni vzporednosti Soo =
^To oceno je dejansko prvi vpeljal McNaughton v [3]
^ in se glasi
To oceno bomo označevali s pToo,ce-
Hujeva ocena. Hu je v [4] vpeljal oceno za px^ na sledeč način. Naj bo £(r) = {v e V | fi{v) = r}, torej množica vseh točk, ki se morajo izstreliti najkasneje v trenutku r. Potem je
PT^ = max
^ EI AO
T = 1
Hujevo oceno bomo označevali s PTca,H in jo imenovali tudi največja povprečna vzporednost.
Ramamoorthy - Chandy - Gonzalezova ocena. Ramamoorthy et al. - so v [5] izboljšali PToo,h tako, da so upoštevali tudi kritično vzporednost, ki je vpeljana kot
K = max
0<t<To<
/C(r) I .
I J. CO
Oceno so definirali kot
PT^ = max (pTco,
Njihovo oceno pa bomo označili s PToo,R-
Razširjena kritična vzporednost. Razvidno je, da je krhična vzporednost k precej šibka ocena za PToo » saj se pri relativno velikih grafih njen vpliv izniči. Takrat postane PToo.R ~ PTao,H- Eden od načinov za izboljšanje natančnosti ocene je torej izostritev kritične vzporednosti k, kar bomo storili v nadaljevanju. Predpostavimo, da je v vseh trenutkih r intervala [ri,72] v vsaki množici /C(r) po k elementov. Zgodi se, da se mora v [t\ , tq] poleg kritičnih izvrševati tudi katera od nekritičnih točk. Kadar obstaja vsaj ena taka točka, potrebujemo dodatni procesni element, torej je potrebnih K 1 procesorjev! Do podobne situacije pa seveda pogosto pride tudi v intervalih, kjer je število kritičnih točk sicer manjše od k, vendar se mora znotraj tega intervala (delno) izvrševati toliko nekritičnih točk, da skupno število potrebnih procesorjev preseže k. V nadaljevanju bomo zato vpeljali razširjeno kritično vzporednost k' in jo upora-. bili pri lastni oceni za pr^ [6].
Na končnem intervalu [O, Too] poiščimo najmanjše končno zaporedje trenutkov O = ro < n < ... < Tk = Too, in sicer takšno, da je na vsakem intervalu [rj_i,rj), j = l,2,...,k število kritičnih točk I JC(t) i stalno. To število krajše označimo s
/Cj_i. Definirajmo množico Wj_i tistih nekritičnih točk, ki zahtevajo v intervalu [Tj-i,Tj) procesor vsaj za en trenutek:
Wj_i = { veV-ICl (se(t;) > V
/e(u) >	> 3e(u))A
ifliv) < fliv) > Tj >
Izrševanje točke v € Wj_i se časovno prekriva (v vsaj enem trenutku) z izvrševanjem kritičnih točk v časovnem intervalu [rj-i,Tj). To prekrivanje je v splošnem krajše od časa t{v), kajti točka se lahko sproži že pred trenutkom rj_i in/ali konča izvrševanje po trenutku rj. Zato upoštevamo pri izračunu skupnega prekrivanja v intervalu [rj_i, r^) za vsako točko v G Wj-i le njeno minimalno prekrivanje cjj-i(v), ki je
ojj-i{v) = min{/e(u) - r^-i. Tj - si{v), t(i;)}
Minimalno potrebno število dodatnih procesnih elementov v časovnem intervalu [rj_i,rj) je tako:
=( E	/
\eWj_.	\ '
max{rj_i, rmn Se(tj)} - min{rj, ^ f,{v)}.
Končno je mogoče zapisati razširjeno kritično vzporednost k' kot
k' = max \ÌKj -t- A,) in definiramo oceno za px^ takole:
PToo =max(pToo,H,«')-To oceno bomo označili tudi .s PToo,«'-
Opisana metoda je poenostavitev Fernandez-Bussellove metode, v kateri namesto C9(T^) intervalov analiziramo največ O(Too) disjunktnih intervalov. S takšno poenostavitvijo pa se natančnost ocene ne poslabša bistveno.
n	PToo.CE	PToo.H	PToo.Ji	"Toc.'^'
1 - 20	.85897	.91815	.93984	.98225
21 - 40	.81865	.89119	.89983	.93207
41 - 60	.87800	.91306	.91595	.92843
61 - 80	.88899	.91847	.92151	.93322
81 - 100	.88649	.91497	.91904	.92596
1 - 100	.87006	.91143	.91768	.93529
Tabela 1: Relativna natančnost ocen pri t{v) = 1.
Primerjava ocen. Ocene za spodnjo mejo potrebnega števila procesorjev smo računali^
^V ta namem smo uporabili računalnik IBM PC in razvili ustrezna programska orodja.
n	ptao.cb	PToo.H	PToo.R	
1 - 20	.88188	.92392	.92392	.98498
21 - 40	.82895	.89294	.89354	.94139
41 - 60	.86430	.90486	.90486	.91888
61 - 80	.89379	.91816	.91816	.93241
81 - 100	.89224	.91446	.91446	.92759
1 - 100	.87384	.91040	.91051	.93561
Tabela 2: Relativna natančnost ocen pri t{v) < 5.
n	ptoo.ce	pt^.h		"To»,«'
1-20	.88200	.92100	.92100	.98200
21 - 40	.82912	.89350	.89350	.93622
41 - 60	.87045	.90739	.90739	.92385
61 - 80	.89447	.91911	.91911	.93026
81 - 100	.89115	.91370	.91370	.92194
1 - 100	.87510	.91072	.91072	.93348
Tabela 3: Relativna natančnost ocen pri < 10.
po Fernandez-Bussellovi, Chen-Epleyevi, Hu-jevi, Ramamoorthy-Chandy-Gonzalezovi in lastni metodi. Skupno smo analizirali 7.500 naključno generiranih grafov pretoka podatkov. Pri tem smo spreminjali število točk n < 100 in čas njihovega izvrševanja t{v) < 10. Rezultati analiz so prikazani v tabelah 1, 2 in 3. Natančnost metod smo določali glede na najnatančnejšo, tj. Fernandez-Bussellovo oceno PTocFBì saj je število PTao neznano. Rezultati potrjujejo, da je naša metoda po svoji natančnosti najbliže PToo,fBi saj je v povprečju le za 6.52% slabša, hkrati pa je za red velikosti hitrejša. Naši oceni sledijo pToo.h (8.70%), (8.92%) in ^^^cE (12.71%). Primerjava med pToo,h in PToo,R l^aže, daje slednja ocena boljša le pri tistih GPP, katerih vrednosti se spreminjajo zelo malo. Samo v takšnih grafih kritična vzporednost prevlada nad največjo povprečno vzporednostjo. Razširjena kritična vzporednost, ki smo jo vpeljali pri svoji oceni PToo,k'ì P^- prevlada tudi v tistih GPP, kjer je t{v) spremenljiv.
1.6 Zahteve po času
Naj bosta dana GPP = [G, t) in naravno število P < PToo- Iščemo najmanjše
naravno število
sprožitvenih funkcij je seveda smiselno le za p < PToo-
1.6.1 Ocene spodnje meje
Tudi problem iskanja vrednosti Tp je NP-poln, zato namesto natančnega računanja T-optimalne sprožitvene funkcije uporabimo njeno hevristično konstrukcijo. Podobno kot pri iskanju p-optimalnih sprožitvenih funkcij je tudi tu koristno poznati kar se da natančno spodnjo mejo za Tp, v nadaljevanju označeno s Tp. Tudi tokrat določata kvaliteto metode za računanje spodnje meje: časovna zahtevnost računanja Tp in natančnost Tp, ki jo določa vrednost Tp — Tp.
Hujeva ocena. Hu je v [4] vpeljal za Tp sledečo oceno: Naj bo zopet jC{t) množica vseh točk, ki se morajo izstreliti najkasneje v trenutku r. Potem je
Tp = Too + max
^ T = 1
Hujevo oceno bomo označevali s Tp^H-
Fernandez - Bussellova ocena. Izboljšanje ocene Tp^n sta opisala Fernandez in Bussell v [1]. To oceno določimo s sredstvi, ki so bUa vpeljana med konstruiranjem pt^^fb- Naj bosta ti in T2 poljubni naravni števili in naj velja O < n < r2 < Too- če je na voljo le p procesorjev, potem se izvrševanje točk znotraj intervala [tijTj] podaljša za najmanj	- (r2 - ri). Od tod moremo
določiti oceno za Tp, ki je
Tp = T
oo + max
TI<T2
K{ruT2)
- {t2 - n)
V nadaljevanju bomo to oceno označevali s fp^pB-
Primerjava ocen. V [1] je pokazano, da je Fernandez-BusseUova ocena natančnejša od Hu-jeve. Ta natančnost se doseže za ceno večje časovne kompleksnosti, ki znaša O(T^) in je za razred večja od Hujeve.
Tp > Too, za katero je množica sprožitvenih funkcij 2. Mehanizmi sinhronizacije S(^Tp) 0. Posledica pomanjkanja procesorjev je podaljšanje časa izvrševanja ATp, ki znaša
ATp = Tp-T^
Sprožitvene funkcije, ki minimizirajo zgornji izraz imenujemo časovno optimalne sprožitvene funkcije - krajše T-optimalne. Iskanje T-optimalnih
Sedaj bomo opisali hevristična algoritma za konstrukcijo T- in p-optimalnih sprožitvenih funkcij, ki ju bomo uporabili v dveh hevrističnih algoritmih za dodeljevanje; z njima dani GPP porazdelimo med procesorje [9].
vhod: GPP, p.
izhod: SGPP{p,Tp), oz. 5(u), za vsak v e V.
T := 0; Tp := 0; ? := 0; W := V repeat
if g > O then
Vp := {t; € V|/(i;) = r}; W := W - V^; q := q - \V„\ endif
V, := {u e V|i> ima vse vhodne podatke};
—	Množica izvršljivih točk je V,- = /C(r) U Vn, kjer sta /C(r) in V„
—	množici kritičnih oz. nekritičnih točk na globini r. if q < p then
if p - g < |/C(r)| then bodi Vd C /C(r), kjer je IVjI < p - q else if p - g > j V,I then Vd := V^ else
Bodi Vd C V„, kjer je \Vd\ < p - q - \JC{t)\-, Vd Vd U fC{t) endif
g := g + |Vd|	-- Sproži se nekaj dodatnih, naključno izbranih točk.
endif
forali v 6 Vd do s{v) := r endforall Tp:=r; r r + 1 until = 0;
Algoritem TOptSinh: Konstruiranje T-optimalne sprožitvene funkcije.
2.1 Sinhronizacija
Algoritma za konstrukcijo optimalnih sprožitvenih funkcij, kiju bomo opisali v tem poglavju, temeljita na spoznanju, da si moremo izvrševanje GPP predočiti s pomočjo prehajanja točk iz ene množice (stanja) v drugo. Že v prej smo vpeljali eno takšnih množic - množico IC{t) kritičnih točk v trenutku r. Nadalje za vsak trenutek r vpeljemo še množici: V,-izvršljivih točk, tj. točk, ki so zbrale vse vhodne podatke, a se še niso sprožile in Vp = {v € V|/(v) = r} pozabljenih točk, tj. točk, ki so se izstrelile v tem trenutku. V splošnem so poleg kritičnih v množici V; tudi točke, ki smejo svojo sprožitev odložiti, ne da bi to nujno vplivalo na najkrajše izvrševanje GPP. Te točke imenujemo nekritične v trenutku r in jih zberemo v množico Vn.
Par {GPP, s), kjer je s sprožitvena funkcija, ki posredno določa tudi p in T, imenujemo sinkronizirani graf pretoka podatkov ter ga označimo z SGPP{p,T). Torej T-optimalna sprožitvena funkcija določa SGPP{p,Tp), medtem ko p-optimalna funkcija določa SGPP{pt^,Too)-
2.1.1 T-optimalna sprožitvena funkcija
Za konstruiranje T-optimalne sprožitvene funkcije smo razvili algoritem, ki smo ga imenovali
TOptSinh. Ta nam za dani GPP ter vnaprej določeno število p procesorjev vrne takšno sprožitveno funkcijo 5, ki zagotavlja čas izvrševanja Tp, ki je kar se da blizu oceni Tp.
Kvaliteto algoritma smo ocenjevali z odstotkom primerov, ko je čas Tp dosegel oceno Tp^n, saj natančne vrednosti Tp ne poznamo. Algoritem je bil preverjen® nad 500 GPP in je v 75.6 % dosegel Tp = Tp,H- Obenem smo merili tudi upad idealne popospešitve Dp v odvisnosti od pomanjkanja procesorjev. Primerjava med asinhronim podatkovno vodenim računanjem (sprožitvena funkcija Sg) in sinhroniziranim podatkovno vodenim računanjem (T-optimalna sprožitvena funkcija) je prikazana v tabeli 4, kjer so podani povprečni rezulati.
Ključni del algoritma TOptSinh je v konstruiranju množice Vj, tj. v sprožanju dodatnih izvršljivih točk, kadar so na voljo prosti procesorji. Absolutno prednost pri sprožanju imajo kritične točke v danem trenutku (zaradi omejenega števila procesorjev seveda v splošnem pride do odloga sprožitve celo pri nekaterih kritičnih točkah). Uvrščanje nekritične točk v množico Vd pa smo izvajah v skladu z naslednjimi strategijami: naključno izbiranje (v vrstnem redu, kot prihajajo
® V ta namem smo uporabili lačunčdnik IBM PC in razvili ustrezna programska orodja.
vhod: GPP, Toc.
izhod: SGPP{pt^,Too), oz. ^(u), za vsak t; e V.
Izračunaj	r 0; pr«, := 0; q := O
repeat
if 5 > O then
Vp--={veV\f{v)^T}; g:=:g-|Vp| endif
V,- := {v G V|i; ima vse vhodne podatke);
—	Množica izvršljivih točk je V,- = K,{t) U V„, kjer sta /C(r) in V„
—	množici kritičnih oz. nekritičnih točk na globini r.
5 := g + 1^(^)1	— Sprožijo se vse kritične točke.
ifq< pT^ then
Bodi Vd C V„, kjer je \Vd\ < pt^ -'g;
q := q+ |Vd|	— Sproži se nekaj dodatnih, naključno izbranih točk.
endif
forali v G IC{t) U Vd do 5(1;) := r endforall PToo := max(g,pToo); t t + 1 until r = Too;
Algoritem pOptSinh: Konstruiranje p-optimalne sprožitvene funkcije.
PToo	p = 3/4pT„ p = IßpToo p = l/4pT„o		
Sprožitvena funkcija Sg			
4	0.030	0.223	1.232
5	0.016	0.121	0.454
6	0.006	0.205	0.621
7	0.004	0.104	0.761
8	0.015	0.147	0.883
9	0.006	0.071	0.397
10	0.003	0.100	0.464
E	0.011	0.139	0.687
T-optimalna sprožitvena funkcija			
4	0.011	0.211	1.079
5	0.002	0.048	0.375
6	0.002	0.117	0.537
7	0.000	0.029	0.718
8	0.000	0.044	0.789
9	0.000	0.001	0.324
10	0.000	0.018	0.311
L'	0.002	0.067	0.590
najkrajši čas izvrševanja Too vrne sprožitveno funkcijo s, ki zagotavlja izvrševanje GPP na številu procesorjev, ki je kar se da blizu ocene Pt^. Algoritem v vsakem trenutku r poskuša sprožiti čimveč, toda kvečjemu izvršljivih točk. V vsakem trenutku r sprožimo vse točke iz ÌC{t). Če je zasedenih procesorjev še vedno manj kot pTooj na njih sprožimo nekatere nekritične točke, ki jih izberemo naključno (v vrstnem redu, kot prihajajo v V,). Iz povedanega je očitno, da je pri tem odločilna natančnost PToo-
Optimalnost algoritma smo ocenjevali z odstotkom primerov, ko je pxoo dosegel oceno PTcc.H. Pt^.k' oziroma Ptoo.fb, saj natančne vrednosti pT^ ne poznamo. Algoritem je bil preverjen^ nad 1.500 GPP in je dosegel rezultate, prikazane v tabeli 5.
Tabela 4: Upad idealne pospešitve Dp.
-	—	-
PToo.R	PToo.'i'	PToo, F B
1 0.705	0.783	0.824
v V,), po naraščajočih t{v) in po padajočih t{v). Poskusi so pokazali, da nobena od strategij ni bila izrazito boljša od ostalih.
2.1.2 p-optimalna sprožitvena funkcija Algoritem pOptSinh za dani GPP ter pripadajoči
Tabela 5: Optimalnost algoritma pOptSinh.
Pri problemu optimizacije procesorjev je ključen podatek izkoriščenost procesorjev Ep, za katero želimo, da se čimbolj približa vrednosti 1. Slika
'v ta namem smo uporabili računalnik IBM PC in razvili ustrezna programska orodja.
E.
• •
• •

o o o o
o o
-tì—
o ... sprožitvena funkcija • ... p-optimalna sprožitvena funkcija —I—I—I—.—I—I—I—I—I—.—W
O 20 40 60 80 100 120
Število točk n
Slika 1: Izkoriščenost procesorjev Ep.
PToo Pi 6
4
2
s — p-optimalna
		(	, 0 '	1 °
	( 0	\J 1		
i. 0	1		■	
_1_l.
2 4 6 8 .10
PToo Pn 5 = Se
Slika 2: Potrebe po procesorjih.
1 prikazuje izkoriščenost procesorjev E-p v odvisnosti od velikosti GPP za asinhro podatkovno vodeno računanje (sprožitvena funkcija Sg) in sinkronizirano podatkovno vodeno računanje {p-optimalna sprožitvena funkcija). Računanje, ki sledi p-optimalni sprožitveni funkciji, ima mnogo manjše zahteve po procesorjih kot računanje, ki sledi 5e sprožitveni funkciji, kar potrjujejo rezultati, prikazani na sliki 2. Tudi tu smo analizirali 1.500 GPP, pri čemer smo spreminjali število točk n < 120 in čas njihovega izvrševanja t{v) < 10.
2.2 Dodeljevanje
Po končani fazi sinhroniziranja je GPP pridružena sprožitvena funkcija s in skupaj tvorita SGPP{p,T). S tem so vse v e V urejene po trenutkih sprožitve s{v). Takšna urejenost zagotavlja, da se GPP izvrši na p procesorjih v času T ob uporabi najsplošnejšega algoritma za dodelje-
vanje (algoritem NakljDod) [7], ki točko v dodeli naključno izbranemu prostemu procesorju. •
vhod: SGPP{p,T). izhod: x(t?), za vsak u G V.
Razvrsti pare (t;,5(t;)) po naraščajočih s{v) in
jih shrani v sklad S.
for g := 1 to p do F[q] := O endfor
repeat
Vzemi iz S vse pare z enakim s in jih shrani v VV. F {g I < 5} forali ti e >V do
Naključno izberi q ^ P. ■k{v) := q;
F[q] f{v); P := P - {q} endforall
VF := 0; P := 0 until 5 = 0;
Algoritem NčikljDod: Naključno dodeljevanje.
Po končanem dodeljevanju je vsaki točki v £
V	pridružen procesor z indeksom 7r(v), kjer je 1 < Tr{v) < p. V vsakem trenutku je na voljo vsaj toliko prostih procesorjev, kot je točk, ki se morajo tedaj sprožiti. Dodeljevanje teh točk je poljubno, kar pomeni, da moremo v splošnem dani SGPP{p,T) porazdeliti na več načinov. Vse dodelitve so enakovredne, saj vse zagotavljajo, da se GPP izvrši na p procesorjih v času T.
Točki M in u iz V sta ločeni, če sta dodeljeni različnima procesorjema. Povezavo med ločenima točkama imenujemo globalna povezava.
V	primeru hibridne arhitekture poteka komunikacija med ločenima točkama preko nadzorno-povezovalne enote in v splošnem zahteva čas tc > 0.
V	takšnem primeru najsplošnejši algoritem torej ne vrača več enakovrednih dodelitev, saj se število globalnih povezav spreminja. Že prej smo videli, da število globalnih povezav vpliva na čas izvrševanja GPP. Zato se bomo osredotočili na konstruiranje takšnih algoritmov za dodeljevanje, ki bodo mini-mizirali število globalnih povezav v dodelitvah [8]. Točneje: trivialni kriterij naključnega dodeljevanja prostih procesorjev bomo nadomestili s kompleksnejšim, ki se glasi:
Dodeli točke w množice W procesorjem q množice P tako, da bo ^ c{w, q) maksimalna, kjer je c(w, q) število sosednjih točk točke w, ki so bile doslej dodeljene procesorju q.
vhod: SGPP{p,T). izhod: ir{v), za vsak v e V.
Razvrsti pare (u,5(t;)) po naraščajočih s{v) in jih shrani v sklad S.
for 7 := 1 to p do := O endfor
repeat
Vzemi iz S vse pare z enakim s in jih shrani v W.
< s} forali v G W do forali qe P do
= število neposrednih predhodnikov od v, ki so bili dodeljeni v g-ti procesor, endforall endforall
Reši problem WBM za graf (VV U P, W X P), forali pare (v,q), ki so del rešitve do t:{V) := g; F[q] := fiv) endforall
]y:=0;P:=0 until 5" = 0;
Algoritem MinGlDol: Minimizacija globalnih povezav (navzdol).
Dodeljevanje, ki poteka v skladu z zgornjim pravilom, je v nekem smislu konservativno, saj poskuša točko pridružiti procesorju, v katerem je največ njenih sosedov. Opisano pravilo je primer znanega problema uteženega dvodelnega ujemanja (WBM») [10, 11]:
Naj bo dan dvodelni graf G = (W U P, E), kjer je E C }V X P ter cenovna funkcija c : E —IN. Iščemo ujemanje MCE (množico povezav M, v kateri noben par povezav nima skupne točke) tako, da je T,(w,q)€M 9) maksimalna.
Problem WEM znamo rešiti v času 0(nelogra/max(l,log^)), kjer je e = \ E \ in n =1 W I + I P I .
V algoritmu MinGlDol poteka dodeljevanje od začetnih točk proti končnim, medtem ko poteka dodeljevanje v algoritmu MinGlGor v nasprotni smeri. V obeh algoritmih se pojavlja problem WBM, pri čemer v prvem primeru določajo ceno c(tü, q) neposredni predhodniki točke w, v drugem pa njeni neposredni nasledniki.
2.3 Primeri
Z nekaterimi primeri bomo pokazali učinkovi-
tost časovne optimizacije asinhronega računanja s pomočjo mehanizmov sinhronizacije. Obravnavali bomo naslednje primere: hitro Fourierjevo transformacijo (FFT), dinamično analizo scene (DAS) in LU razcep matrike (LU). Privzeli bomo hibridno arhitekturo s p = 3 procesorji (Pi,P2 in P3), katere medprocesorsko komunikacijo t^ bomo ustrezno spreminjali. Kvaliteto naših rezultatov, ki jih dobimo z uporabo sinhronizacijskega algoritma TOptSinh ter dodeljevalnih algoritmov MinGlDol in MinGlGor, bomo primerjali z naslednjimi znanimi razvrščevalnimi algoritmi: CPM^ [12], HNF^" [13] in WL" [13].
2.3.1 FFT: Hitra Fourierjeva transformacija
Povrnimo se na primer izračuna hitre Fourierjeve transformacije na 8 točkah, ki smo ga že obravnavali v prvem delu. Predpostavimo, da se točke A, C, E, G, I, J, M, N, Q, R, S in T izvršujejo eno časovno enoto, točke B, D, F, H, K, L, O, P, U, V, W in X pa pet časovnih enot.
CPM, HNF in WL algoritmi. Za primer FFT algoritma dajejo vse tri metode (CPM, HNF, WL)
'Weighted Bipartite Matching
® Critical Path Method '"Heavy Node First "Weighted Length
vhod: SGPP{p,T). izhod: 7r(u), za vsak v £ V.
Razvrsti pare (t;,s(u)) po padajočih 5(u) in jih shrani v sklad S.
for 9 := 1 to p do := T endfor
repeat
Vzemi iz S vse pare z enakim / in jih shrani v W. P--= {q\F[q] >/}; forali t? 6 VV do forali qe P do
c{v,q) — število neposrednih naslednikov od v, ki so bili dodeljeni v g-ti procesor, endforall endforall
Reši problem WBM za graf (W U P, W x P), forali pare {v,q), ki so del rešitve do 7r(v) := q
F[qV:=s{v); endforall W:=0; P := 0; until 5 = 0
Algoritem MinGlGor: Minimizacija globalnih povezav (navzgor).
J-
_UL
rrlRRl
Pi I H I
P2 I p iQlEl P I K I X-m
P3 I F IcUl g I^UN V I w I
10
15
20
25
30
35
Slika 3: FFT: Razvrstitev po CPM, HNF in WL.
enakovredne rezultate. Točke se dodelijo procesorjem, kot je prikazano na sliki 3. Razvidno je, da dobimo v tem primeru 22 globalnih povezav. Upad idealne pospešitve Dp se pri tc > O poveča, tako dobimo pri t^ = 10 čas izvrševanja Tp - 43, kar se odraža tudi v povečanju upada idealne pospešitve Dp = 1.87. Podrobnejši rezultati CPM, HNF in WL dodeljevanja v odvisnosti od časa tc so prikazani v tabeli 6.
				
'c		Sp	Ep	Dp
0	25	2.88	0.96	0.67
2	27	2.67	0.89	0.80
4	31	2.32	0.77	1.07
10	43	1.67	0.56	1.87
Tabela 6: FFT: CPM, HNF in WL dodeljevanje pri različnih t^.
MinGlDol in MinGlGor algoritma. GPP FFT
v	.(v)	v	s(v)	v	
A	6	I	15	Q	23
B	5	J	13	R	22
C	5	K	12	S	22
D	0	L	10	T	21
E	6	M	14	U	16
F	0	N	12	V	15
G	5	0	7	W	20
H	0	P	7	X	17
					
Tabela 7: FFT: T-optimalna sprožitvena funkcija.
algoritma najprej sinhroniziramo, za kar uporabimo algoritem TOptSinh, ki vrne T-optimalno sprožitveno funkcijo. Rezultat je prikazan v tabeli 7.
Pi [
P2 [
P3
1 H	1 B	I	L lil U h-lRßl
			
1 D	IGIEI	0	INUMI V 1 W 1
			
1 F	KJlAl	P	1 K 1 X isl :
o
10
15
20
25
30
35
Slika 4: FFT: Razvrstitev po MinGlDol.
V drugem koraku uporabimo dodeljevalni algoritem MinGlDol oz. MinGlGor. Razvrstitev točk po MinGlDol algoritmu je prikazan na sliki 4, medtem ko je razvrstitev po MinGlGor algoritmu prikazana na sliki 5.
56
Pi C L
Ps C
-TgTeT
„WJN
I w I
F IclAl F I K I X ZEm
•p—r
I I, 111 u~ffm
0
10
15
20
25
30
35
Slika 5: FFT: Razvrstitev po MinGlGor.
Z uporabo algoritmov MinGlDol in MinGlGor dobimo pri = O enake rezultate kot pri algoritmih CPM, HNF in WL (Tp = 25, Sp = 2.88, Dp = 0.667 in Ep = 0.96). Pri tc > O pa naša algoritma vračata rezultate z manjšim upadom idealne pospešitve Dp. Tako je pri tc — 10 čas izvrševanja Tp = 40 (v prejšnjem primeru 43), kar pomeni, da je Dp le 1.67. Podrobnejši rezultati MinGlDol in MinGlGor dodeljevanja v odvisnosti od časa tc so prikazani v tabeli 8.
25 25 28 40
2.88 2.88 2.57 1.80
0.96 0.96 0.86 0.60

0.67 0.67 0.87 1.67
Tabela 8: FFT: MinGlDol in MinGlGor dodeljevanje pri različnih tc-
Oba algoritma občutno zmanjšata število globalnih povezav, tako dobimo pri MinGlDol algoritmu 16 globalnih povezav, algoritem MinGlGor pa nam število globalnih povezav zmanjša celo na 15.
2.3.2 DAS: Dinamična analiza scene
Za naslednji primer vzemimo algoritem za dinamično analizo scene. Algoritem DAS se uporablja pri izločanju ■ podob gibljivih objektov in je podrobneje opisan v [14]. Pripadajoči GPP prikazuje slika 6. Točke A, B, C in D se izvršujejo 345 časovnih enot, točke E, F, G in H 259 časovnih enot, točki I in J 190 časovnih enot, točki K in L 241 časovnih enot in točka M 69 časovnih enot.
CPM, HNF in WL algoritmi. Tudi v primeru DAS algoritma dajejo metode (CPM, HNF in WL) enakovredne rezultate (slika 7).
MinGlDol in MinGlGor algoritma. Oba algoritma vračata enake rezultate kot algoritmi CPM, HNF in WL, torej pri = O dobimo Tp = 1449, Sp = 2.31, Dp = 0.31 in Ep = 0.77 ter 12 globalnih povezav. Z algoritmom MinGlGor dobimo tudi enako dodelitev med procesorje (slika 7), medtem ko dobimo z al-
Slika 6: GPP DAS algoritma.
Pi I-TT
P2 I-T
P3 I-^
I P I F-
IZ3
I I I
500
1.000
1.500
Slika 7: DAS: Razvrstitev po CPM, HNF, WL in MinGlGor.
goritmom MinGlDol sicer drugačno dodelitev med procesorje (slika 8), ki pa, kot rečeno, rezultira v enako število globalnih povezev. Podrobnejša analiza pri O < ic < 300 je prikazana v tabeli 9.
tc	Tv	5>		
0 100 200 300	1449 1649 1849 2049	2.31 2.03 1.81 1.63	0.77 0.68 0.60 0.54	0.31 0.49 0.68 0.86
Tabela 9: DAS: CPM, HNF, WL, MinGlGor MinGlDol dodeljevanje pri različnih tc-
m
2.3.3 LU: LU razcep matrike
Za zadnji primer vzemimo algoritem za LU razcep matrike [15], ki je eden od najpogosteje uporabljenih algoritmov za reševanje sistema linearnih enačb. GPP LU algoritma je podan na süki 9. Točke A, F, K in P se izvršujejo 4 časovne enote, točke B, C, D in E 5 časovnih enot, točke G, L in Q 9 časovnih enot, točke H, I in J 10 časovnih enot.
Slika 9: GPP algoritma za LU razcep matrike.
Fl I C I fl I fi I rT~1
P2 I BI -P I	I L '1
P3 I A I r> I H I t I v rv
500
1.000
1.500
lAINhl I, I -T—T
P2 IklHIRI U P3 IKKil ft I
T—r
25
50
75
100
Slika 8: DAS: Razvrstitev po HinGlDol.
Slika ,11: LU: Razvrstitev po HNF.
Pi lAini ft I H-
P2 EElEmZDC
P3 iKini I, I
o
25
□ I ■•) I
50
75
100
Slika 10: LU: Razvrstitev po CPM in WL.
ko razvrstitev po HNF metodi na sliki 11. Pri analizi LU algoritma smo tc spreminjali med O in 30 (tabeli 10 in 11). Metodi CPM in WL sta vrnili 36 globalnih povezav, medtem ko je HNF vrnila le 32 globalnih povezav. Zato je upad idealne pospešitve Dp pri tc = 10 za 12.5% boljši.
točka O 13 časovnih enot, točki M in R 14 časovnih enot, točka N 15 časovnih enot, točka S 19 časovnih enot in točka T 20 časovnih enot.
CPM, HNF in WL algoritmi. LU razcep matrike je primer, da HNF algoritem vrača boljše rezultate od ostalih dveh. Razvrstitev točk po CPM oz. WL metodi je prikazana na sliki 10, medtem
tc		Sp	Ep	Dp
0 10 20 30	96 126 166 206	1.96 1.49 1.13 0.91	0.65 0.50 0.38 0.30	0.10 0.45 0.91 1.37
Tabela 10: LU: CPM in WL dodeljevanje pri različnih
tc.
«c	'■'p	5>				tc	'^P	Sp		Dp
0	96	1.96	0.65	0.10		0	96	1.96	0.65	0.10
10	122	1.54	0.51	0.40		10	112	1.68	0.56	0.29
20	162	1.16	0.39	0.86		20	152	1.24	0.41	0.75
30	202	0.93	0.31	1.32		30	192	0.98	0.33	1.21
Tabela 11: LU: HNF dodeljevanje pri različnih tc-
MinGlDol in MinGlGor algoritma. Še boljše rezultate kot HNF pa vračata naša algoritma MinGlDol in MinGlGor. Razvrstitvi točk po MinGlDol ter MinGlGor sta opisani na slikah 12 in 13.
Pi IKIM t, I r I M I M I ^ -1
Pj IFICI g I H I R I Pa IaIRIPIEI Q I J I
—1
Tabela 12: LU: MinGlDol in MinGlGor dodeljevanje pri različnih tc-
tc	MinGlGor (Dp/Dl)	MinGlDol (Dp/D^)
5	1.3729	1.3623
10	1.2216	1.2199
20	1.1260	1.1187
25
50
75
100
Tabela 13: Relativna kvaliteta MinGlDol in MinGlGor algoritmov.
Slika 12: LU: Razvrstitev po MinGlDol.
Fl IPIftI n I o I J I
P2 lA'lffI Zr I f/ I M
I (? I
Pi	f I /i I
25
50
75
100
Slika 13: LU: Razvrstitev po MinGlGor.
Pri tc>0 dosežeta obe metodi enak upad idealne pospešitve, ki je boljši od upada idealnih pospešitev metod CPM, HNF in WL (tabela 12).
2.3.4 Primerjava rezultatov
Na osnovi povedanega sledi, da algoritma MinGlDol in MinGlGor dodeljujeta GPP ob manjšem (kvečjemu enakem) številu globalnih povezav. Analiza FFT, DAS in LU algoritmov je potrdila našo domnevo, da je število globalnih povezav v tesni zvezi z upadom idealne pospešitve. S tem je upravičena naša odločitev, da smo se pri oblikovanju algoritmov za dodeljevanje osredotočili na minimizacijo števila globalnih povezav. To minimizacijo opravljata algoritma MinGlDol in MinGlGor, ki za svoje delo potrebujeta sinhro-niziran GPP. Slednjega pa konstruiramo z enim od naših algoritmov TOptSinh oz. pOptSinh. S takšno minimizacijo je dosežen zastavljeni cilj, tj. časovna optimizacija asinhronega procesiranja.
Algoritma MinGlDol in MinGlGor sta bila preizkušena nad 500 GPP, pri čemer smo spreminjali: število točk n < 120, čas njihovega izvrševanja
t{v) < 10 in medprocesorsko komunikacijo tc < 20. Število procesorjev smo omejili na p = l/2pXoo-Kvaliteto algoritmov MinGlDol in MinGlGor smo ocenjevali^^ glede na algoritem NakljDod. Rezultati so zbrani v tabeli 13, kjer so D
P'
Dl
m
Dì
upadi idealne pospešitve pri algoritmih NakljDod, MinGlGor in MinGlDol.
3. Organizacija stroja
Končno bomo predstavili še računalniško arhitekturo, ki učinkovito podpira podatkovno vodeno računanje, oplemeniteno s sinhronizacijskimi mehanizmi, kot so bili vpeljani v prejšnjem poglavju. Takšna arhitektura v popolnosti izkorišča rezultate časovne optimizacije asinhronega procesiranja.
3.1 Funkcionalni opis
Že uvodoma smo opozorili na problem kopičenja podatkovnih paketov v vrsti pred procesno enoto, ki je posledica omejenega števila procesorjev v procesni enoti. Nakazali smo tudi eno od možnih rešitev, ki temelji na pravilnem vstopanju paketov v vrsto oz. izstopanju paketov iz nje. Na osnovi vpeljanih sinhronizacijskih mehanizmov je to rešitev možno uresničiti z vzporedno računalniško arhitekturo, kot bo opisana v nadaljevanju; poimenovali jo bomo sinkronizirana podatkovno pretokovna arhitektura (SPPA) [7, 16]. SPPA sodi v družino hibridnih arhitektur. Ses-
V ta namem smo uporabili računalnik IBM PC in razvili ustrezna programska orodja.
tavlja jo množica enakih podatkovno pretokovnih procesorjev (PPP) ter nadzorno-povezovalna enota (NPE), ki so krožno povezani, kot kaže slika 14. Vhodno/izhodna komunikacija z gostiteljskim računalnikom poteka preko NPE.
HOST
vhodni paketi
NPE
izhodni paketi
PPPI		PPPJ		pppp
			• • •	
				
Slika 14: SPPA.
Preden se lotimo podrobnejšega opisa enot, na kratko opišimo potek reševanja danega problema na SPPA. Reševanje si lahko predstavljamo kot zaporedje treh faz: prevajanje programa ter optimizacija GPP, nalaganje SGPP v SPPA in izvrševanje v SPPA.
Prevajanje ter optimizacija. Naj bo dan nek
poljuben algoritem, zapisan v kakem od visokih podatkovno pretokovnih jezikov. Z ustreznim prevajalnikom se algoritem prevede v strojni kod, tj. GPP. Prevajanje poteka na gostiteljskem računalniku. V naslednjem koraku GPP optimiziramo, tj. konstruiramo p- ali T-optimalnò sprožitveno funkcijo (pOptSinh in TOptSinh) ter z uporabo algoritmov MinGlGor oz. MinGlDol določimo procesorske indekse tt. Ti indeksi so pomemebni za samo nalaganje GPP v SPPA. Poleg tega pa so ob koncu optimizacije znane še vse globalne povezave ter trenutki sprožitve vseh tistih točk {vhodne ločene točke), v katere vstopajo globalne povezave. Ti podatki imajo pomembno vlogo pri izvrševanju GPP v SPPA.
Nalaganje. Kot bomo videli v nadaljevanju, ima vsak PPP svoj grafni pomnilnik, v katerem hrani podatke o delu GPP. V fazi nalaganja se vsaka točka v iz GPP naloži v PPP z indeksom i, če je ■jv(v) — i. Y PPP s tem indeksom se implicitno vpišejo tudi vse povezave, katerih začetna in končna točka sta dodeljeni procesorju z indeksom i, kot narekuje logična zgradba grafnega pomnilnika. V NPE pa se shranijo globalne povezave ter trenutki
sprožitve vseh vhodnih ločenih točk. Pri nalaganju sodelujeta gostiteljski računalnik ter NPE.
Izvrševanje. Po fazi nalaganja vsak PPP hrani ustrezen podgraf od GPP. Vse točke v PPP, ki za svojo izvršitev potrebujejo vsaj en podatkovni paket iz drugega podgrafa, se imenujejo vhodne ločene točke. Podobno pa so izhodne ločene točke vse tiste točke podgrafa, ki vsaj en svoj rezultat posredujejo v drug podgraf. Vse ostale točke v podgrafu imenujemo notranje točke. Izmenjava podatkov med notranjimi točkami poteka asinhrono, zato je podgraf čisti graf pretoka podatkov brez vnaprej določenih trenutkov sprožitve. Tudi izhodna ločena točka posreduje svoj rezultat takoj, ko se le ta izračuna.
Izmenjava podatkovnih paketov med PPP poteka posredno preko NPE. Vsaka izhodna ločena točka torej pošlje svoj paket v NPE. Ta enota prebere iz seznama globalnih povezav, kateri vhodni ločeni točki je paket namenjen. Poleg tega pa iz seznama sprožitvenih trenutkov ugotovi, kdaj mora ta paket poslati ustreznemu PPP. Vidimo, da NPE deluje popolnoma sinhrono na osnovi globalne ure.
3.2 Nadzorno-povezovalna enota
NPE opravlja naslednje funkcije: skrbi za vhodno/izhodno komunikacijo z gostiteljskim računalnikom, omogoča nalaganje delov GPP v ustrezne PPP in skrbi za posredovanje paketov med ločenimi točkami. Logično si NPE predstavljamo kot tabelo
Globahia povezava	Procesorski indeks	Podatkovno polje	Trenutek sprožitve
			
. u 1—► v		P	
			
kjer je u i—v globalna povezava iz točke u v v, 7r{v) indeks PPP, v katerem je vhodna ločena točka v, p podatkovno polje, ki ga točka u pošilja točki v, ter s{v) trenutek sprožitve točke v. Podatkovno polje p je par p = {d, a), kjer je d vrednost, a pa določa, kateri od argumentov točke v bo sprejel vrednost d.
Tabela se pred začetkom izvrševanja uredi po naraščajočih vrednostih ^(u), ki so bile določene
V	fazi optimizacije. Delovanje NPE opišimo na primeru. Naj bo A i—> B globalna povezava. Točka A naj bo dodeljena procesorju i, točka B pa procesorju j. Točka B se mora sprožiti v trenutku t.
V	nekem trenutku r < t točka A pošlje podatkovno polje p v izhodnem paketu oblike
NPE
A
B
P
v NPE. Ta na osnovi globalne povezave A
B
poišče v tabeli vrstico s to globalno povezavo ter v podatkovno polje vpiše vrednost p. S tem je sprejem izhodnega paketa končan.
Sočasno globalna ura enote NPE šteje čas t. Ko postane r = i, NPE tvori vhodni paket oblike
B
in
ga pošlje verigi PPP, kjer ga jr-ti PPP sprejme.
3,3 Podatkovno pretokovni procesor
Podatkovno pretokovni procesor omogoča hranjenje in izvajanje podgrafov GPP ter hkrati učinkovito komuniciranje s svojo okolico. Arhitektura je zasnovana tako, da je uporabljen sinhro-nizacijski mehanizem, ki temelji na shranjevanju paketov. Procesor sestavljajo vhodno-izhodni krmilnik, grafni pomnilnik, enota za ažuriranje in dostavo, čakalna vrsta, procesna enota ter izhodna vrsta (slika 15).
Slika 15: Zgradba PPP.
Vhodno-izhodni krmilnik skrbi za komunicajo med PPP in okolico. Vhodni podatkovni paketi, ki vstopajo v krmilnik, imajo obliko
7r(v)
P
kjer je v točka, ki (v procesorju z indeksom 7r(-y)) čaka na podatkovno polje p = {d, a). Iz indeksa ir(v) krmilnik ugotovi, če je prispeli paket namenjen njemu. Če ni, ga vhodno-izhodni krmilnik nespremenjenega v istem ciklu posreduje naslednjemu PPP. Procesorje tako za tuje pakete transparenten. Če pa se ■k(v) ujema z indeksom danega procesorja, se paket sprejme. V tem primeru enota za ažuriranje in dostavo iz paketa izloči indeks t'{v), preostanek
I
d
pa pošlje grafnemu pomnilniku.
Grafni pomnilnik hrani opise točk in povezav podgrafa GPP. Opis točke v se nahaja v tabeli
Točka	Op	St.	Operandi			Točke čakajoče na rezultat		
								
v	op	C			dm	<"1 ./l ."1		«"n./n.an
								
kjer je op operacija, ki jo mora točka v izvršiti nad operandi di,d2, • • ■ ,dm ter rezultat poslati točkam wi,w2,..., Wn\ rezultat mora biti shranjen v točko Wi kot argument z zaporedno številko a,. Zastavica fi zavzame vrednost i ali G glede na to, ali je točka to, v istem (lokana točka, / = L) ali drugem PPP (globalna točka, / = G). Števec c manjkajočih vhodnih operandov se ob nalaganju postavi na vrednost m.
Enota za ažuriranje in dostavo vpiše vrednost d paketa v grafni pomnilnik v vrstico z oznako točke v na mesto operanda da ter hkrati zmanjša števec C za eno. Takoj po vpisu enota za ažuriranje in dostavo preveri, če je vrednost števca c enaka nič. Če je temu tako, posreduje paket oblike
op
dx
v čakalno vrsto, kjer se paketi kopičijo in čakajo na sprostitev procesne enote. Sočasno pa na osnovi v-te vrstice grafnega pomnilnika tvori v izhodni vrsti naslednjo tabelo
Povezava	Zastavica	Rezultat	St. argumenta
			
v . u/-|	u		
v • Wj	h		a.
			
v --- u^n	Ir.		"n
			
Ko procesna enota izračuna rezultat r op[di,..., dm), tvori paket
in ga pošlje izhodni vrsti. Ta vpiše vrednost f v polja za rezultat vseh vrstic, ki ta rezultat pričakujejo.
Enota za ažuriranje in dostavo na osnovi zastavice fi tvori lokalni paket, če je /,- = L oz. izhodni paket, če je fi = G. Lokalni paket ima obliko
Wi I r
a;
izhodni paket pa obliko
NPE
v I—> Wi 1 d
kjer je d = (r,ai).
Vrednost r lokalnega paketa se preko enote za ažuriranje in dostavo vpiše v grafni pomnilnik v vrstico z oznako na mesto operanda da,. Izhodni paket pa se preko vhodno-izhodnega kr. milnika posreduje NPE.
3.4 Izvedba
Zadnji korak do končne izvedbe SPPA predstavlja razvoj strojne opreme NPE in PPP.
V začetni fazi je moč NPE relativno preprosto emulirati s kakim od obstoječih mikroračunalnikov; končni cilj pa je izvedba NPE v obliki VLSI čipa.
Tudi PPP je smiselno zasnovati kot VLSI vezje, vendar pa že danes obstajajo na tržišču procesorji, ki bi v prvi fazi zadovoljivo opravljali funkcijo PPP. Najbliže temu je podatkovno vodeni mikroprocesor yiPD7281 [17, 18]. Primeren kandidat, ki bi v prvi fazi prevzel funkcijo PPP, je transputer (npr. T9000) [19].
Za konec omenimo še možnost, da bi PPP nadomestili tudi s podatkovno vodenim procesorskim poljem. Še posebej so zanimiva heksag-onalna procesorska polja, ki so trenutno še predmet raziskav [20]. Zgradbo procesorskega polja
prikazuje slika 16. Podatkovno vodene celice (procesorji) so organizirane v vrstice. Med vsakim parom vrstic je speljano komunikacijsko vodilo, ki omogoča vhodno/izhodno komunikacijo z NPE ter porazdelitev delov GPP med celice. Vsaka celica je točkovno povezana s šestimi sosednjimi celicami. Slika 16a prikazuje povezanost celice O s sosedami 1, 2, 3, 4, 5 in 6. Iz tehnoloških razlogov je število celic v polju omejeno (trenutno do nekaj 100 [20]). Zato moramo v splošnem GPP porazdeliti po več poljih. Na primer, slika 16b prikazuje rezultat nalaganja tistega dela GPP za FFT, ki je ga je algoritem MinGlDol priredil procesorju P2.
4. Zaključek
Povrnimo se ponovno na nalogo, ki smo si jo zastavili. Predpostavimo, da je na voljo podatkovno pretokovni računalnik s potencialno neskončnim številom procesorjev ter izberimo poljuben graf pretoka podatkov. Denimo, da je za najhitrejšo asinhrono izvršitev izbranega grafa potrebnih vsaj m procesorjev. Tedaj označimo s T^ najkrajši čas, v katerem se ta graf izvrši na m procesorjih. Na računalniku z n < m procesorjev pa bi se v splošnem isti graf asinhrono izvršil v času Tn ^ Tm + ATn, kjer Ar„ > 0. Za nalogo si zadajmo minimizirati podaljšek izvrševanja AT„, tj. časovno optimizirati asihrono procesiranje pri n danih procesorjih.
Časovno optimizacija asinhronega procesiranja se rešuje bodisi dinamično, tj. med izvrševanjem grafa pretoka podatkov, ali pa statično, tj. med prevajanjem programa v graf. Dinamično dodeljevanje je obremenjeno z "overheadom" ter zaradi lokalne optimizacije redko vodi v globalno (časovno in/ali prostorsko) optimalno izvrševanje grafa pretoka podatkov. Zato je smiselno čim večji del optimizacije prenesti v fazo prevajanja. K razrešitvi opisanega problema smo pristopili po izvirni poti. Rešitev, ki jo predlagamo, temelji na uvedbi nekaterih mehanizmov sinhronizacije v asinhrono procesiranje.
Graf pretoka podatkov s predhodno analizo opremimo z dodatno informacijo, ki bo koristila pri vlaganju grafa v računalnik ter med njegovim izvrševanjem. Postopek, imenovan statično dodeljevanje, poteka v dveh korakih:
Sinhronizacija: Naj bo V množica točk danega grafa pretoka podatkov ter označimo s t{v) čas
				L (	)	(	t )	1		
										
			Comuni	.kac	jsb	D V(	dilc	)		>
										
		f	J	< -o (	) ( )	( ) (	) G)	-O z	1	
			C	o		(	) (			
										
<		Komuni		kacijsko vodik				)		
(a)			
o 0— o G o o	—° o rt^ o	o o o E 0	o o o D o o o
Kon Lunikac
jsko VC
dilo
o
o o
9
-M-
ò
J O
Q	O
O	6
O W O O o
o
o v o-
o o
Komunikacijsko vodilo
(b)
Slika 16: Heksagonalno procesorsko polje.
izvrševanja točke v £ V. Vsaki točki v € V hevristično priredimo trenutek njene sprožitve «(v) tako, da minimiziramo ATn, kjer je n < m. K hevrističnim metodam se zatečemo zaradi NP-polnosti opisanega problema. Graf, katerega točke so opremljene s trenutki sprožitve, imenujemo sinhronizirani graf pretoka podatkov. Sinhro-nizirani graf je torej oplemeniten graf, v katerem je znano, kdaj oziroma v kakšnem vrstnem redu se morajo točkam pridruženi ukazi pričeti izvrševati, da se bo celoten graf izvršil na n < rn procesorjih v najkrajšem času.
Dodeljevanje: Vsaki v £ V priredimo indeks 1 < ''^i'") < n, ki pove, kateremu od n procesorjev se bo točka dodelila. Torej razbijemo
V	v n particij Vi,V2,...V„, kjer je V,- množica točk, ki se bodo izvrševale na i-tem procesorju. Točki imenujemo ločeni, če sta dodeljeni različnima procesorjema. Povezavo med ločenima točkama imenujemo globalna povezava. Množico V je v splošnem moč razbiti na več načinov, seveda pa se omejimo le na konstrukcijo dopustnih particij, ki omogočajo izvršitev grafa v skladu z določenimi trenutki sprožitve s(u). Med dopustnimi partici-jami iščemo optimalno, tj. takšno, pri kateri bo najmanj globalnih povezav. Tako bo zagotovljena tudi najmanjša medprocesorska komunikacija. Rezultat dodeljevanja je, da imamo za vsako v £
V	določen indeks 7r(v) ter "označene" globalne povezave.
Sinkronizirani graf pretoka podatkov dobimo s pomočjo hevrističnih algoritmov pOptSinh in TOptSiah, za konstrukcijo optimalnih sprožitvenih funkcij. Po pesimistični oceni vračata predlagana algoritma optimalno rešitev v 80% primerov.
V algoritmu pOptSinh je uporabljena izvirna ocena za spodnjo mejo potrebnih procesorjev, ki temelji na razširjeni kritični vzporednosti grafa. Ta ocena je po svoji natančnosti v povprečju le za 6.52% slabša od optimalne Fernandez-Bussellove ocene, hkrati pa je njeno določanje za red velikosti hitrejše.
Za dodeljevanje predlagamo algoritma MinGlDol in MinGlGor, ki temeljita na optimizaciji medpro-cesorskih komunikacij. V primerjavi z znanimi razvrščevalnimi algoritmi dobimo s predlaganima algoritmoma boljše rezultate, kar potrjujejo analizirani primeri algoritmov za izračun hitre Fourier-jeve transformacije, dinamične analize scene in LU razcepa matrike.
Končno je predlagana tudi organizacija računalnika, ki podpira asinhrono procesiranje z elementi sinhronizacije. Nakazane so možnosti realizacije z VLSI podatkovno pretokovnimi mikroprocesorji in podatkovno pretokovnimi polji.
Zahvala
Raziskavo je finančno podprlo Ministerstvo za znanost in tehnologijo Republike Slovenije po pogodbi C2-0521-106-92. Za strokovno pomoč pri nastanku pričujočega dela gre zahvala mag. Borutu Robiču, sodelavcu Laboratorija za računalniške arhitekture IJS.
Literatura
[1]	E. B. Fernandez and B. BusselL Bounds on the Number of Processors and Time for Multiprocessor Optimal Schedules. IEEE Trans. Computers, C-22(8):745-751, August 1973.
[2]	Y. E. Chen and D. L. Epley. Bounds on Memory Requirements of Multiprocessing Systems. In Proc. 6th Annu. AUerion Conf. Circut and Syst. Theory, pages 523-531, 1968.
[3]	R. McNaughton. Scheduling with Deadlines and Loss Functions. Management Sci., 6, October 1959.
[4]	T. C. Hu. Parallel Sequencing and Assembly Line Problems. Oper. Res., 9(6):841-848, November 1961.
[5]	C. V. Ramamoorthy, K. M. Chandy, and M. J. Gonzalez. Optimal Schedulling Strategies in a Multiprocessor System. IEEE Trans. Computers, C-21(2):137-146, February 1972.
[6]	J. Šile, B. Robič, and L. M. Patnaik. Performance Evaluation of an Extended Static Dataflow Architecture. Computers and Artificial Intelligence, 9(l):43-60, 1990.
[7]	J. Šile and B. Robič. Synchronous Dataflow-Based Architecture. Microprocessing and Microprogramming, 27(l-5);315-322, August 1989.
[8]	J. Šile and B. Robič. Program Graph Partitioning for Macro-Dataflow. In Proc. ISSM Int'l Workshop on Parallel Computing, pages 327-330, September 1991.
[9]	J. Šile. Časovna optimizacija., asihronega procesiranja z uvedbo nekaterih mehanizmov sinhronizacije. Doktorska disertacija, Fakulteta za elektrotehniko in računalništvo, Ljubljana, junij 1992.
[10]	E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, 1976.
[11]	K. Mehlhorn. Graph Algorithms and NP-Completeness. Springer-Verlag, 1984.
[12]	E. G. Coffman et al. . Computer and Job-Shop Scheduling Theory. Wiley-Interscience, 1976.
[13]	B. Shirazi, M. Wang, and G. Pathak. Analysis and Evaluation of Heuristic Method for Static Task Schedulling. Journal of Parallel and Distributed Computing, 10(3):222-232, November 1990.
[14]	G. Pathak and D. P. Agrawal. Task Division and Multicomputer System. In Proc. 5th Int'l Conf. on Distributed Computing System, page 273, May
1985.
[15]	G. H. Golub and C. F. Van Loan. Matrix Computations. The Johns Hopkins University Press, 1989.
[16]	J. Šile and B. Robič. MADAME - Macro-Dataflow Machine. In Proc. Mediterranean Electrotechnical Conference - MELECON'91, pages 985-988, May 1991.
[17]	T. Jeffery. The //PD7281 Processor. Byte, pages 237-246, November 1985.
[18]	J. Šile in B. Robič. Procesor s podatkovno pre-tokovno arhitekturo. Informatica, 10(4):74-80,
1986.
[19]	D. Fountain. The Transputer Strikes Back. Byte, 16:265-275, August 1991.
[20]	S. Weiss, I. Spillinger, and G. M. Silberman. Architectural Improvements for Data-Driven VLSI Processing Arrays. In Proc. Functional Programming Languages and Computer Architecture, pages 243259, September 1989.
AN INFORMATIONAL APPROACH OF BEING-THERE AS UNDERSTANDING III
Keywords: dictionary, Heideggerian Being-there, information, informational formulas, philosophy, text formalization, understanding
Anton R Železnikar Volaričeva ulica 8, 61111 Ljubljana
This part of the essay includes the remaining dictionary of Fraktur operands and informational operators pertaining to the Heideggerian Being-there as understanding. These dictionaries complete the discussion concerning understanding as informational phenomenality in terms of informational formulas in which operands communicate among themselves in a dynamic, that is processing and operational way. This informational model of understanding approaches the concept of treating texts informationally in the most imaginable entirety. At the end a short comment is added.
Informacijski pristop k biti-tu kot razumevanju ni
V tem delu spisa imamo še preostali del slovaija fraktumih operandov in slovar informacijskih operatorjev, ki se tičejo Heideggrove tu-biti kot razumevanja. S tema slovarjema se končuje razprava o razumevanju kot informacijski pojavnosti v terminih informacijskih formul, v katerih operandi medseboj dinamično komunicirajo v procesni in operacijski obliki. Ta informacijski model razumevanja se približuje konceptu informacijskega obravnavanja besedil v kar najbolj domiselni celosti. Na koncu je dodana še kratka opomba.
Fraktur Operands (A Continuation)
«in	Being-in | In-Sein, das | v-bit | (2.2),
(2.3), (2.4), (7.2), (10.11) □ 58m(U(2Bworld))
Being-in of understanding of the world 1 In-sein des Verstehens der
Welt, das | v-bit razumevanja sveta I (10.11) □
®in-the-world
%
'one's-Self
possible
Being-in-the-world | In-der-Welt-sein, das ) bit-v-svem (2.4), (2.6), (2.8), (7.1), (7.2), (8.4), (10.1), (10.6), (10.10), (12.4), (16.5), (17.1), (17.7) □ Being-one's-Self | Selbstsein, das | bit-pri-sebi; samobit | (10.6) □ Being-possible | Sein-konnen, das | moči-bit I (3.4), (3.6), (3.7), (4.4), (4.6) □
«possibIe(S))
Being-possible of Dasein | Möglichsein des Daseins, das moči-bit tubiti | (4.6) □ ®there Being-there | Sein des "Da", das | tu-bit 1(1.1), (1.2), (1.6), (2.2), (2.4) □
®there(®world)
Being- there of the world | Da-sein
der Welt, das | biti-tu sveta |
(2.2), (2.4) □
®with Being-with | Sein bei, das ] pri-bit;
bit pri I (12.5) □
^withC^^) Being-with Others | Mitsein mit
Anderen, das | bit pri drugih |
(12.5)0
*^comport comporting | Verhalten, das | vedénje | (8.6) □
^comport(^oneself)
comporting oneself | S ich verbal ten,
S,
const
Sconst(®)
S)
das I Se-vedénje | (8.6) □ constitution | Konstitution, die konstitucija | (16.6) □ Constitution of the Being | Konstitution des Seins, die | konstitucija biti | (16.6) □
Dasein
tubit I (1.5),
®discl S)fact

exist
®exist(«)

'expl
®general
Dasein, das (1.5), (2.2), (2.3), (2.4), (2.8), (3.3), (3.4), (3.5), (3.6), (3.7), (3.1 D,-(4.2), (4.3), (4.4), (4.5), (4.6), (5.1), (5.2), (5.3), (5.4), (5.5), (5.6), (5.7), (6.1), (7.9), (8.3), (8.5), (8.6), (8.7), (8.8),(8.11),(9.1), (9.2), (9.3), (10.2),(10.3), (10.5), (11.1), (12.1),
(12.2),	(12.3), (13.1), (16.1), (17.2),
(17.3),	(17.4), (17.5), (17.6), (17.7) □
disclosure | Erschließen, das | razprtje | (7.1)0 factical Dasein | faktische Dasein, das I faktična tubit | (11.1) □ existing; existentiality | Existieren, das; Existenzialität, die | eksistiranje; eksistencialnostj (3.12), (12.5) □
existence of entities | existierende Seiende, das | eksistirajoče bivajočega | (12.5) □ explaining | Erklären, das | pojasnjevanje | (1.6) □

grasp
in general | überhaupt | nasploh | (14.7) □
©grant granting | Vorwegnehmen, das | vnaprej danost | (16.3) □ grasping | Erfassen, das | zapopadanje | (8.10)D ®grasp(U) grasping of understanding | Erfassen von Verstehen, das | zapopadanje razumevanja | (8.10) □ ®known that_which_we_have_such_ _compentence_over; known | Gekonnte, das | znano | (3.2'), (3.2"), (3.2^) □ :^inter interpretation | Interpretation, die interpretacija | (16.7) □
Sinter(^temporal(®))
temporal interpretation of Being | temporale Seinsinterpretation, die | časovna interpretacija biti | (16.7) □ R	kind I Art, die | način | (3.3), (8.5),
m)
mm
(8.11), (9.1), (15.4), (16.5), (18.1) □
kind of Being | Seinsart, die ] način biti | (3.3), (8.5), (9.1), (18.1) □
kind of Being of entity | Seinsart des
Seienden, die bivajočega
način biti
(16.5) □
ß(93(S))) kind of Being of Dasein, the | Seinsart des Daseins, die | način biti mbiti | (8.11) □ ^(Ssee(®)) kind of seeing of Being | Art des

cogn

lOW
Sehens von Sein, die | način videnja biti | (15.4) □ kind of cognition | mögliche Erkennmisart, die spoznavni način | (1.6) □ knowing; knowledge | Wissen, das znanje | (5.4), (12.4) □
knowledge of the Self »Selbsterkenntnis«, die samospoznanje | (12.4) □ ^know(^) knowing of Dasein | Wissen des Daseins, das | védenje tubiti | (5.4) □
[Di
3JÌ(ll)
SR
D,
'opaque
mood I gestimmtes | razpoloženo (1.4), (17.2), (17.3) □ mood of understanding | gestimmtes des Verstehens | razpoloženo razumevanja | (1.4) □ nature | Natur, die | narava | (7.6), (7.7) □ opaqueness | Undurchsichtigkeit, (13.1) □
die I neprozomost sDopaque(®) Dasein's opaqueness |
Undurchsichtigkeit des Daseins, die

imm
^imm(S))
^perceive ^percept
neprozomost tubiti | (13.1) □ self-perception, immanent | immanente Selbstwahmehmung, die | imanentno samozaznavanje | (5.4) □ immanent self-perception of Dasein | immanente Selbstwahmehmung des Daseins, die | imanentno samozaznavanje mbiti | (5.4) □ perceiving | Wahmehmen, das | zaznavanje | (14.3) □ perceptually tracking down and inspecting j wahmehmende Aufspüren und Beschauen, das |
66
zaznavno zasledovanje in ogledovanje | (12.4) □
^ercept(cfself)
perceptually tracking down and inspecting a point called the "Self" | das wahrnehmende Aufspüren und Beschauen eines Selbstpunktes zaznavno zasledovanje in ogledovanje nekega Se | (12.4) □ project projecting | Entwerfen, das |
snovanje; projektiranje | (8.5), (8.6), (8.7), (8.10), (8.11), (16.3) □ ^project(<^) what is projected | Entworfene, das |

uestion
zasnovano (8.10) □ or D,
'quest
question | Frage, die | vprašanje (7.7), (17.5), (17.6), (17.7) □
Öquest(®(®))
^to-hand
question about the Being of Dasein Frage nach dem Sein des Daseins, die I vprašanje po biti tubiti | (17.5), a7.6)n ready-to-hand | Zuhandene, das | priročno
(7.4), (7.5) □ ®mind state-of-mind | Befindlichkeit, die | počutnost (počutje, nahajalnost) | (1.1), (1.2), (1.3), (4.2), (5.6), (17.1), (18.1) □ ®of-Bemg state-of-Being | In-der-Welt-sein, das I stanj e-biti; svetovno-biti | (8.4) □
®of-Beiiig(TcharOi))
State-of-Being of the character of
understanding | In-der-Welt-sein des
Charakters von Verstehen, das
stanje-biti karakterja razumevanja |
(8.4) □
6,
see
seemg
»Sehen«, das | »videnje«
(14.3),	(14.4), (14.6), (14.7),
(15.4)	□
6see(®) seeing of Being | Sehen von Sein,
das I videnje biti | (15.4) □ ®seize seizing | verstehende Ergreifen, das razumevno prijetje | (12.4) □
®seize(<Pfull(^disclose(®in-the-world)))
seizing upon the full disclosedness of Being-in-the-world | verstehendes Ergreifen der vollen Erschlossenheit des In-der-Welt-seins | razumevno prijetje polnega razprtja
biti-v-svetu I (12.4) □ ^temporal temporal | temporal | časoven ( (16.7) □
^temporale®)
temporal of Being, the | Temporale
des Seins, das | časovno biti |
(16.7) □
thinking | Denken, das | mišljenje (15.2) □
throwing | Werfen, das | metanje (8.10) □
understanding | Verstehen, das |
^think ^throw
U
razumevanje
m)
U(Sex)
(1.2), (1.3), (1.4), (1.5), (1.6),(2.4), (2.5), (2.6), (3.1), (3.2), (3.3), (3.13), (5.1), (5.3), (5.4), (5.5), (5.6), (6.1), (7.1), (8.1), (8.2),(8.3), (8.4), (8.5), (8.9), (8.10), (8.11),(9.4), (10.1), (10.2), (10.3), (10.4), (10.8), (10.9), (10.10), (10.11), (11.1),(12.1), (12.4), (15.1), (15.2), (16.1),(16.3), (16.5), (16.6), (16.7), (17.1), (18.1) □ understanding something | etwas verstehen j nekaj razumeti | (3.1), (8.9) □
understanding of existence | Verstehen der Existenz, das | razumevanje eksistence | (10.11) □ ^(<Psake) understanding of the »for-the-sake-of-which« j Verstehen des Worumwillen, das | razumevanje zaradi-česa | (2.5) □ understanding of Being | Seins Verständnis, das | razumevanje biti I (16.3), (16.5), (16.7) □ U(95(Tthere))
understanding of the Being of the "there" | Verstehendes Seins des Da, das | razumevanje biti Tuja (9.4) □
ll(®worid) understanding the world | Verstehen von Welt, das | razumevanje sveta | (10.11) □
authentic understanding | eigentliche Verstehen, das | pravo razumevanje | (10.4), (10.7) □
existential understanding | existenziale Verstehen, das | eksistencialno razumevanje | (15.3) □ inauthentic understanding |
um
^auth
^exist
^inauth
U
pnm
uneigentliche Verstehen, das | nepravo razumevanje | (10.4), (10.7) □
U^s misunderstanding | Mißverständnis, das I nesporazum; nerazumevnost | (14.1) □
^niis(^express(^sight))
misunderstanding of the expression 'sight' I Mißverständnis des Ausdrucks »Sicht«, das | nerazumevnost izraza »vid« |
(14.1)	□
understanding, primary primäre Verstehen, das | primamo razumevanje | (1.6) □ ^well well-understanding; well understood, the I wohlverstanden | dobro razumljen | (12.4) □ ®basic_state whole basic state |
ganze Grand Verfassung, die celotno osnovno stanje | (7.1) □
®basic_state(®m-the- world)
whole basic state of Being-in-the-. world, the | ganze Grand Verfassung des Ih-der-Welt-seins, die | celotno osnovno stanje biti-v-svetu | (7.1) □ ^categoria! whole, categorial |
kategoriale Ganze, das | kategorialna celost | (7.5) □ ®cur_world current world, the | jeweilige Welt, die I vsakokratni svet (8.3) □
'cur_world(^)
current world of understanding, the | jeweilige Welt des Verstehens, die | vsakokratni svet razumevanja | (8.3) □ way I Art, die | način | (14.6), (16.1),
(16.2),	(17.2), (18.1) □
®5way(^for-Being(®))
way of Dasein's potentiality-for-Being |
Seinkönnen des Daseins, das |
potencialnost biti tubiti | (16.1) □
® way (^access)
way of access | Zugangsart, die |

10
way
način dostopa | (14.6) □ ®way(3^) way of having a mood, the | in der Weise der Gestimmtheit | na način (17.2) □
Was, das I Kaj | (3.2),
razpoloženosti ®what "what"; what
(5.3'), (6.1), (7.8), (10.1), (16.6) □
®what(®exist)
"what" of the existential Being, the Was des existenzialen Seins, das Kaj eksistencialne biti | (6.1), (7.8) □ ®whole whole, the | ganz; Ganze, das | cel;
celota I (10.10) □ ©why why; the "Why" | warum; das
"Waram" | zakaj; Zakaj | (8.1) □ ®world worid I Welt, die | svet | (2.2),
(2.4), (3.6), (7.3), (10.2), (10.5), (10.6), (10.11), (12.5), (13.1), (16.2) □
®world(^sign)
world on the basis of significance,
the I Bedeutsamkeit ist das,
woraufhin Welt... , die | svet na
temelju pomembnosti | (2.7) □
®world(®) Dasein's worid Welt des Daseins,
®worldhood
die I svet tubiti | (10.2) □
worldhood | Weltlichkeit, die | svetnost | (8.3) □
®worldhood(®cur_world(^))
worldhood of understanding's current
world, the | Weltlichkeit der
jeweiligen Welt des Verstehens, die |
svetnost trenutnega sveta
razumevanja | (8.3) □
A DICTIONARY OF INFORMATIONAL OPERATORS
(Operator symbols with English, German, and Slovene explanation)
1=	inform(s); impact(s); make(s);
am/are/is; maintain(s); etc. | informiert; beeinflußt/beeinflussen; bin/bist/ist/sind/seid; usw. | informira(m/aš/mo/te/jo) ; vpliva(m/aš/mo/te/jo); sem/si/je/smo/ste/so; itd. | (1.1),
(1.5),	(1.6), (2.2), (2.3), (2.4), (2.8), (3.1), (3.2), (3.5), (3.7), (3.12), (3.13), (4.1), (4.3), (4.4), (4.5),
(4.6),	(5.1), (5.2), (5.5), (6.1), (7.4), (8.2), (8.5), (8.7), (8.8), . (8.9), (8.10), (9.4), (12.2), (12.3), (12.4), (12.5),-(14.3), (15.1), (16.1), (16.6), (16.7), (17.2), (17.5), (17.6),
Nable
Nable_nian
Nabout Naccess
Naccid
(18.1) □
is/are_able | will_und_kaiin_ sein je/sojahko | (9.1) □
to_be_able_to_manage | vorstehen_köiinen | biti_sposoben | (3.1) □ is_about I ist_nach je_po/o I (7.7), (17.7) □
is/are_acćessible | ist/sind_
zugänglich I je/so_dostopen/ dostopni I (14.4) □ is_accidental | ist_zufällig | je_slučajno | (7.7) □
Naccomp_by
is_accompained_by | ist_befmdlich(es) | je_spoznano(_za) | (5.6) □ =aim_at aim(s)_at | ziehlt_auf
se_usmeija_na | (7.7) □
—alLpress_for
always_press(es)_forward | dringt_ _immer_in | napreduje_vselej_v (8.1) □
inform(s)_all | informier-t/-en_ _wesenhaft | informira(jo)_bistveno (12.4) □
Nall
^already
je_že
is_already | istJe_schon (4.2), (15.1), (16.3) □
Nalready ° Nbeen
has/have_already_been | ist/sind_
schon I je/so_že | (16.3) □
(Nalready ° Nbeen) o Ntake
has/have_already_been_taken | ist/sind_schon_vorweggenommen | je/so_že_vnaprejvzet(i) | (16.3) □
—aLunderst
always has understood and always will understand | versteht sich immer schon und immer noch | je vselej že in še razumljeno | (8.8) □
^always infor(s)_always | informier-t/-en_
_immer | informira(jo)_vselej | (10.1), (10.10), (10.11), (12.2), (17.3) □
Nalway s ° Npertain
always_pertain(s)_to | betrifft/ betreffenjmmer | se_tiče(jo)_vselej | (10.1), (10.10) □
l=always°Nu
understand(s)_always | versteht/
N
arr
ist/sind_solange
-astray
verstehenjeweils | razume(jo)_ _vselej 1 (10.11) □ arrange(s) | einrichtet (einrichten) uravnava(jo) | (8.6) □
Narise_out arise(s)_out I entspringt_aus | izvira(jo)_iz | (10.4) □ as; is_as | als; ist_als | kot; je_kot (2.6), (2.8), (3.2), (3.3), (3.11), (3.12), (3.13), (4.1), (4.3), (5.1), (5.3), (7.1), (7.2), (7.3), (7.4), (8.3), (8.4), (8.5), (8.7), (8.8), (8.10), (8.11), (9.1), (9.3), (9.4),
(10.1),	(10.4), (10.6), (10.8), (10.10), (10.11), (11.1), (12.2), (14.6), (14.7), (15.1), (15.4), (16.6), (17.1) □
Nas_long_as
is/are_as_long_as doklerJe/so | (8.7), (8.8) □
Nas_not_yet
is/are_as_not_yet | ist/sind_sondem_als_nie toda_ni/niso_nikoli | (5.1) □ inform(s)_astray | informiert_verlaufend informira(jo)_blodno | (5.5), (5.6) □ has/have_been | ist/sind(_gewesen) | je/so_bil(i) (16.3) □ bring(s) I bring-t/en (18.1)0
but_there_is; but | sondern | temveč | (3.2'), (3.2"), (7.3), (12.4), (18.1) □
hbut°(Nfirst° Neven)
but_is/are_in_the_first_instance_ _even | ist/sind_zunächst_nur_(um) | je/so_najprej_le | (18.1) □ inform(s)_by | ist_hinsichlich ] informira(jo)_glede_na | (8.4) □ is/are_capable | 'woran(_es)_ist/sind' ] je_sposobno | (5.3), (6.1) □ characterize(s) | charakterisier-t/-en | karakterizira(jo) | (3.9), (3.11),
(14.2),	(14.7), (17.1) □ clarifies/clarify | aufklär-t/en | pojasnjujejo) | (16.7) □ come(s) I kommt/kommen_zu | prideòo)_do/k/h | (17.7) □
Nbeen
Nb, Nb
ring
prinese(jo)
ut
Nbv
N
cap
—char
Nclarify
-come
-comp
to_be_compentent_to_do | können
N N
conceive
concern
—confront
N
connect
-const
znati (3.1) □ conceive(s) | begreif-t/en | doume(jo) | (16.4) □ concern(s) | betrifft/betreffen zadeva(jo) | (3.6) □ confront(s) | ist_gegenüber | je_nasproti | (7.9) □ keep(s)_connection_with | wahrt/wahren_den_Zusammenhang_ _mit I ohranja(jo)_povezanost_s/z (14.7) □
constitute(s) | konstituier-e/st/t/en; konstituira-in/š/mo/te/jo | (1.2), (8.4), (9.1) □
Nconstantly
is/are_constantly | ist/sind_ständig.| je/so_trajno I (9.1) □ inform(s)_on_the contrary sondem_hat/inforniiert | temveč_ima/je/informira | (8.7) □ correspond(s) | entspricht/entsprechen I odgovaqaöo) I (14.2), (15.1)0
-corresp'^Nnoe
correspond(s)_noetically | entspricht/entsprechen_noetisch | odgovaija(jo)_noetično | (15.1) □ cut(s)_off I abschnürt/abschnüren | odvežeOo) | (10.5) □ is/are_deceptional I täuscht/täuschen | vara(jo) | (13.1) □ decide(s) | entscheide-t/n | odločaOo) I (15.4) □ deliver(s)_over_to | überantworte-t/n | odgovaija(jo) | (17.4) □ is/are_delivered(_to) | ist/sind_überantwortete(s) | je/so_i2ročeno(i) | (4.4), (5.7) □ deprive(s) | nimmt/nehmen | odvzame(jo) I (15.1)D
Ncontra Ncorresp
Nc
=cut_off —decept Ndecide Ndeliver Ndeliver
Nd
lepnve
^devote devote(s) I legt/legen_sich_in |
se_posveča(jo) | (10.2) □ Ndiscl inform(s)_the_disclosedness_of; disclose(s) I
inforniiert_die_Erschlosseheit_von; erschließt | informira(jo)_razprtost; razpira(jo) | (2.4), (2.5), (2.6), (2.7), (6.1), (7.3), (7.6), (7.9), (10.1) □
Ndiscover can_be_discovered_only |
Neither
N
wird_nur_entdeckbar | bo_le_odkrito | (7.6) □
—discover_as
discover(s)_as | entdeckt_als |
odkriva(jo)_kot | (7.4) □
Ndivert divert(s) I ist/sind_verlegt |
je/so_založen(i), odvmjen(i) | (10.9),
(ll.l)D
do(es) I leistet/leisten | dela(jo) | (14.5), (18.1) □ Ndogma inform(s)_dogmatically ist/sind_dogmatisch | informira(jo)_dogmatsko | (16.6) □
—draw_upon
draw(s)_upon | nimmt/nehmen_in_ Anspruch | uposteva(jo) | (14.4) □
=draw_upon ° Fmerely
draw(s)_upon_merely | ninimt/nehmen_in_Anspruch_nur upošteva(jo)_le | (14.4) □ is/are_either | ist/sind_entweder | je/so_ali I (10.4), (10.7) □ emerge(s) | läßt/lassen_heraustreten | izhaja(jo) | (17.7) □ is_empty | ist_leer | je_prazno (3.7) □
Nencounter encounter(s) | begegnet/begegnen | srečuje(jo) | (14.4) □
Nencounter ° N^conceal
encounter(s)_unconcealedly |
begegnet/begegnen_unverdeckt
I	srečuje(jo)_nezakrito | (14.4) □
is/are_enough
kann/können_so_weit |
je/so_lahko_tako | (14.7) □
Nobtain is/are_enough_to_obtain |
kann/können_so_weit_.. .„gewinnen
je/so_lahko_tako_pridobljen(i)_s/z |
(14.7) □
is/are_equal | ist/sind_gleich | je/so_enak(i) | (12.5) □ am/are/is_equiprimordial | bin/bist/ist/sind/seid_gleichursprüng-lich I sem/si/je/smo/ste/so_enakoiz-vor-en/na/no/ni | (1.2), (12.2) □
=equi_p°Nalways
is/are_equiprimordially_in_each_ _way I ist/sind_^leichursprünglich_ _nach_der_Weise | je/so_
emerge
—empty
—enough
—enough'
—equal
-equi_p
_enakoizvir-en/ni_na_načm | (12.2) □ Nessen is/are_essentially | ist/sind_weseiihaft | je/so_bistveno | (10.1), (16.5) □
Nessen ° Ndiscl
is/are_essentialIy_disclosable | ist/sind_weserüiaft_erschließbar je/so_bistveno_razprt/i | (10.1) □
is/are_essential(_for) ist/sind_wesenliaft | je/so_bistven(o)Cza) | (3.6) □ is/informs_essentially | ist_wesenhaft I je_bistveno | (5.4) □ is/are_even | ist/sind_auch je/so_tudi I (17.7), (18.1) □ is_existential(_in every_case) | ist_(je_)existeazial | je_(vselej Jeksitencialno | (3.7), (9.3), (10.10), (12.2), (12.2) □ exist(s)_as | existier-t/en_als | eksistiraOo)_kot | (10.3) □
—essen_for
—essential
l—even
—exist
—exist_as
Nexist
const
is_existentially_constitutive konstituiert | konstituira.
(8.4) □
(5.6) □
.eksistencialno Nexist.surr is_existentially_surrended ist_existenzial_ausgeliefert je_eksistencialno_izročeno ^explicate explicate(s) | explizier-t/en | eksplicira(jo) | (17.5) □ informs_in_an_extra_way | inforniiert_noch_als_Zugabe | inforniira_kot_dodatek | (3.4) □ is/are_factually | ist/siiid_tatsächlich |
-extra
—factually
(9.1), (9.2) □
je/so_dejansko
—fail_to_recognize
fail(s)_to_recognize |
verkennt/verkennen_sich |
se_ne_spozna(jo) | (5.5), (5.6) □
=first is/are_first | ist/sind_zunächst | je/so_najprej | (17.7), (18.1)0
—first°Peven
is/are_in_the_first_ins tance ist/sind_zunächst_nur | je/so_najprejJe | (18.1) □
Nfirst(Nlet ° Nenierge
must_first_let_emerge j muß/müssen_erst_heraustreten_ Jassen | mora(jo)_najprej_dopustiti_ Jzstopiti I (17.7) □
Nfirst_find is_rirst_to_fmd_in |
ist_erst_zu_fmden_in | je_najprej_najti_v | (5.7) □ =for is/are_for | ist/sind_für je/so_za I (3.6), (4.5)□ Nformalize formalize(s) | formalizier-t/en |
formalizira(jo) | (14.7) □ ^formulate formulate(s) | formulier-t/en |
formulira(jo) | (17.7) □ =free gives_free
Nf,
rom
Ngeneral
Nget Ngive
gibt_frei I daje_prostost | (7.3) □ is_are_from | ist/sind_von | je/so_od (10.5) □
is/are_in_general | ist/sind_iiberhaupt | je/so_na_splošno | (16.2) □
dobi(jo)/je/so |
N
in
—have
get(s) I ist/sind (8.4), (16.6) □ give(s) I ist/sindC_gegeben) | dajeöo) | (14.4) □
=guard_against
guard(s)_against | bewahr-t/en_vor obvaruje(jo)_pred | (14.1) □ is/are_in | ist/muß_in | je/so_v | (9.3), (12.1) □ has/have hat/haben | ima(jo) (16.3), (16.5), (17.3)□
Nhave o ((Nalready ° Nbeen)t=take)
has/have_already_been_taken ist/sind_schon_vorweggenommen | je/so_že_vnaprej_vzet-o/i | (16.3) □
—have°Nalways
has/have_already | ist/sindJe_schon je/so_vselej_že | (17.3) □
^in inform(s)_iii | ist/sind_iii informiraOo)_v | (18.1)0
Nin_manner
inform(s)_in_a_manner ist_solche(s) I je/informira_tako (8.10) □
interpret(s) | interpretie-rt/ren | interpretirajo) | (1.5), (1.6) □ inform(s)_into | informier-t/en_in | informira(jo)_v | (11.1), (18.1) □ is/arejust | ist/sind_nur j je/so_le j (14.3), (18.1) □
-just_as_miich
is/are J ust_as_much_in | ist/sind_einzig_und_primär_in | je/so_ravnotako_v | (13.1) □
-mt
N
into
N
•just
t=kn
lOW
Flet
—just ° Nbring
is/areJust_to_bring ist/sind_zu_bringen je/so_kot_prineše-n/ni | (18.1) □ know(s) I weiß, wissen | ve/vedo (5.3) □
must_let I muß/müssen_lassen mora(jo)_dopustiti | (17.7) □
Nlet°l^einerge
must_let_emerge muß/müssen_heraustreten_lasseii mora(jo)_dopustiti_izstopiti | (17.7) □ =:iist list(s) I registrier-t/en | registrira(jo) | (9.1) □
=make make(s) | will/wollen | želi(jo) | (9.1) □
=make_up niake(s)_up | macht/machen_aus | donkončuje(jo) | (12.1) □
—make_up ° Nexist
make(s)_up_existentially | macht/machen_aus_existenzial dokončuje(jo)_eksistencialno | (12.1) □ =match to_be_a_match_for | gewachsen_sein | biti_dorasel | (3.1)D =merely is/are_merely | ist/sind_nur |
je/so_samo | (14.4) □ =most_part is/are_for_the_most_part ist/sind_zumeist | je/so_zlasti | (10.2) □ Nmust	I muß/müssen; bedarf/bedürfen |
mora(jo); potrebujeOo) | (18.1) □
—must ° Nwork_out
must_work_out | bedarf/bedürfen_ .Ausarbeitung | potrebuj e(jo)_ _izdelavo I (18.1)n [=noe inform(s)_noetically |
informier-t/en_noetisch | informira(jo)_noetično | (15.1) □ is/are_now | ist/sindjetzt je/so_zdaj | (16.6), (17.5) □
Nnow Nnow ° N
get
—obtain
Fof
now^et(s) I erhält/erhaltenjetzt | dobi(jo)_zdaj | (16.6) □ obtain(s) | gewinnt/gewinnen pridobiva(jo) | (14.7) □ of; is_of; depend(s)_of | von od 1(7.5),, (10.5), (15.1), (16.7), (17.7) □ '
Nonly is/are_only | ist/sind_»nur« je/so_»samo« | (10.5) □
Nonly_because
is/are_only_because | ist/sind_nur_
_weil I je/so_samo_zaradi | (9.4) □
=ont is_ontologically | ist_ontologisch |
je_ontološko | (3.10), (3.11) \ -\J
=ont,some is/are_ontically_sometimes | ^
ist/sind_zuweilen_iii_ontischer_Rede
j e/so_občasno_v_ontološki_govorici |
(3.1)D
or_inform(s) | oder_ist/sind | alije/so I (10.4), (10.7) □ orient(s)| orientier-t/en| se_usmeija(jo)| (14.6) □
Norient ° (Nprim ° Ntowards)
orient(s)_primarily_towards
orientier-t/en_sich_primär_zu |
se_usmeij a(j o)_naj prej_k/h/na
(14.6) □
inform(s)_over | informier-t/en_
Nor Norient
Nover Npass_by
_um I informiraoo)_o | (17.7) □ has_let_pass_by | hat_vorbeigehen_lassen |
(4.3) □
j e_pustil (o)_niimo_iti =penneate permeat(s)_with |
durchsetzt/durchsetzen | prepojuje(jo) | (10.8) □ Npertain pertain(s) | betrifft/betreffen |
zadevaOo) | (3.6), (10.1), (10.7) □
Nposit posit(s) I ansetz-t/en | določa(jo) | □
Nposit°Ndogina
posit(s)_dogmatically | ansetz-t/en_dogmatisch | določa(jo)_dogmatsko | (16.6) □ ,nni is_primarily | ist_primär |
je_primamo j (3.4), (14.6) □ Nprim_soI is/are_primarily_and_solely_in | ist/sind_einzig_und_primär_in | je/so_edino_in_primamo_v | (13.1) □ =prim_to is/are_primarily_to ist/sind_primär_in | je/so_primami_v | (10.2) □
Nprim°Ntowards
is/are_primarily_towards | ist/sind_primär^zu ] je/so_primamo_k/h/na | (14.6) □
Npri
Nproject project(s) | entwirft/entwerfen |
snujeOo)/projektira(jo) | (8.7), (8.9), (16.2) □
Nproject_upon
project(s)_upon
entwirft/entwerfen_auf
snuje(jo)_na/v | (8.3), (16.2) □
provides 1 bietet j nudi | (3.13) □
is/are_proximally | ist/sind_zunachst |
je/so_najprej | (10.2) □
Nprov Nprox
Nprox°N
h
pure
r-most_part
is/are_proximally_and_for_the_
_most_part | ist/sind_zunächst_und_
„zumeist I je/so_najprej_iii_najbolj |
(10.2) □
is/are_pure | ist/sind_pur | je/so_čist-i/a/o | (14.3) □
Npure°Msense
is/are_pure_non-sensory | ist/sind_pur(e)_unsirmlich(e)
je/so_čisto_nesmiseln-i/a/o
N
quest
Nreceive Nreduce
(14.3) □ fragt(_nach) |
(7.7), (7.8), (7.9),
dobi(jo)
question(s) vprašujeCpo) (8.1) □
receive(s) | erhält/erhalten (9.4) □
reduce(s) | zieht/ziehen herab | znižujeOo) | (8.10) □
Nrel_prim_whole
relate(s)_primarily_and_on_the_ _whole I bezieh-t/en_sich primär_und_ _im_ganzen | se_nanaša(jo)_ _predvsem_iii_v_celoti | (12.3) □ Nreveal_as reweal(s)_as | entdeckt_in |
odkriva(jo)_kot | (7.5) □ =root root(s)_in | wairzel-t/n_iii | temeljiOo)_v | (13.1) □
Nroot ° Njust_as_much
root(s)Just_as_much_in | wurzel-t/n_ebensosehr_in | temelji(jo)_pravtako_v | (13.1) □ inform(s)_for_the_sake_of_which ist/sind_umwillen_dessen(_als) | informira(jo)_zaradi_tega(_kot) | O □ say(s) I sagt/sagen | reče(jo) | (9.4) □ say(s)_with | sagt/sagen_mit | rečeOo)_s/z | (9.4) □ see(s) I sieht/sehen | vidi(jo) | (17.2) □
N:
sake
Nsay
Nsay_with
-see
Nseize Nshow Nsight Nsign
seize(s) I ergreift/ergreifen se_polastiöo) ] (4.3) □
kažeOo)
show(s) I zeigt/zeigen (15.1) □
sight(s) I sichtet/sichten_»sich« »se«_ugleda(jo) | (12.5) □ signifies I bedeuted | pomeni (3.8) 1 □
Nsketch_out_beforehand
sketch(es)_out_beforehand | zeichne-t/n_vor | skicira(jo)_vnaprej | (10.1) □ is/are_only_in_so_far_as ist/sind_nur_sofem_iii | je/so_samo_dokler | (12.5) □
Nso_far
Nsuch
t_e c
"supp
-sure
Ntake Ntake_away
is_such_that_in_every_case | verhält_sich_so_daß_immer | je_tak_da_vselej | discussion of (5.2)□
keep(s)_suppressed; iiiforms_in_a_ _suppressed_way | hält_nieder; infornaiert_verdeckt | duši; informira_zakrito | (1.3) □ must_be_sure | muß/müssen | mora(jo)_biti_prepričan(i) | (14.1) □ take(s) I nimmt/nehmen | vzame(jo) | (16.3)□
take(s)_away | zieht/ziehen_herab | odvzemaQo) | (8.10) □ than(_is) | (istjals ( (jejkot | (3.10), (9.1) □
inform(s)_that | infoniiier-t/en_ _in/im I informira(jo)_v | (17.5) □ Nthink_out think(s)_out | denkt/denken_aus |
si/se_izmišlja(jo) | (8.6) □ Nthrough is/are_through_and_through | ist/sind_durch_und_durch |
Nthan Nthat
je/so_skozi_in_skozi (16.4) □
(4.4), (9.4),
—throughout •
is/are_throughout | ist/sind_durch
je/so_skozi 1 (12.4) □
l=throughout°Nall
is/are_throughout_all |
ist/sind_durch_hindurch |
je/so_vseskozi | (12.4) □
throw(s) I wirft/werfen | vrže(jo) |
(10.3) □
Nthro
IW
Ntla row_before
throw(s)_before vorwirft/vorwerfen | vrže(jo)_v_ospredje | (8.10) □ is/are_thrown | ist/sind_gewerfen je/so_vržen(i/o/e) | (8.5) □
Ntlirown
No
—towards
Ntrans
Nu
FU°Fbnly
N
waive
-upon
"why
inform(s)_to | informiert_zu informira(jo)_v | (8.10), (14.6), (14.7), (17.6), (18.1) □ inform(s)_towards informier-t/en_zu | informira(jo)_k | (8.6), (14.6) □ is/are_transparent | ist/sind_durchsichtig | je_razviden/so_razvidni | (4.6) □ understand(s); has_understood | versteh-t/en; hat_verstanden | razume(jo); je_razuiiielo (5.2), (7.9), (10.2), (10.5), (10.11), (16.4) □
understand(s)_'only' versteh-t/en_»nur« razume(io)_»samo« | (10.5) □ is_constantly_waiving begibt_sich_ständig | je_vselej_na_poti_k | (4.3) | □ is/are_upon | ist/sind_auf | je/so_na (16.2), (16.3) □ why_is I warumjst j zakajje | (7.9) □
=with is_with
je_z|(5.1), (12.2),
ist_mit
(12.5), (13.1), (14.3), (18.1) □
-witli°Neqiial
is/are_with_equal | ist/sind_gleich_in je/so_enak(i)_v | (12.5) □
Nwith_eq_p
inform(s)_witli_equal_primordiality \ informiert_ebenso_urspriinglich informira(j o)_prav_tako_iz virno (8.3) □
Nwith_regard
is/are_with_regard_to ist/sind_hinsichtlich | je/ so_glede_na .| (8.4) □
Nwork_out
Nyet
work(s)_out I arbeite-t/-n_aus I izdelajo) I (18.1) □ is/are_yet | ist/sind_doch | je/so_pač (9.3) □
M,
comp
^conceal
^	does/do_not_inform;
does/do_not_impact; deos/do_not_make; am/are/is_not; does/do_not_maintain; etc. | informiert_nicht; beeinflußt/beeinflussen_mcht; bin/bist/ist/sind/seid_nicht; usw. | ne_informira-m/š/mo/te/jo; ne_vpli va-m/š/mo/te/j o ; nisem/nisi/ni/nismo/niste/niso; itd. | (3.4), (3.8), (5.1), (7.9), (8.6), (10.7), (12.4) □ ^act is_not_yet_actual |
ist_noch_nicht_Wirkliche | še_ni_aktuaIno | (3.8) □ has/have_not_competence | ist_kein(e) j ni_kompetenten | (3.2) □
inform(s)_unconcealedly ; do(es)_not_inform_concealedly | ist/sind_unverdeckt; ist/sind_nicht_ _verdeckt | informira(jo)_nezakrito; ne_infprmira(jo)_zakrito | (14.4) □ Fressen is_essentially_never
ist_als_wesenhaft_nie | ni_bistveno_nikoli | (5.1) □ ^first does/do_not_first_arise
ist/sind_nicht_erst_erwachsen | ni(so)_šele_nastal(i) | (5.4) □
Ngrasp_thenia
does/do_not_grasp_thematically erfaßt/erfassen_nicht_thematisch ne_zapopade(jo)_tematsko | (8.9) □ ^lay_aside lay(s)_aside | legt/legen_nicht_ab |
ne_odIoži(jo)(_vstran) | (10.9) □ T^less is/are_never_less.l
ist/sind_nie_weaiger ni (so)_nikoli_manj Mmeaii do(es)_not_mean
'-meaii

more
(9.3) □ mein-t/en_nicht ne_pomeni(jo) | (10.5), (14.3) □
'Njust
do(es)_not_meanJust
mein-t/en_nicht_nur |
ne_pomeni(jo)_samo | (14.3) □
does/do_not_become_more
wird/werden_nicht_.. .er
ni(so)_...ji/...ejši | (17.5)0
^more° —
-now
N^onto
does/do_not_become_now_more | wird/werdenjetzt_nicht_.. .er ni(so)_zdaj_...ji/...ejši | (17.5) □
N^more_than
is/are_never_more_than | ist/sind_nie_mehr_als | ni(so)_nikoli_več_kot | (9.2) □ is/are_not_ontologically | ist/smd_mcht_ontologisch | iii(so)_ontološko | (16.4) □
Monto ° Nconceive
does/do_not_ontologically_conceive | begreif-t/en_mcht_ontologisch | ne_zapopade(jo)_ontološko | (16.4) □
^root do(es)_not_root_m |
wurzelt/wurzeln_nicht_in | ne_temelji(jo)_v | (13.1)D
^root ° Nprim_sol
do(es)_not_root_primarily_and_ _solely_m |
wurzelt/wurzeln_iiicht_einzig_und_ _primär_m |
ne_temelj i(j o)_edino_le_iii_ _predvsem_v | (13.1) □ is/are_not_satifactory | ist/sind_nicht_entsprechend | ni(so)_ustrezno | (16.7) □
N^satisfy ° ^clarify
is/are_not_satisfactorily_clarified_ „within I entspricht/entsprechen_iiicht. _einer_befriedigenden_Aufklärung_ _in/im I ne_ustreza(jo)_zadostni_ _razjasnitvi_v | (16,7) □ is/are_non-sensoiy ist/sind_unsinnlich je/so_nesmiseln(i) | (14.3) □ does_not_signify | bedeuted_nicht | ne_pomeni | (4.1) □ is/sre_not_yet | ist/sind_noch_nicht ni(so)_še I (9.3) □ has_not_understood | hat_nicht_verstanden | ni_razumel(o) | (5.2') □
^satisfy
sense
Msign
N^yet
Mu
infórm(s)_altematively | informiert_in_alteraativen_Weise | informira(jo)_altemativno | (5.2') □ Haccord is/are_in_accordance_with | ist/sind^emäß
je/so_skladno_s/z | (8.6) □ ^as äs; is_altematively_as | als; ist_alternativ_als kot; je_aIternativno_kot ] (3.8) □ Hchar characterize(s)_altematively |
characterisier-t/en_in_altemativen_ _Weise I karakterizirao o) alternativno | (3.6) □
inform(s)_not_altematively | informiert_nicht_in_altemativen_ _Weise I
ne_informira(jo)_al temativno | (5.2'), (9.4) □
lt=	is_in_parallel | ist_parallel |
je_paralelno | (3.11)D
V	inform(s)_for_all |
informiert_fiir_alle | informira(j o)_za_vse discussion of (4.2), (5.2) □ ^already is/are_in_every_case_already ist/sindJe_schon | je/so_vselej_že | (5.6) □ '"'^pertain always_pertain(s)_to
betrifftjrmner | zadeva(jo)_vselej |
(7.1)	□
implies/imply; if...then... I impliziert/implizieren; wenn... dann... | implicira(jo); če...potem... | (1.5), (2.3), (2.4), (5.5), (5.6), (7.3), (7.6), (7.9),
(8.2),	(9.1), (10.9), (10.10), (14.1), (15.1), (15.4), (16.5), (17.7), (18.1) □
<=	implies_altematively
impliziert_in_altemativen_Weise | implicira_al temati vno | (7.9), (9.2) □
^so-far-as is_implied_so_far_as | ist_impliziert_sofera | je_implicirano_do_nadaljnega (3.7) □
is/are_equivalent_to; mean(s) j ist/sind_equivalent; besagt/besagen |
j e_ekvi valentno; pomeni (j o) (2.4), (2.8), (4.4) □
(2.2),

^always
^clarify
^comp
Qiscl
Q:
ssen
-exist
-ground
-ground '
Qie C,
pnm
is/are_m_e very_case ; is_definitively |
ist/sindje | je/so_vselej | (3.5) □
is_a_part_of; is_in; has/have (read in the right to the left direction of operator Q, etc. | ist_ein_Teil_von; ist_in; hat/haben (gelesen in der Richtung von rechts nach links der Operanden); usw. | je/so_del; je/so_v; ima/imajo (prebrano v smeri od desnega proti levemu operandu); itd. 1(1.5), (1.6), (2.4), (2.5), (3.2),
(3.3),	(3.7), (3.11), (4.2), (5.1),
(5.4),	(5.7), (7.3), (8.2), (8.10), (8.11), (10.1), (14.3), (14.5), (14.7), (17.3), (17.4), (17.5) □ is_always_a_part_of; has_always (<-) etc. I ist_immer_ein_Teil_von; hatje (<-); usw. | je/so_vselej_del; ima/imajo_vselej | (1.3), (1.4), (3.6) □
clarifies/clarify_in | klärt/klären_sich_auf_in/im se_razjasni(jo)_v | (16.7) □ possesses_compentence_for | besitzt_.. ._zu_können | ima_..._kar_razume | (3.4)□ is/are_disclosed_in | ist/sind_in/im_..._erschlossen | je/sta/so_razprt(a/i)_v | (2.8), (8.1) □
as_essentially_haviiig | ist_als_wesenhaft_in je_kot_bistveno_v | (4.2) □ lies_existentially_in | liegt_existenzial („in/im) | se_nahaja_eksistencialno_v | (3.3) □ is/are_grounded_in gründet/gründen_in/im | temelji(jo)_v | (15.3) □
-prim
is/are_gronded_primarily_in | gründet/gründen_primär_in/im | temelji(jo)_predvsem_v | (15.3) □ lies/lie_in | liegt/liegen_in/im | leži(jo)_v I (16.2) □ is/are_primarily_in | ist/sind_primär_in/im | je/so_najprej_v | (15.1), (16.1),
^essi
len
'equi_p

^sharply
(16.2), (16.3), (16.4), (16.6) □
is_one_of; belongs_to ist_eine(r)_der; gehört_zu | je_eden/ena/eno_izmed; pripada ] (1.1), (1.5), (1.6), (10.5)0 belong(s)_essentially | gehört/gehören_wesenhaft | pripada(jo)_bistveno | (9.2) □
is_distinguished_from; is_different_from | ist_unterschieden_von | je_razločljivo_od | (1.6) □ is_to_be_sharply_distinguished_ _from I
unterscheidet_sich_ebensosehr_von | se_razlikuje_prav_tako_ostro_od | (3.7) □
pertains_equiprimordially | betrift_gleichursprünglich zadeva_enakoizvomo | (2.6) □
operator_composition | Operatorskomposition, die | operatorska_kompozicija | (10.1), (10.2), (10.5), (10.10), (10.11), (12.1), (12.2), (12.4), (12.5), (13.1), (14.3), (14.4), (14.6), (14.7), (15.1), (16.2), (16.3), (16.4), (16.6), (16.7), (17.3), (17.5), (18.1) □
A Short (and Essential) Comment
The informational operand is a synonym for the processing, acting entity, is an informational subject which during its existence predicates (operates) the nature, constimtion, being, foundation, behavior, phenomenality, impacting, impacted-ness, informing, communicating, etc. bf the marked real entity. An informational operand operates informationally, predicates its subjectivity, behaves as a predicating subject.
Novice in zanimivosti
Sistemske znanosti in kibernetika
(Oblikovanje seznama elektronske pošte)
Seznam elektronske pošte za področje sistemskih znanosti in kibemetike se oblikuje na računalniškem sistemu SUNY-Binghampton (NY). Seznam je namenjen izmenjavi sporočil, ki zadevajo splošno razumevanje razvoja zapletenih, večravenskih sistemov, kot so organizmi, entitete uma (minds) in družbe, in sicer kot informacijske entitete (informational entities) v obliki možgočih cirkulamih procesov.
Namen elektronskega seznama je
(1)	vzpodbujanje razprave na področju sistemov in kibemetike,
(2)	komuniciranje v okviru raziskovalne komune med sistemskimi znanstveniki in kiber-netiki,
(3)	namestitev odlagališča elektronskih zbirk za splošno distribucijo na področju sistemov in kiber-netike ter naposled
(4)	oblikovanje osrednjega, javnega imenika za sistemske znanstvenike in kibemetike. Elektronska pošta lahko shranjuje in oddaja notice in sporočila, članke (technical papers), reference, pozive piscem člankov oz. referatov, računalniške programe, slike in diagrame.
K sodelovanju v tej razpravi so vabljeni vsi zainteresirani.
Za vpis (subskripcijo) je potreben računalniški konto z dostopom na eno od mednarodnih mrež. Pošljite najprej zbirko z eno samo vrstico:
"SUB CYBSYS-L vaše_polno_ime" strežniku (server) na naslov
LISTSER V^ BING VMB. BITNET
Ko prejmete potrditev subskripcije, pošljite sporočilo v sam seznam na naslov
C YBSYS-L(a)BING VMB. BITNET V sporočilo zapišite vaše ime, delovno mesto in kratek opis vašega dela ali interesa na področju sistemov in kiberentike.
Anton P. Železnikar
Spreminjanje paradigem v programirni tehniki
Avstrijska računalniška družba (ÖCG) in madžarsko Društvo Johna von Neumanna za računalniške znanosti (NJSZT) prirejata v Celovcu (Avstrija), od 21. do 23. septembra 1992, skupno letno konferenco na temo »Spreminjanje paradigem v programirni tehniki« (Shifting Paradigms in Software Engineering). Namen konference je obravnava najnovejšega stanja in trendov v softverski tehniki. Bistvene spremembe te tehnike se kažejo v objektno usmerjenem razvoju programov in tehniki računalniško podprtega programiranja. Nove tehnike spreminjajo šolniško znanje in vplivajo na aplikacije, teorijo, vzgojo in prenos znanja. Praktiki, raziskovalci in učitelji majhnih držav naj bi bili še posebej zainterisirani za ta razvoj.
Naslovne teme konference so: projektno upravljanje; umetna inteligenca: vidiki modeliranja; umetna inteligenca: vidiki gradnje orodij; jezikovne značilnosti; objektno usmeijeni razvoj programov; izzivi soočenja s kompleksnostjo; metodologija in izkustvo; in poučevanje programime tehnike. Sponzorji konference so: Zvezno ministrstvo za znanost in raziskavo. Društvo prijateljev Instituta za informatiko, Bacher Electronics, DEC in Siemens AG Österreich. Na koncu konference bo okrogla miza na temo Raziskovalna politika za informacijske tehnologije v majhnih evropskih državah. Sodelovali bodo predstavniki Komisije Evropske skupnosti, avstrijske, madžarske in slovenske vlade. Ob konferenci bo razstava CASE orodij.
Slovenija se bo na konferenci predstavila z referatoma K. Rizmana in I. Rozmana (Enhancing Reusability and Simplifying The OO Development with the Use of Events and Object Environment) ter Tatjane Welzer in Joszefa Györkösa (Teaching and Training in the CASE Tool Environment) z mariborske Tehniške fakultete. Kotizacija za pozno registracijo in nečlane znaša ÖS 3400. Naslov: Universität Klagenfurt, Institut für Informatik, Uni versi tätsstr. 65, A-9020 Klagenfurt, Österreich Elektronska pošta pa je:
mittermeir @ edvz .uni-klagenfurt.ada. at).
A.P. Železnikar
Strokovno povezovanje Slovenije na področju informatike
Definicija majhnih in velikih evropskih držav bržkone ni potrebna. Naredimo pa lahko poseben izbor, ki bi utegnil biti zanimiv za Slovenijo. V ta izbor spadajo ali bodo spadale: Avstrija, Belorusija*, Bolgarija*, Bosna in Hercegovina, Belgija, Češka, Danska*, Estonija*, Francija*, Grčija*, Hrvaška, Italija, Latvija*, Litva, Luksemburg*, Makedonija, Madžarska, Nemčija, Poljska*, Portugalska*, Romunija, Rusija, Slovaška, Srbija, Španija*, Švica*, Ukrajina*, Velika Britanija itd. Od neevropskih držav so aktualne Argentina*, Avstralija*, Izrael, Japonska, Južna Koreja*, Južnoafriška republika, Kanada, Nova Zelandija*, Singapur*, ZDA itn. Povezava preko svetovne podatkovne mreže bo prej ko slej mogoča in učinkovita, vendar z državami z zvezdico trenutno še nimamo dobrih osebnih povezav.
V naslednjem letu bo časopis Informatica razširil syoj uredniški odbor, v katerem so že zdaj zastopniki novih balkanskih držav, še na urednike iz Avstrije, Italije, Japonske, Madžarske, Romunije in ZDA. Časopis bo dosledno uporabljal angleški jezik. Vsebinski spekter časopisa bo ostal ohranjen, ojačila pa se bodo področja umetne inteligence, informacijske sistemske znanosti, robotske in kibemetske informatike. Kriteriji za objavo se bodo poostrevali skladno s ponudbo piscev, vendar bo Slovensko društvo Informatika (SDI) kot založnik obdržalo specifične kakovostne kriterije in strategijo znanstvenega in tehnološkega razvoja regionalnih prostorov.
Povezava s strokovnimi društvi in združenji omenjenih držav se bo sistematično ojačevala. Izhodišče SDI in drugih slovenskih društev bo, da bodo strokovne manifestacije (konference, seminaci, publikacije, projekti) s področja računalništva in informatike vselej mednarodna, tudi tako, da bodo slovenski strokovnjaki dejavno udeleženi na tujih prireditvah, pri tujih projektih in organizaciji, vendar s skupnimi cilji in dogovori. V tem okviru bo omogočena tudi strokovna razprava o ekonomskih vidikih in strategiji razvoja informacijskih znanosti in informacijske tehnologije v
Sloveniji in v drugih državah. Tako bo mogoče, postavljati vprašanja: Kaj proizvajati na področju informacijske tehnologije v Sloveniji? Kako organizirati racionalno obliko informacijskih raziskav? Kje pospeševati priliv tujega kapitala in investicij v domačo informacijsko industrijo, komunikacije in majhna računalniška tehnoločka in visokotehnolpška podjetja?
A.P. Železnikar
Popravek
v članku »An Introduction to Structured Systems Analysis«, objavljenem v časopisu Informatica 16 (1992), št. 2, stran 1, je bil v naslovu napačno odtisnjen priimek avtoija članka, in sicer Dimij namesto pravilno Damij. Avtorju Talibu Damiju se uredništvo opravičuje.
Nekateri zanimivi regionalni časopisi
Revue internationale de sistemique (Revue éditéeparl'AFCET; M.R. Vallèe, AFCET, 156, Boulevard Péreire, F-75017, France) objavlja prispevke v angleščini in francoščini.
Cybernetics and Systems (Robert Trappl, Department of Medical Cybernetics and Artificial Intelligence, University of Vienna, Freyung 6, A-lOlO Vienna, Austria).
Computers and Artifìcial Intelligence (Institute of Technical Cybernetics, Slovak Academy of Sciences, Dubravskà cesta 9, 842 37 Bratislava, Republika Češka in Slovaška).
Communication and Cognition (Fernand Vandamme, Blandijnberg, 2, B-9(XX) Gent, Belgium).
Metalogicon (Rivista intem^ionale di logica pura e applicata, di linguistica e di filosofia. Corso Umberto I, 70, 80034 Marigliano, Italy) izhaja v angleščini.
Cybernetica (Review of the International Association for Cybernetics, Palais des Expositions, Place A. Rijckmans, B-5(XX) Namur, Belgium) izhaja štirikrat na leto in objavlja prispevke v angleščini in francoščini.
XIII Magazine (Directorate General for Telecommunications, Information Industries and Innovation of the Commission of the European Communities) izhaja v evropskih jezikih.
A.P. Železnikar
Nada Lavrač
Compulog NoE: Network of Excellence in Computational Logic
Given is an overview of the ESPRIT III Network of Excellence in Computational Logic (Compulog NoE) and the report on the Second General Meeting of the Compulog Network of Excellence held in Rome, May 11-14, 1992. Since 1991, two Ljubljana Artificial Intelligence Laboratories (at the J. Stefan Institute and the Faculty of Electrical Engineering and Computer Science) act as a node in this network.
1	Introduction
Compulog Net is the ESPRIT Network of Excellence (NoE) in Computational Logic. It currently consists of over 60 nodes in leading European universities, research institutes and industries. The NoE aims at coordinating research in computational logic, coordinating training and mobility, and promoting the exploitation by European industry of the research results. The network is structured around six areas: constraint logic programming, knowledge bases, knowledge representation and reasoning, program development, programming languages, and parallelism and implementation techniques. The first General Meeting was in May 1991 in Rome. I participated at this meeting as the manager of the Ljubljana node of the Compulog NoE. Since the first meeting, the network has set up email facilities (ECRC, Munich) and a publication server (KU Leuven). Furthermore, a summerschool in Logic Programming will be held in Zurich (September 7-11, 1992), with a particular emphasis on industrial applications. For the near future, attention will be focussed on improving the structure of the NoE, improving the contacts with industry, and the implementation of a training and mobility scheme.
2	Area overviews
The network is structured around six areas. At the Rome meeting, the area overviews consisted mostly of an overview of the papers presented at the various area workshops.
Constraint Logic Programming (Alain Col-merauer, Marseille) deals with extensions of the
logic programming paradigm by means of algorithms and methods for constraint satisfaction. Work was reported on solving Boolean constraints, constraints on finite domains, linear equations on integers, non-linear constraints, and Gaussian elimination.
Knowledge Bases (Sury Sripada, ECRC Munich) topic deals with methods and techniques for building, querying, updating and checking the integrity of large deductive databases. The report was focussed on knowledge representation in KBs (semantics, different kinds of knowledge, structuring knowledge), querying KBs (conditional and intensional answers, simplifying queries by integrity constraints, complexity classes of queries), updating KBs (intensional updates, integrity checking), and building KBs (verification and validation, conceptual modeling, architectures). The proceedings of this workshop are available at the J. Stefan Institute.
Knowledge Representation and Reasoning (Bob Kowalski, London) dealswith the computer modeling of knowledge and mechanised reasoning procedures to use that knowledge for problem solving. Work was reported on abduction, nonmonotonic reasoning, inductive logic programming, temporal reasoning, and meta-level reasoning. Work on the first three areas is advancing significantly, while especially meta-level reasoning is "wide-open for future development", says Kowalski. He furthermore claimed that "work in Europe is presently influencing work in North-America". J. Stefan Institute was active in this workshop: Sašo Džeroski (co-author Ivan Bratko) has presented the paper "Using the m-estimate in inductive logic programming". The proceedings of this workshop are available at the J. Stefan Institute.
Program Development (Maurice Bruynooghe, Leuven) deals with methods and techniques for the automatic development of computer programs together with techniques for improving their efficiency. Work is being done on program analysis (mainly termination analysis), program transformation (with a renewed interest in fold/unfold transformations), program synthesis (proofs as programs, derivation of programs from specification, program synthesis from examples), and abstract interpretation. Bruynooghe signalled a trend from Logic Programming in general to LP languages, and from syntax to semantics.
Programming Languages (Franco Turini, Pisa) topic deals with the design of innovative programming languages and environments based on the logic programming paradigm. Turini gave an overview of the state of the art. Research aims at bridging the gap between the conceptual power of computational logic, and practical programming, without re-inventing the wheel, and maintaining the basic ideas. Work is done on semantics (negation, from ground Herbrand models to richer models, algebraic properties of program composition and backtracking, metalogic), pushing existing techniques to their limits (e.g., metalogic, negation as failure), generalisations of existing techniques (e.g., constraint LP), importing linguistic features of other programming paradigms (e.g., modules, object orientation), and software engineering for LP (e.g., debugging).
Parallelism and Implementation Techniques (Manuel Hermenegildo, Madrid): This network area has only recently been established. One . of its aims is improving the status of Computational Logic in the marketplace, by exploiting concurrent computers, and by formalisation of concurrent languages.
Invited talks were given by U. Montanari (Pisa): True concurrency for concurrent constraints and Krysztof Apt (CWI): Why the occur-check is not a problem. The occur-check (which should prevent the construction of circular bindings) is omitted from Prolog for efficiency reasons, thus rendering Prolog unsound. A solution to this problem is to let the interpreter decide where the occur check is needed. Apt presented conditions for occur-check free programs.
3 Software demonstrations
The following systems were demonstrated: UNIF, an environment for solving symbolic constraints (Claude Kirchner, INRIA); CMCAI CLP, a Prolog system featuring extensible unification for CLP (Christian Holzbaur, Vienna); FOLON, an environment for declarative construction of logic programs (Namur); and a generic abstract interpreter for Prolog (Namur). These systems are available frorri the authors.
4 The COMPULOG project
The COM P ULOG BRA (Basic Research Action, not to be confused with the NoE, and therefore written in capitals) has just finished; it will be continued as a basic research project in ESPRIT IIL Partners presented their achievements and future plans. The following topics are/have been addressed: Constraint Logic Programming (Marseille; actually they will not be in COMPULOG II, but have submitted their own project), types and objects (Kaiserslautern, Rome, Lisbon, Aachen, ECRC), non-monotonic reasoning (Lisbon, Cyprus, Amsterdam, Leuven), the meta-programming language Godei (Bristol), meta-reasoning (Pisa, London, Rome), legal reasoning (London, Uppsala), program development (Leuven, Pisa, Uppsala, Amsterdam, Edinburgh, Rome).
5 Overview of other approved ESPRIT III projects
MEDLAR (Wolfgang Bibel, Darmstadt): Mechanizing deduction in the logics of practical reasoning. This is a continuation of an ESPRIT II BRA, aiming at providing a parametrised logical framework for different kinds of practical reasoning. The framework proposed is that of labeled deduction systems, advocated by Dov Gabbay (Imperial College). Bibel also proudly announced that the German government is funding a big national project on Deduction.
PARFORCE (Manuel Hermenegildo, Madrid): Parallel formal computing environment. This project aims at building, integrating and assessing tools for global analysis and program transformation.
ACCLAIM (Janson, SICS): Advanced concurrent constraint languages: application, implementation, methodology.
ILP (Maurice Bruynooghe, Leuven): Inductive Logic Programining ESPRIT III Basic Research project no. 6020. Artificial Intelligence Laboratories of the J. Stefan Institute and Faculty of Electrical Engineering and Computer Science, Ljubljana are a partner in this project.
LAC (Antonio Porto, Lisbon): Logical account of change. This is a working group.
The future of Compulog NoE and ESPRIT Basic Research
Simon Bensasson (CEC, Brussels) mentioned the following two main goals of NoEs: they are funded for coordination (not for e.g., research), and they are the vehicles to make research industrially interesting, leaving Basic Research basic. On the topic of the new BRA round, Bensasson could not guarantee a starting date, which he said was due to the new procedures entered after Maastricht: the new contracts are now to be signed by the Commission, supposedly causing a considerable delay. The really bad news was not made public by Bensasson, but was spread later: the amount of money spent on Esprit III will be seriously reduced (supposedly because of necessary aid to Eastern Europe), and contracts will be signed only for one and a half year. This bad news significantly influenced a general discussion on the future of the Compulog NoE. The most optimistic remarks came from Kowalski, who said: "ESPRIT has been bad before, and they will improve again." He added that one should treat Brussels a bit less seriously, and just proceed with the things one thinks should be done. Anyway, "you shouldn't be in Compulog NoE if you hadn't joined it, had it not been funded". He conceives a role for the NoE as a sort of European chapter of the Association of Logic Programming. Others added that the NoE should focuss on activities for which one needs a network of groups rather than an association of individuals, such as preparing proposals, managing communication, contacts with industry and other networks, and acting as a pressure group. With respect to this last point, it was decided to protest firmly against the cuts in ESPRIT III, possibly seeking publicity.
Later in June this year, NoE members got more optimistic news about the starting date of ESPRIT III projects and the financing of them. The J. Stefan Institute is in particular interested in the beginning of the ILP basic research project no. 6020 which should start in September this year. ILP stands for Inductive Logic Programming, an emerging research area spawned by machine learning and logic programming whose main goal is to upgrade the classical empirical learning paradigm to a logic programming framework. There are 7 main partners and two associate partners in the project (coordinated by Maurice
Bruynooghe and Luc De Raedt, Katholieke Uni-versiteit Leuven). Ljubljana AI laboratories act as one of the main partners (principal researcher Ivan Bratko, project manager Nada Lavrač).
7 Our participation in Compulog NoE
Compulog NoE facilitates comminication, mobility and technology transfer by means of regular scientific meetings, access to electronic communication, coordination of training of graduate and postgraduate researchers and dissemination of information about publications.
Regular scientific meetings provide a firm basis for building a strong research community with shared goals and common techniques. Two types of meetings are organized each year: a general meeting covering the whole field and an area meeting for each of the subgroups. In addition, NoE organizes annual summer schools for training students and for technology transfer to industry.
Since June this year, NoE is being reorganized: network nodes are now classified as managing nodes, full nodes and associated nodes. As th'e emphasis of the work at the J. Stefan Institute is on the use of logic programming and machine learning rather than computational logic itself, we got classified as an associated node. We are part of the subgroup area Knowledge Representation and Reasoning (coordinated by Robert Kowalski, London). Although the participation in the NoE does not bring any financial funding, our involvement in this NoE is more than useful - we got access to many useful informations, we take part in the Compulog NoE database of scientific publications, etc. Since NoE wiU coordinate European research in different subareas and allocate funds which will be available through the new ESPRIT III initiative named Human capital and mobility, our involvement in this NoE is invaluable.
Acknowledgements
My participation at the Second General Meeting of the Compulog Network of Excellence was financed in part by the Slovenian Ministry of Science and Technology and by the J. Stefan Institute. The report is partially based on the text written by Peter Flach, ITK, Tilbugh University.
STATUT SLOVENSKEGA DRUŠTVA INFORMATIKA
1. SPLOŠNE DOLOČBE Čl. 1
Ime društva je »Slovensko društvo INFORMATIKA« (v nadaljnjem besedilu: društvo). Sedež društva je v Ljubljani, Vožarski pot 12.
Čl. 2
Društvo je prostovoljno združenje vseh, ki so zainteresirani za razvoj in uporabo informatike in jih združuje, vključuje in povezuje na profesionalni podlagi. Dejavnosti, ki določajo delo društva, se določijo s klasifikacijo dejavnosti NACE REV. 1. — so za društvo 0/91.12. Društvo deluje predvsem na področjih informacijske tehnnologije in informacijske storitve ali informatike.
Društvo je nepolitična organizacija, sestavina civilne družbe in deluje na neprofitnih principih.
Čl. 3
Društvo deluje na območju Republike Slovenije. Čl. 4
Društvo je pravna oseba,
Č1.5 -
Društvo ima svoj znak in pečat. Znak društva je oblikovan napis INFORMATIKA. Pečat društva je krog s premerom 3 cm, v sredini katerega je znak društva, ob robu pa napis »Slovensko društvo, Ljubljana«.
Čl. 6
Društvo lahko ustanovi območne podružnice zaradi učinkovitejšega delovanja povsod, kjer je za to interes članov, in sekcije, kjer se je potrebno organizirati po interesnih področjih. Podružnice in sekcije niso pravne osebe.
Čl. 7
Društvo se lahko včlani v sorodno tujo ali mednarodno društveno organizacijo s podobnimi nameni in cilji, predpisanimi s temi pravili pod pogojem, da dejavnost te organizacije ni v nasprotju z interesi Slovenije.
Čl. 8
Društvo obvešča o svojem delovanju širšo in ožjo javnost.
1.	Ožjo javnost obvešča:
—	z razpošiljanjem vabil in zapisnikov občnega zbora članom društva;
—	z občasnimi obvestili društva;
—	s tem da so zapisniki vseh organov društva dostopni na vpogled članom društva.
2.	Širšo javnost obvešča:
—	s tem, da so seje vseh organov društva javne in da se nanje vabijo osebe, ki kažejo tak interes;
—	z izdajo vabil, strokovnih publikacij in obvestil ter preko drugih sredstev javnega obveščanja.
Za zagotovitev javnosti dela je odgovoren predsednik ali član odbora, ki je za to pooblaščen.
Čl. 9
Društvo ima naslednje namene in cilje predvsem na področjih, določenih v členu 2 :,
—	da organizirano širi zavest in krepi pomen informacijske tehnologije in storitev za razvoj slovenske družbe in njeno vključevanje v svetovno in evropsko delitev dela;
—	da pospešuje razvoj znanj med članstvom in drugimi strokovnjaki razvija medsebojno sporazumevanje, strokovno kritiko, tekmovalni duh in strokovnost;
—	da pomaga in pospešuje razvoj tehnologije in znanosti;
—	da spremlja, proučuje in pomaga pri razvoju, vpeljevanju in uporabi informatike;
—	da skrbi za popularizacijo in pospeševanje strokovnega usix)sabljanja kadrov na svojem področju in na sorodnih področjih;
—	da povezuje delo svojega članstva z delom ostalih strok;
—	da omogoča svoj emu članstvu in širši j a vnosti seznanjanje z najnovejšimi dosežki iz svojega področja doma in v tujini;
—	da sodeljuje s podobnimi tujimi in mednarodnimi društvenimi organizacijami;
—	da sodeluje z organi oblasti, političnimi in gospodarskimi organizacijami in drugimi asociacijami;
—	da sodeluje pri izdelavi zakonskih predpisov in standardov, ki se nanašajo na razvoj in uporabo računalniške tehnike in informatike
V Sloveniji;
—	da pri svojih članih razvija in vzpodbuja profesionalno etiko;
—	da pomaga ali samo ustanovi druge organizacije civilne družbe na svojem področju, kot so na primer programerska ali podobne zbornice, in za to kandidira in prevzema koncesije za določene državne pristojnosti.
Čl. 10
Društvo uresničuje svoje namene in cilje z naslednjimi dejavnostmi:
—	s prirejanjem strokovno-znanstvenih sestankov, simpozijev, seminaijev, tečajev, razstav, tekmovanj;
—	z izdajanjem zbornikov, referatov in člankov, strokovnih časopisov, internega glasila, posebnih obvestil in strokovne literature;
—	s posredovanjem podatkov o aktualnih problemih in najnovejših dosežkih na področju informatike doma in v svetu javnosti prek javnega obveščanja;
—	s povezovanjem in vključevanjem v podobne domače, tuje in mednarodne društvene organizacije;
—	z organizacijo posebnih oblik funkcionahiega izobraževanja v svoji organizaciji ali v sodelovanju z drugimi;
—	s smotrnim gospodarjenjem z lastnimi sredstvi in premoženjem;
—	z iniciranjem raziskovalnih in razvojnih pobud in njihovim izvajanjem;
—	z iniciranjem pobud za funkcioniranje državne uprave, ki so povezane s področjem informatike, oziroma upravne tehnologije.
Čl. 11
Društvo dela strokovno prek sekcij in komisij ter podružnic:
—	Sekcije so praviloma odprte vsem članom društva, ki so za delo pokazali interes. Vodi jih predsednik, nadomešča pa namestnik. Po potrebi lahko Izvršni odbor društva ustanovi nove sekcije.
—	Po potrebi se oblikujejo komisije za specifične dejavnosti. Komisije delajo praviloma v trajnem sestavu in so njihove naloge bolj eksperme. Vodi jih načehiik in ima namestnika. Člani so imenovani s strani
Izvršnega odbora.
—	Podružnice se lahko ustanovijo po potrebi po krajevnem principu. Pravila za volitev vodstev in način upravljanja dela podružnic določa izvršni odbor. Verificira jih naknadno. Predsednika podružnice voli njen občni zbor. Podružnice se praviloma oblikujejo po enotah lokalne uprave v Sloveniji. Podružnice samostojno določajo svoj program dela in lahko vodijo svoj račun v okviru skupnega računovodstva društva.
—	Sekcije, komisije in podružnice vodijo praviloma člani izvršnega odbora ali tisti, ki jih za to pooblasti izvršni odbor.
II. ČLANSTVO
Čl. 12
Član društva lahko postane vsak državljan Republike Slovenije, kije zainteresiran za ravoj in uporabo informatike oz. informacijske tehnologije in storitev in sprejema ta statut ter se ravna po njem.
Član društva lahko postane tudi tujec, če je njegovo delovanje v skladu z načeli naše družbe in nameni društva, navedenimi v tem statutu in ga sprejme s posebnin sklepom Izvršni odbor.
Čl. 13
Pravice članov društva so:
—	da volijo in so izvoljeni v organe društva;
—	da sodelujejo pri delu organov društva;
—	da dajejo predloge in sugestije organom društva o delu in reševanju nalog;
—	da imajo vpogled v delo organov društva in dajejo o njem pripombe.
Čl. 14
Dolžnosti članov društva so:
—	da volijo v organe društva;
—	da sodelujejo pri delu organov društva;
—	da se ravnajo po statutu in sklepih organov društva;
—	da z osebnim prizadevanjem in vzorom pripomorejo k uresničitvi delovnega programa društva;
—	da redno plačujejo članarino;
—	da se ravnajo po kodeksih in drugih etičnih normah, sprejetih v društvu
Člani društva in voljeni organi društva so osebno odgovorni za vestoo opravljanje sprejetih nalog in
funkcij.
Društvo lahko izvoli častnega predsednika, izmed članov, ki so se posebno uveljavili pri razvoju društva in njenih dejavnosti. Častni predsednik je vabljen na seje organov društva, lahko pa mu občni zbor ali izvršilni odbor poveri tudi konkretne zadolžitve.
Častni član društva lahko postane oseba, ki se je posebno uveljavila z delom pri razvoju področja dejavnosti društva in sprejema to priznanje.
Častne člane imenuje občni zbor na predlog Izvršnega odbora društva.
Čl. 16
Pravice in dolžnosti članov v organih društva so častne. Za svoje delo v organih društva člani ne prejmejo plačila. Izjema so operativno-ad-ministrativne funkcije, za katere se prizna honorar po pogodbi o delu.
Čl. 17
Članstvo v društvu preneha:
—	z izstopom;
—	s črtanjem;
—	z izključitvijo na podlagi odločbe disciplinskega odbora društva;
—	s smrtjo.
Čl. 18
Član izstopi iz društva prostovoljno, kadar poda Izvršnemu odboru društva pisno izjavo o izstopu.
Čl. 19
Član se izključi iz društva, če grobo krši pravice in dolžnosti, naštete v 13. in 14. členu stamta, če zavestno ravna proti interesom in ciljem društva in če ga disciplinski odbor spozna za odgovornega.
ra. ORGANIZACIJA DRUŠTVA
Čl. 20
Organi društva so:
—	občni zbor;
—	izvršni odbor;
—	nadzorni odbor;
—	disciplinski odbor.
Mandat vseh organov društva traja 3 leta.
Občni zbor Čl. 21
Občni zbor je najvišji organ društva in voli druge njegove organe. Sestavljajo ga vsi člani društva.
Čl. 22
Občni zbor je lahko reden ali izreden. Redni občni zbor sklicuje izvršni odbor vsako tretje leto. Izredni občni zbor se skliče po potrebi. Skliče ga lahko izvršni odbor na svojo pobudo, na zahtevo nadzornega odbora ali na zahtevo 1/4 članov. Izredni občni zbor sklepa samo o stvari, za katero je sklican.
Izvršni odbor je dolžan sklicati izredni občni zbor najkasneje v roku enega meseca po tem, koje prejel tako zahtevo. V naspromem primeru lahko skliče izredni občni zbor 1/3 članov društva ali predsednik nadzornega odbora.
Sklic občnega zbora z dnevnim redom mora biti objavljen najmanj 10 dni pred občnim zborom.
Čl. 23
Občni zbor sprejema svoje sklepe z večino glasov navzočih članov. Način glasovanja določi občni zbor. Ko se glasuje o razrešnici članov organov društva, ti ne morejo glasovati. Volitve članov organov društva so tajne.
Čl. 24
Občni zbor je sklepčen, če je ob predvidenem začetku navzočih več kot polovica članov.
Če ob predvidenem začetku občni zbor ni sklepčen, se začetek odloži za 1 uro, nakar občni zbor veljavno sklepa, če je prisotnih vsaj 10 članov, ki niso izvoljeni v organe društva.
Čl. 25
Občni zbor odpre predsednik društva in ga vodi, dokler občni zbor ne izvoli delovnega predsedstva. Poleg tega, izvoli občni zbor še zapisnikaija in dva overovatelja zapisnika, volilno komisijo, kandidacijsko komisijo, in druge delovne organe, vse iz navzočih članov društva.
Čl. 26
Občni zbor:
—	sklepa o dnevnem redu;
—	razpravlja o delu in poročilih izvršnega in nadzornega odbora ter sklepa o njem;
—	Sprejema delovni program društva;
—	odloča o pritožbah proti sklepom izvršnega odbora ali odločbam disciplinskega odbora;
—	sklepa o finančnem načrtu za obdobje trajanja mandata ter potrjuje zaključni račun za preteklo obdobje;
—	sprejema, spreminja in dopolnjuje statut ter druge splošne akte društva ter potrjuje statutarne sklepe;
—	z glasovanjem neposredno voli predsednika, podpredsednika in sekretaija društva ter člane izvršnega, nadzornega in disciplinskega odbora;
—	odloča o prenehanju in včlanjevanju društva v druge organizacije doma ali v taj ini;
—	imenuje delegate in delegacije, ki zastopajo društvo pri drugih organizacijah, oziroma daje pooblastila za taka imenovanja;
—	odloča o višini članarine ter o olajšavah, ki se priznajo članom društva ob uporabi uslug društva, ter določa valorizacijo obveznosti iz članarine;
—	imenuje častne člane društva na predlog izvršnega odbora;
—	daje in odvzema pooblastila Izvršnemu odboru.
Čl. 27
O delu občnega zbora se piše zapisnik, ki ga podpišejo predsednik delovnega predsedstva in oba overovatelja zapisnika.
Čl. 28
Društvo lahko za potrebe društva in njegove dejavnosti ustanovi profitno d.o.o, delniško družbo ali zadrugo in lahko ustanovi ali sodeljuje v delu katerekoli gospodarske družbe, vendar mora za to Izvršni odbor dobiti soglasje Občnega zbora.
Izyršni odbor
Čl. 29
Izvršni odbor je izvršilni organ občnega zbora in opravlja zadeve, ki majih naloži ta organ in druge zadeve, ki po naravi spadajo v njegovo delovno področje.
Izvršni odbor opravlja organizacijske, upravne, administrativne in strokovno tehnične zadeve in izvršuje sklepe občnega zbora in programa društva.
Izvršni odbor je za svoje delo odgovoren občnemu zboru društva.
Čl. 31
Izvršni odbor sestavljajo: predsednik, podpredsed-nik(a) in sekretar društva, 4 izvoljeni člani odbora, predsedniki sekcij ali podružnic. Namestniki predsednikov sekcij in podružnic imajo v času nadomeščanja iste pravice in dolžnosti, kot tisti, ki jih nadomeščajo.
Predsednik društva je istočasno predsednik izvršnega odbora. Izvršni odbor se sestane po potrebi, vendar najmanj 4-krat lemo.
Čl. 32
Društvo ima predsednika in podpredsednika. Predsednik (v primeru njegove odsotoosti pa podpredsednik) društva zastopa društvo pred državnimi organi in drugimi organizacijami ali tretjimi osebami po navodilih izvršnega odbora. Podpredsednika in člani si razdelijo delo, eden od njih pa po dogovoru nadomešča predsednika.
Predsednik, podpredsedniki, tajnik in dva člana Izvršnega odbora oblikujejo sekretariat Izvršnega odbora kot obliko dela, ki tekoče izvršuje naloge tega odbora.
Čl. 33
Izvršni odbor upravlja društvo v času med dvema občnima zboroma in po sklepih in programu, sprejetih na občnem zboru.
Sekcije se na osnovi potijenaga programna praviloma sestajajo dvakrat letno, po potrebi tadi bolj pogosto. Podružnice se sestanejo najmanj dvakrat na leto.
Seje izvršnega odbora sklicuje predsednik društva. Sklic seje mora biti objavljen najmanj 7 dni pred dnevom, za katerega je seja sklicana. Izvršni odbor lahko za svoje delo in delo sekcij ter podružnic in komisij določi poslovnik.
Čl. 34
Člane Izvršnega odbora voli občni zbor za tri leta in so lahko ponovno izvoljeni. Izvršni odbor lahko kooptira največ tretjino novih članov — praviloma vodij novoustanovljenih sekcij ali podružnic. Izvršno odbor lahko na osnovi ostavke zamenja največ tri voljene člane. Zamenjavo lahko izvrši tudi, če se član tega telesa ni odzval na vabilo dvakrat zaporedoma in to neupravičeno.
Izvršni odbor imenuje tudi predsednika in člane organizacijskih in programskih odborov posameznih strokovno znanstvenih sestankov oziroma člane uredniških odborov posameznih publikacij ali glasil društva.
Čl. 35
V okviru svojega delovnega področja opravlja izvršni odbor tele zadeve:
—	sklicuje občni zbor in pripravlja poročila o delu ter predloge za občni zbor;
—	pripravlja predloge za splošne akte društva;
—	pripravlja in sestavlja predlog za finančni načrt in zaključni račun;
—	vodi evidenco članov;
—	imenuje iz vrst članstva komisije, organizacijske in programske odbore ter uredništva;
—	skrbi za materialno-finančno poslovanje in sredstva društva;
—	neposredno skrbi za uresničevanje ciljev in nalog, ki jih določajo 8., 9. in 10. člen statuta;
—	koordinira delo sekcij, organizacijskih in programskih odborov ter uredništev;
—	sklepa pogodbe o delu z osebami, ki opravljajo tehnično-administrativne posle društva ter usmeija in nadzoruje njihovo delo.
Čl. 36
Izvršni odbor sprejema sklepe, če seji prisostvuje večina članov. Sklepi so sprejeti, če zanje glasuje večina navzočih članov.
Po potrebi lahko Izvršni odbor organizira dopisne seje, kjer se odloča za posamezne predloge z da ali ne. Vedno mora biti istočasno izvedeno glasovanje o potrebi dopisnega izjasnjevanja.
Nadzorni odbor
Čl. 37
Nadzorni odbor je sestavljen iz šestih članov, kijih izvoli občni zbor za tri leta. Nadzorni odbor izvoli iz svoje srede predsednika, dva člana in dva namestnika.
Čl. 38
Naloga nadzornega odbora je, da spremlja delo izvršnega odbora in opravlja stalni nadzor nad finančnim poslovanjem ter izvajanjem statuta in drugih aktov društva. Nadzorni odbor je
odgovoren občnemu zboru in mora o delu Izvršnega odbora pisno poročati ob koncu leta v javnem glasilu, če v tem lem ni občnega zbora.
Čl. 39
Nadzorni odbor sprejema veljavne sklepe, če so prisotoi trije člani in če zanje glasujeta,vsaj dva člana.
Člani nadzornega odbora ne morejo biti hkrati člani izvršnega odbora, vendar se praviloma vabijo na vse seje izvršnega odbora brez pravice odločanja.
Disciplinski odbor Čl. 40
Disciplinski odbor sestavljajo trije člani, ki jih izvoli občni zbor za tri leta.
Disciplinski odbor izvoli iz svoje srede predsednika. Disciplinski odbor vodi disciplinski postopek in izreka ukrepe po disciplinskem pravihiiku.
Za svoje delo je odgovoren občnemu zboru društva.
IV. MATERIALNO-FlNANČiNO POSLOVANJE DRUŠTVA
Čl. 41
Dohodki društva so:
—	članarina;
—	dohodki od prijavnin za strokovno znanstvena srečanja in prodaje publikacij;
—	dotacije in subvencije;
—	darila in volila;
—	prihodki iz sponzorskih pogodbenih odnosov;
—	drugi dohodki.
Društvo razpolaga s finančnimi sredstvi v mejah odobrenega finančnega načrta in običajih ter normah, določenih za neprofitni sektor.
Čl. 42
Premoženje društva predstavljajo vse premičnine in nepremičnine, ki so last društva in so kot take vpisane v inventarno knjigo. S premoženjera društva upravlja Izvršni odbor.
Premičnine se lahko odstopijo ali odmjijo tretjim osebam le na podlagi sklepa seje Izvršnega odbora. O nakupu in odmjitvi nepremičnin odloča Občni zbor društva.
Materialno in finančno poslovanje mora biti v skladu z načeli, ki veljajo za društva in z veljavnimi predpisi. Pri določanju položaja zaposlenih, njihovega nagrajevanja, honoriranju in plačevanju materialnih nadomestil za društvo veljajo določila, ki veljajo za državno upravo.
Čl. 44
Finančno poslovanje društva se odvija v skladu z zakonom.
Blagajnik vodi finančno poslovanje društva po pravilniku materialno-finančnem poslovanju oziroma standardih, ki so za to določeni.
Denarna sredstva društva vodi blagajnik v blagajniški knjigi. Blagajnik poroča o finančnem poslovanju Izvršnemu odboru.
■ Čl. 45
Finančne in materialne listine podpisuje predsednik ali sekretar društva oziroma določeni pooblaščeni podpisniki.
Odredbodajalec je predsednik društva, v njegovi odsotnosti pa podpredsenik.
V. KONČNE IN PREHODNE DOLOČBE Čl. 46
Društvo preneha obstajati:
—	s sklepom občnega zbora, če zanj glasuje dvotrećinska večina navzočih članov;
—	z odločbo pristojnega upravnega organa o prepovedi dela;
—	če pade število članov pod 10.
Čl. 47
V	primeru prenehanja društva pripadejo njegova sredstva ustrezni organizaciji, ki nadaljuje dejavnost društva v Republiki Sloveniji, ali Rdečemu križu Slovenije, če take organizacije niso ustanovili eno leto po prenehanju dela društva.
Čl. 48
V	skladu s tem statutom ima društvo naslednje splošne akte:
—	Disciplinski pravilnik, oziroma kodeks društva;
—	Pravilnik o materialno-finančnem poslovanju;
—	Poslovnik o poslovanju komisij, organizacijskih, programskih in uredniških od-
borov.
Splošni akti iz prejšnjega odstavka morajo biti sprejeti na prvem občnem zboru po ustanovitvi društva. Pravilnike sprejema občni zbor, pripravlja pa izvršni odbor društva.
Prehodne določbe
Čl. 49
Zaradi konsolidacije organov društva se izjemoma določi rok za nov redni občni zbor društva najkasneje eno leto po sprejemu statuta.
Čl. 50
Izvršni odbor se pooblasti za kooptiranje, poleg izvoljenih, največ štirih novih članov, ker še niso določene vse sekcije in komisije.
Čl. 51
Na prihodnjem občnem zboru naj Izvršni odbor predloži sestav sekcij in komisij kot statutarno določbo.
Čl. 52
Ta statut je sprejel občni zbor društva, dne 2. julija 1992 v Ljubljani in stopi v veljavo, ko gà overovi pristojni upravni organ. S tem dnem preneha veljati statut, sprejet na ustanovnem občnem zboru, dne 19.marca 1981.
Sekretar društva: Ema Rupnik, l.r.
Predsednik društva: Tarnal Banovec, l.r.
Editor-in-Chief
anton p. zeleznikar
Volaričeva 8 61111 Ljubljana Slovenia
The Slovene Society Informatika Vožarski pot 12 61000 Ljubljana, Slovenia PHONE: ( + 38 61) 15 53 22 , TELEX: 31105 zastat yu FAX: (+38 61) 21 69 32 3 AM
Associate Editor
RUDOLF MURN
Jožef Stefan Institute Jamova c. 39 61000 Ljubljana, Slovenia PHONE: ( + 38 61) 15 91 99
Editorial Board
Publishing Council
suad alagic
Faculty of Electrical Engineering University of Sarajevo Lukavica - Toplička bb 71000 Sarajevo Bosnia and Herzegovina
damjan b0jad2iev
Jožef Stefan Institute
Jamova c. 39
61000 Ljubljana, Slovenia
jozo dujmovic
University of Texas at Dallas School of Eng. & Computer Sci. Richardson, TX 75083 - 0688 U.SA.
janez grad Faculty òf Economics University of Ljubljana Kardeljeva ploSčad 17 61000 Ljubljana, Slovenia
bogomir horvat
Faculty of Engineering University of Maribor Smetanova ul. 17 62000 Maribor, Slovenia
UUBO PIPAN
Faculty of Electrical Engineering and Computing University of Ljubljana Tržaška c. 25 61000 Ljubljana, Slovenia
TOMAZ pisanski
Department of Mathematics and Mechanics
University of Ljubljana Jadranska c. 19 61000 Ljubljana
oliver popov
Faculty of Natural Sciences
and Mathematics
C. M. University of Skopje
Arhimedova 5
91000 Skopje, Macedonia
saso prešern
PAREX, Institut for Computer Kardeljeva 8
61000 Ljubljana, Slovenia
viuem rupnik
Faculty of Economics University of Ljubljana Kardeljéva ploščad 17 61000 Ljubljana, Slovenia
branko soucek
Faculty of Natural Sciences and Mathematics University of Zagreb Marulićev trg 19 41000 Zagreb, Croatia
TOMAZ BANOVEC
Zavod SR Slovenije za statistiko Vožarski pot 12 61000 Ljubljana, Slovenia
ANDREJ JERMAN- BLAZIČ
Iskra Računalniki Tržaška c. 2
61000 Ljubljana, Slovenia
BOJAN^ KLEMENČIC
Ljubljana Slovenia
STANE SAKSIDA Institute of Sociology University of Ljubljana Cankaijeva ul. 1 61000 Ljubljana, Slovenia
JERNEJ VIRANT
Faculty of Electrical Engineering and Computing University of Ljubljana Tržaška c. 25 ' 61000 Ljubljana, Slovenia
Informatica is published four times a year in Winter, Spring, Summer and Autumn by the Slovene Society Informatika, Vožarski pot 12, 61000 Ljubljana, Slovenia.
Informatica
A Journal of Computing and Informatics
CONTE NT S
Basic Informational Axioms
Integrity in the Relational Data Model
Understandability of the Software Engineering Method as an Important Factor for Selecting a CASE Tool
Allocation of HADF Graphs onto a Tree Structure (in Slovene)
Predictable Dynamic Task Scheduling in Hard Real-Time (in Slovene)
Synchronous Dataflow Computer Architecture II (in Slovene)
An Informational Approach of Being-there as Understanding III
News (in Slovene and English): Miscellaneous News (in Slovene) Compulog NoE ... The Statute of SDI (in Slovene)
A.P. Zeleznikar
M. Radovan
L Rozman J. Gyorkos K. Rizman '
P. Zaveršek R Kolbezen
Barbara Koroušić P. Kolbezen
J. Šile L. Gyergyek
A.P. Zeleznikar
Nada Lavrač
1
17 25
29 36 46 64
76 76 78 81