Home

Design und Implementierung eines Frameworks für

Contents

1. nicht gegeben Das bedeutet dass insbesondere Typen aus numerischen Bibliotheken nicht als Basistyp verwendet werden k nnen Damit der Entwickler trotzdem mit beliebigen numerischen Bibliotheken arbeiten kann kennt Lethe das Konzept der Arbeitstypen Das ist ein beliebiger Typ der von einem Modul eingesetzt wird Zu einem Arbeitstyp muss ein Basistyp existieren der ihn inhaltlich aufnehmen kann Definiert der Entwickler wie ein Objekt des einen Typs in ein Objekt des anderen Typs und umgekehrt zu konvertieren ist kann der Stream den Basistyp und das Modul den Arbeitstyp verwenden Um das zu verdeutlichen sei angenommen ein Modul muss komplexe Zahlen verar beiten und der Entwickler m chte daf r die GSL vgl Abschnitt 2 6 verwenden Das bedeutet dass das Modul die komplexen Zahlen als Objekte des Types gsl_complex lesen und schreiben m chte Der Basistyp des ein und des ausgehenden Streams sei Complex der die beiden Flie kommazahlen real und imag enth lt Um die Konvertie rung zu erm glichen muss der Entwickler in der Basistyp Datei von Complex folgendes definieren Complex const gsl_complex amp c real GSL_REAL c imag GSL_IMAG c operator gsl_complex const return gsl_complex_rect real imag Die erste Funktion ist der Konstruktor der die beiden Variablen real und imag mit den entsprechenden Werten aus der bergebenen gsl_complex Zahl initialisiert Dazu verwendet er die beiden GSL Macros GSL_R
2. April 2006 Message Passing Interface http www mpi forum org April 2006 GNU Octave http www octave org April 2006 PAYNE W H Fortran Tausworthe pseudorandom number generator Communi cations of the ACM 13 1 S 57 57 Januar 1970 Ptolemy http ptolemy eecs berkeley edu April 2006 Parallel Virtual Machine http www csm ornl gov pvm April 2006 Python http www python org April 2006 Scilab http www scilab org April 2006 STL fit An STL Error Message Decryptor for C http www bdsoft com tools stlfilt html April 2006 STROUSTRUP BJARNE Die C Programmiersprache Addison Wesley 1 Auf lage 2000 LITERATURVERZEICHNIS 36 37 38 39 40 41 STROUSTRUP BJARNE Design and Evolution of C Addison Wesley 2004 TANENBAUM ANDREW S A Tutorial on Algol 68 ACM Comput Surv Seiten 155 190 1976 TANENBAUM ANDREW S Moderne Betriebssysteme Carl Hanser Verlag M n chen 2 Auflage 1995 THOMAS BEUTER PETER DADAM Prinzipien der Replikationskontrolle in ver teilten Systemen Ulmer Informatik Berichte 95 11 University of Ulm November 1995 WEINBERG JOSHUA Centralized Logging with syslog Sys Admin The Journal for UNIX Systems Administrators 7 10 S 27 30 34 Oktober 1998 WIST STEPHANIE Entwurf und Implementierung eines verteilten Systems mit Be nutzerschnittstelle zur Erstellung Verteilung und Verwaltung von Simulationen in der Kanalcodierung
3. Falls alle Leser eines Streams beendet haben ist es manchmal n tig dass der Schreiber ganz normal weiterarbeiten kann vgl Abschnitt 3 1 4 Deshalb kennt die WriteVector Klasse einen Modus in dem sie auf jeden Fall einen tempor ren Puffer zum Beschreiben anlegt und diesen am Ende einfach verwirft 4 3 2 Die Adapter Klasse Lethe generiert f r jedes Modul eine passende Klasse die die Anbindung an die Streams realisiert Diese Klassen hei en Adapter und sind im Namensraum des jeweiligen Modul definiert Abschnitt 4 4 erkl rt die Details F r jeden Port eines Moduls existiert in der Adapter Klasse eine Funktion mit dem Namen des Ports Der Aufruf einer solchen Funktion l st je nach Typ des Ports eine Lese oder Schreiboperation auf dem angeschlossenen Stream aus Der R ckgabetyp einer solchen Funktion tr gt auch den Namen des Ports Beides wird in der Adapter Klasse zum Komfort des Entwicklers entsprechend definiert Jede Port Funktion besitzt einen Parameter der die Anzahl der zu lesenden bzw zu schreibenden Einheiten angibt Das zur ckgelieferte Vektor Objekt bietet dann den Zugriff auf die angegeben Anzahl von Daten an Jede Port Funktion berpr ft mittels einer Assertion ob die angegeben Blockgr e des Ports tats chlich eingehalten wird Dadurch ist es m glich auf entsprechende Fehler des Entwicklers definiert zu reagieren Wie Abschnitt 4 2 2 erkl rt ist die Blockgr e die maximale Anzahl der Daten auf die ein Modu
4. GNU Portable Threads Bibliothek Sie stand in der Diskus sion fiir das Multitasking in Lethe eingesetzt zu werden vgl 2 3 In Abschnitt A 1 ermittelt eine Messung die Laufzeitkosten die durch den Kontextwechsel zwischen zwei Threads entstehen Abschnitt A 2 nennt anschlie end eine M glichkeit die Anzahl der Kontextwechsel gegen ber der aktuellen PTH Implementierung zu halbieren A 1 Zeitmessung der GNU PTH Die folgende Zeitmessung zu den Kosten von Userland Threads wurde im Rahmen die ser Arbeit durchgeftihrt Das Ergebnis war ausschlaggebend ftir die Entscheidung die GNU PTH nicht zu verwenden Die beiden folgenden Programme messen wieviel Zeit f r 1 Milliarde Kontextwechsel ben tigt wird Das erste Programm verwendet dazu die PTH Threads Das zweite Programm verwendet statt dessen einen Verteiler und Be handlungsfunktionen A 1 1 Verwendung der GNU PTH swap c include lt ucontext h gt include lt stdio h gt include lt stdlib h gt ucontext_t uctx 3 define STACKSIZE 64 1024 void funci void arg int i int count int arg for i 0 i lt count i swapcontext amp uctx 0 amp uctx 1 77 Anhang A GNU PTH void func2 void arg while 1 swapcontext amp uctx 1 amp uctx 0 typedef void handler_t void handler_t handler 2 int main int argc char argv 1 int i if arge 2 printf usage s count n argv 0 return 1
5. Alle Zust nde eines Moduls die in keiner Bibliothek enthalten sind sollten st ndig von der _state Variablen gespeichert werden Dann kann der Entwickler einfach die generierte Implementierung dieser Funktion verwenden die diese Variable zur ck gibt Zeile 8 Im Fall des Gausskanals ist der Zustand allerdings im Zufallsgenerator Objekt enthal ten Die vom Entwickler hinzugef gten Zeilen lesen diesen Zustand aus Zeilen 2 3 und speichern ihn in der Zustandsvariablen des Moduls Zeilen 4 7 welche anschlie end zur ckgegeben wird Zeile 8 Die Variable state des Modulzustandes wurde vom Entwickler als Byte Array spe zifiziert Der dazugeh rige C Typ hei t std vector lt unsigned char gt Dieser Typ 4 Eine typische C Implementierung w rde die Standardbibliothek vgl 35 Teil IIT zum Kopieren der Container verwenden Damit zum Verst ndnis des Beispiels wenig C Kenntnisse n tig sind werden die Daten auf klassische Weise kopiert 52 4 4 Module definiert die Funktionen clear und push_back die in den Zeilen 4 und 6 verwendet wer den Die erste Funktion entleert den Vektor und die zweite Funktion h ngt ein Element hinten an Da die von der GSL angebotenen M glichkeiten den Zustand des Zufallsgenerators zu lesen und zu schreiben leider nicht plattformunabh ngig sind vgl 23 Kapitel 17 5 und 17 8 sollte diese Implementierung nicht in heterogenen Netzwerken eingesetzt werden Das ist ein Beispiel f r die
6. ber denen mit der Optimierung Allerdings f llt die Differenz zwischen ihnen mit der steigenden Blockgr e was nicht erwartet wurde Eine m gliche Begr ndung f r dieses Verhalten ist dass dieses Programm auf Grund der Iterationen eine h here Lokalit t des Codes und der Daten besitzt so dass die CPU Caches besser genutzt werden k nnen 5 6 Erh hung der Datenmenge Bei den bisherigen Messungen blieb der Laufzeitgewinn durch die Optimierung sehr gering Da aufgrund dieser Optimierung die Modul Klassen Templates sein m ssen vgl Abschnitt 4 4 und sie somit negative Auswirkungen auf die Entwickler API hatte w re es in Anbetracht dieser Messergebnisse vielleicht besser gewesen sie nicht einzuf hren Es ist allerdings m glich dass die bisher verwendete Datenmenge von 10 Millionen bertragenen Zahlen zu gering ist als dass sich der Effekt der Optimierung bei den Messungen herauskristallisieren kann Deshalb wird in einer abschlie enden Messreihe die Datenmenge erh ht und die Laufzeit jeweils mit und ohne Optimierung gemessen Es ist in beiden F llen ein lineares Wachstum zu erwarten Von Interesse wird sein wie gro die jeweiligen Steigungen sind Die Eigenschaften der Ports sind in beiden F llen die aus Tabelle 5 9 F r die Mes sung wurde die hunderfache Blockgr e gew hlt da sich dadurch wie in Abschnitt 5 5 erl utert der Aufwand f r die Konvertierungen deutlicher zeigt Die Kanten besitzten f r den Fall mit Optimie
7. den der Universit t Ulm f r ihren Hilfe bei dieser Diplomarbeit danken Diese sind die Gutachter Prof Dr Ing Martin Bossert und Prof Dr Ing Franz J Hauck und meine Betreuer Dipl Ing Axel Hof und Dipl Inform Steffen Schober Diese Diplomarbeit wurde von einigen Diskussionen mit Aussenstehenden begleitet was f r viele Entscheidungen ausschlaggebend oder hilfreich war Die wesentlichen Per sonen waren Volker Birk Andreas Pretzsch Michael Feiri und die Kommilitonen aus dem Linux Pool Ich bin diesen Leuten f r ihre Zeit und ihre Gedanken dankbar Desweiteren danke ich allen Korrekturlesern f r ihre Arbeit Zuerst ist hier mein Bru der Andreas Bernauer zu nennen der durch fr hzeitige und kritische Korrekturen den Aufbau dieser Arbeit erheblich beinflusst hat Andere Korrekturleser waren Liesa Keizer Markus Schaber und Ulrich Dangel Besonders danken m chte ich Anne Keizer und Nico Brinker f r die abschlie ende Korrektur von Rechtschreibfehlern am Osterwochenende F r die Entwicklung und die Implementierung der in dieser Arbeit vorgestellten Soft ware wurde sehr viel freie Software von Dritten eingesetzt Deshalb m chte ich mich an dieser Stelle bei den Entwicklern und Maintainern f r ihre jeweilige Arbeit bedanken Schlie lich geht noch ein besonderer Dank an Liesa Keizer die mich vorallem gegen Ende hin trotz zahlreicher Entbehrungen st ndig unterst tzt hat Inhaltsverzeichnis Inhaltsverzeichnis 1 Einf hrung 1 1
8. implizit inaktiv Wenn ein Port einer Kante inaktiv ist kann ein anderer Port derselben Kante durchaus aktiv sein Falls keiner der verbundenen Knoten die Kante verwendet ist sie damit implizit inaktiv Eine inaktive Kante beh lt ihre enthaltenen Daten einfach bis sie wieder aktiv wird oder die Simulation zu Ende ist Versucht ein Knoten auf einen inaktiven Port zuzugreifen bricht die Laufzeitumge bung die Simulation ab und informiert den Benutzer Dieser muss anschlie end unter suchen warum sich der Knoten anders verh lt als von ihm erwartet 22 3 1 Die Simulation Im Laufe einer Simulation werden alle Phasen nacheinander ausgef hrt F r das Ende einer Phase gelten die in Abschnitt 3 1 4 diskutierten Regeln Vor dem Beginn der n ch sten Phase nimmt die Laufzeitumgebung alle Knoten wieder in den Graphen auf und gibt dem Scheduler eine neue benutzerdefinierte Menge von Beobachtern und Proto kollierern Anschlie end aktiviert oder deaktiviert die Laufzeitumgebung die Ports und startet den Scheduler Die Simulation ist schlie lich zu Ende wenn die letzte Phase zu Ende ist Es gibt mehrere M glichkeiten festzulegen welche Daten einer Kante ein aktiver Leser zu Beginn einer Phase sieht Die einfachste davon ist dass die Kante f r ihn leer ist Falls es f r den Leser keine Rolle spielt was in der vorhergehenden Phase geschehen ist ist es wichtig dass diese M glichkeit existiert Deshalb kann der Benutzer f r jeden eingehe
9. int count atoi argv 1 for 1 0 i lt 3 i 4 getcontext amp uctx i handler 0 funci handler 1 func2 for i 0 i lt 2 i uctx il uc_stack ss_sp malloc STACKSIZE uctx i uc_stack ss_size sizeof STACKSIZE makecontext amp uctx i void void handler i 1 void amp count uctx 0 uc_link amp uctx 2 uctx 1 uc_link NULL swapcontext amp uctx 2 amp uctx 0 return 0 A 1 2 Verwendung eines Verteilers disptacher c include lt stdio h gt 78 A 1 Zeitmessung der GNU PTH inc int int A 1 Compiler Compileroptionen System CPU A 1 time real user sys time real user lude lt stdlib h gt funci return 0 func2 return 0 main int argc char argv int i if arge 2 printf usage s count n argv 0 return 1 int count atoi argv 1 for i 0 i lt count i funci func2 3 Umgebung gcc 4 0 2 O0 keine Optimierung Debian GNU Linux sarge 4 Ergebnisse swap 1000000000 12m30 041s 7m27 952s 4m32 666s dispatcher 1000000000 Om8 170s 0m8 167s AMD Athlon tm 64 Processor 3200 79 Anhang A GNU PTH sys Om0 002s A 2 Halbieren der Anzahl der Kontextwechsel Wenn bei der GNU PTH ein Thread mittels yield abgeben m chte so wird zuerst in den Thread des Schedulers zurtick gewechselt Dort wird entschieden welcher Thread nun an die Reihe kommen soll um dann
10. 2 1 erl utert und wie im Falle des obigen WriteVectors deutlich wird kann zwischen dem Schreibaufruf und dem Zeitpunkt der tats chlichen Aktualisierung der Daten im Stream beliebig viel Zeit vergehen Es kann deshalb durch implizite Aufrufen dazu kommen dass andere Module auf denselben Stream zugreifen und somit vermeintlich geschriebene aber noch nicht aktualisierte Daten lesen Auch kann es passieren dass andere Module Daten berschreiben die der Leser noch gar nicht gelesen hat Um die Konsistenz der Streams zu sichern d rfen die Lese und Schreibzeiger des Ringpuffers erst erh ht werden wenn mit Sicherheit keine weiteren Schreib oder Lesezugriffe mehr gemacht werden Durch die Verwendung der Vektor Objekte ist dieser Zeitpunkt allerdings genau defi niert Wenn das Objekt zerst rt wird k nnen anschlie end keine Zugriffe mehr gemacht werden Deshalb ist der Destruktor der Vector Klassen genau der richtige Ort um die Lese und Schreibzeiger zu aktualisieren Um sicherzustellen dass keine Kopien der Vektor Objekte mehr existieren f hren die Vektor Objekte eine Referenzz hlung durch Alternativ m sste das Kopieren von Vektor Objekten verboten werden was f r einen Entwickler eine st rende Einschr nkung sein kann Die verz gerte Aktualisierung der Schreib und Lesezeiger bewirkt dass die Module auf Speicherbereichen des Puffers arbeiten ohne dass diese w hrendessen als benutzt markiert sind Allerdings stellt das kein Problem
11. Abschnitte bieten jeweils eine kurze Einfiihrung in die Themen die fiir die Diskussionen um Lethe relevant sind 2 1 Simulationsprogramme Ein weitverbreitetes und sehr beliebtes Simulationsprogramm ist Matlab 24 Dabei ist es im eigentlichen Sinn kein Simulationsprogramm sondern eine allgemeine Plattform f r numerische Berechnungen Gr nde f r die Beliebtheit und die weite Verbreitung sind sicherlich die m chtige Matlab Programmiersprache und die sehr umfangreichen Bibliotheken Damit ist es m glich einfach und in kurzer Entwicklungszeit komplexe Berechnungen durchzuf hren Mit etwas Programmieraufwand lassen sich diese Berech nungen schlie lich zu einer Simulation verkn pfen Ein gro es Problem das sich dem Einsatz von Matlab in den Weg stellt ist der hohe Preis f r eine Lizenz Je nach Lizenztyp kostet das Basispaket bis zu 1900 US Dollar Dazu kommen weitere Kosten f r Zusatzpakete die zwischen 400 und 5000 liegen Stand 10 April 2006 F r den der sich diese Ausgaben sparen m chte besteht die M glichkeit auf eine freie Alternative wie Scilab 33 oder mit eingeschr nktem Funktionsumfang auch GNU Octave 28 zur ckzugreifen Die Unterst tzung f r verteiltes und paralleles Rechnen muss bei Matlab mit Hil fe von Zusatzpaketen nachger stet werden Die meisten dieser Pakete verwenden eine Implementierung des Message Passing Interface MPI 27 oder die Parallel Vir tual Machine PVM 81 Beides bede
12. Aufteilung und Gliederung 1 2 Die Anforderungen 22 2 2 on nn nn 2 Grundlagen und Stand der Technik 2 1 Simulationsprogramme non nn 2 2 Simulationsalgorithmen o 22 on on nn 2 3 Multitasking es sa su aa aa Sn ns ea nn 2 4 Hypergraphen aoaaa 25 CH ee ee re er eR ee Bi Ge er ee 2 6 Numerische Bibliotheken 2222 2 CE non nn 3 Systementwurf 3 1 Die s mul ationl 4 eca peek ou a ee re Be ee rei 3 1 1 Das Fallbeispiel 2 2 2 oo Eon nn 3 1 2 Das Modell 2 Co oo none 3 1 3 Das Scheduling 2 22 2 oo rn nn 3 1 4 Das Ende einer Simulation 22 22 m onen 3 1 5 Verteilung ae a eee Aga nen ee ee 3 1 6 Feedback Kanten 2 2 2 Cm mm n nn 3 1 7 Phasen p 2 5 au pee KR ER ee 3 1 8 Mehrere Schreiber 2 0 0 a 3 1 9 Zwischenzustande 2 Common 3 1 10 Der Lebenszyklus eines Knotens 05 3 1 11 Die Simulationsbeschreibung 4 3 2 Das verteilte System 2 22 2 on on nn 3 2 1 Manager 4 su 20 0 eS oR a bee sa sn ne 3 2 2 Simulationsobjekte 2 2 22 2m Emm nn 3 2 3 Der Generator 2 2 2 2m mn 3 2 4 Source oervice 2 gs sssaaa ee BS d 2o lt P TOXIES lt a 4 20a ua eee a be ee ve al Te pe ke ee ce 3 2 6 Der Breeze Server 222 Comm Vil 13 13 14 14 16 18 20 21 22 24 25 26 27 28 28 28 31 31 32 33 VII INHALTSVERZEICHNIS 4 Implementierung 4 1 Die Wahl der Programmiersprache 4 2 Streams 4 3 4 4 4 5 5 M
13. Entwicklers Dar berhinaus gibt es noch eine Hilfsfunktion f r die user_trigger Funktion Sie setzt den caller Parameter an Hand einer internen Kennung die von der Laufzeitum gebung geliefert wird 4 5 Das Scheduling Wie die Abschnitte 4 2 und 4 4 erkl ren ist die Laufzeitumgebung in zwei Schichten aufgeteilt Die obere Schicht ist dabei verantworlich f r das Scheduling Dazu muss der Simulationsgraph aufgebaut werden damit sich die Streamobjekte und die Modulobjek te gegenseitig kennen Abschnitt 4 5 1 erkl rt welche Probleme sich dabei ergeben und wie diese gel st werden In der Diskussion der unteren Schicht blieb in Abschnitt 4 3 2 die Frage offen woher die Ports die Streamobjekte kennen Die Antwort auf diese Frage ergibt sich aus den Erl uterungen von Abschnitt 4 5 1 Es existieren zwei Typen von Interaktionen zwischen den Schichten Der erste ist die Delegation von Schedulingentscheidungen von der unteren Schicht an die obere Schicht Dort werden ggf implizite Aufrufe vorgenommen und berpr ft ob eine der Bedingun gen f r die Regeln des impliziten Beendens vgl Abschnitt 3 1 4 erf llt ist Je nachdem wird die untere Schicht angewiesen mit einer entsprechenden Ausnahme zu reagieren 54 4 5 Das Scheduling ae Abbildung 4 1 Der Hypergraph des Fallbeispieles mit Kennungen vgl Abschnitt 4 3 2 oder den Datentransport vorzunehmen Der zweite Typ von In teraktionen sind Ausk nfte die die obere Schicht
14. Operator tiberladen 11 Phase 14 22 Port 14 22 35 Protokollierer 14 19 Proxy 32 92 publish 34 87 Puffertyp 41 Runde 14 20 Scheduler 16 Servant 32 Simulationsbeschreibung 13 27 Simulationsobjekt 29 station rer Algorithmus 18 Stream 35 36 Tausworthe 51 Template 11 Templates Stream 36 Vererbung 11 Vorausschau 45 Zwischenzustand 25 Abbildungsverzeichnis 2 1 3 1 3 2 3 3 3 4 3 9 3 6 4 1 5 1 5 2 9 3 5 4 5 9 5 6 Abbildung eines gerichteten Hypergraphen auf einen gerichteten Graphen 10 Ein Simulationsgraph 22 22 Con non nn 15 Der Hypergraph des Fallbeispieles 2 2 2 2 n nn nennen 15 Der Hypergraph eines ARQ Verfahrens 2 22 2 22m 21 Initialisierung einer Feedback Kante 2 2 2 2 nn nenn 22 Interaktion eines Knotens mit der Laufzeitumgebung 26 Zustandsautomat eines Simulationsobjektes 2 2 22 2 2 29 Der Hypergraph des Fallbeispieles mit Kennungen 55 Die Simulation f r die Messungen 2 2 2 Emm nn 59 Der Verwaltungsaufwand in Abh ngigkeit zur Blockgr e 64 Der Verwaltungsaufwand in Abh ngigkeit zur Blockgr e gr ere Skala 64 Vergleich mit und ohne Optimierung 2 2 2 nn nn nn 65 Vergleich mit und ohne Optimierung gr ere Skala 66 Erh hung der Datenmenge Vergleich mit und ohne Optimierung 67 93 Literaturverzeichnis 10 11 12 13 14 1
15. Ortes an dem ein Fehler auftritt vom Ort an dem der Fehler behandelt wird Kapitel 14 berladene Operatoren Ein wichtiger Teil der Gleichstellung von benutzerdefinierten und eingebauten Typen Durch die Verwendung von g ngigen Operatoren ist es m glich intuitive Schnittstellen zu definieren Kapitel 11 Namensr ume Erm glichen eine hierarchische Definition von Bezeichnern Dadurch las sen sich Namenskonflikte zwischen verschiedenen Teilen der Software vermeiden Ein qualifizierter Bezeichner gibt durch den Bereichsoperator an in welchem Namensraum er definiert ist Beginnt er mit dem Bereichsoperator so ist die Adres sierung absolut zur Wurzel der Hierarchie zu verstehen Kapitel 8 Neben den Vorteilen hat C aber auch viele Nachteile von C geerbt Beispiele hierf r sind die komplexe Syntax L cken in der Sprachdefinition variable Parameterlisten der Pr prozessor und das Linker Modell Au erdem fehlen der Sprache wichtige Konzepte die in modernen Programmiersprachen zum Alltag geh ren Dazu geh rt ein Import Konzept das dynamische Nachladen von Code eine umfangreiche Standardbibliothek Unterst tzung f r nebenl ufiges Programmieren und umstritten aber dennoch zu nennen eine automatische Garbage Collection G ngige Compiler unterst tzen das Sprachmittel export 35 Kapitel 13 7 nicht Dadurch ist man gezwungen die Definition und die Deklaration von Template Klassen und Funktionen in einer Datei
16. Sein Wert h ngt von den Arbeitstypen der Ports ab Falls alle Ports denselben Arbeitstyp haben ist der Puffertyp gleich dem Arbeitstyp was der oben beschriebenen Optimierung entspricht Haben die Ports aber unterschiedliche Arbeitstypen bleibt nichts anderes brig als den Puffertyp auf den Basistyp zu setzen und beim Lesen und Schreiben zu konvertie ren Es w re noch denkbar einen der Arbeitstypen als Puffertyp zu verwenden um so nur beim Lesen oder nur beim Schreiben konvertieren zu m ssen Allerdings bedeutet das dass das Kreuzprodukt aller verwendeten numerischer Bibliotheken an Konver tierungsfunktionen existieren muss Das w rde die Basistypen extrem un bersichtlich und die Einf hrung einer neuen Bibliothek sehr aufwendig machen Deshalb wird diese Optimierung nicht unterst tzt Die Unterst tzung f r den Einsatz verschiedener numerischer Bibliotheken innerhalb einer Simulation beschr nkt sich also darauf ihn zu erm glichen Empfohlen wird al lerdings durchg ngig dieselbe Bibliothek zu verwenden In diesem Fall k nnen durch 41 4 Implementierung die Optimierung sehr viele Konvertierungen eingespart werden Wie viel das ausmachen kann klart Kapitel 5 4 3 Ports Ports sind die Verbindungsst cke zwischen Modulen und Streams Sie bieten dem Ent wickler eine Schnittstelle f r die Ein und Ausgabe der Module Die Eigenschaften eines Ports sind Name Um mehrere Ports eines Moduls voneinander unterscheiden zu k
17. Sollte sich herausstellen dass diese Zeit inakzeptabel lang ist so kann der Ge nerator folgenderma en beschleunigt werden Die Source Services unterst tzen eine differentielle bertragung von Daten Dadurch werden im Zielverzeichnis des Generators nur die Dateien berschrieben die der Source Service in einer anderen Version vorliegen hat Das Buildsystem bersetzt anschlie end nur die Teile neu die sich ver ndert haben Dadurch kann in den meisten F llen die Neu bersetzung der Laufzeitumgebung und der verwendeten Module und Typen ver mieden werden da blicherweise alle Benutzer die jeweils aktuelleste Softwareversion verwenden Verwendet ein Benutzer eine andere Version kann diese L sung im schlech testen Fall dazu f hren dass dennoch alles neu bersetzt werden muss Eventuell w re es denkbar dass der Generator mehrere Arbeitsverzeichnisse verwendet um diesen Fall zu verhindern 73 7 Zusammenfassung Das Ziel dieser Diplomarbeit war es in Kooperation mit Stephanie Wist ein Simu lationsprogramm zu schaffen das im Gegensatz zu allen bekannten Alternativen die M glichkeiten die sich durch verteiltes Rechnen ergeben vollst ndig aussch pft In ei nem Netzwerk von mehreren Computern kann vor allem die Wartezeit auf Ergebnisse durch paralleles Ausf hren einer Simulation deutlich gesenkt werden Zus tzlich erlaubt die Flexibilit t die sich durch die Migration von laufenden Simulationen auf andere Computer ergibt eine
18. Streamobjektes gerufen Die Parameter dieser Funktionen sind ein Zeiger auf den Kommunikationspartner und die beiden Kennungen die die beiden Objekte untereinander verwenden Im Falle der Streams ist die gerufene Funktion zur Vernetzung in der oberen Schicht definiert da die untere Schicht keine Referenzen auf seine Leser und Schreiber braucht Im Falle der Module allerdings ist die gerufene Funktion in der unteren Schicht definiert Diese Funktion gibt zum einen dem Adapter vgl 4 3 2 und zum anderen der oberen Schicht den Zeiger und die Kennungen 4 5 2 Ereignisse Neben den impliziten Aufrufen existieren noch weitere Ereignisse in der oberen Schicht Diese werden alle durch das explizite oder implizite Beenden eines Moduls ausgel st So teilt das Modul allen seinen eingehenden Streams unter Nennung der Kennung aus Abschnitt 4 5 1 mit dass ein Leser beendet hat Den ausgehenden Streams wird entsprechend mitgeteilt dass ein Schreiber beendet hat Erkennt ein Stream dass der letzte Leser beendet hat so teilt er allen seinen Schreibern wieder unter Nennung seiner Kennung mit dass ein ausgehender Stream geschlossen wurde Analoges geschieht falls der letzte Schreiber beendet So f hren alle Module und Streams st ndig Buch ber den Zustand des Graphen Sie brauchen diese Informationen um Entscheidungen f r das Scheduling treffen zu k nnen Neben den Streams benachrichtigt ein Modul beim Beenden auch den Scheduler Dieser kann daraufhin
19. an die Entwickler API sind sicher erf llt Erstens zeigen die Messungen in Kapitel 5 dass der Anteil der Verwaltung an der Laufzeit einer Simulati on vernachl ssigbar ist Zweitens f hren die vordefinierten Funktionen vgl Abschnitt 4 4 2 und das implizite Beenden vgl Abschnitt 3 1 4 dazu dass das Sinnvollste ge schieht wenn der Entwickler nicht eingreift und drittens verhindern die Hilfsfunktionen vgl Abschnitt 4 4 2 13 dass der Entwickler Code schreiben muss dessen Zweck und Hintergr nde nicht offensichtlich sind 6 2 Anwendungsgebiete Lethe wurde speziell auf den Einsatz in der Kanalcodierung hin entwickelt Das bedeutet aber nicht dass es nicht auch in anderen Anwendungsgebieten eingesetzt werden kann Jedes Problem dass sich als Hypergraph modellieren l sst bei dem in den Knoten station re Algorithmen Daten von eingehenden auf ausgehende Kanten abbilden l sst sich mit Lethe simulieren Das bedeutet insbesondere dass Lethe nicht nur in der Kanal codierung sondern in vielen Gebieten der Informationstheorie eingesetzt werden kann 69 6 Schlu folgerungen und Ausblicke Durch das speziallisierte Scheduling vgl Abschnitt 3 1 3 eignet sich Lethe nur be dingt fiir die Simulation von verteilten Algorithmen wie z B Netzwerkprotokollen Ins besondere das Fehlen einer Simulationszeit ist dabei das Problem So l sst sich z B die Verz gerung von Nachrichten nur umst ndlich realisieren Auch f r Simulationen v
20. auf einem beliebigen Computer fortgesetzt werden k nnen Lethe k mmert sich damit um die transparente Behandlung von Sy stemausf llen Alle automatisierten Vorg nge k nnen auch manuell gesteuert werden Dabei sind Zugriffe auf das verteilte System durch ein Rechtesystem f r Benutzer ge sch tzt Zum anderen ist Lethe ein Framework f r die Simulationen das aus einer Program mierschnittstelle und eine Laufzeitumgebung besteht Das wesentliche Kriterium f r die Gestalt dieses Frameworks ist die Erm glichung der im vorigen Absatz beschriebenen Der Name Lethe stammt aus der griechischen Mythologie Er bezeichnet dort den Flu des Vergessens im Reich von Hades dem Gott der Unterwelt 20 1 Einf hrung Fahigkeiten von Lethe Dabei wird vor allem die Tatsache ausgenutzt dass Lethe auf Anwendungen in der Kanalcodierung spezialisiert ist Ein anderes wichtiges Kriterium ist es die Wiederverwendbarkeit von Implementierungen zu maximieren Deshalb exi stiert unter anderem ein Konzept fiir parametrisierbare Module Lethe kennt also zwei getrennte Rollen von Anwendern Der Entwickler ist derjeni ge der einen neuen Algorithmus erforschen m chte und ihn deshalb unter Verwendung des Frameworks implementiert Der Benutzer ist dagegen derjenige der auf eine gege bene Menge von implementierten Algorithmen zur ckgreift und daraus mit Hilfe des Anwenderprogramms Simulationen erstellt die von Lethe ausgef hrt werden sollen Eines der
21. das Modul ggf aus der Menge der Beobachter oder Protokollierer entfernen vgl Abschnitt 3 1 4 4 5 3 Die call Funktion Die call Funktion ist in der abstrakten Core Module Klasse definiert Sie wird von den Streams und dem Scheduler gerufen und ruft ihrerseits die user_trigger Funktion Der Aufruf der user_trigger Funktion ist mit einer Reihe von Ausnahmebehandlun gen versehen Egal auf Grund welcher Ausnahme die user_trigger Funktion verlassen wurde l st die Funktion die in Abschnitt 4 5 2 beschriebenen Ereignisse aus Ist die Ausahme keine die von den Streams geworfen wird vgl Abschnitt 4 3 2 und damit zum normalen Ablauf der Simulation geh rt wird eine entsprechene Lognachricht an den Breeze Server vgl Abschnitt 3 2 6 geschickt Bevor die call Funktion die user_trigger Funktion ruft legt sie ein LoopPrevention Objekt an Die LoopPrevention Klasse setzt in ihrem Konstruk tor eine boolsche Variable die der Destruktor wieder zur ck setzt Diese Variable ist dabei eine Membervariable der Core Module Klasse die angibt ob die call 56 4 5 Das Scheduling Funktion des Moduls bereits im Wartestack des Schedulings vorhanden ist Falls die Variable beim Aufruf des Konstruktors bereits gesetzt ist wirft die Klasse eine LoopPrevention LoopDetected Ausnahme Auf diese Weise wird das Verbot von zirkul ren Abh ngigkeiten durchgesetzt vgl Abschnitt 3 1 3 Durch die Verwendung des Destruktors ist garantiert dass die b
22. der Fehlermeldungen gefunden werden damit der Benutzer ausgehend von einer konkreten Fehlermeldung m glichst schnell Hinweise auf den Grund finden kann Problematisch an diesem Ansatz ist dass f r jeden Compiler vielleicht sogar f r jede Compilerversion ein eigenes Nachschlagewerk gebraucht wird Ein komfortablere L sung ist wenn aus den Fehlermeldungen automatisiert eine ver st ndliche Erkl rung des Problems erzeugt wird Programme wie z B STLFilt 34 zei gen dass das m glich ist Allerdings muss auch hierbei f r jeden Compiler in jeder Version extra Arbeit gemacht werden Zufriedenstellend sind also beide L sungen nicht Vielleicht gibt es bessere M glich keiten was noch untersucht werden muss 6 4 3 Unterst tzung von manueller Parallelisierung Wie Abschnitt 3 1 5 diskutiert parallelisiert Lethe ausschlie lich an Rundengrenzen Der Grund daf r ist dass Lethe selbst ndig keine korrekte Aufspaltung einer Runde finden kann 71 6 Schlu folgerungen und Ausblicke Falls der Benutzer eine solche Aufspaltung findet muss er die Parallelisierung von Hand realisieren Dazu muss er mehrere fiir Lethe unabh ngige Simulationen erzeugen und die Ergebnisse der einzelnen Teile mit Hilfe von externen Programmen zusam men hren Sollte sich herausstellen dass die Parallelisierung von Runden einen erheblichen Zeit gewinn darstellt ist dar ber nachzudenken ob der oben beschriebene Vorgang nicht automatisiert werden ka
23. der Laufzeitumgebung stattfindet In beiden F l len ist die Startfunktion des Threads die wohldefinierte Umgebung f r lokale Daten des Algorithmus Die GNU Portable Threads Bibliothek PTH 11 ist f r diesen Zweck eine gute Wahl Dem Autor Ralf Engelschall ist es n mlich gelungen 10 kooperatives Multi tasking ohne die Verwendung von plattformspezifischem Assembler und ausschlie lich unter Verwendung von POSIX konformen ISO 9945 Schnittstellen zu implementieren Allerdings haben Messungen im Rahmen dieser Arbeit ergeben Anhang A 1 dass ein Kontextwechel zwischen zwei User Threads ungef hr so viel Laufzeit kostet wie 100 nicht optimierte Funktionsaufrufe Auch wenn es im Rahmen dieser Arbeit gelungen ist die Anzahl der Kontextwechsel gegen ber der aktuellen PTH Implementierung zu halbieren Anhang A 2 bleibt die Verwendung der PTH teuer Andere Bibliotheken sind vielleicht schneller verwenden daf r aber nicht portablen Assembler Code M chte man also die Laufzeit einer Simulation niedrig halten muss man dem Entwick ler ein wenig Komfort absprechen Anstatt eine eigene ausf hrende Einheit zu haben muss er seinen Algorithmus als Behandlungsfunktion von geeignet definierten Freig nissen formulieren damit das kooperative Multitasking durch einen zentralen Verteiler erledigt werden kann Da dieser Ansatz sehr schnell ist ist er typisch f r Simulationen Es handelt sich um den in Abschnitt 2 2 diskutierten ereignisbasier
24. einen zweiten Kontextwechsel in diesen neuen Thread vorzunehmen Stand Version 2 0 6 Es ist allerdings auch m glich die Schedulingalgorithmen in den Benutzerthreads aus zuf hren Dann wird kein Thread f r den Scheduler ben tigt und der Wechsel zwischen zwei Threads findet direkt statt Das folgende Programm ist der Nachweis dass dies m glich ist Es verwendet die GNU PTH Sub API f r die Kontextwechsel A 2 1 pth fast h ifndef __PTH_FAST_H define __PTH_FAST_H include lt unistd h gt define MAX_NUMBER_OF_THREADS 10 call this method first and once void pthf_init start scheduling function returns if the last thread exists void pthf_run add a new thread for scheduling void pthf_spawn void func void void arg char stack size_t stacksize let control be passed to another thread void pthf_yield endif A 2 2 pth fast c include lt stdlib h gt include lt stdio h gt include lt pth h gt include pth fast h define die pthf_abort __LINE__ 80 A 2 Halbieren der Anzahl der Kontextwechsel the round robin queue pth_uctx_t threads MAX_NUMBER_OF_THREADS index of the currently running thread int current 1 number of spawned threads int number 0 the context of the main thread pth_uctx_t mainContext the context of the exit handler pth_uctx_t exitContext local functions void pthf_exit void void pthf_abort int line vo
25. end die Laufzeit der Simulation gemessen Die Eigenschaften der Ports sind in in Tabelle 5 7 abgebildet Der Paramter b ist die Variable f r die wachsende Blockgr e Die Optimierung ist eingeschaltet so dass sich f r die Eigenschaften der Kanten die Tabelle 5 8 ergibt Knoten Kante Basistyp Arbeitstyp Blockgr e Quelle 1 Integer int 1 b Encoder 1 Integer int 2 b 2 Complex gsl_complex 1 b Kanal 2 Complex gsl_complex 1 b 3 Complex gsl_complex 1 b Decoder 3 Complex gsl_complex 1 b 1 Integer int 2 b Senke 1 Integer int 1 b 3 Integer int 1 b Tabelle 5 7 Die Eigenschaften der Ports aus der Messung 5 5 Kante 1 2 3 4 Puffertyp int gsl_complex gsl_complex int Basistyp Integer Complex Complex Integer Tabelle 5 8 Die Eigenschaften der Kanten aus der Messung 5 5 Die Abbildungen 5 2 und 5 3 zeigen die Ergebnisse dieser Messreihe Wie erwartet sinkt der Verwaltungsaufwand mit steigender Blockgr e 63 5 Messungen Laufzeit Sekunden Abbildung 5 2 Der Verwaltungsaufwand in Abh ngigkeit zur Blockgr e Laufzeit Sekunden Abbildung 5 3 Der Verwaltungsaufwand in Abh ngigkeit zur Blockgr e gr ere Skala 64 5 5 Erh hung der Blockgr e Die Itereration ber die Vektor Objekte erfordert eine einmalige Erh hung der Co dekomplexit t in den Knoten Daf r kann die Laufzeit im Austausch ge
26. er h lt den Simulationsprozess zu beenden Nach Ablauf dieser Zeit wird der Simu lationsprozess zur ck gelassen und eine Fehlermeldung ausgegeben Config MakeCmd Pfad zum GNU make Programm 25 Dar berhinaus k nnen in der Datei global config mak die sich im Arbeitspfad befindet die folgenden Einstellungen vorgenommen werden 85 Anhang B Dienste CC Pfad zum C Compiler LD Pfad zum Linker SLICEC Pfad zum Slicecompiler f r C vgl ICE Benutzerhandbuch Abschnitt 4 18 21 AR Pfad zum ar Programm zum Erstellen von statischen Bibliotheken RANLIB Pfad zum ranlib Programm zum inidzieren von statischen Bibliotheken GLOBAL_CCFLAGS Optionen fiir den Compiler GLOBAL_LDFLAGS Optionen fiir den Linker GLOBAL_SLICEC_FLAGS Optionen fiir den Slicecompiler B 2 Breeze Server Abschnitt 3 2 6 erklart die Aufgaben des Breeze Servers B 2 1 Nachrichten Eine Nachricht besteht aus den folgenden Feldern Typ Der Typ der Nachricht M gliche Werte sind vgl Abschnitt 3 2 6 e EMERG e ALERT e CRIT e ERR e WARNING e NOTICE e INFO DEBUG Herkunft Ein beliebiger String der die Herkunft einer Nachricht beschreibt Inhalt Ein beliebiger String der den eigentlichen Inhalt der Nachricht wieder gibt Zeitstempel Die Unixzeit zu dem die Nachricht beim Breeze Server einging Das ist die Anzahl der vergangenen Sekunden seit dem 1 Januar 1970 00 00 h UTC 86 B 2 Breeze Server B 2 2 Konfiguration Zur Konfigu
27. keine Programmierkenntnisse braucht Am Ende der Simulation kann er sich die Ergebnisse graphisch anzeigen lassen und mit Hilfe von mitgelieferten Werkzeugen analysieren Das ist alles sehr komfortabel Inwiefern ein Anwender selbst neue Kom pontenten entwickeln kann ist allerdings unklar Die oben zitierte Internetseite schweigt sich dar ber aus Die Lizenz f r eine kommerzielle Nutzung von GoldSim kostet 3950 f r das Basispaket F r akademische Zwecke existiert eine kostenlose Version mit einem etwas eingeschr nkten Funktionsumfang F r Zusatzpakete kommen allerdings auf jeden Fall Kosten zwischen 1000 und 9000 hinzu Stand 10 April 2006 Bekannte Alternativen zu GoldSim sind z B MLDesigner 26 das CoCentric Sy stems Studio 7 und das freie Ptolemy 30 Obwohl die drei Programme jeweils einen etwas anderen Einsatzzweck haben ergeben sich f r den Kanalcodierer dieselben Pro bleme So ist keines der Programme auf den Einsatz in der Kanalcodierung spezialisiert Das bedeutet dass der Kanalcodierer eine geeignete Abbildung seines Problems auf das Modell des Simulationsprogrammes finden muss Das kann mitunter sehr aufwendig und frustrierend sein Dazu kommt dass keines der Programme die in der Einf hrung aufgelisteten Probleme beim Einsatz in Netzwerken l st Der Anwender muss selbst n dig verteilen und die einzelnen Simulationen verwalten Simulationen migrieren oder Sicherungspunkte erstellen ist berhaupt nicht m glic
28. nnen besitzt jeder Port einen Namen berall wo der Anwender mit einem Port arbeiten muss kann er dessen Namen verwenden vgl Abschnitt 4 4 2 4 Da der Name auf Grund von Namenskonventionen in verschieden Kontexten anders geschrieben wird m s sen sich die Namen von zwei Ports durch mehr als nur die Gro Kleinschreibung unterscheiden Blockgr e Die Blockgr e erm glicht es Lethe die ben tigte Puffergr e des ange schlossenen Streams zu berechnen vgl Abschnitt 4 2 2 Basistyp Der Basistyp stellt sicher dass zwei Ports die durch einen Stream miteinander verbunden sind miteinander kommunizieren k nnen Au erdem erm glicht er es einem Stream seinen Zustand zu persistieren vgl Abschnitt 4 2 3 Arbeitstyp Der Arbeitstyp erlaubt im Zusammenspiel mit Konvertierungsfunktionen des Basistyps die Benutzung von beliebigen numerischen Bibliotheken vgl Ab schnitt 4 2 4 Die zentralen Datenstrukturen f r die Ein und Ausgabe sind die Vector Klassen Abschnitt 4 3 1 erkl rt wie sie gleich eine ganze Reihe von Problemen aus Abschnitt 4 2 l sen Abschlie end erl utert Abschnitt 4 3 2 die Implementierung der Ports durch die Adapter Klasse 4 3 1 Die Vector Klassen Die Kernidee der Vector Klassen ist die folgende anstatt eines Zeigers in den Puffer erh lt der Entwickler bei Lese bzw Scheibzugriffen von den Ports ein Objekt vom Typ ReadVector bzw WriteVector Da die Vector Klassen den Indexoperator definieren ist
29. sind existiert f r jede von ihnen eine eigene Version von Lethe die auf der beigef gten CD enthalten ist Tabelle 5 1 listet diese auf Abschnitt Version 5 3 342 5 4 345 5 4 1 353 5 4 2 354 5 5 355 5 5 1 363 branch 5 6 355 und 363 branch Tabelle 5 1 Die verwendeten Softwareversionen 5 3 Verwaltungsaufwand Idealerweise sollte nur ein Bruchteil der Laufzeit einer Simulation f r den Verwaltungs aufwand verbraucht werden Die Messung berpr ft ob das f r Lethe zutrifft indem sie die Laufzeit der Simulation bestimmt bei der wie bereits erw hnt in den Knoten minimale Laufzeit verbraucht wird Die Eigenschaften der Knoten sind so gew hlt dass an keiner Stelle benutzerdefinierte Konvertierungen auftreten vgl Abschnitt 4 2 4 Da ein Complex aus zwei Flie komma zahlen und ein Integer aus einer Ganzzahl besteht kommt es im Encoder und Decoder unvermeidlich zu Konvertierungen zwischen den Typen int und double Der Aufwand daf r ist aber vernachl ssigbar Die f r die Messungen relevanten Eigenschaften der Ports sind in Tabelle 5 2 aufgeli stet Tabelle 5 3 zeigt die Eigenschaften der Kanten Die Messung ergab eine Laufzeit von 57 Sekunden Erfahrungsgem h ngt die Lauf zeit einer Simulation sehr stark von der Komplexit t des simulierten Codes ab So er geben sich f r Simulationen diesen Umfangs Zeiten zwischen einer Stunde und einem Tag Der Anteil der Verwaltung liegt also zwischen 1 58 u
30. verantwort lich und muss seine Leser und Schreiber implizit aufrufen Zweitens muss er die Daten des Schreibers puffern und allen Lesern zur Verf gung stellen Die erste Aufgabe ber nimmt die Klasse Stream Die zweite Aufgabe bernimmt die davon abgeleitete Klasse Templates Stream Beide Klassen sind im Namensraum Core definiert Diese Aufteilung der Aufgaben in zwei Schichten dient der Trennung von Daten fluss und Schedulinglogik In diesem Abschnitt wird nur die Implementierung der Templates Stream Klasse behandelt Die Aufgaben der Stream Klasse er rtert ein eigener Abschnitt ber das Scheduling Abschnit 4 5 Da die Streams die zentrale Infrastruktur der Simulationen sind ist vor allem die Geschwindigkeit zur Laufzeit ma geblich f r Entscheidungen ber die Implementierung Die ersten Konsequenzen daraus ergeben sich in Abschnitt 4 2 1 Er erkl rt wie der 1 Zur Notation von Namensr umen siehe Abschnitt 2 5 36 4 2 Streams Puffer in einem Stream implementiert ist Abschnitt 4 2 2 leitet anschlie end her wie gro ein Puffer mindestens sein muss und welche Gr e Lethe f r die Puffer w hlt Abschnitt 4 2 3 f hrt die sogenannten Basistypen ein Diese erm glichen es dass der Zustand eines Streams erfasst werden kann und stellen au erdem sicher dass alle durch den Stream verbundenen Module miteinander kommunizieren k nnen Insbesondere er l utert dieser Abschnitt dass Templates Stream eine Template Kl
31. verteilen um sie parallel in mehreren Recheneinheiten zu erledigen Die dadurch entstehenden Ne benl ufigkeiten k nnen allerdings zu Konflikten f hren Ein Konflikt ist z B wenn zwei Ereignisse auf Grund der nicht synchronen Simulationszeiten der einzelnen Rechenein heiten von einem Empf nger in der falschen Reihenfolge behandelt werden Um diesem Problem zu begegnen existieren im Wesentlichen zwei Ans tze die pessimistischen und die optimistischen Verfahren Die in der Fachwelt als konservativ bezeichneten pessimistischen Verfahren gehen da von aus dass ein Konflikt wahrscheinlich ist und investieren deshalb in die Vermeidung Dazu verwendet das Scheduling die Kausalit tskette der Ereignisse um voneinander abh ngige Freignisse ausschlie lich in der richtigen Reihenfolge zu behandeln Kausal unabh ngige Ereignisse k nnen hingegen parallel behandelt werden Um die Korrektheit des Verfahrens zu garantieren muss das Scheduling im Zweifelsfall annehmen dass eine kausale Abh ngigkeit zwischen zwei Ereignissen existiert und kann ihre Bearbeitung damit nicht parallelisieren Die Effizienz dieses Verfahrens h ngt deshalb direkt von der Vollst ndigkeit der ermittelten Kausalit ten ab Da die Kausalit ten eine Eigenschaft der Simulationslogik sind k nnen sie nicht automatisiert ermittelt werden Vielmehr braucht das Scheduling dazu Metainformationen vom Benutzer Die Effizienz von pes simistischen Verfahren h ngt also im Endeffekt davo
32. von diesem ICE Typ abgeleitet und definiert die Funktionen serialize und deserialize und den Default Konstruktor Die ersten beiden Funktionen werden gebraucht da die ICE Funktionen zum Seriali sieren und Deserialisieren eines Typs leider nicht im Namensraum dieses Typs existieren Da die Templates Stream Klasse aber nur ber den Typ ihres Puffers auf passende Funktionen zugreifen kann muss der Basistyp welche definieren die den Aufruf der je weiligen ICE Funktionen kapseln Der Grund f r den Default Konstruktor ist dass der Entwickler wie Abschnitt 4 2 4 erkl rt in der Klasse des Basistyps eventuell Konstruk toren zur Typkonvertierung definieren muss Dadurch entfernt er die in C implizite Definition des Default Konstruktors Da dieser aber gebraucht wird muss er explizit definiert werden Da es denkbar ist dass ein Modul von zwei verschiedenen Streams Daten von un terschiedlichem Typ haben m chte muss der Basistyp eine Eigenschaft eines Ports sein Zwei Module k nnen genau dann miteinander kommunizieren wenn die durch den Stream verbundenen Ports denselben Basistyp verwenden Anders formuliert bedeutet das dass alle Ports die an denselben Stream angeschlossen sind denselben Basistyp verwenden m ssen 4 2 4 Arbeitstypen Wie der vorherige Abschnitt erl utert ist die besondere Eigenschaft eines Basistyps dass die ICE Laufzeitumgebung diesen serialisieren kann Das ist f r beliebige andere Typen 39 4 Implementierung
33. wird es f r die folgenden Messungen nicht ber ck sichtigt Stattdessen sind die Knoten so implementiert dass sie die Daten unver ndert durchreichen Die Quelle erzeugt fortlaufend aufsteigende Zahlen und die Senke ber pr ft ob die Zahlen von der Quelle und vom Decoder jeweils identisch sind Damit ist diese Messung gleichzeitig ein Funktionstest der Laufzeitumgebung Der folgende Abschnitt listet die Testkriterien der durchgef hrten Messungen auf Anschlie end erkl rt Abschnitt 5 2 wie sie wiederholt werden k nnen Die restlichen Abschnitte dokumentieren die eigentlichen Messungen 5 1 Testkriterien Die Testumgebung hatte f r alle Messungen die folgenden Eigenschaften Prozessor Intel Pentium M Prozessor mit 1 73GHz Speicher 2GB System Debian GNU Linux 8 Compiler GNU C Compiler 4 0 3 14 Compileroptionen DNDEBUG O1 Assertions deaktivieren einfache Optimierung 59 5 Messungen Die Simulation endet sobald die Senke 10 Millionen Zahlen gelesen und verglichen hat Dies ist eine realistische Anzahl fiir typische Simulationen Gemessen wird im folgenden jeweils die Zeit die zwischen dem Start und dem Ende der ersten und einzigen Phase der Simulation vergeht 5 2 Wiederholung der Messungen Bei den Messungen wurden jeweils andere Implementierungen der Module verwendet Ihre Eigenschaften und die der Kanten haben au erdem einen Einflu auf den Code den der Generator erzeugt hat Damit die Messungen wiederholbar
34. zu ihrem Ende kommt Der Nachteil des Schedulingalgorithmus ist dass die Aufrufreihenfolge der Knoten erstens von der Wahl der initialen Knoten zweitens von den Gr en der Puffer in den Kanten und drittens vom Verhalten der einzelnen Knoten abh ngt Die Wahl der initialen Knoten ist wie Abschnitt 3 1 4 erl utert nicht beliebig und vom Anwender 17 3 Systementwurf beeinflussbar Die Gr e der Puffer ist wie Abschnitt 4 2 2 erkl rt auch relativ einfach zu bestimmen Doch die Komplexit t des Zusammenspiels dieser Faktoren und vor allem die Tatsache dass das Verhalten eines Knotens eventuell unbekannt ist wenn man nicht dessen Entwickler ist legen nahe trotz ihrer Determiniertheit keine Annahmen ber die Aufrufreihenfolge zu machen Eine direkte Konsequenz aus diesem Nachteil ist dass die Menge der verwendeten Algorithmen beschr nkt ist auf die Klasse der station ren Algorithmen So k nnen z B Interrupts nicht abgebildet werden Eine weitere direkte Konsequenz ist dass eine Kante maximal einen Schreiber haben kann vgl Abschnitt 3 1 8 3 1 4 Das Ende einer Simulation Ein scheinbar trivialer aber im Detail doch komplexer Sachverhalt ist die Frage wann eine Simulation zu Ende ist Ein denkbarer Anwendungsfall ist dass die Simulation beendet werden soll wenn die Senke eine bestimmte Anzahl von Vergleichen gemacht hat Allerdings k nnte es auch sein dass die Simulation fr hzeitig beenden soll wenn z B die Senke
35. zu jedem beliebigen Zeitpunkt beenden lassen die Um die Abbildung 3 6 bersichtlich zu halten sind die dazu geh renden Zustands berg nge und der Endzustand selber nicht eingezeichnet Wie bereits erw hnt bietet die Schnittstelle des Managers die M glichkeit ihn zu informieren wenn die Simulation das Ende einer Runde erreicht hat Zus tzlich bietet sie die M glichkeit den Manager zu benachrichtigen wenn w hrend der Simulation ein 30 3 2 Das verteilte System Fehler auftritt Wie Abschnitt 3 2 5 allerdings diskutiert tibernimmt der Proxy dieses Aufgabe 3 2 3 Der Generator Wie Abschnitt 3 2 2 erl utert muss f r jede Simulation eine eigene ausf hrbare Datei bersetzt und gestartet werden Diese Aufgabe bernimmt der Generator Auf jedem teilnehmenden Computer l uft eine Instanz eines Generators Hat der Manager entschieden auf welchem Computer eine Simulation ausgef hrt werden soll kontaktiert er den entsprechenden Generator Sobald der Simulationsprozess l uft gibt der Generator dem Manager die Referenz auf das Simulationsobjekt so dass dieser in Zukunft direkt mit der Simulation kommunizieren kann Die bersetzung des Quellcodes zur ausf hrbaren Daten wird durch das GNU ma ke 25 Programm gemacht Daf r existieren eine Reihe von Skript und Konfigurati onsdateien die in ihrer Gesamtheit das Buildsystem f r Simulationen ausmachen Der Generator kann ber dieses Buildsystem in einem ersten Schritt den
36. zu machen Die Modularisierung des Programms ist damit aufgebrochen Einer der Nachteile die sich daraus ergeben ist dass in jeder bersetzungseinheit die die Deklaration der Template Klasse braucht alle Abh ngig keiten der Implementierung dieser Klasse mit eingef gt werden 2 6 Numerische Bibliotheken Die Algorithmen die in der Kanalcodierung auftreten f hren h ufig numerische Be rechnungen durch F r diesen Zweck gibt es schon eine Reihe von Bibliotheken Am weitesten verbreitet sind dabei die Basic Linear Algebra Subprograms BLAS 6 22 Diese in Fortran 19 geschriebene hoch optimierte Bibliothek ist die Basis f r viele erweiterte numerische Bibliotheken wie z B das Linear Algebra Package LAPACK 9 oder die GNU Scientific Library GSL 23 11 2 Grundlagen und Stand der Technik Eine alternative M glichkeit ist die Verwendung der Matlab Bibliotheken die sehr umfangreich sind Implementiert man die Verwendung dieser Bibliotheken in der kom fortablen Matlab Hochsprache kann man anschlie end mit Hilfe eines Matlab nach C Compilers die Methoden in ein in C oder C geschriebenes Programm einbinden Au er einer Einschr nkung die in Abschnitt 3 1 9 erl utert wird spielt die tats chlich verwendete numerische Bibliothek im Grunde keine Rolle Es ist allerdings wichtig zu wissen dass es verschiedene Bibliotheken gibt und dass viele Entwickler ihre Favoriten haben Um einen m glichst gr
37. zum Zeitpunkt seines Beendens f r ihn gepuffert hatte sind diejenigen die dem neuen Leser zu Beginn der neuen Phase zur Verf gung stehen Hinzu kommen die Daten die der Schreiber nach dem Beenden des letzten Lesers ggf in die Kante eingef gt hat Die erste Regel entspricht dem was der Benutzer normalerweise erwartet Die Regel 2a bewirkt dass ein neuer Leser so viel Daten wie m glich zur Verf gung hat Die Festlegung der Regel 2b hat den Sinn dass nach dem Beenden des letzten Lesers der Schreiber die Kante noch maximal f llen kann Es ist bei Regel 2 m glich dass der neue Leser die ersten Daten die er in der neuen Phase liest in der alten schon einmal gelesen hat Das h ngt davon ab wann er in der alten Phase beendet hat und wie sich die anderen Leser danach verhalten haben Wenn 23 3 Systementwurf die Menge der Daten die der neue Leser am Anfang der neuen Phase sieht vorhersagbar sein muss dann muss dieser Leser w hrend der alten Phase entweder gar nicht oder als letzter beenden Denn dann gilt entweder Regel 1 oder Regel 2b so dass er auf jeden Fall nahtlos weitermachen kann Die Tatsache dass das Scheduling keine Garantie ber die Aufrufreihenfolge gibt vgl Abschnitt 3 1 3 kann allerdings dazu f hren dass sich vorab nicht bestimmen l sst ob der Leser eventuell implizit beendet wird bevor der letzte Beobachter beendet Ob das f r viele Anwendungsf lle problematisch ist wird die Erfahrung mit Lethe ze
38. 46 47 54 55 56 56 59 59 60 60 61 62 62 63 65 66 69 69 69 70 70 71 71 71 72 72 75 INHALTSVERZEICHNIS A GNU PTH A 1 Zeitmessung der GNU PTH A 1 1 Verwendung der GNU PTH A 1 2 Verwendung eines Verteilers A 1 3 Umgebung A 1 4 Ergebnisse A 2 Halbieren der Anzahl der Kontextwechsel A 2 1 pth fast h A 2 2 pth fast c A 2 3 Eine beispielhafte main c B Dienste B 1 Generator B 2 Breeze Server B 2 1 Nachrichten B 2 2 Konfiguration B 2 3 Logdateien B 2 4 publish B 2 5 lastlog C Verwendete Software Index Abbildungsverzeichnis Literaturverzeichnis IX 1 Einf hrung Die Telekommunikation spielt in der modernen Gesellschaft eine zentrale Rolle Egal ob bei Steuerchips in Autos Schiffen oder Flugzeugen bei Signalprozessoren in Mobil telefonen oder bei Controllern von Bussystemen in Computern oder Industrieanlagen berall werden Informationen ausgetauscht und verarbeitet Dabei steigen die Anfor derungen an Geschwindigkeit und Robustheit unter immer kritischeren Bedingungen kontinuierlich an Forscher auf dem Gebiet der Informationstheorie sorgen seit Jahrzehnten immer wie der f r L sungen die den wachsenden Anspr chen gerecht werden Einer der zentralen Schaupl tze auf diesem Gebiet ist dabei die Kanalcodierung Sie besch ftigt sich mit der Frage wie man den Informationsaustausch durch kontrolliertes Hinzuf gen von m g lichs
39. 49 4 Implementierung 10 return CONTINUE 11 Zeile 1 zeigt die Signatur der user_trigger Funktion Der Riickgabewert ist vom Typ Decision Dies ist eine Enumeration die die beiden Konstanten CONTINUE und QUIT definiert Durch R ckgabe der Konstanten QUIT signalisiert ein Modul der Lauf zeitumgebung dass es f r die aktuelle Phase beenden m chte vgl Abschnitt 3 1 4 Die generierte Implementierung gibt am Ende der Funktion immer CONTINUE zur ck was f r alle Module im Normalfall das korrekte Verhalten ist Der einizige Parameter der Funktion ist vom Typ Caller Wie Abschnitt 4 3 2 erkl rt kann das Modul an diesem Parameter erkennen warum es gerufen wurde Die Zeilen 2 und 3 zeigen wie der Zugriff auf ein und ausgehende Streams ber das in Abschnitt 4 3 2 eingef hrte ports Objekt geschieht InputVector und OutputVector sind Aliasnamen f r passende Instanzen der Vector Klassen vgl Abschnitt 4 3 1 Es ist in diesen Zeilen nicht zu erkennen ob ein Lese oder ein Schreibzugriff stattfindet Deshalb ist es empfehlenswert aussagekr ftige Namen f r die Ports zu verwenden Da die Blockgr e f r beide Ports eins ist ist zu den verwendeten Parametern der Port Funktionen nicht viel zu sagen Die Zeilen 4 bis 9 zeigen die lesenden und schreibenden Zugriffe auf die Daten der Streams mit Hilfe der Vektor Objekte Die gsl_ran_gaussian Funktion aus der GSL gibt eine gaussverteilte Zufallszahl zur ck Dazu verwendet sie den Zufall
40. 5 Beowulf http www beowulf org April 2006 BOSSERT M Channel Coding for Telecommunications John Wiley amp Sons New York 1 Auflage 1999 BREITBACH M und M BOSSERT Digitale Netze Teubner Verlag Stuttgart 1 Auflage 1999 BRIAN W KERNIGHAN DENNIS RITCHIE Programmieren in C Hanser Fachbuch 2 Auflage Januar 1990 BROWN WILLARD A SIMULA for those who know FORTRAN PL I or BA SIC Norwegian Computing Center SIMULA information publication Norwegian Computing Center Oslo Norway 1981 C L Lawson R J Hanson D R KINCAID und F T KROGH Basic Line ar Algebra Subprograms for Fortran Usage ACM Transactions on Mathematical Software 5 3 S 308 323 September 1979 CoCentric System Studio http www synopsys com April 2006 Debian GNU Linux http www debian org April 2006 E ANDERSON Z BAI C BISCHOF S BLACKFORD J DEMMEL J DONGARRA J Du Croz A GREENBAUM S HAMMARLING A MCKENNEY und D SOREN SEN D LAPACK Users Guide Society for Industrial and Applied Mathematics Philadelphia PA 3 Auflage 1999 ENGELSCHALL RALF S Portable Multithreading In USENIX Annual Technical Conference June 2000 ENGELSCHALL RALF S GNU Pth The GNU Portable Threads http www gnu org software pth April 2006 Free Software Foundation http www fsf org April 2006 FUJIMOTO RICHARD M Parallel and Distributed Simulation Systems Wiley Series on Parallel and Distributed Comp
41. Design und Implementierung eines Frameworks fur Simulationen in der Kanalcodierung mit Anbindung an ein verteiltes System Diplomarbeit von Alexander Bernauer Abteilung Telekommunikationstechnik und Angewandte Informationstheorie Universitat Ulm April 2006 D 2005 XL 2 Abteilung Telekommunikationstechnik und Angewandte Informationstheorie Universitat Ulm DIPLOMARBEIT Design und Implementierung eines Frameworks fiir Simulationen in der Kanalcodierung mit Anbindung an ein verteiltes System Erlauterungen Um in der Kanalcodierung theoretische Ergebnisse zu verifizieren werden Simulationen fiir die Berechnung der Restbit und blockfehlerraten verwendet Dabei werden entweder graphische Simulationstools wie ML Designer verwendet oder es werden komplette Si mulationsumgebungen in einer Programmiersprache wie C C oder Matlab erstellt Beide M glichkeiten haben ihre Vor und Nachteile Bestehende Simulationstools sind meist recht umfangreich und dementsprechend un bersichtlich Die Einarbeitung nimmt daher oftmals viel Zeit in Anspruch Desweite ren handelt es sich bei diesen Tools h ufig um kommerzielle Software wodurch hohe Lizenzkosten anfallen Auf der anderen Seite sind vom Anwender selbst geschriebene Simulationsumgebungen zwar frei haben aber den Nachteil dass von anderen Benutzern sehr viel Progam mierkenntnis verlangt wird um Modifikationen vornehmen zu k nnen Die komfortable graphische Benutzer
42. Diplomarbeit University of Ulm Mai 2006 97
43. EAL und GSL_IMAG die den Real bzw Imagin rteil einer gsl_complex Zahl liefern Mit Hilfe dieses Konstruktors kann berall ein Objekt vom Typ gsl_complex verwendet werden wo ein Objekt vom Typ Complex erwartet wird Die zweite Funktion ist ein Castoperator Er wird immer dann gerufen wenn ein Objekt vom Typ Complex verwendet aber ein Objekt vom Typ gsl_complex erwar tet wird Mit Hilfe der GSL Funktion gsl_complex_rect erzeugt diese Funktion eine gsl_complex Zahl aus den Variablen real und imag und gibt sie zur ck Der Arbeitstyp ist wie der Basistyp eine Eigenschaft eines Ports Da es bei einfa chen Modulen denkbar ist dass gar keine numerische Bibliothek zum Einsatz kommt entspricht der Arbeitstyp falls vom Entwickler nicht anders angegeben dem Basistyp Damit die GSL Funktionen und Typen bekannt sind muss der Entwickler die pas senden Header Dateien in der Basistyp Datei einbinden include lt gsl gsl_complex_math h gt 40 4 2 Streams Au erdem muss das Buildsystem dar ber informiert werden dass die GSL verwendet wird damit die Bibliotheken beim Linken mit eingebunden werden Dazu muss der Entwickler die folgenden Zeilen in die config mak eintragen LDFLAGS lgsl lgslcblas CCFLAGS Beide Zeilen sind make Kommandos 18 Die erste f gt den Linkeroptionen die Anwei sungen an die von der GSL ben tigten Bibliotheken mit zu verwenden Mit der zweiten Zeile k nnen spezielle Compileroptionen angegeben werden
44. GPL f r ihn keine Rolle Insofern ist es m glich Lethe f r die kommerzielle Entwicklung neuer Algorithmen zu verwenden Verwendet das Modul eine numerische Bibliothek deren Lizenz nicht GPL kompatibel ist ist die Weitergabe problematisch Dann muss im Einzelfall gekl rt werden welche juristischen M glichkeiten existieren Eventuell wird in Zukunft auch eine andere Lizenz f r den generierten Code festgelegt Dann w re es m glich Module zu erstellen die nicht unter der GPL stehen Die juristischen und kommerziellen Diskussionen dazu sind allerdings komplex und werden im Rahmen dieser Arbeit deshalb nicht gef hrt 6 4 Ausblicke Lethe ist ein sehr umfangreiches Projekt Selbst die Aufteilung auf zwei Diplomarbei ten kann nicht verhindern dass nicht alle Probleme im Rahmen dieser Arbeiten gel st werden k nnen Insbesondere ist die Implementierung nur ein Prototyp F r die Produktreife m ssen vor allem noch vollst ndige Modultests gemacht werden Auch die Robustheit der Soft ware muss verbessert werden An vielen Stellen bricht die Laufzeit in einem Fehlerfall einfach ab anstatt diesen geeignet zu behandeln 70 6 4 Ausblicke Die ersten beiden der folgenden Abschnitte benennen Punkte die in dieser Arbeit be reits im Entwurf oder der Implementierung aufgekommen sind Darauf folgen Abschnitte mit Ideen die den Komfort f r den Benutzer steigern 6 4 1 IceStorm Wie Abschnitt 3 2 6 erkl rt ist der Breeze Server aus Zei
45. GSL vgl Abschnitt 2 6 Alle Funktionen sind von Lethe vordefiniert Die Zeilen die der Entwickler im Beispiel hinzugef gt hat sind mit einem markiert Es ist in keinem Fall n tig gewesen dass eine generierte Zeile entfernt werden musste Die vordefinierte Implementierung wurde extra so gew hlt dass dies im Allgemeinen nie n tig sein d rfte 4 4 2 1 Metainformationen Im Folgenden sind alle Metainformationen aufgelistet die der Entwickler f r den Gaus skanal angeben muss Name GaussChannel e Ports erster Port Name Input AT 4 Implementierung x Typ eingehend x Basistyp Complex x Arbeitstyp gsl_complex x Blockgr e 1 zweiter Port x Name Output x Typ ausgehend x Basistyp Complex x Arbeitstyp gsl_complex x Blockgr e 1 Konfiguration Eine Enumeration die f r das Beispiel nur die Konstante TAUS definiert Eine Variable namens typeofRng vom Typ der Enumeration Einstellungen Eine Variable namens sigma vom Typ double Das ist die Varianz der Wahr scheinlichkeitsverteilung Eine Variable namens seed vom Typ unsigned long Das ist der Anfangs wert des Zufallsgenerators Zustand Ein Byte Array namens rngState Das ist der Zustand des Zufallsgenerators Ergebnis Der Gauss Kanal liefert keine Ergebnisse Der Typ ist deshalb leer 4 4 2 2 Vorbereitungen Der Gausskanal verwendet zum einen die komplexen Zahlen und zum anderen die Zu fallsgen
46. In den folgenden Abschnitten findet sich eine kurze Anleitung zu diesen Diensten und ihrer Konfiuguration Da die Dienste Teil des Grids sind werden sie automatisch gestartet und beendet Au erdem verwenden sie f rs Logging von internen Fehlerereignissen nicht den Breeze Server Statt dessen schreiben sie die Nachrichten auf ihre Standardausgaben so dass diese als Ausgabe der Grid Nodes erscheinen vgl ICE Benutzerhandbuch Abschnitt 36 15 2 21 B 1 Generator Abschnitt 3 2 3 erkl rt die Aufgaben des Generators und Abschnitt 3 2 5 f hrt aus dass die Proxies Teil des Generatorprozesses sind Zur Konfiguration des Breeze Servers existieren in der Deployment Beschreibung des ICE Grids die folgenden Eigenschaften Config WorkingDirectory Arbeitspfad in dem die Simulationen bersetzt werden Zu Beginn muss in diesem Verzeichnis der vollst ndige Quellcode des Frameworks enthalten sein Config WaitpidTimeout Zeit in Sekunden die der Proxy auf das Beenden eines Simu lationsprozesses der die Pipe zum Proxy geschlossen hat maximal wartet Nach Ablauf dieser Zeit wird der Simulationsprozess zur ck gelassen und eine Fehler meldung ausgegeben Config ShutdownTimeout Zeit in Sekunden die die Simulation vom Proxy maximal erh lt in Folge des die Kommandos zu beenden Nach Ablauf dieser Zeit wird das Betriebssystem angewiesen den Simulationsprozess zu beenden Config KillTimeout Zeit in Sekunden die das Betriebsssytem vom Proxy maximal
47. Knoten ausschlie lich aus der Menge der verblie benen Beobachter kann das zu Teilgraphen f hren die durch das implizite Scheduling nicht mehr erreicht werden Allerdings wird so eine Situation vom Scheduler nicht ex plizit erkannt so dass die Knoten des unereichbaren Teilgraphen nicht beendet werden Ist in so einem unereichbaren Teilgraphen ein Knoten der mit protokollieren soll f hrt das zu einem unvollst ndigen Protokoll Um dies zu verhindern h tte der Benutzer zwar die M glichkeit diesen Knoten als Beobachter zu markieren Allerdings m sste dieser Knoten dann auch mitentscheiden wann die Simulation zu Ende ist Wenn er das nicht kann oder nicht soll gibt es ein Problem Um das zu l sen bietet Lethe eine weitere Klasse von besonders markierten Knoten die sogenannten Protokollierer Diese werden vom Scheduler neben den Beobachtern regelm ig als initiale Knoten gew hlt spielen aber keine Rolle bei der Festlegung des Endes der Simulation 19 3 Systementwurf 3 1 5 Verteilung Wie der letzte Absatz in Abschnitt 3 1 2 erkl rt besteht eine Simulation im Allge meinen aus einer Menge von Runden die sich untereinander in den Einstellungen der Knoten unterscheiden Dieser Begriff einer Runde besitzt im Kontext von Lethe genau diese Bedeutung Jeder Knoten bekommt am Anfang jeder Runde seine vom Benut zer vorgegebenen Einstellungen Das Aussehen dieser Einstellungen wird vom jeweiligen Entwickler festgelegt vgl 41 Di
48. Quellcode berset zen und in einem zweiten Schritt die daraus entstanden Bibliotheken zusammenlinken lassen Schl gt einer der beiden Schritte fehl wird der Benutzer dar ber informiert Leider bekommt er dabei die Ausgaben des Compilers oder Linkers zu sehen und muss dar aus erkennen wo der Fehler liegt Abschnitt 6 4 2 diskutiert wie der Benutzer dabei unterst tzt werden kann Damit nur der ben tigte Benutzercode bersetzt und mit in das Simulationsprogramm gelinkt wird muss der Generator am Anfang eine Konfigurationsdatei f r das Buildsy stem erzeugen in der die Abh ngigkeiten in geeigneter Form enthalten sind Wie Abschnitt 3 1 3 diskutiert muss der Hypergraph aus der Simulationsbeschreibung im Speicher aufgebaut werden damit das Scheduling funktioniert Ein entsprechender Algorithmus der Laufzeitumgebung einer Simulation muss generisch sein um jede m g liche Simulationsbeschreibung verarbeiten zu k nnen Das ist komplex und bringt dabei keinen Vorteil gegen ber der folgenden L sung Der Manager gibt dem Generator auch die Simulationsbeschreibung Damit stehen diesem alle n tigen Informationen zur Verf gung um einen spezialisierten Code zu generieren der sp ter in der laufenden Simulation den Graphen aufbaut Der generierte Code wird bersetzt und als Bibliothek mit in das Simulationsprogramm gelinkt Die Schnittstelle ber die der Manager mit dem Generator kommuniziert ist extrem einfach In einem einzigen Aufruf g
49. Thompson und Dennis Ritchie entwickelte Sprache C 4 damals weit verbreitet war hat er diese als Ausgangsbasis verwendet und um neue Konzepte erweitert Diese Konzepte hat er gr tenteils von Simula 67 5 und sp ter von Algol 37 bernommen Mittlerweile ist aus dieser Arbeit der ISO C Standard geworden ISO IEC 14882 1998 der auf dem C90 Standard von C aufbaut ISO IEC 9899 1990 C ist also bis auf wenige Details eine Obermenge von C Die Kenntnisse ber die Sprache C sind so weit verbreitet dass eine Einf hrung im Rahmen dieser Arbeit nicht n tig ist Die oben erw hnten neuen Konzepte werden allerdings f r das Verst ndnis von Kapitel 4 ben tigt und sollten deshalb bei Bedarf angeeignet werden Deshalb sind sie im folgenden mit einem jeweiligen Verweis auf das jeweils entsprechende Kapitel im Buch von Bjarne Stroustrup 35 aufgelistet 10 2 6 Numerische Bibliotheken Klassen Das sind die zentralen Strukturen der objektorentierten Programmierung Ka pitel 10 Vererbung Ein wichtiger Mechanismus der objektorentierten Programmierung der die Spezialisierung oder Verallgemeneinerung von Klassen erm glicht Man spricht in diesem Zusammenhang auch von einer Ableitung Kapitel 12 Templates Ein zur Vererbung orthogonales Konzept der generischen Programmierung Es erm glicht die datentypunabhangige Formulierung von Algorithmen Kapitel 13 Ausnahmen Ein Konzept zur Fehlerbehandlung Es erm glicht eine Trennung des
50. Typen aus der Liste entspricht Wird die Option nicht gesetzt wird kein Typ ausgeschlossen o lt regex gt Nimmt eine Nachricht auf wenn der regul re Ausdruck auf die Herkunft der Nachricht passt Wird die Option nicht gesetzt wird auf das Herkunftsfeld nicht gefiltert m lt regex gt Nimmt eine Nachricht auf wenn der regul re Ausdruck auf den Inhalt der Nachricht passt Wird die Option nicht gesetzt wird auf den Inhalt nicht gefiltert b lt days gt Nimmt eine Nachricht auf wenn sie innerhalb der letzten lt days gt Tage beim Breeze Server eingetroffen ist Die Vorgabe ist ein Tag Diese Option kann nicht zusammen mit der Option c gesetzt werden s lt days gt Nimmt eine Nachricht nicht auf wenn sie innerhalb der letzten lt days gt Tage beim Breeze Server eingetroffen ist Die Vorgabe sind 0 Tage Diese Option kann nicht zusammen mit der Option d gesetzt werden c lt timestamp gt Nimmt eine Nachricht auf wenn ihr Zeitstempel j nger ist als lt ti mestamp gt Diese Option kann nicht zusammen mit der Option b gesetzt werden d lt timestamp gt Nimmt eine Nachricht nicht auf wenn ihr Zeitstempel j nger ist als lt timestamp gt Diese Option kann nicht zusammen mit der Option s gesetzt werden f lt seconds gt Diese Option aktiviert den follow Modus In diesem Modus wird der Breeze Server automatisch alle lt seconds gt Sekunden nach neuen Nachrichten be fragt Diese Option berschreibt die Optionen s un
51. Ziele von Lethe ist es einen m glichst gro en Anwenderkreis zu erreichen Deshalb stellt es an das Netzwerk in dem es eingesetzt wird fast keine Anforderun gen Es ben tigt lediglich POSIX kompatible ISO 9945 Systeme wobei die einzelnen Systeme im Netzwerk verschieden sein d rfen Au erdem steht Lethe unter der GNU General Public Licence 16 der Free Software Foundation 12 so dass so gut wie keine lizenzrechtlichen Hiirden existieren 1 1 Aufteilung und Gliederung Das Lethe Projekt ist zu umfangreich um in einer einzigen Diplomarbeit ausreichend behandelt werden zu k nnen Aus diesem Grund besch ftigen sich zwei Diplomarbeiten mit diesem Thema Die Arbeit von Stephanie Wist 41 deckt die Themen um das verteilte System und das Anwenderprogramm ab Die vorliegende Arbeit k mmert sich um das Framework Die Schnittpunkte zwischen diesen beiden Teilen werden jeweils aus der entsprechenden Perspektive in beiden Arbeiten behandelt Diese Arbeit ist folgenderma en gegliedert das zweite Kapitel erkl rt zuerst welche alternativen L sungen existieren und warum diese den Anforderungen nicht gerecht werden Au erdem liefert dieses Kapitel kurze Einf hrungen in relevante Themengebiete und verweist dabei ggf auf weiterf hrende Literatur Der Systementwurf in Kapitel 3 diskutiert wie die Anforderungen umgesetzt und die dabei entstehenden Probleme gel st werden Das nachfolgende Kapitel 4 ber die Imple mentierung besch f
52. ante vgl Abschnitt 3 1 7 e die Konfiguration f r jeden Knoten vgl Abschnitt 3 1 10 e die Anzahl der Runden und pro Runde die Einstellungen f r alle Knoten vgl Abschnitt 3 1 5 e die Anzahl der Phasen pro Runde vgl Abschnitt 3 1 7 e pro Phase die Menge der aktiven Ports vgl Abschnitt 3 1 7 Beobachter vgl Abschnitt 3 1 4 Protokollierer vgl Abschnitt 3 1 4 Knoten die als neue Leser an einer Kante eine leere Kante sehen sollen vgl Abschnitt 3 1 7 l Auf welche Weise diese Informationen angeben werden m ssen und wie diese ihren Weg zum Manager finden ist wie eingangs in diesem Kapitel bereits erw hnt Teil der Diplomarbeit von Stephanie Wist Wichtig f r diese Arbeit ist nur dass der Manager der Simulation diese Informationen zukommen l sst 3 2 Das verteilte System Die folgenden Abschnitte geben eine bersicht ber die Teilnehmer des verteilten Sy stems die f r diese Arbeit relevant sind und im Folgenden als ICE Objekte bezeichnet werden Zus tzlich erl utern sie deren Schnittstellen f r die Kommunikation unterein ander 3 2 1 Manager Der Manager ist die zentrale Einheit im verteilten System Seine Aufgabe ist die Ver waltung der Simulationen Er sichert au erdem Zwischenzust nde und Simulationser gebnisse und ist der Ansprechpartner f r die Anwenderprogramme des Benutzers Er ist der einzige der mit den Generatoren vgl Abschnitt 3 2 3 und den Simulationsobjekten vgl Absch
53. asse ist und disku tiert warum das so sein muss Um die Verwendung beliebiger numerischer Bibliotheken zu erm glichen f hrt Ab schnitt 4 2 4 die sogenannten Arbeitstypen ein Mit Hilfe von Konvertierungsfunktionen zwischen Arbeitstypen und Basistypen wird es m glich dass ein Modul einen anderen Typ f r die Daten verwendet als der Stream Insbesondere ist es dadurch m glich dass zwei durch einen Stream verbundene Module unterschiedliche Bibliotheken verwenden Abschnitt 4 2 5 diskutiert anschlie end eine Optimierung die unn tiges Konvertieren verhindert um im Normalfall trotz Arbeitstypen eine hohe Ausf hrungsgeschwindigkeit zu erhalten 4 2 1 Der Puffer Ein Stream ist eine first in first out Warteschlange FIFO Die geschriebenen Daten m ssen unver ndert und in der Schreibreihenfolge den Lesern zur Verf gung gestellt werden Wie Abschnitt 3 1 2 erl utert muss dabei garantiert werden dass alle Leser dieselben Daten sehen F r die Implementierung der Streams sind zwei Dinge entscheidend um hohe Ge schwindigkeiten zur Laufzeit zu erreichen erstens die Verwendung von statischem Spei cher und zweitens das Prinzip keine Daten zu kopieren Die Konsequenz des ersten Punktes ist dass s mtliche dynamische Datenstrukturen wie z B Queues ausscheiden Statt dessen werden Ringpuffer eingesetzt Diese Daten struktur ist altbekannt und hat sich f r den Einsatz in FIFOs bew hrt Im Gegensatz zu einem typischen Ringpuffer bra
54. bedeutet dass es f r das Kommando suspend und falls die Simulation im Zustand RUNNING ist auch f r das Kommando createCheckpoint keine Garantie auf die Antwortzeit gibt Beim bergang vom Zustand RUNNING in den Zustand STOPPED wird nicht unterschie den ob ein Zwischenzustand erhoben wird oder nicht Dadurch bleibt der Zustandsau tomat schlicht Allerdings bedeutet das dass es f r das Kommando stop ebenfalls keine Garantie auf die Antwortzeit gibt weil wie im Fall von suspend gewartet werden muss bis die Simulation einen persistierbaren Zustand erreicht hat Daf r gibt es allerdings die Garantie dass das Kommando createCheckpoint sofort beantwortet wird wenn sich die Simulation im Zustand STOPPED befindet Ist die Simulation der aktuellen Runde zu Ende geht das Simulationsobjekt von alleine in den Zustand FINISHED und informiert den Manager Der kann sich dann die Simulationsergebnisse bei Bedarf auch wiederholt geben lassen getResults Er kann au erdem eine neue Runde anfangen start oder einen Zwischenzustand laden und fortsetzen resume lassen Der Manager kann sich zu jedem Zeitpunkt Informationen ber den aktuellen Status einer Simulation geben lassen getStatusInformation Dazu geh ren der Zustand in dem sich die Simulation befindet sowie Angaben zur Laufzeit und der Fortschritt Im Falle eines Fehlers werden au erdem n here Informationen zu dessen Ursache geliefert Schlie lich kann der Manager den Simulationsprozess
55. d d 88 B 2 Breeze Server h Zeigt eine Hilfe zu den Optionen und beendet das Programm 89 Anhang C Verwendete Software Zur Entwicklung von Lethe und zur Erstellung dieser Diplomarbeit wurde eine Reihe von freier Software eingesetzt die ich an dieser Stelle nennen m chte Debian GNU Linux http www debian org Dia http www gnome org projects dia GNU Compiler Collection http gcc gnu org GNU make http www gnu org software make gnuplot http www gnuplot info KTEX http www latex project org Subversion http subversion tigris org The GNU Project Debugger http www gnu org software gdb The Internet Communication Engine http zeroc com trac http www edgewall com trac Vim http www vim org Vim KTEX http vim latex sourceforge net Xfig http www xfig org Xpdf http www foolabs com xpdf F r die bersetzung der KTEX Dateien wurde das TEX Framework von Prof Dr Hermann H rtig der TU Dresden verwendet http os inf tu dresden de mp26 download DA latex template tgz 91 Index Ableitung 11 Arbeitstyp 37 40 ARQ 21 Assertion 29 Ausnahme 11 Basistyp 37 39 Beobachter 14 18 Blockgr e 38 Breeze Server 33 explizites Beenden 19 Feedback Kante 21 Generator 31 Hypergraph 15 ICE Objekt 28 IceStorm 33 impliziter Aufruf 16 implizites Beenden 19 initialer Knoten 16 Kante 15 Klasse 10 Knoten 15 lastlog 34 88 Modul 35 Namensraum 11
56. d Ausblicke Dieses Kapitel liefert eine abschlie ende Diskussion ber Lethe Zuerst er rtert Ab schnitt 6 1 ob das Framework die in Kapitel 1 gestellten Anforderungen erf llt Da Le the speziell f r den Einsatz in der Kanalcodierung entwickelt wurde stellt sich die Frage welche Anwendungsgebiete es letztendlich abdeckt Diese Frage kl rt Abschnitt 6 2 Ab schnitt 6 3 erl utert anschlie end welche lizenzrechtlichen Konsequenzen die GPL f r Lethe und dessen Anwender mit sich bringt Zuletzt nennt Abschnitt 6 4 Ideen die im Rahmen dieser Arbeit aufgekommen sind und aus Zeitgr nden nicht umgesetzt wurden Sie sind m gliche Punkte f r die Weiterentwicklung von Lethe 6 1 Erf llung der Anforderungen In den Entwurf und die Implementierung von Lethe sind Erkenntnisse aus Gespr chen mit potentiellen Nutzern eingeflossen um eine m glichst praxistaugliche Schnittstelle zu erhalten Zu den Konsequenzen dieser Gespr che geh ren der caller Parameter der Behandlungsfunktionen vgl Abschnitt 4 4 2 4 und die M glichkeit einer Vorausschau auf eingehende Daten vgl Abschnitt 4 3 2 Trotz sorgf ltiger Planung und Entwicklung wird erst der praktische Einsatz von Lethe zeigen ob die Entwickler API ausgereift genug ist um alle Anwendungsf lle ab zudecken und ob sie intuitiv bedienbar ist Die bisherigen Gespr che und erste Versuche von Nutzern deuten allerdings daraufhin dass diese Anforderungen erf llt sind Die anderen Anforderungen
57. d behindert deren Wie derverwendbarkeit Deshalb muss eine M glichkeit vorgesehen werden Feedback Kanten mit Daten zu initialisieren bevor die eigentliche Simulation beginnt Da allerdings nicht auszuschlie en ist dass die Initialisierungswerte algorithmisch bestimmt werden m ssen braucht der Benutzer mehr als nur eine M glichkeit die Werte anzugeben Am besten w re eine L sung die m glichst viele Anwendungsf lle abdeckt ohne dabei kompliziert zu sein Initialisierung Abbildung 3 4 Initialisierung einer Feedback Kante Lethe kennt zu diesem Zweck das Konzept von Phasen Eine Runde einer Simulation besteht aus beliebig vielen Phasen Jeder Knoten kann pro Phase aktiv oder inaktiv f r jede ein und ausgehende Kante sein Damit daf r ein handlicher Begriff existiert definiert Lethe einen Port als das Verbindungsst ck zwischen einem Knoten und ei ner Kante Aktiv oder inaktiv ist damit pro Phase eine Eigenschaft der Ports die der Benutzer festlegt Beim bergang von einer Phase in die n chste bleiben die Daten in den Kanten erhalten Die Simulation in Abbildung 3 4 besteht z B aus zwei Phasen In der ersten Phase ist nur der eine Port des Initialisierungsknotens aktiv In der zweiten Phase ist dieser Port dann inaktiv und daf r alle anderen aktiv Damit ist die Kante vom Decoder zum Encoder am Anfang der zweiten Phase vorinitialisiert Beendet ein Knoten w hrend einer Phase sind alle seine Ports ab diesem Zeitpunkt
58. dar Der Speicherbereich zwischen dem 43 4 Implementierung Schreibzeiger und dem nachsten Lesezeiger wird von niemand anderem verwendet da es nur einen Schreiber in jeder Phase gibt und die Lesezeiger den Schreibzeiger nicht berholen k nnen Der Speicherbereich zwischen einem Lesezeiger und dem Schreibzei ger wird maximal lesend von anderen Modulen verwendet da der Schreibzeiger keine Lesezeiger tiberholen kann Da die Lesezugriffe der einzelnen Module unabhangig von einander sind ist auch dieser Fall unproblematisch Greift ein Modul wahrend eines Aufrufs mehrmals auf einen Stream zu so muss der Entwickler aufpassen Existiert zum Zeitpunkt des zweiten Zugriffes das erste Vektor Objekt noch so enthalt das zweite Vektor Objekt exakt dieselben Daten Wie Abschnitt 4 3 2 beschreibt wird dem Entwickler allerdings empfohlen w hrend eines Aufrufs ma ximal einmal auf einen Stream zuzugreifen M chte er dennoch mehrmals zugreifen muss er geeignete G ltigkeitsbereiche der Vektor Objekte verwenden Es ist wichtig dass Zugriffe auf Streams ausschlie lich ber Vektor Objekte geschehen Bei einem direkten Zugriff ber den Zeiger eines Objektes aus dem Vektor riskiert der Entwickler Probleme beim Umbruch am Pufferende Sollte es f r eine Bibliothek n tig sein einen Zeiger auf den Datenbereich zu haben bleibt dem Entwickler nichts anderes brig als einen lokalen Puffer anzulegen und die Daten aus dem Vektor dort hinein zu kopieren
59. das System ist unbenutzbar alert ein sofortiger Benutzereingriff ist erforderlich critical ein kritisches Freignis ist eingetreten error ein Fehlerereignis ist eingetreten warning es ist ein Ereignis eingetreten das Probleme machen k nnte notice es ist ein normales aber dennoch wichtiges Ereignis eingetreten info es ist ein normales Ereignis eingetreten 33 3 Systementwurf debug es ist ein Ereignis eingetreten das zum Zweck der Fehlersuche festgehalten wird Zus tzlich zum Breeze Server geh ren publish und lastlog zwei Konsolenprogramme zum Versenden und Abfragen von Lognachrichten zum Umfang von Lethe Vor al lem Letzteres kann vom Benutzer direkt eingesetzt werden um ber Ereignisse in den Simulation auf dem Laufenden zu bleiben Der Anhang B 2 beschreibt diese beiden Programme und die Konfigurationsm glichkeiten des Breeze Servers 34 4 Implementierung Dieses Kapitel besch ftigt sich mit der Umsetzung der im Entwurf gefundenen L sungen Zuerst kl rt Abschnitt 4 1 in welcher Programmiersprache Lethe implementiert ist Anschlie end er rtert Abschnitt 4 2 die Implementierung der Kanten die sogenannten Streams Dort stellen sich die Fragen nach der Gr e des Puffers und der Persistierung des Zustandes Da Streams die von den Knoten verwendeten Daten transportieren m s sen stellt sich au erdem die Frage wie man die Verwendung von beliebigen numerischen Bibliotheken erm glichen kann Bei der Diskussion die
60. den Beginn einer neuen Phase informiert damit er sich geeignet verhalten kann vgl Abschnitt 3 1 7 26 3 1 Die Simulation Aufruf user_trigger Jeder Knoten wird entweder explizit vom Scheduler oder impli zit von einer Kante wiederholt gerufen Wahrend eines Aufrufes kann der Knoten entweder explizit oder implizit beenden vgl Abschnitt 3 1 3 Erfassen des Zustandes user_serialize Bei der Erfassung eines Zwischenzustandes muss jeder Knoten seinen aktuellen Zustand erfassen und ihn der Laufzeitumge bung zur Verfiigung stellen vgl Abschnitt 3 1 9 Laden des Zustandes user_deserialize Bei der Wiederaufnahme eines Zwischen zustandes muss jeder Knoten den zuvor erfassten Zustand wieder annehmen vgl Abschnitt 3 1 9 Erfragen des Fortschrittes user_getProgress Es kann sein dass der Benutzer einen berblick ber den Fortschritt der Simulation haben m chte Neben der Nummer der aktuell laufenden Phase ist es dabei von Interesse wie weit diese Phase fort geschritten ist Da ihr Ende der Laufzeitumgebung vorab nicht bekannt ist kann Lethe diese Information nicht selbst ndig liefern Deshalb fragt es alle Knoten wie viel Prozent der Phase ihrer Meinung nach schon erledigt sind Wenn ein Knoten keine Aussage ber den Fortschritt machen kann ist 100 die passende Antwort da die Laufzeitumgebung von allen Angaben das Minimum w hlt Welche Aussa gekraft der Fortschritt f r den Benuzter besitzt liegt an der jeweiligen Sim
61. den Knoten erm glichen Abschnitt 2 3 diskutiert die be kannten M glichkeiten f r dieses Multitasking und kommt zu dem Schlu dass ein ereignisbasierter Simulator die schnellste dieser M glichkeiten ist Die Definition von geeigneten Ereignissen ist allerdings nicht trivial denn nach der g ngigen Definition vgl Abschnitt 2 2 existiert neben den Ereignissen kein zweiter Informationsweg zwischen den Teilnehmern einer Simulation Im Fall von Simulationen in der Kanalcodierung f hrt das aber zu Problemen So kann es z B sein dass eine Quelle einzelne Zahlen erzeugt der Encoder aber immer gro e Tupel von Zahlen lesen m chte Bei Blockcodes 2 ist dies z B der Fall Es ist unklar wie in einem solchen Fall die Freignisse zu definieren sind Entweder muss die Quelle Teilereignisse erzeugen oder der Encoder muss mehrere Ereignisse auf einmal bearbeiten Alternativ kann ein Hilfsknoten eingef hrt werden der aus mehreren Ereignissen der Quelle ein Ereignis f r den Encoder erzeugt Diese L sung erh ht allerdings den ohnehin schon erheblichen Aufwand der f r die Erzeugung die Verwaltung in der Warteschlange und die Zustellung von Ereignissen entsteht Da sich Lethe ausschlie lich auf Simulation in der Kanalcodierung konzentriert kann es diesen Problemen aus dem Weg gehen und einen in der Literatur f r Simulationen un typischen Ansatz verwenden Die Idee von Ereignissen und einem zentralen Entscheider wird aufgegeben Statt dessen orienti
62. der Kanal nicht welche anderen Knoten sich an seinem Eingang und seinem Ausgang befinden Aus Gr nden der Wiederverwendbarkeit der Algorithmen sollte das auch prinzipiell so sein Im Graphen aus Abbildung 3 1 ist dieses Prinzip f r die Quelle allerdings verletzt So h ngt die Anzahl der ausgehenden Kanten davon ab ob eine Senke vorhanden ist oder nicht Um die Logik der Verwendung innerhalb eines Graphen aus den Algorith men in den Knoten fern halten zu k nnen muss das Modell zu einem Hypergraphen vgl Abschnitt 2 4 erweitert werden Eine Kante kann dann mehrere Leser haben Da bei muss die Laufzeitumgebung garantieren dass alle Leser die gleichen Daten sehen Abbildung 3 2 zeigt wie der Graph aus Abbildung 3 1 korrekt aussehen muss Abbildung 3 2 Der Hypergraph des Fallbeispieles Jeder Knoten kann eine Konfiguration und Einstellungen besitzen Die Konfiguration des Encoders aus dem Fallbeispiel ist die Generatormatrix die dessen Realisierung als Schieberegister beschreibt Damit kann derselbe Knoten f r die Simulation beliebiger 15 3 Systementwurf Faltungscodes verwendet werden Die Einstellung des Kanals aus dem Fallbeispiel ist die Rauschleistung die er verwenden soll In mehreren Runden derselben Simulation kann somit der gesuchte Verlauf des Fehlerwahrscheinlichkeit ermittelt werden 3 1 3 Das Scheduling Die Laufzeitumgebung muss das gleichzeitige und voneinander unabh ngige Ablaufen der einzelnen Algorithmen in
63. die bei der bersetzung des Basistyps mit verwendet werden Allerdings ist das f r das Beispiel nicht n tig 4 2 5 Vermeidung von Konvertierungen Die obigen Konvertierungen verbrauchen Laufzeit Zum einen weil die entsprechen den Berechnungen durchgef hrt werden m ssen und zum anderen weil es sich dadurch nicht mehr vermeiden l sst zu kopieren vgl Abschnitt 4 3 1 Da bei jeder Lese und Schreiboperation eine Konvertierung durchgef hrt werden muss und es w hrend einer Simulation sehr viele solcher Operationen gibt sind die Kosten in der Summe signifi kant Deshalb lohnt es sich ber eine Optimierung nachzudenken die Konvertierungen vermeidet Verwenden alle Ports eines Streams denselben Arbeitstyp ist es unn tig dass beim Schreiben vom Arbeitstyp in den Basistyp hin und beim Lesen vom Basistyp in den Arbeitstyp zur ck konvertiert wird Es gen gt wenn die gepufferten Daten nur beim Erfassen des Zustandes in den Basistyp konvertiert werden damit sie mit Hilfe der ICE Laufzeitumgebung persistiert werden k nnen Die Anzahl der Konvertierungen ist damit durch die Gr e des Puffers beschr nkt Verglichen mit der Anzahl von Konvertierungen die in der Summe durch die Lese und Schreiboperationen zustande kommen ist das eine erhebliche Reduzierung Um diese Tatsache auszunutzen ist ein Stream neben dem Basistyp mit dem Puffertyp parametrisiert Der Puffertyp ist dabei der Typ den der Puffer des Streams verwalten k nnen muss
64. die eine bessere Laufzeit oder einen geringeren Aufwand gegen ber allgemeingehaltenen Ans tzen mit sich bringen Zweitens soll es aus Gr nden der Robustheit und einer flexiblen Verteilung der Simula tionen m glich sein von einer laufenden Simulation einen Zwischenzustand zu erheben der jederzeit ggf auf einem anderen Computer fortgesetzt werden kann Das muss in einer plattformunabh ngigen Art und Weise geschehen damit zum einen beliebige und zum anderen heterogene Hardwarelandschaften unterst tzt werden Die Diskussionen in diesem Abschnitt werden zur besseren Verst ndlichkeit von ei nem einfachen Beispiel begleitet Abschnitt 3 1 1 stellt den Ausgangspunkt vor Sp tere Abschnitte modifizieren dieses Beispiel stellenweise um spezielle Aspekte des System entwurfs veranschaulichen zu k nnen Das f r die Simulationen verwendete Modell muss zugleich einfach und m chtig sein Abschnitt 3 1 2 erkl rt warum der Hypergraph vgl Abschnitt 2 4 diese beiden Eigen schaften besitzt In seinen Knoten befinden sich dabei die von den Entwicklern definier ten Algorithmen der Kanalcodierung die ber die Kanten miteinander kommunizieren In welcher Weise das Multitasking zwischen den Knoten funktioniert diskutiert Ab schnitt 3 1 3 Insbesondere stellt sich dabei heraus dass ein in der gesichteten Literatur nicht erw hnter Algorithmus f r das Scheduling von Simulationen im Fall von Lethe den geringsten Aufwand und die geringsten Laufzeitkost
65. diese Tatsache transparent f r den Entwickler Beim Zugriff ber den Indexoperator k nnen nun allerdings die folgenden Aufgaben erledigt werden Erstens wird eine optionale Bereichspr fung vorgenommen um definiert reagieren zu k nnen wenn der Entwickler einen Fehler macht und zu gro e Indizes verwendet Die berpr fung findet als Assertion statt so dass sie bei Bedarf vom Compiler wegoptimiert werden kann Zweitens kann bei einem Zugriff der ber das Ende des Puffers hinausgehen w rden der Umbruch an den Pufferanfang durchgef hrt werden Hierf r ben tigt der Vektor In formationen ber die Gr e des Puffers Diese sind zusammen mit dem g ltigen Bereich und dem Zeiger in den Puffer Parameter des Kontruktors 42 4 3 Ports Drittens kann auf transparente Weise eine Typkonvertierung durchgef hrt werden F r den ReadVector ist das trivial Der Indexoperator gibt ein Objekt des Arbeits typs zur ck verwendet zur R ckgabe allerdings ein Objekt des Basistyps Falls sich die beiden Typen unterscheiden sorgt der Compiler daf r dass der Castoperator des Ba sistyps gerufen wird vgl Abschnitt 4 2 4 Die Daten werden dadurch effektiv kopiert Unterscheiden sich die beiden Typen nicht erzeugt der Compiler Code der das Objekt unver ndert und ohne Kopieren durchreicht Der WriteVector muss einen etwas gr eren Aufwand treiben Das liegt daran dass ein Entwickler erwartet dass er den Indexoperator auch f r Lesezugriffe ve
66. digen Algorithmus steht Ein Pfeil bedeutet dass die damit verbundenen Rechtecke ber diesen Weg in der eingezeichneten Richtung kommunizieren Diese Darstellung ist intuitiv und erfahrungsgem m chtig genug um die allermeisten F lle abbilden zu k nnen 14 3 1 Die Simulation Es liegt also nahe den gerichteten Graphen als Modell fiir Simulationen in der Kanal codierung zu verwenden Er besteht aus einer Menge von Knoten und einer Menge von Kanten mit einer Richtung die jeweils genau zwei Knoten miteinander verbinden Die Idee ist dass die Algorithmen der Simulation in den Knoten ablaufen und die Kanten eine Infrastruktur zur Kommunikation der Knoten untereinander aufbauen Jede Kante besitzt folglich einen Puffer der die Ausgaben des schreibenden Knoten dem lesenden als Eingabe zur Verf gung stellt Abbildung 3 1 zeigt den Simulationsgraphen f r das Fallbeispiel Abbildung 3 1 Ein Simulationsgraph Die Algorithmen in den Knoten sind also beliebige Abbildungen von k Eing ngen auf n Ausg nge wobei entweder k oder n null sein kann Im Fallbeispiel nimmt der Algorithmus im Kanal fortlaufend Zahlen vom Encoder entgegen addiert gaussverteilte Zufallszahlen dazu und stellt das Ergebnis dem Decoder zur Vef gung Der Kanal ver wendet sinnvollerweise jedes Mal eine andere Zufallszahl Damit das m glich ist m ssen die Knoten zustandsbehaftet sein Die obige Beschreibung des Kanals ist nicht pr zise Denn eigentlich wei
67. e muss dazu gekl rt werden wie eine Abbildung der Verwaltungsklassen vgl Abschnitt 4 4 1 aussehen kann Eine weitere zentrale Frage ist ob der gesamte Zustand eines in Matlab geschriebenen Moduls berhaupt erfassbar ist Falls eine Matlab Bibliothek keinen Zugriff auf interne Zust nde gew hrt ist das ein Problem Denn eine vollst ndige Erfassung des Zustandes ist entscheidend f r die Funktionalit t von Lethe vgl Abschnitt 3 1 9 Wichtig f r eine solche Zwischenschicht ist die Frage wieiel Laufzeit durch sie verloren geht Immerhin wird sie w hrend einer Simulation sehr oft durchlaufen Sind die Kosten zu hoch kann sich daraus je nach Anforderung ergeben dass die Matlabunterst tzung unbrauchbar ist Alles in allem erfordert die Unterst tzung von Matlab zwar einigen Aufwand scheint aber prinzipiell m glich zu sein 6 4 5 Beschleunigung des Generators Der Generator erh lt den Quellcode der zur Ausf hrung kommen soll von den Source Services vgl Abschnitt 3 2 4 Die momentane Implementierung des Generators beginnt 72 6 4 Ausblicke f r jede Simulation mit einem leeren Verzeichnis in das die Source Services den Quellco de kopieren Deshalb m ssen die Laufzeitumgebung und alle verwendeten Module und Typen jedesmal bersetzt werden Die bersetzungszeit ist verglichen mit der Laufzeit der Simulation kurz Allerdings muss der Benutzer diese Zeit abwarten um zu wissen ob seine Simulation erfolgreich startet
68. e zentrale Eigenschaft von Runden ist dass sie alle voneinander unabh ngig sind Damit eignen sie sich ideal f r eine parallele Berechnung denn die Verteilung der Runden einer Simulation auf mehrere Computer oder mehrere Prozessoren ist embarrassingly parallel vgl Abschnitt 2 2 Nach welcher Strategie Lethe das macht ist Thema von 41 Eine automatisierte zeitliche Verteilung mit einer feineren Granularit t wird von Lethe aus zwei Gr nden nicht unterst tzt Erstens wei die Laufzeitumgebung nicht wann eine Runde zu Ende ist vgl Abschnitt 3 1 4 Damit ist es unklar wie eine Runde aufgeteilt werden kann Zweitens kann es f r das Ergebnis einer Simulation eine Rolle spielen ob eine Runde am St ck oder in mehrere Teile aufgespaltet simuliert wird Denn im letzten Fall besitzt ein Knoten am Anfang eines Teils einen initialen Zustand der vom Zustand am Ende des vorherigen Teils abweichen kann Nur wenn f r alle Knoten gilt dass diese Abweichung das Ergebnis nicht verf lscht kann eine Runde parallelisiert werden Da die automatisierte Suche nach einer geeigneten Aufspaltung vermutlich ein nicht entscheidbares Problem ist verfolgt Lethe diesen Ansatz nicht weiter Ob die Vermutung zutrifft wird im Rahmen dieser Arbeit allerdings nicht entschieden Eine verbleibende M glichkeit ist dass der Benutzer eine Aufspaltung manuell durchf hrt vgl Abschnitt 6 4 3 Denkbar ist auch eine r umliche Verteilung der Knoten auf mehrere Comput
69. eder erst Daten vom Kanal um arbeiten zu k nnen Auf diese Weise werden die drei Knoten unendlich lange im Kreis herum aufgerufen Um das zu verhindern muss sich z B der Encoder anders verhalten So kann er beim allerersten Aufruf initiale Feedback Daten annehmen anstatt sie ber die Feedback Kante zu lesen Abschnitt 3 1 7 beschreibt eine Alternative dazu Es ist zu vermuten dass eine zirkul re Warteabh ngigkeit immer eine Verklemmung darstellt deren Ursache im Verhalten der Knoten dem Aufbau der Simulation oder einer ungen genden Vorinitialisierung zu suchen ist Deshalb handelt es sich dabei um einen Logikfehler in der Simulation und nicht um eine Einschr nkung der M glichkeiten von Lethe Die Erfahrung wird zeigen m ssen ob diese Vermutung uneingeschr nkt zutrifft F r Lethe bedeutet das dass es das Verbot von zirkul ren Warteabh ngigkeiten durchsetzt um robust auf solche F lle reagieren zu k nnen Es erkennt wenn ein Knoten der bereits im Wartestack vorhanden ist implizit aufgerufen wird und bricht daraufhin die Simulation ab Der Benutzer wird anschlie end dar ber informiert und erh lt f r die Fehlersuche eine Auflistung der wartenden Knoten 21 3 Systementwurf 3 1 7 Phasen Wie Abschnitt 3 1 6 erkl rt ist es zur Vermeidung von Verklemmungen manchmal n tig dass einer der beteiligten Knoten eine Sonderbehandlung f r seinen ersten Aufruf vorsieht Das erh ht allerdings die Komplexit t der Knoten un
70. ei entspricht dem Namen des Basistyps Eine weitere Datei in dem Verzeichnis des Basistyps ist die sogenannte config mak die zum Buildsystems geh rt Abschnitt 4 2 4 erkl rt welche Rolle sie spielt Die Header Datei f r einen Basistyp wird im Folgenden als die Basistyp Datei bezeichnet F r die Implementierung der Streams bedeutet die freie Wahl der Basistypen dass der Puffer generisch sein muss um Daten von beliebigem Typ verwalten zu k nnen Ein Stream ist also ein generischer Datencontainer In C existiert f r solche Zwecke das Konzept der Templates Der Vorteil gegen ber alternativen M glichkeiten wie z B die Verwendung einer abstrakten Oberklasse f r Daten ist die Effizienz zur Laufzeit Alle n tigen Informationen ber die verwendeten Typen sind zum Zeitpunkt der bersetzung bekannt so dass zur Laufzeit keine Entscheidungen mehr dar ber getroffen werden m ssen Die gepufferten Daten in einem Stream geh ren zum Zustand des Streams Damit dieser Zustand persistiert werden kann vgl Abschnit 3 1 9 muss es der ICE Laufzeit umgebung m glich sein die Daten des jeweiligen Typs zu serialisieren Deshalb generiert Lethe aus der Typspezifikation des Entwicklers zus tzlich eine Datei die den Typ in der ICE Sprache f r Schnittstellen spezifiziert Slice vgl ICE Benutzerhandbuch Kapitel 4 21 Der Slice Compiler kann aus diesen Informationen die Funktionen zum Serialisie ren und Deserialisieren generieren Der Basistyp ist
71. elevant sind Dar berhinaus maximiert sie die Wiederverwendbarkeit der Module so dass sie sich in vielen verschiedenen Simulationen verwenden lassen Die Parallelisierung einer Simulation findet an den Grenzen der voneinander unab h ngigen Runden statt und ist somit trivial Nichtsdestotrotz wird die Wartezeit auf die Simulationsergebnisse dadurch deutlich gesenkt F r jede Runde existiert ein Simulati onsobjekt im verteilten System Aus Robustheitsgr nden sind alle Simulationsobjekte unabh ngig voneinander Die Proxies erh hen die Robustheit zus tzlich indem sie die Simulationen berwachen und bei Bedarf kontrolliert beenden Au erdem kann der Be nutzer bei einem Abbruch einer Simulation durch sie den Grund daf r erfahren Zuletzt existiert noch ein zentraler Logging Server der es dem Benutzer auf einfache Weise erm glicht ber Ereignisse in seinen Simulationen informiert zu werden Der praktische Einsatz von Lethe wird zeigen m ssen inwiefern manche Vermutun gen die beim Entwurf des Frameworks gemacht wurden zutreffen Bisher deuten erste Gespr che mit potentiellen Nutzern darauf hin Dennoch kann das f r die Weiterent 75 7 Zusammenfassung wicklung von Lethe bedeuten dass nachtr gliche nderungen des Entwurfs n tig sind Eine mit Sicherheit noch anstehende Aufgabe ist den Prototypen der im Rahmen dieser Arbeit implementiert wurde zur Produktreife zu f hren 76 Anhang A GNU PTH GNU PTH steht fiir die
72. em Benutzer sich auf die eigentlichen Probleme zu konzentrieren 20 3 1 Die Simulation 3 1 6 Feedback Kanten Bei den ARQ Verfahren 3 passt der Encoder die Menge der Redundanz an die aktuellen Eigenschaften eines ver nderlichen Kanals an Dazu muss der Decoder dem Encoder mit teilen wie gut oder wie schlecht die Decodierung der Daten gelingt In der Summe wird dadurch bei gleichbleibender Fehlerwahrscheinlichkeit weniger Redundanz bertragen Abbildung 3 3 zeigt dass die zugeh rige Feedback Kante einen Zyklus im Hypergraphen dieser Simulation erzeugt Dieser Abschnitt diskutiert welche Konsequenzen sich daraus ergeben Abbildung 3 3 Der Hypergraph eines ARQ Verfahrens Abschnitt 3 1 3 braucht f r die Korrektheit des Schedulings ein Verbot von zirkul ren Warteabh ngigkeiten Der Grund daf r ist dass es andernfalls zu einer unendlichen Folge von impliziten Aufrufen entlang des Zykluses kommen kann Die Simulation w rde damit nie terminieren Im Beispiel der ARQ Verfahren kann es folgenderma en zu einer zirkul ren Warteab h ngigkeit kommen der Decoder braucht zuerst Daten vom Kanal Erst danach kann er die f r den Encoder notwendigen Daten bestimmen und sie zur Verf gung stellen Allerdings braucht der Kanal seinerseits Daten vom Encoder M chte jetzt der Encoder erst Feedback Daten vom Decoder bevor er entscheidet wie er die Daten von der Quelle codiert wird wiederum der Decoder gerufen Dieser braucht aber wi
73. en bringt Die Frage nach der Terminierung des Schedulings ist nicht trivial Deshalb diskutiert Abschnitt 3 1 4 wie das Ende einer Simulation definiert ist Dazu f hrt er die Begriffe 13 3 Systementwurf des Beobachters und des Protokollierers ein Beides sind optionale Eigenschaften eines Knotens die zu einer Sonderbehandlung durch das Scheduling f hren Die Menge der Beobachter bestimmt ber das Ende der Simulation F r die Protokollierer ist gew hr leistet dass sie bis zum Ende an der Simulation teilnehmen Eine M glichkeit die Simulationsgeschwindigkeit zu steigern ist es die Simulation zu verteilen um sie parallel durchzuf hren Abschnitt 3 1 5 f hrt dazu den Begriff der Runden ein und diskutiert warum im Falle von Lethe ausschlie lich an den Grenzen dieser voneinander unabh ngigen Teile effizient parallelisiert werden kann Abschnitt 3 1 6 besch ftigt sich anschlie end damit warum Zyklen im Graphen ben tigt werden und wie das Scheduling mit dadurch m glichen Verklemmungen umgeht Da sich bei Zyklen die Frage nach M glichkeiten zur Vorinitialisierung von Kanten stellt f hrt Abschnitt 3 1 7 die Begriffe der Phasen und der Ports ein Die zentrale berlegung dabei ist dass w hrend einer Phase jeweils nur ein Teilgraph aktiv ist Die Vorinitialisierung von Kanten f hrt auf das Problem von mehreren Schreibern hin Abschnitt 3 1 8 erkl rt warum dieses Problem direkt von den Eigenschaften des Schedulings herr h
74. er Dann m ssen alle Daten die ber Kanten von einem Teilgraphen in den anderen flie en ber das lokale Netzwerk transportiert werden Da w hrend einer Simulation sehr viele Daten verarbeitet werden ist der Aufwand daf r erheblich Die positive Wirkung der Vertei lung auf die Laufzeit wird also durch den steigenden Aufwand f r den Datentransport relativiert Dazu kommt dass in den meisten Simulationen der gr te Rechenaufwand im Decoder steckt Eine erhebliche Beschleunigung durch die Verteilung der anderen Knoten ist also in den meisten F llen nicht zu erwarten Da dieser Ansatz also nicht gewinnbringend zu sein scheint wird er in dieser Arbeit nicht weiter verfolgt Es bleibt also dabei dass ausschlie lich an Rundengrenzen parallelisisert wird Auf Grund der Unabh ngigkeit der Runden ist keine Kommunikation zwischen den einzel nen Teilsimulationen n tig Deshalb ist das Verh ltnis zwischen den Laufzeiten einer vollst ndig parallelisierten Simulation und der dazugeh rigen nicht parallelisierten Si mulation antiproportional zur Anzahl der Runden Das ist in den meisten F llen bereits ein erheblicher Gewinn Dieser Sachverhalt ist nat rlich trivial Nicht umsonst bem hen sich Kanalcodierer um eine gleichzeitige Berechnung der unabh ngigen Teile ihrer Simulationen Die Leistung von Lethe an dieser Stelle ist allerdings dass die Verteilung automatisiert gemacht wird Das ist komfortabler weniger fehleranf llig und erlaubt es d
75. eratoren der GSL Deshalb m ssen am Anfang der Modul Datei die entsprechen den Header Dateien eingebunden werden 1 2 include lt gsl gsl_complex_math h gt include lt gsl gsl_randist h gt Die f r die Verwendung der GSL n tigen Bibliotheken werden schon auf Grund der config mak des Basistyps vom Buildsystem ber cksichtigt vgl Abschnitt 4 2 4 Au erdem sind f r das Beispielmodul keine speziellen Compileroptionen n tig Die config mak des Moduls sieht deshalb folgenderma en aus LDFLAGS CCFLAGS 48 4 4 Module 4 4 2 3 Der Logger Wie Abschnitt 3 2 6 erl utert bringt Lethe einen zentralen Logging Service mit Damit Entwickler diesen verwenden k nnen existiert im Namensraum Core die Klasse Logger die f r jeden Nachrichtentyp eine Funktion definiert Beim Aufruf dieser Funktionen kann eine gew hnliche printf Syntax verwendet wer den Alternativ kann ein C String bergeben werden Damit im Log zu erkennen ist aus welchem Modul die Nachricht stammt definiert die Core Modul Klasse die Funktion getVertexName Sie liefert den Namen den der Benutzer bei der Erstellung der Simulation dem Knoten gegeben hat Um z B f r eine Fehlersuche zu registrieren dass irgendein Ereignis geschehen ist kann der Entwickler eine der beiden folgenden Zeilen verwenden Core Logger debug s something happened getVertexName Core Logger debug getVertexName something happened Jeder Aufr
76. erichteten Hypergraphen auf einen gerichteten Graphen einfache Kante verbunden ist Unter Ber cksichtigung der Richtungen l sst sich auf die gleiche Weise jeder gerichtete Hypergraph auf einen gerichteten Graphen abbilden Abbildung 2 1 verdeutlicht das Ein Hypergraph besitzt demzufolge dieselbe M chtigkeit wie ein Graph Er ben tigt lediglich keine Extraknoten um die gemeinsame Konnektivit t einer beliebigen Menge von Knoten darzustellen 2 5 C Wie Abschnitt 4 1 diskutiert muss ein Entwickler seine Algorithmen in C imple mentieren Dieser Abschnitt liefert deshalb einen kurzen berblick ber diese Sprache Als weiterf hrende Literatur wird das Buch Die C Programmiersprache des C Erfinders Bjarne Stroustrup 35 empfohlen Der Grund f r die Entwicklung von C war dass alle in den 70ern bekannten Programmiersprachen entweder sehr ineffizient oder sehr rudiment r waren Stroustrup erkannte das damals als all seine Versuche eine Software fiir ein Projekt zu schreiben scheiterten Der Grund war entweder dass die gew hlte Sprache keine Werkzeuge mit sich brachte um die Komplexit t der Implementierung in den Griff zu bekommen oder dass das Programm am Ende zu langsam war Damit er nie wieder solchen Problemen ausgesetzt sein w rde machte er sich daran eine neue Sprache zu entwickeln 36 Stroustrup wollte dass mit seiner Arbeit real existierende Probleme kurzfristig gel st werden k nnen Da die von Ken
77. ert sich das Scheduling am Aufbau des Hypergra phen Die Daten werden ber die Kanten transportiert und die Leser und Schreiber bei Bedarf aufgerufen Die Schedulingentscheidungen werden dabei dezentral in den Kanten getroffen weshalb ein solches Ereignis im Folgenden als ein impliziter Aufruf bezeichnet wird Das Scheduling funktioniert also folgenderma en e Der Scheduler w hlt einen beliebigen Knoten und ruft ihn Ein solcher Knoten wird im Folgenden als initialer Knoten bezeichnet e M chte ein Knoten aus einer Kante mehr Daten lesen als darin gepuffert sind so ruft die Kante ihren Schreiber so oft bis er genug Daten erzeugt hat um den Aufruf des Lesers zu befriedigen e M chte ein Knoten in eine Kante mehr Daten schreiben als der Puffer dieser Kante Platz besitzt so geht die Kante analog vor Sie ruft wiederholt einen ihrer Leser bis genug Platz im Puffer entstanden ist um den Aufruf des Schreibers durchf hren zu k nnen Dabei w hlt sie jedesmal denjenigen Leser der bisher am wenigsten gelesen hat und daher am meisten Platz im Puffer verbraucht e Ist der Aufruf des initialen Knotens beendet so beginnt der Scheduler von vorne 16 3 1 Die Simulation Die einzige Aufgabe des Schedulers besteht darin fortlaufend einen initialen Knoten zu w hlen Es l sst sich deshalb dar ber streiten ob er berhaupt noch als Scheduler zu bezeichnen ist Aus Mangel an alternativen gebr uchlichen Bezeichnungen wird dieser Algorith
78. eshalb ist es bei mehreren aktiven Schreibern an einer Kante unklar was ein Leser dieser Kante zu sehen bekommt Er kann nicht davon ausgehen dass die Daten aus der Kante abwechselnd von den je weiligen Schreibern stammen Die Schreiber m ssten deshalb Metainformationen ber die Herkunft der Daten hinzuf gen Allerdings ist diese Vermischung von Daten und Simulationslogik nicht w nschenswert und vermutlich eine potentielle Problemquelle Deshalb verbietet Lethe schlichtweg die Verwendung von mehreren aktiven Schreibern an einer Kante Es ist allerdings m glich eine Kante mit n Schreibern auf n Kanten mit je einem Schreiber abzubilden vgl Abschnitt 2 4 Damit l sst sich das Problem mit mehre ren Schreibern umgehen indem der Entwickler den Leser mit n eingehenden Kanten versieht Falls die Anzahl der Schreiber f r den Leser transparent sein muss kann der Entwickler einen Knoten entwerfen der zwischen den Schreibern und dem Leser ein geeignetes Multiplexing vornimmt 24 3 1 Die Simulation 3 1 9 Zwischenzustande Eines der besonderen Merkmale von Lethe ist die M glichkeit von einer Simulation Sicherungspunkte zu erstellen und Simulationen auf andere Computer zu migrieren Da der einzige Unterschied zwischen diesen beiden Aktionen darin besteht dass die Simulation bei einer Migration auf einem anderen Computer fortgesetzt wird verwenden beide Funktionalit ten denselben Mechanismums Die Kernidee ist dass jeder Teil einer Si
79. essungen Testkriterien Wiederholung der Messungen Verwaltungsaufwand 5 1 5 2 5 3 5 4 5 0 5 6 AQ Der Putter sis 4 1 a Sr kee ann ae ee a 4 2 2 Die Gr e eines Puffers 2 2 22 on nn nn 4 2 3 Basistypen 2 2 2 o onen rennen 4 2 4 Arbeitstypen aoaaa 4 2 5 Vermeidung von Konvertierungen 2 2 22 2 2 Ports eee 0 ee hae ee ee Reha 4 3 1 Die Vector Klassen 2 2 ee ee 4 3 2 Die Adapter Klasse 2 2 ee ee Mod lel 4 ape ae 4 aid an ek ea ew a oie as 4 4 1 Verwaltungsklassen 2222 Coon nn ee 4 4 2 Die Entwickler API gc un wa a ass a Mia ae Das Scheduling es sos u wa a na a bE RO ee Gk Don 4 5 1 Vernetzung 2 a 4 5 2 Ereignisse Co 2 oo on 4 5 3 Die call Funktion 22 22 CE non Konvertierungen 5 4 1 5 4 2 5 5 1 Erh hung der Konvertierungshaufigkeit Verwendung der Optimierung Erh hung der Blockgr e Deaktivierung der Optimierung Erh hung der Datenmenge 6 Schlu folgerungen und Ausblicke 6 1 6 2 6 3 6 4 Erf llung der Anforderungen Anwendungsgebiete o oo aa a Lizenzrecht 2 22 2 22 Con Ausblicke 2 222 Comm 6 41 Icestorml se erak p nern 6 4 2 Fehlersuche 2 22 2 CC none 6 4 3 Unterst tzung von manueller Parallelisierung 6 4 4 Unterst tzung f r Matlab 2 2 m nme 6 4 5 Beschleunigung des Generators 22 2 2 2 2 mn nennen 7 Zusammenfassung VII 35 35 36 37 38 38 39 41 42 42 44 46
80. f den Quellcode verwiesen der durch aussagekr ftige Bezeichner und geeignete Kommentare leicht verst ndlich ist Er ist dieser Arbeit auf einer CD beigef gt 4 1 Die Wahl der Programmiersprache Der Entwickler sollte die Algorithmen in derselben Sprache implementieren in der die Laufzeitumgebung geschrieben ist Alles andere kostet auf Grund von Zwischenschichten unn tig Laufzeit Da ein Anwender im Normalfall nicht bereit ist eine neue Sprache zu lernen um eine Software einzusetzen muss bei der Wahl dieser Sprache ber cksichtigt werden welche Kenntnisse typischerweise beim Anwender vorhanden sind Die Erfahrung zeigt dass bei Kanalcodierern haupts chlich Kenntnisse ber Matlab und C vorhanden sind Matlab ist wie Abschnitt 2 1 erl utert eine auf numerische 35 4 Implementierung Berechnungen spezialisierte Sprache Sie ist fiir Programme mit anderen Schwerpunk ten nicht geeignet Da die Laufzeitumgebung nahezu keine numerischen Berechnungen durchf hrt statt dessen aber die Simulation verwalten und eine Anbindung an das ver teilte System bereitstellen muss scheidet Matlab aus Allerdings ist C auch keine gute Wahl Aus Mangel an wesentlichen Konzepten muss vieles von Hand implementiert werden was zu einem umfangreichen und schwer ver st ndlichen Code f hrt Das war mitunter die Motivation f r die Entwicklung vieler neuer Programmiersprachen Eine dieser Sprachen ist C Wie Abschnitt 2 5 erkl rt ist C bis auf we
81. feststellt dass die Performance des simulierten Codes sehr schlecht ist Es sind weiterhin Anwendungsf lle denkbar bei denen nur Teile der Simulation beenden w hrend die anderen weiter laufen sollen Das ist z B der Fall wenn der Benutzer mehr als eine Senke in der Simulation platziert und die Senken verschiedene Kriterien f r das Ende verwenden Es ist einem Knoten deshalb m glich der Laufzeitumgebung mitzuteilen dass f r ihn das Ende der Simulation erreicht wurde woraufhin sie ihn aus dem Graphen entfernt Au erdem kann der Benutzer eine beliebige Teilmenge von Knoten als relevant f r die Entscheidung ber das Ende der Simulation markieren Diese Knoten werden als Beob achter bezeichnet Wurden alle Beobachter aus dem Graphen entfernt ist die Simulation zu Ende Diese Vorgehensweise ist zugleich einfach zu verstehen und sehr flexibel Eine Frage die sich hier sofort stellt ist wie der restliche Graph auf fehlende Knoten reagiert Dazu existieren die folgenden drei Regeln 1 Falls ein Lesezugriff auf eine Kante zu einem impliziten Aufruf des Schreibers f hren w rde und der Schreiber dieser Kante bereits beendet hat so entfernt die Laufzeitumgebung den Knoten aus dem Graphen falls der Knoten diesen Sonder fall nicht behandelt 2 Falls ein Schreibzugriff auf eine Kante zu einem impliziten Aufruf eines Lesers f h ren w rde und alle Leser der ausgehenden Kanten des Schreibers bereits beendet haben so entfernt die Laufzeitum
82. fordert die Ergebnisse der Simulation zu liefern 1 Lethe Result user_getResult 2 return _result 3 53 4 Implementierung Die generierte Implementierung liefert einfach das Ergebnisobjekt des Moduls zur ck Zeile 2 Falls die user_trigger Aufrufe immer auf diesem Objekt arbeiten kann der Entwickler die Funktion so verwenden Ansonsten muss er in dieser Funktion die Ergeb nisse geeignet ermitteln und in das _result Objekt schreiben 4 4 2 12 user_getProgress Die user_getProgress Funktion wird immer gerufen wenn der Benutzer ber den Verlauf der Simulation informiert werden m chte 1 float user_getProgress 2 return 1 3 Die Funktion gibt durch einen Riickgabewert zwischen 0 0 und 1 100 an wie weit die aktuellen Phase vorangeschritten ist Da Lethe von den Werten aller Module das Minimum nimmt kann der Entwickler diese Funktion unver ndert verwenden wenn sein Modul keine Aussage ber den Verlauf machen kann oder soll 4 4 2 13 Hilfsfunktionen Die Funktionen user_serialize user_deserialize user_reset und user_ getResult verwenden modulabh ngige Typen Die Laufzeitumgebung ist allerdings generisch und kann mit diesen Typen nicht umgehen Deshalb gibt es f r jede dieser Funktionen eine Hilfsfunktion mit dem Pr fix lethe_ Diese Hilfsfunktionen vermitteln zwischen generischen Byte Str men aus der Laufzeitumgebung und den typisierten Objekten des Moduls Sie dienen damit dem Komfort des
83. gebung den Knoten aus dem Graphen falls der Knoten diesen Sonderfall nicht behandelt 3 Falls ein Schreibzugriff auf eine Kante zu einem impliziten Aufruf eines Lesers f hren w rde der Leser dieser Kante bereits beendet hat und mindestens ein Leser einer ausgehenden Kante dieses Knotens noch nicht entfernt wurde so bleibt der Knoten im Graphen Die geschriebenen Daten werden nachtr glich verworfen Die Laufzeitumgebung kann den Schreiber optional ber diesen Sonderfall informieren 18 3 1 Die Simulation Wenn ein Knoten der Laufzeitumgebung mitteilt dass fiir inn das Ende der Simulation erreicht wurde dann beendet er explizit Wird ein Knoten allerdings auf Grund der obigen Regeln aus dem Graphen entfernt beendet er implizit Der Grund f r die erste Regel ist dass sich auf diese Weise Entscheidungen ber das Ende der Simulation automatisch im Graphen fortpflanzen Au erdem stellt sich die Frage was in so einem Fall sonst mit dem Knoten geschehen soll Schlie lich ist es ihm aus Mangel an eingehenden Daten nicht mehr m glich seiner Aufgabe weiterhin nach zu kommen Sollte es im Einzelfall n tig sein dass der Knoten trotzdem weitermacht so kann er seine Entfernung verhindern indem er den Sonderfall behandelt vgl Abschnitt 4 3 2 hnliches gilt f r die zweite Regel Der Grund hierf r ist dass die Arbeit eines Kno tens im Normallfall nicht mehr n tig ist wenn kein anderer Knoten mehr an seinen Daten interessiert is
84. gen Speicher gesenkt werden Der Anteil der Verwaltung an der Laufzeit geht asymptotisch gegen null Ab einer hunderfachen Blockgr e liegt die Laufzeit im Bereich von einer Sekunde und damit unterhalb der Messgenauigkeit 5 5 1 Deaktivierung der Optimierung Wenn der Verwaltungsaufwand wie im letzten Abschnitt gezeigt gegen null gehen kann dann l sst sich durch eine weitere Messreihe vielleicht genauer feststellen wie gro der Anteil der Konvertierungen an der Laufzeit ist Denn die Anzahl der Konvertierungen ist unabh ngig von der Blockgr e In dieser Messungreihe wird deshalb die Optimierung ausgeschaltet Die Eigenschaf ten der Ports entspricht denen aus Tabelle 5 7 Durch die ausgeschaltete Optimierung ergeben sich f r die Kanten wieder die Eigenschaften der ersten Messung aus diesem Kapitel vgl Tabelle 5 3 Die Ergebnisse dieser Messreihe sind in den Abbildungen 5 4 und 5 5 zu sehen Zum Vergleich sind die Ergebnisse der vorherigen Messreihe mit eigenschalteter Optimierung mit eingezeichnet 78 nit Optinierung ohne Optinierung Laufzeit Sekunden Abbildung 5 4 Vergleich mit und ohne Optimierung 65 5 Messungen 78 nit Optinierung ohne Optinierung ae 4 38 F q Laufzeit Sekunden 28 7 q 180 F 4 Abbildung 5 5 Vergleich mit und ohne Optimierung gr ere Skala Die Laufzeiten die sich ohne Optimierung ergeben bleiben wie erwartet
85. guration wie in Zeile 2 zu sehen ist abspeichert Dadurch kann in der user_trigger Funktion auf die Konfiguration des Moduls zugegriffen werden M ssen wie im Beispiel interne Strukturen aufgebaut werden sollte dies in der user_trigger Funktion geschehen Die gsl_rng_alloc Funktion aus der GSL erzeugt ein Zufallsgenerator Objekt Dabei wird durch die Konfiguration des Gausskanal Moduls gesteuert von welchem Typ der Generator sein soll Das Beispiel verwendet einen Taus worthe Zufallsgenerator 29 F r das Beispiel spielt der Typ allerdings keine weitere Rolle Er dient hier nur dem Zweck die Verwendung einer Konfiguration zu demonstrie ren Damit die Variable f r das Zufallsgenerator Objekt definiert ist muss noch folgende Zeile zur Modul Datei hinzugef gt werden 1 gsl_rng _rng 4 4 2 6 user_finish Die user_finish Funktion dient dazu eventuell belegte Ressourcen wieder frei zu ge ben Es ist garantiert dass nach dem Aufruf dieser Funktion keine andere user Funktion mehr gerufen wird 1 void user_finish 2 gsl_rng_free _rng 3 Die generierte Funktion ist leer F r das Gausskanal Modul muss der Entwickler das zuvor erzeugte Zufallsgenerator Objekt wieder freigeben Zeile 2 4 4 2 7 user_reset Die user_reset Funktion wird immer gerufen wenn eine neue Runde beginnt Das Modul erh lt dabei seine Einstellungen 1 void user_reset const Lethe Settings amp settings _settings settings 3 gsl_
86. h 2 2 Simulationsalgorithmen Auf dem Gebiet der parallelen und verteilten Simulationen sind vor allem die Publi kationen von Richard M Fujimoto ma geblich Sein Buch Parallel and Distributed Simulation Systems 13 behandelt Ideen zur Beschleunigung von Simulationen durch paralleles und verteiltes Rechnen In den ersten Kapiteln liefert er au erdem einen ber blick ber bekannte Architekturen f r Simulationen Die folgenden Definitionen und Erl uterungen beziehen sich alle auf dieses Buch Eine Simulation ist abstrakt beschrieben eine Menge von Teilnehmern die nach ge wissen Regeln untereinander Informationen austauschen Dieser Informationsaustausch findet ausschlie lich durch Ereignisse statt die von Teilnehmern ausgel st werden und bei einem empfangenden Teilnehmer Reaktionen hervorrufen Ein solches Ereignis be sitzt au er seinen simulationsspezifischen Informationen und einer Kennung f r den Empf nger einen Zeitpunkt zu dem es behandelt werden soll Gestartet wird die Si mulation durch ein initiales Ereignis Da nicht pro Teilnehmer eine Recheneinheit zur Verf gung steht muss ein sogenannter Scheduler entscheiden wann welcher Teilnehmer an der Reihe ist Au erdem muss er den Austausch der Ereignisse verwalten Im Wesent lich existieren zwei Ans tze hierf r der getaktete und der ereignisbasierte Simulator Die Architekturen der getakteten Simulatoren sind sehr schlicht F r jede Zeiteinheit der Simulation ex
87. ht den Typ DEBUG o lt origin gt Die Herkunft der Nachricht Falls diese Option nicht gesetzt wird hat die Nachricht keine Herkunft h Zeigt eine Hilfe zu den Optionen und beendet das Programm 87 Anhang B Dienste B 2 5 lastlog Mit dem Kommandozeilenprogramm lastlog kann der Benutzer Lognachrichten vom Breeze Server erfragen Dazu gibt er eine Reihe von Filterkriterien f r die einzelnen Felder der Nachrichten an Der Breeze Server liefert eine Nachricht genau dann aus wenn sie alle Filter passiert Die vollst ndige Kommandozeile sieht folgenderma en aus lastlog py p lt proxy gt n lt locator gt i lt type gt lt type gt e lt type gt lt type gt o lt regex gt m lt regex gt b lt days gt lt timestamp gt s lt days gt d lt timestamp gt f lt seconds gt h Die Bedeutungen der Optionen sind C p lt proxy gt Die Stringrepr sentation des ICE Proxies vom Breeze Servers Diese Op tion kann nicht zusammen mit der Option n verwendet werden n lt locator gt Die Stringrep rsentation des ICE Proxies vom Namensdienst Diese Op tion kann nicht zusammen mit der Option p verwendet werden i lt typliste gt Nimmt eine Nachricht auf wenn ihr Typ einem der Typen aus der Liste entspricht Anstatt die vollst ndige Liste anzugeben kann diese Option einfach weg gelassen werden e lt typliste gt Nimmt eine Nachricht auf wenn ihr Typ keinem der
88. ibt der Manager dem Generator eine Simulationsbe schreibung und erh lt nach einiger Zeit die Referenz auf das neu entstandene Simula tionsobjekt oder eine Fehlermeldung falls beim Compilieren Linken oder Starten ein Fehler aufgetreten ist 3 2 4 Source Service Das Konzept der Source Services l st das Problem der Verteilung des Quellcodes Es erm glicht die garantierte Verwendung von verschiedenen Softwareversionen im verteil 31 3 Systementwurf ten System Au erdem erlaubt es einem Benutzer seinen verwendeten Code geheim zu halten Behandelt wird dieses Konzept in der Diplomarbeit von Stephanie Wist Wichtig f r diese Arbeit ist dass der Generator den Quellcode der zur Ausf hrung kommen soll von den Source Services erh lt F r die bertragung des Quellcodes wird der IcePatch2 Dienst verwendet vgl ICE Benutzerhandbuch Kapitel 43 21 Die Informationen ber den Ort der Source Services sind in der Simulationsbeschreibung enthalten Au erdem besitzt jede Simulationsbe schreibung eine eindeutige Identifikation die vom Manager gesetzt wird Mit Hilfe dieser Identifikation wird garantiert dass der Generator die richtige Version des Quellcodes vom Source Service erh lt Der Generator muss sich also bei allen in der Beschreibung aufgelisteten Source Services unter Nennung der Identifikation melden und kann anschlie end entsprechend viele IcePatch Clients starten Am Ende dieses Vorgangs ist der richtige Quellcode loka
89. icht verwendete Algorithmen simuliert werden sollen Den dazuge h rigen Code muss die Laufzeitumgebung in diesem Fall n mlich dynamisch nachladen Wie Abschnitt 4 1 diskutiert ist dieser Teil von Lethe allerdings in C geschrieben und in dieser Sprache existiert daf r keine portable M glichkeit Deshalb m sste ei ne plattformspezifische Abstraktionsschicht eingef gt werden Das bedeutet einen extra Aufwand und erschwert die Portierung der Software Verwendet man statt dessen pro Simulation einen eigenen Prozess ergeben sich diese Nachteile nicht Erstens ist diese L sung robust gegen Fehler im Benutzercode da die einzelnen Prozesse voneinander unabh ngig sind Zweitens muss kein Code dynamisch nachgeladen werden weil von vorneherein der gebrauchte Code zu einer ausf hrbaren Datei zusammengelinkt werden kann Diese Aufgabe erledigt der Generator vgl Ab schnitt 3 2 3 Zu guter Letzt ist ein Vorteil dieser L sung dass das Scheduling zwischen den Simulationen vom Betriebssystem erledigt wird Ein solcher Prozess beherbergt genau ein Simulationsobjekt Dieses wird ausschlie lich vom Manager gesteuert Die Schnittstelle bietet alle f r Lethe essentiellen Funktionali t ten und wird als Zustandsautomat beschrieben vgl Abbildung 3 6 Eine Simulation wird genau einmal initialisiert init Dabei gibt ihr der Manager die Simulationsbeschreibung Daraufhin erstellt die Laufzeitumgebung der Simulation 29 3 Systementwurf alle n
90. id pthf_init if pth_uctx_create amp mainContext FALSE die if pth_uctx_create amp exitContext FALSE die if pth_uctx_make exitContext NULL 16 1024 NULL pthf_exit NULL NULL FALSE die F void pthf_run if number 0 die pass control to the first thread current 0 if pth_uctx_switch mainContext threads current FALSE die we reach here only if the exit handler passes control to here This is only done if no more threads are living So clean up the resources and return if pth_uctx_destroy exitContext FALSE die if pth_uctx_destroy mainContext FALSE die F 81 Anhang A GNU PTH void pthf_spawn void func void void arg char stack size_t stacksize if number MAX_NUMBER_OF_THREADS die create and setup a new context pth_uctx_t context if pth_uctx_create amp context FALSE die if pth_uctx_make context stack stacksize NULL func arg exitContext FALSE die enqueue the new thread threads number context void pthf_yield round robin int old current current if current number current 0 switch directly to the next thread this is where we save one context switch if pth_uctx_switch threads old threads current FALSE die void pthf_exit void arg 82 int i while 1 whenever we reach here a thread terminated and control was therefore passed to here if
91. igen m ssen In Regel 2b k nnen zwischen dem Zeitpunkt des Beendens des letzten Lesers und dem Zeitpunkt zu dem der neue Leser aktiv wird beliebig viele Phasen liegen denn eine Kante kann ber mehrere Phasen hinweg inaktiv sein Der Fall in dem zu Beginn der ersten Phase einer Runde alle Leser inaktiv sind wird behandelt als ob genau ein Leser zu Beginn dieser ersten Phase aktiv war und sofort beendet hat Das Beispiel aus Abbildung 3 4 ist so ein Fall Der Encoder bekommt dadurch genau den Inhalt den der Initialisierungsknoten geschrieben hat Dabei muss allerdings sichergestellt sein dass der Puffer der Kante gro genug ist um alle Daten aufnehmen zu k nnen Da nur der Benutzer wei wie viel Daten das sind bietet Lethe ihm die M glichkeit f r jede Kante eine Mindestgr e des Puffers anzugeben Die tats chliche Gr e des Puffers berechnet sich dann aus dieser und weiteren Metainformationen vgl Abschnitt 4 2 2 3 1 8 Mehrere Schreiber Am Ende von Abschnitt 3 1 3 wird erw hnt dass eine Kante maximal einen Schreiber haben kann Dennoch ist die Abbildung 3 4 in der eine Kante zwei Schreiber besitzt wie im vorherigen Abschnitt ausgef hrt korrekt Genauer formuliert muss die Aussage aus Abschnitt 3 1 3 n mlich hei en dass an einer Kante pro Phase maximal ein Schreiber aktiv sein darf Der Grund f r diese Beschr nkung ist die Tatsache dass das Scheduling keine Ga rantie ber die Aufrufreihenfolge der Knoten gibt D
92. in 3 1 9 erw hnten Einschr nkungen die die Verwendung einer numerischen Bibltiothek mit sich bringen kann 4 4 2 10 user_deserialize Die user_deserialize Funktion wird immer dann gerufen wenn ein vorher persistierter Zustand wieder geladen werden soll 1 void user_deserialize const Lethe State amp state 2 unsigned char rngState unsigned char gsl_rng_ state _rng 3 assert state rngState size gsl_rng_size _rng 4 for unsigned int i 0 i lt state rngState size i 5 rngState i state rngStatelil 6 T _state state 8 Das Modul bekommt beim Aufruf das Zustandsobjekt das es zuvor beim Aufruf von user_serialize zurtickgegeben hat Die generierte Implementierung speichert es Zeile 7 so dass anschlieBend der Zustand vom Zeitpunkt des entsprechenden Aufrufes von user_serialize wiederhergestellt ist Die Implementierung des Gausskanals muss allerdings noch den Zustand des Zufalls generators wiederherstellen was die hinzugef gten Zeilen 2 bis 6 erledigen Wie bereits erw hnt ist das Lesen und Schreiben des Zustanden von Zufallsgenera toren der GSL nicht portabel Es ist unklar wie garantiert sichergestellt werden kann dass die bertragung des Zustandes korrekt ist falls die Fortsetzung auf einer ande ren Plattform stattfindet In der Zeile 3 wird berpr ft ob zumindest die Gr e des Zustandes stimmt 4 4 2 11 user _getResult Am Ende einer Runde wird jedes Modul aufge
93. irgendwann einen Knoten erreichen der seine Arbeit erledigen kann Sp testens an diesem Punkt w chst der Wartestack nicht weiter und wird bis zu einem Knoten abgebaut f r den die Bedingungen seines wartenden Lese oder Schreibaufrufes noch nicht erf llt sind Falls ein Knoten dazwischen einen weiteren Lese oder Schrei baufruf macht wird der Abbau des Wartestacks enstprechend fr her unterbrochen Auf jeden Fall w chst der Wartestack anschlie end wieder Insgesamt ist so garantiert dass alle wartenden Knoten immer wieder aufgerufen werden was zu zeigen war Da ein Entwickler eine ein oder ausgehende Kante nicht ohne Grund vorsieht ist die oben genannte hinreichende Bedingnung im Normalfall erf llt Allerdings liegt das tats chlich in der Hand des Entwicklers Ist die Bedingung nicht erf llt so kann das h chstens die Laufzeitumgebung mit Hilfe einer Heuristik erkennen weil die zuverl ssige Erkennung sehr wahrscheinlich ein nicht entscheidbares Problem darstellt Allerdings wurde das im Rahmen dieser Arbeit nicht nachgewiesen Auch wird die angesprochene Idee einer Heuristik nicht weiter verfolgt Das vorgestellte Scheduling f hrt dazu dass fortlaufend alle Knoten bei Bedarf auf gerufen werden um Daten zu erzeugen zu konsumieren oder zu verarbeiten Mit jedem Aufruf eines initialen Knotens durch den Scheduler l uft die Simulation ein St ck weiter Abschnitt 3 1 4 erl utert wann der Scheduler damit aufh rt so dass die Simulation
94. istiert eine Runde in der nach dem Round Robin Prinzip jeder Teil 2 2 Simulationsalgorithmen nehmer einmal an der Reihe ist Die dabei ausgel sten Ereignisse werden vom Scheduler eingesammelt Zu Beginn der n chsten Runde stehen alle Ereignisse deren Behand lungszeitpunkt gekommen ist ihren Empf ngern zur Verf gung Der Nachteil dieser Architketur ist dass es jedesmal wenn ein Teilnehmer f r keines der Ereignisse einer Runde der Empf nger ist zu einer Leer Operation kommt Je nach Simulation ist die Anzahl der Leer Operationen hoch und damit die Laufzeitverschwendung signifikant Der ereignisbasierte Simulator arbeitet mit einer Warteschlange f r Ereignisse die nach dem Behandlungszeitpunkt sortiert sind Der Scheduler nimmt nacheinander die obersten Ereignisse aus der Schlange und gibt sie dem Empf nger zur Behandlung Der kann daraufhin neue Ereignisse erzeugen die wiederum in die Warteschlange aufge nommen werden Der Effizienzvorteil dieser Architektur begr ndet sich dabei auf zwei Eigenschaften Erstens werden keine unn tigen Leer Operationen verursacht Zweitens muss die Simulationszeit nicht linear verlaufen So wird z B das oberste Ereignis in der sortierten Warteschlange immer sofort behandelt auch wenn der gew nschte Zeitpunkt der Behandlung in der Zukunft liegt Die Simulationszeit macht in diesem Fall einfach einen entsprechend gro en Sprung Eine M glichkeit die Laufzeit zu verk rzen ist die Berechnungen zu
95. kehrt gilt das auch f r die eingehenden und die ausgehenden Streams Anschaulich hei t dies dass die Module Kennungen wie z B erster Schreiber oder dritter Leser und die Streams Kennnungen wie z B zweiter ausgehender Stream oder erster eingehender Stream erhalten Die Kennung ist im Kontext eines Streams bzw eines Moduls jeweils eindeutig Die Eigenschaften Schreiber und Leser bzw eingehend und ausgehend ergeben sich dabei implizit durch die Wahl der Ereignis behandlungsfunktion So w rde z B niemals ein Schreiber das Ereignis ausl sen dass ein Leser beendet hat Abbildung 4 1 zeigt den Hypergraph aus dem Fallbeispiel mit den Kennungen der Module und Streams So ist die Senke f r den Stream zwischen Quelle und Decoder der zweite Leser F r die Senke ist dieser Stream der erste und der Stream zwischen Decoder und Senke der zweite eingehende Stream Diese Festlegung richten sich wie 55 4 Implementierung bereits erw hnt nach der Simulationsbeschreibung Die dort festgelegte Reihenfolge ist zwar willk rlich bleibt aber bei eventuellen Migrationen oder Fortsetzungen der Simulation konstant Die Vernetzung der Module und der Streams findet ausschlie lich im Code statt den der Generator f r jede Simulation erzeugt vgl Abschnitt 3 2 3 Nachdem die Modul und die Streamobjekte erzeugt wurden werden f r jede Verbindung einmal eine Funkti on des Modulobjektes und einmal eine des
96. l vorhanden und kann wie im Abschnitt 3 2 3 beschrieben gebaut werden 3 2 5 Proxies Die Verwendung von Benutzercode in den Simulationen kann wie schon erw hnt dazu f hren dass eine Simulation pl tzlich abgebrochen wird F r die Fehlersuche ist es sehr hilfreich wenn der Benutzer oder der Entwickler in so einem Fall den Grund f r den Abbruch erfahren kann Zu diesem Zweck wurden die Proxies eingef hrt Das ist pro Simulation ein ICE Ser vant vgl ICE Benutzerhandbuch Abschnitt 2 2 2 211 der im Prozess des Generators ausgef hrt wird So lange eine Simulation l uft reicht er einfach ICE Aufrufe zwischen den Simulationen und dem Manager durch Zwischen dem Proxy und dem Simulations prozess besteht au er der ICE Verbindung eine Pipe die die Standardausgabe und die Standardfehlerausgabe des Simulationsprozesses mit dem Proxy verbindet Beendet sich nun der Simulationsprozess wird die Pipe geschlossen wor ber der Proxy informiert wird Den Grund f r das Beenden kann sich der Proxy anschlie end vom Betriebssytem geben lassen da der Generatorprozess der Vater des Simulationspro zesses war Au erdem sind etwaige Fehlermeldungen aus dem Simulationsprozess in der Pipe Der Proxy kann damit den Manager zuverl ssig und ausf hrlich ber aufgetretene Fehler informieren Zu guter Letzt besteht mit den Proxies eine einfache M glichkeit einen Simulations prozess garantiert zu beenden auch wenn dieser eventuell nicht mehr auf ICE Auf
97. l w hrend eines Aufrufs ber einen Port zugreift Wird sie nicht eingehalten kann es zu Verklemmungen kommen Die obige Sicherheitsma nahme wird allerdings umgangen wenn ein Modul w hrend eines Aufrufs mehrere Zugriffe auf einen Stream macht Deshalb wird dem Entwickler empfohlen pro Aufruf nur einmal auf einen Stream zuzugreifen Soll ein Modul mehrmals auf einen Stream zugreifen so muss der Entwickler 44 4 3 Ports selber sicherstellen dass die Blockgr e nicht berschritten wird Wie Abschnitt 4 3 1 erl utert muss er dabei au erdem auf die Lebensdauer der Vektor Objekte achten F r eingehende Ports existiert eine zweite Funktion mit einem weiteren Parameter der angibt um wieviel Einheiten der Lesezeiger erh ht werden soll Damit ist eine Voraus schau auf die Daten m glich Viele Filter m ssen z B bei jedem Aufruf den aktuellen Wert zusammen mit den n n chsten ber cksichtigen W rde es f r solche Module kei ne Vorrausschau geben m ssten sie die Daten zwischenspeichern Diesen Mehraufwand kann man sich mit der obigen zweiten Funktion einfach einsparen Wie Abschnitt 3 1 4 erl utert kann es bei Lese und Schreiboperationen zu Situatio nen kommen auf die die Laufzeitumgebung mit einem impliziten Beenden eines Moduls reagiert falls das Modul den Sonderfall nicht behandelt Implementiert ist dieser Mecha nismus mit C Ausnahmen die von der Laufzeitumgebung bei Eintritt der Sonderf lle geworfen werden Das Fange
98. mulation der zustandsbehaftet ist diesen Zustand in geeigneter Form vollst ndig persistiert Wird dieser Zustand zu sp terer Zeit und evtl an einem anderen Ort von allen Teilen wieder exakt angenommen so l uft die Simulation ab diesem Zeitpunkt genau so ab wie sie abgelaufen w re wenn man nie einen Zwischenzustand erfasst h tte Erm glicht wird das sehr einfach durch ICE 21 Der Mechanismus zum plattformun abh ngigen Austausch von Objekten wird hier lediglich auf eine andere Art verwendet Lethe l sst die Objekte von der ICE Laufzeitumgebung serialisieren und speichert die so erzeugten Datenstr me anstatt sie z B ber das lokale Netz zu senden Zur Rekon struktion der Zust nde nimmt Lethe diese gespeicherten Daten wieder her um sie von der ICE Laufzeitumgebung deserialisieren zu lassen und die Zustandsobjekte zu erhal ten Die Plattformunabh ngigkeit dieser Vorgehensweise ergibt sich dabei direkt aus der Plattformunabh ngigkeit von ICE Eine Simulation ist damit nichts anderes als ein Wirt f r die Manipulation von Zu standsobjekten Existieren auf zwei Computern zwei gleiche Wirte kann die Manipula tion der Zustandsobjekte beliebig oft abwechselnd in beiden Wirten fortgesetzt werden Zwei Wirte sind genau dann gleich wenn sie aus derselben Simulationsbeschreibung erzeugt wurden vgl Abschnitt 3 2 3 Der Entwickler muss beachten dass er auch Zust nde aus ggf verwendeten Biblio theken mit ber cksichtigt Bietet eine
99. mus in dieser Arbeit trotzdem weiterhin als Scheduling bezeichnet Die Folge von impliziten Aufrufen baut einen Wartestack auf der wieder abgebaut wird wenn die Bedingungen f r die wartenden Lese oder Schreibaufrufe erf llt sind Die H he des Stacks ist durch die Anzahl der Knoten beschr nkt da zirkul re Warte abh ngigkeiten verboten sind und die Laufzeitumgebung dieses Verbot durchsetzt vgl Abschnitt 3 1 6 Da ein Knoten bei einem wartenden Schreibaufruf fr hestens dann weiter machen kann wenn der Leser mit dem meisten Verbrauch seine Daten gelesen hat w hlt die Kante immer diesen Leser aus Damit wird die Zeit die der Aufruf des initialen Knotens ben tigt minimal gehalten Das ist wichtig um kurze Antwortzeiten bei der Erhebung eines Zwischenzustandes zu erm glichen vgl Abschnitt 3 1 9 Es muss noch gekl rt werden ob der Aufruf eines initialen Knotens unter Garantie terminiert Es ist n mlich denkbar dass sich die Folge von impliziten Aufrufen st ndig in einem Teilgraphen hin und her bewegt Um das zu verhindern ist folgendes hinreichend Jeder Knoten muss garantieren dass jede Kante immer wieder innerhalb von endlich vielen Aufrufen bedient wird Dann ist n mlich sichergestellt dass jeder wartende Lese oder Schreibaufruf irgendwann erledigt werden kann falls der implizit gerufene Knoten immer wieder aufgerufen wird Durch das Verbot von zirkul ren Warteabh ngigkeiten muss die Folge von impliziten Aufrufen immer
100. n ab wie viele Kausalit ten der Benutzer erkennt und angibt Die optimistischen Verfahren die in der Fachwelt auch als timewarp Verfahren be zeichnet werden gehen stattdessen davon aus dass ein Konflikt unwahrscheinlich ist Daher sparen sie sich den Aufwand f r die Vermeidung und nehmen daf r h here Ko sten f r die Behandlung eines Konfliktes in Kauf F r den Ablauf einer Simulation hei t das dass wenn ein Ereignis versp tet eintrifft alle zu fr h behandelten Ereignisse r ck Diese Bezeichnungen sind f r Simulatoren eigentlich un blich Trotzdem wurden sie an dieser Stelle gew hlt da sich die Kernidee dahinter in anderen Gebieten der Informatik wie z B den Datenbanken 39 wiederfindet und diese Begriffe dort verwendet werden 2 Grundlagen und Stand der Technik g ngig gemacht werden m ssen Anschlie end werden diese Ereignisse zusammen mit dem versp teten Ereignis in der richtigen Reihenfolge neu behandelt Der Nachteil die ser Verfahren ist offensichtlich die gro e Anzahl an Informationen die der Scheduler speichern muss um behandelte Ereignisse vollst ndig r ckg ngig machen und erneut behandeln lassen zu k nnen Ist zwischen den einzelnen Recheneinheiten keine Kommunikation w hrend der Simu lation erforderlich spricht die Fachwelt von einem embarrassingly parallel Algorith mus weil dieser Fall keine Herausforderung darstellt 2 3 Multitasking In einer Simulation in der Kanalcodierung la
101. n dann liegt eine zirkul re Warteabh ngigkeit vor Neben der Tatsache dass das Scheduling so etwas verbietet vgl 3 1 6 ist das Problem an dieser Situation dass sie eine Verklemmung zwischen den beiden Modulen darstellt gegen die weder der Benutzer noch der Entwickler etwas unternehmen kann Formal l sst sich das folgenderma en beschreiben Gegeben sei ein Puffer der maximal b Einheiten aufnehmen kann ein Leser der in einem Aufruf r Einheiten liest und ein Schreiber der in einem Aufruf w Einheiten schreibt Wenn der Puffer mit a Einheiten gef llt ist dann ist die notwendige Bedingung f r eine zirkul re Warteabh ngigkeit unabh ngig davon ob der Leser oder der Schreiber als erster beginnt folgenderma en gegeben a lt rAb a lt w 4 1 Um verhindern zu k nnen dass diese Bedingung jemals zutrifft braucht Lethe vom Entwickler die Information wie viele Einheiten pro Aufruf maximal gelesen bzw ge schrieben werden Diese Anzahl wird die Blockgr e genannt und ist eine Eigenschaft eines Ports Angenommen der obige Stream besitzt m Leser mit den Blockgr en r i 1 m und n Schreiber mit den Blockgr en wj j 1 n Dann existiert kein a das f r beliebige 7 und j die Bedingung 4 1 erf llt genau dann wenn b gt max ri 1 mx wj 4 2 i 1 m jetl n Letztendlich hei t das wenn der F llstand f r die gr te Leser Blockgr e gerade um eins zu klein ist dann muss im Puffer mindestens
102. n einer solchen Ausnahme entspricht der Behandlung des Sonderfalles denn wird die Behandlungsfunktion des Moduls vgl Abschnitt 4 4 2 4 auf Grund einer nicht gefangenen Ausnahme verlassen f hrt das immer zum impliziten Beenden des Moduls Die den ersten beiden Regeln aus 3 1 4 entsprechenden Ausnahmen sind die BufferEmpty Ausnahme und die ModuleHasNoReaders Ausnahme die beide im Na mensraum Core Exceptions definiert sind Die dritte Regel nennt eine M g lichkeit f r das Modul ber den Sonderfall informiert zu werden Dazu existiert f r ausgehende Ports eine zweite Funktion mit einem zus tzlichen boolschen Pa rameter Hat dieser einen positiven Wahrheitswert wirft die Laufzeitumgebung eine Core Exceptions BufferFull Ausnahme falls die Bedingungen daf r erf llt sind Das Modul kann diese Ausnahme entweder fangen oder sich durch sie implizit beenden lassen Das einzige Objekt vom Typ der Adapter Klasse steht einem Modul unter dem Namen ports zur Verf gung ber dieses Objekt erledigt der Entwickler alle Ein und Ausgaben f r sein Modul In Abschnitt 4 4 2 4 findet sich ein Beispiel f r die Verwendung des Adapter Objektes In der Adapter Klasse ist auch die Enumeration Caller definiert Die Namen aller Ports tauchen darin als Konstanten auf Die Behandlungsfunktion des Moduls vgl Ab schnitt 4 4 2 4 erh lt einen Parameter dieses Typs Falls das Modul auf Grund eines impliziten Aufrufs gerufen wurde kann das Modul an Ha
103. nd 0 07 und ist damit f r komplexe Codes vernachl ssigbar klein 60 5 4 Konvertierungen Knoten Kante Basistyp Arbeitstyp Blockgr e Quelle 1 Integer Integer 1 Encoder 1 Integer Integer 2 2 Complex Complex 1 Kanal 2 Complex Complex 1 3 Complex Complex 1 Decoder 3 Complex Complex 1 1 Integer Integer 2 Senke 1 Integer Integer 1 3 Integer Integer 1 Tabelle 5 2 Die Eigenschaften der Ports aus der Messung 5 3 Kante 1 2 3 4 Puffertyp Integer Complex Complex Integer Basistyp Integer Complex Complex Integer Tabelle 5 3 Die Eigenschaften der Kanten aus der Messung 5 3 5 4 Konvertierungen Diese Messung zeigt wieviel Laufzeit durch Konvertierungen verbraucht wird Dazu verwendet der eingehende Port des Kanals den Arbeitstyp gsl_complex Damit kommt es bei Lese und Schreibzugriffen des Kanals zu benutzerdefinierten Konvertierungen In der Tabelle 5 4 sind die Eigenschaften der Ports aufgelistet wobei die Unterschiede zur letzten Messung vgl Tabelle 5 2 hervorgehoben sind Die Eigenschaften der Kanten sind bez glich der letzten Messung unver ndert vgl Tabelle 5 3 Knoten Kante Basistyp Arbeitstyp Blockgr e Quelle 1 Integer Integer 1 Encoder 1 Integer Integer 2 2 Complex Complex 1 Kanal 2 Complex gsl_complex 1 3 Complex Complex 1 Decoder 3 Complex Complex 1 1 Intege
104. nd des Wertes dieses Para meters erkennen von welchem Stream der implizite Aufruf kommt Auf diese Weise ist eine Sonderbehandlung von Anfragen einzelner Streams m glich So kann z B ein De coder bei einer adaptiven Decodierung erst dann Informationen in den Feedback Stream schreiben wenn der Encoder diese anfordert vgl Abschnitt 3 1 6 Falls das Modul als initialer Knoten ausgew hlt und deshalb vom Scheduler selber gerufen wurde ist der Wert des Parameters LETHE_SCHEDULER Es besteht eine Analogie zwischen Decodern und Parsern Deshalb wurde dieser Begriff gew hlt der bei LR k Parsern 17 die gleichartige Technik bezeichnet 3 Die Verwendbarkeit des Caller Parameter ist fraglich da er nur von nicht station ren Algorithmen ber cksichtigt werden kann 45 4 Implementierung 4 4 Module Ein Modul hat zwei Aufgaben Erstens muss es das Scheduling unterst tzen und zweitens muss es M glichkeiten zur Interaktion mit der Laufzeitumgebung bereitstellen Die erste Aufgabe bernimmt die Klasse Core Module F r die zweite Aufgabe generiert Lethe aus den Metainformationen des Entwicklers pro Modul sechs Klassen Diese sind alle in einem Namensraum definiert der in Extensions Modules liegt und den Namen des Moduls tr gt Eine der generierten Klassen ist die Adapter Klasse die alle Ports des Moduls ent h lt Sie wurde bereits in Abschnitt 4 3 2 behandelt Die in Abschnitt 4 3 aufgelisteten Metainformationen be
105. nden Port pro Phase angeben ob die angeschlossene Kante zu Beginn dieser Phase f r den Leser leer oder gef llt sein soll Falls es f r einen Knoten wie im Beispiel aus Abbildung 3 4 f r den Encoder von Relevanz ist dass in der vorherigen Phase Daten in die eingehende Kante geschrieben wurden wird der Benutzer f r diesen Knoten letzteres angeben Einfach gesprochen stehen dem Knoten in dem Fall die Daten aus der vorhergehenden Phase zur Verf gung Doch welche Daten das sinnvollerweise sind ist nicht trivial zu entscheiden Die folgenden Regeln legen fest welche Daten ein Leser zu sehen bekommt wenn der Benutzer festlegt dass er zu Beginn einer Phase eine gef llte Kante sehen soll 1 Wenn ein Leser am Ende der alten Phase aktiv war und zu Beginn der neuen Phase aktiv ist dann gehen f r ihn die beiden Phasen nahtlos ineinander ber Die Daten die er am Ende der alten Phase gesehen hat sind die Daten die er zu Beginn der neuen Phase sieht 2 Ansonsten ist dieser Leser neu an der Kante Dann h ngt die Entscheidung f r ihn von den anderen Lesern der Kante ab a Falls es andere Leser gibt die am Ende der alten Phase aktiv waren dann ist von ihnen der Leser ausschlaggebend f r den die Kante am Ende der alten Phase die meisten Daten gepuffert hatte Diese Daten sind diejenigen die der neue Leser zu Beginn der neuen Phase sieht b Ansonsten ist der Leser ausschlaggebend der als letztes beendet hat Die Daten die die Kante
106. nderma en aus Lethe Configuration _config Lethe Settings _settings Lethe State _state Lethe Result _result Jeder Typ ist ein C struct dessen Felder genau die Typen und Namen haben die der Entwickler spezifiziert hat Lethe ist ein Namensraum der im Namensraum des Moduls existiert und alle generierten Typen enthalt Dadurch muss der Entwickler keine R cksicht bei der Wahl von Bezeichnern nehmen Zu jedem dieser Typen existiert ein ICE Pendant damit die Inhalte der Variablen ber das verteilte Netz transportiert werden k nnen Es ist f r jeden Typ m glich dass er f r ein Modul nicht ben tigt wird und deshalb leer ist Da ICE die Definition von leeren Typen verbietet f gt Lethe in einem solchen Fall eine einizige Variable ein F r den Entwickler spielt das allerdings keine Rolle 4 4 2 Die Entwickler API Die folgenden Abschnitte definieren die API Funktionen von Lethe Sie erw hnen dabei nur kurz den Zweck der Funktionen Abschnitt 3 1 10 erl utert sie ausf hrlicher und erkl rt vor allem das Zusammenspiel der Funktionen mit der Laufzeitumgebung Zur besseren Verst ndlichkeit findet die Erkl rung dieser Funktionen anhand eines Beispielmoduls statt Das Beispiel ist ein Gausskanal der komplexen Zahlen am Eingang eine gaussverteilte komplexe Zufallszahl hinzuaddiert und sie in den Ausgang schreibt Abschnitt 4 4 2 1 listet die Metainformationen dieses Moduls auf Die Implementierung des Gausskanals verwendet die
107. nige Details eine Obermenge von C Der Lernaufwand f r den Ent wickler kann also in Grenzen gehalten werden Vor allem die Unterst tzung von objektorientiertem Programmieren war ausschlag gebend f r die Entscheidung das Framework in C zu implementieren Die Program mierschnittstelle f r Entwickler ist dabei so gestaltet dass die Unterschiede zwischen C und C m glichst keine Rolle spielen Doch wie Abschnitt 2 5 auch erkl rt schneidet C im Vergleich mit moderneren Programmiersprachen schlecht ab Der Grund daf r ist vor allem dass C viele Alt lasten von C geerbt hat Lassen es die Anforderungen zu eine langsamere Ausf hrung des Programmes zu erlauben ist einem Programmierer deshalb gut geraten wenn er eine modernere Sprache verwendet Der Generator die Proxies und der Breeze Server sind in Python 32 geschrieben Der Grund hierf r ist dass Python durch elegante Konzepte wie die dynamische Typisierung sehr kurze Entwicklungszeiten und die Erstellung von kompaktem Code erm glicht Die betroffenen Teile sind der Generator die Proxies und der Breeze Server Da die Implementierungen dieser Teile wie eingangs in diesem Kapitel erw hnt in dieser Arbeit nicht behandelt werden wird auf eine genauere Beschreibung von Python im Rahmen dieser Arbeit verzichtet Der Interessierte wird auf die umfangreiche Dokumentation unter 32 verwiesen 4 2 Streams Ein Stream hat zwei Aufgaben Erstens ist er wesentlich f r das Scheduling
108. nitt 3 2 2 kommuniziert Behandelt wird der Manager in 41 3 2 2 Simulationsobjekte Eine laufende Simulation ist ein Zusammenspiel einer Laufzeitumgebung und beliebigem von Entwicklern stammenden Code Es stellt sich daher die Frage wie dieses Zusam menspiel am besten organisiert wird 28 3 2 Das verteilte System f createCheckpoint getStatusinformation getStatusInformation stop suspend RUNNING resume STOPPED createCheckpoint getStatusinformation continue start resume start resume getStatusInformation FINISHED ww getResults getStatusInformation Abbildung 3 6 Zustandsautomat eines Simulationsobjektes Eine naheliegende M glichkeit ist es einen zentralen Prozess mit einer Laufzeitumge bung zu haben Zu jeder eingereichten Simulationsbeschreibung erzeugt die Laufzeitum gebung eine entsprechende Struktur und startet die Algorithmen Dieser Ansatz bringt allerdings zwei gro e Nachteile mit sich Erstens bedeutet die Tatsache dass in den Simulationen ein vom Benutzer stammen der Code ausgef hrt wird dass im Wirtsprozess von einer negativen Assertion vgl Ansi C bzw ISO IEC 9899 1990 ber einem Speicherzugriffsfehler bis hin zu einer Flie kommaausnahme alles auftreten kann Fehlerhafter Code eines Benutzers f hrt al so zum Abbruch aller im selben Prozess gerechneten Simulationen Zweitens ergibt sich f r den zentralen Prozess ein Problem wenn in einer neuen Simulation bisher n
109. nn Dazu muss der Benutzer angeben ob und wie eine Runde geteilt werden kann Zus tzlich muss die Entwickler API um eine Funktion erweitert werden die aus einer Menge von Teilergebnissen das Gesamtergebnis eines Knotens berechnet Lethe kann dann die Runden automatisch verteilen am Ende der Simula tionen die Teilergebnisse sammeln und sie einer der Simulationen zum Berechnen der Gesamtergebnisse geben Neben dem Komfort f r den Benutzer bringt diese L sung den Vorteil dass die Algorithmen zum Zusammenf hren von Teilergebnissen innerhalb von Lethe und nicht in irgendwelchen untereinander inkompatiblen Formaten f r externe Programme definiert sind 6 4 4 Unterst tzung f r Matlab Wie Abschnitt 4 1 diskutiert muss der Entwickler die Algorithmen in C implemen tieren Die in Abschnitt 2 5 erw hnten Probleme dieser Sprache machen diese Arbeit allerdings m hsam Wie sich aus Gespr chen ergeben hat sind deshalb nicht alle poten tiellen Entwickler bereit Lethe zu benutzen Dies w rde sich ndern wenn es m glich w re Module in Matlab zu programmieren Um diese Anwender zu gewinnen muss Lethe also eine M glichkeit bieten Modu le in Matlab zu implementieren Mit Hilfe eines Matlab nach C Compilers w re es m glich diese Module in die Simulation mit einzubinden Es w re also zu untersuchen ob eine Abbildung der Lethe API auf eine Matlab API m glich ist und wie man eine solche Zwischenschicht am besten realisisert Insbesonder
110. o en Anwenderkreis ansprechen zu k nnen unterst tzt Lethe die Verwendung beliebiger Bibliotheken sogar innerhalb einer Simulation F r die Beispielimplementierungen wurde die GSL verwendet da sie weit verbreitet und m chtig ist Es ist allerdings zu beachten dass Lethe unter der GPL steht vgl Abschnitt 6 3 12 3 Systementwurf Der erste Teil des Entwurfes erarbeitet zum einen ein Modell der Simulation und zum anderen eine Architektur des Frameworks Der zweite Teil des Entwurfes besch ftigt sich mit den Teilnehmern des verteilten Systems die Inhalt dieser Arbeit sind Fr diskutiert welche Teilnehmer welche Aufgaben haben und welche Schnittstellen zur Kommunika tion zwischen ihnen existieren Warum Lethe ein verteiltes System ist und es die Dienste der Internet Communi cation Engine ICE 21 verwendet wird in 41 diskutiert Auch die Frage wie der Entwickler und der Benutzer die von Lethe ben tigten Metainformationen zu den Al gorithmen und den Simulationen angeben kann ist Thema von 41 Wichtig f r diese Arbeit hier ist nur dass es daf r einen Weg gibt und dass alle ben tigten Informationen den Teilnehmern in Form einer Simulationsbeschreibung zur Verf gung gestellt werden 3 1 Die Simulation Die Diskussionen in diesem Abschnitt sind vor allem von zwei Anforderungen gepr gt Erstens wird eine f r Kanalcodierer spezialisierte L sung geschaffen Dadurch sind an einigen Stellen Optimierungen m glich
111. oberfl che kommerzieller Tools entf llt in diesem Fall Im Rahmen dieser Diplomarbeit soll daher ein Framework f r Simulationen in der Ka nalcodierung implementiert werden Dabei soll die Anbindung an ein verteiltes System gegeben sein um Simulationen zu verwalten und in einem heterogenen Netzwerk zu verteilen was jedoch Teil einer weiteren Diplomarbeit ist Damit soll es Anwendern oh ne tiefergehende Programmierkenntnisse m glich sein auf einfache Weise Simulationen durchzuf hren Zu diesem Zweck soll das Framework nur eine Beschreibung der Simulation mit betei ligten Modulen und Parametern entgegennehmen und die Simulation dann eigenst ndig durchf hren Zudem soll f r die Entwicklung neuer Module nur sehr wenig Wissen ber die Interna des Frameworks notwendig sein Die Einbindung neuer Module ist damit f r programmiererfahrenere Anwender relativ einfach zu bewerkstelligen Abgabetermin 17 April 2006 Bearbeiter Alexander Bernauer Betreuung Prof Dr Ing M Bossert Prof Dr Ing F J Hauck Dipl Ing A Hof Dipl Inform S Schober Katalognr D 2005 XL 2 Erklarung Ich versichere dass ich die vorliegende Diplomarbeit selbst ndig und ohne unzul ssige fremde Hilfe angefertigt habe Ulm den 17 Juli 2006 Alexander Bernauer Danksagung Mein gr ter Dank geht an meine Eltern die mir durch ihre jahrelange finanzielle Un terst tztung mein Studium erm glicht haben Au erdem m chte ich allen Mitwirken
112. on Echtzeitsystemen ist Lethe deshalb keine gute Wahl Dazu kommt in diesem Fall dass Lethe keine Abbdildung von Interrupts erm glicht 6 3 Lizenzrecht Lethe verwendet die Internet Communication Engine ICE 21 Diese wird von der Firma ZeroC unter der GNU General Public Licence GPL 16 vertrieben Unter anderem schreibt diese Lizenz vor dass Programme die GPL lizenzierten Quellcode verwenden oder gegen GPL lizenzierte Bibliotheken linken auch unter die GPL gestellt werden m ssen Eine der Konsequenzen daraus ist dass man den vollst ndigen Quell code zur Verf gung stellen muss wenn man sein Programm weitergibt F r die Weiterentwicklung von Lethe bedeutet das dass Verbesserungen oder Erwei terungen der Allgemeinheit zur Verf gung stehen sobald sie an einen Dritten weiterge geben werden Dagegen sind die M glichkeiten einer kommerziellen Nutzung von Lethe durch die GPL eingeschr nkt Da ZeroC bei Bedarf allerdings auch kommerzielle Lizen zen vergibt und das Framework au er ICE keine andere Software verwendet ist eine kommerzielle Lizenz f r diesen Teil von Lethe denkbar Ob dies f r den Rest von Lehte auch gilt kl rt 41 Der von Lethe generierte Code steht derzeit auch unter der GPL Da alle Module diesen Code verwenden m ssen sie auch unter der GPL stehen Das bedeutet f r einen Entwickler dass er den Quellcode zur Verf gung stellen muss wenn er ein Modul weiter gibt Unterl t er dies spielt die
113. oolsche Variable zur ckgesetzt wird egal aus welchem Grund die call Methode terminiert Falls eine LoopPrevention LoopDetected Ausnahme geworfen wird f ngt die call Funktion diese selbst auf und wirft statt dessen eine Core Exceptions LoopDetected Ausnahme der sie den Namen des Moduls mitgibt Diese Ausnahme folgt nun dem Wartestack des Schedulings und wird von der call Funktion des n chsten wartenden Moduls gefangen Diese f gt wiederum den Namen des Moduls an die Ausnahme hinzu und wirft sie weiter Auf diese Weise erh lt der Scheduler am Ende die Ausnahme mitsamt der Folge von impliziten Aufrufen die zu der Verklemmung f hrten Der Scheduler versendet daraufhin eine entsprechende Lognachricht an den Breeze Server und beendet die Simulation 57 5 Messungen Dieses Kapitel kl rt inwiefern das Framework der Anforderung bez glich einer hohen Ausf hrungsgeschwindigkeit gerecht wird Dazu wurden im Rahmen dieser Arbeit meh rere Messungen durchgef hrt die im Folgenden dokumentiert sind Der den Messungen zugrundeliegende Hypergraph der Simulationen ist in Abbildung 5 1 zu sehen Er entspricht dem Hypergraphen des Fallbeispieles aus Abschnitt 3 1 2 Die Kanten sind durchnummeriert damit in den folgenden Abschnitten darauf referenziert werden kann 1 2 3 4 Abbildung 5 1 Die Simulation f r die Messungen Das Laufzeitverhalten der Algorithmen in den Knoten ist unabh ngig von der Imple mentierung des Frameworks Deshalb
114. optimale Nutzung der zur Verf gung stehenden Ressourcen Zu sammen mit der Erstellung von Sicherungspunkten mittels denen eine abgebrochene Simulation fortgesetzt werden kann bietet die Migration au erdem Sicherheit gegen Hardwareausf lle Das Besondere an Lethe ist nicht nur dass es alldiese M glichkeiten bietet sondern dass dies alles automatisiert geschieht und der Benutzer sich dadurch auf die wesentlichen Probleme konzentrieren kann Das Framework das Thema dieser Arbeit erm glicht diese F higkeiten von Lethe Es erzielt eine hohe Ausf hrungsgeschwindigkeit der Simulationen und ist zugleich komfor tabel zu bedienen Das Modell des Hypergraphen verspricht au erdem m chtig genug zu sein um alle Anwendungsf lle der Kanalcodierung abzudecken Zuletzt ist durch die Plattformunabh ngigkeit die Unterst tzung nahezu beliebiger numerischer Bibliothe ken und die freie Lizenz der potentielle Anwenderkreis sehr gro Das einzige was diesen einschr nkt ist die Tatsache dass der Entwickler in C programmieren muss Der Scheduler n tzt die Tatsache aus dass Lethe auf Anwendungen in der Kanal codierung spezialisiert ist Das erm glicht ihm schlicht und dennoch effizient zu sein Allerdings gibt er keine Garantien ber die Aufrufreihenfolge der Knoten so dass sich nicht voraussagen l sst wie eine Simulation im Detail ablaufen wird In der Konsequenz ist die Entwicklerschnittstelle so definiert dass diese Details im Normalfall irr
115. pth_uctx_destroy threads current FALSE die number if number 0 the last thread did exit so terminate the whole scheduler by passing control back to the pthf_run methode if pth_uctx_switch exitContext mainContext FALSE die not reached die else A 2 Halbieren der Anzahl der Kontextwechsel remove the thread from the queue for i current i lt number i threads i threads it 1 if current number current 0 pass control to the next thread if pth_uctx_switch exitContext threads current FALSE die void pthf_abort int line printf aborting s da n __FILE__ line abort A 2 3 Eine beispielhafte main c include pth fast h include lt stdio h gt include lt unistd h gt typedef struct char name int count Params void run void arg int i Params p Params arg for i 0 i lt p gt count i printf loop d s n i p gt name sleep 1 pthf_yield F 83 Anhang A GNU PTH int main Params p1 t1 2 Params p2 t2 4 pthf_init pthf_spawn run amp pil NULL 16 1024 pthf_spawn run amp p2 NULL 16 1024 pthf_run return 0 84 Anhang B Dienste Die Diplomarbeit von Stephanie Wist 41 behandelt das ICE Grid von Lethe vlg ICE Benutzerhandbuch Kapitel 36 21 Zwei der Dienste in diesem Grid sind die Generatoren und der Breeze Server
116. r Integer 2 Senke 1 Integer Integer 1 3 Integer Integer 1 Tabelle 5 4 Die Eigenschaften der Ports aus der Messung 5 4 61 5 Messungen Erstaunlicherweise verursachten die Konvertierungen keinen messbaren Mehraufwand Dies deutet darauf hin dass der Aufwand f r die restliche Verwaltung deutlich ber wiegt Die folgende Messung untersucht dies n her 5 4 1 Erh hung der Konvertierungsh ufigkeit Ausgehend von der vorherigen Messung wird in einem zweiten Schritt die Anzahl der Konvertierungen maximiert indem jeder Port einen vom Basistyp verschiedenen Ar beitstyp erh lt und die Optimierung aus Abschnitt 4 2 5 ausgeschaltet ist Die Tabelle 5 5 veranschaulicht dies wobei sich die hervorgehobenen Unterschiede auf die vorherge hende Messung beziehen vgl Tabelle 5 4 Die Eigenschaften der Kanten sind weiterhin unver ndert vgl Tabelle 5 3 Knoten Kante Basistyp Arbeitstyp Blockgr e Quelle 1 Integer int 1 Encoder 1 Integer int 2 2 Complex gsl_complex 1 Kanal 2 Complex gsl_complex 1 3 Complex gsl_complex 1 Decoder 3 Complex gsl_complex 1 1 Integer int 2 Senke 1 Integer int 1 3 Integer int 1 Tabelle 5 5 Die Eigenschaften der Ports aus der Messung 5 4 1 Diesesmal konnte eine Erh hung der Laufzeit um 4 Sekunden auf 61 Sekunden ge messen werden F r eine Berechnung der zus tzlichen Laufzeitkosten die durch Konver tierungen in einem Port ent
117. r die Ports spielen f r die Generierung dieser Klasse eine Rolle Neben der Adapter Klasse werden Klassen f r die Konfiguration die Einstellungen den Zustand und die Ergebnisse eines Moduls generiert Abschnitt 4 4 1 nennt die Namen dieser vier Verwaltungsklassen und erkl rt wie sie der Entwickler verwenden kann Die zentrale Klasse unter den sechs generierten ist die Module Klasse Sie enth lt alle Funktionen die die Laufzeitumgebung aufruft um mit dem Modul zu interagieren Die Implementierung dieser Funktionen ist das einzige was der Entwickler erledigen muss nachdem Lethe die Klassen generiert hat Abschnitt 4 4 2 erkl rt anhand eines Beispiels diese Funktionen die zusammen mit den Ports die Entwickler API von Lethe bilden Die Module Klasse ist eine Template Klasse Der Grund daf r ist dass der Typ der ein und ausgehenden Streams erst fest steht wenn der Graph der Simulation bekannt ist vgl Abschnitt 4 2 5 und ein Modul Referenzen auf seine Streams braucht vgl Abschnitt 4 5 1 F r jeden ein und ausgehenden Stream besitzt die Template Klasse also einen Parameter f r den Typ des Streams Die Module Klasse aus dem Extensions Namensraum ist von Core Module ab geleitet Die Vererbungsbeziehung zwischen den beiden Modul Klassen erzeugt dieselbe zweischichtige Architektur wie bei den Streams Ein eigener Abschnitt ber das Sche duling behandelt die obere Schicht Abschnitt 4 5 Folglich behandelt dieser Abschnitt hier n
118. ration des Breeze Servers existieren in der Deployment Beschreibung des ICE Grids die folgenden Eigenschaften Breeze Path Das Verzeichnis f r die Logdateien Breeze FileName Ein Pr fix f r den Namen der Logdateien Breeze FileExtension Die Dateiendung der Logdateien B 2 3 Logdateien Der Breeze Server legt f r jeden Tag eine eigene Logdatei an Der komplette Pfad einer Logdateien hei t lt Breeze Path gt lt Breeze FileName gt JJJJ MM TT lt Breeze FileExtension gt Alle Dateien deren Pfad diesem Muster entsprechen werden vom Breeze Server beim Starten automatisch als Logdateien interpretiert und verwendet Wahrend der Breeze Server l uft sollten diese Dateien nicht gel scht werden B 2 4 publish Mit dem Kommandozeilenprogramm publish kann der Benutzer Nachrichten an den Breeze Server senden Die Kommandozeile sieht folgenderma en aus publish py p lt proxy gt n lt locator gt m lt message gt t lt type gt o lt origin gt h Die Bedeutungen der Optionen sind p lt proxy gt Die Stringrepr sentation des ICE Proxies vom Breeze Servers Diese Op tion kann nicht zusammen mit der Option n verwendet werden n lt locator gt Die Stringrep rsentation des ICE Proxies vom Namensdienst Diese Op tion kann nicht zusammen mit der Option p verwendet werden m lt message gt Der Inhalt der Nachricht t lt type gt Der Typ der Nachricht Falls diese Option nicht gesetzt ist hat die Nachric
119. reich mit Hilfe einer Semaphore eines Mutexes oder eines Monitors angelegt werden Je nach System erfordert das ggf einen Aufruf ans Betriebs system die Erstellung von Speicherbarrieren oder die Entleerung der CPU Caches Da w hrend einer Simulation viele Daten zwischen den Algorithmen ausgetauscht werden werden die kritischen Bereiche sehr oft betreten so dass der Aufwand daf r die Laufzeit sp rbar erh ht Zweitens verursacht das pr emptive Multitasking des Betriebssystems viel mehr Kon textwechsel als n tig Je l nger jeder Thread seine Arbeit erledigt bis er unterbrochen wird desto seltener muss zwischen zwei Threads umgeschaltet werden Anstatt also nach einem Zeitscheibenverfahren pr emptiv umzuschalten kann eine programmeigene Lo gik ihr Wissen ber die Aufgaben der Threads und die bergabepunkte ausnutzen um seltener und zu den g nstigen Zeitpunkten kooperativ umzuschalten Neben einer deut lichen Senkung der Anzahl der Kontextwechsel fallen zus tzlich die kritischen Bereiche weg weil es dann keine echte Nebenl ufigkeit mehr gibt 2 4 Hypergraphen F r diesen Ansatz werden sogenannte User Threads ben tigt Im Unterschied zu Ker nel Threads wei das Betriebssystem nichts ber deren Existenz womit die Verantwor tung f r das Scheduling in der Hand des Programms liegt F r den Entwickler eines Algorithmus ndert sich dabei verglichen mit dem pr emptiven Fall nichts wenn die bergabe in einem Bibliotheksaufruf
120. rng set _rng settings seed 4 Die generierte Implementierung speichert die neuen Einstellungen ab Zeile 2 Da durch kann die user_trigger Funktion immer auf die aktuellen Einstellungen zugrei fen Der Gausskanal muss an dieser Stelle seinen Zufallsgenerator zurticksetzen Zeile 3 Dazu erh lt er vom Benutzer ber die Einstellungen den neuen Anfangswert 5l 4 Implementierung 4 4 2 8 user_newPhase Der einzige Zweck der user_newPhase Funktion ist die Module tiber den Beginn einer neuen Runde zu informieren 1 void user_newPhase int phaseNumber int numberofPhases 2 Das Modul erh lt die Nummer der aktuellen Phase und die Gesamtanzahl an Phasen Dadurch k nnen sich Module je nach Phase unterschiedlich verhalten Die user_newPhase Funktion wird unabh ngig davon ob das Modul w hrend der Phase berhaupt aufgerufen werden wird immer f r alle Module aufgerufen Die generierte Funktion ist leer und bleibt unver ndert da der Gausskanal an dieser Stelle nichts erledigen muss 4 4 2 9 user_serialize Die user_serialize Funktion wird immer dann gerufen wenn die Simulation ihren Zustand persistieren soll 1 Lethe State user_serialize 2 unsigned char rngState unsigned char gsl_rng_state _rng 3 const size_t size gsl_rng size _rng 4 _state rngState clear 5 for unsigned int i 0 i lt size i 6 _state rngState push_back rngStateli 7 8 return _state 9
121. rt und wie man es l sen kann Abschnitt 3 1 9 diskutiert wie mit Hilfe einer ICE Funktionalit t die plattformun abh ngige Erhebung von Zwischenzust nden erm glicht wird Au erdem erkl rt er auf was ein Entwickler dabei achten muss Um einen berblick ber die Interaktionen der Knoten mit der Laufzeitumgebung zu erhalten erkl rt Abschnitt 3 1 10 den Lebenszyklus eines Knotens Einen berblick ber die vom Benutzer ben tigten Metainformationen ber einen Knoten bietet Abschnitt 3 1 11 3 1 1 Das Fallbeispiel Der Kern des Fallbeispieles ist ein AWGN Kanal der die bertragenen Daten additiv mit einem wei en gaussverteilten Rauschen berlagert Ein Faltungscode 2 Kapitel 8 soll die Fehlerwahrscheinlichkeit der bertragung unter einen gewissen Wert dr cken Die zu bertragenen Daten stammen aus einer Quelle die gewisse hier nicht n her er l uterte statistische Eigenschaften hat Der Kanalcodierer ist daran interessiert welche Fehlerwahrscheinlichkeiten sich f r verschiedene Rauschleistungen des Kanals ergeben Ermittelt wird diese Wahrscheinlichkeit von einer Senke die die Daten der Quelle mit den Daten des Decoders vergleicht Das ist der Ausgangspunkt der folgenden Diskussio nen 3 1 2 Das Modell Eine gebr uchliche Darstellung f r Simulationen ist das sogenannte Blockschaltbild Dabei werden einfache Rechtecke und Pfeile verwendet wobei ein Rechteck z B f r den Encoder oder den Kanal also einem eigenst n
122. rufe reagiert Die Proxies sind also nahezu transparent Deshalb besitzt ein Proxy zum einen die Schnittstelle des Simulationsobjektes und zum anderen die Schnittstelle des Managers Hinzu kommt noch eine Methode die das Bootstrapping des Simulationsobjektes er m glicht Da zwischen dem Proxy und dem Simulationsobjekt eine ICE Verbindung besteht m ssen beide Objekte ICE Referenzen auf den Partner besitzen Dazu gibt der Proxy seine Referenz per Kommandozeilenparameter an das Simulationsobjekt Ist die Simu 32 3 2 Das verteilte System lation erfolgreich initialisiert meldet sich das Simulationsobjekt tiber die Schnittstelle des Proxies und gibt ihm auf diesem Weg seine eigene Referenz Eine alternative M glichkeit ist dass sich das Simulationsobjekt beim Namensdienst vgl ICE Benutzerhandbuch Kapitel 36 21 anmeldet und der Proxy den Namens dienst so lange fragt bis der entsprechende Eintrag vorhanden ist Allerdings muss der Proxy daf r den Namen des Simulationsobjektes kennen Wenn er diesen per Komman dozeilenparameter festlegen w rde w re gegen ber der obigen L sung nichts gewonnen Au erdem ist die Transparenz der Proxies beeintr chtigt wenn sowohl der Proxy als auch das Simulationsobjekt im Namensdienst eingetragen sind Zugegebenerma en ist Letzteres eine sthetische Entscheidung 3 2 6 Der Breeze Server W hrend einer Simulation k nnen vielerlei Dinge geschehen ber die der Benutzer gerne informiert i
123. rung die Eigenschaften aus Tabelle 5 6 und f r den Fall ohne Optimierung die Eigenschaften aus Tabelle 5 3 Abbildung 5 6 zeigt die Ergebnisse dieser Messreihe In beiden F llen w chst die Laufzeit ungef hr linear mit der Anzahl der bertragenen Zahlen Die Steigungen sind 66 5 6 Erh hung der Datenmenge Knoten Kante Basistyp Arbeitstyp Blockgr e Quelle 1 Integer int 100 Encoder 1 Integer int 200 2 Complex gsl_complex 100 Kanal 2 Complex gsl_complex 100 3 Complex gsl_complex 100 Decoder 3 Complex gsl_complex 100 1 Integer int 200 Senke 1 Integer int 100 3 Integer int 100 Tabelle 5 9 Die Eigenschaften der Ports aus der Messung 5 5 allerdings verschieden mit der Optimierung betr gt sie 0 14 und ohne die Optimierung 0 23 Sekunden pro 10 Millionen Zahlen Die Optimierung bewirkt damit nahezu eine Halbierung der Laufzeit 25 nit Optinierung ohne Optinierung Laufzeit Sekunden 18 28 38 48 58 68 70 88 98 188 Anzahl Milltionen St ck Abbildung 5 6 Erh hung der Datenmenge Vergleich mit und ohne Optimierung Ob die Optimierung letztendlich sinnvoll ist oder nicht kann nicht einfach entschieden werden Relativ gesehen bewirkt sie signifikante Einsparungen f r den Verwaltungsauf wand jedoch absolut gesehen sind das nur ein paar Sekunden die verglichen mit den langen Simulationszeiten keine Rolle spielen 67 6 SchluBfolgerungen un
124. rwenden kann Dabei muss er den Wert erhalten den er zuvor an den gleichen Index geschrie ben hat In Abschnitt 4 4 2 4 ist ein Beispiel f r einen solchen Fall Bei einem solchen Zugriff muss also das bereits in den Basistyp konvertierte Datum in den Arbeitstyp zur ck konvertiert werden Nach der Aktualisierung muss das Datum wieder zur ck in den Basistyp konvertiert werden Es ist schwer zu garantieren dass es allen iterativen Zugriffsmustern f r alle denkbare Datentypen inklusive der Konvertierungsfunktionen egal ist ob sie direkt auf den Daten oder auf Schattenkopien arbeiten die bei jedem Zugriff hin und zur ck konvertiert werden Abgesehen vom Aufwand ist das der Grund weshalb ein WriteVector einen tempor ren Puffer des Arbeitstyps besitzt auf dem das Modul arbeitet Sind alle Schreibzugriffe erledigt wird dieser Puffer einmal objektweise in den Basistyp konvertiert und in den Puffer des Streams kopiert Damit der Aufwand eines tempor ren Puffers eingespart wird wenn nicht konvertiert werden muss existiert eine Template Spezialisierung f r den Fall dass Arbeitstyp und Basistyp identisch sind Dieser WriteVector ist trivial und entspricht dem ReadVector Eine noch zu kl rende Frage ist wann der Zeitpunkt erreicht ist ab dem die Lese oder Schreibzugriffe mit Sicherheit erledigt ist Neben dem obigen WriteVector der seinen tempor ren Puffer kopieren muss ist das f r die Konsistenzsicherung der Stre ams wichtig Wie Abschnitt 4
125. ser Fragen kommen weitere Probleme wie z B die Konsistenz sicherung der Streams auf Abschnitt 4 3 erkl rt wie diese Probleme durch die Ports die Verbindungsst cke zwischen Knoten und Kanten gel st werden Abschnitt 4 4 besch ftigt sich mit der Implementierung der Knoten den sogenannten Modulen Insbesondere erkl rt dieser Abschnitt die Programmierschnittstelle API von Lethe Sowohl die Streams als auch die Module sind in zwei Schichten aufgeteilt Die Ab schnitte 4 2 und 4 4 behandeln jeweils nur die untere Schicht die f r den Datentransport und die Datenmanipulation zust ndig ist Die obere Schicht ist verantwortlich f r das Scheduling Abschnitt 4 5 besch ftigt sich mit dieser Schicht und erl utert wie der Al gorithmus aus Abschnitt 3 1 3 umgesetzt wird Die Implementierung der Teile von Lethe die f r das Verst ndnis der API und der Laufzeitumgebung irrelevant sind und keine Besonderheiten aufweisen werden in diesem Kapitel nicht behandelt Der Grund daf r ist schlichtweg dass eine komplette Softwa rebeschreibung den Rahmen dieser Arbeit bei weitem sprengen w rde Die betroffenen Teile sind der Generator vgl Abschnitt 3 2 3 der Proxy vgl Abschnitt 3 2 5 der Breeze Server vgl Abschnitt 3 2 6 und Details der Laufzeitumgebung Auch das Build system vgl Abschnitt 3 2 3 wird in dieser Arbeit nicht n her beschrieben Nur die Tei le die den Entwickler direkt betreffen werden erl utert Der Interessierte wird au
126. sgenerator _rng vgl n chster Abschnitt Die Varianz der Zufallsverteilung ist dabei eine Einstellung des Moduls und wird direkt aus der _settings Variablen gelesen Die _config _results und _state Variablen werden in diesem Beispiel in der user_trigger nicht ben tigt Muss ein Modul allerdings auf seine Konfiguration zugrei fen Ergebnisse protokollieren oder auf seinem Zustand arbeiten sollte das am Besten direkt mit diesen Variablen geschehen Denn dann kann der Entwickler die folgenden Funktionen unver ndert verwenden Der Grund warum das Beispiel die _state Variable nicht verwendet ist dass sich der gesamte Zustand des Modul im _rng Objekt befindet Das Beispiel ist brigends ein Fall in dem der Indexoperator eines WriteVectors zum Lesen der Daten verwendet wird vgl Abschnitt 4 3 1 Bei den beiden Zugriffen auf den ausgehenden Stream werden jeweils nur Teile des Objekte ver ndert 4 4 2 5 user_init Die user_init Funktion wird f r jedes Modul genau einmal gerufen Dabei erh lt das Modul seine Konfiguration 1 void user_init const Lethe Configuration amp config 2 _config config 3 switch config typeofRng 4 case Config GaussChannel TAUS 5 _rng gsl_rng_alloc gsl_rng_taus break 6 aa 7 50 4 4 Module 8 Die Implementierung der user_init Funktion braucht normalerweise keine Eingrif fe des Entwicklers Der generierte Code handelt in den meisten Fallen richtig indem er die Konfi
127. so viel Platz sein dass die gr te Schreiber Blockgr e noch hinein passt Neben diesem Minimum muss Lethe noch die Mindestgr e ber cksichtigen die der Benutzer f r einen Stream angeben kann vgl Abschnitt 3 1 7 Es ist nicht zu erwarten dass eine Vergr erung der Puffer ber das Maximum dieser beiden Minima hinaus Vorteile mit sich bringt Deshalb w hlt Lethe f r jede Puffergr e dieses Maximum 4 2 3 Basistypen Unterschiedliche Module k nnen mit unterschiedlichen Datentypen arbeiten Je nach Anwendungsfall kommen z B ganze oder komplexe Zahlen vor Es ist auch denkbar dass gemischte Tupel von beliebiger Gr e verarbeitet werden Im Allgemeinen l sst sich nicht abgrenzen was als Repr sentationen der zwischen den Modulen ausgetauschten Daten in Frage kommt und was nicht Deshalb bietet Lethe dem Entwickler die M glichkeit beliebige Typen zu spezifizie ren Die ausf hrliche Diskussion dar ber findet in 41 statt Wichtig f r diese Arbeit 38 4 2 Streams ist dass alle von Entwicklern spezifizierten Typen als sogenannte Basistypen den Mo dulen und den Streams zur Verfiigung stehen Dazu generiert Lethe ftir jeden Basistyp ein Verzeichnis in dem sich unter anderem eine Header Datei befindet die von belie bigen C Modulen eingebunden werden kann Diese Datei definiert im Namensraum Extensions Types eine Klasse mit dem Namen des Basistyps Auch der Name des Verzeichnisses und der Name der Header Dat
128. st Zu diesem Zweck bietet Lethe eine an Syslog 40 angelehnte Schnittstelle zum Ausgeben von Lognachrichten Diese Nachrichten werden ber die ICE Middleware an einen zentralen Logging Server den sogenannten Breeze Server geschickt Die urspr ngliche Idee f r Lethe war den IceStorm Dienst zu verwenden vgl ICE Benutzerhandbuch Kap 42 21 Dieses Publisher Subscriber System w rde es erm g lichen alle Interessierten sofort ber ein Ereignis zu benachrichtigen Allerdings persi stiert IceStorm nicht Der Benutzer m chte aber z B am n chsten Morgen wissen was ber Nacht mit seinen Simulationen geschehen ist Man muss also den IceStorm Dienst dahingehend erweitern dass er Ereignisse persistiert und auf Anfrage wieder versendet Aus Zeitgr nden wurde diese Idee allerdings gegen eine einfachere L sung den Breeze Server ersetzt Dieser Dienst persistiert alle Nachrichten kann diese aber nicht pushen Statt dessen muss jeder Interessierte den Dienst regelm ig abfragen um auf dem Lau fenden zu bleiben Eine Nachricht besteht dabei aus einem Typ einer Herkunft einem Text und einem Zeitstempel der vom Breeze Server bei Eingang der Nachricht gesetzt wird Auf alle diese Felder kann serverseitig gefiltert werden so dass man sich z B nur die kritischen Fehler einer bestimmten Simulation seit gestern Abend anzeigen lassen kann Im Folgenden sind die Typen einer Lognachricht und ihr gedachter Einsatzweck defi niert emergency
129. stehen ist die Messgenauigkeit zu niedrig Es l sst sich nur absch tzen dass f r die 10 Millionen Konvertierungen pro Port weniger als eine halbe Sekunde ben tigt wurde 5 4 2 Verwendung der Optimierung Die gleiche Messung vgl Tabelle 5 5 mit eingeschalteter Optimierung ergibt die Ei genschaften f r die Kanten aus Tabelle 5 6 In dieser Messung besitzen sie zum ersten Kante 1 2 3 4 Puffertyp int gsl_complex gsl_complex int Basistyp Integer Complex Complex Integer Tabelle 5 6 Die Eigenschaften der Kanten aus der Messung 5 4 2 62 5 5 Erh hung der Blockgr e Mal einen vom Basistyp abweichenden Arbeitstyp was in diesem Fall dazu f hrt dass keine benutzerdefinierten Konvertierungen n tig sind Es ist also zu erwarten dass sich dieselbe Laufzeit wie in der Messung aus Abschnitt 5 3 ergibt was durch die Messungen best tigt wurde 5 5 Erh hung der Blockgr e Verwenden die Knoten gr ere Blockgr en dann kommt es bei der gleichen Datenmen ge insgesamt zu weniger Schreib und Leseaufrufen wodurch der Verwaltungsaufwand sinkt Die folgende Messreihe pr ft in welchem Rahmen sich die nderung des Verwal tungsaufwandes dabei bewegen kann Dazu wird die Implementierung der Knoten dahingehend ver ndert dass sie ber die Vektor Objekte die nun gro e Bl cke von Daten enthalten iterieren und die Daten einzeln wie bisher durchreichen Zu jeder Blockgr e wird anschlie
130. t Auch hier kann der Knoten seine Entfernung falls n tig verhin dern So lange es noch Leser gibt die auf die Daten eines Knotens angewiesen sein k nnten ist es wichtig dass dieser Knoten normal weiterarbeitet Deshalb muss es f r ihn in so einem Fall transparent sein ob die Kante in die er schreibt noch einen Leser besitzt oder nicht Das ist der Grund f r die dritte Regel Hier stellt sich noch die Frage warum ein Knoten nicht sofort aus dem Graphen entfernt wird wenn der letzte Leser beendet Der Grund daf r ist dass es f r die In itialisierung von Kanten vgl Abschnitt 3 1 7 n tig ist dass ein Knoten in eine Kante schreiben kann zu der noch kein Leser existiert Um zu garantieren dass die Simulation terminiert ist es hinreichend wenn jeder Be obachter vom Benutzer ein erreichbares Abbruchkriterium erhalten hat und der Sche duler jeden verbliebenen Beobachter regelm ig als initialen Knoten w hlt Letzteres garantiert dass jeder Beobachter die M glichkeit erh lt sein Abbruchkriterium zu er reichen auch wenn der Graph durch die Entfernung von Knoten in Teilgraphen zerf llt Ein isolierter Beobachter der durch das implizite Scheduling nicht mehr erreicht werden kann w rde andernfalls zu einer nicht terminierenden Simulation f hren Da ein Beob achter auch implizit beenden kann ist die obige Bedingung brigens keine notwendige Bedingung f r die Terminierung der Simulation W hlt der Scheduler die initialen
131. t wenig Redundanz robust gegen bertragungsfehler machen kann Die Komplexit t der Systeme die sich bei der Erforschung geeigneter Algorithmen ergeben ist ohne Hilfsmittel allerdings kaum in den Griff zu bekommen Eines dieser Hilfsmittel ist die Simulation Dabei berechnet ein Computer anhand eines Modells m glichst exakt wie sich das System bei einem echten Einsatz verhalten w rde Es existiert also ein Markt f r Simulationsprogramme und er wird reichlich bedient Doch keine der L sungen sch pft die M glichkeiten die sich durch verteiltes Rechnen er geben ausreichend aus obwohl in den meisten Forschungseinrichtungen viele Computer vorhanden sind Deshalb bleibt es dem Anwender berlassen die Probleme zu l sen die sich beim Einsatz in einem Netzwerk ergeben es gibt keine automatisierte Verteilung keine Ausfallsicherheit und keine zentrale Verwaltung f r Ressourcen Simulationen und Benutzer Diese Arbeit behandelt den Entwurf und die Implementierung von Lethe einer L sung dieser Probleme Lethe ist zum einen ein verteiltes System mit einem zentralen Anwenderprogramm f r die Erzeugung und Verwaltung von Simulationen Neben der automatisierten Verteilung erm glicht Lethe es Simulationen im laufenden Betrieb auf andere Computer zu migrieren Damit ist eine flexible Nutzung der zur Verf gung ste henden Ressourcen m glich Au erdem erstellt Lethe in regelm igen Abst nden Siche rungspunkte von Simulationen die jederzeit
132. ten Simulator 2 4 Hypergraphen Die Graphentheorie ist eine alte und allgemein bekannte Disziplin der Mathematik Dementsprechend exsitiert sehr viel Literatur zu diesem Thema Allerdings ist die Defi nition eines Hypergraphen nicht allgemein bekannt Deshalb erl utert dieser Abschnitt sehr knapp die zentralen Eigenschaften die in sp teren Kapiteln von Relevanz sind Ein Graph besteht aus einer Menge von Knoten und einer Menge von Kanten Jede Kante verbindet immer genau zwei Knoten Bei einem gerichteten Graphen besitzen die Kanten eine Richtung Der ungerichtete Graph ist ein Spezialfall des gerichteten Gra phen da eine ungerichtete Kante zwei gerichteten Kanten mit entgegengesetzer Rich tung entspricht Jede beliebige Teilmenge von Knoten mit dazugeh rigen Kanten wird als Teilgraph bezeichnet Ein Hypergraph ist eine Verallgemeinerung eines Graphen Anstatt Kanten besitzt ein Hypergraph sogenannte Hyperkanten die mehr als nur zwei Knoten miteinander verbin den k nnen Ist die Hyperkante gerichtet zerf llt die Menge der verbundenen Knoten in die Menge der Anfangskonten und die Menge der Endknoten G ngige Eigenschaften von Graphen wie z B Zyklen sind f r Hypergraphen analog definiert Jeder ungerichtete Hypergraph l sst sich auf einen einfachen Graphen abbilden indem ein neuer Knoten eingef hrt wird der mit allen Knoten der Hyperkante durch eine 2 Grundlagen und Stand der Technik D8 Hod Abbildung 2 1 Abbildung eines g
133. tigen Strukturen und wartet auf weitere Anweisungen Der Manager kann nun entweder eine Runde der Simulation starten start oder einen gespeicherten Zwischen zustand einer Runde laden und fortsetzen lassen resume Der Manager kann eine laufende Simulation jederzeit anhalten stop Optional kann er dabei den aktuellen Zwischenzustand anfordern suspend den er sp ter ggf auf einem anderen Computer fortsetzen lassen kann Hat der Manager eine Simulation mit oder ohne Erhebung des Zwischenzustandes angehalten existieren f r ihn drei M glichkeiten Erstens kann er die Simulation ein fach weiterlaufen lassen continue Zweitens kann er einen Zwischenzustand laden und diesen fortsetzen lassen resume Drittens kann er einfach eine beliebige Runde der Simulation starten lassen start In den letzten beiden F llen wird der aktuel le Zwischenzustand der Simulation verworfen und ist falls der Manager sich ihn nicht zuvor hat geben lassen verloren Unabh ngig davon ob die Simulation momentan l uft oder angehalten wurde kann sich der Manager den aktuellen Zwischenzustand geben lassen createCheckpoint Ist die Simulation im Zustand RUNNING l st das Kommando intern einen suspend gefolgt von einem continue aus Wie Abschnitt 3 1 9 erl utert kann beliebig viel Zeit vergehen bis ein Zwischenzu stand erhoben werden kann Das liegt daran dass die Simulation nur zu bestimmten Zeitpunkten berhaupt einen persistierbaren Zustand erreicht Das
134. tigt sich damit wie die L sungen des Entwurfs tats chlich umgesetzt werden Trotz der Aufteilung in zwei Diplomarbeiten werden nicht alle Fragen gekl rt die sich bei der Diskussion um Lethe ergeben Kapitel 6 listet diese offenen Fragen auf und bietet einen Ausblick auf eventuelle Folgearbeiten Die Zusammenfassung in Kapitel 7 rundet die Arbeit ab 1 2 Die Anforderungen Wie schon erw hnt muss das Framework vor allem die Erstellung von Sicherungspunk ten und die Migration von Simulationen erm glichen Dar ber hinaus ist die Wieder verwendbarkeit von Implementierungen eine zentrale Anforderung Auf Grund der langen Simulationslaufzeiten ist au erdem die Ausf hrungsgeschwindig keit der Simulationen von gro em Interesse Des Weiteren muss die Programmierschnitt 1 2 Die Anforderungen stelle zum einen m chtig genug sein um alle Anwendungsf lle abzudecken und zum anderen intuitiv bedienbar sein Letzteres impliziert vor allem dass der Entwickler keinen Code schreiben muss dessen Zweck und Hintergr nde nicht offensichtlich sind Au erdem m ssen berall Vorgaben existieren die zu einem sinvollen Verhalten der Laufzeitumgebung f hren Damit muss der Entwickler nur das bedenken was f r seinen Fall von Relevanz ist 2 Grundlagen und Stand der Technik Dieses Kapitel besteht aus zwei Teilen Zuerst klart Abschnitt 2 1 welche Alternativen zu Lethe existieren und an welchen Stellen es sich von ihnen abgrenzt Die restlichen
135. tmangel entstanden Der Hauptnachteil gegen ber der urspr nglich gedachten L sung dem IceStorm Dienst zu verwenden ist dass der Benutzer regelm ig nach neuen Lognachrichten fragen muss Sollte sich herausstellen dass ein Pushdienst erhebliche Vorteile mit sich bringen w rde so m sste man die urspr nglich gedachte L sung umsetzen und den IceStorm Dienst so erweitern dass er Nachrichten persistiert und auf Anfrage hnlich wie der Breeze Server wieder zur Verf gung stellt 6 4 2 Fehlersuche Wie Abschnitt 3 2 3 erkl rt wird f r jede Simulation ein eigenes Programm erstellt Fehler des Benutzers oder des Entwicklers k nnen dabei zu Compiler oder Linker fehlern f hren Der Benutzer muss dann die Fehlersuche anhand der Fehlermeldungen vornehmen Teilweise l sst sich diese Situation verhindern wenn das Anwenderprogramm fr hzei tig eine Analyse der Benutzereingaben vornimmt Dabei besteht die M glichkeit dem Benutzer mitzuteilen an welcher Stelle ihm Fehler unterlaufen sind Wenn ein Entwickler allerdings etwas bei der Implementierung einer Konvertierungsfunktion vgl Abschnitt 4 2 4 oder eines Moduls vgl Abschnitt 4 4 2 falsch macht kann das erst vom Compiler erkannt werden Eine M glichkeit die Situation zu verbessern ist ein Nachschlagewerk mit den g n gigsten Benutzer und Entwicklerfehlern inklusive der dazugeh rigen Compiler oder Linkerfehlermeldung zu erstellen Dazu muss ein geeigneter Weg der Darstellung
136. ucht der Ringpuffer eines Streams mehrere Lesezei ger die unabh ngig voneinander bei Leseaufrufen der entsprechenden Module erh ht werden Ein Puffer ist deshalb genau dann voll wenn der Schreibzeiger einen beliebigen Lesezeiger erreicht hat Ansonsten ist die Implementierung die eines typischen Ringpuf fers so dass hier nicht n her darauf eingegangen wird Die Konsequenz des zweiten Punktes ist dass die Leser und Schreiber direkte Zei ger in den Puffer erhalten Dadurch kann ein Modul die Daten zwischen zwei Streams abbilden ohne dass dazwischen kopiert werden muss Allerdings ergeben sich dadurch zwei Probleme Erstens ist der Umbruch am Ende des Puffers ein Sonderfall der be handelt werden muss Zweitens vergeht beliebig viel Zeit zwischen dem Schreibzugriff eines Moduls und der tats chlichen Aktualisierung der Daten im Puffer Dadurch k n nen zwischenzeitlich durch implizites Aufrufen andere Module auf den Stream zugreifen Dasselbe gilt analog f r Lesezugriffe Die Konsistenz der Streams muss also gesichert werden Abschnitt 4 3 1 erkl rt wie die Ports die beiden obigen Probleme l sen 37 4 Implementierung 4 2 2 Die Gr e eines Puffers Falls der Lese bzw Schreibaufruf eines Moduls zu einem impliziten Aufruf des Schrei bers bzw des Lesers f hrt darf es nicht passieren dass der anschlie ende Schreib bzw Leseaufruf auf demselben Stream wiederum zu einem impliziten Aufruf des urspr ng lichen Moduls f hrt Den
137. uf des Loggers l st einen ICE Aufruf im Netzwerk aus da die Meldung zum Breeze Server transportiert werden muss Das muss synchron gemacht werden damit eine Fehlersuche mittels Lognachrichten m glich ist Es ist also zu beachten dass die berm ige Verwendung des Loggers die Laufzeit steigert Deshalb existiert f r Debugging Zwecke das Macro DEBUGOUT Es bildet auf die Funk tion Core Logger debug ab wenn die Simulation mit Debugging compiliert wird Wird die Simulation ohne Debugging compiliert werden alle DEBUGOUT Aufrufe weg optimiert Das daf r verwendete Macro ist dasselbe Macro das Assertions deaktiviert Eingeschaltet wird es durch die Compileroption DNDEBUG Der Aufruf von oben sieht mit dem DEBUGOUT Macro folgenderma en aus DEBUGOUT getVertexName something happened 4 4 2 4 user_trigger Das ist die zentrale Funktion eines Moduls Hier werden eingehende Daten auf ausge hende Daten abgebildet Gerufen wird die Funktion solange bis das Modul beendet Ein Aufruf kommt dabei entweder direkt vom Scheduler oder implizit von einem Stream vgl Abschnitt 3 1 3 1 Decision user_trigger Lethe Caller caller 2 InputVector input ports input 1 3 OutputVector output ports output 1 4 GSL_REAL output 0 5 GSL_REAL input 0 6 gsl_ran_gaussian _rng _settings sigma 7 GSL_IMAG output 0 8 GSL_IMAG input 0 9 gsl_ran_gaussian _rng _settings sigma
138. ufen mehrere Algorithmen gleichzeitig und unabh ngig voneinander ab Es findet also per Definition ein Multitasking statt Die ser Abschnitt diskutiert welche M glichkeiten des Multitaskings existieren und welche davon die schnellste ist Zur Kl rung der hier verwendeten Begriffe kann z B 38 kon sultiert werden Eine Form des Multitaskings ist die Verwendung von mehreren Prozessen Das ist die typische Architektur moderner Betriebssysteme um mehrere Programme gleichzeitig und unabh ngig voneinander auszuf hren Im Falle einer Simulation existiert also pro Algorithmus ein Prozess Da die einzelnen Prozesse allerdings in voneinander getrennten Adressr umen liegen muss zur Kommunikation das Betriebssystem verwendet werden Neben den Kontextwechseln zwischen den Prozessen die auf Grund des Wechsels des Adressraumes bereits teuer sind m ssen also noch Kontextwechsel ins Betriebssystem gemacht werden Dieser Ansatz ist also sehr langsam Eine bessere M glichkeit ist jeden Algorithmus in einem eigenen Thread laufen zu lassen Zwei Threads laufen im Gegensatz zu zwei Prozessen im selben Adressraum Der Kontextwechsel zwischen ihnen ist also billiger und f r die Kommunikation wird das Betriebssytem nicht gebraucht Dennoch wird weiterhin das Scheduling vom Be triebssytem erledigt Doch auch dieser Ansatz kostet unn tig Laufzeit Erstens erfordert die Nebenl ufigkeit eine Synchronisation an den bergabestellen Dazu muss ein kritischer Be
139. ulation Verhalten sich die Knoten passend ist der Verlauf des Fortschrittes z B linear so dass eine Absch tzung der Gesamtlaufzeit m glich ist Einsammeln der Ergebnisse user_getResult Am Ende der Simulation wird jeder Knoten aufgefordert aus den protokollierten Informationen ein Ergebnis zu er mitteln und es der Laufzeitumgebung zu bergeben Falls ein Knoten nichts pro tokolliert hat kann er eine leere Menge bergeben Zerst ren eines Knotens user_finish Am Ende der Simulation wird jeder Knoten gebeten evtl belegte Ressourcen wieder frei zu geben Anschlie end werden alle Knoten und die Laufzeitumgebung zerst rt Diese Methode kann zu jedem Zeit punkt aufgerufen werden und ist deshalb in Abbildung 3 5 zur Erhaltung der bersichtlichkeit nicht eingezeichnet In welcher Reihenfolge die Interaktionen tats chlich statt finden h ngt vom Manager vgl Abschnitt 3 2 ab Dieser bestimmt n mlich entweder automatisch oder gesteuert durch den Benutzer was mit den Simulationen geschehen soll Abbildung 3 5 zeigt welche Reihenfolgen der Interaktionen dabei allgemein m glich sind 3 1 11 Die Simulationsbeschreibung Lethe braucht f r die Simulation eine ganze Reihe von Metainformationen vom Benutzer Diese werden im Folgenden zusammengefasst e die Menge der beteiligten Knoten 27 3 Systementwurf e den Hypergraphen den die beteiligten Knoten miteinander bilden vgl Abschnitt 3 1 2 e die Mindestgr e jeder K
140. ur die Klassen aus Extensions Module Die generierten Klassen stehen in mehreren Dateien die alle in einem Verzeichnis mit dem Namen des Moduls liegen Details dazu finden sich in 41 Wichtig f r diese Arbeit sind nur zwei dieser Dateien eine Header Datei mit dem Namen des Moduls und eines Datei mit dem Namen config mak Die erste Datei definiert die Modul Klasse Wie Abschnitt 2 5 erkl rt ist die unzureichende Unterst tzung der C Compiler f r Templates der Grund daf r dass die Implementierung des Moduls in einer Header Datei stehen muss Diese Datei wird im Folgenden als die Modul Datei bezeichnet Analog zu Abschnitt 4 2 4 kann der Entwickler mit der zweiten Datei das Verhalten des Buildsystems steuern 4 4 1 Verwaltungsklassen Im Kapitel ber den Entwurf von Lethe wird mehrfach erw hnt dass der Entwickler spezielle Typen f r ein Modul spezifizieren kann Damit kann er kontrollieren wie die Konfiguration die Einstellungen der Zustand und die Ergebnisse eines Moduls aussehen Lethe generiert aus diesen Spezifikationen C Klassen vgl 41 46 4 4 Module Die generierte Module Klasse enthalt von jedem Typ ein Objekt Der Zweck dieser Objekte ist zum einen alle gleichartigen Informationen zu sammeln Zum anderen ver wenden die vordefinierten Funktionen der Module Klasse diese Objekte so dass der Entwickler in vielen F llen die Funktionen nicht ver ndern muss Die Definition der Objekte sieht in einem Modul folge
141. utet dass der Entwickler die Algorithmen zur Verteilung von Hand implementieren muss Letzteres zwingt sogar zum Einsatz einer homogenen Hardwarelandschaft Diesen Nachteil bringen auch die Pakete mit die eine transparente Verteilung bieten da sie einen Cluster wie z B Beowulf 1 voraussetzen Scilab unterst tzt die PVM von Haus aus F r GNU Octave existiert ein MPI basierter Klon namens Parallel Octave Beide bringen jeweils die oben genannten Nachteile mit sich Matlab und seine Alternativen bringen keine Unterst tzung zum Migrieren von Si mulationen oder zum Erstellen von Sicherungspunkten mit Auch die Verteilung der Rechenkapazit ten im Netzwerk und die Durchsetzung von Interessen verschiedener Be nutzergruppen muss mit Mitteln der jeweiligen Systeme von Hand gemacht werden Da so etwas von einer Plattform f r numerische Berechnungen auch nicht erwartet wird ist das nicht verwunderlich Dennoch ist der Einsatz dieser Programme in einem Netzwerk deshalb unkomfortabel und fehlertr chtig 2 Grundlagen und Stand der Technik Wer dem oben erw hnten Programmieraufwand zur Erstellung einer Simulation ent gehen m chte greift zu einem auf Simulationen spezialisierten Programm wie z B GoldSim 15 ber eine graphische Benutzeroberfl che kann der Anwender dort sei ne Simulation zusammenstellen und die einzelnen Komponenten konfigurieren Dabei kann er auf eine umfangreiche Menge von fertigen Kompontenten zur ck greifen so dass er
142. uting John Wiley amp Sons INC 2000 GNU Compiler Collection http gcec gnu org April 2006 GoldSim http www goldsim com April 2006 95 LITERATURVERZEICHNIS 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 96 GNU General Public Licence http www gnu org copyleft gpl html April 2006 H PARTSCH W GUTTMANN Grundlagen des Ubersetzerbaus Vorlesungskript University of Ulm Oktober 2004 HEROLD HELMUT make Das Profitool zur automatischen Generierung von Pro grammen Addison Wesley M rz 2003 HIGH PERFORMANCE FORTRAN FORUM High Performance Fortran Language Spe cification 1992 Howatson M C Reclams Lexikon der Antike Reclam 2006 The Internet Communication Engine http www zeroc com April 2006 L SUSAN BLACKFORD JAMES DEMMEL JACK DONGARRA IAIN DUFF SVEN HAMMARLING GREG HENRY MICHAEL HEROUX LINDA KAUFMAN ANDREW LUMSDAINE ANTOINE PETITET ROLDAN POZO KARIN REMINGTON und R CLINT WHALEY An updated set of Basic Linear Algebra Subprograms BLAS ACM Transactions on Mathematical Software 28 2 S 135 151 Juni 2002 MARK GALASSI JIM DAVIES JAMES THEILER BRIAN GOUGH GERARD JUNG MAN MICHAEL BOOTH FABRICE Ross GNU Scientific Library Reference Manual Network Theory Ltd 2003 Matlab http www mathworks com April 2006 MECKLENBURG ROBERT GNU make O Reilly Mai 2005 MLDesigner http www mldesigner com
143. von der unteren einfordert um die Schedulingentscheidungen treffen zu k nnen Das betrifft vor allem Ausk nfte ber den F llstand des Puffers 4 5 1 Vernetzung Ein Modul kann mit beliebig vielen Streams und ein Stream mit beliebig vielen Modulen verbunden sein 3 1 2 Wenn Streams und Module miteinander kommunizieren brau chen sie folglich ein Adressierungsschema Einfach ausgedr ckt bedeutet das dass die Freignisbehandlungsfunktionen der Streams bzw der Module einen Parameter haben der angibt welches Modul bzw Stream das Ereignis ausgel st hat Eine M glichkeit ist alle Module und alle Streams jeweils zu nummerieren Das w rde zweifelsfrei funktionieren ist allerdings in diesem Fall ungeeignet Der Grund daf r ist dass die Module und die Streams verschiedene Felder besitzen in denen sie f r jeden Kommunikationspartner Informationen zum Scheduling speichern Ein Beispiel hierf r ist die Menge der aktiven Module eines Streams Beim obigen Adressierungsschema muss die Kennung des Partners irgendwie auf einen Index in diese Felder abgebildet werden was sehr umst ndlich ist Deshalb verwendet Lethe ein relatives Adressierungsschema Dabei werden pro Stream die angeschlossenen schreibenden Module durchnummeriert Die Reihenfolge der Module entspricht dabei der Reihenfolge der dazugeh rigen Ports die sie in der Simulationsbe schreibung bei den Eigenschaften des Streams haben Dasselbe wird f r die lesenden Module gemacht Umge
144. zu bertragen bleibt 25 3 Systementwurf user_serialize user_getProgress user_newPhase user_trigger user_init user_reset user_deserialize user_getResults Abbildung 3 5 Interaktion eines Knotens mit der Laufzeitumgebung als einzige einfache M glichkeit mit der Erfassung des Zwischenzustandes zu warten bis der Aufruf des initialen Knotens beendet und der Wartestack damit leer ist Das Scheduling vgl Abschnitt 3 1 3 garantiert dass der Wartestack immer wieder leer wird und sorgt au erdem daf r dass die Wartezeit darauf minimal ist 3 1 10 Der Lebenszyklus eines Knotens Der Lebenszyklus eines Knotens ist eine Folge von verschiedenen Interaktionen mit der Laufzeitumgebung Zu jeder Interaktionsm glichkeit geh rt in der Implementierung eine Methode deren Namen in Abbildung 3 5 vorweggreifend schon genannt werden Im Folgenden ist zusammenfassend und erg nzend die Menge der Interaktionen eines Knotens mit der Laufzeitumgebung aufgelistet Die Namen der zugeh rigen Methoden der Implementierung sind dabei hervorgehoben Initialisierung user_init Zu Beginn einer Simulation erh lt jeder Knoten bei seiner Initialisierung eine benutzerdefinierte Konfiguration vgl Abschnitt 3 1 2 letzter Absatz Beginn einer neuen Runde user_reset Jeder Knoten bekommt zu Beginn einer neu en Runde seine Einstellungen vgl Abschnitt 3 1 5 Beginn einer neuen Phase user_newPhase Jeder Knoten wird ber
145. zustandsbehaftete Bibliothek keine M glichkeit ihre Zust nde zu lesen und zu schreiben ist sie f r den Einsatz innerhalb von Lethe schlecht geeignet In diesem Fall muss der Entwickler entscheiden ob sich die Tatsa che dass nach einem Umzug diese Zust nde wieder einen initialen Wert annehmen auf das Simulationsergebnis auswirkt Falls es eine M glichkeit gibt diese aber nicht platt formunabh ngig ist bedeutet ihre Verwendung dass der Einsatz der entsprechenden Implementierungen auf homogene Netzwerke beschr nkt ist Es liegt in der Hand des Entwicklers was der Zustand eines Knotens alles umfassen kann Die Arbeit von Stephanie Wist 41 behandelt wie der Entwickler die Zustands menge die brigens durchaus leer sein kann spezifiziert und wie sichergestellt wird dass die ICE Laufzeitumgebung damit umgehen kann Bei der Erhebung eines Zwischenzustandes werden auch die Zust nde der Kanten erfasst Dazu geh ren insbesondere die im Puffer enthaltenen Daten Zum Zustand des Schedulers geh ren die aktuellen Mengen der Beobachter der Protokollierer und der bereits beendeten Knoten und die Nummer der aktuellen Phase Um zu garantieren dass es f r die Ergebnisse keine Rolle spielt ob eine Simulation einmal persistiert und wieder fortgesetzt wurde oder nicht muss das Scheduling bei einer Fortsetzung an exakt derselben Stelle weitermachen Da es keine portable M glichkeit gibt den Wartestack des Schedulings auf einen anderen Computer

Download Pdf Manuals

Related Search

Related Contents

SIDE- POWER  JVC AV-27F703 User's Manual    File  MSDSを参照する  Microlife O3 Navigation Manual    Introduction 1 Premi ere pr esentation 2 Comment ajouter un article  ファイルサポート用品（P86～P111）  APC Smart  

Copyright © All rights reserved. Failed to retrieve file