algo1 & algo2

diff --git a/paper.tex b/paper.tex
index 09421adba1f57a566d8f056677df8504572157ad..a40df2f4bee979a39a320ef4c8144984da1498b5 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -505,13 +505,14 @@ The main steps of Ehrlich-Aberth method are shown in Algorithm.~\ref{alg1-seq} :
 \caption{A sequential algorithm to find roots with the Ehrlich-Aberth method}
 
 \KwIn{$Z^{0}$ (Initial root's vector), $\varepsilon$ (error tolerance
 \caption{A sequential algorithm to find roots with the Ehrlich-Aberth method}
 
 \KwIn{$Z^{0}$ (Initial root's vector), $\varepsilon$ (error tolerance

-  threshold), P (Polynomial to solve), $\Delta z_{max}$ (maximum value
+  threshold), $P$ (Polynomial to solve),$Pu$ (the derivative of P) $\Delta z_{max}$ (maximum value

   of stop condition), k (number of iteration), n (Polynomial's degrees)}
   of stop condition), k (number of iteration), n (Polynomial's degrees)}

-\KwOut {Z (The solution root's vector), ZPrec (the previous solution root's vector)}
+\KwOut {$Z$ (The solution root's vector), $ZPrec$ (the previous solution root's vector)}

 
 \BlankLine
 
 
 \BlankLine
 

-Initialization of the coefficients of the polynomial to solve\;
+Initialization of $P$\;
+Initialization of $Pu$\;

 Initialization of the solution vector $Z^{0}$\;
 $\Delta z_{max}=0$\;
  k=0\;
 Initialization of the solution vector $Z^{0}$\;
 $\Delta z_{max}=0$\;
  k=0\;


@@ -521,7 +522,7 @@ $\Delta z_{max}=0$\;
 \For{$j \gets 0 $ \KwTo $n$}{
 $ZPrec\left[j\right]=Z\left[j\right]$;// save Z at the iteration k.\
 
 \For{$j \gets 0 $ \KwTo $n$}{
 $ZPrec\left[j\right]=Z\left[j\right]$;// save Z at the iteration k.\
 

-$Z\left[j\right]=H\left(j,Z\right)$;//update Z with the iterative function.\
+$Z\left[j\right]=H\left(j, Z, P, Pu\right)$;//update Z with the iterative function.\

 }
 k=k+1\;
 
 }
 k=k+1\;
 


@@ -574,31 +575,33 @@ Algorithm~\ref{alg2-cuda} shows a sketch of the Ehrlich-Aberth algorithm using C
 %\LinesNumbered
 \caption{CUDA Algorithm to find roots with the Ehrlich-Aberth method}
 
 %\LinesNumbered
 \caption{CUDA Algorithm to find roots with the Ehrlich-Aberth method}
 

-\KwIn{$Z^{0}$ (Initial root's vector), $\varepsilon$ (error tolerance threshold), P(Polynomial to solve), $\Delta z_{max}$ (maximum value of stop condition)}
+\KwIn{$Z^{0}$ (Initial root's vector), $\varepsilon$ (error tolerance threshold), P(Polynomial to solve),Pu (the derivative of P), $n$ (Polynomial's degrees),$\Delta z_{max}$ (maximum value of stop condition)}

 
 

-\KwOut {Z (The solution root's vector)}
+\KwOut {$Z$ (The solution root's vector), $ZPrec$ (the previous solution root's vector)}

 
 \BlankLine
 
 
 \BlankLine
 

-Initialization of the coefficients of the polynomial to solve\;
+Initialization of the of P\;
+Initialization of the of Pu\;

 Initialization of the solution vector $Z^{0}$\;
 Initialization of the solution vector $Z^{0}$\;

-Allocate and copy initial data to the GPU global memory\;
+Allocate and copy initial data to the GPU global memory ($d\_Z,d\_ZPrec,d\_P,d\_Pu$)\;

 k=0\;
 k=0\;

-\While {$\Delta z_{max}\succ \epsilon$}{
+\While {$\Delta z_{max} > \epsilon$}{

  Let $\Delta z_{max}=0$\;
  Let $\Delta z_{max}=0$\;

-$ kernel\_save(d\_Z^{k-1})$\;
+$ kernel\_save(d\_ZPrec,d\_Z)$\;

 k=k+1\;
 k=k+1\;

-$ kernel\_update(d\_Z^{k})$\;
-$kernel\_testConverge(\Delta z_{max},d\_Z^{k},d\_Z^{k-1})$\;
+$ kernel\_update(d\_Z,d\_P,d\_Pu)$\;
+$kernel\_testConverge(\Delta z_{max},d\_Z,d\_ZPrec)$\;

 
 }
 
 }

+Copy results from GPU memory to CPU memory\;

 \end{algorithm}
 ~\\ 
 
 \end{algorithm}
 ~\\ 
 

-After the initialisation step, all data of the root finding problem to be solved must be copied from the CPU memory to the GPU global memory, because the GPUs only access data already present in their memories. Next, all the data-parallel arithmetic operations inside the main loop \verb=(do ... while(...))= are executed as kernels by the GPU. The first kernel named \textit{save} in line 6 of Algorithm~\ref{alg2-cuda} consists in saving the vector of polynomial's root found at the previous time-step in GPU memory, in order to check the convergence of the roots after each iteration (line 8, Algorithm~\ref{alg2-cuda}).
+After the initialization step, all data of the root finding problem to be solved must be copied from the CPU memory to the GPU global memory, because the GPUs only access data already present in their memories. Next, all the data-parallel arithmetic operations inside the main loop \verb=(do ... while(...))= are executed as kernels by the GPU. The first kernel named \textit{save} in line 6 of Algorithm~\ref{alg2-cuda} consists in saving the vector of polynomial's root found at the previous time-step in GPU memory, in order to check the convergence of the roots after each iteration (line 8, Algorithm~\ref{alg2-cuda}).

 
 The second kernel executes the iterative function $H$ and updates
 
 The second kernel executes the iterative function $H$ and updates

-$z^{k}$, according to Algorithm~\ref{alg3-update}. We notice that the
+$d\_Z$, according to Algorithm~\ref{alg3-update}. We notice that the

 update kernel is called in two forms, separated with the value of
 \emph{R} which determines the radius beyond which we apply the
 exponential logarithm algorithm. 
 update kernel is called in two forms, separated with the value of
 \emph{R} which determines the radius beyond which we apply the
 exponential logarithm algorithm. 


@@ -608,10 +611,10 @@ exponential logarithm algorithm.
 %\LinesNumbered
 \caption{Kernel update}
 
 %\LinesNumbered
 \caption{Kernel update}
 

-\eIf{$(\left|Z^{(k)}\right|<= R)$}{
-$kernel\_update(d\_z^{k})$\;}
+\eIf{$(\left|d\_Z\right|<= R)$}{
+$kernel\_update((d\_Z,d\_Pcoef,d\_Pdegres,d\_Pucoef,d\_Pudegres)$\;}

 {
 {

-$kernel\_update\_ExpoLog(d\_z^{k})$\;
+$kernel\_update\_ExpoLog((d\_Z,d\_Pcoef,d\_Pdegres,d\_Pucoef,d\_Pudegres))$\;

 }
 \end{algorithm}
 
 }
 \end{algorithm}