Convolution in Detail

convolution

Direct Convolution

for 루프로 직접 계산(MAC : Multiply Accumulation operation)

캐시 사용하지 못함, 병렬처리 못함

 

GEMM(General Matrix Multiply)

IM2COL로 Input과 Weight를 matrix로 변형해서 계산

im2col

GPU 연산에 빠르다

 

FFT-based Convolution

weight와 input을 FFT로 변환해서 pointwise multiplication 수행

IFFT로 원복

(자세한 내용은 다음에 다루겠습니다)

FFT 연산

2-D convolution

$(G*F)[i,j]=\sum_m \sum_n G[i+m,j+n]F[m,n]$

i+m,j+n가 범위를 벗어나면 무시한다.

Fourier Transform 후 곱셈 계산을 위해 filter에 zero padding을 더한다

그리고 IFFT를 구하고 나머지 범위는 버린다

 

 

https://koreascience.kr/article/JAKO202102539955594.pdf

Winograd Transform

winograd transformation

𝐹(𝑚 × 𝑚, 𝑟 × 𝑟)

- kernel size : 𝑟 × 𝑟

- output size : 𝑚 × 𝑚

=> Input size : (𝑚+𝑟-1) × (𝑚+𝑟-1)

 

Element wise multiplication를 수행할 때만 곱셈이 일어나고, 나머지 과정에서는 shift, 더하기, 빼기만 일어난다

naive하게 계산하면 곱셈이 m*m*r*r번 발생하지만, winograd에서는 (𝑚+𝑟-1) × (𝑚+𝑟-1) 번 발생한다

kernel이 3x3이고 input이 작을 때만 쓰인다.

 

$Y = A^T[(G gG^T) \odot  (B^TdB)]A$

 

F(2x2,3x3)일때는

${B=\begin{bmatrix}
1 & 0 & -1 & 0 \\ 
0 & 1 & 1 & 0\\ 
0 & -1 & 1 & 0\\ 
0 & 1 & 0 & -1
\end{bmatrix}}$, ${G= \begin{bmatrix}
1 & 0 & 0  \\ 
\frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ 
\frac{1}{2} & -\frac{1}{2} & \frac{1}{2}\\ 
0 & 0 & 0 
\end{bmatrix}}$, ${A^T= \begin{bmatrix}
1 & 1 & 1 & 0 \\ 
0 & 1 & -1 & -1
\end{bmatrix}}$

 

 

 

 

https://aircconline.com/csit/papers/vol11/csit111716.pdf