node7.html

Design and building parallel program

<A NAME=322>&#160;</A>
that can be performed concurrently.  The time to perform a basic
<A NAME=323>&#160;</A>
operation is ultimately limited by the ``clock cycle'' of the
processor, that is, the time required to perform the most primitive operation.
However, clock cycle times are decreasing slowly and appear to be
approaching physical limits such as the speed of light
(Figure <A HREF="node7.html#figcycletime" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node7.html#figcycletime">1.2</A>).  We cannot depend on faster processors to
provide increased computational performance.
<P>

<P>
<P><A NAME=812>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img90.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img90.gif">
<BR><STRONG>Figure 1.2:</STRONG> <em> Trends in computer clock cycle times.  Conventional vector
supercomputer cycle times (denoted ``o'') have decreased only by a
factor of 3 in sixteen years, from the CRAY-1 (12.5 nanoseconds) to
the C90 (4.0).  RISC microprocessors (denoted ``+'') are fast
approaching the same performance.  Both architectures appear to be
approaching physical limits.</em><A NAME=figcycletime>&#160;</A><BR>
<P>
<P>
To circumvent these limitations, the designer may attempt to utilize
internal concurrency in a chip, for example, by operating
simultaneously on all 64 bits of two numbers that are to be
multiplied.  However, a fundamental result in Very Large Scale
<A NAME=329>&#160;</A>
Integration (VLSI) complexity theory says that this strategy is
expensive.  This result states that for certain transitive
computations (in which any output may depend on any input), the chip
area <em> A</em>
 and the time <em> T</em>
 required to perform this computation
are related so that <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img91.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img91.gif"> must exceed some problem-dependent function
of problem size.  This result can be explained informally by assuming
that a computation must move a certain amount of information from one
side of a square chip to the other.  The amount of information that
can be moved in a time unit is limited by the cross section of the
chip, <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img92.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img92.gif">.  This gives a transfer rate of <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img93.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img93.gif">, from
which the <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img94.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img94.gif"> relation is obtained.  To decrease the time required
to move the information by a certain factor, the cross section must be
increased by the same factor, and hence the total area must be
increased by the square of that factor.
<P>
This <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img95.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img95.gif"> result means that not only is it difficult to build
individual components that operate faster, it may not even be
desirable to do so.  It may be cheaper to use more, slower components.
For example, if we have an area <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img96.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img96.gif"> of silicon to use in a
computer, we can either build <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img97.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img97.gif"> components, each of size
<em> A</em>
 and able to perform an operation in time <em> T</em>
, or build a single
component able to perform the same operation in time <em> T/n</em>
.  The
multicomponent system is potentially <em> n</em>
 times faster.
<P>
Computer designers use a variety of techniques to overcome these
<A NAME=338>&#160;</A>
limitations on single computer performance, including pipelining
(different stages of several instructions execute concurrently) and
multiple function units (several multipliers, adders, etc., are
controlled by a single instruction stream).  Increasingly, designers
are incorporating multiple ``computers,'' each with its own processor,
memory, and associated interconnection logic.  This approach is
<A NAME=339>&#160;</A>
facilitated by advances in VLSI technology that continue to decrease
the number of components required to implement a computer.  As the
cost of a computer is (very approximately) proportional to the number
of components that it contains, increased integration also increases
the number of processors that can be included in a computer for a
particular cost.  The result is continued growth in processor counts
(Figure <A HREF="node7.html#figprocs" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node7.html#figprocs">1.3</A>).
<P>

<P>
<P><A NAME=833>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img98.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img98.gif">
<BR><STRONG>Figure 1.3:</STRONG> <em> Number of processors in massively parallel computers
(``o'') and vector multiprocessors (``+'').  In both cases, a steady
increase in processor count is apparent.  A similar trend is starting
to occur in workstations, and personal computers can be expected to
follow the same trend.</em><A NAME=figprocs>&#160;</A><BR>
<P><H2><A NAME=SECTION02213000000000000000>1.1.3 Trends in Networking</A></H2>
<P>
<A NAME=346>&#160;</A>
Another important trend changing the face of computing is an enormous
<A NAME=347>&#160;</A>
increase in the capabilities of the networks that connect computers.
Not long ago, high-speed networks ran at 1.5 Mbits per second; by the
end of the 1990s, bandwidths in excess of 1000 Mbits per second will
be commonplace.  Significant improvements in reliability are also
expected.  These trends make it feasible to develop applications that
use physically distributed resources as if they were part of the same
computer.  A typical application of this sort may utilize processors
on multiple remote computers, access a selection of remote databases,
perform rendering on one or more graphics computers, and provide
real-time output and control on a workstation.
<P>
<A NAME=348>&#160;</A>
We emphasize that computing on networked computers
(``distributed computing'') is not just a subfield of parallel
computing.  Distributed computing is deeply concerned with problems
such as reliability, security, and heterogeneity that are generally
regarded as tangential in parallel computing.  (As Leslie Lamport has
observed, ``A distributed system is one in which the failure of a
computer you didn't even know existed can render your own computer
unusable.'')  Yet the basic task of developing programs that can run
on many computers at once is a parallel computing problem.  In this
respect, the previously distinct worlds of parallel and distributed
computing are converging.
<P>
<H2><A NAME=SECTION02214000000000000000>1.1.4 Summary of Trends</A></H2>
<P>
This brief survey of trends in applications, computer architecture,
and networking suggests a future in which parallelism pervades not only
supercomputers but also workstations, personal computers, and
networks.  In this future, programs will be required to exploit the
multiple processors located inside each computer and the additional
processors available across a network.  Because most existing algorithms
<A NAME=350>&#160;</A>
are specialized for a single processor, this situation implies a need
<A NAME=351>&#160;</A>
for new algorithms and program structures able to perform many
operations at once.  <em> Concurrency
 </em> becomes a fundamental
requirement for algorithms and programs.
<P>
This survey also suggests a second fundamental lesson.  It appears
likely that processor counts will continue to increase---perhaps, as
they do in some environments at present, by doubling each year or two.
Hence, software systems can be expected to experience substantial
increases in processor count over their lifetime.  In this
<A NAME=353>&#160;</A>
environment, <em> scalability
 </em>---resilience to increasing
<A NAME=355>&#160;</A>
processor counts---is as important as portability for protecting
software investments.  A program able to use only a fixed number of
processors is a bad program, as is a program able to execute on only a
single computer.  Scalability is a major theme that will be stressed
throughout this book.
<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=tex2html1918 HREF="node6.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node6.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=tex2html1926 HREF="node8.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node8.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=tex2html1924 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=tex2html1928 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=tex2html1929 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=tex2html1927 HREF="node8.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node8.html">1.2 A Parallel Machine Model</A>
<B>Up:</B> <A NAME=tex2html1925 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=tex2html1919 HREF="node6.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node6.html">1 Parallel Computers and Computation</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>