Deutsch

In dieser Dissertation werden Modelle für parallele Systeme vorgestellt, ein Überblick über Algorithmen für diese Modelle gegeben und effiziente Implementierungen entwickelt. Der Schwerpunkt liegt dabei auf der Familie der Bulk Synchronous Parallel Modelle, da diese die Entwicklung portabler, aber trotzdem effizienter paralleler Programme erlauben. Für die Implementierungen werden zwei Architekturen betrachtet: ein On-Chip-Parallelcomputer und Workstation-Cluster. Mit einem On-Chip-System zeigt die Arbeit, wie das benutzte Modell die Entwicklung applikationsunabhängiger, effizienter, paralleler Systeme unterstützen kann. Auf der anderen Seite des Spektrums paralleler Systeme stehen Workstation-Cluster, auf denen nur freie Rechenkapazitäten genutzt werden. Sie unterscheiden sich vom On-Chip-System durch größere Latenzen, geringere Kommunikationsbandbreite und größeren Arbeitsspeicher. Durch die Heterogenität (z.B. verschiedene Computertypen) und durch die variable, sich ständig ändernde, nutzbare Rechenkapazität der einzelnen Knoten ergeben sich besondere Herausforderungen, z.B. Lastbalancierung. Hierfür wird eine Implementierung vorgestellt, welche mittels virtueller Prozessoren und deren Migration die Last gleichmäßig im Netzwerk verteilt. Exemplarische Implementierungen zeigen, dass die Idee eines allgemeinen Modells funktioniert, d.h., dass ein Algorithmus für dieses Modell zu effizienten Implementierungen auf unterschiedlichen Systemen führen kann.

English

To provide more performance, computers have to utilize more and more processing units. A general model for such systems is needed, which allows portable yet efficient parallel programs. In the thesis, a family of models — the bulk synchronous parallel (BSP) models — is evaluated. The thesis surveys algorithms for BSP, and examines implementations of algorithms as well as libraries supporting the implementation of BSP algorithms on different architectures. A general implementation of BSP, the Paderborn University BSP(PUB) library, is provided, which allows the implementation of efficient BSP algorithms for a wide range of architectures in a very comfortable way. In particular, techniques to utilize unused computational power of existing workstation clusters are considered. Parallelism on a single chip is also investigated, as multi core processors are the most promising way to increase performance for every-day user. It is shown that implementing many simple processors increases parallelism more effectively than implementing only one to four more complex “classical” processors. The benchmarks, although using very small and simple 32 bit RISC processor cores, give an impression of the potential performance of such systems. BSP can be useful in such a scenario as well. Thus, BSP algorithms can be implemented on a large range of parallel systems by using the appropriate compiler and library, without modifying the source code.