2次元メッシュバス上での高速な確率ラウティングアルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
メッシュバス計算機 (MBUS) とは, n×nのプロセッサ間をn本の行バスとn本の列バスで結合した並列計算機モデルである. 本稿では確率ラウティングアルゴリズムを提案し, このアルゴリズムは高い確率で1.46875n+o (n) ステップ時間のラウティングを行なうことを示す. 決定性ラウティングの場合には, 1.5n時間のラウティングアルゴリズムが知られているが, 本結果は, 乱数を用いることで1.5n時間より早くラウティングを行なうことが可能であることを示している.
- 一般社団法人情報処理学会の論文
- 1997-11-28
著者
関連論文
- ランダムに生成された和積形論理式が充足不能となるしきい値について (アルゴリズムと計算の理論)
- Low-Level Tradeoffs between Cross And Alternation(Algorithms : Mathematical Foundations and Applications)
- 解の存在が保障されている組合せ探索問題について(計算機科学の基礎理論とその応用)
- シャフルされた記号列の復元問題 (形式言語理論とオートマトン理論)
- 自己シャフルに関する判定問題について (数理情報科学の基礎理論と応用)
- 2入出カ対オートマトンによる計算機結合インタフェースの設計手順 (計算機構の数学的研究)
- 2次元メッシュバス上での高速な確率ラウティングアルゴリズム
- 2次元メッシュバス並列計算機上での確率ラウティングアルゴリズム
- メッシュ型モデル上でのラウティングについて
- 為替交換問題に対する最適に近いオンラインアルゴリズムの設計と解析
- 為替交換問題に対するオンラインアルゴリズムの効率解析
- テープ記号数を制限した決定性TMと交代性TMの領域計算量について