大规模并行PIM阵列中不规则计算的支持与高效执行策略

### 大规模并行PIM阵列中不规则计算的支持与高效执行策略 #### 1. 引言半导体制造技术的发展使得高密度DRAM与CMOS逻辑在同一芯片上紧密耦合，催生了处理器内置内存（PIM）架构这一重要的新型架构。大规模的PIM阵列可组成大规模并行架构。PIM架构将处理器核心与DRAM块相结合，能直接访问内存行缓冲区，使内存带宽提升约两个数量级。当前的PIM较为基础，将内存视为物理资源，而未来的PIM架构可能更适合处理不规则数据结构。并行程序可大致分为规则程序和不规则程序。规则程序的并行线程数量固定，每个线程的计算量相近，调度相对容易；不规则程序的并行线程数量和每个线程的计算量在执行过程中会发生变化，若管理不善会浪费计算资源。我们主要关注不规则程序，特别是完全不规则、通信密集型的并行程序。 #### 2. 不规则问题许多高级科学问题具有不规则性且蕴含大量内在并行性，如稀疏矩阵计算、非结构化网格扫描、树搜索和粒子单元代码等，且很多相关问题具有自适应特性。要在大规模并行的PIM阵列上高效执行这些代码，需在局部性和并行性的利用之间找到平衡，其性能很大程度上取决于数据和工作分配的决策。 - **数据分配**：需对大型数据结构进行分区，并将其分布到机器的各个内存中。 - **工作分配**：要结合数据分配，考虑代码中的依赖关系和访问模式做出选择。规则问题具有规则（通常是线性）的数据访问模式，可利用编译时知识在传统架构上高效实现。而不规则算法的数据访问模式、数据和工作分配通常需在运行时解决，这给现有并行机器带来了很大问题，主要是由于内存访问延迟使得间接引用的运行时转换和相关通信成本高昂，且往往需要预处理来有效组织数据的批量通信。不规则应用通常具有以下典型特征： - **不规则数据分布**：管理不规则数据分布是关键问题，涉及数据结构的生成、内存表示、访问机制的实现以及（全量和增量）重新分配算法。 - **线程组**：不规则算法需要复杂的机制来生成协作线程组，如一组以松散同步的单程序多数据（SPMD）模式处理问题的数据并行线程，或树搜索产生的线程结构。关键操作包括线程生成、通信、前缀和归约操作、互斥和条件同步，这些操作可能在芯片内或芯片间进行。 - **地址转换**：将间接引用（如A(X(I))或指针值）映射到内存地址的问题。对于不规则数据结构，这种转换通常需在运行时进行，因为数据分布和索引数组的值通常不是静态已知的。 #### 3. 宏服务器我们定义了一个基于对象的模型，为大规模并行PIM阵列提供了抽象的编程范式。该模型的核心概念是宏服务器，它是一个自主的、活跃的对象，基于宏服务器类创建。宏服务器类为一组变量和方法以及线程及其同步建立了封装和上下文。在任何时刻，宏服务器都有一个明确的“家”，即虚拟内存中可找到管理该对象所需元数据的位置。宏服务器与一组变量相关联，这些变量的值定义了其状态。变量可以分布在PIM的各个内存中，其底层分布机制可看作是维也纳Fortran或高性能Fortran（HPF）等语言中相应概念的扩展，适用于LISP类型的数据结构，并允许任意映射和增量重新分配。宏服务器中方法的激活会产生（同步或异步）线程。线程可以直接读取和修改所属宏服务器的状态，每个线程可以激活自身或可访问的其他宏服务器的方法，因此该模型提供了服务器内和服务器间的并发，反映了底层架构的多级并行性。同时，该模型还为线程组的操作提供了特殊支持，并提供了简单的互斥机制（原子方法），允许通过条件变量和未来进行同步。元数据包括状态变量的信息（如类型和分布）、方法的签名以及当前在宏服务器中运行的线程的表示，大部分元数据存储在对象的“家”，便于相关PIM进行高效的集中管理。 #### 4. PIM阵列及其对不规则计算的支持 PIM将内存单元块和处理逻辑集成在同一集成电路芯片上。典型内存块的行缓冲区可能有1K或更多位，在单个内存周期内可获取，在内存的感测放大器处的数据传输速率通常为每秒4GB。设计用于同时直接操作这些数据的处理器通常可达到每秒10亿次操作（Gigaops）的性能。多个内存 - 处理器对可位于同一芯片上，目前总性能可达4Gigaops，对于简单算术或小字段操作，速率可能更高。一个由PIM芯片阵列组成的典型内存系统，总吞吐量可达256Gigaops，对于字节级操作，峰值吞吐量可达1Teraops。在一些设计中，将传统微处理器作为核心处理器集成到PIM中，以减少开发时间和成本，并利用现有软件（如编译器）；而在其他情况下，可能会专门为PIM设计更简单的处理器，以减少芯片面积并优化内存带宽。典型的PIM芯片包括多个内存块和处理器模块、内存总线接口以及共享功能单元（如浮点运算单元），芯片内处理器使用的地址通常是物理地址。包含PIM芯片的系统可能与传统结构有很大不同，以充分利用PIM的能力。例如，最简单的结构是用PIM芯片直接替换常规内存，保留系统处理器及其分层缓存层次结构；而其他结构可能会提供专门用于PIM间通信的高度并行网络，以及作为PIM后备存储的二级大容量存储，“吉尔伽美什”（十亿逻辑门阵列网格）就是一