4

lenタイプの要素の配列が与えられると、配列signed short内の最大絶対値要素に設定された最上位ビットの位置を見つけることになります。たとえば、配列 L が含まれている場合は{-134, 123, 0, -890}、f(L)を返す必要がありfloor(log2(abs(-890)))+1ます。

これが私の現在の機能です：

short MSBSetMaxMagnitude(const short *p, int len)
{
   unsigned int t = 0;

   while (len > 0)
   {
      t |= abs(*p);
      p++;
      len--;
   }
   if(t)
      return (short)(32 - __builtin_clz(t));
   else
      return 0;
}

ただし、 abs() 関数が分岐を必要とするため、少し遅くなります。代わりに分岐せずに abs() を使用しようとしましたが、少なくとも 3 つの算術命令が含まれているため、さらに遅くなります。ですから、必要なものを正確に見つけるための効率的なアルゴリズムがあることを願っています。

4

2 に答える 2

1

ARM プラットフォームで作業していることを確認すると、次のabsin 2 命令の実装を使用できます。

EORS r1, r1, r1, ASR #32 (x = x ^ (x >> 32); carry_flag = sign_bit)
ADC r1, r1, #0           (add the sign_bit to x)

計算で +/-1 のエラーを許容できる場合は、2 番目の命令を削除します。次に、Cで表現できます：

int abs_almost_exact(int x)
{
    return x ^ (x >> 32);
}

しかし、より大きな問題はループです。おそらくアンロールから多くの恩恵を受けるでしょう (各反復で行うことはほとんどないため):

do { // assuming len is even!
    int value1 = *p++;
    int value2 = *p++;
    value1 = abs(value1); // or replace abs by the hand-made version
    value2 = abs(value2);
    t |= value1;
    t |= value2;
    len--;
}
while (len > 0);

注：使用したコンパイラ（ARMコンパイラ）がこの方法でより良いコードを生成するため、while {}置き換えました。do {} while

shortまた、メモリから変数をロードするとき（私が使用したプロセッサ上）、ARMには2クロックサイクルのレイテンシがあることに注意してください。したがって、最小展開係数は 3 です (ただし、とにかく可能な限り展開する必要があります)。

ああ、あなたのプロセッサshortはメモリからの (ハーフワード) 変数の読み取りをサポートしていますか? それができない非常に古いプロセッサがあると聞いたことがあります。このような場合は、一度に 2 つの値 (1 ワード) をロードするようにコードを変更し、ビットをいじってそれらを分離する必要があります。

于 2012-11-22T18:12:50.003 に答える
0

3 つの算術命令は、最新のプロセッサではほとんど時間がかからないはずです。ループとインデックス作成を管理する際に、2 つの算術演算と条件分岐を実行しています。速度の低下は、データ キャッシュ ミスと、ポインターの使用とポインター演算のためにコンパイラーがアンロールするのが困難なループの組み合わせが原因である可能性があります。

配列内のすべての要素を調べずに、配列内のすべての要素に依存する値を見つける方法はないため、目的は、配列をスキャンするのにかかる時間内にすべてが実行されるようにすることです。

以下を置き換えることで、これが問題かどうかをテストできます。

t |= abs(*p);

t |= *p;

それが大幅に速くない場合は、手動で展開されたループで非分岐 abs バージョンを試すことをお勧めします。

于 2012-11-22T17:31:43.543 に答える