\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{enumitem}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{epsfig}
\usepackage[right=0.8in, top=1in, bottom=1.2in, left=0.8in]{geometry}
\usepackage{setspace}
\usepackage{xcolor}
\spacing{1.06}

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{\vspace{0.25cm}
      \hbox to 5.78in { {COMS 4995-2:\hspace{0.12cm}Advanced
          Algorithms (Spring'20)} \hfill #2 }
      \vspace{0.48cm}
      \hbox to 5.78in { {\Large \hfill #5  \hfill} }
      \vspace{0.42cm}
      \hbox to 5.78in { {#3 \hfill #4} }\vspace{0.25cm}
    }
  }
  \end{center}
  \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{#3}{Scribes:\hspace{0.08cm}#4}{Lecture #1}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}

\newcommand{\E}{{\mathbb E}}
\DeclareMathOperator{\var}{Var}

\begin{document}

\lecture{Lecture 23: Parallel models, MPC model}{Apr 21,
  2020}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Wang Yao, Zhengping Jiang}}

\section{Introduction}
Today's lecture is about
\begin{itemize}[]
\item PRAM
\item MPC
\end{itemize}

\section{Parallel Randomized Access Machine (PRAM)}

\subsection{PRAM:}
\begin{itemize}[label=-]
\item P processors
\item Shared memory
\item Synchronized
\end{itemize}

Now a natural question here is about confidence. Is it allowed for two processors to read the same location at the same time? Is it allowed for two processors to write the same location at the same time?

This leads to 4 different sub-type architectures: \textbf{E/C-R-E/C-W}, where E stands for exclusive and C stands for concurrent. Now the question is about the performances of these 4 architectures.

\subsection{Performance Measure:}
\begin{itemize}[label=-]
\item Parallel time ($\approx$ Depth of circuit)
\item Work ($\approx$ Size of circuit)
\end{itemize}


\begin{example}
Computing XOR for n bits
\end{example}
\begin{figure}[h]
    \includegraphics[width=0.4\textwidth]{Example1.pdf}
    \caption{}
    \label{fig:Example1}
\end{figure}
On EREW we need $O(\log n)$ time

Lower bound: Even on CRCW we need $\Omega(\frac{\log n}{\log \log n})$ time.


\section{Massive Parallel Computing (MPC) $\approx$ Map Reduce System}
\subsection{MPC}

\begin{itemize}[label=-]
    \item M machines
    \item Each machine has space $O(S)$ \\
    (Local space, the biggest difference between PRAM and MPC is the space is not shared.)\\
    \hspace*{0.6cm}$\rightarrow{}$ Total space $O(mS)$
    \item Computation proceeds in rounds
    \begin{itemize}
        \item Do any local computation
        \item Shuffle step, which means change information between machines\\
        (Shuffle has constraint that the amount of data in/out for each machine is $O(S)$)
    \end{itemize}
\end{itemize}

\subsection{Performance Measure:}
\begin{itemize}[label=-]
\item Number of rounds ($\approx$ Parallel time)
\item Total space used ($\approx$ Work)
\end{itemize}

Related to  BSP: Bulk-Synchronous-Parallel (Valiant)\\

\textbf{Note}: Can simulate "Shared Memory" by: Each machine be responsible for S addresses 

\begin{theorem}
Can simulate PRAM (at least EREW) where number of rounds $R=O(Parallel-time)$ (for any $S=\Omega(1)$)
\end{theorem}

\begin{proof}
Why easy for EREW: each machine is responsible for S addresses, this means the number of requests is $\frac{O(S)}{round}$
\end{proof}
\textbf{Params:}\\
\begin{itemize}[label=-]
\item $S=O(1)\rightarrow{}$ Like PRAM (EREW)
\item S can be much larger, total space $O(m\cdot S)\geq N$
\item Ideally $m\cdot S=O(N)$
\item $S=N^\delta$, $\delta=\text{Small constant}$

If each machine has a list of all other machines $\rightarrow{}S\geq m \rightarrow{}S\geq \sqrt{N}$, i.e. $\delta=\frac{1}{2}$
\end{itemize}

\textbf{Question:} When $\delta=\Omega(1)$ can we do better than PRAM ?\\

\textbf{Problem 1:} XOR of N bits\\

Note: At start each machine has S bits of inputs, split arbitrarily\\

PRAM:~$O(\log N)$ Parallel time \\



$R=O(1)$ rounds, when $S=\sqrt{N}$\\

\begin{figure}[h]
    \centering
    \includegraphics[width=0.5\textwidth]{Problem1.pdf}
    \caption{}
    \label{fig:problem1}
\end{figure}

\textbf{Algorithm:}[see Figure~\ref{fig:problem1}]
\begin{itemize}[label=-]
\item XOR locally
\item Compute answer to C
\item C XORs its inputs
\end{itemize}

$R=O(\log_S N)=O(\frac{1}{\delta})$, When $S=N^\delta$, implement that in S-Arrays tree where number of rounds is the height of tree $=O(\log_S N)$

\begin{theorem}
Can simulate CRCW with number of rounds $R=O(\text{Parallel-time} \cdot \log_S N)$
\end{theorem}
\textbf{Problem 2:} Prefix sum\\

Input: $(i,a_i), i=1,2,\cdots,n$

Output: $(i,\sigma_i), \sigma_i=\sum_{j=i}^i$\\

We'll solve in rounds $R=O(\log_S N)$\\



$M_l(i)=\text{Ancestor of i at level } l, l=1,2,\cdots,n$\\

\textbf{Algorithm:}[see Figure~\ref{fig:problem2_tree}]
\begin{itemize}[label=-]
\item Send $(i,a_i)$ to machine $M_L(i)$
\item For $l=L\nearrow2$ send sum of "local" numbers to parent
\item For $l=1\searrow L-1$ send to child c: the sum of children $1,2,\cdots,c-1$ plus $\sigma_p$

where $\sigma_p$ is the sum of $a_i$s to the left of the node.[see Figure~\ref{fig:problem2_tree_2}.]
\item Machine $M_L(i)$ computes $\sigma_i=\sigma_p+a_j+a_{j+1}+\cdots+a_i$ and produces pair $(i,a_i)$ [see Figure~\ref{fig:problem2_tree_3}.]
\end{itemize}

Number of rounds $R=O(L)=O(\log_S N)=O(\frac{1}{\sigma})$
\begin{figure}[!h]
    \centering
    \includegraphics[width=\textwidth]{Problem2_tree.pdf}
    \caption{}
    \label{fig:problem2_tree}

    \begin{minipage}[l]{.45\textwidth}
        \includegraphics[width=\textwidth]{Problem2_tree_2.pdf}
        \caption{}
        \label{fig:problem2_tree_2}
    \end{minipage}
    \begin{minipage}[r]{.45\textwidth}
        \centering
        \includegraphics[width=\textwidth]{Problem2_tree_3.pdf}
        \caption{}
        \label{fig:problem2_tree_3}
    \end{minipage}

\end{figure}
\clearpage

\textbf{Problem 3: Sorting}\\

Input: $(i,a_i), i=1,2,\cdots,n$

Output: $(i,a_i,r), i=1,2,\cdots,n, r=\text{ rank of }a_i \text{ in } \{a_j\}_{j=1,2,\cdots,n}$\\

$S=O(n^{\frac{3}{4}})$, $\delta=\frac{3}{4}$, $m=O(n^\frac{1}{4})$, we can also do like $S\geq N^\delta$\\

Idea: Quick-sort with many pivots $\rightarrow{} n^\frac{1}{4}$
\begin{enumerate}
\item For each $i\in [n]$ call i a pre-pivot with probability $\frac{n^{1/3}}{n}$

$\rightarrow{}$ number of pre-pivots is $O(n^{1/3})$
\item Send pre-pivots to every machine
\item For every machine and every pre-pivots $p$, compute "local rank" $\rightarrow{}$ number of elements $\leq p$
\item Every machine sends "local rank" of every pre-pivot to C
\item C computes rank of each pre-pivot
\item C chooses set of $n^{1/4}$ pre-pivots, called $\mathcal{P}$, with ranks $i\cdot n^{3/4}\pm O(n^{3/4})$, $i=1,2,\cdots,n^{1/4}$

$\rightarrow{}$For averaging purpose
\item C sends pivots $\mathcal{P}$, together with their ranks to all machines
\item Each machine for each $(i,a_i)$ finds j s.t. $p_j\leq a_i<p_{j+1}$ ($p_0=-\infty$, $p_{n^{1/4}+1}=+\infty$), send $a_i$ to machine $j$
\item Machine $j$ has all $a_i$s s.t. $p_j\leq a_i< p_{j+1}$, sort locally, assign ranks to $a_i$ using rank of $p_j$
\end{enumerate}

\end{document}
