11

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

4

3 に答える 3

8

記事 http://www.1024cores.net/home/parallel-computing/cache-oblivious-algorithmsで

彼らはそれを指摘します

キャッシュ無視アルゴリズムの背後にある考え方は、プロセッサ キャッシュの効率的な使用とメモリ帯域幅要件の削減です。どちらもシングル スレッド アルゴリズムでは同様に重要ですが、並列アルゴリズムでは特に重要です。使用可能なメモリ帯域幅は通常、ハードウェア スレッド間で共有され、スケーラビリティのボトルネックになることが多いためです。

メモリへのアクセスは、並列アルゴリズムのボトルネックになる可能性があるため、キャッシュされたメモリを利用しようとするアルゴリズムを使用すると、より効率的になる可能性があります。

同じ記事で、キャッシュ無視アルゴリズムが利用可能なキャッシュをどのように利用するかについて説明しています。

キャッシュ無視アルゴリズムは、問題のデータセットをより小さな部分に再帰的に分割し、各部分の計算をできるだけ多く行うことによって機能します。最終的に副問題データセットはキャッシュに収まり、メモリにアクセスせずに大量の計算を実行できます

于 2011-05-08T11:30:28.377 に答える
5

あなたの質問は、複数のプロセッサが独自のプライベートキャッシュと複数のコア間の共有キャッシュを持つマルチコアアーキテクチャ内で特に重要であることを指摘したいだけです. 高い効率性とスケーラビリティを実現するには、並列アルゴリズムがデータ キャッシュで優れた空間的局所性と時間的局所性を示す必要があります。

Harald Prokop の修士論文以前は、アルゴリズムとデータ構造は、キャッシュ ミスの比率を減らすためにキャッシュを意識した (キャッシュを意識した) 方法で設計されていました。たとえば、B ツリーは、キャッシュを意識したデータ構造のよく知られた例です。パラメータ B は、CPU キャッシュ サイズを使用して調整されます。キャッシュ無視モデルでは、アルゴリズムの再帰的な性質により、サブ問題は最終的にキャッシュに収まり、そのようなサブ問題を操作すると、少数のキャッシュ ミスが発生します。

キャッシュ無視アルゴリズムのいくつかの優れた特性は、CPU キャッシュ サイズとは無関係であり、あらゆるメモリ階層で適切に機能し、キャッシュの複雑さにおいて最適であることが証明されています。マルチコア並列処理の台頭により、キャッシュ無視アルゴリズムは、パフォーマンスの高い並列プログラムを導出する上で重要な役割を果たす可能性があります。次の記事http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspxで、再帰的なデータ構造とキャッシュを無視するアルゴリズムに関する興味深い議論も見ています。.

于 2011-05-09T13:01:58.207 に答える
4

マルチコア プロセッサでは、コアあたりのキャッシュが少なくなります。専用のシングルコア プロセッサのキャッシュは、シリコン上で膨大なスペースを占有します。グーグル画像検索で自分の目で確かめることができます。キャッシュ サイズが非常に大きいことがわかります。

したがって、20 個のコアがあり、それぞれが通常のプロセッサの 20 分の 1 のキャッシュを持っている場合、巨大なキャッシュがなくてもアルゴリズムが適切に機能することを期待したほうがよいでしょう。=)

于 2011-05-08T11:25:18.013 に答える