부분곱 축약: 곱셈기의 많은 비트는 어떻게 하나의 답이 될까

곱셈기의 그림에서 AND gate가 많이 보이면 그 부분이 가장 느릴 것처럼 느껴진다. 하지만 각 부분곱은 병렬로 만들어질 수 있다. 어려운 일은 자릿수가 다른 많은 비트를 하나의 결과로 모으는 과정에 있다. 부분곱 축약을 보면 곱셈의 비용이 단순히 곱셈 기호 하나로 설명되지 않는 이유가 드러난다.

여기서는 unsigned 정수의 전체 결과를 구한다. signed 곱셈과 하위 비트만 필요한 연산은 부호 보정과 버릴 수 있는 비트가 달라지므로 따로 정의해야 한다.

작은 곱셈을 비트의 열로 풀기

4비트 A=11(1011), B=13(1101)을 곱한다고 하자. B의 각 비트가 1이면 A를 해당 자리만큼 이동한 값을 더하고, 0이면 그 항은 0이다.

합은 11+44+88=143, 8비트로 10001111이다. 비트 곱 자체는 AND로 만들 수 있지만, 같은 가중치를 가진 열에 여러 비트가 쌓인다. 일반적인 4×4 unsigned 전체 곱에는 8비트 결과가 필요하다. 예제의 중간 항을 작게 잘라서 더하면 높은 자릿수가 사라질 수 있다.

부분곱의 이동은 입력마다 다른 가변 이동이 아니다. 각 비트가 놓일 가중치를 고정 배선으로 정한 것이다. 실제 합성에서는 0과 상수, 결과의 사용 범위에 따라 원래의 직사각형 그림보다 작은 구조가 될 수 있다.

세 비트를 두 비트로 줄이기

한 열의 세 비트는 full adder 하나로 줄일 수 있다. sum은 같은 열에, carry는 다음 높은 열에 남는다. 총 가중치는 변하지 않는다. 여러 열에 이 작업을 병렬로 수행해 남은 항을 줄이고, 마지막에 두 벡터가 되면 일반 덧셈으로 하나의 숫자를 만든다.

중요한 것은 매번 전체 부분합을 완성하지 않는다는 점이다. 처음 두 부분곱의 carry를 끝까지 전달하고, 그 답에 다음 부분곱을 더하는 직렬 구조는 긴 의존을 반복할 수 있다. 축약 구조는 중간 결과를 여러 열의 sum·carry로 유지하며 더 많은 항을 한꺼번에 처리한다.

Yosys의 maccmap 구현은 입력 곱을 비트 항으로 만들고, full-adder 축약과 마지막 연산으로 연결하는 공개 사례다. add의 부분곱 생성과 fulladd, synth의 축약을 나눠 보면 생성과 축약의 역할이 구분된다. 특정 곱셈기의 실제 topology가 이 코드와 같다는 뜻은 아니다.

축약 단계 수만 줄이면 좋은 곱셈기일까

축약을 넓게 병렬화하면 논리 의존을 줄일 수 있다. 대신 더 많은 연결이 서로 다른 열과 단계 사이를 오간다. 셀 배치가 흩어지거나 fan-out과 배선 부하가 커지면 논리 깊이만의 예상과 다른 지연이 나온다.

또 최종 두 벡터를 더하는 carry-propagate adder가 임계 경로를 차지할 수 있다. 축약 단계에서 시간을 줄였어도 마지막 carry 계산과 결과 선택기가 남는다. 입력 도착 시간, 부분곱 생성, 축약, 최종 합, 출력 선택을 나눈 timing 보고서를 봐야 병목을 찾을 수 있다.

가상의 비교에서 생성 0.2ns, 축약 0.8ns, 최종 합 0.6ns라면 총 1.6ns다. 축약을 0.5ns로 줄여도 최종 합을 포함한 총합은 1.3ns다. 축약의 37.5% 개선이 전체의 같은 비율 개선은 아니다. 수치는 측정이 아닌 구성 요소의 기여를 설명하는 계산이다.

부분곱이 처음부터 적으면 축약의 답도 달라진다

한 피연산자가 상수이면 0인 비트의 항은 필요 없다. 13을 곱하는 예는 A, A<<2, A<<3만 사용한다. 임의의 두 4비트 입력을 곱하는 회로보다 적은 항으로 표현할 수 있지만, 어떤 상수 곱 구조를 실제 선택할지는 합성 목표에 달려 있다.

하위 결과만 필요하면 상위 가중치의 일부 항을 버릴 수 있다. 다만 어느 열의 carry가 필요한 낮은 결과에 영향을 주는지 구분해야 한다. 낮은 열에서 높은 열로 흐르는 carry 관계와 잘라내는 결과 범위를 명시한다. 전체 곱과 modulo 곱을 같은 검증 모델로 비교하면 잘못된 결론이 된다.

signed 입력은 부호 비트의 음의 가중치를 처리해야 한다. unsigned 배열에 단순히 sign bit를 추가하는 것으로 끝나지 않는다. 부호 확장이나 보정 항을 포함한 구조를 사용하고, 최소 음수·−1·0 같은 경계에서 전체 결과와 하위 결과를 따로 검사해야 한다.

파이프라인을 넣어 축약과 최종 합을 다른 사이클에 배치할 수도 있다. 그때는 결과 latency와 거래 식별, valid의 정렬이 회로의 일부가 된다. 축약의 수학적 동치만 확인하고 사이클 계약을 빠뜨리면 정상 숫자가 잘못된 요청에 붙을 수 있다.

곱셈기의 비용을 이해하려면 많은 AND gate의 수만 세기보다, 같은 가중치의 비트들이 어떤 순서로 두 벡터와 최종 합으로 줄어드는지 보면 된다. 부분곱 축약의 좋은 구조는 항의 가중치를 보존하면서 긴 의존을 줄이고, 그 이득을 배선과 마지막 덧셈에서도 유지하는 구조다. 생성이 빠른 것과 결과 전체가 빠른 것 사이의 간격을 설명해 준다.