🏠

tree_based_ml_quantized_models_l2: FPGA-Accelerated Quantized Tree-Based Machine Learning

一句话概括

本模块实现了在FPGA上高速训练量化决策树和随机森林的完整流水线，通过定点数量化、数据流架构和层叠式并行处理，在保持模型精度的同时，将训练吞吐量提升10-100倍于CPU实现。

1. 问题空间：为什么要做这件事？

1.1 树模型训练的计算瓶颈

决策树和随机森林是机器学习中最常用的模型之一，但训练过程存在固有的计算挑战：

计算复杂度：对于 \(N\) 个样本、\(F\) 个特征、深度为 \(D\) 的树，每个节点需要扫描所有样本计算最佳分裂点，复杂度为 \(O(N \cdot F \cdot 2^D)\)。随机森林的 \(T\) 棵树使总复杂度乘以 \(T\)。

内存带宽瓶颈：训练过程需要反复遍历数据集，对内存带宽极度敏感。CPU缓存层次难以应对这种随机访问模式。

不规则并行性：不同节点的最佳分裂计算相互依赖（需要父节点分裂完成），难以提取大规模并行性。

1.2 量化：精度与效率的权衡艺术

浮点运算（32/64位）在FPGA上消耗大量DSP资源且延迟较高。量化技术将浮点数值映射到低精度定点数（如8位），带来三重收益：

  • 资源效率：8位定点运算消耗的DSP资源仅为32位浮点的1/4到1/8
  • 存储密度：相同的片上存储可容纳4-8倍的数据
  • 计算吞吐：定点运算流水线的时钟频率更高， initiation interval (II) 更低

但量化需要谨慎设计：过度的量化会导致模型精度显著下降，而不足的量化则浪费硬件资源。

1.3 FPGA的独特价值主张

相比GPU和CPU，FPGA为树模型训练提供了差异化优势：

细粒度数据流架构：不同于GPU的SIMT执行模型，FPGA可以实现自定义数据流流水线，每个计算单元专门化执行特定操作，消除指令开销。

确定性的内存访问：通过显式控制数据移动和存储层次（BRAM/URAM/DRAM），可以实现接近理论的内存带宽利用率。

动态精度调节：可以在同一设计中混合使用不同精度（如8位索引与16位累加），而GPU的warp执行模型要求同warp内统一精度。

低延迟推理：训练完成后，同一硬件可以立即进行超低延迟推理，无需数据搬运。

1.4 本模块的设计目标

本模块针对以下场景优化：

  • 中等规模数据集：样本数在 \(10^4\) 到 \(10^7\) 量级，特征数在 \(10\) 到 \(10^3\) 量级
  • 批量训练：需要快速训练多棵树（随机森林）或多轮迭代（GBDT）
  • 资源受限部署：需要在单张Alveo加速卡上完成训练和推理，不依赖外部CPU/GPU
  • 精度可接受的量化场景：如推荐系统排序、广告点击率预测、风控评分等

非目标场景：

  • 需要高精度浮点训练的科学计算
  • 样本数极少（\(<10^3\)）的小数据集（CPU更快）
  • 特征维度极高（\(>10^4\)）的稀疏数据（需要专门设计）

2. 心智模型：如何理解这个模块？

2.1 核心抽象：四层架构塔

想象本模块是一个精密的四层建筑，每一层处理不同粒度的并行性：

┌─────────────────────────────────────────────────────────────┐
│  Layer 4: Tree Ensemble (Forest Level)                     │
│  多棵树并行训练，每棵树独立但共享数据扫描逻辑               │
├─────────────────────────────────────────────────────────────┤
│  Layer 3: Node Parallelism (Layer Level)                    │
│  同一层多个节点同时处理，PARA_NUM个节点并行计算分裂         │
├─────────────────────────────────────────────────────────────┤
│  Layer 2: Split Evaluation (Feature Level)                  │
│  对每个候选分裂点，并行计算信息增益/基尼指数               │
├─────────────────────────────────────────────────────────────┤
│  Layer 1: Sample Streaming (Data Level)                     │
│  样本流式输入，HLS数据流流水线处理，II=1循环               │
└─────────────────────────────────────────────────────────────┘

关键洞察：并行性在"哪个维度切分"决定了不同的权衡。本模块选择 层内节点并行 + 特征分裂并行，而非样本并行，是因为：

  1. 样本并行需要同步梯度/统计信息，通信开销大
  2. 特征数量通常适中（数十到数百），可以并行评估
  3. 层内节点数随深度指数增长，后期有足够并行度

2.2 数据流隐喻：工厂流水线

想象本模块是一个高度自动化的工厂流水线，处理"样本数据包"：

工位1：原料卸货 (Scan)

  • AXI总线将原始数据从DDR搬运到片上
  • 数据按行存储，但流水线需要按列访问特征
  • axiVarColToStreams 完成行→列的转置，输出多个特征流

工位2：路径分拣 (FilterByPredict)

  • 每个样本需要确定它当前落在哪个节点
  • 从根节点开始，根据特征值和阈值判断左右分支
  • 这是一个小型状态机，更新 node_id 直到到达当前层目标节点

工位3：精细加工 (DispatchSplit)

  • 只选取当前节点需要评估的分裂特征
  • 从完整的特征流中提取特定列，打包成分裂候选流
  • 这一步是内存带宽优化的关键，避免传输无关特征

工位4：质量检验 (statisticAndCompute)

  • 对每个候选分裂，统计左右子树的类别分布
  • 计算基尼指数或信息增益，找出最佳分裂
  • 使用8项LRU缓存 (cache_nid_cid) 避免重复统计

工位5：产品入库 (updateTree + writeOut)

  • 根据最佳分裂更新树结构，创建子节点
  • 将完成的树序列化为512位AXI流，写回DDR
  • 后续推理可以直接加载这个紧凑表示

为什么用数据流而不是控制流？

HLS数据流(#pragma HLS dataflow)将上述工位映射为并行的硬件流水线阶段，每个阶段有独立的FIFO缓冲。这带来：

  • II=1循环：每个时钟周期处理一个新样本，理论吞吐量 = 时钟频率 × 数据宽度
  • 背压传播：下游工位满时自动阻塞上游，无需显式同步
  • 确定性延迟：没有缓存未命中或分支预测失败，延迟可精确计算

2.3 量化心智模型："比例尺地图"

想象量化过程是制作一张比例尺地图：

浮点世界（真实地形）：

  • 特征值可能是 3.1415926 或 -0.0001234
  • 阈值需要精确比较：if (feature < 0.5)
  • 动态范围极大：从 \(10^{-38}\) 到 \(10^{38}\)

量化地图（8位索引）：

  • 将连续值域划分为 numSplits 个离散桶（通常128个）
  • 每个桶用8位索引 0, 1, 2, ..., 127 表示
  • 实际阈值存储在独立的 splits_float 表中

为什么这种"地图"有效？

  1. 树模型对精度不敏感：决策树只关心 feature < threshold 的布尔结果，而非精确差值。8位量化足以保持99%+的分裂决策正确率。

  2. 局部性原理：相邻样本的特征值通常相近，落入相同或相邻桶。量化缓存友好，TLB未命中减少。

  3. 硬件友好：8位比较器比32位浮点比较器小10倍，时钟频率更高。可以在相同面积部署更多并行单元。

风险点：

  • 边界效应：恰好落在桶边界的阈值可能导致不同硬件/软件实现产生不同结果
  • 长尾分布：指数分布或幂律分布的特征，量化后可能丢失尾部细节
  • 累积误差：多轮迭代（如GBDT）中量化误差可能累积

2.4 节点结构："压缩档案袋"

每个 Node 结构是一个72+64位的压缩档案袋，装着决策所需的所有信息：\n\n\nnodeInfo (72 bits): 决策导航图\n├─ bit 0 : isLeaf — 是否是终点？\n├─ bits 1-15 : leafCat — 终点类别编号\n├─ bits 16-31 : featureId — 用哪个特征决策？\n└─ bits 32-71 : chl (child left) — 左孩子节点索引\n\nthreshold (64 bits): 决策标尺\n├─ bits 0-7 : quantizedSplit — 8位量化分裂点索引\n└─ bits 8-63 : (预留，可用于扩展精度)\n\n\n为什么这种"档案袋"设计？\n\n1. URAM对齐：72+64=136位接近URAM（UltraRAM）的144位端口宽度，几乎100%利用存储带宽，无浪费周期。\n\n2. 单周期决策：从读取节点到确定下一节点（左右孩子），所有信息在一个时钟周期内可用，流水线无气泡。\n\n3. 紧凑序列化：整棵树可以线性存储为 Node 数组，无需指针间接寻址，DMA传输高效，缓存未命中为零。\n\n4. 向后兼容：预留位域允许未来扩展（如支持回归的浮点阈值、多输出类别等），不破坏现有二进制格式。\n

On this page