时间戳

首页 > 解决方案 > Prolog中的平行素数？

multithreading - Prolog中的平行素数？

问题描述

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

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

标签： multithreadingparallel-processingprolog

解决方案

这是迄今为止我能做的最好的。我部署了 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

所以我猜这里介绍的花束解决方案，它没有大量的非常短暂的工作，在分配框架中造成的摩擦比没有花束的解决方案要小。

推荐阅读