並列アルゴリズムに適用した確率アルゴリズムの性能評価の試み (<特集>並列処理)
スポンサーリンク
概要
- 論文の詳細を見る
並列アルゴリズムにおいて最悪時の時間計算量を改善するために,乱数を導入する研究が進んでいる.しかし決定性アルゴリズムと確率アルゴリズムとは,必ずしも同一の規準で評価されていない.超立方体ネットワークのパケットルーティング問題においても,並列決定性オブリビアス(oblivious)アルゴリズムには最悪時の個別問題に対する解析がなされ,(Valiant-Brebnerが開発した)並列確率アルゴリズム(以下VB法)には平均的な解析がなされている.これよりVB法が"オーダ的に優れている"ことがわかるが,実際規模の具体問題でVB法が優位であるかは解明されているとは言いがたい.そこで,超立方体の次元を大きくしていき,オブリビアスアルゴリズムの一つであるLR法がVB法にどの程度まで優位であるかをシミュレーションにより実測値で評価した.その結果ある個別問題に関しては,10次元以上の超立方体において,確かにLR法がVB法より,問題を解くのに要するステップ数が多くなることが確認できた.本論文ではオブリビアスでない決定性ルーティングアルゴリズムを提案する.シミュレーションにより,この方法では大幅なステップ数の減少が見られ,15次元以下の問題規模ならどのような個別問題に対してもLR法よりステップ数が多くなく,LR法では最悪となる個別問題に関してもVB法より性能が良いことがわかった.
- 一般社団法人情報処理学会の論文
- 1993-04-15
著者
-
石原 鑑
三菱電機(株)先端技術総合研究所
-
首藤 勝
大阪大学大学院基礎工学研究科
-
首藤 勝
大阪大学基礎工学部情報工学科
-
魚井 宏高
大阪大学基礎工学部
-
萩原 兼一
奈良先端科学技術大学院大学
-
首藤 勝
大阪大 大学院
-
石原 鑑
三菱電機(株)
関連論文
- 5B-3 APIを用いたデータ移行並びに検証方式の提案(プログラム設計支援,一般セッション,ソフトウェア科学・工学)
- 企業情報システム再利用型開発のためのアプリケーション共通基盤のモデルベース設計手法
- Web Mediator: WWWにおける社会的インタラクション : JavaインタフェースによるプライベートWeb空間共有機能の実現
- Fittsの法則に基くマウスの操作方向の効率への影響
- ミドルウェア化を指向した知的エージェントシステムの開発
- 知的インタフェ-スエ-ジェントによるアプリケ-ションユ-ザの支援 (特集「知識の相互伝達」)
- 知的インタフェ-スエ-ジェントによるアプリケ-ションユ-ザの支援 (テ-マ:特集「知識の相互伝達」)
- 社会的インタラクション支援による組織の知の形成
- グループウェアにおけるボトムアップな情報共有 : 社会的インタラクションとインフォーマルコミュニケーションの支援
- 協調作業を支援する分散ハイパメディアシステム
- マウスとペンの操作精度の比較
- アルゴリズムの段階的学習を支援することを目的とした階層型アニメーションの実装と評価
- 企業情報統合ミドルウェアを実現する多段購読コンポーネントモデル
- B-009 テスト観点分析によるソフトウェア要求仕様の品質向上(B分野:ソフトウェア,一般論文)
- 2S-5 インターフェースエージェントのイントラネット応用システムへの適用の試み
- 同期付シャフル表現の記述能力
- 発想支援グループウェアの実施に及ぼすテキストベースコミュニケーションの影響(分散協調支援とその応用)
- チャットに注目した発想支援グループウェアのコミュニケーションに関する検討
- チャットに注目した発想支援グループウェアのコミュニケーションに関する検討
- インターネットを用いた多地点研究指導実験
- 音声に重点を置いたネットワークに関する検討
- 発想支援におけるマルチメディアコミュニケーションの各メディアの役割とその対応
- モデルによるシステムテスト開発環境の再利用とその適用
- 制御の流れに重点をおいてアルゴリズム学習を支援するシステムの構想
- 段階的学習を支援することを目的とした階層的アニメーションの実装と評価
- 図形表現とテキスト表現を併用したプログラム実行状態の可視化
- 能動的学習を支援するためのアルゴリズムアニメーションの拡張法に関する考察
- グループ知的生産支援システムSharedWadaman
- 知的生産支援システムWadaman
- 知的生産支援システムWadamanのグループウェア化の実現
- 知的生産支援システム Wadaman のグループウェア化 : SharedWadaman
- 知的生産支援システム Wadaman のグループウェア化 : SharedWadaman
- コミュニケーション手段が異なる分散協調型KJ法のインターネットを介した実施
- インターネット応用監視制御フレームワーク"DiaSynapse/JAXSON" (特集 インターネット時代の社会インフラシステム)
- 共有メモリ式SIMD型並列アルゴリズム解析ツール
- 拡張ユースケースシナリオからテストプログラムの自動生成を支援する開発環境の提案と評価について
- ユースケースモデルを活用した業務システムの開発ライフサイクル (特集 新たな時代の電力ビジネスに対応したシステムソリューション)
- 完全ネットワークでの最小重み生成木構成分散問題のビット複雑度について
- IT技術を適用した省エネルギー支援システムの構築 (特集 エコファクトリー化技術)
- 横配置型メニューを用いた階層型ポップアップメニュー方式とその実験的評価
- マルチカラムメニューとプルダウンメニューの比較について
- リモートプルダウンメニュー方式の提案とその評価
- プロセッサ間通信遅延を考慮した完全2分木状タスク依存グラフのスケジューリングアルゴリズム
- プロセッサ間通信遅延を考慮した完全2分木状タスク依存グラフのスケジューリング手法
- プロセッサ間通信遅延を考慮した完全2分木状タスク依存グラフのスケジューリング手法
- BC-chainを用いたコンビネ-タコ-ドへの翻訳アルゴリズム
- ソフトウェア要求定義の品質向上技術 (特集 ソフトウェア開発環境)
- 監視アプリケーション構築のための Ajax フレームワークの提案
- 並列アルゴリズムに適用した確率アルゴリズムの性能評価の試み (並列処理)
- 並列アルゴリズムに適用した確率アルゴリズムの性能評価の試み
- 遠隔ゼミナール支援システムのインターネットを介した適用と評価 (マルチメディア分散・協調コンピューティング)
- 遠隔ゼミ支援システムRemote Wadamanの開発と適用
- 遠隔ゼミ支援システムの3地点運用を考慮した改良
- KJ法文章のVA手法に基づく評価法の提案と実装
- 遠隔研究指導支援システムの開発
- インターネット上の監視制御システムにおけるJavaクライアントの実現方式
- 内容と構造を対象としたKJ法B型文章評価方法の提案と適用
- 動画アイコンの開発と適用
- 動画アイコンの開発と適用
- ペトリネットによるKJ法B型文章の構造の評価に関する検討
- インターネットを介して実施した分散協調型KJ法に関する考察
- ペトリネットのKJ法B型文章化への適用
- 動画のインタラクティブな分岐方法の提案とその適用
- 動画のインタラクティブな分岐に関する検討
- KJ法の一貫支援に関する検討
- 大学内/研究所内LANとデータの共有
- 部品階層に基づくオブジェクト指向プログラミングトランスレータの検証