Item Type: |
Ph.D. Thesis |
Type of entry: |
Primary publication |
Title: |
Untersuchung des Parallelisierungspotentials diskreter ereignisgesteuerter Simulationen am Beispiel der Schaltkreissimulation |
Language: |
German |
Referees: |
Mattern, Prof. Dr. Friedemann ; Kammerer, Prof. Dr. Peter |
Advisors: |
Mattern, Prof. Dr. Friedemann |
Date: |
17 January 2000 |
Place of Publication: |
Darmstadt |
Date of oral examination: |
14 October 1999 |
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. |
Alternative Abstract: |
Alternative Abstract | Language |
---|
The goals of this thesis are to isolate the critical factors that influence the potential for acceleration of parallel discrete-event simulation, to find their influence on existing simulation algorithms, to detect bottlenecks and deficiencies, and to examinate whether these may be eliminated or reduced. The testbed DVSIM (Distributed VHDL Simulator) has been designed to integrate different parallel simulation algorithms and to examine their scalability in the context of digital circuit simulation. In a frist step, the known basic algorithms according to Chandy/Misra/Bryant (conservative) and Jefferson's Time Warp (optimistic) were realised. We found that their performance stay below the expectations and it is hard to obtain even moderate speed-ups. The analysis is based on a fair measurement to judge the potential for accelleration. The runtimes of the parallel versions are compared to those of an optimised and purely sequential simulator that runs on only one computer. The quality of the results strongly depends on the partitioning. Additionally, the calulation of the partions is very costly for large models. These costs have to be added to the total effort needed for parallel simulation. To avoid them, a module for dynamic load balancing at runtime was incorporated into DVSIM. The gates are redistributed during simulation from heavily loaded processors to less loaded ones. The analysis of this module for the optimistic algorithms yielded no improvements. In many cases, the performance was even reduced. The conclusion of this thesis is that parallel discrete-event simulation may in general not deliver the expected accelleration. With a lot of overhead for implementation and optimisation between 25 and 50 percents of the linear speed-up are obtained. Additionally, deep insight into parallel programming techniques are neccessary to realise efficient parallel simulators. However, an important result is also that for increasing model sizes and growing granularity (time to calculate the changes cause by an event) large speed-ups are possible on parallel computers and even on clusters of workstations. For a user this might provide interesting perspectives in a LAN environment with a reduction of calculation times by factors 2 to 5 for long running batch jobs. | English |
|
Uncontrolled Keywords: |
Parallele diskrete ereignisgesteuerte Simulation, Parallele Schaltkreissimulation, Leistungsbewertung, Lastbalancierung, Partitionierung, Time Warp, Beschleunigung, Granularität, VLSI, Paralleles Rechnen |
Alternative keywords: |
Alternative keywords | Language |
---|
Parallele diskrete ereignisgesteuerte Simulation, Parallele Schaltkreissimulation, Leistungsbewertung, Lastbalancierung, Partitionierung, Time Warp, Beschleunigung, Granularität, VLSI, Paralleles Rechnen | German | Parallel discrete event simulation, parallel logic simulation, performance evaluation, load balancing, partitioning, Time Warp, speed-up, granularity, VLSI, parallel computing | English |
|
URN: |
urn:nbn:de:tuda-tuprints-226 |
Classification DDC: |
000 Generalities, computers, information > 004 Computer science |
Divisions: |
20 Department of Computer Science |
Date Deposited: |
17 Oct 2008 09:20 |
Last Modified: |
09 Dec 2012 09:34 |
URI: |
https://tuprints.ulb.tu-darmstadt.de/id/eprint/22 |
PPN: |
|
Export: |
|