Hi
It is probably not useful to work much on the current FFT code. We
have
long planned--and worked quite a bit on--replacement FFT code with much
better memory access pattern.
The replacement code works with multiple small coefficient fields
instead of a large ring. It also implements Bailey's multidimensional
FFT trick for memory locality improvements.
I have forgotten the exact state of the code, but I am sure Nisse can
fill me in.
Any parallel work should go in that code, but only after it is
well-tuned for a single thread, I think.
Making GMP scale well for multiple thread is highly non-trivial. Only
superlinear algorithm should even be attempted. And then, one will
want to make it as course grain as possible, perhaps even with some
cache topology understanding built in to the code.
Generating data in thread A which is then processed in thread B will
typically mean that data needs to be transferred from one cache to
another. That is super expensive, and will offset any benefit untless
the comutation before or after the data transfer is huge.
The basic idea I've been looking at is not to run the FFT itself in
parallel, but to parallelise the inner loop. The algorithm recurses
until the operand sizes are below a suitable size, then loops K times;
each iteration multiplies 2 numbers of n limbs.
Naively, if you have m CPUs, then you should get a speedup if each CPU
multiplies 2 numbers of n/m limbs. There will be a total of mK
multiplications, but since each is smaller, it should go faster.
As Torbjörn says, cache usage is key: but within some uncertainty, the
cache requirement should be roughly the same. 2m operands of n/m limbs
should need roughly the same total space as 2 operands of n limbs, and
the code should take up roughly the same space; at this point in the
algorithm all the operands are the same size, so the GMP code will pick
the same method for all the iterations (schoolbook, Toom, etc), so there
will only be 1 copy of the code in cache - assuming it's re-entrant, as
all modern code should be. There is an overhead of a stack per thread,
which must be checked out.
The other assumption is that the forward FFT leaves the operands in a
suitable state, ie, each operand is in contiguous memory. This is an
advantage anyway, even if you're not running in parallel, so I think
it's a reasonable assumption. Also, since each of the smaller operands
is a piece of the original, cache locality for the smaller
multiplications is no worse than before.
Finally, the multiplications must leave their results in a suitable
state for the inverse FFT. Again, I think this is a reasonable
assumption, as the non-parallel version of the loop does the same thing
as the parallel version, just with larger operands.
Does the reasoning appear OK, or am I totally on the wrong track?
Even it looks OK in today's code, does Nisse's new FFT code change
anything?
Regards
Richard Foster
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
