锁无关桶式布谷鸟哈希与BitHist：高效计算的新突破

# 锁无关桶式布谷鸟哈希与BitHist：高效计算的新突破 ## 锁无关桶式布谷鸟哈希（LFBCH） ### 现有方法的局限性 在并发访问桶式布谷鸟哈希的相关研究中，多种方法各有优劣。 - **Memc3**：允许多个读者和单个写者同时访问桶式布谷鸟哈希，但功能相对单一。 - **Xiaozhou Li的工作**：将事务性内存（HTM）引入桶式布谷鸟哈希，不过HTM存在固有局限性，当事务频繁失败时，会导致显著的性能下降。 - **libcuckoo**：采用桶式结构并使用细粒度锁来控制并发访问，然而随着线程数量增加，竞争导致的性能下降不可避免。 - **Lfcuckoo**：对原始布谷鸟哈希进行了无锁改进，但未扩展到桶式布谷鸟哈希，空间利用效率较低。 - **Level hash**：在桶式布谷鸟哈希中采用了无锁技术，但其设计是针对持久内存场景的。 ### LFBCH的提出与优势 为了解决上述问题，研究人员引入无锁技术到桶式布谷鸟哈希中，提出了LFBCH。 - **无锁操作**：LFBCH保证所有操作都是无锁的，避免了诸如误判和重复键等常见问题。 - **锁无关的重新哈希和热点调整**：实现了锁无关的重新哈希和热点调整功能，灵感来源于hotring，通过将链表头指针指向热点键，在数据倾斜的情况下提高了链式哈希表的性能。 - **高吞吐量**：与其他流行的并发哈希表相比，LFBCH的吞吐量提高了14% - 360%。 ### 性能优化展望 当工作线程分布在不同CPU插槽时，访问相同的共享数据结构会引入额外的延迟。未来可以针对LFBCH在跨CPU插槽场景下进行优化，以进一步提高其性能。 ## BitHist：精确可扩展的稀疏感知DNN加速器 ### CNN模型部署面临的挑战 卷积神经网络（CNN）模型在计算机视觉、自主决策和自然语言处理等领域取得了优异的性能。然而，由于其大量的参数和密集的计算，在边缘设备上的部署受到了有限存储容量和计算资源的限制。为了减轻边缘设备的计算和存储负担，常用的压缩技术包括低秩压缩、知识蒸馏、剪枝和量化等。 ### 量化与多精度加速器 量化可以通过将权重或激活值降低到16位甚至1位，在不显著降低模型精度的情况下，减少片外数据访问和功耗。目前已经有许多CNN加速器可以支持量化网络的部署，但大多数只支持一种量化数据精度，无法充分发挥量化模型的潜力。因此，一些研究致力于开发多精度加速器，以兼容CNN模型中不同数据位宽的计算。 ### 精度可扩展的MAC单元 CNN的主要计算模式是乘加（MAC）计算，因此加速器计算混合精度模型的能力取决于精度可扩展的MAC单元。常见的精度可扩展MAC单元设计有以下三种： |类型|特点|缺点| | ---- | ---- | ---- | |传统精度可扩展MAC|通过门控计算单元来计算低位宽数据的乘法|面积利用率低，存在许多空闲门| |时间精度可扩展MAC（TPM）|为乘数生成并临时累积多个部分积|在对称精度情况下，处理时间随位宽呈二次增长| |空间精度可扩展MAC（SPM）|如BitFusion，可将高比特位宽MAC中的子单元阵列重新组合为多个低精度乘法器，将数据精度的降低转化为吞吐量和能源效率的提高|随着位宽增加，需要更多的移位器和高位宽加法器，导致能源效率降低| ### BitHist的创新点 为了克服上述MAC架构的缺点，研究人员提出了一种基于唯一产品直方图的新MAC方法，并在此基础上设计了BitHist加速器。 - **基于直方图的位宽可扩展MAC方法**：利用SPM方法中2位无符号乘法有限的唯一产品（UPs），避免了SPM方法中许多冗余的2位乘法，节省了一半的面积。 - **同时利用位级和数据级稀疏性**：采用的编码方式避免了潜在的零值切片积，通过标志蒸馏处理引入的标志稀疏性，进一步提高