Barrel shifter와 단계별 MUX

선수 지식: MUX^{i멀티플렉서 선택 신호에 따라 여러 입력 중 하나를 출력으로 연결하는 조합회로입니다. 선택 비트와 입력 번호의 대응을 명세해야 합니다. 자세히 보기}, 논리·산술 시프트, 조합회로의 전파 지연^{i전파 지연 입력이 바뀐 뒤 출력이 올바른 값으로 안정되기까지 걸리는 시간입니다. 논리식의 등가성과 시간 특성은 별개입니다. 자세히 보기}을 이해해야 합니다.

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

한 비트씩 이동하는 시프트 레지스터^{i레지스터 여러 비트의 상태를 저장하는 회로입니다. 이 과정의 동기식 레지스터는 클록 에지에서 정해진 입력을 저장합니다. 자세히 보기}는 이동 횟수만큼 클록 사이클이 필요합니다. 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개씩 있으므로, 전체 회로에는 1비트 2:1 MUX가 64개 있습니다. 배선·상수 전파를 최적화하기 전의 구조적 개수입니다. 일반적인 $W=2^K$에서는 데이터 선택 구조가 $W\log_2W$에 비례하고 깊이는 $\log_2W$에 비례합니다. 각 출력에 W:1 MUX를 따로 그려도 합성 후에는 트리 형태로 바뀔 수 있으므로 RTL 줄 수로 면적이나 주파수를 단정해서는 안 됩니다.

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

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

비트 순서를 뒤집은 값을 오른쪽으로 s칸 논리 이동한 뒤 다시 뒤집으면 왼쪽 논리 이동이 됩니다. 이 대칭을 이용하면 단계 네 개를 공유할 수 있습니다. 단, 입력과 출력에 방향 선택용 MUX가 추가되므로 필요한 MUX는 64개보다 많습니다. 비트 순서를 고정해서 뒤집기만 한다면 배선으로 구현할 수 있습니다.

산술 오른쪽 이동은 빈 상위 비트에 원래 입력의 부호 비트를 채웁니다. 왼쪽 이동에는 산술 모드여도 0을 채웁니다. 2의 보수^{i2의 보수 고정 폭 비트열로 부호 있는 정수를 나타내는 방식입니다. n비트 범위는 −2^(n−1)부터 2^(n−1)−1까지입니다. 자세히 보기}에서 산술 왼쪽과 논리 왼쪽은 같은 비트 이동이며 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^{iunsigned 비트열을 음수가 없는 정수로 해석하는 규칙입니다. n비트의 범위는 0부터 2^n−1이며, 같은 비트열의 signed 해석과 다를 수 있습니다. 자세히 보기} 벡터에도 산술 이동을 구현합니다. 같은 동작을 연산자로 표현할 때는 오른쪽 산술 이동에 signed 피연산자와 >>>를 사용해야 합니다. >>> 기호를 붙이거나 part-select의 원래 변수를 signed로 선언하는 것만으로는 의도한 부호 처리가 보장되지 않습니다. 연결과 일부 선택은 signed 해석을 잃을 수 있으므로 의도한 폭의 signed 값으로 먼저 변환해야 합니다. 합성 도구가 지원하는 연산자는 AMD의 Verilog 표현식 문서에서 확인할 수 있습니다.

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

조합 단계 네 개에 방향·범위 선택과 배선 지연이 더해집니다. 타이밍이 부족하면 중간에 레지스터를 넣을 수 있지만, 데이터와 함께 남은 이동량·방향 제어도 같은 클록만큼 늦춰야 합니다. 그때부터는 출력 latency^{i지연 사이클 입력을 받아 대응하는 출력이 나올 때까지의 시간 또는 사이클 수입니다. 단위 시간에 처리하는 양인 처리율과 다릅니다. 자세히 보기}가 바뀌며 단순한 조합 모듈과 같은 인터페이스로 취급할 수 없습니다.

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