Parallelizing GMP

[bodrato at mail.dm.unipi.it]

Ciao,

Il Sab, 29 Ottobre 2011 10:03 am, Marc Glisse ha scritto:
> On Sat, 29 Oct 2011, Kentaro Yamamoto wrote:
>
>> I am using GMP for computing modular exponentiation by repeated
>> squaring (since the power are always a power of 2 and the modulus has

If the exponent is always a power of 2, then you do only use squarings.

>> repeated squaring part (if you do, please let me know), I am planning
>> to parallelize in the library level by OpenMP.
>
> do you only compute the exponentiation of a single number? When you
> parallelize, the higher the level, the greater the gains, and computing

The higher level you can try to parallelize, in the library, is
mpn/generic/sqrmod_bnm1.c, it "Compute xm = a^2 mod (B^n - 1), xp = a^2
mod (B^n + 1)", and the two computation can go parallel. They are already
enclosed in two {}-blocks. Unfortunately inserting a few pragma is not
enough, I fear, because the two computation probably share some scratch
memory area.
But if you do not care of the increased memory footprint, this can be a
good place to start.

> If you are close to the FFT threshold, you could also try
> parallelizing the toom multiplications.

Yes, it is possible to parallelize Toom. With high degree (toom6h and
toom8h) you can take four by four point (+a,-a,+1/a,-1/a) and evaluate,
multiply (square), and execute some steps of the interpolation. Then most
of the remaining interpolation can be done by two independent threads.
But the same observation expressed above applies here, the current
implementation can not trivially go parallel, one needs to rethink memory
usage.

> See also this discussion (but beware that the code is slightly different):

Marc, you also tested openmp somehow, didn't you?
http://gmplib.org/list-archives/gmp-devel/2009-April/000826.html

Regards,
Marco

-- 
http://bodrato.it/papers/