Achtung: Dies ist eine historische Web-Site. Aktuell ist https://rainer.gerhards.net/ (engl) bzw https://www.rainer-gerhards.de/ (deutsch). Alle dynamischen Funktionen, Formulare etc auf dieser Seite sind abgeschaltet.
Datenschutzerklärung Impressum

Astronomy and Space Flight, Astronomie und Raumfahrt und dies und das...

Imperative Programmierung - Präzedenzrelation
rgerhards - 03.12.2008, 16:14 Uhr
Titel: Präzedenzrelation
Ich füge das hier nochmal ein, damit ich leichter darauf verweisen kann. Ich möchte ausdrücklich darauf hinweisen, dass hier Fehler enthalten sein können. So im groben sollte es aber stimmen. Über Kommentare freue ich mich.

Rainer

Lass mich auch noch einmal die Definition der Präzedenzenratlation wiedergeben:

Basis der Präzedenzenrelation ist der uns vertrautet Zeitstrahl. Ohne tiefer in das Wesen der Zeit eindringen zu wollen, sei unterstellt, dass der Zeitstrahl eine Gegenwart, eine Vergangenheit und eine Zukunft aufweist. Dies ist vergleichbar mit dem Strahl der ganzen Zahlen, die Gegenwart entspricht der 0, die Vergangenheit den negativen und die Zukunft den positiven Zahlen in diesem Vergleich. Weiter sei unterstellt, dass das Kausalitätsprinzip in allen Fällen gilt, das Ereignisse also nur in einer bestimmten Reihenfolge auftreten und insbesondere Wirkungen nie vor ihren Ursachen auftreten können.

Weiter sei daran erinnert, dass eine Relation immer eine Menge von geordneten Paaren ist.

Auf dieser Basis können wir nun in die gegebene Definition eintreten (Anmerkungen von mir in Kursivschrift):

Fernuni Hagen, Kurs 1601, EA 1-17 hat folgendes geschrieben::

Ein Ereignis F heisst abhängig von einem anderen Ereignis E, sofern F nicht stattfinden kann, ohne dass sich vorher E ereignet hat (hier wird also auf das Kausalitätsprinzip verwiesen). Wir schreiben in diesem Fall E<\!\!\!\cdot\,F. (Dies entspricht auch der von mir oben genannten Analogie auf dem Zeitstrahl. D.h. das frühere Ereignis steht vor dem späteren. Das Zeichen <\!\!\!\cdot interpretiere ich als ein "temporales kleiner als", d.h das link stehende Ereignis steht auf dem Zeitstrahl "weiter links" als das rechts stehende - damit ist auch dieses Zeichen aus der Analogie der ganzen Zahlen zu erklären.

\begin{aligned} E<\!\!\!\cdot\ &= \text{Ereignis } F \text{ ist abhängig von Ereignis } E \\ &= \text{Ereignis } E \text{ findet stehts vor Ereignis } F \text{ statt} \end{aligned}

Da die Relation <\!\!\!\cdot\, die zeitliche Reihenfolge bestimmter Ereignisse festlegt, spricht man auch von einer Präzedenzrelation. Präzedenzrelationen sind strenge partielle Ordnungen, d.h. sie sind:

transitiv, irreflexsiv und asymmetrisch

Irreflexivität schließt aus, dass es ein Ereignis gibt, welches bereits stattgefunden haben muss, bevor es stattfinden kann (damit wird das Kausalitätsprinzip wieder gesichert).

Zwei verschiedene Ereignisse A und B, für die in einem Prozess keine Reihenfolge festgelegt ist, für die also weder A<\!\!\!\cdot\,B noch B<\!\!\!\cdot\,A gilt, heissen nebenläufig (concurrent), und wir schreiben in diesem Fall:

\begin{displaymath}A\mbox{\em\,co\,}B \end{displaymath}

Nebenläufige Ereignisse eines Prozesses können zeitgleich, überlappend oder in einer beliebigen Reihenfolge stattfinden, da kein ursächlicher Zusammenhang zwischen ihnen besteht. Prozesse ohne Nebenläufigkeit heissen sequentielle Prozesse. Die Präzedenzrelation bildet in diesem Fall (also für sequentielle Prozesse) eine strenge totale Ordnung, das heisst für jedes Paar E,F von Ereignissen gilt genau eine der folgenden drei Beziehungen

\begin{displaymath}E<\!\!\!\cdot\,F\;\mbox{ oder }\;E=F\;\mbox{ oder }\;F<\!\!\!\cdot\,E \end{displaymath}


In einem realen Programm werden sich nebenläufige Befehlssequenzen mit solchen abwechseln, die in Sequenz ausgeführt werden können. Im Regelfall wird es so sein, dass einige Sequenzen nebenläufig ausgeführt werden können, die Ergebnisse der Sequenz aber zu einem bestimmten Zeitpunkt vorliegen müssen, da nun alle Ergebnisse benötigt werden. Hier ist also eine Synchronisation erforderlich (auf "hoher Ebene" ist dies z.B. bei multiplen Threads möglich, hier werden dann auf Semaphoren aufbauende Mechanismen (das ist sehr vage ausgedrückt und nicht 100% korrekt) verwendet [z.B. Condition-Variablen in POSIX Threads]).

Ein Beispiel. Zu berechnen ist (A+B)*(C+D). Dann sind die beiden Operationen A+B sowie C+D nicht voneinander abhängig. Wohl aber kann die Multiplikation der beiden Ergebnisse erst durchgeführt werden, wenn sowohl beide Berechnungen beendet sind, als auch als Eingangswerte für die Multiplikation zur Verfügung stehen.

Bei der (noch) im Kurs verwendeten einfachen Single-Prozessor-Maschine wird dabei zwangsweise eine Sequentiallisierung der Additionen erzwungen, das Problem reduziert sich somit auf die korrekte Verfügbarkeit beider Ergebnisse. Komplexer wird das Szenario allerdings bei einer Maschine, die tatsächlich beide Additionen parallel ausführen kann.

Wie kann ich nun hier die Präzedenzenrelation angeben?

Gegeben ist: (A+B), (C+D) sind nicht voneinander abhängig.
MUL ist aber von (A+B), (C+D) abhängig.
Wäre dies dann eine korrekte Schreibweise?

((A+B) \text{ co } (C+D)) <\!\!\! \cdot \text{ MUL}

Oder muss ich, um dies abbilden zu können, noch eine Art "temporale max-Funktion (max_t(p_1,p_2) \text{ mit } p_1, p_2 \in \text{ Präzendenzenralation}) definieren?


Nun einmal zu einem konkreten Beispiel, nämlich dem der Aufgabenstellung:

Gegeben sei die Befehlssequenz:

\begin{displaymath}((\mbox{$<$A$>$}+\mbox{$<$B$>$})*(\mbox{$<$C$>$}+\mbox{$<$D$>... ...<$A$>$}+\mbox{$<$C$>$}+\mbox{$<$E$>$}))\ \rightarrow\ \mbox{A} \end{displaymath}

Es stehen Zwei-Adress-Befehle zur Verfügung, nicht mehr benutzte Register dürfen überschrieben werden. Das Ergebnis muss in Register A abgelegt werden. Weitere Register dürfen nicht verwendet werden.

Damit muss darauf geachtet werden, wo die Zwischergebnisse abgelegt werden dürfen. Prinzipiell sind A*B, C+D und A+C+E nebenläufig ausführbar. Allerdings dürfen die Register A,C nur in einem Fall von Zwischeergebnissen überschrieben werden, da hier Abhängigkeiten Bestehen. Diese Abhängigkeiten resultieren allerdings nur aus der Forderung, die Zwischenergebnisse in den genannten Registern abzulegen. Könnten sie in anderen Registern abelegt werden (ein Umbennenungsproblem), so könnten die drei Instruktionen vollständig nebenläufig ausgeführt werden. Dies ist aber nicht der Fall. Eine geeignete Reihenfolge ist daher diese:

A1 = ADD B,A ; erste Operation wird in B zwischengespeichert
A2 = ADD D,C ; zweite Operation wird in D zwischengespeichert

A3 = ADD A,C ; dritter Operationsblock, Reihenfolge innerhalb im Prinzip beliebig
A4 = ADD A,E

A5 = MUL A,B ; vierter Operationsblock, Reihenfolge innerhalb im Prinzip beliebig
A6 = MUL A,D

Dadruch, dass die Register B,D hier nur einmal verwendet werden und keine weiteren Abhängigkeiten bestehen, ist die Reihenfolge der ersten beiden Operationsblöcke beliebig. Sie müssen aber vor dem Dritten beendet sein. Anmerkung: diese Abhängigkeit könnte auch entfernt werden, wenn der dritte Operationsblock sein Zwischenergebnis nicht in A ablegen würde. Dann wäre aber später ein (zusätzlicher) Ladebefehl notwendig, um das Gesamtergebnis in das Register A zu transferieren. Die oben gezeigte Befehlssequenz erscheint mir daher sinnvoll. Allerdings lassen sich Datenkonflikte verringern, wenn A5, A6 wie folgt umgestellt werden:

A5 = MUL B,D
A6 = MUL A,B

In diesem Fall hat A4 einen Takt länger Zeit, um das Ergebnis zur Verfügung zu stellen. Ein Pipeline-Stall ist damit nicht mehr unbedingt erforderlich.

Die weitere Analyse baut aber auf der ursprünglichen Sequenz auf.

Zunächst betrachte ich, welche Befehle von A1 "abhängig" sein können. Dabei ist "Abhängigkeit" ein weit gefasster Begriff. Nach DLX Architektur, die keine Befehle umordnen kann, ist z.B. A4 nicht abhängig von A1. Geht man jedoch von einer möglichen Befehlsumordnung aus, so ist in der Tat A4 von A1 abhängig, allerdings nur in der Art und Weise, dass A1 eigentlich davon abhängig ist, dass A4 noch nicht (hinreichend weit) ausgeführt wurde (A4 darf bis zur EX-Phase gelangen, ohne A1 zu beeinträchtigen, wenn A4 vor A1 ausgeführt wird).

Da mir eine solche Definition aber zumindest nicht im Sinne des Kurstextes zur Verfügung steht, muss ich wohl von einer "Abhängigkeit" von A4 von A1 ausgehen, also A1 <\!\!\! \cdot A4 (auch wenn ich eigentlich etwas wie A4 >\!\!\!\!\!\! \cdot \text{ } A1 meine, was IMHO bei hinreichend genauer Betrachtung nicht äquivalent ist).

Aufbauend auf dieser Definition erhalte ich dann die folgende Teilmenge der Präzedenzrelation:

P = {
(A1,A3),
(A1,A4),
(A1,A5),
(A2,A5),
(A3,A4),
(A3,A5),
(A4,A5),
(A5,A6)
}

Es handelt sich nur um eine Teilmenge, weil die Transitivitäten nicht berücksichtigt sind. Durch (A1,A4), (A4,A5) und (A5,A6) sind in der vollständigen Relation auch die Paare (A1,A5) und (A1,A6) sowie (A4,A6) enthalten, oben jedoch nicht aufgeführt.

Hier sei erklärend auch noch einmal eine Aussage der Kursbetreuung 1609 aufgeführt:

[quote=]
Zitat temporär entfernt, da die Aussage in einem nicht-öffentlichen Forum erfolgte und - aufgrund der komplizierten Rechtslage - keine Eindeutige Zustimmung des Autors zur Veröffentlichung erlangt wurde. Ich werde das später nochmals in eigene Worte kleiden. Ich denke aber, der Forumpost ist im Wesentlichen auch ohne das Zitat nutzbar, daher entferne ich übergangsweise nur dieses.
[/quote]

In der oben von mir beschriebene Menge P existieren solchen transitiven Beziehungen, und zwar:

(A1,A4) folgt aus (A1,A3),(A3,A4).
(A1,A5) folgt aus (A1,A3),(A3,A4),(A4,A5)
(A3,A5) folgt aus (A3,A4)(A4,A5)

Diese Tupel können somit entfernt werden. Die kleinste Menge, die die im zu betrachtenden Codefragment zu beachtenden Präzedenzen vollständig angibt ist somit:

P = {
(A1,A3),
(A2,A5),
(A3,A4),
(A4,A5),
(A5,A6)
}

Insbesondere listet sie kein Element mehr auf, das sich unmittelbar aus der Transitivität der anderen angegebenen Elemente ergibt.

Dies passt allerdings nicht zu dem von der Kurs-Aufgabenstellung gewünschten Ergebnis. Dies hat wohl seinen Grund darin, dass die Instruktionen "in der Reihenfolge des Auftretens im Term" angegeben werden sollen (also gänzlich unoptimiert). Eine naheliegende Lösung habe ich bisher übersehen, möchte Sie hier aber als Alternative gleich nochmals vorstellen. Die Codesequenz ist schlechter, da sie erheblich mehr Abhängigkeiten erzeugt:

A1 = ADD B,A
A2 = ADD D,C
A3 = MUL B,D ; B wird als Zwischenspeicher verwendet!
A4 = ADD A,C
A5 = ADD A,E
A6 = MUL A,B

Durch diese Sequenz ist eine frühzeitige Multiplikation möglich. Ein gesonderter Ladebefehl für das Ergebnisregister wird dennoch vermieden.

Die Kern der Präzedenzenrelation für diese Codesequenz ist nun wie folgt:

{
(A1,A3),
(A1,A4),
(A2,A3),
(A3,A6),
(A4,A5),
(A5,A6)
}

Damit habe ich 6 transitivitätsfreie Paare ermittelt. Dies entspricht aber nach wie vor nicht den Vorgaben der Aufgabenstellung. Und obendrein gibt die Aufgabe weiter vor (wie Oliver Burger hinwies), dass zuerst 4 Additionen und dann 2 Multiplikationen erfolgen sollen. Damit ist dieser Ansatz hier natürlich schon mal gar nicht mehr als Lösung geeignet. Als Übungsbeispiel erscheint mir die Ausführung aber natürlich dennoch nützlich.
Alle Zeiten sind GMT + 1 Stunde
PNphpBB2 © 2003-2007