Untersuchungen zur parallelen, objektorientierten Verkehrssimulation

Um Mehrprozessorsysteme mit verteiltem Speicher effizienter für die Simulation von Verkehr nutzen zu können, wurde innerhalb einer Dissertation untersucht, in wieweit sich objektorientierte Verkehrssimulationen und insbesondere die in unserer Arbeitsgruppe entwickelte Software PLANSIM-T parallelisieren lassen. Wesentlich hierzu ist die hinsichtlich der Lastenverteilung ausgewogene Zerlegung des zugrunde liegenden gewichteten Objektgraphen, der das Straßennetz mit seinen Eigenschaften repräsentiert. Die daraus resultierenden Teilgraphen werden dann parallel von unterschiedlichen Rechnern oder Prozessoren bearbeitet. Um die Kommunikation zwischen den einzelnen Prozessen niedrig zu halten, ist es nötig, die Anzahl der geschnittenen Kanten möglichst gering zu halten, da eine Absprache zwischen den Prozessoren genau dann erforderlich ist, wenn Fahrzeuge zwischen zwei Teilnetzen bewegt werden.

Aus diesem Grund ist der Algorithmus, der das Netz auf die Prozessoren aufteilt, besonders wichtig. Es wurden hierfür verschiedene Verfahren untersucht, die zur Zerlegung eines Objektgraphen verwendet werden können. Dabei wurden sowohl einfache Verfahren betrachtet, die keine Informationen über die Struktur des Graphen verwenden, als auch physikalisch motivierte sowie geometrische Verfahren, die Zerlegungen über die Berechnung von Trägheitsmomenten oder harmonischen Schwingungen finden. Zusätzlich wurden Reduktionsverfahren untersucht, die aus dem Graphen einen vereinfachten Hilfsgraphen konstruieren, der dann mit einem einfachen Verfahren zerlegt wird. Diese Zerlegung lässt sich mit lokalen Optimierungsverfahren auf den ursprünglichen Graphen übertragen. Es hat sich gezeigt, dass als Reduktionsverfahren die von Karypis vorgeschlagen Multilevel

-way Partitionierung die für das vorliegende Problem geeignetesten Ergebnisse liefert. Dieses Verfahren lässt sich zudem sehr gut parallelisieren.

**Abbildung 3.2:** *Erzielte Leistungssteigerung durch die Parallelisierung von PLANSIM-T mit zunehmender Zahl von Prozessoren.*
$\begin{figure}\noindent \centering\epsfig{file=verkehr/figures/rawi.eps,width=\linewidth} \end{figure}$

Neben den theoretischen Überlegungen über die Zerlegung von Straßennetzen wurde eine universell einsetzbare Bibliothek entwickelt, welche es den einzelnen Prozessen ermöglicht, miteinander zu kommunizieren. Diese wurde speziell auf die Verkehrssimulation PLANSIM-T zugeschnitten und greift auf die frei erhältlichen Standardbibliotheken PVM (Parallel Virtual Machine) und MPI (Message Passing Interface) zurück, welche die Programmierung eines heterogenen Netzwerks von parallelen und seriellen Computersystemen als einen einzigen parallelen Rechner mit verteiltem Speicher ermöglicht.

Um die Leistungssteigerung zu messen, wurden verschiedene Netze auf unterschiedlichen Rechnersystemen simuliert und der Geschwindigkeitszuwachs bewertet. Abbildung 3.2 zeigt die Ergebnisse für ein großes Netz von NRW mit über 50.000 Kanten und 65.000 Knoten. Als Testrechner wurde eine SGI SC900XL mit 16 Prozessoren mit je 75MHz und insgesamt 8Gigabyte Hauptspeicher verwendet.

Es zeigt sich, dass die Leistung mit der Anzahl der Prozessoren steigt, dabei jedoch die Zuwachsrate sinkt. Diese Sättigungstendenz hängt mit der Kommunikation zwischen den Prozessoren zusammen, die mit zunehmender Anzahl immer aufwändiger und ineffizienter wird.

Abschließend lässt sich feststellen, dass durch die angewandten Verfahren zur Parallelisierung der Verkehrsflusssimulationen PLANSIM-T wesentliche Leistungssteigerungen erreicht werden können. Die erzielbare Steigerung ist dabei stark abhängig von der Struktur des zugrunde liegenden Straßennetzes. Insbesondere im Hinblick auf große Netze mit vielen Einzelfahrzeugen wurde die Einsatzfähigkeit der Software PLANSIM-T durch die Parallelisierung deutlich erweitert. Die Überlegungen der Arbeit lassen sich desweiteren auf andere Verkehrssimulationen übertragen, die objektorientiert konzipiert sind.