FPGAが時々動かない？？-ステート・マシンのデッドロック-

「時々FPGAが動かない！」という再現性の低い不具合に遭遇したことはありませんでしょうか？原因の１つとして、ステート・マシン（Finite State Machine, FSM）のデッドロック（Deadlock）が考えられます。

今回は、ステート・マシンのデッドロックについて解説します。

この記事のまとめ

• 何も設定しないと、ステート・マシンはワン・ホット方式でエンコードされる
• ワン・ホット方式にはイリーガル・ステートがある
• イリーガル・ステートになるとデッドロックする
• データ入力が非同期だとイリーガル・ステートになる可能性がある
• リセット入力が非同期だとイリーガル・ステートになる可能性がある

ステート・マシンはワン・ホット方式でエンコードされる

FPGAでは、論理合成ツールが「これはステート・マシンだね！」と思うと（ステート・マシンを推定すると）ユーザーの記述とは異なる回路になります。どのような回路になるかは、設定できます。設定方法はこちらの記事をご覧ください。

関連記事

FPGAにおけるステート・マシン（FSM）のエンコード方式は？

https://www.fpgaland.tech/fsm_encoding_in_fpga

今回はステート・マシン（Finite State Machine, FSM）のステートがどのようにエンコードされるかについて解説します。注意しないと、ユーザーの想定とは異なる回路になってしまいますので、ぜひご覧ください。各エンコード方式の違いと、XilinxのVivado、...

設定をしない場合、多くのケースではワン・ホット方式でエンコードされます。4状態のワン・ホット方式の例を表1に示します。

このとき、ステートマシンの回路は図1のようになります。なお、同図の雲で示したステート遷移ロジックには、通常STATE[3:0]が入力されますが、図を簡単にするために省略しています。

イリーガル・ステートとデッドロック

論理合成ツールが表1のようなステートの割り付けを行います。このとき、定義されていないステートのことを、イリーガル・ステート（Illegal State）といいます。たとえば、4’b0011 や 4’b1110 などです。（この場合12通りあります）

定義されたステートは、定義された条件によって、図2の左のようにステートが遷移します。しかし、定義されていないステートは、図2の右のように、どこにも行くことはできません。この状態をデッドロック（Deadlock）といいます。

デッドロックになると、もう、動きません。「電源を再投入すると治る」というような現象になります。

デッドロックが発生するケース(1) 非同期データ

どのようなときにイリーガル・ステート＆デッドロックが発生するかというと、最も気を付けるべきは非同期です。例を示します。

図1において、正しい動作は以下だとします。

• STATE = 4’b0001 のとき、TRG = High で、STATE→4’b0010 に遷移する

配線や組合せ回路の遅延が異なるため、D0とD1は図3のように異なるタイミングで変化します。TRGが非同期のとき、D0とD1が絶妙なタイミングでラッチされる可能性があります。すると、図3のように STATE = 4’b0011 のイリーガル・ステートになり、デッドロックします。

デッドロックが発生するケース(2) 非同期のリセット

図1において、正しい動作は以下だとします。

• リセット値は STATE = 4’b0001 で、リセット解除後の初期状態は STATE = 4’b0010

図4のように、配線遅延により、リセット信号が到達する時間は異なります。RSTが非同期のとき、ステートを保持するフリップ・フロップが絶妙なタイミングでリセット解除される可能性があります。すると、図4のように STATE = 4’b0011 のイリーガル・ステートになり、デッドロックします。

ちなみに、次のクロックで STATE[0] = 1’b0 になるのでは？と思われるかもしれませんが、そうとは限りません。FF0がリセット解除されて取り込むデータD0は、STATE = 4’b0011 をステート遷移ロジックに入力したときのものです。したがって、”変な”データを取り込むことになります。

次のコードのRSTは、「非同期リセット」と呼ばれますが、ステート・マシンの非同期リセット入力は、非同期にしてはいけません。必ずCLKに同期したリセットを生成して入力するようにします。

1
2
3
4
5
6
7

always @ (posedge CLK or posedge RST) begin
    if (RST) begin
        current_state   <=  INIT;
    end else begin
        current_state   <=  next_state;
    end
end

まとめ

• 何も設定しないと、ステート・マシンはワン・ホット方式でエンコードされる
• ワン・ホット方式にはイリーガル・ステートがある
• イリーガル・ステートになるとデッドロックする
• データ入力が非同期だとイリーガル・ステートになる可能性がある
• リセット入力が非同期だとイリーガル・ステートになる可能性がある