node33.html

Design and building parallel program

single signal at a time.</em><A NAME=figether1>&#160;</A><BR>
<P><H4><A NAME=SECTION02472030000000000000> Ethernet.</A></H4>
<P>
<A NAME=3797>&#160;</A>
The Ethernet network often used in LANs to
connect workstations or personal computers at a departmental level is
another example of a bus-based interconnect.  As noted in
Table <A HREF="node29.html#tabmach" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node29.html#tabmach">3.1</A>,
<A NAME=3799>&#160;</A>
standard Ethernet can provide network bandwidths of up to about
1 Mbytes per second.  All computers connected via an Ethernet share a
single communication channel (Figure <A HREF="node33.html#figether1" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node33.html#figether1">3.13</A>).  A computer
that needs to send must wait until the channel is idle, then send its
message; if it detects a collision, it waits a while and then
retransmits.  Since a computer requires exclusive access to the entire
channel when sending a message, any algorithm that requires more than
one processor to communicate concurrently will suffer reduced
effective bandwidth.  Hence, the term <em> S</em>
 in
Equation <A HREF="node33.html#eqcomm1" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node33.html#eqcomm1">3.10</A> is, as in other bus-based networks, equal to
the number of simultaneous senders.  The impact of Ethernet bandwidth
limitations on performance is illustrated in the examples that follow.
<P>
<P><A NAME=4959>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img547.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img547.gif">
<BR><STRONG>Figure 3.14:</STRONG> <em> A two-dimensional torus interconnection network.  This
is a 2-D mesh with end-around connections so that each processor is
connected to four neighbors.</em><A NAME=figperfmc2>&#160;</A><BR>
<P><H4><A NAME=SECTION02472040000000000000> Mesh Networks.</A></H4>
<P>
<A NAME=3808>&#160;</A>
A mesh network can be thought of as a crossbar switch
(Figure <A HREF="node33.html#figcrossbar" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node33.html#figcrossbar">3.11</A>) in which processors are associated with
switching elements rather than being placed on the edge of the mesh.  In a
mesh network of dimension <em> D</em>
, each nonboundary processor is
connected to <em> 2D</em>
 immediate neighbors.  Connections typically
consist of two wires, one in each direction.  Two- and
three-dimensional meshes are commonly used in parallel computing. They
have the advantage over some more sophisticated networks that they can
be constructed in three-dimensional space without long wires.  In a
2-D mesh, a message is communicated from processor
<em> (i,j)</em>
 to processor <em> (k,l)</em>
 in <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img548.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img548.gif"> steps.
One-, two- and three-dimensional cubic meshes of <em> P</em>
 processors
have diameters of <em> P-1</em>
, <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img549.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img549.gif">, and <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img550.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img550.gif">
and contain <em> 2(P-1)</em>
, <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img551.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img551.gif">, and <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img552.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img552.gif"> wires,
respectively.  As illustrated in Figure <A HREF="node33.html#figperfmc2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node33.html#figperfmc2">3.14</A>, these
diameters can be halved by extending a mesh with toroidal connections
<A NAME=3821>&#160;</A>
so that boundary processors are also connected with neighbors.
<A NAME=3822>&#160;</A>
However, the torus has two disadvantages.  First, longer wires are
needed for the end-around connections in the 3-D case.  (The need for
longer wires can be avoided in a 2-D torus by folding the mesh.)
Second, a subset of a torus is not a torus, so the benefits of the
toroidal connections are lost if a torus-connected computer is
partitioned among several users.
<P>
<P><A NAME=4982>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img553.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img553.gif">
<BR><STRONG>Figure 3.15:</STRONG> <em> Competition for bandwidth in a 1-D mesh.  In (a),
processors P0 and P1 communicate and P2 and P3 communicate.  Because the two
communications use different wires, both can proceed concurrently.  In
(b), processors P0 and P2 communicate and P1 and P3 communicate.  The two
communications must both traverse the wire connecting P1 and P2;
hence, the two communications cannot proceed concurrently, and
<em> S=2</em>
.  In (c), processors P0 and P2 communicate and P3 and P1 communicate.
Because each connection is bidirectional, the two communications can
proceed concurrently.</em><A NAME=figmesh1>&#160;</A><BR>
<P>
<P>
Competition for bandwidth in a mesh network occurs when two or more
processors attempt to send over the same wire at the same time
(Figure <A HREF="node33.html#figmesh1" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node33.html#figmesh1">3.15</A>).  The analysis used to determine <em> S</em>
 for
a particular algorithm is illustrated in the examples that follow.
<P>
<P><A NAME=5003>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img554.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img554.gif">
<BR><STRONG>Figure 3.16:</STRONG> <em> Hypercubes of dimension zero through four. The processors
in the cubes of dimension 1, 2, and 3 are labeled with integers, here
represented as binary numbers. Notice that two processors are
neighbors in dimension <em> d</em>
 if and only if their binary labels
differ only in the <em> d</em>
th place.  Notice also that in a hypercube
of dimension <em> d</em>
, a message can be routed between any pair of
processors in at most <em> d</em>
 hops.</em><A NAME=fighyper>&#160;</A><BR>
<P><H4><A NAME=SECTION02472050000000000000> Hypercube Network.</A></H4>
<P>
<A NAME=3837>&#160;</A>
The hypercube network was introduced in Section <A HREF="node18.html#secbfly" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node18.html#secbfly">2.4.1</A>.  As in
<A NAME=3839>&#160;</A>
the mesh, processors in a hypercube network are associated with
<A NAME=3840>&#160;</A>
switching elements.  A <em> d</em>
-dimensional hypercube connects each of
<IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img555.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img555.gif"> processors to <em> d</em>
 other processors.  A hypercube can be
defined recursively as follows (Figure <A HREF="node33.html#fighyper" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node33.html#fighyper">3.16</A>). A
zero-dimensional hypercube is a single processor and a one-dimensional
hypercube connects two zero-dimensional hypercubes. Generally, a
hypercube of dimension <em> d+1</em>
 is constructed by connecting
corresponding processors in two hypercubes of dimension <em> d</em>
.  As
with the mesh, the competition-for-bandwidth factor <em> S</em>
 is
algorithm dependent, although the greater number of wires in the
hypercube means that competition for bandwidth tends to occur less
often.
<P>
The many interesting properties of hypercubes are beyond the scope of
this book (but see Chapter <A HREF="node123.html#chapcube" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node123.html#chapcube">11</A>).  However, we note that
when labeled as shown in Figure <A HREF="node33.html#fighyper" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node33.html#fighyper">3.16</A>, two processors are
connected if and only if the binary representation of their labels
differs in a single position.  We exploit this property when
specifying algorithms that use the hypercube communication structure.
Another important feature of a hypercube is that it contains a mesh:
it may be considered a mesh with additional, long-distance
connections.  The additional connectivity reduces the diameter to
<em> d</em>
 and increases the number of available wires, particularly for
nonlocal communication.  A disadvantage of the hypercube interconnect
from an engineering point of view is that it is more complex than the
mesh.  In particular, it requires more and longer wires, since a
hypercube with dimension greater than three cannot be laid out in three-dimensional
space so that wires connect only physically adjacent processors.
<P>
<P><A NAME=5032>&#160;</A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img556.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img556.gif">
<BR><STRONG>Figure 3.17:</STRONG> <em> Example multistage interconnection networks.  Shaded circles
represent processors and unshaded circles represent crossbar switches.
The network on the left has <em> k=2</em>
 and <em> n=3</em>
; on the right,
<em> k=4</em>
 and <em> n=2</em>
.  The network can be constructed from unidirectional
switches and links, in which case it is folded so that the processors
on the left and right are the same. Alternatively, it can be
constructed from bidirectional switches and links, in which case
processors on the left and right are
distinct.</em><A NAME=figbutt>&#160;</A><BR>
<P><H4><A NAME=SECTION02472060000000000000> Multistage Interconnection Networks.</A></H4>
<P>
In a multistage interconnection network (MIN), as in a crossbar,
switching
<A NAME=3858>&#160;</A>
elements are distinct from processors.  However, fewer than <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img557.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img557.gif">
switches are used to connect <em> P</em>
 processors.  Instead, messages
pass through a series of switch stages.  Figure <A HREF="node33.html#figbutt" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node33.html#figbutt">3.17</A>
illustrates two MINs, which are representatives of a general class of networks
characterized by parameters <em> n</em>
 and
<em> k</em>
.  These networks are sometimes referred to as radix <em> k</em>
,
dimension <em> n</em>
 butterflies, or <em> k</em>
-ary <em> n</em>
-flies.  Either
<em> n</em>
 stages of <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img558.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img558.gif"> <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img559.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img559.gif"> unidirectional crossbar
switches connect <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img560.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img560.gif"> processors, or <em> n</em>
 stages of <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img561.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img561.gif">
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img562.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img562.gif"> bidirectional crossbar switches connect <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img563.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img563.gif">
processors.  In the latter case, each link comprises two channels
that carry data in opposite directions, and each crossbar switch can
route data arriving on any of <em> 2k</em>
 inputs to any of
<em> 2k</em>
 outputs.  Notice that each stage of these networks connects
<em> P</em>
 inputs with <em> P</em>
 outputs, although not every input is directly
connected to every output in each stage.