![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
[[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-10(a) は PTHOR での無効化の分布を表している。大規模な無効化を引き起こす共有への書き込み（shared write）が非常に少ないことがわかる。 PTHOR の基本オブジェクトは論理素子と、ネットデータ構造である。これらに加え、要素の activation list と free list と、グローバルアレイ（global array）（"各プロセスの値 "per-process values"）と、グローバルスカラ（"global values"）がある。 グローバルスカラが、アルゴリズム中でデッドロックに至っているプロセッサの数のような値である間、グローバルアレイは各プロセスの計算途中のデータを保持している？？ 2-10(c)にデータオブジェクトについて書いてある。 ---- プログラムの実行中、論理素子は移動する（migratory）オブジェクト（単一の無効化をおこす）のように振る舞う。 要素データ構造の一部分は、それを見るプロセッサの全てから変更されるわけではない。 これら長寿命な値、例えば要素（elements）の最小有効時間、は良く読まれるカテゴリ（mostly-read category）に入るんじゃないかな。これらはアップデートされると大きな無効化を引き起こす。 ---- PTHOR で共有されるネットデータは、回路の接続によって決まる。いくつかのネット、例えばクロック回路、はかなりの素子(elements)がくっついている。だから、これらは多くのプロセッサにキャッシュされていて、アップデートされると大きな無効化を引き起こす。 典型的には、多くのネットデータは少ない素子（elements）しかくっついてない。だから書き込んでも少しの無効化しか起こらない。 ---- データ構造のためにある free list のヘッドポインタは、大抵は移動する（migratory）ものである。 しかしヘッドポインタは、アイテムを持ってくる前に、free list と照合される。もしリストがからなら、多くのプロセッサはヘッドポインタをキャッシュする。ヘッドポインタは短期間 mostly-read カテゴリにはいる。 PTHOR で起きる無効化のうち、多くの割合を占めるのは、task queue のように働く activation list からのものである。このリストは典型的には多くのプロセッサに横断される（traversed）だから、良く読まれる（mostly-read）カテゴリに入れる。これらもまた大きな無効化の大半の原因となる。 プロセス毎の値は、普通はちいさな無効化の原因となる。各プロセスの最小時間の値を除いて。この値はデッドロックに至っていないかどうか決定しようとするときに、全てのプロセッサに見られている。デッドロックを決定する間に値が書かれて、全てのプロセッサに無効化を起こさせる。 ---- gobal values カテゴリの無効化の中心となる一つの値、これは、いくつのプロセッサがデッドロックに至っているかのカウント。この変数は良く読まれる（mostly-read）カテゴリで、大きな無効化を起こす。 free list から持ってきたあとのデータ構造は、全く無効化を起こさない。 同期の振る舞いは（2-10(e) に示している）要素（elements）のロックによって左右される。これらの分散ロックは、めったに衝突しない。アンロックされる時には、ほとんどの場合は誰も待っていない状態だ。 アンロックされる時の待機者の多くは、Chandy-Misra シミュレーションアルゴリズムで、デッドロックに至っているプロセッサのカウント値を保護するために使う、あるロックに対するものがほとんど全てだ。 ***2.11.7 LocusRoute [#o0965996] 2-11(a) は LocusRoute での無効化の分布を示している。15以上の無効化を引き起こす書き込みがある "tail" 部分があって、目立ってる。普通はこれは良く読まれる（mostly-read）データの傾向です。 LocusRoute では、無効化に対して遙かに大きな原因となるのはグローバルコスト配列である。これは良く読まれる（mostly-read）データの良い例といえるだろう。 これは異なるルートを配線するテストをする間、頻繁に読まれる。しかしルートが決定したときには、一度だけ書かれる。 コスト配列に無効化を起こす書き込みがなされた毎に無効化が起きる、その数の平均はだいたい 3 だ。しかしいくつかの書き込みは 20 以上の無効化を引き起こす。（これらの書き込みが、無効化の分布グラフに現れるのは非常にまれ） ちいさな無効化はより多く見られる（more common）、なぜなら LocusRoute ではコスト配列の領域を共有するプロセッサの数を小さくしたまま維持するための、十分な局所性があるから。 ---- density array というオブジェクトのグループは（2-11(c) と (d) に示した）読んで変更して書く（read-modify-write）傾向なので、単一の無効化を起こす。 ---- 無効化を起こす書き込みのうち、三つ目に大きな原因となるのは、様々なデータ（misc. data）という変数の集まりである。2-11 の (c) と (d) に示した。これはほとんど移動する（migratory）。 この変数のうちよく使われる変数は RouteRecord というもので、これはプロセッサが配線をルーティングするときに使われる。これらは他のプロセッサが他の配線をルーティングするときに再利用される。 そして 0 あるいは単一の無効化が起きる。配線作業に関連したデータ構造に、同じ状況が存在する。これらもまた移動する（migratory）。 ---- global values というグループはグローバル変数の集まりを表している。これらは二つに分けることができる。 グローバルカウント、これは読んで変更して書く（read-modify-write）操作を使って更新されて、移動する（migratory）オブジェクトとして振る舞う。 グローバルフラグ、これは多くのプロセッサから読まれる。しかし変更されるのはまれで、良く読まれる（mostly-read）オブジェクトとして振る舞う。 ---- implicit sync としたグループは、プロセスの同期に使われるフラグを表している。 これらが示すのは、例えばタスクキューが一杯か、空か、とか。このたぐいのデータオブジェクトは普通は良く読まれる（mostly-read）で、大きな無効化を起こす。しかしアクセスされるのは非常にまれで、全体の無効化において大したインパクトは持っていない。 2-11(e) は LocusRoute における同期の振る舞いである。131 のロックがある。そのうち 128 は衝突がまれな分散ロックである。 残る三つのうち 2つだけ、どのプロセッサがタスクキューから目立つ衝突を伴う配線作業を獲得するかを制御するのに使う。しかしそれを使うのはまれだから問題にはならない。 ***2.11.8 Cholesky [#t216ca0d] コレスキーだと 1より大きいサイズではほとんど無効化が起こらない（2-12(a)に示している）。なんでかというと計算の間、各アップデートにおいては因数分解される行列のパネルは「読んで、変更して、書く（read-modify-write）」という操作を受けるから。 一度全てのアップデートが完了したら、パネルはプロセッサが読む（もっと先のアップデートのために使う）が、もう決して書かれることはない。2-12(d) で、ほとんどの無効化が因数分解される行列のパネルを更新することによって起きていることがわかる。 無効化の次の原因は、incoming count の配列である。これはスーパーノードが更新を終えたときを決定するために使われる。このデータはパネルを変更したプロセッサによって更新され、またたいていは排他的で単一の無効化を引き起こす。done flag と task queue がラベル付けされたデータは、何も無効化を起こさない。 コレスキーの同期処理は 2-12(e) に示している。256 の列のロックがあって、ごくまれにしか衝突しない。たまに、いくつかのプロセッサが同じ列を更新したときは、一つか二つの待機者がいる。 残ったロックは、タスクキューにアクセスをする。そして多くの待機者が居るアンロック全ての原因となる。（意味不明） 特徴的なアンロックの数（約 40〜55 の待機者）がある。これが示すのは、解くべき問題が 64プロセッサにしては小さすぎて、ロードバランスがとれないことである。 ***2.11.9 Barnes-Hut [#p6f02835] Barnes-Hut アプリケーションは特徴的で、移動するデータ（migratory）が比較的少ない。プロセッサでなされるほとんどの計算は、プロセッサ自身にある部分的なデータセット（良く読まれる（mostly-read）データ）上で行われる。 時間が経つ間、データが書かれて、その結果大きな無効化が起きる（2-13(a) を見れ）。 Barnes-Hut の主なデータ構造はセルと粒子のツリーです。これを粒子とセル（これをノードデータとする）、リンク（これをツリーとする）、ルートに分割する。これが global なデータグループの部分である。 ---- 無効化の大部分はノードデータ（良く読まれる（mostly-read）データ）のせいです。 次に大きい要因は、セルと粒子のツリーを作るためのリンク構造によるもの。これらの構造も良く読まれる（mostly-read）データで、比較的まれにだが非常に大きい無効化を引き起こすぜ。 最後はグローバルデータの集合であるよ。この集合は二つのグループ、「カウンタの集合」と「セルと粒子のツリー構造のルート」に分割されるよ。 カウンタは常に読まれて、変更されているから、単一の無効化の原因にしかならない。 ツリーのルートは良く読まれる（mostly-read）データで、非常に大きい無効化の大部分の原因になるよ。でもこの構造体もまれにしかアクセスされないし、全体の無効化の数としては小さい。 ---- 2-13(e) は Barnes-Hut の同期の振る舞いを示しているぞ。アプリケーション中には 532 以上のロックが見つかる。529 の分散ロックは粒子とセル構造を守るためにある。各ロックはさまざまな粒子とセルによって使われる。 ツリーの下の方にあるこれらのロックは、ほぼ衝突がない。が、高い位置にあるノード、特にルートノードのロックはいくらかの衝突がある。 三つのロックがグローバル構造体を守るために残っている。これらのなかでも、グローバルカウンタを守っているロックだけは、多くの衝突がある。 ***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] 書こうとしたら、塚田君とかぶってたぜ！
