Das Grid-Occam-Projekt

2004

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.

Material

• HU-Informatik-Bericht 77
• Occam auf WoTUG, Occam Reference Manual
• The Occam archive (Link nicht mehr verfügbar: http://vl.fmnet.info/occam/)
• CSP-Folien von Bill Roscoe (Oxford University Computing Laboratory)
• Ausführungen zum Thema Paralleles Rechnen in Multicomputersystemen
• Occam-Pi
• ion.occ
• Demo-Video (kurz)

Vorlesungsfolien

• Syntax und Semantik von Programmiersprachen
• Übersicht über die OCCAM-Sprachdefinition
• Syntaxanalyse
• Lexikalische Analyse

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

1. Implementieren Sie ein Occam-Laufzeitsystem für .NET (in 100% pristine IL), welches parallele Prozesse auf Threads abbildet.
   1. Ü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.
   2. Erweitern Sie diese Bibliothek um weitere Occam-Konstrukte, etwa ALT, wiederholte Prozesse, und weitere Datentypen.
   3. Entwickeln Sie ein Konzept, wie zusätzliche Occam-Konstrukte (IF, WHILE, CASE) in C#/.NET IL dargestellt werden können.
2. 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.
3. 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.