研究紹介


研究分野
並列計算、オンラインアルゴリズム
現在の興味
不規則なトポロジの相互結合網に対する適応的経路制御アルゴリズム
現在の研究内容について

相互結合網の設計は並列計算機の設計での大変重要な課題であり、これに関連 した研究テーマの一つに経路制御がある。経路制御とは、「パケットが 相互結合網のどの経路を通過するか?」を決定することであり、経路制御 アルゴリズムを上手に設計すると、遅延(パケットがあるノードを出発してから 目的ノードに到着するまでの時間)やスループット(相互結合網全体での パケット転送量)を大幅に改善することができるが、安易に設計してしまうと デッドロック等の問題が生じてしまうため、経路制御アルゴリズムの設計は 非常に挑戦的な仕事であると言える。

経路制御アルゴリズムは、経路選択の自由度の点で二つに大別される。 一つは、決定的経路制御アルゴリズムであり、もう一つは、適応的経路制御 アルゴリズムである。決定的経路制御では、パケットの出発点と終点の対に 対して、唯一つの経路が決定される(途中の各ノードにおいて、次に選択する リンクが唯一つに決定される)。一方、適応的経路制御では、パケットの 出発点と終点の対に対して、複数の経路が候補として求められる。そして、 相互結合網の混雑状況に応じて、適切な経路が選択される(途中の各ノードに おいて、次に選択するリンクの候補が複数列挙され、リンクの使用状態に 応じて、適切なリンクを選択する)。次の例は、両者の違いを示している。 決定的経路制御では緑色の経路しか用いることができないが、適応的経路制御 では赤色の経路の一つを選択できるため、相互結合網を有効に活用できる。

二次元メッシュでの例

一方、この10年ほどで、ワークステーションやPCの性能は急激に高性能化し、 コスト面でも非常に安価なものとなってきた。現在、こうした計算機を用いて、 高性能かつ安価な並列計算機(計算機クラスタ)を設計するための研究が 活発に行われている。計算機クラスタでは、wiring flexibility、及び、 scalabilityを追求するため、相互結合網に不規則なトポロジが採用されて いるが、逆に、この不規則性が経路制御およびデッドロックの回避をより 難しいものとしている。本研究では、不規則なトポロジの相互結合網に対して、 デッドロックフリーな適応型経路制御アルゴリズムを設計し、より低い遅延と より高いスループットを達成することを目標としている。