[Multi-Core & GPU Programming] Matrix Multiplication (Multi-Threaded)

"Matrix Multiplication (Multi-Threaded)"

[Matrix Multiplication]

<C(i, j) = ∑k A(i, k) · B(k, j)>
1
2
3
4
5
6
7
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        for (int k = 0; k < N; k++) {
            C[i][j] += A[i][k] * B[k][j];
        }
    }
}
cs

** Memory Access Pattern
· Computer Memory : 행 기준 저장
· A : 같은 행을 따라 이동 → 연속된 메모리 접근 → Good
· B : 열 방향으로 이동 → 메모리 띄엄띄엄 접근 → Cache Miss↑ → Bad

[Parallelization]

▣ Column-Wise Block Striping

1
2
3
4
for i = 1 to n
    for j = p to n step P
        for k = 1 to n
            C(i,j) = C(i,j) + A(i,k) * B(k,j)
cs

· C의 Column을 Thread마다 나누어 계산 (P : 전체 Thread 수 / p : 현재 Thread의 ID)

Ex. P = 4
· Thread 0 : j = 0, 4, 8, …
· Thread 1 : j = 1, 5, 9, …
· Thread 2 : j = 2, 6, 10, … 
· Thread 3 : j = 3, 7, 11, …

> 접근 방식
· 한 Thread가 C의 한 열을 계산 → A 전체를 모두 Read & B의 특정 Column을 Read

· A : 행 기준 저장이라 접근 용이
· B : Column을 따라 읽기 때문에 메모리에서 떨어진 위치를 Read = 메모리 접근 비효율적

△ 중복 계산 X
△ 공유를 위한 추가 계산 X
△ 이론상 계산량 O(N) = N3 / P
△ Lock 필요 X

** But, 성능↓

※ False Sharing : Thread들이 실제로는 서로 다른 변수를 수정하고 있는데 해당 변수들이 같은 Cache Line 안에 들어 있어서 Cache 일관성 Protocol 때문에 서로 방해하는 현상

Ex. C[i][0], C[i][1], C[i][2], C[i][3],  … → 행 방향 저장으로 메모리에서 붙어 있음
· Thread 0 : C[i][0] 수정
· Thread 1 : C[i][1] 수정
· Thread 2 : C[i][2] 수정
· Thread 3 : C[i][3] 수정
→ 하나의 Cache Line에 존재

① 한 Thread가 Update 후 Cache 일관성 Protocol에 의해 해당 Cache Line 무효화(구 버전임을 알림)
② 다른 Thread가 Update 후 Cache 일관성 Protocol에 의해 해당 Cache Line 무효화(구 버전임을 알림)
③ 무효화의 반복
→ Coherence Traffic 폭증

∴ 명시적으로 데이터를 공유하지 않았어도, HW 입장에서는 Cache Line 단위로 공유 충돌 발생

▣ Row-Wise Block Striping
1
2
3
4
for i = p to n step P
    for j = 1 to n
        for k = 1 to n
            C(i,j) = C(i,j) + A(i,k) * B(k,j)
cs

· C의 Row를 Thread마다 나누어 계산 (P : 전체 Thread 수 / p : 현재 Thread의 ID)

Ex. P = 4
· Thread 0 : i = 0, 4, 8, …
· Thread 1 : i = 1, 5, 9, …
· Thread 2 : i = 2, 6, 10, … 
· Thread 3 : i = 3, 7, 11, …

△ 중복 계산 X
△ Lock 필요 X
△ False Sharing↓ (∵ 서로 다른 행은 떨어져 있음)

∴ Thread마다 서로 다른 행을 맡으면 같은 Cache Line을 동시에 수정할 가능성 크게 감소

** But, 여전히 B 메모리 접근으로 인한 Cache 효율 문제 존재

[Consider Caches]

· L1 Cache : 32KB ~ 64KB (Small & Low Latency & High Bandwidth)
→ float 기준 4-Byte ▶ 8K ~ 16K Elements
→ 128 x 128 x 4-Byte = 64KB ▶ 128 x 128 행렬 하나가 L1 Cache에 한번에 들어감
→ But, A, B, C 모두 필요 & 기타 변수 존재 ▶ 실제로 최대 N = 128이 아닌 N = 64

** 성능은 연산이 아닌 Cache를 최대한 활용하는 것이 핵심

[Single Thread Performance]

· Cache 효율, 메모리 접근 패턴 → Single/Multi Thread 공통 문제

∴ Single Thread에서 최적화하여 성능↑ → Multi Thread 성능↑

1
2
3
4
for i = 1 to n
    for j = 1 to n
        for k = 1 to n
            C(i,j) = C(i,j) + A(i,k) * B(k,j)
cs

▣ for k = 1 to n
· A → 처음 접근 → All Miss (= Cold Miss)
· B → 처음 접근 → All Miss (= Cold Miss)

∴ 처음 Loop 실행 → All Miss (= Cold Miss)

· A → 계속 재사용 → All Hit
· B → All Miss (= Cold Miss)    ∵ k가 바뀌면서 Column Access 발생

· A → 계속 재사용 → All Hit
· B → All Miss (= Cold Miss)    ∵ k가 바뀌면서 Column Access 발생

▣ for j = 1 to n
· A → N/c Reads
· B → N2/c Reads

※ c : Cache Line Size (보통 64B)

▣ for i = 1 to n
· A → Miss (Cold Miss)
· B → Miss (Capacity Miss)    ∵ Cache 안에 다 못 들어가서 다시 새로 접근

· A → N/c Reads
· B → N2/c Reads

· A → N2/c Reads
· B → N3/c Reads (조건 만족 시 해당)
· C → N2/c Reads + N2/c Writes

** C는 Update 될 때마다 메모리에 매번 쓰지 않음 → N2 원소 Read 1번 (N2/c) & Write 1번 (N2/c) 

** B는 연산량과 같은 수준으로 메모리 접근 발생 → 성능 병목

▣ Column Access
· B를 Column Access → 매번 Cache Line을 새로 Read

** Cache Line = 64B, float = 4B → 한 줄에 16개 존재, But, Column Access 시 1개만 사용 = 15개 Waste
→ 다음 Column 계산까지 방출되지 않으려면 최소 16N개의 항목 유지

· Cache Size < 16N (최악의 경우) : N3    ∵ Cache가 작아서 재사용 불가
· Cache Size > 16N : N3/c → But, 해당 조건만으로 만족하기 어려움

▣ Set Associativity
· Cache는 여러 개의 "Set"으로 나뉨 → 각 Set 안에 여러 Line (Way)

Ex. L1 = 32KB & Cache Line = 64B & 8-Way → 32KB / 64B = 512 Lines & 512 / 8 = 64 Sets

> N = 2k
· N = 128 & float = 4B → 1 Row의 크기 = 128 x 4B = 512B = 8 Cache Lines
· 접근하는 주소 간격 = 512B (1 Row씩 점프) / Cache Line 단위 = +8 Lines씩 증가
· 0 → 8 → 16 → 24 → 32 → 40 → 48 → 56 → 0 → 8 → … (64개 Set 중 8개 Set만 사용하여 데이터가 계속 같은 Set으로 몰림)
→ Conflict Miss 발생 (Cache가 부족해서 발생한 문제 : X / Cache를 제대로 사용 못해서 발생한 문제 : O)

∴ 사용 가능한 Cache = Cache Size / 8

> N ≠ 2k
· N = 144 & float = 4B → 1 Row의 크기 = 144 x 4B = 576B = 9 Cache Lines
· 0 → 9 → 18 → 27 → 36 → 45 → 54 → 63 → 8 → 17 → … (모든 Set 사용으로 데이터가 고르게 분산)

△ Cache 활용률 증가 & 성능 향상

∴ B → N3/c Reads 조건
· Cache Size > 128N    ∵ Cache Size / 8 > 16N (충돌 고려)
· Cache Size > 16N (N ≠ 2k)

※ Cache Size / 8 = Usable Cache Size

· N = 2k 형태에서 일부 Cache Set만 사용하는 Conflict Miss에 의해 시간 증가

> Small N : Cache에 잘 들어가서 문제 없음  → 빠름
> Medium N : Capacity Miss 발생(Usable Cache Size < 16N) → 속도 감소
> N = 2k : Conflict Miss 발생 → 시간 폭증 (Peak)

[Solution]

▣ Padding
· B 행렬을 조금 더 크게 만들어서 복사 (Ex. N x N → N x (N + 1))
· 행 길이 변화 → Stride(간격) 변화 → 주소 Pattern이 깨짐 → Cache Set에 고르게 분산

∴ Padding은 Cache Locality를 개선하는 것이 아니라 "나쁜 Alignment(정렬)"를 깨는 방법

△ N = 2k일 때의 Peak 값 제거
▼ 메모리 낭비 약간 존재
▼ Bandwidth 약간 증가

▣ Transpose
· B = Column Access = Cache Line 낭비 → BT = Row Access = 연속된 메모리 접근
· Transpose 비용 = N2/c Reads + N2/c Writes (큰 N의 경우 N3 >>> N2 → Transpose 비용 무시 가능)

∴ B의 Column Access 문제를 완전히 해결 + 메모리 간격(Stride)이 깨져 Set 충돌(Conflict Miss)이 거의 발생하지 않거나 줄어듦


· A → N2/c Reads
· B → N3/c Reads (Transpose 비용 N2 무시 가능)
· C → N2/c Reads + N2/c Writes
→ Transpose 방법이 Naive에 비해 빠르지만 아직 메모리 접근은 N3/c로 많음

** Naïve는 Cache Size 조건을 만족해야 N3/c Reads, 조건을 만족하지 못하면 N3 Reads, But, Transpose는 항상 N3/c Reads

▣ Blocked Matrix Multiply
1
2
3
4
5
6
7
for i = 1 to n step b
    for j = 1 to n step b
        for k = 1 to n step b
            for ii = 1 to b
                for jj = 1 to b
                    for zz = 1 to b
                          C(i+ii,j+jj) = C(i+ii,j+jj) + A(i+ii,k+kk) * B(k+kk,j+jj)
cs

· 전체 행렬은 Cache에 들어가지 않아 작은 Block으로 나눠 Block 단위로 계산
· 바깥 Loop = Block 선택 / 안쪽 Loop = Block 내부 계산 → Block 단위로 계산 시 Reuse 증가

C(i, j) = ∑k A(i, k) · B(k, j) → Cij = ∑k Aik · Bkj
· k Index가 같은 Block끼리 곱 연산 진행 (C00 = A00 x B00 + A01 x B10 + A02 x B20 + …)

> A00 · B00 (C00)
· A00 : b2/c Reads
· B00 : b2/c Reads

> A01 · B10 (C00)
· A01 : b2/c Reads
· B10 : b2/c Reads

> A00 · B01 (C01)
· A00 : b2/c Reads
· B01 : b2/c Reads

** A00이 Cache에 없을 수도 있음 = 완벽한 Reuse는 아님

> Entire A · B
· N/b : Block의 개수
· A : (N/b)3 x b2/c = N3/bc = (N/b) N2/c Reads
· B : (N/b)3 x b2/c = N3/bc = (N/b) N2/c Reads
· C : N2/c Reads + N2/c Writes

∴ b가 클수록 성능↑ (** But, b가 Cache를 초과하면 망함)

· Transpose + Blocked가 가장 성능이 좋음
· But, Transpose를 해도, L2 Cache에서 N = 2k일 때 Conflict Miss가 발생 가능하여 여전히 N = 2k일 때 Peak
∵ Block Size b를 L1 Cache에 맞게 선택 → L2 Cache에서 여전히 Capacity Miss / Conflict Miss 발생 가능

∴ L1 Cache 최적화 ≠ 전체 System 최적화

[Two-Level Blocking]

· 두 단계의 Block Size로 Cache 활용

· 각 Core에 L1, L2 Cache 존재(각 Core가 다른 Block 담당 → 중복 읽기 X + 중복 계산 X + 데이터 Reuse↑) + 공유 메모리 존재
    (같은 데이터를 여러 Core가 Read → Memory Traffic↑ + Bandwidth 낭비 + Cache Coherence Overhead 발생)
→ 데이터가 한 번 메모리에서 올라오면 L2 Cache에서 오래 머물고, L1 Cache에서 여러 번 사용

∴ N이 클수록 효과↑ (∵작은 N : 이미 Cache에 들어감 / 큰 N : L2 Cache에서 Miss 많음)

[Extra Optimization]

> Loop Reordering : Cache 접근 Pattern 변경 (ijk → jik / kji / ikj / …)
> Loop Unrolling : Loop 펼치기 (Multi-Thread를 통해 한 번에 여러 개를 처리하여 반복 횟수 감소)
> Partition Strategy : Block 기반 분배 (Block-Strip / Block-Column / By Block-Work Queue)
> Vector Processing (SSE, AVX 등) : 한 번에 여러 연산
> Strassen / Winograd Transform : 연산량 감소

[Reference]

· 3_mat_mul_mgp_2026 (MGP) - Yongjun Park

댓글

댓글 쓰기

이 블로그의 인기 게시물

[Mini-NPU RTL] NN Reference Model

이미지
"NN Reference Model" 1. Neuron 단 1개의 Neuron만 존재하며 해당 Neuron이 가중합을 잘 구하고 활성화 함수를 제대로 통과시키는지 확인 → 28x28=784개의 입력 데이터와 784개의 가중치를 각각 곱한 후 ∑, 이후 활성화 함수를 통과시킨 뒤, 1개의 값 출력 → "test_data.txt"에서 데이터를 읽어 Neuron에 직접 넣음 → 가중치와 편향이 "w_1_0.mif", "b_1_0.mif"로부터 정적으로 고정되어 Load neuron_tb.sv) include.v) 공통 상수를 미리 정해두는 파일로, 숫자를 고치면 Network 깊이, Neuron 개수 등을 조절 ReLU.v) 공통 활성화 함수인 ReLU를 하드웨어로 구현한 코드 Sig_ROM.v) 공통 Sigmoid 함수 연산을 실시간으로 계산하지 않고  미리 계산된 결과값 을 메모리에서 꺼내 쓰는  LookUp Table  방식의 구현 Weight_Memory.v) 공통 가중치를 저장하는 메모리 장치로 가중치를 읽고 쓴다. Neuron.v) 공통 입력 데이터를 받아 가중치와 곱하고, 누적 한 후, 편향을 더하고, 활성화 함수를 거쳐 출력하는 연산 Unit 2. Network 수많은 Neuron이 합쳐진 전체 시스템의 데이터 흐름과 제어 Logic이 제대로 작동하는지 확인 → 28x28=784개의 입력 데이터가 30개의 Neuron에게 동시에 전달되면 784x30개의 가중치를 곱해 30개의 결과 출력     (첫 번째 입력이 1 Cycle에 서로 다른 30개의 가중치와 병렬 연산으로 곱해진다. ∴ 784 Cycle) → 30개의 입력이 다음 Layer의 20개 Neuron에 전달되어 30x20개의 가중치를 곱해 20개의 결과 출력 → 20개의 입력이 다음 Layer의 10개 Neuron에 전달되어 20x10개의 가중치를 곱해 10개의 결과 출력 → 10개의 출력은 입력 이미지 0~9의 점수를 나...
자세한 내용 보기

[Mini-NPU RTL] TPU (Study Paper)

이미지
"In-Datacenter Performance Analysis of a Tensor Processing Unit" 1. Introduction to Neural Networks   NN은 입력 값들의 가중 합에 비선형 함수(ex. max(0, value))를 적용하는 단순한 인공 뉴런에 기초한다.   ※ 가중합 : 입력 데이터에 중요도인 가중치 를 곱해서 더한다.   ※ 비선형 함수 : 계산된 합을 그대로 쓰지 않고 변형하는 함수(활성화 함수)   ※ max(0, value) : ReLU(Rectified Linear Unit) 함수이며, 음수면 0, 양수면 해당 값을 그대로 내보낸다.   NN은 계층(Layer) 으로 모이며, 한 계층의 출력은 다음 계층의 입력이 된다.   DNN(Deep Neural Networks) 은 NN에서 계층의 수가 많은 것 을 의미한다.   NN은 개발 단계인 Training(학습) 단계와 실전 단계인 Inference(추론) 단계가 있다.   개발자는 계층의 수 와 NN의 유형 을 선택하고, 학습 과정을 통해 가중치 를 결정한다.   학습이 끝난 후, 추론 단계에서는 소수점 아래 긴 자리까지 필요 없는 경우가 많다.   ∴ Quantization(양자화) 단계에서 단순한 정수( 8-bit )로 바꿔 용량↓ & 속도↑         → 8-bit 정수 곱셈 : 16-bit 부동소수점 곱셈보다 에너지 소모 6배↓ & 칩 면적 6배↓         → 8-bit 정수 덧셈 : 16-bit 부동소수점 덧셈보다 에너지 소모 13배↓ & 칩 면적 38배↓   NN의 유형은 3가지로 볼 수 있다.   ·  MLP(Multi-Layer Perceptrons) : 각 계층은 이전 계층의 모든 출력 값(Fully Conn...
자세한 내용 보기