HitMatch（论文 2511.22460）工程化实现

该目录给出按论文 Algorithm 1 / Algorithm 2 对齐的实现：

1. CPU C++：离线索引构建 + 在线检索
2. CUDA：GPU 端并行累加（match_value + hit_count）
3. Ascend（CANN/ACL）：主机侧调度 + AscendC kernel 示例

深入源码级算法讲解请见：docs/hitmatch_algorithm_deep_dive.md

1. 当前实现状态（最新）

1. CPU 路径：已完成并验证可运行。
2. CUDA 路径：功能原型已实现，但当前代码仍由 CPU 先展开 posting，再拷到 GPU 计算；且本环境未安装 nvcc，未完成本地编译验证。
3. Ascend 路径：ACL + custom-op 对接骨架已实现；src/hitmatch_ascend.cpp 依赖外部 LaunchHitMatchScoreKernel，ascend/ 目录为示例内核与 launcher，不是开箱即用的完整 CANN 工程。
4. 结论：当前是“CPU 完整 + GPU/NPU 原型骨架”，不是 GPU/NPU 的最终生产版。

2. 论文数据结构（对齐 Algorithm 1）

核心不是“feature top-k ads 截断”，而是：

1. 构造 feature -> ad list 的倒排（稀疏矩阵 L 的 key-value 形式）。
2. 对每个 ad id 做 header=ad_id>>8、low8=ad_id&0xFF。
3. 形成 block：{header_high24, low8_list}。
4. 按 block 长度 n 分到组 g = ceil(log2(n))。
5. 每个 block pad 到 2^g。
6. 每组存成 SoA：keys/offsets + headers + values。

代码：include/hitmatch/hitmatch.hpp, src/hitmatch_cpu.cpp

2.1 论文中的 bias 对应关系

论文在 Section 3.3 的 Eq.(9) 里将最终分数写成“基线打分 + HitMatch 显式交互”之和；Figure 2 也体现为 main logit + IPNN logit + HitMatch logit 的合并。

本仓库将这部分“非 HitMatch 显式交互”的基线贡献工程化折叠为 bias：

1. 输入字段：SparseAdVector::bias（include/hitmatch/hitmatch.hpp）
2. 打分公式：score = alpha * match_value + beta * bias（src/hitmatch_cpu.cpp）

因此，这里的 bias 可以理解为 Eq.(9) 中基线项（例如 main/IPNN logit）的统一承载。

3. 离线索引构建

HitMatchIndex::Build（src/hitmatch_cpu.cpp）流程：

1. 遍历广告稀疏特征，生成 feature -> ad list。
2. 执行 low-8 bit block 压缩。
3. 按 ceil(log2(block_len)) 分组并做 power-of-two padding。
4. 写入 GroupSoA（组内按 feature 分段，block 结构按 SoA 存储）。

4. 在线检索

HitMatchIndex::Query（src/hitmatch_cpu.cpp）流程：

1. 输入 query 非零特征值（QueryFeature{feature_id, value}）。
2. 每组中查找 feature 段。
3. 解压 block，恢复 ad id：(header<<8)|low8。
4. 累加 match_value += query_value，并累计 hit_count。
5. 最终打分：score = alpha * match_value + beta * bias。
6. 输出全局 top-k。

5. 使用案例

示例：examples/demo.cpp

1. 5 条广告 + query {101,205,309}。
2. 输出字段：ad_id, hit_count, match_value, score。
3. 当前 CPU 本地实测输出：

CPU HitMatch top-3
ad_id=0, hit_count=3, match_value=3, score=3.06
ad_id=2, hit_count=2, match_value=2, score=2.11
ad_id=4, hit_count=2, match_value=2, score=2.025

6. 编译运行

CPU

cmake -S . -B build
cmake --build build -j
./build/hitmatch_demo

CUDA

cmake -S . -B build_cuda -DHITMATCH_ENABLE_CUDA=ON
cmake --build build_cuda -j
./build_cuda/hitmatch_demo

Ascend

export ASCEND_TOOLKIT_HOME=/usr/local/Ascend/ascend-toolkit/latest
cmake -S . -B build_ascend -DHITMATCH_ENABLE_ASCEND=ON
cmake --build build_ascend -j
./build_ascend/hitmatch_demo

7. Ascend 自定义算子源码

1. ascend/hitmatch_count_kernel.cpp：AscendC kernel（posting_ads + posting_weights -> match_values + hit_counts）。
2. ascend/hitmatch_count_kernel_host.cpp：Host launcher 示例。
3. src/hitmatch_ascend.cpp：ACL 主机检索流程。

说明：ascend/ 目录是示例代码，用于接入你自己的 CANN custom-op 工程。算子注册、构建脚本、版本适配需按本机 CANN 补齐。