Java 中的 Eratosthenes 平行筛
Parallelizing Sieve of Eratosthenes in Java
我正在尝试并行执行埃拉托色尼筛法。我制作了一个布尔列表，其中填充了给定大小的 true。每当找到素数时，该素数的所有倍数在布尔列表中都标记为假。
我试图使这个算法并行的方法是启动一个新线程，同时仍然过滤初始素数。例如，算法从素数 = 2 开始。在过滤器的 for 循环中，当素数 * 素数时，我制作了另一个 for 循环，其中检查素数 (2) 和素数 * 素数 (4) 之间的每个数字。如果布尔列表中的那个索引仍然为真，我启动另一个线程来过滤那个素数。
随着要过滤的质数不断增加，嵌套 for 循环会产生越来越多的开销，因此我将此限制为仅在质数 < 100 时执行此嵌套 for 循环。我假设到那时， 1亿个数字会被过滤掉。这里的问题是，这样，要过滤的素数保持在 9500 个素数以下，而算法停止在 10000 个素数 (prime * prime < size(100m))。我也认为这根本不是正确的方法。我在网上搜索了很多，但没能找到筛子的并行 Java 实现的任何示例。
我的代码如下所示：
主要class:
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);
}
}
}
}
}
亚军class:
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);
}
}
我觉得有一种更简单的方法可以解决这个问题...
你们有什么关于我如何使这种并行化工作并且可能更简单一些的建议吗？
创建高性能 并发 算法的实现比创建高性能的单线程实现要困难一些，例如埃拉托色尼筛法。原因是您需要找到一种方法来划分工作，从而最大限度地减少并行工作线程之间的通信和干扰。
如果您实现完全隔离，那么您可以希望速度提高到接近可用逻辑处理器的数量，或者在典型的现代 PC 上提高大约一个数量级。相比之下，使用筛子的良好单线程实现将使您的速度至少提高两到三个数量级。一个简单的逃避方法是在需要时简单地从文件加载数据，或者 shell 输出到像 Kim Walisch 的 PrimeSieve.
这样的体面的素数筛选程序。
即使我们只想看看并行化问题，仍然有必要对算法本身和运行它的机器有一些了解。
最重要的方面是现代计算机具有很深的缓存层次结构，其中只有 L1 缓存（通常为 32 KB）可以全速访问，而所有其他内存访问都会受到严重影响。翻译成埃拉托色尼筛法，这意味着您需要一次筛分一个 32 KB window 的目标范围，而不是将每个质数跨越许多兆字节。必须在平行舞开始之前筛选直到目标范围末端的平方根的小素数，但随后每个段或 window 可以独立筛选。
筛选给定的 window 或片段需要确定要筛选的小素数的起始偏移量，这意味着每个 window 的每个小素数至少有一个模除法，除法是a 操作极其缓慢。但是，如果您筛选连续段而不是任意 windows 放置在范围内的任何位置，那么您可以将每个素数的结束偏移量保留在一个向量中，并将它们用作下一段的开始偏移量，从而消除昂贵的计算起始偏移量。
因此，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 等筛选每个片段，而是在片段（甚至整个范围）上爆破预先计算的模式。这节省了时间，因为这些小素数在每个片段中进行了很多很多步骤，占了筛分时间的大部分。
还有更多可能的优化，包括一些更容易实现的成果，但要么 returns 正在减少，要么工作量曲线急剧上升。尝试在 Code Review 中搜索 'sieve'。另外，请不要忘记，除了算法问题和机器架构之外，您还在与 Java 编译器作斗争，例如数组边界检查之类的事情，您的编译器可能会或可能不会将其提升到循环之外。
给你一个大概的数字：在 C# 中，一个带有预先计算模式的单线程分段赔率筛选器可以在 2 到 4 秒内筛选整个 32 位范围，这取决于你应用了多少 TLC 除了上面提到的事情。在我老化的笔记本上，你的质数高达 100000000 (1e8) 的小得多的问题在不到 100 毫秒的时间内得到了解决。
这里有一些代码显示了 windowed 筛分的工作原理。为了清楚起见，我在读出素数等时放弃了所有优化，例如仅赔率表示或 wheel-3 stepping 等。它是 C#，但它应该与 Java 足够相似以便于阅读。
注意：我将筛子数组命名为eliminated，因为真值表示一个划掉的数字（省去了在开始时用所有真值填充数组，无论如何它更合乎逻辑）。
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);
}
我正在尝试并行执行埃拉托色尼筛法。我制作了一个布尔列表，其中填充了给定大小的 true。每当找到素数时，该素数的所有倍数在布尔列表中都标记为假。
我试图使这个算法并行的方法是启动一个新线程，同时仍然过滤初始素数。例如，算法从素数 = 2 开始。在过滤器的 for 循环中，当素数 * 素数时，我制作了另一个 for 循环，其中检查素数 (2) 和素数 * 素数 (4) 之间的每个数字。如果布尔列表中的那个索引仍然为真，我启动另一个线程来过滤那个素数。
随着要过滤的质数不断增加，嵌套 for 循环会产生越来越多的开销，因此我将此限制为仅在质数 < 100 时执行此嵌套 for 循环。我假设到那时， 1亿个数字会被过滤掉。这里的问题是，这样，要过滤的素数保持在 9500 个素数以下，而算法停止在 10000 个素数 (prime * prime < size(100m))。我也认为这根本不是正确的方法。我在网上搜索了很多，但没能找到筛子的并行 Java 实现的任何示例。
我的代码如下所示：
主要class:
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);
}
}
}
}
}
亚军class:
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);
}
}
我觉得有一种更简单的方法可以解决这个问题... 你们有什么关于我如何使这种并行化工作并且可能更简单一些的建议吗？
创建高性能 并发 算法的实现比创建高性能的单线程实现要困难一些，例如埃拉托色尼筛法。原因是您需要找到一种方法来划分工作，从而最大限度地减少并行工作线程之间的通信和干扰。
如果您实现完全隔离，那么您可以希望速度提高到接近可用逻辑处理器的数量，或者在典型的现代 PC 上提高大约一个数量级。相比之下，使用筛子的良好单线程实现将使您的速度至少提高两到三个数量级。一个简单的逃避方法是在需要时简单地从文件加载数据，或者 shell 输出到像 Kim Walisch 的 PrimeSieve.
这样的体面的素数筛选程序。即使我们只想看看并行化问题，仍然有必要对算法本身和运行它的机器有一些了解。
最重要的方面是现代计算机具有很深的缓存层次结构，其中只有 L1 缓存（通常为 32 KB）可以全速访问，而所有其他内存访问都会受到严重影响。翻译成埃拉托色尼筛法，这意味着您需要一次筛分一个 32 KB window 的目标范围，而不是将每个质数跨越许多兆字节。必须在平行舞开始之前筛选直到目标范围末端的平方根的小素数，但随后每个段或 window 可以独立筛选。
筛选给定的 window 或片段需要确定要筛选的小素数的起始偏移量，这意味着每个 window 的每个小素数至少有一个模除法，除法是a 操作极其缓慢。但是，如果您筛选连续段而不是任意 windows 放置在范围内的任何位置，那么您可以将每个素数的结束偏移量保留在一个向量中，并将它们用作下一段的开始偏移量，从而消除昂贵的计算起始偏移量。
因此，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 等筛选每个片段，而是在片段（甚至整个范围）上爆破预先计算的模式。这节省了时间，因为这些小素数在每个片段中进行了很多很多步骤，占了筛分时间的大部分。
还有更多可能的优化，包括一些更容易实现的成果，但要么 returns 正在减少，要么工作量曲线急剧上升。尝试在 Code Review 中搜索 'sieve'。另外，请不要忘记，除了算法问题和机器架构之外，您还在与 Java 编译器作斗争，例如数组边界检查之类的事情，您的编译器可能会或可能不会将其提升到循环之外。
给你一个大概的数字：在 C# 中，一个带有预先计算模式的单线程分段赔率筛选器可以在 2 到 4 秒内筛选整个 32 位范围，这取决于你应用了多少 TLC 除了上面提到的事情。在我老化的笔记本上，你的质数高达 100000000 (1e8) 的小得多的问题在不到 100 毫秒的时间内得到了解决。
这里有一些代码显示了 windowed 筛分的工作原理。为了清楚起见，我在读出素数等时放弃了所有优化，例如仅赔率表示或 wheel-3 stepping 等。它是 C#，但它应该与 Java 足够相似以便于阅读。
注意：我将筛子数组命名为eliminated，因为真值表示一个划掉的数字（省去了在开始时用所有真值填充数组，无论如何它更合乎逻辑）。
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);
}