1

私はこのCコードを持っています:

for (k = 0; k < n_n; k++) {
    if (k == i || k == j) continue;
    dd=q2_vect[k]-q1_vect;
    d2=dd*dd;
    if (d2<0) {
        a=1;
        break;
    }       
}

コンパイラの最適化の理由から (Cell プロセッサの SPE で)、これを手動でループ解除する必要があるため、次のことを試しました。

dd=q2_vect[0]-q1_vect;
d2=dd*dd;
if (d2<0)goto done;

dd=q2_vect[1]-q1_vect;
d2=dd*dd;
if (d2<0)goto done;

dd=q2_vect[2]-q1_vect;
d2=dd*dd;
if (d2<0)goto done;

.....
.....

// end
goto notdone;

done: 
ok=0;

notdone:
.....

しかし、私はに対処する方法がわかりません

if (k == i || k == j) continue;

また、lopp は "n_n" の各実行に依存するため、手動で最大値 "n_n" が得られる回数だけコードを記述する必要があります。

どのように修正できると思いますか？

4

6 に答える 6

3

書かれているコードは正しいですか？現在のコードは、 が符号付き整数型である場合の動作が未定義であり、が符号なしの場合、またはおよびが浮動小数点型ddである場合、 if の条件が決して満たされない。式の二乗がオーバーフローする以外の最初のインデックスの壊れた検索を行っているようです。d2ddd2kijq2_vect[ k]-q1_vect

iとの反復を効率的にスキップするためにj、代わりに展開された「ループ」がどこで停止したかを確認し、 がorに等しいk+1場合に再開します。これは、ループ内のコードに副作用/実行中の合計がないことを前提としていますが、これは書かれているとおりですが、コードが他のことをすることを意図していた可能性があります (二乗の合計など)。kij

最後に、最初からコードが機能していないように見えるのに、ループを手動でアンロールしたいというあなたの希望には、私は非常に懐疑的です。優れたコンパイラであればループを展開できますが、実行しようとしているループ展開のタイプによっては、パフォーマンスが向上するどころか悪化することがよくあります。最初にコードが正しく動作するようにしてから、測定 (およびコンパイラによって生成された asm を確認) し、問題があると判断した後でのみ、それを改善しようとする方がよいと思います。

于 2010-11-28T18:20:59.077 に答える
1

このコードは分岐が非常に多いため、SPE にはまったく適していません。また、関連する変数の型に関する情報も役立ちます。書かれているテストは (修正されていても) かなりあいまいに見えますが、コードは、オーバーロードしてベクトル減算を意味し、2 つのベクトルを使用して内積を計算する>0ある種のベクトル クラスを使用する C++ のように見えます。operator -operator *

SPE でこのような単純なループを処理する最初のことは、それらを分岐なしにすることです (少なくとも内側のループ。つまり、数回アンロールし、N 回の反復ごとに早期終了のみをチェックします)。SIMD 命令を使用します。SPEには SIMD のみがあります。命令なので、ループで SIMD 処理を使用しないと、利用可能なレジスタ空間と計算能力の 75% が即座に無駄になります。同様に、SPE は一度にアラインされた qword (16 バイト) しかロードできません。より小さいデータ型を使用すると、レジスタの内容をシャッフルして、ロードしようとしている値が「優先スロット」に収まるように余分な作業が必要になります。

次の分岐のない形式を使用してループの最初の部分を書き直すことで、 を取り除きますif (k == i || k == j)(これは疑似コードです。int にはすぐに適用できますが、浮動小数点でビット演算を取得するには組み込み関数を使用する必要があります)。

dd = q2_vect[k] - q1_vect;
d2 = dd * dd;
d2 &= ~(cmp_equal(k, i) | cmp_equal(k, j));

ここでcmp_equalは、それぞれの SPE 組み込み関数 (セマンティクス: cmp_equal(a,b) == (a == b) ? ~0u : 0) に対応します。これは、またはの場合に強制的d2にゼロにします。k == ik == j

if (d2 > 0)内側のループでの分岐を回避するには、次の手順を実行します。

a |= cmp_greater(d2, 0);

a数回のループ反復ごとにゼロ以外 (アーリーアウト)かどうかのみを確認します。計算されたすべての値d2が負でない場合 (型が int、float、または実数値のベクトル クラスの場合)、これをさらに単純化できます。ただ行う：

a |= d2;

最終a的に、個々の項のすべてが非ゼロである場合にのみ非ゼロになります。ただし、整数オーバーフロー (int を使用している場合) と NaN (float を使用している場合) には注意してください。これらのケースを処理する必要がある場合、上記の単純化によりコードが壊れます。

于 2010-11-29T00:54:12.610 に答える
0

このループを展開しても、ここではあまり役に立ちません。内部ループ ソフトウェア アンローリングは、命令のソフトウェア パイプライン処理を支援し、実行時の IPC を向上させます。ここでは、展開によってロジックが破損する可能性があります。

于 2011-04-19T23:25:32.093 に答える
0

最初の問題については、条件が満たされたときにループ本体を「実行」する必要はありません。この特定の問題については、その条件の論理否定をifステートメントの条件内に配置するだけです。

通常、アンロールは係数によって行われます。展開されたコードはまだループ内に存在します (ループ境界が非常に小さいことがわかっている場合を除く)。さらに、作業の「残り」(問題サイズの残りをアンロール係数で割った値に相当) をループの外で実行する必要があります。

ループ展開の例:

for (i = 0; i < n; ++i) do_something(i);

次のように 2 倍に展開できます。

for (i = 0; i < n-1; i += 2) { do_something(i); do_something(i+1); }
for (; i < n; ++i) do_something(i);

ここで、2 番目のループは「残り」を行います (これもi展開されたループと同じように設定されますが、iこの後に が必要ない場合は、行全体if (i < n) etcをこのケースに使用できます)。

于 2010-11-28T18:19:13.243 に答える
0

n_n がコンパイル時の定数であると仮定すると、ループは次のように簡単に展開できます。

do
{ 
  k=0
  if (k == i || k == j) 
    ;
  else
  {
    dd=q2_vect[ k]-q1_vect;
    d2=dd*dd;
    if (d2<0)
    {
      a=1;
      break;
    }
  }

  k=1
  if (k == i || k == j) 
    ;
  else
  {
    dd=q2_vect[ k]-q1_vect;
    d2=dd*dd;
    if (d2<0)
    {
      a=1;
      break;
    }
  }

  /* and so on, n_n times */

  k= n_n-1
  if (k == i || k == j) 
    ;
  else
  {
    dd=q2_vect[ k]-q1_vect;
    d2=dd*dd;
    if (d2<0)
    {
      a=1;
      break;
    }
  }

} while (0);

基本的に、continue の後のすべてがelseif ステートメントの部分に入ります。

編集:n_nはコンパイル時の定数ではないため、ループ内のループを数回実行してループを展開し、switch-case ステートメントで終了することができます。実際、このように組み合わせることができます。これをダフのデバイスと呼びます。

#define LOOP_BODY              \
do{                            \  
  if (k == i || k == j)        \
    ;                          \
  else                         \
  {                            \
    dd=q2_vect[ k]-q1_vect;    \
    d2=dd*dd;                  \
    if (d2<0)                  \
    {                          \
      a=1;                     \
      break;                   \
    }                          \
  } while (0)          


k = 0;
switch(n_n % 8)
{
  case 0: for (; k < n_n; k++) { LOOP_BODY; k++; 
  case 7:                        LOOP_BODY; k++;
  case 6:                        LOOP_BODY; k++;
  case 5:                        LOOP_BODY; k++;
  case 4:                        LOOP_BODY; k++;
  case 3:                        LOOP_BODY; k++;
  case 2:                        LOOP_BODY; k++;    
  case 1:                        LOOP_BODY; k++;}
}
于 2010-11-28T18:21:28.583 に答える
0

通常、ループ展開とは、実行回数が少なくなるように、ループにいくつかの反復を含めることを意味します。例えば、

for(i=0;i<count;i++) {
    printf("%d", i);
}

に展開できます

i=0;
if(count%2==1) {
    printf("%d", i);
    i=1;
}
while(i<count) {
    printf("%d", i);
    printf("%d", i+1);
    i+=2;
}
于 2010-11-28T18:22:06.073 に答える