Dieses Dokument beschreibt, wie CompAnn intern zu den Ergebnis-ANNs kommt, bzw. wie diese strukturiert werden; weiters wird auf die Algorithmen von EvAnn eingegangen.
Ein ANN (Artificial Neural Network) ist ein System bestehend aus mehreren Neuronen, die zu einem gegebenen Zeitpunkt jeweils aktiv oder inaktiv sein können — sie stellen gewissermaßen einen “1-Bit-Speicher” dar.
Es werden zwei Typen von ANNs unterschieden, sog. Feed-Forward-ANNs und Recurrent ANNs; ich beschäftige mich ausschließlich mit dem zweiten Typ. Ein solches Netzwerk kann als zellulärer Automat gesehen werden.
Jedes Neuron sendet Signale von bestimmter Stärke an bestimmte andere Neuronen, wenn es aktiv ist. Übersteigt die Signalsumme eines Neurons eine gewisse Schwelle, ist es in der nächsten Runde selbst aktiv, ansonsten nicht; diese Schwelle wird dadurch repräsentiert, dass in jeder Runde ein fester Wert (Bias) zur Summe dazugezählt wird (der auch negativ sein kann, bzw. oft negativ ist).
Die Aktivität eines Neurons kann von der eines anderen “abhängig” gemacht werden, indem man die beiden Neurone mit einem starken Signal verbindet, diese Signalstärke dafür aber vom Bias des abhängigen Neurons abzieht — so kann es nur aktiviert werden, wenn das andere Neuron im Takt zuvor auch aktiv ist, wird aber nicht weiter beeinflusst.
Somit stellt ein ANN mit n Neuronen eine Art “Computer” dar, der über n Bit dynamischen Speicher verfügt, und dessen ROM-Speicher (der das eigentliche “Programm”, das ausgeführt wird, enthält) aus den Verbindungen und Biasen besteht. Der Laufzeitstatus eines bestimmten ANNs ist eindeutig durch die n Bits gegeben, die die Aktivität seiner Neuronen beschreiben.
CompAnn gliedert seine ANNs in eine Reihe von Befehlen, die sequentiell ausgeführt werden. Jedem Befehl ist ein Aktivator-Neuron zugeordnet; der Befehl ist “an der Reihe”, wenn dieses Neuron aktiviert wird. Dieser Aktivator aktiviert seinerseits den Aktivator des Folgebefehls, sodass die Befehle wirklich der Reihe nach ausgeführt werden.
Das allererste Neuron eines ANNs ist der Aktivator des ersten Befehls, und signalisiert den Programmstart. Das allerletzte Neuron wird vom Programm aktiviert, wenn die Arbeit abgeschlossen ist, und signalisiert das Programmende an das Interpreter-Programm.
Input-Parameter werden dem Programm übergeben, indem die ersten k Neuronen (für ein Gesamtvolumen von k Bits) nach dem Programmstart-Aktivator (also die Neuronen 2 bis k+1) auf die Bits der Parameter gesetzt werden, bevor das Programm gestartet wird; dabei werden die einzelnen Input-Parameter nacheinander “eingefüllt”, und die Bits eines jeden Parameters in Little-Endian-Reihenfolge.
Analog dazu sind errechnete Output-Werte bei Programmende in den l Neuronen vor dem Programmende-Neuron (also in den Neuronen n-l bis n-1) zu finden. Auch hier ist die Bit-Reihenfolge Little-Endian, aber die einzelnen Output-Werte sind in umgekehrter Reihenfolge in diesen l Bits hintereinander zu finden (der erste Output-Parameter ist physisch in den letzten Neuronen des Netzwerks angesiedelt).
Für komplexere Interaktionen zwischen ANN und Laufzeitumgebung, als sie mit reiner Parameterübergabe möglich sind, können Callbacks verwendet werden. Dabei handelt es sich sozusagen um “native” Funktionen, die aus dem ANN heraus aufgerufen werden (mit Parametern), von der Laufzeitumgebung implementiert sind und dem ANN Rückgabewerte liefern können.
Ein solches Callback besteht dabei aus einem Aktivatorneuron, gefolgt von Neuronen, die die Rückgabewerte enthalten, und denen, in denen die Parameter übergeben werden; Bit-Reihenfolge ist auch hier Little-Endian, so dass sich ein Parameterformat wie beim Programm als Ganzes ergibt (siehe Parameter), jedoch mit vertauschten Positionen von Input- und Output-Parametern.
Wird nun das Aktivatorneuron vom ANN aktiviert, muss die Laufzeitumgebung asynchron zur ANN-Simulation sofort die Input-Werte einlesen, das Callback ausführen und die Output-Werte setzen.
Ein SmartNeuron ist ein Objekt, das CompAnn intern verwendet, um z. B. “konstante Neurone”, die stets aktiviert oder nicht aktiviert sind, und nicht als Neurone vorhanden sein müssen, sondern in die Biase der verbundenen Neuronen eingerechnet werden können, programmiertechnisch gleich verwenden zu können wie ganz normale Neuronen.
Intern handelt es sich dabei um ein Interface, das einfach mit mehreren abstrakten Methoden Zugriff auf die Fähigkeiten gibt, eine Verbindung mit anderen Neuronen aufzubauen, und sich in ein bestehendes Netzwerk einzufügen.
Außerdem kann ein SmartNeuron “komplexe” Verbindungen herstellen; eine inverse Verbindung ist eine Verbindung, die effektiv dann sendet, wenn das Neuron inaktiv ist. Sie wird durch eine negative Verbindung und einen positiven Bias-Wert erzeugt.
Das RealNeuron ist ein SmartNeuron, das einfach ein “normales” Neuron darstellt — es verbindet sich mit anderen Neuronen, indem es die Verbindung speichert, und es fügt sich ganz einfach in das Netzwerk ein.
Konstante Neurone sind stets entweder aktiv oder inaktiv — daher müssen sie nicht als Neurone real im Netzwerk vorhanden sein, sondern können in die Biase der mit ihnen verbundenen Neuronen eingerechnet werden. Solche Neurone finden Anwendung, wenn z. B. Konstanten in einem Programm vorkommen.
Diese Neurone verbinden sich mit anderen Neuronen, indem sie die Signalstärke zum Bias des Zielneurons addieren, wenn sie aktiv sind. Das Einfügen in ein Netzwerk ist dagegen einfach eine Dummy-Operation, die nichts bewirkt.
Dieser Typ von SmartNeuron dient einfach als “Schlüssel” zu einem oder mehreren anderen Neuronen, zu denen Verbindungen direkt weitergeleitet werden.
ForwardNeuronen finden z. B. bei Goto-Befehlen Anwendung, wo man über sie zwar programmieren kann, als wären sie konkrete Neuronen, sie die Verbindungen aber direkt an den nächsten Aktivator weiterleiten, und dadurch kein Taktzyklus verschwendet wird.
CompAnn wandelt ein in Anne geschriebenes Programm nicht direkt in ein ANN um, sondern geht den Umweg über ein temporäres, internes Zwischenformat, SAM. Dieses Format kann man grob mit der Assembler-Sprache eines Computers vergleichen, die vom Compiler aus einer Hochsprache erzeugt wird, und anschließend in das eigentliche Ausgabeprogramm übersetzt wird. Aber fast noch wirklichkeitsnäher ist es, SAM mit der RTL (Register Transfer Language) zu vergleichen, die von GCC intern aus denselben Gründen verwendet wird, aus denen CompAnn auch SAM verwendet.
Ein Nutzen von SAM ist es, dass man auf diese Weise nicht “komplexe”
Anne-Ausdrücke, wie z. B. (a^b)&3, direkt in ein ANN übersetzen muss,
sondern zuerst diese Berechnung in allgemeiner Weise auf eine Reihe von
Sub-Berechnungen zurückführen kann, die dann anschließend wieder einfacher in
die entsprechenden ANN-Komponenten übersetzt werden können.
Außerdem bietet das SAM-Zwischenergebnis den besten Ausgangspunkt für Compiler-Optimierungen, da das Programm einerseits schon in ein paar wenige, grundlegende Befehle zerlegt vorliegt, aber andererseits noch wirklich als Programm, und nicht als reines ANN.
Variablen, Input-Argumente und Output-Werte werden von SAM und damit auch im erzeugten ANN vollkommen gleichberechtigt behandelt — der einzige Unterschied besteht darin, dass Input-Argumente eben “Variablen” sind, die in den ersten Neuronen eines ANNs platziert sind, während Output-Werte als Variablen in den letzten Neuronen zu finden sind.
Eine Variable mit k Bits wird durch k Neuronen implementiert, deren Aktivitätsstatus je ein Bit speichert. Damit der Speicherinhalt erhalten bleibt, wird jedes Neuron mit sich selbst verbunden — so aktiviert sich ein aktives Neuron in jeder Runde neu, während ein inaktives Neuron immer inaktiv bleibt.
Der Wert einer solchen Variable kann von “außen” geändert werden, indem ein viel stärkeres positives/negatives Signal an das entsprechende Bit gesendet wird, als jenes, mit dem es sich selbst re-aktiviert.
Zuweisungen sind als Befehle davon abhängig, dass ihr Aktivator-Neuron aktiviert wird, um ausgeführt zu werden; da aber nur Neuronen (nicht Verbindungen) von Aktivität/Nichtaktivität beeinflusst werden können, kann der Wert nicht direkt mit den Neuronen der Zielvariable verdrahtet werden — dann gäbe es keine Möglichkeit zu verhindern, dass die Zielvariable auch dann “gestört” wird, wenn die Zuweisung gar nicht an der Befehlsreihe ist!
Um dieses Problem zu lösen, muss jede Zuweisung den zuzuweisenden Wert zuerst in einer temporären Variable speichern, die ausschließlich aus k Neuronen besteht, die nicht mit sich selbst verbunden werden, und die auch nur dann aktiviert werden können, wenn der Aktivator der Zuweisung aktiv ist — ihr Bias wird also auf einen hohen negativen Wert gesetzt, und der Aktivator mit derselben hohen (positiven) Signalstärke mit ihnen verbunden. Dadurch ist sicher gestellt, dass diese Neuronen genau dann den zuzuweisenden Wert enthalten, wenn die Zuweisung auch aktiv ist.
Deshalb kann man diese zwischenspeichernden Neuronen auch direkt mit den Bits der Zielvariable verbinden; dadurch werden die zu setzenden Bits der Zielvariable vom Zwischenspeicher aktiviert. Um die Variable zuvor “auf Null” zu setzen, wird der Zuweisungs-Aktivator negativ mit allen Bits verbunden.
Die eigentliche Zuweisung findet auf diese Weise erst später statt, deshalb muss zur Verzögerung der weiteren Befehlsausführung noch ein “Zwischenaktivator” eingeschaltet werden — der Aktivator gibt die Aktivität nicht direkt an den Aktivator des Folgebefehls weiter, sondern zuerst an ein anderes Neuron, das erst eine Runde später den Folgebefehl aktiviert; dann nämlich, wenn die Zuweisung auch wirklich schon statt gefunden hat.
Je nach Art der Zuweisung bzw. Berechnung ist es unterschiedlich, wie der Zwischenspeicher überhaupt gesetzt wird.
Direkte Zuweisungen (also der Form a=b, ohne Berechnung) sind auf dem
oben beschriebenen allgemeinen Prinzip aufbauend sehr leicht zu implementieren;
die Bits der zuzuweisenden Variablen können direkt mit den entsprechenden Bits
der temporären Variable verknüpft werden, es werden weder ein zusätzlicher Takt
noch zusätzliche Neuronen benötigt.
Für das binäre “Und” wird die temporäre Variable der Zuweisung so mit den Bits der Ausgangsvariablen verbunden, dass ihre Bits nur dann gesetzt sind, wenn beide Bits der Ausgangsvariablen gesetzt sind.
Dafür werden diese beiden Bits mit dem Ziel-Bit verbunden, dieses erhält aber zusätzlich einen negativen Bias-Wert, der quasi eine dieser Verbindungen wieder “neutralisiert”.
Beim binären “Oder” wird ein Bit der Ziel-Variable gesetzt, wenn mindestens eines der entsprechenden Eingangs-Bits gesetzt ist. Dies wird realisiert, indem einfach beide Ausgangs-Bits mit dem Ziel-Bit verbunden werden.
Das binäre exklusive “Oder” `a^b' wird gebildet als `(a|b)&(~(a&b))' — also “a oder b, aber nicht a und b”.
Um das zu realiseren, wird sowohl ein weiterer temporärer Speicher (für den Wert von `a&b') als auch ein drittes Aktivator-Neuron benötigt. Dieser Speicher wird zu `a&b' verdrahtet, siehe SAM Und; außerdem ist er vom Aktivator abhängig, und bekommt daher einen zusätzlichen negativen Bias und eine Verbindung mit diesem.
Die Ziel-Bits werden als `a|b' verbunden, siehe SAM Oder. Zusätzlich dazu werden jedoch auch die Bits des neuen Zwischenspeichers negativ dazuverbunden, sodass die Ziel-Bits auch nur dann gesetzt werden, wenn nicht beide Ausgangs-Bits aktiv sind.
Das binäre “Nicht” wird implementiert, indem die Bits der Ausgangsvariable invers mit den zugehörigen Ziel-Bits verbunden werden.
Inkrementieren könnte man auch simpel als Spezialfall der Addition ansehen und deren Code verwenden (siehe SAM Plus), aber inkrementieren läuft in konstanter Zeit, unabhängig von der Bitanzahl der Operanden. Auch handelt es sich dabei sicherlich um eine Operation, die häufig ausgeführt wird.
Das angewendete Verfahren ist dieses: Suche die niederwertigste Null in den Bits der Zahl und negiere die Bits von dieser Position (inklusive) abwärts. Das führt dazu, dass unterhalb dieser Null nur Nullen stehen (da ja vorher nur Einsen dort waren), diese Null selbst zu einer Eins wird, und darüber alles gleich bleibt.
Im ersten Schritt muss dazu diese unterste Null gefunden werden, dazu wird ein temporäres Array von n Neuronen eingesetzt (n ist die Bitanzahl des Operanden), in dem nur das Neuron, das an der Position der untersten Null liegt, aktiviert wird. Dies geschieht, indem jedes Eingangsbit invers mit dem entsprechenden temporären Bit und negativ invers mit allen höherwertigen verbunden wird.
In der zweiten Iteration wird jedes Eingangsbit mit dem zugehörigen Ausgangsbit verbunden, um den Wert zu kopieren. Die temporären Bits werden ebenfalls mit den zugehörigen Ausgangsbits verbunden, was dafür sorgt, dass die unterste Null zu einer Eins wird, und negativ mit allen niederwertigeren Ausgangsbits, um dort alle Einser zu löschen.
Um auch den Fall abzudecken, dass der Operand ausschließlich aus Einsen besteht, müssen alle Zielbits davon abhängig gemacht werden, dass irgendwo im temporären Speicher überhaupt eine Eins vorkommt. Sie erhalten einen negativen Bias und werden mit allen temporären Bits verbunden.
CompAnn verwendet Two's complement Darstellung für negative Zahlen; die Konvertierung in dieses Format entspricht einer bitweisen Negierung und anschließenden Inkrementierung. Der genaue Algorithmus ist: Suche die unterste Eins; kopiere sie und alle Nullen darunter und invertiere alle höherwertigeren Bits.
Dieses Verfahren ist sehr offensichtlich dem der Inkrementierung ähnlich (siehe SAM Inc), auch die Implementierung ist es und wird daher hier nur kurz erläutert.
In einem temporären Array wird die unterste Eins gesucht, wobei dazu invers zur Inkrementierung verbunden wird; die Eingangsbits werden invers mit den Zielbits verbunden, dann muss noch die Eins kopiert werden und alle Bits darunter müssen gelöscht werden. Dazu wird der temporäre Speicher genau so wie bei der Inkrementierung mit den Zielbits verbunden.
Die Addition funktioniert ähnlich zum üblicherweise zum händischen Berechnen von Summen verwendeten Verfahren. Schritt für Schritt werden die Ergebnisbits von “hinten nach vorne” ermittelt.
Jedes dieser Bits ist abhängig von den entsprechenden Bits der beiden Summanden und — das niederwertigste Bit ausgenommen — dem Übertragsbit. Das Ziel ist, dass das neue Übertragsbit bei mindestens zwei Einsen in diesen drei Bits aktiviert wird und das Ergebnisbit bei entweder genau einem oder genau drei.
Das neue Übertragsbit ist leicht zu erzielen, dafür muss es einfach mit allen drei Eingangsbits verbunden werden und einen negativen Bias erhalten (ähnlich wie bei der binären “Und”-Operation, siehe SAM Und).
Eine Iteration später ist auch das Ergebnisbit zu ermitteln, indem es ebenfalls mit allen drei Eingangsbits verbunden wird, jedoch zusätzlich negativ und mit doppelter Wertigkeit mit dem gerade ermittelten Übertragsbit. Auf diese Weise wird es im Fall von genau zwei nicht aktiviert.
Wenn alles so eingestellt ist, stellt sich nach n+1 Iterationen (wobei n die Bitanzahl im Ergebnis ist) ein Gleichgewicht im Netzwerk ein und das Ergebnis ist “fertig”. Deshalb ist es nicht nötig, diese ganzen Operationen von irgendwelchen Aktivatorneuronen abhängig zu machen; es muss nur mit einer Neuronenkette lange genug gewartet werden.
Ich denke, es ist möglich, unabhängig von der Bitanzahl der Summanden immer mit nur drei Übertragsneuronen auszukommen, die reihum wiederverwendet werden. Dies ist aber bis jetzt noch nicht implementiert.
Für den “Kleiner als”-Vergleich wird sozusagen das Vorzeichen der Differenz der beiden Operanden (in der richtigen Reihenfolge) betrachtet. Ein spezielles Neuron wird so verbunden, dass es genau dann aktiviert wird, wenn diese Differenz positiv ist — also der Vergleich wahr.
Dies geschieht, indem jedes Bit mit der Stärke seiner eigenen Wertigkeit der Operanden mit diesem Neuron verbunden wird; und zwar die Bits des ersten Operanden negativ, und die des zweiten positiv.
Diese Operation wird gleich zur “Kleiner als”-Operation ausgeführt, siehe SAM Kleiner. Allerdings erhält das Ziel-Neuron zusätzlich den Bias 1, so dass es bei völliger Gleichheit ebenso aktiv ist.
Der “normale” Vergleich von zwei Zahlen wird mit Hilfe von zwei Neuronen wie denen der “Kleiner als”-Operation, siehe SAM Kleiner, ausgeführt, von denen jedoch eines mit umgekehrtem Vorzeichen verdrahtet wird.
Sein Gesamtergebnis ergibt sich dann aus “weder Neuron 1 noch Neuron 2”, also quasi “nicht a<b und nicht b<a”.
Die “Ungleich”-Operation verläuft fast gleich wie der normale Vergleich (siehe SAM Gleich), jedoch wird das Ergebnis dann aktiviert, wenn eines der beiden Kleiner-Neuronen aktiv ist.
Unbedingte (einfache) Sprungbefehle in SAM werden dadurch realisiert, dass ihr Aktivatorneuron seine Aktivität einfach ans Sprungziel weitergibt — wie man aber leicht merken kann, ist das derselbe Vorgang, wie er bei der Aktivitätsweitergabe sowieso immer vorkommt.
Daher werden Sprünge intern mit ForwardNeuronen (siehe ForwardNeuron) implementiert, und benötigen im Endeffekt kein einziges Neuron und keinen einzigen Taktzyklus!
Bedingte Sprünge (Sprung wird nur ausgeführt, wenn eine Bedingung wahr ist)
bilden die Grundlage für Kontrollstrukturen einer Hochsprache wie if-,
while- oder for-Befehle. In Computer-Assembler-Sprachen gibt es
meistens eine ganze Reihe von entsprechenden Anweisungen, wie “Jump on equal”,
“Jump on not equal”, “Jump on zero”, “Jump on not zero”...
Eine solche Anweisung benötigt neben dem Aktivator-Neuron zwei weitere Neurone, eines für “If” (wenn die Bedingung wahr ist), und eines für “Else” (wenn die Bedingung nicht wahr ist) — die Bedingung selbst besteht im Wert eines Bits, also in der Aktivität eines bestimmten anderen Neurons.
If- und Else-Neuron werden vom Aktivator abhängig gemacht, und zusätzlich werden sie so verbunden, dass abhängig vom Bedingungs-Bit entweder das If- oder das Else-Bit aktiviert wird. Dies geschieht, indem das Bedingungs-Bit direkt mit dem If-Bit und invers mit dem Else-Bit verbunden wird.
Anschließend braucht man nur mehr das If-Bit mit dem Aktivator des Sprungziels zu verbinden und das Else-Bit mit dem des Folgebefehls (der ausgeführt wird, wenn der Sprung nicht zu Stande kommt).
Threads werden in SAM mit asynchronen Sprüngen erzeugt, die die Ausführungslinie gleichzeitig an ihren Folgebefehl wie an ein definiertes “Sprungziel” weitergeben.
Dies lässt sich auf Neuronenebene sehr einfach realisieren, das Aktivatorneuron des Sprungs muss nur mit beiden folgenden Aktivatorneuronen verbunden werden; dieses Neuron lässt sich als ForwardNeuron (siehe ForwardNeuron) realisieren, so dass die Thread-Abspaltung keinen Perfomance-Verlust darstellt. Deshalb können auch mehrere Abspaltungen in Folge passieren, um so ebenso ohne Verlust mehr als einen neuen Thread zu erzeugen — ein Aufspaltungsbefehl für mehrere asynchrone Sprungziele in einem ist somit nicht nötig.
Zum Beenden von Threads wird die Ausführunslinie schlicht und einfach “abgebrochen”, indem das Neuron, das für die Aktivitätsweitergabe verantwortlich ist, mit keinem folgenden Aktivatorneuron verbunden wird.
Diese einfache Methode, um Threads wieder zu beenden, ist zwar billiger aber auch nicht ganz so nützlich oder sicher wie das Wiedervereinigen von Threads, siehe SAM Thread Date!
Der sicherste Weg, um Threads wieder “los zu werden”, ist die Wiedervereinigung (Date), denn hierbei wird nicht einfach ein Thread beendet und ein anderer läuft weiter, sondern es wird sichergestellt, dass beide (bzw. alle) Threads am Ende des Multi-Threading-Blocks angekommen sind, bevor der Code danach ausgeführt wird — dies ist dann nötig, wenn nach dem Thread-Block eine Anweisung kommt, die erst ausgeführt werden darf, wenn alle Threads zu Ende sind, und es aber zur Kompilierzeit nicht absehbar ist, welcher Thread am längsten laufen wird.
Ein Date wird im Netzwerk implementiert, indem für jeden Thread, auf den gewartet werden muss, ein Neuron angelegt wird, das mit sich selbst verbunden ist; dieses wird als Folge-Aktivatorneuron für die jeweiligen Code-Blöcke verwendet. Und erst wenn alle diese Neuronen aktiv sind, sind alle Theads beendet und es kann mit einer einzigen Ausführungslinie weiter gemacht werden — dazu wird ein weiteres Neuron, das von allen diesen Aktivatorneuronen abhängig ist, verwendet, um die Aktivität an den Folgebefehl weiterzuleiten.
Man sieht jedoch, dass diese zusätzliche Flexibilität und Sicherheit einige Neuronen und zwei Laufzeititerationen kostet; wie schon oben erwähnt ist somit ein einfaches Beenden von Threads (siehe SAM Thread Die) billiger und zu empfehlen, wo es möglich und ausreichend ist.
Um den erzeugten Code und dessen Kosten in Richtung Neuronenbedarf und benötigter Laufzeit besser einschätzen zu können, stelle ich hier in einer Übersicht die SAM-Sprachelemente ihren Performance-Kosten gegenüber; die Details der Implementierung, wie diese Kosten zu Stande kommen, sind in den entsprechenden anderen Abschnitten nachzulesen.
| Operation | Neuronen | Iterationen | Kommentar
|
|---|---|---|---|
| Programmoverhead | 2 | 1 | Argumente zählen als Variablen dazu.
|
| Variable | n | - | Für n Bits Speicher.
|
| Konstante | 0 | - | In die Verbindungen eingerechnet.
|
| Sprung | 0 | 0 |
|
| Bedingter Sprung | 3 | 1 |
|
| Thread starten | 0 | 0 | Analog zum Sprung.
|
| Thread beenden | 0 | 0 |
|
| Thread daten | n+1 | 2 | Bei n Threads.
|
| Zuweisung | n+1 | 2 | Bei n Zielbits; hinzu kommt noch die Berechnung selbst.
|
Für Zuweisungen kommen noch die Kosten der Berechnung dazu, wobei d die Bitanzahl des Ergebnisses (und somit die generell verwendete Bitanzahl) angibt:
| Operation | Neuronen | Iterationen | Kommentar
|
|---|---|---|---|
a&b | 0 | 0 |
|
a|b | 0 | 0 |
|
a^b | d+1 | 1 |
|
~a | 0 | 0 |
|
a<b | 0 | 0 | Generell konstant, da d auch 1 sein muss.
|
a<=b | 0 | 0 | Siehe oben.
|
a==b | 2 | 1 | Siehe oben.
|
a!=b | 2 | 1 | Siehe oben.
|
a# | d+1 | 1 |
|
-a | d+1 | 1 | Analog zur Inkrementierung.
|
a+b | 3*d+1 | d+1 |
|
Gerade durch die Art und Weise (durch Einsatz von temporären Variablen), wie der Anne-Compiler SAM-Code erzeugt, enthält dieser nicht selten viele Variablen, die aber nur über einen sehr beschränkten Bereich in Verwendung sind. Da diese Variablen zwar Neuronen zum Datenspeicher benötigen, diese aber fast die ganze Programmlaufzeit ungenützt sind, bietet sich die Technik des Bitsharing an.
Dabei wird nicht jeder Variable für jedes Bit einfach ein Neuron zugeteilt, das ihr voll und ganz “gehört”, sondern alle Speicher-Neuronen werden zu einem Pool zusammengefasst, aus diesem sie dann den Variablen zugeteilt werden — ein Neuron kann aber auch mehreren Variabeln gleichzeitig gehören; dafür muss der Optimierer nur sicherstellen, dass sich die Verwendungsbereiche der beiden Variablen nicht überschneiden.
Um diesen Verwendungsbereich zu ermitteln, kann man folgenden Grund-Algorithmus verwenden:
Auf diese Weise wird der Verwendungsbereich auf den gesamten Code ausgedehnt, der zwischen dem ersten und letzten Vorkommen ausgeführt werden könnte; allerdings ist dies sicherlich nicht die bestmögliche Technik, da auf diese Weise sehr große Bereiche ermittelt werden (was für die Optimierung natürlich schlecht ist).
Doch da der meiste SAM-Code als Output des Anne-Compilers entsteht, für den Variablen einen bestimmten Geltungsbereich (von der Deklaration bis zum Ende des Blockes, in dem sie deklariert wurden) haben, über dessen Grenzen hinaus sie unbestimmte Werte haben dürfen, so kann man den maximal möglichen Verwendungsbereich auf eben diesen Geltunsbereich einschränken — und somit jeden Sprungbefehl, der den Verwendungsbereich darüberhinaus erweitern würde, einfach ignorieren!
Diese Erkenntnis bringt mitunter enorme Vorteile, da z. B. Variablen, die innerhalb von großen Schleifenblöcken deklariert werden, nicht den ganzen Block als Verwendungsbereich haben müssen (und somit evt. ihre Bits mit anderen Variablen desselben Blocks teilen können); denn sie müssen ihre Werte nicht von einem Schleifendurchlauf zum nächsten beibehalten.
Die Grundidee hinter Compactor ist es, den Compiler möglichst viele
Codezeilen zu Multi-Threading-Blöcken zusammenziehen zu lassen. Denn durch die
außergewöhnliche Fähigkeit von Anne, echtes Multithreading anbieten zu
können, sind nicht unbeachtliche Laufzeiteinsparungen möglich; werden jedoch
manuell vor allem sehr viele sehr kleine parallel-Blöcke geschrieben,
wird dadurch die Lesbarkeit des Codes sehr in Mitleidenschaft gezogen.
Deshalb versucht der Compiler mit Hilfe von Compactor diese Parallelisierung (die vor allem bei längeren Blöcken mehr oder weniger von einander abhängiger Zuweisungen (also Berechnungen) funktioniert) automatisch zu erledigen, damit der Code einfacher lesbar und wartbar bleibt, weil auch die Aufgabe, die Richtigkeit der parallelen Ausführung zu prüfen, vom Programmierer abfällt.
Da Sprungbefehle, bedingt oder unbedingt, synchron oder asynchron, “die Arbeit von Compactor erschweren” bzw. unmöglich machen, wird der SAM-Code zuerst in eine Art Baumstruktur überführt, den CompactTree, auf den der Compactor angewendet werden kann. Das Kennzeichen dieser Struktur ist es, dass Geschwisterknoten dieses Baums keine Sprungbefehle untereinander haben — also, sofern es der “Datenfluss” zulässt, gefahrlos parallel ausgeführt werden können. Der Compactor-Algorithmus kann anschließend rekursiv auf diesen Baum angewendet werden.
Ein kritischer Befehl ist ein Sprung oder das Ziel eines Sprungs, ein unkritischer jeder andere (typischerweise eine Zuweisung).
Der CompactTree kann dabei zwei Arten von Knoten haben, gebundene und ungebundene; jeder Knoten besitzt eine Folge von anderen Knoten und/oder SAM-Actions als Kinder. Ungebundene Knoten haben ausschließlich unkritische Befehle als Kinder und dürfen diese somit umgruppieren (also “Compacted” werden), gebundene Knoten dagegen beinhalten auch kritischen Befehle als Kinder, sodass sie den Compact-Algorithmus nur an ungebundene Kinderknoten weitergeben können.
Ein einfacher Algorithmus, einen solchen Baum zu bauen, fügt einfach den gesamten SAM-Code in den Wurzelknoten ein und markiert diesen als gebunden. Mehrere unkritische Befehle in Folge werden anschließend zu einem ungebundenen Block zusammengefasst, der parallelisiert werden kann. Rekursiv sind sicherlich weit ausgefeiltere Algorithmen denkbar, doch auch dieser einfache sollte für den Anfang sehr gute Ergebnisse liefern, und schon die meisten Fälle, in denen der Compactor Verbesserungen bringt, abdecken können.
Dieser Algorithmus läuft in Zeit linear zur Code-“Zeilen”-Anzahl.
Ist der CompactTree erstellt, wird dieser rekursiv verarbeitet, indem jeder Block zuerst seine Kinder diesen Algorithmus anwenden lässt; anschließend versucht er selbst, seine Kind-Blöcke zu parallelisieren, wenn er ungebunden (dies also überhaupt erlaubt) ist.
Um die Legitimität von Code-Parallelisierungen zu prüfen, beruht Compactor auf der Annahme, dass zwei Code-Blöcke zusammengezogen werden dürfen, wenn
Der Datenfluss zwischen den Kindblöcken kann als Graph (bzw. Netzwerk) dargestellt werden, indem die vorkommenden Variablen sowie die Blöcke durch Knoten ersetzt werden, und Zugriffe auf die Variablen als entsprechend gerichtete Kanten zwischen dem Variablen- und Blockknoten eingefügt werden.
Variablen, die nur gelesen werden (also Variablenknoten, die Quellknoten sind), dürfen entfernt werden; besteht der Graph anschließend aus mehreren, unverbundenen Komponenten, dürfen die Blockknoten dieser Komponenten gefahrlos parallel ausgeführt werden.
Die Schwierigkeit besteht nun darin, möglichst erfolgreich Teilmengen der Kindblöcke zu bestimmen, die parallelisiert werden — denn für ein gutes Ergebnis kann es nötig sein, einzelne Code-Zeilen aus dem Block zu nehmen (die zwei Komponenten des Netzwerks verbinden würden). Ebenso kann es von Vorteil sein, die Reihenfolge der Blöcke zu ändern; ein Block darf verschoben werden, wenn er von all jenen Zeilen, “über die hinweg” er bewegt wird, unabhängig ist.
Da ich vermute, dass die hier vorgestellten Techniken denen, die in herkömmlichen Compilern bereits vorhanden sind, um beispielsweise C-Programme in Assembler zu übersetzten, sehr ähneln, beschreibe ich in diesem Kapitel nur sehr kurz, wie die “Hochsprache” Anne in die Netzwerk-Assembler-Sprache SAM transformiert wird.
Komplexe Ausdrücke, die aus mehreren Operatoren, Operanden und Teilausdrücken bestehen, müssen zuerst in eine Folge von einzelnen SAM-Zuweisungen (siehe SAM Zuweisungen allgemein) “übersetzt” (aufgelöst) werden.
Dies geschieht durch Umwandlung “von innen nach außen” in eine Folge von Zuweisungen temporärer Variablen, die später als die Werte der Teilausdrücke in den äußeren Verknüpfungen verwendet werden. Die Vielzahl an kurzlebigen Variablen, die durch diese Technik entsteht, ist ein Hauptgrund für die Sinnhaftigkeit der BitSharing-Optimierung (siehe Bitsharing).
Für Kontrollstrukturen setzt der Compiler “oft und gerne” Sprungbefehle und dazugehörige Labels in Form von NOP-Befehlen ein. Da diese Komponenten weder mit Speicher- noch Laufzeitkosten verbunden sind, ergibt das eine preiswerte einfache Lösung für einige Probleme.
If-Then-Else-Bedingungen bauen auf bedingte Sprünge (siehe SAM If Goto) auf — am Beginn des bedingten Blocks steht ein solcher Sprung, der diesen bei Nicht-erfüllt-Sein der Bedingung einfach überspringt.
Ist noch ein Else-Block vorhanden, springt dieser Befehl stattdessen an den Beginn des Else-Blockes, während am Ende des If-Blocks ein unbedingter Sprung steht, der den Else-Teil überspringt, wenn die Bedingung erfüllt ist.
Mit While- bzw. Do-While-Schleifen lassen sich alle Aufgaben prozeduraler Programmierung formulieren, und auch diese Strukturen bauen auf bedingte Sprünge in SAM, SAM If Goto, auf.
Am Beginn einer While-Schleife steht ein Sprung, der “aus” der Schleife an ihr Ende springt, sobald die Bedingung nicht mehr erfüllt ist. Um aus diesem bedingten Code-Block eine Schleife zu machen, wird außerdem noch ein unbedingter Sprung am Ende des Schleifenkörpers benötigt, der wieder zum Bedingungscheck springt.
Do-While-Schleifen können dagegen noch einfacher implementiert werden, hierzu ist schlicht und einfach am Code-Ende ein bedingter Sprung zurück an den Anfang einzufügen.
Die Umsetzung der asynchronen und parallelen Ausführung in SAM ist mehr oder weniger einfach zu verstehen:
Asynchrone Statements erzeugen einen eigenen Thread, der am Ende mit die
beendet wird; für parallele Ausführung wird ein Date verwendet (siehe
SAM Thread Date), das auf alle Ausführungsäste wartet.
Dieses Kapitel beschreibt die Algorithmen, die von EvAnn zur Neuroevolution verwendet werden. Diese bauen auf denen des Projekts ANNEvolve auf.
Neuroevolution ist eine Technik, bei der es darum geht, ANNs “automatisch” verbessern zu lassen, also ohne menschliches Zutun. Wie der Name schon vermuten lässt, wurde sie sowohl von der Evolution als auch von genetischen Vorgängen inspiriert.
Das Grundprinzip funktioniert dabei so: Es wird eine Population von ANNs gebildet, entweder rein zufällig oder von einer bzw. mehreren vorgegebenen, semi-funktionalen Problemlösungen ausgehend.
Anschließend wird diese Population ausgewertet (die Fitness jedes einzelnen ANNs ermittelt), und je nach Fitness werden die schwächeren Individuen entfernt. Die so entstandenen freien Plätze werden durch neue ANNs, die auf den besseren Individuen basieren (ihre “Nachkommen”), gefüllt, und dieser Vorgang beginnt für die “nächste Generation” von Vorne.
Wird diese simulierte Evolution lange genug ausgeführt, stellt sich eine generelle Progression in der Fitness der Individuen ein.
Für die im Folgenden beschriebenen Mutations- und Evolutionsalgorithmen spielt der Zufall eine große Rolle; damit verbunden müssen auch gewisse Wahrscheinlichkeiten ermittelt werden, dass ein bestimmtes Ereignis eintritt.
Die dafür verwendeten Formeln, sowie die darin verwendeten Parameter, sind willkürlich gewählt, beeinflussen jedoch sicherlich nicht unbedeutend sowohl die Performance der Simulation als auch den Erfolg des Vorgangs.
Parameter sind dabei:
Für manche Wahrscheinlichkeiten ist auch die Fitness des ANNs (Fitness) im Vergleich zur Fitnessverteilung der Population entscheidend; dort gibt es die Variablen MinFitness, MaxFitness, AvgFitness für Populationsminimum, -maximum und -mittelwert, sowie Range als MaxFitness-MinFitness, LowRange als AvgFitness-MinFitness und HighRange als MaxFitness-AvgFitness.
Die Wahrscheinlichkeiten für bestimmte Ereignisse und Vorgänge:
Obwohl Netzwerke in der Ausführung aus einer Objektstruktur bestehen, ist für genetische Veränderungen die Chromosomenform besser geeignet.
Dabei wird das Netzwerk in eine reine Folge von Zahlen serialisiert; die Neuronen werden dabei aneinander gereiht, und jedes Neuron besteht aus seinem Bias gefolgt von den Verbindungswerten zu jedem Neuron des Netzwerkes (bzw. 0, wenn keine Verbindung besteht). Das ergibt bei einem Netzwerk mit n Neuronen somit 1+n Zahlen je Neuron.
Bei einer Mutation wird ein zufälliger Wert des Chromosoms verändert; dies wird dabei solange wiederholt, wie die MutationProbability “eintritt”, also gar nicht bis unbestimmt oft.
Ist der Wert ungleich 0 (also eine Verbindung vorhanden) und es tritt die DisconnectionProbability ein, wird er auf 0 gesetzt (die Verbindung getrennt); analog dazu wird ein 0-Wert auf einen Zufallswert gesetzt, wenn die ConnectionProbability eintritt.
Ansonsten wird der Wert mit einem gewählten Mutationsfaktor multipliziert.
Ein Crossing-Over verändert zwei Chromosomen, indem beide “mit einander in Verbindung gebracht werden”. Dies kann an einem Punkt oder an zwei Punkten geschehen. Dies ist jedoch nur möglich, wenn beide Chromosomen dieselbe Länge haben (also das Netzwerk dieselbe Neuronenanzahl).
Bei einem Ein-Punkt-Crossing-Over werden die Teile beider Chromosomen ab einer zufälligen Position miteinander vertauscht. Findet das Crossing-Over an zwei Punkten statt, wird der jeweilige Teil zwischen zwei Zufallspositionen vertauscht.
Um “gestorbene” Individuen zu ersetzen, werden stets paarweise Eltern ausgewählt, die ebenfalls paarweise Nachkommen zur Welt bringen. Dabei werden beide Eltern kopiert, die Kindchromosomen je mutiert, und anschließend kann ein Crossing-Over stattfinden.
GNU Free Documentation License
Version 1.2, November 2002
Copyright (C) 2000,2001,2002 Free Software Foundation, Inc.
51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
Everyone is permitted to copy and distribute verbatim copies
of this license document, but changing it is not allowed.
0. PREAMBLE
The purpose of this License is to make a manual, textbook, or other
functional and useful document "free" in the sense of freedom: to
assure everyone the effective freedom to copy and redistribute it,
with or without modifying it, either commercially or noncommercially.
Secondarily, this License preserves for the author and publisher a way
to get credit for their work, while not being considered responsible
for modifications made by others.
This License is a kind of "copyleft", which means that derivative
works of the document must themselves be free in the same sense. It
complements the GNU General Public License, which is a copyleft
license designed for free software.
We have designed this License in order to use it for manuals for free
software, because free software needs free documentation: a free
program should come with manuals providing the same freedoms that the
software does. But this License is not limited to software manuals;
it can be used for any textual work, regardless of subject matter or
whether it is published as a printed book. We recommend this License
principally for works whose purpose is instruction or reference.
1. APPLICABILITY AND DEFINITIONS
This License applies to any manual or other work, in any medium, that
contains a notice placed by the copyright holder saying it can be
distributed under the terms of this License. Such a notice grants a
world-wide, royalty-free license, unlimited in duration, to use that
work under the conditions stated herein. The "Document", below,
refers to any such manual or work. Any member of the public is a
licensee, and is addressed as "you". You accept the license if you
copy, modify or distribute the work in a way requiring permission
under copyright law.
A "Modified Version" of the Document means any work containing the
Document or a portion of it, either copied verbatim, or with
modifications and/or translated into another language.
A "Secondary Section" is a named appendix or a front-matter section of
the Document that deals exclusively with the relationship of the
publishers or authors of the Document to the Document's overall subject
(or to related matters) and contains nothing that could fall directly
within that overall subject. (Thus, if the Document is in part a
textbook of mathematics, a Secondary Section may not explain any
mathematics.) The relationship could be a matter of historical
connection with the subject or with related matters, or of legal,
commercial, philosophical, ethical or political position regarding
them.
The "Invariant Sections" are certain Secondary Sections whose titles
are designated, as being those of Invariant Sections, in the notice
that says that the Document is released under this License. If a
section does not fit the above definition of Secondary then it is not
allowed to be designated as Invariant. The Document may contain zero
Invariant Sections. If the Document does not identify any Invariant
Sections then there are none.
The "Cover Texts" are certain short passages of text that are listed,
as Front-Cover Texts or Back-Cover Texts, in the notice that says that
the Document is released under this License. A Front-Cover Text may
be at most 5 words, and a Back-Cover Text may be at most 25 words.
A "Transparent" copy of the Document means a machine-readable copy,
represented in a format whose specification is available to the
general public, that is suitable for revising the document
straightforwardly with generic text editors or (for images composed of
pixels) generic paint programs or (for drawings) some widely available
drawing editor, and that is suitable for input to text formatters or
for automatic translation to a variety of formats suitable for input
to text formatters. A copy made in an otherwise Transparent file
format whose markup, or absence of markup, has been arranged to thwart
or discourage subsequent modification by readers is not Transparent.
An image format is not Transparent if used for any substantial amount
of text. A copy that is not "Transparent" is called "Opaque".
Examples of suitable formats for Transparent copies include plain
ASCII without markup, Texinfo input format, LaTeX input format, SGML
or XML using a publicly available DTD, and standard-conforming simple
HTML, PostScript or PDF designed for human modification. Examples of
transparent image formats include PNG, XCF and JPG. Opaque formats
include proprietary formats that can be read and edited only by
proprietary word processors, SGML or XML for which the DTD and/or
processing tools are not generally available, and the
machine-generated HTML, PostScript or PDF produced by some word
processors for output purposes only.
The "Title Page" means, for a printed book, the title page itself,
plus such following pages as are needed to hold, legibly, the material
this License requires to appear in the title page. For works in
formats which do not have any title page as such, "Title Page" means
the text near the most prominent appearance of the work's title,
preceding the beginning of the body of the text.
A section "Entitled XYZ" means a named subunit of the Document whose
title either is precisely XYZ or contains XYZ in parentheses following
text that translates XYZ in another language. (Here XYZ stands for a
specific section name mentioned below, such as "Acknowledgements",
"Dedications", "Endorsements", or "History".) To "Preserve the Title"
of such a section when you modify the Document means that it remains a
section "Entitled XYZ" according to this definition.
The Document may include Warranty Disclaimers next to the notice which
states that this License applies to the Document. These Warranty
Disclaimers are considered to be included by reference in this
License, but only as regards disclaiming warranties: any other
implication that these Warranty Disclaimers may have is void and has
no effect on the meaning of this License.
2. VERBATIM COPYING
You may copy and distribute the Document in any medium, either
commercially or noncommercially, provided that this License, the
copyright notices, and the license notice saying this License applies
to the Document are reproduced in all copies, and that you add no other
conditions whatsoever to those of this License. You may not use
technical measures to obstruct or control the reading or further
copying of the copies you make or distribute. However, you may accept
compensation in exchange for copies. If you distribute a large enough
number of copies you must also follow the conditions in section 3.
You may also lend copies, under the same conditions stated above, and
you may publicly display copies.
3. COPYING IN QUANTITY
If you publish printed copies (or copies in media that commonly have
printed covers) of the Document, numbering more than 100, and the
Document's license notice requires Cover Texts, you must enclose the
copies in covers that carry, clearly and legibly, all these Cover
Texts: Front-Cover Texts on the front cover, and Back-Cover Texts on
the back cover. Both covers must also clearly and legibly identify
you as the publisher of these copies. The front cover must present
the full title with all words of the title equally prominent and
visible. You may add other material on the covers in addition.
Copying with changes limited to the covers, as long as they preserve
the title of the Document and satisfy these conditions, can be treated
as verbatim copying in other respects.
If the required texts for either cover are too voluminous to fit
legibly, you should put the first ones listed (as many as fit
reasonably) on the actual cover, and continue the rest onto adjacent
pages.
If you publish or distribute Opaque copies of the Document numbering
more than 100, you must either include a machine-readable Transparent
copy along with each Opaque copy, or state in or with each Opaque copy
a computer-network location from which the general network-using
public has access to download using public-standard network protocols
a complete Transparent copy of the Document, free of added material.
If you use the latter option, you must take reasonably prudent steps,
when you begin distribution of Opaque copies in quantity, to ensure
that this Transparent copy will remain thus accessible at the stated
location until at least one year after the last time you distribute an
Opaque copy (directly or through your agents or retailers) of that
edition to the public.
It is requested, but not required, that you contact the authors of the
Document well before redistributing any large number of copies, to give
them a chance to provide you with an updated version of the Document.
4. MODIFICATIONS
You may copy and distribute a Modified Version of the Document under
the conditions of sections 2 and 3 above, provided that you release
the Modified Version under precisely this License, with the Modified
Version filling the role of the Document, thus licensing distribution
and modification of the Modified Version to whoever possesses a copy
of it. In addition, you must do these things in the Modified Version:
A. Use in the Title Page (and on the covers, if any) a title distinct
from that of the Document, and from those of previous versions
(which should, if there were any, be listed in the History section
of the Document). You may use the same title as a previous version
if the original publisher of that version gives permission.
B. List on the Title Page, as authors, one or more persons or entities
responsible for authorship of the modifications in the Modified
Version, together with at least five of the principal authors of the
Document (all of its principal authors, if it has fewer than five),
unless they release you from this requirement.
C. State on the Title page the name of the publisher of the
Modified Version, as the publisher.
D. Preserve all the copyright notices of the Document.
E. Add an appropriate copyright notice for your modifications
adjacent to the other copyright notices.
F. Include, immediately after the copyright notices, a license notice
giving the public permission to use the Modified Version under the
terms of this License, in the form shown in the Addendum below.
G. Preserve in that license notice the full lists of Invariant Sections
and required Cover Texts given in the Document's license notice.
H. Include an unaltered copy of this License.
I. Preserve the section Entitled "History", Preserve its Title, and add
to it an item stating at least the title, year, new authors, and
publisher of the Modified Version as given on the Title Page. If
there is no section Entitled "History" in the Document, create one
stating the title, year, authors, and publisher of the Document as
given on its Title Page, then add an item describing the Modified
Version as stated in the previous sentence.
J. Preserve the network location, if any, given in the Document for
public access to a Transparent copy of the Document, and likewise
the network locations given in the Document for previous versions
it was based on. These may be placed in the "History" section.
You may omit a network location for a work that was published at
least four years before the Document itself, or if the original
publisher of the version it refers to gives permission.
K. For any section Entitled "Acknowledgements" or "Dedications",
Preserve the Title of the section, and preserve in the section all
the substance and tone of each of the contributor acknowledgements
and/or dedications given therein.
L. Preserve all the Invariant Sections of the Document,
unaltered in their text and in their titles. Section numbers
or the equivalent are not considered part of the section titles.
M. Delete any section Entitled "Endorsements". Such a section
may not be included in the Modified Version.
N. Do not retitle any existing section to be Entitled "Endorsements"
or to conflict in title with any Invariant Section.
O. Preserve any Warranty Disclaimers.
If the Modified Version includes new front-matter sections or
appendices that qualify as Secondary Sections and contain no material
copied from the Document, you may at your option designate some or all
of these sections as invariant. To do this, add their titles to the
list of Invariant Sections in the Modified Version's license notice.
These titles must be distinct from any other section titles.
You may add a section Entitled "Endorsements", provided it contains
nothing but endorsements of your Modified Version by various
parties--for example, statements of peer review or that the text has
been approved by an organization as the authoritative definition of a
standard.
You may add a passage of up to five words as a Front-Cover Text, and a
passage of up to 25 words as a Back-Cover Text, to the end of the list
of Cover Texts in the Modified Version. Only one passage of
Front-Cover Text and one of Back-Cover Text may be added by (or
through arrangements made by) any one entity. If the Document already
includes a cover text for the same cover, previously added by you or
by arrangement made by the same entity you are acting on behalf of,
you may not add another; but you may replace the old one, on explicit
permission from the previous publisher that added the old one.
The author(s) and publisher(s) of the Document do not by this License
give permission to use their names for publicity for or to assert or
imply endorsement of any Modified Version.
5. COMBINING DOCUMENTS
You may combine the Document with other documents released under this
License, under the terms defined in section 4 above for modified
versions, provided that you include in the combination all of the
Invariant Sections of all of the original documents, unmodified, and
list them all as Invariant Sections of your combined work in its
license notice, and that you preserve all their Warranty Disclaimers.
The combined work need only contain one copy of this License, and
multiple identical Invariant Sections may be replaced with a single
copy. If there are multiple Invariant Sections with the same name but
different contents, make the title of each such section unique by
adding at the end of it, in parentheses, the name of the original
author or publisher of that section if known, or else a unique number.
Make the same adjustment to the section titles in the list of
Invariant Sections in the license notice of the combined work.
In the combination, you must combine any sections Entitled "History"
in the various original documents, forming one section Entitled
"History"; likewise combine any sections Entitled "Acknowledgements",
and any sections Entitled "Dedications". You must delete all sections
Entitled "Endorsements".
6. COLLECTIONS OF DOCUMENTS
You may make a collection consisting of the Document and other documents
released under this License, and replace the individual copies of this
License in the various documents with a single copy that is included in
the collection, provided that you follow the rules of this License for
verbatim copying of each of the documents in all other respects.
You may extract a single document from such a collection, and distribute
it individually under this License, provided you insert a copy of this
License into the extracted document, and follow this License in all
other respects regarding verbatim copying of that document.
7. AGGREGATION WITH INDEPENDENT WORKS
A compilation of the Document or its derivatives with other separate
and independent documents or works, in or on a volume of a storage or
distribution medium, is called an "aggregate" if the copyright
resulting from the compilation is not used to limit the legal rights
of the compilation's users beyond what the individual works permit.
When the Document is included in an aggregate, this License does not
apply to the other works in the aggregate which are not themselves
derivative works of the Document.
If the Cover Text requirement of section 3 is applicable to these
copies of the Document, then if the Document is less than one half of
the entire aggregate, the Document's Cover Texts may be placed on
covers that bracket the Document within the aggregate, or the
electronic equivalent of covers if the Document is in electronic form.
Otherwise they must appear on printed covers that bracket the whole
aggregate.
8. TRANSLATION
Translation is considered a kind of modification, so you may
distribute translations of the Document under the terms of section 4.
Replacing Invariant Sections with translations requires special
permission from their copyright holders, but you may include
translations of some or all Invariant Sections in addition to the
original versions of these Invariant Sections. You may include a
translation of this License, and all the license notices in the
Document, and any Warranty Disclaimers, provided that you also include
the original English version of this License and the original versions
of those notices and disclaimers. In case of a disagreement between
the translation and the original version of this License or a notice
or disclaimer, the original version will prevail.
If a section in the Document is Entitled "Acknowledgements",
"Dedications", or "History", the requirement (section 4) to Preserve
its Title (section 1) will typically require changing the actual
title.
9. TERMINATION
You may not copy, modify, sublicense, or distribute the Document except
as expressly provided for under this License. Any other attempt to
copy, modify, sublicense or distribute the Document is void, and will
automatically terminate your rights under this License. However,
parties who have received copies, or rights, from you under this
License will not have their licenses terminated so long as such
parties remain in full compliance.
10. FUTURE REVISIONS OF THIS LICENSE
The Free Software Foundation may publish new, revised versions
of the GNU Free Documentation License from time to time. Such new
versions will be similar in spirit to the present version, but may
differ in detail to address new problems or concerns. See
http://www.gnu.org/copyleft/.
Each version of the License is given a distinguishing version number.
If the Document specifies that a particular numbered version of this
License "or any later version" applies to it, you have the option of
following the terms and conditions either of that specified version or
of any later version that has been published (not as a draft) by the
Free Software Foundation. If the Document does not specify a version
number of this License, you may choose any version ever published (not
as a draft) by the Free Software Foundation.
ADDENDUM: How to use this License for your documents
To use this License in a document you have written, include a copy of
the License in the document and put the following copyright and
license notices just after the title page:
Copyright (c) YEAR YOUR NAME.
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.2
or any later version published by the Free Software Foundation;
with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
A copy of the license is included in the section entitled "GNU
Free Documentation License".
If you have Invariant Sections, Front-Cover Texts and Back-Cover Texts,
replace the "with...Texts." line with this:
with the Invariant Sections being LIST THEIR TITLES, with the
Front-Cover Texts being LIST, and with the Back-Cover Texts being LIST.
If you have Invariant Sections without Cover Texts, or some other
combination of the three, merge those two alternatives to suit the
situation.
If your document contains nontrivial examples of program code, we
recommend releasing these examples in parallel under your choice of
free software license, such as the GNU General Public License,
to permit their use in free software.