协方差优化 LeeRinji

暑假里选拔赛的第二题,感觉自己当时还是轻视了这个题,其实这个题能学到的东西真的很多(现在觉得比第一题还给劲)。自己当时是做到了六七秒,而这个题最佳目前是可以跑到一秒左右的。

由于之前暑假里已经做了一些优化,这次记录一下内培里自己新学到的一些东西。

访存不连续

除了一些常见的改编译选项、矩阵分块之类的优化以外,这个题目最主要的性能瓶颈是访存不连续。换言之,在求协方差的过程中有大量的同列不同行的访问。所以,代码层面要解决这个问题,有以下两种思路:

自己暑假做这个题的时候使用的思路是前者。后者这个思路是自己之前从来没有想过的,主要是因为要重新存一遍整个数组,这个至少要先把这个矩阵遍历一遍。

然而,虽然计组课上已经学过,对“缓存的速度快于内存几个数量级”这个概念没有亲身经历过还是没有理解。后续主循环内有十到二十次左右都在跨行访问列,因此这样做虽然是需要有一个额外存转置的过程,但时间上反而能快数十倍。再一个就是空间复杂度,一个50000*50000的矩阵只需要额外占用 20G 的空间(打 ACM 单题能有 512M 都觉得好奢侈啊),由于当时提供的 knl 平台有 96G 内存,因此是完全足够的。

矩阵分块

其实自己暑假也有尝试过,但是在自己改变循环顺序的代码上效果不明显。在转置的代码上应该挺明显的吧…

关闭超线程

暑假确实发现这个程序使用 64 线程和 256 线程几乎无差别,还以为是自己哪里写错了…

其他