[Multi-Core & GPU Programming] Basic Parallel Architectures
"Basic Parallel Architectures"
[ILP(Instruction Level Parallelism)]
· Code는 순차적으로 작성되지만, 그중 일부(= Some of Them without Dependencies)는 병렬로 실행 가능· Superscalar Processor : HW가 실행 시점에 독립적인 명령어를 동적으로 찾아내어 자동으로 병렬 실행하는 장치
→ 물리적으로 Single Core
→ 1개의 Core 안에 명령어 실행 Unit(Execution Unit)을 여러 개 두어 한 번에 여러 명령어 처리
→ Dynamic Scheduling : HW가 실행 시점에 실시간으로 명령어의 순서 결정
→ OoO(Out of Order) : 명령어의 원래 순서와 상관없이, 준비된 명령어부터 먼저 실행
▣ 순차 처리
· 총 5 Cycle 소요
▣ 병렬 처리
· (1), (2), (3)은 서로 독립적이므로 동시에 실행 가능
· (4)은 (1), (2) 결과가 나올 때까지 대기해야 하는 데이터 의존성 존재
· (5)은 (3), (4) 결과가 나올 때까지 대기해야 하는 데이터 의존성 존재
→ 총 3 Cycle 소요
→ Execution Unit은 2개면 충분 (① (1), (2) 연산 → ② (3), (4) 연산 → ③ (5) 연산)
[Superscalar Processor]
> Scalar Processor
· 1개의 Execution Unit → 매 Cycle마다 1개의 명령어만 Pipeline에 진입
· 5개 병렬 처리 가능
> Superscalar Processor
· 2개의 Execution Unit → 매 Cycle마다 2개의 명령어만 Pipeline에 진입
· 10개 병렬 처리 가능
· Program을 새로 짤 필요 없이 HW가 알아서 속도를 향상 시킴
· 명령어 간의 의존성 때문에 Processor의 처리 능력을 무한정 늘려도 성능 향상에는 한계 발생
→ 일반적인 Code에서 서로 아무런 연관성 없이 동시에 실행될 수 있는 명령어의 개수는 평균적으로 3~4개 like 덧셈 명령어 (4)
∴ Processor의 Execution Unit(ALU)을 8개, 16개, … 늘려도 성능 향상에 한계 존재
[Multi-Core Processor]
· 각 Core의 주파수↓(x 80%) / Throughput = (# of Core) x 80%
** Processor의 주파수를 높이면 성능↑ But, 전력 소모와 발열↑↑↑
→ 만약 Multi-Core의 모든 Core를 Single-Core 수준의 최고 주파수로 돌린다면 칩이 소모하는 전체 전력 감당 불가
→ 칩이 타버리거나 System Down 가능
∴ 주파수를 조금만 낮춰도 전력 소모는 크게 감소 → 남는 전력 여유분을 활용해 더 많은 Core를 칩에 집적 가능
· Multi-Core 환경에서 기존의 순차 Code를 그대로 돌리면, Core당 클럭 주파수가 낮기 때문에 오히려 Single-Core보다 성능 저하
∴ Multi-Core를 제대로 활용하려면 Programming 방식 변화 필요 → Thread 활용
[Thread]
· Subroutine 호출 : Program 실행 중에 특정 Subroutine이 필요하면 해당 Code로 제어 흐름 이동
→ Subroutine이 종료되어 복귀할 때까지 원래 실행하던 Code 대기 = 제어 흐름이 하나뿐이며 순차적으로 실행
· Thread 생성 : 원래의 제어 흐름과 병렬로 실행되는 새로운 흐름을 만들어내어 동시에 작업 수행
> 공유 자원 : Code, Heap, 주소 공간 등을 공유
> 개별 자원 : PC(Program Counter), Stack, Register 등은 Thread마다 독립적으로 보유
<Single-Thread Code>
· 0~N까지 순서대로 하나씩 계산 수행
· MAC 연산이 병렬 처리 가능한 이유 = 각 반복은 배열의 서로 다른 Index만(i) 접근하여 서로 독립적
→ [i - 1]이 계산에 사용되는 경우 이전 단계의 결과가 필요하므로 데이터 의존성 존재
<Multi-Thread Code>
· void mac : 각 Thread가 자신의 ID(tid)를 보고, 전체 배열 중 자신이 맡은 범위가 어디인지 계산하여 그 부분만 연산하도록 설계
· std : : thread : 새로운 Thread를 생성하여 mac 함수를 동시에 실행· thread.join( ) : 모든 Thread가 작업을 마칠 때까지 Main Thread가 대기
· mac(1, 2) : 1번 Thread → tid = 1 → int idx = 1 * (100/2) + i; → 50번 Index부터 시작
[OpenMP(Open Multi-Processing)]
· Programmer가 직접 Thread를 관리하는 대신 #pragma omp parallel for 지시어 사용
· Programmer가 Loop의 각 반복이 독립적임을 선언 시, OpenMP가 자동으로 Multi-Thread Code 생성
→ 2개의 Core가 똑같은 명령어를 실행하는데, 굳이 2개의 Unit이 각각 똑같은 명령어를 읽고(Fetch) 해석(Decode)할 필요 X
→ Fetch/Decode Unit은 하나만 두고 Execution Unit(ALU)만 여러 개 두는 것이 훨씬 효율적
[Vector Processing]
· 1개의 명령 Stream & Data는 여러 개를 한 번에 처리 (다루는 Data 구간만 다름) = Single Instruction & Multiple Data
→ 각 Core가 똑같은 명령어를 반복해서 Fetch/Decode하는 비효율을 해결
<c[i] = a[i] * k[i] + b[i] * k[i] (Multi-Core + SIMD)>
· #pragma omp parallel for : 여러 CPU Core가 구간을 나누서 Loop를 동시에 실행
· i += 8 : 32-bit 정수 8개를 한 번에 담아서 처리 = 한 번 반복할 때마다 원소 8개씩 처리 ∴ 8씩 증가
· __m256i : 256-bit Vector Register = 32-bit 정수 8개 저장 가능 (i = integer)
> 8개의 32-bit 정수를 읽어서 Vector Register에 저장
· __m256i A = _mm256_load_si256((__m256i*)(&a[i]));
→ A = [a[i], a[i+1], a[i+2], a[i+3], a[i+4], a[i+5], a[i+6], a[i+7]]
· __m256i B = _mm256_load_si256((__m256i*)(&b[i]));
→ B = [b[i], b[i+1], b[i+2], b[i+3], b[i+4], b[i+5], b[i+6], b[i+7]]
· __m256i K = _mm256_load_si256((__m256i*)(&k[i]));
→ K = [k[i], k[i+1], k[i+2], k[i+3], k[i+4], k[i+5], k[i+6], k[i+7]]
> 32-bit 정수끼리 Lane별 곱셈 수행 (mullo : 32-bit x 32-bit 곱셈 결과 중 하위 32-bit만 저장)
· __m256i C1 = _mm256_mullo_epi32(A, K);
→ C1[0] = A[0] * K[0], C1[1] = A[1] * K[1], …, C1[7] = A[7] * K[7]
→ C1 = [a[i]*k[i], a[i+1]*k[i+1], …, a[i+7]*k[i+7]]
· __m256i C2 = _mm256_mullo_epi32(B, K);
→ C2[0] = B[0] * K[0], C2[1] = B[1] * K[1], …, C2[7] = B[7] * K[7]
→ C2 = [b[i]*k[i], b[i+1]*k[i+1], …, b[i+7]*k[i+7]]
> Lane별 Vector 덧셈 수행
· __m256i C = _mm256_add_epi32(C1, C2);
→ C[0] = C1[0] + C2[0], C[1] = C1[1] + C2[1], …, C[7] = C1[7] + C2[7]
→ C = [a[i]*k[i]+b[i]*k[i], a[i+1]*k[i+1]+b[i+1]*k[i+1], …, a[i+7]*k[i+7]+b[i+7]*k[i+7]]
> 계산한 Vector를 다시 메모리에 저장
· _mm256_store_si256((__m256i*)(&c[i]), C);
→ C[i] = C[0], C[i+1] = C[1], …, C[i+7] = C[7]
** a[i] ~ a[i+7], b[i] ~ b[i+7], k[i] ~ k[i+7], c[i] ~ c[i+7] → 서로 다른 구간을 다뤄서 병렬화 가능
▣ SIMD Width
· 한 번에 처리 가능한 개수 = (# of Vector Register Bit) / (# of Data Type Bit)
→ SSE = 128-bit / AVX2 = 256-bit / AVX-512 = 512-bit
Ex. 32-bit int ▶ SSE = 128/32 = 4, AVX2 = 256/32 = 8, AVX-512 = 512/32 = 16
64-bit double ▶ SSE = 128/64 = 2, AVX2 = 256/64 = 4, AVX-512 = 512/64 = 8
<64-bit Double>
▣ Vectorization
· Compiler가 자동으로 Vector 명령을 생성 가능 (Compiler가 코드 분석을 해서 병렬성이 보이면 SIMD화)
→ But, Programmer가 직접 원하면 Intrinsics를 사용 가능
> Compiler의 자동 벡터화
· 단순한 배열 연산 Loop
→ Compiler가 {Loop 반복끼리 독립적 & 메모리 의존성 X & 정렬/Aliasing 문제 X} 판단 시 자동으로 SIMD 명령으로 변경
△ 코드가 깔끔 & 이식성↑
▼ Compiler가 항상 최적으로 해주지는 않음 & 복잡한 경우 벡터화를 포기할 가능성 존재
> Intrinsics(내장 함수) 사용
· "_mm256_*" 함수를 직접 작성
△ SIMD 동작을 직접 더 제어 가능 & 원하는 벡터 명령을 명시적으로 사용 가능
▼ 코드가 복잡도↑ & 특정 ISA(like AVX2)에 종속적이고 유지보수성↓
▣ SIMD의 조건문 처리
· 한 원소씩 보면서 True → if 구문 실행 / False → else 구문 실행
> SIMD
· 여려 원소를 한 번에 처리 ▶ 어떤 원소는 True, 어떤 원소는 False
> Predication / Masking
① 먼저 각 원소에 대해 조건에 대한 True/False 검사
② 결과를 mask bit로 생성 (True = 1 / False = 0)
③ if에 해당하는 연산을 mask가 1 Lane에만 적용 / else에 해당하는 연산은 mask가 0인 Lane에만 적용
→ 실제로는 분기해서 따로 실행하지 않고, 한 벡터 안에서 어떤 원소만 활성화할지 mask로 제어
> Low Utilization (낮은 활용도)
SIMD는 원래 여러 데이터를 같은 방식으로 처리할 때 효율적인데 분기가 생기면 Lane들이 제각각 행동하려 하므로 효율 감소
SIMD는 원래 여러 데이터를 같은 방식으로 처리할 때 효율적인데 분기가 생기면 Lane들이 제각각 행동하려 하므로 효율 감소
▣ Matrix Multiplication
· 일반 SIMD보다 더 큰 단위의 행렬 연산을 다루기 위해 Tile 형태의 Register TMUL(Tile Matrix Multiply) 같은 전용 연산을 제공
· Vector Register : 길게 늘어선 1차원 데이터 묶음
· Tile Register : 2D Register Files → 작은 행렬 블록 같은 데이터 묶음
※ TMUL : Tile 단위의 행렬 곱셈/누산 연산
> CPU
· add : 두 값 더하기
· mul : 두 값 곱하기
· vector mul : 여러 값 각각 곱하기
> AMX
· 행렬 블록 전체를 대상으로 하나의 명령이 훨씬 더 많은 Multiply-Accumulate를 수행하도록 함
→ Instruction당 일을 훨씬 많이 수행
[Terminology]
> SISD (Single Instruction, Single Data)
· 하나의 명령이 하나의 Processing Unit에 들어가서 데이터 하나를 처리
→ 전통적인 순차 처리 모델 (Scalar Processor, Superscalar Processor)
> MIMD (Multiple Instruction, Multiple Data)
· 여러 Processing Unit이 각자 다른 명령과 다른 데이터를 처리 = 각 Core가 독립 실행
→ Multi-Core CPU (Multi-Core Processor)
> SIMD (Single Instruction, Multiple Data)
· 하나의 명령이 여러 Processing Unit으로 Broadcast되고, 각 Processing Unit이 서로 다른 데이터 조각을 처리
→ Vector Processor 또는 GPU의 기본 아이디어 (Vector Processor)
> MISD (Multiple Instruction, Single Data)
· 같은 데이터가 여러 Processing Unit을 거치고, 각 Processing Unit은 서로 다른 연산을 수행
→ Pipeline / Systolic Array
[Reference]
· 1_arch_mgp_2026 (MGP) - Yongjun Park
댓글
댓글 쓰기