并行化大循环并改进高速缓存访​​问

Question

我有一个类似于以下代码的代码，用于在一个范围内查找素数（使用Eratosthenes筛选）并使用OpenMP进行并行化。在此之前，我有一个预处理阶段，我将所有的偶数和3和5的倍数标记出来，这样我就不必在这个阶段做更少的工作。 测试床共享三级缓存为12MB，物理内存为32 GB。我正在使用12个线程。 flag阵列是unsigned char。

#pragma omp parallel for 
for (i = 0; i < range; i++) 
{ 
    for (j = 5; j < range; j+=2) 
    { 
     if(flag[i] == 1 && i*j < range) 
      if (flag[i*j] == 1) 
       flag[i*j] = 0; 
     } 
} 

这个程序适用于小于1,000,000的范围......但是在此之后，执行时间会在更大范围内出现;例如range = 10,000,000这个程序需要大约70分钟（不适合缓存？）。我已经修改了上面的程序来合并循环平铺，以便它可以将缓存用于任何循环范围，但即使阻塞方法似乎也很耗时。交换循环也不利于大范围。

如何修改上面的代码来处理大范围？我怎么能重写代码，使其完全平行（range和flag [因为flag数组非常大，所以我不能声明它是私人]共享）？

Answer 1

其实，我只是注意到你的代码中有一些简单的加速。因此，在进入快速算法之前，我会提及这些：

1. 使用位域而不是char数组。您可以在内存中保存8个因子。
2. 你的外循环遍历所有整数。不仅仅是素数。每次迭代之后，从尚未被划掉的第一个数字开始。 （该数字将是素数）

我建议您这样做，因为您提到需要70分钟。在一台（非常强大的）机器上运行N = 10,000,000。这看起来不正确，因为我自己的简单实现可以在笔记本电脑上在20秒内完成N = 2^32 - 单线程，无源级优化。那么我注意到你错过了一些基本的优化。

以下是有效的解决方案。但需要一些工作。

关键是要认识到Eratosthenes筛只需要达到您的目标尺寸的sqrt（N）。换句话说，在完成之前，您只需要在sqrt（N）的所有素数上运行筛选。

所以诀窍是首先在sqrt（N）上运行算法。然后将所有素数转储为密集的数据结构。通过预先计算所有需要的素数，可以打破对外部循环的依赖。

现在，对于来自sqrt（N） - N的其余数字，您可以将预计算表中任何素数都可以除的所有数字相除。请注意，这对所有剩余的数字都是独立的。所以这个算法现在是令人尴尬的并行。

为了保持高效，需要使用适合缓存的块上的“迷你”环境。为了更有效率，您应该计算并缓存表中所有素数的倒数。这将帮助您在填写每个“小筛”时有效地找到每个素数的“初始偏移量”。

运行sqrt（N）顺序算法的初始步骤将非常快，因为它只是sqrt（N）。其余的工作是完全可并行化的。

在完全一般的情况下，该算法可以在初始筛上递归应用，但这通常是矫枉过正的。