Return to search

Program Reversal Schedules for Single- and Multi-processor Machines / Schemata zur Programmumkehr für Ein- und Mehrprozessormaschinen

Bei der Berechnung von Adjungierten, zum Debuggen und für ähnliche Anwendungen kann man die Umkehr der entsprechenden Programmauswertung verwenden. Der einfachste Ansatz, nämlich das Mitschreiben einer kompletten Mitschrift der Vorwärtsrechnung, welche anschließend rückwärts gelesen wird, verursacht einen enormen Speicherplatzbedarf. Als Alternative dazu kann man die Mitschrift auch stückweise erzeugen, indem die Programmauswertung von passend gewählten Checkpoints wiederholt gestartet wird. Das Ziel der Arbeit ist die Minimierung des von der Programmumkehr verursachten Zeit- und Speicherplatzbedarfs. Dieser wird gemessen in Auswertungswiederholungen bzw. verwendeten Checkpoints. Optimale Umkehrschemata werden für Ein- und Mehr-Schritt-Verfahren entwickelt, welche zum Beispiel bei der Diskretisierung einer gewöhnlichen Differentialgleichung Verwendung finden. Desweiteren erfolgte die Entwicklung von parallelen Umkehrschemata, d. h. mehrere Prozessoren werden für die Umkehrung der Programmauswertung eingesetzt. Diese zusätzlichen Prozessoren dienen dazu, die wiederholten Berechnungen des Programms zu parallelisieren, so daß ein Prozessor die Rückwartsrechnung ohne Unterbrechung durchführen kann. Sowohl für die seriellen als auch für die parallelen Umkehrschemata wurde gezeigt, daß die Länge der umzukehrenden Programmauswertung exponentiell in Abhängigkeit von der Zahl der verwendeten Checkpoints und der Zahl der wiederholten Auswertungen bzw. verwendeten Prozessoren wächst. / For adjoint calculations, parameter estimation, and similar purposes one may need to reverse the execution of a computer program. The simplest option is to record a complete execution log and then to read it backwards. This requires massive amounts of storage. Instead one may generate the execution log piecewise by restarting the ``forward'' calculation repeatedly from suitably placed checkpoints. The basic structure of the resulting reversal schedules is illustrated. Various strategies are analysed with respect to the resulting temporal and spatial complexity on serial and parallel machines. For serial machines known optimal compromises between operations count and memory requirement are explained, and they are extended to more general situations. For program execution reversal on multi-processors the new challenges and demands on an optimal reversal schedule are described. We present parallel reversal schedules that are provably optimal with regards to the number of concurrent processes and the total amount of memory required.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa.de:swb:14-1011612099250-05302
Date19 January 2002
CreatorsWalther, Andrea
ContributorsTechnische Universität Dresden, Mathematik und Naturwissenschaften, Mathematik, Institut für Wissenschaftliches Rechnen, Prof. Ph. D. Andreas Griewank, Prof. Ph.D. Andreas Griewank, Ph. D. Alan Carle, Prof. Ph.D. Richard Brent
PublisherSaechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageGerman
Typedoc-type:doctoralThesis
Formatapplication/pdf

Page generated in 0.0024 seconds