TABLA: A Unified Template-based Framework for Accelerating Statistical Machine Learning

2016 IEEE InternationalSymposium 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]生成加速器调度。同时也为将要学习的模型参数生成一个顺序，这个顺序用于决定参数在内存中的布局和通信。

图1：Tabla的工作流

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.