关于多线程、锁和多核处理器的多部分问题（multi^3）

Question

我有一个有两种方法的程序。第一个方法采用两个数组作为参数，并执行一个操作，其中一个数组中的值有条件地写入另一个数组，如下所示：

void Blend(int[] dest, int[] src, int offset)
{
    for (int i = 0; i < src.Length; i++)
    {
        int rdr = dest[i + offset];
        dest[i + offset] = src[i] > rdr? src[i] : rdr; 
    }
}

第二个方法创建两组独立的 int 数组并迭代它们这样一组中的每个数组都与另一组中的每个数组混合，如下所示：

void CrossBlend()
{
    int[][] set1 = new int[150][75000]; // we'll pretend this actually compiles
    int[][] set2 = new int[25][10000]; // we'll pretend this actually compiles
    for (int i1 = 0; i1 < set1.Length; i1++)
    {
        for (int i2 = 0; i2 < set2.Length; i2++)
        {
            Blend(set1[i1], set2[i2], 0); // or any offset, doesn't matter
        }
    }
}

第一个问题：由于这种方法显然是并行化的候选者，所以它是吗？本质上线程安全？似乎不是，因为我可以设想一种场景（我认为不太可能），其中一个线程的更改由于不同的线程〜同时操作而丢失。

如果不是，这会

void Blend(int[] dest, int[] src, int offset)
{
    lock (dest)
    {
        for (int i = 0; i < src.Length; i++)
        {
            int rdr = dest[i + offset];
            dest[i + offset] = src[i] > rdr? src[i] : rdr; 
        }
    }
}

是一个有效的解决方案吗？

第二个问题：如果是这样，使用这样的锁可能会产生什么性能成本？我假设，对于这样的事情，如果一个线程尝试锁定当前被另一个线程锁定的目标数组，第一个线程将阻塞，直到锁被释放，而不是继续处理某些内容。

另外，获取锁实际上需要多少时间？纳秒级或更糟？这会是这样的事情的一个主要问题吗？

第三个问题：我如何以利用多核处理器的多线程方式最好地解决这个问题（这是基于一个潜在错误的假设，即多线程解决方案不会在单核处理器上加速此操作）？我猜想我希望每个核心运行一个线程，但我不知道这是否属实。

Answer 1

CrossBlend 的潜在争用是 set1 - 混合的目的地。与其使用锁（与您正在执行的工作量相比，锁的成本相对较高），不如安排每个线程在其自己的目标上工作。也就是说，给定的目标（set1 中某个索引处的数组）由给定的任务拥有。这是可能的，因为结果与 CrossBlend 处理数组的顺序无关。

每个任务应该只运行 CrossBlend 中的内部循环，并且使用要使用的目标数组 (set1) 的索引（或范围）对任务进行参数化）

您还可以并行化 Blend 方法，因为每个索引都是独立于其他索引计算的，因此不会出现争用。但在当今的机器上，拥有 <40 个内核，只需线程化 CrossBlend 方法即可获得足够的并行性。

为了在多核上有效运行，您可以

1. 对于 N 个核，将问题分为 N 个部分。鉴于 set1 与核心数量相比相当大，您可以将 set1 划分为 N 个范围，并将每个索引范围传递到运行内部 CrossBlend 循环的 N 个线程中。这将为您提供相当好的并行性，但这并不是最佳的。 （有些线程会更快完成，并且最终没有任何工作可做。）
2. 更复杂的方案是使 CrossBlend 内部循环的每次迭代成为一个单独的任务。有 N 个队列（针对 N 个核心），并在队列之间分配任务。启动 N 个线程，每个线程从队列中读取其任务。如果线程队列变空，它将从其他线程的队列中获取任务。

第二种方法最适合大小不规则的任务，或者系统正在用于其他任务的情况，因此某些核心可能会在其他进程之间进行时间切换，因此您不能期望在不同的任务上大致相同的时间内完成等量的工作核心。

第一种方法的编码要简单得多，并且会给您带来良好的并行性。