并行计算模型与细粒度算法在GPU上的实现

### 并行计算模型与细粒度算法在GPU上的实现 在当今的计算领域，并行计算和图形处理单元（GPU）的应用越来越广泛。本文将介绍两种重要的计算概念：GCA - w大规模并行模型和细粒度算法在GPU上的实现。 #### GCA - w大规模并行模型 在传统的一维细胞自动机（1D - CA）规则中，存在一些效率问题。例如，在某些计算过程中，大约只有一半的单元格能产生有用的结果，而且每行右侧会冗余产生零值。GCA - w模型则解决了这些问题。 ##### 模型原理 GCA - w模型是全局细胞自动机（GCA）模型的扩展，与细胞自动机（CA）模型相关。在GCA和GCA - w模型中，邻居与当前考虑的单元格动态链接，数据和链接信息由局部规则修改。这使得单元格可以自行决定下一代的邻居。新的GCA - w模型克服了单元格只能修改自身状态的限制，整个单元格数组中的任何全局单元格都可以成为信息传输的目标。与普通GCA模型相比，写访问可以直接在O(1)时间内执行，而无需以O(log n)的速度进行模拟。 ##### 初始状态与操作 初始时，只有单元格(k = 0)处于活动状态。在第一代，它执行三个操作： 1. 向其右侧邻居(k = 1)写入d <= 1。 2. 激活右侧邻居。 3. 使自身失活。 这样，在每一代，最右侧会激活一个新的单元格。 以下是该模型的代码实现： ```plaintext type cell = (data: integer; active: activity) // left, right are temps used as effective addresses to be computed C: array [0 .. n] of cell // example n=5 initial C[0].data <= 1, C[0].active <= TRUE endinitial repeat parallel C[k where active] // only do for active cells left = k-1, right = k+1 // fixed local neighbors like in CA if (k=0) then active <= FALSE, right.data<= 1, right.active <= TRUE endif if (data ≠ 1) then data <= data + left.data endif if (data =1) and (k<n) then data <= data + left.data, right.data <= 1, right.active <=TRUE endif if (data =1) and (k=n) then data <= data + left.data, right.data <= 1 endif endparallel endrepeat ``` ##### 硬件架构 为GCA - w模型设计高效的硬件架构并不困难。设计者可以选择以下几种架构： 1. **全并行架构**：对于n个单元格，使用n个寄存器（q，或d和p）、n个功能单元（h，e，g）和一个链接网络，该网络可以并行提供并行算法执行所需的链接。 2. **多处理器架构**：可以使用或设计标准的多处理器架构，并辅以特殊的硬件组件或类似向量的指令，以支持模型并加速执行。 3. **流水线顺序架构**：这是一种用于数据并行架构的组件。其工作原理如下： - 使用地址计数器k从主存储器R中顺序读取单元格的状态q。 - 计算有效地址peff，并从存储器S中读取邻居。 - 使用函数f计算下一个单元格状态qnext和q*next，使用函数w计算写入地址。 - RS’是一个临时双端口存储器，将qnext存储在单元格的位置k（或更一般地在v(k, control)），将q*next存储在计算出的写入地址w的位置。 - 在当前代结束时，将RS’复制回R和S，以实现同步更新方案。 为避免复制新数据，可以使用两个双端口存储器RS（读 + 读）和RS’（写