低消費電力のための状態エンコーディング

状態エンコーディングは、有限状態マシン(FSM)の各定義済み状態に 1 と 0 の一意のパターンを割り当てます。従来、FSM 合成の設計基準は、速度、面積、またはその両方でした。ムーアの法則に従い、技術の進歩により、集積回路の密度と速度は指数関数的に増加しました。これにより、面積あたりの電力消費は必然的に増加し、ポータブル コンピューティング デバイスや高速プロセッサの設計者は、設計検討時に電力消費を重要なパラメータとして考慮せざるを得なくなりました。^{[1] [2]}

FSM の合成には、次の 3 つの主要なステップが含まれます。

1. 状態の最小化:名前が示すように、FSM を表すために必要な状態の数が最小化されます。含意テーブル、行マッチング、連続パーティション アルゴリズムなどのさまざまな手法とアルゴリズムにより、同等または冗長な状態が識別され、削除されます。
2. 状態の割り当てまたはエンコードには、FSM の内部状態のブール表現の選択が含まれます。言い換えると、各状態に一意のバイナリ コードを割り当てます。適切なエンコード手法を選択することは非常に重要です。誤った決定を行うと、FSM がロジック領域を過剰に使用したり、速度が遅すぎたり、電力を過剰に消費したり、あるいはこれらの組み合わせになったりする可能性があります。
3. 組み合わせロジックの最小化では、割り当てられていない状態コードをドントケアとして使用して、組み合わせロジックを削減します。

以下は、状態のエンコーディングに広く使用されているテクニックの一部です。

• ワンホットエンコーディングでは、任意の状態に対して状態変数の 1 つのビットのみが「1」(ホット) になります。他のすべてのビットは「0」です。この手法のハミング距離は 2 です。ワンホットでは、FSM のすべての状態に対して 1 つのフリップフロップが必要です。その結果、状態マシンは既に「デコード」されているため、どのフリップフロップがアクティブであるかを調べるだけでマシンの状態が決定されます。このエンコーディング手法により、組み合わせロジックの幅が縮小され、その結果、状態マシンのレジスタ間のロジック レベルが少なくなり、複雑さが軽減され、速度が向上します。
• バイナリ符号化では、状態あたりのビット数 (b) は状態数 (n) に依存します。この関係は次の式で定義されます。

   b = log2(n)

この技術では、状態はバイナリ シーケンスで割り当てられ、状態はバイナリ 0 から順に番号付けされます。明らかに、使用されるフリップフロップの数はビット数 (b) に等しくなります。バイナリ エンコーディングでは、マシンをエンコードするために最小限の数のビット (フリップフロップ) を使用するため、フリップフロップは最大限に活用されます。その結果、One Hot と比較すると、各状態をデコードするためにより多くの組み合わせロジックが必要になります。One Hot と比較すると、必要なフリップフロップの数は少なくなりますが、ハミング距離はビット数 (b) と同じくらい悪くなる可能性があります。

• グレーエンコーディング

グレイコード（反射バイナリコードとも呼ばれる）では、連続する状態コードが1ビットだけ異なるよう状態が割り当てられます。このエンコードでも、ビット数と状態数の関係は次のように定義されます。

   b = log2(n)

使用されるフリップフロップの数とデコードロジックの複雑さはバイナリエンコードと同じです。ただし、グレイコードのハミング距離は常に 1 です。

• その他のエンコード技術

出力ベースのエンコーディング、MUSTANG、^[3] NOVA、^[4]

低消費電力のための状態エンコーディングの設計における主な考え方は、最も可能性の高い状態遷移のハミング距離を最小化し、スイッチングアクティビティを減らすことです。したがって、消費電力を最小化するコストモデルは、最小重み付けハミング距離（MWHD）を持つことです。^{[1] [2]}

カウンターの場合、グレイ コーディングはスイッチング アクティビティを最小限に抑えるため、低電力設計に適しています。グレイ エンコーディングは、状態の変化が連続している場合に最適です。任意の状態変化では、FSM グレイ コードは低電力設計には適していません。このような FSM の場​​合、ワンホット エンコーディングにより、状態変化ごとに 2 ビットのスイッチングが保証されます。ただし、必要な状態変数の数は状態の数に等しいため、状態が増えると、ワンホット エンコーディングは非実用的なソリューションになります。これは主に、回路への入力と出力の数が増えると、複雑さと容量性負荷が増加するためです。バイナリ コーディングは、最大ハミング距離が状態変数の数に等しいため、低電力には最悪です。

任意の状態変更 FSM に対するソリューションの必要性から、状態遷移中のスイッチング アクティビティの削減に重点を置いたいくつかの状態エンコーディング手法が生まれました。

^[5] このアプローチは、状態遷移間のスイッチングアクティビティを最小化する状態割り当てを選択することで、順次回路による電力消費を削減することを目的としています。したがって、FSMの組み合わせ部分は入力遷移確率が低く、合成時に低電力消費になる可能性が高くなります。このアルゴリズムは、行が状態コードに対応し、列が状態変数に対応するブール行列を使用します。一度に1つの状態変数が考慮され、割り当て全体のスイッチングアクティビティを最小化できる方法で、FSMの各状態にその値を割り当てようとします。この手順は次の変数に対して繰り返されます。最小化手法は列ごとに適用されるため、この手法は列ベースと呼ばれます。

マルチコード状態割り当て技術は、冗長な状態を抑制することによって優先符号化を実装する。これにより、状態はより少ない状態変数（ビット）を使用して符号化することができる。さらに、それらの不在状態変数に対応するフリップフロップはクロックゲートすることができる。^[6]

^[7] この技術は、FSMプロファイリングデータから抽出された動的ループ情報を状態割り当てに利用し、スイッチングアクティビティを削減します。この技術が使用する手順は次のとおりです。

1. FSM状態プロファイリングは、関連する入力データセットのFSMの動的動作に関する情報を収集します。
2. ループ検出は、状態トレース内のループを検索し、各ループを保存してカウントし、ループの頻度を取得します。
3. 状態割り当ては、最初の2つのステップで収集されたデータに基づいて各状態に状態変数を割り当て、スイッチングアクティビティを最小限に抑えます。状態変数を割り当てるアルゴリズムは3つあります。

• 基本的なDFS状態割り当てアルゴリズム
• ループベースのDFS状態割り当てアルゴリズム
• ループベースの状態ごとのヒューリスティック状態割り当てアルゴリズム

• いくつかの技術では、状態遷移グラフ（STG）をエンコードして、低消費電力を目標とした2レベルおよびマルチレベルの実装を生成します^{[8] [9]}
• 既存の論理レベル順序回路を再エンコードして電力を最適化する方法が提案されている^[10]
• スパニングツリーベースの状態エンコーディング、^[11]深さ優先法、^[12]最小距離法、^[12] 1レベル法、^[12] 1レベルツリー法、^[12]ここでも焦点は、状態遷移によるスイッチングアクティビティが削減されるように、異なる状態に状態変数を割り当てることにあります。
• 低電力のために状態をエンコードするだけでなく、FSMを2つ以上のサブマシンに分解して、ほとんどの時間アクティブになるのはそのうちの1つだけになるようにする技術もあります。これを利用して、他のサブマシンをクロックゲート^{[13]またはパワーゲート[14]}にすることができます。

• バスエンコーディング
• DFAの最小化
• 論理合成
• 低電力電子機器
• レジスタ転送レベル