协方差优化

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

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

访存不连续

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

• 改变循环顺序：将 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 的方式，但是在这里用不到，通常在需要进行多种运算，多次迭代的程序中使用。（看起来好烦啊）