cuDNN Convolution FWD Algorithm 분석 (1) Overview

이전 글 : 2022.04.26 - [Deep Learning/jhDNN] - jhDNN - 3 : Convolution 연산 및 GEMM-Convolution에 대한 고찰 (Feat. im2col)

이전 글에서 cuDNN의 convolution forward algorithm에 대해서 간단히 소개하였다. 앞으로 각 알고리즘에 대하여 분석해보고자 한다. 

 

 

 

cuDNN Convolution FWD Algorithm Overview

cuDNN에서 공식 제공하는 convolution FWD algorithm은 다음 8개이다[1]. cuDNN은 구체적인 구현 방법은 공개하지 않기에(not open-source), 괄호 안에 개인적인 구현 방법 추론을 적어두었다.

 

1. CUDNN_CONVOLUTION_FWD_ALGO_DIRECT
   • 기본적인 convolution (실제 연산은 correlation) 실행
   • 현재는 지원하지 않음 (실행 시 CUDNN_STATUS_NOT_SUPPORTED 에러 발생)
2. CUDNN_CONVOLUTION_FWD_ALGO_GEMM
   • Convolution 연산을 GEMM 연산으로 변환하여 실행. 변환된 input matrix 저장을 위한 매우 큰 workspace 필요 (메모리 사용량 높음)
   • 메모리 사용량을 높임으로서 계산 성능 향상 달성
3. CUDNN_CONVOLUTION_FWD_ALGO_IMPLICIT_GEMM
   • Convolution 연산을 GEMM 연산으로 변환하여 실행하지만, 실제 input을 matrix로 변환하지는 않음
   • (어떻게 구현했을까? 실시간으로 matrix index -> input index로 변환하는 방식이지 않을까? 예를 들어 matrix[3][1]에 접근하면 input[56]에 접근하게끔. 56은 그냥 임의의 수)
4. CUDNN_CONVOLUTION_FWD_ALGO_IMPLICIT_PRECOMP_GEMM
   
   • Convolution 연산을 GEMM 연산으로 변환하여 실행하지만, 실제 input을 matrix로 변환하지는 않음
   • Matrix indices 계산(=이걸 precompute라고 함)을 위한 workspace 필요 (메모리 사용량 증가)
   • Matrix indices를 미리 계산하여 메모리에 저장하는데, 이를 implicit matrix라고 함 (암시적으로 행렬을 생성했다는 의미)
   • (CUDNN_CONVOLUTION_FWD_ALGO_IMPLICIT_GEMM에서 실시간으로 matrix index -> input index로 변화하는 것을 미리 계산해서 저장해 두는 것이 아닐까 싶음)
5. CUDNN_CONVOLUTION_FWD_ALGO_FFT
   • Convolution 연산을 Fast-fourier transform 변환 방식으로 구현함
   • 중간 결과 저장을 위해 매우 큰 workspace가 필요하다. (메모리 사용량 매우 증가)
6. CUDNN_CONVOLUTION_FWD_ALGO_FFT_TILING
   • Convolution 연산을 Fast-fourier transform 방식으로 구현함
   • 다만 input 데이터를 tile 단위로 쪼개서 convolution 연산을 구현하여 메모리 사용량을 줄임
7. CUDNN_CONVOLUTION_FWD_ALGO_WINOGRAD
   • Convolution 연산을 Winograd transform 방식으로 구현함
   • 중간 결과를 저장하는데 그렇게 큰 workspace가 필요하지 않음 (적절한 메모리 사용량)
   • Filter의 사이즈가 3*3이어야 함 (다른 filter 사이즈는 에러 발생)
8. CUDNN_CONVOLUTION_FWD_ALGO_WINOGRAD_NONFUSED
   • Convolution 연산을 Winograd transform 방식으로 구현함
   • 매우 큰 메모리 사용량
   • Filter의 사이즈가 3*3 혹은 5*5 가능
   • (일반 winograd 방식과 무슨 차이인지를 파악하여야 겠음)

 

 

 

간단한 실행 예시 및 성능 분석

다음과 같은 기본적인 convolution configuration에 대하여 계산 속도 및 메모리 사용량을 비교하였다.

 

// Input 데이터 구성
const int BATCH_NUM=128, INPUT_C=3, INPUT_H=256, INPUT_W=256;

// Convolution layer 구성
const int OUTPUT_C=3, FILTER_H=3, FILTER_W=3;
const int PAD_H=0, PAD_W=0;
const int STRIDE_H=1, STRIDE_W=1;
const int DILATION_H=1, DILATION_W=1;

 

위 convolution configuration을 가지고 성능을 측정하였다. Input 및 filter의 값은 random하게 설정되었다. 실험 환경은 Ubuntu 18.04, CUDA 10.2, cuDNN 8.4, a single NVIDIA RTX 2060 super GPU이다.

 

알고리즘	50회 반복 실행 시간 (초)	메모리 사용량 (GB)
GEMM	0.738	0.831
IMPLICIT_GEMM	0.246	0.000 (추가 메모리 사용량 없음)
IMPLICIT_PRECOMP_GEMM	0.170	0.000362
FFT	0.335	0.193
FFT_TILING	0.285	0.006
WINOGRAD	0.499	0.000017
WINOGRAD_NONFUSED	0.212	0.422
DIRECT	X (실행 불가)	X (실행 불가)

 

위 표는 CNN에서 일반적으로 많이 쓰이는 3X3 convolution에 대한 실험 결과이다. 계산 속도는 IMPLICIT_PRECOMP_GEMM이 가장 빨랐으며, 메모리 사용량은 IMPLICIT_GEMM이 가장 적었다. 특히 IMPLICIT_PRECOMP_GEMM의 경우 합리적인 수준에서 추가적인 메모리가 필요하기에, IMPLICIT_PRECOMP_GEMM이 가장 좋은 성능을 보여준다고 할 수 있을 것이다.

 

다만 위 실험은 가장 단순한 convolution layer configuration에 대한 실행이기에, 어떤 알고리즘이 언제 좋은 지를 정확히 보여주지 못한다. 다음 포스터에서는 mini-batch size, filter의 크기, channel의 크기 등 convolution layer의 다양한 configuration에서 테스트를 진행한 결과를 추가하겠다.

 

 

 

Implementation

테스트에 사용한 코드는 다음과 같다. 

https://github.com/jhson989/analyse-cudnn-conv-fwd-algo

GitHub - jhson989/analyse-cudnn-conv-fwd-algo

make run 시 forward 과정 계산 시간 및 필요한 메모리 크기를 출력한다.

 

 

 

Reference

[1] https://docs.nvidia.com/deeplearning/cudnn/api/index.html#cudnnConvolutionFwdAlgo_t

[2] M. Jordà, P. Valero Lara and A. J. Peña, "Performance Evaluation of cuDNN Convolution Algorithms on NVIDIA Volta GPUs," in IEEE Access, vol. 7, pp. 70461-70473, 2019, doi: 10.1109/ACCESS.2019.2918851.