- 追加された行はこの色です。
- 削除された行はこの色です。
[[FrontPage]] > [[sys_parallel]]
* 並列分散システム特論 [#ac46fad9]
-担当部分: 69〜76ページ
*前提となる内容 [#rf1e00b9]
途中からだと意味がわからんので。
**2.11 Invalidation Patterns [#bb1db98e]
前章では並列アプリケーションが生成する通信量に注目した。
この章ではなんでそのような通信量が発生するのか深く見る。
どのアプリケーションも無限のキャッシュ（4〜8 バイトの小さなラインサイズ）があるとして、走ってる。
どれだけのプロセッサがラインを共有していて、書き込みによってどれだけ無効化されたかがわかる。
各書き込みに対応する無効化の回数は、書き込まれたアドレスにいる高レベルのデータオブジェクトに戻されてますよっと。
***2.11.1 Classification of Data Objects [#z3f2faba]
-2.11.1.1 Code and Read-Only Data Objects
--どんなデータか：読み取り専用データで、確保、初期化後は滅多に無効化されない。
--キャッシュへの影響：あまりない。
--例：fixed database などがそう。
-2.11.1.2 Migratory Data Objects
--どんなデータか：一つのプロセッサから操作されるデータである。
--キャッシュへの影響：単一の無効化（※）を引き起こす。
--例：MP3D のスペースセルなどがそう。
---単一の無効化とは）（※）ある CPU A だけが触る、その後に別の CPU B がいじると、前持ってた CPU A のキャッシュが無効化される。ということのようですが？
-2.11.1.3 Mostly-Read Data Objects
--どんなデータか：頻繁に読まれるデータで、何か書き込むべき最良の物が見つかったときに更新される。
--キャッシュへの影響：書き込みされると、周りのキャッシュが一気に無効化されるが、非常にまれにしか書き込まれないので影響は少ない。
--例：LocusRoute のコストアレイがそうらしい。
-2.11.1.4 Frequently Read/Written Objects
--どんなデータか：読み込みも書き込みも頻繁に行われる。
--キャッシュへの影響：各書き込みは小さな無効化しか引き起こさないけれども、頻繁に書かれるから無効化がすごい大量に起こる。
--例：今回用いた中にこの例はない。
---普通のオブジェクトなのに、間違って同期オブジェクトとして使ってるときにこの例を見かける。（これはあってはいけないことって意味か？）
-2.11.1.5 Synchronization Objects
--どんなデータか：同期処理に使われるデータである。低衝突のものと、高衝突のものに分かれる。
---低衝突：あまり無効化が起きない。例：共有データを保護する分散ロックなど。
---高衝突：かなりの無効化が生じる。例：タスクキューなど。
--キャッシュへの影響：
--例：ロックやバリアといったものがそう。
---プロセッサ数をスケールさせるためには、同期オブジェクトのハードウェア的なサポートが必要になるとのこと。
*担当部分の内容 [#a8ae5bcf]
***2.11.6 PTHOR [#m577b1f7]
***2.11.7 LocusRoute [#o0965996]
***2.11.8 Cholesky [#t216ca0d]
***2.11.9 Barnes-Hut [#p6f02835]
***2.11.10 Summary of Individual Invalidation Distributions [#idd22bf7]
分散処理を無効化してしまう多くのアプリケーションは、小さな無効化が主な原因である。一般的には、移動するデータ、つまりデータオブジェクトが一つのキャッシュから次へ移るような、単一の無効化が原因である。
大きな無効化は頻繁に読み出されるデータオブジェクトに起因する。
これらのオブジェクトが書き込まれるのは比較的まれである。
普通は、広く共有されないか、あるいは頻繁に書かれないと思う。
これはキャッシュ無効式のコヒーレントプロトコルや、ディレクトリ式のコヒーレントプロトコルの強い支え（endorsement）だ。
----
同期オブジェクトはデータオブジェクトと著しく違う振る舞いをする。
あまり競合（contention）のない同期オブジェクトだと、少しの無効化しか引き起こさない。なぜなら同期オブジェクトを待っている待機者（waiter）はゼロ、あるいは少数だからである。
かなり競合している（high contention）オブジェクトだと、大規模な無効化を起こす。そしてオブジェクトには比較的頻繁にアクセスがある。
この場合、これらのオブジェクトを対象としたハードウェアのサポートが望ましい。
----
残りのセクション（↓二個）はアプリケーション中に見られる無効化がどんなものか、見よう。パラメータや、プロセッサや問題サイズ、キャッシュラインサイズを変えて。
***2.11.11 Effect of Problem Size [#md1e831e]
比較的遅いシミュレーションによる物だったから、比較的小さいデータでやっていた。
キャッシュの無効化に問題サイズが及ぼす影響を勉強するには、同じ環境（同じプロセッサ数、同じ条件）でサイズだけを色々変えて問題を解いてみる必要がある。
ここでは三つの条件、今まで使ってきた物、今までの倍、今までの半分、で実験する。
問題サイズが増加したとき、分散が無効化される一般的な傾向である。原因としては、無効化を伴う書き込み毎に、同じあるいは少ない無効化をもつため。
問題サイズが増加すると、少ない共有オブジェクトが、そして共有されたデータオブジェクトがより狭い範囲で共有される傾向がある。
唯一の例外は LocusRoute である。回路のサイズより、回路の密度が無効化の主な原因となる。
次に重要な傾向としては、問題サイズが増加すると無効化を伴う書き込みの頻度が一定あるいは減少することである。
この傾向は、問題サイズが大きいと通信と計算の比がより有利になることが原因である。
問題サイズが大きくなったとき、多くの仕事は、それまでと同じかあるいはよりよい通信と計算の比を導く。
***2.11.12 Effect of Number of Processors [#m8a83c7f]
書こうとしたら、塚田君とかぶってたぜ！
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
