범용적인 NPU 만들기(11) - 곱셈기(3) - 이론(3) - Wallace Tree

https://github.com/thousrm/universal_NPU-CNN_accelerator/releases/tag/0.1
첫 릴리즈 버전이 5일 전 출시되었다. 아직 Arithmetic Part만이 구현되어있다.

저번 포스팅을 올리고 한달 가까이 지났다. 그동안 첫 릴리즈 버전을 앞두고 이것저것 바쁘기도 했지만 사실 가장 큰 이유는 포스팅을 올리는게 귀찮아서였음을 인정하겠다.

포스팅 하나를 작성하는데 꽤 시간을 잡아먹다보니 연재하기가 솔직히 좀 부담스럽기는 하다. 그래도 일단 시작한 일인만큼 끝을 맺겠다.

---

Wallace Tree는 여러개의 Partial Product들을 덧셈하는 방식 중의 하나다. Wallace Tree의 가장 큰 특징 중 하나는 stage를 나누어서 덧셈한다는 점이다.

Dr. shirshendu roy. Wallace and Dedda Multiplier Design. https://digitalsystemdesign.in/wallace-and-dedda-multiplier-design/

위 그림은 8bit * 8bit multiplier의 경우이다. (MBE 미적용)

stage1(level1)에서 초기 상태로 partial product들이 배열되어 있을 때 몇개의 요소(그림 상 원)끼리 묶어서 계산한 후 다시 그 결과에 대해 반복해 최종적으로 한 자리에 2개 이하만 배치되게 하는 것이다.

마지막에는 ripple adder든 fast adder든 원하는 adder를 배치해 계산을 완료한다.

위의 그림에서 delay는 최종적으로 4 FA + 1 final adder가 된다. area의 경우는 14 HA + 38 FA + 1 final adder가 된다.

carry save adder의 경우 delay는 1 HA + 7 FA + 1 final adder가 되고, area는 15 HA + 49 FA + 1 final adder가 된다.

결과적으로 delay에서 약 3.5 FA, area에서 11.5 FA만큼 이득을 본다.

---

이대로도 이득이긴 하지만 이는 wallace tree에서 FA와 HA만을 쓰는 것을 전제로 했을 때의 결과이다. wallace tree는 필요한 stage의 수가 줄어들수록 delay와 area에서 큰 이득을 보게 된다.

필요한 stage는 결국 요소의 개수에 비례하는데 이는 즉 다음 stage로 넘어갈 때 adder를 잘 배치해 요소의 개수를 많이 줄인다면 stage수가 적어져 이득을 보게 된다는 뜻이다.

HA는 2개의 요소를 input으로 받아들이고 2개의 요소를 output으로 낸다. 즉 이득이 없다.(물론 1개의 요소를 상위 비트로 이동시킨다는 메리트는 있다.)

FA는 3개 input, 2개가 output이 되어 1개의 이득이 있다. 이를 봤을 때 wallace tree에서 HA 와 FA만을 사용하는 것은 그리 효율적이지 않다는 것을 알 수 있다.

만약 위의 그림에서 여러 종류의 adder 배치하면 어떻게 됐을까?

파란색 - 8:4 adder | 빨간색 - 7:3 adder | 주황색 - 6:3 adder | 노란색 5:3 adder

stage2에 남는 요소의 개수가 확연하게 줄어들었음을 알 수 있다. 특히 이와 같은 방법은 요소의 수, 즉 partial product의 수가 많을 수록 이득이 커진다.

예를 들어서 16bit * 16bit를 계산할 때 HA와 FA만으로 계산한다면 약 15개 stage나 필요하지만 만약 5:3, 4:3 adder를 같이 사용할 경우 9개 stage 이하로 줄일 수 있다.

이는 FA에 비해 다른 adder의 area나 delay가 크더라도 이를 충분히 상쇄할 수 있는 이득이다.

---

이 프로젝트에서 계산해야할 요소의 수는 MBE를 적용해도 8bit * 8bit * 9 + 16bit 이므로 매우 많다.

MBE 이후 각 자리에

0 1 1 1 2 11 11 19 20 37 37 37 37 46 28 37 19 28 10 19

위의 값만큼의 요소가 배치되는데 이를 HA와 FA만으로 계산하는 것은 대단히 무식한 일이다.

그래서 15:4 adder ~ 4:3 adder까지 여러 종류의 adder를 사용하였고 이를 통해 5개 stage로 압축할 수 있었다.