📄 node37.html
字号:
<html><!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 95.1 (Fri Jan 20 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE> Exercises</TITLE>
</HEAD>
<BODY>
<meta name="description" value=" Exercises">
<meta name="keywords" value="book">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<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=tex2html2297 HREF="node36.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node36.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=tex2html2305 HREF="node38.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node38.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=tex2html2303 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=tex2html2307 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=tex2html2308 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=tex2html2306 HREF="node38.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node38.html"> Chapter Notes</A>
<B>Up:</B> <A NAME=tex2html2304 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=tex2html2298 HREF="node36.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node36.html">3.10 Summary</A>
<BR><HR><P>
<H1><A NAME=SECTION024110000000000000000> Exercises</A></H1>
<P>
The exercises in this chapter are designed to provide experience in
the development and use of performance models. When an exercise asks
you to implement an algorithm, you should use one of the programming
tools described in Part II.
<P>
<OL><LI>
Discuss the relative importance of the various performance metrics
listed in Section <A HREF="node27.html#secmetrics" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node27.html#secmetrics">3.1</A> when designing a parallel
floorplan optimization program for use in VLSI design.
<P>
<LI>
Discuss the relative importance of the various performance metrics
listed in Section <A HREF="node27.html#secmetrics" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node27.html#secmetrics">3.1</A> when designing a video server that
uses a parallel computer to generate many hundreds of thousands of
concurrent video streams. Each stream must be retrieved from disk,
decoded, and output over a network.
<P>
<LI>
<A NAME=exch21> </A>
The self-consistent field (SCF) method in computational chemistry
<A NAME=4248> </A>
involves two operations: Fock matrix construction and matrix
<A NAME=4249> </A>
diagonalization. Assuming that diagonalization accounts for 0.5 per
cent of total execution time on a uniprocessor computer, use Amdahl's
law to determine the maximum speedup that can be obtained if only the
Fock matrix construction operation is parallelized.
<P>
<LI>
You are charged with designing a parallel SCF program. You estimate
your Fock matrix construction algorithm to be 90 percent efficient on
your target computer. You must choose between two parallel
diagonalization algorithms, which on five hundred processors achieve
speedups of 50 and 10, respectively. What overall efficiency do you
expect to achieve with these two algorithms? If your time is as
valuable as the computer's, and you expect the more efficient
algorithm to take one hundred hours longer to program, for how many
hours must you plan to use the parallel program if the more efficient
algorithm is to be worthwhile?
<P>
<LI>
Some people argue that in the future, processors will become
essentially free as the cost of computers become dominated by the
cost of storage and communication networks. Discuss how this
situation may affect algorithm design and performance analysis.
<P>
<LI>
Generate an execution profile similar to that in Figure <A HREF="node30.html#figfdcomp" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node30.html#figfdcomp">3.8</A> for
an implementation of a parallel finite difference algorithm based on a
2-D decomposition. Under which circumstances will message startups
contribute more to execution time than will data transfer costs?
<P>
<LI>
<A NAME=experf2> </A>
Derive expressions that indicate when a 2-D decomposition of a finite
difference computation on an <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img699.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img699.gif"> grid will be superior
to a 1-D decomposition and when a 3-D decomposition will be superior
to a 2-D decomposition. Are these conditions likely to apply in
practice? Let <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img700.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img700.gif">sec, <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img701.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img701.gif">sec, <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img702.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img702.gif">sec, and
<em> P=1000</em>
. For what values of <em> N</em>
does the use of a 3-D
decomposition rather than a 2-D decomposition reduce execution time by
more than 10 percent?
<P>
<LI>
<A NAME=experf3> </A>
Adapt the analysis of Example <A HREF="node30.html#experfgrid" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node30.html#experfgrid">3.4</A> to consider 1-D and
2-D decompositions of a 2-D grid. Let
<em> N=1024</em>
, and fix other parameters as in Exercise <A HREF="node37.html#experf2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node37.html#experf2">7</A>. For
what values of <em> P</em>
does the use of a 2-D decomposition rather than
a 1-D decomposition reduce execution time by more than 10 percent?
<P>
<LI>
<A NAME=experf99> </A>
Implement a simple ``ping-pong'' program that bounces messages between
a pair of processors. Measure performance as a function of message
size on a workstation network and on one or more parallel computers.
Fit your results to Equation <A HREF="node29.html#eq88" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node29.html#eq88">3.1</A> to obtain values for <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img703.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img703.gif">
and <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img704.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img704.gif">. Discuss the quality of your results and of the fit.
<P>
<LI>
<A NAME=experf4> </A>
Develop a performance model for the program constructed in
Exercise <A HREF="node24.html#exfd87" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node24.html#exfd87">5</A> in Chapter <A HREF="node14.html#chap2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node14.html#chap2">2</A> that gives execution
time as a function of <em> N</em>
, <em> P</em>
, <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img705.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img705.gif">, <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img706.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img706.gif">, and <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img707.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img707.gif">.
Perform empirical studies to determine values for <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img708.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img708.gif">, <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img709.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img709.gif">, and
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img710.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img710.gif"> on different parallel computer systems. Use the results of
these studies to evaluate the adequacy of your model.
<P>
<LI>
Develop performance models for the parallel algorithms developed in
Exercise <A HREF="node24.html#exgs" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node24.html#exgs">10</A> in Chapter <A HREF="node14.html#chap2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node14.html#chap2">2</A>. Compare these models
with performance data obtained from implementations of these
algorithms.
<P>
<LI>
Determine the isoefficiency function for the program developed in
Exercise <A HREF="node37.html#experf4" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node37.html#experf4">10</A>. Verify this experimentally.
<P>
<LI>
Use the ``ping-pong'' program of Exercise <A HREF="node37.html#experf99" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node37.html#experf99">9</A> to study
the impact of bandwidth limitations on performance, by writing a
program in which several pairs of processors perform exchanges
concurrently. Measure execution times on a workstation network and on
one or more parallel computers. Relate observed performance to
Equation <A HREF="node33.html#eqcomm1" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node33.html#eqcomm1">3.10</A>.
<P>
<LI>
Implement the parallel summation algorithm of Section <A HREF="node18.html#secbfly" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node18.html#secbfly">2.4.1</A>.
Measure execution times as a function of problem size on a network of
workstations and on one or more parallel computers. Relate observed
performance to the performance models developed in this chapter.
<P>
<LI>
Determine the isoefficiency function for the butterfly summation
algorithm of Section <A HREF="node18.html#secbfly" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node18.html#secbfly">2.4.1</A>, with and without bandwidth
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -