Fast Convolution

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

위 loop중에서 1,2,3,4는 병렬로 실행 가능하고 5-7은 변수를 아래 연산에서 서로 공유하므로 병렬 실행이 불가능하다.

만약, batch를 고려하지 않아서 image를 1개로 생각한다면 아래와 같은 loop로 처리된다.
또한, stride를 고려할 경우에도 아래와 같은 loop가 된다.

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

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

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

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

최종 아웃풋 크기 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은 올라가는 이점이 있다.

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쪽 부담이 증가

참고문헌

• [1] Understanding Winograd Fast Convolution
• [2] CENNA: Cost-Effective Neural Network Accelerator, electronics.
• [3] Making Faster
• [4] Fast Algorithm for Convolutional Neural Networks, CVPR 16