Any interest in multi-threaded code?

[Torbjörn Granlund]

"Richard Foster" <r-foster at gmx.com> writes:

  I have an idea for a multi-threaded version of the GMP FFT multiply
  code. I've had a browse through the archives and found a few
  references, but nothing to indicate that there's anything
  available. There was even a hint that it could be in an upcoming
  version, but I can't find any code.

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.

-- 
Torbjörn
Please encrypt, key id 0xC8601622