Identifying and Harnessing Concurrency for Parallel and Distributed Network Simulation

Abstract

Da Netzwerke von Computern inha ̈rent parallele Systeme darstellen, ko ̈nnen Simu- lationen von Computernetzen ha ̈ufig durch parallele und verteilte Ausfu ̈hrung auf mehreren Prozessoren substantiell beschleunigt werden. Simulationsmodelle von Computernetzen ko ̈nnen sich jedoch grundlegend in ihrer Eignung fu ̈r eine Paral- lelisierung unterscheiden. Obwohl sich bereits eine Vielzahl von vorausgehenden Arbeiten mit der effizienten parallelen Ausfu ̈hrung von Netzwerkmodellen befasst hat, besteht ein Mangel an Verfahren, die Entscheidungen bezu ̈glich der Paralle- lisierung von Netzwerkmodellen und die Wahl geeigneter Hardware-Plattformen, Simulatorarchitekturen und Synchronisationsansa ̈tze unterstu ̈tzen. Zusa ̈tzlich hat die breite Verfu ̈gbarkeit kostengu ̈nstiger Manycore-Hardware das Spektrum mo ̈glicher Realisierungen von Simulatoren u ̈ber die Mo ̈glichkeiten traditioneller CPU-basierter Ansa ̈tze hinaus erweitert. Diese Dissertation betrachtet die effiziente Ausfu ̈hrung von Netzwerksimulationen aus zwei Perspektiven: zuna ̈chst werden Evaluationsmethoden vorgeschlagen, die eine Abscha ̈tzung des Parallelisierungspotentials von Netzwerkmodellen erlauben. Im Anschluss werden Ansa ̈tze vorgestellt, die das identifizierte Parallelisierungspotential mittels moderner Manycore-Hardware effizient ausnutzen. Identifizierung von Nebenla ̈ufigkeit: wir stellen einen analytischen Ansatz vor, der die durchschnittliche Anzahl an Recheneinheiten abscha ̈tzt, die von einem ideali- sierten parallelen oder verteilten Simulationslauf eines gegebenen Netzwerkmodells ausgelastet werden ko ̈nnen. Die Abscha ̈tzung erfolgt auf Basis von Modellwissen und einfachen Netzwerkstatistiken, die in sequentiellen Simulationsla ̈ufen gewon- nen werden. Da das vorgestellte Verfahren nicht auf automatisierten Methoden wie der “Critical Path Analysis” beruht, erlauben die Scha ̈tzungen ein Versta ̈ndnis von Zusammenha ̈ngen zwischen den Kommunikationsmustern im simulierten Netzwerk und der resultierenden Nebenla ̈ufigkeit des Netzwerkmodells. Ein Versta ̈ndnis dieser Zusammenha ̈nge kann Modelloptimierungen und die Auswahl geeigneter Simu- latorarchitekturen unterstu ̈tzen. Das Verfahren basiert auf einer na ̈herungsweisen Bestimmung des Simulationsfortschritts unter dem Synchronisationsalgorithmus YAWNS. Wir legen den Zusammenhang zwischen Critical Path Analysis und YAWNS dar und beweisen die Gu ̈ltigkeit unseres Ansatzes sowie existierender Arbeiten, die unsere Annahmen teilen. Eine Evaluation der Akkuratheit konkreter Scha ̈tzungen wird anhand einer Anwendung des Scha ̈tzverfahrens auf Implementierungen dreier Netzwerkmodelle in bekannten Netzwerksimulatoren durchgefu ̈hrt. Um zusa ̈tzlich zu den Eigenschaften des untersuchten Netzwerkmodells auch die zur Durchfu ̈hrung verwendete Hardware und den Synchronisationsansatz zu beru ̈ck- sichtigen, stellen wir ein Werkzeug vor, dass die Laufzeit paralleler und verteilter Simulationen auf Basis sequentieller Simulationen und Hardware-Messungen pra ̈di- ziert. Das Werkzeug fu ̈hrt eine Simulation einer geplanten parallelen oder verteilten Simulation durch (“Simulation zweiter Ordnung”). Wir zeigen, dass im Falle von Netzwerkmodellen mit nicht-trivialen Berechnungen pro simulierter Nachricht eine angemessen akkurate Pra ̈diktion erreicht wird. Nutzung von Nebenla ̈ufigkeit: traditionelle Ansa ̈tze der parallelen und verteil- ten Simulation greifen zur Ausfu ̈hrung des Netzwerkmodells auf einen Verbund von CPUs zuru ̈ck. In einigen existierenden Arbeiten ergaben sich fu ̈r Modelle von Peer-to-Peer-Netzwerken durch Parallelisierung der Simulation nur geringe Lauf- zeitverbesserungen. Wir analysieren und vergleichen zwei Partitionierungsstrategien fu ̈r Modelle von Netzwerken, die auf dem Protokoll Kademlia basieren. Ein Beispiel fu ̈r ein solches Netzwerk ist die BitTorrent DHT, eines der gro ̈ßten o ̈ffentlichen Peer- to-Peer-Netzwerke. Mittels einer Partitionierung der Simulation basierend auf der logischen Topologie des Netzwerkes erreichen wir eine Beschleunigung der Simulati- on um einen Faktor von 6,0 im Vergleich mit einer sequentiellen Ausfu ̈hrung sowie eine nahezu lineare Reduktion des Speicherbedarfs pro Rechenknoten. Da die mittels einer CPU-basierten parallelen und verteilten Ausfu ̈hrung erreichte Beschleunigung einer Simulation die hierzu erforderlichen Hardware-Ressourcen nicht in jedem Falle rechtfertigen kann, untersuchen wir die Ausfu ̈hrung von Netz- werksimulationen auf Grafikprozessoren (Graphics Processing Units, GPUs). Heutige GPUs sind in der Lage, allgemeine Berechnungen auf hunderten oder tausenden paralleler Recheneinheiten durchzufu ̈hren. Eine im Arbeitsplatzrechner eines For- schers vorhandene kostengu ̈nstige GPU kann dazu dienen, die Wartezeit zwischen ̈Anderungen an einem Netzwerkmodell und dem Erhalten von Simulationsergeb- nissen zu verringern. Zua ̈chst vergleichen und evaluieren wir Architekturen zur GPU-Beschleunigung rechenaufwa ̈ndiger Schritte einer CPU-basierten detaillierten Simulation drahtlo- ser Netzwerke. Obwohl eine einzelne simulierte Nachrichtenu ̈bertragung bereits Mo ̈glichkeiten zur parallelen Verarbeitung bietet, zeigen unsere Messungen, dass eine signifikante Beschleunigung der Simulation es erforderlich macht, mehrere Nachrichtenu ̈bertragungen aggregiert zu betrachten. Um die Korrektheit der Simula- tion zu gewa ̈hrleisten, muss hierbei muss die Mo ̈glichkeit von Interaktionen zwischen mehreren Sendevorga ̈ngen beru ̈cksichtigt werden. Unsere Ergebnisse demonstrieren daher, dass bereits im betrachteten Fall einer GPU-Beschleunigung einzelner Schritte einer durch eine CPU verwalteten Simulation Synchronisationsmechanismen aus dem Feld der parallelen und verteilten Simulationen erforderlich sind. Schließlich stellen wir einen rein GPU-basierten Simulationsansatz vor, in welchem neben dem Netzwerkmodell auch die gesamte Simulationslogik auf einer GPU aus- gefu ̈hrt wird. Da auf eine Interaktion zwischen einer CPU des Host-Systems und der GPU weitestgehend verzichtet wird, eignet sich der rein GPU-basierte Ansatz auch im Falle von Netzwerkmodellen, deren Simulationsereignisse jeweils nur ge-ringfu ̈gige Berechnungen erfordern. Im Gegensatz zu existierenden Arbeiten werden in unserem Ansatz die simulierten Knoten zu Gruppen zusammengefasst, welche jeweils gemeinsam betrachtet werden. Diese Aggregation erlaubt es, die Auslastung der Rechneneinheiten der GPU gegenu ̈ber dem Verwaltungsaufwand der Simulation abzuwa ̈gen, indem der Grad an Aggregation basierend auf Messungen der Simulati- onsleistung dynamisch zur Laufzeit angepasst wird. Eine Leistungsbewertung unserer Implementierung des Ansatzes anhand eines Modells Kademlia-basierter Netzwerke und des Benchmark-Modells PHOLD zeigt eine Beschleunigung der Simulationen um einen Faktor von bis zu 19, 5 bzw. 27, 5 im Vergleich mit einer sequentiellen CPU- basierten Ausfu ̈hrung, sowie eine Ereignisrate von bis zu 6, 8 ∗ 106 bzw. 39, 3 ∗ 106 Ereignissen pro Sekunde auf einer einzelnen GPU.