[C++] 행렬곱 연산 최적화 및 속도 비교

C++ 에서 행렬곱 연산을 구현할 때, 여러 방법에 따라 속도 차이가 많이 난다고 해서 간단한 실험으로 속도 비교를 해보았습니다. 행렬곱 연산 과정은 따로 설명하지 않고, 가장 나이브한 방식에서 속도를 향상시킬 수 있는 몇가지 방법들을 단계적으로 설명합니다.

사실 행렬 연산 시 많이 사용하는 Eigen 라이브러리를 쓰면 최적화가 잘되어 있어서 실무에서 행렬 연산을 직접 구현해야할 상황이 얼마나 있는지는 잘 모르겠습니다. 아직 경험이 많이 없어서... ㅠ

Baseline (naive version)

/*
@input
mat_x: m x k size matrix
mat_y: k x n size matrix
@output
mat_z: m x n size matrix 
*/

void matmult_baseline(int M, int N, int K, const float* mat_x, const float* mat_y, float* mat_z)
{
	for (int i = 0; i < M; i++)
		for (int j = 0; j < N; j++)
			for (int k = 0; k < K; k++)
				mat_z[N * i + j] += mat_x[i * K + k] * mat_y[k * N + j];
}

기본적인 행렬곱 연산은 A행렬의 row와 B 행렬의 column의 각 원소끼리 곱하고 더하는 과정으로 구성됩니다.

즉, 총 세개의 index(e.g. i,j,k)가 필요하여 삼중 for문을 순회하며 계산하므로 시간 복잡도 (O^3) 를 가지므로 기본적으로 연산이 빠르지는 않겠구나 생각이 듭니다.

이 때, 저장된 행렬의 원소를 행을 바꿔가며 호출하게 되는데 이는 cache 메모리를 굉장히 비효율적으로 사용하는 방법이기에 시간이 오래 걸리게 됩니다.

Cache 메모리는 사이즈가 작고 유한하며 지금 사용하는 주소값 근처의 값에 접근하는 경우에는 효율적으로 사용이 가능하지만, 멀리있는 주소값에 반복적으로 접근 시 효율이 떨어져 시간이 오래 걸리게 됩니다.

즉, 행렬 곱 연산시 row를 움직이면서 원소에 접근하면 행렬 사이즈가 큰 경우에는 coulmn size * sizeof(~) 만큼 주소 값을 이동시켜야되기 때문에 비효율적이게 됩니다.

Indexing 변경 : (IJK → KIJ)

Baseline 보다 cache 메모리를 효과적으로 사용하기 위해 indexing 순서를 변경하는 방법입니다.

기존 indexing (IJK) 에서 (KIJ)로 변경 시, 가장 많이 순회하는 마지막 for문을 보면 column을 움직이면서 연산하기 때문에 row 를 움직이면서 연산하는 방법보다 속도가 빨라집니다.

근데, 이런 트릭 수준의 알고리즘 변경으로 속도가 얼마나 빨라질까 했는데... 행렬 사이즈가 커질수록 효과가 굉장히 드라마틱합니다.

SIMD (Single Instruction Multiple Data) 적용

SIMD는 CPU 에서 병렬 연산을 하기 위한 multiple data를 한번에 연산하는 방법입니다.

어셈블리어로 직접 구현하는 방법도 있고, 어셈블리어와 1대1 매칭되는 Intrinsic function 을 사용하는 방법도 있습니다. Intrinsic function을 사용하는 것이 비교적 편하지만 자료형별로 사용되는 함수도 다르고 하드웨어(컴퓨터구조)에 대한 기본적인 이해도가 필요합니다.

즉, 원소 하나 하나를 순회하며 계산하는 방식이 아니라, 여러 원소의 묶음을 메모리에 올려서(병렬적) 한번에 계산하기 때문에 속도 향상을 기대할 수 있습니다.

GPU 사용 (CUDA)

GPU를 이용한 병렬 프로그래밍을 하기 위해 CUDA toolkit 사용하는 방법입니다. 딥러닝 학습시 아주 간단하게 .cuda() 만 적으면 간단하게 사용가능했던 GPU이지만, C++ 의 경우에는 data를 CPU-GPU 간 복사하고 메모리를 할당하는 과정들이 필요해서 비교적 복잡합니다.

하지만, 가장 결과가 좋은 방법입니다.

* 기본 순서

1)Data를 CPU → GPU 복사

2)GPU에서 kernel 함수 실행하여 연산

3)결과를 GPU에서 CPU 로 복사

실험 결과

모든 실험은 (1000x1000 size matrix) * (1000x1000 size matrix) 의 행렬곱 연산의 평균 소요 시간(ms)입니다.

CUDA 방법의 경우 메모리에 올리는 시간까지 포함했습니다. (그래도 압도적으로 빠릅니다)

결론만 정리하면, Cache 메모리 접근을 효과적으로 할 때(Indexing 변경), 병렬 프로그래밍 사용할 때 (SIMD), GPU 사용할 때(CUDA) 성능이 좋아집니다.

CPU 한정으로 봤을 때, Eigen 라이브러리가 연산 속도가 좋고 행렬을 다루기 편하기 때문에 선택의 여지가 없을 것 같습니다.

*전체 코드 : https://github.com/ldj7672/Matrix-Multiplication-Algorithm/blob/main/matmul.cpp

CV DOODLE