11rule로 만드는 상태 기계

1. 상태는 enum입니다

상태 기계는 "지금 어디에 있는가"를 담는 레지스터와 다음에 어디로 갈지 정하는 회로입니다. BSV에서 "어디에 있는가"에 맞는 타입은 enum입니다. 나열한 레이블만을 값으로 가지는 새 타입입니다.

형식

typedef enum { Idle, Count, Done } State deriving (Bits, Eq, FShow);

Reg#(State) state <- mkReg(Idle);

deriving (Bits)는 타입에 비트 패턴을 주고, 그 덕분에 레지스터에 담을 수 있습니다. Eq는 ==를 주고, FShow는 fshow(state)로 레이블 이름을 출력하게 합니다. 값을 명시하지 않으면 첫 레이블이 0이고 다음 레이블마다 1씩 커지며, 가장 큰 코드를 담는 최소 비트 수가 폭입니다. 상태는 숫자가 아니라 레이블로 비교합니다. state == 1이 아니라 state == Count입니다.

enum 값의 인코딩·비교·폭은 사용자 정의 타입 장의 enum 절에서 실행 예제와 함께 다룹니다. 이 장은 enum을 상태 레이블로 쓰고 그 규칙은 전제로 둡니다.

2. 상태마다 rule 하나

상태 기계를 상태마다 rule 하나로 씁니다. guard는 ==로 상태를 지정하고, 본문은 그 상태의 일을 하고 다음 상태를 레지스터에 씁니다. 레지스터는 레이블을 정확히 하나만 가지므로 서로 다른 레이블에 대한 guard는 함께 참이 되지 않습니다. 그래서 rule들은 경쟁하지도 충돌하지도 않습니다.

rule start (state == Idle);
  state <= Count;
endrule

rule count (state == Count && n < 3);
  n <= n + 1;
endrule

rule leave (state == Count && n == 3);
  state <= Done;
endrule

state는 현재 상태, state <= …는 다음 상태로 읽으세요. 사이클 k에 쓴 전이는 사이클 k + 1에 guard가 보는 상태입니다. 위의 Count처럼 rule이 둘 이상 필요한 상태는 두 rule이 여전히 배타적이 되도록 조건을 나눕니다.

3. 상태표에서 rule로

기계를 먼저 표로 설계하고, 행마다 rule 하나를 씁니다.

같은 표를 case (state) 하나를 가진 rule 하나로 쓸 수도 있습니다. 각 arm이 조건과 쓰기를 담습니다. 두 형식은 같은 하드웨어를 기술합니다. 상태별 rule은 각 상태의 일을 그 자리에 모아 두고, 단일 rule은 모든 전이를 한곳에 모아 둡니다.

4. phase 레지스터: 한 rule로 못 하는 순서 만들기

상태 기계는 이름 붙은 모드를 가진 프로토콜에만 쓰는 것이 아닙니다. 두 연산을 모두 수행해야 하는데 같은 원자적 전이에 넣을 수 없을 때도 답이 됩니다. 실행 하나는 전이 하나이고 그 안의 모든 읽기는 진입 상태를 보기 때문입니다. 현재 단계를 나타내는 레지스터를 두고 단계마다 정확히 한 rule만 활성화되게 합니다.

형식

typedef enum { 단계1, 단계2, ... } Phase deriving (Bits, Eq);

Reg#(Phase) phase <- mkReg(단계1);

rule 첫_작업 (phase == 단계1);
  ...
  phase <= 단계2;
endrule

typedef enum { Load, Shift, Done } Step deriving (Bits, Eq);
Reg#(Step) step <- mkReg(Load);

rule load (step == Load);
  data <= input_value;
  step <= Shift;
endrule

rule shift (step == Shift);
  data <= data << 1;
  step <= Done;
endrule

load와 shift의 조건은 동시에 참일 수 없으므로 scheduler가 임의로 고를 일이 없습니다.

참고. phase를 추가하면 레지스터 하나와 사이클 하나의 지연이 늘어납니다. 대신 작업 중인 구간을 관찰할 수 있고, 순서가 모호하지 않으며, 프로토콜에 단계를 추가하기 쉬워집니다. 충돌하는 두 rule에 우선순위만 주는 방법은 순서 문제를 해결하지 못합니다. 우선순위는 한 연산을 고를 뿐, 두 연산이 정해진 순서로 모두 일어난다는 보장을 주지 않습니다.

5. 두 전이의 순서 정하기

OrderedRuleTransitions.bsv는 value = 10, increment = 3, phase = AddReady에서 시작합니다. addFirst는 AddReady에서만, doubleSecond는 DoubleReady에서만, show는 Idle에서만 활성화됩니다.

실행하기 전에 예측해 보세요. 각 에지 뒤의 value와 phase를 계산해 보세요.

package OrderedRuleTransitions;

typedef enum { Idle, AddReady, DoubleReady } Phase
  deriving (Bits, Eq, FShow);

(* synthesize *)
module mkTop(Empty);
  Reg#(Bit#(8)) value <- mkReg(10);
  Reg#(Bit#(8)) increment <- mkReg(3);
  Reg#(Phase) phase <- mkReg(AddReady);

  // 각 phase에서는 정확히 한 rule만 활성화되므로 scheduling에 임의적인 우선순위가
  // 필요하지 않다.
  rule addFirst (phase == AddReady);
    value <= value + increment;
    phase <= DoubleReady;
  endrule

  // DoubleReady는 두 원자적 전이 사이에서 관찰 가능한 중간 상태다.
  rule doubleSecond (phase == DoubleReady);
    value <= value << 1;
    phase <= Idle;
  endrule

  rule show (phase == Idle);
    $display("value = %0d", value);
    $finish(0);
  endrule
endmodule

endpackage

결과 확인.

출력이 26이면 덧셈 뒤에 곱셈이 일어났다는 뜻입니다. 순서가 반대였다면 10 × 2 + 3 = 23이 나옵니다. 중간값 13은 한 rule 안의 임시 식이 아니라 사이클 1 동안 실제로 저장된 상태입니다. 이 예제는 경고 없이 컴파일됩니다.

직접 바꿔 보세요.

1. value의 초깃값을 250으로, increment를 10으로 바꿔 보세요. 8비트 덧셈 250 + 10 = 260은 256을 넘으므로 중간값은 4가 되고, 두 배인 8이 출력됩니다. 순서와 고정 폭 연산을 함께 확인할 수 있습니다.
2. 두 연산을 한 rule에 value <= (value + increment) << 1;로 합치면 사이클 하나와 DoubleReady 단계가 사라집니다. 외부에서 중간 단계를 관찰할 필요가 없다면 이쪽이 더 단순합니다.

6. 두 상태 기계를 예측하세요

상태 두 개와 입력 하나로 이루어진 간단한 기계를 생각해 보겠습니다. 토글은 0 또는 1인 q와 입력 t를 가집니다. t가 1이면 다음 상태는 반대쪽이고, t가 0이면 유지합니다. rule로 쓰면 t를 guard로 하고 q <= ~q를 쓰는 rule 하나이고, 거짓인 guard가 유지입니다.

표를 채우세요. 사이클 0은 리셋 상태 q = 0에서 시작합니다. t 열은 그 사이클 동안 rule이 보는 입력이고, 채울 열은 그 사이클을 끝내는 에지 뒤의 q입니다.

이 표는 상태 기계의 브라우저 모델이고 컴파일된 설계가 아닙니다. 위의 예제가 실제 툴체인입니다.

7. 나중의 선택지: 순차 문장

어떤 과정은 표보다 계획으로 읽는 편이 쉽습니다. 이것을 하고, 그 다음 저것을 합니다. StmtFSM 라이브러리는 동작의 seq … endseq를 받아 직접 썼을 상태 레지스터와 rule로 컴파일합니다. 동작 하나가 단계 하나이고, 단계 사이에 클록 에지가 있습니다. 레지스터에 3을 쓴 뒤 4를 더하는 seq는 7로 끝납니다. 두 번째 단계가 나중 사이클에 실행되어 첫 단계가 반영한 값을 읽기 때문입니다. 두 쓰기를 한 rule에 넣으면 둘 다 진입 값을 읽게 되고, 애초에 순서를 표현할 수 없습니다.

이 과정에서 StmtFSM이 필요한 곳은 없습니다. 필요해지면 유한 상태 기계 장이 start, done, 그리고 예제의 테스트벤치에 필요한 started 플래그까지 다룹니다.

8. 적용: 충돌을 두 전이로 바꾸기

예제 아래의 실습 문제는 두 rule이 모두 AddReady에서 활성화되어 같은 레지스터를 읽고 쓰는 상태에서 시작합니다. 상태를 공유하는 rule 장의 충돌입니다. 이미 제공된 Phase enum을 사용해 4절의 기계로 바꾸세요. 먼저 리셋 상태와 start가 만드는 전이를 확인하고, 덧셈 뒤의 다음 단계와 두 배 연산의 guard를 고치세요. 마지막으로 출력된 결과가 요구된 순서에서만 나올 수 있는지 확인하세요.

9. 정리

10. 확인 문제

1. 상태별 rule에서 충돌 경고가 나오지 않는 이유는 무엇일까요?

   정답 보기

   guard가 레지스터 하나를 서로 다른 레이블과 비교하기 때문입니다. 사이클 시작에 그 레지스터는 레이블 하나만 가지므로 많아야 한 guard가 참이고, 두 rule이 같은 사이클을 원할 수 없습니다.

2. 두 rule이 정해진 순서로 모두 실행되어야 하고 각자 상대가 쓴 값을 봐야 합니다. 한쪽에 우선순위를 주는 방법으로 해결되지 않는 이유는 무엇일까요?

   정답 보기

   우선순위는 둘이 같은 사이클을 원할 때 어느 쪽을 실행할지 정할 뿐 순서를 만들지 않습니다. 해결책은 phase 레지스터입니다. 사이클마다 정확히 하나만 활성화되고, 다음 단계가 같은 원자적 전이 안에서 기록됩니다.

3. 순서 예제에서 사이클 1 동안 value에 담긴 값은 무엇이고, 두 rule을 합치면 무엇을 잃게 될까요?

   정답 보기

   value는 사이클 1 내내 중간값 13을 담습니다. 바깥에서 관찰할 수 있는 실제 상태입니다. value <= (value + increment) << 1;로 합치면 그 관찰 가능한 단계와 사이클 하나가 사라집니다. 바깥에서 중간 단계를 볼 필요가 없을 때만 옳은 선택입니다.