Adaptive な局所ごみ集め戦略

前節の結果を受けて, 我々はシステムがadaptiveに局所ごみ集めか同期するか しないかを選択するスケジューリング戦略を探求する. adaptiveな戦略では, システムは二つのごみ集めモードを持っている.

independent mode

各プロセッサは独立ごみ集めを行なう

synchronized mode

各局所ごみ集めは全体のバリア同期を行なう

基本アイデアはプログラムがレイテンシに敏感なセクションを走っている時に は同期をしてやり, 一方レイテンシに耐性がある時には同期をしないことである. 現在の主な問題はプログラムがレイテンシに耐性があることを どのように検出するかである. 正確な判断はもちろん難しい問題である. しかし, 幸運にも, 前節の結果はかならず同期するデフォルト戦略が 少なくとも安全であることを我々に教えてくれる. adaptiveなスケジューリング戦略の設計基準は

1. デフォルトでは同期する(起動時もしくはわからない場合)
2. プログラムがレイテンシに耐性があると システムが確信したときには, 独立モードに入る
3. もしそれが実際には悪い選択のときは, すぐさま独立 モードから回復する

2.では, 現在同期モードのアプリケーションが実際に レイテンシに耐性があるかどうかを, 各プロセッサが あるインターバル中に何回アイドル状態に入ったかを 調べることによって検出している. アイドル期間の数から, 各プロセッサは アイドル期間が受信プロセッサの局所ごみ集め期間 と衝突したときに性能がどれくらい落ちるかを後で述べる確率によって計算する. 各プロセッサはこの数(degrade factor)とプロセッサ使用状況をマスタに報告する. マスタは, もしほとんどのプロセッサが小さいdegrade factorを 報告したときは, アプリケーションが現在はレイテンシに耐性があると推測する.

より正確に言えば, システムが現在同期モードにあり, 同期局所ごみ集めに入ろうとしているとしよう. 各プロセッサについて, L を前回と今回の同期ごみ集めの 間の時間とし, n をそのプロセッサがその期間にアイドルになった回数とする. この期間の degrade factor D を次で定義する.

ここで G は一つの局所ごみ集めの推定時間であり, p = G / (L + G) は与えられた通信が目的プロセッサの 局所ごみ集めによって遅れる確率を近似する. もし一つの推定局所ごみ集め時間が G ならば, 受信プロセッサが 偶然局所ごみ集めをしているときの平均追加遅延は G/2 である. np と G/2 をかけ算することによって, もし最後の インターバルが独立モードにあった場合に課される総合追加遅延を 得ることができる. まとめると, D は, もし 最後のインターバルが独立モードにあったと仮定したときに, それはどれくらい影響されたか, 表している.

D とともに, プロセッサ使用状況もマスタに集められる. マスタは次の場合に, 独立ごみ集めがより望ましいと推測する.

1. ある閾値(現在の実装では 0.3)よりも大きい D を 報告するプロセッサの数がまた別のある閾値(現在の実装では全 プロセッサ数の八分の一)よりも小さい, かつ
2. 閾値(現在の実装では 0.5)よりも小さい使用状況 を報告するプロセッサの数がまた別のある閾値(プロセッサの数の 半分)よりも小さい

条件1.はレイテンシの増加によってほとんどのプロセッサが ダメージを受けず, ゆえに, レイテンシに耐性があることを言っている. 条件2.は多くのプロセッサがアイドルであり, 各プロセッサの 局所ごみ集めを全体で同期をとって行なうことがほとんど問題外で ある場合を排除している. そのような場合では, 安全のために同期局所ごみ集めを選択する.

一方, システムが独立モードで走っているときは, 各プロセッサは めいめいが独立ごみ集めの後に自分のプロセッサ使用状況をチェックする. もし使用状況が閾値(= 50%)よりも低いならば, プロセッサはマスタにそのことを知らせる. マスタは それらの知らせが事前に決められた値まで蓄積された時に 同期モード戻ることを決定する.

実際の状態変化は 3つ (-1,0,1) の状態をもつ飽和カウンタによって 制御される. もしシステムが独立ごみ集めがより望ましいことを 検出したときは, カウンタを減らし, そのカウンタが -1 に なったら独立局所ごみ集めモードにスイッチする. これはアプリケーションがレイテンシに耐性がある部分と レイテンシに敏感である部分を行ったり来たりするときに, 二つのごみ集めモード間を行ったり来たりすることを防ぐ. 一方, システムが独立モードにあり, アプリケーションがレイテンシに耐性があることを 検出したときには, カウンタを直接 1 にセットし, すぐに同期モードに戻る.

         図3.17: Barnes-256 におけるadaptiveな局所ごみ集めの影響. 
                 AS は同期戦略から始めるadaptiveなスケジューリング, 
                 AI, FS, FI はそれぞれ, 独立戦略から始まるadaptiveな
                 戦略, 固定同期戦略, 固定独立戦略である. 

         図3.18: RNA-256 におけるadaptiveな局所ごみ集めの影響. 
                 ラベルの意味は図3.17と同じ. 

         図3.19: GA-256 におけるadaptiveな局所ごみ集めの影響. 
                 ラベルの意味は図3.17と同じ. 

図3.17から図3.19は adaptiveなスケジューリング戦略と 二つの強制されない全体ごみ集めを装備した固定戦略(例えばSGとIG)を比較している. システムが本当に正しい戦略を選択しているかどうかを確認するため, adaptiveなスケジューラに対し, 両方の戦略をadaptiveな 戦略の最初の戦略として試している. 我々は全部で次の4バージョンを持っている.

AS:

同期戦略から始まるadaptiveなスケジューリング

AI:

独立戦略から始まるadaptiveなスケジューリング

FS:

固定同期戦略

FI:

固定独立戦略

Barnes と GA では, 初めの戦略に関わらず, adaptiveなスケジューリングが 4つの中で最適もしくは最適に近い性能を実現している. アプリケーションの transcript から, 我々はアプリケーションを通じて, アプリケーションの非常に初めの期間を除いては, Barnes が同期戦略を選び, GA が独立戦略を選ぶ ことも確認している. RNA については, 二つの adaptive な戦略が同じ性能を示さなかった. 我々はこれは RNA 固有の非決定性からくるもの だろうと推測している. 我々はtranscriptを調べ, 両方のバージョンが独立モードを選択し, 一旦選択されたならば, たくさんのプロセッサが 負荷の不均衡によってアイドルになる, 探索のほとんど終わりに 近いところまで独立モードであり続けることを確認した. ゆえにシステムはアプリケーションがレイテンシに耐性があることを ことを検出し, 実際そうである.