Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!watmath!clyde!burl!ulysses!allegra!princeton!caip!lll-crg!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: <236@ecrcvax.UUCP> Date: Fri, 30-May-86 15:19:19 EDT Article-I.D.: ecrcvax.236 Posted: Fri May 30 15:19:19 1986 Date-Received: Mon, 2-Jun-86 16:53:51 EDT References: Reply-To: max@ecrcvax.UUCP (Max Hailperin) Organization: ECRC, D-8000 Muenchen 81, W. Germany Lines: 28 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.