空間不変3次元光結合によるハイパーキューブの最適実現
スポンサーリンク
概要
- 論文の詳細を見る
並列計算機の情報処理の大容量化と高速化に伴い,通信網の電気結合による実現の様々な問題点が指摘され,これらの問題を解決する手段として通信網の光結合による実現が提案されている.小文では,並列計算機の相互結合網としてよく用いられているハイパーキューブを光結合で最適に実現する方法について考察する.よく知られているように,自由空間を用いた光結合はチップ間配線やボード間配線の実現に適している.また,結合パターンが正則である空間不変光結合は,レンズやホログラムのような代表的な光学部品の性能に適しており,光学的実現が容易であることが知られている.そこで小文では,以下のようなモデルを用いて相互結合網を最適に実現する問題について考察する.ここで用いるモデルは,プロセッサ及び各プロセッサに付随する光源といくつかの受光素子を2次元アレイ状に配置した二つの配列平面を3次元空間内に向かい合わせて平行に配置すると共に,これらの配置平面の中間に空間不変光結合を実現する光結合モジュールを配置して相互結合網を実現するものである.上の空間不変3次元光結合による実現(以後単に実現という)の複雑度を支配しているのは,光結合モジュールにおける光分岐数と配列平面の面積である.N点から成るハイパーキューブQ_Nは,21ogN-1の光分岐数と面積O(Vlog^4N)の配列平面を用いて実現できることが知られている.小文では, Q_Nの実現に対して,2logN-1とN(logN+1)/2がそれぞれ光分岐数と配列平面の面積の下界であることを示すと共に,2logNの光分岐数と面積NlogN+N/2の配列平面を用いたQ_Nの(オーダの意味で)最適な実現を示す.
- 一般社団法人情報処理学会の論文
- 1996-09-04
著者
関連論文
- 3-連結グラフの3分割アルゴリズム
- 3-連結グラフの3分割アルゴリズム
- Bandwidth of Convex Bipartite Graphs and Related Graph Classes
- On the Three-Dimensional Orthogonal Drawing of Outerplanar Graphs : Extended Abstract (Computational Geometry and Discrete Mathematics)
- dcBruijnグラフのVLSI分解について
- deBruijnグラフのVLSI分解について
- グラフ理論とその回路とシステムへの応用に関する研究(グラフ,ペトリネット,ニューラルネット及び一般)
- グラフ理論とその回路とシステムへの応用に関する研究(グラフ,ペトリネット,ニューラルネット及び一般)
- シャッフル交換ネットワークとde Bruijnネットワークの3次元VLSIレイアウト
- de Bruijn ネットワークの効率的なレイアウトについて
- 端子間容量行列の枝容量和最小実現の枝数最小化について(グラフ理論とその応用)
- 最小数枝付加によるk-枝連結グラフの(k+1)-枝連結グラフへの拡大構成(グラフ理論とその応用)
- 3-消去可能グラフについて(グラフ理論とその応用)
- 完全二分木ATMネットワークにおける最適な仮想パスレイアウト
- 完全二分木ATMネットワークにおける最適な仮想パスレイアウト
- マルチプロセッサシステムの逐次診断について
- コスト制限付最小遅延マルチキャスト(信号処理,LSI,及び一般)
- コスト制限付最小遅延マルチキャスト(信号処理,LSI,及び一般)
- コスト制限付最小遅延マルチキャスト(信号処理,LSI,及び一般)
- 外平面グラフの直交描画について(グラフ,ペトリ,ニューラルネット,及び一般)
- 外平面グラフの直交描画について(グラフ,ペトリ,ニューラルネット,及び一般)
- 外平面グラフの直交描画について
- 2分木のハイパキューブへの埋込みについて
- パス幅の制限された2分木のパスと格子への効率的な埋め込み
- 空間不変3次元光結合によるハイパーキューブの最適実現
- WSIネットワークの動的耐故障性について
- ネットワークの回線交換固定ルーティングの評価
- トーラスの耐故障固定ルーティングについて
- グラフのトポロジカルバンド幅と真のパス幅
- 逐次診断可能次数の上界
- グラフの幅2の真のパス分解を求める効率的アルゴリズム
- グラフの格子への辺負荷最小埋め込みの計算複雑度について
- グラフのハイパーキューブへの辺負荷最小の埋め込み
- 耐故障線形配列の最適構成
- 最適な耐故障線形アレイについて
- 最適な耐故障線形アレイについて
- マルチプロセッサシステムに対する適応的故障診断について
- 部分k木ネットワークとバタフライネットワークに対して確率的故障に耐える疎なネットワーク
- 部分k木ネットワークとバタフライネットワークに対して確率的故障に耐える疎なネットワーク
- マルチプロセッサシステムの逐次診断について
- CCCの逐次診断可能次数の評価
- 光ネットワーク上のオンラインマルチキャスティング
- CCCの3次元空間不変光相互結合による最適実装について
- ピラミッドネットワークの3次元レイアウト
- ピラミッドネットワークの3次元レイアウト
- De Bruijnネットワークの3次元レイアウト
- d値de BruijnグラフのVLSI分解について
- マルチプロセッサシステムの確率的逐次診断について
- WDMネットワークにおけるルーティングと波長変換
- A Note on the Three-Dimensional Optical Implementation of Regular Bipartite Graphs
- 空間不変3次元光結合によるハイパーキューブの最適実現
- CCCの3次元空間不変光相互結合による最適実装について
- CCCの逐次診断可能次数の評価