leading-zero counter: 첫 1을 찾았는데 0 입력에서 틀리는 이유

00000001을 가장 높은 자리부터 검사하면 일곱 번 0을 만난 뒤에야 1을 찾는다. 64비트나 128비트 입력에서도 이런 순서대로 검사해야 할까. leading-zero counter는 앞에서 연속된 0의 개수를 구하지만, 회로는 여러 구간에 1이 있는지 병렬로 판단하며 검색 범위를 좁힐 수 있다.

이 값은 숫자를 정규화할 때 유용하다. 첫 1의 위치를 알면 유효한 숫자 부분을 어느 만큼 이동해야 하는지 정할 수 있다. 여기서는 그 위치를 찾는 회로와 0 입력의 의미에 집중하자.

8비트를 반으로 나누어 찾아보기

입력 00100010의 leading zero 수는 2다. 높은 네 비트 0010에 1이 있으므로 답은 그 구간에 있다. 그 안의 높은 두 비트 00에는 1이 없고, 낮은 두 비트 10에는 있다. 따라서 앞의 두 비트를 건너뛰고 10의 첫 자리가 1임을 확인한다.

각 구간은 두 정보를 만들 수 있다. 구간에 1이 있는지 나타내는 valid와, 있다면 그 구간 안의 첫 1 위치다. 높은 구간이 valid이면 그 결과를 선택한다. 높은 구간이 비어 있고 낮은 구간이 valid이면 높은 구간의 길이를 더한 낮은 결과를 선택한다.

이 관계를 두 비트, 네 비트, 여덟 비트 구간으로 반복하면 tree를 구성할 수 있다. 각 구간의 존재 여부는 OR 계열 논리로, 선택 위치는 mux와 위치 정보로 전달된다. 모든 비트를 직렬로 한 번씩 검사하는 개념과 달리 여러 하위 구간의 계산이 동시에 진행된다.

PULP의 leading/trailing zero counter는 선택 노드와 위치 노드를 나누어 트리로 연결하는 공개 구현이다. leading 모드에서는 비트 순서를 변환해 같은 우선순위 검색 관계를 재사용한다. 기능의 “앞”이 회로에서 어떤 방향인지 확인해야 한다.

숫자 0의 답에는 한 비트가 더 필요하다

32비트 입력에서 첫 1의 위치는 0–31이다. 다섯 비트로 표현할 수 있다. 하지만 모든 입력이 0이면 leading zero 수는 32다. 그 값까지 같은 출력에 담으려면 여섯 비트가 필요하다.

따라서 어떤 인터페이스는 별도의 empty 또는 all-zero 신호를 사용한다. 위치 값은 0–31 범위를 담고, all-zero일 때 그 위치를 정상 숫자로 해석하지 않는 계약이다. 다른 인터페이스는 출력 자체에 32를 담는다. 둘은 기능적으로 대응시킬 수 있지만 포트의 숫자 의미가 다르다.

확인한 PULP 구현은 empty_o로 0 입력을 알린다. 입력 폭이 2의 거듭제곱인 구성에서는 all-zero의 cnt_o가 최대 위치 값에 해당하는 결과를 낸다. 8비트 입력이 모두 0이면 empty_o=1이고 cnt_o를 “0이 7개뿐이다”라는 독립 결과로 소비해서는 안 된다. source의 계약은 두 출력의 조합으로 읽어야 한다.

표의 개수는 수학적인 정의다. 특정 모듈의 count 포트가 마지막 행의 8을 직접 낸다고 주장하는 표가 아니다.

0을 이동시켜도 정규화된 1은 나오지 않는다

정규화 회로가 all-zero를 무시하고 count 값만 shifter에 보내면, 없는 첫 1을 정상 위치처럼 취급할 수 있다. 입력 0은 얼마나 이동해도 0이므로 숫자 비트만 보면 오류가 숨을 수 있다. 하지만 지수 보정이나 valid 상태는 잘못 갱신될 수 있다.

예를 들어 정상 입력 00000001과 0 입력을 같은 위치 값 7로 처리하면, 두 경우 모두 지수를 같은 만큼 바꾸는 제어가 실행될 수 있다. 하나는 유효 숫자를 이동하는 동작이고, 다른 하나는 별도의 zero 결과여야 한다. 위치 계산이 맞아도 all-zero 처리의 관측 계약이 틀리면 전체 숫자 의미가 달라진다.

그 밖의 입력에서도 count는 가장 높은 1의 위치만 알려 준다. 이동 중 잘라내는 낮은 비트와 반올림에 필요한 정보까지 제공하지는 않는다. 위치 탐지와 이후 숫자 변환의 책임을 분리해야 한다.

입력 폭이 2의 거듭제곱이 아니면

7비트나 24비트 입력을 균형 트리에 넣으려면 마지막 구간의 길이와 존재하지 않는 자리를 처리해야 한다. 단순히 높은 쪽에 0을 추가한 뒤 더 넓은 leading-zero 개수를 그대로 반환하면 원래 입력에 없는 0까지 셀 수 있다.

없는 자리는 후보가 없다는 정보로 취급하고, 실제 위치와 구간 길이를 유지하거나 최종 count의 기준을 보정해야 한다. source의 PULP 코드도 범위 밖 노드를 별도 처리한다. parameter가 여러 폭을 허용한다고 해서 우연히 사용하는 32비트만 시험하면 범위 경계 오류를 놓칠 수 있다.

Width=1은 또 다른 경계다. 일반적인 $clog2(1)은 0이므로 포트 폭을 그대로 만들면 선언 문제가 생길 수 있다. 작은 폭을 별도 처리하거나 최소 index 폭을 정하는 구현 정책이 필요하다. 원문의 단일 비트 분기는 이런 경계를 드러낸다.

트리의 이득을 어디까지 기대할까

균형 검색은 구간 크기를 두 배씩 늘려 위치를 찾는다. 하지만 노드의 선택 경로와 배선, 위치 비트의 부하가 실제 지연을 정한다. 전체 위치를 만들 필요 없이 “높은 절반이 비었는가”만 필요한 회로는 더 단순할 수 있다. 반대로 넓은 normalization 경로에서는 이후 shifter가 더 긴 임계 경로일 수 있다.

검증은 첫 1을 모든 위치로 옮긴 one-hot 입력과 0 입력부터 시작하면 명확하다. 여러 1이 있으면 높은 위치가 우선하는지도 확인한다. 결과 폭, empty 처리와 parameter 경계를 같은 검사에 포함해야 숫자와 인터페이스가 일치한다.

leading-zero counter가 빨라질 수 있는 이유는 0을 하나씩 세지 않고 구간의 존재 정보를 병렬로 합치기 때문이다. 좋은 구현은 첫 1을 빠르게 찾는 것에 더해, 1이 없는 입력과 실제 폭 밖의 자리를 정확히 구분한다. 첫 1의 위치보다 먼저 count가 언제 유효한 숫자인지 정하는 것이 설계의 출발점이다.