2次元メッシュバス並列計算機上での確率ラウティングアルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
メッシュバス計算機(MBUS)とは, n × nのプロセッサ間をn本の行バスとn本の列バスで結合した並列計算機モデルである。同じ二次元メッシュモデルであるメッシュ計算機(MC)にあまり劣らない実現性を有し, 通信路長にかかわる直径が2でMCの場合のnに比べてずっと小さいという特色を持つ。ラウティング問題とは, n×n個のパケット(行き先とデータの組)がMBUSの各プロセッサに与えられた時, これら全てのパケットを正しい行き先へと移動させる問題である。本論文では確率ラウティングアルゴリズムを提案し, このアルゴリズムは高い確率で1.4375n+o(n)ステップ時間のラウティングを行なうことを示す。決定性ラウティングの場合には, 1.5n時間の上限と(1ーβ)n時間(βはいくらでも小さくてよい正数)の下限が知られている。また無情報ラウティングに限ると, 上限および下限が1.5nで一致することが示されている。本稿では, 乱数を用いることで1+5n時間より早くラウティングを行なうことが可能であることを示す。
- 一般社団法人情報処理学会の論文
- 1997-09-24
著者
関連論文
- ランダムに生成された和積形論理式が充足不能となるしきい値について (アルゴリズムと計算の理論)
- Low-Level Tradeoffs between Cross And Alternation(Algorithms : Mathematical Foundations and Applications)
- 解の存在が保障されている組合せ探索問題について(計算機科学の基礎理論とその応用)
- シャフルされた記号列の復元問題 (形式言語理論とオートマトン理論)
- 自己シャフルに関する判定問題について (数理情報科学の基礎理論と応用)
- 2入出カ対オートマトンによる計算機結合インタフェースの設計手順 (計算機構の数学的研究)
- 2次元メッシュバス上での高速な確率ラウティングアルゴリズム
- 2次元メッシュバス並列計算機上での確率ラウティングアルゴリズム
- 為替交換問題に対する最適に近いオンラインアルゴリズムの設計と解析
- 為替交換問題に対するオンラインアルゴリズムの効率解析
- 一切の情報を漏らさずプログラムの正当性を証明する方法
- テープ記号数を制限した決定性TMと交代性TMの領域計算量について