1

クラスプロジェクトの一環として、CPUアーキテクチャでパスファインディングアルゴリズムのパフォーマンスを向上させる方法を検討しています。アルゴリズムはC++で実装されています。基本的な操作は、x、y座標を読み取り、それらに対していくつかの操作を実行することです。

私が今持っているアイデアは、x座標とy座標を2つのキャッシュバンクに別々に格納することです（関連付けを設定）。場所に入力された2つの座標は、それらを並行して読み取り、x座標とy座標に対して別々の操作を実行し、結合された結果を保存できるように、異なるバンクに保存する必要があります。ベクトル演算を使用することにより、このプロセスをさらに高速化して、最大4つのx座標と4つのy座標を同時に読み取ることができます。

たとえば、ゴールノードからのユークリッド距離を計算するには、各位置でx座標とy座標を読み取り、ゴール座標から差し引いて距離を求める必要があります。

並列処理を利用するために、x座標とy座標を異なるキャッシュライン/ブロックに保持する効果的な方法（キャッシュ配置ポリシー）があるかどうかを知りたいです。実装に使用できる座標の操作/エンコードはありますか？

PS：私はソフトウェアの最適化を探しているのではなく、アルゴリズムを高速化するために変更されたキャッシュ設計（理論的）を探しています。

参照：このブログ投稿では、「L1キャッシュは、異なるバンクのキャッシュラインにアクセスする場合は2つのアクセスを並列に処理でき、同じバンクに属する場合はシリアルに処理できます」と述べています。

4

1 に答える 1

0

次のような構造で保持される座標:

struct {
  int x;
  int y;
} coordinate;

1 つのキャッシュ ラインに収まります。実際、32 バイトのキャッシュ ラインを持つ典型的な MIPS プロセッサでは、 の 8 つのインスタンスがcoordinateキャッシュ ラインに収まります。CPU は、データ キャッシュ内の 1 つのバンクまたはウェイからライン全体を一度に読み取り、それ以降、32 バイトすべて、または 4 つの座標すべてが、パイプラインへのゼロ遅延で32 バイトのフィル/ストア バッファ(FSB) で利用可能になります。 . 通常、キャッシュ付きの MIPS プロセッサには複数の FSB があります。

バンク キャッシュまたはセットアソシアティブキャッシュを備えた MIPS プロセッサは、通常、LRUアルゴリズムを使用して、キャッシュ ミス時に新しいデータを配置するバンク/ウェイを選択します。一般に、特定の場所からのデータが常にキャッシュ内の特定のウェイに配置されることを保証することはできません。

これはすべて、x 座標と y 座標を別々のキャッシュ バンクに格納するスキームは、ナイーブ スキームに対する FSB のプラスの効果と、ウェイ選択アルゴリズムの予測不可能な効果のために、ナイーブ スキームよりもパフォーマンスを向上させないということです。キャッシュ。

于 2012-12-08T02:09:55.400 に答える