1

最近接ペアアルゴリズムを使用するアプリケーション用に要素の配列をキャッシュする方法を見つけようとしています(当面は総当たり攻撃)。The Cache Performance and Optimization of Blocked Algorithm の論文によると、次のように書かれています。

ブロッキングは、メモリ階層の有効性を高めるための一般的な最適化手法です。階層のより高速なレベルでデータを再利用することにより、平均アクセス遅延を削減します。また、階層のより遅いレベルへの参照の数を減らします。したがって、ブロッキングは、プリフェッチなどの最適化よりも優れています。プリフェッチは、レイテンシを隠しますが、メモリ帯域幅要件を削減しません。メモリ帯域幅がシステムのボトルネックになることが多いため、この削減はマルチプロセッサにとって特に重要です。ブロッキングは、線形代数の多くのアルゴリズムで役立つことが示されています。

この論文は行列乗算コードを提供し、キャッシュミスを減らしてブロッキングに変更されています。

for kk = 1 to N by B
  for j = 1 to N by B
    for i = 1 to N
      for k = kk to min(kk + B-1, N)
         r = X[i,k];  // register allocated
         for j = jj to min(jj + B-1, N)
           Z[i,j] += r * Y[k,j];

ここで、Bがブロッキング ファクターですが、これをどのように判断できますか? CPUキャッシュが処理できる特定の制限を見つける一般的な方法はありますか? おそらく、すべての CPU が同じキャッシュを持っているわけではありません。一般的な手順は次のように述べています。

  • 1 つ目は、コードを再構築して、再利用を伴うループをブロックできるようにすることです。
  • 2 つ目は、局所性を最大化するブロッキング ファクターを選択することです。

最近接ペア アルゴリズム (ブルート フォース) は次のとおりです。

minDist = infinity
for i = 1 to length(P) - 1
  for j = i + 1 to length(P)
    let p = P[i], q = P[j]
    if dist(p, q) < minDist:
      minDist = dist(p, q)
      closestPair = (p, q)
return closestPair

総括する：

  • 特定の CPU キャッシュ サイズの制限を手動でテストすることなく、B ファクターを最適化するにはどうすればよいですか。C言語を使用して現在利用可能なキャッシュを返す方法はありますか?
  • 1D 配列を使用する最も近いペア アルゴリズムを最適化するにはどうすればよいですか? つまり、x、y 座標を含む struct 要素の 1D 配列であり、すべてのポイントを他のすべてのポイントと比較する必要があるため、どの要素を保存して再利用する必要があるかということです (ブルート フォース アルゴリズムに固執しましょう)。

前もって感謝します！

4

1 に答える 1

4

最初の質問:

最適化する予定のマシンで実際にテストせずにBを決定する簡単な方法はありません。そうは言っても、おそらく、いくつかの実験で「ほとんどのシステムに適した」数値を見つけることができます（私は12〜15年前にこの種のことにかなり取り組んでいました）、約8〜16KBのブロックを使用すると機能することがわかりました結構です。この効果は、「すべてのメモリをそのまま実行する」と「ブロックを処理する」の間で非常に劇的であり、非常に小さなブロックから始めると、大きくなるにつれて大きな改善が見られます。次に、 Bが非常に大きくなり、開始した場所に戻るレベルに到達するまで、「リターン」が低下します (以前は使用しないものをフェッチするために適切なキャッシュを破棄します)。

コードのBの「サイズ」を選択して作業し、どのようなパフォーマンスが得られるかをテストすると、グラフをプロットすると、おそらく「バスタブ」のように見えることがわかります。 「かかった時間」をプロットします（または「単位時間あたりに処理されるアイテムの数」をプロットする場合は逆さまのバスタブ）。浴槽の「平らな」部分でポイントを見つけてください。ただし、すべての（または少なくともほとんどの）マシンで「フラットビット」にいることを確認するために、いくつかの異なるマシンで試してください。

2 番目の質問については、次のようになります。

minDist = infinity
for i = 1 to length(P) - 1 by B
  for j = i + 1 to length(P) by B
    for ib = i to i+B-1
      for jb = j to j+B-1
       let p = P[ib], q = P[jb]
       if dist(p, q) < minDist:
         minDist = dist(p, q)
         closestPair = (p, q)
return closestPair

がBlength(P)の倍数でない場合は、最後のいくつかの要素を処理するために少し余分な作業が必要になるため、ループの代わりにループが必要になる場合があります。i+B-1ibmax(length(P), i+B-1)jb

編集：

どのデータをキャッシュに保持するかは、キャッシュ自体が決定します。ここで行われることを変更するためにできることはほとんどありません。変更できるのは、作業しているデータのブロックです。

「ブロッキング」の鍵は、作業中のデータを (L1) キャッシュに保持することです。

データのロック全体が、それぞれ 4 バイトの 100000 要素、つまり約 400KB であるとしましょう。これは最新のプロセッサの L1 キャッシュには収まりません。最大で 64KB、多くの場合 32KB です。そのため、 を使用して項目をループするとi、jループは配列の後の部分をロードすることによって、適切な L1 キャッシュ コンテンツをすべて「破棄」します。そしてもちろんj、次回ループが開始されると、現在キャッシュ内にあるデータはどれも役に立たなくなります。これは、すべてが配列の上位インデックスであるためです。

代わりに、ブロック単位で一度に少しずつ配列を処理すると、各ループで配列のBサイズの 2 乗を処理できます。ここで、 B要素はキャッシュに収まる以上のスペースを使用しません。したがって、jbループはループのデータをスローしませんib(またはその逆)。これは、各内部ループが大幅に高速に実行されることを意味します (実行速度が 3 倍以上速くなったのを見たことがあります。これは、既に「適切」であると想定されていたコード上にあります)。

于 2013-04-29T09:43:05.630 に答える