Designing Parallel Algorithms for SMP Clusters

Abstract

In the following thesis, we observe methods for designing and optimizing parallel algorithms for SMP clusters. This particular architecture for parallel computers combines two different concepts. SMP cluster consist of computing nodes that are shared-memory systems, because the processors have access to common resources and especially to the local memory system. Hence, the processors within the same node are capable to communicate and synchronize using the shared-memory. An interconnection network connects the nodes. Communication and synchronization of processors from different nodes is done over this network and thus, correspond to a distributed memory system. In the first place, this organization leads to a parallel hierarchy, because parallelism is involved within and between the nodes. Secondly, a hierarchy is created concerning communication. In general, communication within a node is faster than communication between the nodes due to the use of shared-memory. Therefore, there are at least two levels of hierarchy. Due to modern trends like hierarchical interconnection structures, Metacomputing technology, where several parallel machines are connected, or Grid computing technology that use the Internet to unify distributed computing resources in the whole world, there might be even more levels of hierarchy. Basically, the lower the level of the network for a communication operation, the faster the communication can be done. On this account, efficient algorithms have to be designed in the way that the parallel as well as the communication hierarchy is considered. In the following, we show a concept that shows the dependencies between theoretical cost models, programming models and SMP clusters. It enables the developer to convert a theoretical analysis of an algorithm into an efficient implementation for SMP clusters. Besides the bridge from a theoretical analysis to an efficient implementation, we present several methods for designing and optimizing parallel algorithms for SMP clusters. With the help of case studies, we explain the design methods and the usage of the cost model for the algorithm analysis.

In der vorliegenden Arbeit untersuchen wir Entwurfs- und Optimierungsmethoden für die Entwicklung von parallelen Algorithmen für SMP Cluster. Dabei handelt es sich um eine spezielle Architektur von Parallelrechnern, die zwei verschiedene Konzepte in einem System vereint. SMP Cluster bestehen aus Rechenknoten, deren Prozessoren speichergekoppelt sind (shared-memory). Die Rechenknoten selbst werden durch ein Verbindungsnetzwerk miteinander verknüpft. Die Kommunikation und Synchronisation von Prozessoren in verschiedenen Rechenknoten erfolgt über dieses Netzwerk und entspricht einem Nachrichtengekoppeltem System bzw. einem System mit verteiltem Speicher (distributed-memory). Diese Organisation führt zum einen zu einer parallelen Hierarchie, denn Parallelität gibt es sowohl innerhalb als auch zwischen den Rechenknoten. Zum anderen entsteht eine Hierarchie bezüglich der Kommunikation. Im Allgemeinen ist die Kommunikation innerhalb eines Rechenknotens bei der ein gemeinsamer Speicher verwendet wird schneller, als die Kommunikation über ein Verbindungsnetzwerk.Es existieren demnach mindestens zwei Hierarchiestufen. Durch moderne Entwicklungen wie hierarchische Strukturen von Verbindungsnetzwerken, Metacomputing Technologien, bei der mehrere Parallelrechner verbunden werden oder Grid Computing Technologien, die das Internet verwenden um weltweit verteilte Rechenressourcen zu vereinen, kann es jedoch weitere Hierarchiestufen geben. Auch hier gilt, je "niedriger" die Ebene in der Netzwerkhierarchie, desto schneller ist die Kommunikation. Aus diesem Grund müssen effiziente Algorithmen in der Art gestaltet werden, dass sowohl die parallele Hierarchie als auch die Kommunikationshierarchie berücksichtigt werden. Wir stellen ein Konzept vor, das die Zusammenhänge zwischen theoretischen Kostenmodellen, Programmiermodellen und SMP Cluster aufzeigt und es dadurch ermöglicht eine theoretische Analyse eines Algorithmus in eine effiziente Implementierung für SMP Cluster münden zu lassen. Neben dieser Brücke von einer theoretischen Analyse zur effizienten Implementierung stellen wir verschiedene Methoden für den Entwurf und die Optimierung von parallelen Algorithmen für SMP Cluster vor. Anhand verschiedener Algorithmen erklären wir die Methoden und die Verwendung des Kostenmodells bei der Analyse der entwickelten Algorithmen.