Baixe o app para aproveitar ainda mais
Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
cs 152 L1 5 .* DAP Fa97, Ó U.CB Chapter 9 Multiprocessors cs 152 L1 5 .* DAP Fa97, Ó U.CB 9.1 Introduction Until now we have studied how to improve performance by exploring parallelism inside the processor(ILP) with techniques such as: Pipelining, superscalar machines, VLIW, and Dynamic Scheduling. What if we try to connect many processors to build a machine with as much performance as we want? Multiprocessors must therefore be scalable: the hardware and software are designed to be sold with a variable number of processors. We want performance to improve proportionally to the increase in the number of processors. cs 152 L1 5 .* DAP Fa97, Ó U.CB Multiprocessors Idea: create powerful computers by connecting many smaller and ones good news: works for timesharing (better than supercomputer). Vector processing may be coming back bad news: it´s really hard to write good concurrent programs. Many commercial failures cs 152 L1 5 .* DAP Fa97, Ó U.CB Why Use Multiprocessors? System is fault tolerant. If one processor fails, the system will continue service with the others. Multiprocessors may have the highest absolute performance Faster than the fastest uniprocessor. More cost effective to use many single-chip uniprocessors than building a high-performance uniprocessor from a more exotic technology. Current file servers can be ordered with multiple processors. The data base industry has standardized on multiprocessors. cs 152 L1 5 .* DAP Fa97, Ó U.CB Performance in Multiprocessors Commercial dealers usually define high performance as high throughput for independent tasks. Alternative: running a single task on multiple processors. Definition: Parallel processing program is a single program that runs on multiple processors simultaneously. cs 152 L1 5 .* DAP Fa97, Ó U.CB Key Questions How do parallel processors share data? — single address space — message passing How do parallel processors coordinate? — synchronization (locks, semaphores) — built into send / recieve primitives How many processors should the system have? — connected by a single bus (2 - 32 procs) — connected by a network (8 - 256 procs) cs 152 L1 5 .* DAP Fa97, Ó U.CB Shared Memory Processors (SMPs) Processors with a single address space: all processors share a single memory address space. Processors communicate through shared variables in memory. All processors are capable of accessing any memory location with loads and stores. cs 152 L1 5 .* DAP Fa97, Ó U.CB Coordinating Shared Memory Processors Prohibit one processor to start working on data before another is finished with it: synchronization. When sharing is supported with a single address space, there must be a separate mechanism for synchronization. Example synchronization mechanism: lock. When a processor j wants to access a shared variable it must require its lock. Only one processor at a time can aquire the lock. Other interested processors must wait until j unlocks the variable. cs 152 L1 5 .* DAP Fa97, Ó U.CB Classifying SMPs as to Memory Access UMA (Uniform Memory Access) multiprocessors, also called (Symmetric Multiprocessors - SMPs): All memory accesses take the same time, independently of which processors access and which word is accessed. (2 - 64 procs). NUMA (Nonuniform Memory Access) multiprocessors. Memory access times depend on which processors access which words. (8 - 256 procs). It is harder to program NUMA machines efficiently, but they are more scalable. cs 152 L1 5 .* DAP Fa97, Ó U.CB Distributed Memory Processors (8 - 256 procs) Each processor has a local (private) memory. Coordination (communication) is physically achieved by message passing. The system has send / recieve primitives (routines) for achieving this. Much harder to program. New programming paradigms. Events are triggered in the processors by the sending or the reception of a message. cs 152 L1 5 .* DAP Fa97, Ó U.CB Clusters One can achieve multiprocessing by making a LAN (computers connected by Local Area Network) act as a single large multiprocessor. The switch based LAN must provide high bandwidth between computers in the cluster. cs 152 L1 5 .* DAP Fa97, Ó U.CB Keeping Up to Date Industry is rapidly changing in this field. There is no clear answer to all the key questions presented. Many answers depend strongly on application behavior. Find some of the latest information in this field in http:\\www.mkp.com/cod2e.htm. cs 152 L1 5 .* DAP Fa97, Ó U.CB 9.2 Programming Multiprocessors Uniprocessors that compose multiprocessors are cheap since the early 1980s. Communication interconnection network technology is well established. We have good programming languages for parallel program execution. cs 152 L1 5 .* DAP Fa97, Ó U.CB What´s Difficult in Parallel and Distributed Processing? Identifying real (and important) applications that have inherent parallelism and can benefit from parallel processing. Writing parallel programs for parallel execution for these applications is harder than writing sequential programs. The challenge is even greater if we want the application to scale (maintain efficiency when the problem size increases and larger multiprocessors are used). As a result, parallel processing has had sucess when parallel programming specialists have developed a parallel subsystem that presents a sequential interface. cs 152 L1 5 .* DAP Fa97, Ó U.CB Why is Parallel Program Development so Hard? An analogy: For 10 people to work on a task (e.g. painting a house, writing an article or developing SW), they must communicate and coordinate their work. There is no such overhead if one person does the task alone. The overhead is even greater if the number of people increases to 100, 1000 or even 1000000. Because of this overhead, 1000 people do not finish the task 1000 time faster than a single person. n-fold speedup becomes especially unlikely as n increases. The programmer must know a good deal about the HW (number and types of processors, interconnection topology). cs 152 L1 5 .* DAP Fa97, Ó U.CB Problems of Parallel Program Development On a uniprocessor, the high-level language programmer writes the program largely ignoring the underlying machine organization. Uniprocessor design techniques for ILP (Instr Level Parallelism) such as pipelines, SS and out-of -order execution are transparent to the programmer. The compiler handles these issues. you must get good performance and efficiency from the parallel program on a multiprocessor, otherwise you would use a uniprocessor, since programming is easier. Even small parts of a program must be parallelized to reach their full potential (see Amdahl´s law in chapter 2). Sequential parts are bottlenecks. cs 152 L1 5 .* DAP Fa97, Ó U.CB 9.3 Multiprocessors Connected by a Single Bus Single-bus multiprocessor (2 - 32 processors) cs 152 L1 5 .* DAP Fa97, Ó U.CB Why use Single-bus Architectures? Low cost of microprocessors. Each microprocessor is much smaller than a multichip processor, so more processors can be placed on a bus. Local caches can lower bus traffic. There are mechanisms for keeping caches and memory consistent (like consistency protocols for caches and memory for I/O) simplifies programs. Traffic per processor and the bus bandwidth determine the useful number of processors in such a multiprocessor. cs 152 L1 5 .* DAP Fa97, Ó U.CB Caches Caches replicate data in their faster memories: to reduce the latency to the data and to reduce memory traffic on the bus cs 152 L1 5 .* DAP Fa97, Ó U.CB Example Parallel Program for Single Bus Sum 100000 numbers 10 processors Each processor sums 100000 / 10 numbers Variables Pn: number of the local processor A[100000]: Array with numbers to be summed Each processor Pn executes (i is private variable) sum [Pn] = 0; for (i = 10000 *Pn; i < 10000 * (Pn + 1); i++) sum [Pn] = sum [Pn] + A[ i ]; Load Instrs bring correct subset of numbers to the local caches from main memory. cs 152 L1 5 .* DAP Fa97, Ó U.CB Divide and Conquer to Add Partial Sums Divide to Conquer to Add Partial Sums Divide to Conquer to Add Partial Sums Divide to Conquer to Add Partial Sums cs 152 L1 5 .* DAP Fa97, Ó U.CB Program that Adds Partial Sums half = 10; /* 10 processors */ repeat synch( ); if ( half % 2 != 0 && Pn == 0 ) sum [0] = sum [0] + sum [half - 1]; half = half / 2; if ( Pn < half ) sum [Pn] = sum [Pn] + sum [Pn + half]; until (half ==1); /* exit with final sum in sum[0] */ cs 152 L1 5 .* DAP Fa97, Ó U.CB synchronization primitives synch() is a barrier synchronization primitive, processors wait at the barrier until every processor has reached it. When this occurs, all may proceed. This function can be implemented either in SW with the lock synchronization primitive, or with special HW that combines each processor ready signal into a single global signal that all processors can test. cs 152 L1 5 .* DAP Fa97, Ó U.CB Cache Consistency In the example program, the part that adds the partial sums implies in communication. It is convenient to have copies of the same data in multiple caches (sum[ ] in the example). There may be inconsistencies between data in memory and data in caches and also among same data in different caches. Protocols that maintain coherency for multiprocessors are called cache coherency protocols. cs 152 L1 5 .* DAP Fa97, Ó U.CB Some Interesting Problems Cache Coherency Most popular protocol to maintain cache coherency is called snooping. cs 152 L1 5 .* DAP Fa97, Ó U.CB Synchronization Using Coherency Read in page 724 of section 9.3. cs 152 L1 5 .* DAP Fa97, Ó U.CB 9.4 Multiprocessors Connected by a Network 3 Desirable bus characteristics: high bandwidth low latency long length INCOMPATIBLE There is also a limit to the bandwidth of a single memory module attached to a bus. Number of proceessors that can be connected to a single bus is limited (Max processors ~36 processors) cs 152 L1 5 .* DAP Fa97, Ó U.CB Solution for More Demands on Communication Use more communication channels: a Network connects processor-memory modules. cs 152 L1 5 .* DAP Fa97, Ó U.CB Example Network Topologies cs 152 L1 5 .* DAP Fa97, Ó U.CB Example Network Topologies cs 152 L1 5 .* DAP Fa97, Ó U.CB Distributed Memory X Shared Memory Shared Memory: a single address space (implicit communication with loads and stores). Multiple Private Memories (Address Spaces): explicit communication with sends and receives. Distributed Memory: refers to the physical location of the memory. Physical memory is divided into modules, with some placed near each processor. Centralized Memory: access time to a physical memory location is the same for all processors because all accesses go over the interconnect. cs 152 L1 5 .* DAP Fa97, Ó U.CB Many Combinations are Possible Multiprocessors can have a single address space and a distributed physical memory. Decisions: single address space? explicit communication? distributed physical memory? In machines without a single global address, communication is explicit, the programmer or compiler must send / receive messages to export / import data to / from other nodes. cs 152 L1 5 .* DAP Fa97, Ó U.CB Parallel Message Passing Program Sum 100000 numbers 100 processors Each processor sums 100000 / 100 numbers Variables Pn: number of the local processor A[100000]: Array with numbers to be summed One processor containing 100000 numbers sends subsets to each of the 100 processors. Each processor Pn executes to sum its subset sum = 0; for (i = 0; i < 1000; i++) sum = sum + A[ i ]; cs 152 L1 5 .* DAP Fa97, Ó U.CB Divide and Conquer to Add Partial Sums Divide to Conquer to Add Partial Sums Divide to Conquer to Add Partial Sums Divide to Conquer to Add Partial Sums cs 152 L1 5 .* DAP Fa97, Ó U.CB Parallel Message Passing Program Communicate partial sums among neighbors through the network to accumulate the final sum. Divide and conquer to obtain final sum in parallel. send (x, y): routine that sends the value y over the interconnection network to processor x. receive(): function that accepts a value from the network for this processor. half = limit = 100; /* 100 processors */ repeat half = (half + 1) / 2; if (Pn >= half && Pn < limit) send (Pn - half, sum); if ( Pn < (limit / 2 -1) ) sum = sum + receive(); limit = half; until (half ==1); cs 152 L1 5 .* DAP Fa97, Ó U.CB Parallel Message Passing Program The program divides processors into senders and receivers. Each receiving processor gets only one msg a receiving processor will stall until it receives a message. send and receive can be used as promitives for synchronization as well as for communication. cs 152 L1 5 .* DAP Fa97, Ó U.CB Addressing in Large-Scale Processors To be scalable a multiprocessor must have distributed memory. For HW designer it is easier to offer only send and receive. Msg passing also minimizes communication because the programmer who knows the application parallelism should optimize it. It is possible to add a SW layer to provide a single address space on top of sends and receives so that communication is possible using loads and stores (implicit communication) Distributed Shared Memory (DSM). DSM is comparable to the Virtual Memory system. It tries to detect spatial locallity of data and is only efficient if shared memory communication is rare. Otherwise most of the time is spent transferring data. cs 152 L1 5 .* DAP Fa97, Ó U.CB Concluding Remarks Evolution vs. Revolution “More often the expense of innovation comes from being too disruptive to computer users” “Acceptance of hardware ideas requires acceptance by software people; therefore hardware people should learn about software. And if software people want good machines, they must learn more about hardware to be able to communicate with and thereby influence hardware engineers.” cs 152 L1 5 .* DAP Fa97, Ó U.CB Problems for Chapter 9 9.1, 9.2, 9.3, 9.4, 9.7 1 1 1 1 1 1
Compartilhar