node31.html

Design and building parallel program

resend when messages collide.  An unfortunate schedule can result in
repeated resendings, thereby increasing execution time.  In
Section <A HREF="node33.html#secperfrefine" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node33.html#secperfrefine">3.7</A>, we describe advanced modeling
techniques that can account for some such effects.
<P>
<LI>
<em> Random resource allocation.</em> The operating system may use a
random processor allocation strategy, which will affect execution
times if communication costs depend on processor location in a network
(see Section <A HREF="node33.html#secperfrefine" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node33.html#secperfrefine">3.7</A>).  If possible, the same allocation
should be used for all experiments.
</UL>
<P>
Studies of variability in experimental results can help us to identify
sources of error or uncertainty in our measurements.  However, even
when results are reproducible, we still have no assurance that they
are correct.  Confidence in our results can be increased by measuring
the same thing several different ways and verifying that the results
of these redundant measurements are consistent.  For example, in
addition to measuring the time taken in individual program components,
we can measure the total time for the entire program.
<P>
<H2><A NAME=SECTION02453000000000000000>3.5.3 Fitting Data to Models</A></H2>
<P>
<A NAME=3524>&#160;</A>
When experimental studies are performed for calibration purposes, we
<A NAME=3525>&#160;</A>
fit results to the function of interest to obtain values for unknown
parameters.  A fit can be performed graphically by plotting data
points and estimating the fit.  For example, if the function is
<P><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img488.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img488.gif"><P>
we can plot the data points <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img489.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img489.gif"> as a function of
<em> L</em>
 and draw a straight line that fits these points.  The slope
of this line will be <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img490.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img490.gif">, and the intercept of the <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img491.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img491.gif"> axis
when <em> L=0</em>
 will be <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img492.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img492.gif">.
<P>
<A NAME=3533>&#160;</A>
Alternatively, and more accurately, we can perform a least-squares fit
of the function with the data.  (Mathematical packages such as
Mathematica and Matlab incorporate fitting functions.)  A
least-squares fit involves a minimization of the sum of the squares of
the differences between the observations, <tt> obs</tt><em> (i)</em>
, and the
corresponding function values, <tt> f</tt><em> (i)</em>
:
<P><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img493.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img493.gif"><P>
<P>
For example, when fitting the function <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img494.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img494.gif"> with observations
of <em> T</em>
 for different values of <em> N</em>
 in order to determine the
value <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img495.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img495.gif">, we minimize
<P><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img496.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img496.gif"><P>
<P>
When fitting to execution times for different numbers of processors,
the method just described gives less weight to the (presumably
smaller) times on larger numbers of processors.  Yet these are
typically the times of greatest interest.  Hence, we can use a <em>
scaled
 </em> least-squares fit in which the difference between
observation and function value is scaled by the observation, as
follows:
<P>
<P><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img497.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img497.gif"><P>
<P>
<BR><HR>
<b> Example <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img509.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img509.gif">.<IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img498.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img498.gif">    Determining Computation Time (<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img499.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img499.gif">)</b>:<A NAME=exfdc>&#160;</A>
<P>
We consider the problem of determining the computation cost per grid
<A NAME=3557>&#160;</A>
point in the finite difference problem.  Recall that we have modeled
this cost as follows (Equation <A HREF="node29.html#eq87" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node29.html#eq87">3.2</A>):
<P><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img500.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img500.gif"><P>
In this equation, <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img501.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img501.gif"> is the parameter that we wish to determine,
and <em> N</em>
 is a value that we can vary while measuring performance.
(For simplicity, we keep <em> Z</em>
 fixed.)  Table <A HREF="node31.html#tabfd" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node31.html#tabfd">3.2</A> gives
execution times measured on a Sun SPARC 2 workstation.  Experiments
were performed when the machine was idle but not in single-user mode;
hence, there might have been a small amount of background activity.
Each experiment was repeated three times so that we could study
variability; the table also lists the means of each set of three
values.  The repeated experiments show little variation in total
execution time.
<P>
<P><A NAME=4471>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img502.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img502.gif">
<BR><STRONG>Table 3.2:</STRONG>  Execution times in milliseconds for a single time step
of the finite difference code on a Sun SPARC 2, with
<em> Z=10</em>
.
<A NAME=tabfd>&#160;</A><BR>
<P>
<P>
<P><A NAME=4831>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img505.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img505.gif">
<BR><STRONG>Figure 3.9:</STRONG> <em> Simple and scaled least-squares fits of the function
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img504.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img504.gif"> to finite difference execution times on a Sun SPARC 2
workstation.  Notice the use of logarithmic
scales.</em><A NAME=figstuff>&#160;</A><BR>
<P>
<P>
<A NAME=3580>&#160;</A>
<P>
<P><A NAME=4472>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img506.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img506.gif">
<BR><STRONG>Table 3.3:</STRONG>  Execution times predicted for finite difference code on
Sun SPARC 2, with <em> Z=10</em>
 (milliseconds).
<A NAME=tabfd2>&#160;</A><BR>
<P>
<P>
Figure <A HREF="node31.html#figstuff" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node31.html#figstuff">3.9</A> shows simple and scaled least-squares fits of
Equation <A HREF="node29.html#eq87" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node29.html#eq87">3.2</A> to the data in Table <A HREF="node31.html#tabfd" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node31.html#tabfd">3.2</A>.  The two fits
correspond to <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img507.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img507.gif"> values of 0.0120 msec and 0.0112 msec,
respectively.  The execution times predicted by the two models are
<A NAME=3598>&#160;</A>
<A NAME=3599>&#160;</A>
shown in Table <A HREF="node31.html#tabfd2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node31.html#tabfd2">3.3</A>.  As expected, the simple fit is more
accurate for larger <em> N</em>
, while the scaled fit is better for
smaller <em> N</em>
; both are good enough for most practical purposes.
These results suggest that the hypothesized performance model, <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img508.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img508.gif">, is an adequate characterization of finite difference
computation time.
<P>
<BR><HR>
<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=tex2html2225 HREF="node30.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node30.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=tex2html2233 HREF="node32.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node32.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=tex2html2231 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=tex2html2235 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=tex2html2236 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=tex2html2234 HREF="node32.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node32.html">3.6 Evaluating Implementations</A>
<B>Up:</B> <A NAME=tex2html2232 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=tex2html2226 HREF="node30.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node30.html">3.4 Scalability Analysis</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>