【ASC15】工作篇—Gridding调优

在中大的ASC15队伍里,我和一个同是数计院的学长YRK搭配,负责Gridding这道代码调优的题目。关于Gridding,可以参见这篇报道,我也顺便给出浪潮提供的初赛源代码复赛源代码,有兴趣的诸位可以下载下来看一下。由于相关规定,我不能公开我们的源代码。下面简单提一下我们都做了些什么。

我们在拿到这份代码的时候,负责指导我们的叶老师(我们喊他叶总)告诉我们,浪潮自己已经做过这个代码的优化了,在一个双路E5(24个物理核心)+一张MIC卡的节点上能做到原始串行程序的80倍优化速度。所以我们初赛的目标就是达到80倍,这样就比较保险了。当时我们想了一下,如果按多核多线程加速效率0.7这个比较理想的值来算,我们要在串行代码上压榨出5倍的性能来才能达到要求,感觉压力还是挺大的。

在压榨串行性能方面,我们做了一些常规的工作,比如AoS to SoA,排序,砍掉不参与计算的虚部,以及将一个矩阵降维变成了两个向量。最后这一点非常关键,没有做这个操作之前我们的并行程序最多跑到20倍加速,但是通过这种数学上的处理以后,我们的内存使用量和内存带宽可以大大减少,而Gridding某种意义上是Memory Bound的程序,所以可以有很大的加速效果。至于砍虚部,是我们观察到在计算中整个虚部都是0,所以就一刀砍掉了。这个方法其他不少队伍也用了,但不知道降维的方法有没有人用。

初赛之前我们只需要做单节点上的共享内存模型并行化,所以直接用OpenMP。为了解决写冲突,我们对计算范围进行了分块并加入了冗余单元以避免写冲突。最后测出来,Xeon E5-2692v2 @ 2.2 GHz上24个物理核心的加速效率在0.6左右,总的加速倍数在85倍左右,还算可以接受。

交初赛报告之前有一件很惊险的事情。在初赛报告提交前一天(3月19日早上9点截止交报告)下午,浪潮放出了第三份Questions & Answer,对一些提问做了集中回答,其中就有关于虚部的问题。浪潮表示,所有的代码应该确保,在他们对虚部进行初始化以后还能得到正确的结果。这一份QA是我们交了报告以后才看到的,相信不少队伍也是如此。叶总知道以后很无奈地说不管了,我们砍了就砍了吧,且看浪潮怎么对应。出结果前的那个星期,我们真的很担心浪潮因此砍掉我们这道题,结果最后浪潮五天就出结果,显然没去用“有初始化虚部的数据”去测一次所有的代码。

不过进了决赛以后,代码果然被改了:虚部被初始化了,而且那个可以被降维的矩阵的表达式也被改了。但是,世上无难事,只怕『夹硬来』,我们又硬生生地把这个新的矩阵给降维了。直到四月中旬决赛发布会,浪潮的人义正言辞地说我们只能改gridKernel这个函数里面的内容,外面的内容我们不能改,并且无论他们怎么改外面的,只要gridKernel的参数和接口都还没变,我们的程序都要跑一个正确的结果出来。这个结果让我们很无语,因为我们的优化是针对实际问题对应的数学背景做出来的,完全是合法合理的啊!毕竟一个数学模型上的优化可能比一堆计算技术上的优化都要来得彻底!

决赛的新代码里已经帮我们写好了MPI通信分发工作负载和各MPI Worker计算完以后回收到根进程的代码了。这部分不允许改,也不在计时范围内,倒也是帮我们省了不少工作量。显然,当MPI进程多的时候,数据收回(这个需要计时)的时间会很多,所以我们最后还是要在单节点内用OpenMP开多线程,节点之间用MPI。

为了使得访问内存连续和后续优化,排序是必须要做的。初赛的时候数据量不多,我直接写了一个串行排序就解决了。到了决赛,数据量会大上千倍,O(nlogn)的算法显然撑不住,所以我用最经典和最容易实现的PSRS算法写了一个节点内多线程的并行排序。节点之间的数据在读入的时候就进行了切分,不需要我们去操心。我们还对同一个节点内的数据做了分割处理,每一次最多只处理一亿个sample点,避免排序的时间太长和需要的内存太多。后来,我们发现可以先用桶排序,然后各个桶之间再同时做快排。这样每一次的排序时间从2.5秒下降到了0.8秒,最后算是一个很有效的优化。

为了减少访问不连续带来的内存跳行甚至换页掉页,针对这个代码的数学模型,我交换了第一层和第二层循环。这个优化的效果是很明显的。

为了减少内存申请的时间,我把所有中间数组都先申请一个很大的空间,每一次判断是否超出范围,如果是的话再重新申请空间。同时我发现,使用malloc比使用new要快,大概是因为new要处理对象的成员函数指针问题。我测了一下,我们申请一次空间,new需要1.5秒,malloc只需要0.6秒。

初赛的时候叶总没让我们用BLAS(基础线性代数子程序集,高性能计算经常使用的一个数学库),进入决赛以后我们发现,对complex的计算 += a * (x y表示行向量,a是一个标量),cblas_zaxpy(cblas表示c风格的BLAS函数,z表示双精度的复数,axpy = A * X Plus Y)比我们手写循环要快,而且CPU的有效计算利用率也更高一点。但后来我们发现,只要在编译时告诉编译器使用AVX指令集,在代码里强制使用#pragma simd指令进行向量化,计算速度和 Intel Math Kernel Library 里的cblas_zaxpy一样快。

决赛要求一定要使用offload模式在MIC卡上进行计算,所以我们硬着头皮去给MIC卡写了代码。说是说只要加几条#pragma offload target(mic)的引语在代码里就可以在MIC上运行,但是速度却是令人无语。MIC卡L1 L2 Cache和CPU的一样,但是没有L3 Cache,这是一个很大的问题。这意味着,如果数据不能命中L2,就是LLC Miss了,需要到显存里去读取。这令我们的优化很难做。事实上,我们也没有为MIC卡单独做优化,因为时间不够了。但是我们还是做了一点小的优化。虽然决赛规定不能拆其他部分,意味着我们不能做全局的AoS to SoA,但是我们把传给MIC的数据做了AoS to SoA,同时加上了手动四路展开循环来达到指令流水线级的并行化,以及别的一些局部计算顺序优化,速度总算上来了。还有一个问题就是,MIC卡的显存太小了,使得我们需要将计算的数据分批上传,否则也会影响速度甚至爆显存。到出发前,我们MIC卡的速度和单节点CPU 24核的速度,大概是4:5左右,接近1:1。

出发前一天我们做了一个很关键的优化,这个优化让我们的速度在数据量足够大的时候提升了一个数量级。之前我考虑过这个做法,但是一直没敢动手,就是担心是否有那么密集的数据可以给我占这个便宜。后来考虑到决赛的数据肯定会很大,就大胆地做了这个优化。其实说起来很简单,就是乘法分配率,A×B + A×C = A×(B + C),但是由于加法的速度比乘法的快,所以就压掉了很多时间。最后决赛的成绩,我们和清华基本一样,都甩了其他队伍一个量级,就是因为这个优化。按照SKA出的论文,我们和清华的优化速度,已经能够用16个节点解决他们2011年所需要的几千个节点才能处理的数据。即使按照后来浪潮发的新闻,我们“完成同等规模计算量的功耗只有原来的二十分之一”,这么说来买机器的钱都能省下好大一笔了。

回头看看,我们初赛和决赛最大的优化,都是数学模型上的简化。果然数学才是大杀器啊!

最后,我们很幸运地获得了今年的e Prize计算挑战奖。可惜这个奖并不是由SKA软件包的负责人来给我们颁发的,也不是刘慈欣来颁发(大刘没到现场)。

 

【ASC15】工作篇—Gridding调优》上有2条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注