cache effects

今日は、参考になる記事のリンクを張ってみます。キャッシュ効率に関する記事です。簡単なプログラムを用いて「CPUのキャッシュの使い方」が丁寧に解説されています。データの読み/書きが頻繁に発生するアプリケーションを設計・実装する方に、ご一読お薦めします。

Gallery of Processor Cache Effects

英語の記事ですけど、情報系の方でしたら楽しく読めると思います。頭の片すみに置いておいて損はない情報だとも思います。というか、とっても簡潔なプログラムで、きちんと動作説明できちゃってるところが、すごいなぁって思うんですよね。コメントも面白い。以上です。

（以下駄文）massive data set への parallel access がボトルネックになるような場合、最も慎重に設計しないといけないポイントの一つがキャッシュ効率です。記事では、基本的な L1, L2 キャッシュの操作について、とても分かりやすく説明されています。加えて mmap なんかを押さえておけば、階層を意識したメモリ効率の良いアルゴリズムを設計する上での下地ができたと言っても良いかと思います。memory mapped file まわりについて→参考１, 参考２。それから、設計とかは、Algorithms for Memory Hierarchies: Advanced Lectures (Lecture Notes in Computer Science) も参考になるかと思います。グラフまわりのキャッシュ効率はもう一度確認しておきたいですね。

（以下さらなる駄文）マルチコアやGPGPU、だいぶ聞き慣れた言葉になりました。PRAM モデル*1 とかまで含めて、並列処理についても復習してみた方が良いでしょうか。EREW? Amdahl's Law? (R)NC? いろいろ忘れてる*2... っていってもやっぱり PRAM は、まだ少し違う気がします*3。とりあえず、SPAA の確認とかあまりやってませんでしたけど、やっといても良さそうですね。

*1:ちょっと古いですけど参考: http://www.mcs.anl.gov/~itf/dbpp/

*2:用語について忘れたときは、辞書 DADSで軽く確認。もう少し詳しく気になるならやっぱりwikipedia (PRAM) が良いですね！っていうか、DADS は展望用ですね

*3:pthread で並列凸包アルゴリズムを組んで、それほど大きくないサイズであっけなく破綻したことを思い出します。ふむ。CPUx32の計算機ではね。コア数1K/1ノードとか、それほど珍しくなくなってきました（汎用かどうかは置いておいて）。コア数1Gになったら楽しくなりそう