Institute of

Theoretical Computer Science

Carl-Friedrich-Gauß-Fakultät

Technische Universität Braunschweig

SEP: UnicornPL

Ziel des Softwareentwicklungsprojektes UnicornPL ist es, eine Programmiersprache zu erstellen, welche native Unterstützung für Nebenläufigkeit und Distribution bietet. Zur Kommunikation zwischen nebenläufigen Komponenten soll Message-Passing verwendet werden. Im Gegensatz zu den meisten bekannten Programmiersprachen, wie z.B. Java, bedeutet dies, dass zur Kommunikation kein geteilter Speicher (Shared-Memory) zur Verfügung steht. Die neue Programmiersprache soll auf eine existierende Hochsprache abgebildet werden.

Der Fokus unserer Sprache liegt darin, sogenannte Stencil-Codes verteilt zu berechnen. Diese Art der verteilten Berechnung ist im High-Performance Computing auf Clustern weit verbreitet; unter anderem, da dieses Entwurfsmuster eine schwache Synchronisation der einzelnen Komponenten erlaubt und somit zum Load-Balancing beiträgt. In diesem Projekt wollen wir insbesondere das Game of Life (ein 2-dimensionaler Stencil-Code, Simulator hier) betrachten und in der neuen Programmiersprache implementieren.

Lerninhalte

Die Teilnehmer erlangen/vertiefen während des Projektes ihre technischen Fähigkeiten in folgenden Gebieten:

Es steht den Teilnehmern frei, die eingesetzten Technologien selbst zu wählen. Insbesondere kann zur Implementierung und Abbildung durch den Compiler eine beliebige Hochsprache verwendet werden. Auch der Parser-Generator kann frei gewählt werden. Wir empfehlen allerdings, Java, RMI und ANTLR zu verwenden.

Beispiel und Motivation

Wir betrachten im folgenden einen einfachen Stencil-Code, der auf einem 2D-Grid arbeitet. Eine Iteration des Stencils soll für eine Zelle bedeuten, dass ihr neuer Wert die Summe aller ihrer direkten von-Neumann-Nachbarn (Manhattandistanz 1) wird. Der Rand des Grids wird dabei als 0 interpretiert. Folgender Übergang wäre dementsprechend eine Iteration: 

    1   2   7   4            2  11   7  17
    0   3   1  10     →     13   5  21  12
    9   2   1   7            2  13  10  11

Für das obige 4x3 Grid ist eine nebenläufige/verteilte Rechnung sicherlich nicht sinnvoll. Wenn es sich allerdings um sehr große Grids handelt, kann es durchaus zu einer Beschleunigung kommen. In solchen Fällen unterteilen wir das gegebene Grid in n gleich große Teile, wobei n die Anzahl der nebenläufige Worker ist. Für zwei Worker könnten wir das obige Grid in zwei 2x3 Subgrids aufteilen. Um z.B. den neuen Wert der 3. Spalte zu berechnen, muss der Inhalt der 2. Spalte bekannt sein. Es muss Kommunikation stattfinden: jeder Worker muss Teileergebnisse einer Iteration im Rand des Subgrids (halo genannt) an alle anderen Worker weitergeben. In UnicornPL bedeutet dies, dass eine Message gesendet werden muss; ein direkter Zugriff auf den Speicher ist nicht möglich.

Dieses Programmierparadigma mag auf den ersten Blick ungewöhnlich und ineffizient wirken. Allerdings bietet es einen entscheidenden Vorteil: es ist inhärent frei von einer Klasse von Programmierfehlern, sogenannten Data-Races. Data-Races sorgen in größeren Projekt oft für Fehler, da sie laut Spezifikation der meisten Hochsprachen zu undefiniertem Verhalten führen und dieses auch aufzeigen. Solche Fehler zu finden, stellt sich in der Praxis allerdings als hochgradig schwierig heraus.

Sprache

Die zu entwickelnde Sprach soll folgender EBNF folgen. 

    Program     ::= Function* Unicorn Run
    Unicorn     ::= 'unicorn' '(' QueueList ')' Body
    Function    ::= Ident '(' ParamList ')' ':' Type Body
    Run         ::= 'run' '(' ParamList ')' Body
    Body        ::= '{' Statement* '}'
    QueueList   ::= ('!' | '?') Ident ':' Type
                  | ('!' | '?') Ident ':' Type ',' QueueList
    ParamList   ::= ''
                  | Ident ':' Type (',' Ident ':' Type)*
    Type        ::= ('void' | 'bool' | 'int' | 'char' | 'string') '[]'*
                  | '<' Type ',' Type '>'
    QueueAccess ::= Ident '<<' UnicornExpr '.' Ident
                  | UnicornExpr '.' Ident '<<' Expr
    UnicornExpr ::= $id
                  | $total
                  | $(Expr)

Dabei spiegelt die unicorn-Prozedur einen einzelnen Schritt des zu simulierenden Stencil-Codes dar. Des Weiteren soll die Laufzeitumgebung automatisch dafür sorgen, dass all verfügbaren Ressourcen verwendet werden. Das heißt, alle verfügbaren Kerne und verteilten Komponenten sollen zur Berechnung verwendet werden. Ein weiterer Aspekt, um schwache Synchronisation zu verwenden, ist, dass die nebenläufigen Worker sich gegenseitig überholen können und lediglich auf Grund von Datenabhängigkeiten ausgebremst werden. Das heißt insbesondere, dass sich verschiedene Worker zur gleichen Zeit in verschiedenen unicorn-Iterationen befinden können

Um einen ersten Eindruck für unsere Sprache zu bekommen, zeigt das folgende Beispiel, wie ein einfaches Consumer/Producer-Pattern implementiert werden könnte. 

    Produce (val : int) : void {
        $0.input << val    // send to self for next iteration
        $1.input << val    // send to consumer
    }
    
    Consume () : int {
        res : auto          // type inference
        res << $id.input    // get from input queue
        return res
    }
    
    unicorn (?input : int, !ouput : string) {
        if ($id == 0) {         // PRODUCER
            local : auto         
            local << $0.input   
            local++
            Produce(local)
        } elseif ($id == 1) {   // CONSUMER
            local : auto
            local = Consume()
            clear ouput                      // only last output relevant
            $1.ouput << "Consumed " + local  // generate output
        }
    }

    run () {
        $0.input << 0   // initialize the queue of the producer
        unicorn<77>     // let the unicorn run for 77 iterations
        print $1.output // print produced value
    }

Hinweis: Im obigen Programm arbeiten nur die Worker-Threads mit den IDs 0 und 1. Für Stencil-Codes im Allgemeinen verwendet man jedoch Implementierung, welche unabhängig von der tatsächlich Anzahl an Workern ist.

Ansprechpartner

Betreut wird das Projekt durch Roland Meyer, Sebastian Muskalla und Sebastian Wolff.