|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 553-554 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 553
522
MULTIPLE PROCESSOR SYSTEMS
CHAP. 8
memories is the
crossbar switch
, shown in Fig. 8-3. Crossbar switches have been
used for decades in telephone switching exchanges to connect a group of incoming
lines to a set of outgoing lines in an arbitrary way.
At each intersection of a horizontal (incoming) and vertical (outgoing) line is a
crosspoint
.
A crosspoint is a small electronic switch that can be electrically open-
ed or closed, depending on whether the horizontal and vertical lines are to be con-
nected or not.
In Fig. 8-3(a) we see three crosspoints closed simultaneously, allow-
ing connections between the (CPU, memory) pairs (010, 000), (101, 101), and
(110, 010) at the same time. Many other combinations are also possible.
In fact,
the number of combinations is equal to the number of different ways eight rooks
can be safely placed on a chess board.
Memories
CPUs
Closed
crosspoint
switch
Open
crosspoint
switch
(a)
(b)
(c)
Crosspoint
switch is closed
Crosspoint
switch is open
000
001
010
011
100
101
110
111
100
101
110
111
000
001
010
011
Figure 8-3.
(a) An 8
×
8 crossbar switch. (b) An open crosspoint.
(c) A closed
crosspoint.
One of the nicest properties of the crossbar switch is that it is a
nonblocking
network
, meaning that no CPU is ever denied the connection it needs because
some crosspoint or line is already occupied (assuming the memory module itself is
available). Not all interconnects have this fine property.
Furthermore, no advance
planning is needed. Even if seven arbitrary connections are already set up, it is al-
ways possible to connect the remaining CPU to the remaining memory.
Page 554
SEC. 8.1
MULTIPROCESSORS
523
Contention for memory is still possible, of course, if two CPUs want to access
the same module at the same time.
Nevertheless, by partitioning the memory into
n
units, contention is reduced by a factor of
n
compared to the model of Fig. 8-2.
One of the worst properties of the crossbar switch is the fact that the number of
crosspoints grows as
n
2
. With 1000 CPUs and 1000 memory modules we need a
million crosspoints. Such a large crossbar switch is not feasible.
Nevertheless, for
medium-sized systems, a crossbar design is workable.
UMA Multiprocessors Using Multistage Switching Networks
A completely different multiprocessor design is based on the humble 2
×
2
switch shown in Fig. 8-4(a). This switch has two inputs and two outputs. Mes-
sages arriving on either input line can be switched to either output line. For our
purposes, messages will contain up to four parts, as shown in Fig. 8-4(b). The
Module
field tells which memory to use. The
Address
specifies an address within a
module. The
Opcode
gives the operation, such as
READ
or
WRITE
.
Finally, the op-
tional
Value
field may contain an operand, such as a 32-bit word to be written on a
WRITE
.
The switch inspects the
Module
field and uses it to determine if the mes-
sage should be sent on
X
or on
Y
.
A
B
X
Y
(a)
(b)
Module
Address
Opcode
Value
Figure 8-4.
(a) A 2
×
2 switch with two input lines,
A
and
B
, and two output
lines,
X
and
Y
. (b) A message format.
Our 2
×
2 switches can be arranged in many ways to build larger
multistage
switching networks
(Adams et al., 1987; Garofalakis and Stergiou, 2013; and
Kumar and Reddy, 1987). One possibility is the no-frills, cattle-class
omega net-
work
, illustrated in Fig. 8-5. Here we have connected eight CPUs to eight memo-
ries using 12 switches. More generally, for
n
CPUs and
n
memories we would need
log
2
n
stages, with
n
/2 switches per stage, for a total of (
n
/2) log
2
n
switches,
which is a lot better than
n
2
crosspoints, especially for large values of
n
.
The wiring pattern of the omega network is often called the
perfect shuffle
,
since the mixing of the signals at each stage resembles a deck of cards being cut in
half and then mixed card-for-card. To see how the omega network works, suppose
that CPU 011 wants to read a word from memory module 110.
The CPU sends a
READ message to switch 1D containing the value 110 in the
Module
field. The
switch takes the first (i.e., leftmost) bit of 110 and uses it for routing.
A 0 routes to
the upper output and a 1 routes to the lower one. Since this bit is a 1, the message
is routed via the lower output to 2D.
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
