\documentclass{beamer} 
\usepackage{graphicx} 
\usepackage{url}
\usepackage{fancyvrb}
\usepackage{relsize}
\usepackage{listings}

\lstset{language=R}

\mode<presentation>
{ \usetheme{Hannover} }

\title{Parallel Computation in R:  What We Want, and How We (Might) Get It}
\author{Norm Matloff \\
University of California at Davis  
}

\date{Keynote Address 
\\
useR! 2017
\\
Brussels, 6 July, 2017
}

\begin{document} 

% \lstset{language=R}
\lstset{language=R,basicstyle=\smaller,commentstyle=\rmfamily\smaller,
   showstringspaces=false,
   xleftmargin=4ex,literate={<-}{{$\leftarrow$}}1 {~}{{$\sim$}}1}

\begin{frame} 
\titlepage
\tableofcontents

% URL for these slides (repeated on final slide):
% \url{http://heather.cs.ucdavis.edu/parmatpows/Slides.pdf}

\end{frame}

\begin{frame}
\frametitle{Shameless Promotion}\pause

\begin{columns}

\column{0.6\linewidth}

\begin{center}
\includegraphics[width=2in]{RegressBook.jpg}
\end{center}

\column{0.3\linewidth} 
\Large{Out July 28!} 

\vspace{1in}

\normalsize{
(A longheld plan --- decades --- now finally got around to it.)
}

\end{columns}

\end{frame}

\begin{frame}
\frametitle{Disclaimer}\pause

\begin{itemize}

\item ``Everyone has an opinion.''
\pause

\item I'll present mine.
\pause

\item I will essentially propose general design patterns,
\pause
illustrated with our own package {\bf partools} but meant to be general.
\pause

\item Dissent is encouraged. :-)

\end{itemize}

\end{frame}

\begin{frame}
\frametitle{The Drivers and Their Result}\pause

\begin{itemize}

\item Parallel hardware for the masses:
\pause

   \begin{itemize}
   
   \item 4 cores standard, 16 not too expensive
   \pause

   \item GPUs
   \pause

   \item Intel Xeon Phi, $\approx$ 60 cores (!), coprocessor,
   as low as a few hundred dollars
   \pause

   \end{itemize}

\item Big Data
\pause

   \begin{itemize}
   \item Whatever that is.
   \pause
   \end{itemize}

\end{itemize}

\bigskip

Result:  Users believe, 
\pause

\begin{quote}

``I've got the hardware and I've got the data
need --- so I should be all set to do parallel computation in R on the
data.''

\end{quote}

\end{frame}

\begin{frame}
\frametitle{Not So Simple}\pause

\begin{itemize}

\item Non-``embarrassingly parallel'' algorithms.
\pause

\item Overhead issues:
\pause

   \begin{itemize}

   \item Contention for memory/network.
   \pause

   \item Bandwidth limits --- CPU/memory, CPU/network, CPU/GPU.
   \pause

   \item Cache coherency problems (inconsistent caches in multicore
   systems).
   \pause

   \item Contention for I/O ports.
   \pause

   \item OS/R limits on number of sockets (network connections).
   \pause

   \item Serialization.
    
   \end{itemize}

\end{itemize}

\end{frame}

\begin{frame}
\frametitle{Wish List}\pause

\begin{itemize}

\item Ability to run on various types of hardware --- from R.
\pause

\item Ease of use for the non-cognoscenti.
\pause

\item Parameters to tweak for the experts or the daring.

\end{itemize}

\end{frame}

\begin{frame}
\frametitle{The Non-cognoscenti Can Become the Daring}\pause

\bigskip

{\it Help, I'm in over my head here!} -- a prominent R developer, 
entering the parallel comp.\ world.
\pause

\bigskip

\begin{center}
\includegraphics[width=1.5in]{Scream.jpg} 
\end{center}

\end{frame}

\begin{frame}
\frametitle{Non-cognoscenti (cont'd.)}\pause

\begin{itemize}

\item Casual users, even if they are deft programmers, quickly
learn that this is no casual operation.
\pause

\item After getting burned by disappointing performance, some will be
emboldened to learn the subtleties.
\pause

\item Painless parallel computation is not possible.

\end{itemize}

\end{frame}

\begin{frame}[fragile]
\frametitle{Example:  Matrix-Vector Multiplication}\pause

\begin{itemize}

\item $D = AX$, with $A$ being $n \times p$ and $X$ being $ p \times 1$
\pause

\item Naive approach:  Parallelize the loop
\pause

\begin{lstlisting}
for (i in 1:n) 
   d[i] <- a[i,] %*% x
\end{lstlisting}
\pause

\item Naive use of {\bf foreach} package 
likely quite slow; scatter-gather overhead a substantial
proportion of the overall time.

\end{itemize}

\end{frame}

\begin{frame}[fragile]
\frametitle{Example (cont'd.)}\pause

\begin{itemize}

\item Solution is obvious:
\pause
For $r$ processes, partition rows $A_i$ into 
$n/r$ chunks and change the above loop from $n$ iterations to $n/r$. 
\pause

\begin{lstlisting}
for (k in 1:r)  
   d[rowblockk] <- a[rowblockk,] %*% x
\end{lstlisting}
\pause

\item 
But {\bf casual users may miss this}.
\pause
And {\bf automatic parallelization \underline{would} miss it}. 

\end{itemize}

\end{frame}

\begin{frame}
\frametitle{Use Cases}\pause

A few reference examples, somewhat spanning the space:
\pause

\begin{itemize}

\item Compute-intensive parametric:  Quantile regression.
\pause

\item Compute-intensive nonparametric:  Nearest-neighbor regression.
\pause

\item Compute-intensive nonparametric: Graph algorithms.
\pause

\item Run-of-the-mill aggregation:  Group-by-and-find-means op.
\pause

\item Tougher aggregation:  Credit card fraud detection.

\end{itemize}

\end{frame}

\begin{frame}
\frametitle{Software Alchemy (SA)}\pause

\begin{itemize}

\item My term for method developed by a number of authors (Matloff,
2016).
\pause

\item Break data into chunks.  Apply estimator, say {\bf lm()} to each
chunk, then average the results.
\pause

\item For parallel comp. with $r$ processes, use $r$ chunks.
\pause

\item Same statistical accuracy.
\pause

\item Often produces {\it superlinear} speedup, i.e.\ $> r$.
\pause

\item Useful in some apps.
\pause

\item Available in {\bf partools} package (NM, C. Fitzgerald),
{\bf github.com/matloff}.

\end{itemize}

\end{frame}

\begin{frame}
\frametitle{Programming World Views}\pause

\begin{itemize}

\item Message passing/distributed comp.:  Send data to the R processes;
each process works on its data; possibly combine results.  \pause

\bigskip

In R, e.g.\ {\bf parallel} (the part from {\bf snow}), {\bf rMPI}.
\pause

\bigskip

In C, e.g.

\bigskip

\includegraphics[width=0.8in]{MPILogo.jpg} 

\end{itemize}

\bigskip

\end{frame}

\begin{frame}
\frametitle{World Views (cont'd.)}\pause

\begin{itemize}

\item 
Shared-memory:  The processes have access to a common memory, so no data
transfer needed.
\pause

\bigskip

Not (yet) common in R, but do have
{\bf Rdsm} (NM), {\bf thread} (R. Bartnik). 
\pause

\bigskip

In C, e.g.\ 

\bigskip

\includegraphics[width=0.8in]{OpenMPLogo.jpg}
\hspace{0.5in}
\includegraphics[width=0.8in]{CUDALogo.jpg}

\end{itemize}



\end{frame}

\begin{frame}
\frametitle{Premises in This Talk}\pause

\begin{itemize}

\item There is a lot of hype about parallel computation. 
\pause

\item Parallel computation is not for the casual user.
\pause

\item Efficient {\bf automatic} parallelization ---
\pause
no user intervention/sophistication needed ---
\pause
is generally not possible and should not be expected.
\pause
Please stop asking for it. :-)
\pause

\item As in politics, transparency in software tools is vital. :-)  
\pause
What do those APIs really do?
\pause

\item UseRs are different from aggregation-oriented (e.g.\ Spark) users.
\pause

   \begin{itemize}

   \item Aggregation is only part of what useRs do.
   \pause

   \item We need iterative estimators, std. errors, linear algebra, etc.
   \pause

   \item Newer methodology, e.g.\ ML, random graphs etc.
   \pause

   \item UseRs may have become fairly good programmers, but lack systems
   knowledge.

   \end{itemize}

\end{itemize}

\end{frame}

\begin{frame}
\frametitle{Premises (cont'd).}\pause

\begin{itemize}

\item Use of SA as means of parallelization should be fine for things
like linear models, quantile regression, k-nearest neighbor regression etc.
\pause

\item Some apps, e.g.\ graph algorithms, are based on sharing state, so
shared-memory world view/hardware may be needed.
\pause

\item But in most of the Use Cases, including the SA ones, distributed
world view works well,
\pause
and may be needed anyway at very large scale.
\pause

\item {\bf Bottom line:} For most Use Cases, use one of the following
\pause

   \begin{itemize}

   \item SA

   \item Distributed computation,
   \pause
   esp.\ using ``Leave it there'' concept.

   \end{itemize}

\end{itemize}

\end{frame}

\begin{frame}
\frametitle{Spark}\pause

\includegraphics[width=1in]{SparkLogo.png}

\bigskip

One well-publicized distributed approach today is Spark/SparkR.
\pause

% Having an R interface to Spark may not be very useful for most R users.
   \begin{itemize}

   \item MapReduce not well-suited to most of the above Use Cases.
   \pause

   \item Highly elaborate Spark machinery violates the transparency
   requirement.
   \pause

   \item  On the other hand, the distributed file system approach of
   Hadoop/Spark is good for useRs too.

   \end{itemize}

% http://www.sciencedirect.com/science/article/pii/S0169260716303807

\end{frame}

\begin{frame}
\frametitle{Example Study: I}\pause

\begin{itemize}

\item (Gittens {\it et al}, 2016). {\it Matrix Factorizations at Scale:
a Comparison of Scientific Data Analytics in Spark and C+MPI Using Three
Case Studies}
\pause

In spite of careful optimization, performance of Spark ranged from 
slightly slower to really, really slower. :-)
\pause

Just not what Spark was designed for.
\pause

\bigskip

{\it My personal side comment:}  Not clear whether, say, PCA, has much
accuracy or usefulness at the truly Big Data scale, including for sparse
matrices.

\end{itemize}

\end{frame}

\begin{frame}
\frametitle{Example Study: II}\pause

% https://www.researchgate.net/publication/282543037_Big_data_analytics_in_the_cloud_Spark_on_Hadoop_vs_MPIOpenMP_on_Beowulf

Reyes-Ortiz {\it et al}, {\it Big Data Analytics in the Cloud: Spark on
Hadoop vs MPI/OpenMP on Beowulf}
\pause

\bigskip

Abstract:
\pause

\begin{quote}
...MPI/OpenMP outperforms Spark by more than one order of magnitude in
terms of processing speed and provides more consistent performance.
However, Spark shows better data management infrastructure and the
possibility of dealing with other aspects such as node failure and data
replication 

\end{quote}
\pause

\bigskip

I contend that very few useRs, even those who need parallel
computation, need to guard against node failure.

\end{frame}

\begin{frame}
\frametitle{The Principle of ``Leave It There''}\pause

Extremely simple idea, but very powerful.
\pause

\begin{itemize}

\item Common setting (e.g.\ {\bf parallel} package):
Scatter/gather.
\pause

   \begin{itemize}

   \item [(a)] Manager node partitions (scatters) data to worker nodes.
   \pause

   \item [(b)] Worker nodes work on their chunks.
   \pause

   \item [(c)] Manager collects (gathers) and combines the results.
   \pause

   \end{itemize}

\item {\bf But NO, avoid step (c) as much as possible.}

\end{itemize}

\end{frame}

\begin{frame}
\frametitle{Example of ``Leave It There''}\pause

Say we wish to perform the following on some dataset:
\pause

\begin{itemize}

\item Convert categorical variables to dummies.

\item Replace NA values by means. (Not great, but just an example.)

\item Remove outliers, as def. by $|X - \mu| > 3 \sigma$.  (Just an
example.)

\item Run linear regression analysis.

\end{itemize}
\pause

The point is to NOT do the gather op after each of the above steps.
\pause
Leave the data there (in distributed form).
\pause

\bigskip

Note too:  The last step can be done in parallel too, with SA.

\end{frame}

\begin{frame}
\frametitle{Comparing Just a Few Packages}\pause

A few packages that facilitate the above approach:
\pause

\bigskip

\begin{tabular}{|r|r|r|}
\hline
pkg & flexibility & high-level ops \\
\hline
{\bf partools} & high & few \\
\hline
{\bf ddR} & medium & medium \\
\hline
{\bf multidplyr} & low & more \\
\hline
\end{tabular}

\end{frame}

\begin{frame}
\frametitle{Going One Step Further:  Distributed Files}\pause

\begin{itemize}

\item Since will do ``Leave it there'' over many ops,
\pause

\item might as well distribute a persistent version of the data,
i.e.\ have {\bf distributed files.}
\pause

\item Like Hadoop/Spark, but without the complex machinery.
\pause

\item Our {\bf partools} package includes various functions for managing
distributed files

\end{itemize}

\end{frame}

\begin{frame}
\frametitle{Distributed Files in partools}\pause

\begin{itemize}

\item File {\bf x} spread across {\bf x.001}, {\bf x.002} etc.

\item {\bf filesplit():} Make distributed file from monolithic one.

\item {\bf fileread():}  If node {\bf i} does {\bf fileread(x,d)}, then
{\bf x.i} will be read into the variable {\bf d}.

\item {\bf filesave():}  Saves distributed data to distributed file.

\item Etc.

\end{itemize}

\end{frame}

\begin{frame}
\frametitle{Partools Example of ``Leave It There''}\pause

\begin{itemize}

\item Say have distributed file {\bf xy}, physically stored in files
{\bf xy.001}, {\bf xy.002} etc.
\pause

\item Say we have written functions (not shown) {\bf NAtoMean} and {\bf
deleteOuts}, to handle missing values and remove outliers, as mentioned
before.  The functions have been given to the workers

\end{itemize}

% gensim <- function(n) {
%    x <- rnorm(n)
%    k <- round(0.1*n)
%    x[sample(1:n,k)] <- NA
%    y <- x + rnorm(n)
%    data.frame(x,y)
% }
% 
% NAtoMean <- function(v) {
%    vbar <- mean(v,na.rm=TRUE)
%    v[which(is.na(v))] <- vbar
%    v
% }
% 
% deleteOuts <- function(v) {
%    vbar <- mean(v,na.rm=TRUE)
%    vs <- sd(v,na.rm=TRUE)
%    vs3 <- 3 * vs
%    v[abs(v-vbar) > vs3] <- NA
%    v
% }
% 
% cls <- makeCluster(2)
% setclsinfo(cls)
% xy <- gensim(10000)   
% distribsplit(cls,'xy')
% clusterExport(cls,c('NAtoMean','deleteOuts'))
% clusterEvalQ(cls,xy <- apply(xy,2,NAtoMean))
% clusterEvalQ(cls,xy <- apply(xy,2,deleteOuts))
% 
% clusterEvalQ(cls,xy <- as.data.frame(xy))
% calm(cls,'y ~ .,data=xy')$tht

\end{frame}

\begin{frame}[fragile]
\frametitle{``Leave It There'' Example (cont'd.)} \pause

\begin{lstlisting}
# do NA removal at each worker, 
# on the worker's chunk of xy
clusterEvalQ(cls,xy <- apply(xy,2,NAtoMean))
# do the outlier removal at each worker,
# on the worker's chunk of xy
clusterEvalQ(cls,xy <- apply(xy,2,deleteOuts))

# use Software Alchemy to perform linear regression, 
# returning just the coefficients in this case
calm(cls,'y ~ .,data=xy')$tht

\end{lstlisting}

\end{frame}

\begin{frame}[fragile]
\frametitle{What Is Happening}\pause

E.g.

\begin{lstlisting}
clusterEvalQ(cls,xy <- apply(xy,2,NAtoMean))
\end{lstlisting}
\pause

We are saying, At each worker node, do

\begin{lstlisting}
xy <- apply(xy,2,NAtoMean))
\end{lstlisting}

which means, each node does the {\bf apply} op {\it on its portion of}
{\bf xy}.

\end{frame}

\begin{frame}
\frametitle{``Leave It There'' Example (cont'd.)} \pause

The key point:
\pause

\begin{quote}

For typical data analysis, hopefully we have:
\pause

\begin{itemize}

\item Data file stored in distributed fashion.
\pause

\item Lots of ``leave it there'' ops:
\pause

   \begin{itemize}

   \item Parallel.
   \pause

   \item No network delay.
   \pause

   \item No serialization overhead.
   \pause

   \end{itemize}

\item Have occasional ``collect'' ops, hopefully small in size, e.g.
from an aggregation such as {\bf colMeans}.
\pause

\item If change data or create new data, save in distributed file form too!
\pause
Use {\bf partools::filesave}.

\end{itemize}

\end{quote}

\end{frame}

\begin{frame}
\frametitle{Heavy Use of SA}\pause

\begin{itemize}

\item Have SA forms of
\pause

   \begin{itemize}
 
   \item {\bf lm()/glm()}
   \pause

   \item k-NN
   \pause

   \item random forests
   \pause

   \item PCA
   \pause

   \item {\bf quantile()}
   \pause

   \end{itemize}

\item Very easy to make your own SA functions.

\end{itemize}

\end{frame}

\begin{frame}[fragile]
\frametitle{Various Collection Ops}\pause

E.g. {\bf addlists()}.
\pause

Say have distributed list, 2 compoments.  From one, manager node
receives 

\begin{lstlisting}
list(a=3,b=8)
\end{lstlisting}

and from the other

\begin{lstlisting}
list(a=5,b=1,c=12)
\end{lstlisting}

The functions ``adds'' them, producing (non-distributed)

\begin{lstlisting}
list(a=8,b=9,c=12)
\end{lstlisting}


\end{frame}

\begin{frame}
\frametitle{Conclusions}\pause

No ``silver bullet.''
\pause
But the following should go a long way toward your need for parallel
computation.
\pause
\bigskip

\begin{itemize}

\item SA for the computational stuff.
\pause

\item For aggregation, ``leave it there'' and distributed files.
\pause

\item Could do in other packages, not just {\bf partools}.

\end{itemize}

\bigskip
\pause
Ready for the dissent. :-)

\end{frame}

\end{document}