Java中埃拉托色尼的平行筛

Question

我正在尝试对厄拉多塞的筛子进行并行实现。我做了一个布尔列表，对于给定的大小，用true填充。无论何时发现一个素数，该素数的所有倍数在布尔列表中都被标记为假。

我试图使这个html" target="_blank">算法并行的方法是在仍然过滤初始质数的同时启动一个新线程。例如，算法从素数 = 2 开始。在 for 循环中，当素数 * 素数时，我做另一个 for 循环，其中检查素数 （2） 和素数 * 素数 （4） 之间的每个数字。如果布尔列表中的该索引仍然为 true，我会启动另一个线程来过滤该质数。

随着要过滤的质数的进展，嵌套for循环会产生越来越多的开销，所以我将其限制为仅在质数时执行嵌套for循环

我的代码如下所示:

主要类：

public class Main {
    private static ListenableQueue<Integer> queue = new ListenableQueue<>(new LinkedList<>());
    private static ArrayList<Integer> primes = new ArrayList<>();
    private static boolean serialList[];
    private static ArrayList<Integer> serialPrimes = new ArrayList<>();
    private static ExecutorService exec = Executors.newFixedThreadPool(10);
    private static int size = 100000000;
    private static boolean list[] = new boolean[size];
    private static int lastPrime = 2;

    public static void main(String[] args) {
        Arrays.fill(list, true);

        parallel();
    }

    public static void parallel() {
        Long startTime = System.nanoTime();
        int firstPrime = 2;

        exec.submit(new Runner(size, list, firstPrime));
    }

    public static void parallelSieve(int size, boolean[] list, int prime) {
        int queuePrimes = 0;
        for (int i = prime; i * prime <= size; i++) {
            try {
                list[i * prime] = false;
                if (prime < 100) {
                    if (i == prime * prime && queuePrimes <= 1) {
                        for (int j = prime + 1; j < i; j++) {
                            if (list[j] && j % prime != 0 && j > lastPrime) {
                                lastPrime = j;
                                startNewThread(j);
                                queuePrimes++;
                            }
                        }
                    }
                }
            } catch (ArrayIndexOutOfBoundsException ignored) { }
        }
    }

    private static void startNewThread(int newPrime) {
        if ((newPrime * newPrime) < size) {
            exec.submit(new Runner(size, list, newPrime));
        }
        else {
            exec.shutdown();
            for (int i = 2; i < list.length; i++) {
                if (list[i]) {
                    primes.add(i);
                }
            }
        }
    }
}

亚军等级：

public class Runner implements Runnable {
    private int arraySize;
    private boolean[] list;
    private int k;

    public Runner(int arraySize, boolean[] list, int k) {
        this.arraySize = arraySize;
        this.list = list;
        this.k = k;
    }

    @Override
    public void run() {
        Main.parallelSieve(arraySize, list, k);
    }

}

我觉得有一种更简单的方法来解决这个问题……你们有什么建议可以让我如何使这个并行化工作，也许会更简单一些？

Answer 1

创建一个高性能的并发算法实现，比如厄拉多塞的筛子，比创建一个高性能的单线程实现要困难一些。原因是您需要找到一种方法来划分工作，使并行工作线程之间的通信和干扰最小化。

如果您实现了完全隔离，那么您可以希望速度提高接近可用逻辑处理器的数量，或者在典型的现代PC上大约提高一个数量级。相比之下，使用良好的单线程筛选实现将使您的加速至少达到两到三个数量级的速度。一种简单的规避方法是在需要时从文件中加载数据，或者向一个像样的主筛选程序（如Kim Walisch的PrimeSieve）发送数据。

即使我们只想研究并行化问题，仍然有必要深入了解算法本身并对其运行进行机器处理。

最重要的一点是，现代计算机具有深度缓存层次结构，其中只有L1缓存（通常为32 KB）可以全速访问，所有其他内存访问都会受到严重的惩罚。这意味着您需要一次筛选一个32 KB的窗口，而不是跨越多个兆字节的每个素数。在平行舞开始之前，必须对达到目标范围末端平方根的小素数进行筛选，然后可以独立筛选每个片段或窗口。

筛选给定的窗口或段需要确定您要筛选的小素数的开始偏移，这意味着每个窗口和除法中的每个小素数至少有一个模除法是一个极其缓慢的操作。但是，如果您筛选连续的段，而不是放置在范围内任何地方的任意窗口，那么您可以将每个素数的结束偏移保留在向量中，并将它们用作下一个段的开始偏移，从而消除了开始偏移的昂贵计算。

因此，厄拉多塞筛选的一个有前途的并行化策略是给每个工作线程一组连续的32 KB块进行筛选，这样每个工作线程只需要计算一次起始偏移量。这样，工作者之间就不会有内存访问争用，因为每个工作者都有自己独立的目标范围子范围。

但是，在您开始并行化之前——即使您的代码更加复杂——您应该首先精简它并将要完成的工作减少到绝对的基本要素。例如，看看代码中的这个片段：

for (int i = prime; i * prime <= size; i++)
   list[i * prime] = false;

不是在每次迭代中重新计算循环边界并用乘法索引，而是对照预先计算的循环不变值检查循环变量，并将乘法减少到迭代加法:

for (int o = prime * prime; o <= size; o += prime)
   list[o] = false;

有两种简单的筛子特定优化，可以产生显著的速度控制杆。

1）把偶数从你的筛子里拿出来，在需要的时候凭空拉出素数2。答对了，你刚刚把你的表现翻了一番。

2)不是通过小的奇素数3、5、7等来筛选每个片段，而是在该片段(或者甚至整个范围)上爆炸预先计算的模式。这样可以节省时间，因为这些小素数在每一段中都要走很多很多步，并且占据了筛选时间的绝大部分。

还有更多可能的优化，包括几个更容易实现的目标，但是要么回报正在减少，要么努力曲线急剧上升。试着在代码评论中搜索“筛子”。此外，不要忘记，除了算法问题和机器架构之外，你还在与一个Java的编译器作斗争，比如数组边界检查，你的编译器可能会也可能不会从循环中提升出来。

给你一个大概的数字:在C#中，一个带有预计算模式的单线程分段奇数筛选可以在2到4秒内筛选整个32位范围，这取决于除了上面提到的事情之外你还应用了多少TLC。你的小得多的高达100000000 (1e8)的素数问题，在我的旧笔记本上不到100毫秒就解决了。

这里有一些代码展示了窗口筛选是如何工作的。为了清楚起见，我省略了所有的优化，比如读出质数时的奇数表示或三轮步进等等。它是C#，但应该和Java足够相似，以便于阅读。

注意:我将sieve数组称为< code>eliminated,因为true值表示一个被划掉的数字(省去了在开始时用全true填充数组，这样更符合逻辑)。

static List<uint> small_primes_between (uint m, uint n)
{
    m = Math.Max(m, 2);

    if (m > n)
        return new List<uint>();

    Trace.Assert(n - m < int.MaxValue);

    uint sieve_bits = n - m + 1;
    var eliminated = new bool[sieve_bits];

    foreach (uint prime in small_primes_up_to((uint)Math.Sqrt(n)))
    {
        uint start = prime * prime, stride = prime;

        if (start >= m)
            start -= m;
        else
            start = (stride - 1) - (m - start - 1) % stride;

        for (uint j = start; j < sieve_bits; j += stride)
            eliminated[j] = true;
    }

    return remaining_numbers(eliminated, m);
}

//---------------------------------------------------------------------------------------------

static List<uint> remaining_numbers (bool[] eliminated, uint sieve_base)
{
    var result = new List<uint>();

    for (uint i = 0, e = (uint)eliminated.Length; i < e; ++i)
        if (!eliminated[i])
            result.Add(sieve_base + i);

    return result;
}

//---------------------------------------------------------------------------------------------

static List<uint> small_primes_up_to (uint n)
{
    Trace.Assert(n < int.MaxValue);    // size_t is int32_t in .Net (!)

    var eliminated = new bool[n + 1];  // +1 because indexed by numbers

    eliminated[0] = true;
    eliminated[1] = true;

    for (uint i = 2, sqrt_n = (uint)Math.Sqrt(n); i <= sqrt_n; ++i)
        if (!eliminated[i])
            for (uint j = i * i; j <= n; j += i)
                eliminated[j] = true;

    return remaining_numbers(eliminated, 0);
}