TABLA: A Unified Template-based Framework for Accelerating Statistical Machine Learning
2016 IEEE International Symposium on High Performance Computer Architecture (HPCA)
motivation:
通用型处理器(CPU/GPU)对于计算密集型的机器学习算法的收益下降，FPGA提供了ASIC效率和通用处理器可编程性的中间点。但是使用FPGA去加速机器学习需要很长的设计周期和硬件的专业知识，所以开发了TABLA框架为一类机器学习生成加速器。
key:
关键在于找到大部分机器学习算法的共性，然后利用共性给程序员提供一个高度抽象。这个共性就是许多学习算法可以表示为一个随机优化问题。所以学习任务就变成了使用随机梯度下降，最小化目标函数来解决优化问题。
main work
TABLA提供了基于模板的加速框架，开发人员使用高级语言模板特殊化学习模型作为目标函数的梯度，TABLA自动为FPGA生成可综合的加速器实现(Verilog code)。
Overview
机器学习通常包含两个步骤：学习和预测。在学习阶段通过输入的数据生成一个模型，用于预测阶段得到结果。在学习阶段有着更多的计算可以从加速器中显著收益。所以TABLA提供了从编程模型到电路的全面解决方案来加速学习阶段。下面是TABLA的几个组成部分：
- High-level programming model: 随机梯度下降对于一类ML算法来说是统一的，所以，只需要程序员提供目标函数的梯度函数，程序员还提供了学习算法的初始参数和元参数，如学习率。
- Design Builder: 获得目标函数的梯度函数后，design builder利用预定义的加速模板和接口逻辑，输出可综合的Verilog代码用于加速器的具体实现。
- Predesigned template: 预定义的模板是由专业的硬件设计人员设计的，提供了一个通用的语言结构。
- Model compiler: 为加速器静态的生成执行调度。将梯度函数转换为数据流图，并用梯度下降的数据流图对其进行扩充，然后，使用最小延迟资源约束调度算法[17]生成加速器调度。同时也为将要学习的模型参数生成一个顺序，这个顺序用于决定参数在内存中的布局和通信。
Background on Stochastic Gradient Descent
SGD是一种优化算法，它的目标是找到使函数最小化的一组参数，这个函数通常称为目标函数或成本函数（objective/cost function）
Objective Function:
目标函数有根据输入的训练数据一系列学习的参数，它也称为cost函数，用于量化预测值和真实值之间的误差。
\[f(w^t_ix_i) \]\(w^t_i\) 表示第t次迭代中函数的参数，\(x_i\) 表示第i个输入的数据
目标函数是变化的，随机梯度下降的算法是不变的
Stochastic Gradient Descent:
随机梯度下降是利用梯度使下面的目标函数值最小
目标函数的值是有参数权重W决定的，所以梯度下降算法就是从一个初始的参数出发，不断的迭代移动这些参数使得函数值最小化。
这种迭代最小化的实现是通过在函数的导数递减方向上一步步实现的：
上面是梯度下降的公式。对于非常大的训练数据集，梯度下降迭代一次的花销overhead会非常大，为了避免非常大的数据花销，随机梯度下降被使用：
目标函数被分为更小的函数，小函数的梯度由一个单个的数据计算。相比传统的梯度下降迭代次数更多，但是避免了每次迭代对所有数据进行访问。
所以，TABLA框架只需要程序员将学习模型指定为目标函数的梯度。唯一的编程任务是为各自的算法实现这个梯度函数。经验表明这个梯度函数可以由少于50行的代码实现。
问题：
为什么不用其他的优化器，SGD的噪声和局部最优解的问题？（对比实验or前人的工作）
机器学习：各种优化器Optimizer的总结与比较_SanFanCSgo的博客-CSDN博客_optimizer
收藏版｜史上最全机器学习优化器Optimizer汇总 - 知乎 (zhihu.com)
Programming Interface
编程接口由两种类型的构造组成:数据声明（data declaration）和数学操作（mathematical operations）。
逻辑回归的例子：用于求逻辑回归的梯度
问题：
- 迭代次数怎么确定？
- 为什么不封装为一个函数，中间的代码也是模板（输入model_input，model_output着两个参数）
Model Compiler for TABLA
主要做两件事：一个是将目标函数梯度和随机梯度下降结合在一起生成数据流图，二是编译器将数据流图表示的学习任务生成一个静态调度
Integration of Stochastic Gradient Descent：
随机梯度下降的模板代码：
Data-Flow Graph Generation：
每个类型的数学操作的数据流图：
根据单个类型的数据流图进行组合，将随机梯度下降算法的代码加到梯度函数的数据流图里面：
Scheduling：
编译器生成DFG后，调度器可以为给定的资源约束生成操作的逐步调度。本文涉及的调度算法称为最小时延资源约束调度(Minimum Latency Resource Constrained Scheduling，ML-RCS)。
上面所示的算法通常被称为 Hu's Scheduling algorithm:
David C Ku and Giovanni De Micheli. High level synthesis of ASICs under timing and synchronization constraints. Kluwer Academic Publishers, 1992.
该算法通过以下假设来调度操作:(1)所有的操作都是单步的;(2)所有操作都使用单一类型的资源。这些假设适用于我们的加速器设计，因为我们的基础设计只包含一种类型的资源，称为Processing Engine，它只需要一步就能生成结果。
distance from sink：一个操作(op)的下沉距离是需要执行的操作的数量，在达到最终的输出/接收器之后。与接收器的距离是量化每个操作优先级的一个重要指标。
所有操作按照周期(c)调度：
(1) 之前的工作都已经安排完成;
(2) 它在未计划就绪的操作中具有最高的优先级(或距离接收器的距离)
(3)可用资源来容纳该操作
当所有操作都成功调度时，算法终止。
问题：
- 怎么计算下沉距离？
- 资源的移出和释放？（每一次周期的迭代都使用所有资源，每周期计算完成资源都自动释放？那么计算结果如何保存？数据的调度）
Accelerator Design
用FPGA来加速以编译器提供的调度表示的机器学习任务
Processing Unit:
Target FPGA Platform:
问题：
- 8个PE组成PU的结构优点？（布线资源的限制？）
- 是否有更好的加速结构？（流水线结构，根据功能划分模块的数据流水？）
Evaluation
FPGA: Xilinx Zynq ZC702
multicore CPUs:ARM Cortex A15 and Xeon E3
many-core GPUs :Tegra, GTX 650 Ti, and Tesla K40
Experimental Results
- Performance improvements:
图7a显示了taba生成的FPGA加速器和至强E3 CPU与ARM A15 CPU的基准加速。ARM是所有加速图中的基线。
如图7b所示。基线是ARM多核处理器。
- Performance-per-Watt comparison
- Area and FPGA utilization
表6显示了每种学习算法在FPGA上不同组件的资源利用率
