計算量の多いプログラムのパフォーマンステスト

Question

計算量の多いプログラムのパフォーマンスを最適化および向上させるためのヒントやテクニックを教えてください。私は複雑なグラフィックスの計算や数秒間のプログラミングやシミュレーションのようなものについて話していますが、一定のスピードアップだけが役に立つIO重いプログラムとは対照的に、1秒ごとに保存しておくと便利です。

ここで最も効果的な方法としてアルゴリズムの変更が頻繁に言及されていますが、最初は効果的なアルゴリズムがどれほど効果的かを知りたいので、可能な限りアルゴリズムごとに効率を上げたいと考えています。私が解決している "問題"はよく知られているものではないので、Web上にアルゴリズムがあるのはほとんどありませんが、進める方法と探すべきことについてのアドバイスを探しています。

私は、進化的アルゴリズムと関連する問題の特定のグループに対してより簡単なアプローチの有効性の違いを探求しています。私はすでに問題の3つの進化的アルゴリズムを書いており、今私はできるだけ速くしようとしているブルートフォース技術を書いています。

編集：もう少し指定します。私はC＃を使用しており、アルゴリズムはすべて式の制約タイプの問題の計算と解決を中心に展開しています（式ツリーを使用）。式では、x^2 + 4のようなものや、式ツリーに解析されるようなものを意味します。私のアルゴリズムはすべて、これらの木を作成し、操作してより良い近似を見つけようとします。しかし、他の誰かを助ける場合に備えて、一般的な方法で質問を出したいと思っていました。

私は、さまざまなプロパティの良い近似である式を見つけるための有用な進化的アルゴリズムを書くことが可能かどうかを調べようとしています。両方とも、私は良い近似がどのようなものかを知り、進化論的なものが従来の方法とどのように比較されるかを知りたいからです。

Answer 1

最適化問題が（準）凸であるか、またはそのような形式に変換できる場合、進化的探索よりはるかに効率的なアルゴリズムがあります。

大きな行列がある場合は、線形代数ルーチンに注意してください。適切なアルゴリズムは、計算時間を大幅に短縮することができます。特に、行列が疎である場合にはそうです。

データがどのようにメモリにロードされるかを考えてください。あなたが純粋な算術演算にあなたの時間を費やしていると思っても、実際には、キャッシュのレベル間で物事を動かすのに多くの時間を費やしています。

不必要なメモリ割り当てと割り当て解除を避けるようにしてください。ここでは、純粋にOOのアプローチから離れていくことが理にかなっています。

Answer 2

これは他の最適化とほぼ同じプロセスです。プロファイル、実験、ベンチマーク、リピートです。

まず、コードのどの部分が時間を費やしているのか把握する必要があります。次に、速度を上げるためにさまざまな方法を試してみましょう（メリットに基づいたメソッドの試行は、ランダムに試行するよりも良いアイデアです）。あなたが実際にそれらをスピードアップしたかどうかを判断するベンチマーク。そうした場合は、古いメソッドを新しいメソッドに置き換えます。プロフィールをもう一度。

Answer 3

これを行う方法は、あなたが使用している言語のほとんどに依存します。 それでも、任意の言語のキー がプロファイラにあります。コードをプロファイルします。これらの高価な操作をより効率的にするには、 の機能/操作が最も時間を費やしているかどうかを確認してから を決定してください。

数値アルゴリズムの標準的なボトルネックは、メモリ の使用です（要素 がメモリに格納されている順序でアクセスします）。通信オーバヘッド、など。 は、他の非数値プログラムと少し異なる場合があります。

また、プレコンディショニングなどの他の多くの要因 は、同じ問題のSAMEアルゴリズムのパフォーマンスの違いが大幅に大きくなる可能性があります。 を確認して、実装に最適なパラメータを決定してください。異なるアルゴリズムを比較するためとして

、私は紙

ホルヘ以上とエリザベスD.ドーラン、数理計画法91（2002）、201から213「のパフォーマンスプロファイルと最適化ソフトウェアのベンチマーク」を読ん をお勧めします。

同じ問題セットに適用されている異なるアルゴリズム を比較するためのすばらしく統一的な方法を提供します。それは実際には最適化コミュニティの外で の方がよく知られているはずです（私の謙虚な意見では少なくとも ）。

幸運を祈る！

Answer 4

もし何か他のやり方をすることが可能であれば、私はブルートフォースアプローチに反対することをお勧めします。しかし、ここであなたのコードをスピードアップするのに役立つガイドラインがいくつかあります。

コードに多くのさまざまな最適化を適用できますが、何かをする前にボトルネックがどこにあるのかを把握する必要があります。

• GProf
• PerfMon2
• OProfile
• HPCToolkit

これらすべての使用のサンプリング：ここではあなたにホットスポットがあなたのコードのどこにいるかについて良いアイデアを与える必要があり、いくつかのプロファイラーがありますデータを取得するため、コードで実行する際のオーバーヘッドが最小限に抑えられます。 GProfだけでコードを再コンパイルする必要があります。また、最後の3つでは、時間とhardware performance counterの両方のプロファイルを使用できるので、時間（またはCPUサイクル）プロファイルを作成すると、より暑い地域を拡大してがなぜであるかがわかります（キャッシュミス、 FP命令カウント、など）。

これ以外にも、コードをどのように再構築するのが最も良いかということは、問題の内容によって異なります。コンパイラがうまく最適化しないループがあり、コンパイラを助けるためにループ内外に物事をインラインまたは移動することができます。または、基本的な算術演算でできるだけ速く実行している場合は、ベクトル命令（SSEなど）を利用しようとするとよいでしょう。コードが並列であれば、ロードバランスに問題があるかもしれません。コードを再構築して、データがコア全体に分散されるようにします。

これはほんの数例です。パフォーマンスの最適化は複雑であり、まずは徹底したアプローチを行っている場合は、十分に役立つことはありません。人々は物事を最適化した方法の詳細については

、最近Why do you program in assembly?問題のいくつかのかなり良い例がありました。

Answer 5

これは、アルゴリズム自体に穴を見つけるために、先端の詳細です...

他のすべてを犠牲にして、最も内側のループ内のすべてのものを簡素化する、最大のパフォーマンスを実現するために。

古典的なバウンスボールアニメーションが簡単なものです。あなたの物理学の本の中で定義を調べると数字に差し込むことによって重力を実装することができ、またはあなたはこのようにそれを行うと、貴重なクロックサイクルを節約することができます

initialize: 
float y = 0; // y coordinate 
float yi = 0; // incremental variable 

loop: 
y += yi; 
yi += 0.001; 

if (y > 10) 
    yi = -yi; 

しかし、今のあなたはこれを行うには持っているとしましょうすべてのパーティクルが他のすべてのパーティクルに引き付けられるN-bodyシミュレーションでネストされたループを使用します。何千もの粒子を処理する場合、これは非常にプロセッサーを要する作業になります。

もちろん、最も内側のループ内のすべてを単純化するのと同じアプローチをとるべきです。しかしそれよりも、最も単純なレベルでは、データ型を賢明に使うべきです。たとえば、浮動小数点変数よりも整数を扱う場合の演算は高速です。また、加算は乗算より高速であり、乗算は除算よりも高速です。

これを念頭において、主に整数の加算と乗算を使用して最も内側のループを単純化することができます。そして、あなたがしなければならない可能性のあるスケールダウンは、後で行うことができます。 、YおよびYI例を取るために、Yiはあなたが内側のループ内で変更の整数であるならば、あなたはこのようなループの後、それを縮小できます。

y += yi * 0.01; 

は、これらは非常に基本的な低レベルのパフォーマンスのヒントですが、私はプロセッサ集中型アルゴリズムを使って作業しているときは、私が心に留めようとしているすべてのことです。もちろん、これらのアイディアをGPU上の並列処理に適用すれば、アルゴリズムを全く新しいレベルにすることができます。 =）