导航：X技术最新专利计算;推算;计数设备的制造及其应用技术

　　本专利针对有限差分算法在异构众核架构中计算效率低、数据传输开销大及负载不均衡的问题，提出三步递进优化方法：通过消除分支预测失误、循环展开和向量化提升单核性能；采用OpenMP并行模型与多级预取指令优化内存访问；利用offload分载模式实现CPU与MIC间的动态负载均衡与数据传输优化，显著提升算法执行效率。

　　【专利摘要】本发明属于高性能计算技术领域，具体的涉及一种异构众核架构中有限差分算法的优化方法，在基于众核加速器(MIC)与多核通用处理器(CPU)相结合的混合异构高性能计算机系统中，对有限差分算法使用三步递进优化法进行优化：主要包括基本优化法、并行优化法和异构协同优化法。本发明的有益效果是：应用三步递进优化法解决有限差分算法从多核系统到异构众核系统时由跨越式访存、可并行执行绪不足带来的计算性能低、并行效果差的问题，是一种具有高效性、可扩展性的优化方法，通过分支消除、循环展开、不变量外提等基本优化法削减计算强度并为向量化扫除障碍；通过分析数据依赖，循环分块，使用向量指令集改写核心算法等并行优化法，充分利用众核处理器多线程、长向量的机制。

　　[0001] 本发明属于高性能计算技术领域，具体的说，属于高性能计算机领域中异构系统 中的CPU与MIC协同优化技术领域，具体的设及一种异构众核架构中有限差分算法的优化方 法。

　　[0003] 近年来，随着大规模并行体系结构的发展，异构众核架构在超级计算领域获得了 广泛应用。从每半年公布一次的超级计算机TopSOO榜单中可W看出，更专注于并行处理性 能的MIC越来越多地被集成在高性能集群中，其中2015年11月公布的榜单中，排名第一的天 河2号与排名第二的Titan均采用该体系架构。

　　[0004] 从程序设计角度看，由于MIC和CPU使用相同的编程模型，用户程序并不需要做特 别的修改就可W正常运行于MIC架构上。但是大多用户程序都是串行程序，即使用户实现了 其并性版本，往往由于并行度不够，远不能发挥出MIC架构并行执行程序的高性能。MIC架构 上的并行分为四个层面：（1 )MIC核层面的并行:每个MIC核都配有长度超过CPU核的向量处 理单元，W支持更高效率的SIMD(Single Instruction Multiple Data)并行操作，实现指 令级并PG电子平台网站行。（2)单MIC卡层面的并行:每个MIC卡由多于50个核构成，每个核提供4个硬件线多个线程，实现线)MIC+CPU层面的并行:MIC和CPU异构协 同，通过数据传输最小化，负载均衡，实现CPU和MIC间进程级并行。（4)MIC集群层面的并行： 在集群间部署多MIC卡，通过任务划分，MPI通信模型，实现集群级并行。

　　[0005] 有限差分数值算法用于模拟波在弹性介质中的传播，广泛应用于地震模拟、资源 勘探、无损探伤等领域。该算法通过求解偏微分方程组和时间迭代模拟弹性波传播，具有简 单、灵活、通用性强、易于程序实现等优点。但是有限差分存在访存跨度大，计算密度高，算 法性能差等问题，往往受限于模拟范围、模拟时长的规模。利用异构众核系统的并行特性进 行有限差分数值模拟，可W很好解决上述问题。

　　[0006] 本发明要解决的技术问题是:解决有限差分数值算法在异构众核架构运行时性能 较低，受限于模拟范围和模拟时长的问题。本发明提供一种使有限差分算法高效运行于异 构众核架构优化方法。

　　[0007] 本发明的技术方案是:一种异构众核架构中有限差分算法的优化方法，有限差分 算法采用=步递进优化法进行优化，所述=步递进优化法的具体步骤为： 步骤一、基本优化，提取循环不变量削减计算强度、消除循环分支W利于向量化； 步骤二、并行优化，采用化enMP并行模型，通过在核屯、循环前加入编译指示，实现线程 级并行，采用内建向量指令改写核屯、循环，实现指令级并行； 步骤S、异构协同优化，在异构众核平台下，使用offload分载模式可W将部分计算从 CPU端分载至MIC端。

　　[0008] 所述的异构众核架构中有限差分算法的优化方法，所述步骤一的具体为:通过循 环展开、不变量外提基本优化法削减计算强度，变换循环变量初值及退出条件消除分支判 断。所述的异构众核架构中有限差分算法的优化方法，所述步骤二具体为:循环分块后，使 用化enMP并行模型，使多线程执行算法时具有更好的空间局部性，同时，使用内建向量指令 并插入数据预取指令，在充分利用MIC核指令级并行的基础上，有效缩短计算单元等待数据 传输的时间。

　　[0010] 所述的异构众核架构中有限差分算法的优化方法，所述步骤=主要包括数据传输 优化和负载均衡优化。

　　[0011] 所述的异构众核架构中有限差分算法的优化方法，所述数据传输优化具体方法 为:有限差分算法主要包括next、prev和Vel =个数组;=个数组的传输量均与分载给MIC的 负载有关:设在X，Y，Z维度下的输入规模为Nl，N2和N3 ,CPU与MIC的负载比例为Lc: Lm,数组 ve 1作为只读数组，仅需首次由CPU传向MIC并由MIC保留在其内存中，传输数据量为

　　!字节，之后的迭代不再需要将vel传给MIC，使用分载模式 中的nocopy技术实现;数组next和prev均为读写数组，在时间步迭代中依次轮流担任写目 的地数组，因此除了需要首次将数据传输至MIC，迭代过程中还要相互交换依赖部分;首次 传输数组next和prev的数据量均为

　　戸 节;每次迭代结束时，CPU端与MIC端交换依赖数据:CPU端传输Nl*N2*8*sizeof(float)字节 的数据至MIC，同时MIC端传输NI*肥*8*sizeof (float)字节的数据至CPU;将数组next分给 CPU和MIC并行计算，阴影部分数据不在计算范围，而是在当次迭代结束后由另一端传输过 来;数组nextmic最后的N1*N2*8个数据由CPU端对应部分的计算结果传入，nextcpu最前的NI* N2*8个数据由MIC端对应部分的计算结果传入;数据交换结束后即可开始下次迭代，直至程 序结束。所述的异构众核架构中有限差分算法的优化方法，所述负载均衡优化具体方法为： 首先根据输入规模分别在CPU端和MIC端运行优化后的程序，使用分块探索工具得到最优的 分块大小;然后使用在CPU和MIC上测得的程序吞吐量Tcpu和Tmi。，并根据公式 LcpU ? Lmic Tcpu ? Tmic 计算得到CPU和MIC的负载Upu和Lmi。;最后根据负载比例，将数据从CPU端分载至MIC端， 使用offload分载模式中的异步计算模式在CPU和MIC端并行计算，W此做到负载均衡。

　　[0012] 本发明的有益效果是：1、本发明异构众核系统中有限差分算法优化方法，应用= 步递进优化法解决有限差分算法从多核系统到异构众核系统时由跨越式访存、可并行执行 绪不足带来的计算性能低、并行效果差的问题，是一种具有高效性、可扩展性的优化方法， 通过分支消除、循环展开、不变量外提等基本优化法削减计算强度并为向量化扫除障碍;通 过分析数据依赖，循环分块，使用向量指令集改写核屯、算法等并行优化法，充分利用众核处 理器多线程、长向量的机制;在异构众核平台下，通过数据传输最小化，负载均衡等异构协 同优化法，实现并优化了多核处理器和众核处理器的并行计算。

　　[0013] 2、本发明异构众核系统中有限差分算法优化方法，采用指令级预取技术解决算法 由跨越式访存导致缓存脱祀从而造成计算部件等待数据加载，浪费计算资源的问题。创新 地采用多级缓存预取，使基于流水线的硬件执行单元可W提前完成读数据操作，减少流水 线气泡的产生，加速指令的执行。

　　[0014] 3、本发明异构众核系统中有限差分算法优化方法，应用多层循环分块技术解决算 法从多核系统到异构众核系统时可并行执行绪不足的问题，是一种灵活、可扩展的优化技 术，创新地采用启发式分块探索最优块大小，使算法具有更好的局部性，更加紧密地适应异 构众核系统的多级cache配置。

　　[0015] 4、本发明异构众核系统中有限差分算法优化方法应用于众核加速器(MIC)与多核 通用处理器(CPU)或其它处理器相结合的混合异构的高性能计算机系统中，通过数据传输 和异构协同优化将数值计算在多核处理器与众核处理器上并行进行，同W往的多核或众核 并行结构相比，利用该优化方法即可W支持异构众核系统上算法的高效执行，又可W通过 PCI-E互联其他异构众核系统，使用消息传递接口（MPI)提供集群级并行，取得最大程度的 加速。

　　[0016] 图1为有限差分(Finite Difference)算法异构协同计算原理图； 图2为有限差分算法异构数据划分及传输示意图；

　　[0017] 实施例1:结合图1-图2,一种异构众核架构中有限差分算法的优化方法，有限差分 算法采用=步递进优化法进行优化，所述=步递进优化法的具体步骤为： 步骤一、基本优化，提取循环不变量削减计算强度、消除循环分支W利于向量化;具体 为:通过循环展开、不变量外提基本优化法削减计算强度，变换循环变量初值及退出条件消 除分支判断。

　　[0018] 步骤二、并行优化，采用化enMP并行模型，通过在核屯、循环前加入编译指示，实现 线程级并行，采用内建向量指令改写核屯、循环，实现指令级并行;具体为:循环分块后，使用 OpenMP并行模型，使多线程执行算法时具有更好的空间局部性，同时，使用内建向量指令并 插入数据预取指令，有效缩短计算单元等待数据传输的时间；内建向量的具体步骤为:步骤 201:将X维循环for(x = xx;xxmax;x++)改写为for(x = xx;xxmax;x+ = 16)，Wl6个单精度 浮点数为一个向量，每循环一次得到16个计算结果，循环量降为原来的1/16; 步骤202:将16个连续数据prev[x+i]. . .prev[x+i+15]读取至512位向量寄存器xVec中 W计算FDx的第i个分量，并将结果累加至向量寄存器sumVec中，将16个连续数据prev[x+i* nl]. . .prev[x+i*nl+15]读取至512位向量寄存器^ec中并计算FDy的第i个分量，并将结果 累加至向量寄存器sumVec中，同理将16个连续数据prev[x+i*nln2]. . .prev[x+i*nln2+15] 读取至512位向量寄存器zVec中W计算FDz的第i个分量，并将结果累加至向量寄存器 sumVec 中； 步骤203、使用向量融合加/减指令计算next,将计算结果写回next[x]. . .next[x+15]。

　　[0019] 步骤S、异构协同优化，在异构众核平台下，使用offload分载模式可W将部分计 算从CPU端分载至MIC端。主要包括数据传输优化和负载均衡优化。

　　[0020] 数据传输优化具体方法为:有限差分算法主要包括next、prev和vel立个数组;=个数 组的传输量均与分载给MIC的负载有关:设在X，Y，Z维度下的输入规模为Nl，N2和N3,CPU与MIC 的负载比例为Lc:Lm，数组vel作为只读数组，仅需首次由CPU传向MIC并由MIC保留在其内存 中，传输数据量天

　　字节，之后的迭代不再需要将vel传给MIC， 使用分载模式中的nocopy技术实现;数组next和prev均为读写数组，在时间步迭代中依次轮流 担任写目的地数组，因此除了需要首次将数据传输牵MIC，巧化讨巧中还要巧巧专換依硫部 分；首次传输数组next和prev的数据量均；

　　字节;每次迭代结束时，CPU端与MIC端交换依赖数据:CPU端传输Nl*N2*8*sizeof(float)字 节的数据至MIC,同时MIC端传输Nl*N2*8*sizeof (f Ioat)字节的数据至CPU;将数组next分 给CPU和MIC并行计算，阴影部分数据不在计算范围，而是在当次迭代结束后由另一端传输 过来;数组nextmiG最后的N1*N2*8个数据由CPU端对应部分的计算结果传入，nextcpu最前的 N1*N2*8个数据由MIC端对应部分的计算结果传入;数据交换结束后即可开始下次迭代，直 至程序结束。负载均衡优化具体方法为:首先根据输入规模分别在CPU端和MIC端运行优化 后的程序，使用分块探索工具得到最优的分块大小;然后使用在CPU和MIC上测得的程序吞 吐量Tepu和Tmi。，并根据公式 Lcpu : Lmic - Tcpu ： Tniic 计算得到CPU和MIC的负载Upu和Lmi。;最后根据负载比例，将数据从CPU端分载至MIC端， 使用offload分载模式中的异步计算模式在CPU和MIC端并行计算，W此做到负载均衡。

　　[0021] 具体实施例2:结合图1-图2,参见图1、图2,本发明异构众核系统中有限差分数值 算法优化方法，在基于众核加速器(MIC)与多核通用处理器(CPU)相结合的混合异构高性能 计算机系统中，通过变换循环变量初值及退出条件消除分支判断，因为处理器在处理条件 分支时，分支预测逻辑单元在计算结果可用之前就会采用基于统计的方法对该计算结果进 行预测，一旦分支预测失误，指令流水线将重新回到该分支位置，产生流水线气泡，造成时 钟周期的浪费。此外，分支预测失败后，编译器也就不能继续进行循环展开或SIMD向量化等 后续优化，影响程序性能;通过在核屯、循环前加入编译指示，实现线程级并行，采用多层循 环分块的方法对算法的=层循环进行分块，将算法核屯、的=重循环局部于块内，同时使用 化enMP编译指示collapse子句压缩分块后的循环W提供充足的可并行执行绪；由于程序存 在跨越式数据访存，存在访存不连续现象，因此加入多级缓存预取指令_111111_966*证^降 低由于缓存脱祀所产生的延迟:在每次读取一个维度的向量数据之后，调用_mm_pref etch 将下一循环所需要的同维度向量数据预取至LO化che，同时将距离DIST的向量数据预取至 Ll化Che，其中DIST需要通过测试获得。

　　[0022]通过CPU与MIC协同并行进一步提高程序效率。使用off load分载模式可W将部分 计算从CPU端分载至MIC端，需要指出，由于CPU和MIC不共享物理内存，对有限差分算法进行 异构协同优化时，分载至MIC端的计算所依赖的数据也要从CPU的内存空间传输至MIC的内 存空间，因此会产生额外的通信开销；另一方面，由于程序并行运行在CPU和MIC上，两端硬 件结构的差异势必造成程序在两端运行时的性能差异。因此需要对数据传输进行优化W最 小化数据交换，W及按照CPU和MIC的计算能力合理地分配负载。在负载均衡优化中，首先根 据输入规模分别在CPU端和MIC端运行优化后的程序，使用自动测试工具得到最优的分块大 小;然后使用在CPU和MIC上测得的程序吞吐量(单位时间内处理浮点数的数据量)Tcpu和Tmic 计算得到CPU和MIC的负载Upu和Lmi。。最后根据负载比例，将数据从CPU端分载至MIC端，使用 offload分载模式中的异步计算模式在CPU和MIC端并行计算，W此做到负载均衡。

　　1. 一种异构众核架构中有限差分算法的优化方法，其特征在于:有限差分算法采用三 步递进优化法进行优化，所述三步递进优化法的具体步骤为：步骤一、基本优化，提取循环不变量削减计算强度、消除循环分支以利于向量化；步骤二、并行优化，采用OpenMP并行模型，通过在核心循环前加入编译指示，实现线程 级并行，采用内建向量指令改写核心循环，实现指令级并行；步骤三、异构协同优化，在异构众核平台下，使用offload分载模式可以将部分计算从 CHJ端分载至MIC端。2. 根据权利要求1所述的异构众核架构中有限差分算PG电子平台网站法的优化方法，其特征在于:所述 步骤一的具体为:通过循环展开、不变量外提基本优化法削减计算强度，变换循环变量初值 及退出条件消除分支判断。3. 根据权利要求1所述的异构众核架构中有限差分算法的优化方法，其特征在于:所述 步骤二具体为:通过分析数据依赖，使用内建向量指令改写算法，进行循环分块，然后使用 OpenMP并行模型，使多线程执行算法时具有更好的空间局部性，同时，使用内建向量指令并 插入数据预取指令，有效缩短计算单元等待数据传输的时间。4. 根据权利要求3所述的异构众核架构中有限差分算法的优化方法，其特征在于:所述 内建向量的具体步骤为： 步骤201:将父维循环;1^〇1(叉=叉叉;叉〈叉1]1叉++)改写为;1^〇1(叉=叉叉;叉〈叉1]1叉+=16)，以16个单精度浮点数为一个向量，每循环一次得到16个计算结果，循环量降为原来的1/16;步骤202:将16个连续数据prev[x+i] · · .prev[x+i+15]读取至512位向量寄存器xVec中 以计算FDx的第i个分量，并将结果累加至向量寄存器sumVec中，将16个连续数据prev[x+i* nl]. . .prev[X+i*nl+15]读取至512位向量寄存器yVec中并计算的第i个分量，并将结果 累加至向量寄存器sumVec中，同理将16个连续数据prev[x+i*nln2] · · .prev[x+i*nln2+15] 读取至512位向量寄存器zVec中以计算FDz的第i个分量，并将结果累加至向量寄存器 sumVec 中；步骤203、使用向量融合加/减指令计算next，将计算结果写回next[x]. . .next[x+15]。5. 根据权利要求1所述的异构众核架构中有限差分算法的优化方法，其特征在于:所述 步骤三主要包括数据传输优化和负载均衡优化。6. 根据权利要求5所述的异构众核架构中有限差分算法的优化方法，其特征在于:所述 数据传输优化具体方法为:有限差分算法主要包括ne Xt、preV和vel三个数组;三个数组的 传输量均与分载给MIC的负载有关:设在X，Y，Z维度下的输入规模为NI，N2和N3，CPU与MIC的 负载比例为Lc :Lm，数组vel作为只读数组，仅需首次由CPU传向MIC并由MIC保留在其内存 中，传输数据量）：节，之后的迭代不再需要将vel传给MIC，使用分载模式中的nocopy技术实现;数组next和prev均为读写数组，在时间步迭代中依次轮流 担任写目的地数组，因此除了需要首次将数据传输至MIC，迭代过程中还要相互交换依赖部分；首次传输数组next和prev的数据量：字节;每次迭代结束时，CPU端与MIC端交换依赖数据:CPU端传输Nl*N2*8*sizeof(float)字 节的数据至MIC，同时MIC端传输Nl*N2*8*sizeof(float)字节的数据至CPU;将数组next分给CPU和MIC并行计算，阴影部分数据不在计算范围，而是在当次迭代结束后由另一端传输 过来;数组nextmi。最后的N1*N2*8个数据由CPU端对应部分的计算结果传入，Iiextcpu最前的 N1*N2*8个数据由MIC端对应部分的计算结果传入;数据交换结束后即可开始下次迭代，直 至程序结束。7.根据权利要求5所述的异构众核架构中有限差分算法的优化方法，其特征在于:所述 负载均衡优化具体方法为:首先根据输入规模分别在CPU端和MIC端运行优化后的程序，使 用分块探索工具得到最优的分块大小；然后使用在CPU和MIC上测得的程序吞吐量 Tmi。，并根据公式：计算得到CPU和MIC的负载1^11和1^。;最后根据负载比例，将数据从0?1]端分载至[(：端， 使用off load分载模式中的异步计算模式在CPU和MIC端并行计算，以此做到负载均衡。

　　【申请人】中国人民解放军信息工程大学, 中国南方电网有限责任公司电网技术研究中心, 南方电网科学研究院有限责任公司

　　技术所有人：中国人民解放军信息工程大学;中国南方电网有限责任公司电网技术研究中心;南方电网科学研究院有限责任公司;

　　针对传统PS-DInSAR参数估计方法在时间/空间基线不均匀时精度低的问题，提出结合优化解空间搜索与Levenberg-Marquardt算法的混合策略。通过先粗略搜索确定参数范围，再局部优化...

　　1.计算机网络安全 2.计算机仿线.网络安全；物联网安全 、大数据安全 2.安全态势感知、舆情分析和控制 3.区块链及应用