12

変数 shift op またはブランチを実際に使用せずに、間接的な左/右シフト操作を実行する方法を見つけようとしています。

私が取り組んでいる特定の PowerPC プロセッサには、次のような定数による即時シフトという癖があります。

int ShiftByConstant( int x ) { return x << 3 ; }

高速、単一操作、スーパースカラーであるのに対し、変数によるシフトは次のように

int ShiftByVar( int x, int y ) { return x << y ; }

はマイクロコード化された操作で、実行に 7 ～ 11 サイクルかかり、残りのパイプライン全体が完全に停止します。

私がやりたいのは、sraw がデコードするマイクロコード化されていない整数 PPC ops を特定し、それらを個別に発行することです。これは、それ自体のレイテンシーには役立ちませんsraw— 1 つのオペレーションが 6 つに置き換えられます — しかし、それらの 6 つのオペレーションの間に、一部の作業を他の実行ユニットに二重ディスパッチして、純利益を得ることができます。

μops sraw がデコードしたものをどこにも見つけられないようです — 可変ビットシフトを一連の定数シフトと基本的な整数演算に置き換える方法を知っている人はいますか? (正しく予測された分岐であっても、分岐ペナルティはマイクロコード ペナルティよりもさらに大きいため、for ループ、スイッチ、または分岐を含むものは機能しません。)

これはアセンブリで答える必要はありません。私は特定のコードではなくアルゴリズムを学びたいと思っているので、C言語や高級言語、さらには疑似コードでの回答があれば完全に役に立ちます。

編集：追加する必要があるいくつかの説明：

  1. 携帯性は少しも気になりません

  2. PPC には条件付き移動があるため、分岐のない組み込み関数の存在を想定できます。

    int isel(a, b, c)  { return a >= 0 ? b : c; }

    （同じことを行う三項を書き出すと、あなたの言いたいことがわかります）

  3. 整数乗算もマイクロコード化されており、sraw. :-(
  4. Xenon PPC では、予測される分岐のレイテンシは 8 サイクルであるため、1 つでもマイクロコード化された命令と同じくらいコストがかかります。ポインターへのジャンプ (任意の間接分岐または関数ポインター) は、予測ミス (24 サイクルのストール) が保証されています。
4

8 に答える 8

8

どうぞ...

Mike Acton が、 CellPerformanceサイトで CELL/PS3 マイクロコード化されたシフトを使用するよりも高速であると主張したため、これらも試してみることにしました。ただし、私のすべてのテストでは、マイクロコード化されたバージョンを使用すると、間接シフトの完全な汎用分岐フリー置換よりも高速であるだけでなく、コードに必要なメモリが大幅に少なくなります (1 命令)。

これらをテンプレートとして使用した唯一の理由は、符号付き (通常は算術) シフトと符号なし (論理) シフトの両方で正しい出力を得るためでした。

template <typename T> FORCEINLINE T VariableShiftLeft(T nVal, int nShift)
{   // 31-bit shift capability (Rolls over at 32-bits)
    const int bMask1=-(1&nShift);
    const int bMask2=-(1&(nShift>>1));
    const int bMask3=-(1&(nShift>>2));
    const int bMask4=-(1&(nShift>>3));
    const int bMask5=-(1&(nShift>>4));
    nVal=(nVal&bMask1) + nVal;   //nVal=((nVal<<1)&bMask1) | (nVal&(~bMask1));
    nVal=((nVal<<(1<<1))&bMask2) | (nVal&(~bMask2));
    nVal=((nVal<<(1<<2))&bMask3) | (nVal&(~bMask3));
    nVal=((nVal<<(1<<3))&bMask4) | (nVal&(~bMask4));
    nVal=((nVal<<(1<<4))&bMask5) | (nVal&(~bMask5));
    return(nVal);
}
template <typename T> FORCEINLINE T VariableShiftRight(T nVal, int nShift)
{   // 31-bit shift capability (Rolls over at 32-bits)
    const int bMask1=-(1&nShift);
    const int bMask2=-(1&(nShift>>1));
    const int bMask3=-(1&(nShift>>2));
    const int bMask4=-(1&(nShift>>3));
    const int bMask5=-(1&(nShift>>4));
    nVal=((nVal>>1)&bMask1) | (nVal&(~bMask1));
    nVal=((nVal>>(1<<1))&bMask2) | (nVal&(~bMask2));
    nVal=((nVal>>(1<<2))&bMask3) | (nVal&(~bMask3));
    nVal=((nVal>>(1<<3))&bMask4) | (nVal&(~bMask4));
    nVal=((nVal>>(1<<4))&bMask5) | (nVal&(~bMask5));
    return(nVal);
}

編集: isel() に関する注意 私はあなたのisel() コードをあなたのウェブサイトで見ました。

// if a >= 0, return x, else y
int isel( int a, int x, int y )
{
    int mask = a >> 31; // arithmetic shift right, splat out the sign bit
    // mask is 0xFFFFFFFF if (a < 0) and 0x00 otherwise.
    return x + ((y - x) & mask);
};

FWIW、isel() を書き直してマスクとマスクの補数を行うと、PowerPC ターゲットでより高速になります。これは、コンパイラが「andc」オペコードを生成するほどスマートだからです。オペコードの数は同じですが、オペコードの結果から入力レジスタへの依存関係が 1 つ少なくなっています。2 つのマスク操作は、スーパースカラー プロセッサで並列に発行することもできます。すべてが正しく並んでいれば、2 ～ 3 サイクル速くなる可能性があります。PowerPC バージョンでは、戻り値を次のように変更する必要があります。

return (x & (~mask)) + (y & mask);
于 2009-10-21T21:35:16.593 に答える
5

これはどう：

if (y & 16) x <<= 16;
if (y & 8) x <<= 8;
if (y & 4) x <<= 4;
if (y & 2) x <<= 2;
if (y & 1) x <<= 1;

実行にはおそらくまだ時間がかかりますが、間に他のコードがある場合は簡単にインターリーブできます。

于 2009-02-12T03:19:10.577 に答える
4
于 2009-02-12T04:06:23.350 に答える
1

これは私の頭を壊します。私は今、半ダースのアイデアを破棄しました。それらはすべて、ものをそれ自体に追加すると左に 1 シフトし、結果に同じことをすると左に 4 シフトするという概念を利用しています。左シフト 0、1、2、4、8、および 16 のすべての部分的な結果を保持する場合、シフト変数のビット 0 から 4 をテストすることによって、最初のシフトを取得できます。ここで、シフト変数の 1 ビットごとに 1 回、もう一度実行します。率直に言って、プロセッサーをコーヒーに出す方がいいかもしれません。

私が本当の助けを求める唯一の場所は、Hank Warren のHacker's Delightです (これは、この回答の唯一の有用な部分です)。

于 2009-02-12T03:27:51.087 に答える
0

これはどう：

int[] multiplicands = { 1, 2, 4, 8, 16, 32, ... etc ...};

int ShiftByVar( int x, int y )
{
    //return x << y;
    return x * multiplicands[y];
}
于 2009-02-12T03:33:56.187 に答える
-1

ビット操作の黒魔術に関しては、ここにいくつかの優れたものがあります: 高度なビット操作 fu (Christer Ericson のブログ)

直接適用できるものがあるかどうかはわかりませんが、方法があれば、その方法のヒントがどこかにある可能性があります。

于 2009-02-12T04:27:19.337 に答える
-1

これは自明に展開できないものです：

int result= value;

int shift_accumulator= value;

for (int i= 0; i<5; ++i)
{
    result += shift_accumulator & (-(k & 1)); // replace with isel if appropriate
    shift_accumulator += shift_accumulator;
    k >>= 1;
}
于 2009-08-24T17:34:43.943 に答える