| Author |
Message |
aschunk
|
|
Post subject: Präzedenzenrelation
 Posted: Nov 30, 2008 - 08:37 AM
|
|
Joined: Oct 03, 2008
Posts: 313
Status: Offline
|
|
Ich postee hier mal ein paar Gedankengänge zur Präzedenzlogik wie in Aufgabe 17 und 18 aus Kurs 1609 beshrieben.
Bei der Präzedenz haben wir es ja mit sogenannten Ereignissen zu tun, die voneinander abhängig sind. Diese Ereignisse haben bestimte Eigenschaften.
Sie sind zum Beispiel Transitiv, d.h. E1 < E2, oder anders ausgedrückt, Ereignis E1 kann nicht vor Ereignis E2 auftreten oder umgekehrt, Ereignis E2 kann nicht vor Ereignis E1 auftreten.
Ein Beispiel: Die Addition von 4 Registern A, B, C, D. Angenommen wir möchten zuerst A und B addieren und dann C und D. In Assembler Notation ausgedrückt:
Add A, B
Add C, D
Wenn nun die Addition von C und D von der Addition A und B abhängig ist, dann gilt folgende Relation: (A+B) < (C+D), d.h. (A+B) muss vor (C+D) ausgeführt werden.
Oder wir möchten zunächst zwei Register addieren und dann ein Register mit dem Wert 2 multiplizieren:
Add A, B
Mul A, 2
In diesem Fall ist (A+B) < (Mul A, 2) denn es muss zuerst die Addition ausgeführt werden und dann die Multiplikation.
Eine weitere Eigenschaft von Ereignissen ist folgende: (E1 < E2) und (E2 < E3) daraus folgt E1 < E3.
Beispiel: Addition von 4 Registern und anschließender Multiplikation:
Add A, B
Add C, D
Mul A, D
Die Multiplikation kann erst ausgeführt werden, nach dem die 4 Register addiert worden sind.
Ferner ist es unmöglich, dass ein Ereignis von sich selbst abhängig ist, d.h. es gibt kein Ereignis für das folgendes gilt: E1 < E1.
Das würde bedeuten, dass zum Beispiel der Befehl Add A, B von sich selbst abhängig wäre, was ja keinen Sinn macht. Eine Ausnahme könnten eventuell for Schleifen sein, in denen eine Laufvariable immer wieder einen neuen Wert bekommt und sich dadurch einer der Werte der Register verändert:
for (int i = 0; i <= 10; i++)
i = i+1;
Ich bin mir nich sicher ob dieses Beispiel Sinn macht, deswegen lass ich da mal gedanklich ein Fragezeichen stehen.
Danben gibt es noch Ereignisse, für die weder E1 < E 2 noch E2 < E1 gilt, d.h. die nicht voneinader abhängig sind. Solche Ereignisse heißen kokurrent - ich hoffe das ist richt so - und man schreibt E1 co E2.
Mir fällt jetzt hierzu kein Beispiel ein, oder, na gut, das ist abe ein besonders schlechtes. In C und Java muss bzw. kann man eine Variable vor ihrer Verwendung initialisieren, d.h. ihr einen Wert zuweisen:
int x; // E1
int y; // E2
x = 1; // E3
y = 2; // E4
Die Ereignisse E1 und E2 und E3 und E4 sind hier jeweils voneinander unabhängig, nicht aber E1 und E3 und E2 und E4. In diesem Fall kann man glaube ich schreiben:
E1 = E2 und E3 = E4, wenn denn das Gleichheitszeichen diese Relation ausdrücken soll. |
|
|
| |
|
|
|
 |
|
aschunk
|
|
|
Post subject: Präzedenzlogik
Posted: Nov 30, 2008 - 09:21 AM
|
|
Joined: Oct 03, 2008
Posts: 313
Status: Offline
|
|
Nachtrag zu dem Beispiel mit der Schleife. In Assembler kann man Schleifen glaube ich so ausdrücken:
:Schleife
loop
Add A, B
Mul A, 2
jmp Schleife
Wenn Schleife eine Marke ist, dann spring jmp Schleife immer wieder zu dieser Marke und führt die Anweisungen aus. Es gibt glaube ich Sprungbefehle, die in Abhängigkeit von Werten, zum Beispiel jumpifzero oder jumpifnozero immer wieder zu dieser Marke springen. Denn ansonsten wäre es ja eine Endlosschleife. |
|
|
| |
|
|
|
|
|
rgerhards
|
|
|
Post subject: Präzedenzlogik
Posted: Nov 30, 2008 - 10:25 AM
|
|
Joined: Sep 25, 2006
Posts: 688
Status: Offline
|
|
Hi Alexander,
schöne Zusammenfassung, ich muss das auch nochmal durchdenken.
Der Gedanke mit der Schleife ist interessant. Der Sprung an sich, so es denn ein unbedingter ist, hat sicherlich keine spezielle Abhängigkeit zu den vorherigen Anweisungen. Die Schleife als Ganzes aber sicherlich sehr wohl. Denn die Anweisungen, da es ja in jedem Durchlauf die gleichen sind, stehen in Verbindung zueinander...
... wobei: diese Sichtweise ist zu simpel. Nehmen wir mal an, in der Schleife wird eine Skalarmultiplikation einer Matrix durchgeführt. Dann ist der Skalar innerhalb der Schleife konstant, lediglich die Elemente der Matrix sind verschieden. Zwischen den Elementen der Matrix bestehen aber keine weiteren Abhängigkeiten. Die eigentlichen Multiplikationen können somit vollständig nebenläufig durchgeführt werden (und werden es im Regelfall auch, z.B. bei der Berechnung der Wettervorhersage).
Die "Schleife" kann hier also vollkommen aufgerollt und durch entsprechend parallele Operationen ausgeführt werden.
Abhängigkeiten ergeben sich natürlich durch die Ressourcen. Wenn z.B. nur eine Gleitkomma-ALU zur Verfügung steht, so kann auch "real" nur eine Operation zu einer Zeit druchgeführt werden. Dennoch kann der Codegenerator die Reihenfolge der einzelnen Multiplikationen nach belieben vertauschen. Das wird er, wenn er gut is, auch in der Tat ausnutzen, indem er dann nämlich Rücksicht auf die Cache-Struktur des Prozessors nimmt und solche Operationen nacheinander ausführt, die zu einer Optimalen Cache-Hit-Rate führen.
Das Ganze ist also durchaus komplex... Die formale Definition mittels der Präzedenzrelation kannte ich bisher noch nicht, sie erscheint mir aber ein gutes Mittel, um die komplexen Zusammenhänge zu beschreiben und zu verstehen. |
|
|
| |
|
|
|
|
|
rgerhards
|
|
|
Post subject: Präzedenzlogik
Posted: Nov 30, 2008 - 10:48 AM
|
|
Joined: Sep 25, 2006
Posts: 688
Status: Offline
|
|
Off-Topic: Falls 'mal jemand Lust verspüren sollte, sich mit wirren Gedanken auseinander zu setzen: ich hätte da noch eine kleine Betrachtung über das Wesen der Zeit (und einige andere Dinge) anzubieten:
http://www.gerhards.net/download/phil.pdf
Das liegt schon 'ne Weile unvollendet bei mir, ich habe es einfach einmal hochgeladen. Vielleicht dient es ja zumindest der Belustigung  |
|
|
| |
|
|
|
|
|
rgerhards
|
|
|
Post subject: Präzedenzenrelation
Posted: Nov 30, 2008 - 11:39 AM
|
|
Joined: Sep 25, 2006
Posts: 688
Status: Offline
|
|
Posting entfernt, bitte statt dessen diese hier verwenden:
http://www.gerhards.net/PNphpBB2-viewtopic-t-136.phtml
(In dem Ursprungsposting war ein nicht zur Veröggentlichung freigegebenes Zitat enthalten). |
Last edited by rgerhards on Jul 02, 2009 - 10:46 AM; edited 9 times in total
|
| |
|
|
|
|
|
aschunk
|
|
|
Post subject: Präzedenzlogik
Posted: Nov 30, 2008 - 01:25 PM
|
|
Joined: Oct 03, 2008
Posts: 313
Status: Offline
|
|
|
|
|
|
|
rgerhards
|
|
|
Post subject: Präzedenzlogik
Posted: Nov 30, 2008 - 05:51 PM
|
|
Joined: Sep 25, 2006
Posts: 688
Status: Offline
|
|
| Ich habe meine Ausarbeitung jetzt ergänzt und empfehle, sie nochmals zu betrachten (und, ja, sie ist deutlich länger ) |
|
|
| |
|
|
|
|
|
Micha
|
|
|
Post subject: Präzedenzlogik
Posted: Dec 01, 2008 - 11:18 PM
|
|
Joined: Nov 27, 2008
Posts: 47
Status: Offline
|
|
Hallo Alex,
du schreibst im Wiki:
Quote:
Wenn E1 (A+B), E2 (C+D) und E3 (A+B)*(C+D) ist, dann häben wir hier folgende Präzedenzrelation: E1 < E2 < E3, denn wir könen erst multiplizieren, wenn wir addiert haben.
Dem stimme ich nicht zu, da E1 < E2 nicht gilt. Richtig wäre wohl so etwas wie (E1 = E2) < E3. Ob das aber korrekt ausgedrückt ist, möchte ich stark bezweifeln.
Michael |
|
|
| |
|
|
|
|
|
Micha
|
|
|
Post subject: Präzedenzlogik
Posted: Dec 01, 2008 - 11:29 PM
|
|
Joined: Nov 27, 2008
Posts: 47
Status: Offline
|
|
Habe gerade gesehen, dass Rainer das schon in der Newsgroup angemerkt hatte.
Michael |
|
|
| |
|
|
|
|
|
|
|
Home Page 
Administration 
Logout 
Web Links 
FAQ
Search
Register
Log in to check your private messages
Log in
Maximize
::