采用隐式求解的众核流水线并行方法

摘要

本发明提供了一种采用隐式求解的众核流水线并行方法，包括：在众核处理器的p个计算核心上将变量a

说明书

技术领域

本发明涉及计算机技术领域，具体涉及一种采用隐式求解的众核流水 线并行方法。

背景技术

隐式算法(implicitalgorithm)指的是，在将微分方程转化为代数方程 的过程中，如果求解某时刻函数值需要用到该时刻的变量，那么这种离散 方法即为隐式算法。

在数值计算中，隐式算法由于稳定性好、收敛速度快等优点得到广泛 应用。采用隐式算法对微分方程进行离散，最终归结为分块并行求解大型 稀疏矩阵线性代数方程组。如果采用两步扫描格式，即LU-SGS方法求解 线性代数方程组，将得到递归方程，在给定边界条件后，采用递推方法求 解。隐式求解得到的方程组在空间方向有严格的相关性，并行较为困难。

近年来，高性能计算正在从多核CPU并行计算模式向CPU+众核的多 级并行计算模式发展。基于众核的高性能并行计算技术在科学与工程数值 计算领域显现出巨大的利用价值，能够在保证计算精度的情况下，大幅缩 短复杂物理问题的计算时间。但是众核处理器并行度高，每个计算核心存 储资源有限，计算核心之间数据交互复杂，因此在众核处理器上实现隐式 算法的并行难度更大。

目前众核处理器上的多数应用都是采用显式数值算法，隐式算法的众 核应用非常有限，仅能做到部分并行，无法使整个计算区域整体求解，因 此无法保证算法的严格隐式，对数值计算的稳定性和收敛性都造成较大影 响。

发明内容

本发明所要解决的技术问题是针对现有技术中存在上述缺陷，提供一 种采用隐式求解的众核流水线并行方法，其能够在众核处理器的各计算核 心之间通过流水线并行，实现隐式算法中空间结点的关联，保证串并行结 果的严格一致，最大限度地保留隐式算法较高的稳定性和收敛性。

根据本发明，提供了一种采用隐式求解的众核流水线并行方法，包括：

第一步骤：在众核处理器的p个计算核心上将变量a_i,j沿i方向划分数 据，使得变量a_i,j被分成p段，其中p为大于1的整数，而且将 {a_i,j,i＝n_k,…,n_k+1-1}存储在计算核心p_k上，其中k＝0,…,p-1,并且 1＝n₀<n₁<…<n_p-1＝n+1；

第二步骤：采用计算核心间寄存器通信实现流水线并行。

优选地，第二步骤包括：在沿j方向的循环中，使得非0号计算核心p_k从前一个计算核心p_k+1处取数据并开始沿i方向的循环，在沿i方向 的循环中根据递归函数计算a_i,j:＝F(a_i-1,j)，然后结束沿i方向的循环；随后， 计算核心p_k向后一个计算核心p_k+1发送数据此后结束沿j方向的循 环。

优选地，变量a_i,j沿j方向计算相互独立。

优选地，变量a_i,j沿i方向的计算存在着向前依赖关系。

附图说明

结合附图，并通过参考下面的详细描述，将会更容易地对本发明有更 完整的理解并且更容易地理解其伴随的优点和特征，其中：

图1示意性地示出了局部相关的递归问题图示。

图2示意性地示出了根据本发明优选实施例的采用隐式求解的众核流 水线并行方法的具体示例的流程图。

需要说明的是，附图用于说明本发明，而非限制本发明。注意，表示 结构的附图可能并非按比例绘制。并且，附图中，相同或者类似的元件标 有相同或者类似的标号。

具体实施方式

为了使本发明的内容更加清楚和易懂，下面结合具体实施例和附图对 本发明的内容进行详细描述。

本发明主要针对众核处理器，采用流水线并行解决隐式求解带来的分 块递归相关性问题，保证隐式求解串并行计算结果严格一致，从而保留隐 式求解的稳定性和收敛性优势，扩大众核处理器的应用范围。其中，流水 线并行是这样一种并行技术，其基本思想是将一个计算任务分成一系列的 阶段，一旦前面的阶段完成，后继的阶段立即开始，处理多个计算任务时， 流水线并行能够支持与阶段数相同的并行性。

下面参考附图并且以一个局部相关的递归问题为例，阐述众核处理器 上流水线并行算法所对应的方法处理。

隐式算法离散后得到递归方程组，各变量之间存在相关性，需要求解 出一个变量后再计算另一个变量，依次求解。如求出变量a_0,j，才能计算变 量a_1,j，然后依次计算a_i,j＝F(a_i-1,j),i＝1,…,n,j＝1,…,m。其中n和m分别为i 和j方向的网格单元数，其中F()是递归方程。其中，i方向和j方向是相 互独立的两个方向。

如图1所示，沿j方向计算相互独立，沿i方向的计算存在着向前依 赖关系(递归关系)，无法独立进行。当数据在众核处理器的各计算核心 之间的划分仅沿j方向进行时，计算完全并行。因此，需要考虑当沿i方 向进行数据划分时递归问题的并行算法。不失一般性，假设在众核处理器 的p个计算核心上沿i方向划分数据，使得变量a_i,j被分成p段(p为大于 1的整数)，其中{a_i,j,i＝n_k,…,n_k+1-1}存储在计算核心p_k上，k＝0,…,p-1,这里 1＝n₀<n₁<…<n_p-1＝n+1。采用计算核心间寄存器通信实现流水线并行。

在沿j方向的循环中，使得非0号计算核心p_k从前一个计算核心p_k+1处 取数据并开始沿i方向的循环，在沿i方向的循环中根据递归函数 计算a_i,j:＝F(a_i-1,j)，然后结束沿i方向的循环；随后，计算核心p_k向后一个 计算核心p_k+1发送数据此后结束沿j方向的循环。

例如，计算流程示例如下：

通过计算核心间流水线并行，实现了递归方程组各变量之间顺序计 算，从而保证了众核并行计算结果与串行计算结果的一致性。

相应地，图2示意性地示出了根据本发明优选实施例的采用隐式求解 的众核流水线并行方法的具体示例的流程图。

如图2所示，根据本发明优选实施例的采用隐式求解的众核流水线并 行方法包括：

第一步骤S1：在众核处理器的p个计算核心上将变量a_i,j沿i方向划分 数据，使得变量a_i,j被分成p段，其中p为大于1的整数，而且将 {a_i,j,i＝n_k,…,n_k+1-1}存储在计算核心p_k上，其中k＝0,…,p-1,并且 1＝n₀<n₁<…<n_p-1＝n+1；

第二步骤S2：采用计算核心间寄存器通信实现流水线并行。

具体地，例如，第二步骤S2包括下述步骤：在沿j方向的循环中，使 得非0号计算核心p_k从前一个计算核心p_k+1处取数据并开始沿i方 向的循环，在沿i方向的循环中根据递归函数计算a_i,j:＝F(a_i-1,j)，然后结束 沿i方向的循环；随后，计算核心p_k向后一个计算核心p_k+1发送数据此后结束沿j方向的循环。

本发明使用流水线并行算法实现隐式求解在众核处理器上的应用，其 中通过各计算核心间寄存器通信实现流水线并行的方式，而且通过流水线 并行解决递归方程组求解的相关性问题，保证隐式数值算法的串并行完全 一致，实现隐式算法在众核处理器上的应用。

本发明的优点包括：众核处理器上的多数应用都是采用显式数值算 法，隐式算法的众核应用非常有限，仅能做到部分并行，无法使整个计算 区域整体求解。采用本发明，能够有效解决递归方程组求解的相关性问题， 保证隐式数值算法的串并行完全一致，从而最大限度地保留隐式算法较高 的稳定性和收敛性，实现隐式算法在众核处理器上的应用。

此外，需要说明的是，除非特别指出，否则说明书中的术语“第一”、“第 二”、“第三”等描述仅仅用于区分说明书中的各个组件、元素、步骤等，而 不是用于表示各个组件、元素、步骤之间的逻辑关系或者顺序关系等。

可以理解的是，虽然本发明已以较佳实施例披露如上，然而上述实施 例并非用以限定本发明。对于任何熟悉本领域的技术人员而言，在不脱离 本发明技术方案范围情况下，都可利用上述揭示的技术内容对本发明技术 方案作出许多可能的变动和修饰，或修改为等同变化的等效实施例。因此， 凡是未脱离本发明技术方案的内容，依据本发明的技术实质对以上实施例 所做的任何简单修改、等同变化及修饰，均仍属于本发明技术方案保护的 范围内。