우선순위 디코더를 병렬로 바꾸면 정말 같은 회로일까

세 입력 중 하나를 고르는 디코더가 임계 경로에 들어갔다. if-else를 병렬 식으로 바꾸면 짧아질 것 같지만, 두 요청이 동시에 들어왔을 때 결과가 달라진다. 우선순위 디코더의 깊이는 코드가 길어서 생기는 것이 아니라, 앞선 조건이 뒤의 선택을 막아야 한다는 의미에서 생긴다. 따라서 타이밍을 고치기 전에 무엇을 보존해야 하는지부터 정해야 한다.

여기서는 요청 r2, r1, r0가 있고 각각 8비트 데이터 c, b, a를 가진다고 하자. 아무 요청도 없으면 출력은 0이며, 여러 요청이 동시에 오면 높은 번호가 이긴다. 이 조건은 예제의 설계 계약이다. 실제 제품의 회로 크기나 지연을 측정한 사례가 아니다.

아래 요청은 위 요청의 부재를 기다린다

always_comb begin
  selected = 8'h00;
  if (r2)
    selected = c;
  else if (r1)
    selected = b;
  else if (r0)
    selected = a;
end

r1의 데이터가 선택되려면 r1=1뿐 아니라 r2=0이어야 한다. r0의 선택에는 r2=0과 r1=0이 모두 필요하다. 한 출력 비트의 논리를 AND와 OR로 풀면 다음과 같다.

y = (r2 AND c) OR ((NOT r2) AND r1 AND b) OR ((NOT r2) AND (NOT r1) AND r0 AND a)

여기서 a, b, c는 해당 비트다. 뒤의 항일수록 더 높은 요청이 없는지를 확인한다. 단순한 mux 체인으로 구현하면 이런 우선 관계가 여러 단계의 선택으로 나타날 수 있다. 합성기는 이를 다른 게이트 구조로 바꾸거나 공유·균형화를 할 수 있으므로, RTL의 if 개수가 최종 게이트 단계 수와 정확히 같다는 뜻은 아니다.

이 의미를 무시하고 다음처럼 바꾸면 어떻게 될까.

assign selected = ({8{r2}} & c)
                | ({8{r1}} & b)
                | ({8{r0}} & a);

각 후보를 독립적으로 마스킹한 뒤 OR한다. 요청이 하나뿐일 때는 원래 결과와 같다. 하지만 r2=r1=1, c=8'h0F, b=8'hF0이라면 우선순위 버전은 0x0F, 병렬 OR 버전은 0xFF다. 두 입력을 동시에 섞었기 때문이다. 빨라 보이는 식으로 바꾸면서 동작까지 바꾼 것이다.

입력의 배타성이 있다면 문제가 달라진다

시스템이 r2, r1, r0 중 최대 하나만 높게 만든다고 보장한다면 OR 형태도 같은 선택을 표현할 수 있다. 이 경우 뒤 요청이 위 요청을 기다려야 할 이유가 없어진다. 다만 보장은 주석 한 줄이 아니라, 입력 생성기와 연결 전체에서 확인해야 하는 성질이다.

assert property (@(posedge clk) disable iff (!rst_n)
  !$isunknown({r2, r1, r0}) && $onehot0({r2, r1, r0}));

이 예제는 reset 이후 매 에지에서 요청이 의미 있다고 가정한다. onehot0는 0개 또는 1개의 비트가 켜진 요청을 허용한다. X에 대한 확정성 검사도 함께 적었다. 여러 요청이 합법인 중재기라면 이 assertion을 추가해 입력을 제한하는 것은 최적화가 아니라 요구사항 변경이다.

하위 디코더가 주소의 서로 겹치지 않는 범위에서 생성된다면 배타성을 구조로 증명할 수 있을지도 모른다. 반면 여러 독립 장치가 각각 요청을 내는 경우에는 동시 요청이 자연스럽다. 같은 모양의 r 벡터라도 출처가 다르면 우선순위를 없앨 수 있는 조건이 달라진다.

lowRISC의 조건문과 case 지침은 배타적인 선택과 우선 선택을 코드에서 분명히 드러내는 방식에 참고할 수 있다. 스타일 규칙을 따랐다는 사실보다, 선언한 배타성과 실제 입력의 계약이 같은지가 중요하다.

우선순위를 보존하며 구조를 바꾸는 방법

동시 요청을 허용해야 한다면 우선순위를 버리는 대신 선택 신호를 계산하는 구조를 바꿀 수 있다. 예제의 유효 선택은 g2=r2, g1=r1 AND NOT r2, g0=r0 AND NOT(r2 OR r1)이다. g는 최대 하나만 켜지므로 데이터는 g로 마스킹하여 OR할 수 있다.

이 방식도 더 높은 요청의 존재를 계산해야 한다. 입력 수가 커지면 상위 요청의 OR를 공유하거나 prefix 구조로 계산할 수 있고, 데이터 mux 구조와 선택 논리를 분리할 수도 있다. 그렇다고 이 표현이 항상 빠르거나 작다는 뜻은 아니다. 공유된 신호의 fan-out, 데이터 폭, 셀 라이브러리, 배선과 부하가 결과를 바꾼다.

레지스터를 추가하는 방법도 있다. 하지만 출력이 한 에지 늦어지면 소비자가 어느 거래의 데이터인지 구별할 수 있어야 한다. 디코더 결과만 등록하고 그 결과가 고르는 데이터는 현재 입력으로 남겨 두면, 이전 요청으로 현재 데이터를 고르는 정렬 오류가 생긴다. 타이밍 개선은 제어와 payload의 시간 계약까지 포함한다.

보고서에서 확인할 것은 줄 수가 아니다

실제 변경의 효과를 판단하려면 동작의 동치성과 구현의 경로를 각각 확인해야 한다. 동치성에는 동시 요청과 무요청을 포함한 허용 입력이 들어간다. 타이밍에서는 어떤 요청 비트가 어떤 출력까지 가장 늦게 전달되는지, 그 사이 선택 셀과 배선이 어떻게 놓였는지 봐야 한다. Yosys의 합성 과정 설명은 RTL 프로세스가 여러 최적화 단계를 거쳐 회로로 바뀐다는 점을 보여 준다.

따라서 “if를 case로 바꾸었으니 병렬이다”나 “OR 트리로 적었으니 더 빠르다”는 결론은 구현 근거가 부족하다. 합성기가 이미 같은 구조를 만들었을 수도 있고, 배선 때문에 논리 단계가 적은 쪽이 더 늦을 수도 있다. 코드 변화 자체를 지연의 증거로 쓰기보다, 유지한 기능 계약과 해당 경로의 결과를 함께 보아야 한다.

처음의 작은 디코더는 이제 선택지 셋이 아니라 높은 요청이 낮은 요청의 의미를 바꾸는 회로로 보인다. 그 의존성이 필요하다면 효율적으로 구현해야 하고, 필요 없다면 배타성의 근거를 갖추어 제거할 수 있다. 우선순위 디코더를 고치는 가장 중요한 단계는 식을 짧게 만드는 것이 아니라, 동시에 들어오는 요청에 어떤 답을 내야 하는지 확정하는 것이다.