COMP5426 Distributed
Parallel A
Interconnects are links (wires, fiber).
Copyright By PowCoder代写 加微信 powcoder
Interconnection networks carry data between processors and to memory.
Static networks consist of point-to-point communication links among processing nodes
so referred to
Dynamic networks are built using switches
of switches an
munication links. Dynamic networks
referred to as indirect networks.
ct networks.
ne is designed
Static networks form all connections when
the connection is needed. In a static network, messages must be routed alon
links. This
message must hop through intermediate
Dynamic networks establish
en two or more nodes
messages are routed along t
r than when
eans a single
destination.
a connection
on the fly as
Topologies
iety of network
been proposed and implemented.
These topol
ogies trade
performance for cost and scalability.
Commercial machines often impleme hybrids of multiple topologies for
asons of pa
ailable components.
topologies have
Static Network Topologies:
essor is conn
The number of links in the network
scales as O(p2).
ile the performance scales very
hardware complexity is n
values of p.
Static Network Topologies:
Every node
the center.
Distance between any pair However, the central node
only to a c
ommon node at
of nodes is O(1). becomes a bottleneck.
Static Network
A further generalization t nodes with 2d neighbors.
A special case of a d-dimensio hypercube. Here, d = log p, wh
Topologies:
eshes, and
In a linear array, each node has two neighbors, one to its left and one to its right. If the nodes at either end are connected, we
A generalization to 2 dimensions has nodes with 4 neighbors, to the north, south, east,
nal mesh ere p is t
Static Network
Topologies:
Linear arrays: (a) with
no wraparound
links; (b)
aparound link.
Network Topologies:
Two and three dimensional meshes: (a) with no wraparound; (b) 2-D mesh with link (2-D torus); and (c) a 3-D mesh wit
2-D mesh wraparound
Static Network Topologies:
their Constru
Static Network Topologies:
Properties
most log p.
log p neighbors.
The distance between any two n
The distance between two nodes is
given by th
at which the
two nodes differ.
Static Network Topologies:
Dynamic Network Top
Links higher up the
more traffic than t
The distance between any two
For this reason, a variant called a fat-tree,
rossings. rees.
can be laid out in 2D with no wire
tree potentially carry
the lower leve
an attractive property of
Dynamic Network
All processors ac exchanging data.
However, the bandwidth is a major bottleneck.
Typical bus
dozens of nodes.
ed machine
cess a common
The distance between any two node O(1) in a bus. The bus also provides convenient broadcast media.
Dynamic Network
Dynamic Network
grows as O(p2).
is generally diffic
values of p.
crossbar o
Dynamic Network
Multistage
Multistage inte
compromise between
poor performance scalability.
excellent performanc
ility, but poor cost scalability.
ects strike
scalability,
these extremes.
Dynamic Network
Multistage
Dynamic Network
the most commonly
s network cons
interconne
where p is the number of inputs/outputs.
f log p stages,
Dynamic Network
Dynamic Network
The perfect shu connected using
ffle patterns are p/2 2×2 switches.
he 2×2 switches operate in two mod pass-through or crossover.
Dynamic Network
An omega networ
k has p/2 × log p switching nodes,
h a network grow
O(p log p).
Multistage
Let s be the binary r
p switching Note that t
ce and d be that
The data traverses the link switching node. If the most
routed in pass-through mode by the switch else, it switches to crossover.
stages. his is not
epresentation of the
non-blocking
to the first significant bits
Multistage
Evaluating In
Diameter: The distance betwe
two nodes in the network. The diameter of
ear array is p −
1, that of
at of a tree and hypercube is log p, and t
completely connected network is O(1).
Arc Connectivity: the minimum number of a that must be removed from the network to break it into two disconnected network.
Bisection Width:
must be cut to
equal parts. The bisection width of a linear
array and tree is 1, that of a mesh is
of a hypercube is p/2 and that of a completely connected network is p2/4.
a mesh is 2(
mum number
Evaluating In
network, the lengt
Cost: The number of links or switches
(whichever
symptotically higher) is
a meaningful measure of the cost. However, a number of other factors,
h of wires, etc., also
Evaluating In
Evaluating In
The total time to tran a network comprises o
programming r
Startup time (ts): Time spent at sending receiving nodes (executing the routing
algorithm,
time (th): This
number of hops and includes factors such as
switch latencies, network delays, etc.
Per-word transfer time (tw): This time incl all overheads that are determined by the l
of the message. This includes bandwidth of
links, error checking
sfer a message over f the following:
function of
ection, etc.
Simplified
we can approximat
transfer by
cally smaller
cost of message
ication Costs in
It is important to note that the original expression for communication time is valid for only uncongested networks
The actual cost of communication is dependent on a variety of features including the programming model semantics, the network topology, dat handling and routing, and associated software protocols
Parallel Machines
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com