問題タブ [localityofreference]

Locality of Referenceに関するウィキペディアの記事を読んでいますが、 Equidistant Localityの説明がやや不可解であることがわかります。

あまり意味が分からないので、どなたか平易な英語で説明していただけないでしょうか？

等距離の局所性: 空間的局所性と分岐局所性の中間です。等距離パターンで場所にアクセスするループを考えてみましょう。つまり、時空間座標空間のパスは点線です。この場合、単純な線形関数を使用して、近い将来にアクセスされる場所を予測できます。

「等距離パターンで場所にアクセスするループ」とはどういう意味ですか? 場所は互いに等距離ですか？

「時空間座標空間は点線である」というこのゴミは何ですか？それは私には意味がありません。

等距離の局所性が何を意味すると考えられているかについて誰かが明確にすることができれば、それは素晴らしいことです!

空間的局所性に関してキャッシュ操作を学んでいます。（これまでの私の参考資料は、LinとSnyderによる並列プログラミングの原則、このチュートリアル、そしてもちろんWikipediaです。）

次の例を見てください。gccでコンパイルされ、Windows 7 Professionalで実行され、Intel Core2 Duo CPU（L7500）を使用しています。

ルーチンの後半では、整数の配列全体が読み取られるため、空間的な場所ごとに、CPUは事前に整数をキャッシュにロードする必要があります。しかし、ループ中の任意の時点で、アレイのどのくらいの量をキャッシュにロードできますか/しますか/ロードする必要がありますか？一度に1つのキャッシュライン（64バイト/intあたり4バイト=16整数）、それの大きなブロック、または一挙に配列全体？

また、私が理解していることから、RAMからキャッシュに（または教科書ごとに、非ローカルメモリからローカルメモリに）データをロードすることに伴う遅延は、実際にルーチンを実行するのに必要な時間よりもはるかに重要です。本当ですか？

ここで、このコードをマルチプロセッサ/マルチコアマシンに移動し、コードのカウント部分を4、8、16などの並列スレッド（pthreadを使用）で実行するように変更し、配列の個別の部分をカウントしてから、プライベートは最後に一緒にカウントされます。これにより、RAMからキャッシュへのレイテンシが複数回発生し、パラレルバージョンの実行がシリアルバージョンよりも遅くなる可能性がありますか？

私の教授は、2 次元配列を最初の方法で初期化する方が、2 番目の方法よりもはるかにコストがかかると言いました。ボンネットの下で何が起こっているのか、誰かが説明できますか? または、2 つの初期化手段のパフォーマンスは同じですか?

構造体の配列をクラスの配列およびクラスのリストと比較する多くのテストを実行してきました。これが私が実行してきたテストです：

私はこれをリリースモードで次のように実行しています:

結果：

padding=0 を使用すると、次のようになります。

padding=64 を使用すると、次のようになります。

padding=128 を使用すると、次のようになります。

違いがもっと大きいと予想していたので、これらの結果には少し混乱しています。すべての構造体は小さく、メモリ内に次々と配置されますが、クラスは最大 128 バイトのガベージによって分離されます。

これは、キャッシュの使いやすさについても心配する必要がないということですか? それとも私のテストに欠陥がありますか？

実装が次のような C++ クラスがあるとします。

C++ レベルでは、これらのメソッドの空間的な局所性を制御できますか? それとも、コンパイラが関連するメソッドを認識し、それに応じてそのアセンブリを最適化することを期待する必要がありますか? 理想的には、命令キャッシュに一緒にロードされるように、それらを互いに隣り合わせにしたいのですが、コンパイラーにこれを本当に望んでいることを知らせる方法がわかりません。

私は現在、入力データがHDFSになく、HDFSにロードできないマップリデュースジョブを作成しようとしています。これは、データを使用するプログラムがHDFSからのデータを使用できず、少なくともHDFSにコピーするには多すぎるためです。ノードあたり1TB。

したがって、クラスター内の4つのノードのそれぞれに4つのディレクトリがあります。理想的には、マッパーがこれら4つのローカルディレクトリのパスを受け取り、file：/// var / mydata / ...のようなものを使用してそれらを読み取るようにします。そうすれば、1つのマッパーが各ディレクトリで機能します。つまり、合計16個のマッパー。

ただし、これを実行できるようにするには、ノードごとに正確に4つのマッパーと、そのマシンにローカルなパスが割り当てられている正確に4つのマッパーを取得する必要があります。これらのパスは静的であるため、fileinputformatとrecordreaderにハードコーディングできますが、特定の分割が既知のホスト名を持つ特定のノードで終了することを保証するにはどうすればよいですか。それがHDFSにある場合、FileInputFormat設定のバリアントisSplittableをfalseに使用でき、hadoopがそれを処理しますが、すべてのデータがローカルであるため、これにより問題が発生します。

基本的に私が望むのは、クラスター内のすべてのノードのローカルディレクトリ構造を1回だけクロールし、これらのディレクトリ内のSSTableのコレクションを処理し、（マッパー上で）行を出力し、結果を（reduceステップで）reduceできるようにすることです。さらなるバルク処理のためのHDFS。

inputSplitsがgetLocations関数を提供していることに気付きましたが、これは実行の局所性を保証するものではなく、最適化するだけであり、各マッパーでfile：/// some_pathを使用しようとすると、正確な局所性を確保する必要があります。一部のディレクトリを繰り返し読み取り、他のディレクトリはまったく読み取らない。

どんな助けでも大歓迎です。

移動用の新しい命令と新しいメモリ コントローラーを備えた新しい CPU を考慮すると、C++で仮想メンバー関数で構成されるDerivedオブジェクトのベクトルがあるDerived場合、これは局所性にとって良いことですか、悪いことですか?

Base*から 1-2-3 レベル上の派生オブジェクトへの参照を格納する基本クラスへのポインターのベクトルがある場合はどうなるBaseでしょうか。

基本的に動的型付けは両方のケースに適用されますが、キャッシングとメモリアクセスにはどちらが適していますか?

私はこの2つのどちらかを好みますが、この件に関する完全な回答を見たいと思います.

過去 2 ～ 3 年間で、ハードウェア業界から革新的なものと見なす新しいものがありますか?

ソートされていない配列と連結リストがあるとします。両方のデータ構造の要素を検索する場合の最悪のケースは O( n ) ですが、私の質問は次のとおりです。

キャッシュ内の空間的局所性を使用するため、配列はさらに高速になりますか、それともキャッシュは分岐局所性を使用して、リンクされたリストを任意の配列と同じくらい高速にすることができますか?

配列についての私の理解では、要素がアクセスされると、そのメモリのブロックと周囲のブロックの多くがキャッシュに取り込まれ、メモリアクセスがはるかに高速になります。

リンクされたリストについての私の理解は、リストをトラバースするために取られるパスは予測可能であるため、リストのノードがヒープ内で遠く離れている場合でも、キャッシュはそれを利用して適切なメモリブロックを保存するということです.

別の関数への別のポインターを返す関数へのポインターが、C で使用されるメカニズムであり、ランタイム ポリモーフィズム/コールバックを導入するという事実を考慮すると、局所性を改善し、ポインターと間接参照に関するコストを削減しながら、C++ でこれを実装する同等の方法は何ですか? ?

たとえば、このシンタックス シュガーは役に立ちますが、私はこれにはあまり興味がありません。C っぽいのではなく、C++ の方法で物事を行うには良い方法ですが、ローカルtypedef性を改善することにもっと関心があります。実行時の明示的なポインターの使用。