21FIFO·split·라이브러리 primitive

BSV 설계는 대부분 몇 가지 라이브러리 요소로 만들어집니다. 폭이 정해진 비트 벡터, 튜플, 레지스터, FIFO, 시뮬레이터의 시스템 태스크가 그 요소입니다. 이 장에서는 각 요소를 타입이 미리 정하는 사실, 한 클록 사이클 안에서 method가 하는 일, 호출한 rule을 기다리게 하는 조건으로 나누어 배웁니다. 수 타입과 명시적인 폭 변환은 타입·폭·명시적 변환 장에서, mkReg와 mkRegU는 레지스터와 rule 하나 장에서 다루었습니다. 이 장은 split과 튜플, FIFO와 FIFOF, 시스템 태스크를 다룹니다.

Bit#(n), 타입클래스와 proviso 장의 Add 같은 proviso, 그리고 method: value·Action·ActionValue 장에서 배운 value method, Action method, 원자적 rule을 알고 있어야 합니다. FIFO 절에서는 guard: 유지와 정지 장의 implicit condition이 특히 중요합니다.

예제는 모두 bsc로 컴파일해 Verilog를 생성하고 Icarus Verilog로 시뮬레이션합니다. 실행을 누르면 이 세 단계가 차례로 실행됩니다.

1. split과 튜플

1.1 split의 분할 위치는 결과 타입이 정합니다

split은 벡터 하나를 상위 부분과 하위 부분으로 나눕니다. 어디서 나눌지 알려 주는 인자는 없습니다. 호출하는 쪽이 결과 타입을 쓰면 컴파일 과정에서 두 폭이 결정됩니다.

형식

function Tuple2#(Bit#(m), Bit#(n)) split(Bit#(mn) value)
  provisos (Add#(m, n, mn));

Bit#(8) a = 8'hA5;                             // 1010_0101
Tuple2#(Bit#(2), Bit#(6)) parts = split(a);
// tpl_1(parts)는 2'b10, tpl_2(parts)는 6'b100101

두 결과 폭의 합이 입력 폭과 다르면 Add를 만족하는 m과 n이 없습니다. 이때는 하드웨어가 생성되기 전에 컴파일이 중단됩니다.

1.2 튜플은 소수의 값을 위치로 묶습니다

Tuple2부터 Tuple8까지는 타입을 따로 선언하지 않고 정해진 개수의 값을 묶습니다. tuple2, tuple3 같은 함수로 만들고, tpl_1, tpl_2 같은 함수로 원소를 읽습니다. 패턴 매칭 장의 match를 쓰면 모든 원소를 한 번에 이름과 결합할 수 있습니다.

형식

Tuple2#(타입1, 타입2) 이름 = tuple2(값1, 값2);
타입1 첫째 = tpl_1(이름);
match {.x, .y} = 이름;

let pair = tuple2(8'h12, True);
Bit#(8) data  = tpl_1(pair);     // 8'h12
Bool    valid = tpl_2(pair);     // True
match {.d, .v} = pair;           // d는 8'h12, v는 True

튜플의 원소에는 이름이 없고 위치만 있습니다. 그래서 split의 결과처럼 잠깐 쓰고 버리는 값에 알맞습니다. 여러 곳에서 다시 쓰는 개념이라면 필드 이름이 있는 구조체를 쓰세요. 순서를 혼동할 일이 없고 코드가 스스로 의미를 드러냅니다.

1.3 예제: 12비트 프레임 나누기

SplitVector.bsv는 12비트 프레임을 4비트 kind와 8비트 payload로 나눕니다. 먼저 splitFrame의 선언을 읽으세요. 분할 위치가 나타나는 곳은 결과 타입뿐입니다. 그다음 show rule의 match 선언을 읽으세요.

입력 12'ha5c는 2진수로 1010 0101 1100입니다. 결과 타입 Tuple2#(Bit#(4), Bit#(8))에서 m = 4, n = 8이 정해지고 Add#(4, 8, 12)가 성립합니다.

실행하기 전에 예측해 보세요.

1. kind가 되는 비트는 bit 11..8일까요, bit 3..0일까요?
2. 출력되는 두 16진수 값은 무엇일까요?
3. splitFrame의 본문에 4나 8이라는 숫자가 나올까요?

package SplitVector;

function Tuple2#(Bit#(4), Bit#(8)) splitFrame(Bit#(12) frame);
  // 결과 타입의 폭이 split의 분할 위치를 정한다.
  return split(frame);
endfunction

(* synthesize *)
module mkTop(Empty);
  rule show;
    match {.kind, .payload} = splitFrame(12'ha5c);
    $display("kind=%h payload=%h", kind, payload);
    $finish(0);
  endrule
endmodule

endpackage

결과 확인.

첫 번째 결과 폭이 지정한 대로 분할 위치는 최상위에서 4비트 아래입니다. 함수 본문에는 그 위치가 한 번도 나오지 않습니다.

직접 바꿔 보세요.

1. 결과 타입을 Tuple2#(Bit#(8), Bit#(4))로 바꾸세요. 분할 위치가 최하위에서 4비트 위로 옮겨 가므로 kind=a5 payload=c가 출력됩니다. 함수 본문은 그대로입니다.
2. 입력은 Bit#(12)로 두고 결과 타입을 Tuple2#(Bit#(4), Bit#(4))로 바꾸세요. bsc가 오류 T0031을 보고하며 컴파일이 중단됩니다. 오류 메시지는 Add#(4, 4, 12) 인스턴스가 없다고 알리고 split 호출 위치를 가리킵니다. 비트를 잘라 내지 말고 결과 폭의 합을 12에 맞추어 고치세요.

2. FIFO: 순서와 implicit condition

2.1 네 가지 method

FIFO는 값을 들어온 순서대로 보관합니다. FIFO 패키지의 FIFO#(a)는 method 네 개를 제공합니다.

형식

import FIFO::*;

FIFO#(타입) 이름 <- mkFIFO;              // 깊이는 라이브러리가 정함
FIFO#(타입) 이름 <- mkSizedFIFO(깊이);   // 깊이를 명시
FIFO#(타입) 이름 <- mkFIFO1;             // 깊이 1

FIFO#(Bit#(8)) queue <- mkSizedFIFO(4);

rule produce;
  queue.enq(8'h12);
endrule

rule consume;
  Bit#(8) oldest = queue.first;
  queue.deq;
endrule

2.2 한 rule에서 first와 deq를 함께 호출할 때

mkFIFO, mkSizedFIFO, mkFIFO1에서 first는 사이클 시작 시점의 FIFO를 보고, deq는 사이클이 끝날 때 반영됩니다(mkLFIFO와 mkBypassFIFO는 method 순서가 다릅니다). 따라서 한 rule에서 두 method를 함께 호출하면 first는 deq가 제거할 바로 그 항목을 반환합니다. 상태를 공유하는 rule 장에서 본 대로 rule은 원자적이므로 두 문장의 순서를 바꾸어도 결과는 같습니다.

2.3 implicit condition이 호출자를 기다리게 합니다

호출하는 쪽에서 가득 찼는지, 비었는지를 따로 검사할 필요가 없습니다. 각 method의 준비 조건이 그 method를 호출하는 rule의 조건에 자동으로 포함됩니다. 위의 코드에서 produce는 FIFO가 가득 찬 동안 실행되지 않고, consume은 FIFO가 빈 동안 실행되지 않습니다.

참고. implicit condition 때문에 기다리는 rule은 오류를 내지 않고 실행되지 않을 뿐입니다. FIFO 상태를 바꿀 다른 rule이 없으면 설계 전체가 진행을 멈춥니다.

2.4 예제: 들어온 순서대로 나가는 두 값

FIFOOrder.bsv는 바이트 두 개를 넣었다가 다시 꺼냅니다. mkSizedFIFO(2)의 깊이를 확인한 뒤 네 rule을 step 순서로 읽으세요. rule마다 다른 step 값을 조건으로 쓰므로 사이클마다 정확히 하나의 rule이 실행됩니다.

실행하기 전에 예측해 보세요.

1. dequeueFirst와 dequeueSecond는 각각 어떤 값을 출력할까요?
2. FIFO가 비었는지, 가득 찼는지 검사하는 rule이 있을까요?
3. dequeueFirst의 $display를 queue.deq 아래로 옮기면 출력값이 달라질까요?

package FIFOOrder;

import FIFO::*;

(* synthesize *)
module mkTop(Empty);
  FIFO#(Bit#(8)) queue <- mkSizedFIFO(2);
  Reg#(UInt#(3)) step <- mkReg(0);

  rule enqueueFirst (step == 0);
    queue.enq(8'h12);
    step <= 1;
  endrule

  rule enqueueSecond (step == 1);
    queue.enq(8'h34);
    step <= 2;
  endrule

  // first는 가장 오래된 항목을 읽고 deq는 그 항목을 제거한다.
  rule dequeueFirst (step == 2);
    $display("first=%h", queue.first);
    queue.deq;
    step <= 3;
  endrule

  rule dequeueSecond (step == 3);
    $display("second=%h", queue.first);
    queue.deq;
    $finish(0);
  endrule
endmodule

endpackage

결과 확인.

어느 rule도 FIFO 상태를 검사하지 않았고, implicit condition이 그 일을 대신했습니다. $display를 queue.deq 아래로 옮겨도 first=12가 출력됩니다. 원자적 rule 안에서는 문장 순서가 deq의 반영 시점을 앞당기지 않습니다.

직접 바꿔 보세요.

1. 깊이를 mkSizedFIFO(1)로 바꾸세요. 사이클 1에서 enqueueSecond는 가득 찬 FIFO에 enq를 호출하므로 implicit condition이 거짓이 되어 실행되지 않습니다. step은 1에 머물고 실행 가능한 다른 rule도 없으므로 설계가 교착 상태에 빠집니다. 아무것도 출력되지 않고 $finish에도 도달하지 않아서, 실행 시간 제한이 실행을 끝냅니다. 오류 없이 출력만 사라지는 현상은 implicit condition으로 멈춘 설계의 전형적인 증상입니다.

mkFIFO는 용량을 라이브러리에 맡기고 mkSizedFIFO(깊이)는 용량을 직접 정합니다. 정확성이 깊이에 좌우되지 않아야 하면 mkFIFO로 시작하세요. 위의 교착 상태처럼 버퍼 용량이 설계 동작에 영향을 준다면 깊이를 명시하세요.

2.5 예제: 가득 찬 큐는 생산자를, 빈 큐는 소비자를 붙잡습니다

FIFOOrder.bsv에서는 phase 레지스터 덕분에 어떤 호출도 가득 찬 FIFO나 빈 FIFO를 만나지 않았습니다. FIFOBackpressure.bsv는 두 상황을 모두 일으킵니다. tick은 사이클을 셉니다. produce는 sent < 4인 동안 0, 1, 2, 3을 넣으며 큐가 가득 찼는지 묻지 않습니다. consume의 명시 guard는 cycle >= 3이고, 큐가 비었는지는 묻지 않습니다. 큐는 mkSizedFIFO(2)입니다. 출력되는 모든 줄이 사이클 번호로 시작하므로, rule이 실행되지 않은 사이클은 빠진 줄로 드러납니다. stop은 사이클 9에서 실행을 끝냅니다.

package FIFOBackpressure;

import FIFO::*;

(* synthesize *)
module mkTop(Empty);
  FIFO#(UInt#(8)) queue <- mkSizedFIFO(2);
  Reg#(UInt#(8)) cycle <- mkReg(0);
  Reg#(UInt#(8)) sent <- mkReg(0);

  rule tick;
    cycle <= cycle + 1;
  endrule

  // 가득 찼는지 묻지 않는다. 큐가 가득 차 있는 동안은 enq의 implicit condition이 이 rule을 멈춘다.
  rule produce (sent < 4);
    queue.enq(sent);
    sent <= sent + 1;
    $display("cycle %0d: enq %0d", cycle, sent);
  endrule

  // 명시 guard는 사이클 3부터 참이지만, deq는 여전히 항목이 들어오기를 기다린다.
  rule consume (cycle >= 3);
    queue.deq;
    $display("cycle %0d: deq %0d", cycle, queue.first);
  endrule

  rule stop (cycle == 9);
    $display("cycle %0d: stop", cycle);
    $finish(0);
  endrule
endmodule

endpackage

실행하기 전에 예측해 보세요. 사이클마다 시작 시점의 항목 수, 각 rule의 명시 guard가 참인지, FIFO method가 준비됐는지, 어떤 줄이 출력되는지를 적어 보세요.

결과 확인. 모든 줄을 다음 추적표와 맞춰 보세요. guard/준비 쌍에서 앞의 값은 명시 guard, 뒤의 값은 FIFO method의 준비 여부이며, 둘 다 참일 때만 rule이 실행됩니다.

값은 들어온 순서대로 0부터 3까지 나가고, 어느 rule도 큐를 검사하지 않았는데 빠지거나 겹친 값이 없습니다. 출력이 없는 사이클은 겉보기에 같아도 원인이 다릅니다. 사이클 2에는 생산자가 enq를 기다리고(사이클 3까지 계속 기다립니다), 사이클 7과 8에는 소비자가 deq를 기다립니다.

직접 바꿔 보세요.

1. 깊이를 mkSizedFIFO(4)로 바꾸세요. 생산자는 한 번도 막히지 않습니다. 사이클 0부터 3까지 enq 0부터 enq 3이 나오고, cycle 3: deq 0은 enq 3과 같은 사이클에, 이어서 deq 1, deq 2, deq 3이 사이클 4, 5, 6에 나옵니다.
2. 깊이를 2로 되돌리고 consume의 guard를 cycle >= 1로 바꾸세요. 실행하기 전에 마지막 deq 줄의 사이클을 예측하세요.

3. FIFOF: 준비 상태를 값으로 읽기

3.1 notFull과 notEmpty

FIFOF 패키지의 FIFOF#(a)는 FIFO의 method를 모두 제공하고 value method 두 개를 더합니다. 제어 논리는 이 두 method로 FIFO 상태를 확인할 수 있고, 확인하는 것만으로는 기다리지 않습니다. mkSizedFIFOF의 다른 value method와 마찬가지로 사이클 시작 시점의 상태를 반환합니다(우회 FIFO나 mkCReg 기반 요소는 같은 사이클의 쓰기를 보일 수 있습니다).

형식

import FIFOF::*;

FIFOF#(타입) 이름 <- mkSizedFIFOF(깊이);
Bool roomLeft = 이름.notFull;    // enq를 수행할 수 있음
Bool hasData  = 이름.notEmpty;   // first와 deq를 수행할 수 있음

FIFOF#(Bit#(8)) queue <- mkSizedFIFOF(4);
Reg#(UInt#(8)) stalls <- mkReg(0);

rule countStalls (!queue.notFull);
  stalls <= stalls + 1;           // 가득 찬 사이클마다 1씩 센다
endrule

countStalls는 enq도 deq도 호출하지 않으므로 FIFO에서 오는 implicit condition이 없습니다. 이 rule은 큐가 가득 찬 상태로 시작하는 모든 사이클에 실행됩니다. FIFO가 준비되지 않았을 때 기다리는 대신 다른 일을 하는 것이 상태 플래그의 용도입니다.

3.2 예제: 채움 수준에 따른 두 플래그

FIFOFStatus.bsv는 FIFO에 항목이 0개, 2개, 1개, 0개 있을 때 두 플래그를 출력합니다. mkSizedFIFOF(2)의 깊이를 확인한 뒤 step을 따라 다섯 rule을 읽으세요. 각 $display는 같은 rule의 enq, deq, clear가 반영되기 전에 실행됩니다.

실행하기 전에 예측해 보세요. 출력되는 네 줄마다 (notFull, notEmpty) 쌍을 적어 보세요.

1. 비어 있는 깊이 2 FIFOF는 어떤 값을 보고할까요?
2. 항목이 두 개일 때는 어떨까요?
3. 항목이 하나일 때 두 플래그가 동시에 참일 수 있을까요?

package FIFOFStatus;

import FIFOF::*;

(* synthesize *)
module mkTop(Empty);
  FIFOF#(Bit#(8)) queue <- mkSizedFIFOF(2);
  Reg#(UInt#(3)) step <- mkReg(0);

  rule enqueueFirst (step == 0);
    $display("empty: notFull=%0d notEmpty=%0d", queue.notFull, queue.notEmpty);
    queue.enq(8'haa);
    step <= 1;
  endrule

  rule enqueueSecond (step == 1);
    queue.enq(8'hbb);
    step <= 2;
  endrule

  // 깊이 2인 FIFOF는 두 번 enq한 뒤 notFull이 거짓이다.
  rule removeOne (step == 2);
    $display("full: notFull=%0d notEmpty=%0d", queue.notFull, queue.notEmpty);
    queue.deq;
    step <= 3;
  endrule

  rule clearRest (step == 3);
    $display("one: notFull=%0d notEmpty=%0d", queue.notFull, queue.notEmpty);
    queue.clear;
    step <= 4;
  endrule

  rule finish (step == 4);
    $display("cleared: notFull=%0d notEmpty=%0d", queue.notFull, queue.notEmpty);
    $finish(0);
  endrule
endmodule

endpackage

결과 확인.

두 플래그는 서로 독립적으로 변합니다. 생산자의 rule을 notEmpty로 가드하면 명시 guard가 엉뚱한 때에 참이 됩니다. 빈 FIFO 앞에서는 거짓이고, 가득 찬 FIFO 앞에서는 참이지만 enq의 implicit condition이 rule이 활성화되는 것 자체를 막습니다. 명시 guard가 참인 것과 rule이 활성화된 것은 다릅니다.

직접 바꿔 보세요.

1. 깊이를 mkSizedFIFOF(3)으로 바꾸세요. 항목 두 개로는 FIFO가 가득 차지 않으므로 full: 줄에 notFull=1 notEmpty=1이 출력되고, full:이라는 표시는 사실과 맞지 않게 됩니다. 두 플래그는 코드의 enq 호출 횟수가 아니라 선택한 깊이를 기준으로 용량을 나타냅니다.

3.3 implicit condition과 상태 플래그 가운데 고르기

FIFO가 준비되지 않았을 때 호출자가 해야 할 일로 판단합니다.

4. 시스템 태스크

4.1 시뮬레이터가 제공하는 태스크

$로 시작하는 이름은 시스템 태스크입니다. 시뮬레이터가 제공하는 Action이나 값이며 테스트벤치와 디버깅에 씁니다.

형식

$display(형식_문자열, 인자...);   // 한 줄 출력
$write(형식_문자열, 인자...);     // 줄바꿈 없이 출력
$finish(종료_코드);               // 시뮬레이션 종료
let now <- $time;                 // 현재 시뮬레이션 시간

rule report (count == 3);
  let now <- $time;
  $display("time=%0t count=%0d", now, count);
  $finish(0);
endrule

4.2 시스템 태스크는 하드웨어가 아닙니다

bsc는 시스템 태스크를 synopsys translate_off와 translate_on 주석으로 감싼 Verilog 블록에 생성하고, 합성 도구는 이 블록을 건너뜁니다. 결과를 출력 문자열로만 보여 주는 모듈은 실제 칩에서 아무 동작도 하지 않습니다. 시스템 태스크는 테스트벤치나 시뮬레이션 전용 코드에 두고, 모듈의 결과는 인터페이스와 상태로 제공하세요.

5. 자주 하는 실수

5.1 합이 맞지 않는 split 결과 폭

Bit#(12) frame = 12'ha5c;

// 잘못된 코드: 4 + 4는 12가 아니므로 Add#(4, 4, 12) 인스턴스가 없다(T0031)
Tuple2#(Bit#(4), Bit#(4)) bad = split(frame);

// 바른 코드: 결과 폭의 합이 입력 폭과 같다
Tuple2#(Bit#(4), Bit#(8)) good = split(frame);

오류는 split 호출을 가리키지만 고칠 곳은 결과 타입입니다. 필드 폭을 먼저 적고 그 합이 입력 폭과 같은지 확인하세요.

5.2 생산자를 notEmpty로 제어하기

// 잘못된 코드: 공간이 아니라 데이터를 기다리는 생산자
rule produce (queue.notEmpty);
  queue.enq(x);
endrule

// 바른 코드: 생산자는 공간이 있는지 확인한다
rule produce (queue.notFull);
  queue.enq(x);
endrule

notEmpty는 소비자가 확인하는 플래그입니다. 플래그를 잘못 고르면 생산자는 FIFO가 비어 있을 때, 곧 가장 일해야 할 때 멈춰 있습니다.

5.3 같은 rule 안에서 deq가 first를 바꾼다고 생각하기

rule takeTwo;
  Bit#(8) a = queue.first;
  queue.deq;
  Bit#(8) b = queue.first;   // 여전히 a와 같은 항목
endrule

두 번의 first는 모두 사이클 시작 시점의 상태를 보므로 a와 b는 같습니다. 항목 두 개를 꺼내려면 FIFO를 두 개 쓰거나 두 사이클에 나누는 식으로 구조를 바꾸어야 합니다.

6. 정리

7. 확인 문제

1. split의 분할 위치는 어디에서 정해지며, 잘못된 위치는 어느 단계에서 검출될까요?

   정답 보기

   결과 타입에서 정해집니다. 두 결과 폭에서 m과 n이 결정되고 Add#(m, n, mn)을 검사합니다. 합이 입력 폭과 다르면 하드웨어가 생성되기 전, 타입 검사 단계에서 T0031이 발생합니다.

2. 한 rule에서 first와 deq를 함께 호출하면 first가 deq로 제거될 항목을 반환하는 까닭은 무엇일까요?

   정답 보기

   first는 value method이며 mkFIFO에서는 사이클 시작 시점의 상태를 반환합니다. deq는 사이클이 끝날 때 반영되는 Action입니다. 원자적 rule 안에서는 문장 순서가 제거 시점을 앞당기지 않습니다.

3. 깊이 2인 FIFOF에 항목이 하나 있습니다. notFull과 notEmpty는 각각 어떤 값이며, 생산자는 어느 플래그를 확인해야 할까요?

   정답 보기

   둘 다 참입니다. 항목 하나를 더 넣을 공간이 있고 읽을 항목도 하나 있습니다. 생산자는 notFull을 확인합니다. notEmpty는 소비자가 확인하는 플래그입니다.

4. mkSizedFIFO(1)로 바꾸면 FIFOOrder.bsv에서 어느 rule이 멈추며, 오류 메시지가 없는 까닭은 무엇일까요?

   정답 보기

   enqueueSecond가 멈춥니다. 가득 찬 FIFO에 enq를 호출하므로 implicit condition이 거짓입니다. 거짓인 implicit condition은 rule의 실행을 막을 뿐 오류가 아닙니다. step이 바뀌지 않으므로 다른 rule도 실행되지 않고, 실행 시간 제한이 실행을 끝냅니다.

아래 실습 문제는 각각 이 장의 계약 하나를 다시 사용합니다. 12비트 프레임을 4비트 kind와 8비트 payload로 나누는 method, 가장 오래된 바이트를 반환하고 제거하는 큐 method, 그리고 비어 있는데도 데이터를 받을 수 없다고 보고하는 elastic queue의 원인 찾기입니다.