GPU 최적화 기초 - 알고리즘 최적화

행렬과 벡터의 곱셈을 통해 최적화 기법의 영향을 분석해본다.

알고리즘, 블록 크기, 메모리, 분기문제거 요 네가지 부분으로 알아본다.

 

알고리즘 파트

행렬 M : NxN

벡터 V : Nx1

결과행렬 W : Nx1

 

곱하는 행렬의 행과 곱해지는 행렬의 열이 결과행렬이니까

이걸 가지고 최적화 한거랑 안한거랑 성능평가를 할 겁니다

 

 

기존의 알고리즘대로 하자면

그리드와 블록은 1차원

하나의 스레드는 결과 벡터 W의 복수의 항에 들어갈 값을 계산한다.

행렬 M의 블록 ID번째 행과 벡터 V의 벡터내적을 통하여 벡터 W의 블록 ID번째 항을 계산한다.

 - 그니까 행렬의 ID행과 벡터의 ID항을 곱해, 걍 행렬곱

스레드 크기보다 큰 행은, '행번호 / 스레드크기의 나머지'번째의 스레드가 계산을 한다.

 

 

최적화된 알고리즘대로 하면

그리드와 블록은 여전히 1차원 (뭐 2차원이던 뭐던 상관없는데 1차원이 다루기 편하기 때문에)

하나의 스레드가 행렬 M의 한 행을 계산하는 것 보다

블록이 행렬 M의 한 행에 해당하는 곱셈을 계산하도록 묶었어

 - 전역메모리 접근 시 최소의 트랜잭션이 일어나도록 하기 위해

 - 블록단위로 묶어서 처리하기 때문에 여러개의 스레드를 실행시키는것 보다 트랜잭션의 갯수 감소

1차원의 그리드와 블록에 대해 블록의 각 스레드들은

M의 '열 번호 / 블록크기의 나머지' 번째 열과,

V의 '행 번호 / 블록크기의 나머지' 번째 행의 곱을 모두 더한다.

그 후 각각의 스레드가 계산한 값을 취합하면 결과 W의 한 항의 값이 생성된다.

행렬 곱인데 1행 1열 곱을 하나의 블록단위로 묶은 것 뿐이야,

그걸 공유메모리에 퐁당

 - 전체 스레드 블록이 1/2씩 공유메모리 크기를 줄여가며 그 값을 누적해 나가는 방식을 사용