Kogge-Stone Adder

왜인지 정확히는 잘 모르겠지만

나는 굉장히 arithmetic unit에 집착하는 편인 것 같다.

사실 processor의 설계 면에서 봤을 때는

arithmetic unit의 algorithm이나 efficiency는

전체 processor의 성능에 그렇게 큰 영향을 미친다고 볼 수 없기 때문에

(뭐 single cycle CPU라면 얘기가 다르겠지만...)

굉장한 뻘짓이긴 하다만

사실 이것만큼 재밌는 분야가 없는 것 같기도...

여하튼, 오늘의 포스팅은

Kogge-Stone adder인데,

요거는

Peter M. Kogge 횽과 Harold S. Stone 횽이 1973년도에 

Kogge, P. & Stone, H. "A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations". IEEE Transactions on Computers, 1973, C-22, 783-791

요기서 제기된 이론이 되겠따.

위는 32-bits Kogge-Stone adder의 구조.

하이튼,

잡설 생략하고 톡까놓고 말해보자면

"가장 빠른 adder로 간주된다."

보통 prefix adder는 세 가지 갈래로 나뉘는데

속도↑ ------------------- 크기↓

KSA          HKA          BKA

요렇게 나뉘고 여기서 hybrid adder라던가 하는 것이 등장한다.

Ladner-Fischer adder나 공부할때 많이 참조했던

UCA Oklobdzija 교수님 adder라던가 하는 것도 세부 분류라고 볼 수 있다.

(현재 비마관 휴게실인데 에어콘물이 졸라 꼴꼴거려서 불안해하고있다)

prefix adder의 원리는 그렇게 어렵지 않다.

다만 책에 잘 안나와있을뿐이지.......

이것들은 carry look-ahead adder의 확장판이라고 볼 수 있다

따라서 P와 G의 개념

(P = a ^ b , G = a & b)을 그대로 사용한다.

요거를 또 어떻게 사용하나,

위의 KSA의 그림을 예로 들어보자면,

처음에 31-bits(끝에꺼 빼고) 전부가 다음 bit로 넘어가고,

그 다음부터 2, 4, 8 번 bit부터 넘기는 것을 볼 수 있다.

(요 tree의 설계는 안드로메다행 급행열차이니

다른 prefix adder들과 더불어 찬찬히 알아보도록 하자)

따라서, 여기서 귀납적으로 유추해보면

64-bits adder는 16번 bit부터 넘기는 stage가 하나 더 필요하다고 볼...

오늘따라 굉장히 두서없이 글을 싸질르는것 같다.

자, 다시 위의 그림으로 되돌아가 볼 때,

일단은, 처음의 P와 G를 모든 bit에 대해 구해 두도록 한다.

이것이 첫줄 끝이다.

둘째 줄을 보면,

LSB에는 점 위에 연결된 또다른 점이 없는 것을 볼 수 있다.

그럼 얘는 에미없으니깐 Gray cell을 통과시킨다.

나머지는 부모 노드를 가지고 있는 것을 볼 수 있으니

Black cell을 통과시킨다.

그리고 셋째 줄, 넷째 줄 이렇게 나가다보면

그레이쎌 8개(사실은 마지막 스테이지에선 끝까지 그레이쎌)

가 되는 순간 tree가 완성됨을 확인할 수 있다.

그럼...

Gray cell이 뭐고 Black cell이 뭐냐고 ???

찬찬히 가보면,

CLA에서 p와 g로 다음 carry 를 구하는 것이

cout = g+p&cin

이잖은가??

gray cell은 이 공식을 이용하여

전단의 G를 cin에 대입하고

현단의 P와 G를 각각 넣어서 다음 (stage/level/row의)

G를 구하는 cell이며,

black cell은 gray cell을 하나 가지며

이 외에 전단의 P를 입력받아 이를 현단의 P와

AND operate하여 다음 P와 G를 구하는 cell이다.

(둘중 하나만 없으면 캐삭빵!!!!!!!)

자 이렇게 하면 간단히

그렇게나 빠르다는 Kogge-Stone Adder를 구성할 수 있다.

오오미

아 깜빡한게 있는데

이렇게 해서 값이 나오는 것은 아니고

최종 결과값은 각 단의 carry in(최종 stage의 g)과

 p를 XOR 연산해 주면 나온다

그렇다면 최종 carry out은 역시 gray cell을 이용하여 구할 수 있당

허허허허

하이튼

그렇게 해서 나오는 KSA_64와 KSA_32의 resource utilization by entity 표이다.

64-bits KSA는 안드로메다 저 너머롴ㅋㅋㅋㅋㅋㅋ

32-bits KSA도 64-bits KSA와 공유하는 부분이 synthesize되어 있을 뿐이지

CLA 등과 비교해 볼땐 상당히 큰 크기를 가진다

(다시 프로젝트를 만들어서 측정하긴 귀찮으므로 일단 생략)

q_add와 q_add_32는 검증을 위해 사용한 뻘module이므로 신경쓰지 말것

위의 그림에서 slow model에서의 worst case propagation delay를 볼 수 있따.

놀라운 점은

32-bits adder와 64-bits adder가 delay가 다른점이 없다

(실험을 잘못한것같다 -_-;;;;;)

그래서 약 24ns에 64-bits add연산을 끝마치는 것으로 훈훈하게~

허허 잡adder를 쓴다고 했다가

곱셈기부터 쓰고 씨피유 쓰고

갑자기 코그스톤애더를 훈훈하겤ㅋㅋㅋㅋㅋ

일단 오늘은 여기까지