A Scalable Routing Methodology for Low-Latency Interconnection Networks

(邦訳:低遅延相互結合網のためのスケーラブルなルーティング手法)
 
河野 隆太
慶應義塾大学 研究員

[背景]スーパーコンピュータ向けの低遅延ネットワークの需要増加
[問題]低遅延なランダムネットワークの実用化に向けた拡張性向上
[貢献]提案のルーティング手法による低遅延性と拡張性の両立


 大規模な科学技術計算の問題の解決には,高性能なスーパーコンピュータの構築が不可欠である.スーパーコンピュータは小さなマシンの集まりであり,その数は今後10万台以上にもなるといわれる.これらがネットワークで繋がることにより,大規模な並列計算の問題を解くことが可能となる.個々のマシンがどれほど高スペックであっても,それらを繋ぐネットワークが遅い場合,全体としてスーパーコンピュータの性能は大きく低下する.さらに,無数のマシンをつなぐ,数千キロメートル以上にもなるケーブルが,実装面やコスト面から問題となっている.

 このような問題に対する解決策として,マシン間を不規則に繋ぐ【ランダムネットワーク】が,高性能計算機向けのネットワークとして提案されている.一見使いにくいように見えるこのランダムネットワークは,マシン間を規則的に接続した従来型のネットワークに比べ,通信遅延を大幅に削減できるという興味深い性質を持つ.さらに,このランダムネットワークは,ケーブルの長さを一定以下に制限しても,その低遅延性を維持するという驚くべき特性がある.すなわち,ケーブル長を制限したランダムネットワークをスーパーコンピュータのマシン間に用いることで,低遅延性とケーブル長の削減を両立し,全体性能を向上できることが分かっている.

 本研究では,このような低遅延かつケーブル長の小さいランダムネットワークを研究対象とし,スーパーコンピュータ向けに実用化させるための課題解決に取り組んだ.大きく分けて,(1)コンパクトで速いパケット・ルーティングの手法と,(2)実装コストが小さく,アルゴリズム計算量の小さい通信の混雑制御手法,の2点について,対応する解決策を以下の通り開発した.

(1)通常,ランダムネットワークでは,各マシンがすべての宛先マシンについてのルーティング情報(経路の情報)を持つ必要がある.このルーティング情報の肥大化が,巨大なランダムネットワークを実現する上での課題となっている.提案手法では,ケーブルの長さを制限したランダムネットワークに対して,各マシンが近傍の一部マシンへのルーティング情報のみを持つこととした.このようにコンパクト化したルーティング情報を用いることで,従来の巨大なルーティング情報を持たせた場合と同等の低遅延ネットワークを実現可能とした.

(2)ランダムネットワークのように循環構造を持つネットワークでは,デッドロックと呼ばれる通信の行き詰まりが発生し,パケット通信が止まってしまう問題が存在する.提案する通信の混雑制御手法では,ネットワーク上でパケットを格納するバッファ数の削減と,通信フローをネットワーク上に割り当てるためのアルゴリズムの計算量の削減を両立し,従来手法に比べ大規模システムに対する高い実装可能性を達成した.

 上記2手法を組み合わせ,ケーブル長を制限したランダムネットワークに適用することにより,低遅延性と拡張性を両立し,スーパーコンピュータ向けの実用的なネットワーク・アーキテクチャを確立した.

 
 
 (2018年5月29日受付)
取得年月日:2018年3月
学位種別:博士(工学)
大学:慶應義塾大学



推薦文
:(システム・アーキテクチャ研究会)


大規模な並列コンピュータのノード間を結ぶ結合網に,制限付きランダムリンクを用いるために,ノード数が増大しても対応可能なルーチング法と,デッドロックフリーなチャネルの割り当て法を提案した.このことで,ランダムリンクを用いた効率の良い大規模結合網の実用可能性を大幅に前進させた.


研究生活


博士課程の始めの期間は,修士課程から続けてきた自身の研究を見つめ直し,足元を固めるために費やしました.このため一時的に低迷しましたが,そこから何とか這い上がり,博士進学時の相互結合網の研究をさらに発展させることができました.未知の問題と向き合い,解決策を考案していった経験は,今後の大きな糧になると信じています.学部3年の研究室配属から博士学位取得に至るまでの長きにわたり,指導教員の天野英晴教授をはじめ,研究室の皆様に大変お世話になりました.今後さらに成長し,研究活動に邁進して参ります.