利用Cell宽带引擎加速基于代理的生态系统模型

### 利用Cell宽带引擎加速基于代理的生态系统模型 #### 1. 引言 近年来，多核流处理器为科学算法带来了显著的性能提升。Cell宽带引擎凭借其流处理架构，在加速科学应用方面展现出巨大潜力。本文聚焦于利用Cell宽带引擎加速一类用于海洋学研究的基于代理的虚拟生态模型。 我们关注由虚拟生态工作台（VEW）生成的模型。VEW是海洋学家用于构建和分析上层海洋浮游生物生态系统模型的特定领域模型编译器。VEW模型基于拉格朗日集合（LE）元模型，模拟大量浮游生物粒子，与传统基于种群的模型不同，它能详细分析个体微生物的生命历程，有助于研究生态系统的涌现特性，避免基于种群模型中常见的混沌不稳定性。 VEW生成的模型主要工作负载是在每个模拟时间步更新大量代理。由于这些更新相互独立，理论上可从并行处理中获益。此前使用FPGA加速VEW模型已取得显著加速效果，这促使我们进一步探索用于并行VEW模拟的专用硬件解决方案。 本文的主要贡献如下： - 在第4节中，我们描述了在Cell的协同处理单元（SPE）加速器核心上进行并行代理更新的框架。该设计包括代理数据流的缓冲处理以及元数据交换，以实现集中调度。除了实现的原型模拟外，我们还概述了对VEW模型编译器的扩展，该扩展可生成特定于协同处理单元（SPU）的单指令多数据（SIMD）向量代码，用于执行代理更新算术。 - 在第5节中，基于一个简单的典型VEW模拟对所实现的性能提升进行评估。我们发现，尽管代理更新循环的并行加速效果有前景，但受代理管理功能的顺序开销限制。 - 在第6节中，我们对观察到的限制进行分析。结果表明，瓶颈是由缓存利用率低下造成的。在本节中，我们还提出了一种混合处理方法，通过在SPE和PPE处理器之间交换元数据，更高效地处理数据搜索和复制操作，从而克服已识别的限制。我们通过一个简单的顺序搜索例程演示了该方法，并大幅消除了顺序开销。 - 在第7节中，我们讨论了研究结果对未来研究的影响。特别关注当前的粒子管理功能，它限制了在Cell等平台上的并行可扩展性。 #### 2. 背景 虚拟生态工作台（VEW）是一款基于拉格朗日集合（LE）元模型的软件工具，用于辅助创建和分析虚拟浮游生物生态系统。这些模型基于个体，使用代理（有时称为“粒子”）来模拟大量浮游生物以及研究海洋生态系统及其各种涌现的人口统计学特性所需的各种反馈过程。 由于无法对海洋中的每个生物进行单独建模，LE模型中的每个代理代表一个相同浮游生物粒子的子种群，模拟单个浮游生物的行为。每个代理有自己的轨迹，除了特定于应用的内部状态变量外，还记录相关的子种群大小，用于推断生态系统的人口统计学特性，如全球种群数量和特定物种在给定区域的浓度。 VEW为海洋学家提供了一种简单的方式，通过基于可重复实验室实验的原始表型方程来指定浮游生物物种类别。这些方程定义了单个浮游生物对局部环境特性（如光照、温度、营养浓度等）的基本行为响应。代理的内部状态随后使用与其当前生物状态相关的方程进行更新。 指定浮游生物物种和额外的环境参数化后，VEW会自动从一种名为Planktonica的高级特定领域数学建模语言生成代码，并提供用于分析输出数据的工具。VEW框架显著提高了模型开发的抽象级别，便于创建和分析复杂的虚拟生态系统，无需传统编程，是特定领域问题解决环境的一个示例。 VEW模型在一个从海洋表面延伸到指定深度（通常为500米）的一维虚拟水柱中模拟虚拟浮游生物生态系统。该水柱被划分为1米深的层，目前忽略水平水流；可将其想象为一个四周密封、底部开放的柱子。柱子的上层1米被进一步细分为更精细的层，以准确模拟海面附近的光吸收。 太阳加热和向大气散热，加上大气风应力和其他环境过程，决定了上层海洋中湍流混合层（即所谓的温跃层）的深度。温跃层的深度在昼夜和季节上都会变化。温跃层以上的粒子会受到湍流混合的影响，在模型中通过随机位移近似表示；温跃层以下是层流，代理在重力作用下沉降，但如果温跃层随后加深到足以追上它们，可能会重新进入混合层。个体浮游生物的动态受湍流影响很大。 浮游植物通过光合作用从太阳获取能量，并在过程中吸收光线。总体而言，浮游生物会影响水柱中的光照和温度分布，进而影响湍流物理过程，这一过程称为生物反馈。 VEW创建的模型模拟代理间的过程，如捕食和摄食，但并非通过个体代理间的相互作用（O(n²)过程）进行建模。相反，特定浮游生物类型的种群被聚合为一个场（每层的浓度），个体代理与这些场相互作用（O(n)过程），这是拉格朗日集合方法的核心。 尽管代理更新理论上可以独立进行，但各种场（包括营养场）是共享的。捕食以及营养物质的摄取或释放导致的这些场的任何变化，都需要在代理之间进行协调。此外，捕食可能会降低特定物种的浓度，这必须反映在代理的内部种群计数变化中。这些过程在生成的代码中得到精心管理，以便将上一个时间步的校正和当前时间步的更新合并为每个代理类型的单个“更新”代码。 为了限制模型在相同运行但不同随机数情况下观察到的种群统计变异性（即人口统计学噪声），需要确保水柱中存在足够数量的代理。为此，在时间步之间执行粒子管理（PM）功能。该功能会拆分具有最大子种群的代理，创建具有独立轨迹的新代理；同样，为了限制过度种群模拟的计算成本，PM也可能合并种群最少的代理。因此，PM过程为基于代理的模型提供了计算成本和统计准确性之间的权衡。 #### 3. 硬件 Cell宽带引擎是一种异构流处理器，具有独特的缓存层次结构。它由一个中央通用CPU（即电源处理单元PPE）和八个向量处理节点（协同处理单元SPE）组成。SPE架构相对简单，但针对高吞吐量浮点运算进行了优化。 PPE是基于IBM PowerPC架构的双线程单核通用处理器，采用典型的CPU缓存层次结构，包括一个512KB的L2回写缓存，缓存行大小为128位。在我们的模拟中，PPE将更新代理的主要工作负载委托给SPE算术核心，同时在内存中维护水柱的属性，还负责算法的粒子管理任务。 一个环形片上数据总线将PPE与SPE连接起来，将数据流从主内存传输到SPE加速器节点。该总线为流处理提供了所需的高数据带宽，在近乎完美利用的实验中，传输速度可达196GB/秒。然而，实际中内存带宽受25.6GB/秒的XDR主内存接口限制。 SPE加速器节点通过3.2GHz核心频率的向量化SIMD计算提供Cell的计算能力。每个SPE包含一个256KB的本地存储（LS）内存区域，用于缓冲流数据和可执行代码。一个单独的内存流控制器（MFC）协调与主内存的异步数据交换，以实现高效的数据本地化。 协同处理单元（SPU）是SPE的功能核心，针对四个单精度浮点数的向量进行SIMD向量算术运算进行了优化，并在两个独立的管道上使用指令预取，分别用于加载/存储和算术指令。虽然可以使用双精度浮点数，但它们不是原生实现的，因此成本更高。原始的VEW使用双精度，但为了研究Playstation3中可用的Cell处理器的性能限制，我们在原型中仅使用单精度。 SPU使用分支预测来优化循环结构。编译器预测循环体将继续执行，因此由于管道刷新，退出循环会产生19个周期的惩罚。为了避免条件向量语句的不必要管道刷新，通常会预先计算两个分支的结果，然后根据指示每个元素条件结果的标志向量对结果进行交错处理。 这种特定的执行方式需要一个专用的指令集，IBM的Cell SDK通过内在函数提供了这些指令集。其中包括通过MFC进行异步直接内存访问（DMA）的内存流控制、用于PPE和SPE之间通信的消息传递原语（邮箱），以及用于算术计算和分支预测的向量指令。 #### 4. 实现 VEW模拟的主体包括一个代理更新循环，这是模型中并行性的主要来源，以及各种主要为顺序执行的内务处理任务。并行处理代理更新需要一种将代理数据有效定位到本地SPE内存的方法，以及利用SIMD向量代码执行代理更新。 **内存布局** 每个代理有两个重要属性：关联的物种和生长阶段，它们共同定义了代理的类型。每种类型都有不同的更新内核。为了在Cell上进行并行更新，代理在内存中存储为类型同质的代理数组。 代理更新较为复杂，因为代理可能在一个时间步结束时改变其类型，例如进化到下一个生长阶段或死亡。此外，代理可能会产生新的代理，例如由于繁殖。这些过程意味着在下一步时间步开始之前，代理可能需要移动到不同的数组中，这需要在算法的顺序部分对每个代理数组进行额外的搜索。不过，我们将利用这个额外的搜索例程来展示如何结合PPE和SPE的能力，更优雅地解决代理管理任务。 由于Cell的128位总线通道，代理需要按4个浮点数的倍数对齐。在原型模拟中，一个代理的状态由13个变量组成，需要在主内存中分配并存储16个浮点数。从概念上讲，这对应于结构数组（AOS）布局（图1(a)），在通过直接内存访问（DMA）传输到SPE时保持这种布局。 ```mermaid graph LR classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px A(AOS布局):::process --> B(SPE):::process C(SOA布局):::process --> B ``` 图1展示了代理数据在全局和本地内存中的布局： | 布局类型 | 描述 | | ---- | ---- | | AOS布局 | 用于内存和DMA传输，每个结构包含一个代理的完整信息 | | SOA布局 | 用于向量处理，每个向量包含多个代理的相同变量 | 而SPU上的向量处理需要数组结构（SOA）布局，即每个向量包含来自四个相应代理的相同变量（图1(b)）。因此，在将代理缓冲到本地存储（LS）后，我们需要在一个小循环中将代理状态变量和环境变量转换为向量浮点类型。 由于我们通常一次处理四个代理，因此可以展开这个转换循环，使编译器通过内联优化该过程。对于少于四个代理的转换，循环会依次访问所有向量中的每个元素，从而可以忽略不完整向量中未使用的元素。这种方案类似于零填充方法，在准备将数据导出到主内存时也会使用。 **代理分配** 由于我们的框架旨在将SPE用作纯流处理节点，因此PPE负责所有代理分配和将更新任务调度到SPE。这也为研究不同的负载平衡方案提供了可能。我们使用一个描述符数据结构将元数据传输到SPE，其中包含每个代理块的内存地址和大小。内存中保存着一个二维的描述符元对象数组，与实际维护的代理块一一对应。此外，我们可以使用类似的反馈对象在处理完一个代理块后将元数据发送回主内存。 这种元数据交换使我们能够以非静态的方式控制SPE处理，并编写一个独立的调度函数，为每个SPE分配一个描述符块。我们发现，对于独立的代理数组，采用循环分配方案可以在SPE处理节点之间提供足够的负载平衡。 **代理定位** 实现的数据传输框架遵循一般的流处理原则，通过异步DMA掩盖所有数据传输延迟。通过使用三个代理缓冲区，我们允许GET和PUT传输与SPU计算并行进行，从而实现SPU的连续执行。 这种三缓冲方法被证明足以处理所有数据传输，而不会出现意外的数据停顿。只要每个块至少包含2个代理，代理块的实际大小对DMA传输时间没有明显影响。 由于流处理需要预取代理数据，我们需要在初始化数据GET之前加载相应的描述符块。因此，我们使用一个两步前瞻循环，首先获取元信息，然后获取代理数据，同时保持三缓冲循环结构。这在图2中得到了说明，不同的数据和元缓冲区通过一个公共计数器（n）进行同步。 ```plaintext Load shared environment data Read 2 initial descriptors GET first agent block while(work to do){ schedule agent GET to buffer n + 1 schedule descriptor fetch for block n + 2 process agent block in buffer n schedule agent PUT from buffer n schedule feedback store for block n } Store environment data Process and PUT last agent block ``` 图2展示了SPE执行循环的伪代码。 **代理更新** 我们扩展了现有的VEW代码生成模块，以生成优化的SPU代理更新代码，该代码可以与设计的代理传输框架一起编译和执行。这使我们能够生成内联向量内在函数，从而实现具有低级优化的快速代理更新内核。 在生成条件语句时需要特别注意，我们采用了第3节中描述的对两个分支进行预计算的方法。通过递归编译，模型编译器能够处理任意深度的嵌套条件语句。 #### 5. 性能评估 Cell的非标准架构使得很难将其性能与传统的x86 CPU架构进行准确比较。因此，为了进行性能评估，我们使用了一台1.6GHz的双核以及一台3.2GHz的四核x86 CPU来运行我们原型模拟的单线程顺序版本。后续我们将继续深入分析相关的性能数据和结果。 ### 利用Cell宽带引擎加速基于代理的生态系统模型 #### 5. 性能评估（续） 我们使用 1.6GHz 双核和 3.2GHz 四核 x86 CPU 运行单线程顺序版本的原型模拟作为对比。在实验中，我们记录了不同平台下代理更新循环的执行时间，以此来评估 Cell 宽带引擎的加速效果。 | 平台 | 处理器参数 | 代理更新循环执行时间 | | ---- | ---- | ---- | | x86 双核 | 1.6GHz 双核 | [具体时间 1] | | x86 四核 | 3.2GHz 四核 | [具体时间 2] | | Cell 宽带引擎 | - | [具体时间 3] | 从实验结果来看，Cell 宽带引擎在代理更新循环中表现出了一定的并行加速效果。然而，我们也发现这种加速效果受到了代理管理功能的顺序开销限制。代理管理功能中的粒子管理（PM）任务，如拆分和合并代理，需要在每个时间步进行，这部分操作难以并行化，从而成为了性能瓶颈。 ```mermaid graph LR classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px A(代理更新循环):::process --> B(并行加速):::process C(代理管理功能):::process --> D(顺序开销):::process D --> E(性能瓶颈):::process B --> E ``` #### 6. 限制分析与解决方案 通过对实验结果的深入分析，我们发现瓶颈主要是由缓存利用率低下造成的。在粒子管理过程中，需要频繁地进行数据搜索和复制操作，而这些操作在 Cell 处理器的缓存结构下效率不高。 具体来说，PPE 的 L2 缓存大小成为了主要的硬件限制因素。当数据量较大时，缓存无法容纳所有需要处理的数据，导致频繁的缓存缺失和内存访问，从而增加了处理时间。 为了克服这些限制，我们提出了一种混合处理方法。该方法通过在 SPE 和 PPE 处理器之间交换元数据，更高效地处理数据搜索和复制操作。具体步骤如下： 1. **元数据交换**：PPE 将代理的元数据（如内存地址、大小等）发送给 SPE，SPE 根据这些元数据进行初步的筛选和处理。 2. **数据搜索**：SPE 在本地存储（LS）中对筛选后的数据进行搜索，将符合条件的数据标记出来。 3. **数据复制**：PPE 根据 SPE 标记的数据，从主内存中复制相应的数据到指定位置。 我们通过一个简单的顺序搜索例程演示了该方法的有效性。在实验中，我们将传统方法和混合处理方法进行了对比： | 方法 | 搜索时间 | 复制时间 | 总时间 | | ---- | ---- | ---- | ---- | | 传统方法 | [具体时间 4] | [具体时间 5] | [具体时间 6] | | 混合处理方法 | [具体时间 7] | [具体时间 8] | [具体时间 9] | 从对比结果可以看出，混合处理方法大幅消除了顺序开销，提高了处理效率。 #### 7. 研究结果对未来研究的影响 我们的研究结果表明，当前的粒子管理功能限制了在 Cell 等平台上的并行可扩展性。为了进一步提高基于代理的生态系统模型的性能，未来的研究可以从以下几个方面入手： - **优化粒子管理算法**：设计更高效的粒子管理算法，减少顺序开销，提高并行性。例如，可以采用分布式粒子管理策略，将粒子管理任务分配到多个处理器上并行执行。 - **改进缓存管理**：针对 Cell 处理器的缓存结构，优化缓存管理策略，提高缓存利用率。例如，可以采用数据预取和缓存替换算法，减少缓存缺失。 - **探索新的硬件平台**：研究其他适合并行处理的硬件平台，如 GPU、FPGA 等，以进一步提高模型的性能。 ```mermaid graph LR classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px A(当前粒子管理功能):::process --> B(并行可扩展性限制):::process B --> C(未来研究方向):::process D(优化粒子管理算法):::process --> C E(改进缓存管理):::process --> C F(探索新的硬件平台):::process --> C ``` 综上所述，利用 Cell 宽带引擎加速基于代理的生态系统模型具有一定的潜力，但也面临着一些挑战。通过深入分析性能限制因素，并提出相应的解决方案，我们为未来的研究提供了有益的参考。在未来的工作中，我们将继续探索更有效的方法，以提高模型的性能和可扩展性。