ベクトル計算機のための探索問題の計算法 : 並列バックトラック計算法
スポンサーリンク
概要
- 論文の詳細を見る
この論文では,探索問題に適用することができる,ベクトル計算機むきのあたらしい計算法並列バックトラック計算法をしめす.この方法にしたがってFortranでプログラムを記述すれば,数値計算専用とかんがえられていたSB10のようなスーパ・コンピュータや,M-680H IAP/IDP(内蔵型アレイ・プロセッサ/内蔵型データベース・プロセッサ)のようなベクトル計算機構を付加した汎用計算機で,広範囲の探索問題を高速に実行することができるまたこの方法では,並列度を適切に制御することによって,必要な記憶量を逐次計算法とひとしいオーダにおさえることができる.この計算法をNクウィーン問題に適用し,つぎのような性能をえた.エイト・クウィーンの全解探索においてはS-81Oで逐次処理の約9倍,M-680H IAPおよびIDPを使用して約1.7倍だった.また,S-810においてはN≧14のとき単解探索でも逐次処理より高速になった.これによって並列パックトラック計算法の有効性がたしかめられるとともに,ベクトル計算機S-810およびM-680H IAP/IDPの記号処理への適用可能性がしめされた.また,並列バックトラック計算法は,Prologのような論理型言語のベクトル計算磯による高速実行の可能性を示唆している.
- 1988-10-15
著者
関連論文
- メディアプロセッサを応用したブロードバンド端末のソフトウェア設計手法(システムプログラム)
- マルチメディアブラウジングインタフェース「アルバムメタファ」の開発とインターネットへの適用
- ソフトウェアによる実時間ディジタルメディア処理向けシステムオンチップ(VLSIシステム)
- 文書情報管理システムBibliotheca/IS(1) : 文書情報管理の概要
- 情報のブロードキャッチシステム
- ヒューマンインタフェースの動向 : ポストGUIの座をめぐって
- マージ型ベクトル演算機構を用いた非数値処理の高速化方式
- ベクトル型データベースプロセッサIDP
- ベクトル計算機のための探索問題の計算法 : 並列バックトラック計算法
- ベクトル型高速データベースプロセッサIDP : ソート性能評価
- 次世代エディタ (エディタ)
- モジュラー・プログラミングのための支援環境
- プロセス・デバイス統合シミュレーションシステム : VFLの開発とデバイス設計への適用
- Hydrodynamic方程式を用いた高速イオン打ち込みシミュレーション方法の提案
- 蓄積拡散長を用いた高速三次元不純物分布シミュレーション
- B-7-15 帯域要求値の平均、分散を用いたQoS制御技術(B-7.情報ネットワーク,一般セッション)
- SB-6-4 "Active Edge"基本アーキテクチャの提案
- 共有部分がある複数データのベクトル処理方法
- リストのデータ構造変換にもとづく論理型言語プログラムのベクトル処理法とその評価
- 段階的変換によるLispプログラムのベクトル化
- プログラム変換にもとづくリストのベクトル処理方法とそのエイト・クウィーン問題への適用
- OR並列実行のための論理型言語プログラムのベクトル化法
- 配列の大域データフロー解析法