2014全国并行应用挑战赛初赛技术报告模版

应用程序简介应用程序运行环境应用程序分析应用程序运行和优化过程应用程序运行和优化结果1.应用程序简介3D

Elastic

Wave

Modeling（简称3D-EW），三维弹性波模型。3D-EW方法是一种用波场延拓的方法来模拟弹性波在各

向同性的弹性介质中

的方法。在这个程序中，纵波（P波）和横波（S波）被分别模拟，这样可以更好地得知纵波和横波在弹性介质中的传递。该方法可以通过高阶有限差分方法来模拟弹性波的传递。3D-EW广泛应用于石油和天然气勘探领域。这个应用 在参加ASC14，2014世界大学生超级计算机竞赛时，取得了满分的好成绩。如今 在之前的代码上进一步优化，取得了大约15%的提升。2.

应用程序运行环境硬件环境：CPU:

2×In Xeon

E5-2670(8

Cores,

2.6GHz,

20MB

Cache,8.0GT)Mem:

64GB(8×8GB)

ECC

Registered

DDR3

1600MHz

Samsung

MemoryMIC：In Xeon

Phi

5110P

Knights

Corner环境：OS:

Red

Hat

Enterprise

Linux

Server

release

6.3

(Santiago)Kernel:2.6.32-279.e16.x86_64In compiler:13.1.1

(gcc

version

4.4.6

compatibility)并行接口：OpenMP输入规模：case1:360*360*280的介质区域，100单位时间，模拟20次波传递case2:360*360*280的介质区域，500单位时间，模拟1次波传递注：波 的范围随着时间加大。在case1中，波只 了该区域1/30不到的空间，在case2中就已经充满了整个区域，所以虽然第二次算例只模拟一次波的

，运算量却大大超过算例13.应用程序分析这个程序的代码并不长，只有几百行。没有自编函数和类，是典型的面向过程的程序。程序需要一个输入文件和两个输出文件。输入文件包含了许多参数，输出文件包含两个，一个是真正的输出文件，输出一组参数；另一个是log文件，记录程序的输入信息和运行时间。3.应用程序分析程序的结构如右边的图所示。程序主要是由一个ishot循环和一个lt循环构成，其中ishot每次循环不需要迭代，lt循环前后需要迭代数据。在计算各点参数时，实际上也是一个kji的三层循环（kji对应区域的长宽高）。每次ishot循环完成后都要输出一组数据，为高度为169的点的一个参数。最终运行完以后会统计程序运行时间并输出时间。验证程序输出是否正确需要用到另一个专门检验误差的程序。在这个程序中，如果和原程序输出的误差在规定范围内，程序输出就算正确。4.应用程序运行和优化过程程序的I/O很少，热点集中在对各点的参数计算那一部分。主要的瓶颈则在CPU的计算部分1：因为源代码是串行程序，用OpenMP与在单节点上达到并行效果，提高效率2：用OpenMP进行线程级并行以后，使用向量化进一步提高性能3：通过OpenMP并行+向量化后，程序在CPU上获得了非常好的加速效果，之后

尝试在CPU+MIC上进一步提升性能4：使用传统编程方法优化后，发现MIC上虽然已实现并行和向量化，但是性能远远低于理论值，通过阅读大量文献以及查看生成的汇编代码，发现编译器生成了大量的低效率的gather/scatter指令，运用底层的Cintrinsic指令改写代码，使得程序变得更有效率，单M性能达到最优版本（OpenMP+SIMD）代码在CPU上性能的两倍。5：最后，根据程序的情况，修改了算法中不合理的地方，同时在向量化方面取得了 优化，使得程序性能进一步提高。4.应用程序运行和优化过程优化方法1：用openmp使得程序有线程级并行注：并非每一处的openmp优化的pragma都一样，此为示例返回4.应用程序运行和优化过程优化方法2：使用simd使得程序做到向量化注：实际上向量化并不都是这么简单，有些地方需要手动展开循环，有些地方要修改运算步骤返回4.应用程序运行和优化过程优化方法3：将程序由cpu运行改写为CPU+MIC运行，具体方法是把一部分cpu的计算转移到MIC上去原代码改进代码{}…//计算{…//一部分计算}#pragmaoffload

(mic){…//另一部分计算}{…//host与MIC通信}注：这是CPU+MIC

思路，在之后的程序相比这时其实做了非常多的调整，但 并没有改变起先， 在规划CPU+MIC的运算时，想的方法是在ishot上进行拆分，前后的ishot没有数据依赖，通过ishot进行并行，好处是数据传输少后来 发现，有些算例nshot只有1，比如case2。这种时候这个方法就不合适了。在后面的优化方法中，拆分的方法为区域分解，在运算中把波的区域分成两个部分，一部分放在CPU上运行，另一部分放在MIC上运行。两个需要的数据传输了，但这个方法的泛用性更高。返回4.应用程序运行和优化过程原程序部分代码：这个循环是在刚才流程图中，这个部分里的一段可以看出，循环内 数组的跨度很大，空间局部性比较差，这也是为什么，普通

在MIC上取得的优化非常有限，一定要使用C

intrinsic修改代码才能达到比较好的效果4.应用程序运行和优化过程优化方法4：程序本身对MIC并不算很友好，所以要改写成对MIC友好的代码，具体方法是用Cintrinsic改写代码，可以使Cache存取效率得到大幅度提高并避免编译器生成的低效率指令原代码

C

intrinsic代码返回4.应用程序运行和优化过程优化方法5：最后

时发现算法还有一个可以改进的地方，把原本的数组值传递改为了地址传递，使得效率进一步提高原代码 改进代码for(….){…up2[…]=up1[…];up1[…]=up[…];…}Double

*tmp

=

up2;up2=up1;up1=up;up=tmpPS：这两步是在ASC14之后，在这次比赛中采用的新的优化4.应用程序运行和优化过程优化方法6：向量化之前有不完善的地方：在一这个三层循环 ，包括2个小循环与其他代码。自 量化不是在三层循环的最内层展开，而是在2个小循环处展开，结果剩下的一小部分代码就没有做到向量化

1：这两个小循环都是常数循环。为此 手动展开了这两个循环。2：即使如此向量化还是没有完成，后来发现是因为之前未循环的代码中有一部分的存在使得向量化无法成功。幸运的是，这一部分可以写在循环外面，做了这些改进了，向量化效果进一步提升了。4.应用程序运行和优化过程优化方法6：原代码

改进代码1：for

(…){for

(kk=1;kk<5;++kk){…//循环代码A（向量化）}…//代码B（未向量化）}for

(…){…//循环代码A（kk替换为1）…//循环代码A（kk替换为2）…//循环代码A（kk替换为3）…//循环代码A（kk替换为4）…//循环代码A（kk替换为5）…//代码B}4.应用程序运行和优化过程优化方法6：原代码

改进代码2：….….最后在循环外面添加5.

应用程序运行和优化结果优化汇总注：最开始的CPU+MIC的性能并不好，可以看到在case1里面提升很少，实际上，这里cpu承担了70%的工作（20个shot中的14次shot）而MIC只做了30%的工作，但即使如此MIC的时间仍然远远超过单用CPU的时间（128秒可以看做MIC算30%数据的时间+传输时间）。按照未加入C

intrinsic的代码，2块CPU的工作效率是MIC的10倍以上。case2的中，shot只有1次，所以只能100%CPU处理或者100%MIC处理，所以这里没有用最初的cpu+MIC测case2。优化时间（case1）提升（case1）加速比（case1）时间（case2）提升（case2）加速比（case2）原始404.001.004544.001.00修改，用openmp并行40.708.939.93368.0011.3512.35手动做simd向量化36.7010.0111.01263.0016.2817.28cpu+mic128.002.163.16///mic上添加intrinsic，手动做数据对齐62.505.466.46195.0022.3023.30改进数组传输，减少计算量61.805.546.54179.0024.3925.39完善向量化60.005.736.73169.0025.8926.895.应用程序优化结果126.8911.013.156.466.546.7317.2812.35123.3024.399.92CPUCPU+MIC5.应用程序优化结果在本次应用中，

发现，对3D-EW这种访存数据跨度比较大的程序，传统的优化 在MIC上效果不是很大，甚至性能不如CPU。 最终只能通过底层的C

intrinsic编程指令集消除编译器生成的低效率代码，发挥MIC架构核多、向量化宽度大的优点，并最终发挥出MIC的性能优势，使其在计算能力获得近2倍于最优化版本CPU程序在8核CPU上的性能。从刚才的表上可以看出，在case1中，MIC只占30%的计算量，时间就已经达到了128秒，而纯CPU的最佳版本，运行完整个应用只要36秒。由于这个CPU+MIC版本中I/O部分很少，如果简单用128/0.3，时间会达到

400秒以上，几乎与串行CPU版本没有差异，而最佳CPU版本的速度在它。按照这个比例case2中，自己估计甚至不止这个10倍以上，而此时两者用了完全相同的优化纯MIC版本至少也需要4500秒才可能跑完，据数。虽然在case1中，cpu+mic的最终版本的时间比单用cpu少，但这时因为传输 了太多的时间。case1的计算量远远小于case2，但其中每次传输的部分却是一样的。最终版本的cpu+mic程序中，在规模一样的情况下，传输的数据与shot*lt成正比。如此看来，计算量远远超过case1的case2，传输量却只是case1的1/4。这也就可以得知，为何在case2中，cpu+mic的性能会比纯cpu好不少。优化工作亮点之一是通过写底层的Cintrinsic代码，把3D-EW这个程序，从本身的MIC不友好，CPU的速度远超过MIC，改进成一个对MIC比较友好的版本。在最完美的版本中，CPU与MIC上的负载比例为4:5，也就是说，1块M

可以得到2.5块cpu（8核）的速度。尽管如此，由于host和MIC间需要做大量的 ，性能提升的红利被数据传输 了很多。之所以得到这种结果，是因为 对MIC编译器做了深入的研究。我们发现，如果不手动使用C

intrinsic编写代码，编译器就会调用很多低效率指令，从而造 能严重