OR-Parallel Prolog and Search Problems in Artificial Intelligence
T.J.Reynolds and
P. Kefalas
Abstract: This paper describes the language
Brave, updating previous papers. Brave is a dialect of Prolog designed
for all-solutions parallel execution. The language allows control of OR-parallelism
by means of clause terminators and an if_ then_else construction. Language
constructs allow collection of solutions into lists, as well as splitting
lists to generate OR-parallelism. Brave does not possess a cut or the general
power of assert and retract, instead a special database for partial results
or lemmas is provided. Meta-directives under programmer control decide
which results to lemma as well as controlling search by pruning on the
basis of lemma information. We consider the application of Brave to search
problems in Artificial Intelligence and demonstrate how the meta-control
of Brave can be used to write parallel versions of well-known algorithms.
Results are presented for the performance of parallel Branch-and-Bound
and Alpha-Beta pruning using a multi-processor simulator.
Keywords: Prolog, OR-Parallelism, Memoisation, Branch
& Bound, Alpha-Beta Pruning
Appeared in: Proc. of the 7th Intern. Conf. in Logic Programming,
D.H.D.Warren and P.Szeredi (eds.), pp 340-354, MIT Press, Jerusalem,Israel,1990
Available: Hardcopy on request from the authors. .
Back
to Dept. of Computer Science, CITY Liberal Studies
Back
to Petros Kefalas home page