Fast Convolution


기본 convolution 연산 방법

아래와 같다고 했을때 convolution은 7중 loop로 구현 된다.
N: number of images
K: kernel size (assumed square)
W: input width
H: input height
C: number of input channels
D: number of output channels
스크린샷 2020-02-12 오후 2.40.48
위 loop중에서 1,2,3,4는 병렬로 실행 가능하고 5-7은 변수를 아래 연산에서 서로 공유하므로 병렬 실행이 불가능하다.

만약, batch를 고려하지 않아서 image를 1개로 생각한다면 아래와 같은 loop로 처리된다.
또한, stride를 고려할 경우에도 아래와 같은 loop가 된다.
스크린샷 2020-02-12 오후 2.36.36

im2col, GEMM 스타일로 변경하여 Conv연산

위와 같이 loop로 구현하면 연산속도가 매우 느리게 된다. 비록 메모리 사용량은 Feature map 측면에서 많지만 아래와 같이 matrix multiplication 방식으로 구현하면 200배 이상의 성능 향상을 가져온다.

Convolution_With_Im2col

먼저 커널의 경우 커널의 숫자 D와 커널의 사이즈 KKC로 결정된다. 즉 여기서 필터가 96개라고 한다면 [96x(11*11*3)]으로 [96x363]이 된다.

그 다음 Feature map의 경우 [커널사이즈x최종아웃풋 크기(N)]이다. 이 작업을 im2col이라 한다. 아래 그림과 같이 수행한다.

im2col_operation

최종 아웃풋 크기 N의 경우 아래와 같이 계산한다.

  • 입력 이미지를 [227x227x3]
  • stride: 4
  • filter: [11x11x3] = 363
  • output feature map: ((227-11)/4)+1 = 55
    이면, 55*55=3025이다.
    즉, Feature map은 [363x3025]가 된다.

최종 연산 결과 matrix는
[96x363] * [363x3025] = [96x3025]이다.
그리고 [96x3025]은 reshape되어 [55x55x96]으로 변환 된다. 이러한 reshape 과정을 col2im이라 한다.

여기서 loop로 구현 했을 때와 비교 했을 때 발생하는 메모리 overhead는 (227x227x3) - (363x3025) = 943,488 이다.

결국 이 방법은 데이터는 반복해서 메모리에 올라가지만 연산자의 수는 적기 때문에 throughput은 올라가는 이점이 있다.

스크린샷 2020-02-12 오후 5.41.52

Winograd Convolution

발표논문: Lavin, CVPR 2016[4]

  • 장점: 2.25x 성능향상 3x3 filter 일 때
  • 단점: 필터 사이즈에 의존된 특별한 연산. 필터사이즈가 맞지 않으면 연산상의 이득이 줄어듬

Strassen Algorithm

발표논문: Mathieu, ICLR 2014

  • 장점: $O(N^{3})$
    에서 $O(N^{2.807})$으로 복잡도가 감소
  • 단점: 산술적인 안전성이 떨어짐

Fast Fourier Transform (FFT)

발표논문: Mathieu, ICLR 2014

  • 장점: $O(N_{o}^{2}N_{f}^{2})$ to $O(N_{o}^{2}\log_{2}N_{o})$ 으로 복잡도가 감소
    • 단점: storage쪽 부담이 증가

참고문헌


'Data Science > Theory' 카테고리의 다른 글

Fast Convolution  (2) 2020.02.13
Loss functions  (0) 2018.08.09
Feature (Attribute) Selection  (0) 2015.09.15
Ensemble Method  (0) 2015.09.15
Active Learning  (0) 2015.08.19
기계학습을 구현하기 위해서 어떤 언어가 좋은가?  (0) 2015.07.11
  1. Kjun25 2020.05.04 13:44 신고

    가장이 된후 포스팅이 올라오지 않는군요

    • JAYNUX 2020.05.05 07:48 신고

      댓글보고 ONNX 포스팅 하나 올렸습니다. 회사에서 클라우드가 막혀서 posting이 어렵네요

+ Recent posts