PL-REND - Datenstrukturen für Multithreading

Aufgabenstellung:

Eine mit Hilfe einer Reihe besonderer Graphik-Routinen beschriebene Szene (incl. Blickpunkt, Lichtern etc.) soll als ein 2-dim. (Pixel-)Bild dargestellt ("gerendert") werden.

Sourcen:

pl-rend.c Hauptprogramm

stage-g.c Generierungs-Stufe

stage-t.c Transformations-Stufe

stage-c.c Clipping-Stufe

stage-e.c Edge-Stufe

stage-p.c Pixel-Stufe

graphics.h Graphik-Bibliothek (Header)

graphics.c Graphik-Bibliothek (Implementierung)

graphic-utils.h Hilfsfunktionen zur Graphik (Header)

graphic-utils.c Hilfsfunktionen zur Graphik (Implementierung)

boolean.h Wahrheitswerte

queue.h Queue mit Synchronisation (Header)

queue.c Queue mit Synchronisation (Implementierung)

pipeline.h allgemeine Pipeline (Header)

pipeline.c allgemeine Pipeline (Implementierung)

render-pipe.h besondere Graphik-Render-Pipeline (Header)

render-pipe.c besondere Graphik-Render-Pipeline (Implementierung)

Bemerkungen zur skalaren Version:

Graphik-Rendern ist ein Prozeß mit mehreren Stufen:

GENerierung der Szene
Die Objekte - viele Polygone, Lichtquellen, eine Kamera u.a. - werden beschrieben (z.B. mit dem RenderMan-Interface)
TRANsformation
Polygone werden geometrischen Transformationen unterworfen, z.B. Abbildungen in das Kamera-Koordinaten-System oder perspektivische Darstellung.
CLIPping
Polygone außerhalb des Sichtbereichs werden verworfen, solche im Grenzbereich zurechtgeschnitten.
Ecken-("EDGE"-)Berechnung
Die Daten für die Ecken der Polygone, neben den Koordinaten die Farben und Normalen, werden bestimmt.
PIXEL-Berechnung
Jedes Polygon wird pixelweise abgescannt. Nur die Farbe des am dichtesten an der Kamera liegenden Polygons (größter z-Wert) wird abgespeichert (z-Buffer-Verfahren). Am Ende gibt diese Stufe den fertigen Buffer aus (hier in ein File).

Fließband-artiger Kontrollfluß:
Die erste Stufe erzeugt Daten und gibt sie weiter, die anderen lesen "vom Band", arbeiten und geben ggf. wieder Daten zur Weiterverarbeitung an die folgende Stufe:

GEN TRANS CLIP EDGE PIXEL

Die Objekte auf dem Band ("Token") beinhalten eine Aufgabe und die damit
verbundenen Daten. Beispiele:

Beschreibung der Geometrie eines Objekts

GEN erzeugt ein Token mit Polygon-Daten
jede Stufe verarbeitet es und gibt es weiter

Beschreibung einer Lichtquelle

GEN erzeugt ein entsprechendes Token
TRANS und CLIP reichen es einfach weiter
EDGE nimmt es und merkt sich die Daten, um sie bei später kommenden Polygonen anzuwenden.

Programm nach "Programming with Threads" und Beispielsourcen dazu (s.o.).

Grundidee der Parallelisierung:

Jeder Thread entspricht einer Stufe.

Synchronisation der Threads durch eine Pipeline = Kette von Zwischenspeichern (Queues):

Liest ein Thread schneller, als sein Vorgänger Daten liefert, wird er gestoppt, sobald die Queue leer wird.
Schreibt ein Thread schneller, als sein Nachfolger Daten abholt, wird er gestoppt, sobald die Queue voll wird.

Queue

Interface:

queue_t queue_init(int count);

Initialisiere eine Queue der Länge count.

void queue_destroy(queue_t q);

Beseitige die Queue-Struktur.

void queue_put(queue_t q, void *ptr);

Stelle das Objekt, auf das ptr zeigt, ans Ende der Queue.

void *queue_get(queue_t q);

Hole das Objekt von der Spitze der Queue.

Implementierung:

queue_t enthält:

Array von Pointern für die Daten
Indizes, die Anfang und Ende in diesem Array bezeichnen
zwei Bedingungsvariable (Queue leer/voll)
ein zugehöriger Lock

queue_put:

       lock
       Queue voll -> warte
       Queue war leer -> wecke einen möglichen Abholer
       stelle Objekt in die Queue
       unlock

queue_get:

       lock
       Queue leer -> warte
       Queue war voll -> wecke einen möglichen Lieferanten
       hole Objekt aus der Queue
       unlock

Pipeline

Interface:

pipe_t *pipe_init(int size, int q_size, pipe_stage_t stage[],
data_new_t data_new, data_free_t data_free);

Initalisiere die Pipeline: Anzahl der Stufen, Größe der Queues, Funktionen für die einzelnen Stufen (s.u.) und zum Speicher-Management der Token.
Starte die Threads.

void pipe_destroy(pipe_t *pipe);

Warte auf die Threads der Pipeline und räume anschließend auf.

void pipe_put(pipe_t *pipe, void *data);

Stelle data an den Anfang der Pipeline
(wird nur von der Funktion der Stufe 0 aufgerufen).

Das Hauptprogramm macht nichts weiter als die Pipeline zu starten und dann (via pipe_destroy) zu warten. Die eigentliche Initiative geht von der 1. Stufe aus.

Implementierung:

Die von pipe_init gestarteten Threads führen alle die zentrale Funktion pipe_dispatch aus:

       get my stage
       if (stage == 0)
         führe die entsprechende 1. Stufen-Funktion aus
         (die kümmert sich dann darum, die Pipeline zu füttern)
       else
         hole ein neues Token
         übergib dieses der Stufen-Funktion zur Bearbeitung
         entscheide anhand des Return-Codes, ob das (evtl.
            veränderte) Token weitergegeben oder aufgeräumt wird.

Die Pipe wird beendet, indem die 1. Stufe ein shutdown-Token auf die Reise schickt. Dieses wird von allen gelesen und zum Anlaß genommen, die Arbeit einzustellen, nicht ohne die frohe Botschaft seinem Nachfolger zuzurufen.

Render-Pipeline

Die Render-Pipeline ist einfach eine spezialisierte Pipeline mit 5 Stufen (je eine für GEN, TRAN, CLIP, EDGE, PIXEL) und einem besonderem Token-Datentyp nebst zugehörigen Speicher-Management-Funktionen.

Token beinhalten jeweils einen Typ (Aufgabe) und zugehörige Daten. Es gibt folgende Typen:

BEGIN	Initialisierungs-Infos für alle
END	Aufräumen und Beenden, PIXEL schreibt das Ergebnis ins File
POLY	Geometriedaten eines Polygons, für alle
TRANS	Transformationsmatrizen für TRAN
LIGHT	Lichtquelle für EDGE
FOV	spezielle Transformation für EDGE

Graphik-Interface

Die Graphik-Bibliothek enthält neben GiBegin und GiEnd einige Routinen zur Beschreibung von Flächen im Raum (Geometrie und Oberfläche) und Lichtquellen sowie für Transformationen (Verschiebung, Drehung, Skalierung, Projektion). Sie ist stark an das RenderMan-Interface angelehnt.
Diese Routinen enthalten auch die pipe_put-Calls, die die Render-Pipe füttern.

Die GEN-Stufe ist das eigentliche "Anwendungsprogramm", es enthält die Beschreibung der darzustellenden Szene. Dazu baut es aus den Funktionen der Graphik-Bibliothek höhere Funktionen zur Beschreibung von Kugeln, Würfeln, einem Trinkbecher usw. auf und stellt so eine Demo-Szene zusammen:

weitere Bemerkungen

Die Thread-Struktur bzw. Parallelisierung ist vollständig in den Datenstrukturen Pipeline (Thread-Verwaltung) und Queue (Synchronisation) versteckt. Nur der Programmierer der Graphik-Bibliothek muß überhaupt etwas von der Pipeline wissen, sie ist für ihn ein Ausgabedevice (wie ein Framebuffer oder ein File).

Einen gewissen Einfluß auf die Performance hat die gewählte Queue-Größe: Ist sie zu klein, warten Threads vielleicht unnötig auf Arbeit bzw. auf Abnehmer.

Angesichts der ungleichen und sich dynamisch ändernden Arbeitsbelastung der einzelnen Stufen ist das größte Performance-Problem, ein ordentliches Load-Balancing zu erzielen.

Da normalerweise die PIXEL-Stufe einen Großteil der CPU-Zeit schluckt, sollte man sie selbst auch wieder parallelisieren. Dazu eignen sich "normale" Schleifen-Aufteilungs-Verfahren. Diese Mischung mehrerer Parallelisierungs-Methoden ist typisch für "richtige" Anwendungen

Peter Junglas 24.2.1998

pl-rend.c	Hauptprogramm
stage-g.c	Generierungs-Stufe
stage-t.c	Transformations-Stufe
stage-c.c	Clipping-Stufe
stage-e.c	Edge-Stufe
stage-p.c	Pixel-Stufe

graphics.h	Graphik-Bibliothek (Header)
graphics.c	Graphik-Bibliothek (Implementierung)
graphic-utils.h	Hilfsfunktionen zur Graphik (Header)
graphic-utils.c	Hilfsfunktionen zur Graphik (Implementierung)

boolean.h	Wahrheitswerte
queue.h	Queue mit Synchronisation (Header)
queue.c	Queue mit Synchronisation (Implementierung)
pipeline.h	allgemeine Pipeline (Header)
pipeline.c	allgemeine Pipeline (Implementierung)
render-pipe.h	besondere Graphik-Render-Pipeline (Header)
render-pipe.c	besondere Graphik-Render-Pipeline (Implementierung)