Barrel Shifters and Staged Multiplexers

선수 지식: MUX, 논리·산술 시프트, 조합회로의 전파 지연을 이해해야 합니다.

가변 시프트를 고정 배선의 선택으로 바꾸기

한 비트씩 이동하는 시프트 레지스터는 이동 횟수만큼 클록을 사용합니다. barrel shifter는 이동량을 입력으로 받아 한 조합 경로에서 결과를 만듭니다. 비트가 시간을 두고 여러 번 움직이는 것이 아니라, 원하는 위치의 입력 비트를 출력으로 연결하는 배선 경로가 선택됩니다.

16비트 값을 0~15칸 이동한다면 이동량은 $s=s_0+2s_1+4s_2+8s_3$입니다. 따라서 1칸, 2칸, 4칸, 8칸을 이동하는 네 단계를 직렬로 놓습니다. 각 단계는 “그대로 통과”와 “정해진 칸만큼 이동” 중 하나를 MUX로 선택합니다.

예를 들어 11은 이진수 1011이므로 1,2,8칸 단계를 선택하고 4칸 단계는 통과합니다. $X=0xD2A5$를 논리 오른쪽으로 옮기면 0x6952, 0x1A54, 0x1A54, 0x001A를 차례로 얻습니다. 이 중간값들은 네 클록의 값이 아니라 네 조합 단계의 값입니다.

단계별 MUX는 16개씩 네 묶음, 즉 64개의 1비트 2:1 선택 지점입니다. 배선·상수 전파를 최적화하기 전의 구조적 개수입니다. 일반적인 $W=2^K$에서는 데이터 선택 구조가 $W\log_2W$에 비례하고 깊이는 $\log_2W$에 비례합니다. 각 출력에 W:1 MUX를 따로 그려도 합성 후에는 트리 형태로 바뀔 수 있으므로 RTL 줄 수로 면적이나 주파수를 단정해서는 안 됩니다.

입력 0xD2A5를 논리 오른쪽으로 11칸 이동합니다. 이동량 1011의 각 비트가 선택하는 네 조합 단계를 표시했습니다. 네 클록에 걸쳐 실행되는 그림이 아닙니다.

오른쪽 이동 회로로 왼쪽 이동도 만들기

비트 순서를 뒤집은 값을 오른쪽으로 s칸 논리 이동한 뒤 다시 뒤집으면 왼쪽 논리 이동이 됩니다. 이 대칭을 이용하면 단계 네 개를 공유할 수 있습니다. 단, 입력·출력의 방향 선택 MUX가 추가되므로 전체 비용이 64개에서 끝나지는 않습니다. 방향 전환이 없는 고정 비트 역순 자체는 배선입니다.

산술 오른쪽 이동은 빈 상위 비트에 원래 입력의 부호 비트를 채웁니다. 왼쪽 이동에는 산술 모드여도 0을 채웁니다. 2의 보수에서 산술 왼쪽과 논리 왼쪽은 같은 비트 이동이며 signed overflow를 자동으로 검사하지 않습니다.

이동량의 범위도 회로 계약입니다. 아래 예제는 5비트 shamt로 0~31을 받습니다. 16 이상이면 논리 이동과 왼쪽 이동은 0, 산술 오른쪽 이동은 부호 비트 16개입니다. shamt의 하위 4비트만 사용하면 16칸 이동을 0칸 이동으로 오해하므로 별도 처리가 필요합니다.

module barrel16 (
  input  wire [15:0] x,
  input  wire [4:0] shamt,
  input  wire left,
  input  wire arithmetic,
  output wire [15:0] y
);
  wire fill;
  wire [15:0] stage [0:4];
  assign fill = (!left) && arithmetic && x[15];

  for (genvar i = 0; i < 16; i++) begin : direction
    assign stage[0][i] = left ? x[15-i] : x[i];
    assign y[i] = shamt[4] ? fill :
                  (left ? stage[4][15-i] : stage[4][i]);
  end

  for (genvar k = 0; k < 4; k++) begin : shift_stage
    localparam int D = 1 << k;
    assign stage[k+1] = shamt[k]
      ? {{D{fill}}, stage[k][15:D]}
      : stage[k];
  end
endmodule

generate의 k는 회로를 만들 때 정해지는 상수입니다. 런타임에 반복문을 네 번 실행하는 장치가 아닙니다. 각 단계의 part-select와 반복 연결 길이가 고정되므로 네 가지 고정 배선과 MUX로 표현됩니다. fill은 단계마다 달라지지 않아 여러 단계를 선택해도 같은 부호로 확장됩니다.

이 RTL은 부호 채움을 명시해 unsigned 벡터에도 산술 이동을 구현합니다. 연산자로 줄이면 오른쪽 산술 이동에는 signed 피연산자와 >>>가 필요합니다. 단순히 >>> 기호만 붙이거나 part-select의 원래 변수만 signed로 선언해 두면 안전하다고 생각하지 마십시오. 연결과 일부 선택은 signed 해석을 잃을 수 있으므로 의도한 폭의 signed 값으로 먼저 변환해야 합니다. 합성 도구가 지원하는 연산자는 AMD의 Verilog 표현식 문서에서 확인할 수 있습니다.

지연과 정보 손실을 따로 다루기

조합 단계 네 개에 방향·범위 선택과 배선 지연이 더해집니다. 타이밍이 부족하면 중간에 레지스터를 넣을 수 있지만, 데이터와 함께 남은 이동량·방향 제어도 같은 클록만큼 늦춰야 합니다. 그때부터는 출력 latency가 바뀌며 단순한 조합 모듈과 같은 인터페이스로 취급할 수 없습니다.

시프트는 잘려 나간 정보를 복구하지 못합니다. unsigned 왼쪽 이동에서 밀려 나간 상위 비트가 하나라도 1이면 범위 초과입니다. signed 범위 초과는 원래 부호와 잘리는 비트까지 고려해야 합니다. 이 모듈은 그런 플래그를 출력하지 않습니다. 또한 음수의 산술 오른쪽 이동은 $2^s$로 나눈 값을 아래쪽 정수로 내립니다. 따라서 $-3$을 한 칸 옮기면 $-2$이며, 0 방향 정수 나눗셈의 $-1$과 다릅니다.