📄 node12.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=tex2html1978 HREF="node11.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node11.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=tex2html1986 HREF="node13.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node13.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=tex2html1984 HREF="node6.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node6.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=tex2html1988 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=tex2html1989 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=tex2html1987 HREF="node13.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node13.html"> Chapter Notes</A>
<B>Up:</B> <A NAME=tex2html1985 HREF="node6.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node6.html">1 Parallel Computers and Computation</A>
<B> Previous:</B> <A NAME=tex2html1979 HREF="node11.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node11.html">1.5 Summary</A>
<BR><HR><P>
<H1><A NAME=SECTION02260000000000000000> Exercises</A></H1>
<P>
Exercises <A HREF="node12.html#ex1" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node12.html#ex1">6</A>--<A HREF="node12.html#exn" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node12.html#exn">10</A> require you to describe a parallel
algorithm. You should describe the task/channel structure created by
the algorithm and provide a definition for each task, including its
interface (inports and outports), its local data, and the actions it
performs.
<P>
<OL><LI>
If today's workstations execute at <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img148.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img148.gif"> operations per second, and
performance increases at a rate of 25 percent per year, how long will
it be before we have workstations capable of <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img149.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img149.gif"> operations per
second? <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img150.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img150.gif">?
<P>
<LI>
A climate model requires <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img151.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img151.gif"> floating point operations for a
ten-year simulation. How long would this computation take at <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img152.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img152.gif">
floating point operations per second (10 Mflops)?
<P>
<LI>
A climate model generates <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img153.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img153.gif"> bytes of data in a ten-day
simulation. How fast must data be transferred to secondary storage?
What transfer rate is required if we are to search this data in ten
minutes?
<P>
<LI>
Consider a three-dimensional chip. Demonstrate that chip volume
<em> V</em>
and computation time <em> T</em>
are related as <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img154.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img154.gif">, just as area
<em> A</em>
and computation time are related as <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img155.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img155.gif"> in a
two-dimensional chip.
<P>
<LI>
Execute the parallel algorithm described in Section <A HREF="node10.html#exfd" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node10.html#exfd">1.4.1</A> by
hand for <em> N=4</em>
, and satisfy yourself that execution is
deterministic.
<P>
<LI>
<A NAME=ex1> </A>
Adapt the parallel algorithm of Section <A HREF="node10.html#exfd" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node10.html#exfd">1.4.1</A> to deal with a
two-dimensional finite difference problem in which the value of each
point <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img156.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img156.gif"> in a two-dimensional grid of size
<em> N</em>
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img157.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img157.gif"><em> N</em>
is updated as follows:
<P>
<P><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img158.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img158.gif"><P>
<P>
<LI>
Describe a variant of the parallel algorithm of
Section <A HREF="node10.html#exinteractions" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node10.html#exinteractions">1.4.2</A> that allows for the case when <em> N</em>
is
even.
<P>
<LI>
Describe a parallel algorithm for Hoare's quicksort
algorithm [<A HREF="node132.html#Quicksort" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node132.html#Quicksort">153</A>] based on the parallel divide-and-conquer
strategy employed in Section <A HREF="node10.html#exsearch1" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node10.html#exsearch1">1.4.3</A>.
<P>
<LI>
Describe a task/channel structure for a parallel database system in
which <em> M</em>
concurrently executing users can generate requests to
read and write data located in <em> N</em>
databases and requests to
access different databases can be handled concurrently. You must use
less than <em> M.N</em>
channels.
<P>
Extend this structure to allow a user to request that a set of read
and write operations be performed as an atomic operation, that is,
without read or write operations generated by other tasks intervening.
<P>
<LI>
<A NAME=exn> </A>
Extend the parallel algorithms of Sections <A HREF="node10.html#exfd" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node10.html#exfd">1.4.1</A>
and <A HREF="node10.html#exsearch1" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node10.html#exsearch1">1.4.3</A> to provide for the loading of initial data
values in from disk and the writing out of the solutions to disk.
<P>
</OL>
<P>
<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=tex2html1978 HREF="node11.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node11.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=tex2html1986 HREF="node13.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node13.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=tex2html1984 HREF="node6.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node6.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=tex2html1988 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=tex2html1989 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=tex2html1987 HREF="node13.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node13.html"> Chapter Notes</A>
<B>Up:</B> <A NAME=tex2html1985 HREF="node6.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node6.html">1 Parallel Computers and Computation</A>
<B> Previous:</B> <A NAME=tex2html1979 HREF="node11.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node11.html">1.5 Summary</A>
<BR><HR><P>
<P><ADDRESS>
<I>© 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>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -