CSC 320 Chapter #7, Spring 2015

Course Learning Outcomes � Students shall demonstrate an understanding of the internal organization of a computer system through assembly language. � Students shall design and simulate the data path and the control unit of a simple computer based on an instruction set. � Students shall demonstrate an understanding of pipelining including instruction sequencing, register value forwarding, data interlocking. � Students shall demonstrate an understanding of the basic concepts of multiprocessor and multi-core designs. � Students shall demonstrate an understanding of the history and possible future of the field necessary for staying at the forefront of computing systems development (life-long learning). Chapter 7 — Multicores, Multiprocessors, and Clusters — 1 Course Learning Outcomes � Students shall demonstrate an understanding of the internal organization of a computer system through assembly language. � Students shall design and simulate the data path and the control unit of a simple computer based on an instruction set. � Students shall demonstrate an understanding of pipelining including instruction sequencing, register value forwarding, data interlocking. � Students shall demonstrate an understanding of the basic concepts of multiprocessor and multi-core designs. � Students shall demonstrate an understanding of the history and possible future of the field necessary for staying at the forefront of computing systems development (life-long learning). Chapter 7 — Multicores, Multiprocessors, and Clusters — 2 Chapter 7 Multicores, Multiprocessors, and Clusters Chapter 7 — Multicores, Multiprocessors, and Clusters — 4 Introduction � Goal: connecting multiple computers to get higher performance � Multiprocessors � Scalability, availability, power efficiency � Job-level (process-level) parallelism � High throughput for independent jobs � Parallel processing program � Single program run on multiple processors � Multicore microprocessors � Chips with multiple processors (cores) §9.1 Introduction Chapter 7 — Multicores, Multiprocessors, and Clusters — 5 Hardware and Software � Hardware � Serial: e.g., Pentium 4 � Parallel: e.g., quad-core Xeon e5345 � Software � Sequential: e.g., matrix multiplication � Concurrent: e.g., operating system � Sequential/concurrent software can run on serial/parallel hardware � Challenge: making effective use of parallel hardware Chapter 7 — Multicores, Multiprocessors, and Clusters — 7 Parallel Programming � Parallel software is the problem � Need to get significant performance improvement � Otherwise, just use a faster uniprocessor, since it’s easier! � Difficulties � Partitioning � Coordination � Communications overhead §7.2 The Difficulty of Creating Parallel Processing Programs Chapter 7 — Multicores, Multiprocessors, and Clusters — 8 Amdahl’s Law � Sequential part can limit speedup � Example: 100 processors, 90× speedup? � Tnew = Tparallelizable/100 + Tsequential � � Solving: Fparallelizable = 0.999 � Need sequential part to be 0.1% of original time 90 /100 F ) (1 F 1 Speedup parallelizable parallelizable = + − = Chapter 7 — Multicores, Multiprocessors, and Clusters — 9 Scaling Example � Workload: sum of 10 scalars, and 10 × 10 matrix sum � Speed up from 10 to 100 processors � Single processor: Time = (10 + 100) × tadd � 10 processors � Time = 10 × tadd + 100/10 × tadd = 20 × tadd � Speedup = 110/20 = 5.5 (55% of potential) � 100 processors � Time = 10 × tadd + 100/100 × tadd = 11 × tadd � Speedup = 110/11 = 10 (10% of potential) � Assumes load can be balanced across processors Chapter 7 — Multicores, Multiprocessors, and Clusters — 10 Scaling Example (cont) � What if matrix size is 100 × 100? � Single processor: Time = (10 + 10000) × tadd � 10 processors � Time = 10 × tadd + 10000/10 × tadd = 1010 × tadd � Speedup = 10010/1010 = 9.9 (99% of potential) � 100 processors � Time = 10 × tadd + 10000/100 × tadd = 110 × tadd � Speedup = 10010/110 = 91 (91% of potential) � Assuming load balanced Chapter 7 — Multicores, Multiprocessors, and Clusters — 11 Strong vs Weak Scaling � Strong scaling: problem size fixed � As in example � Weak scaling: problem size proportional to number of processors � 10 processors, 10 × 10 matrix � Time = 20 × tadd � 100 processors, 32 × 32 matrix � Time = 10 × tadd + 1000/100 × tadd = 20 × tadd � Constant performance in this example Chapter 7 — Multicores, Multiprocessors, and Clusters — 12 Shared Memory � SMP: shared memory multiprocessor � Hardware provides single physical address space for all processors � Synchronize shared variables using locks � Memory access time � UMA (uniform) vs. NUMA (nonuniform) §7.3 Shared Memory Multiprocessors Chapter 7 — Multicores, Multiprocessors, and Clusters — 13 Example: Sum Reduction � Sum 100,000 numbers on 100 processor UMA � Each processor has ID: 0 ≤ Pn ≤ 99 � Partition 1000 numbers per processor � Initial summation on each processor sum[Pn] = 0; for (i = 1000*Pn; i < 1000*(Pn+1); i = i + 1) sum[Pn] = sum[Pn] + A[i]; � Now need to add these partial sums � Reduction: divide and conquer � Half the processors add pairs, then quarter, … � Need to synchronize between reduction steps Chapter 7 — Multicores, Multiprocessors, and Clusters — 14 Example: Sum Reduction half = 100; repeat synch(); if (half%2 != 0 && Pn == 0) sum[0] = sum[0] + sum[half-1]; /* Conditional sum needed when half is odd; Processor0 gets missing element */ half = half/2; /* dividing line on who sums */ if (Pn < half) sum[Pn] = sum[Pn] + sum[Pn+half]; until (half == 1); Chapter 7 — Multicores, Multiprocessors, and Clusters — 15 Message Passing � Each processor has private physical address space � Hardware sends/receives messages between processors §7.4 Clusters and Other Message-Passing Multiprocessors Chapter 7 — Multicores, Multiprocessors, and Clusters — 16 Loosely Coupled Clusters � Network of independent computers � Each has private memory and OS � Connected using I/O system � E.g., Ethernet/switch, Internet � Suitable for applications with independent tasks � Web servers, databases, simulations, … � High availability, scalable, affordable � Problems � Administration cost (prefer virtual machines) � Low interconnect bandwidth � c.f. processor/memory bandwidth on an SMP Chapter 7 — Multicores, Multiprocessors, and Clusters — 19 Grid Computing � Separate computers interconnected by long-haul networks � E.g., Internet connections � Work units farmed out, results sent back � Can make use of idle time on PCs � E.g., SETI@home, World Community Grid Chapter 7 — Multicores, Multiprocessors, and Clusters — 20 Multithreading � Performing multiple threads of execution in parallel � Replicate registers, PC, etc. � Fast switching between threads � Fine-grain multithreading � Switch threads after each cycle � Interleave instruction execution � If one thread stalls, others are executed � Coarse-grain multithreading � Only switch on long stall (e.g., L2-cache miss) � Simplifies hardware, but doesn’t hide short stalls (eg, data hazards) §7.5 Hardware Multithreading Chapter 7 — Multicores, Multiprocessors, and Clusters — 21 Simultaneous Multithreading � In multiple-issue dynamically scheduled processor � Schedule instructions from multiple threads � Instructions from independent threads execute when function units are available � Within threads, dependencies handled by scheduling and register renaming Chapter 7 — Multicores, Multiprocessors, and Clusters — 23 Multithreading Example Chapter 7 — Multicores, Multiprocessors, and Clusters — 25 Instruction and Data Streams � An alternate classification §7.6 SISD, MIMD, SIMD, SPMD, and Vector Data Streams Single Multiple Instruction Streams Single SISD: Intel Pentium 4 SIMD: SSE instructions of x86 Multiple MISD: No examples today MIMD: Intel Xeon e5345 � SPMD: Single Program Multiple Data � A parallel program on a MIMD computer � Conditional code for different processors Chapter 7 — Multicores, Multiprocessors, and Clusters — 30 History of GPUs � Early video cards � Frame buffer memory with address generation for video output � 3D graphics processing � Originally high-end computers (e.g., SGI) � Moore’s Law ⇒ lower cost, higher density � 3D graphics cards for PCs and game consoles � Graphics Processing Units � Processors oriented to 3D graphics tasks � Vertex/pixel processing, shading, texture mapping, rasterization §7.7 Introduction to Graphics Processing Units Chapter 7 — Multicores, Multiprocessors, and Clusters — 32 GPU Architectures � Processing is highly data-parallel � GPUs are highly multithreaded � Use thread switching to hide memory latency � Less reliance on multi-level caches � Graphics memory is wide and high-bandwidth � Trend toward general purpose GPUs � Heterogeneous CPU/GPU systems � CPU for sequential code, GPU for parallel code � Programming languages/APIs � DirectX, OpenGL � C for Graphics (Cg), High Level Shader Language (HLSL) � Compute Unified Device Architecture (CUDA) Chapter 7 — Multicores, Multiprocessors, and Clusters — 33 Example: NVIDIA Tesla Streaming multiprocessor 8 × Streaming processors Chapter 7 — Multicores, Multiprocessors, and Clusters — 34 Example: NVIDIA Tesla � Streaming Processors � Single-precision FP and integer units � Each SP is fine-grained multithreaded � Warp: group of 32 threads � Executed in parallel, � SIMD 8 SPs × 4 clock cycles Chapter 7 — Multicores, Multiprocessors, and Clusters — 36 Interconnection Networks � Network topologies � Arrangements of processors, switches, and links §7.8 Introduction to Multiprocessor Network Topologies Bus Ring 2D Mesh N-cube (N = 3) Fully connected Chapter 7 — Multicores, Multiprocessors, and Clusters — 37 Multistage Networks Chapter 7 — Multicores, Multiprocessors, and Clusters — 38 Network Characteristics � Performance � Latency per message (unloaded network) � Throughput � Congestion delays (depending on traffic) � Cost � Power � Routability in silicon Chapter 7 — Multicores, Multiprocessors, and Clusters — 54 Concluding Remarks � Goal: higher performance by using multiple processors � Difficulties � Developing parallel software � Devising appropriate architectures � Many reasons for optimism � Changing software and application environment � Chip-level multiprocessors with lower latency, higher bandwidth interconnect � An ongoing challenge for computer architects! §7.13 Concluding Remarks