C/C++アルゴリズム設計における任意のビット幅の使用

固定小数点アルゴリズムを開発する場合、設計機能、数値的に正確なモデリング、検証 (シミュレーション) 速度の間でバランスを取る必要があることがよくあります。現在、新しいデータクラスによってこのプロセスが簡素化され、モデリングの精度がよりシンプルで正確になり、数値の改良が向上し、検証サイクルが高速化されます。ANSI C/C++ は、このような数値改良アルゴリズムの開発に最適な言語です。

一部のアルゴリズムは、整数、または理想的には実数 (デジタルフィルターの係数など) を操作するのに自然に適しており、浮動小数点型または固定小数点型を使用することもできます。一般的に、アルゴリズム開発の初期段階では、C 言語の float 型または double 型浮動小数点型がよく使用されます。これは、これらの型が非常に大きな動的データ範囲を提供し、ほとんどのプログラムに適しているためです。

Cの組み込みfloat型を使用してFIRフィルタをモデル化する

アルゴリズムを数値的に改良して固定小数点演算を使用することで、最終的なハードウェアまたはソフトウェア実装の複雑さを軽減できます。ハードウェア側では、整数演算または固定小数点演算を最小ビット幅に制限することで、パフォーマンス、スペース、および電力の要件を本質的に満たすことができます。実装に DSP プロセッサを使用する場合、アルゴリズムを整数演算または固定小数点演算に制限すると、特定のプログラムに可能な限り安価なプロセッサを使用できるようになります。

固定小数点演算のモデル化は、C の組み込み浮動小数点型または整数型を使用して行うことができますが、明示的なエンコードが必要であり、C で表現できる最大の数値 (64 ビット整数または 53 ビット仮数) に制限されます。これにより、オペランドのビット幅にさらなる制限が課せられるため、たとえば、2 つの 33 ビット数値を乗算すると、64 ビット C 整数で表現できる範囲を超えてしまいます。図 2 は FIR フィルターの例を示していますが、temp 変数は固定小数点精度の 15 ビットに制限されており、そのうち 10 ビットが整数ビットとして使用されます。この実装では、LSB の右側のビットは破棄され (量子化モデルの切り捨て)、MSB の左側のビットも破棄されます (パッキングオーバーフローモデル)。float (または double) を使用するモデルは精度が制限されており、再度合成できないことに注意してください。同様に、丸めモデルの厳密なビット精度の定義と、組み込みの浮動小数点型の丸めが最初に適用されるため、除算などの演算を実装するのは非常に困難です。

float を使用した固定小数点の動作のモデリング

多くのアルゴリズムがネイティブ C データ型の精度に依存して記述できるようになったため、任意長の整数と固定小数点演算のサポートに大きな期待が寄せられ、VHDL などのハードウェア記述言語 (HDL) も同じ道をたどりました。 C/C++ が高レベル合成および検証ツールでますます使用されるようになるにつれて、この言語には本質的に、現在のプログラムおよび将来のプログラムのニーズを満たすのに十分なデータ型ライブラリがあることが証明されています。任意の長さの型のサポートにより、データ型の動作の統一された定義も可能になり、統一されたセマンティクスにより手動実装の制限がいくつか回避されます。

アルゴリズム C データ型

アルゴリズム C データ型は、任意の長さの整数型と固定小数点型を実装するクラスベースの C++ ライブラリです。これらの自由にアクセスできる型には、統一された明確に定義されたセマンティクス、C/C++ 組み込みデータ型に匹敵する実行速度、SystemC の対応する型よりも 10 倍以上高速な実行速度など、多くの利点があります。これらのデータ型は、C++ または SystemC 仕様に準拠し、高度に合成可能なセマンティクスを持つ任意のプログラムで使用できます。

セマンティクス

意味の統一性と一貫性は、アルゴリズムの機能エラーを回避するための鍵となります。次の例はこの点を示しています。

ご存知のとおり、変数 ActLength の範囲は 1 ～ 255 です。コンパイラの合成でその範囲がわからない場合、対応する最適化を実行できず、その宣言は int からより厳密な sc_uint<8> 型に変更されます。合成ではより良い結果が得られますが、設計は正しくシミュレーションされません。デバッグを行った結果、問題の原因が判明しました。比較式 k >= ActLength では、2 つのオペランドが signed int と unsigned long long (sc_uint 型の基本型である 64 ビットの符号なし整数) の比較になっていました。この理由としては、C/C++ の整数昇格ルールでは、比較の前にオペランド int が unsigned long long に昇格されることが規定されているためです。たとえば、k の値が -1 の場合、unsigned long long に昇格された後、2^64 - 1 になります。

このようなセマンティクスの問題は通常は非常に微妙で、ビット幅に関連しています。たとえば、既存のアルゴリズムのビット幅を増やしたいが、結果を見てうまくいかないことに気づく場合があります。問題はプラットフォーム固有のものである可能性もあります。たとえば、1 << 32 (両方のオペランドが int 型で、結果も int 型) は 0 を返すと予想されますが、ほとんどのプラットフォーム (またはコンパイラ) では 1 が返されます (シフトは行われず、2 番目のオペランドの下位 5 ビットがカウントされるだけです)。最初のオペランドが 64 ビット整数の場合、プラットフォームの依存関係はより明白かつ頻繁に発生します。主な問題は、C/C++ 標準では、シフト値 (2 番目のオペランド) が 32 ビット整数の場合は 0 ～ 31 の範囲外、64 ビット整数の場合は 0 ～ 63 の範囲外の場合の動作が指定されていないことです。残念ながら、sc_int や sc_uint などのデータ型では、このようなプラットフォーム依存性の問題からユーザーを保護することはできません。

アルゴリズム C データ型は、均一で一貫したセマンティクスを提供するように設計されているため、予測可能です。たとえば、符号なしのオペランドと符号付きの数値を混在させても、期待どおりの結果が生成されます。これらの型の長さは無制限であるため、いわゆる精度の問題はありません。シフトや除算を含むすべての演算は完全に一貫して定義されており、異なる型を混在させても期待どおりの結果が生成されます。たとえば、x が C 組み込み型で、y がアルゴリズム C 型の場合、式 x+y と y+x はどちらも同じ結果を返します。

実行時間

私たちの目標は、任意の長さの型をサポートし、前述のセマンティックの問題を回避しながら、組み込み型 (最大 64 ビット幅) を使用して手動で作成された C/C++ コードのランタイムを最適化できるようにすることです。アルゴリズム C 型は、高速実行と簡単に合成できるセマンティクスのために設計および実装されています。すべての操作のビット幅は C++ コンパイラによって静的に決定されるため、動的なメモリ割り当てが回避され、実行時間が短縮され、セマンティクスの合成が容易になります。さらに、実装は速度が最適化されているため、今日のコンパイラの最適化機能を活用して、より特殊で効率的なコードを呼び出すことができます。

表1: ac_fixedに正規化された実行時間の比較

表 1 は、アルゴリズム C 固定小数点型 ac_fixed を使用して固定小数点演算をモデル化した場合のさまざまな実行時間を比較したものです。float の実装は図 2 に示されており、sc_fixed_fast は精度が制限された SystemC 固定小数点データ型であり、sc_fixed は任意精度の固定小数点型です。実際には、FIR フィルタは 10^8 回呼び出され、TRN/WRAP の実行時間は 6.5 秒、RND/SAT の実行時間は 29 秒です。他のタイプの実行時間もこの表から推測できます。たとえば、sc_fixed TRN/WRAP には 6.5 秒 × 227 = 1476 秒 (約 25 分) かかります。参考までに、図 1 のアルゴリズム (固定小数点モデリングなしで float を使用) は 3.5 秒かかります (固定小数点モデリングを使用する ac_fixed のほぼ 2 倍の速度です)。

上記の実行時間データはすべて GCC 4.1.1 で測定されており、以前のバージョンの GCC または Visual C++ 2005 で取得されたデータもほぼ同じです。

さらに、整数データ型またはビット演算を使用することで、実行時間をさらに短縮できます。表 2 は、一度に 2 ビットを読み書きするシフト操作によって書き込まれる DCT アルゴリズムの対応する結果を、SystemC の精度制約付き sc_int および任意の長さの sc_bigint の実行時間と比較したものです。

結論は

ユニバーサル標準 ANSI C++ に基づく新しい整数および固定小数点演算 C 型により、アルゴリズムおよびシステム設計者は任意のビット幅を指定できるようになり、従来のデータ型よりも最大 200 倍のシミュレーション効率が実現します。これらの新しいデータ型は、C から RTL への設計チェーンにおいて非常に貴重なリンクとなり、実装フロー全体を通じて任意のビット幅の精度を保証します。

【編集者のおすすめ】