|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 577-578 out of 1137
Modern Operating Systems by Herbert Bos and Andrew...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Modern Operating Systems by Herbert...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Page 577
546
MULTIPLE PROCESSOR SYSTEMS
CHAP. 8
8.2.1 Multicomputer Hardware
The basic node of a multicomputer consists of a CPU, memory, a network in-
terface, and sometimes a hard disk. The node may be packaged in a standard PC
case, but the monitor, keyboard, and mouse are nearly always absent.
Sometimes
this configuration is called a
headless workstation
because there is no user with a
head in front of it.
A workstation with a human user should logically be called a
‘‘headed workstation,’’ but for some reason it is not.
In some cases, the PC con-
tains a 2-way or 4-way multiprocessor board, possibly each with a dual-, quad- or
octa-core chip, instead of a single CPU, but for simplicity, we will assume that
each node has one CPU.
Often hundreds or even thousands of nodes are hooked
together to form a multicomputer. Below we will say a little about how this hard-
ware is organized.
Interconnection Technology
Each node has a network interface card with one or two cables (or fibers) com-
ing out of it. These cables connect either to other nodes or to switches.
In a small
system, there may be one switch to which all the nodes are connected in the star
topology of Fig. 8-16(a).
Modern switched Ethernets use this topology.
(a)
(d)
(b)
(e)
(c)
(f)
Figure 8-16.
Various interconnect topologies.
(a) A single switch. (b) A ring.
(c) A grid. (d) A double torus.
(e) A cube. (f) A 4D hypercube.
Page 578
SEC. 8.2
MULTICOMPUTERS
547
As an alternative to the single-switch design, the nodes may form a ring, with
two wires coming out the network interface card, one into the node on the left and
one going into the node on the right, as shown in Fig. 8-16(b). In this topology, no
switches are needed and none are shown.
The
grid
or
mesh
of Fig. 8-16(c) is a two-dimensional design that has been
used in many commercial systems.
It is highly regular and easy to scale up to large
sizes. It has a
diameter
, which is the longest path between any two nodes, and
which increases only as the square root of the number of nodes.
A variant on the
grid is the
double torus
of Fig. 8-16(d), which is a grid with the edges connected.
Not only is it more fault tolerant than the grid, but the diameter is also less because
the opposite corners can now communicate in only two hops.
The
cube
of Fig. 8-16(e) is a regular three-dimensional topology.
We have il-
lustrated a 2
×
2
×
2 cube, but in the most general case it could be a
k
×
k
×
k
cube. In Fig. 8-16(f) we have a four-dimensional cube built from two three-dimen-
sional cubes with the corresponding nodes connected.
We could make a five-
dimensional cube by cloning the structure of Fig. 8-16(f) and connecting the cor-
responding nodes to form a block of four cubes.
To go to six dimensions, we could
replicate the block of four cubes and interconnect the corresponding nodes, and so
on. An
n
-dimensional cube formed this way is called a
hypercube
.
Many parallel computers use a hypercube topology because the diameter
grows linearly with the dimensionality. Put in other words, the diameter is the base
2 logarithm of the number of nodes. For example, a 10-dimensional hypercube has
1024 nodes but a diameter of only 10, giving excellent delay properties. Note that
in contrast, 1024 nodes arranged as a 32
×
32 grid have a diameter of 62, more
than six times worse than the hypercube. The price paid for the smaller diameter is
that the fanout, and thus the number of links (and the cost), is much larger for the
hypercube.
Two kinds of switching schemes are used in multicomputers.
In the first one,
each message is first broken up (either by the user software or the network inter-
face) into a chunk of some maximum length called a
packet
.
The switching
scheme, called
store-and-forward packet switching
, consists of the packet being
injected into the first switch by the source node’s network interface board, as
shown in Fig. 8-17(a). The bits come in one at a time, and when the whole packet
has arrived at an input buffer, it is copied to the line leading to the next switch
along the path, as shown in Fig. 8-17(b). When the packet arrives at the switch at-
tached to the destination node, as shown in Fig. 8-17(c), the packet is copied to that
node’s network interface board and eventually to its RAM.
While store-and-forward packet switching is flexible and efficient, it does have
the problem of increasing latency (delay) through the interconnection network.
Suppose that the time to move a packet one hop in Fig. 8-17 is
T
nsec. Since the
packet must be copied four times to get it from CPU 1 to CPU 2 (to
A
, to
C
, to
D
,
and to the destination CPU), and no copy can begin until the previous one is fin-
ished, the latency through the interconnection network is 4
T
.
One way out is to
Ace your assessments! Get Better Grades
Browse thousands of Study Materials & Solutions from your Favorite Schools
Concordia University
Concordia_University
School:
Operating_Systems
Course:
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades
Know more
Students also viewed documents
lab 18.docx
lab_18.docx
Course
Course
3
Module5QuizSTA2023.d...
Module5QuizSTA2023.docx.docx
Course
Course
10
Week 7 Test Math302....
Week_7_Test_Math302.docx.docx
Course
Course
30
Chapter 1 Assigment ...
Chapter_1_Assigment_Questions.docx.docx
Course
Course
5
Week 4 tests.docx.do...
Week_4_tests.docx.docx
Course
Course
23
Week 6 tests.docx.do...
Week_6_tests.docx.docx
Course
Course
106
