7

私が書いている C++ の CPU バウンド シミュレーションでは、プログラム内の valgrind を介してボトルネックを追跡しましたcmath::exp。現在、シミュレーション時間の 40% 以上を消費しています。入力を比較的小さな領域に限定することはできますが、精度を制御したいと考えています。LUT（ルックアップテーブル）に移行して置き換えることを検討してexpいましたが、これを「正しい方法」（tm）で行う方法がよくわかりません。私が持っている懸念：

  1. 大きなルックアップ テーブルはキャッシュに収まらないため、アクセスが遅くなります
  2. ルックアップ テーブルにアクセスするために倍精度入力を整数に変換する最良の方法
  3. (2)の答えは入力関数の傾きに依存しますか?
  4. 車輪の再発明ですか - これは以前に行われたことがありますか?

のLUTを実装/(ライブラリからインクルード)する最良の方法は何expですか?

4

3 に答える 3

1

  1. 最適なルックアップ テーブルのサイズは、パフォーマンス、精度、および実装の複雑さの間のトレードオフによって決まります。プロフィールを作成する必要があります。答えはわかりません (答えはわかりません)。

  2. lrintfromを使用し<math.h>て に変換doubleしlong intます。にあるかどうかはわかりません<cmath>。

  3. 浮動小数点数を整数に変換する際にどのような勾配が関係しているのかわかりません。気になるところを詳しく教えていただけますか？

  4. はい、車輪の再発明です。あなたがしていることは、数学ライブラリを実装したことがある人なら誰でも何度も何度も行っています。このテーマに関する文献はたくさんあります。

単純なルックアップ テーブルは最適とは言えません。ある種の多項式近似、おそらくルックアップ テーブルから選択された係数を使用した区分的な近似を使用する必要があります。のように滑らかで予測可能な関数の場合exp、多項式を使用すると、同じ量の計算量ではるかに高い精度が得られます。必要な多項式は、複雑さと精度の間のトレードオフ、および予想誤差を最小化するか、最大誤差を最小化するか、または他の損失関数を使用するかによって異なります。

のドメインを制限してexpも、ドメイン全体に簡単に拡張できるため、実際にはそれほど役に立ちません。

// only works for x in [0, 1]
double exp2_limited(double x);

// works for all x, but doesn't handle overflow properly
double exp2(double x)
{
    return scalbn(exp2_limited(fmod(x, 1.0)), (long) floor(x));
}

概要：

  • このような関数を設計する前に、必要な精度を知る必要があります。

  • また、損失関数を知る必要があります (つまり、損失関数を選択します)。

  • 速度を知る前にプロファイルを作成する必要があります。

  • 多項式を使用します。

于 2012-07-25T21:09:23.830 に答える
1

私はこの問題を抱えていて、それを診断するためにいくつかのスタックサンプルを取りました. それが行うことは、呼び出しがどこから来ているか、引数の値が何であるかを伝えることです。expが特定の場所から呼び出された場合、引数の値は非常に再現性が高いことがわかりました。

これはメモ化アプローチを示唆しており、大きな違いをもたらしました。

シンプルな「ラッパー」関数が必要でした。

double exp_cached(double arg, double* old_arg, double* old_result){
  if (arg== *old_arg) return *old_result;
  *old_arg = arg;
  *old_result = exp(arg);
  return *old_result;
}

exp(foo)呼び出されていた場所では、次のようにします。

static double old_arg = -999999999, old_result;
...
... exp_cached(foo, &old_arg, &old_result)...

そうexpすれば、呼び出された場所の引数が以前と同じ引数値を持つ場合、呼び出されません。

于 2012-07-26T12:01:47.710 に答える
0

非常によく似た質問が以前に尋ねられました。これが私の答えです：

このアプローチはその質問の著者によって提案されたもので、効率的に実装することができました (小さなルックアップ テーブルとルックアップ後の最小限の余分な作業)。これは C# ですが、C++ への変換は簡単です。問題が発生した場合は、私がお手伝いします。

于 2012-07-25T21:14:00.993 に答える