20StmtFSM으로 만드는 유한 상태 기계

rule은 작업이 가능해질 때마다 반응하는 하드웨어를 기술합니다. 그런데 어떤 과정은 "하나를 하고, 사건을 기다리고, 작업을 몇 번 반복한 뒤, 끝났다고 알린다"처럼 순서가 있는 계획으로 적는 편이 훨씬 자연스럽습니다. 이런 계획을 rule만으로 쓰면 rule로 만드는 상태 기계 장의 phase 레지스터처럼 현재 진행 위치를 나타내는 상태가 여러 레지스터와 조건에 흩어집니다. StmtFSM 라이브러리를 쓰면 계획을 순차 문장으로 적고, 그 문장을 일반 BSV rule로 변환할 수 있습니다.

레지스터, Action, rule 조건을 알고 있어야 하며, 레지스터 쓰기가 클록 에지에서 반영된다는 사실을 기억해야 합니다. 패턴 매칭 장에서는 한 사이클 안의 선택을 다루었습니다. 이 장에서는 작업을 여러 사이클에 나누어 진행합니다.

1. 과정의 기술과 실행

1.1 Stmt와 mkFSM

Stmt는 제어 흐름을 기술하는 값입니다. Stmt를 만들기만 해서는 어떤 Action도 실행되지 않습니다. Stmt를 mkFSM에 전달해야 컨트롤러가 만들어집니다. 컨트롤러는 과정이 어디까지 진행했는지 기억하는 상태와 그 상태를 전진시키는 rule로 이루어집니다.

형식

import StmtFSM::*;

Stmt 이름 = seq
  문장;
  문장;
endseq;

FSM 컨트롤러 <- mkFSM(이름);

Stmt process = seq
  value <= 3;
  value <= value + 4;
endseq;

FSM controller <- mkFSM(process);

컨트롤러의 상태는 과정이 어디까지 진행했는지를 기억하고, 설계의 레지스터는 과정이 무엇을 처리하는지를 기억합니다. 두 상태를 구분하면 FSM이 기다리는 동안에도 다른 레지스터가 계속 바뀌는 까닭을 쉽게 이해할 수 있습니다.

참고. mkFSM에 전달하지 않은 Stmt는 아무 일도 하지 않습니다. FSM 없이 Stmt p = seq v <= 9; endseq;만 선언하면 v는 초기값 그대로입니다.

1.2 FSM 인터페이스

mkFSM이 반환하는 인터페이스에는 method가 네 개 있습니다.

done은 첫 start 전에도 True이고, 마지막 문장이 끝난 뒤 다시 True가 됩니다. 실행이 끝난 컨트롤러는 다시 시작할 수 있습니다.

1.3 시작과 완료 관찰

done은 실행 전에도 참이므로, 테스트벤치는 컨트롤러를 시작했다는 사실을 따로 기억해야 합니다.

Reg#(Bool) started <- mkReg(False);

rule launch (!started);
  controller.start;
  started <= True;
endrule

rule finish (started && controller.done);
  $finish(0);
endrule

started가 없으면 finish가 첫 사이클의 유휴 컨트롤러를 보고, 아무 작업도 하기 전에 시뮬레이션을 끝냅니다. 이 장의 모든 예제가 이 형태를 사용합니다.

2. seq의 순차 단계

2.1 Action 하나가 단계 하나

seq ... endseq 안의 문장은 소스 순서대로 실행됩니다. Action 문장 하나가 FSM 단계 하나이며, 그 단계의 레지스터 쓰기는 다음 단계가 시작되기 전의 클록 에지에서 반영됩니다. 따라서 뒤 단계는 앞 단계가 쓴 값을 읽습니다.

형식

seq
  Action1;
  Action2;
endseq

상태를 공유하는 rule 장에서 본 것처럼 rule 안의 모든 읽기는 시작 시점의 상태를 보는데, seq는 그 점이 다릅니다. 쓰기 여러 개를 한 단계에 넣으려면 action ... endaction 블록으로 묶습니다. 묶인 쓰기는 함께 반영되고, 블록 안의 읽기는 여전히 이전 값을 봅니다.

seq
  action
    value <= 3;
    other <= value + 4;   // 3이 아니라 이전 값을 읽습니다
  endaction
endseq

2.2 예제: 서로 의존하는 두 단계

SequentialActions.bsv의 과정은 value에 3을 쓴 뒤 4를 더합니다. value 선언, process의 두 문장, start와 finish 순서로 읽으세요.

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

1. 두 번째 대입은 초기값 0과 첫 단계가 쓴 3 가운데 어느 값을 읽을까요?
2. finish는 어떤 값을 출력할까요?

package SequentialActions;

import StmtFSM::*;

(* synthesize *)
module mkTop(Empty);
  Reg#(UInt#(8)) value <- mkReg(0);

  // 각 Action은 순서대로 실행되는 별도의 FSM 단계가 된다.
  Stmt process = seq
    value <= 3;
    // 두 번째 단계는 첫 단계가 반영한 값을 읽는다.
    value <= value + 4;
  endseq;

  FSM controller <- mkFSM(process);
  Reg#(Bool) started <- mkReg(False);

  rule start (!started);
    controller.start;
    started <= True;
  endrule

  rule finish (started && controller.done);
    $display("value=%0d", value);
    $finish(0);
  endrule
endmodule

endpackage

결과 확인. 들여쓰기가 아니라 상태 전이를 따라가세요.

출력된 7은 단계의 순서와 두 쓰기 사이의 클록 에지를 함께 보여 줍니다. 두 번째 단계가 초기값 0을 읽었다면 결과는 4였을 것입니다.

직접 바꿔 보세요.

1. 두 문장의 순서를 바꾸어 보세요. 4를 먼저 더한 뒤 3으로 덮어쓰므로 finish는 3을 출력합니다. 식은 그대로이고 제어 순서만 바뀌었습니다.
2. 두 문장을 action ... endaction 하나로 묶어 보세요. 한 단계가 value를 두 번 쓰게 되어, 컴파일이 오류 G0004로 중단됩니다. 메시지는 rule이 "uses methods that conflict in parallel", 즉 value.write 호출 두 개가 충돌한다고 알려 줍니다. 원자적 Action 하나에서는 레지스터를 한 번만 쓸 수 있습니다.

3. 반복과 조건

3.1 repeat, while, for

Stmt 안의 반복문은 FSM 단계를 여러 사이클에 걸쳐 반복합니다. 변수·반복문·리터럴의 문맥 장에서 본 함수 안의 반복문이 elaboration 중에 한 사이클짜리 하드웨어로 펼쳐지는 것과 다릅니다.

형식

repeat (횟수) 문장
while (조건) 문장
for (초기화; 조건; 갱신) 문장

Stmt 안에서 for의 각 부분은 Action이므로 인덱스는 <=로 쓰는 레지스터입니다.

for (i <= 0; i < 3; i <= i + 1)
  acc <= acc + 10;

acc = 0에서 시작하면 10을 세 번 더하므로, FSM이 끝났을 때 i는 3, acc는 30입니다.

3.2 예제: 네 번 증가

RepeatLoop.bsv는 count를 1 늘리는 동작 하나를 반복합니다. count의 초기값, 반복 횟수, 레지스터 쓰기 하나를 찾으세요.

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

1. finish는 무엇을 출력할까요?
2. 증가가 몇 번 반영되며, 중간 값은 각각 얼마일까요?

package RepeatLoop;

import StmtFSM::*;

(* synthesize *)
module mkTop(Empty);
  Reg#(UInt#(8)) count <- mkReg(0);

  Stmt process = seq
    // repeat 횟수가 본문의 실행 횟수를 정한다.
    repeat (4) seq
      count <= count + 1;
    endseq
  endseq;

  FSM controller <- mkFSM(process);
  Reg#(Bool) started <- mkReg(False);

  rule start (!started);
    controller.start;
    started <= True;
  endrule

  rule finish (started && controller.done);
    $display("count=%0d", count);
    $finish(0);
  endrule
endmodule

endpackage

결과 확인. count는 0 -> 1 -> 2 -> 3 -> 4로 변하고 finish는 4를 출력합니다. 화살표 하나가 본문 한 번의 실행과 쓰기 한 번의 반영입니다. 네 번째 쓰기가 반영된 뒤에야 컨트롤러가 완료를 알리므로, 출력값은 반복 제어와 레지스터 갱신을 함께 검증합니다.

직접 바꿔 보세요.

1. 초기값을 mkReg(2)로 바꾸어 보세요. repeat (4)는 여전히 네 번 증가하므로 결과는 6입니다.
2. mkReg(2)를 유지한 채 repeat (4)를 while (count < 4)로 바꾸어 보세요. 반복이 목표 상태에서 멈추므로 두 번 증가하고 결과는 4입니다.

3.3 Stmt 안의 if

if와 else는 FSM이 다음에 실행할 문장을 고릅니다. 조건은 FSM이 if에 도달했을 때, 즉 앞 단계가 모두 반영된 뒤에 평가됩니다.

seq
  x <= 7;
  if (x > 5) x <= 100; else x <= 1;
endseq

if는 반영된 7을 읽으므로 x는 최종적으로 100이 됩니다.

4. await로 기다리기

4.1 제어 위치 하나에 머무르기

await (조건)은 조건이 참이 될 때까지 FSM을 현재 위치에 붙잡아 둡니다. 뒤의 문장은 실행되지 않고 FSM은 완료를 알리지 않습니다. 같은 모듈의 다른 rule은 계속 실행되며, 언젠가 조건을 참으로 만들 rule도 그 가운데 하나입니다.

형식

await (조건);

주의. 조건을 참으로 만드는 곳이 없으면 FSM은 끝없이 기다립니다. 그러면 done을 조건으로 쓰는 종료 rule도 실행되지 않고, 실행 시간 제한에 걸려야 시뮬레이션이 끝납니다.

4.2 예제: 준비 신호를 기다린 뒤 결과 쓰기

AwaitCompletion.bsv에는 사이클을 세다가 cycle == 3을 보면 ready를 세우는 advance가 계속 실행됩니다. FSM은 ready를 기다린 뒤 result에 8'h2a를 씁니다. advance, await, 결과 쓰기, finish 순서로 읽으세요.

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

1. FSM이 await에서 기다리는 동안 바뀌는 레지스터는 무엇일까요?
2. finish가 0인 result를 출력하는 경우가 있을까요?
3. 출력되는 cycle은 정확히 3일까요?

package AwaitCompletion;

import StmtFSM::*;

(* synthesize *)
module mkTop(Empty);
  Reg#(UInt#(4)) cycle <- mkReg(0);
  Reg#(Bool) ready <- mkReg(False);
  Reg#(Bit#(8)) result <- mkReg(0);

  rule advance;
    cycle <= cycle + 1;
    if (cycle == 3) ready <= True;
  endrule

  Stmt process = seq
    // FSM은 ready가 참이 될 때까지 await에 머문다.
    await (ready);
    result <= 8'h2a;
  endseq;

  FSM controller <- mkFSM(process);
  Reg#(Bool) started <- mkReg(False);

  rule start (!started);
    controller.start;
    started <= True;
  endrule

  // 실행을 시작한 뒤에는 마지막 Action이 끝나야 done이 다시 참이 된다.
  rule finish (started && controller.done);
    $display("cycle=%0d result=%02h", cycle, result);
    $finish(0);
  endrule
endmodule

endpackage

결과 확인. 실행은 네 단계로 나뉩니다.

1. start가 컨트롤러를 시작합니다. 이때 ready는 거짓, result는 0입니다.
2. advance는 계속 cycle을 증가시키고 FSM은 await에 머뭅니다.
3. 시작 시점의 cycle이 3인 사이클에 advance가 ready <= True를 예약합니다. 쓰기는 에지에서 반영되므로 await는 그다음 사이클 이후에 참을 봅니다.
4. FSM이 await를 지나 다음 단계에서 8'h2a를 쓰고, 그 쓰기가 반영된 뒤에야 완료를 알립니다.

출력되는 result는 0이 아니라 2a입니다. FSM이 단계를 진행하는 동안에도 advance가 계속 실행되었으므로 cycle은 3을 한참 지나 있습니다. 소스 줄 수로 정확한 지연을 계산하지 마세요. 사이클 배치는 생성된 제어 단계와 다른 rule이 정합니다. 보장되는 계약은 준비, 결과 쓰기, done의 순서입니다.

직접 바꿔 보세요.

1. cycle == 3을 cycle == 6으로 바꾸어 보세요. 출력되는 cycle이 3만큼 커지고 result는 여전히 2a입니다. 지연은 바뀌었지만 순서는 그대로입니다.
2. 비교를 되돌리고 finish 조건에서 started &&를 지워 보세요. 유휴 상태의 컨트롤러는 이미 done이 참이므로 finish가 첫 사이클에 실행되어 cycle=0, result=00을 출력합니다. 1.3절에서 설명한 조기 종료 증상을 일부러 재현한 결과입니다.

5. par의 병렬 분기

5.1 par ... endpar

par 블록의 분기는 동시에 진행할 수 있습니다. par 문장은 모든 분기가 끝나야 완료됩니다.

형식

par
  분기1;
  분기2;
endpar

par
  a <= 1;
  b <= 2;
endpar

두 분기가 서로 다른 레지스터를 쓰므로 독립적입니다. par가 끝나면 a는 1, b는 2입니다.

5.2 par에도 일반 스케줄링이 적용됩니다

분기 안의 Action은 각각 생성된 rule이 되고, par를 쓴다고 rule의 스케줄링 방식이 바뀌지는 않습니다. 두 분기가 x를 읽지 않고 쓰기만 한다면 충돌이 아니라 가림입니다. bsc는 경고 G0036과 G0117을 내면서 컴파일하고, 경고에는 f_action_l7c28처럼 소스의 줄과 열로 만든 생성 rule 이름이 나옵니다. 남는 것은 스케줄에서 뒤에 오는 쓰기입니다. 각 분기가 상대가 쓰는 것을 읽는다면 그것은 진짜 충돌이고, 두 분기는 한 사이클을 나눌 수 없습니다. 두 경우 모두 상태를 공유하는 rule 장의 두 rule과 똑같이 동작합니다. 사이클 단위의 겹침이 설계 계약에 들어 있다면 스케줄링 경고를 확인하거나 명시적인 rule로 작성하세요.

6. 자주 하는 실수

6.1 시작하지 않고 done으로 종료하기

// 잘못된 코드: start 전에도 done은 참입니다
rule finish (controller.done);
  $finish(0);
endrule

// 바른 코드: 실행을 시작했다는 증거를 함께 요구합니다
rule finish (started && controller.done);
  $finish(0);
endrule

잘못된 코드는 첫 사이클에 초기값으로 시뮬레이션을 끝냅니다. await 예제에서는 cycle=0, result=00이 출력됩니다.

6.2 의존하는 쓰기를 한 단계에 넣기

// 잘못된 코드: 두 쓰기가 모두 시작 시점의 0을 봅니다
seq
  action
    value <= 3;
    other <= value + 4;   // 7이 아니라 4
  endaction
endseq

// 바른 코드: 단계를 나누어 두 번째가 반영된 3을 읽게 합니다
seq
  value <= 3;
  other <= value + 4;     // 7
endseq

Action 하나 안의 읽기는 모두 시작 시점의 상태를 봅니다. 새 값에 의존하는 계산에는 단계 경계가 필요합니다.

6.3 Stmt를 선언만 하고 실행하지 않기

// 잘못된 코드: 과정을 기술만 하고 아무것도 실행하지 않습니다
Stmt process = seq v <= 9; endseq;

// 바른 코드: 컨트롤러를 만들고 시작합니다
Stmt process = seq v <= 9; endseq;
FSM controller <- mkFSM(process);
// ... 그리고 rule에서 controller.start를 호출합니다

Stmt는 기술일 뿐입니다. mkFSM과 start가 없으면 어떤 레지스터도 바뀌지 않습니다.

6.4 목표 상태가 계약인데 repeat 쓰기

// "4에 도달"이 목표라면 잘못된 코드: 2에서 시작하면 6에서 끝납니다
repeat (4) count <= count + 1;

// 목표 상태에 맞는 코드
while (count < 4) count <= count + 1;

repeat (n)은 결과가 아니라 반복 횟수를 셉니다. 반복문을 고르기 전에 계약이 작업량을 정하는지 최종 상태를 정하는지 먼저 판단하세요.

6.5 두 par 분기에서 같은 레지스터 쓰기

// 잘못된 코드: 한 분기의 x 쓰기가 다른 분기의 쓰기를 가립니다
par
  x <= 1;
  x <= 2;
endpar

// 바른 코드: 분기마다 다른 상태를 쓰거나 순서를 정합니다
seq
  x <= 1;
  x <= 2;
endseq

잘못된 코드는 경고 G0036, G0117과 함께 컴파일되며 쓰기 하나가 사라집니다. par는 분기가 겹칠 수 있다는 뜻일 뿐, 한 레지스터에 대한 두 쓰기에 의미를 부여하지 않습니다.

7. StmtFSM과 명시적 rule의 선택

StmtFSM은 테스트벤치, 초기화 절차, 처리량이 낮은 컨트롤러처럼 사이클 최적화보다 읽기 쉬운 과정이 중요한 곳에 알맞습니다. 대기, 반복, 완료를 한곳에 모아 둘 수 있습니다.

처리량, 자원 충돌, 정확한 겹침을 직접 설계해야 하면 명시적인 rule이 낫습니다. 두 연산이 안전하다는 것을 아는 설계자는 반복 관리와 실제 작업을 한 사이클에 합칠 수 있지만, 범용 FSM 변환은 안전을 위해 단계를 하나 더 쓸 수 있습니다. 두 방식 모두 하드웨어가 되므로, 선택 기준은 구조의 명료성과 사이클의 직접 제어 가운데 무엇이 더 중요한가입니다.

8. 정리

9. 확인 문제

1. Stmt를 선언해도 레지스터가 바뀌지 않는 까닭은 무엇일까요?

   정답 보기

   Stmt는 elaboration 중에 제어 흐름을 기술하는 값입니다. mkFSM이 만든 컨트롤러를 시작해야 Action이 실행됩니다.

2. seq의 두 번째 Action이 첫 Action의 결과를 읽을 수 있는 까닭은 무엇일까요?

   정답 보기

   두 Action이 서로 다른 FSM 단계이기 때문입니다. 첫 단계의 쓰기가 클록 에지에서 반영된 뒤에 두 번째 단계가 평가됩니다.

3. FSM이 await에서 멈춰 있는 동안 계속 바뀔 수 있는 상태는 무엇일까요?

   정답 보기

   예제의 cycle처럼 다른 rule이 쓰는 모든 레지스터입니다. 멈추는 것은 해당 FSM의 진행뿐입니다.

4. par의 두 분기가 같은 사이클에 실행된다는 보장이 없는 까닭은 무엇일까요?

   정답 보기

   분기의 Action은 각각 생성된 rule이 되어 다른 rule과 똑같이 스케줄링되기 때문입니다. 같은 레지스터에 대한 뒤 분기의 쓰기는 앞 분기의 쓰기를 가리고, 각자 상대가 쓰는 것을 읽는 분기는 충돌하므로 한 사이클을 나눌 수 없습니다.

5. 종료 rule이 초기 유휴 상태와 실행 완료 상태를 구분해야 하는 까닭은 무엇일까요?

   정답 보기

   두 상태 모두 done이 참입니다. started 같은 별도 기록이 없으면 FSM이 아무 작업도 하기 전에 종료 rule이 실행됩니다.

아래 Practice 문제에서는 FSM을 직접 만들고 고칩니다. Stmt에 noAction만 있어서 레지스터가 0에 머무는 문제, 반복 본문이 필요한 횟수보다 한 번 적게 실행되는 문제, FSM이 기다리던 작업의 결과가 나오기 전에 완료를 알리는 문제입니다.