[인공지능 하드웨어] 7 - Winograd Convolution

# 들어가며

Deep Learning Optimization 기법 중의 하나인 Winograd Convolution에 대해서 알아본다. 컴퓨터 구조 관련한 배경지식이 있으면 이해하기 편하므로 글을 읽다가 이해가 되지 않는다면 관련 블로그 포스트나 유튜브를 찾아보는 것이 좋다. 이전 글은 다음 링크의 블로그 포스트를 참고하면 된다.

[인공지능 하드웨어] 6 - Deep Learning Optimization(Convolution Lowering, Systolic Array)

---

# Winograd Convolution

일반적으로 덧셈보다 곱셈 연산이 더 비싸다. 그 원인은 모르겠다. 아마 회로상의 문제일 것이다. 하지만 조금 신기한 생각을 해 보자면 사람도 덧셈보다는 곱셈을 힘들어 한다. 기계또한 곱셈이 더 복잡하고 더 많은 에너지를 소모한다. 어쩌면 이 자연은 그렇게 Design 되었는지도 모르겠다. 어쨌든, Winograd Convolution은 같은 Convolution 연산이라도 곱셈을 최대한 덜 사용하고 덧셈을 최대한 더 사용하는 방법이다.

 

예시를 들어보도록 하자. 다음과 같은 1차원 Convolution 연산이 있다.

 

 

위 그림을 조금 풀어보자면, 먼저 입력데이터가 아래와 같으며

d0

d1

d2

d3

 

커널은 다음과 같은 길이 3의 1차원 벡터이고,

g0

g1

g2

 

결과물은 y0, y1이다. 이때, y0, y1 벡터를 구하는 과정을 행렬곱으로 나타내면 매우 당연하게 다음과 같다. 

위의 그림의 계산 과정을 나타낸 행렬곱

이때, y0, y1을 계산하는 과정에서 6번의 multiplications과 4번의 additions가 발생한다. 눈으로 따라서 해보면 당연하게 나오는 수치이다.

 

수학자들은 이 계산 과정에 만족하지 않았다. 그들은 덧셈을 늘려서라도 곱셈을 줄이고 싶었다. 그래서 다음과 같이 억지로 값들을 끼워맞춰서 4번의 mulitiplications과 8번의 additions로 만들었다!

새롭게 y0, y1을 만드는 과정

새로운 연산에 필요한 m0~m3를 만드는 과정

 

이때 g0 + g1 + g2, g0-g1-g2에 사용된 4번의 multiplications들은 거의 latency가 미미해서 웬만하면 count하지 않는다. 왜냐면 가중치끼리의 덧셈은 미리 만들어두고 하드웨어상에서 구해놓을 수 있으므로, offline cost라고 한다.

 

위의 과정을 행렬 연산으로 간략하게 만들면 아래와 같이 나타낼 수 있다. 수식이 꽤나 복잡해 보이지만, 크게 어려운 부분은 없다. 대괄호 안에 있는 Gg, BTd로 m0부터 m3을 만들어서 배치시키고, 대괄호 밖의 AT는 m0~m3 사이의 덧셈 뺄셈을 행렬 연산으로 나타낸 것 뿐이다. 모든 선형 다항식 계산은 행렬 연산으로 치환할 수 있다는 원리 덕분에 가능한 것이다!

 

 

2D Convolution 연산도 다를바는 없다. 먼저 2D Convolution 연산을 Convolution Lowering을 사용해서 행렬곱으로 바꿔준다.

Convolution Lowering을 하면 결과는 다음과 같다.

 

어라 그런데 조금 크게 크게 보면 이렇게 나타낼 수 있을것 같다. 그림을 잘보면 k4, k5, k6, k5, k6, k7을 한 블럭을 생각 했을 때 아래 그림에서의 위치와 동일하게 반복되는 것을 볼 수 있다. 커널이 이미지를 훑고 지나가는 과정을 Convolution Lowering을 사용해 행렬곱의 형태로 변환했으니 당연한 것이다.

이제 위의 1차원 Winograd Convolution과 동일하게 2차원에도 적용할 수 있게 되었다. 이처럼 Convolution 연산이 몇차원인지 상관 없이 Winograd Convolution을 적용할 수 있다. 이렇게 하면 기존의 9x4=36번의 multiplications에서 4x4=16번의 multiplications로 감소하여 연산에서 큰 이득을 볼 수 있다.

 

 

이때 4x4=16인 이유는 W0가 원래는 [w0, w1, w2]이고, k0-k2가 원래는 [[k0-k8, k1-k9, k2-k10], [k1-k9, k2-k10, k3-k11]]이므로 저 곱셈 자체도 한번 더 Winograd Convolution을 하기 때문이다. 어찌보면 Divide and Conquer 알고리즘과 비슷한 것 같다!

---

 

[인공지능 하드웨어] 8 - Deep Learning HW Accelerator(TPU)

국민대학교 권은지 교수님의 인공지능 하드웨어 강의를 수강하며 정리한 내용입니다.

Slides Provided

임베디드 시스템 프로그래밍 - Eunhyeok Park

딥러닝 최적화 - Eunhyeok Park

References