CODEWITHSUNDEEP
multithreadingconcurrencyparallel-processingprologlogic
Joey Eremondi
Joey Eremondi

Reputation: 8423

Is there an automatic parallel prolog implementation?

I'm currently doing some research in theoretical computer science, and one of the main tools I'm using is prolog. I've found it particularly handy for writing very quick tests to disprove conjectures.

However, I've gotten to a point where the brute-force search is getting too slow. While I could use a different language, the whole point of my using prolog is that it's extremely fast/simple to write code to test a hypothesis.

I'm wondering, is there an implementation of Prolog that allows for automatic paralellization? It wouldn't have to be razor fast, but ideally I'm looking for something that I could just drop my code into and get at least a small speedup.

I don't know if this is possible. Google search reveals lots of academic articles about automatic parallelism in Prolog, but I didn't come across any implementations. However, I'm really only familiar with SWI-prolog, so I could definitely use advice from someone familiar with many implementations.

My code uses cuts, but I am fairly sure that I can eliminate them. As for IO, the only IO is printing to the console, which could probably be moved outside any parallel code.

Upvotes: 6

Views: 2702

Answers (3)

user502187
user502187

Reputation:

In Jekejeke Prolog I have tried to make it as simple as possible for a programmer and did offer a simple construct called balance/1. With balance/1 a generate and test problem:

 /* sequential */
 ?- Generate, Test.

Will be distributed over multiple threads. The invokation is as simple as wrapping the conjunction into the predicate balance/1. The result might undergo some reordering:

 ?- use_module(library(runtime/distributed)).

 /* parallel */
 ?- balance((Generate, Test)).

Here is an example parallel generation of prime numbers. The sequential code reads as follows:

:- use_module(library(advanced/arith)).

prime(N) :-
    M is floor(sqrt(N)),
    between(2,M,K),
    N mod K =:= 0, !, fail.
prime(_).

?- time(aggregate_all(count, 
                     (between(1,1000000,X), prime(X)), N)).
% Up 6,737 ms, GC 33 ms, Thread Cpu 6,656 ms (Current 07/16/19 01:49:02)
N = 78499

Doing the same in parallel gives:

?- time(aggregate_all(count, 
                      balance((between(1,1000000,X), prime(X))), N)).
% Up 4,167 ms, GC 39 ms, Thread Cpu 219 ms (Current 07/16/19 01:49:50) 
N = 78499

So there was a speed-up, since the problem could be run on multiple threads.

Upvotes: 1

Sergii Dymchenko
Sergii Dymchenko

Reputation: 7209

Are you sure you need parallelism to "get at least a small speedup"?

You say that you are only familiar with SWI-Prolog, so try other Prolog systems. According to the results of a benchmark at http://www.probp.com/performance.htm (which may or may not be relevant to your particular problem) you should try B-Prolog, YAP and SICStus-Prolog (this one is not free). If you're lucky, you can get several times speedup just from switching your Prolog system.

Another possible low-cost way to speed up - use a system with tabling support (B-Prolog, XSB or YAP) and just add something like :- auto_table. as a first line of your program. Depending on your problem and your existing program you can get significant speedup (or get no speedup at all).

Upvotes: 6

Davorin Ruševljan
Davorin Ruševljan

Reputation: 4392

With Prolog it is not difficult to find parallelism, it is difficult to choose which one to use ;) .

Maybe Parlog - logic based programming language, designed for parallel execution would be of help to you. There is implementation for windows but I am not sure if it uses multiple cores. You could however try to contact the authors there.

Upvotes: 5

Related Questions