問題タブ [cache-oblivious]

式キャッシュの忘却の意味を理解しています。しかし、キャッシュのサイズを知らなくても、キャッシュを最適に使用できるデータ構造を設計する方法について簡単な説明があるかどうか疑問に思いました。

できれば（簡単な）例を挙げて、そのような説明をお願いします。

暗黙的なポインターを使用して、van Emde Boas レイアウトを使用して配列に格納される、キャッシュを無視するバイナリ ツリーを実装したいと思います。ツリー内のすべての項目は 32 ビット整数であり、ツリーはかなり大きくなるため、ポインターを格納すると、少なくとも 3 倍のデータが必要になります。

問題は、ノード インデックスが与えられた場合に、左右の子へのポインターを計算するための非反復的な方法を考えられないことです (ツリーを走査している間、あらゆる情報を追跡できます)。多くの論文や講演では、暗黙的なポインターを使用してそのようなツリーを参照していますが、ポインターを計算するアルゴリズムは見たことがありません。それを行う効率的な方法はありますか？

キャッシュ忘却アルゴリズムやストリーミングツリーなどについてたくさん読んだことがあります。まだ理解できない基本事項は、並列プログラミングに適している理由です。ジョン・ハロップがそのために革命的だと言っているのを見たと思います。

倍増配列を使用してキャッシュ無視スタックを実装できることを読みました。

1/B分析により、各プッシュとポップが償却された I/O の複雑さをどのように持つのか、誰か説明してもらえますか?

モートン順序を使用して行列の転置を改善したいと考えています。

モートンオーダーに関する記事を見つけましたが、その使い方がわかりません。

特に、

と

この行列を逆にしたい A = [1 2 3 4; 5 6 7 8; 9 10 11 12; 13 14 15 16] (リニアアドレス)

に

B = [1 2 5 6; 3 4 7 8; 9 10 13 14; 11 12 15 16;]。

そして転置。

でも解けない……。

この変換の原理を知っている人はいますか?

よろしくお願いします。

Do cache (oblivious|optimal|aware) アルゴリズムは通常、モデルでシーク時間を考慮します。そうでない場合は、シーク時間を考慮したモデルの例があり、このモデルのアルゴリズムの分析があります。

私は速度のために C コードの大部分を最適化する時間が迫られており、任意のサイズ(行数、行数、列数) をターゲット行列(行数、列数) に「キャッシュに適した」方法、つまりデータの局所性を尊重する方法で変換します。の典型的なサイズは、約 5000 ～ 15000 行、50 ～ 500 列であり、要素の行単位のアクセスが非常にキャッシュ効率が悪いことは明らかです。 u[r][c] rcv[s][d]s = cd = ru

このトピックについては Web で多くの議論があります (このスレッドの近く) が、私が見る限り、それらのすべてが正方行列のような空間的なケースu[r][r]、または次元配列の定義について議論していますu[r * c]。Numerical Recipesのコンテキストで使用される「配列の配列」(同じ長さ) (背景はこちらを参照)。

「車輪の再発明」を省くのに役立つヒントがあれば、非常に感謝しています。

マーティン