光インターコネクションとアルゴリズム

ネットワークの通信帯域が極度に貧弱な従来の計算機環境では、 通信を極力使用しないような様々な工夫が求められたきた。 ところが、光インターコネクションが計算機システムに導入 された場合、通信能力が極端に向上するため、システム設計思想 の根底が覆る。アルゴリズム設計の考え方も再検討する必要が生じ てくるだろう。

そこで本研究では、チップ間通信に光インターコネクション技術が導入された システムを光の特性を考慮して適切にモデル化した上で、 与えられたアプリケーションを最も効率よくシステム上に実装するための理論を、 離散数学的手法を基礎として構築した[1]。

光を導入したシステムにおける物理層の能力は、配線の空間密度や光線の伝搬時 間等に基づく通信能力、及びチップ上のトランジスタ密度等に基づく計算能力と して適切に評価する。その上で、集積化光デバイス技術と半導体集積回路技術の 現在及び将来の能力から、「計算にかかるコスト」と「通信にかかるコスト」が コンパラブルとなることが導かれる。このことから、与えられたアプリケーション に内在するコストを定量するために、「要素的通信」及び「要素的演 算」の概念を定義した。この概念は、直観的には、「単一の計算式 f」の結果 を得るために必要なデータを「準備」する過程（要素的通信）と、 用意されたデータを用いて「計算本体」を実行するための過程（要素的計算）である。 この概念を用いて、アプリケーションの内部に存在するすべての「要素的通信」と 「要素的演算」を導いておく。これらを、光インターコネクションを導入した システムに対して、如何にして適切に割り当てることができるか、が議論の焦点となる。

まず、システムの物理層モデルとアプリケーションの性質の双方を基礎として、 「コスト行列」を導く。この「コスト行列」の各要素は、直観的には、 「アルゴリズムのある一段階を、現実のシステムで実行する際に必要になる計算 時間」と言えるが、この行列の一番の特徴は、「負の値」を持つ要素を 同時に与えることである。 この「負の値」は、直観的には「可能かもしれない計算時間短縮の量」を示している。 コスト行列の複数の要素をある一定のルールで選択したときに、もしその総和 が負であれば、「より効率のよい」アルゴリズムが存在する。 このような状況を、本理論では「負の閉路の存在」と呼んでいる。 ネットワークフロー理論を用いると、「負の閉路」の存在しないことが、最適なアルゴ リズムの必要十分条件であることがわかり、さらに、「負の閉路」のないアルゴリズムを システィマティックに導く手法が構成できる。

OCULAR-II システムなどの 光電子融合型システムは、複数の LSI による計算、光による通信、さらには電気配線 による通信など、様々な技術の混成によってもたらされる機能の 複合体になっている。したがって、このような光電子融合型システムにおける最適なアル ゴリズムは、与えられたアプリケーションの性質と物理層の性能を包括的に考慮した上で 論じる必要がある。本理論は、システムの物理的性能とアプリケーション自体を同時に 評価し、さらに最適なアルゴリズムを導出するものであり、例えば、OCULAR-II システム における複数のプロセッサ層への処理の最適割り当ての考察も可能になってくる。

参考文献

1. 成瀬 誠, 石川 正俊: 光インターコネクションを用いたシステムのための並列アルゴリズムの構築, 情報処理学会論文誌, Vol. 41, No. 5, pp. 1509-1516, 2000.

[ホーム| センサフュージョン| ビジョンチップ| 光コンピューティング| メンバー| 論文]