포항공대 병렬 프로그래밍 강의 1

규규·2024년 1월 24일

병렬 프로그래밍

목록 보기

1/11

1. Introduction to Algorithms

강의 자료 :
- Matloff 2015 온라인 교재 활용
- Programming on Parallel Machines: CPU, Multicore, Clusters and More
- https://www.freetechbooks.com/topics

2. Parallel Algorithms and Parallel Programs

Introduction to Parallel Processing

병렬 컴퓨터 종류
- Multiprocessor
  - Symmetric Multiprocessor (SMP)
    - 각 core 게 동일한 위치에 있고, 메모리 접근 시간이 동일 함
    - Normally Bus Based
  - Message Passing
    - 여러 컴퓨터를 사용 (Multicomputer)
    - 메모리 접근을 각각 함
    - 프로그래밍이 어려움
    - symmetric 하지 않아, 최적 성능 달성이 어려움
  - Distributed shared memory (DSM)
    - sw 적으로는 memory 를 공유하지만, 물리적으로는 공유 안 함
    - shared virtual memory (SVM)
    - provide shared memory capability in a distributed memory machine using software
Flynns' Classification
- number of instruction, data streams 에 따라 구분
- 분류
  - SISD : Single instruction stream, Single data stream (1개 CPU)
  - SIMD : Single instruction stream, Multiple data streams (GPU)
  - MISD : Multiple instruction streams, Single data stream (희귀)
  - MIMD : Multiple instruction streams, Multiple data streams (가장 범용적, 독립된 컴퓨터 여러개가 협력)
성능 평가 기준
- Speedup = Time (1 processor) / Time (p processors)
- Efficiency = Sppedup / p (이상적인 병렬화 대비 어느 정도 인지..)
- Cost = Execution time on parallep computer * p
Trends in speedup
- Ahmdalh's Law (1960??)
  - Speedup = 1 / [ (1-f) + (f / p)]
  - f : 병렬화 가능한 비율, p : 병렬 processor 개수
  - Key message : 병렬화로 성능 개선은 serial portion of the program 에 의해 제한 됨.
- Gustafson's Law (scaled speedup) (2010??)
  - Ahmdalh's law 보다 생각보다 더 빨라져서 새로운 법칙 등장
  - Speedup = (1 - f) + (p * f)
  - Key idea : p 가 커질수록 처리하는 Workload (size of data) 가 커짐 (??)

Introduction to Parallel Programming

Sequential Algorithm, Parallel Algorithm, Parallel Program
- Sequential algorithm
  - 1개 CPU 에서 execute 되는 것을 목표로 설계 됨.
  - A problem 은 formal 하게 정의 됨 : Input, Condition, Output
  - Algorithm description : pseudo code 로 표현, Computer system 과는 독립적
- Parallel algorithm
  - parallel computer 에서 parallel executtion 을 목표로 설계 됨.
  - sequential algorithm 과는 다름. Core 간 협력을 묘사. computer system 과는 독립적
- Parallel program
  - parallel computer system 에서 p core 개수에서 실행 됨
  - High speedup, efficiency characteristics 를 추구
  - superlinear speedup : p 개 processor 를 사용해서 p 배 이상으로 빨라지는 경우 (data size, memory 계층 구조 (cache) 를 더 잘 활용 할 경우 가능)
Creating a Parallel Program
- 절차
  1. Sequential algorithm 을 decomposition 하여 순차적 실행 해야 할 것을 n 개의 task 로 분해 함
  2. tasks 들을 p 개의 processes 로 assign 함
  3. processes 들이 어떻게 통신 할 것인지 정함 (Orchestrate the communication)
  4. processes 들을 processors(cores) 로 mapping 함. 1개의 core 에 여러개의 process, thread 도 할당 가능. 단, 1개의 thread 만 할당하는게 효율은 가장 좋음.
- example
  1. Matrix-Vector Multiplication
  - rows * column 곱에서 여러개의 rows 를 쪼개서 process 마다 따로 따로 수행
  - 자세한 내용은 pdf 참조
  1. Parallel Merge Sort
  - Merge Sort : array 를 여러 partition 으로 쪼개서 각각 sorting
  - partition 된 부분을 각각 process 가 진행
  - 한 stage 가 종료되면 merge 하고, 다음 stage 진행
  - stage 마다 barrier 가 존재 (한 stage 의 모든 processes 가 종료되야 다음 stage 진행 가능)
  - 자세한 내용은 pdf 참조
Parallel Programming Methods
- Task Farming
- Data Parallelism
  - Merge sort 에서 사용하는 방법
  - fork-join 이 사용하는 방식
  - 제일 많이 사용
- Divide and Conquer

Writing Parallel Programs

Sequential Program and Parallel Program
- 직렬 프로그램은 operation 을 순서대로 작성하면 됨
- 병렬 프로그램은
  - 각 core 가 어떤 작업을 하는지
  - core 끼리 어떤 data 를, 어떻게 주고 받을지
  - 작업 간 언제 기다려야 하는지 (global data item 접근, Barrier synchronization (모든 core 의 작업이 끝나는 것))
Distributed Memory, Shard Memory Parallel Programming
- 분산 메모리는 각각 core 가 각각 memory 를 가짐
  - data 를 보낼 때는 a core 에서 send, b core 에서 receive 작업이 필요
  - 일반적으로, 1개의 program 을 작성해서 각 core 에 execution 을 보냄.
  - 각 core 는 고유 id 가 있어서 id 를 보고 실행 (???)
- 공유 메모리는 모든 core 가 공유하는 global memory space 가 있다고 가정
  - data 를 공유하기 위해서, 공유 메모리 공간을 사용
  - Multicast : 1 core 가 여러개의 core 로 보내는 것
  - Broadcast : 1 core 가 다른 모든 core 로 보내는 것
  - shared memory 에서는 일반적으로 특정 library 함수를 사용 write,read 는 그냥 하면 되나, 특별히 기다리거나 보호된 변수를 사용해라 할 때 특정 library 함수 사용
Programming Interface (API) Used for Parallel Programming
- Distributed Memory Parallel Programming
  - 분산 메모리 병렬 프로그래밍이 더 어려움. 디버깅도 어려움. explicit send/receive 가 필요하고, data 를 보내거나 global synchronization barrier 존재 시 기다려야 함.
  - MPI (Message Passing Interface: IEEE standard)
  - Threads
    - pthread.h(POSIX threads) : UNIX 에서 기본 정의된 library
    - java threads : java 활용 시 사용
- Shared Memory Parallel Programming
  - 공유 메모리 병렬 프로그래밍이 훨씬 쉬움. 동일 memory address 를 사용하기 때문에 단순하게 read, write 만 하면 core 간 data 공유 가능. globally shared variable 만 지정하면 됨.
  - 보통 fork-join parallel 방법을 사용함. main 프로그램을 1개의 core 에서 실행하다가 여러개의 thread 를 생성 (spawns) (t-1 core). 모든 작업이 끝나야 하는 barrier 존재.
  - OpenMP
    - 제일 많이 씀
  - OpenACC
  - OpenCL
    - Nvidia 를 제외한 회사들의 연합
  - CUDA
    - Nvidia GPU 사용 시 사용
    - Graphics 를 위해 제작 됬으나, 일반적인 병렬 프로그래밍도 가능함
    - Nvidia GPU 가 인기 있어서, OpenCL 보다 많이 활용 됨.

3. Shared Memory Parallel Programming and OpenMP

Shared Memory Parallel Programming

Shared 의 개념
- Shared memory 의 global variables 는 physically 동일한 memory address 를 사용함
- stack 공간을 활용하는 local variable 의 경우에는, 각각의 processor 가 각각의 SP (Stack Pointer) register 를 가지기 때문에, 각각의 processor 는 own independent copy of the local variable 을 가지므로, 각각의 thread 마다 local variable 의 값은 다름.
- Matloff 교재 3.1 chapter 참조
Typical structure and execution method of parallel programs
- sequential program 과 같은 결과를 위해서 각각의 thread 가 서로 기다려주는 과정 등이 필요함
- 그러나 위 과정이 너무 힘들어서, 편의성을 위해서 1개의 program 을 작성하고 컴파일 한 다음 모든 core 에 보내서 실행 시킴. 이 때 각 core 는 별도의 ID 를 가져서, 병렬화를 시킴

Introduction to OpenMP

Overview of the OpenMP API
- API
  - API 는 service 를 제공하는 software interface
  - API 에는 Compiler directives (컴파일 할 때 어떻게 해라), 환경 변수, Constant, library function 이 존재
- OpenMP (Open Multi-Processing) API 는 공유 메모리에서 가장 많이 사용
- C, C++, Fortran 지원
- 여러개의 회사 consotium 으로 운영 됨. (www.openmp.org)
- 같은 프로그램을 직렬로도, 병렬로도 가능
- 병렬 프로그래밍의 simplicity 를 추구! OpenMP 를 안 쓰고 정말 잘 짠 병렬 프로그래밍보다는 느림.
- 어쩔때는 OpenMP 안 쓰고 직렬이 더 빠를 수도 있음.. 잘 짜야 빠름..
Basic OpenMP Usage
- Linux 는 gcc, OpenMP 를 지원
  - code 에 #include <omp.h>, compile 시 gcc -fopenmp 만 추가
    - fork-join 가능 : #pragma omp parallel

OpenMP Core Elements

Thread Creation and Forking
- #pragma omp parallel
  - a "team" of threads is created and started (forked)
  - 사용 할 threads 개수 설정
    - Default : 현재 computer 의 core 개수 (lscpu 로 확인)
    - Compile directive : pragma omp parallel num_threads(int)
    - Environment variable : OMP_NUM_THREADS (setenv OMP_NUM_THREADS 4)
    - int omp_get_threads_num(); 으로 사용하는 thread 개수 확인 가능
Work Sharing - Assigning work to threads
- Loop iteration 을 threads 로 나누어서 할당 (가장 많이 사용)(#pragma omp for)
- scheduling method 는 Chunkg, type 으로 분류
  - Chunk
    - thread 1개에 몇 개의 iteration 을 할당 할 것이냐
    - default 값은 전체 loop iteration 개수를 thread 개수로 나눔.
  - type
    - static, dynamic, guided 3가지 중 선택
    - Static 은 default, 모든 thread 에 chunck 단위로 할당
    - Dynamic 은 효율을 조금 더 높이기 위해, 초기에는 static 을 사용하나, 나머지 일들은 chuck size 를 조절해서 동적으로 할당.
    - Guided 는 Dynamic 을 조금 더 개선. 처음에는 chunk 단위로 할당. 그 다음 할당은 chunk size 를 절반씩 줄여가며 할당.
  - Examples
    - #pragma omp parallel for
    - #pragma omp parallel for schedule(dynamic)
    - #pragma omp parallel for schedule(guided,4)
Shared and Private Variables
- default 로 OpenMP code 의 대부분의 variables 는 shared (visible, modifiable by all threads)
- Shared
  - parallel region 바깥에 선언된 data 는 다 shared
  - 잘못 사용해도 따로 warning, error message 가 없음. 따라서 항상 example 을 통해서 output 이 잘 나왔는지 확인을 해야 함.
- Private
  - parallel region 내에서 data 를 declared 하면 private variable.
  - 특이하게 for loop 에서 index 변수는 (ex:"i") 바깥에서 선언이 됬다고 하더라도, default 로 private 임
- Firstprivate
  - private 이랑 똑같은데, parallel region 바깥에서 초기화가 가능
- Lastprivate
  - data 값 바꾸고 parallel region 나가면, 바뀐 값이 바깥에서 반영 됨
- Threadprivate
  - shared 와 같지만, parallel region 안에서만 private 로 작동 함.
- Reduction
  - for 구문 안에서 공유 변수의 값을 수정하려고 할 때, 충돌을 방지
  - ex : + reduction - 썻던 값들이 다 합쳐짐
  - +, -, &, &&, ||, max, min 다 가능
- Example
  - #pragma omp parallel for private(i,j) shared(input_data) reduction(+:sum)
  - 의미 : i/j 는 private, input_data 는 shared, sum 값은 parallel block 나갈 때 다 더한다는 의미
Thread Synchronization
- #pragma omp parallel for 을 사용하면 default 로 block 종료 시 모든 threads 를 synchronize (implicit barrier 라고 불림)
- Barrier : 모든 thread 가 끝날 때까지 먼저 끝난 thread 는 기다려야 함.
- Nowait : 먼저 끝난 thread 는 알아서 계속 실행
- Ordered : 직렬과 동일
- Single : 맨 먼저 온 thread 1개만 실행 (나머지 thread 는 그 block 무시)
- Master : master thread (main 함수 실행하는 thread) 만 실행 가능
- Critical : 어느 한 순간에 어느 한 thread 만 실행 가능 (race 에서 shared 보호 가능)
- Atomic : Critical 과 유사하나, memory update (write) 부분에 대해서만 보호
- If : 어떤 조건에만 병렬화를 해라
User-Level Functions and Environment Variables
- Linux environment variable : OMP_NUM_THREADS
- 주로 쓰는 OpenMP 함수
  - omp_set_num_threads(int) : thread 개수 설정
  - int omp_get_num_threads() : thread 개수 return
  - int omp_get_thread_num() : current thread id return
  - omp_init_lock(omptlock_t) : mutual exclusion 을 위해 "lock" variable initialize
  - omp_destroy_lock(omp_lock_t*) : Uninitilizeds a lock
  - omp_set_lock(omp_lock_t*) : lock 이 가능할때까지 thread block
  - omp_unset_lock(omp_lock_t*) : releases a lock
- example :
  - `#pragma omp parallel for num_threads(4) reduction(+:total)
  - shared 변수에 값 update 할 때는, 여러 thread 가 동시에 update 할 경우 문제가 발생 할 수 있으므로, mutual exclusion 이 필요함. lock 을 통해서 구현
```
int total = 0;
#pragma(omp_parallel for num_threads(4)
for (i = 0; i < 10; i++){
    omp_set_lock (&lock1);
    total = total + input_data[i]; # shared 변수 값 update 할 때는 보호된 위치에서만 update 해라!
    omp_unset_lock (&lock1);
}
```

4. OpenMP Parallel Programming Examples

OpenMP Example 1 - Graphs

TODO

OpenMP Example 2 - Sorting

Merge sorting 에서는 task 병렬 기법을 활용
condition 이 true 일 때만 task 를 만듦 #pragma omp task if <condition>
"task farming" 을 구현해서 master process 가 문제를 쪼개서 수 많은 task 를 만든 다음에, core 가 free 해질 때 task farm 에서 task 를 할당 받음
load balancing 이 자동으로 됨. task 가 작을수록 더 잘 됨. 단 task 가 너무 작으면 오히려 task 관리에 overhead 가 발생 할 수도 있으므로 적절한 task size 선택이 필요함.

OpenMP Example 3 - Jacobi Method

Linear system (Ax=b) solve 를 위해 iterative method 인 jacobi method 이용
TODO

5. GPU Architecture and CUDA Programming

GPU Architecture and GPGPU Processing

CPU (Central Processing Unit)
- CPU 의 주요 용도는 general purpose computing
- 어떤 프로그램이든 실행 가능, 특정 용도의 프로그램을 빠르게 실행하는 목적이 아님
- 특정 프로그램을 돌리기 위해서는 그 프로그램에 맞춤된 hardware circuit 이 필요
- CPU Design 목표
  - CPU 는 latency (명령어 실행 시간) 을 줄이는 방향으로 설계되어 있음
  - Powerful 한 ALU (Arithmetic Logic Unit)
  - 큰 cache memory
  - complex control logic 사용 (CPU instruction 을 빨리 처리하기 위해) (large circuit area)
GPU (Graphics Processing Unit)
- image 처리
- 8bit 의 2D pixel 을 처리 할 경우가 많음. MULTIPLY 같은 single instruction 에 최적
- GPU Design 목표
  - 높은 throughput (초 당 처리하는 데이터 개수)
  - single instruction 의 latency 는 포기
  - 수백~수천개의 core. small, low performance ALU (PE 라고 부름. Processing Element)
  - Heavily pipelined PEs
  - 엄청나게 많은 SW thread 를 time-multiplexed (시분할) 로 처리
  - 크기가 작고 매우 많은 cache 사용
  - 작은 control logic
GPGPU (General Purpose GPU)
- NN inference 시에는 low precision(8bit) weight factor 사용 해도 됨.

Heterogeneous Processing

Heterogeneous parallel computing : 2개 이상의 processor 를 사용
신호 처리만을 위한 processor : DSP (Digital Signal Processor)
GPGPU Processing
- heterogeneous parallel computing with CPU, GPU
- CPU 에서 program 시작, data intensive operation 시에는 data 를 GPU memory 로 이동. GPU 연산. 결과를 CPU Memory 로 다시 이동

CUDA Programming Basics

Parallel program 실행의 3가지 방법
- Library functions 사용
  - 사용 쉬움
  - NVIDIA GPU 사용을 위한 library
    - Deep learning : cuDNN, TensorRT
    - Linear Algebra : cuBLAS, cuSPARSE, cuSOLVER
    - Signal Processing : cuFFT
    - Parallel Algorithms : nvGRAPH, NCLL, Thrust
- Compiler directives 사용
  - 사용 쉬움
  - Code 이식성이 높음
  - Ex : OpenMP, OpenCL, OpenACC
- 새로운 Programming language
  - 가장 어려움
  - 가장 높은 performance
  - 효율적인 GPU 사용을 위한 언어
    - MATLAB, PyCUDA, CUDA C, CUDA C++, OpenACC, Thrust
Heterogeneous Parallel Computing using a CPU and GPU
- 2개의 Program part 가 필요 (CPU 실행 부분, GPU 실행 부분)
- 처음에는 CPU 로 Program 실행
- low latency 필요 부분, I/O 발생 부분은 반드시 CPU
- Data 처리가 매우 많은 부분은 GPU 가 실행
- CPU memory 에서 GPU memory 로 보내기 위해 특별한 CUDA function 호출 필요 (cudaMemcpy). 함수 호출의 latency 가 길음
- GPU 연산이 끝나면 cudaMemcpy 를 다시 호출해서 GPU 에서 GPU memory 로..
- 2014년에는 "Unified Memory" 라는 가상 메모리 개념을 사용해서 CPU, GPU 가 둘 다 사용 할 수 있는 메모리 공간처럼 보이게 함. Compiler 가 알아서 CPU, GPU 의 메모리를 왔다갔다..
CUDA 사용을 위한 환경 설정
- TODO

CUDA Programming Examples

matloff 교재에 CUDA 예제 많음. 구글에도 많음.
CUDA Thread Hierachy
- CUDA 는 threads 기반으로 실행 됨 (병렬로)
- Grid : set of all threads in app. Grid 안에 Block 이 있음
- Block : 1개의 block 안에 있는 thread 는 똑같이 실행되고, data 를 쉽게 공유. Block 안에 threads 가 있음. 1개의 block 은 1개의 SM (symmetric multiprocessor) 안에서 실행.
- thread : 각 ID 가 있고, x/y/z coord 가 있음. thread 가 몇 천개..
- Grid size : programmer 는 grid size(grid 안에 block 이 몇 개인지), block size (block 안에 thread 가 몇 개 인지) 를 지정
CUDA example
- TODO

6. Hadoop and MapReduce

Apache Hadoop

Hadoop 이 Spark 로 upgrade(?) 됬음
Introduction to MapReduce
- 2004 년 Google 에서 MapReduce 라는 parallel programming model 개발. Big data 를 처리 할 때 매우 효과적.
- 데이터가 몇 MB, 1000 개면 더 느림. 1000만~ 몇 억개 일 때는 효율적
- 빠른 Web search, 빠른 data processing (ex: 특정 단어 찾기)에 주로 사용 됨.
- Main component of MapReduce program
  - Map procedure
    - Filtering and sorting of a large data set
      - Data 를 category 에 따라 정리하고 정렬하고, 분산된 여러개의 파일로 저장
      - data 를 "spreading out" 하는 개념
        
        p 개의 process 로 병렬 작업 가능
        
        write conflicts 가 없는 indexing 개념
  - Recude operation
    - Map 에서 만든 여러 개의 파일 데이터를 합치는 작업을 함 (병렬로..!)
    - 목적에 따라서 data 를 "collecting". 특정 category 를 traversing 하는 효율적인 method 사용 (index 를 활용)
Apache Hadoop
- Big data processing (TB, PB)
- Data mining 을 해서 유용한 정보 추출 (massive parallel processing 필요)
- 2014 년에 Apache Spark 가 Hadoop 을 대체 (속도가 10~100 배 더 빠름) (Hadoop 은 분산 파일 기반 시스템으로 data 저장하나, Spark 는 memory 로 data 를 처리)
- MapReduce 는 프로그래밍 언어로 실행 가능 (ex: R)

출처 :
포스텍 STAR-MOOC 병렬 프로그래밍 강의1 (이승규 교수)
https://postech.edwith.org/

강의 모음 (HPC Lab)
https://hpclab.tistory.com/4

내 udemy 강의 목록

규규

복습용 저장소

다음 포스트

포항공대 병렬 프로그래밍 강의 1

병렬 프로그래밍

1. Introduction to Algorithms

2. Parallel Algorithms and Parallel Programs

Introduction to Parallel Processing

Introduction to Parallel Programming

Writing Parallel Programs

3. Shared Memory Parallel Programming and OpenMP

Shared Memory Parallel Programming

Introduction to OpenMP

OpenMP Core Elements

4. OpenMP Parallel Programming Examples

OpenMP Example 1 - Graphs

OpenMP Example 2 - Sorting

OpenMP Example 3 - Jacobi Method

5. GPU Architecture and CUDA Programming

GPU Architecture and GPGPU Processing

Heterogeneous Processing

CUDA Programming Basics

CUDA Programming Examples

6. Hadoop and MapReduce

Apache Hadoop

CPU Parallel 동작 방법

0개의 댓글