multithreading - Prolog中的并行素数？

Question

我有以下简单的代码来确定素数。它是一个简单的生成和测试，而没有极端优化:

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

这是一个示例运行:

?- between(1,20,N), prime(N), write(N), nl, fail; true.
1
2
3
5
7
11
13
17
19
true.

我如何并行化Prolog中多个线程上的素数列表？输出列表无需排序。

Answer 1

到目前为止，这是我能做的最好的事情。我部署了JDK 13.0，其顺序性能较差，但并行性能较好。我使用了balance/1谓词，但也应用了一些代码转换。

代码转换是这样的，我将范围切成具有1000个数字的花束，并且已经进行了聚合。在具有8个逻辑CPU的i7-6700HQ上进行了测试:

顺序的:

Jekejeke Prolog 4, Runtime Library 1.4.0 (July 6, 2019)

?- time(count(N)).
% Up 8,655 ms, GC 39 ms, Thread Cpu 8,593 ms (Current 07/16/19 16:47:49)
N = 78499

平行线:

?- time(count2(N)).
% Up 2,628 ms, GC 4 ms, Thread Cpu 0 ms (Current 07/16/19 16:48:16)
N = 78499

这是源代码:

:- use_module(library(advanced/arith)).
:- use_module(library(advanced/aggregate)).
:- use_module(library(runtime/distributed)).

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

/* sequential */
count(N) :-
   aggregate_all(sum(M), (between(1, 1000, Y), slice(Y, M)), N).

/* parallel */
count2(N) :-
   aggregate_all(sum(M), balance((between(1, 1000, Y), slice(Y, M))), N).

slice(Y, M) :-
   aggregate_all(count, (H is Y*1000, L is H-999, between(L, H, X), prime(X)), M).

编辑17.07.2019:
更改了time/1谓词，以便它还显示了所有派生线程中花费的线程CPU时间。似乎该解决方案几乎是最佳的，因为它的逻辑CPU利用率接近逻辑CPU的数量。

以下是线程时间/正常运行时间的一些比率:

/* parallel, primes 1, no bouquets */
25622/5732 ~ 4.46 

/* parallel, primes 2, bouquets */
21464/2717 ~ 7.89 

因此，我想这里介绍的花束解决方案与没有花束的解决方案相比，该解决方案没有大量的短期工作，导致分配框架中的摩擦较小。