稀疏矩阵计算工程实现心得
2018-03-02
在机器学习中，经常遇到稀疏向量，稀疏矩阵。如何高效处理这些稀疏对象，决定了一些模型能否在线落地应用。目前正在专攻这方面，自己瞎琢磨，走了不少弯路，也有一点心得。这里记录下来，不断总结。
算法改进
这是最直接简单的，收益也最大的。比如在千万级以上的向量空间中搜索最近邻居，暴力的两两计算代码层面无论如何加速计算量依然太大了。Faiss 通过预训练聚类和向量压缩大大减少搜索时的计算量，上亿级别搜索也能在毫秒级完成。
例外情况是计算量本身不是特别大，并且在代码层面很方便加速，改进对 CPU 负载的也不是特别大。比如利用 avx 和 openmp，这时直接代码加速也是可行的。
引用第三方库
当要在代码层面加速时，首先考虑已有的第三方库。选择库时第一原则轻量，稳定，而不是花哨，功能强大。BLAS 实现中 OpenBlas 最好用，但是只支持稠密矩阵。MKL 支持稀疏矩阵，性能也最好，但是编译链接很麻烦。不过机器学习中的算法一般不能很好的直接映射到稠密矩阵计算，比如 FM。
手写Kenerl
BLAS 库适用场景是超大矩阵和超大向量，一次计算，结果写回主存。如果计算步骤过多，中间结果读写主存会有很大开销，这时比较适合手动优化。手动优化需要充分利用寄存器和缓存，尽量让中间结果在寄存器和缓存中保存。其实挺难的，而且现代硬件已经特别复杂，自己臆想的一些手段不一定就符合硬件的喜好。所以验证很重要。
并行计算 当并行数不大时，可以直接使用 CPU 并行。但是 CPU 核心毕竟比较少，大规模并行GPU更有优势，这是目前正在学习的方向。
心得
- 工程实现常常要对公式做变换，利于向量计算或并行计算。因此理解核心算法才能做出取舍和变换。
- 多多学习第三方库的优秀算法，第三方库的实现通常为了考虑通用性优化没有做到极致。而为了适应手头的需求可以各种魔改，优化就是特化。