suite

[book_gpu.git] / BookGPU / Chapters / chapter11 / ch11.tex

diff --git a/BookGPU/Chapters/chapter11/ch11.tex b/BookGPU/Chapters/chapter11/ch11.tex
index 1bf638ef6f0633bfabe920143b52b57256bc35ad..270fcc4174d123ff4c5b2ef203085fac0187d68d 100644 (file)
--- a/BookGPU/Chapters/chapter11/ch11.tex
+++ b/BookGPU/Chapters/chapter11/ch11.tex
@@ -28,14 +28,14 @@ The rest of the chapter is organised as follows. Section \ref{ch11:splines} disc
 \begin{figure}[h]
 \centering
 \includegraphics[angle=0,width=8cm]{Chapters/chapter11/gregory1_plot1.pdf}
 \begin{figure}[h]
 \centering
 \includegraphics[angle=0,width=8cm]{Chapters/chapter11/gregory1_plot1.pdf}

-\caption{Cubic spline (solid) and monotone quadratic spline (dashed) interpolating monotone data from \cite{Gregory1982}. Cubic spline fails to preserve monotonicity of the data.}
+\caption[Cubic spline (solid) and monotone quadratic spline (dashed) interpolating monotone data]{Cubic spline (solid) and monotone quadratic spline (dashed) interpolating monotone data from \cite{Gregory1982}. Cubic spline fails to preserve monotonicity of the data.}

 \label{ch11:fig1}
 \end{figure}
 
 \begin{figure}[h]
 \centering
 \includegraphics[angle=00,width=8cm]{Chapters/chapter11/gregory1_plot2_b.pdf}
 \label{ch11:fig1}
 \end{figure}
 
 \begin{figure}[h]
 \centering
 \includegraphics[angle=00,width=8cm]{Chapters/chapter11/gregory1_plot2_b.pdf}

-\caption{Hermite cubic spline (solid) and Hermite rational spline interpolating monotone data from \cite{Gregory1982} with non-negative prescribed slopes. Despite non-negative slopes, Hermite cubic spline is not monotone.}
+\caption[Hermite cubic spline (solid) and Hermite rational spline interpolating monotone data]{Hermite cubic spline (solid) and Hermite rational spline interpolating monotone data from \cite{Gregory1982} with non-negative prescribed slopes. Despite non-negative slopes, Hermite cubic spline is not monotone.}

 \label{ch11:fig2}
 \end{figure}
 
 \label{ch11:fig2}
 \end{figure}
 


@@ -395,7 +395,9 @@ u_i=\max_{k\leq i} \min_{l \geq i} \hat y(k,l),
 $$
 with $\hat y(k,l)$ being the unrestricted maximum likelihood estimator of $y_k\ldots,y_l$. For quadratic cost function $\hat y(k,l)$ is the mean, as in PAV and MLS algorithms, for the absolute deviations it becomes the median, and for other cost functions an M-estimator of location. The MLS algorithm can be applied to such isotone regression problems with very little modification, while linear in time algorithm may not be available. Our parallel MLS algorithm will be valuable in such cases.
 
 $$
 with $\hat y(k,l)$ being the unrestricted maximum likelihood estimator of $y_k\ldots,y_l$. For quadratic cost function $\hat y(k,l)$ is the mean, as in PAV and MLS algorithms, for the absolute deviations it becomes the median, and for other cost functions an M-estimator of location. The MLS algorithm can be applied to such isotone regression problems with very little modification, while linear in time algorithm may not be available. Our parallel MLS algorithm will be valuable in such cases.
 

-%\renewcommand{\baselinestretch}{1}
+
+
+%% %\renewcommand{\baselinestretch}{1}

 \begin{table}[!h]
 \begin{center}
 \caption{The average CPU time (sec) of the serial PAVA, MLS and parallel MLS algorithms.  } \label{ch11:table1}
 \begin{table}[!h]
 \begin{center}
 \caption{The average CPU time (sec) of the serial PAVA, MLS and parallel MLS algorithms.  } \label{ch11:table1}


@@ -423,70 +425,72 @@ $n=50 \times 10^6$ &11& 11& -- \\
 \end{tabular}
 \end{center}
 \end{table}
 \end{tabular}
 \end{center}
 \end{table}

-%\renewcommand{\baselinestretch}{2}
+%% %\renewcommand{\baselinestretch}{2}

 
 
 
 

-\begin{figure}[!hp]
- \begin{alltt}
-\begin{center}
-\begin{minipage}{13cm}\small
-template<typename Tx>   
-__device__ Tx Aver(Tx z,int i,int j, Tx *z) \{return (z-z[j+1])/(j-i+1);\}
-
-template<typename Tx>
-__global__ void monotonizekernel(Tx *y, Tx *z, Tx *u, int *key, int n)  
-\{ int i = threadIdx.x + blockIdx.x * blockDim.x;
-   if(i<n) \{
-      int smallestJ = i;
-      Tx curP, smallestP, curz=z[i];
-      smallestP=Aver(curz,i,i,z);
-      for(int j = i+1; j < n; j++) \{
-          curP=Aver(curz,i,j,z);
-          if(smallestP>curP) \{
-               smallestJ = j;
-               smallestP = curP;
-          \}   
-      \}
-      curP=y[i];
-      if(curP > smallestP) t=smallestP;
-                      else smallestJ=i;
-      key[i]=smallestJ;
-      u[i]=t;
-   \}
-\}
-
-template< typename Tx >
-void MonotonizeData(Tx *y, int n, Tx *u) \{
-    thrust::less_equal<int> binary_pred;
-    thrust::maximum<Tx>     binary_op2;
-    thrust::device_vector<Tx> z_d(n+1);
-    thrust::device_vector<int> keys_d(n);      
-    thrust::device_ptr<Tx> y_d(y), u_d(u);
-    thrust::fill(u_d, u_d+n, -1e100);
-    thrust::fill(keys_d.begin(), keys_d.end(), 0);
-
-    thrust::reverse_iterator< typename thrust::device_vector<Tx>::iterator >
-            y_reverse_b(y_d+n), y_reverse_end(y_d), z_reverse_b(z_d.end());
+%% \begin{figure}[!hp]
+%%  \begin{alltt}
+%% \begin{center}
+%% \begin{minipage}{13cm}\small
+%% template<typename Tx>        
+%% __device__ Tx Aver(Tx z,int i,int j, Tx *z) \{return (z-z[j+1])/(j-i+1);\}
+
+%% template<typename Tx>
+%% __global__ void monotonizekernel(Tx *y, Tx *z, Tx *u, int *key, int n)  
+%% \{ int i = threadIdx.x + blockIdx.x * blockDim.x;
+%%    if(i<n) \{
+%%       int smallestJ = i;
+%%       Tx curP, smallestP, curz=z[i];
+%%       smallestP=Aver(curz,i,i,z);
+%%       for(int j = i+1; j < n; j++) \{
+%%           curP=Aver(curz,i,j,z);
+%%           if(smallestP>curP) \{
+%%                smallestJ = j;
+%%                smallestP = curP;
+%%           \}        
+%%       \}
+%%       curP=y[i];
+%%       if(curP > smallestP) t=smallestP;
+%%                       else smallestJ=i;
+%%       key[i]=smallestJ;
+%%       u[i]=t;
+%%    \}
+%% \}
+
+%% template< typename Tx >
+%% void MonotonizeData(Tx *y, int n, Tx *u) \{
+%%     thrust::less_equal<int> binary_pred;
+%%     thrust::maximum<Tx>     binary_op2;
+%%     thrust::device_vector<Tx> z_d(n+1);
+%%     thrust::device_vector<int> keys_d(n);   
+%%     thrust::device_ptr<Tx> y_d(y), u_d(u);
+%%     thrust::fill(u_d, u_d+n, -1e100);
+%%     thrust::fill(keys_d.begin(), keys_d.end(), 0);
+
+%%     thrust::reverse_iterator< typename thrust::device_vector<Tx>::iterator >
+%%             y_reverse_b(y_d+n), y_reverse_end(y_d), z_reverse_b(z_d.end());

        
        

-    thrust::inclusive_scan(y_reverse_b, y_reverse_end, z_reverse_b+1);
+%%     thrust::inclusive_scan(y_reverse_b, y_reverse_end, z_reverse_b+1);

 
 

-    monotonizekernel<<<grid, block>>>(y, thrust::raw_pointer_cast(&z_d[0]), 
-                               u, thrust::raw_pointer_cast(&keys_d[0]), n );
+%%     monotonizekernel<<<grid, block>>>(y, thrust::raw_pointer_cast(&z_d[0]), 
+%%                                u, thrust::raw_pointer_cast(&keys_d[0]), n );

 
 

-    thrust::sort(keys_d.begin(), keys_d.end());
-    thrust::inclusive_scan_by_key(keys_d.begin(), keys_d.end(), 
-                                  u_d, u_d, binary_pred, binary_op2);
-\}
-\end{minipage}
-\end{center}
-\end{alltt}
-\caption{Fragments of implementation of a parallel version of the MLS algorithm using Thrust library.}
-\label{ch11:algMLS}
-\end{figure}
+%%     thrust::sort(keys_d.begin(), keys_d.end());
+%%     thrust::inclusive_scan_by_key(keys_d.begin(), keys_d.end(), 
+%%                                   u_d, u_d, binary_pred, binary_op2);
+%% \}
+%% \end{minipage}
+%% \end{center}
+%% \end{alltt}
+%% \caption{Fragments of implementation of a parallel version of the MLS algorithm using Thrust library.}
+%% \label{ch11:algMLS}
+%% \end{figure}
+
+\lstinputlisting[label=ch11:algMLS,caption=Fragments of implementation of a parallel version of the MLS algorithm using Thrust library.]{Chapters/chapter11/code4.cu}

 
 \section{Conclusion} \label{ch11:conc}
 
 We presented three GPU-based parallel algorithms for approximating monotone data: monotone quadratic spline, monotone Hermite rational spline and minimum lower sets algorithm for monotonizing noisy data. These tools are valuable in a number of applications that involve large data sets modeled by monotone nonlinear functions.
 
 \section{Conclusion} \label{ch11:conc}
 
 We presented three GPU-based parallel algorithms for approximating monotone data: monotone quadratic spline, monotone Hermite rational spline and minimum lower sets algorithm for monotonizing noisy data. These tools are valuable in a number of applications that involve large data sets modeled by monotone nonlinear functions.

-The source code of the package monospline is available from \texttt{www.deakin.edu.au/$\sim$ gleb/monospline.html }
+The source code of the package monospline is available from \texttt{www.deakin.edu.au/$\sim$gleb/monospline.html }

 
 \putbib[Chapters/chapter11/biblio11]
 
 \putbib[Chapters/chapter11/biblio11]