multi-threaded multiplication speed-up

Jason Martin jason.worth.martin at
Fri Jan 12 00:01:54 CET 2007

Hi All,

Out of curiosity, I recently tried a naive multi-threaded
multiplication scheme (using pthreads) and got a speed-up of about 25%
for extremely large operands (over 2000 limbs).  I was just using
simple "textbook" style multiplication (break the larger operand in
half, do two multiplies using mpn_mul, then shift/add back together).
I got similar results on a Woodcrest running OS X and a dual core
Opteron running Linux.

I suspect that a quad-core CPU in which all the cores share the L2
cache could really benifit from a Karatsuba-style multi-threaded
multiply since the three multiplies could run in parallel without
having to go off-chip for memory accesses.

Is anyone working on this already?  Does anyone care?


Jason Worth Martin
Asst. Prof. of Mathematics
James Madison University
phone: (+1) 540-568-5101
fax: (+1) 540-568-6857

"Ever my heart rises as we draw near the mountains.
There is good rock here." -- Gimli, son of Gloin

More information about the gmp-discuss mailing list