vantreeck@logic.dec.com.UUCP (05/21/86)
I've read that parallel processor implementations of PROLOG machines use some variant of breadth first search. I was wondering if anybody has designed a parallel implementation using DFID (Depth First Iterative Deepening). Because it has been proven that DFID is the asymptotically optimal brute-force tree search algorithm (asymptotically optimal in cost of solution, space, and time), I was thinking that perhaps it may have usefulness in parallelism. Would it be worth while for me to try and develop an DFID-PROLOG for a single processor, e.g., on my Apple Macintosh? Or are their some problems that would would make such a PROLOG to large for the Mac? Is the algorithm applicable to a parallel PROLOG? George Van Treeck Digtal Equip. Corp. PS: If you're not familiar with the algorithm, it's description and proof of optimality can be found in: ARTIFICAL INTELLIGENCE 27(1985) 97-109
max@ecrcvax.UUCP (Max Hailperin) (05/28/86)
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)micha@ecrcvax.UUCP (Micha Meier) (05/28/86)
Some points to a possible implementation of DFID search in Prolog:
1. The DFID algorithm always finds the solution; so does a useful Prolog
program, unless it goes into an infinite loop. This means that DFID
can never find a solution in a shorter time than the usual Prolog:
either Prolog's depth-first search is faster or Prolog fails to
find anything and it loops. The same holds then for a parallell
implementation of DFID, it could only be a way to prevent infinite
loops in a better time than a serial DFID rather than speeding
up the search in comparison with Prolog.
2. DFID always finds the optimal solution, the usual Prolog finds
*any* and maybe all solutions if necessary. If the user wants to find
all solutions and the usual Prolog loops, DFID will loop as well;
therefore the use of DFID could be only restricted.
3. As Max says, the predicates would have to be divided into two
groups, ordered and unordered; this would be the case in any
non-sequential processing of the subgoals. If we allow ordered
predicates to call the unordered ones and vice versa then the
distribution of processors in a parallell execution is no more
so easy. There is maybe a simple solution to this problem, otherwise
one direction of calls between the two classes of predicates
must be forbidden - is it a significant restriction?
(I suspect anyway that this is another of George's attempts to bring
flames into net.lang.prolog, right? :-)
Michamax@ecrcvax.UUCP (Max Hailperin) (05/28/86)
Well, if George was trying to trigger flaming, he's succeeded. Strange that two researchers at the same center should flame at each other via a world-wide network, but I sincerely believe this is of general interest. Micha's comments aren't all wrong, but they certainly aren't 100% correct either. The big point he misses is this: If there is a branch of the tree to the left of the solution that is much deeper than the solution, but still finite, DFID is more efficient than depth-first search. This -- not questions of completeness -- is the argument for DFID which interests me. Naturally this case only arises in some class of programs, but that's the point -- I'm curious whether that class of programs is interesting. The point about ordered and unordered predicates calling each other is a bit confused. In reality there is no problem. If an unordered predicate calls an ordered predicate, and that ordered predicate fails because its execution was truncated, some solutions to the unordered predicate are lost -- but this doesn't matter. If an ordered predicate calls an unordered predicate, and the execution is truncated, the outer ordered' predicate fails, because of the general rule I proposed in my last note. Thus the right thing always happens. Much of the time all the programmer wants is one solution, any solution. In this case it doesn't matter whether it is the leftmost or shallowest (= "optimal"). If we can get the shallowest faster than the leftmost (or if they are the same, and we can get it faster by looking for the shallowest), than that's good. Naturally if you really want all solutions, DFID has nothing to offer. This can be viewed as a consequence of my execution rule for bagof. By the way, the proposed modified Prolog does not offer one control structure DFID can support that has been proposed in the context of other parallel Prologs: an unordered, one-solution predicate.
max@ecrcvax.UUCP (Max Hailperin) (05/30/86)
Well, I've devoted the last three days to working on the idea of a depth-first iterative-deepening Prolog, and it's potential for parallel implementation. The results are far from optimistic, particularly as far as parallelism goes. There are some applications which could be much more cleanly programmed in DFID-prolog then normal Prolog. (Read "programmed" as programmed with realistic efficiency.) In particular, many puzzle-solving programs fall into this category. As far as I can tell, not much else does. However, I also found that the DFID search can be quite cleanly programmed in Prolog in a way that keeps the distinction between logic and control fairly clear. Thus, I would guess that DFID doesn't warrant a modified Prolog interpreter, but rather merely inclusion in Prolog programmers' "bag of tricks." I also discovered that (contrary to my original claims) parallel deepening is *not* a good use for parallelism. The reason is simple: almost all the time in DFID search is in the last iteration (that's why DFID is asymptotically optimal). This means regardless of the depth of the search or the number of processors available, DFPD's speedup over DFID can be at most (1-1/b)^-2 (where b is the branching factor). Don't be fooled into thinking that for small b this is a significant speedup: this is merely saying that for small b DFID performs especially poorly. This means that even considering parallel processors, DFID is best considered an option for Prolog programmers and not for Prolog implementors.
alf@sicsten.UUCP (Thomas Sj|land) (06/11/86)
I agree with earlier statements that DFPD is rather useless as an approach
for or-parallel logic programming systems. It has one interesting point though:
It is hard to think of an or-parallel scheme which has a simpler implementation
than this one. The needed communication is minimal and the variable
representation is optimal ( = Warren's for instance). The price you pay is
reexecution. In all other schemes I have seen (in our lab there is work going
on considering a handful (sic!)) there are considerable measures taken as to
either reach a highly flexible variable representation (Haridi/Ciepielweski
/Hausman proposes hashing etc.) or trying to avoid copying through more or less
smart heuristics or even specialized hardware (Khayri/Fahlen/Karlsson).
All of these schemes involve a considerable amount of communication, at least
compared to DFPD.
An implementation of a DFPD Horn Clause prover ("pure Prolog") could show
useful in the sense that any proposed "smart" scheme has to be at least as
good as the DFPD scheme (for at least some subclass of programs and queries)
to be taken seriously. It is also interesting to notice that DFPD is
complete, whereas most of the "smarter" schemes are not.