node28.html

Design and building parallel program

 and problem size <em> N</em>
.  In
each case, we assume that the total computation performed by an
optimal sequential algorithm scales as <em> N+N</em>
<IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img361.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img361.gif">.
<P>
<OL><LI>
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img362.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img362.gif">.  This algorithm partitions the computationally
demanding <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img363.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img363.gif"> component of the algorithm but replicates the
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img364.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img364.gif"> component on every processor.  There are no other sources of
overhead.
<P>
<LI>
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img365.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img365.gif">.  This algorithm partitions all the
computation but introduces an additional cost of 100.
<P>
<LI>
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img366.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img366.gif">.  This algorithm also partitions all the
computation but introduces an additional cost of <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img367.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img367.gif">.
</OL>
<P>
These algorithms all achieve a speedup of about 10.8 when
<em> P=12</em>
 and <em> N=100</em>
.  However, they behave differently in other
situations, as illustrated in Figure <A HREF="node28.html#figperf3" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node28.html#figperf3">3.1</A>.  With
<em> N=100</em>
, all three algorithms perform poorly for larger <em> P</em>
,
although Algorithm (3) does noticeably worse than the other two.  When
<em> N=1000</em>
, Algorithm (2) is significantly better than Algorithm (1)
for larger <em> P</em>
.
<P>
<P><A NAME=4514>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img368.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img368.gif">
<BR><STRONG>Figure 3.1:</STRONG> <em> Efficiency as a function of <em> P</em>
 for three different
algorithms (described in the text).  The upper figure is for
<em> N=100</em>
, and the lower figure is for <em> N=1000</em>
.  Notice the use
of logarithmic scales.  When <em> N=100</em>
, Algorithms (1) and (2) are
indistinguishable.</em><A NAME=figperf3>&#160;</A><BR>
<P><H2><A NAME=SECTION02423000000000000000>3.2.3 Asymptotic Analysis</A></H2>
<P>
<A NAME=3135>&#160;</A>
Textbooks frequently characterize the performance of parallel
algorithms by stating something like the following:
<blockquote> <A NAME=3137>&#160;</A>
Asymptotic analysis reveals that the algorithm requires <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img369.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img369.gif"> time on <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img370.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img370.gif"> processors.
</blockquote>
That is, there exists a constant <em> c</em>
 and minimum problem size
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img371.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img371.gif"> such that for all <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img372.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img372.gif">, cost<em> (N)</em>
 <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img373.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img373.gif"> on
<em> N</em>
 processors. This relationship tells how cost varies with <em> N</em>
 when
<em> N</em>
 and <em> P</em>
 are large.
<P>
<A NAME=3145>&#160;</A>
While this information is interesting, it is often not directly
relevant to the task of developing an efficient parallel program.
Because it deals with large <em> N</em>
 and <em> P</em>
, it ignores
lower-order terms that may be significant for problem sizes and
processor counts of practical interest.  For example, the actual cost
of an algorithm with asymptotic complexity of <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img374.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img374.gif"> might be
<em> 10 N + N</em>
 <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img375.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img375.gif">.  The <em> 10 N</em>
 component is larger
for <em> N&lt;1024</em>
 and must be incorporated in a performance model if
problems of interest are in this regime.  A second deficiency of
asymptotic analysis is that it says nothing about absolute cost.
Asymptotic analysis would suggest that an algorithm with cost
<em> 1000 N</em>
 <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img376.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img376.gif"> is superior to an algorithm with cost <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img377.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img377.gif">.
However, the latter is faster for <em> N&lt;996</em>
, which again may be the
regime of practical interest.  A third deficiency is that such
analyses frequently assume idealized machine models that are very
different from the physical computers for which we develop programs.
<A NAME=3153>&#160;</A>
For example, they may assume the PRAM model, in which communication
costs are assumed to be nil.
<P>
Asymptotic analysis has a role to play in parallel program design.
However, when evaluating asymptotic results, we must be careful to
identify the machine model for which the results are obtained, the
coefficients that are likely to apply, and the <em> N</em>
 and
<em> P</em>
 regime in which the analyses hold.
<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=tex2html2189 HREF="node27.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node27.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=tex2html2197 HREF="node29.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node29.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=tex2html2195 HREF="node26.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node26.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=tex2html2199 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=tex2html2200 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=tex2html2198 HREF="node29.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node29.html">3.3 Developing Models</A>
<B>Up:</B> <A NAME=tex2html2196 HREF="node26.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node26.html">3 A Quantitative Basis for Design</A>
<B> Previous:</B> <A NAME=tex2html2190 HREF="node27.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node27.html">3.1 Defining Performance</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>