Parallel Example

In this example, we demonstrate how Jekejeke Prolog can be used for parallel search. We will determine the perfect numbers between 1 and 10'000. Perfect numbers were already mentioned in Euclid's Elements and also considered by Euler. A perfect number is such that the proper divisors sum up the number itself. Here is how to decide 28:

1 || 28, 2 || 28, 4 || 28, 7 || 28, 14 || 28
1 + 2 + 4 + 7 + 14 = 28 ✓

A Prolog code to check for perfect numbers needs to be able to compute the sum of a set of numbers. Since Prolog does only have lists and not sets, we use a list without duplicates to represent a set. Summing a list can be coded as a simple recursive predicate sum_list/2 directly as follows:

sum_list([], 0).
sum_list([X|Y], R) :-
sum_list(Y, H), R is X+H.

?- sum_list([1,2,4,7,14],X).

The above predicate could be rewritten into a predicate with an accumulator, which would then be tail recursive. To find the list of divisors we use the built-in predicates between/3 and findall/3. The largest proper divisor can only be the size of half of the number, so that we only need to search up to half of the number:

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

?- findall(Z, (between(1,14,Z), 28 rem Z=:=0), L).
L = [1,2,4,7,14]

The idea is now a predicate perfect/2, which puts everything together. This predicate will first determine the half of the number, then collect the divisors and finally compute the sum and check whether it equals the given number. Our predicate should answer "yes" for 28 and for non-perfect numbers it should answer "no":

perfect(X) :- Y is X//2,
findall(Z, (between(1,Y,Z), X rem Z=:=0), L),
sum_list(L, X).

?- perfect(27).
No

?- perfect(28).
Yes

The first four perfect numbers were the only ones known to early Greek mathematics, the mathematician Nicomachus had noted 8128 as early as 100 AD. The above predicate is a brute force solution and does not use much number theory. It can already find the perfect numbers between 1 and 10'000 in a reasonable time.

?- between(1,10000,X), perfect(X).
X = 6 ;
X = 28 ;
X = 496 ;
X = 8128 ;
No

?- time((between(1,10000,X), perfect(X), fail; true)).
% Up 2,965 ms, GC 11 ms, Thread Cpu 2,938 ms
(Current 02/01/19 15:31:25)

?- time((between(1,20000,X), perfect(X), fail; true)).
% Up 11,818 ms, GC 94 ms, Thread Cpu 11,672 ms
(Current 02/01/19 15:43:35)
Yes

One way to speed up the search is to use more CPU power. We will now explain how Jekejeke Prolog can help in running a search on multiple CPUs. Usually setting up a parallel solution involves using the modules "thread", "pipe" and "group". The predicate balance/[1,2] from the module "distributed" abstracts away all these details.

The predicate balance/1 implements a non-deterministic distributed generate and test. The predicate balance/2 allows additionally specifying the number of desired threads. Using a modern microprocessor with a modern operating system, multiple threads will run truly parallel on multiple cores. The only bottleneck being the shared memory:

?- time((balance((between(1,10000,X), perfect(X))), fail; true)).
% Up 1,587 ms, GC 14 ms, Thread Cpu 0 ms (Current 02/01/19 15:40:45)
Yes

?- time((balance((between(1,20000,X), perfect(X))), fail; true)).
% Up 6,800 ms, GC 57 ms, Thread Cpu 0 ms (Current 02/01/19 15:45:34)
Yes

In the above query, we used the predicate balance/1 without specifying the number of desired threads. The predicate will then use the number of logical CPUs of the main board. When using the predicate balance/1 also some new overhead will be inducted by the setup and teardown of the threads, and the communication between threads.


Figure: Measurements on a Lenovo Ideapad and on a Huawei Media Pad

The predicate balance/1 is both available on the non-Android and Android platform. On both platforms, the modules "thread" and "group" were implemented via the platform Java thread and thread groups. On the other hand, the module "pipe" uses some custom Queues implemented with the platform Java monitors.

Comments