Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!genrad!panda!husc6!harvard!seismo!mcvax!unido!ecrcvax!max From: max@ecrcvax.UUCP (Max Hailperin) Newsgroups: net.lang.prolog Subject: Re: Depth First Iterative Deepening in parallel PROLOGs Message-ID: <233@ecrcvax.UUCP> Date: Wed, 28-May-86 08:38:26 EDT Article-I.D.: ecrcvax.233 Posted: Wed May 28 08:38:26 1986 Date-Received: Fri, 30-May-86 09:12:07 EDT References: Reply-To: max@ecrcvax.UUCP (Max Hailperin) Organization: ECRC, D-8000 Muenchen 81, W. Germany Lines: 90 George Van Treeck raised the interesting question of depth-first iterative-deepening (DFID) search's applicability to Prolog execution in general and parallel execution in particular. A quick check with the gurus around here (ECRC is a major center of Prolog activity) came up with no knowledge of any existing literature on DFID and Prolog. But of course there might be some. What follows are my own comments, in the absence of any literature. DFID could be integrated into a Prolog interpreter. The language it interpreted would have to be a bit modified, as the standard Prolog control structures and side-effect primitives wouldn't work. The smallest possible change in language definition (I think) would be: - declaration of ordered vs. unordered predicates - cuts only allowed in ordered predicates - no side-effects (assert, retract, I/O). The three non-obvious points in the design of such an interpreter are - negation as failure - bagof - ordered predicates. The implementation of these three features has to take as its guiding rule: truncating the search at a particular depth may only eliminate solutions, never add any. Concretely this means that when executing not(X), you have to keep a record of whether the cutoff-depth is reached in executing X. If so, then not(X) should fail even if X failed. This is because X might have succeeded given a greater cutoff-depth. The same technique is necessary for bagof: if it is possible that not all members of the bag were found, the bagof should fail. Similarly, if a clause of an ordered predicate fails, but had been prematurely truncated by the cutoff-depth, the whole predicate should fail, even if clauses remain. The next question is whether DFID would do any good. In today's Prolog programs it wouldn't, because the average branching factor is extremely low (between 1 and 2). The graph in the article in Artificial Intelligence shows quite clearly how big a loss DFID search is with such a low branching factor. Moreover Prolog programmers are very clever about always putting the easiest clauses first, and also use non-logical constructs to direct the search. Prolog execution is not a brute-force search in a well-balanced tree. So for normal Prolog programs, DFID would make the execution slower rather than faster. Whether the class of programs no one writes with today's Prologs but would write if they had a DFID Prolog is an interesting class of programs is an open question. Note, however, that DFID can also be used for only those portions of a program which would benefit from it. There have also been proposals for adding heuristic control information to Prolog's search. This would encourage programmers to use Prolog's built-in search rather than programming their own. Thus some amount of optimism about DFID's applicability may be justified. Finally comes the question of parallel execution (my own specialty). *If* DFID were useful (see the paragraph above), or in fact if it even came close to the performance of normal depth-first search, then a parallel version could be a practical way of exploiting parallel processing for logic programming. For example, if we could find interesting programs that a DFID Prolog executed at half the speed of normal Prolog, then by using 20 processors we could hope to get an order-of-magnitude speedup over normal Prolog. This possibility is so interesting because DFID has an extremely easy, low overhead parallel version. The idea is that each depth-first search is still sequential, but the search for the proper depth is done in parallel. This "DFPD" (depth-first parallel-deepening) strategy might for example have processor A search to a depth of 1 in parallel with processor B searching to a depth of 2. As soon as A is done, it starts searching to a depth of 3. In general: each time a processor is free, it starts a depth-first search with the next untaken cutoff-depth. This has a much lower communication and coordination overhead than OR-parallel Prologs. Returning to my original caution: DFPD is only a speedup over DFID, *not necessarily* over other forms of search. With a finite number of processors, there will be many realistic programs (virtually all of today's Prolog programs) for which even a normal single-processor depth-first search will be faster than DFPD. (In the infinite-processor case DFPD can be no worse than depth-first search.) Thus this is only a useful use of parallelism if we write programs for which DFID performs at least comparably to depth-first search. Conclusions: 1) a DFID Prolog is easily implementable, though not for normal Prolog 2) today's Prolog programs would not benefit from DFID (in fact, they would suffer) 3) it is possible that conclusion 2 can be changed (particularly if Prolog is extended to accept heuristic control information) 4) if conclusion 2 were changed, generalizing DFID to DFPD would be an easy way to make use of parallel processing (actually it's not necessary that conclusion 2 be changed -- DFID need only approach depth-first search in efficiency, not surpass it)