Show simple item record

2015-09-24Diplomarbeit DOI: 10.18452/14266
Parallel reversal schedules using more checkpoints than processors
dc.contributor.authorDiels-Grabsch, Volker
dc.date.accessioned2017-06-18T02:53:54Z
dc.date.available2017-06-18T02:53:54Z
dc.date.created2016-02-15
dc.date.issued2015-09-24
dc.identifier.urihttp://edoc.hu-berlin.de/18452/14918
dc.description.abstractParallele 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.ger
dc.description.abstractParallel 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.eng
dc.language.isoeng
dc.publisherHumboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät
dc.rightsNamensnennung - Weitergabe unter gleichen Bedingungen
dc.rights.urihttp://creativecommons.org/licenses/by-sa/3.0/de/
dc.subjectMathematikger
dc.subjectSimulationger
dc.subjectDiplomarbeitger
dc.subjectautomatisches Differenzierenger
dc.subjectalgorithmisches Differenzierenger
dc.subjectSchedulingger
dc.subjectRückwärts-Ablaufpläneger
dc.subjectDiskrete Optimierungger
dc.subjectParallelrechnerger
dc.subjectmathematicseng
dc.subjectsimulationeng
dc.subjectautomatic differentiationeng
dc.subjectschedulingeng
dc.subjectdiploma thesiseng
dc.subjectalgorithmic differentiationeng
dc.subjectreversal scheduleseng
dc.subjectdiscrete optimizationeng
dc.subjectparallel computingeng
dc.subject.ddc510 Mathematik
dc.titleParallel reversal schedules using more checkpoints than processors
dc.typemasterThesis
dc.identifier.urnurn:nbn:de:kobv:11-100236764
dc.identifier.doihttp://dx.doi.org/10.18452/14266
dc.identifier.alephidBV043366214
dc.contributor.refereeGriewank, Andreas
dc.contributor.refereeWalther, Andrea
local.edoc.pages83
local.edoc.type-nameDiplomarbeit
local.edoc.institutionMathematisch-Naturwissenschaftliche Fakultät

Show simple item record