光インターコネクションとアルゴリズム
研究内容
ネットワークの通信帯域が極度に貧弱な従来の計算機環境では、通信を 極力使用しないような様々な工夫が求められてきた。ところが、光イン ターコネクションが計算機システムに導入された場合、通信能力が極端 に向上するため、システム設計思想の根底が覆る。アルゴリズム設計の 考え方も再検討する必要が生じてくるだろう。
そこで本研究では、チップ間通信に光インターコネクション技術が導入 されたシステムを光の特性を考慮して適切にモデル化した上で、与えら れたアプリケーションを最も効率よくシステム上に実装するための理論 を、離散数学的手法を基礎として構築した[1]。
光を導入したシステムにおける物理層の能力は、配線の空間密度や光線 の伝搬時間等に基づく通信能力、及びチップ上のトランジスタ密度等に 基づく計算能力として適切に評価する。その上で、集積化光デバイス技 術と半導体集積回路技術の現在及び将来の能力から、「計算にかかるコ スト」と「通信にかかるコスト」がコンパラブルとなることが導かれる。 このことから、与えられたアプリケーションに内在するコストを定量す るために、「要素的通信」及び「要素的演算」の概念を 定義した。この概念は、直観的には、「単一の計算式 f」の結果を得る ために必要なデータを「準備」する過程（要素的通信）と、用意された データを用いて「計算本体」を実行するための過程（要素的計算）であ る。この概念を用いて、アプリケーションの内部に存在するすべての 「要素的通信」と「要素的演算」を導いておく。これらを、光インター コネクションを導入したシステムに対して、如何にして適切に割り当て ることができるか、が議論の焦点となる。
まず、システムの物理層モデルとアプリケーションの性質の双方を基礎 として、「コスト行列」を導く。この「コスト行列」の各要素 は、直観的には、「アルゴリズムのある一段階を、現実のシステムで実 行する際に必要になる計算時間」と言えるが、この行列の一番の特徴は、 「負の値」を持つ要素を同時に与えることである。この「負の値」 は、直観的には「可能かもしれない計算時間短縮の量」を示している。 コスト行列の複数の要素をある一定のルールで選択したときに、もしそ の総和が負であれば、「より効率のよい」アルゴリズムが存在する。こ のような状況を、本理論では「負の閉路の存在」と呼んでいる。 ネットワークフロー理論を用いると、「負の閉路」の存在しないことが、 最適なアルゴリズムの必要十分条件であることがわかり、さらに、「負 の閉路」のないアルゴリズムをシスティマティックに導く手法が構成で きる。
OCULAR-II システムなどの 光電子融合型システムは、複数の LSI による計算、光による通信、さ らには電気配線による通信など、様々な技術の混成によってもたらされ る機能の複合体になっている。したがって、このような光電子融合型シ ステムにおける最適なアルゴリズムは、与えられたアプリケーションの 性質と物理層の性能を包括的に考慮した上で論じる必要がある。本理論 は、システムの物理的性能とアプリケーション自体を同時に評価し、さ らに最適なアルゴリズムを導出するものであり、例えば、OCULAR-II シ ステムにおける複数のプロセッサ層への処理の最適割り当ての考察も可 能になってくる。
動画
参考文献
- 成瀬誠, 石川正俊：光インターコネクションを用いたシステムのための並列アルゴリズムの構築, 情報処理学会論文誌, Vol.41, No.5, pp.1509-1516 (2000)
