11 - Hardware Acceleration for Linear Algebra
首先讲解了通用优化方法，比如向量化操作。然后以矩阵乘法为例，不断的优化矩阵乘法中的缓存问题。
General acceleration techniques向量化 Vectorization数据布局 和步长 Data layout and stridesParallelizationCase study: matrix multiplicationVanilla matrix multiplicationRegister tiled matrix multiplicationCache line aware tilingPutting it together
General acceleration techniques
机器学习框架的组成，hw1实现了计算图，hw2用计算图封装了机器学习模型，hw3实现一个 Tensor 库， 所以本课程像是自顶向下，但是又环环相扣。
向量化 Vectorization
在 Vector 寄存器加载一块连续的内存，运算完成后，再存储到特定的内存。
上图中的伪代码，展示了 长度为256的数组相加时的向量化版本：一次加载4个数字，可以减少循环次数。
数据布局 和步长 Data layout and strides
向量化的关键是从一块连续的内存块中加载数据，所以存储数据时内存分配需要有特殊要求。一般从内存的角度看有如下两种存储方式：
- 按行存储
- 按列存储
这里的行和列均为 广义的行和列，对于高维数组，按行存储是指最后一个维度是按照行存储的。Fortran 语言实现的库大都是按照列优先顺序存储。而 c /c++ 语言实现的库一般是按行存储的。
上述为两种存储方式，但是在索引的时候，除了上述两种，还可以按照步长 strides 来索引，现代 线性代数库通常即是按照这种方式来索引，其优势在于可以不操作内存而实现高维数组的reshape、broadcast、transpose等操作。其优缺点如下：
- Advantages:
- can perform transformation/slicing in zero copy way
- Slice: change the begin offset and shape
- Transpose: swap the strides
- Broadcast: insert a stride equals 0
- Disadvantages:
- memory access becomes not continuous
- Makes vectorization harder
- Many linear algebra operations may require compact the array first
因为只通过 改变 strides，实现的reshape 之后，内存不连续了，所以在很多操作实现需要执行 compact 操作，即新创建一个内存紧凑的高维数组。
Parallelization
使用openmp来并行计算是另外一种常见的优化手段
Case study: matrix multiplication
Vanilla matrix multiplication
Compute C = dot(A, B.T) 时间复杂度为 float A[n][n], B[n][n], C[n][n]; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { C[i][j] = 0; for (int k = 0; k < n; ++k) { C[i][j] += A[i][k] * B[j][k]; } }
从内存架构及每部分的的延迟可知，需要减少从DRAM加载数据的次数，尽可能的的在缓存Cache上多利用已经加载的数据，即提高缓存命中率。XGboost 有专门对这个做优化。
从架构的角度分析一下矩阵乘法：
上图的数据 为 从dram到寄存器 花费的时间 以及 寄存器的内存消耗 。可见，主要的时间消耗都在数据加载上面。因此有了下面两种优化手段：
Register tiled matrix multiplication
上图表示，一次从内存种读取 A矩阵中的 v1 * v3 大小的矩阵，因此，少了 v2 倍，这里为什么是v2倍呢？因为 矩阵A的数据肯定是都要加载一遍的，但是通过分块，使得 少加载了v2倍次。
改变加载数据的方式，时间消耗减少了，寄存器消耗增多了
Cache line aware tiling
一次加载一行的优化方式。
Putting it together
将上述两种方式合并一起。然后再优化一下代码，便有如下代码：
上述代码中的 a, b 也是一个矩阵，只是元素比较小。
hw3 中有上述的具体实现。