node85.html

Design and building parallel program

<A NAME=10952>&#160;</A>
of an array, a mapping of array indices to abstract processors in a
<A NAME=10953>&#160;</A>
processor arrangement.  Each dimension of an array may be distributed
<A NAME=10954>&#160;</A>
in one of three ways.
<P>

<PRE><TT> 
		<tt> *</tt>        		: No distribution
<P>
		<tt> BLOCK(n)</tt> 		: Block distribution (default: <tt> n=<em> N/P</em>
</tt>)
<P>
		<tt> CYCLIC(n)</tt>		: Cyclic distribution (default: <tt> n=1</tt>)
<P>
</TT></PRE>

<P>
<P><A NAME=11913>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img958.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img958.gif">
<BR><STRONG>Figure 7.7:</STRONG> <em> The HPF <tt> DISTRIBUTE</tt> statement, as used to specify
different distributions of a two-dimensional array of size <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img956.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img956.gif"> onto four processors organized either as a one-dimensional array
(in the three examples with a ``<tt> *</tt>'') or as a <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img957.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img957.gif"> array
(in the other three examples).  The data mapped to processor 1 is
shaded in each example.</em><A NAME=fighpfdistr>&#160;</A><BR>
<P>
<P>
Let <em> N</em>
 be the number of elements in an array dimension, and let
<em> P</em>
 be the number of processors assigned to that dimension.  Then, as illustrated in
Figure <A HREF="node85.html#fighpfdistr" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node85.html#fighpfdistr">7.7</A>, a <tt> BLOCK</tt> distribution divides the
indices in a dimension into contiguous, equal-sized blocks of size
<em> N/P</em>
, while a <tt> CYCLIC</tt> distribution maps every <em> P</em>
th index to the
same processor.  The optional integer argument to <tt> BLOCK</tt> and <tt>
CYCLIC</tt> specifies the number of elements in a block.
<P>
<A NAME=10976>&#160;</A>
The <tt> ONTO</tt> specifier can be used to perform a distribution across
a particular processor array.  If no processor array is specified, one
is chosen by the compiler.  Hence, both <tt> DISTRIBUTE</tt> statements in
the following code fragment are valid.
<P>

<PRE><TT> 
		<tt> !HPF$</tt> 		 <tt> PROCESSORS p(32)</tt>
<P>
				              <tt> real D(1024), E(1024)</tt>
<P>
		<tt> !HPF$</tt> 		 <tt> DISTRIBUTE D(BLOCK)</tt>
<P>
		<tt> !HPF$</tt> 		 <tt> DISTRIBUTE E(BLOCK) ONTO p</tt>
<P>
</TT></PRE>

<P>
<A NAME=10988>&#160;</A>
A <tt> DISTRIBUTE</tt> directive applies not only to the named array but
also to any arrays that are aligned with it.  Thus, a <tt>
DISTRIBUTE</tt> directive cannot be applied to an array that is aligned
with another.  For example, in the following code fragment the <tt>
DISTRIBUTE</tt> directive specifies a mapping for all three arrays.
<P>

<PRE><TT> 
		<tt> !HPF$</tt> 		 <tt> PROCESSORS p(20)</tt>
<P>
				              <tt> real A(100,100), B(100,100), C(100,100)</tt>
<P>
		<tt> !HPF$</tt> 		 <tt> ALIGN B(:,:) WITH A(:,:)</tt>
<P>
		<tt> !HPF$</tt> 		 <tt> ALIGN C(i,j) WITH A(j,i)</tt>
<P>
		<tt> !HPF$</tt> 		 <tt> DISTRIBUTE A(BLOCK,*) ONTO p</tt>
<P>
</TT></PRE>

<P>
<P><A NAME=proghpf1>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img959.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img959.gif"><P>
<P>
<BR><HR>
<b> Example <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img962.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img962.gif">.<IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img960.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img960.gif">    HPF Finite Difference</b>:<A NAME=exfdii>&#160;</A>
<P>
<A NAME=11022>&#160;</A>
Program <A HREF="node85.html#proghpf1" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node85.html#proghpf1">7.2</A> is an HPF version of Program <A HREF="node84.html#progf90" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node84.html#progf90">7.1</A>.
<A NAME=11025>&#160;</A>
Notice that only three directives have been added: <tt> PROCESSORS</tt>,
<tt> DISTRIBUTE</tt>, and <tt> ALIGN</tt>.  These directives partition each of
the two arrays by row, hence allocating 25 rows to each of four
processors.
<P>
The following is an alternative set of directives that partitions the
two arrays in two dimensions so that each processor has a block of
size 50<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img961.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img961.gif">50.  Notice that only the directives need to
be changed to specify this alternative algorithm.
<P>

<PRE><TT> 
		<tt> !HPF$</tt> 		 <tt> PROCESSORS pr(2,2)</tt>
<P>
				              <tt> real X(100,100), New(100,100)</tt>
<P>
		<tt> !HPF$</tt> 		 <tt> ALIGN New(:,:) WITH X(:,:)</tt>
<P>
		<tt> !HPF$</tt> 		 <tt> DISTRIBUTE X(BLOCK,BLOCK) ONTO pr</tt>
<P>
</TT></PRE>

<P>
As discussed in Example <A HREF="node30.html#experfgrid" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node30.html#experfgrid">3.4</A>, the two-dimensional
decomposition is typically more efficient than the one-dimensional
decomposition.
<P>
<BR><HR>
<P>
<BR><HR>
<b> Example <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img972.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img972.gif">.<IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img963.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img963.gif">    Pairwise Interactions</b>:<A NAME=expix>&#160;</A>
<P>
Consider the following version of the pairwise interactions problem of
<A NAME=11041>&#160;</A>
Section <A HREF="node10.html#exinteractions" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node10.html#exinteractions">1.4.2</A>.  We must compute the total
<A NAME=11043>&#160;</A>
force <tt> force<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img964.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img964.gif"></tt> acting on each of <em> N</em>
 objects <tt> x<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img965.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img965.gif"></tt>.
This is defined as follows, where <tt> force<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img966.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img966.gif"></tt> and <tt> x<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img967.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img967.gif"></tt> are
both 3-vectors and the function <tt> f</tt> computes the force between two
objects:
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img968.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img968.gif">  <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img969.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img969.gif">
<P>
<P><A NAME=proghpfpair>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img970.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img970.gif"><P>
<P>
An HPF formulation of this problem is presented in
Program <A HREF="node85.html#proghpfpair" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node85.html#proghpfpair">7.3</A>.  This program is defined for an array of
ten processors.  The arrays <tt> Force</tt>, <tt> Tmp</tt>, and <tt> X</tt> are
aligned and distributed blockwise.  The <em> N(N-1)</em>
 interactions are
computed in <em> N-1</em>
 steps, with the <em> i</em>
th step computing
interactions between each element <tt> X<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img971.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img971.gif"></tt> and the element offset
by <em> i</em>
 in <tt> X</tt>.  The <tt> CSHIFT</tt> operation is used to update a
temporary array containing the offset values.  This temporary array is
shifted one element at each step.  Each call to the function <tt> f</tt>
computes <em> N</em>
 interactions.
<P>
<A NAME=11070>&#160;</A>
Naively, we might expect each of the <tt> CSHIFT</tt> operations to result
in a communication operation.  On many machines, it will be more
efficient to block these communications so that data circulates among
the ten processors in just nine communication steps, as described in
<A NAME=11072>&#160;</A>
Section <A HREF="node10.html#exinteractions" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node10.html#exinteractions">1.4.2</A>.  An HPF compiler would normally be
expected to perform this optimization.
<P>
<BR><HR>
<P>
<A NAME=11074>&#160;</A>
<P>

<BR> <HR><a href="msgs0.htm#2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/tppmsgs/msgs0.htm#2"><img ALIGN=MIDDLE src="asm_color_tiny.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/asm_color_tiny.gif" alt="[DBPP]"></a>    <A NAME=tex2html2976 HREF="node84.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node84.html"><IMG ALIGN=MIDDLE ALT="previous" SRC="previous_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/previous_motif.gif"></A> <A NAME=tex2html2984 HREF="node86.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node86.html"><IMG ALIGN=MIDDLE ALT="next" SRC="next_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/next_motif.gif"></A> <A NAME=tex2html2982 HREF="node82.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node82.html"><IMG ALIGN=MIDDLE ALT="up" SRC="up_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/up_motif.gif"></A> <A NAME=tex2html2986 HREF="node1.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node1.html"><IMG ALIGN=MIDDLE ALT="contents" SRC="contents_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/contents_motif.gif"></A> <A NAME=tex2html2987 HREF="node133.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node133.html"><IMG ALIGN=MIDDLE ALT="index" SRC="index_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/index_motif.gif"></A> <a href="msgs0.htm#3" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/tppmsgs/msgs0.htm#3"><img ALIGN=MIDDLE src="search_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/search_motif.gif" alt="[Search]"></a>   <BR>
<B> Next:</B> <A NAME=tex2html2985 HREF="node86.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node86.html">7.4 Concurrency</A>
<B>Up:</B> <A NAME=tex2html2983 HREF="node82.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node82.html">7 High Performance Fortran</A>
<B> Previous:</B> <A NAME=tex2html2977 HREF="node84.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node84.html">7.2 Fortran 90</A>
<BR><HR><P>
<P><ADDRESS>
<I>&#169 Copyright 1995 by <A href="msgs0.htm#6" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/tppmsgs/msgs0.htm#6">Ian Foster</a></I>
</ADDRESS>
</BODY>