node127.html

Design and building parallel program

<P>
<P><A NAME=15528>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1155.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1155.gif">
<BR><STRONG>Figure 11.6:</STRONG> <em> The parallel merge operation, performed in hypercubes
of dimension one, two, and three.  In a hypercube of dimension
<em> d</em>
, each task performs <em> d</em>
 compare-exchange operations.  Arrows
point from the ``high'' to the ``low'' task in each
exchange.</em><A NAME=figsort3>&#160;</A><BR>
<P><H4><A NAME=SECTION04340020000000000000> Parallel Merge.</A></H4>
<P>
A parallel merge algorithm performs a merge operation on two sorted
sequences of length <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1156.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1156.gif">, each distributed over <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1157.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1157.gif"> tasks, to
produce a single sorted sequence of length <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1158.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1158.gif"> distributed over
<IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1159.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1159.gif"> tasks.  As illustrated in Figure <A HREF="node127.html#figsort3" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node127.html#figsort3">11.6</A>, this is
achieved by using the hypercube communication template.  Each of the
<IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1160.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1160.gif"> tasks engages in <em> d+1</em>
 compare-exchange steps, one with
each neighbor.  In effect, each node executes
Algorithm <A HREF="node124.html#algbutalg" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node124.html#algbutalg">11.1</A>, applying the following operator at each
step.
<P>

<PRE><TT> 
		<tt> if ( myid AND <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1161.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1161.gif"> &gt; 0 ) then</tt>
<P>
				<tt> state = compare_exchange_high(state,message)</tt>
<P>
		<tt> else</tt>
<P>
				<tt> state = compare_exchange_low(state,message)</tt>
<P>
		<tt> endif</tt>
<P>
</TT></PRE>

<P>
In this code fragment, <tt> AND</tt> is a bitwise logical and operator,
used to determine whether the task is ``high'' or ``low'' in a
particular exchange; <tt> myid</tt> and <tt> i</tt> are as in
Algorithm <A HREF="node124.html#algbutalg" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node124.html#algbutalg">11.1</A>.
<P>
<H4><A NAME=SECTION04340030000000000000> Mergesort.</A></H4>
<P>
We next describe the parallel mergesort algorithm proper.  Each task in
the computation executes the following logic.
<P>
<PRE>    procedure parallel_mergesort(myid, d, data, newdata)
    begin
      data = sequential_mergesort(data)
      for dim = 1 to d
        data = parallel_merge(myid, dim, data)
      endfor
      newdata = data
    end
</PRE>
<P>
First, each task sorts its local sequence using sequential mergesort.
Second, and again using the hypercube communication structure, each of
the <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1162.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1162.gif"> tasks executes the parallel merge algorithm <em> d</em>
 times,
for subcubes of dimension 1..<em> d</em>
.  The <em> i</em>
th parallel merge
takes two sequences, each distributed over <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1163.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1163.gif"> tasks, and
generates a sorted sequence distributed over <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1164.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1164.gif"> tasks.  After
<em> d</em>
 such merges, we have a single sorted list distributed over
<IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1165.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1165.gif"> tasks.
<P>
<H4><A NAME=SECTION04340040000000000000> Performance</A></H4>
<P>
<A NAME=15185>&#160;</A>
Parallel mergesort uses the hypercube communication template at
multiple levels.  We review these uses and develop a performance
model.  We assume <em> N</em>
 data distributed over <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1166.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1166.gif"> tasks (that
is, <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1167.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1167.gif">), with <em> N</em>
 an integer multiple of <em> P</em>
.  Hence,
the total number of compare-exchanges is
<P><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1168.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1168.gif"><P>
<P>
Because each compare-exchange requires one message containing
<em> N/P</em>
 data, the per-processor communication cost is
<P>
<P><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1169.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1169.gif"><P>
<P>
The computation costs comprise the initial intraprocessor sort and the
comparisons performed during the interprocessor communication phase.
The former involves a total of <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1170.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1170.gif"> comparisons, while the
latter requires at most <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1171.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1171.gif"> comparisons, thereby giving
computation costs summed over <em> P</em>
 processors of
<P>
<P><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1172.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1172.gif"><P>
<P>
Because the algorithm is perfectly balanced, we can assume that idle
time is negligible. Thus, we obtain the following model for parallel
execution time:
<A NAME=15214>&#160;</A>
<P>
<P><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1173.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1173.gif"><P>
<A NAME=15237>&#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=tex2html3518 HREF="node126.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node126.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=tex2html3526 HREF="node128.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node128.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=tex2html3524 HREF="node123.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node123.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=tex2html3528 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=tex2html3529 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=tex2html3527 HREF="node128.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node128.html">11.5 Summary</A>
<B>Up:</B> <A NAME=tex2html3525 HREF="node123.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node123.html">11 Hypercube Algorithms</A>
<B> Previous:</B> <A NAME=tex2html3519 HREF="node126.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node126.html">11.3 Matrix Transposition</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>