Return to efficient.tex CVS log

Up to [local] / OpenXM / doc / calc2000p

Annotation of OpenXM/doc/calc2000p/efficient.tex, Revision 1.2

1.2     ! noro        1: % $OpenXM: OpenXM/doc/calc2000p/efficient.tex,v 1.1 2000/07/21 08:27:11 noro Exp $
1.1       noro        2: \documentclass{slides}
                      3: \usepackage{color}
1.2     ! noro        4: \usepackage{rgb}
1.1       noro        5: \usepackage{graphicx}
                      6: \usepackage{epsfig}
                      7: \begin{document}
                      8: \parskip 3pt
                      9: \fbox{{\huge \color{blue} We Are Efficient}}
                     10:
1.2     ! noro       11: {\color {red} Real speedup by parallelism}
1.1       noro       12:
1.2     ! noro       13: Each process can communicate with any other process on {\color{green} MPI}
1.1       noro       14:
1.2     ! noro       15: $\Rightarrow$ {\color{green} Collective operations} similar to \\
        !            16: {\color{SeaGreen} MPI\_Bcast} and {\color{SeaGreen} MPI\_Reduce}
1.1       noro       17:
1.2     ! noro       18: \vskip 8pt
1.1       noro       19:
                     20: {\color{red} An example} :
1.2     ! noro       21: the product of dense univariate polynomials with 3000bit coefficients
1.1       noro       22:
1.2     ! noro       23: \vskip 8pt
        !            24: {\color{green} Algorithm}(Shoup) : FFT+Chinese Remainder
        !            25: \vskip 5pt
        !            26: {\color{green} Parallel computing time} : $O((n\log n)/L+n{\color{red}\log L})$\\
        !            27: No collective operations : $O((n\log n)/L+n{\color{red}L})$\\
        !            28: ($L$: number of processes, $n$: degree)
1.1       noro       29:
1.2     ! noro       30: \vskip 8pt
1.1       noro       31:
                     32: \epsfxsize=17cm
                     33: \epsffile{3k.ps}
1.2     ! noro       34: \rightline{ {\color{red} {\tt http://www.openxm.org} }}
1.1       noro       35: \end{document}