popcount: 비트의 1 개수가 거리와 이진 곱의 답이 되는 조건

8비트 10101010과 11100000은 얼마나 다를까. XOR하면 01001010이고, 1이 세 개이므로 서로 다른 자리는 세 곳이다. popcount는 이런 비트열의 1 개수를 세는 연산이다. 숫자의 크기가 아니라 비트 패턴의 구성에 답한다는 점에서 일반 덧셈과 다른 용도가 생긴다.

popcount의 또 다른 이름은 population count 또는 Hamming weight다. 거리 계산, mask의 활성 원소 수, 이진 표현의 연산에 사용할 수 있다. 다만 같은 기호로 표현해도 회로의 모양과 수치의 계약은 확인해야 한다.

1비트 값들을 충분한 폭으로 더하기

N비트 popcount의 출력은 0부터 N까지다. 8비트 입력은 최대 8이므로 출력에 4비트가 필요하고, 32비트 입력은 최대 32이므로 6비트가 필요하다. 입력 폭의 위치 index를 표현하는 비트 수와 혼동하면 all-ones 입력에서 결과가 감긴다.

덧셈 tree로 생각해 보자. 8개의 1비트 값을 두 개씩 더하면 네 개의 2비트 결과가 된다. 다시 두 개씩 더하면 두 개의 3비트 결과, 마지막에는 하나의 4비트 결과가 된다. 각 단계는 더 많은 입력 비트의 개수를 담으므로 필요한 폭도 늘어난다.

모든 입력이 1이면 첫 단계 결과들은 2, 다음은 4, 마지막은 8이다. 첫 단계부터 끝까지 1비트나 3비트만 사용하면 값의 범위가 맞지 않는다. 중간 덧셈 폭을 명확히 하는 것이 빠른 구조를 고르는 것보다 먼저다.

for문이 반드시 직렬 덧셈기를 만들까

RTL의 조합 블록 안에서 반복문으로 입력 비트를 더하면 코드의 실행 순서는 직렬처럼 보인다. 하지만 합성은 순차 프로그램의 실행 시간을 그대로 회로 사이클로 옮기는 과정이 아니다. 고정된 반복은 펼쳐지고, 합성기가 산술식을 변환하거나 균형을 바꾸고 목표 셀에 매핑할 수 있다.

PULP의 공개 popcount는 출력 폭을 $clog2(InputWidth+1)로 정하고, 조합 for문으로 비트를 더한다. 원문의 설명은 이전의 명시적 tree 대신 고수준 반복 표현을 사용하는 이유를 합성 heuristics와 연결한다. 따라서 “tree를 직접 쓰면 for문보다 언제나 빠르다”는 일반 결론은 source의 취지와도 맞지 않는다.

반대로 모든 도구가 같은 최적화를 한다고 가정해서도 안 된다. 실제 목표와 제약에서 생성된 연산 깊이와 배선을 확인해야 한다. RTL의 글자 수가 짧은 것과 회로가 작거나 빠른 것은 같은 척도가 아니다.

XOR 뒤에 놓으면 비트 거리다

처음의 예에서 X=10101010, Y=11100000이면 X XOR Y=01001010이고 popcount는 3이다. 두 값의 십진 차이나 절댓값과는 관계가 다르다. XOR는 각 자리의 불일치를 표시하고 popcount는 그 표시의 개수를 합친다.

mask가 있는 비교라면 비교 대상에 포함되는 자리만 세어야 한다. (X XOR Y) AND mask를 입력으로 쓰면 mask=1인 자리의 불일치 개수를 얻는다. mask 밖의 비트까지 세면서 그 결과를 활성 원소의 거리로 해석하면 요구와 다른 값을 만든다.

가변 활성 수에서 결과를 비율로 읽을 때도 분모를 고정 전체 폭으로 쓰면 안 된다. 8비트 중 4자리만 활성화했고 두 자리가 다르면 활성 영역의 불일치 비율은 2/4다. 전체 폭의 2/8과는 다른 지표다. 비트 연산의 결과가 맞아도 후속 숫자 해석은 틀릴 수 있다.

이진 곱을 개수로 바꾸는 특별한 조건

두 벡터의 원소가 각각 −1 또는 +1이라고 하자. 같은 부호끼리 곱하면 +1, 다른 부호끼리 곱하면 −1이다. 두 비트 표현을 XNOR하여 같은 부호의 개수 M을 세면 N개 원소의 dot product는 M−(N−M)=2M−N이다.

가상의 N=8에서 같은 부호가 5개이면 결과는 10−8=2다. 이 관계는 ±1 대응을 사용하고 모든 원소가 포함된 경우의 자체 계산이다. 일반적인 8비트 정수나 임의의 양자화 scale에도 곱셈을 XNOR로 바꾸어도 된다는 뜻은 아니다.

활성 mask가 있다면 N도 활성 원소 수로 바뀌어야 한다. 또 2M−N은 음수가 될 수 있으므로 popcount의 unsigned 출력과 후속 signed 결과 폭을 구분해야 한다. 입력 비트를 세는 작은 연산이 다른 수치 계약으로 연결되는 지점이다.

count만 빨라져도 전체 경로가 빨라질까

입력 XOR나 mask, count tree, 후속 scale 또는 비교가 하나의 조합 경로로 이어질 수 있다. popcount 본체를 줄여도 다른 부분이 지배하면 전체 지연의 개선은 작다. 높은 fan-out의 mask나 긴 입력 배선도 구현 비용에 포함된다.

폭이 커지면 레지스터를 추가해 count를 여러 단계로 계산할 수 있다. 이때 결과와 mask의 활성 수, 거래 식별 정보를 같은 요청에 맞춰 전달해야 한다. 같은 숫자 count가 나와도 요청이 어긋나면 기능은 틀린다. 추가 latency와 수락 간격을 모듈 계약으로 적어야 한다.

검증에서는 all-zero, all-ones와 one-hot 입력을 보고, 특정 위치에만 결과가 달라지는지 검사한다. mask가 있다면 비활성 위치의 입력을 바꾸어도 count가 유지되는지 확인할 수 있다. 가장 큰 결과 N을 담는 폭이 특히 유용한 경계 검사다.

popcount는 숫자의 크기 대신 비트의 구성과 관계를 빠르게 요약한다. 활용의 기준은 무엇을 1로 표시했는지, 어느 자리를 포함했는지, 최대 count와 후속 signed 결과를 담을 폭이 충분한지다. 그 조건이 맞으면 짧은 비트 연산이 거리나 이진 합처럼 의미 있는 계산으로 이어진다.