1

我正在尝试将此素筛分功能转移到使用 Parallel.For 以便它可以利用多个核心。

但是，当我运行它时，b 变量的值似乎随机跳跃甚至根本没有变化，尤其是对于较高的 To 值。

static List<long> Sieve(long To)
{
    long f = 0;
    To /= 2;

    List<long> Primes = new List<long>();
    bool[] Trues = new bool[To];

    if (To > 0)
        Primes.Add(2);

    long b = 0;

    Parallel.For(1L, To, a =>
    {
        b++;

        if (Trues[b])
            return;

        f = 2 * b + 1;
        Primes.Add(f);

        for (long j = f + b; j < To; j += f)
            Trues[j] = true;
    });

    return Primes;
}

发生了什么事，我怎样才能阻止这种情况发生？

4

3 回答 3

1

欢迎来到多线程的美妙世界。

马上，我可以看到循环的每次迭代都执行 a b++，然后b在整个过程中使用。这意味着循环的每次迭代都将b在所有其他迭代中修改 的值。

您可能想要做的是使用a在您的内联函数中提供的变量，这正是您似乎试图用b. 如果情况并非如此，那么您应该在b对其进行处理之前研究锁定并将其值复制到本地（每次迭代）变量。

试试这个，让我知道这是否是你想做的：

static List<long> Sieve(long To)
{
    To /= 2;

    List<long> Primes = new List<long>();

    if (To > 0)
        Primes.Add(2);

    Parallel.For(1L, To, a =>
    {
        long f = 2 * a + 1;
        Primes.Add(f);
    });

    Primes.Sort();

    return Primes;
}
于 2013-01-31T21:08:19.880 回答
1

您在这里面临的问题称为race conditions，当多个 CPU 内核将相同的变量加载到各自的缓存中，处理它，然后将值写回 RAM 时会发生这种情况。显然，在此期间，写回 RAM 的值可能已经过时了（例如，当核心在变量被另一个值覆盖之前加载变量时）

首先：我不会使用b++，而是int i = Interlocked.Increment(ref b);。Interlocked.Increment 确保没有 2 个线程尝试同时增加相同的值。结果是将增加的值保存到变量i中。这非常重要，因为您需要该值在 for 循环的每次迭代中保持不变，否则这是不可能的，因为其他线程将递增该变量。

接下来是您的变量f和a（定义为 For-iterator）。忘记f，a改用。

f = 2 * b + 1; // wrong
a = 2 * b + 1; // correct

最后： System.Collections.Generic.List不是，我重复一遍（因为它很重要）不是线程安全的。有关详细信息，请参阅http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx 。

Primes.Add(f); // will likely break something
lock (Primes)  // LOCK the list
{
    Primes.Add(a); // don't forget, we're using 'a' instead of 'f' now
}

该lock关键字仅接受引用类型变量作为参数，这是因为锁定变量不会阻止另一个线程访问它。相反，您可以将其想象为在引用之上设置一个标志，以便向其他线程发出信号I'm working here, please do not disturb!

当然，如果另一个线程在Primes没有事先要求锁定它的情况下尝试访问，该线程仍然可以访问该变量。

不过，您应该已经学会了所有这些，因为 Parallel Prime Sieve 是第一次学习多线程时最常见的初学者练习之一。

编辑：

完成上述所有步骤后，程序不应该乱跑；但这并不意味着解决方案是正确的，或者您将获得加速，因为您的许多线程将做重复的工作。

假设Thread a有责任标记每个 3 的倍数，而Thread n有责任标记 9 的倍数。当顺序运行时，当Thread n开始处理 9 的倍数时，它会看到 9 已经是另一个的倍数 (素数）数。但是，由于您的代码现在是并行的，因此无法保证Thread n在开始工作时会标记 9 。更不用说 - 因为 9 可能没有被标记 - 可能会被添加到素数列表中。

因此，您必须依次找到 1 和 的平方根之间的所有素数To。为什么是平方根To？那是你必须自己找出来的东西。

一旦你找到了从 1 到 的平方根的所有素数To，你就可以开始你的平行素数筛，以便使用之前找到的所有素数来找到剩余的素数。

最后一个值得注意的一点是，只有在填充之后Primes才应该构建它。那是因为： Trues

1.你的线程只需要处理 2 的平方根的倍数To，因此在当前实现中不会在根之外添加更多元素Primes。

2.如果您选择让您的线程超出根目录，您将面临一个问题，即您的一个线程将Primes在另一个线程将该数字标记为非素数之前不久添加一个非素数，这不是什么你要。

3.即使你很幸运，所有元素Primes确实都是 1 和 之间的素数To，它们也不一定是有序的，需要Primes先排序。

于 2013-01-31T22:02:53.540 回答
1

b跨线程共享。如果多个线程同时敲击那个糟糕的变量，你期望会发生什么？

在您的代码中似乎b并且a总是相等（或相差一个）。使用a. 并同步访问所有其他共享状态（如列表）。

于 2013-01-31T21:05:10.030 回答