CS217 2_BLAS Hardware Accelerators for Machine Learning

Goal

Design of hardware architectures for accelerating Machine Learning (ML)
课程目的设计加速ML的硬件结构
仅用于学习目的，有学习参考知乎严同学笔记内容

BLAS, Basic Linear Algebra Subprograms (BLAS)

BLAS

BLAS库是经典的高性能科学计算数学库接口标准，大部分超算用户在编程时都会调用BLAS库，同类型的线性代数库还有LAPACK以及intel的MKL等等。其中gotoBLAS库和openblas是开源的，

可以下源码来看，BLAS分为3个Level，Level1是向量-向量操作，比如向量加、向量乘等；Level2是矩阵-向量操作；level3是矩阵-矩阵操作。

BLAS Level3

BLAS Level3的核心实现是基于GEMM，IBM的算法和Power处理器架构能够很好的支持，并且有Fortran版本的BLAS库。

BLAS的复杂度

三层Level有不同复杂度，访问Mem的次数和计算次数复杂度。
BLAS库操作的复杂度如上图所示，Axpy表示Ax+y，只有复杂度n的操作，GEMV表示矩阵向量乘，有n平方的复杂度；而GEMM则是n的三次方的操作复杂度。同时每操作的访存次数也和n相关。

GEMM

GEMM是线性代数数学库中最核心的计算，也是很多重要应用的核心计算内容。在很多超算应用中很多时候都通过手动优化


GEMM是三层循环，计算C=C+A*B。所以算法的操作是2n^{3，同时要访问3n}2次内存。那么我们要怎么才能提升这个性能呢

Cache Oblivious/ Recursive GEMM

很直接的方法是使用cache进行划分处理，可以将A或B或AB的各一部分数据放在cache中，这样就可以减少访问主存的次数。但是这样也不能减少计算次数。

Blocked GEMM – 块处理

块处理GEMM对一个nxn的矩阵，每次处理大小为N的块，这样对于硬件来看其实处理的是bxb大小的矩阵，b=n/N是分块大小。大小为N的块可以存入cache或其他快速memory中，以便快速读出，计算完成后将结果写回主存。

gotoBLAS中的GEMM实现就使用了分块算法。从图中我们可以看到三种处理方法。第一种是将A和B矩阵分块，第二种方法是将C和B矩阵分块，第三种方法是将C和A矩阵分块。GEMM的子任务是GEPP或GEMP；最小粒度的任务是GEBP或GEPB或点乘。

GEMM 的计算

图中示例完成4x4的矩阵GEMM的核心计算如下所述：
rank1更新：
将大小为4x1的a向量（A矩阵的第0列）和大小为1x4的b向量（B矩阵的第0行）相乘，得到4x4的矩阵结果，然后与C矩阵的初始值相加；
然后是循环移动rank1的更新A矩阵的第1列和B矩阵的第1行进行rank1更新，直到A矩阵的最后一列和B矩阵的最后一行进行rank1更新，整个GEMM完成。

1）下面再从存储的视角观察GEMM的执行过程。首先最基本的是所有数据都在主存中，所以要完成C=C+AB的任务
2）然后在Cache中完成分块的子任务：A按列划分的子矩阵与B按行划分的子矩阵乘积，去更新C的值。
3）Cache中再将向量-向量乘继续细分到A列子矩阵的子行和B行子矩阵的子列进行乘积计算，得到更新后的C矩阵的行。
4）在核心内部寄存器按先列后行顺序更新packed A矩阵读入，在Cache中按先行后列顺序更新packed B矩阵读入。

GEMM Micro-Kernel

一个MRxNR的计算需要KC次A和B进行乘积更新运算，这也是GEMM微核心的典型循环迭代计算称为块点乘：载入packed A的一列，载入packed B的一行，计算点乘，更新寄存器中的C的老值。

那为什么不用简单的点乘一个一个元素去更新，而要用块点乘每次更新整个块的方法呢？可以看到浮点操作和访存操作的比值，简单点乘的话约等于1；而块点乘的则远大于1。由于我们希望运算访存比越高越好（这样计算效率就高），所以采用块点乘的方式。



当矩阵更大包含多个MR或NR的A、B矩阵时，就有两层的外层循环，循环更新步长为MR和NR。外层称为宏核心或内核心，也是通过cache实现的主要方式。
再最后来回顾一下GEMM，完成GEMM将矩阵划分为6级

Custom vs. General Purpose Design

通用设计中靠Cache、分支预测、乱序执行、SIMD等技术来提高GEMM实现效率。

Pedram实现了Rank-1的线性代数核，基本思路是用广播实现数据的分发，使用多个核完成计算。

整个硬件架构可以看到是一个2维MESH的处理单元阵列，PE每拍可以完成一个MAC运算，通过广播总线传输数据。

Tensor Core Unit of Nvidia

Nvidia的张量计算单元叫Tensor core，可以完成半精度浮点、单精度浮点的MAC运算。

从表中可以看到乘法的能耗要比加法大好几倍，而访存的能耗比访问寄存器要大很多。

在45nm工艺下，面积是SRAM占大头，功耗是MAC操作占大头。对于双精度浮点计算，60G/W是上限

性能扩展和功耗、面积的相关曲线如上图所示，我们的目标就是在设计空间找到最优的设计。

所以在设计系统时要将浮点部件功耗最优解的和访存系统最优功耗结合起来分析

最后要进行算法-硬件架构的协同设计，这样才能更好的加速算法，优化算法实现