% @(#) bicubic.f 1.5 (IDS) 1/19/95
\documentstyle [12pt, sane]{article}
\setlength{\textheight}{8.7in}
\setlength{\topmargin}{-1cm}
\setlength{\oddsidemargin}{+7mm}
\setlength{\textwidth}{6.2in}
\pagestyle{fancy}
\input{psfig}

\begin{document}
\title{Update}
\author{{\it Research Assistant} : Manu Natarajan \\ \\
Northeast Parallel Architectures Center \\
	Syracuse University, 111, College Place \\
	Syracuse, NY, 13244-4100 }

\date{}
\maketitle
\clearpage\section{Selection of Data Points}

In this lasagnia decomposition each node receives an input partition of the 
latitude, longitude grid and each of the two wind components [Fig 2].  Each
node then computes a set of points (ordered pairs) {(ii,jj)} from the
latitude, longitude grid, based on which an interpolation is carried out.
In case of the bilinear interpolation, associated with the set of points 
{(ii,jj)} there exist four sets of points {(ii,jj+2)}, {(ii,jj+3)}, 
{(ii+1),(jj+2)}, {(ii+1,jj+3)} which are required for the interpolation 
[Fig. 3].
In case of the bicubic interpolation there are sixteen such sets of points
[Fig. 4]
\footnote{ Hereafter,
the discussion will consider only the bilinear interpolation, but the same
reasoning holds good for the bicubic interpolation.  }.

In the first approach to interpolation, the algorithm is outlined below.

\begin{itemize}
\item {Do for all (ii,jj)}
\begin{itemize}	
\item	Find the 4 points (ii,jj+2), (ii,jj+3), (ii+1,jj+2), (ii+1,jj+3)
\item   Obtain the values of the wind component at above points.
\begin{itemize}
	\item If the value is not available locally, {\em fetch} from
         the appropriate neighboring node
\end{itemize}
\item  Find the interpolation point.
\item  Compute the value at interpolation point.
\end{itemize}
\item End of do loop
\end{itemize}

It is obvious that though the above approach is simple, it is impractical
to implement because of the huge communication overhead involved.  For, every
point that is not available locally, a communication call will have to be
generated to fetch the value at that point.  There are at least two approaches
which lower the communication overhead. In both the
approaches strips of the wind components are shifted from node to node.  The
shifting occurs in both the southern and northern directions.  The amount of
shifting is determined by the approach discussed in section 3.1.

In the second approach we wish to fully reconstruct the four associated sets 
of points {(ii,jj+2)}, {(ii,jj+3)}, {(ii+1),(jj+2)}, {(ii+1,jj+3)} in four
arrays  for every node.  Then the four arrays are indexed to obtain the four 
points required for interpolation on every node.  As a wind component has
been partitioned as shown in Fig. 2, there is an upper and a lower bound
on the index jj in the North-South direction that decides which values of
a wind component may be found locally.  Thus, at every shift of the wind
strips, the four arrays maybe partially reconstructed using the new bounds 
obtained with every shift.  At the end of the shifting the arrays should be
 fully reconstructed.  However, there will be points such that the points
 (ii,jj) will be local but (x,jj+2) or (x,jj+3) may not be local as seen in
 figure 3 \footnote
{ x maybe ii or ii + 1.  This does not matter as in the East-West direction
 the elements of the wind component are local to a node. }. Thus it will not 
 be possible to reconstruct {\em entirely locally } the four associated sets of 
 points for all jj that that fall within the bounds of the node's partition.
 {\em If the reconstruction is not done entirely locally, there would be additional
 communication overhead to fetch the missing values one at a time, as in the
 first approach. }  This hitch may be
 rectified by initially creating a 3-element wide strip in the Northern 
 direction by fetching those elements from the neighboring nodes [Fig. 6]. 
 The 
 creation of the Northern buffer is created before performing any shifts.
 The original partition and this northern buffer is now termed a segment.
 These segments are shifted instead of the original partition. The algorithm
 for the second approach is outlined as follows, which is executed once for
 each of the two wind components.

 \begin{itemize}
   \item { Number of elements in E-W direction for a partition is imp3 }
   \item { Number of elements in N-S direction for a partition is range }
   \item { Pre-determine the degree of circulation }
   \item { Construct the northern buffer. }
   \item {Select elements from segment}
   \item {Fetch segments and select elements from southern direction}
   \item {Fetch segments and select elements from northern direction}
   \item {Perform local interpolation}
  \end{itemize}


Algorithm for {\em construction of northern buffer}

 \begin{itemize}
   \item {Copy original wind partition to temporary buffer (depart)}
   \item {If partition width less than 3 then}
   \begin {itemize}
   \item {While northern buffer incomplete}
   \begin{itemize}
     \item { Send depart to southern node }
     \item { Receive partition into northern buffer from northern node}
     \item { Copy received partition into depart }
   \end{itemize}
   \item {End of while}
   \end{itemize}
   \item {Else (partition width is .ge. 3) }
   \begin{itemize}
     \item { Send original partition to southern node }
     \item { Receive new partition in northern buffer from northern node }
   \end{itemize}
   \item {Append northern buffer to original wind partition. This will
            be called segment. }
 \end{itemize}


Algorithm for {\em fetching of segments from southern direction}

     \begin {itemize}
       \item {Current partition bounds = Original partition bounds }
       \item {Copy original segment into temporary buffer (depart)}
       \item {For number of hops in southern direction }
       \begin {itemize} 
	 \item {Send upper \& lower bounds of current partition to northern
                node.}     
         \item {Receive upper \& lower bounds of new partition from southern 
                node.}
         \item {Send 'depart' to northern node.}
         \item {Receive new segment from southern node in buffer 'landing'.}
	 \item {Current partition bounds = new partition bounds}
         \item {Copy 'landing' into 'depart'}
         \item {Select elements from landing (new segment)}
       \end {itemize}
      \end {itemize}


Algorithm for {\em fetching of segments from northern direction}

     \begin {itemize}
       \item {Current partition bounds = Original partition bounds }
       \item {Copy original segment into temporary buffer (depart)}
       \item {For number of hops in northern direction }
       \begin {itemize} 
	 \item {Send upper \& lower bounds of current partition to southern
                node.}     
         \item {Receive upper \& lower bounds of new partition from northern 
                node.}
         \item {Send 'depart' to southern node.}
         \item {Receive new segment from northern node in buffer 'landing'.}
	 \item {Current partition bounds = new partition bounds}
         \item {Copy 'landing' into 'depart'}
         \item {Select elements from landing (new segment)}
       \end {itemize}
      \end {itemize}


Algorithm for {\em selection of elements from segment }
  \begin{itemize}
   \item { Number of elements in E-W direction for a partition is imp3 }
   \item { Number of elements in N-S direction for a partition is range }
   \item { Input : }
   \begin{itemize}
     \item {segment}
     \item {partition (corresponding to segment as in Fig x) bounds 
           (lower, upper)}
     \item {set of points \{(ii,jj)\}}
     \item {arrays to hold the four sets of points - w1, w2, w3, w4}
   \end{itemize}	
   \item {For i = 1, imp3}
     \begin{itemize}
       \item {For j = 1, range}
       \begin{itemize}
         \item {If (jj(i,j) .le. upper) .and. (jj(i,j) .ge. lower)}
         \begin{itemize}
	   \item {w1 = segment(ii(i,j), jj(i,j) +2)}
           \item {w2 = segment(ii(i,j), jj(i,j) +3)}
	   \item {w3 = segment(ii(i,j)+1, jj(i,j) +2)}
           \item {w4 = segment(ii(i,j)+1, jj(i,j) +3)}
         \end{itemize}
       \end{itemize}
       \item {end of for i = ...}
      \end{itemize}
      \item {end of for j = ...}
    \end{itemize}
   

Algorithm for {\em bilinear interpolation}
\begin{itemize}
   \item { Number of elements in E-W direction for a partition is imp3 }
   \item { Number of elements in N-S direction for a partition is range }
   \item {for j = 1, range}
   \begin{itemize}
     \item {for i = 1, imp3}
	\begin{itemize}
	  \item {value at interpolated point = 
             (1.0 - delx(i,j)) * 
                ((1.0 - dely(i,j)) * w1(i,j) + dely(i,j) * w2(i,j)) 
             + delx(i,j) * ((1.0 - dely(i,j)) * w3(i,j) + dely(i,j) * w4(i,j))}
        \end{itemize}
   \end{itemize}
\end{itemize}

The drawback with this approach is that the communication overhead for 
creating the northern buffer increases when the width of an individual strip 
is smaller than the overlap region [Fig. 7]. 

The third approach recognizes the fact that given the set of computed points
{(ii,jj)} on each node, the node only needs to see a segment of the entire
wind component to perform a local interpolation; there is no necessity for 
reconstructing the associated four sets of points.  This segment is not the
same as in the second approach, in that its size is not a static quantity. The
size of the segment depends on how far back one needs to go along
the fluid trajectory to perform an interpolation, and hence is a dynamic 
quantity.  Thus, no extra communication is needed to establish a northern
buffer. Additionally, only the {\em original } partitions of the wind 
component need be shifted to 
create the segment.  The circulated wind strips are appended as shown in 
Fig. 8. Some, book-keeping needs to be done in order to the relative position
of the partition in the segment and for generation of local indices.  This 
book-keeping is of less overhead than the previous approach, as it needs to
be done only once per shift and not for every point in the shifted component.
The interpolation is then carried out locally. The four points are obtained by
 the use of the local indices.  The algorithm is outlined below.

The {\em first-level refinement} for the third approach. The individual 
steps are elaborated subsequently.

\begin{itemize}
   \item { Number of elements in E-W direction for a partition is imp3 }
   \item { Number of elements in N-S direction for a partition is range }
   \item { Pre-determine the degree of circulation }
   \item { Copy the partition into a large buffer called segment}
   \item { Fetch partitions from the southern direction and append to
	   segment. }
   \item { Fetch partitions from the northern direction and append to
	   segment. }
   \item { Convert global indices to local indices. }
   \item { Perform the interpolation locally. }
\end{itemize}

The pre-determination of the degree of circulation is as outlined in section
3.1.

The algorithm for {\em fetching of partitions from the southern direction and
appending to the segment} is as below.

\begin {itemize}
       \item {Current partition bounds = Original partition bounds }
       \item {Copy partition into temporary buffer (depart)}
       \item {For number of hops in southern direction }
       \begin {itemize} 
	 \item {Send upper \& lower bounds of current partition to northern
                node.}     
         \item {Receive upper \& lower bounds of new partition from southern 
                node.}
         \item {Send 'depart' to northern node.}
         \item {Receive new partition from southern node in buffer 'landing'.}
         \item {Update parameters needed for generation of local indices.}
	 \item {Move up the previously filled columns in the segment by width
                of the new partition (southern partitions occupy lower 
                indices in the segments [Fig. 8]. }
         \item {Append the new partition to the 'southern end' of the segment.}
         \item {Update width of segment.}
         \item {Copy 'landing' into 'depart'}
       \end {itemize}
      \end {itemize}


The algorithm for {\em fetching of partitions from the northern direction and
appending to the segment} is as below.

\begin {itemize}
       \item {Current partition bounds = Original partition bounds }
       \item {Copy partition into temporary buffer (depart)}
       \item {For number of hops in northern direction }
       \begin {itemize} 
	 \item {Send upper \& lower bounds of current partition to southern
                node.}     
         \item {Receive upper \& lower bounds of new partition from northern 
                node.}
         \item {Send 'depart' to southern node.}
         \item {Receive new partition from northern node in buffer 'landing'.}
         \item {Update parameters needed for generation of local indices.}
         \item {Append 'landing' to the 'northern end' of the segment; 
                northern partitions occupy higher indices in the segment
                 [Fig 8].}
         \item {Update width of segment.}
         \item {Copy 'landing' into 'depart'}
       \end {itemize}
      \end {itemize}


The local indices are generated with the following considerations :

\begin {itemize}
\item { The first column in any segment does not necessarily correspond
        to column '1' in the wind component. }
\item { There maybe a wrap around in the southern direction; i.e. the southern
most node communicated may cross the south pole. }

\item { Similarly there may be a wrap around in the northern direction. }

\end {itemize}

The algorithm {\em generation of local indices} is as below.  Fig. X illustrates the algorithm.

\begin {itemize}
  \item {co\_lower = lower bound of non-wrapped part of segment }
  \item {wr\_lower = lower bound of wrapped part of segment }
  \item {wrapd = width of wrapped part of segment.}
  \item {Let 'njj' denote the set of new (local) indices}
  \item {If there is no wrap around in either direction}
    \begin{itemize}      
      \item {for i = 1, imp3}
	\begin {itemize}
	  \item {for j = 1, range}
	    \begin{itemize}      
		\item {njj(i,j) = jj(i,j) - co\_lower + 1}
            \end{itemize}
         \end{itemize}
     \end{itemize}

  \item {If there is wrap around in southern direction}
    \begin{itemize}      
      \item {for i = 1, imp3}
	\begin {itemize}
	  \item {for j = 1, range}
	    \begin{itemize}      
                \item {if jj(i,j) .ge. wr\_lower
                       then njj(i,j) = jj(i,j) - wr\_lower + 1}
		\item {Else njj(i,j) = jj(i,j) + wrapd}
            \end{itemize}
         \end{itemize}
     \end{itemize}

  \item {If there is wrap around in northern direction}
    \begin{itemize}      
      \item {for i = 1, imp3}
	\begin {itemize}
	  \item {for j = 1, range}
	    \begin{itemize}      
                \item {if jj(i,j) refers to the wrapped part
                       then njj(i,j) = jj(i,j) + jmp3 - co\_lower + 1}
		\item {Else njj(i,j) = jj(i,j) - co\_lower + 1}
            \end{itemize}
         \end{itemize}
     \end{itemize}

\end{itemize}

The algorithm for {\em the bilinear interpolation} is below

\begin{itemize}
  \item {Let 'seg' denote segment}
  \item {Let 'njj' denote new (local) jj}
  \item { Number of elements in E-W direction for a partition is imp3 }
  \item { Number of elements in N-S direction for a partition is range }
  \item {for j = 1, range}
  \begin {itemize}
    \item {for i = 1, imp3}
    \begin{itemize}
            value at interpolated point =  
             (1.0 - delx(i,j)) * 
                ((1.0 - dely(i,j)) * seg(ii(i,j), njj(i,j)+2)) + 
                  dely(i,j) * seg(ii(i,j), njj(i,j)+3) +
                  delx(i,j) * ((1.0 - dely(i,j)) * seg(ii(i,j)+1, njj(i,j)+2) +
                  dely(i,j) * seg(ii(i,j)+1, njj(i,j)+3))
   \end{itemize}
  \end{itemize}
\end{itemize}

The algorithm for {\em the pre-determination of degree of circulation} is below
\begin{itemize}
  \item { ny = Number of nodes (processors) used }
  \item { Let 'myaddr' denote the address of the node executing the code}
  \item {Let 'ownp0' denote nodal address where value 'jj(i,j)+0' resides }
  \item {Let 'ownp3' denote nodal address where value 'jj(i,j)+3' resides }
  \item { Number of elements in E-W direction for a partition is imp3 }
  \item { Number of elements in N-S direction for a partition is range }
  \item {for j = 1, range}
  \begin {itemize}
    \item {for i = 1, imp3}
      \begin {itemize}
        \item {ownp0 = jj(i,j) / partition width }
        \item {ownp3 = (jj(i,j) + 3) / partition width }
        \item { Find the inter-nodal distance in {\em northern direction}
                from 'myaddr' to both ownp0 and ownp3}
	\begin{itemize}
          \item {distp0 = ownp0 - myaddr}
          \item {distp3 = ownp3 - myaddr}
          \item {if (distp0 .lt. 0),distp0 = ny + distp0}
          \item {if (distp3 .lt. 0),distp3 = ny + distp3}
        \end{itemize}

	\item {Find the shortest inter-nodal distance for both ownp0, ownp3, 
               and update the local maximum inter-nodal distances if required}
      \end{itemize}
    \end{itemize}

    \item {Find the global max. northern dist. (reduction operation)}
    \item {Find the global max. southern dist. (reduction operation)}
\end {itemize}


Expansion of {Updation of local maximum inter-nodal distances}
        \begin {itemize}
          \item {Let distp0 be the inter-nodal distance in 
                 {\em northern direction} from 'myaddr' to ownp0}
          \item {Let distp3 be the inter-nodal distance in 
                 {\em northern direction} from 'myaddr' to ownp3}
	  \item { If distp0 .gt. (ny / 2)}
            \begin{itemize}
              \item {distp0 = ny - distp0}
	      \item {if (max. southern dist .lt. distp0) max. southern dist =
                     distp0}
            \end{itemize}
          \item {Else}
          \begin{itemize}
            \item{if (max. northern dist .lt. distp0) max. northern dist =
                     distp0}
          \end{itemize}

	  \item { If distp3 .gt. (ny / 2)}
            \begin{itemize}
              \item {distp3 = ny - distp3}
	      \item {if (max. southern dist .lt. distp3) max. southern dist =
                     distp3}
            \end{itemize}
          \item {Else}
          \begin{itemize}
            \item{if (max. northern dist .lt. distp3) max. northern dist =
                     distp3}
          \end{itemize}
        \end{itemize}

\end{document}

