暑假里选拔赛的第二题，感觉自己当时还是轻视了这个题，其实这个题能学到的东西真的很多（现在觉得比第一题还给劲）。自己当时是做到了六七秒，而这个题最佳目前是可以跑到一秒左右的。
由于之前暑假里已经做了一些优化，这次记录一下内培里自己新学到的一些东西。
访存不连续
除了一些常见的改编译选项、矩阵分块之类的优化以外，这个题目最主要的性能瓶颈是访存不连续。换言之，在求协方差的过程中有大量的同列不同行的访问。所以，代码层面要解决这个问题，有以下两种思路：
- 改变循环顺序：将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的方式，但是在这里用不到，通常在需要进行多种运算，多次迭代的程序中使用。（看起来好烦啊）
|
|
|
|