Training

Size: px

Start display at page:

Download "Training"

脂翠甄
5 years ago
Views:

1 计算机组织与系统结构从终端到云端的并行处理器 Parallel Processors from Client to Cloud ( 第十一讲 ) 程旭

2 Introduction Goal: connecting multiple computers to get higher performance Multiprocessors Scalability, availability, power efficiency Task-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)

3 C3 S 6 1 c Why Parallel Processing? CPU Clock Rates are no longer increasing Technical & economic challenges Advanced cooling technology too expensive or impractical for most applications Energy costs are prohibitive Parallel processing is only path to higher speed Compare airlines: Maximum speed limited by speed of sound and economics Use more and larger airplanes to increase throughput And smaller seats

4 4 Using Parallelism for Performance Two basic ways: Multiprogramming run multiple independent programs in parallel Easy Parallel computing run one program faster Hard We ll focus on parallel computing in the lecture

5 Machine Structures (It s a bit more complicated!) Software Parallel Requests Assigned to computer e.g., Search Katz Parallel Threads Assigned to core e.g., Lookup, Ads Parallel Instructions >1 instruction @ one time e.

5 5 Machine Structures (It s a bit more complicated!) Software Parallel Requests Assigned to computer e.g., Search Katz Parallel Threads Assigned to core e.g., Lookup, Ads Parallel Instructions >1 one time e.g., 5 pipelined instructions Parallel Data >1 data one time e.g., Add of 4 pairs of words Hardware descriptions All one time Programming Languages Harness Parallelism & Achieve High Performance Hardware SIMD Warehouse Scale Computer Core Memory Input/Output Instruction Unit(s) Cache Memory Computer Core (Cache) Core Functional Unit(s) A 0 +B 0 A 1 +B 1 A 2 +B 2 A 3 +B 3 Smart Phone Logic Gates

6 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

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

8 Amdahl s Law Get enhancement E for your new PC E.g. floating-point rocket booster E Speeds up some task (e.g. arithmetic) by factor S E F is fraction of program that uses this task Execution Time: T 0 (no E) T E (with E) no speedup speedup section 1-F F 1-F F / S E Speedup: Speedup = T O / T E = 1 / ((1-F) + F/S E )

9 Big Idea: Amdahl s Law Speedup = T O / T E = 1 / ((1-F) + F/S E ) Part not sped up Part sped up Example: The execution time of half of a program can be accelerated by a factor of 2. What is the program speed-up overall? T O / T E = 1 / ((1-F) + F/S E ) = 1/((1-0.5)+0.5/2) = 1.33 << 2

10 Amdahl s Law Sequential part can limit speedup Example: 100 processors, 90 speedup? T new = T parallelizable /100 + T sequential Speedup (1 F parallelizable ) 1 F parallelizable / Solving: F parallelizable = Need sequential part to be 0.1% of original time

11 Maximum Achievable Speed-Up Speedup = 1 / ((1-F) + F/S E ) (S E -> ) = 1/(1-F) Question: What is a reasonable # of parallel processors to speed up an algorithm with F = 95%? (i.e. 19/20 th can be sped up) a) Maximum speedup: S max = 1/(1-0.95) = 20 but needs S E =! b) Reasonable engineering compromise: Equal time in sequential and parallel code: (1-F) = F/S E S E = F/(1-F) = 0.95/0.05 = 20 S = 1/( ) = 10

12 If the portion of the program that can be parallelized is small, then the speedup is limited 500 processors for 19x 20 processors for 10x In this region, the sequential portion limits the performance

13 Scaling Example Workload: sum of 10 scalars, and matrix sum Speed up from 10 to 100 processors Single processor: Time = ( ) t add 10 processors Time = 10 t add + 100/10 t add = 20 t add Speedup = 110/20 = 5.5 (55% of potential) 100 processors Time = 10 t add + 100/100 t add = 11 t add Speedup = 110/11 = 10 (10% of potential) Assumes load can be balanced across processors

14 Scaling Example (cont) What if matrix size is ? Single processor: Time = ( ) t add 10 processors Time = 10 t add /10 t add = 1010 t add Speedup = 10010/1010 = 9.9 (99% of potential) 100 processors Time = 10 t add /100 t add = 110 t add Speedup = 10010/110 = 91 (91% of potential) Assuming load balanced

15 Strong vs Weak Scaling Strong scaling: problem size fixed As in example Weak scaling: problem size proportional to number of processors 10 processors, matrix Time = 20 t add 100 processors, matrix Time = 10 t add /100 t add = 20 t add Constant performance in this example

16 Strong and Weak Scaling To get good speedup on a parallel processor while keeping the problem size fixed is harder than getting good speedup by increasing the size of the problem. Strong scaling: when speedup can be achieved on a parallel processor without increasing the size of the problem Weak scaling: when speedup is achieved on a parallel processor by increasing the size of the problem proportionally to the increase in the number of processors Load balancing is another important factor: every processor doing same amount of work Just one unit with twice the load of others cuts speedup almost in half

17 1 7 Single-Instruction Stream /Single-Data Stream (SISD) Sequential computer that exploits no parallelism in either the instruction or data streams. Examples of SISD architecture are traditional uniprocessor machines Processing Unit -E.g. our trusted RISC-V pipeline

18 Single-Instruction Stream/Multiple-Data Streams (SIMD or sim-dee ) SIMD computer exploits multiple data streams against a single instruction stream to operations that may be naturally parallelized, e.g., Intel SIMD instruction extensions or NVIDIA Graphics Processing Unit (GPU)

19 Data Pool Multiple-Instruction Streams/Multiple-Data Streams (MIMD or mim-dee ) Instruction Pool PU PU PU PU Multiple autonomous processors simultaneously executing different instructions on different data. MIMD architectures include multicore and Warehouse-Scale Computers

20 Multiple-Instruction Streams/Single-Data Stream (MISD) Multiple-Instruction, Single-Data stream computer that exploits multiple instruction streams against a single data stream.

21 2 1 Flynn* Taxonomy, 1966 SIMD and MIMD are currently the most common parallelism in architectures usually both in same system! Most common parallel processing programming style: Single Program Multiple Data ( SPMD ) Single program that runs on all processors of a MIMD Cross-processor execution coordination using synchronization primitives

22 SIMD:Single Instruction Multiple Data

23 SIMD Applications & Implementations Applications Scientific computing Matlab, NumPy Graphics and video processing Photoshop, Big Data Deep learning Gaming Implementations x86 ARM RISC-V vector extensions

24 First SIMD Extensions: MIT Lincoln Labs TX-2, 1957

C2 S 5 6 1 c x86 SIMD Evolution New instructions New, wider, more registers

25 C2 S c x86 SIMD Evolution New instructions New, wider, more registers More parallelism /VectorOps.pdf

26 SIMD Registers

27 SIMD Data Types (Now also AVX-512 available)

28 SIMD Vector Mode

29 Problem Today s compilers (largely) do not generate SIMD code Back to assembly x86 (not using RISC-V as no vector hardware yet) Over 1000 instructions to learn Green Book Can we use the compiler to generate all non- SIMD instructions?

30 Vector Processors Highly pipelined function units Stream data from/to vector registers to units Data collected from memory into registers Results stored from registers to memory Example: Vector extension to RISC-V v0 to v31: element registers, (64-bit elements) Vector instructions fld.v, fsd.v: load/store vector fadd.d.v: add vectors of double fadd.d.vs: add scalar to each element of vector of double Significantly reduces instruction-fetch bandwidth

31 Example: DAXPY (Y = a X + Y) Conventional RISC-V code: fld f0,a(x3) // load scalar a addi x5,x19,512 // end of array X loop: fld f1,0(x19) // load x[i] fmul.d f1,f1,f0 // a * x[i] fld f2,0(x20) // load y[i] fadd.d f2,f2,f1 // a * x[i] + y[i] fsd f2,0(x20) // store y[i] addi x19,x19,8 // increment index to x addi x20,x20,8 // increment index to y bltu x19,x5,loop // repeat if not done Vector RISC-V code: fld f0,a(x3) // load scalar a fld.v v0,0(x19) // load vector x fmul.d.vs v0,v0,f0 // vector-scalar multiply fld.v v1,0(x20) // load vector y fadd.d.v v1,v1,v0 // vector-vector add fsd.v v1,0(x20) // store vector y

32 Vector vs. Scalar Vector architectures and compilers Simplify data-parallel programming Explicit statement of absence of loop-carried dependences Reduced checking in hardware Regular access patterns benefit from interleaved and burst memory Avoid control hazards by avoiding loops More general than ad-hoc media extensions (such as MMX, SSE) Better match with compiler technology

33 SIMD Operate elementwise on vectors of data E.g., MMX and SSE instructions in x86 Multiple data elements in 128-bit wide registers All processors execute the same instruction at the same time Each with different data address, etc. Simplifies synchronization Reduced instruction control hardware Works best for highly data-parallel applications

34 Vector vs. Multimedia Extensions Vector instructions have a variable vector width, multimedia extensions have a fixed width Vector instructions support strided access, multimedia extensions do not Vector units can be combination of pipelined and arrayed functional units:

Machine Structures (It s a bit more complicated!) Parallel Requests Assigned to computer e.g., Search Katz Parallel Threads Assigned to core e.g., Lookup, Ads Parallel Instructions >1 instruction @ one time e.

Hardware Warehouse Scale Computer Core Memory Input/Output Instruction Unit(s) Computer (Cache) Core Core Functional Unit(s) A 0 +B 0 A 1 +B 1 A 2 +B 2 A 3 +B

35 Machine Structures (It s a bit more complicated!) Parallel Requests Assigned to computer e.g., Search Katz Parallel Threads Assigned to core e.g., Lookup, Ads Parallel Instructions >1 one time e.g., 5 pipelined instructions Parallel Data >1 data one time e.g., Add of 4 pairs of words Software Harness Parallelism & Achieve High Performance Hardware Warehouse Scale Computer Core Memory Input/Output Instruction Unit(s) Computer (Cache) Core Core Functional Unit(s) A 0 +B 0 A 1 +B 1 A 2 +B 2 A 3 +B 3 Smart Phone Hardware descriptions All one time 12/28/2017 Programming Languages Cache Memory Logic Gates 35

36 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)

37 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 Example: Intel Pentium-4 HT Two threads: duplicated registers, shared function units and caches

38 Multithreading Example

all processors Synchronize shared variables using

39 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)

40 Example: Sum Reduction Sum 64,000 numbers on 64 processor UMA Each processor has ID: 0 Pn 63 Partition 1000 numbers per processor Initial summation on each processor sum[pn] = 0; for (i = 1000*Pn; i < 1000*(Pn+1); i += 1) 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

41 C h a p t e half = 64; r 6 do P a r synch(); a l l e l P r o c e s s o r s f r o m C Example: Sum Reduction if (half%2!= 0 && Pn == 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+half]; while (half > 1);

42 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

43 Graphics in the System

44 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)

45 Example: NVIDIA Fermi Multiple SIMD processors, each as shown:

46 Example: NVIDIA Fermi SIMD Processor: 16 SIMD lanes SIMD instruction Operates on 32 element wide threads Dynamically scheduled on 16-wide processor over 2 cycles 32K x 32-bit registers spread across lanes 64 registers per thread context

47 Basic unified GPU architecture (Tesla architecture of an NVIDIA GeForce 8800) 14 SM(Streaming Multiprocessor) * 8 SP(Streaming Processor) * 96 Threads raster operation processors (ROPs) ; texture/processor cluster (TPC)

48 GPU Memory Structures(CUDA) Nested granularity levels thread, thread block, and grid have corresponding memory sharing levels local, shared, and global

49 Classifying GPUs Don t fit nicely into SIMD/MIMD model Conditional execution in a thread allows an illusion of MIMD But with performance degredation Need to write general purpose code with care Instruction-Level Parallelism Data-Level Parallelism Static: Discovered at Compile Time VLIW SIMD or Vector Dynamic: Discovered at Runtime Superscalar Tesla Multiprocessor

50 Putting GPUs into Perspective Feature Multicore with SIMD GPU SIMD processors 4 to 8 8 to 16 SIMD lanes/processor 2 to 4 8 to 16 Multithreading hardware support for SIMD threads Typical ratio of single precision to doubleprecision performance 2 to 4 16 to 32 2:1 2:1 Largest cache size 8 MB 0.75 MB Size of memory address 64-bit 64-bit Size of main memory 8 GB to 256 GB 4 GB to 6 GB Memory protection at level of page Yes Yes Demand paging Yes No Integrated scalar processor/simd processor Yes No Cache coherent Yes No

51 Message Passing Each processor has private physical address space Hardware sends/receives messages between processors

52 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

53 Sum Reduction (Again) Sum 64,000 on 64 processors First distribute 1000 numbers to each The do partial sums sum = 0; for (i = 0; i<1000; i += 1) sum += AN[i]; Reduction Half the processors send, other half receive and add The quarter send, quarter receive and add,

54 Sum Reduction (Again) Given send() and receive() operations limit = 64; half = 64;/* 64 processors */ do half = (half+1)/2; /* send vs. receive dividing line */ if (Pn >= half && Pn < limit) send(pn - half, sum); if (Pn < (limit/2)) sum += receive(); limit = half; /* upper limit of senders */ while (half > 1); /* exit with final sum */ Send/receive also provide synchronization Assumes send/receive take similar time to addition

55 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., World Community Grid

56 Interconnection Networks Network topologies Arrangements of processors, switches, and links Bus Ring 2D Mesh N-cube (N = 3) Fully connected

57 Multistage Networks

58 Network Characteristics Performance Latency per message (unloaded network) Throughput Link bandwidth Total network bandwidth Bisection bandwidth Congestion delays (depending on traffic) Cost Power Routability in silicon

59 Parallel Benchmarks Linpack: matrix linear algebra SPECrate: parallel run of SPEC CPU programs Job-level parallelism SPLASH: Stanford Parallel Applications for Shared Memory Mix of kernels and applications, strong scaling NAS (NASA Advanced Supercomputing) suite computational fluid dynamics kernels PARSEC (Princeton Application Repository for Shared Memory Computers) suite Multithreaded applications using Pthreads and OpenMP

60 Fallacies Amdahl s Law doesn t apply to parallel computers Since we can achieve linear speedup But only on applications with weak scaling Peak performance tracks observed performance Marketers like this approach! But compare Xeon with others in example Need to be aware of bottlenecks

61 Concluding Remarks Goal: higher performance by using multiple processors Difficulties Developing parallel software Devising appropriate architectures SaaS importance is growing and clusters are a good match Performance per dollar and performance per Joule drive both mobile and WSC

Concluding Remarks (con t) SIMD and vector operations match multimedia applications and are easy to program Potential speed-up via parallelism from MIMD, SIMD, and both MIMD and

62 Concluding Remarks (con t) SIMD and vector operations match multimedia applications and are easy to program Potential speed-up via parallelism from MIMD, SIMD, and both MIMD and SIMD over time for x86 computers. This figure assumes that two cores per chip for MIMD will be added every 2 years and the number of operations for SIMD will double every 4 years

Intel® Core2™ i7 Processor

Intel® Core2™ i7 Processor Intel CPU 的演進及 Core2 i7/i5/i3 處理器架構之探討報告人 : 資訊工程系俞朝福中華民國九十九年三月三十一日 1 PART I Intel 處理器的演進 1971~2010 走過處理器 40 年 2 Intel CPU Pre-x86 4004-- 全球第一款微處理器, 於