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.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa.de:bsz:ch1-qucosa-63402 |
| Date | 15 December 2010 |
| Creators | Schwind, Michael |
| Contributors | Technische Universität Chemnitz, Fakultät für Informatik, Prof. Dr. Gudula Rünger, Prof. Dr. Petr Kroha, Prof. Dr. Gudula Rünger |
| Publisher | Universitätsbibliothek Chemnitz |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | deu |
| Detected Language | German |
| Type | doc-type:doctoralThesis |
| Format | application/pdf, text/plain, application/zip |
Page generated in 0.0064 seconds