全体ごみ集めのオーバヘッドの解析

         図3.12: 一回のごみ集めのオーバヘッドの分割. 256 プロセッサ上の
                 Barnes-256 において 10 回のごみ集めの平均をとった. これは
                 同期, 未配送のメッセージ中の参照の発見, 局所マーキング, 
                 遠隔マーキング, アイドルに費やされた時間を示している. 

図3.12は全体ごみ集めのオーバヘッドが比較的大きい Barnes-256 の各フェーズで 費やされている時間を分解している. Barnes-256 では, エントリテーブルは 5000 エントリまで拡大され, 各プロセッサは全体ごみ集めが起動されるまでに 約 4500 個のオブジェクトを輸出する.

グラフのフィールドは,

Sync:

起動時の同期

Undelivered:

プロセッサ間で輸出カウントを交換するのと未配送のメッセー ジによって参照されているオブジェクトを発見するのに費やされた時間

Local:

局所マーキングに費やされた時間

Remote:

エグジットテーブルをスキャンするのとマークメッセージを送るのに 費やされた時間

Idle:

ごみ集め中のアイドル時間(ロードおよびフロー制御のアンバランス によってひき起こされる)

である.

グラフは一つの全体ごみ集めの平均停止時間が約 1700 ミリ秒であり, 非常に多 くの時間が遠隔マーキングに費やされていることを我々に教えてくれる. すで に3.3.3 (4)節で述べたように, 各プロセッサは局所探索フェーズと遠隔マークフェー ズの間を粗粒度に交替で行なう. プロセッサは局所マーキングを集中して行な い, 局所マーキングができなくなったとき, 直前の局所マークでマークされた スタブのためのマークメッセージを送信する. 我々の現在の実装では, この遠 隔マーキングは, ただ単に各局所探索後にエグジットテーブル全体をスキャンするだけ である. この決定は局所ごみ集め器がスタブについてまったく知識を持たない ことによってなされているが, それが性能を制限することも明らかになっ ている. エグジットテーブルはプロセッサ数と同じ個数のハッシュ表からなり, 各ハッ シュ表は 128 個のエントリを持っている. 簡単な実験によって, 全体ごみ集め の終わりの段階では, ほとんど新しいオブジェクトが発見されないことがわかっ ている. つまり, 新しくマークされたたった数個のオブジェクトを発見するた めにエグジットテーブル全体がスキャンされる. 将来的な実装では, 新しくマークされ たスタブを含まないエグジットテーブルのエントリをより効率的にスキップするために この性質をうまく利用することになろう.