導入

多くの高性能並列プログラミング言語とその実装技術が研究されてきているが, 大規模並列計算機におけるごみ集めの性能についてはまだよく理解されていな い. 特に, 分散メモリ並列計算機におけるごみ集めの性能に関する研究は少な いが, これはおそらく実装の困難さによるものと思われる.

本研究では, 大規模分散メモリ並列計算機上の単純なごみ集めの設計と実装に ついて述べ, その性能を測定する. 特に, 局所ごみ集めと全体ごみ集め の様々なスケジューリング戦略が性能に与える影響を調べ, 様々なアプリケー ションの挙動に対してよい性能を与える効率的でadaptiveなスケジュー リング戦略を提案する. 我々のごみ集め器は, ごみ集めは非同期局 所(独立)か, 同期局所か, 全体である. 非同期局所ごみ集めは 各プロセッサが他のプロセッサとまったく協調することなしに局所的なごみを回収 する. 同期局所ごみ集めはすべてのプロセッサが同時に局所ごみ集めを行なう. 最後に, 全体ごみ集めは, すべてのプロセッサが協調して全体のオブジェクト が形づくるグラフを探索し, 遠隔ポインタをたどるためにマークメッセージを 交換する分散マーキングごみ集めである. 二つの局所ごみ集めはそれらがどう スケジュールされるかという点のみが異なる. 非同期ごみ集めは他のプロセッ サに全く知らせを送らずに起動される. 一方, 同期ごみ集めはすべてのプロセッ サに知らされ, すべてのプロセッサはごみ集めに集中する.

我々は様々な領域確保と通信の動作を行なう三つのアプリケーションを用 い, 様々なタイプのごみ集めの性能の特徴を調査した. 実験から導かれる結論 は次のことを含んでいる.

• アプリケーションの全体の性能は領域確保/回収それ自体の性能 ばかりでなく, ごみ集めがどうスケジュールされるかにも影響される. 特に, 多くの同期的な通信を行ない, ほとんどノード内の並列性を持たない同期的な アプリケーションは, 独立局所ごみ集めによってひき起こされる平均レイテン シの増加に非常に敏感である.
• 同期局所ごみ集めと全体ごみ集めの同期コストは, たとえ単純な1対Nのメッセージ送受信があったとしても, 少なくとも256プロセッサまでは(分散メモリ並列計算機AP1000+  [22] ), それほど大きくはない. これは我々は決して独立局所 ごみ集めを行なわず, 同期局所ごみ集めや全体ごみ集めのみを 起動するという「安全」なごみ集め戦略に我々を導く.
• さらに進んだ戦略として, 我々は, プロセッサのCPU使用状況に応じて adaptivelyに非同期局所ごみ集めと同期局所ごみ集めの 間をスイッチする. 我々はCPUがア イドルやlatency sensitiveの時は同期ごみ集めを奨励し, アプリケーションが latency-tolerantの時は独立ごみ集めを奨励する.
• 全体ごみ集めのコストは大きくない. 256台のプロセッサ上では, それ は最悪の場合で全体の実行時間の20%を占めるだけである. 3.3.2節で 並列および分散環境におけるごみ集 め方法についてのこれまでの研究を概観する. 3.3.4節には実験結果を示す. 他の選択肢と制限を 3.3.5節で議論したのち, 3.3.6節でまとめを行なう.