密結合型マルチプロセッサシステム上でのProlog OR並列処理の実現

甲斐 宗徳  加茂 正充  佐藤 弘幸  笠原 博徳  

誌名
電子情報通信学会論文誌 D   Vol.J75-D1   No.8   pp.675-684
発行日: 1992/08/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 特集論文 (並列/分散処理論文特集)
専門分野: AI/分散協調
キーワード: 
並列探索,  論理型プログラミング言語,  マルチプロセッサシステム,  ダイナミックスケジューリング,  

本文: PDF(768.6KB)
>>論文を購入


あらまし: 
本論文では,筆者らがPrologのOR並列処理手法として従来提案している階層型挟み打ち探索法の共有メモリ型マルチプロセッサシステム上への実現法について述べる.階層型挟み打ち探索法は,Prologの処理課程をAND逐次・OR並列実行の条件下でOR木を用いて表現し,そのOR木を複数のプロセッサで左右から階層的に挟み打ちする形で並列かつ独立に深さ優先探索を行うというもので,他のOR並列処理手法に比べて更に大きなタスクグラニュラリティを得ることができ,部分木のプロセッサへのスケジューリングの頻度およびそれに伴うオーバヘッド,プロセッサ間のデータ転送オーバヘッドを低く抑えることができるという特徴をもっている.このような利点を実マシン上で実現することによって確かめると共に,PrologのOR並列処理において問題となっている再帰の並列化やassert等の副作用をもつ述語を含むプログラムへ対応するための改良点についても述べる.