Nächste Seite: Kenntnisstand bei der letzten Aufwärts: SFB376
 |
Sonderforschungsbereich 376Teilprojekt A1: Eine realitätsnahe Theorie effizienter paralleler Algorithmen |
Personal
Leitung:
Prof. Dr. Friedhelm Meyer auf der HeideWissenschaftliche Mitarbeiter:
Dipl.-Inform. Olaf Bonorden (EA)Weitere MitarbeiterInnen:
Dr. Martin Ziegler (EA)
M. Sc. Marcin Bienkowski (GA)
Dr. Fedor V. Fomin (GA)
Dr. Petr Kolman (GA)
Dr. Christian Sohler (GA)
Dr. Rolf Wanka (GA)
Zusammenfassung
Ziel des Teilprojektes A1 ist die Entwicklung und Untersuchung paralleler
Rechenmodelle und Kostenmaße, die einerseits reale Parallelrechner und
deren Kommunikationskosten genügend genau beschreiben, andererseits
aber noch einfach genug sind, um Algorithmen theroretisch zu
analysieren. Für diese Modelle werden Algorithmen entwickelt, analysiert
und implementiert. Für die Implementierung und Evaluation dieser
Algorithmen wurde eine leistungsfähige Plattform (BSP Bibliothek PUB)
geschaffen, die mittlerweile europaweit an vielen Instituten eingesetzt wird.
Im Berichtzeitraum haben wir uns insbesondere mit Untersuchungen zur
Erweiterung unserer
Modelle und Bibliotheken auf heterogene dynamische Umgebungen
auseinandergesetzt.
Die Arbeiten in der Berichtsphase gliedern sich in vier Teilbereiche:
(i) BSP auf heterogenen, dynamischen Netzwerken
Wir betrachteten in diesem Schwerpunkt Netzwerke aus PCs, bei denen eine parallele Anwendung die Idle-Zeiten ausnutzt, d.h. nur die Resourcen, die zum jeweiligen Zeitpunkt vom ,,Benutzer`` des jeweiligen Computers nicht benötigt werden. Wir haben zum einen Modellierungen von Idle-Zeiten und Online-Algorithmen zum Scheduling entwickelt und analysiert. Zum anderen wurde die BSP-Bibliothek PUB um Migrationen von virtuellen Prozessoren erweitert, um Lastschwankungen ausgleichen zu können. Erste Implementierungen von Schedulingalgorithmen für die dynamische Variante der virtuellen Prozessoren wurden implementiert und evaluiert.
(ii) BSP auf statischen Netzwerken
Hier haben wir unsere Arbeiten über parallele Algorithmen der früheren Antragsphasen weiter geführt. Zum einen wurde ein System für verschachtelte Algorithmen im BSP-Modell entwickelt. Es basiert auf einer Sammlung von Algorithmen und -beschreibungen, die zu jedem Algorithmus Informationen über die Worst-Case-Laufzeit und eventuell erzeugte Unterprobleme liefern. Aus diesen Beschreibungen generiert ein Konfigurator dann einen für einen gegebenen Computer, beschrieben durch seine BSP-Parameter, und eine Größe der Eingabedaten einen optimalen Gesamtalgorithmus.
Zum anderen untersuchten wir verschiedene Modellierungaspekte bei BSP-Modellen. Verschiedene Erweiterungen des BSP-Modells, z.B. das von uns entwickelte BSP*-Modell, beziehen weitere Parameter in das Kostenmaß ein, z.B. Nachrichtengrößen, Kommunikationsmuster usw. Hier haben wir untersucht, wie groß der Einfluss dieser Parameter auf die Genauigkeit der Laufzeitvorhersagen ist.
(iii) Routing und Scheduling
In diesem Abschnitt beschäftigten wir uns mit Routing- und Scheduling-Problemen. Wir entwickelten einen Online-Algorithmus für das Disjunkte-Wege-Problem. Weiterhin analysierten wir Disk-Graphen, die das Routing in drahtlosen Netzwerken modellieren, und betrachteten verschiedene Färbungsalgorithmen. Jede Farbe modelliert hierbei eine Funkfrequenz.
Außerdem analysierten wir das Scheduling bei Evolving-Tree-Computations.
Hierbei wird ein vollständiger 
-ärer Baum Level für Level auf ein
Prozessornetzwerk verteilt. Für eine Klasse von Lastbalancierungsverfahren,
die auf so genannten Regimen basiert, konnten wir berechnen, wie sich
die Last der mittleren Last nähert.
(iv) Analyse von Netzwerken
In diesem Abschnitt betrachteten wir einige Eigenschaften von Netzwerken. Wir untersuchten die Eigenwerte von Netzwerken der Hypercubefamilie, die eng mit Routing- und Lastbalancierungs-Eigenschaften dieser Netzwerke zusammenhängen.
Weiterhin führten wir unsere früheren Arbeiten über kurzperiodische
Sortierverfahren fort und entwickelten einen Simulator hierfür.
Olaf Bonorden