Parallel reversal schedules using more checkpoints than processors

Abstract

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.Parallel reversal schedules describe how to calculate the states of an evolutionary system, such as atmospheric and oceanographic simulations, in reverse order without having to keep all states in memory. This is possible without any increase in computation time, by recalculating intermediate results using multiple processors on a parallel computer system. These schedules are not only applied physical simulations that need to run in reverse, but also in algorithmic differentiation, which in turn is used, among others, in nonlinear optimization and to solve partial differential equations. Earlier research led to optimal schedules under the central assumption that if k states can be kept in memory, there are enough processors to run computations on roughly half of them in parallel, while the other half can only be used for holding checkpoints. This diploma thesis is an attempt to continue the research by relaxing the central assumption, such that memory for a large number of plain checkpoints can be used with a comparatively small number of processors. To cope with this challenge, a symbolic approach to reversal schedules is proposed, and a comprehensive algebra is developed to analyze schedules via their profiles. This algebra is very generic and could have applications outside parallel reversal schedules. Using that instrument, new optimal schedules are developed, to be applied in situations where the earlier schedules are not applicable. Moreover, suboptimal schedules are provided where optimal schedules could not be found in a systematic way.