並列分枝限定法と動的探索木分割によるクラスタシステム向き最適順序付けアルゴリズム(アルゴリズム)
スポンサーリンク
概要
- 論文の詳細を見る
Task Control Architecture (TCA)と呼ばれるロボット制御プログラムの開発法において, 開発したプログラムがデッドロックに陥らないことを検証する際に, 複数のプログラムモジュール間に適切な順序付けを与えると検証時間を大幅に短縮できる.本稿ではそのような順序付けを求めるための並列アルゴリズムを提案する.本アルゴリズムは, クラスタマシン上での実行を前提としており, 最適な順序付けを探索する際に, 並列分枝限定法を用いる.さらに, 探索過程において, 探索木を動的に分割しながらクラスタマシンの各ノードに部分探索問題を割り当てることにより, 各ノードの計算負荷をバランスさせている.実験の結果, 91並列で236倍の高速化を達成することができ, 提案アルゴリズムがきわめて有効であることを示した.
- 一般社団法人情報処理学会の論文
- 2005-08-15
著者
関連論文
- 有限オートマトンと表現等価な正則時相論理とその論理設計検証への応用
- 正則時相論理のモデルチェック法の改良と設計検証への適用
- 設計検証技術(総論) : 現在の設計検証技術はペンティアムのバグを見つけることができるか
- 1. 論理関数処理に基づく形式的検証手法 ( 論理設計の形式的検証)
- 形式的設計検証のための分岐時間正則時相論理
- 時相論理と言語階層の対応関係について(計算および計算量理論とその周辺)
- 有限オートマトンと表現等価な正則時相論理とその論理設計検証への応用
- 線形時間のモデルチェックアルゴリズムを持つ正則時相論理と変数代入機構による拡張
- On Design Varification between Different Levels of Abstraction Using Regular Temporal Logic
- 正則時相論理の充足可能性判定アルゴリズム
- 特集「論理設計の形式的検証」の編集にあたって
- マルチコンピュータ・マルチスクリーン・グラフィクス・システム(MCMSシステム)の論理シンボル入力/編集
- マルチコンピュータ・マルチスクリーン・グラフィクス・システム(MCMSシステム)による論理回路図の入力
- マルチコンピュータ・マルチスクリーン・グラフィクスワークステーションの開発
- 並列分枝限定法と動的探索木分割によるクラスタシステム向き最適順序付けアルゴリズム(アルゴリズム)
- 通信状態の可視化によるメッセージ通信型並列プログラムのデバッグ支援ツール
- クラスタシステムにおける並列バイトニックソートの性能評価
- Verification of Deadlock Free Property of Asynchronous Robot Control Programs
- 情報技術革命を支える高性能・高効率計算システムの研究
- 平成13年度活動概要
- Verification of Deadlock Free Property of Asynchronous Robot Control Programs
- HRクラスタシステムガイド(ハイテクリサーチプロジェクト)
- 静的部分問題割り当てに基づくN-queen問題の並列アルゴリズム
- 静的部分問題割り当てに基づくN-queen問題の並列アルゴリズム
- 形式的論理設計検証の研究
- 形式的論理設計検証の研究
- 形式的論理設計検証の研究
- 記号モデル検証システムSMVにおける像計算 (テストと設計検証論文特集)
- タスク制御アーキテクチャ入力支援システム
- 形式的論理設計検証およびメッセージ書換型プロキシサーバーの研究
- メッセージ書換型プロキシサーバの研究開発
- 形式的論理設計検証に関する研究
- 16ビットマイクロプロセッサの形式的設計検証
- 順序回路検証の技術
- イベントの2項関係に基づく並列システムの代数的仕様記述
- 正則集合と表現等価な正則時相論理RTL
- GPGPU による組み合わせ論理回路の入力パタン並列論理シミュレーション
- 形式的論理設計検証に関する研究
- 形式的論理設計検証に関する研究
- 形式的設計検証
- 正則集合に表現等価なテンポラル・ロジック(アルゴリズムの数学的基礎理論とその応用)