I have a quiz the quiz includes 7 questions. the time only 45 m.
506 MULTIPLE PROCESSOR SYSTEMS CHAP. 8 8.1 MULTIPROCESSORS A shared-memory multiprocessor (or just multiprocessor henceforth) is a computer system in which two or more CPUs share full access to a common RAM. A program running on any of the CPUs sees a normal (usually paged) vir- tual address space. The only unusual property this system has is that the CPU can write some value into a memory word and then read the word back and get a dif- ferent value (because another CPU has changed it). When organized correctly, this property forms the basis of interprocessor communication: one CPU writes some data into memory and another one reads the data out. For the most part, multiprocessor operating systems are just regular operating systems. They handle system calls, do memory management, provide a file sys- tem, and manage I/O devices. Nevertheless, there are some areas in which they have unique features. These include process synchronization, resource manage- ment, and scheduling. Below we will first take a brief look at multiprocessor hardware and then move on to these operating systems issues. 8.1.1 Multiprocessor Hardware Although all multiprocessors have the property that every CPU can address all of memory, some multiprocessors have the additional property that every memory word can be read as fast as every other memory word. These machines are called UMA (Uniform Memory Access) multiprocessors. In contrast, NUMA (Nonun- iform Memory Access) multiprocessors do not have this property. Why this dif- ference exists will become clear later. We will first examine UMA multiproces- sors and then move on to NUMA multiprocessors. UMA Bus-Based SMP Architectures The simplest multiprocessors are based on a single bus, as illustrated in Fig. 8-1(a). Two or more CPUs and one or more memory modules all use the same bus for communication. When a CPU wants to read a memory word, it first checks to see if the bus is busy. If the bus is idle, the CPU puts the address of the word it wants on the bus, asserts a few control signals, and waits until the memory puts the desired word on the bus. If the bus is busy when a CPU wants to read or write memory, the CPU just waits until the bus becomes idle. Herein lies the problem with this design. With two or three CPUs, contention for the bus will be manageable; with 32 or 64 it will be unbearable. The system will be totally limited by the bandwidth of the bus, and most of the CPUs will be idle most of the time. The solution to this problem is to add a cache to each CPU, as depicted in Fig. 8-1(b). The cache can be inside the CPU chip, next to the CPU chip, on the processor board, or some combination of all three. Since many reads can now be SEC. 8.1 MULTIPROCESSORS 507 CPU CPU M Shared memory Shared memory Bus (a) CPU CPU M Private memory (b) CPU CPU M (c) Cache Figure 8-1. Three bus-based multiprocessors. (a) Without caching. (b) With caching. (c) With caching and private memories. satisfied out of the local cache, there will be much less bus traffic, and the system can support more CPUs. In general, caching is not done on an individual word basis but on the basis of 32- or 64-byte blocks. When a word is referenced, its entire block is fetched into the cache of the CPU touching it. Each cache block is marked as being either read-only (in which case it can be present in multiple caches at the same time), or as read-write (in which case it may not be present in any other caches). If a CPU attempts to write a word that is in one or more remote caches, the bus hardware detects the write and puts a signal on the bus informing all other caches of the write. If other caches have a ‘‘clean’’ copy, that is, an exact copy of what is in memory, they can just discard their copies and let the writer fetch the cache block from memory before modifying it. If some other cache has a ‘‘dirty’’ (i.e., modified) copy, it must either write it back to memory before the write can proceed or transfer it directly to the writer over the bus. Many cache transfer protocols exist. Yet another possibility is the design of Fig. 8-1(c), in which each CPU has not only a cache, but also a local, private memory which it accesses over a dedicated (private) bus. To use this configuration optimally, the compiler should place all the program text, strings, constants and other read-only data, stacks, and local variables in the private memories. The shared memory is then only used for writ- able shared variables. In most cases, this careful placement will greatly reduce bus traffic, but it does require active cooperation from the compiler. UMA Multiprocessors Using Crossbar Switches Even with the best caching, the use of a single bus limits the size of a UMA multiprocessor to about 16 or 32 CPUs. To go beyond that, a different kind of interconnection network is needed. The simplest circuit for connecting n CPUs to k memories is the crossbar switch, shown in Fig. 8-2. Crossbar switches have been used for decades within 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 508 MULTIPLE PROCESSOR SYSTEMS CHAP. 8 a crosspoint. A crosspoint is a small switch that can be electrically opened or closed, depending on whether the horizontal and vertical lines are to be connected or not. In Fig. 8-2(a) we see three crosspoints closed simultaneously, allowing connections between the (CPU, memory) pairs (001, 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 C P U s 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 10 0 10 1 11 0 11 1 00 0 00 1 01 0 01 1 Figure 8-2. (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). Furthermore, no advance planning is needed. Even if seven arbi- trary connections are already set up, it is always possible to connect the remaining CPU to the remaining memory. 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. SEC. 8.1 MULTIPROCESSORS 509 UMA Multiprocessors Using Multistage Switching Networks A completely different multiprocessor design is based on the humble 2 × 2 switch shown in Fig. 8-3(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-3(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 optional 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 message should be sent on X or on Y. A B X Y (a) (b) Module Address Opcode Value Figure 8-3. (a) A 2 × 2 switch. (b) A message format. Our 2 × 2 switches can be arranged in many ways to build larger multistage switching networks (Adams et al., 1987; Bhuyan et al., 1989; and Kumar and Reddy, 1987). One possibility is the no-frills, economy class omega network, illustrated in Fig. 8-4. Here we have connected eight CPUs to eight memories using 12 switches. More generally, for n CPUs and n memories we would need log2n stages, with n/2 switches per stage, for a total of (n/2)log2n switches, which is a lot better than n 2 crosspoints, especially for large values of n. CPUs b b b b a a a a 3 Stages Memories 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 1A 1B 1C 1D 2A 2B 2C 2D 3A 3B 3C 3D Figure 8-4. An omega switching network. 510 MULTIPLE PROCESSOR SYSTEMS CHAP. 8 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, sup- pose that CPU 011 wants to read a word from memory module 110. The CPU sends a READ message to switch 1D containing 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 mes- sage is routed via the lower output to 2D. All the second-stage switches, including 2D, use the second bit for routing. This, too, is a 1, so the message is now forwarded via the lower output to 3D. Here the third bit is tested and found to be a 0. Consequently, the message goes out on the upper output and arrives at memory 110, as desired. The path followed by this message is marked in Fig. 8-4 by the letter a. As the message moves through the switching network, the bits at the left-hand end of the module number are no longer needed. They can be put to good use by recording the incoming line number there, so the reply can find its way back. For path a, the incoming lines are 0 (upper input to 1D), 1 (lower input to 2D), and 1 (lower input to 3D), respectively. The reply is routed back using 011, only read- ing it from right to left this time. At the same time all this is going on, CPU 001 wants to write a word to memory module 001. An analogous process happens here