
doi: 10.26204/kluedo/8434
Algorithmic differentiation (AD) is a set of techniques to "differentiate computer programs": Given a primal program that evaluates some mathematical function, AD allows to evaluate the derivative function. Unlike numerical difference quotients, algorithmic derivatives are accurate up to machine precision and, in the "reverse mode", can be formed with respect to a large number of input variables in one stroke. When combined with gradient-based optimization algorithms, AD is therefore a powerful tool to optimize engineering designs or learn weights of neural networks, besides many other applications. Up to date, most implementations of AD access the primal program via its source code, which they require to be available and written in a limited set of programming languages, typically not supporting the full language standards without manual user intervention. In this dissertation, we present the novel AD tool Derivgrind that interacts with the machine code of the compiled primal program. Implemented in the Valgrind framework for dynamic binary instrumentation, Derivgrind augments portions of machine code with AD logic just in time before they potentially execute on the processor. Specifically, Derivgrind's forward-mode AD logic keeps track of a floating-point "dot value" for every floating-point number appearing during the execution of the primal program. These dot values store the derivatives with respect to a single input variable, and are computed alongside, using elementary differentiation rules. Derivgrind also implements reverse-mode AD, by inserting AD logic that tags all floating-point numbers with identifiers, and uses them to record the real-arithmetic evaluation graph on a datastructure called the "tape". Besides our extensive suite of regression tests and a simple numerical solver for Burgers' partial differential equation, we have tested Derivgrind on three larger software projects: the Python interpreter CPython, the spreadsheet software LibreOffice Calc, and the medical imaging application GATE based on the Monte-Carlo particle physics simulator Geant4. We are not aware of any successful previous attemps to compute algorithmic derivatives of these programs. With Derivgrind, only a few lines of code needed to be changed to accomplish that. As a price for its versatility, Derivgrind slows down the primal program by a larger factor than many source-code-based tools. In addition, the issue of "bit-tricks" is more pronounced on the machine code level: If the primal program performs real-arithmetic operations in too obscure ways, Derivgrind cannot recognize their arithmetic meaning and may compute wrong derivatives. We have included a detailed discussion of various bit-trick mechanisms; in practical terms, nearly all of them are academic or originate from highly optimized math libraries. As long as differentiating those are avoided, Derivgrind is applicable to an unprecedentedly wide range of cross-language or partially closed-source software with little manual efforts.
ddc:004, 000, 004 Informatik, 004
ddc:004, 000, 004 Informatik, 004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
