固定スケジューリング戦略

 

次に我々はアプリケーションの性能が様々なごみ集め戦略によってどのように 影響されるのかを調査した. この節は特に4つの固定戦略を調査する.

SG:

強制されない全体ごみ集めありの同期局所ごみ集め

SNG:

強制されない全体ごみ集めなしの同期局所ごみ集め

IG:

強制されない全体ごみ集めありの独立局所ごみ集め

ING:

強制されない全体ごみ集めなしの独立局所ごみ集め

「強制されない全体ごみ集めあり」とは, 全体ごみ集めがデフォルトのスケジュー リング戦略によって起動されることを意味する. 「強制されない全体ごみ集めな し」では, 全体ごみ集めは局所領域確保が失敗したときのみ起動される. 局所 領域確保が失敗したときには, 我々はすぐに, 「緊急の全体ごみ集め」をマスタープロセッサに対して要求する .

         図3.13: Barnes-32 におけるごみ集め戦略の影響. SG は同期ごみ集め+
                 (強制されない)全体ごみ集めを意味する. SNG, IG, ING はそれぞれ, 
                 強制されない全体ごみ集めなしの局所ごみ集め, 強制されない全体
                 ごみ集めありの独立ごみ集め, そして強制されない全体ごみ集めなしの
                 独立ごみ集めである. グラフは, どれだけの時間がユーザ(ビジー), 
                 ユーザ(アイドル), 全体ごみ集め(ビジー), 全体ごみ集め(アイドル)
                 に費やされているかを示している(下から上へ). 

         図3.14: Barnes-256 におけるごみ集め戦略の影響. 
                 ラベルの意味は図3.13と同じ. 

         図3.15: RNA-256 におけるごみ集め戦略の影響. 
                 ラベルの意味は図3.13と同じ. 

         図3.16: GA-256 におけるごみ集め戦略の影響. 
                 ラベルの意味は図3.13と同じ. 

図3.13から図3.16は Barnes-32, Barnes-256, RNA-256, GA-256 における様々なスケ ジューリングポリシーの性能への影響を明らかにしている. RNA-256 について は, 我々は同じ戦略を 5 回走らせ, 平均をとっている. 常に他を上回る明らか な勝者はないが, いくつかの有用な発見が得られた.

• 独立局所ごみ集めは, ユーザアイドル時間を増加させることによっ て, Barnes の性能をかなり低下させる. これは, Barnes は, ノード内の並列 性なしで, 頻繁に通信を行ない, それゆえに非常にレイテンシに敏感であるア プリケーションであるからである. 独立局所ごみ集めでは, 各プロセッサは 予測不可能な形で, 無反応状態になる. 局所ごみ集めをしているプロセッサに 対して要求を出した不運なプロセッサは, 受信プロセッサが現在の局所ごみ集め を終わるまでアイドル状態のままになる.
• GA については, 独立局所ごみ集めは, 局所ごみ集めのコストの低下に より, わずかだが, 一貫して同期ごみ集めよりもよい. RNA については, 同期ごみ集めも, 独立ごみ集めも一貫して他よりもよい. 実際のところ, RNA の性能は同じ戦略によってさえも, 走らせるごとに 10 % ほど変化する. ゆ えに, RNA については, 実際により適切な戦略を結論づけることはできない.
• 独立ごみ集めが勝つときには, 差はわずかである. どんな環境でこれが成り立つの か検証してみよう. プロセッサの確保の割合がかなり均一化されている場合は, 同期ごみ集めは必要になるよりもわずかに早くごみ集めを起動するだけであり, ごみ集め器にほとんど余分な仕事を加えない. ペナルティは主としてマ スタに加えられるが, オーバヘッドは, それでもなお, 一つのメッセージを送 るだけである. 初期化フェーズで典型的に起こるように, 確保の割合が 非常に不均一になると, 忙しくないプロセッサはそうでなければ全く必要でなかった マーキングを行なわなければならない. 幸運にも, そのような環境では, 典型 的に, アプリケーションのクリティカル・パスが忙しいプロセッサに存在 し, 忙しくないプロセッサに仕事を追加することが全体に影響を与える ことはないと思われる. ゆえに, 独立ごみ集めのマージンは(もしあれば)非常に 広い範囲のアプリケーションにおいて小さいと思われる.

これらの考察から, 並列アプリケーションにおいては, 同期局所ごみ集めを 「デフォルト」の戦略として採ることが合理的である. 少なくとも広い範囲のア プリケーションに対してより安全であり, より頑強である. これが我々の実験 から引き出される主な結論であり, 独立ごみ集めが必要で, 良いことであると いう従来信じられてきた事実と矛盾する.