prolog on the epiphany?

[CIB]

So, I'm working on my own information representation system, which has a few things in common with prolog. For that reason, I recently looked up prolog and the way it does proof search. Incidentally, the concept is almost identical to my idea, which also means that this should be incredibly simple to do in parallel.

Here's the gist of it: http://www.learnprolognow.org/lpnpage.p ... pn-htmlse6

So from what I understand, each core could simply be assigned an item that it tries to prove. The database to check for proofs could be stored on core-local memory(if very small), on on-die memory(if small) or if large-ish, the database could be stored in SDRAM and "streamed" through the epiphany. Each core can issue new "search commands", which will be scheduled to be run on the complete database on one of the cores. On the ARM cores, a "search graph" would be built, and the results from the individual cores would be assembled here as they come in.

Overally, it seems this would be a problem that could make very good use of both the parallella's parallel nature, *and* of the parallela's ability to do branches, execute different code on each core, etc.

Implementation is another matter. As I said, I'm working on something like this myself, and will probably eventually write a proof search optimized for the epiphany for my system. But whether prolog itself is a simple enough framework that pulling the proof search out into the epiphany is worthwhile, I don't know.

[over9000]

I thought about this a little bit too, but I think that you'd be better off looking at Erlang instead. There are various blog posts about how they've got it working, so you could have a look at that. From what I've read about Erlang, it's very similar to Prolog. I'm not sure how easy it would be to implement parallelism. Are you talking about at the level of each predicate? It seems pretty tricky ...

[fdeutschmann]

If you look into Prolog implementation research, you will find a lot done on parallel implementation in the '90s. In Prolog, there are two approaches to parallel evaluation: and-parallel and or-parallel; sometimes these are combined in the same implementation, but often a given Prolog is one or the other.

Choice points - alternate unifications - are or's; an or-parallel Prolog evaluates multiple different unifications in parallel. Or-parallel Prologs excel when asked to find many or all the solutions to a given query; they are less of a win for ordinary single-unification queries as they are frequently trying to unify where the results will never be used. Thus, or-parallelism is usually exposed to the programmer so that it can be enabled for only certain predicates.

And's - the comma for rules with multiple clauses - can also be evaluated in parallel. As with or-parallelism, and-parallelism is frequently exposed to the programmer so that the parallel functionality is not applied needlessly, or (particularly) on branches which make use of side effects.

Added: Note that both parallel approaches need to be controlled - by either the programmer or the system - to prevent running off in all directions at once: the unification (or's) and rule chaining (comma's - and's) is the control structure of a Prolog program, and if we evaluate all of these in parallel, we are attempting to explore all possible branches....

The 'pure' core of Prolog is very enticing, particularly from a parallel point of view. However, side effects and cuts wreak havoc with parallel functionality, which makes proper implementation of a high-performance Prolog quite complex. If we keep to the core of the language, using the language for pure knowledge representation / data storage, I think it is quite well suited to implementation on the Adapteva / Parallela. (Cuts are non-optional: proper use of cuts is essential to good Prolog programming.) With a good scheme for managing the local modifications to the knowledge base along each parallel path (on each eCore), and migrating the local changes to the global knowledge base, an Adapteva parallel Prolog could be quite performant - and might offer some significant advantages for data storage....

I suggest reading about the WAM (Warren Abstract Machine), and you might also look at a Prolog variant called CLP(R).

-frank

[CIB]

[fdeutschmann]