有限ステートマシン設計――SoC検証をシンプルに（1/2 ページ）

有限ステートマシン（FSM）を用いた設計では、設計スタイルの選択やFSMの特性である複雑性を考えることが、最終的な製品の品質や検証の容易さを左右する非常に重要な要素となる。

[Shaker Sarwary（米Atrenta社，Michael A Beaver 米inSilica社），EDN]

　大規模SoC（system on chip）は、多数のFSM（finite state machine）で構成されており、それらはデータパスやメモリーなどの部品と組み合わせて使用される。FSMはチップ上に最も数多く存在しているにも関わらず、その最終的な製品の品質や検証の容易さへの影響の大きさを理解している設計者は少ない。FSMは、SoCの機能的なバグの原因にもなりうる。FSM設計のまずさが、タイミングのエラー、処理能力や性能に関する問題などの原因となることも多い。したがって、FSMの検証の容易さや設計スタイルに関する検討が、FSMを用いたSoC設計において重要な要素となる。検証ツールでは、FSMにおいてデッドロックや到達不能なステート（状態）に関するチェックは実行できるが、これらのツールはFSMの設計スタイルに十分対応できていない場合がある（図1）。この記事では、FSMの特徴および、さまざまなFSM設計スタイルにおいて発生する機能や実装上の問題について説明する。また、設計目標を達成するためのFSMの設計・実装のガイドライン^＊1)、^＊2)を示す。

図1　米Atrenta社の「SpyGlass」などの検証ツールは、FSMにおけるデッドロックや到達不能な状態のチェックが可能である。

　FSMにおいて最もよく知られている機能上の問題として、到達不能な状態やデッド・トランジション、デッドロック状態、レジスタ値の固定、非同期入力などが挙げられる。到達不能な状態とは、FSMがあらゆる初期状態から到達できない状態のことである。設計の機能的問題や、FSMにおける意図しない遷移（トランジション）によって発生する。いずれにしろ、この状態は冗長ロジックが存在することを示しており、それらは除去しなくてはならない。デッド・トランジションとは前述したような意図しない、もしくは実際には発生しないような遷移であり、これも冗長なロジックに起因する。

図2　この最終デッドロック状態では、状態“2”はcntの値が4に達するまでは状態”0”に遷移し、それ以降は状態“2”にロックされる。　

　デッドロック状態とは、FSMがほかの状態に遷移できない状態である。同様にn-デッドロック状態とはn個の状態の集合であり、その集合に含まれるあらゆる状態からのあらゆる遷移が、同じくこの集合内の状態へ向かうようなものを指す。ある状態（仮にAとする）から、それ以外の状態への遷移が有限回数行われた後、再び状態Aに遷移すると、以降そのままA以外へ遷移しなくなることがある。これは、FSMが最終的にこの状態に固定されることを意味している。このような状態を、最終デッドロック状態という。これは、単純な検証やシミュレーションでは検出されず、チップとなった後に深刻な障害を引き起こす場合がある。図2は、最終デッドロック状態の例を示している。

　FSMのエンコード機能が原因となってFSMの状態レジスタが0または1の定数値に固定されてしまうという問題も、よく発生する。この状況は、エンコードの処理が誤っている、もしくは最適でないことが原因である。そして非同期入力とは、状態レジスタを制御しているものとは異なるクロック・ドメインからFSMへ到達する入力のことを指す。この状況は、適切に設計されたハンドシェイク回路においても起きることがある。異系統クロックによる問題を防ぐには、あらゆる非同期入力を綿密に検査しなければならない。

メトリックを分析する

　これらの問題に加えて、FSMの設計スタイルが検証の容易さに影響を与える可能性もある。設計者はメトリックを分析して、既存の検証フローやフォーマル検証が適用できるか判断しなければならない。解析は、状態、遷移、入力や出力の数、深さなどのFSMの属性に対し、実装および検証の観点から行なう。これらの属性は、FSM設計の最終的な実装品質を左右する。そしてエンコーディングのスタイル、出力、そして次の状態への論理の記述は、初期状態の表現や記述と同様にFSMの実装および検証に大きな影響を与える。

　状態の数は、FSMの複雑さを示す重要な指標である。状態の数が多いと、FSMコードの可読性が下がり、機能上のバグが発生する可能性が高くなる。さらに、FSMのエンコーディングが複雑になって組み合わせ回路や順序回路を追加する必要が出てくる。そうなるとタイミング条件がシビアになるほか、面積が大きくなる、消費電力が増大するなどの悪影響も出てくる。FSMが大規模になると検証がより困難となり、検証カバレッジも低下する。大規模なFSMを、互いにデータをやりとりする小型のFSMに分割することにより、これらの問題を軽減できる。優れたFSMコーディングの条件は、状態の数を20未満に抑えることである。

　遷移の数も、FSMの複雑さを示す重要な指標の1つである。複雑な遷移は次の状態への組み合わせ回路の複雑化を招き、タイミングに直接影響を与える恐れがある。遷移の数も状態の数同様、非常に重要な要素であり、増大するとFSMの保守・拡張・検証が困難になる。遷移の数を少なくするには、制御回路を新たに設計し、モジュールを再構築する必要がある。この再構築によって、コードは保守や拡張が非常に容易なものになる。通常、FSMの機能を表現するには1つの状態につき2つの遷移があれば十分である。すなわち、20個の状態を持つFSMでは40の遷移が発生していればよい。

　FSMの入出力数は、その出力と次の状態への論理の複雑さに影響する。これは経験則だが、FSMへの入力の数はFSM内の状態の数を超えることはない。そしてFSMからの出力の数はさらに少ない。出力の数を25程度に抑えれば、制御の複雑度はかなり低くなる。

　FSMの深さとは、初期状態から同じ状態を2回経由せずにたどることのできる最長のパス上にある状態の数を指す。FSMの深さが大きくなると検証は難しくなる。さらに状態や遷移の数が多くなるとFSMのパスは分岐が増えて複雑になるため、検証は一層困難になる。FSMの検証やデバッグ処理を難しくしないためには、深さを15より小さく抑えることである。

脚注

※1…Cummings, Clifford E, "Coding and Scripting Techniques for FSM Design with Synthesis-Optimized, Glitch-Free Outputs," Synopsys Users Group Conference, 2000, http://www.snug-universal.org.

※2…Cummings, Clifford E, "The Fundamentals of Efficient Synthesizable Finite State Machine Design and Using NC-Verilog and BuildGates," International Cadence User Group Conference, 2002, http://www.sunburst-design.com/papers/CummingsICU2002_FSMFundamentals.pdf.