PROLOG階層型挟み打ち並列探索法のALLIANT FX/4上での性能評価

概要

論文の詳細を見る
本稿では、従来筆者等が提案している階層型挟み打ち探索法と呼ぶPROLOGの並列処理手法をマルチプロセッサ・ミニ・スーパーコンピュータALLIANT FX/4(DSP9040上で実現したのでその結果について報告する。この並列処理手法はOR並列を扱うものであり、PROLOGの処理過程をAND逐次実行の条件下でOR木を用いて表現し、そのOR木を複数のプロセッサが左右から階層的に挟み打ちをする形で並列かつ独立に深さ優先探索を行うというものである。この手法ではプロセッサへの負荷割り当て単位(タスクグラニュラリティ)を大きくとることができ、負荷の割り当て制御(スケジューリング)の頻度を低減させ、スケジューリングによるオーバーヘッドを低く抑えることができる。また、プロセッサ台数以上の速度向上すなわち加速異常が得られることがシミュレータ上で確認されている。本手法は、汎用目的マルチプロセッサシステムOSCAR上でのPROLOGの並列処理手法として開発されたものであるが、それに先立って本手法の実システム上での有効性を実証するために今回FX/4上で実現したものである。
1988-09-12