If I have an M x N matrix and an L1 cache of size K what cache miss rate does an optimal matrix transpose have. Obviously I am looking for something that is a function of M and N (and possibly K, though that is maybe too complex) rather than a specific number.
I am asking because I have a lot of matrix data that has to be processed in both directions and I would like a rule of thumb to know when it is worth while keeping both the original data and a transpose in memory.
あなたが持っているキャッシュタイプについては何も言っていませんが、それは直接マップされていますか? Nウェイセットアソシエイティブ? N-way セット アソシアティブを想定し (そして、特定の CPU アーキテクチャに依存するキャッシュのすべての詳細が必要です)、1 つの特定のマトリックス順序付け、たとえば列優先を想定すると、基本的に M*N/C のコールド ミスがほとんどになります。ここで、C はキャッシュ ラインのサイズです (これは CPU に依存しますが、通常は 8 double です :))。
次に、ターゲット行列にまたがるアクセスがあり、行列が L1 に完全に収まるほど小さい場合を除き、M*N コールド ミスの最悪のシナリオを想定できます。サイズ ~63*63 の行列。
したがって、転置の最悪のケース (M*N/C + M*N) の合計 L1 ミスを調べます。
1つのアイデアは、物理的に移動するのではなく、列優先から行優先など、行列の順序を反転させるトリックを実行し、転置されたものとしてアクセスすることです。同じデータで行列の順序を反転できる適切な行列の実装がある場合、これはゼロ コストの操作です。
ただし、実際に高価なプリフェッチは L1 ではなく、LLC (最終レベル キャッシュ) で行われます。たとえ L1 ミスが発生したとしても、L2 からロードされるため、安価なミスです。結論として、ターゲットの CPU アーキテクチャのすべての小さな詳細がなければ、計算するのは非常に困難です。