I have recently come across the following papers:

  • S. Baktir and E. Savas. Highly-parallel Montgomery multiplication for multi-core general-purpose microprocessors. In E. Gelenbe and R. Lent, editors, Computer and Information Sciences III, pages 467–476. Springer London, 2013.
  • P. Giorgi, L. Imbert, and T. Izard. Parallel modular multiplication on multi-core processors. In Computer Arithmetic (ARITH), 2013 21st IEEE Symposium on, pages 135–142, April 2013.
  • B. S. Fagin, "Large integer multiplication on massively parallel processors," [1990 Proceedings] The Third Symposium on the Frontiers of Massively Parallel Computation, College Park, MD, 1990, pp. 38-42.

where they deal with the issue of computing a multiplication between large numbers (in the first two papers, up to approx $2^{14}$ bits, in the last one up to $2^{23}$ bits) using many processors simultaneously.

I was wondering: what happens beyond that? What is the theoretical maximum speedup for a $2^n$ bit multiplication, having an unlimited amount of processors at disposal? Can the wallclock time of the operation be made arbitrarily small? I guess there are communication bottlenecks among the processors?

  • 1
    $\begingroup$ Please specify your model of computation. Because at some point physical limits and circuit limits (e.g. ignoring spacetime we live in a 3 dimensional world) and the speed of light limits come into play, if you want to be realistic. $\endgroup$ – orlp May 31 '17 at 23:31
  • $\begingroup$ cs.stackexchange.com/a/7024/755, en.wikipedia.org/wiki/NC_%28complexity%29, $\endgroup$ – D.W. Jun 1 '17 at 0:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.