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

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

背景

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

  1. 状態最小化：その名の通り、FSMを表現するために必要な状態数を最小化します。含意表、行マッチング、逐次分割といった様々な手法とアルゴリズムによって、同等または冗長な状態を識別し、削除します。
  2. 状態割り当て、つまりエンコーディングは、FSMの内部状態のブール表現を選択することを意味します。言い換えれば、各状態に固有のバイナリコードを割り当てるということです。適切なエンコーディング手法を選択することは非常に重要です。誤った選択をすると、FSMのロジック領域が過剰に消費されたり、動作が遅くなったり、消費電力が過剰になったり、あるいはこれらの組み合わせになったりする可能性があります。
  3. 組み合わせ論理の最小化では、割り当てられていない状態コードをドントケア状態として使用して、組み合わせ論理を削減します。

既存のエンコード技術

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

  • ワンホットエンコーディングでは、任意の状態において状態変数のビットのうち1つだけが「1」（ホット）になります。他のビットはすべて「0」です。この手法のハミング距離は2です。ワンホットエンコーディングでは、FSM内の各状態に対して1つのフリップフロップが必要です。その結果、ステートマシンは既に「デコード」されているため、どのフリップフロップがアクティブであるかを調べるだけでステートマシンの状態を判断できます。このエンコーディング手法は組み合わせロジックの幅を縮小し、結果としてステートマシンのレジスタ間のロジックレベル数を削減し、複雑さを軽減して速度を向上させます。
  • バイナリ符号化では、状態あたりのビット数 ( b ) は状態数 ( n ) に依存します。この関係は、方程式b = log 2 ( n )で定義されます。この手法では、状態は 0 から始まる番号が付けられたバイナリシーケンスで割り当てられます。使用されるフリップフロップの数は、ビット数 ( b ) と等しくなります。バイナリ符号化では、マシンを符号化するために最小限の数のビット (フリップフロップ) を使用するため、フリップフロップが最大限に活用されます。その結果、ワンホット符号化と比較すると、各状態をデコードするためにより多くの組み合わせロジックが必要になります。バイナリ符号化では、ワンホット符号化と比較すると必要なフリップフロップの数が少なくなりますが、ハミング距離はビット数 ( b ) まで同様に悪くなる可能性があります。
  • グレイ符号化（反射二進符号化とも呼ばれる）では、連続する状態コードが1ビットのみ異なるように状態が割り当てられます。この符号化では、ビット数と状態数の関係はb = log 2 ( n )で定義されます。使用されるフリップフロップの数と復号ロジックの複雑さは二進符号化と同じですが、グレイ符号化におけるハミング距離は常に1です。

その他の符号化技術としては、出力ベース符号化、MUSTANG [3]、NOVA [4]などがある。

モチベーション

低消費電力のための状態符号化設計における主要な考え方は、最も起こりやすい状態遷移のハミング距離を最小化し、スイッチング動作を削減することです。したがって、消費電力を最小化するためのコストモデルは、最小重み付きハミング距離（MWHD）を持つことになります。[1] [2]

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

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

テクニック

低電力状態割り当てのための列ベースのアプローチ

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

マルチコード状態割り当て

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

プロファイリングベースの状態割り当て

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

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

その他の技術

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

参照

参考文献

  1. ^ ab M. PedramとA Abdollahi、「低消費電力RTレベル合成テクニック：チュートリアル」
  2. ^ ab Devadas & Malik、「低消費電力VLSI回路を対象とした最適化手法の調査」、DAC 32、1995年、242～247ページ
  3. ^ S. Devadas他「MUSTANG: 多段ロジック実装をターゲットとした有限ステートマシンの状態割り当て」IEEE Trans. Computer-Aided Design, Vol. CAD-7, No. 12, 1988年12月, pp.129@1300
  4. ^ T. Villa, AS Vincentell, “NOVA: 最適な2レベルロジック実装のための有限ステートマシンの状態割り当て,” IEEE トランザクションズ CAD. VOL. 9 NO. 9. 1990年9月, pp. 905-924
  5. ^ L. BeniniとG. De Micheli、「低消費電力のための状態割り当て」、IEEE J. Solid-State Circuits、第30巻、第3号、1995年、258～268頁
  6. ^ X. Wu、M. Pedram、およびL. Wang、「低電力設計のためのマルチコード状態割り当て」、IEEE Proceedings-Circuits、Devices and Systems、Vol. 147、No. 5、pp. 271–275、2000年10月。
  7. ^ 「マルチメディアコンピューティング」(PDF) . mmc.tudelft.nl . 2024年12月17日閲覧。
  8. ^ K Roy、S Prasad. SYCLOP: 低消費電力アプリケーション向けCMOSロジックの合成. 国際コンピュータ設計会議論文集: コンピュータとプロセッサにおけるVLSI, 464–467ページ, 1992年10月
  9. ^ CY Tsui、M Pedram、CA Chen、AM Despain. 2レベルおよび多レベルロジック実装をターゲットとした低消費電力状態割り当て。国際コンピュータ支援設計会議論文集、82～87ページ、1994年11月。
  10. ^ GD Hachtel, M Hermida, A Pardo, M Poncino, F Somenzi. 電力消費を削減するための順序回路の再エンコード. 国際コンピュータ支援設計会議論文集, 70–73ページ, 1994年11月
  11. ^ W. Noth、R. Kolla「低消費電力のためのスパニングツリーベースの状態符号化」、DATE紀要、pp. 168、1999年3月
  12. ^ abcd "アーカイブコピー" (PDF) . home.deib.polimi.it . 2017年8月28日時点のオリジナル(PDF)からアーカイブ。 2022年1月15日閲覧。{{cite web}}: CS1 maint: アーカイブされたコピーをタイトルとして (リンク)
  13. ^ JC MonteiroとAL Oliveira、「低消費電力設計への暗黙的FSM分解の適用」、IEEE Trans. VLSI Syst.、vol.10、no.5、pp.560-565、2002
  14. ^ SH Chow、YC Ho、T. Hwang、CL Liu、「有限ステートマシンの低電力実現 - 分解アプローチ」、ACM Trans. Design Automat. Elect. Syst.、vol.1、no.3、pp.315-340、1996年7月。
「https://en.wikipedia.org/w/index.php?title=State_encoding_for_low_power&oldid=1313061980」より取得