Eintrag in der Universitätsbibliographie der TU Chemnitz
Programmtransformationen für Vielteilchensimulationen auf Multicore-Rechnern
Program Transformations for Many-Body Simulations on Multi-Core Systems
Kurzfassung in deutsch
In dieser Dissertation werden Programmtransformationen für die Klasse der regulär-irregulären Schleifenkomplexe, welche typischerweise in komplexen Simulationscodes für Vielteilchensysteme auftreten, betrachtet. Dabei wird die Effizienz der resultierenden Programme auf modernen Multicore-Systemen untersucht. Reguläre Schleifenkomplexe zeichnen sich durch feste Schleifengrenzen und eine regelmäßige Struktur der Abhängigkeiten der Berechnungen aus, bei irregulären Berechnungen sind Abhängigkeiten zwischen Berechnungen erst zur Laufzeit bekannt und stark von den Eingabedaten abhängig. Die hier betrachteten regulären-irregulären Berechnungen koppeln beide Arten von Berechnungen eng. Die Herausforderung der effizienten Realisierung regulär-irregulärer Schleifenkomplexe auf modernen Multicore-Systemen liegt in der Kombination von Transformationstechnicken, die sowohl ein hohes Maß an Parallelität erlauben als auch die Lokalität der Berechnungen berücksichtigen.Moderne Multicore-Systeme bestehen aus einer komplexen Speicherhierachie aus privaten und gemeinsam genutzten Caches, sowie einer gemeinsamen Speicheranbindung. Diese neuen architektonischen Merkmale machen es notwendig Programmtransformationen erneut zu betrachten und die Effizienz der Berechnungen neu zu bewerten. Es werden eine Reihe von Transformationen betrachtet, die sowohl die Reihenfolge der Berechnungen als auch die Reihenfolge der Abspeicherung der Daten im Speicher ändern, um eine erhöhte räumliche und zeitliche Lokalität zu erreichen.
Parallelisierung und Lokalität sind eng verknüpft und beeinflussen gemeinsam die Effizienz von parallelen Programmen. Es werden in dieser Arbeit verschiedene Parallelisierungsstrategien für regulär-irreguläre Berechnungen für moderne Multicore-Systeme betrachtet.
Einen weiteren Teil der Arbeit bildet die Betrachtung rein irregulärer Berechnungen, wie sie typisch für eine große Anzahl von Vielteilchensimualtionscodes sind. Auch diese Simulationscodes wurden für Multicore-Systeme betrachtet und daraufhin untersucht, inwieweit diese auf modernen Multicore-CPUs skalieren. Die neuartige Architektur von Multicore-System, im besonderen die in hohem Maße geteilte Speicherbandbreite, macht auch hier eine neue Betrachtung solcher rein irregulärer Berechnungen notwendig. Es werden Techniken betrachtet, die die Anzahl der zu ladenden Daten reduzieren und somit die Anforderungen an die gemeinsame Speicherbandbreite reduzieren.
Kurzfassung in englisch
This thesis considers program transformations for the class of regular-irregular loop complexes which typically arise in complex simulation codes for many-body systems and the efficiency of the resulting programs on modern multi-core systems are examined. Regular loop complexes are characterized by fixed loop bounds and a regular structure of the dependencies of the calculations. Irregular computations have dependencies between calculations which can be only determined at runtime and depend heavily on the input data. The considered regular-irregular computations couple both types of calculations closely in a loop complex. The challenge for an efficient implementation of regular-irregular loop complexes on modern multi-core systems is to combine transformations to have a high degree of parallelism and locality. Modern multi-core systems have a complex memory hierarchy of private and shared caches, and they share a common memory interface. This new architectural characteristics make it necessary to re-examine transformations and to re-evaluate the efficiency of the calculations. Series of transformations are considered that change both, the order of the calculations and the order of the storage of the data in memory to increase spatial and temporal locality. Parallelism and locality are closely related and influence together the efficiency of parallel programs. In this thesis it is shown how different parallelization strategies for regular-irregular calculations for modern multi-core systems influence the performance. Another part of this work are purely irregular computations, which are typical for a large number of many-body simulation codes. It was examined how those irregular computations scale on modern multi-core architectures. The novel architecture of multi-core systems, particularly the highly shared memory bandwidth, makes a new consideration of such purely irregular computations necessary. This thesis considers techniques which try to reduce the number of data accesses and thus reduce the requirements for the shared memory bandwidth.
| Universität: | Technische Universität Chemnitz | |
| Institut: | Professur Praktische Informatik | |
| Fakultät: | Fakultät für Informatik | |
| Dokumentart: | Dissertation | |
| Betreuer: | Rünger, Gudula (Prof. Dr.) | |
| URL/URN: | http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-63402 | |
| Quelle: | 2010. - 99 S. | |
| Freie Schlagwörter (Deutsch): | Vielteilchen Simulation , Multicore-Systeme , regulär Berechnung , irreguläre Berechnungen , Programmtransformationen , Parallele Programmierung , MD-Simulation , Molekulardynamik , Programmtransformation , Mehrkernprozessor | |
| Freie Schlagwörter (Englisch): | Parallel processing | |
| Tag der mündlichen Prüfung | 01.12.2010 |
