SFB 376 Teilprojekt A1

Zusammenfassung

Die Laufzeit von Programmen auf realen Parallelrechnern wird zum erheblichen Teil von den Kommunikationskosten beeinflusst. Reale Parallelrechner bestehen aus einer Anzahl von Prozessoren, die über ein Kommunikationsnetzwerk miteinander verbunden sind. Dabei dauert die Kommunikation der Prozessoren untereinander (z.B. das Versenden von Nachrichten) viel länger als interne Rechenoperationen. Frühere Modelle von Parallelrechnern (PRAM) gingen davon aus, dass Kommunikation und Berechnung gleiche Kosten haben. In diesem Teilprojekt stehen Entwurf und Analyse von parallelen Rechenmodellen im Mittelpunkt, die auch die Kommunikationskosten eines Parallelrechners modellieren, wie beispielsweise das Bulk Synchronous Parallel-Modell (BSP).

Unsere Arbeit in diesem Teilprojekt während des Berichtzeitraums lässt sich in die folgenden Schwerpunkte aufgliedern:

Bulk Synchronous Computing: Modelle & Algorithmen.

Nachdem wir im vorherigen Antragszeitraum eine Verfeinerung des BSP-Modells vorgestellt (das BSP*-Modell) und hierfür Algorithmen entwickelt hatten, stellten wir fest, dass für einige Probleme Modelle wie das BSP-Modell zu ungenau sind, da sie keine Lokalität modellieren. Daher haben wir die Komplexität von Lokalitätsmodellen anhand des Beispielproblems Broadcast untersucht. Desweiteren haben wir Graphprobleme auf dem BSP-Modell betrachtet. Hierbei handelt es sich um eine besonders schwierige Klasse von Problemen, da Kommunikationseffizienz für diese schwer erreichbar erscheint.

Als weiteres interessantes Problem schließt sich an, daß viele BSP-Algorithmen einerseits rekursive Aufrufe enthalten und andererseits andere, bereits gut untersuchte BSP-Verfahren als Unterprogrammaufrufe benutzen. Welche Algorithmen-Variante auf welchem Teil des Parallelrechners in Abhängigkeit von der tatsächlichen Maschine schließlich genutzt werden soll, untersuchen wir bei der automatischen Konfiguration von BSP-Algorithmen.

Bulk Synchronous Computing: Implementationen.

In diesem Teilgebiet ist die Paderborn University BSP-Library (PUB-Library) entstanden. Entsprechend den Wünschen von Nutzern innerhalb des SFBs haben wir PUB erweitert und optimiert. Beispielsweise haben wir das Konzept der BSP Objekte eingeführt und ermöglichen nun die Erzeugung von Untergruppen - was eine einfachere Nutzung und höhere Effizienz ergibt. Weiterhin wurden hier verschiedene parallele Rechenmodelle experimentell evaluiert.

Die ausgeführte Hauptaufgabe in 2000/2001 war die Portierung der PUB-Library auf ein PC-Netzwerk unter dem Betriebssystem Linux und die Realisierung von virtuellen Prozessoren. Diese können, falls ihr aktueller Rechner durch andere Prozesse stark belastet ist, angehalten und zu einem anderen Rechner migriert werden. Die Erforschung und insbesondere experimentelle Evaluierung geeigneter Lastbalancierungsverfahren schließt sich daran an.

Parallele Komplexität.

In diesem Bereich wurden u.A. das Sortierverfahren Shearsort im mehrdimensionalen Fall untersucht, eine Implementierung und Analyse eines hybriden Sortierverfahrens, das Teile der Eingabe parallel auf einem FPGA-Chip sortiert, durchgeführt, parallele Algorithmen zur Erzeugung zufälliger Permutationen vorgestellt, Gossiping-Probleme in Netzwerken betrachtet und untere und obere Schranken für das Job-Shop Scheduling gezeigt.

Sonderforschungsbereich 376

Eine realitätsnahe Theorie effizienter paralleler Algorithmen

Unterabschnitte

Die PUB-Library

Beziehungen zu anderen Teilprojekten

Aktuelle Literatur

Literatur 1996 - 1998

Projektbericht 1996 - 1998

Navigationshilfe: