« Vectorization Techniques for Prolog | メイン | A General-Purpose Conjunctive Iterative Control Structure for Prolog »

ベクトル計算機のための探索問題の計算法 「並列バックトラック計算法」

金田 泰, 小島 啓二, 菅谷 正弘, 情報処理学会論文誌, Vol. 29, No. 10, pp. 985-994, 1988.

[ English page ]
[ PDF 版論文へのいりぐち (IPSJ) ]

要旨: この論文では,探索問題に適用することができる,ベクトル計算機むきの あたらしい計算法並列バックトラック計算法をしめす. この方法にしたがって Fortran でプログラムを記述すれば, 数値計算専用とかんがえられていた S810 のようなスーパ・ コンピュータや,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 のような論理型言語の ベクトル計算磯による高速実行の可能性を示唆している.

研究テーマ紹介: 論理 / 記号 ベクトル処理

キーワード: 探索問題, くみあわせ最適化, 組合せ最適化, 組み合わせ最適化, バックトラック, 記号処理ベクトル化, ベクトル記号処理, 並列記号処理, スーパーコンピューティング, スーパー記号処理, 並列処理, ベクトル処理

コメントを投稿

About

1988-10-01 00:00に投稿されたエントリーのページです。

他にも多くのエントリーがあります。メインページアーカイブページも見てください。

(C) 2008 by Yasusi Kanada
Powered by
Movable Type 3.36