java - Java中的Eratosthenes并行筛选

Question

我正在尝试并行实现Eratosthenes筛。我做了一个布尔列表，其中填充了给定大小的true。每当找到素数时，布尔值列表中该素数的所有倍数都标记为false。

我试图使该算法并行的方式是通过启动一个新线程，同时仍然过滤初始素数。例如，该算法从prime = 2开始。在滤波器的for循环中，当prime * prime时，我制作了另一个for循环，其中检查了prime(2)和prime * prime(4)之间的每个数字。如果布尔值列表中的该索引仍然为true，则启动另一个线程以过滤该素数。

嵌套的for循环会随着要过滤的质数的发展而产生越来越多的开销，因此我将其限制为仅当质数<100时才进行此嵌套的for循环。我假设到那时，一亿个数字将是有点过滤。这里的问题在于，以这种方式，要过滤的素数保持在9500素数以下，而算法在10000素数处停止(素数*素数
我的代码如下所示:

主类:

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

创建像Eratosthenes的Sieve之类的算法的高性能并发实现比创建高性能单线程实现要困难一些。原因是您需要找到一种方法来对工作进行分区，以最大程度地减少并行工作线程之间的通信和干扰。

如果实现了完全隔离，则可以希望速度提高到接近可用逻辑处理器的数量，或者在典型的现代PC上达到一个数量级。相比之下，使用适当的筛子单线程实现将使您的速度至少提高2到3个数量级。一种简单的解决方案是在需要时简单地从文件中加载数据，或者将其打包到像Kim Walisch的PrimeSieve这样的体面的筛选程序中。

即使我们只想看一下并行化问题，仍然有必要对算法本身以及运行它的机器有一些了解。

最重要的方面是，现代计算机具有较深的缓存层次结构，其中只有L1缓存(通常为32 KB)可以全速访问，而所有其他内存访问都将受到严重的惩罚。转换为Eratosthenes筛网后，这意味着您需要一次将目标范围筛分一个32 KB窗口，而不是将每个素数跨过多个兆字节。在平行舞开始之前，必须筛分直至目标范围末端平方根的小素数，但随后可以分别筛分每个片段或窗口。

筛选给定的窗口或片段需要确定要筛选的小质数的起始偏移量，这意味着每个窗口和每个小质数至少有一个模除数是一个非常慢的操作。但是，如果筛分连续的段，而不是放置在范围内任何位置的任意窗口，则可以将向量中每个质数的结束偏移量保留下来，并将其用作下一个段的起始偏移量，从而避免了昂贵的起始偏移量计算。

因此，用于Eratosthenes筛网的一种有前途的并行化策略是为每个工作线程提供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等筛选每个片段，而是在片段(甚至整个范围)上展开预先计算的图案。这节省了时间，因为这些小的素数在每个段中进行了许多步骤，并占据了筛分时间的绝大部分。

还有更多的可能的优化方法，包括增加一些悬而未决的成果，但要么收益递减，要么努力曲线急剧上升。尝试在Code Review中搜索“筛子”。另外，别忘了除了算法问题和机器架构之外，您还在与Java编译器进行斗争，例如，数组边界检查之类的编译器可能会或可能无法退出循环。

为您提供一个大概的数字:在C#中，带有预计算模式的单线程分段仅占优势的筛子可以在2到4秒内筛分整个32位范围，这取决于您除上述内容外还应用了多少TLC。在我老化的笔记本电脑上，不到100毫秒就解决了您小得多的质数高达100000000(1e8)的问题。

这是一些显示窗口筛分工作原理的代码。为了清楚起见，我在读取素数时放弃了所有优化，例如仅赔率表示或wheel-3步进。它是C#，但是应该与Java足够相似，以便可读。

注意:我称筛子数组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);
}