1

用于并行计算的 PRAM 模型主要分为三种类型：EREW、CREW、CRCW。

我可以理解如何在多核机器上实现 EREW、CREW。但是如何在多核 CPU 上实现 CRCW 模型呢？它甚至是一个实用的模型吗，因为并发写入是不可能的，而且每个基本的并行编程课程都会详细介绍竞争条件。

从本质上讲，这意味着尝试避免竞争条件和尝试实现并发写入是两个相反的目标。

4

1 回答 1

1

首先：我们知道 PRAM 是一个理论上的或抽象的机器。进行了一些简化，以便可以将其用于分析/设计并行算法。

接下来，让我们谈谈有意义地进行“并发写入”的方式。

并发写入内存通常根据它们的行为方式分为子类：

  1. 基于优先级的 CW - 处理器具有优先级，如果对同一位置的多个并发写入到达，则来自最高优先级的处理器的写入将提交到内存。

  2. 任意 CW - 任意选择一个处理器的写入进行提交。

  3. Common CW -仅当写入的值相同时，才会提交对同一位置的多个并发写入。即所有写入处理器必须就写入的值达成一致。

  4. 缩减 CW - 对正在写入的多个值应用缩减运算符。例如summation，其中对同一位置的多个并发写入导致要写入内存的值的总和。

这些子类导致了一些有趣的算法。我在课堂上记得的一些例子是：

  1. 以求和形式实现并发写入的 CRCW-PRAM可以在单个时间步中对任意数量的整数求和。输入数组中的每个整数都有一个处理器。所有处理器都将它们的值写入相同的位置。完毕。

  2. 想象一个 CRCW-PRAM，其中仅当所有处理器写入的值相同时，内存才会提交并发写入。现在想象Nnumbers A[1] ... A[N]，你需要找到它的最大值。以下是你的做法：

第1步。

N 2 个处理器将每个值与其他值进行比较，并将结果写入 2D 数组：

parallel_for i in [1,N]
  parallel_for j in [1,N]
    if (A[i] >= A[j])
      B[i,j] = 1
    else
      B[i,j] = 0

所以在这个二维数组中，对应于最大数字的列将全为 1。

第2步：

找到只有 1 的列。并将对应的值存储为最大值。

parallel_for i in [1,N]
  M[i] = 1
  parallel_for j in [1,N]
    if (B[i,j] = 0)
      M[i] = 0              // multiple concurrent writes of *same* value
  if M[i]
    max = A[i]

最后，是否可以真正实施？

是的，有可能。比如说，设计一个寄存器文件，或者一个内存和相关的逻辑，它有多个写端口，并以一种有意义的方式（就像我上面描述的方式）仲裁对同一地址的并发写入是可能的。您可能已经根据我提到的子类看到了这一点。实用与否，我不敢说。我可以说，在我有限的计算机经验中（主要涉及使用通用硬件，比如我现在坐的 Core Duo 机器），我还没有在实践中看到过。

编辑：我确实找到了一个 CRCW 实现。PRAM 上的维基百科文章描述了一种 CRCW 机器，它可以在 2 个时钟周期内找到数组的最大值（使用与上述相同的算法）。描述在 SystemVerilog 中，可以在 FPGA 中实现。

于 2012-07-13T21:46:20.847 回答