ベクトル計算機のための探索問題の計算法 「並列バックトラック計算法」
金田 泰, 小島 啓二, 菅谷 正弘, 情報処理学会論文誌, 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 のような論理型言語の ベクトル計算磯による高速実行の可能性を示唆している．
研究テーマ紹介: 論理 / 記号 ベクトル処理