Das Grid-Occam-Projekt
Prof. Dr. Andreas Polze
Dr. Martin v. Löwis
(Rotor Project Proposal in English)
Die auf dem Modell der "Communicating Sequential Processes" (CSP) von Sir Tony Hoare beruhende Programmiersprache Occam wurde zuerst duch die Firma INMOS für die seinerzeit revolutionären Transputer implementiert. Occam bietet Sprachkonstrukte für feingranulare nebenläufige Programmierung und exzellente Unterstützung für Multiprozessor- und Multicomputersysteme. Im Rahmen der Lehrveranstaltung soll eine Umsetzung von Occam für (weit-) verteilte Systeme entwickelt und studiert werden.
Die Lehrveranstaltung wird sich mit Werkzeugen für den Compilerbau und deren Grundlagen auseinandersetzen. Als konkreter Anwendungsfall soll im Rahmen des Praktikums ein Occam-Compiler für Rotor/.NET studiert werden.
Die Leistungserfassung orientiert sich zum einen an der im Laufe des Semesters anzufertigenden Projektarbeit (Compiler, Syntax-Checker, Pretty Printer, Laufzeitsysteme), zum anderen an der zugehörigen Ausarbeitung und Projektpräsentation.
Der Leistungserfassungsprozeß beginnt am 29.4.2004.
Im einzelnen widmet sich die Lehrveranstaltung folgenden Themen:
- Stufen eines Compilers:
- lexikalische Analyse
- Symbole, Alphabete, reguläre Ausdrücke
- syntaktische Analyse
- Sprachen, Grammatiken, LL(1)/LR(1),
rekursiver Abstieg, tabellengesteuerte Parser
- semantische Analyse
- Symboltabellen, Hash-Algorithmen
- Synthese
- kimwitu-Compilerkit, gcc-backend Architekturbeschreibungen
- Werkzeuge zum Compilerbau: kimwitu, yacc/lex, bison/hairy
- Interludium: Der Occam-Sprachstandard
- Fallbeispiele für Compiler:
- Rotor-C#/JScript-Compiler
- Rotor jit
- Java-Implementation von Occam
Die Lehrveranstaltung bietet sich insbesondere Studierenden an, die eine Masterarbeit im Umfeld von ".NET for Embedded Computing" anstreben.
Literatur
Vorlesungsfolien
KRoC
Im CORBA- und Grid-Computing-Labor ist jetzt
KRoC
installiert. Zur Benutzung muss man /usr/local/kroc/bin/setup.sh
einlesen, und kann dann kroc aufrufen.
Praktikumsaufgaben
- Implementieren Sie ein Occam-Laufzeitsystem für .NET (in 100% pristine IL),
welches parallele Prozesse auf Threads abbildet.
- Übertragen Sie zunächst den Occam-Prozess
PROC hello()
INT x,y:
CHAN OF INT c,d:
PAR
SEQ
c ! 117
d ? x
SEQ
c ? y
d ! 118
:
in ein C#-Programm. Trennen Sie den zur Realisierung dieses
Programms nötigen Code in prozessunabhängige Teile
(das Laufzeitsystem) und prozessabhängige Teile (die spätere
Compilerausgabe). Als Vorlage für diese Umsetzung kann
unsere Implementierung eines
Laufzeitsystems für pthreads verwendet werden.
- Erweitern Sie diese Bibliothek um weitere Occam-Konstrukte,
etwa ALT, wiederholte Prozesse, und weitere Datentypen.
- Entwickeln Sie ein Konzept, wie zusätzliche Occam-Konstrukte
(IF, WHILE, CASE) in C#/.NET IL dargestellt werden können.
- Entwickeln Sie auf Basis eines Compiler-Kits (etwa flex, bison,
kimwitu++) einen Compiler für eine Teilsprache von Occam, der Code
für die in Schritt 1 entwickelte Laufzeitbibliothek generiert.
- Entwickeln Sie eine Version des Laufzeitsystems, welches die
Verteilung eines parallelen Occam-Prozesses auf mehrere Rechner
erlaubt.
Präsentation und Dokumentation
Im Verlauf des Semesters wird jede Arbeitsgruppe zweimal den
Projektstand vorstellen: nach dem 17.5. (Präsentation der
Laufzeitbibliothek) und nach dem 17.6. (Präsentation des Compilers).
Am Ende der Veranstaltung muss eine Dokumentation der
Occam-Implementierung erstellt werden, die zumindest die folgenden
Informationen enthält:
- Welcher Teil der Sprache Occam wurde implementiert? Genauer:
- Welche korrekten Occam-Programme werden vom Compiler
abgelehnt, und auf welche Weise? (Syntaxfehler, erkannte semantische
Einschränkung, interner Fehler/Absturz/Exception, Generierung von
syntaktisch falschem C#)
- Welche inkorrekten Occam-Programme werden vom Compiler übersetzt?
- Welche korrekten Programme werden vom Compiler übersetzt, aber
falsch ausgeführt?
- Welche Technologie wurde für die Entwicklung des Compilers und
die Realisierung des Laufzeitsystems eingesetzt?
- Wie wurden ausgewählte Aspekte von Occam in .NET umgesetzt?
Nach Möglichkeit sollten auch für die Programme prim2.occ
und fraktal.occ Performance-Aussagen ermittelt werden.