Ohne den Umstieg auf Systeme mit mehreren Prozessoren wird sich der in den letzten Jahren erzielte Zuwachs an Rechenleistung kaum in der Zukunft fortführen lassen. Multiprozessorsysteme gewinnen deshalb heutzutage, auch im Bereich der Personal Computer, schon zunehmend an Bedeutung. Mit der Erhöhung der Prozessorenanzahl steigert sich auch die Rechenleistung.
Um aus Multiprozessorsystemen aber auch den gewünschten Geschwindigkeitszuwachs zu erzielen, benötigt man geeignete Algorithmen. Es trifft zwar auch auf ein System mit nur einem Prozessor zu, dass die Laufzeit eines Algorithmus von der Rechenleistung des Prozessors und vom Algorithmus selbst abhängt, aber die Anforderungen beim Design und der Implementierung von parallelen Algorithmen sind höher. Eine Aufgabe muss auf mehrere Prozessoren aufgeteilt werden, welche in der Ausführung miteinander interagieren um zur Gesamtlösung zu kommen. Beim Design paralleler Algorithmen ist man mit zusätzlichen Problemen konfrontiert, welche einer Lösung bedürfen.
Diese Arbeit gibt einen Überblick über das Design von parallelen Algorithmen. Als Modelle zum parallelen Programmieren werden anschließend Message Passing und Shared Address Space vorgestellt. Der praktische Teil der Arbeit beschäftigt sich mit der Parallelität von Algorithmen zur Lösung von Problemen in Graphen. Es werden Algorithmen anhand von Beispielen grafisch in ihren sequentiellen und parallelen Varianten illustriert.