Parallel reversal schedules using more checkpoints than processors

Parallele Umkehr-Ablaufpläne (Parallel reversal schedules) beschreiben, wie die Zustände eines evolutionären Systems, etwa einer atmosphärischen oder ozeanographischen Simulation, in umgekehrter Reihenfolge berechnet werden können, ohne dass alle Zustände im Speicher gehalten werden müssen. Auf einem Mehrprozessorsystem ist das ohne Anstieg der benötigten Rechenzeit möglich, indem Zwischenergebnisse zwar mehrfach berechnet werden, aber gleichzeitig auf mehreren Prozessoren. Diese Ablaufpläne werden nicht nur verwendet, um Simulationen rückwärts abzuspielen, sondern auch in der algorithmischen Differenzierung, die wiederum in der nichtlinearen Optimierung sowie beim Lösen von partiellen Differentialgleichungen eingesetzt wird. Die bisherige Forschung ermittelte optimale Pläne für den Fall, dass folgende zentrale Annahme erfüllt ist: Können k Zustände gleichzeitig im Speicher gehalten werden, so sind stets etwa k/2 Prozessoren verfügbar, die die Berechnung von k/2 Zuständen fortsetzen. Die übrigen k/2 Zustände werden in reinen Speicherpunkten (Checkpoints) vorgehalten. In dieser Diplomarbeit wird die zentrale Annahme gelockert und so die Forschung fortgesetzt. Es ist nun möglich, dass deutlich weniger als k/2 Prozessoren verfügbar sind, oder gleichbedeutend, dass viel mehr Speicherpunkte genutzt werden können. Für diese neue Aufgabenstellung wird eine symbolische Herangehensweise an parallele Umkehr-Ablaufpläne vorgestellt. Es wird eine umfassende Algebra entwickelt, die einen direkten Zugang zu den Profilen der Pläne bietet und so deren Analyse erleichtert. Diese Algebra ist sehr generisch und könnte weitere Anwendungen haben. Es werden neue Pläne entwickelt, die in Situationen anwendbar sind, in denen die bisher bekannten Pläne ungeeignet waren. In einigen Fällen sind sie optimal, für alle übrigen Fälle werden suboptimale Pläne vorgestellt, die ebenfalls eine deutliche Verbesserung zu den bisherigen Plänen darstellen.

Grantor dc:publisher

Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät

Year dc:date.issued

2015

Author dc:creator

• Diels-Grabsch, Volker

• Mathematik
• Simulation
• Diplomarbeit
• automatisches Differenzieren
• algorithmisches Differenzieren
• Scheduling
• Rückwärts-Ablaufpläne
• Diskrete Optimierung
• Parallelrechner
• mathematics
• automatic differentiation
• diploma thesis
• algorithmic differentiation
• reversal schedules
• discrete optimization
• parallel computing

Statement dc:rights

• Namensnennung - Weitergabe unter gleichen Bedingungen

Licence dc:rights.uri

• http://creativecommons.org/licenses/by-sa/3.0/de/

Language dc:language.iso

eng

DOI

https://doi.org/10.18452/14266

OAI record oai:identifier

https://edoc.hu-berlin.de/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aedoc.hu-berlin.de%3A18452%2F14918