<4D F736F F F696E74202D204C FBAB4B7C4C7C1B7CEB1D7B7A1B9D6B1E2C3CA2E BC8A3C8AF20B8F0B5E55D>

Size: px

Start display at page:

Download "<4D F736F F F696E74202D204C FBAB4B7C4C7C1B7CEB1D7B7A1B9D6B1E2C3CA2E BC8A3C8AF20B8F0B5E55D>"

성연 공
5 years ago
Views:

1 The Power and Potential of Parallelism 이홍석 병렬처리시스템활용시대가도래... 소규모 Multi-core 환경 노트북, PC, 워크스테이션, 서버등모두 Multi-core OS 가 multi-core 를지원 POSIX 쓰레드와 win32 쓰레드 GPGPU 기반의개인슈퍼컴퓨터의등장 CUDA/OpenCL/GPGPU 의급속한발전 대규모 multicore 환경 슈퍼컴퓨터 : 1 만 ~ 20 만개수이상코어로구성된시스템 Clusters : 가격대비성능비가좋은시스템 Servers Grid computing

2 병렬컴퓨팅과분산컴퓨팅 병렬컴퓨팅 단일문제를해결하기위하여 multiple processor 를사용 프로세스사이의 interconnection 이우수함을요구 슈퍼컴퓨팅 분산컴퓨팅 많은프로세스들을쉽게이용하도록편리를제공 통신부하가적은응용에적합 병렬계산은짧지만분산하는시간을길다 그리드컴퓨팅 병렬프로그래밍기법을배우자 우수한병렬프로그램작성한다는것은.. 답이정확하고 (correct) 우수한병렬성능 (good performance) 많은프로세스를이용한우수한병렬확장성 (scalability) 이기종병렬시스템에이식성 (portability) 병렬프로그램은하드웨어스펙과밀접한관련이됨 MPI OpenMP Hybrid (MPI+OpenMP) CUDA Pthread, Java,

무어 (Moore) 의법칙리뷰 1965 paper Doubling of the number

com/images-moores-law-turns-40/2009-1041_3-5649019.

Scalar/Special Purpose/Parallel IBM RoadRunner Moore

1.5 Years Pacific TMC CM-5 Cray T3D Super Scalar

3 무어 (Moore) 의법칙리뷰 1965 paper Doubling of the number of transistors on integrated circuits every two years. Moore's law has been the name given to everything that t changes exponentially Moor s 법칙리뷰 1 PF 1TF 1 GF Super Scalar/Special Purpose/Parallel IBM RoadRunner Moore s Law 2X Transistors/Chip ASCI Red ASCI White Every 1.5 Years Pacific TMC CM-5 Cray T3D Super Scalar Vector Cray 1 TMC CM-2 Cray 2 Cray X-MP Parallel Scalar 1 MF IBM 7090 CDC 7600 IBM 360/195 CDC KF UNIVAC 1 EDSAC

Supercomputing 기법변화가속화 세계 1 위성능슈퍼컴퓨터 (2009.

고속의가속보드의등장 General purpose computing on GPU NVIDIA

Newest System Jaguar XT5 Jaguar Total XT5 XT4 Peak

181,504 150,176 31,328 System Memory (TB) 362 300

(TB) 10,750 10,000 750 Interconnect Bandwidth

after acceptance of the new XT5 upgrade.

4 Supercomputing 기법변화가속화 세계 1 위성능슈퍼컴퓨터 (2009.1) IBM Cell 기반 Roadrunner 1 Pflops 이상성능 특별한목적에맞게개발 고속의가속보드의등장 General purpose computing on GPU NVIDIA Tesla S870 Supercomputer ORNL s Newest System Jaguar XT5 Jaguar Total XT5 XT4 Peak Performance 1,645 1, AMD Opteron Cores 181, ,176 31,328 System Memory (TB) Disk Bandwidth (GB/s) Disk Space (TB) 10,750 10, Interconnect Bandwidth (TB/s) The systems will be combined after acceptance of the new XT5 upgrade. Each system will be linked to the file system through 4x-DDR Infiniband

700 600 500 400 300 200 100 19 systems > 100 Tflop/s 51

105 131 157 183 209 235 261 287 313 339 365 391 417 443 469

rising Clock speed flattening sharply Multiple instruction

5 슈퍼컴퓨터 Top500 분석 ( ) Pflop/s systems > 1 Pflop/s Rmax (Tflop/s) systems > 100 Tflop/s 51 systems > 50 Tflop/s 119 systems > 25 Tflop/s Rank 컴퓨터하드웨어발전추이 새로운제약조건 전기사용량이 clock의발전을제한 Instruction Level Parallelism로더이상성능향상은기대하기어려움새로운경향 Transistor count still rising Clock speed flattening sharply Multiple instruction streaming이필요 multicore 프로그래밍 Figure courtesy of Kunle Olukotun, Lance Hammond, Herb Sutter, and Burton Smith

CPU 성능 vs 전기사용비용 Power Voltage 2 x Frequency (V

2010-03-11 11 무어의법칙재검토 칲당코어수가매 2 년마다 2 배가되고있지만,

6 CPU 성능 vs 전기사용비용 Power Voltage 2 x Frequency (V 2 F) Frequency Voltage Power Frequency 무어의법칙재검토 칲당코어수가매 2 년마다 2 배가되고있지만, 클럭속도는줄고있다. Clock speed 는더이상증가하고있지않고 수백만개수쓰레드를동시에관리하는프로그래밍기법이필요 미래세대에는수백만개수의쓰레드 Intro-chip 병렬화가가능한 inter-chip 병렬화를쉽게대체필요 프로세서수의 2 배증가매 2 년마다

Multicore 에서 Manycore 로 멀티코어란 한개의컴퓨터 chip 에 2~4 개프로세스 ( 코어 ) 가있는아키텍처디자인

Intel 80-core TeraScale chip Intel 32-core Larrabee chip IBM Cyclops-64

240-core C870 AMD/ATI FireStream 9170 320 cores 2010-03-11 13 Intel s

architecture New vector instructions set Vector memory operations

7 Multicore 에서 Manycore 로 멀티코어란 한개의컴퓨터 chip 에 2~4 개프로세스 ( 코어 ) 가있는아키텍처디자인 Chip multiprocessors (CMP) Manycore Chip 당 10~100+ 코어가집적 이질성이대세 예를들면 Intel 80-core TeraScale chip Intel 32-core Larrabee chip IBM Cyclops-64 chip with 160 thread units ClearSpeed 96-core CSX chip NvidiaTesla 240-core C870 AMD/ATI FireStream cores Intel s Larrabee Chip Many X 86 IA cores Scalable to Tflop/s New cache architecture New vector instructions set Vector memory operations Conditionals Integer and floating point arithmetic New vector processing unit / wide SIMD

8 GPGPU 가속 : NVIDIA Tesla T10P T10P chip 240 cores; 1.5 GHz Tpeak 1 Tflop/s - 32 bit floating point Tpeak 100 Gflop/s - 64 bit floating point S1070 board 4 - T10P devices; 700 Watts GTX T10P; 1.3 GHz Tpeak 864 Gflop/s - 32 bit floating point Tpeak 86.4 Gflop/s - 64 bit floating point Examples of Parallel Computers

9 최신병렬컴퓨터 Chip multiprocessor: Intel Core Duo AMD Dual Core Symmetric Multiprocessor Sun Fire E25K Heterogeneous Chips Cell Processor NVIDIA 8800 GT Clusters Supercomputers BlueGene/L Intel core duo Two 32-bit Pentium processors each has its own 32K L1 D and I cache shared 2MB or 4MB L2 cache, fast communication through shared L2 coherent shared memory 사용 : 보통개인용 PC

10 AMD Dual Core Opteron Two AMD64 processors each with 64K L1 D and I cache each with 1MB L2 cache coherent shared memory Intel 과 AMD 비교 main difference L2 cache position AMD... o more core private memory o easier to share cache coherency info with other CPUs o more general SMP architecture o preferred in multi chip systems Intel... o core can use more of the shared L2 at times o lower latency communication between cores o preferred in single chip systems

11 Generic SMP 멀티코어와멀티CPU Use: Both multi-core and multi-cpu PCs single logical memory image uniform or non-uniform memory architecture shared bus often bottleneck small number of processors 8, 16, Sun Fire E25K Use: High-end servers from Sun Sun의 High-End servers 18 E25K boards, 4 cores each, two hardware threads each core can access up to 16GB of memory uniform memory access latency directory based cache coherence protocol

12 Cluster Low-core largre-scale parallelism parallel computers made of commodity parts a number of boards each with... small number of CPUs RAM disk connected by commodity interconnect, e.g. fast Ethernet good price / performance memory not shared between boards message passing Cell Processor PlayStation 3, Roadrunner Supercomputer with Opterons SONY, IBM and Toshiba 64-bit PowerPC with two hardware 8 Synergistic Processing Elements 256KB of on chip memory per SPE dual 12.8GB/s memory bandwidth no coherent memory for SPEs, must be managed by programmer Use: PlayStation 3, Roadrunner supercomputer (w/opterons)

BlueGene/L IBM Supercomputer CPU clock 770MHz 65,536 dual core nodes each node PowerPC 440 processor 4 floating point ops per node per clock 32K L1 I and D cache per node L2 prefetch buffer 4MB of

13 BlueGene/L IBM Supercomputer CPU clock 770MHz 65,536 dual core nodes each node PowerPC 440 processor 4 floating point ops per node per clock 32K L1 I and D cache per node L2 prefetch buffer 4MB of shared L3 cache 512MB of shared off chip RAM Use: Supercomputing Interconnection Networks Each node has PE and memory routing follows the shortest path through the available links a) 2D torus, b) 3-cube

14 Interconnection Networks Each node has PE and memory fat tree multiple roots to avoid congestion Interconnection Networks Omega Network processors on the left memory modules on the right can block

Heterogeneous Chips 멀티코어대신특별한코프로세서 GPU FPGA Cell Hybrid Programming Model Main

compute intensive parts 2010-03-11 29 NVIDIA CUDA NVIDIA Compute Unified Device

blocks 8192 registers per SM 32 threads processed in 4 clock cycles different

15 Heterogeneous Chips 멀티코어대신특별한코프로세서 GPU FPGA Cell Hybrid Programming Model Main CPU performs hard to parallelize portion Attached processor (GPU) performs compute intensive parts NVIDIA CUDA NVIDIA Compute Unified Device Architecture (CUDA) 8 SIMD cores per SM on chip memory 16KB, organized into 16 blocks 8192 registers per SM 32 threads processed in 4 clock cycles different SM cannot synchronize or communicate atomic operations on global memory

Multiple Instruction Streams 를이용한병렬화 2010-03-11 31

많은메모리계산이가능 하지만, 그리간단한문제가아님 병렬화지원컴파일러가없음 ALU REGISTERS L1

16 Multiple Instruction Streams 를이용한병렬화 왜병렬처리시스템인가? 슈퍼컴퓨터혹은고성능컴퓨팅시스템 거대규모계산문제를빠르게처리가가능 왜? 많은메모리계산이가능 하지만, 그리간단한문제가아님 병렬화지원컴파일러가없음 ALU REGISTERS L1 CACHE FETCH/ DECODE UNIT Main Memory I/O Devices L2 CACHE

17 병렬컴퓨팅 공유메모리 (Shared-Memory) Intel quad-core Nehalem micro-architecture AMD Barcelona (quad-core) AMD Sanghai (quad-core) Sun Niagara Distributed-Memory IBM BlueGene/L Cell (see Mini-cores Intel Teraflops GPUs 병렬프로그래밍모델 How to transfer data between processors? Can be a key scalability bottleneck 1-sided models better at latency hiding How do we program the parallel machine? Single Execution Stream Data Parallel, e.g. HPF Multiple Execution Streams Partitioned-Local Data Access :MPI Uniform-Global-Shared Data Access :OpenMP Partitioned-Global-Shared Data Access : Co-Array Fortran Uniform-Global-Shared + Partitioned Data Access

18 쓰레드의개념 병렬화의기본단위로쓰레드 : thread Stream of instruction를실행하기위한모든것을포함 Private program text A call stack A program counter 다중쓰레드사이의메모리는공유 메모리참조메커니즘.. Shared Memory single address space easy to use easy to create inefficient programs through non-local references easy to create race conditions typically requires hardware support to make it coherent A A=B B P0 shared memory load/stores 0-sided model P

19 Memory Reference Mechanisms One-side communication single address space direct load/store on local memory get/put on remote memory, not coherent must use synchronization to ensure coherency simpler hardware, more burden on software A P0 put B P1 remote memory access (RMA) 1-sided model Memory Reference Mechanisms Message Passing no shared address space most primitive least hardware support can directly access only local memory send / recv used to exchange data between processors claimed to be easier to debug communication is more explicit and easier to find in programs A P0 receive send message passing 2-sided model B P

Not a good model : PRAM extend RAM to parallel computers PRAM doesn't work well as communication cost

20 Models of Computation 대표적인성공순차코딩모델 : Random Access Machine (RAM) model Known as the von Neumann model Here, RAM is not random access memory. Not a good model : PRAM extend RAM to parallel computers PRAM doesn't work well as communication cost is ignored Models of Parallelism A good model : CTA Stands for Candidate Type Architecture Makes useful predictions about real performance

21 멀티코어아키텍처에서프로그래밍 멀티코어 / 매니코어에서우수한병렬성능은 프로세서 / 코어사이의통신과동기화를최소화 효율적인병렬알고리즘디자인 알고리즘레벨에서 concurrency 사용 메모리대역폭은매우제한됨 (bytes/flop) IO 는 bottleneck 이다. Flops 는거저얻지만대역폭은매우고가이다 예제프로그램 Counting 3s

22 예제 1 : Iterative sum 순차코드 vs Pair-wise 합 1: sum = 0 ; 2: for ( i = 0 ; i < n ; i ++ ) 3: sum += x[ i ] ; 순차합순서. The order of combining a sequence of numbers (7, 3, 15, 10, 13, 18, 6, 4) when adding them to an accumulation variable 순차코드 : counting 3s #include <stdlib.h> #include <stdio.h> #include <time.h> void dtime(); int *array; const int length = ; int count; const int iters = 10000; /* artificially multiply work */ int count3s() { int i, j; int count = 0; for (j = 0; j < iters; j++) { for (i = 0; i< length; i++) ){ if (array[i] == 3) { count++; } } } return count; } static void make_array() { int i; array = (int *)malloc(length * sizeof(int)); for (i = 0; i < length; i++) array[i] = i % 10; } int main(int argc, char **argv) { make_array(); double stime, etime, wtime; dtime(&stime); printf("%d\n", count3s()); dtime(&etime); printf("elapsed Time = %12.8lf (sec) \n ",etime-stime); return 0; }

23 일반적인컴파일러처리과정 병렬처리시스템 Organization of a multi-core computer system: - Each processor has a private L1 cache; - it shares an L2 cache with its chip-mate -and shares an L3 cache with the other processors

24 병렬합 Pair-wise 합 Summing in pairs. The order of combining a sequence of numbers (7, 3, 15, 10, 13, 18, 6, 4) by (recursively) combining pairs of values, then pairs of results, and so on Thread 프로그래밍모델 Schematic diagram of data allocation to threads. Allocations are consecutive indices

Thread 0 Thread 1 Thread 2 Thread 3 2010-03-11 49 Race condition One of several possible interleavings

25 Multithreaded system 4 개의쓰레드를이용한배열합 1: sum = 0 ; 2: for ( i = start ; i < end ; i ++ ) 3: sum += x[ i ] ; 병렬화방법 인덱스 i는 local로stack 공유메모리는 sum, x 각각의쓰레드에다른값 0 start, end Thread 0 Thread 1 Thread 2 Thread Race condition One of several possible interleavings of references to the unprotected variable count, illustrating a race condition. : locking 필요

26 공유메모리정리사항 용어정리 Thread ~ instruction stream을실행하기위한모든것이포함된유닛 Race condition ~ 한실행의결과가두가지실행시간에의존함 Mutex ~ mutual exclusion을제공하는오브젝트, 2개의상태를갖음 Lock contention ~ multiple threading 할경우한개의쓰레드가 critical 세션을위하여대기하는추가시간 Granularity ~ 서로상호통신하는프로세스주기 False sharing ~ locally 데이터가물리적인 cache lined을공유함 Tachyon: Quad-Core AMD Processor (Barcelona) Core 1 Core 2 Core 3 Core 4 64KB L1 64KB L1 64KB L1 64KB L1 512KB L2 512KB L2 512KB L2 512KB L2 2MB L3 Memory I/O Direct Connect Architecture, AMD CoolCore Technology Integrated DDR2 DRAM Controller AMD Balanced Smart Cache, AMD Wide Floating Point Accelerator

27 Results on KISTI supercomputer Tachyon Initializing array with 16 threads Array size: elements, Gigabytes With branch With no 3s Running serial test Running with false sharing Nthread= Nthread= Nthread= Nthread= Nthread= Running with padded counters Nthread= Nthread= Nthread= Nthread= Nthread= Running OpenMP parallel for Nthread= Nthread= Nthread= Nthread= Nthread= count = 0 Running OpenMP reduction Nthread= Nthread= Nthread= Nthread= Nthread= count = 0 Running bcopy Nthread= Nthread= Nthread= Nthread= Nthread= count = 0 Running with local counters Nthread= Nthread= Nthread= Nthread= Total Elapsed Time (sec) Nthread= AMD Barcelona Chip : Tachyon 16GB 배열 : counting 3s 예제 컴파일옵션 icc mcmodel=medium이필요

28 Multi-core and Parallel Performance Tuning Techniques Parallel Performance Metrics The simplest parallel performance metric is always wallclock time. Represents the "time to solution CPU time is even less useful here than in the single processor case. Hardware performance counters can still be used to assess overall performance as well. The parallelism in the application introduces the concept of scalability and two new metrics to consider: Speedup Parallel efficiency

29 Parallel Performance Metrics : Speedup Speedup is the ratio of the time for a single processor to that for N processors, given the same input: S(N) = N 0 t(n 0 ) /t(n) This is a measure of how much faster an application i becomes as more processors are used. Ideally, speedup would be exactly equal to the processor count: S ideal (N) = N superlinear speedup the speedup on N processors is greater than N Elapsed Times and Speedup

30 Amdahl's Law Amdahl's Law : 1967 An observation on the practical limits of speedup for a given problem The maximum speedup that can be achieved by that application is: S max = 1 / (1-p) Note that this does not consider other limiting factors such as memory, interconnect, or I/O bandwidth Measuring the Performance of Parallel Applications For parallel applications with strong scaling characteristics, timing is absolutely critical to assessing parallel performance. Timings needed to compute speedups Speedups needed d to compute parallel l efficiency i Profiling can be used to identify performance bottlenecks in parallel applications. In parallel, performance bottlenecks are parts of the code

31 Interconnect Characteristics Performance characteristics bandwidth 6000 Bandwith (MPI1) 5000 Bandwith (MPI2) Band dwidth (MB/s) p595 p690 x6420 Ban ndwidth (MB/s) p595 p690 x Mesage Size(Bytes) Mesage Size(Bytes) Timing of Parallel Programs wallclock timing /usr/bin/time. it is usually a good idea to instrument your application with timing calls around important sections of the code. MPI (C/C++/Fortran): MPI_Wtime

32 Profiling of Parallel Programs Profiling parallel program is often difficult. Profiling tools included with compilers typically not designed for use with concurrent programs. two parallel profiling tools Tau TAU (Tuning and Analysis Utilities) is a set of tools for analyzing the performance of C, C++ and Fortran programs. Totalview

Integ

Integ HP Integrity HP Chipset Itanium 2(Processor 9100) HP Integrity HP, Itanium. HP Integrity Blade BL860c HP Integrity Blade BL870c HP Integrity rx2660 HP Integrity rx3600 HP Integrity rx6600 2 HP Integrity