[Multi-Core & GPU Programming] HW1 - Parallel Softmax

"Parallel Softmax"

[Objective]

Softmax 함수 Logic을 이해한 후, Softmax 함수를 병렬로 실행하여 완료 시간을 단축하는 과정을 통해 Parallel Logic 이해하기

[Theory]


▣ my_softmax
· 지수 함수 ex는 x가 조금만 커져도 값이 기하급수적으로 증가
→ 입력값(a)이 큰 경우, Overflow 발생

▣ my_new_softmax
· 입력값의 최대값을 모든 요소에 빼면 모든 입력값이 0 이하로 변경
→ e0 = 1이고, 나머지 값들은 0과 1 사이의 작은 실수 = Overflow 발생 X

[Implementation]

▣ Makefile
1
2
3
4
5
6
7
8
9
10
11
12
build:
        mkdir -p build
        g++ -std=c++20 main.cpp -o build/main
 
run:
        ./build/main
 
clean:
        rm -rf build
 
format:
        clang-format -i main.cpp softmax_parallel.h
cs

· make build : "main.cpp" 파일을 Compile해서 실행 파일을 build/main으로 생성
· make run : 만들어진 실행 파일 실행 (make build 후 make run 실행)
· make clean : 생성된 "build" Directory 삭제
· make format : Format 정리

▣ softmax_parallel.h
> Logic Flow
① 입력 값의 최댓값 찾기
② 찾은 최댓값을 사용하여 my_new_softmax 함수 방법으로 exp 계산
③ exp 계산 결과의 전체 합 구하기
④ exp 계산 결과의 전체 합을 나눠 softmax 계산

> Not Use Local Max & Not Use (long long)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <algorithm>
#include <cmath>
#include <thread>
using namespace std;
inline void softmax_parallel(float *in, float *out, int elems) {
        const int NTHREADS = 16;
        std::thread threads[NTHREADS];
        float max = in[0];
        float local_sum[NTHREADS];
        for (int i = 1; i < elems; i++) {
                if (in[i] > max) {
                        max = in[i];
                }
        }
        for (int t = 0; t < NTHREADS; t++) {
                threads[t] = std::thread([&, t]() {
                        int start = elems * t / NTHREADS;
                        int end = elems * (t + 1) / NTHREADS;
                        float sum = 0.0f;
                        for (int i = start; i < end; i++) {
                                out[i] = std::exp(in[i] - max);
                                sum += out[i];
                        }
                        local_sum[t] = sum;
                });
        }
        for (int t = 0; t < NTHREADS; t++) {
                threads[t].join();
        }
        float global_sum = 0.0f;
        for (int t = 0; t < NTHREADS; t++) {
                global_sum += local_sum[t];
        }
        for (int t = 0; t < NTHREADS; t++) {
                threads[t] = std::thread([&, t]() {
                        int start = elems * t / NTHREADS;
                        int end = elems * (t + 1) / NTHREADS;
                        for (int i = start; i < end; i++) {
                                out[i] /= global_sum;
                        }
                });
        }
        for (int t = 0; t < NTHREADS; t++) {
                threads[t].join();
        }
}
cs

· 입력 값 전체에서 최댓값을 찾아서 exp 계산에 사용하는 방식

<왼쪽 : NHTREADS = 16 / 오른쪽 : NTHREADS = 8>
· NTHREADS = 8인 경우 1.66753sec가 소요되는데 NTHREADS = 16인 경우 Segmentation Fault 발생

∵ 16, 17, 36, 37 : "elems"와 "t"는 모두 32-bit int 변수
→ "elems * t" 계산 시 두 수의 곱이 int의 최댓값을 초과 = Overflow가 발생하여 "elems * t" 연산 결과가 음수가 됨
→ out[i]의 i가 음수 Index가 되어 할당 받지 않은 메모리 영역을 참조

> Not Use Local Max & Use (long long)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <algorithm>
#include <cmath>
#include <thread>
using namespace std;
inline void softmax_parallel(float *in, float *out, int elems) {
        const int NTHREADS = 64;
        std::thread threads[NTHREADS];
        float max = in[0];
        float local_sum[NTHREADS];
        for (int i = 1; i < elems; i++) {
                if (in[i] > max) {
                        max = in[i];
                }
        }
        for (int t = 0; t < NTHREADS; t++) {
                threads[t] = std::thread([&, t]() {
                        int start = (long long) elems * t / NTHREADS;
                        int end = (long long) elems * (t + 1) / NTHREADS;
                        float sum = 0.0f;
                        for (int i = start; i < end; i++) {
                                out[i] = std::exp(in[i] - max);
                                sum += out[i];
                        }
                        local_sum[t] = sum;
                });
        }
        for (int t = 0; t < NTHREADS; t++) {
                threads[t].join();
        }
        float global_sum = 0.0f;
        for (int t = 0; t < NTHREADS; t++) {
                global_sum += local_sum[t];
        }
        for (int t = 0; t < NTHREADS; t++) {
                threads[t] = std::thread([&, t]() {
                        int start = (long long) elems * t / NTHREADS;
                        int end = (long long) elems * (t + 1) / NTHREADS;
                        for (int i = start; i < end; i++) {
                                out[i] /= global_sum;
                        }
                });
        }
        for (int t = 0; t < NTHREADS; t++) {
                threads[t].join();
        }
}
cs

· 16, 17, 36, 37 : (long long) 추가
→ "elems * t" 연산 시 32-bit int 공간이 아닌 64-bit 공간에서 수행되어 Overflow 발생하지 않고 정확한 큰 수를 계산 가능
→ out[i]의 Index로 사용 가능

<왼쪽 : NTHREADS = 16 / 오른쪽 : NTHREADS = 32>
· Thread 수가 증가할수록 연산 완료 시간 감소

<NTHREADS = 64>
· NTHREADS = 64인 경우 최대 Thread 개수 상한선을 초과하여 생성을 강제로 차단하고 프로그램이 중단(Abotred)됨

> Use Local Max & Use (long long)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <algorithm>
#include <cmath>
#include <thread>
 
using namespace std;
 
inline void softmax_parallel(float *in, float *out, int elems) {
 
        const int NTHREADS = 32;
 
        std::thread threads[NTHREADS];
        float local_sum[NTHREADS];
        float local_max[NTHREADS];
 
        for (int t = 0; t < NTHREADS; t++) {
                threads[t] = std::thread([&, t]() {
                        int start = (long long)elems * t / NTHREADS;
                        int end = (long long)elems * (t + 1) / NTHREADS;
 
                        float max = in[start];
                        for (int i = start + 1; i < end; i++) {
                                if (in[i] > max) {
                                        max = in[i];
                                }
                        }
                        local_max[t] = max;
                });
        }
 
        for (int t = 0; t < NTHREADS; t++) {
                threads[t].join();
        }
 
        float global_max = local_max[0];
 
        for (int t = 1; t < NTHREADS; t++) {
                if (local_max[t] > global_max) {
                        global_max = local_max[t];
                }
        }
 
        for (int t = 0; t < NTHREADS; t++) {
                threads[t] = std::thread([&, t]() {
                        int start = (long long) elems * t / NTHREADS;
                        int end = (long long) elems * (t + 1) / NTHREADS;
 
                        float sum = 0.0f;
                        for (int i = start; i < end; i++) {
                                out[i] = std::exp(in[i] - global_max);
                                sum += out[i];
                        }
                        local_sum[t] = sum;
                });
        }
 
        for (int t = 0; t < NTHREADS; t++) {
                threads[t].join();
        }
 
        float global_sum = 0.0f;
        for (int t = 0; t < NTHREADS; t++) {
                global_sum += local_sum[t];
        }
 
        for (int t = 0; t < NTHREADS; t++) {
                threads[t] = std::thread([&, t]() {
                        int start = (long long)elems * t / NTHREADS;
                        int end = (long long)elems * (t + 1) / NTHREADS;
 
                        for (int i = start; i < end; i++) {
                                out[i] /= global_sum;
                        }
                });
        }
 
        for (int t = 0; t < NTHREADS; t++) {
                threads[t].join();
        }
}
 
cs

· 0.8sec 내로 완료되지 않아 입력 값 전체에서 최댓값 찾기 X
→ 다른 계산과 마찬가지로 구간마다 최댓값을 구한 후, 구간 최댓값 중 최댓값을 찾아 전체 최댓값을 구하는 방식

<왼쪽 : NTHREADS = 16 / 오른쪽 : NTHREADS = 32>
· Thread 마다 각자의 구간에서 최댓값을 구한 후, 전체 최댓값을 구하는 방식의 연산 완료 시간이 감소한 것을 확인 가능

[Discussion]

· Thread를 생성하고 회수하는 System Call과 Context Switching은 CPU 입장에서 매우 무겁고 느린 작업
→ 구현한 코드에는 3번의 Thread 생성과 회수가 존재

** Barrier 사용
① Thread 생성
② 모든 Thread가 각 구간의 최댓값을 찾을 때까지 대기하는 Barrier
③ 전체 최댓값을 찾을 때까지 대기하는 Barrier
④ exp 연산과 구간 sum을 계산할 때까지 대기하는 Barrier
⑤ 전체 합을 계산할 때까지 대기하는 Barrier
⑥ Thread 회수
→ 4개의 Barrier를 사용하여 Phase 할당하면 Thread 생성과 회수를 한번만 실행 가능 = 연산 완료 시간 감소

· Thread 수를 무한정 늘린다고 해서 연산 시간이 0초에 수렴 X
① Thread를 처음 생성하고 회수하는 작업 등은 병렬화 불가 = 무조건 직렬로 수행
    → 이 직렬 구간이 차지하는 시간을 일정 시간 이하로 줄이는 것이 불가능
② 여러 Thread가 동시에 실해오디는 것처럼 보이게 하기 위해 아주 짧은 시간 단위로 Thread를 번갈아 CPU에 할당
    → Thread를 교체할 때마다 기존 상태를 메모리에 저장하고 새 상태를 불러오는 Context Switching 비용 발생
    → Thread가 너무 많아지면 Thread를 교체하는 데 쓰는 시간이 더 길어짐

∴ Thread 수가 특정 임계점을 넘어가면 성능이 기하급수적으로 감소

[Reference]

· HW1 - Parallel Softmax (MGP) - Yongjun Park
· 2_thread_mgp_2026 (MGP) - Yongjun Park
· 1_computer_abstraction (Computer Architecture) - William J. Song

댓글

댓글 쓰기

이 블로그의 인기 게시물

[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...
자세한 내용 보기