11

非常に長い整数 (10 進数で約 100,000 桁) の乗算の算術演算に取り組んでいます。ライブラリの一部として、2 つの長い数字を追加します。

プロファイリングによると、私のコードは add() および sub() ルーチンで時間の 25% まで実行されるため、可能な限り高速であることが重要です。しかし、私はまだ多くの可能性を見ていません。多分あなたは私に助け、アドバイス、洞察、またはアイデアを与えることができます. 私はそれらをテストし、あなたに戻ってきます。

これまでのところ、私の追加ルーチンはセットアップを行ってから、8 回展開されたループを使用します。

mov rax, QWORD PTR [rdx+r11*8-64]
mov r10, QWORD PTR [r8+r11*8-64]
adc rax, r10
mov QWORD PTR [rcx+r11*8-64], rax

異なるオフセットを持つさらに 7 つのブロックが続き、ループします。

以前にメモリから値をロードしようとしましたが、それは役に立ちませんでした。これはプリフェッチが優れているためだと思います。Intel i7-3770 Ivy Bridge 4 コア CPU を使用しています。しかし、最新の CPU で適切に動作するコードを書きたいと思っています。

編集：いくつかのタイミングを取りました：約2.25サイクル/ワードで1kワードを追加します。ADC を削除すると、MOV だけが残り、1 ワードあたり約 1.95 サイクルかかります。したがって、主なボトルネックはメモリアクセスにあるようです。ライブラリmemcpy()は約 0.65 サイクル/ワードで動作しますが、入力は 2 つではなく 1 つだけです。それでも、SSE レジスタを使用しているため、はるかに高速だと思います。

いくつかの質問：

  • 「ロード、ロード、追加、保存」構造を使用することは有用ですか、それとも「ロード、メモリへの追加」が役立ちますか? これまでのところ、私のテストでは利点は見られませんでした。
  • いつものように、期待される SSE(2,3,4) からの助けはありませんか?
  • アドレッシング (スケーリングされたインデックスとベースとオフセット) は悪影響を及ぼしますか? 代わりに使えますADD r11, 8。
  • ループの展開はどうですか？Sandy Bridge アーキテクチャ (Agner Fog http://www.agner.org/optimize/ ) では展開が悪いと読みました。それは優先されるべきですか、それとも回避されるべきですか？
  • (編集) SSE レジスタを使用してメモリから大きなチャンクに単語をロードおよび格納し、汎用レジスタおよび SSE レジスタと効率的に単語を交換できますか?

コメントをいただければ幸いです。

4

3 に答える 3

3

次の操作を実行する前にフェッチされるデータに依存しないため、memcpy の方が高速であると確信しています。

次のようなことができるようにコードを調整できる場合:

mov rax, QWORD PTR [rdx+r11*8-64]
mov rbx, QWORD PTR [rdx+r11*8-56]
mov r10, QWORD PTR [r8+r11*8-64]
mov r12, QWORD PTR [r8+r11*8-56]
adc rax, r10
adc rbx, r12
mov QWORD PTR [rcx+r11*8-64], rax
mov QWORD PTR [rcx+r11*8-56], rbx

-56 のオフセットがコードに適しているかどうかは 100% 確信が持てませんが、コンセプトは「正しい」ものです。

また、キャッシュ ヒット/キャッシュ コリジョンも検討します。たとえば、データのブロックが 3 つある場合 [そう思われるかもしれません]、それらがキャッシュ内の同じオフセットに配置されていないことを確認します。悪い例は、キャッシュ内の同じ場所から、キャッシュサイズの倍数ですべてのブロックを割り当てる場合です。異なるデータ ブロックが少なくとも 512 バイトオフセットされていることを過剰に割り当てて確認します [したがって、4K のオーバーサイズを割り当て、4K の境界開始アドレスに切り上げ、次に 512 を 2 番目のバッファーに追加し、1024 を 3 番目のバッファーに追加します]

データが十分に大きい (L2 キャッシュよりも大きい) 場合は、MOVNT を使用してデータをフェッチ/保存することをお勧めします。これにより、キャッシュへの読み取りが回避されます。これは、非常に大きなデータがある場合にのみ役立ちます。次の読み取りでは、「役立つ」と思われる他の何かがキャッシュから追い出され、取得できません。とにかくキャッシュから追い出す前に戻ってください-したがって、値をキャッシュに保存しても実際には役に立ちません...

編集: ここで説明されているように、SSE などを使用しても役に立ちません: Can long integer routines benefit from SSE?

于 2012-12-20T15:29:20.293 に答える
2

最も困難な依存関係は、すべてのメモリ ブロック間のキャリーの伝搬です。まずは対処法を考えてみます。

次のフラグメントは、キャリーの伝播をシミュレートしますが、キャリー フラグを使用しないという「利点」があります。これは、3 つまたは 4 つの個別のスレッドに対して並列化でき、それぞれが約 25000 桁 (または 10000 バイト) 離れた半分のキャリーを生成します。次に、これらのキャリーが 1 バイト、ワード、dword などにのみ影響を与える可能性は、漸近的にゼロになります。

 long long carry=0;
 for (int i=0;i<N;i++) {
     carry += (long long)*a++ + (long long)*b++;
     *c++ = carry; carry>>=32;
 }

私のプロファイリングによると、xmm を使用したキャリーレス加算には ~550ms (1e9 ワード)、シミュレートされたキャリーには ~1020ms、4 方向並列バージョンには ~820ms かかります (アセンブラーの最適化なし)。

アーキテクチャの最適化には、キャリーを常に伝播する必要がなく、キャリーの評価をほぼ無限に延期できる冗長番号システムの使用が含まれる場合があります。

于 2012-12-20T15:07:46.103 に答える
1

最初にデータのプリフェッチを試行し (最初に x64 レジスターにさらにデータ ブロックを読み取ってから計算を実行することもできます)、データがメモリ内で適切に配置されているかどうかを確認し、16 に配置されたラベルにループ コードを配置し、SIB アドレス指定を削除してみてください。

コードを次のように短縮することもできます。

mov rax, QWORD PTR [rdx+r11*8-64]
adc rax, QWORD PTR [r8+r11*8-64]
mov QWORD PTR [rcx+r11*8-64], rax
于 2012-12-20T14:18:18.060 に答える