日本ソフトウェア科学会第 33 回大会 (2016 年度) 講演論文集

X10 用分散ガベージコレクタの耐故障性サポートについての検討河内谷 清久仁並列分散プログラミング言語 X10 の「Managed X10」と呼ばれる実装では，複数の Java 仮想マシン（JVM）を処理
ノードとして用いて分散処理を行える．Managed X10 では，弱参照の仕組みを利用して各 JVM 内のガベージコレ
クタ（GC）と協調動作することで分散 CG を実現している．X10 処理系には最近，複数の処理ノードのうちいくつかが故障した場合でも処理を継続できる「Resilient X10」という拡張が行われたが，既存の分散 GC では，故障したノードから指されていたオブジェクトが自動回収不能になってしまうという問題があった．本稿では，Resilient X10のために必要となる分散 GC の拡張について，その手法と低オーバーヘッド化についての検討を行う．

X10 is a programming language that incorporates distributed processing functions. In its implementation on multiple Java virtual machines, named “Managed X10”, distributed garbage collector is supported by using the weakreference mechanism of Java. Recently, X10 has been extended to support node failures, as “Resilient X10”. However, existing distributed GC cannot collect objects remotely-referenced from dead places. This paper discusses
how to extend the distributed GC to support resiliency, with low additional overhead.

これにより，リモート参照されたオブジェクトも，リ

1 はじめにモートおよびローカル両方の参照が無くなった時点でX10 [18] は言語単体で並列・分散処理を記述可能な

自動回収することができる．

オブジェクト指向プログラミング言語で，複数の処理

大規模な分散実行環境においてはまた，処理ノード

ノード（X10 用語では「プレース」）を用いた分散処の故障への対応も重要である．X10 ではそのために，理を行うことができる．分散環境上でのアプリケー

プレースの消失をアプリケーションに例外として通ション実行モデルとして X10 は「PGAS（Partitioned

知し，残りのノードで実行を継続することが可能な

Global Address Space）[11]」を採用している．PGAS「Resilient X10」という言語拡張を行っている [3] [4]．

実行モデルでは複数の処理ノードにまたがるグローバ

ユーザは，新たに追加された「DeadPlaceException」

ルなアドレス空間が利用可能で，X10 では GlobalRefという例外を処理するか，その例外を内部的に用いるという仕組みにより，他のプレースにあるオブジェ

ライブラリを利用することで，耐故障性のあるアプリ

クトを「リモート参照」することができる [12]．オブケーションを開発できる [6]．

ジェクトは生成されたプレースに固定されるが，リモート参照はプレース間で受け渡し可能である．

しかし，消失したプレースからリモート参照されているオブジェクトがあると，そのオブジェクトは従X10 の実装のうち，複数の Java 仮想マシン（JVM）

来の分散 GC では回収されないという問題があった．

を処理ノードとして用いる「Managed X10 [15]」とこれによりプログラムの挙動がおかしくなることはいうバージョンは分散 GC の仕組みを備えている [7]．

ないが，回収不能なオブジェクトが生じるため，長くExtending Distributed GC for Resilient X10.
This is an unrefereed paper. Copyrights belong to theauthor(s).
Kiyokuni Kawachiya, 日本アイ・ビー・エム（株） 東京
基礎研究所, IBM Research - Tokyo.

走り続けるアプリケーションではヒープが圧迫されていく危険性がある．そこで本稿では，Resilient X10のために必要となる分散 GC の拡張について，その手法と低オーバーヘッド化についての検討を行う．

1

2 耐故障性のある X10 プログラム
図 1 は，Resilient X10 を用いた耐故障性のあるプclass ResilientMontePi {2static val ITERS = 1000000000 / Place.numPlaces(); // 計 10 億回

3

public static def main(args:Rail[String]) {val result = new Cell(Pair[Long,Long](0,0));4

ログラムの例で，モンテカルロ法を用いて π（の近似56val resultRef = GlobalRef(result); // リモート参照を作成

値）を求めている．計算の中心部分は 12〜15 行目の7

finish for (p in Place.places()) async {// (円の内側だった数, 試行回数) のペアを保持する領域

try {

8

for ループで，乱数生成した座標（x, y）が半径 1.0

at (p) {9の円内かどうかを繰り返し判定している．ITERS 回の 10

val rnd = new x10.util.Random(System.nanoTime());
var c:Long = 0;

11

試行が終了すると，プレース 0 の result というデー 12

for (iter in 1..ITERS) { // 各プレースで ITERS 回試行
val x = rnd.nextDouble(), y = rnd.nextDouble();タペアに試行結果が足し込まれる（17〜20 行目）．こ 13

if (x*x + y*y <= 1.0) c++; // 円の内側だった場合

14の一連の処理が各プレースで並列・分散に行われ，す 15}

べて終了するとプレース 0 で result の中身を取り出16

val count = c;

17

at (resultRef) atomic { // 試行結果を足し込む

して集計が行われる（26〜27 行目）．

18

val r = resultRef();r() = Pair(r().first+count, r().second+ITERS);

19

計算中にノードが故障した場合は，そのノードで 20}} // at 文（9 行目）の終わり，プレース消失時は DPE が発生

実行されているプレースが消失し，9 行目の at 文が 21} catch (e:DeadPlaceException) {22

DeadPlaceException で終了する．この例外は 22 行 23目の catch 文で捕捉され，単純に無視される．消失// 消失したプレースの結果は，単純に無視する}24} // finish 文の終わり，全プレースの処理が終わるまで待つ

25

したプレースでは 17 行目の at 文が実行されず，試行 26

val pair = result();
val pi = 4.0 * pair.first / pair.second;27

結果が result に反映されない．そのため，正常ノー 28

Console.OUT.println("pi="+pi + " (try="+pair.second+")");}

ドの試行結果だけを集計することができる．モンテ 29
30}

カルロ法の試行回数が減り精度が下がる可能性はあるが，計算結果が間違ったものになるわけではない．
このプログラムでは，参考情報として試行回数も出力するようにしている．

図1

耐故障性のある X10 プログラムの例

プレース 2 を消失させている．Resilient X10 上での実行は通常の X10 より 9%程度遅くなるが，プレース

このプログラムでは，result というオブジェクト

消失時にも予備プレースが追加され処理を継続できが各プレースからリモート参照されている．プレースていることがわかる．しかしこの際，消失したプレーが消失した場合，上述のように処理自体は継続するこ

ス中のリモート参照から指されていたデータが回収とが可能であるが，分散 GC は，消失したプレースかできなくなってしまう．この例では，元データである

らの参照が残っていると判断するため，このオブジェ

100 万個の点の値が分散配列に入っており，それが丸クトが回収不能になってしまう．この例ではプログラ

ごと回収不能になる．そのサイズは約 24MB である．

ムがすぐ終了するので問題ないが，サーバプログラム

そのため，この Resilient M3R エンジンがそのまま別のように長く走り続けるものでは，ヒープが徐々に圧の処理に再利用されると，同様のメモリリークが積も迫されていく危険性がある．

り積もってヒープ不足を起こしてしまう可能性があ

たとえば図 2 は，X10 で記述された MapReduce エ
ンジン「M3R [14]」の簡易版に耐故障性を追加した

る．これでは処理系に耐故障性を追加した意味が薄まってしまう．

ものの上で，K-Means 法 [17] によるクラスタリングを行った例である．100 万個の 3 次元の点を 8 つの3 分散 GC の概要と耐故障性サポート

クラスタに分類する処理を，7 つのプレースを使ってManaged X10 用の分散 GC は，Java の弱参照 [10]結果が収束するまで繰り返し行っている．グラフは，の仕組みを利用して各 JVM 内の GC と協調動作する

各繰り返し（イテレーション）における処理時間で，ことで実現されている [7]．図 3 は，そのために用いResilient X10 では 200 イテレーション目で意図的にられる内部データ構造を示したものである．

各イテレーションの処理時間 (msec)

Resilient  X10上の実行では，
ここでプレース2を消失させている
従来の分散GCでは，
ここで約24MBリークしてしまう

X10ランタイムの再構成に約5秒

Resilient  X10

予備プレースがデータを読み込むのに約1.5秒

Normal  (non-­resilient)  X10イテレーション番号

図2

耐故障性のある MapReduce エンジンの実行例

XRJ:  X10  Runtime  in  Java

モート参照数が 0 になった場合，このフィールドには null がセットされ，ローカルな参照も存在しない

プレース0
g

g’  (リモート参照)

o

obj

プレース1

場合は JVM 内の GC によりオブジェクトが回収され

obj=null

home=P0

home=P0

id=123

id=123

る．すると，弱参照の仕組みにより GOT にオブジェ
クト回収が通知されるので，X10 ランタイムが不要とGOT  for  oid2got123

got2id123

XRJ

なった内部データ構造の回収を行う．

RRT  for  g ’

weakRef

weakRefstrongRef

home=P0rCnt=10

id=123

id=123wCnt=10

rrtTable

JVM0

RRT（Remote Reference Tracker）は，オブジェク
トのリモート参照（図では g’）ごとに用意される †2
XRJ
JVM1

ネットワーク

図3Managed X10 の分散 GC が用いる内部データ構造

内部データ構造で，以下のフィールドを持つ．
• weakRef — そのリモート参照への弱参照 †1 ．

• home — そのリモート参照の指すオブジェクトの存在するホームプレース．

GOT（Globalized Object Tracker）は，リモート参照されたオブジェクト（図では o）ごとに用意される内部データ構造で，以下のフィールドを持つ．
• weakRef — そのオブジェクトへの弱参照 †1 ．

• strongRef — リモート参照数が 1 以上の場合，そのオブジェクトへの参照を入れる．

• remoteCount — そのオブジェクトへのリモート
参照数（重み付き）．

• id — そのオブジェクトのプレース内でユニークな ID，GOT 生成時に割り当てられる．

• id — そのリモート参照の指すオブジェクトのID．
• weightCount — そのリモート参照に割り振られている「重み」．
リモート参照が使用されなくなり JVM の GC によって回収されると，弱参照の仕組みにより RRT に通知される．この通知により X10 ランタイムが，不要となった内部データ構造の回収と，対応する GOT（home とid から決定）のリモート参照数（remoteCount）を減らす処理を行う．なお，weightCount はリモートオブジェクト o が他のプレースからリモート参照さ

参照に割り当てられたカウントの「重み」で，1 以れている間は，strongRef フィールドからそのオブ上の値を保持する．X10 の分散 GC では，GOT のリ

ジェクトを参照することで，JVM 内の GC によりそ

モート参照数の増減回数を減らすために重み付き参のオブジェクトが回収されることを抑制している．リ

照カウント [2] [16] の手法を導入しており，このフィールドはそのために使われる．

†1 正確には，GOT や RRT は java.lang.ref.WeakReference の子クラスであり，weakRef というフィール
ドがあるわけではない．

†2 同じオブジェクトを指すリモート参照はプレース内では一つにまとめられるので，RRT も一つでよい．

プレースが消失した場合にリモート参照されたオブする一つの方法は，リモート参照を送る前に S から H

ジェクトが回収不能になる原因は，GOT 内のリモーにメッセージを送り，GOT の remoteCountArray[R]ト参照数の保持方法（remoteCount）にある．ノード

をインクリメントすることである．しかし，この手法

故障によりプレースが消失すると，その中の RRT がでは H でのインクリメント完了を待ってからでない

保持していた weightCount の情報も同時に失われるとリモート参照が送れないため，非常にオーバーヘッ

ため，GOT 内のリモート参照数をいくら減じればよ

ドが高くなってしまう．

いかわからなくなってしまう．そのため，リモート参そこで，オブジェクトの回収を抑止する別の方法と照数が 0 になることがなくなり，オブジェクトが回収して，リモート参照を管理する RRT に「そのリモー不能になってしまうのである．

ト参照を他プレースへ送信中である」ことを示す以下

この問題を解決するには，リモート参照数を「合の配列フィールドを追加する．

計」として保持するのではなく，各リモートプレー• sendingCountArray[NPLACES] — そのリモー

スごとに個別管理するようにすればよい．すなわち，

ト参照を，各プレースに何個「送信中」であるか

GOT 内の remoteCount フィールドを，以下の配列に置き換える．

• remoteCountArray[NPLACES] — そのオブジェのカウント．
この配列に 0 でないエントリがある場合は，RRT 削除の処理を遅延させる．これにより，オブジェクト O

クトへの，プレース別のリモート参照数．

の回収を抑止できる．この手法では，S はリモートプレースが消失した場合は，この配列の対応するエ

参照を R に送る前に sendingCountArray[R] をイン

ントリをゼロクリアし，すべてのエントリが 0 になっ

クリメントするだけでよく，ホームプレース H と通ている場合は GOT の strongRef フィールドを null

信する必要はない．S からリモート参照を受け取ったにすることで，JVM の GC によるオブジェクト回収

プレース R は RRT を作成し，そのことを非同期メッが可能になる．

セージでホームプレース H に通知する．H はこのメッ

ただしこの方法では，リモート参照をプレース間

セージを受け取ると，対応する GOT の remoteCount-で送受信する際に必ず，対応する GOT の remote-Array[R] をインクリメントし，送信元プレースの S

CountArray を修正する必要があり，参照先オブジェに非同期メッセージを送る．S はこのメッセージを受クトの存在するホームプレースとの同期通信が発生してしまう †3 ．この余計な通信は，リモート参照をけ取ると，対応する RRT の sendingCountArray[R]用いる X10 プログラムの性能を大きく低下させる危→受信側プレース R →ホームプレース H →送信側プ

険性がある．次節では，この問題を解決するための手

レース S，と循環する通知を非同期メッセージで行う法について検討する．

ことにより，低オーバーヘッドで全体の整合性を保証

をデクリメントする．このように，送信側プレース Sすることができる．

4 効率のよい実装の検討

プレース P が消失した場合の，残った各プレース

ホームプレース H（home）にあるオブジェクト O

での処理は以下のようになる．まず，たまっているリのリモート参照を，プレース S（sender）からプレー

モート参照関係の通信を全プレースが処理し終える

ス R（receiver）に送る状況を考える．S から送られまで待つ．これは，P に関わるメッセージが後から届たリモート参照を R が受け取る前にプレース S のリ

き状態が不整合になることを防ぐためである．次に，モート参照が無くなると，プレース H にそれが通知

自プレースにある全 GOT について，remoteCount-

され O が回収されてしまう危険性がある．これを回避

Array[P] をゼロクリアする．これにより配列のエン†3 従来の分散 GC では，重みを分配して送ればよかった
ので，RRT の weightCount が 2 以上であればホームプレースとの通信は不要であった．

トリがすべて 0 になった場合は，strongRef フィー
ルドを null にしてオブジェクトの回収を可能にする．
さらに，自プレースにある全 RRT について sending-プレースS (sender)
1  RRT.sendingCountArray[R]++
プレースR (receiver)2  リモート参照をRに送信:
3  Sからリモート参照を受信すると…
:
4  対応するRRTが無かったら作る:
5  RRT.weightCount++
プレースH (home):
6  プレースHに通知
7 Rから通知を受信すると…
:
8  対応するGOTの，GOT.remoteCountArray[R]++:9  プレースSに通知:
10  Hから通知を受信すると…
11 対応するRRTの，RRT.sendingCountArray[R]-­-­
12  RRTを削除できるかチェックする

図4

循環通知法を用いたリモート参照の送受信

CountArray[P] をゼロクリアし，配列のエントリがすべて 0 になった場合は，RRT を削除できるかチェッ(a) 初期状態
プレース0

オブジェクトプレース1
リモート参照クする．もし，そのリモート参照のホームプレース

home=P0
id=123（home）が P だった場合は，sendingCountArray のすべてのエントリをゼロクリアし RRT を削除できる

RRT

GOT
weakRef

weakRefstrongRef
remoteCount
id

かチェックする．

プレース2

home
0      1      0
123

XRJ0

Place0id

123

weightCount1

sendingCount0      0      0

XRJ1

XRJ2

図 4 に，提案する「循環通知法」を用いてリモー
ト参照を送る場合の各プレースでの処理内容をまとめた． 図 5 は，その処理にともなって X10 ランタ(b) ステップ 5 まで終了した時点
プレース0

イムの内部状態がどう変化するかを示したものである †4 ．(a) は初期状態で，オブジェクトのリモート
参照はプレース 1 にだけ存在している．ここから，オブジェクトhome=P0

GOT
weakRef

プレース2
リモート参照2  send0      1      0
123

XRJ0

home=P0

id=123

id=123RRT

RRT

weakRefstrongRef
remoteCountid

リモート参照をプレース 2 に送りステップ 5 まで進プレース1
リモート参照weakRefhome

Place0home

Place0

id

123

id

123

weightCount1

weightCount1

sendingCount0      0      1sendingCount0      0      0

XRJ1

XRJ2

んだ状態が (b) である．プレース 0 にある GOT の

remoteCountArray[P2] はまだ 0 だが，プレース 1にある RRT の sendingCountArray[P2] が 1 である(c) ステップ 8 まで終了した時点
プレース0

オブジェクト

プレース1

プレース2
リモート参照ため，元のリモート参照がローカル GC で回収されて

home=P0
id=123もこの RTT は削除されない点に注目してほしい．これにより，リモート参照の送信中にオブジェクトが回weakRef

RRT

weakRefstrongRef
remoteCountid

収されてしまうのを抑止できる．その後，プレース 2

RRT

GOT

0      1      1
123

XRJ0

weakRefhome

Place0id

123

weightCount1

sendingCount0      0      1home6  notify
XRJ1

id

Place0123

weightCount1

sendingCount0      0      0XRJ2から 0 への通知が行われ，ステップ 8 まで進んだ状
態が (c) である．GOT の remoteCountArray[P2] がインクリメントされ 1 になっている．ここからさら(d) ステップ 11 まで終了した時点
プレース0

オブジェクト

プレース1

プレース2
リモート参照に，プレース 0 から 1 への通知が行われ，ステップ 11

home=P0
id=123RRT

GOT
weakRef†4 この図では，プレース 0（home）のオブジェクトのリモート参照をプレース 1 （sender）からプレース 2（receiver）に送る場合を例に説明している．GOT や
RRT 内の配列フィールドは，左からプレース 0, 1, 2に対応している．

weakRefstrongRef
remoteCount
id

RRT0      1      1123Place0

id

123

id

1

weightCount1

sendingCount0      0      09  notify
weightCountsendingCount

XRJ0

図5

weakRefhome0      0      0

home

XRJ1

X10 ランタイム内部の状態変化

Place0123

XRJ2

まで進むと (d) の状態になる．プレース 1 の RRT のが中途半端に終わってしまった場合（登録したが参照

sendingCountArray[P2] がデクリメントされ，0 にを送る前に送信ノードが故障したなど）のつじつまあなっている．これにより配列のエントリがすべて 0 にわせのために，定期的にノード同士が情報交換する必なったので，この後，遅延させられていた RRT の削要がある．我々の手法では，「登録」は非同期メッセー

除処理が行われる．その結果，GOT の remoteCount-ジで行われ完了を待つ必要がない．また，つじつまあ

Array[P1] が 0 になるが，remoteCountArray[P2]

わせの情報交換も不要である．

が 1 になっているため，オブジェクトは回収されない．

Shapiro の提案した低オーバーヘッドで耐故障性の提案する循環通知法（図 4）では，リモート参照をある分散 GC [13] では，リモート参照はすべて ODT送るためのプレース S から R への通信に加え，R か（Object Directory Table）というテーブルに登録さら H，H から S への通信が追加で必要となるが，これており，GOT や RRT のようなオブジェクトごと・れらはいずれも非同期通信であり結果を待たなくてノードごとのデータ構造としては管理されていない．

よいため，性能低下は最小限ですむと期待できる．一

このシステムではオブジェクトを他のノードに移動で方で，プレース消失時は，たまっているメッセージのきるが，移動するオブジェクトがリモート参照を持つ処理を待ったり，GOT や RRT を全部チェックするな

場合，送信側ノードに「○○に移動した」という情報

どの処理が必要となる．つまりこの手法は，オーバーを残すことで，ホームノードとの通信を不要にしていヘッドをプレース消失時の処理に押しつけることで，る．しかし，リモート参照が多段リンクになってしま

通常処理のコストをなるべく増やさない実装である

い，中間のノードが故障した場合はつじつまあわせのととらえることができる．

ために全ノードから情報を集める必要がある．また，
このような多段リンクによるリモート参照方式は一5 関連研究般的でなく，PGAS 実行モデルにもとづく X10 では

分散システムにおける GC の研究の歴史は古く，採用しづらい．

ノード故障への対応についても様々な手法が提案されてきている．

分散プログラミング言語 Emerald [5] では，分散GC もインクリメンタルマーク＆スイープで行っておMancini らの手法 [9] は，他ノードへエクスポート

り，ノード故障時もオブジェクトを問題なく回収できされたオブジェクトの情報を各ノード内でリストとる．しかし，インクリメンタルマーキングのためにオして保持しており，各ノードのローカル GC はそこ

ブジェクトが「グレー」な状態であることを扱える必も GC ルートとして扱うことで，リモート参照され要があり，各ノード上のローカル GC が分散 GC とているオブジェクトの回収を防止している．そして，密接に連携する必要がある．そのため，JVM 内の既ローカル GC によりリモート参照が削除された場合，存 GC を変更せずに用いる Managed X10 で利用する

その情報を他ノードに配り，上記リストの修正を行っことは難しい．

ている．これらの実現のためにはローカル GC の修

Allen らの提案する手法 [1] では，オブジェクトの正が必要になるため，JVM 内の既存 GC を用いる

リモート参照は [9] と同様リストとして管理されておManaged X10 ではそのまま利用できない．

り，オブジェクトごと・ノードごとのデータ構造にはノード故障に対する処理は彼らの RPC 機構と組なっていない．また， [5] と同じく，ローカル GC でみ合わせて行うことが前提になっており，これも，オブジェクトを「グレー」にするという処理が必要

X10RT のような非同期メッセージベースのランタイ

で，既存の GC を変更せず使うのは困難である．リ

ムではそのまま利用できない．リモート参照を他ノー

モート参照を送る際に，上記リストをどのように更新ドに渡すには，まずオブジェクトの存在するホーム

するかについては言及が見あたらないが，おそらくノードと同期通信して上記リストに登録する必要が[9] と同様にリストを同期的に更新してから送っていあり，コストが高いと考えられる．さらに，この登録ると思われる．

他には，ノード間の参照情報をすべて中央で集中管理するという手法 [8] もある．この方法ではリモート参照を一望できるためノード故障時の対応が行いやすいが，リモート参照ができる時や渡される時に，この集中管理サービスへの同期的な登録が必要なため，コストが高いと思われる．

6 おわりに本稿では，Resilient X10 のために必要となる分散

GC の拡張について，内部データ構造の一部をノード（プレース）別の配列として持つことでノード故障に対応できることと，「循環通知法」によりリモート参照の送受信を少ない追加オーバーヘッドで行えることについて述べた．これらの拡張により，X10 のノード
故障への対応がより完全なものとなり，大規模分散システム上での商用利用が加速されることを期待している．
最後に，本稿で提案した耐故障性のある分散 GC の
特長をまとめる．
特長 1. 既存の GC（各 JVM 内の GC）を変更せず
ローカル GC として用いることができる．
そのために，「オブジェクト回収を防止」するかど
うかのフラグ（GOT 内の strongRef）を用意し，そのフラグをオンオフするためにリモート参照数のカ
ウンタをオブジェクトごとに用意した．このカウン
タを，リモートノードごとに別エントリを持つ配列（remoteCountArray[NPLACES]）として持つことで，リストをスキャンしたり参照状況を再構成する等の処理を不要とした．
特長 2. リモート参照送受信の追加オーバーヘッドが少ない．
そのために，「リモート参照を送信中である」ことを示すデータ構造（sendingCountArray[NPLACES]）を用意し，同期通信を追加せずリモート参照を受け渡しできる「循環通知法」を提案した．既存手法では，オブジェクトの存在するホームノードに同期通信を行ってからリモート参照を渡しているものがほとんどであるのに対し，本手法は非同期通信の追加だけでよいので低オーバーヘッドである．

参考文献[ 1 ] Allen, N. and Terriberry, T. B.: System Description
for a Scalable, Fault-Tolerant, Distributed Garbage Collector, arXiv, Vol. cs.DC/0207036(2002).
[ 2 ] Bevan, D. I.: Distributed Garbage Collection Using
Reference Counting, Proceedings of Parallel Languages
on PARLE: Parallel Architectures and Languages Europe,
1987, pp. 176–187.
[ 3 ] Crafa, S., Cunningham, D., Saraswat, V., Shinnar,A., and Tardieu, O.: Semantics of (Resilient) X10,
Proceedings of the 28th European Conference on ObjectOriented Programming (ECOOP ’14), 2014, to appear.
[ 4 ] Cunningham, D., Grove, D., Herta, B., Iyengar, A.,
Kawachiya, K., Murata, H., Saraswat, V., Takeuchi, M.,
and Tardieu, O.: Resilient X10: Eﬃcient Failure-Aware
Programming, Proceedings of the 19th ACM SIGPLAN
Symposium on Principles and Practice of Parallel Programming (PPoPP ’14), 2014, pp. 67–80.
[ 5 ] Juul, N. C.: A Distributed, Faulting Garbage Collector for Emerald, OOPSLA Workshop on Garbage Collection, 1990, pp. 1–6.
[ 6 ] Kawachiya, K.: Writing Fault-Tolerant Applications Using Resilient X10, Proceedings of the 2014 X10
Workshop (X10 ’14), 2014.
[ 7 ] Kawachiya, K., Takeuchi, M., Zakirov, S., and Onodera, T.: Distributed Garbage Collection for Managed
X10, Proceedings of the 2012 ACM SIGPLAN X10 Workshop (X10 ’12), 2012.
[ 8 ] Liskov, B. and Ladin, R.: Highly Available
Distributed Services and Fault-tolerant Distributed
Garbage Collection, Proceedings of the 5th Annual
ACM Symposium on Principles of Distributed Computing(PODC ’86), 1986, pp. 29–39.
[ 9 ] Mancini, L. and Shrivastava, S. K.: Fault-tolerant
Reference Counting for Garbage Collection in Distributed Systems, The Computer Journal, Vol. 34,
No. 6(1991), pp. 503–513.
[10] Oracle:
Package java.lang.ref, http://docs.
oracle.com/javase/6/docs/api/java/lang/ref/package-summary.html.
[11] PGAS: Partitioned Global Address Space,http://www.pgas.org/.
[12] Saraswat, V., Bloom, B., Peshansky, I., Tardieu,O., and Grove, D.: X10 Language Specification,
http://x10.sourceforge.net/documentation/
languagespec/x10-latest.pdf.
[13] Shapiro, M.: A Fault-Tolerant, Scalable, LowOverhead Distributed Garbage Collection Protocol,
Tenth Symposium on Reliable Distributed Systems, 1991.
[14] Shinnar, A., Cunningham, D., Herta, B., andSaraswat, V.: M3R: Increased Performance for InMemory Hadoop Jobs, Proceedings of the VLDB Endowment, Vol. 5, No. 12(2012), pp. 1736–1747.
[15] Takeuchi, M., Makino, Y., Kawachiya, K., Horii, H.,
Suzumura, T., Suganuma, T., and Onodera, T.: Compiling X10 to Java, Proceedings of the 2011 ACM SIGPLAN
X10 Workshop (X10 ’11), 2011.
[16] Watson, P. and Watson, I.: An Eﬃcient Garbage Col-lection Scheme for Parallel Computer Architectures,
Proceedings of Parallel Languages on PARLE: Parallel Architectures and Languages Europe, 1987, pp. 432–443.
[17] Wikipedia: K-means clustering, https://en.
wikipedia.org/wiki/K-means_clustering.
[18] X10 Project: X10: Performance and Productivity at
Scale, http://x10-lang.org/.

IBM は，世界の多くの国で登録された International Business Machines Corporation の商標です．他の製品名およびサービス名等は，それぞれ IBM または各社の商標である場合があります．現時点での IBM の商標リストについては，www.ibm.com/legal/copytrade.shtml をご覧ください．Java およびすべての Java 関連の商標およびロゴはOracle やその関連会社の米国およびその他の国における商標または登録商標です．

付録: 様々なケースの処理フロー
参考のため，図 6 に，図 4 以外のケースの処理フローを示す．

(a) リモート参照をリモートプレース S からリモートプレース R に送る
図 4 を参照(b) リモート参照をホームプレース H からリモートプレース R に送る
プレースH (home)
対応するGOTが無かったら作る
GOT.strongRef = 当該オブジェクト
GOT.remoteCountArray[R]++
当該オブジェクトのリモート参照（GlobalRef）をRに送信

プレースR (receiver)
Hからリモート参照を受信すると…
対応するRRTが無かったら作る
RRT.weightCount++(c) リモート参照をリモートプレース S からホームプレース H に送る

プレースH  (home)
自オブジェクトのリモート参照を受信すると…
対応するGOTからオブジェクト情報を取り出し，作ったリモート参照（GlobalRef）に入れる

プレースS  (sender)（sendingCountArray[H]の操作は不要）
リモート参照をHに送信(d) プレース P の RRT を削除できるかのチェック
プレースP (remote)
RRTに対応するリモート参照が生きていたら消せない
RRT.sendingCountArray が全部0でなかったら消せない
プレースH  (home)
PからRRT削除の通知を受信すると…
GOT.remoteCountArray[P]  -­=  RRT.weightCountそうでなければ，RRTを削除して，ホームプレースHにweightCountとともに通知

この配列が全部0なら，GOT.strongRef =  null  （àオブジェクトが回収可能になる）(e) プレース P が消失した場合の他プレースでの処理
残った各プレースで処理
プレースP消失の通知を受け取ると…
自分も含め全プレースが，たまっているリモート参照関係の通信を処理し終えるまで待つ
自プレースにある全GOTについて，
GOT.remoteCountArray[P]  =  0，この配列が全部0ならGOT.strongRef =  null（àオブジェクトが回収可能になる）
自プレースにある全RRTについて，
RRT.sendingCountArray[P]  =  0，「RRTを削除できるかチェック」する
RRT.home==Pなら，RRT.sendingCountArrayを全部0にし，「RRTを削除できるかチェック」する

図6

様々なケースの処理フロー