协方差优化 wu-kan

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

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

访存不连续

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

  • 改变循环顺序:将 NV 放入最里层循环,合并相近的跨行访问,利用临时数组储存中间结果
  • 转置数组:先将整个数组转置,然后再进行求值计算

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

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

矩阵分块

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

  • 手动划分数据
    • 为每一个 OMP 线程指定要处理的列的范围(M 列)。
    • 每条 OMP 线程每一次只处理 N 行数据。
    • 利用omp_get_num_threads可以得到总的线程数
    • 利用omp_get_thread_num可以得到当前 OMP 线程的 id。
  • 线程每次处理的数据用临时数组存放,到最后进行汇总。
  • N 和 M 的数值是有依据的,比如 N*M 的大小不要超过 KNL 的 L2 cache,否则会发生不必要的 cacheMiss
  • 分块做完了总加速大概会达到 80+倍左右

关闭超线程

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

  • 服务器默认开启了超线程,超线程将一个物理核分为两个逻辑核,将两条占用资源互补抢占的线程指令混合执行以提高 CPU 利用率。
  • 但是这份代码是计算密集型的,使用超线程会使得两个线程互相抢占 CPU 而拖慢速度。
  • 关闭超线程需要重启服务器,我们只能通过调整线程数来避免抢占。

其他

  • #pragma unroll:将 for 循环展开(看了下编译 log,似乎编译器已经做了)
  • 统一数据类型,将统计数据 NumMissing 改为 double(已经做了)
  • Tbb malloc:高并发内存分配(其实还有别的方法,比如与分配内存,每个线程使用指定区域)。
  • 流水线优化:可以大大提高效率,这里没什么必要用。(待研究,这个怎么搞?)
  • 不使用 OMP,用 pthread 管理:OMP 使用 fork-join 的方法管理线程,我们用 pthread 可以改成 sleep-run 的方式,但是在这里用不到,通常在需要进行多种运算,多次迭代的程序中使用。(看起来好烦啊)