Can I implement a Warren Abstract Machine Runtime to run Prolog on Massively-Parralell MIMD Chips?

[DrRuhe]

Hi everyone,

I am a student at TU-Berlin starting to write my bachelor's thesis.
The plan is to see how well backtracking can be done on massively parallel MIMD systems such as a Graphcore IPU. During the research, I stumbled across the fact that most Prolog implementations use the Warren Abstract Machine as the compile target. Therefore I had the idea to implement a runtime for WAM-Code for these IPUs.

Sadly I have no experience with a WAM, so it is impossible for me to judge if and how well it is possible to implement such a runtime for this hardware.

This brings me to my questions:

• If I have an Implementation that can execute the WAM-Code on this special hardware, can I then just execute the transpiled Prolog programs?
• Is it possible to parallelize the execution of the Warren Abstract Machine to gain a speed improvement?
• Roughly how much effort would be needed to implement the Runtime? I see the /src/machine folder (which is where I assume the whole WAM-Runtime of scryer lives) is around 30k lines of rust code, so I hope most of it is not necessary for a minimal implementation.

[UWN]

That projects sounds way too ambitious for a Bachelor's Thesis. You might do some proof-of-concept measurements and on (meta-interpreted) emulators. No more.

[aarroyoc]

Hi DrRuhe, parallelizing Prolog is a very interesting subject and I think there are a lot of things still to be done, both in implementations and in APIs.
I'm not really an expert but I think I can comment on a few things:

• Compilation of Prolog programs to WAM is not standardized. Most Prolog systems compile to WAM in memory, in their own format, and then execute. It's a very coupled component to the rest of the system unlike other bytecode VMs like BEAM or JVM. For example, in Scryer Prolog it's impossible to "compile" the Prolog code to WAM and later, in another process, execute it. A problem that arises is that Prolog code can create new code dynamically... Probably the system that solves these issues the best way is GNU Prolog which can compile Prolog to native code.
• Prolog code by default can contain non-pure code. That means that any piece of code can generate side-effects that will go very wrong if they're executed in a different order. However, you can try to define a subset where is easier to do parallelization. There is some literature around AND-parallelism and OR-parallelism. They slightly change the execution strategy without changing the API so they're for free to the developer. Also, take a look at Fleng, a language similar to Prolog but concurrent from scratch.
• Even if you do not change the execution strategy, you can get speedups by parallelizing some internal code, Intel did an article about that on SWI-Prolog
• You'll probably find interesting this paper about running Datalog on GPUs
• There's finally the whole topic of adding some API or indication to get parallelization on some stuff (parallel_maplist(?), Jolog, channels (with/without actors),...)

Greetings!

[EricGT]

Don't overlook concurrent_forall/2,3. Here is a simple SWI-Prolog example of it being used.