6

と がdouble xありdouble yます。これを に変換する必要があります。これは、サイズ の正方形でグリッドに収まるint boxnum(フロア化された) インデックスとして定義されます。を超える座標は折り返されます。同上。(x,y)WIDTH x HEIGHTBOX_SIZEWIDTHHEIGHT

私は現在使用しています：

( (((int)(x))/BOX_SIZE)%WIDTH+ WIDTH*((((int)(y))/BOX_SIZE)%HEIGHT) )

このステートメントは現在、実行時間の 20% 程度を消費しており、負の座標に対して完全に安全にするとさらに悪化します (40-50% 程度):

( (( ((int)(x)) /BOX_SIZE)%WIDTH+WIDTH)%WIDTH
    +WIDTH*(( (((int)(y)) /BOX_SIZE)%HEIGHT+HEIGHT)%HEIGHT) )

これを避けるために、アプリケーションを固定小数点に完全に変換することを実際に検討しています。これにより、この恐ろしい変換を行う代わりに、必要な部分をビットマスクできます。

この種の double->int 変換を行うより良い方法はありますか? 0<x<WIDTH*BOX_SIZEそれを確実にして、0<y<HEIGHT*BOX_SIZE残りの2つの操作を削除できるようにすることは価値がありますか? (これを行うことは、大幅な改善が見込めない限り、ベンチマークの価値がないほど困難です)

編集:コメントで適切な懲らしめの後、詳細:

xおよびyは、一連の (10^6 もの) 粒子の座標です。ボックス内のすべての粒子の単純な合計を時間ステップごとに計算するアルゴリズムを使用しています。したがって、粒子全体をループし、粒子が入っているボックスを計算し、それをそのボックスに追加するための配列インデックスとして使用します。パーティクルは、過去の位置が将来の位置を示すものではないほど遠くまで移動することがよくあります。も順不同です。つまり、これについては何も仮定できません。

WIDTH、HEIGHT、およびは、およびがの倍数であるBOX_SIZE限り、技術的には無料です。実際には、それらはすべて指定されたコンパイル時間であり、. 私は からまですべてを実行しましたが、通常は 2 の平方乗ですが (なぜか?)、問題なく動作するはずです。WIDTHHEIGHTBOX_SIZEBOX_SIZE=1WIDTH=HEIGHT=4WIDTH=HEIGHT=512WIDTH=37;HEIGHT=193

この計算は、タイムステップごとにパーティクルごとに 1 回実行されることは避けられません。現在の実装では、2 回実行されます。再計算を避けるために値をキャッシュしようとしましたが、最後のベンチマークのパフォーマンスが低下したため、2 回計算し直しました。

10 particles/box * 100 WIDTH * 100 HEIGHT* 10000 steps = 1 billion particle*timesteps日陰で1分かけて走る基本的な試運転。

これらの座標は「通常の数値」 (1 ～ 1000) の順序になっているため、double.

4

2 に答える 2

7

コードの問題は、(int)キャストによって、浮動小数点ユニットの丸めモードが IEEE754 のデフォルトの丸めからC 標準に最も近い丸めに変更されることです。標準で定義されているように、ゼロまたは「切り捨て」に丸められます。

IEEE754 丸めモードの詳細については、こちらの gcc ドキュメントを参照してください。

最新の深くパイプライン化されたプロセッサでは、丸めモードが変更されたときにパイプライン全体をフラッシュする必要があり、キャストごとにパイプラインが空になるため、大幅な速度低下が発生し(int)ます。これをループで実行している場合、発生する速度低下は典型的なものです。

この問題について、Erik de Castro Lopo (libsndfile と secret rabbit code の作者) による非常に興味深い記事があります。彼のオーディオ変換ルーチンでは、浮動小数点丸めのパフォーマンスが重要です。彼は、POSIX 呼び出しを使用したこの問題に対する一連の興味深いソリューションとlrintf()、非 POSIX プラットフォーム用の x86 アセンブリを提供しています。

記事はこちらからご覧いただけます。

簡単な答えは、C99/POSIXlrintf()関数を使用するか、インライン アセンブリを使用して、浮動小数点の丸めモードを変更せずに整数の切り捨てを実行することです。

于 2013-05-09T21:47:51.547 に答える
3

割り算と余り

コメントで示唆されている問題は、除算 (および/または剰余演算) が高価になる可能性があることです。加算と乗算の 1 サイクルと比較して、除算に数十プロセッサ サイクルかかることは珍しくありません。

このコストを回避する最も簡単な方法は、WIDTH および HEIGHT コンパイル時の定数を 2 の累乗にすることです。これにより、コンパイラは、ビットマスク操作を使用して剰余操作を変更したり、ビットマスク操作を高速化し% WIDTHたりできます。% HEIGHT同様に、BOX_SIZE が 2 のべき乗であるコンパイル時定数である場合、コンパイラは除算をビット シフトに変更できます。

これは、合計が負ではないことが保証されるように Number が WIDTH の倍数であるに変更((int) x / BOX_SIZE % WIDTH + WIDTH) % WIDTHすることをほのめかしている私のコメントの理由でもあります。((int) x / BOX_SIZE + Number) % WIDTHこれにより、剰余演算が不要になります。(ただし、負の座標を処理するためにこの式を提案していましたが、欠陥がある(int) x / BOX_SIZE可能性があります。商をゼロに丸め、負の x に対して間違ったボックス番号を与える可能性があります。したがって、最適化を検討する前に、この式を修正する必要がある場合があります。側面。）

他の

多くの場合、インデックスの計算に実行時間の 20% がかかっているように見える理由として、キャッシュとプロセッサ時間のソース コードへの不正確な帰属が疑われます。表示するインデックス計算は、メモリにアクセスしないため、キャッシュへの影響はありません。ただし、コンパイルされたコードは、インターリーブされた命令になることがよくあります。各ソース コード ステートメントは、複数の命令を生成することになり、さまざまな理由で、1 つのステートメントのすべての命令、次にすべての命令として表示されるのではなく、さまざまなステートメントの命令がインターリーブされます。別のステートメントなど。このインターリーブにより、パフォーマンスに関するソフトウェア レポートでは、プロセッサ時間が消費されている場所を正確に示すことが難しくなります。

このような測定を妨げる他の影響があります。一部の測定はサンプリングによって実行されます。プロセッサは一定間隔で中断され、中断時のプログラム カウンタの値が記録されます。これは、プロセッサが何かを待っていたが、待っていたものではないことを示しています。たとえば、への変換がx浮動int小数点ユニットが使用可能になるのを待っていたが、前の命令がまったく無関係なデータの加算を実行していたためにユニットが使用できなかった場合、サンプルの 20% が(int) x誤解を招くです。

100 万個のパーティクルで操作しているという事実は、一部のデータ アクセスがキャッシュのスラッシングとパフォーマンスの低下を引き起こしていることと一致しています。一方、（負の座標をサポートするために）剰余演算を追加すると、インデックスの計算に時間がかかるように見えるという事実は、キャッシュの問題を示しています。

ただし、プログラムが他の作業をほとんど行っていない場合を除き、これらのインデックス計算がプログラムの時間の大部分を消費することはまれです。

問題を示す自己完結型のコンパイル可能なコードを示すことができれば、役立つかもしれません。

于 2013-05-10T13:19:09.180 に答える