1

私は、Levenverg-Marquardt アルゴリズムを使用して倍精度でフィッティングを行う、非常に複雑で洗練されたデータ フィッティング プログラムを持っています (基本的に、フィッティング クラスはテンプレート化されていますが、インスタンス化して double にします)。フィッティング プロセスには以下が含まれます。

  • 誤差関数 (カイ 2 乗) の計算
  • 線形方程式系を解く (そのためには lapack を使用します)
  • データに適合させたいパラメータに関する関数の導関数の計算 (通常は 20 以上のパラメータ)
  • 関数値を連続的に計算します。関数は、いくつかの高調波を持つ正弦関数と指数関数の複雑な組み合わせです。

私の同僚は、少なくとも 10 倍高速に整数を使用することを提案しました。私の質問は次のとおりです。

  1. そのような改善が得られるというのは本当ですか?
  2. すべてを整数に変換しても安全ですか? そして、これの欠点は何ですか?
  3. この問題全体について、どのようなアドバイスがありますか? あなたならどうしますか?

このプログラムは、信号からオンラインでいくつかのパラメーターを計算するように開発されているため、プログラムはできるだけ高速である必要がありますが、すべてを整数に変換するプロジェクトを開始する価値があるかどうか疑問に思っています。

4

4 に答える 4

6

改善の程度は、プラットフォームによって異なります。たとえば、プラットフォームに高速な浮動小数点コプロセッサがある場合、浮動小数点で演算を実行すると、整数演算よりも高速になる可能性があります。

整数演算に切り替えるのではなく、アルゴリズムを最適化することで、パフォーマンスをさらに向上できる場合があります。

パフォーマンスを向上させるもう 1 つの方法は、データ キャッシュ ヒットを減らし、分岐とループを減らすことです。

プログラムのパフォーマンスを測定して、ボトルネックがどこにあるかを見つけ出し、パフォーマンスの大部分が発生するセクションを確認します。たとえば、私の組み込みシステムでは、提案されているようなマイクロ最適化により、3 マイクロ秒節約されました。この利点は、システム全体を再テストする努力に値しません。動作する場合は、修正しないでください。最初に正確性と堅牢性に集中してください。

于 2013-10-10T15:39:16.170 に答える
2

ここでの結論は、自分でテストして判断する必要があるということです。実際のデータを使用してリリース ビルドをプロファイリングします。

1- そのような改善が得られるというのは本当ですか?

たぶんそうだけどたぶん違う。それは、次のような多くの要因に依存します。

  1. doubleからに変換するのにかかる時間int
  2. マシン上の単語の大きさ
  3. 使用しているプラ​​ットフォーム/ツールセットと有効にした最適化
  4. (おそらく) プラットフォーム上のキャッシュ ラインの大きさ
  5. あなたの記憶の速さ
  6. プラットフォームが浮動小数点と整数を計算する速度。

そして、誰が他に何を知っていますか。つまり、複雑な変数が多すぎて、パフォーマンスが向上するかどうかを確実に判断することはできません。

しかし、あなたの友人の「少なくとも 10 倍高速」という主張には、私は非常に懐疑的です。

2-すべてを整数に変換しても安全ですか? そして、これの欠点は何ですか?

何をどのように変換するかによって異なります。123.456明らかに、整数のような値を変換することは明らかに安全ではありません。

欠点には、精度の低下、精度の低下、および実際に変換を行うためのスペースと時間に関する費用が含まれます。もう 1 つの重大な欠点は、かなりの量のコードを作成する必要があり、作成するコードのすべての行が新しいバグの原因となる可能性があるという事実です。

3- この問題全体について、どのようなアドバイスがありますか? あなたならどうしますか?

私は一歩下がって深呼吸をします。実際の条件下でコードをプロファイリングします。ボトルネックの原因を特定します。本当の問題が何であるか、また問題があるかどうかを調べます。

アルゴリズムの非効率性を特定し、修正します。

問題にハードウェアを投げます。

次に、マイクロ最適化を開始するように努めることができます。これは私の最後の手段です。特に、検討している最適化手法で大量のコードを記述する必要がある場合はなおさらです。

于 2013-10-10T15:42:48.797 に答える
2

まず、これは不必要に最適化しようとする悪臭を放ちます。

2 つ目doublesは、最小 64 ビットです。 intsほとんどのシステムでは 32 ビットです。double を切り捨てる (精度を single に減らす)、2 つの整数のスペースに格納する、またはunsigned long long(これも少なくとも 64 ビットである) として格納するという 2 つの選択肢があります。最初の 2 つのオプションでは、操作している double とそれを格納している整数の間で数値を相互に変換する必要があるため、パフォーマンスの低下に直面しています。3 番目のオプションでは、基本的に同じサイズであるため (メモリ使用量に関して) パフォーマンスが向上することはありません。したがって、理由もなく整数に変換するだけです。

だから、あなたの質問に到達するには:

1) 疑わしいが、自分の目で確かめてみることができる.

2)問題はストレージではありません。ビットがメモリに入ったときのビットは単なるビットです。問題は算数です。倍精度が必要だと述べたので、整数型でこれらの操作を実行しようとしても、探している結果が得られません。

3) パフォーマンスを改善する必要があることが証明されるまで最適化しないでください。そして常にアムダールの法則を覚えておいてください: よくあるケースを速くし、まれなケースを正しくする.

于 2013-10-10T15:39:22.853 に答える
0

私がすることは次のとおりです。

最初に、サイクルを減らす方法が見つからなくなるまで、(ランダム一時停止方法によって) シングルスレッド モードで調整します。私が見つけたものの種類は次のとおりです。

  • sincosexpなどのライブラリ関数で費やされた時間の大部分はlog、引数が変更されないことが多いため、答えは同じになります。そのための解決策は「メモ化」と呼ばれ、引数と結果の古い値を格納する場所を見つけ出し、関数を呼び出す前に最初にそこをチェックします。

  • DGEMM (lapack matrix-multiply) のような最適化されていると思われるライブラリ関数の呼び出しでは、行列が上三角形、下三角形、正方形、対称、または実際に乗算を行うのではなく、何でも。もしそうなら、答えは明らかです - あなたの状況に合わせて特別なルーチンを書いてください。

「でも、そんな問題はありません」とは言わないでください。もちろん、おそらくさまざまな問題を抱えているでしょうが、それらを見つけるプロセスは同じです。

シングルスレッドで可能な限り高速化したら、それを並列化する方法を考えてみましょう。マルチスレッドではオーバーヘッドが高くなる可能性があるため、スレッドを密結合しないことをお勧めします。

double から integer への変換に関するあなたの質問に関しては、他の答えは正しいです。非常に特殊な状況でのみ意味があります。

于 2013-10-10T16:40:59.803 に答える