[LLVMdev] LLVM for numerical computations
Luc Bourhis
luc_j_bourhis at mac.com
Sun Oct 29 15:46:02 PST 2006
Hello there,
I am considering to use LLVM as part of a numerical software. I have
never used LLVM, but I have tried to thoroughly read the material
available on llvm.org. I would appreciate some early pointers. Please
bare with me as I explained the matter as concisely as possible! And
you can already see this is not going to be that concise…
The part of our project LLVM could be relevant to has to do with
automatic numerical differentiation. Basically we have a
computational tree whose leaves are independent variables whereas any
other node is a dependent variable, i.e. its value depends on the
value of its children through some function. Finally the head of the
tree is the final result we are interested in. One of the requirement
is that the set of those functions is open-ended. The tree can have
from 50 to a few thousands nodes and it is typically evaluated
several 1000 times for different values of the leaves (i.e. a
forward sweep to compute the values followed by a reverse sweep to
compute the derivatives, c.f. [*]).
Here is where I was thinking to use LLVM. Instead of actually
computing its value and derivatives, each node could feature two
member functions value_by_LLVM and derivatives_by_LLVM which would
produce the LLVM code necessary to respectively compute the value and
the derivatives, each packaged as a function I guess. A visitor
marching through the computational tree would then assemble the calls
to those LLVM functions to compute the head (forward sweep), then
another visitor would assemble the function calls to compute the
derivatives (reverse sweep) -- it should be noted that the values
computed during the forward sweep may be needed during the reverse
sweep but it is not always the case. The LLVM JIT would then
optimise the code and compile it to native code and execute it.
As I wrote, the function is evaluated 1000 times, and it seems to me
that the overhead of assembling the LLVM code, optimising and
compiling it during the first execution would not be significant
overhaul. It also seems to me that LLVM would generate very efficient
code.
Am I correct? Does it make sense to use LLVM for such a purpose?
How would the functions defined in <cmath> be called from the LLVM code?
How would I best specify in LLVM where to find the values of the
independent variables? That is to say the inputs for the whole
computation LLVM will perform…
You may actually wonder why I do not kit each node with two member
functions compute_value and compute_derivatives by the by. Virtual
calls would be involved for each of them on each node every time and
it turns out that those functions are typically not very complex,
which makes the cost of a virtual call significant. I should also
mention that our golden standard is some old fashion but extremely
fast FORTRAN program (which has only a fixed hard-wired set of types
of node but our potential users are not quite ready to sacrifice
speed for flexibility, the eternal story in numerical computation…).
[*] This is not quite exact: in fact we use the so-called reverse
mode and therefore we actually propagate the derivatives from head to
leaves but this does not matter at the level of this discussion.
More information about the llvm-dev
mailing list