Prolog中的平行素数? [英] Parallel Primes in Prolog?

问题描述

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

I have the following simple code to determine prime numbers. Its a simple generate and test, not extremly optimized:

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 中并行化多个线程上的素数列表?输出列表不需要排序.

How would I parallelize the listing of primes over multiple threads in Prolog? The output listing need not be sorted.

推荐答案

这是迄今为止我能做的最好的事情.我部署了 JDK 13.0，它在顺序上更差，但在并行上更好.我使用 balance/1 谓词，但也应用了一些代码转换.

This is the best I could do so far. I deployed JDK 13.0 which is worse in sequential, but better in parallel. I use the balance/1 predicate, but apply also some code transformation.

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

The code transformation is such that I slice the range into bouquets with 1000 numbers, and already do a aggregation. Testing was carried out on a i7-6700HQ which has 8 logical CPUs:

顺序:

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 的数量.

Edit 17.07.2019:
Changed the time/1 predicate so that it also shows the thread CPU time spent in all spawned threads. It seems that the solution is near optimal, since it has a logical CPU utilization which is close to the number of logical CPUs.

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

Here are some ratios Thread-Time/Up-Time:

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

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

所以我猜这里介绍的花束解决方案与没有花束的解决方案相比，它没有大量的短期工作，在分发框架中造成的摩擦更少.

So I guess the bouquets solution presented here, which does not have very short lived jobs in a high number causes less friction in the distribution framework than the solution with no bouquets.

这篇关于Prolog中的平行素数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！