Real speedup by parallelism

Each process can communicate with any other process on MPI

$\Rightarrow$ Collective operations similar to
MPI_Bcast and MPI_Reduce

An example : the product of dense univariate polynomials with 3000bit coefficients

Algorithm(Shoup) : FFT+Chinese Remainder Communication cost :
     $O(n{\color{red}\log L})$ with collective operations
     $O(n{\color{red}L})$ without collective operations
    ($L$: number of processes, $n$: degree)

=17cm

http://www.openxm.org