共同研究・競争的資金等の研究課題

2001年 - 2002年

PCクラスタにおける適応型ルーティングアルゴリズムに関する研究

日本学術振興会  科学研究費助成事業  若手研究(B)

課題番号
13780226
体系的課題番号
JP13780226
配分額
(総額)
2,000,000円
(直接経費)
2,000,000円

近年、商用のPCが多数無作為に接続されたネットワークにおいて並列処理を行うことにより、全体として高い計算能力を提供するPCクラスタが用いられるようになってきた。本研究ではPCクラスタで用いられるイレギュラーネットワーク上でのルーティングアルゴリズムを提案し、PCクラスタ全体の性能向上を狙う。
今年度はルーティングアルゴリズムの提案、及びシミュレータの実装による評価を行った。ルーティングアルゴリズムには超並列計算機で最近用いられるようになった適応型ルーティングを利用する手法を取った。適応型ルーティングを用いることにより、高い性能向上が達成された。ルーティングアルゴリズムはデッドロックフリーであることを保証しなければならないが、本研究で提案したルーティングアルゴリズム(Z-routing)は深さ優先探索でツリーを構築した後に幅優先探索でツリーの各辺に番号付けを行うというユニークな手法により実現した。この手法は一見、二度手間のように思えるが、他に提案されているルーティングアルゴリズムがツリー構築の計算時間にO(n^2)(nはスイッチの数)かかるところを、Z-routingではO(n+m)(nはスイッチの数、mはリンクの数)に抑えられる。これにより、Z-routingはスイッチの数が増えても十分に実現可能な時間でツリーの構築を行うことができ、高いスケーラビリティを保証する。今後のPCクラスタはノード(スイッチ)数が膨大になることが予想されるため、ツリーの構築時間が短いことは大きな利点となる。また、ルーティングアルゴリズムの性能も既存のルーティングアルゴリズムに比べ高い性能を示すことがわかった。本研究の成果は論文誌に採録され、3月に出版される予定である。

リンク情報
KAKEN
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13780226
ID情報
  • 課題番号 : 13780226
  • 体系的課題番号 : JP13780226