two major factors used to categorize such systems Flashcards
two major factors
used to categorize such systems
processing units
interconnection networks
is performed
by writing to and reading from the global memory
Communication in shared memory systems
plays a major role in determining the communication
speed.
interconnection network
Two schemes are introduced,
static and dynamic interconnection networks
when the system is designed rather than when the connection is needed
Static networks
messages must be routed along established links
Static networks
networks establish connections between two or more nodes on the fly as messages
are routed along the links.
Dynamic interconnection
static networks
hypercube
mesh
k-ary n-cube topologies
dynamic interconnection networks
bus, crossbar, and multistage interconnection
topologies
An interconnection network could be either static or dynamic
true
Connections
in a static network are
fixed links
connections in a dynamic network
established on the fly as needed
Static networks can be further classified according
to their interconnection pattern as
one-dimension (1D), two-dimension (2D), or
hypercube (HC).
Dynamic networks, on the other hand, can be classified based on
interconnection scheme
bus-based versus switch-based.
can further be classified as single bus or multiple buses.
Bus-based networks
can be classified according to the structure of the interconnection network as
single-stage (SS), multistage (MS), or crossbar networks
Switch-based dynamic networks
is considered the simplest way to connect multiprocessor systems.
single bus
The use of multiple buses to connect multiple processors is a natural extension to the
single shared bus system.
true
uses several parallel
buses to interconnect multiple processors and multiple memory modules.
multiple bus multiprocessor system
bus can be classified
synchronous or asynchronous
Asynchronous
bus
depends on the availability of data and the readiness of
devices to initiate bus transactions.
The time for any transaction
over a synchronous bus is known in advance
true
The process of passing bus mastership from one processor
to another is called
handshaking
The process of passing bus mastership from one processor
to another is called handshaking and requires the use of two control signals
bus
request and bus grant
The process of passing bus mastership from one processor
to another is called handshaking and requires the use of two control signals
bus
request and bus grant
Three basic interconnection topologies
crossbar,
single-stage,
and multistage.
represents the other extreme to the limited single bus network
crossbar network
a single stage of switching elements (SEs) exists between the inputs and the outputs of the network.
introduced as a means to improve
some of the limitations of the single bus system while keeping the cost within an
affordable limit.
Multistage interconnection networks (MINs)
possess the property that in the presence
of a currently established interconnection between a pair of input/output, the arrival
of a request for a new interconnection between two arbitrary unused input and output
may or may not be possible.
Blocking networks
characterized by the
property that it is always possible to rearrange already established connections in
order to make allowance for other connections to be established simultaneously.
Rearrangeable networks
characterized by the property
that in the presence of a currently established connection between any pair of
input/output, it will always be possible to establish a connection between any arbitrary
unused pair of input/output.
Nonblocking networks
Static (fixed) interconnection networks
characterized by having fixed paths, unidirectional
or bidirectional, between processors.
Two types of static networks can be
identified
completely connected networks (CCNs) and limited connection
networks (LCNs)
each node is connected to all other nodes
in the network.
completely connected network (CCN)
guarantee fast delivery of messages
from any source node to any destination node (only one link has to be traversed)
completely connected network (CCN)
expensive in terms of the number of links needed
for their construction.
completely connected network (CCN)
do not provide a direct link from every node to
every other node in the network.
Limited connection networks (LCNs)
A number of regular interconnection patterns have evolved over the years for
LCNs These patterns includ
. linear arrays;
. ring (loop) networks;
. two-dimensional arrays (nearest-neighbor mesh);
. tree networks; and
. cube networks.
each node is connected to its two immediate neighboring nodes.
linear array
of which the binary tree (shown in Fig. 2.16d) is a special case,
if a node at level i (assuming that the root node is at level 0) needs to communicate
with a node at level j, where i . j and the destination node belongs to the same root’s
(a) (b)
(c) (d)
(e)
Figure 2.16 Examples of static limited connected networks (a) a linear array network;
(b) a ring network; (c) a two-dimensional array (mesh) network; (d) a tree network; and
(e) a three-cube network.
36 MULTIPROCESSORS INTERCONNECTION NETWORKS
TEAM LinG - Live, Informative, Non-cost and Genuine !
child subtree, then it will have to send its message up the tree traversing nodes at
levels i 1, i 2, . . . , j þ 1 until it reaches the destination node.
tree network
are patterned after the n-cube structure
Cube-connected networks
each node has a degree n. The degree of a node is defined as the
number of links incident on the node
n-cube
can be defined as an interconnection structure that has K0
K1 Kn1 nodes where n is the number of dimensions of the network and Ki is
the radix of dimension i. Figure 2.18 shows an example of a 3 3 2 mesh network.
n-dimensional mesh
is a radix k cube with n dimensions.
k-ary n-cube network
The cost of the crossbar system can be measured in terms of the
number of switching elements (cross points) required inside the crossbar.
each node is connected to all other nodes in the network.
Completely Connected Networks (CCNs)
each node is connected to
its two immediate neighboring nodes.
Linear Array Networks
a given node is connected to both
its parent node and to its children nodes.
Tree Networks
has 2n nodes where two nodes
are connected if the binary representation of their addresses differs by one and only
one bit.
Cube-Connected Networks
connects n n nodes in a
2D manner such that a node whose position is (i, j) is connected to its neighbors at
positions (i+1, j+1)
Mesh-Connected Networks
is a radix k cube
with n dimensions. The number of nodes in a k-ary n-cube is N ¼ kn.
The k-ary n-Cube Networks
