情報処理学会研究報告IPSJ SIG Technical Report
予測ルータによる低遅延 Fat Tree ネットワーク
館下智明†1秋岡明香†1吉永努†1
松谷宏紀†2鯉渕道紘†3
並列計算機においてはノード間の通信遅延が処理能力に影響を与えるため，低遅延なネットワークが求められている．そこで，本論文ではルーティングに予測を用いることにより，Fat Tree ネットワークの通信遅延を削減する試みについて報告する．予測方法として，Tree の上（ルート）方向に向かうメッセージのみ予測した場合と，上下方向のメッセージを予測する場合について考察する．また，システムエリア/オンチップ・ネットワークへの応用についても考察する．シミュレータを用いた実験の結果，Fat Tree トポロジにおいて予測ルータを使用した場合，従来に比べて約 20 ％ほど遅延を小さくできることがわかった．
Prediction router for low latency Fat Tree network
Tomoaki Tateshita,†1 Sayaka Akioka,†1
Tsutomu Yoshinaga,†1 Hiroki Matsutani†2
and Michihiro Koibuchi†3
Low latency networks are required in a parallel computer because the delayof communication between the nodes inﬂuences processing performance. In thispaper, we report on the method of reducing the delay of the communicationon the Fat Tree network when the prediction is used for routing. The paperconsiders the prediction procedure when only messages toward the upside di-rection direction of upside of Tree (root) are predicted and when the messagesin the vertical direction are predicted. Moreover, it is applicable for the systemarea/on chip network. Our results showed that it is able to reduce the delayabout 20% compared with the past when the prediction router is used in theFat Tree topology as a result of the experiment with the simulator.
1.は じ め に
近年，並列計算機はその高性能化に伴い，コア数，ネットワーク規模の増大が進んで来て
おり，コア間の通信遅延が並列計算機の処理能力に与える影響が大きくなってきている．コ
ア間の通信には Interconnection Network が広く用いられるため，通信遅延の小さいルー
タの開発が望まれている．
これまでの研究によって，予測機構を持つ低遅延ルータを用いることによりオンチップ
ネットワーク（OCN）において遅延を削減できることがわかっており1)，予測のヒット率は
予測アルゴリズムやネットワーク構造に依存することがわかっている2)．本研究では，PC
クラスタなどに用いられる Fat Tree ネットワーク3) に対して予測ルータを導入し，通信遅
延を削減する試みについて報告する．オンチップネットワークとシステムエリアネットワー
ク（SAN）の 2 種類の実装を想定してシミュレーションを設定し，それぞれについて通常
のルータを使用した場合と予測ルータを使用した場合の遅延を比較する．システムエリア
ネットワークではフリットのサイズを変えた場合の遅延の比較も行う．またオンチップネッ
トワークを想定したシミュレーションでは，ノード数を変えて 2 種類の予測アルゴリズムの
予測のヒット率の比較も行う．
本論文では，2 章で予測ルータについて説明し，3 章でシリアル通信について説明する．4
章でシミュレータでの評価結果を示し，5 章において関連研究をまとめた後，6 章でまとめ
2.ルータの構造
2.1予測ルータ
図 1 に予測ルータの構造を示す．通常のルータでは入力バッファにメッセージが届いてか
らアービトレーションを行うが，予測ルータではバッファにフリットが無いとき，予測器を
用いて次に来るフリットが使うと予測される出力ポートへアービトレーションを行う．
通常のルータでは，入力バッファにフリットが到着すると図 2 の normal に示すように，
†1 電気通信大学The University of Electro-Comunicasions†2 東京大学The University of Tokyo†3 国立情報学研究所National Institute of Informatics
1c⃝ 2009 Information Processing Society of Japan
Vol.2009-ARC-184 No.312009/8/6
情報処理学会研究報告IPSJ SIG Technical Report
arbiter
buffer
inputoutput
predictor
図 1予測ルータの構造Fig. 1Architecture of prediction router
RCnormal
VSA ST
VSA ST
123cycle
prediction Miss
図 2通常のルータと予測ルータのパイプライン構造Fig. 2Pipelines for a normal router and aprediction router
3 段のパイプラインを経て出力する．まず，宛先アドレスから出力ポートを計算する RC
（Routing computation）を行い，次に RC の結果をもとに出力仮想チャネルの割り当てと
クロスバスイッチの設定を行う VSA（Virtual channel/Switch allocation）を実行する．そ
のうえで，クロスバスイッチを通過する ST（Switch traversal）を経て出力ポートからフ
リットを出力する．
予測ルータでは，予測が正しい場合，入力したメッセージは RC と VSA を省略して ST
を実行することができるため（図 2 の prediction Hit），予測成功率に応じて通信遅延を
削減することができる．また，予測がはずれた場合は予測ルータも通常のルータと同様に，
RC，VSA，ST の 3 段のパイプラインを経て転送を行う（図 2 の prediction Miss）．ただ
し，予測失敗時に間違った出力ポートへフリットが送られてしまう場合がある．その対策と
して，オンチップネットワークでは ST と平行して RC を実行することによって予測失敗を
検出し，予測ミスしたメッセージが出力ポートから出力されることを防止する4)．
2.2予測アルゴリズム
予測ルータは予測の成功率によって通信遅延が左右されるので，予測成功率の高い予測ア
ルゴリズムが求められる．ここでは本論文で使用する予測アルゴリズムについて述べる．
Static Straight（SS）ではフリットは同一次元上を直進すると予測する．Fat Tree におい
ては下の階層から来たフリットは上の階層へ出力されると予測し，上の階層から来たパケッ
トは下の階層を目指すと予測を行う．図 3 の middle のように，本論文で検討する Fat Tree
は上向き，下向きのポート数が等しいので，それぞれのポートが 1 対 1 に対応するポート
を予測出力ポートとする．また，図 3 の top のように，例外的に最上位の階層では折り返
middletop
図 3SS の Fat Tree における予測の仕方Fig. 3Method of prediction in Fat Tree of SS
すように予測を行う．
Up Priority（UP）は up∗/down∗ ルーティングにおいて，上の階層を目指すと予測し，
下の階層を目指す予測は行わない．Fat Tree においては SS は UP を含んでいるといえる．
3.シリアル通信
3.1Ser/Des 変換
システムエリアネットワークではシリアル通信を想定する．ルータ間のデータ送受信をシ
リアル通信で行う場合，通信データのシリアライズとデシリアライズ変換を行う必要があ
る．それぞれの変換処理にはある程度の時間がかかるが，予測ルータで予測が成功した場合
にシリアルデータのままルータを通過できるようにすれば，予測スイッチングを用いること
で，メッセージをルータに入力するときのシリアライズ遅延を通信時間から削減することが
3.2ヒントビット
2.1 節において，ST を実行している間に RC を並列に実行することによって予測ミスを
検出することを述べた．本論文ではオンチップネットワークはパラレル転送を想定している
ため，入力ポートにおいて各フリットを完全にバッファリングした後，RC と ST を実行す
る．しかし，3.1 節で述べたようにメッセージがシリアルデータをそのままルータを通過す
る場合には RC と並列実行する予測ミス検出がルータからメッセージ出力を開始するまで
に間に合わなくなる．
そこで，ヒントビットを用いて予測ミスメッセージの出力を抑制する方法を説明する．ヒ
ントビットは，メッセージの送信元ノードから宛先ノードへ進む方向を示し，メッセージの
先頭に付け加える（図 4）．例えば，Fat Tree トポロジで up∗/down∗ ルーティングを用い
る場合，送信元ノードと宛先ノードがわかれば最短経路は Tree をどこまで up 方向に上が
ればいいかがわかる（Least common ancestor routing）．2 階層のスイッチで構成する Fat
2c⃝ 2009 Information Processing Society of Japan
Vol.2009-ARC-184 No.312009/8/6
情報処理学会研究報告IPSJ SIG Technical Report
Hint bitMessage
Router ARouter B
図 4ヒントビットFig. 4Hint bit
1Hint bit = 0stop
sourcedestination
図 5ヒントビットによる制御Fig. 5Control by Hint bit
Tree の場合を例にとると，1 段上がるだけでいいときはヒントビットを 0 とし，2 段上がる
必要があるときはヒントビットを 1 とする．このとき階層 1 のルータで上向きのポートを
予測しているのにヒントビットが 0 の信号が入力された場合は予測が外れていると判断する
ことができる（図 5）．ヒントビットを用いて予測ミスを検出する機構を用いると，RC と
ST を並列に実行するよりも，予測ミスパケットの kill 機構が簡略化されるなど，ルータの
構造を単純にできる可能性があるが，本論文では議論が発散するため扱わないこととする．
また本論文のシミュレーションでは，ヒントビットはシステムエリアネットワークでのみ用
い，オンチップネットワークでは用いない．
4.評 価 結 果
フリットレベルのシミュレータである booksim シミュレータ5) を用いてシミュレーショ
ンを行い，予測ルータによる遅延削減の効果を調べる．なお，オンチップネットワークとシ
ステムエリアネットワークの 2 種類のネットワークを想定してシミュレーション条件を設定
した．LAN のシミュレーションでは Quadrics 社の QsNetIII6) を条件設定のモデルに用い
たシミュレーション条件を設定した．メッセージの通信パターンには uniform random を
用いた．uniform パターンはメッセージごとに宛先ノードをランダムに選択する．
4.1オンチップネットワーク
オンチップネットワークを想定したシミュレーションでは，Fat Tree トポロジにおいて
通常のルータと予測ルータを比較する．
Fat Tree の構成を示す方法として，ここでは（p，q，r）Fat Tree と表す．p は 1 つの
スイッチが有する上向きのリンク数，q は下向きのリンク数で，r は階層数を表す．よって，
（4，4，3）Fat Tree は上向きに 4 本，下向きに 4 本の計 8 本のリンクを持つルータからな
表 1OCN のシミュレーション条件Table 1Simulation parameter of OCN
Case 1
Topology（4,4,3）Fat TreeTraﬃcuniform
Routingup∗/down∗
SwitchingWormholeChannel2VCPipeline[RC][VSA][ST]ﬂit/packet5 ﬂitInput buﬀer4 ﬂit FIFO
表 2SAN のシミュレーション条件Table 2Simulation parameter of SAN
Case 2
Topology（16，16，2）Fat TreeTraﬃcuniform
Routingup∗/down∗
SwitchingStore and forward or Virtual cut throughChannell4VCPipeline[Des][RC][VSA][ST][Ser][LT]Packet size256 byteInput buﬀer256 byte
図 6（4，4，3）Fat TreeFig. 6（4，4，3）Fat Tree
る 3 階層の Fat Tree を表す（図 6）．
4.1.1ルータの構成
ここで予測ルータと通常のルータの構成について説明する．まず共通点として，ルータは
ワームホールスイッチングを使用し，入力ポートごとに 2 本の仮想チャネルを持つ．それぞ
れの仮想チャネルは 4-ﬂit 分のバッファを持つ．また，パケットは 5-ﬂit と仮定し，ヘッダ
がブロックされると複数のルータにまたがって停止する．
4.1.2遅延の評価
図 7 に，シミュレーションによって得た平均遅延を示す．FatTree-normal は通常のルー
タを使用した場合の遅延のグラフで，FatTree-pred は予測ルータを用いた場合の遅延のグ
3c⃝ 2009 Information Processing Society of Japan
Vol.2009-ARC-184 No.312009/8/6
情報処理学会研究報告IPSJ SIG Technical Report
ラフである．予測アルゴリズムは SS を用いる．2.2. 節で説明したように，通信パターンに
よらずそれぞれのポートが 1 対 1 に対応するポートを予測するので，予測による出力ポート
のアービトレーションでは衝突は起きない．予測が当たれば RC と VSA を省略して，ST
のみの 1 サイクルで転送できる．
通常の Fat Tree と予測ルータの Fat Tree のグラフを比較すると，負荷が小さいときでも
20 ％ほど，予測ルータを用いた Fat Tree の方が遅延が小さいことがわかる．これは，ルー
タ当たりのホップ遅延が必要なパイプライン段数の削減によって小さくなること，またメッ
セージ当たりの遅延低下によってネットワークの飽和スループットが向上することによる．
4.1.3ヒット率の比較
図 8 にノード数を変えた場合の SS と UP の平均ヒット率を示す．ネットワークサイズの
変更に当たっては，ルータのポート数はそのままに，Fat Tree の階層数を変化させた（4，4，
r）Fat Tree を用いた．他のメッセージとの衝突を防ぐため，Injection rate は Zero load，
すなわちネットワーク上にたったひとつしかパケットが存在しない無負荷の状態としている．
UP と SS ともにネットワークサイズが大きくなるにつれてヒット率が上昇し，SS は 60
％，UP は 45 ％程度で飽和していることがわかる．SS は Tree の上下方向に進むメッセー
ジに対して予測するため，予測を行う機会は UP の 2 倍以上あるが，Fat Tree では下向き
ポートの予測は上向きポートの予測に比べて当たりにくいためヒット率は 2 倍にはならな
い．また文献 2) では（1，4，r）Fat Tree および（2，4，r）Fat Tree について予測のヒッ
ト率の比較を行っており，（1，4，r）Fat Tree は約 40 ％，（2，4，r）Fat Tree は約 35 ％で
ほぼ一定の値となっている．文献 2) では上向きポートを異なる経路として扱っているため，
上向きポートが増えると予測のヒット率が低下しているが，本論文では上の階層へ向かう
メッセージはどの上向きポートでも予測成功としているのでヒット率が高くなり，より遅延
を削減することができる．
4.1.4パイプライン段数の比較
図 9 に予測ルータのパイプライン段数を変えた場合の平均遅延を示す．予測アルゴリズム
は SS を使用している．それぞれ 3 段，5 段，7 段のパイプラインだが，予測が成功した場
合は 1 段で転送ができるとする．
パイプライン段数を増やすとルータで複雑な処理を行ったり，動作周波数を上げることが
できるようになるが，図 9 のように平均遅延が大きくなる．しかし，負荷が小さいときはパ
イプラン段数が増えても遅延の増加が小さく，予測ルータによる遅延削減の効果はパイプラ
イン段数が多いほど大きいことがわかる．
 0 0.1 0.2 0.3 0.4 0.5
Latency[cycle]
Injection rate[flit/node/cycle]
FatTree-normal
FatTree-pred
図 7OCN における遅延Fig. 7delay in OCN
 4 16 64 256 1024 4096
Prediction hit rate[%]
Network size
図 8OCN におけるヒット率Fig. 8hitrate in OCN
 0 0.1 0.2 0.3 0.4 0.5
Latency[cycle]
Injection rate[flit/node/cycle]
3-pipeline5-pipeline7-pipeline
図 9パイプラン段数を変えた遅延Fig. 9latency when pipeline is changed
以上より，通信負荷，ノード数，パイプライン段数の 3 つの条件を変えた場合に，予測
ルータを用いることによって遅延を削減できていることを確認した．
4.2システムエリアネットワーク
QsNetIII をモデルとして，システムエリアネットワークを想定したシミュレーションで
は，Fat Tree トポロジで比較を行う．表 2 にシミュレーション条件を示す．
4.2.1ルータの構成
ルータ内の動作周波数を 312 MHz とし，リンクは 6.25 GHz で動作するチャネルが 4
4c⃝ 2009 Information Processing Society of Japan
Vol.2009-ARC-184 No.312009/8/6
情報処理学会研究報告IPSJ SIG Technical Report
チャネルずつ双方向にあると仮定する．よってリンクは 25 Gbit/sec となるが，リンクを
通すときには 8b10b 変換を行うため実際のリンクスループットはやや小さくなり，ルータ
の 1 サイクル（3.2 nsec）当たり 8 byte の情報を転送することができる．パケットは 256
byte としているので，リンクでパケットを全て転送するためには 32 サイクルかかる．ルー
タはリンクごとに 4 本の仮想チャネルを持ち，それぞれの仮想チャネルはパケットサイズと
同じ 256 byte のバッファを持っているとする．
予測アルゴリズムは UP を使用する．よって 2 階層 Fat Tree では予測を行うのは最初の
ルータの一回きりである．ヒントビットを用いることによって予測のヒット/ミスを判定し
て転送ミスをすることなく遅延を削減することができる．パイプラインは Des，RC，VSA，
ST，Ser，LT の 6 段とする．Des はデシリアライズ，Ser はシリアライズ変換を表してお
り，LT は Link Traversal でリンクの移動時間を表している．
4.2.2遅延の評価
図 10 に通信負荷を変化させたときの平均遅延を示す．スイッチング方式はストアアンド
フォワードとし，パケットが全てバッファリングされてからルータ内の動作を行うとする．
そのためリンクの移動時間である LT が 32 サイクル，ルータのパイプラン動作が 5 サイク
ルで，リンクの移動が遅延の大部分である．予測がヒットした場合はパケットが全て到着す
るのを待たずに転送を行うとする．シミュレーションより，負荷が 0.15（ﬂit/node/cycle）
を超えると予測のありなしに関わらず遅延が急激に大きくなっているが，それまでは予測ス
イッチングにより一貫して 20 ％ほど遅延を小さくできることがわかる．
4.2.3OCN との比較
4.1.2 節で評価した SS 予測を用いたオンチップネットワークのシミュレーションでも予
測ルータは通常のルータに比べて 20 ％ほど遅延を削減した．オンチップネットワークでは
3 階層の Fat Tree であり，SS 予測を用いているので最大で 5 回，予測の機会がある．それ
に比べて 2 階層の Fat Tree で UP 予測の場合は最初のルータでの 1 回しか予測の機会が存
在しないにもかかわらず，同程度遅延を削減している．
以上の理由としては 2 つの原因が考えられる．まず，SAN ではデシリアライズとシリア
ライズを行っており，予測成功時にはその両方を省略するため，オンチップネットワークに
比べて予測ルータの遅延削減効果が大きくなる．また，ストアアンドフォワードでフロー制
御をしているため，予測ルータを用いない場合にはパケットが全て届くまで待つ必要があ
る．そのため，予測ルーティングを行った場合とそれ以外の差がさらに大きくなっている．
もうひとつの原因としては，予測の成功率のばらつきが考えれられる．Fat Tree では上
の階層へパケットを送るときは複数あるポートのうちどれを使っても問題はないが，下の階
層へ送るときは唯一のポートを選択することになる．そのため，予測の成功率で考えると下
向きよりも上向きのほうが予測の成功率が高くなりやすい．よって，SS では最大で 5 回の
予測の機会があっても下の階層への予測は成功率が低いため遅延の削減にはつながりにくく
なっている．
4.2.4フリットサイズ
4.2.2 節ではフリットをパケットサイズとしており，ストアアンドフォワードで転送をし
ていたが，ここでは同じサイズのパケットを複数のフリットに分けてカットスルーで制御し
た場合について評価する．
図 11 では横軸をフリットサイズとしており，フロー制御を行うフリットのサイズを表し
ている．パケットのサイズは同じとしているので，フリットサイズが小さければ小さいほど，
1 つのパケットをより多くのフリットに分割できる．またバッファリングはフリット単位で
行い，デシリアライズなどはフリットがバッファに溜まってから行う．たとえば，フリット
サイズが 16 byte のときは LT が 2 サイクル，32 byte のときは LT が 4 サイクルとなる．
そのため，フリットサイズが小さいほど細かいフロー制御ができるので，より遅延を小さく
することができている．
予測ルータを使用した場合，フリットが 8 byte のときで 8.3 ％遅延を削減している．フ
リットが 256 byte のときには 23.2 ％，遅延を小さくできており，フリットサイズが大きく
なるにつれて予測ルータによる遅延削減の割合が大きくなっている．これは予測が成功した
ときにはフリットが全て届くのを待たずに次のルータへ信号を送り出すためである．
5.関 連 研 究
予測ルータの他にも，チップ内ネットワークを対象とした低遅延ルータに関して盛んに研
究が行われている．
本論文では，3 段パイプライン構成のルータを基に予測機構を適用する議論を進めてきた．
一方で，RC と SA をオーバラップさせることで，ルータのパイプラインステージを 1 ス
テージ分削減する投機ルータに関する様々な議論も行われている5)．ただし，SA は RC 完
了後に実行する必要があるため，RC と SA を同一サイクルで実行することは効率が悪い．
そこで，1 ホップ手前のルータに次ホップのルータの RC を予め実行する手法である Next
routing computation，NRC 機構を併用する手法が議論されている．NRC の結果は次ホッ
プのルータで使われ，自ルータの SA に影響を与えないため，NRC と SA を並列に実行で
5c⃝ 2009 Information Processing Society of Japan
Vol.2009-ARC-184 No.312009/8/6
情報処理学会研究報告IPSJ SIG Technical Report
 0 0.05 0.1 0.15 0.2
Latency[cycle]
Injection rate[flit/node/cycle]
normal
prediction
図 10SAN における遅延Fig. 10delay in SAN
 10 20 30 40 50 60 70 80 90
 100 110 120 130 140 150
232425262728
Latency[cycle]
Flit size[byte]
normal
prediction
図 11SAN におけるフリットサイズを変えたときの無負荷遅延Fig. 11zero load latency when the ﬂit size ischanged in SAN
きる．このように次ホップの経路を計算するルーティングをルックアヘッドルーティングと
さらに，SA と ST をオーバラップさせることで 1 サイクル転送も可能となるが，1 サ
イクルに多くの処理を詰め込むことになるので，動作周波数の大幅な低下を招きやすい5)．
また，隣接ルータ間で連携することでパケット処理の遅延を抑える方法も提案されている．
Express VC は，仮想的に非隣接ルータ間でバイパス経路を構成することにより中継ルータ
における所要パイプライン段数を削減する7)．しかし，局所性を持つ通信パターンに対して
は低遅延化の効果が小さい．
これらに比べて，予測ルータは動作周波数の低下が 6 ％と小さく4)，かつ，あらゆる入出
力ポート対の通信に対しても遅延を削減できる点で極めて有効といえる．さらに，我々の評
価結果より4)，通信局所性の強い並列アプリケーションの場合，トポロジの規則性を活用す
ることで 90 ％の予測成功率を達成できることが報告されている．また，本論文では kill 機
構やヒントビットを用いて予測ミスによるメッセージ出力を防止しているが，予測ミスに
よって間違った出力ポートへメッセージが出力される場合でも遅延が削減できることがわ
かっている8)．
本研究では Fat Tree トポロジにおいて予測ルータを用いて，オンチップネットワークと
システムエリアネットワークの 2 種類のネットワーク条件において遅延と予測ヒット率の評
価を行った．評価結果より，それぞれのネットワーク条件で約 20 ％の遅延削減ができるこ
と，ルータのパイプライン処理やリンクの移動に時間がかかるネットワークほど予測ルー
タの効果が大きくなることを確認した．また（4，4，r）Fat Tree において，上向きポート
を同一経路として扱うことにって SS の予測ヒット率を 60 ％近くまで上げられることがわ
今後の課題としては予測ルータの予測成功率を高めるための予測アルゴリズムの研究や
ネットワーク構造の研究を行っていく予定である．
謝辞本研究は，一部科学研究費補助金基盤研究（C）課題番号 19500040，及び平成 21
年度国立情報学研究所・提案型共同研究の援助による．
1) 松谷 宏紀，鯉渕 道紘，天野 英晴，吉永 努：“低遅延オンチップネットワークのための予測ルータの評価”，第 7 回先進的計算基盤システムシンポジウム（SACSIS‘09）論文集，pp.209-218，May 2009．2) 鯉渕 道紘，吉永 努，村上 弘和，松谷 宏紀，天野 英晴：“予測機構を持つルータを用いた低遅延チップ内ネットワークに関する研究”，情報処理学会論文誌コンピューティングシステム，Vol.1，No.2，pp.59-69，（2008）．3) C．E．Leiserson，“Fat-trees：Universal networks for hardware-eﬃcient supercom-puting”，IEEE Transactions on Computers，vol.34，No.10，pp.892-901，1985．4) H．Matsutani，M．Koibuchi，H．Amano and T．Yoshinaga：“Prediction Router:Yet Another Low Latency On-Chip Router Architecture”，Proceedings of the In-ternational Symposium on High-Performance Computer Architecture（HPCA‘09），pp.367-368，Feb 2009．5) W.J．Dally and B．Towles：“Principles and Practices of Interconnection Net-works”，Morgan Kaufman Publishers，（2003）．6) Roweth，D．Jones，T：“QsNetIII an Adaptively Routed Network for High Per-formance Computing”，Proceedings of IEEE Symposium on High Performance In-terconnects（HOTI‘08）．pp.157–164 (2008).7) A．kumar，L.-S．Peh，P．Kundu and N．K．Jha：“Express Virtual Channels：To-wards the Ideal Interconnection Fabric”，Proceedings of the ISCA‘07，pp.150-161，（2007）．8) 吉永 努，村上 弘和，鯉渕 道紘：“2-D トーラスネットワークにおける動的通信予測の効果”，先進的計算基盤システムシンポジウム（SACSIS‘07），pp.219-226，May 2007．
6c⃝ 2009 Information Processing Society of Japan
Vol.2009-ARC-184 No.312009/8/6