Meister, Gerd (2000)
Untersuchung des Parallelisierungspotentials diskreter ereignisgesteuerter Simulationen am Beispiel der Schaltkreissimulation.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

Das Ziel der vorliegenden Arbeit ist, die kritischen Einflussfaktoren für das Beschleunigungspotential der parallelen diskreten ereignisgesteuerten Simulation(PDES) zu isolieren, deren Auswirkungen auf die bekannten Simulationsverfahren zu ermitteln, Engpässe und Defizite zu erkennen und zu überprüfen, ob diese eliminiert oder reduziert werden können. Da insbesondere auch die Relevanz der Ergebnisse für praktische Anwendungen und die Skalierbarkeit für große Modelle von Interesse ist, wurde als Szenarium eine Evaluierungsumgebung für die Simulation digitaler Schaltkreise entwickelt. Das prototypische Testbett DVSIM (Distributed VHDL Simulator) gestattet die Realisierung unterschiedlicher paralleler Simulationsverfahren. Zunächst werden die bekannten Basisprotokolle zur Synchronisation der Simulatoren (konservatives Verfahren nach Chandy/Misra/Bryant und der sogenannte Time Warp von Jefferson als optimistische Methode) implementiert, sowie deren Leistungsfähigkeit bewertet. Im Rahmen dieser Untersuchungen stellte sich heraus, dass die klassischen Basisalgorithmen keine guten Ergebnisse liefern. Um realistische Aussagen bezüglich des Beschleunigungspotentials treffen zukönnen, wurde in der vorliegenden Arbeit ein faires Bewertungsverfahren eingeführt, das die Laufzeiten der parallelen Verfahren mit denen eines rein sequentiellen Simulators vergleicht. Es zeigte sich, dass die Partitionierung des Modells in Zusammenspiel mit den Synchronisationsverfahren eine größere Rolle spielt als allgemein erwartet. Wesentliche Beschleunigungen wurden erst bei großen Schaltkreisen registriert, für die sich der Parallelisierungsoverhead amortisiert. Ähnliches gilt auch für die Rechenzeit der Ereignisbearbeitungsroutinen. Wird diese künstlich variiert, so zeigen sich für reale und synthetische Benchmarks bei höherer Granularität beachtliche Beschleunigungen. Da die Güte der Ergebnisse bei mehreren implementierten statischen Partitionierungsverfahren stark streute und die Partitionierungskosten bei großen Modellen i.a. nicht mehr tragbar erscheinen, wurden dynamische Lastverteilungsverfahrenuntersucht und hierfür das Simulationssystem DVSIM um eine entsprechende Komponente erweitert. Dazu werden Objekte während der Simulation von stark zu wenig belasteten Simulatoren verschoben. Die Untersuchungen mit den so modifizierten Prototypen ergeben bei Verwendung des optimistischen Synchronisationsprinzips allerdings keine Verbesserungen. Der Aufwand für die dynamische Lastbalancierung führtein vielen Fällen sogar zu Leistungseinbrüchen. Abschließend betrachtet lässt sich feststellen, dass die Parallelisierung der ereignisgesteuerten Simulation offenbar nicht die allgemein erwarteten Ergebnisse liefern kann. Es sind in der Praxis höchstens moderate Beschleunigungsfaktoren im Bereich zwischen 25 und 50 Prozent der optimalen (linearen) Beschleunigung möglich. Zudem kostet es viel Wissen im Bereich paralleler Programmiertechniken sowie einen hohenzeitlichen Aufwand, um effiziente Simulatoren zu realisieren. Allerdings hat sich auch gezeigt, dass ab einer gewissen Modellgröße und Ereignisgranularität Beschleunigungen nicht nur auf eng gekoppelten Parallelrechnern sondern auch auf Netzwerken aus Standardarbeitsplatzrechnernerreichbar sind. Dadurch bietet sich einem Anwender mit erzielbaren Beschleunigungsfaktoren von 2 - 5 (für sonst oft Tage oder gar Wochen benötigende Langläufer) bereits eine interessante Optimierungsperspektive.

Frage zum Eintrag

Redaktionelle Details anzeigen