\documentstyle[12pt,epsf]{book}

% abra 
% Fig. \ref{abra-babra}
%
%\begin{figure}
%\centerline{\epsfysize=9cm\epsffile{abra.eps}}
%\caption{Development Cycle in GRADE}
%\label{abra-babra}
%\end{figure}
%

%\input psfig.tex

\headsep=1.2cm
\topmargin=0.0cm
\footskip=1.5cm
\oddsidemargin=0.416cm
\evensidemargin=0.416cm
\textheight=18.33cm
\textwidth=12.5cm
\parskip=\medskipamount
\parindent=0pt
\renewcommand{\footnoterule} {\kern-3pt \hrule width \textwidth \kern 2.6pt}

\pagestyle{headings}
\setcounter{tocdepth}{3}  % 3-subsubsection; 4-paragraph;
                          % 5-subparagraph; 2-subsection(default)


\begin{document}

\chapter {GRAPH ALGORITHMS}

\begin{itemize}
\item{\bf Definitions}

\hskip 0.2in\hbox {
\vbox {
\hbox {directed}
\hbox {complete}       
\hbox {weight}
\hbox {subgraph}
\hbox {path}   
\hbox {independent set}
\hbox {cycle}    
\hbox {clique}
\hbox {tree, forest}
\hbox {bipartite}
\hbox {connected} 
\hbox {colouring}
\hbox {P problems}
\hbox {NP problems, NPC}
\hbox {adjacency matrix}
\hbox {sparse $\vert E\vert\ll\vert V^2\vert /2$}
\hbox {dense $\vert E\vert\sim\vert V^2\vert /2$}
\hbox {MATROIDS}
\hbox {GREEDY algorithms}
      }
%\begin{figure}
%\vbox { \vbox { \hbox {\epsffile{./figs/gr2.ps}}}
        \vbox { \hbox {\epsffile{./figs/gr3.ps}\epsfysize=2in}}
%      }
%\caption{}
%\label{}
%\end{figure}

\bf Representations}

  \begin{itemize}
  \item {matrix representation}
  \item{linked list}
\bigskip

%\centerline{\psfig{figure=./figs/gr_rep1.ps,height=2.35in}}
%\centerline{\psfig{figure=./figs/gr_rep2.ps,height=2.35in}}
%\centerline{\psfig{figure=./figs/gr_rep3.ps,height=2.35in}}
%\begin{figure}
%\centerline{\epsfysize=9cm\epsffile{abra.eps}}
%\caption{Development Cycle in GRADE}
%\label{abra-babra}
%\end{figure}
%

  \end{itemize}

\end{itemize}

\newpage\addcontentsline{toc}{section}{Basic Graph Problems}
\section*{Basic Graph Problems}

Application in the practice.

Many different issues.

\begin{itemize}
\item{\bf Small Overview}

\hskip 0.2in\hbox { {\it "Easy" problems} \hskip 0.2in [Solvable by Polynomial Algorithm]}
\medskip

\hskip 0.2in\hbox{
 \vbox{
 \hbox { connectivity problems}
 \hbox { shortest (weighted) path}
 \hbox { minimum spanning tree}
 \hbox { Flow problems}
 \hbox { Bipartite graph matching}
 \hbox { minimum cut}
 \hbox { etc.}
      }
}
\bigskip

\hskip 0.2in\hbox{ {\it "Hard" problems} \hskip 0.1in [Non Solvable in P, belongs to NP or NPC]}
\medskip

\hskip 0.2in\hbox{
 \vbox{
\hbox { graph isomorphy}
\hbox { max. independent set}
\hbox { colouring}
\hbox { Hamiltonian path}
\hbox { max. clique}
\hbox { max. cut.}
\hbox { etc.}
      }
}

\newpage\addcontentsline{toc}{section}{Matrix Techniques}
\section*{Matrix Techniques}

\item{\bf Operations: $\cdot\quad ; +$}
\bigskip

%\vbox {
%\hbox{\psfig{figure=./figs/gr4.ps,width=5in}}
%\begin{figure}
%\centerline{\epsfysize=9cm\epsffile{abra.eps}}
%\caption{Development Cycle in GRADE}
%\label{abra-babra}
%\end{figure}
%
\vskip -14mm
\hbox {The number of the paths leading from $v_i$ to $v_j$ 
and length $\leq 2$.}


The $A^r={a^{(r)}_{i,j}}$ tells how many path leads
from $v_i$ to $v_j$ which length $\leq r$.

\item{\bf Operations: Bool AND; Bool OR}

The $C^r={c^{(r)}_{i,j}}$ tells wether is there any path leading 
from $v_i$ to $v_j$ having length $\leq r$.
\medskip

%\hbox {
%  \vbox {\hbox to 2in {If there is a path from $v_i$ to $v_j$ then there exists a path which 
%              length $\leq u-1$.}}
%  \vbox {\hbox{\psfig{figure=./figs/gr5.ps,width=1.5in}}}
%}
%\begin{figure}
%\centerline{\epsfysize=9cm\epsffile{abra.eps}}
%\caption{Development Cycle in GRADE}
%\label{abra-babra}
%\end{figure}
%

\newpage\addcontentsline{toc}{section}{Transitive Closure of a Graph}
\section*{Transitive Closure of a Graph}

\item{\bf Definition} $G=(V,E)$ graph, $G^*=(V, E^*)$ is its transitive closure 
if 
$$ (v_i, v_j)\in E^*\Longleftrightarrow \exists \; {\rm path}\; 
   {\rm in}\; G \;{\rm from}\; v_i \;{\rm to}\; v_j.
$$
\item{\bf Computing the $C$ closure matrix}

We have to compute the $A^{(n-2)}$.

Instead of computing $A^1, A^2, A^3, \ .\ .\ . , A^{n-2}$ we
multiply $A^r\times A^r$, so $A^1, A^2, A^4,\ .\ .\ . , A^{n-1}$.

We need: $\lceil\log (n-1)\rceil $ matrix multiplication.
(Any matrix multiplication method can be used.)

Sequential complexity: $\Theta (n^3)$.

Transitive closure sequential complexity:
$$\Theta (n^3\cdot\log n)$$

\item{\bf Parallel formulation}

E.g.: DNS matrix multiplication on hypercube 
$n^3$ processors, $\Theta (\log n)$ parallel execution time.

Transitive closure parallel execution time:
$$\Theta (\log ^2 n)$$

\end{itemize}

\newpage\addcontentsline{toc}{section}{Single Source Shortest Path}

\section*{Single Source Shortest Path}

\hbox{
\vbox {\hsize=2in 
       \hbox{ We want to get }
       \hbox{ the minimum weight path}
       \hbox{ to each $U\in V-\{ v\}$}
       \hbox{ where $G=(V, E, w)$}
       \vskip 0.3in
      }
\hskip 0.3in
%\vbox {\hbox to 2.1in{\psfig{figure=./figs/gr6.ps,width=2in}}}
}
%\begin{figure}
%\centerline{\epsfysize=9cm\epsffile{abra.eps}}
%\caption{Development Cycle in GRADE}
%\label{abra-babra}
%\end{figure}
%

(Why we do not start with a single $(v:u)$ pair?)

\begin{itemize}

\item{\bf Dijkstra algorithm} ($G$ directed, $w(\cdot \ ,\cdot )\geq 0$)
{\bf GREEDY!}
\medskip

\hbox{
\vbox {\hsize=2in 
       \hbox{ $V_T$ the set we investigate,}
       \hbox{ $l\lbrack \rbrack $ array stores the weights.}
       \hbox{ to each $U\in V-\{ v\}$}
       \hbox{ where $G=(V, E, w)$}
       \vskip 0.3in
      }
\hskip 0.3in
%\vbox {\hbox to 2.1in{\psfig{figure=./figs/gr7.ps,width=2in}}\vskip -9mm}
}
%\begin{figure}
%\centerline{\epsfysize=9cm\epsffile{abra.eps}}
%\caption{Development Cycle in GRADE}
%\label{abra-babra}
%\end{figure}
%


     \begin{itemize}
     \item{} $V_T:=\{ s\} $
     \item{} Initialize $l\lbrack \rbrack $ :
     \end{itemize}     
     $$l\lbrack v\rbrack=\cases{w(s, v)\ \ \ (s, v)\in E\cr
                              \infty \quad{\rm otherw.}\cr }$$
     
     \begin{itemize}
     \item{} Iteration: odd new vertex to $V_T$ while $V_T\neq V$

      take $u\in V\backslash V_T$ where  $l\lbrack u\rbrack $ is the minimum 

      $V_T=\{ u\} \bigcup V_T$

      recompute the weight array

     $$l\lbrack v\rbrack=\min\{ l\lbrack v\rbrack, l\lbrack u\rbrack + w(u, v)\}$$
     $$(V\not\in V_T)$$
     \end{itemize}

\item{\bf Sequential complexity:} $\Theta (n^2)$

\item{\bf Parallel formulation}

We cannot add more than one vertex in one step. Parallelism
can take place only in computing the weights.
The block striped representation of the $A$ matrix:
\bigskip 

%\centerline{\psfig{figure=./figs/gr8jo.ps}}
%\begin{figure}
%\centerline{\epsfysize=9cm\epsffile{abra.eps}}
%\caption{Development Cycle in GRADE}
%\label{abra-babra}
%\end{figure}
%
\vskip -17mm
At each iteration step:
    \begin{itemize}
    \item{} Every $P_i$ processor selects the min. weight node $\rightarrow $
            `single accumulation' $P_1$ gets the global minimum.
    \item{} $P_1$ broadcast the selected element (e.g. $`u'$) and
            its weight $l\lbrack u\rbrack $. $P_i$ responsible for $u$ marks $u\in V_T$.
    \item{} $P_i$ processors computes the weights

     $$l\lbrack v\rbrack = 
        \min\{ l\lbrack v\rbrack ,\; l\lbrack u\rbrack\; + \; w(u, v)\}$$
\hbox{in the local array | by broadcasts | in block stripe of $A$}
    \end{itemize}

\item{\bf Mapping onto different architectures}
\medskip

{\it Hypercube}

\bigskip
      
      \begin{itemize}
       
      \item{} Each processor computes the min: $$\Theta ({n\over p })$$
      \item{} Single node accumulation and one to all broadcast:
              $$\Theta (\log p)$$
      \item{} Parallel running time:

       $$\Theta (n\cdot {n\over p})+\Theta (n\cdot\log p)$$
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ computation\ \ \ \ \ communication
      \end{itemize}
            
\bigskip

{\it Mesh:}

       \begin{itemize}
       \item{} Computing factor inside the processors are the same.
       \item{} Single node accumulation + broadcast: $$\Theta (\sqrt p)$$
       \item{} Parallel running time:
       $$\Theta (n\cdot {n\over p}) +\Theta (n\cdot\sqrt p)$$
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ computation\ \ \ \ \ communication
       \end{itemize}

\newpage\addcontentsline{toc}{section}{All Pairs Shortest Path}
\section*{All Pairs Shortest Path}

We want to compute the minimum path to each pair of vertices. 
The results is the $D$ matrix which contains the weights.

\item{\bf Dijkstra}

We execute the single source shortest path for every $v\in V$ vertices.

The single sequential complexity: $$\Theta (n^2)$$

The all pairs shortest path complexity: $$\Theta (n^3)$$

\item{\bf Parallel formulation}

We execute the single source s.p. sequentally for every
vertex on a separate processor.

We use $n$ processor, the parallel time: $$\Theta (n^2)$$

There is no communication between the processors, no overhead, 
the efficiency is $1$.

\bigskip

We execute every single source shortest path on a set of processors. 
In this manner we can use up to $n^2$ processors.

\newpage
\item{\bf Mesh architecture}

We have $p$ processor.
\bigskip

%\centerline{\psfig{figure=./figs/gr9.ps}}
%\begin{figure}
%\centerline{\epsfysize=9cm\epsffile{abra.eps}}
%\caption{Development Cycle in GRADE}
%\label{abra-babra}
%\end{figure}

\vskip -13mm

A specific single source shortest path is executed by 
$$\sqrt {p\over n} \times \sqrt {p\over n} = {p\over n}$$ processors.

No communication between the processor blocks.

Parallel running time:
$$
\Theta (n\cdot {n\over {p\over n}}) + \Theta (n\cdot \sqrt {p\over n})  =
 \Theta ({n^3\over p}) + \Theta (\sqrt {n\cdot p})
$$

\item{\bf Compairing the two parallel formulation}

  \begin{itemize}
  \item{A)} $n$ Processor $\Theta (n^2)$ time
  \item {B)} $p = n^{1.66}$ processor $\Theta (n^{1.33})$ time.
  Better scalability.
  \end{itemize}

\end{itemize}

\newpage\addcontentsline{toc}{section}{Matrix Algorithm}
\section*{Matrix Algorithm}

\begin{itemize}
\item{\bf The only assumption:} no neagtive weight cycles.
\item{\bf The basic idea:}
Let $p^{(k)}_{i,j}$ the minimum weight path
from $v_i$ to $v_j$ which has at most $k$ edges and its weight $d^{(k)}_{i,j}$.
\bigskip

%\centerline{\psfig{figure=./figs/gr10.ps}}
%\begin{figure}
%\centerline{\epsfysize=9cm\epsffile{abra.eps}}
%\caption{Development Cycle in GRADE}
%\label{abra-babra}
%\end{figure}
\vskip -10mm

If $v_m$ on the  $p^{(k)}_{i,j}$ path we can decompose it into two subpath: 
$p^{(k-1)}_{i,m} + p^{(1)}_{m,j}$

Then
$$
d^{(k)}_{i,j} = 
  min_m \lbrace d^{(k-1)}_{i,j}, min_m \lbrace d^{(k-1)}_{i,m} + w(m, j)\rbrace \rbrace
$$
or simply
$$
d^{(k)}_{i,j} =  min_m \lbrace d^{(k-1)}_{i,m} + w(m, j)\rbrace
$$
\item{\bf Start:} $ D^{(1)} = \lbrace d^{1}_{i,j} \rbrace = \lbrace a_{i,j}\rbrace = A$

\item{\bf Aim:} $ D^{(n-1)}$ because the shortest path cannot be longer than $(n-1)$.

\item{\bf Computation}
Operations: 

multiplication $\Longrightarrow$ addition

addition $\Longrightarrow$ minimum($\cdot$) function
\bigskip

%\centerline{\psfig{figure=./figs/gr11.ps}}
%\begin{figure}
%\centerline{\epsfysize=9cm\epsffile{abra.eps}}
%\caption{Development Cycle in GRADE}
%\label{abra-babra}
%\end{figure}
\vskip -18mm
$$
d^{(k)}_{i,j} =  min_m \lbrace d^{(k-1)}_{i,m} + w(m, j)\rbrace
$$

We do not compute  $D^{(1)}, D^{(2)}, D^{(3)}, ...  D^{(n-1)}$ but
$D^{(1)}, D^{(2)}, D^{(4)}, ...  D^{(n-1)}$ by multiplying the matrices
by itself.
We need $\lceil log (n-1)\rceil$ matrix multiplication.

\item{\bf Complexity}

Sequential complexity of matrix multiplication: $\Theta (n^3)$

Sequential complexity of this algorithm: $\Theta (n^3\cdot log n)$

(Recall Dijkstra has only  $\Theta (n^3)$ !)

Using a DNS matrix multiplication algorithm on $n^3$ processor, the 
parallel runtime: $\Theta (log^2 n)$

\end{itemize}

\newpage\addcontentsline{toc}{section}{Floyd Algorithm}
\section*{Floyd Algorithm}

Not the fastest, but $\Theta (n)$ time with $\Theta (n^2)$ processor,
shows useful mapping techniques.

\begin{itemize}
\item {\bf Basic idea:} restrict the attention into a $V_k \subseteq V$ 
subset, and extend it into $V$.
\bigskip

%\centerline{\psfig{figure=./figs/gr12.ps}}
%\begin{figure}
%\centerline{\epsfysize=9cm\epsffile{abra.eps}}
%\caption{Development Cycle in GRADE}
%\label{abra-babra}
%\end{figure}
\vskip -8mm

$p^{(k)}_{i,j}$ denotes the minimum weight path from $v_i$ to $v_j$ where the internal point are in $V_k$.

\item{\bf Start:} $V_1 = \lbrace v_1 \rbrace $

\item{\bf Step:} $V_k = V_{k-1} \cup \lbrace v_k \rbrace $

We have to recompute the path's weights $d^{(k)}_{i,j}$

   \begin{itemize}
   \item{} if $p^{(k)}_{i,j} \not\owns v_k$ then $d^{(k)}_{i,j} = d^{(k-1)}_{i,j}$
   \item{} if $p^{(k)}_{i,j} \owns v_k$ then split into two paths  $p^{(k-1)}_{i,k}$
            $p^{(k-1)}_{k,j}$ (They are in $V_k$ !)
     
$$  d^{(k)}_{i,j} = d^{(k-1)}_{i,k} + d^{(k-1)}_{k,j} $$
   \end{itemize}

\item{\bf Recurrence relation}
$$ 
   d^{(k)}_{i,j}= \cases{ w(i,j) \;{\rm if }\; k = 0\cr
                          min \lbrace  d^{(k-1)}_{i,j}, 
                                       d^{(k-1)}_{i,k} + d^{(k-1)}_{k,j}\rbrace 
                          \quad k \geq 1\cr }
$$
\item{\bf Aim:} $D^{(n-1)}$ matrix.

\item{\bf The algorithm:}
$$
LOOP_{k=1,...n} \Bigg\lbrack LOOP_{i=1,...n} \bigg\lbrack LOOP_{j=1,...n} \Big\lbrack
 d^{(k)}_{i,j}= min \lbrace\cdot\rbrace \Big\rbrack  \bigg\rbrack  \Bigg\rbrack
$$
     
\item{Sequential time:} $\Theta (n^3)$

\item {\bf Parallel Formulation:}
Block checkerboard mapping, one processor maintain ${n\over \sqrt p} \times {n\over \sqrt p}$
submatrix.
\bigskip

%\centerline{\psfig{figure=./figs/gr13.ps}}
%\begin{figure}
%\centerline{\epsfysize=9cm\epsffile{abra.eps}}
%\caption{Development Cycle in GRADE}
%\label{abra-babra}
%\end{figure}
\vskip -8mm

(This is only logical mapping!)

\item{\bf How it works}

The $k$-th step every processor computes 

$$  d^{(k)}_{i,j} = min \lbrace d^{(k-1)}_{i,j}, d^{(k-1)}_{i,k} + d^{(k-1)}_{k,j} $$

\hbox {\hskip 1.2in it is here | in the same row | in the same column}

Before executing the $k$-th step the processor maintaining the 
fragment of the $k$-th row or column sends the value to the neighbours.

\item{\bf Computing steps:}
    \begin{itemize}
    \item{} broadcasts $k$ row and column
    \item{} wait till every process has it
    \item{} compute  $d^{(k)}_{i,j}$
    \end{itemize}

\item{\bf Hypercube architecture}
Parallel runtime:
$$
\Theta (n\cdot {n^2\over p}) + \Theta (n\cdot {n\over\sqrt p}\cdot log p)
$$

\item{\bf Bottleneck:} Synchronisation !
The algorithm remains correct if we drop the synchronisation:
every processor computes immediately when it gets the $ d^{(k)}_{i,j}$
values and then sends to its neighbours.

Pipelined block checkerboarding.

The last processor finishes:
   \begin{itemize}
   \item{} it gets the first value after ${n\over\sqrt p}\cdot\sqrt p = \Theta (n) $ time.
   \item{} then it computes $\Theta ({n^3\over p})$
   \end{itemize}

The parallel runtime:
$$
\Theta ({n^3\over p})  + \Theta (n)
$$

If we use $p = n^2$ processors : 

$$
 \Theta (n)
$$

\end{itemize}

\end{document}






























\section {Sorting Generals}

In computer programs sorting is one of the most frequently used
algorithms. Sorted data are easier to maintain and reduces the
computation need in many cases. The best examples are the database
applications, where the so called 'indexes' are applicated to
keep the sorted order of the database records.
It is a very famous topic in algorithm theory because its formulation is
very simple and it still leads to deep results. Many techniques, algorithms,
theoretical results were devised in the last few decades. In the
parallel algorithm's point of view sorting is one of the best problems
for understanding how the data and work should be divided among processing
units to get optimum performance.

{\bf Definition}

Generally, the problem is to arrange an unordered collection of elements in 
order to get a monotonically increasing/decreasing collection.
To be more formal, let 
$$S=(a_1,a_2,a_3,\ .\ .\ .,a_n)$$    %eqal
be a sequence of n elements in arbitrary order. The sorting operation
transforms $S$ into a monotonically increasing sequence

$$S'=(a'_1, a'_2, a'_3,\ .\ .\ .,a'_n)$$
where $ a'_i\leq a'_j\;,  1\leq i\leq j\leq n$ and $S'$ is a
permutation of $S$.

We can categorize the sorting based upon several attributes:

\begin{itemize}

\item{\bf internal/external}
This attribute reflects to the size of data compared to the applicable
memory size.
When the data is small enough to fit into the memory then we use 
an {\sl internal} sorting, otherwise some external devices (e.g. hard disk) must be
used to maintain the data. In this case the {\sl external} sorting
algorithm has to maintain reading/writing of the external devices
which causes extra algorithmic problems. For the case of simplicity
we focus our attention to the internal sorting algorithms.

\item{\bf comparison-based/non comparison-based}
The {\sl comparison-based} algorithm selects {\bf two} elements
and calls a comparison operation. When they are in the wrong order
it exchanges them. The algorithm repeats this operation until
the sequence is completely sorted.
In contrast the {\sl non comparison-based} algorithm selects only {\bf one} 
element and based on the elements properties (such as binary representation)
puts it into the right place in the sorted sequence.

\end{itemize}

The computation complexity is different because of the extra
sorting information what non comparison-based algorithms use:

{\sl Computational complexity}
     \begin{itemize}
     \item{}  comparison based: $O (n \cdot \log n)$
     \item{}  non comparison based:  $O (n)$
     \end{itemize}


The first type is more general while the latter is applicable only
when the sorted elements has some special properties. We treat only
the comparison based algorithms here.

Concerning the input of the sorting there are two possibilities:
either the input sequence is stored in a single processor's memory or 
the elements of the sequence is distributed among the processors.

In most of the cases the input of the sorting algorithm, 
(i.e. the sequence of the elements to be sorted)
are distributed over the processors. The reason is that 
the sorting frequently appears inside a more complex parallel
algorithm and the elements are created by different processors.
The same happens after the sorting: the output, the sorted sequence is
the input of another parallel algorithm, which also has to handle
a distributed sequence.

The simplest case is if we have only one element per processor,
but generally the sorting has to maintain much more element
than the number of processors. In this case we store more 
elements per processor.

The output will be a sorted sequence which is also distributed
among the processors. Practically,  we arrange the processors,
and each processor stores the elements in sorted order. 
The sorted sequence will contain first the elements of the processor
$P_1$ ${a_1, a_2, ...}$ then the elements of the processor $P_2$ 
and so on.

To enumerate the processor we can use any of the known algorithms,
but the enumeration can have an effect on the performance of the
algorithm. For example, in the case of ring architecture an
enumeration which follows the links yields a better performance.

The key step in the sorting is the
comparison of elements. If the elements appear on the same processor
the operation simply compares and exchanges them if needed.
If the elements stored on different processors they have to communicate.

\subsection {\bf Compare and exchange operation}

Let we suppose that $i \le j$, $a_i$ element is stored by the $P_i$ processor and
the $a_j$ element stored by the $P_j$ processor. (See Fig.\ref{1}.)
In he first step both processor sends its elements to the other
processor. In the second step both processor compares it's own and the
foreign element and the former stores the minimal, the
latter stores the maximal element. 

\begin{figure}[ht]
\centerline{\epsffile{./figs/book/t2.eps}}
\caption{}
\label{1}
\end{figure}


\subsection {\bf Performance considerations}

Let we denote the time elapsed for message startup by $t_s$
the per word transfer time by $t_w$ and the time for comparison by
$t_c$. 

If we have only one element per processor then every
comparison operation between the neighboring processors
requires $(t_s+t_w)$ time for communication and $t_c$
for comparison. In the practice the $t_s$ time is much larger than
the $t_w$ or $t_c$. The time elapsed by the sorting can be estimated
by the number of comparisons times $t_s$. We can conclude now that 
the one element per processor scheme leads to a very inefficient
usage of the multiprocessor architecture while most of the time is
spent to the interprocess communication.

If we have more elements per processor we use the modified version
of the compare and exchange operation. (See Fig.\ref{2}.)

\subsection {\bf Compare and exchange operation: More elements per processor}

\begin{figure}[ht]
\centerline{\epsffile{./figs/book/t3.eps}}
\caption{}
\label{2}
\end{figure}

Let we denote the number of processors by $p$
and the set of elements stored on $P_i$ by $A_i = \{a_{i1},a_{i2}, ...\}$.
We denote $A_i\leq A_j$ if every element in $A_i$ is smaller than 
every element in $A_j$.

We have a properly sorted set of all elements when 
$A'_1\leq A'_2\leq \ . \ . \ . \leq A'_p$ and $A'_i$ is sorted.
The elements having the same processor can be easily sorted by one of
the sequential sorting algorithms but to sort all of them we have to
have a so called {\sl compare and split} step described as follows.
(See Fig.\ref{3}.)
In the first step each processor sends its set ($A_i$, $A_j$) to the
other processor. In the second step the processors perform merging of the sets.
The resultant sets, $B_{j,i}$ and $B_{j,i}$ are sorted while the
original sets were sorted. In the third step the processors take the 
lower or the upper half of the merged sets respectively. It is easy to
see that for the new sets $A'_i \leq A'_j$. 

\begin{figure}[ht]
\centerline{\epsffile{./figs/book/t4.eps}}
\caption{}
\label{3}
\end{figure}

%---------------------------------------------------------------------------------------

\newpage\addcontentsline{toc}{section}{Sorting Networks}
\section {Sorting Networks}

As the first possibility to make sorting parallel we describe the
sorting networks. Using a large number of {\sl comparators} the
sorting time is significantly smaller than $O(n \log n)$. These sorting networks are based
on a comparison network model, in which many comparison operations are performed
simultaneously.

\begin{figure}[ht]
\centerline{\epsffile{./figs/book/t5.eps}}
\caption{}
\label{4}
\end{figure}

A comparator (see Fig.\ref{4}) is a device with two 
inputs $x$ and $y$ and two outputs $x'$ and $y'$. 

There are two types of it: 

\begin{itemize}
\item {} increasing comparator, $x' = min(x, y)$  and $y' = max(x,y)$,
   we denote it by  $\oplus$;
\item {} decreasing comparator $x' = max(x, y)$ and $y' = min(x, y)$,
   we denote it by  $\ominus$;
\end{itemize}

As the two elements enter the input wires of the comparator, they are
compared and if necessary exchanged before they go to the output
wires.
The comparators arrange in several columns, see Fig.\ref{5}.
The comparators having the same columns executed at the same time and
-- by the help of the connections between the columns -- fill the
comparator's input of the next column. Finally, the last column is
filled with the elements which are properly sorted.
The time elapsed by the sorting is proportional of the number of the
columns which is called {\sl depth}. In the next chapter we will see
how the interconnections between the columns are arranged. The
Fig.\ref{5} shows a typical sorting network. 

\begin{figure}[ht]
\centerline{\epsffile{./figs/book/t6.eps}}
\caption{}
\label{5}
\end{figure}

%-----------------------------------------------------------------------------

\newpage\addcontentsline{toc}{section}{Bitonic Sort}
\section {Bitonic Sort}

The bitonic sort is one application of the sorting network.
The name is coming from the {\sl bitonic sequence} which is the key
element of the algorithm.

A bitonic sequence is a sequence of elements
$(a_0, a_1, a_2, \ . \ . \ . , a_{n-1})$ 
with the property that either exists an $1\leq i\leq n-1$ index:

$(a_0, a_1, a_2, \ . \ . \ . ,a_i, a_{i+1}, \ .\ .\ . , a_{n-1})$

$\;\;\;\leq\;\leq\;\leq \ . \ . \ .\leq \Uparrow \geq \; \geq \ .\ .\ . \geq$

such that $(a_0, a_1, a_2, \ . \ . \ . ,a_i)$ is monotonically
increasing and $(a_{i+1}, \ .\ .\ . , a_{n-1})$ monotonically decreasing;
or, exists a circular shift

$(a_k, a_{k+1}, a_{k+2}, \ . \ . \ . ,a_0, a_{1}, \ .\ .\ . , a_{k-1})$

such that the resulting array satisfies the previous condition.

The definition of the {\sl bitonic} property proved to be very useful
for sorting networks. If we have one bitonic sequence then by the help
of the {\sl bitonic split} operation (described below) we can get two
new bitonic sequences where all of the elements belonging to the first
sequence are greater then the elements of the second
sequence. Recursively applying the bitonic split operation to the new
bitonic sequences we get smaller and smaller sequences and finally we
have a bitonic sequences each containing only one element. At this
point we have a properly sorted sequence. (See Fig.\ref {7}.)
Lets now investigate how the bitonic split works.

\begin{figure}[ht]
\centerline{\epsfysize=2.0in\epsffile{./figs/book/t8.eps}}
\caption{}
\label{7}
\end{figure}

\subsection {Bitonic split}

For the sake of the simplicity let we assume $n=2^k$ and the bitonic index $=n/2$.

Let be starting bitonic sequence
$S = (a_0, a_1,\ .\ .\ . , a_{n-1})$,
and define the new $S_1$ and $S_2$ sequences as below:
\medskip

$S_1 = (\min (a_0, a_{n\over 2},
 \min (a_1, a_{{n/2}+1}),\ .\ .\ . \min (a_{{n/2}-1}, a_{n-1})$

and
\medskip

$S_2 = (\max (a_0, a_{n/2}), \max (a_1, a_{{n/2}+1}),\ .\ .\ .
  \max (a_{{n/2}-1}, a_{n-1})$


\begin{figure}[ht]
\centerline{\epsfysize=2.1in\epsffile{./figs/book/t7.eps}}
\caption{}
\label{6}
\end{figure}

The $S_1$ and $S_2$ are bitonic sequences and $$S_1\leq S_2.$$
It is easy to understand how it works by the help of the Fig.\ref{6}.
Let we break the sequence at the bitonic index and shift it to the
right. Then if we take the minimum or the maximum of
the paired elements, we get the lower half bitonic sequence (marked
with dashed line) or the upper half bitonic sequence respectively.
Now it is trivial that both are bitonic and $S_1\leq S_2$.

\subsection {Bitonic merge}

Since after each bitonic split operation
the size of the problem is divided by 2, 
the number of splits required to rearrange the bitonic
sequence into a sorted sequence is $\log n$. (See Fig.\ref {7}.)
The procedure of sorting a bitonic sequence using
bitonic splits is called {\sl bitonic merge}. 
We now have a method for merging a bitonic sequence into a sorted sequence. This
method is easy to implement on a network of comparators. This network of comparators,
known as a bitonic merging network, it is illustrated in Fig.\ref{9}.
The network contains $\log n$ columns. 

\begin{figure}[ht]
\centerline{\epsfysize=2.9in\epsffile{./figs/book/k1.eps}}
\caption{}
\label{9}
\end{figure}

Each column contains $n/2$ comparators and performs one step of the bitonic
merge. This network takes as input the bitonic sequence and outputs the sequence in sorted
order. We denote a bitonic merging network with $n$ inputs by $\oplus$BM[n]. If we replace the
comparators in Fig.\ref{9} with $\ominus$ comparators, the input will be sorted in monotonically
decreasing order. Such a network is denoted by $\ominus BM(n)$.

\bigskip

\hbox 
{
\hskip 0.4in 
\vbox to .7in{
       \hbox {Increasing : $\oplus BM (n)$}
       \hbox {Decreasing : $\ominus BM (n)$}
       \vfill
       \null 
      }
\hskip 0.4in 
\vbox { \hbox {\epsffile{./figs/book/t9.eps}}}
}

Let we take a closer look how it works. Trivially, a sequence of two
elements forms a bitonic sequence.
Hence, any unsorted sequence of elements is a concatenation of bitonic sequences of size
two. Each stage of the network shown in Fig.\ref {10} merges adjacent bitonic sequences
in increasing and decreasing order. According to the definition of a bitonic sequence, the
sequence obtained by concatenating the increasing and decreasing sequences is bitonic.
Hence, the output of each stage in the network in Fig.\ref {10} is a concatenation of bitonic
sequences that are twice as long as those at the input. By merging larger and larger bitonic
sequences, we eventually obtain a bitonic sequence of size n. Merging this sequence sorts
the input. We refer to the algorithm embodied in this method as {\sl bitonic sort} 
and the network as a {\sl bitonic sorting network}. 

\begin{figure}[ht]
\centerline{\epsffile{./figs/book/t10.eps}}
\caption{}
\label{10}
\end{figure}

\subsection {Complexity}

The last stage of an $n$-element bitonic sorting network contains a bitonic merging
network with n inputs. This has a depth of $\log n$. The other stages perform a complete
sort of $n/2$ elements. Hence, the depth, $d(n)$, of the network in Fig.\ref{10} is given by the
following recurrence relation:

$d(n) = d({n\over 2})+\log (n)$

Solving the equation, we obtain 

$d(n) = \Sigma_{i=1}^{\log (n)} i= (\log ^2(n)+\log (n))=O (\log ^2(n))$

So the time complexity of the bitonic network sort is 
              $$O (\log ^2(n)).$$ 

In the next two sections we give two examples how to use the bitonic
sorting algorithm on some of the standard  multiprocessor
architectures.
We show how to use the hypercube and mesh architecture to establish a
bitonic sorting network. Performance considerations will discuss the
one element per processor case.

%-------------------------------------------------------------------------------------

\newpage\addcontentsline{toc}{section}{Bitonic Sort on Hypercube}
\section{Bitonic Sort on Hypercube}

As we have shown in the Fundamentals chapter the d-dimensional hypercube architecture
contains $2^d$ processors. The processors are labeled by the
d-dimensional coordinate system's binary vector which we can consider
as a d-digit binary number. Every processor is
connected by those processors which has a label differing only in one
bit.

\begin{figure}[ht]
\centerline{\epsffile{./figs/book/t11.eps}}
\caption{}
\label{11}
\end{figure}

\subsection{Mapping}

To explain how it is working it is enough to show how we
represent the bitonic merging  network $\oplus BM[]$ on the hypercube.
In the Fig.\ref{9} we depicted the binary addresses of the
processors. It can be seen that every compare and exchange operation
consists of two processors which labels differ on only one bit.
This is the best mapping, while all the compare and exchange
operation appears between neighbors.

\subsection{Executing}
The compare and exchange operations take place along each dimension.
In the $i$th step those processors communicate which have indexes
differing only in the $i$th coordinate.                      
On the Fig.\ref{11} different line types show the steps of the operation.
After the last step, we have a sorted sequence stored in the processors.
The processor having the smallest label has the smallest element if we
used $\oplus$ comparators.
 
\subsection {Complexity}

During each step of the algorithm, every processor performs a compare-exchange
operation. The algorithm performs a total of $(1 + \log n)(\log n)/2$ such steps; thus, the
parallel run time is

$$O(\log ^2 (n))$$

This parallel formulation of bitonic sort is cost optimal with respect to the sequential
implementation of bitonic sort (that is, the processor-time product is
$O(n \log ^2 (n))$, but it is
not cost-optimal with respect to an optimal comparison-based sorting algorithm, which has
a serial time complexity of $O(n \log n)$.


\newpage\addcontentsline{toc}{section}{Bitonic Sort on Mesh}
\section{Bitonic Sort on Mesh}

Consider how the input wires of the bitonic sorting network can be mapped
efficiently onto an n-processor mesh. Unfortunately, the connectivity of a mesh is lower
than that of a hypercube, so it is impossible to map wires to processors such that each
compare-exchange operation occurs only between neighboring processors. Instead, we map
wires such that the most frequent compare-exchange operations occur between neighboring
processors.

\begin{figure}[ht]
\centerline{\epsffile{./figs/book/t12.eps}}
\caption{}
\label{12}
\end{figure}

\subsection{Mapping}

There are several ways to map the input wires onto the mesh processors. Some
of these are illustrated in Fig.\ref{12}. Each processor in this figure is labeled by the
wire that is mapped onto it. Of these mappings, we concentrate on the row-major
shuffled mapping, shown as second.
The advantage of row-major shuffled mapping is that processors that perform
compare-exchange operations reside on square subsections of the mesh whose size is
inversely related to the frequency of compare-exchanges. For example, processors that
perform compare-exchange during every stage of bitonic sort (that is, those corresponding
to wires that differ in the least-significant bit) are neighbors. In general, wires that differ
in the $i^{th}$ least-significant bit are mapped onto mesh processors
that are $2^{\lfloor (i-1)/2\rfloor}$ communication links away.

\subsection{Complexity}

During the $(1 + \log n)(\log n)/2$ steps of the algorithm, processors
that are a certain
distance apart compare-exchange their elements. The distance between processors
determines the communication overhead of the parallel formulation. The total amount of
communication performed by each processor is
$\sum_{i=1}^{\log n}\sum_{j=1}^{i}2^{\lfloor (j-1)/2\rfloor} \approx 7 \sqrt{n}$
which is $O(\sqrt{n})$.
During each step of the algorithm, each processor performs at most
one comparison; thus, the total computation performed by each
processor is $O(\log ^2 n)$.

The parallel run time is:

\ \ \ \ \ Time: $O(\log ^2 (n))+O(\sqrt n)$

\ \ \ \ \ \ \ \ \ \ \ \ comparison \ \ communication

%----------------------------------------------------------------------

\newpage\addcontentsline{toc}{section}{Bubble Sort and its Variants}
\section{Bubble Sort and its Variants}

\subsection{ Bubble sort}

Among the sorting heuristic algorithms the bubble sort is one of the
simplest. Its easy to understand, to implement although it is not
optimal.

\begin{figure}[ht]
\centerline{\epsffile{./figs/book/t13.eps}}
\caption{}
\label{13}
\end{figure}

The sequential bubble sort algorithm compares and exchanges adjacent elements in
the sequence to be sorted. Given a sequence $(a_1, a_2, \dots, a_n)$, 
the algorithm first performs $n-1$ compare-exchange operations in 
the following order: $(a_1, a_2)$, $(a_2, a_3)$, $\dots$, $(a_{n-1}, a_n)$.
(See Fig.\ref{13}.)
This step moves the largest element to the end of the sequence. The last element in the
transformed sequence is then ignored, and the sequence of compare-exchanges is applied
to the resulting sequence $(a'_1, a'_2,\dots, a'_{n-1})$. 
The sequence is sorted after $n-1$ iterations.

We have to perform $O(n)$ comparisons for each element, so multiplied
by $O(n)$, the number of the elements, we get that the complexity of the
bubble sort is $O(n^2)$. A closer look reveals that the bubble sort has
a real sequential nature which makes its parallelization hard. However
some of its variants can be easily parallelized as we show in the
next sections.

\subsection{Odd-Even Transposition}

The odd-even transposition algorithm sorts $n$ elements in $n$ phases ($n$ is even), each of
which requires $n/2$ compare-exchange operations. This algorithm alternates between two
phases, called the odd and even phases. 
Let  $(a_1, a_2, \dots, a_n)$ be the sequence to be sorted. 
(See Fig.\ref{14}.)

\begin{figure}[ht]
\centerline{\epsfysize=2in\epsffile{./figs/book/t14.eps}}
\caption{}
\label{14}
\end{figure}

During the odd phase, elements with odd indices are compared with their right neighbors,
and if they are out of sequence they are exchanged.
Formally, in the first step the  pairs 
$(a_1, a_2)$, $(a_3, a_4)$, $\dots$, $(a_{n-1}, a_n)$
are compare-exchanged (assuming $n$ is even). 
Similarly, during the even phase,
elements with even indices are compared with their right neighbors, and if they are out
of sequence they are exchanged:
$(a_2, a_3)$, $(a_4, a_5)$, $\dots$, $(a_{n-2}, a_{n-1})$

After $n$ phases of odd-even exchanges, the sequence is sorted. Each
phase of the algorithm (either odd or even) requires $O(n)$ comparisons, and there are a total
of $n$ phases, the sequential complexity is $O(n^2)$.

\subsection {Parallelizing the algorithm}

As the algorithm naturally shows, in each phase of the algorithm
compare-exchange operations on pairs of elements can be performed
simultaneously.
Let we consider again the one-element-per-processor case on a ring interconnection
network. During the odd phase, each processor that has an odd label 
compare-exchanges its element with the element residing on its right neighbor.
Similarly, during the even phase, each processor with an even label 
compare-exchanges its element with the element of its right neighbor.

During each phase of the algorithm, the odd or even processors perform
a compare-exchange step with their right neighbors, this requires constant time. 
A total of $n$ such phases are performed, so the parallel run time is $O(n)$. 

Since the sequential complexity of the best sorting algorithm for $n$ elements is
$O(n \log n)$, this formulation is not cost-optimal, because its
processor-time product is $O(n^2)$.
We can optimize the cost function if we use use fewer, $p<n$ processors
for sorting $n$ elements and on each processor we apply an optimal
sequential sort algorithm having complexity $O(n \log n)$. 
In this case the complexities are:
\smallskip

\centerline { time: $O \big ( {n\over p}\cdot\log {n\over p}\big )+ O (n)+ O (n)$}
\centerline{\ \ \ \ \ \ \ \ \ \ \ local sort \ \ \ \ comp. \ \ communic.}

%----------------------------------------------------------------------------------
    
\newpage\addcontentsline{toc}{section}{Quicksort ($\pm $ best!)}
\section*{Quicksort ($\pm $ the best!)}

Quicksort is the most popular algorithm for sequential computers
because it is simple, it has low overhead, and it reaches the optimal average complexity.
Quicksort is a divide-and-conquer algorithm that sorts a sequence by recursively
dividing it into smaller subsequences. There are close relations
between the bitonic split operation and the quicksort's divide
operation as we will see in the next sections.

\subsection{ Algorithm}

Let we have the n-element sequence to be sorted is $A[1,\dots, n] =
{a_1, \dots, a_n}$. 
Quicksort algorithm consists of two steps: divide and conquer.

During the divide step, a sequence $A[q. . . r]$ is partitioned into two nonempty
subsequences $A [q. . . s]$ and $A[s + 1. . . r]$ such that each
element of the first subsequence is smaller than or equal to each 
element of the second subsequence. During the conquer step,
the subsequences are sorted by recursively applying quicksort. 
Since the subsequences $A[q. . . s]$ and $A[s + 1. . . r]$ are sorted
and the first subsequence has smaller elements than
the second, the entire sequence is sorted. (See Fig.\ref{quicks1}.)

\begin{figure}[ht]
\centerline{\epsfysize=2.7in\epsffile{./figs/book/k4.eps}}
\caption{}
\label{quicks1}
\end{figure}

We can perform the divide step in many different ways. Most often a
{\sl pivot} element is chosen and the all elements of the sequence is
compared by this pivot. The smaller elements will form the  $A [q. . . s]$
subsequence while the greater elements will form the  $A[s + 1. . . r]$.

The most interesting question for optimizing quicksort is how we can
select the pivot element. 
The simplest way is to select one (e.g. the first in the array) from
$A[q. . . r]$  and using this element to partition the sequence.

The complexity of partitioning a sequence of size $k$ is $O (k)$ while
$k$ comparison is performed. 
However, quicksort's performance
is greatly affected by the way it partitions a sequence. 
Consider the case in which a sequence of size $k$ is split poorly, 
into two subsequences of sizes 1 and $k - 1$. The run time in this case is
given by the recurrence relation $T(n) = T(n-1) + O(n)$, whose solution is $T(n) = O(n^2)$.
In the case in which the sequence is split well, into two roughly
equal size subsequences of $\lfloor k/2 \rfloor$ and $\lceil k/2\rceil$
elements. In this case, the run time is given by the
recurrence relation $T(n) = 2T(n/2) + O(n)$, whose solution is 
$T(n) = O(n \log n)$. The
second split yields an optimal algorithm. Although quicksort can have $O(n^2)$ worst-case
complexity, its average complexity is significantly better; the
average number of compare-exchange 
operations needed by quicksort for sorting a randomly-ordered input sequence is
$1.4n \log n$, which is asymptotically optimal.

\subsection{Parallelization I. (novice attempt)}

There are several way to parallelize the quicksort
algorithm. There are parallel algorithms which use $O(\log n)$ processors
and the elapsed time is $O(n)$ and -- this is our aim -- there are
algorithms which use $O(n)$ processor meanwhile the time is much
shorter, only $O(\log n)$.

First we discuss a simple, novice parallelization method which leads us
to a bad time complexity but we can learn a lot from this attempt.

Trivially, it comes the idea to use the recursion nature of the quicksort
to make it parallel. (See Fig.\ref{16}.)

\begin{figure}[ht]
\centerline{\epsfysize=2.7in\epsffile{./figs/book/t16.eps}}
\caption{}
\label{16}
\end{figure}

At the beginning a single processor, $P_1$ partitions the 
${a_1, \dots, a_n}$ set into two subsets 
${a'_1,\dots,a'_k}$ and ${a''_1, \dots, a''_s}$.

Then it sends the ${a'_1,\dots,a'_k}$ set to $P_2$ and the
${a''_1, \dots, a''_s}$ to processor $P_3$.

The processors separates the subsets as before and sends to others
according to the recursive process. Finally, the processors contains
single elements which is of course sorted. 

The bottleneck of the method is obvious: the first partition takes
place on a single processor, and it has to make $O(n)$ comparisons, so
the time complexity is at least $O(n)$.

In order to improve it we have to parallelize the very first
separation also. Because the deep of the algorithm -- i.e the number of
the subsequent recursive steps -- is $O(\log n)$ we have to perform the
partition step in $O(1)$ time to achieve the $O(\log n)$ time
complexity.

However, this is difficult for
most parallel computing models. The only known algorithms are for the abstract PRAM
models. Because of communication overhead, the partitioning step takes more than O(1)
time on mesh-connected and hypercube-connected parallel computers. In the following
sections we present two distinct parallel formulations: one for a CRCW PRAM, one for
a hypercube. Each of these formulations parallelizes quicksort by
performing the partitioning step in parallel.

\subsection {Parallelization II: CRCW PRAM}

As we have explained in the Foundation chapter, an arbitrary CRCW
PRAM is a concurrent-read, concurrent-write parallel random-access machine in which
write conflicts are resolved arbitrarily. In other words, when more than one processor tries
to write to the same memory location, only one arbitrarily chosen processor is allowed to
write, and the remaining writes are ignored.

\begin{figure}[ht]
\centerline{\epsffile{./figs/book/t18.eps}}
\caption{}
\label{17}
\end{figure}

In this attempt we use the one element per processor approach, and
assume that the elements are loaded in the $n$ processor.

Executing quicksort can be visualized as constructing a binary tree. In this tree, the
pivot is the root, elements smaller than or equal to the pivot go to the left subtree, and
elements larger than the pivot go to the right subtree. (See Fig.\ref{17}.)

The algorithm starts by selecting a pivot element and partitioning the array into two
parts: one with elements smaller than the pivot and the other with elements larger than the
pivot. 

Subsequent pivot elements, one for each new subarray, are then selected in parallel.
This formulation does not rearrange elements, instead, since all the processors can read
the pivot in constant time, they know which of the two subarrays (smaller or larger) the
elements assigned to them belong to. Thus, they can proceed to the next iteration.

The algorithm that constructs the binary tree is as follows:

\begin {itemize}

\item{a.)} all try to write root, ($P_i$ wins)

\item{b.)} read the root (each reads the $a_i$ as the pivot)

\item{c.)} compare (the winner process, $P_i$ exits, the others
notes in which branch they belong to)

\end{itemize} 

The steps will continue recursively as the algorithm clearly shows, and
each processor (except the winner which gave the pivot element)
compete for writing the relevant branch new pivot element: 

\begin {itemize}

\item{a.)} all try to write left/right child of the tree ($P_j$ and
$P_k$ win)

\item{b.)} read the left/right child ($a_j$ or $a_k$ respectively)

\item{c.)} compare (the two successful, $P_j$ and $P_k$ exist)

\end{itemize}

In order to keep the track of the pivot element selection we set a
table which stores the history of the selections. (See Fig.\ref{18}.)

In this implementation -- to make more easy the the handling of
the selections -- we write the processor index into the table instead of
writing the element contained the processor. By setting up an array
$A[1, \dots, n]$ every processor can read the relevant pivot element
having the index of it.
The table contains the processor index, and the the indexes of 
those processors who won the selection on the left or right branch.

For example if the first pivot elements is coming from processor $P_i$
and the left/right branch's pivot element from $P_j$ or $P_k$
respectively then we write in the $i^{th}$ row of the table $j$ and
$k$.

Each processor maintain a local variable where it stores its current
parent processor index. In the example depicted on Fig.\ref{18} the
processors having smaller or equal elements than $a_i$ has the $P_j$
processor as parent meanwhile the other stores $P_k$ as its parent.

In a typical selection step each processor having parent $P_j$ reads $a_j$
from the array $A[1, \dots, n]$ and compares with its value. If the
value is smaller or equal, it tries to write its index into the table
where row is $j$ (its parent is $P_j$) and column is 'left child' (its
element is smaller than the pivot). If the element is greater then the
pivot it tries to write the 'right child' column.

When a process's elements becomes a pivot, it exits. When no process
left we have sorted the elements.

If we have the tree of sorted elements we can compute the sorted index
for each element in average $O(\log n)$ time.
To compute this first each processor sends to its parent the number
of its children $S_s$, i.e the number of how many processor are below its node.
The leaves of the tree sends 1 to their parents. All the other nodes
send the sum created by adding the left sum, the right sum plus 1 for
the processor itself, e.g. $ S_s = S_l + S_r + 1$ assuming that the two children of
$P_s$ are $P_l$ and $P_r$.

When we arrives to the root, we know the index of the first pivot
element which is the left sum + 1. In the example of Fig.\ref{18} the
index of $a_i$ is $S_j + 1$. Following the tree downwards we
recursively compute the index of the next pivot elements. The index of
$a_j$ is $S_m + 1$ (assuming that the left child of $P_j$ is $P_m$)
meanwhile the index of $a_k$ is $ S_i + S_t + 1 $ 
(assuming that the left child of $P_k$ is $P_t$), ...etc.

When we computed the index of every element in one step every
processor writes its element to the right place in the sorted array.

\begin{figure}[ht]
\centerline{\epsffile{./figs/book/t17.eps}}
\caption{}
\label{18}
\end{figure}

An example of the sorting tree is depicted on Fig.\ref{18} which sorts
the sequence $10, 8, 6, 15, 2, 11, 12, 13, 4, 9, 5, 7, 3, 1, 14$. 

The average depth of the tree is $O(\log n)$ the index--computing
take only $O(\log n)$ steps so the algorithm has the average time complexity 
$$ O(\log n).$$

The cost of quicksort on $n$ processor is $O (n\cdot\log n)$


\subsection {\bf Performance on the Hypercube}

The ideal case what the CRCW PRAM uses is that every processor
connected to every others not manageable in the practice whenever the
number of the process reasonable large. If we adopt the
parallelization of the quicksort algorithm described above to the
standard architectures like hypercube or mesh we got worse result due
to the communication overhead. For instance if we map to the hypercube
we get for the time complexity $O(\log^2 n)$ instead of $O(\log n)$.

If we use the many element per processor approach, sorting $n$
elements on $p$ processor the time complexity is: 

$$O \big ({n\over p}\log {n\over p}\big ) + 
                 O \big ( {n\over p}\cdot\log p\big ) + O (\log ^2 p)$$


\end{document}












