3

nxn行列の逆数を見つけるアルゴリズムを書いています。3x3 行列の特定のケースを考えてみましょう。

手動で行列を反転する場合、通常、1 つ以上のゼロを含む行/列を探して、計算する必要がある項を排除するため、行列式の計算を高速化します。

C/C++ でこのロジックに従って、行/列を 1 つ以上のゼロで識別すると、次のコードになります。

float term1 = currentElement * DetOf2x2(...);
//           ^
//           This is equal to 0.
//
// float term2 = ... and so on.

コンパイラはcurrentElementコンパイル時にゼロになることを認識できないため、次のように最適化することはできずfloat term = 0;、実行時に浮動小数点乗算が実行されます。

私の質問は、これらのゼロ値により浮動小数点乗算が高速になるか、または の値に関係なく乗算に同じ時間がかかるcurrentElementかということです。実行時に乗算を最適化する方法がない場合は、ゼロを含む行/列を検索するロジックを削除できます。

4

5 に答える 5

10

コンパイラは、計算が自明でない限り (たとえば、すべての定数)、これを最適化することはできません。

その理由は、DetOf2x2 が NAN 浮動小数点値を返す可能性があるためです。NAN にゼロを掛けてもゼロは返されませんが、再び NAN が返されます。

ここでこの小さなテストを使用して、自分で試すことができます。

int main (int argc, char **args)
{
  // generate a NAN
  float a = sqrt (-1);

  // Multiply NAN with zero..
  float b = 0*a;

  // this should *not* output zero
  printf ("%f\n", b);
}

コードを最適化したい場合は、自分でゼロをテストする必要があります。コンパイラはそれを行いません。

于 2013-03-05T02:32:41.710 に答える
7 
float term1 = currentElement * DetOf2x2(...);

currentElement が 0 の場合でも、コンパイラは呼び出しますDetOf2x2(...)。これは、0 によるかどうかにかかわらず、最終的な乗算よりもはるかにコストがかかることは確かです。これには複数の理由があります。

  • DetOf2x2(...)の場合でも発生する必要がある副作用 (ログ ファイルへの出力など) がある場合currentElementが0あります。
  • DetOf2x2(...)Not-a-Number / NaN Sentinel のような値を返す場合がありますが、いずれにせよ伝播する必要がありterm1ます (Nils Pipenbrinck が最初に指摘したように)

ほぼ確実DetOf2x2(...)に、実行時にのみ決定できる値に取り組んでおり、後者の可能性はコンパイル時に除外できません。

への呼び出しを避けたい場合は、次Detof2x2(...)を試してください。

float term1 = (currentElement != 0) ? currentElement * DetOf2x2(...) : 0;
于 2013-03-05T02:34:58.453 に答える
3

最新の CPU は、実際にはゼロによる乗算を非常に高速に処理します。一般的な乗算よりも高速であり、分岐よりもはるかに高速です。そのゼロが少なくとも数十の命令を介して伝播しない限り、これを最適化しようとしても気にしないでください。

于 2013-03-05T02:21:16.507 に答える
0

次の構成は、コンパイラが "currentElement" の値を推測できるコンパイル時に有効です。

float term1 = currentElement ? currentElement * DetOf2x2(...) : 0;

コンパイル時に推測できない場合は、実行時にチェックされ、パフォーマンスはプロセッサ アーキテクチャに依存します。分岐間のトレードオフ (分岐レイテンシと、命令パイプラインを再構築するための遅延を含む) は、最大 10 または20 サイクル)、フラット コード (一部のプロセッサはサイクルごとに 3 つの命令を実行)、およびハードウェア分岐予測 (ハードウェアが分岐予測をサポートしている場合)。

乗算のスループットは x86_64 プロセッサでは 1 サイクルに近いため、0.0、1.0、2.0、12345678.99 などのオペランド値によるパフォーマンスの違いはありません。そのような違いが存在する場合、それは暗号化スタイルのソフトウェアの秘密のチャネルとして認識されます。

GCC では、コンパイル時に関数パラメーターをチェックできます

inline float myFn(float currentElement, myMatrix M)

{

#if __builtin_constant_p(currentElement) && currentElement == 0.0

0.0 を返します。

＃そうしないと

return currentElement * det(M);

#endif

}

コンパイラでインライン化とプロシージャ間の最適化を有効にする必要があります。

于 2015-01-06T03:37:23.247 に答える
0

実行時に実行される最適化は、JIT (ジャストインタイム) 最適化として知られています。変換 (コンパイル) 時に実行される最適化は、AOT (事前) 最適化として知られています。JIT最適化について言及しています。コンパイラはマシン コードに JIT 最適化を導入する場合がありますが、一般的な AOT 最適化よりもはるかに複雑な最適化を実装することは確かです。最適化は通常、有意性に基づいて実装されます。この種の「最適化」は、他のアルゴリズムに悪影響を与える可能性があります。C 実装は、これらの最適化を実行する必要はありません。

「ゼロを含む行/列を検索するロジック」、または次のような最適化を手動で提供できます。float term1 = currentElement != 0 ? currentElement * DetOf2x2(...) : 0;

于 2013-03-05T02:32:50.780 に答える