并行计算架构：PRAM与非二进制并行算术架构解析

### 并行计算架构：PRAM 与非二进制并行算术架构解析 #### 1. PRAM 模型与相关概念 PRAM 模型虽被视为 PRAM 算法的一种指令，但存在对共享内存的多次访问，易产生歧义。为避免此问题，我们定义了 PRAM 步骤，即执行一次共享内存访问，或在本地内存中进行算术和逻辑运算。一个 PRAM 步骤的周期处于两个相邻的同步事件之间。例如，PRAM 算法中的指令 `a(i) := a(i) + b(i)` 会被拆分为四个 PRAM 步骤：从共享内存读取 `a(i)` 和 `b(i)`、计算 `a(i) + b(i)` 以及将结果写入用于存储 `a(i)` 的共享内存单元。显然，PRAM 算法的指令可轻松转换为一系列 PRAM 步骤，且无需进行本质修改。 #### 2. PRAM 类计算机的架构 在 PRAM 模型中，用 `P` 表示处理器数量，`C` 表示共享内存单元数量。我们设计的 PRAM 并行计算机由 `N` 个处理器单元、`M` 个内存单元和一个同步处理单元组成，具体结构如下： - **处理器单元**：由 `M - 1` 个节点构成，叶子节点与 `M` 个内存单元相连，以便与每个内存单元通信。节点分为根节点和内部节点，一个处理器单元承担 PRAM 模型中 `P/N` 个处理器的工作。处理器根节点执行算术和逻辑运算、发送内存访问请求、接收内存读取请求的结果并发送同步处理请求；处理器内部节点根据单元 ID 将内存访问请求路由到目标内存单元，并将内存读取请求的结果传递给处理器根节点。 - **内存单元**：设计了三种不同类型的内存单元： - **树模型**：由 `N - 1` 个节点组成二叉树，叶子节点与 `N` 个处理器单元相连，可处理来自每个处理器单元的访问请求。节点分为叶子节点（ML）、根节点（MR）和内部节点（MN），一个内存单元对应 PRAM 模型中的 `C/M` 个共享内存单元。每个内存叶子节点存储相同的数据，可在收到内存读取请求时立即返回结果，内存叶子节点和内部节点负责解决并发写入请求的竞争问题，内存根节点在收到写入请求时将更新信息发送给所有内存叶子节点。 - **树 - 总线模型**：使用总线直接将更新信息从内存根节点传输到内存叶子节点，无需经过内存内部节点。 - **总线模型**：与树 - 总线模型结构相似，但移除了内存根节点、内存内部节点及其之间的边和到内存叶子节点的边，总线用于更新内存叶子节点的数据。 - **同步处理单元**：由 `M - 1` 个节点组成二叉树，叶子节点与 `M` 个内存单元相连，根节点通过总线与 `N` 个处理器单元相连，用于发送同步处理终止信号。 以下是 PRAM 类计算机架构的相关参数表格： | 模型 | 所需物理处理器数量 | 所需路由节点数量 | 读取访问（所有情况） | 所有处理器单元写入同一单元 | 所有处理器单元写入不同单元 | | ---- | ---- | ---- | ---- | ---- | ---- | | T - 模型 | `M*N/2 + N` | `3*M*N/2 - 2*N - 1` | `O(2logM + (P/N - 1)/2)` | `O(logM + logN)` | `O(logM + logN + P/M - 1)` | | TB - 模型 | `M*N/2 + N` | `3*M*N/2 - 2*N - 1` | `O(2logM + (P/N - 1)/2)` | `O(logM + logN)` | `O(logM + logN + P/M - 1)` | | B - 模型 | `M*N/2 + N` | `M*N + M - N - 1` | `O(2logM + (P/N - 1)/2)` | `O(logM + P - 1)` | `O(logM + P - 1)` | #### 3. 内存访问和同步处理 在一个 PRAM 步骤中，处理按以下顺序完成：共享内存访问、算术和逻辑运算以及同步处理。为减少请求数量，每个处理器单元会对所有内存访问请求进行预处理。 - **内存访问**： - **处理器单元的预处理**： - 更改访问请求的顺序，使所有读取请求排在写入请求之前。 - 压缩访问同一单元的请求为一个请求，解决并发访问的竞争问题；压缩访问连续内存单元的读取请求为一个请求，包含连续单元的数量和最小地址信息。由于不同算法的压缩率不同，考虑预处理时间和内存访问时间的权衡，可能不执行此步骤。 - 为避免过多处理器单元同时访问同一内存单元，重新排列访问请求的顺序。假设处理器 ID 为 `i`（`0 ≤ i ≤ N`），将第 `k` 个请求修改为 `((k + i - 1) mod(M))` 个请求。 - **处理器和内存单元之间的处理流程**：处理器单元向内存单元发送访问请求并接收访问结果，内存单元处理来自处理器单元的访问请求并将结果返回。完成一个 PRAM 步骤的访问请求后，处理器单元向所有内存单元发送访问请求终止信号