
%================= BEGIN FILE: latex8.tex  =====================

%
%  $Description: Author guidelines and sample document in LaTeX 2.09$ 
%
%  $Author: ienne $
%  $Date: 1995/09/15 15:20:59 $
%  $Revision: 1.4 $
%

\documentstyle[times,art10,twocolumn,latex8]{article}

\renewcommand{\baselinestretch}{0.9}  % 1.6 for kind of double spacing
                                      % 1.2 for normal

%%%%%%%%%%%%%%%%%%%%
%                  %
%    NEW COMMAND   %
%                  %
%%%%%%%%%%%%%%%%%%%%

\newenvironment{Code}
   { \begin{scriptsize} \begin{tabbing}    }{ \end{tabbing} \end{scriptsize} }
%   { \begin{tabbing}    }{ \end{tabbing}  }
%   { \begin{footnotesize} \begin{tabbing}    }{ \end{tabbing} \end{footnotesize} }
\newcommand{\ttl}{\footnotesize\it}  % title font
\newcommand{\Settab}
   {***\=***\=***\=***\=***\=***\=***\=***\=***\=***\=***\=***\= \kill}
\newcommand{\Line}{
   \noindent \mbox{}\hrulefill\mbox{} }
\newcommand{\LF}{\mbox{} \\}


\newenvironment{mytable}
   {\begin{table}
       \protect\begin{scriptsize}
          \begin{center} 
             %\begin{tabular}
   }
   {         %\end{tabular} 
          \end{center} 
       \protect\end{scriptsize} 
    \end{table}
   }

\newenvironment{my-table}
   { \protect\begin{footnotesize} 
     %\protect\begin{scriptsize} 
        \begin{center} 
           \begin{tabular}
   }
   {       \end{tabular} 
        \end{center} 
     %\protect\end{scriptsize} 
     \protect\end{footnotesize} 
   }


\newenvironment{Ventry}[1]%
   {\begin{list}{}{\renewcommand{\makelabel}[1]{\textsf{##1:}\hfil}%
      \settowidth{\labelwidth}{\textsf{#1:}}%
      \setlength{\leftmargin}{\labelwidth+\labelsep}}}%
   {\end{list}}


%%%%%%%%%%%%%%%
%             %
%  NEW  FONT  % 
%             %
%%%%%%%%%%%%%%%

%\newfont{\bi}{cmbxti10 scaled\magstep1}       % Bold Italics(12pt)
%\newfont{\bi}{cmbxti10 scaled\magstephalf} % Bold Italics(11pt)
\newfont{\bi}{cmbxti10} % Bold Italics(10pt) % Bold Italics(10pt)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%                   NEW COMMAND FOR ALGORITHMS
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\newenvironment{code}
   { \begin{scriptsize} \begin{tabbing} }{ \end{tabbing} \end{scriptsize} }

\newcommand{\1}{{\/\em [}}
\newcommand{\2}{{\/\em ]}}
\newcommand{\3}{{\/\em (}}
\newcommand{\4}{{\/\em )}}
\newcommand{\For}{{\bf for \/}}
\newcommand{\Endfor}{{\bf endfor \/}}
\newcommand{\To}{{\/ \bf to \/}}
\newcommand{\Downto}{{\/ \bf downto \/}}
\newcommand{\If}{{\bf if \/}}
\newcommand{\Endif}{{\bf endif \/}}
\newcommand{\Then}{{\bf then \/}}
\newcommand{\Else}{{\bf else \/}}
\newcommand{\Do}{{\/ \bf do \/}}
\newcommand{\Repeat}{{\bf repeat \/}}
\newcommand{\Until}{{\bf until \/}}
\newcommand{\While}{{\bf while \/}}
\newcommand{\Endwhile}{{\bf endwhile \/}}
\newcommand{\End}{{\bf end \/}}
\newcommand{\Begin}{{\bf begin \/}}
\newcommand{\Procedure}{{\bf procedure \/}}
\newcommand{\Function}{{\bf function \/}}
\newcommand{\HFunction}{{\bf handler--function \/}}
\newcommand{\Arrow}{$\leftarrow$ \/}
\newcommand{\Case}{{\bf case \/}}
\newcommand{\Of}{{\/ \bf of \/}}
\newcommand{\Call}{{\bf call \/}}
\newcommand{\Return}{{\bf return \/}}
\newcommand{\Not}{{\bf not \/}}
\newcommand{\Asynrec}{{\bf asynchronous receive \/}}
\newcommand{\Xor}{{\sf XOR \/}}
\newcommand{\Send}{{\bf send \/}}
\newcommand{\Receive}{{\bf receive \/}}

%********************************************************************************
%*
%*   TITLE and ABSTRACT
%*
%********************************************************************************

%------------------------------------------------------------------------- 
% take the % away on next line to produce the final camera-ready version 
\pagestyle{empty}

%------------------------------------------------------------------------- 
\begin{document}

\title{PACK/UNPACK on Coarse-Grained Distributed\\ 
                 Memory Parallel Machines}

\author{Seungjo Bae\\
2--120 Center for Science and Technology\\
School of Computer and Information Science\\
Syracuse University, Syracuse, NY 13244-4100\\
% For a paper whose authors are all at the same institution, 
% omit the following lines up until the closing ``}''.
% Additional authors and addresses can be added with ``\and'', 
% just like the second author.
\and
Sanjay Ranka\\
CSE Building, \#301 \\
Department of Computer Science \\
University of Florida, Gainesville, FL 32611 \\
}

\maketitle
\thispagestyle{empty}

\begin{abstract}
PACK/UNPACK are Fortran 90/HPF array construction functions 
which derive new arrays from  existing arrays. 
We present algorithms for performing these
operations on coarse-grained parallel machines.
Our algorithms are relatively architecture independent
and  can be applied to arrays of arbitrary dimensions
with arbitrary distribution along every dimension.
Experimental results are presented on the CM-5.
\end{abstract}

%********************************************************************************
%*
%*   Section : Introduction
%*
%********************************************************************************

\Section{Introduction}
PACK/UNPACK are Fortran 90/HPF array construction functions 
which derive new arrays from  existing arrays \cite{1,Koe+94}. 
PACK gathers  selected elements from an input array of any rank 
under the control of a logical mask array and constructs
the new vector.
UNPACK scatters all elements of an input vector
to the  array of any rank under the control of a mask array.

The parallel PACK/UNPACK algorithm
consists of two stages: %{\em ranking\/} and {\em redistribution\/}.
\begin{enumerate}
\item {\it Ranking\/}: Rank all elements of $A$ (or $M$ in UNPACK) 
      under the control of $M$.
\item {\it Redistribution\/}: 
   Redistribute all corresponding elements of $A$ (or $V$)
to $V$ (or $A$).
\end{enumerate}

In this paper we present  algorithms for
performing the ranking in parallel.
Our algorithms are relatively architecture independent
and  can be applied to arrays of arbitrary dimensions
with arbitrary distribution along every dimension.
In the second stage we redistribute selected elements of an array
among all processors. This stage requires many-to-many personalized
communication.

The rest of the paper is organized as follows. 
The definitions and basic operations  are presented in 
Section~\ref{defn-and-notn}.
In Section~\ref{pack-unpack} we describe the parallel
PACK/UNPACK algorithm using the parallel ranking algorithm,
and we present the parallel ranking algorithm in Section~\ref{ranking}.
We explain the optimized schemes in Section~\ref{optimization}.
Section~\ref{results} presents the experimental results,
and  we state our conclusions in Section~\ref{conclusion}.


%********************************************************************************
%*
%*   Section : Definitions and Notations
%*
%********************************************************************************

\Section{Definitions and Basic Operation}
\label{defn-and-notn}

\paragraph{Definitions and Notations}
PACK gathers elements of  input array $A$  to  vector $V$
under the control of  mask array $M$, which
should be conformable with $A$. We assume that  
$M$ is aligned to  $A$. The size of $V$ is the same
as the number of $true$ values in  $M$.
All notations used in this paper are as follows:
%
%-------------------------------------------------------------------------------
%-% \begin{Code}
%-% ***\=*******\=**\= \kill
%-% \> $\bullet \, A     $  \>: \> Array of rank $d$ and shape $(N_{d-1},\ldots ,N_0)$\\ 
%-% \> $\bullet \, A_l   $  \>: \> Local  array of rank $d$ and shape $(L_{d-1},\ldots ,L_0)$\\ 
%-% \> $\bullet \, M     $  \>: \> Mask array of rank $d$ and shape $(N_{d-1},\ldots ,N_0)$\\ 
%-% \> $\bullet \, V     $  \>: \> Vector (rank-one array)\\ 
%-% \> $\bullet \, Pn    $  \>: \> Processor number  \\ 
%-% \> $\bullet \, N     $  \>: \> Global array size $(N=N_{d-1} \times \cdots \times N_0) $\\
%-% \> $\bullet \, P     $  \>: \> Number of processors  ($P=P_{d-1} \times \cdots \times P_0$)\\ 
%-% \> $\bullet \, L     $  \>: \> Local array size $(L=N/P=L_{d-1} \times \cdots \times L_0) $ \\ 
%-% \> $\bullet \, N_i   $  \>: \> Global array size on a dimension $i$  \\ 
%-% \> $\bullet \, P_i   $  \>: \> Number of processors on a dimension $i$  \\ 
%-% \> $\bullet \, W_i   $  \>: \> Block size on a dimension $i$ in block-cyclic distribution \\ 
%-% \> $\bullet \, L_i   $  \>: \> Local array size on a dimension $i$ $(L_i=N_i/P_i)$ \\ 
%-% \> $\bullet \, S_i   $  \>: \> Tile size on a dimension $i$ $(S_i = P_i \, W_i$)\\ 
%-% \> $\bullet \, T_i   $  \>: \> Total number of tiles on a dimension $i$ $(T_i=N_i/S_i)$\\ 
%-% \> $\bullet \, Size  $  \>: \> Total number of $true$ values in  mask array $M$ \\ 
%-% \> $\bullet \, \Delta$  \>: \> Sub-domain where the intermediate ranks are valid  
%-% \end{Code}
\begin{my-table} {|c|l|} \hline
$A$	& Array of rank $d$ and shape $(N_{d-1},\ldots ,N_0)$\\ 
$A_l$   & Local  array of rank $d$ and shape $(L_{d-1},\ldots ,L_0)$\\ 
$M$	& Mask array of rank $d$ and shape $(N_{d-1},\ldots ,N_0)$\\ 
$V$	& Vector (rank-one array)\\ 
$Pn$	& Processor number  \\ 
$N$ 	& Global array size $(N=N_{d-1} \times \cdots \times N_0) $\\
$P$	& Number of processors  ($P=P_{d-1} \times \cdots \times P_0$)\\ 
$L$	& Local array size $(L=N/P=L_{d-1} \times \cdots \times L_0) $ \\ 
$N_i$	& Global array size on a dimension $i$  \\ 
$P_i$	& Number of processors on a dimension $i$  \\ 
$W_i$	& Block size on a dimension $i$ in block-cyclic distribution \\ 
$L_i$	& Local array size on a dimension $i$ $(L_i=N_i/P_i)$ \\ 
$S_i$	& Tile size on a dimension $i$ $(S_i = P_i \, W_i$)\\ 
$T_i$	& Total number of tiles on a dimension $i$ $(T_i=N_i/S_i)$\\ 
$Size$  & Total number of $true$ values in  mask array $M$ \\ 
$\Delta$& Sub-domain where the intermediate ranks are valid  \\ \hline
\end{my-table}
\normalsize
%-------------------------------------------------------------------------------
For the sake of simplicity, we assume that for all $i$ \ $(0 \leq i < d)$,
$P_i \backslash N_i $ and  $W_i \backslash N_i$. Also, we assume that
the row-majored indexing scheme is used and all indices  start from zero.
The above definitions and notations presented for PACK are also valid for 
UNPACK, except that
UNPACK scatters elements of  input vector 
$V$ of size $N'$ to   $A$
under the control of $M$. Note that $N'$ should not be less than $Size$.

%================================================================================
%   
%================================================================================
\paragraph{Vector prefix-reduction-sum}
The {\it vector prefix-reduction-sum\/} primitive, 
which is used in the parallel ranking algorithm,
performs  the element-wise
vector  prefix-sum and  vector reduction-sum  simultaneously
where the prefix operation is exclusive~\cite{14}.
We also define the cost function for vector prefix-reduction-sum
as {\sf PRS\/}$(P,M)$ where $P$ is the 
number of processors and $M$ is the vector size.
Then, {\sf PRS\/}$(P,M)$ is $\Omega (\tau \lg P + \mu  M )$ 
without a control network, and $\Theta (M)$ with a control network as on 
the CM-5 where
$\tau$ is the startup time and $\mu$ is the per-element transfer time.
For details of algorithms, readers are referred to~\cite{14}.


%********************************************************************************
%*
%*   Section : Parallel PACK/UNPACK
%*
%********************************************************************************
\Section{Parallel PACK/UNPACK algorithm}
\label{pack-unpack}
The parallel PACK/UNPACK algorithm consists of two stages, {\it ranking\/}  and
{\it redistribution\/}. In the first stage we  rank all selected elements
under the control of  mask array $M$ by applying the parallel ranking
algorithm, which will be presented in Section~\ref{ranking}.

%==============================================================================
%   Subsection : PACK
%==============================================================================
\SubSection{PACK}
After the ranking stage, 
we know the rank of each element
to be gathered in  result vector $V$ and  $Size$, 
which is also the size of  $V$.
For the sake of simplicity we assume that $V$ is distributed in block 
partitioning among $P$ processors. Then,
the rank (say $r$) of each selected element of $A$  is the same as the global
index of the element of $V$   such that 
the element of $A$ is transferred to $V[r]$.

For the redistribution stage, 
many-to-many personalized communication is required. 
Each processor knows where the local selected elements
of $A_l$ have to be sent, that is, which is the receiving processor.
Also, all messages with the same
 destinations may be coalesced to decrease the communication overhead.

%==============================================================================
%   Subsection : UNPACK
%==============================================================================
\SubSection{UNPACK}
For all $i$ $(0 \leq i < Size)$, $V[i]$ should be transferred to 
the element of $A$ whose corresponding element of $M$ 
has the rank $i$ after the ranking stage.
Note that the transfer from field array $F$
to $A$ is local computation when the corresponding mask element is $false$.

In the redistribution stage, 
 no processor knows who needs the data,
that is, which is the receiving processor.
Therefore,
two-stage communication is required.
Each processor first sends a request  to each sender,
and then each processor  receiving any request  sends data back
to the receiver.
It follows that the communication time for the second stage of UNPACK
may be two times as large as that for PACK.


%********************************************************************************
%*
%*   Section : Parallel Ranking Algorithm
%*
%********************************************************************************

\Section{Parallel ranking algorithm}
\label{ranking}

The ranking algorithm computes the rank of each element to be packed
using the parallel  {\em vector prefix-reduction-sum\/} primitive
without actually moving any elements among processors. 
The ranking algorithm consists of three steps:
{\em initial step\/}, {\em  intermediate step\/}, and 
{\em  final step\/}.
%
For each dimension $i$ \ $(0 \leq i < d)$, we use the  two
local offset arrays, $PS_i$ (for exclusive prefix-sum) and 
$RS_i$ (for reduction-sum),
 of rank $d-i$ and shape
$(L_{d-1}, \ldots ,L_{i+1}, T_i)$
  in order to compute the intermediate rank.
We thus need a total of 
$2d$ local arrays. The final rank is derived by summing all
the offset arrays.

The performance of the ranking algorithm mainly 
depends on the value of $T_i$,
especially the number of tiles on the lower dimension.
Therefore,
we have the lowest ranking overhead in  
block distribution and the highest ranking overhead in  cyclic distribution.
The rest of the presentation is limited to PACK for
obvious reasons.




%================================================================================
%   Subsection : Local Scan
%================================================================================
\paragraph{Initial step (local scan)}
We scan all local elements of   $A_l$
to find the elements to be packed 
and to set the initial rank of those elements
under the control of  $M$, 
initializing $PS_0$ and $RS_0$. 
At the end of this step, 
$PS_0(:, \cdots, :, i)$ and $RS_0(:, \cdots, :, i)$ are the total 
number of local packed elements in $A_{l}(:,  \cdots, :, i \, W_0:(i+1) \, 
W_0 - 1)$ \ where \ $0 \leq i<T_0$, and
$\Delta=[1 \times \cdots \times 1 \times W_0]$.
This initial step takes time $\Theta (L)$.


%================================================================================
%   Subsection : Intermediate step
%================================================================================
\paragraph{Intermediate step}
The intermediate step consists of $d$ (rank of the input array) steps.
Each 
intermediate step $i$ \ $(0 \leq i < d)$ consists of three sub-steps:

\begin{small}
\Line
\begin{itemize}
\item  {\bf Input from the intermediate Step $i-1$}\\
	 Initialized $PS_i$ and $RS_i(L_{d-1},\cdots, L_{i+1}, T_i)$ where 
	 $\Delta= [1\times \cdots \times 1 \times W_i \times
	  	N_{i-1} \times \cdots \times N_0]$.

\item  {\bf Substep 1: Vector prefix-reduction-sum} \\
        Vector prefix-reduction-sum on $PS_i$ (exclusive prefix sum) and
	$RS_i$ (reduction sum) along the dimension $i$ where
        $\Delta= [1\times \cdots \times 1 \times S_i \times
	  	N_{i-1} \times \cdots \times N_0]$.
        This step takes time
 $\Theta(\, \mbox{{\sf PRS\/}}(P_i, \, 
	(\prod^{d-1}_{k=i+1}L_k)T_i) \, )$. 


\item  {\bf Substep 2: Local prefix sum }
\begin{enumerate}
\item $RS_{i+1}(:, \cdots, :, k) \leftarrow RS_{i}(:, \cdots, :, l, T_i-1)$
	\ where \ 
	$0 \leq k < T_{i+1}$ \ and \ $l=(k+1)W_{i+1}-1$. 
      In step $d-1$, $Size \leftarrow RS_{d-1}(T_{d-1}-1)$.

\item Set the starting point of each segment (of total $T_{i+1}$ segments)
      at $RS_i(:, \cdots, :, m, 0)$ for all $m$ such that $m$ {\tt mod}
      $W_{i+1}=0$.
\item Segmented exclusive prefix-sum on $RS_i$ using the same indexing
	scheme.
\item $PS_i \leftarrow PS_i + RS_i$.
\end{enumerate}

Now $\Delta$ is  $ [1\times \cdots \times 1 \times W_{i+1} \times 
		N_i \times N_{i-1} \times \cdots \times N_0]$, and 
this step requires time
 $\Theta ( \, (\prod^{d-1}_{k=i+1}L_k)T_i \,)$.


\item  {\bf Substep 3: Modify $PS_{i+1}$ and $RS_{i+1}$}\\
 $PS_{i+1}$ and $RS_{i+1}(:, \cdots, :, k)
	\leftarrow RS_{i+1}(:, \cdots, :, k) +
		RS_{i}(:, \cdots, :, l, T_i-1)$ 
	\ where \ 
	$0 \leq k < T_{i+1}$ \ and \ $l=(k+1)W_{i+1}-1$. 
       In step $d-1$, $Size \leftarrow Size + RS_{d-1}(T_{d-1}-1).$
       This step takes time
 $\Theta ( \, (\prod^{d-1}_{k=i+2}L_k)T_{i+1} \,)$

\end{itemize}
\Line
\end{small}
%-------------------------------- END   ----------------------------------------|
%-------------------------------------------------------------------------------/

%================================================================================
%   Subsection : Final step
%================================================================================
\paragraph{Final step}
We  compute the global rank of all packed
elements by summing all $PS_i$  $(0 \leq i < d)$. Now the sub-domain $\Delta$
is the same as the whole array. This final step takes time
${\cal O} \,\left( \, \left(\prod^{d-1}_{i=1}L_i\right)T_0 + \alpha\right)$
where $\alpha$ is
the maximum number of local packed elements among all processors
$(0 < \alpha \leq L)$.



%********************************************************************************
%*
%*   Section : Optimization
%*
%********************************************************************************
\Section{Optimization}
\label{optimization}
In this section we present two optimized schemes: {\it compact storage scheme\/}
 and {\it compact message scheme\/}.
We also present an optimized  method using 
redistribution for the input
array that is distributed cyclically in order to reduce the ranking overhead.
First of all, we define  {\it slice\/}, which is a portion
of a local array, $A_l$, such as $A_{l}(:,  \cdots, :, i \, W_0:(i+1) \, 
W_0 - 1)$ \ where \ $0 \leq i<T_0$. 
%Note that  local array $A_l$
%consists of  $\left(\prod^{d-1}_{i=1}L_i\right)T_0$ slices.
%,
%and the size of the slice is equal to the block size on dimension 0, $W_0$.



%==============================================================================
%   Subsection : compact storage scheme
%==============================================================================
\SubSection{Compact storage scheme}

We first present  {\it simple storage scheme\/} and then explain 
the optimized scheme.
In the simple storage scheme information regarding local 
elements to be packed are saved in the initial step, and then
used in the final step of the ranking stage.
This information includes  a local index on each dimension, 
a tile number and an initial local rank. Therefore,
this scheme requires at least four memory-write and memory-read operations
for each  local element to be packed.
As the rank of the input array increases, the  amount of memory access will
increase.

Alternatively, to reduce local memory access time,
we do not save any information at all for local packed elements.
First, we  copy $PS_0$ to the counter array, $PS_c$ before 
the intermediate step.
After computing the final base-rank array, $PS_f$, 
%we can make the $sendl$ vector,
%we can identify the size of the message that will be sent 
we can derive the  size of the message,
which will be sent to each destination processor,
 from
comparing  each element of $PS_c$ with that of $PS_f$ during the final step.
Hence, the time taken by
the final step  depends mainly
on the number of tiles  on dimension~0, $T_0$, since the 
size of two arrays is $\left(\prod^{d-1}_{i=1}L_i\right)T_0$.
%%
In the redistribution stage, message-coalescing requires another local
scan of the input array. 
However, this local scan can be done more efficiently
than that in the initial step, since we know the total number of local packed elements
in each slice.
%First, we need to scan a slice only if the slice has any local packed elements.
%Also, even if the slice has any packed element, we stop scanning the slice
%as soon as we find all packed elements. 
This may be  especially useful when both the slice size
and the total number of packed elements are relatively large.
            
 
%==============================================================================
%   Subsection : Compact Message Scheme
%==============================================================================
\SubSection{Compact message scheme}
In the redistribution stage of PACK,
we need to send
the selected datum value together with its global rank.
In the simple storage scheme
the communication message consists of the pair  
({\it datum value, global rank\/}), so that 
 a message is twice as long as the
number of packed elements.

To reduce  communication overhead (message size), we alternatively use
the  {\it compact message scheme\/}. 
Suppose  there are 
$n$ packed elements in a slice.
Then, we can partition these $n$ values into $i$ segments 
$(0 \leq i < P)$ according to their destination processor.
 Since the global ranks
for the packed elements in each segment are consecutively numbered, we do not
need to send all global ranks together with the packed elements.
 Therefore,
 the communication message consists of
 segments, with each segment having the form 
 of ({\it rank of the first packed element in the segment, 
number of packed elements in the segment, 
datum, $\ldots$, datum\/}).


Since the size of each segment is at least 3,
this optimized scheme may not be useful if the slice size is  one
 or if there is only one packed element in a slice. 
The performance of this compact message scheme 
depends on the block size on dimension~0 
as well as on the number of packed elements in each
slice. 
Also, the performance depends on the block size of the result vector.


%==============================================================================
%   Subsection : Cyclic to Block Distribution
%==============================================================================
\SubSection{Cyclic to block distribution}

Suppose a dimension $i$ of the input array is distributed  cyclicly.
The ranking overhead can be minimized by
redistributing the array along dimension $i$ to the block
distribution. This can be done for one or all the dimensions.
Once the distribution is done as the preliminary step we can apply
the ranking algorithm with the lowest ranking overhead, since all dimensions
are distributed in block.\footnote{Note
that this distribution method can not be used in UNPACK, since UNPACK
is a {\it READ (or GATHER)\/} operation, so that the input data should
be maintained  in the original distribution.}
The details of the communication detection algorithms for array redistribution 
 can be found in~\cite{11}.
 In the following, we describe two redistribution schemes as the 
preliminary steps in PACK.

%%%---- Table
\input{sranka-pack.input}
%%%---

%\paragraph{Redistribution of Selected Data}
%\subsubsection{Redistribution of Selected Data}
%In this redistribution scheme, 
In the first scheme ({\em redistribution of selected data\/})
we redistribute selected input data
to be packed, but no data from the mask array.
Hence, this scheme would be
useful when the total number of packed elements is relatively small.
Since we  redistribute only selected elements, we need to send the global index
together with the selected element.
%\paragraph{Redistribution of Whole Arrays}
%\subsubsection{Redistribution of whole arrays}
On the other hand,
when the total number of the packed elements is relatively large, 
the second scheme ({\em redistribution of whole array\/})
is more useful. That is, we redistribute 
the input array and the mask array  in order to reduce the local 
computation overhead entailed in the previous redistribution
scheme.
%In this redistribution scheme, 
%whole two arrays are redistributed, but the redistributed arrays 
%should be stored in the temporary arrays on the receiver.

%********************************************************************************
%*
%*   Section : Experimental results
%*
%********************************************************************************

\Section{Experimental results}
\label{results}

Three schemes ({\it simple storage scheme\/}, {\it compact storage scheme\/}
and {\it compact message scheme\/}) for PACK, and two schemes
({\it simple storage scheme\/} and {\it compact storage scheme\/})
for UNPACK were programmed in C on the CM-5.
Experiments were conducted for six one-dimensional arrays 
($N=4096, 8192, 16384, 32768, 65536, 131072$) and
  four two-dimensional arrays 
($N\times N= 64 \times 64, 128 \times 128, 256 \times 256, 512 \times 512$).
On the CM-5 16 processors for  one-dimensional arrays and
$4 \times 4$ processors for  two-dimensional arrays 
were used. 

In addition, other experiments were performed on the CM-5
by using 256 processors ($16 \times 16$ for a two-dimensional array), which
is 16 times larger than  the 16 processors used in the former experiments, 
in the following manner.
We first chose two input arrays, $N=65536$ and $N\times N=512 \times 512$,
and then increased the size of the input arrays 16 times as 
we increased the number of processors 16 times. Hence in two experiments
the local array size was fixed, but the number of processors was increased
16 times.


Various block sizes were used,
but $W_0$ was fixed to be 
the same as $W_1$ in the two-dimensional arrays.
The vector $V$ was  fixed to be distributed in block. 
Five input mask arrays were 
randomly generated with density $=10\%, 30\%, 50\%, 70\%,$ 
and~$90\%,$.\footnote{Here the mask density $\delta$ means that the $\delta\%$
of elements in the mask array have  true values.}
Notice that  only partial results are presented in Tables~\ref{t-total}
and~\ref{t-total-unpack}
 due to space limitation.
Full results are available in~\cite{13}.

%----------------------------------------
%   Local Computation
%----------------------------------------
 {\bf Local computation:}
%%As the block size decreases,  local computation time
%%increases no matter how high the mask density is,
%The time for local computation mainly depends on
% the block size, 
%%so that we have the 
%%best result in block distribution.
As the block size, $W_i$ ($i=0,1$), decreases,  local computation time
increases no matter how high the mask density is.
The performance of the intermediate step and 
computing the final base-rank array, $PS_f$, in the final step
of the ranking stage is proportional to the
number of tiles, $T_i$, where $T_i = N_i/(P_i W_i)$  $(i=0,1)$.
In the intermediate step the size of two arrays, $PS_i$ and $RS_i$,
increases as the block size decreases (or as the number of tiles increases).
Similarly, 
the time for computing the final base-rank array, $PS_f$, during the final step
increases as the block size decreases.
%
As the mask density increases, the compact message scheme and the
compact storage scheme give a much better performance than the simple storage
scheme. 
Since the compact message scheme basically requires the compact storage scheme,
the compact message scheme  gives a better performance than the compact storage
 scheme  except when the block size is 1 or 2.
In cyclic distribution we had the worst performance. Also, the simple storage 
scheme gave the better results than two optimized schemes.

%----------------------------------------
%   M-to-M Comm
%----------------------------------------
 {\bf Many-to-many personalized communication:}
For many-to-many personalized communication,
{\it linear permutation scheduling\/} algorithm~\cite{7}
using {\it active messages\/}~\cite{15} was used.
%Since the  difference between the performances of 
%the two schemes is mainly in the message size,
We have results similar  to
those for local computation. 
That is,  as  mask density increases, the compact message scheme
gives  a better performance than the simple storage scheme.
Generally, as the block size increases, 
the compact message scheme  gives  a better performance than the 
simple storage scheme except in block distribution.


%----------------------------------------
%     PRS
%----------------------------------------
 {\bf Vector prefix-reduction-sum:}
The performance of {\em vector prefix-reduction-sum\/}
  depends completely on the size of the vector on which
  prefix-reduction-sum is performed.
The vector size
at the intermediate step $i$ $(0 \leq i < d)$ is 
$\left(\prod^{d-1}_{k=i+1}L_k\right)T_i$. 
In one-dimensional arrays, the vector size is
$T_{0} = L_{0}/W_{0}$. In two-dimensional arrays, the vector sizes
at the intermediate steps 0 and 1 are $L_{1}T_{0} = (L_{1}L_{0})/W_{0}$ and
$T_{1} = L_{1}/W_{1}$, respectively.
Hence, as the block size increases (or the total number of tiles decreases),
the time taken by vector prefix-reduction-sum decreases.

%----------------------------------------
%   Total Execution Time in PACK/UNPACK
%----------------------------------------
{\bf Total execution time in PACK/UNPACK:} 
For a fixed  local array size, the total costs for PACK/UNPACK are dominated by
the cost for local computation in  a small number of processors.
But in a large number of processors the most  time is spent 
for communication (vector prefix-reduction-sum and many-to-many
personalized communication).  Generally, the time for the
vector prefix-reduction-sum is relatively small, compared to that
for local computation and for many-to-many personalized communication.
Only when the block size is very small (especially, block size$=1$),
the time for the vector prefix-reduction-sum
is larger than that for many-to-many personalized communication, but smaller
than that for local computation.
As can be seen in the results for local computation and 
many-to-many personalized communication,
the compact message scheme gives the best performance among three schemes,
and the compact storage scheme gives better results than  the
simple storage scheme when the block size is relatively large and 
the mask density is relatively high.

%%%---- Table
\input{sranka-unpack.input}
%%%---


{\bf Redistribution scheme:} 
In one-dimensional arrays a preliminary redistribution requires
much more time for communication detection than in two-dimensional arrays.
Neither of the two redistribution schemes gives better results
than the simple storage scheme.
In two-dimensional arrays
the first redistribution
scheme gives better results when the mask density is relatively low
(Table~\ref{t-red2}).
The performance of the second redistribution scheme
 is not greatly affected by the mask density,
but the performance of the first redistribution scheme
  depends on the mask density.

%----------------------------------------
%   Redistribution Scheme
%----------------------------------------
%----------------------------------------------------------------------
\begin{table}[htbp]%[p]
\begin{my-table} {|c|rrr|rrr|} 
\hline
Mask          & 
\multicolumn{3}{|c|}{$256\times 256$} &
\multicolumn{3}{|c|}{$512\times 512$} \\ \cline{2-7}
Density   & SSS & Red. 1 & Red. 2 &  SSS  & Red. 1 & Red. 2\\ \hline
%	    
$10\%$    &  46.44 & 34.83  & 60.62    & 184.49 & 110.86  & 195.85  \\ 
$50\%$    &  64.76 & 63.99  & 64.24    & 256.37 & 231.35  & 208.66  \\ 
$90\%$    &  82.38 & 91.59  & 66.97    & 327.34 & 345.72  & 220.59  \\ \hline
\end{my-table}
%
\caption{Comparison of execution time $(millisec)$ for 
two redistribution schemes in  PACK
(number of processors $ = 4 \times 4$)}
\label{t-red2}
\end{table}
%----------------------------------------------------------------------

%********************************************************************************
%*
%*   Section : Conclusion
%*
%********************************************************************************

\Section{Conclusions}
\label{conclusion}

We have  presented a parallel PACK/UNPACK algorithm using the
ranking algorithm and have shown the experimental results for PACK/UNPACK
 on the CM-5. We have also presented two optimization schemes,
{\it compact storage scheme\/}
 and {\it compact message scheme\/}. For the cyclicly distributed
input array we have suggested two redistribution schemes,
{\it redistribution of selected data\/} and
{\it redistribution of whole arrays\/}.


The performance of the ranking algorithm
largely depends on the block size of input arrays distributed
in block-cyclic, especially on the block size of the lower dimension.
Hence we have the lowest ranking overhead when the input array is 
distributed in block. When the input array is distributed  cyclicly,
two redistribution schemes may be used to reduce the ranking overhead.
The performance of the ranking algorithm
may not be greatly affected 
by the total number or the distribution of the elements to be packed.
Parallel PACK/UNPACK using the ranking algorithm are  
architecture independent and can be applied to arrays of arbitrary dimensions
with arbitrary distribution along every dimension.

The compact message scheme has given the best performance of three schemes,
and the compact storage scheme has given better results than those of the
simple storage scheme when the block size is relatively large 
and the mask density is relatively high.
Also, as the local array size increases, two optimized schemes 
gave a much better performance.
This is mainly due
to the reduction of local computation in the compact storage scheme and
the reduction of the communication overhead in the compact message scheme.

%------------------------------------------------------------------------- 
%\nocite{ex1,ex2}
\bibliographystyle{latex8}
\bibliography{sranka}

\end{document}

====================== END FILE: latex8.tex ======================
