Main Content

速度、誤差、およびメモリの使用量に与える間隔の影響

ブレークポイント間隔のタイプを比較するための条件

以下の節では、不等間隔、等間隔、および 2 のべき乗間隔のブレークポイントを使用するルックアップ テーブルの実装を比較します。比較では次の点に注目します。

  • コマンドの実行速度

  • 内挿時の丸め誤差

  • データの読み取り専用メモリ (ROM) の使用量

  • コマンドの ROM の使用量

この比較は、ブレークポイントが調整できない場合にのみ有効です。ブレークポイントが生成コードで調整可能な場合、3 つの事例すべてで同じコードが生成されます。実行速度、誤差、およびメモリの使用量に間隔が与える影響のまとめについては、ブレークポイントの間隔の影響のまとめを参照してください。

ブレークポイントの間隔の影響を説明するモデル

この比較では fxpdemo_approx モデルを使用します。このモデルでは 3 つの固定小数点ルックアップ テーブルが表示されます。3 つのテーブルはすべて第一象限で関数 sin(2*pi*u) を近似し、最悪誤差を 2^-8 以下にします。ただし、ブレークポイントの間隔に関する制限は異なります。

fxpdemo_approx モデルを使用して Simulink® Coder™ コードを生成できます (Simulink Coder のソフトウェア ライセンスが必要)。以下の節では、生成コードのいくつかのセグメントを示し、重要な違いに重点を置いて説明します。

モデルを開くには、MATLAB® プロンプトで以下のように入力します。

openExample('fixedpoint/FixedPointFunctionApproximationExample')

各ルックアップ テーブルに必要なデータ ROM

この節では 3 つの間隔オプションのそれぞれで必要なデータ ROM を調べます。

不等間隔の場合

不等間隔では Y データ点とブレークポイントの両方が必要です。

int16_T  yuneven[8];
uint16_T xuneven[8];

総使用量は 32 バイトです。

等間隔の場合

等間隔では Y データ点のみが必要です。

int16_T yeven[10];

総使用量は 20 バイトです。ブレークポイントは明示的に要求されません。コードは、ブレークポイント間の間隔を使用し、最小ブレークポイントと最大ブレークポイントを使用する可能性があります。最大で、ブレークポイントに関連する 3 つの値が必要です。

2 のべき乗の場合

2 のべき乗では Y データ点のみが必要です。

int16_T ypow2[17];

総使用量は 34 バイトです。ブレークポイントは明示的に要求されません。コードは、ブレークポイント間の間隔を使用し、最小ブレークポイントと最大ブレークポイントを使用する可能性があります。最大で、ブレークポイントに関連する 3 つの値が必要です。

範囲外入力の判定

いずれの場合も、入力値が最小ブレークポイントよりも小さくなったり最大ブレークポイントよりも大きくならないようにしなければなりません。値が小さくなったり大きくなった場合の処理方法は異なります。ただし、通常、その違いはわずかであるため、別の間隔手法の使用を決める重要な要因にはなりません。以下の節では、範囲外の入力が不可能または処理済であると仮定しています。

ルックアップ テーブルの入力位置を決める方法

この節では、3 つのルックアップ テーブルで現在の入力がブレークポイントの位置にどのように関連付けられるかについて説明します。

不等間隔の場合

不等間隔のブレークポイントでは、ブレークポイントと入力の位置を関連付けるために、二分探索法のような汎用アルゴリズムが必要です。コードの例を以下に示します。

iLeft = 0;
iRght = 7; /* number of breakpoints minus 1 */

while ( ( iRght - iLeft ) > 1 )
{
  i = ( iLeft + iRght ) >> 1;

if ( uAngle < xuneven[i] )
  {
    iRght = i;
  }
  else
  {
    iLeft = i;
  }
}

while ループは最大 log2(N) 回実行されます。ここで、N はブレークポイント数です。

等間隔の場合

等間隔のブレークポイントでは、1 つの手順だけでブレークポイントと入力の位置を関連付けることができます。

iLeft = uAngle / 455U;

除数 455U はブレークポイント間の間隔を示します。通常、被除数は (uAngle - SmallestBreakPoint) です。この例では、最も小さいブレークポイントはゼロなので、コードは減算を最適化します。

2 のべき乗の場合

2 のべき乗のブレークポイントでは、1 つの手順だけでブレークポイントと入力の位置を関連付けることができます。

iLeft = uAngle >> 8;

ブレークポイントの間隔は 2^8 なので、シフト数は 8 です。最も小さいブレークポイントはゼロなので、uAngle(uAngle - SmallestBreakPoint) の一般的な事例で置き換えられます。

比較

ブレークポイントと入力の位置を関連付けるために、不等間隔の場合、他の 2 つのケースよりも多くのコードが必要なります。このコードは追加のコマンド ROM が必要です。多くのルックアップ テーブルが関数として二分探索アルゴリズムを共有する場合、この ROM ペナルティを減らすことができます。コードが共有された場合でも、入力の位置を決めるために必要なクロック サイクル数は、不等間隔の場合他の 2 つの場合よりも多くなります。コードが共有された場合、関数呼び出しのオーバーヘッドにより実行速度がまた少し遅くなります。

等間隔と 2 のべき乗間隔の場合、入力の位置を 1 行のコードで指定できます。等間隔の場合は一般的な整数の除算を使用します。2 のべき乗の場合は、除数が正確な2 のべき乗なので、一般的な除算の代わりにシフトを使用します。固有のプロセッサが認識されない場合、シフトの方が除算より適していると断定することはできません。

多くのプロセッサは 1 つのアセンブリ言語命令を使用して除算を実装できるため、コードは小さくなります。ただし、この命令は完了するまで多くのクロック サイクルが必要です。多くのプロセッサでは除算命令が提供されません。これらのプロセッサでは除算は減算を繰り返して行われます。このプロセスは速度が遅く多くのマシン コードが必要ですが、コードを共有できます。

ほとんどのプロセッサには論理シフトと算術シフトを左右に実行する方法があります。重要な違いは、プロセッサが 1 つの命令で N シフト (バレル シフト) を実行できる、または N 命令で 1 ビットずつシフトする必要があるかどうかということです。バレル シフトでは必要なコードが少なくなります。バレル シフトが速度も向上させるかどうかは、動作をサポートするハードウェアによって異なります。

コンパイラが比較を複雑にすることもあります。前の例では、uAngle >> 8 コマンドは基本的に 16 ビットのワードのうち上位 8 ビットを取得します。コンパイラはこの状況を検出し、ビット シフトをビットを直接取得する命令に置き換えます。シフト数がこれ以外の 7 のような値の場合、この最適化は行われません。

各ルックアップ テーブルの内挿

理論上、次のコードを使用して内挿を計算できます。

y = ( yData[iRght] - yData[iLeft] ) * ( u - xData[iLeft] ) ...
    / ( xData[iRght] - xData[iLeft] ) + yData[iLeft]

(xData[iRght] - xData[iLeft]) の項は隣接するブレークポイント間の間隔です。等間隔のためにこの値が定数であれば、単純化が可能です。間隔が等しいだけでなく 2 のべき乗であれば、大幅に単純化して固定小数点を実装できます。

不等間隔の場合

不等間隔の場合、固定小数点に理想的な内挿の実装を可能にする方法が 1 つあります。

xNum  = uAngle         - xuneven[iLeft];
xDen  = xuneven[iRght] - xuneven[iLeft];
yDiff = yuneven[iRght] - yuneven[iLeft];

MUL_S32_S16_U16( bigProd, yDiff, xNum ); 

  DIV_NZP_S16_S32_U16_FLOOR( yDiff, bigProd, xDen );

  yUneven = yuneven[iLeft] + yDiff;

乗算と除算のルーチンは図には示されていません。これらのルーチンは複雑でターゲット プロセッサによって異なります。たとえば、これらのルーチンは 32 ビット プロセッサよりも 16 ビット プロセッサで異なって見えます。

等間隔の場合

不等間隔のブレークポイントでは、等間隔の場合とは少し異なる計算を使用して内挿を実装します。大きな違いは、計算では直接ブレークポイントを使用しない点です。ROM でブレークポイントが必要とされない場合、多くのメモリを節約できます。

xNum  = uAngle - ( iLeft * 455U );

  yDiff = yeven[iLeft+1] - yeven[iLeft];

  MUL_S32_S16_U16( bigProd, yDiff, xNum ); 

  DIV_NZP_S16_S32_U16_FLOOR( yDiff, bigProd, 455U );

  yEven = yeven[iLeft] + yDiff;

2 のべき乗の場合

2 のべき乗間隔のブレークポイントでは、他の 2 つの場合とは大きく異なる計算を使用して内挿を実装します。等間隔の場合と同様、ブレークポイントは生成コードで使用されないため、ROM では不要です。

lambda = uAngle & 0x00FFU;

  yPow2 = ypow2[iLeft)+1] - ypow2[iLeft];

  MUL_S16_U16_S16_SR8(yPow2,lambda,yPow2);

  yPow2 += ypow2[iLeft];

この実装は不等間隔と等間隔の実装に比べて大きな利点があります。

  • 乗算の最後で右シフトを組み合わせたビット単位の論理積 (AND) は減算と除算に置き換えられます。

  • (u - xData[iLeft] ) / ( xData[iRght] - xData[iLeft]) 項の結果は、間隔が 2 のべき乗なので精度は低下しません。

    対照的に、不等間隔と等間隔の場合には通常この計算で丸め誤差が発生します。

ブレークポイントの間隔の影響のまとめ

次の表は、実行速度、誤差、およびメモリの使用量にブレークポイントの間隔が与える影響をまとめています。

パラメーター

2 のべき乗の等間隔データ

等間隔のデータ

不等間隔のデータ

実行速度

実行速度は最速です。位置検索と内挿は等間隔データの場合と同じです。ただし、速度を上げるために、ビット シフトが位置検索に、ビット マスクが内挿に置き換えられます。

実行速度は、位置検索が高速で内挿にはシンプルな除算が必要なため、不等間隔データの場合よりも速くなります。

実行速度は、位置検索が遅く内挿には多くの演算が必要なため、最も遅くなります。

エラー

一様でない曲率を使用する関数の近似には同じ精度を実現するために多くの点が必要になるので、不等間隔データの場合よりも誤差は大きくなります。

一様でない曲率を使用する関数の近似には同じ精度を実現するために多くの点が必要になるので、不等間隔データの場合よりも誤差は大きくなります。

一様でない曲率を使用する関数の近似には同じ精度を実現するため少ない点で済むので、誤差は小さくなります。

ROM の使用量

コマンドの ROM 使用量は減りますが、データの ROM 使用量は増えます。

コマンドの ROM 使用量は減りますが、データの ROM 使用量は増えます。

コマンドの ROM 使用量は増えますが、データの ROM 使用量は減ります。

RAM の使用量

わずかです。

わずかです。

わずかです。

Y データ点の数は予想されるパターンを踏襲します。同じ最悪誤差の場合、制限のない間隔 (不等間隔) では必要なデータ点は少なくなり、2 のべき乗間隔のブレークポイントで最も多くなります。ただし、等間隔と 2 のべき乗の場合の実装では生成コードのブレークポイントは不要です。このためデータに必要な ROM の使用量は半減します。結果として、等間隔の場合は不等間隔の場合よりもデータの実際の ROM 使用量は少なくなります。また、2 のべき乗の場合は不等間隔の場合よりも ROM の使用量がわずかに増えます。最悪誤差を変えると、これらのランクも変わります。それにもかかわらず、データの ROM 使用量を比較する場合、等間隔と 2 のべき乗間隔では ROM のブレークポイントが不要になるという事実を考慮する必要があります。

現在の入力はどのブレークポイントを基準にしているかを調べると、等間隔と 2 のべき乗間隔のどちらが有利かがわかります。不等間隔では、最大 log2(N) 回ループする二分探索法を使用します。等間隔と 2 のべき乗間隔では、1 行の C コードを実行して位置を特定できます。しかし、ハードウェアと C コンパイラの詳細がわからないときに 2 のべき乗間隔に対する等間隔の相対的な利点を特定することはできません。

内挿の計算は、ビット単位の論理積 (AND) とシフトを使用して減算と除算に置き換えられるため、2 のべき乗が有利になります。この動作の利点は固有のハードウェアに依存しますが、コード サイズ、速度、および精度の利点も期待できます。等間隔の場合は、不等間隔の場合に比べて内挿の計算は効率が低下します。