SparseLoop论文阅读笔记
1 问题分解表述
1.1 一些概念
SAFs：sparse acceleration features（i.e. representation format, gating, and skipping）
IneffOps：ineffectual operations(i.e. arithmetic operations and storage accesses associated with ineffectual computations)
1.2 稀疏计算加速器特征
High-Level Sparse Acceleration Features
1.2.1 Representation format
只看一维的稀疏向量，常见的表示法
多维的稀疏张量，可以用单维表示法聚合
1.2.2 Gating IneffOps
可应用于存储单元和计算单元，让其保持空闲；可以节省能耗，但不改变处理周期。
A、先看单个操作数（leader），如果是0，则不访问另一个操作数（follower）的地址；因此不会消除全部的IneffOps，取决于leader的稀疏性特征。Gate Follower ← Leader
B、两个操作数同时看判断是否都不为0，通常靠的是存储格式的元数据；可以消除所有的IneffOps，比A的硬件复杂。Operand0 ↔︎Operand 1
1.2.3 Skipping IneffOps
直接跳过，进入下一个有效计算；同时节省能耗和处理周期。
将跳过应用于计算单元时，计算单元会直接查找下一对操作数，直到找到要执行的有效计算。当跳跃应用于存储单元时，它也可以通过查看单个操作数或两个操作数同时查看（同（2）），从而找到下一次有效计算。
比门控的硬件更复杂。
1.3 数据流
DNN/矩阵乘法。
数据流定义时间和空间中数据移动和计算的计划，SAF 定义实际移动的数据量或执行的计算数。因此，稀疏张量加速器的设计空间是数据流选择和 SAF 选择的交叉乘积
上图的这种分类法，可以将稀疏计算加速器系统地描述，并可用于定性地比较。
2 SparseLoop概述
2.1 设计挑战
（1）设计空间非常大，SAFs和workload的乘积。
（2）精度和速度的平衡，比如同一个workload的映射空间非常大无法穷举，而启发式搜索可能不是最优解。
（3）SAFs设计/workload的发展
2.2 解决方案
（1）对不同的设计方面进行解耦（dataflow、SAFs、微架构）
（2）一些复杂的相关性行为，采用统计数据建模。
3 稀疏循环框架
3.1 输入
3.2 STEP1：dataflow modeling
继承自TimeLoop（一个DNN加速器的模拟器），主要的思想是，抽象出数据流在各个存储级别中的划分和数据移动，然后根据输入的硬件参数估算出能耗等指标。
3.3 STEP2：Sparse modeling
稀疏建模首先使用特定于 SAF 的分析器（即门控跳过分析器和格式分析器）在本地评估 SAF 对每瓦流量的影响，然后通过简单的缩放对本地流量进行后处理，以反映 SAF 对整体流量的影响。
与格式无关的张量说明
fibertree ：每一层（level/rank）是张量的一个秩，最后一级是非零值，准确地反映了张量的稀疏性特征。
每一个fiber对应于正在处理的tile
统计密度模型
不可能枚举每一个fiber的映射空间来探索最佳的设计，因此采用统计模型。对于同样的密度模型（6/16=0.375），同一级不同纤维之间的密度有很大差异（rankO 中的纤维密度为 50%，概率为 0.75，密度为 0%，概率为 0.25）。
密度模型分为两种，一种是不同维密度分布相同，另一种是密度分布不同。SparseLoop目前支持四种密度模型。
format分析
Sparseloop支持5种per-rank format models: B, CP, UOP, RLE, and Uncompressed B。 \[ Overhead_{RLE} = nonEmptyelEments × runLengthBitwidth \\ Overhead_B = totalElements × 1 \]
gating/skipping分析
原始的每块密集流量分解为三种细粒度操作类型：i） 实际发生，ii） 跳过，iii） 被门控。
后处理
在分析器根据每个瓦的流量评估其各自 SAF 的影响后，稀疏建模执行后处理，首先反映 SAF 之间的交互（例如，由于跳过 SAF 而跳过了多少格式开销），然后根据传输的瓦片数量缩放每个瓦的细分，以得出最终的稀疏流量。
3.4 STEP3：Arch modeling
对于能源消耗，我们使用能量估算后端（例如，Accelergy）来评估每个细粒度操作的成本，并将其与其相应的稀疏流量相结合以得出准确的能耗。