SIMA:面向稀疏线性代数的可扩展基于暂存器的索引匹配硬件加速器

《ACM Transactions on Architecture and Code Optimization》:SIMA: Scalable Scratchpad-Based Index-Matching Hardware Accelerator for Sparse Linear Algebra

【字体: 大 中 小 】 时间:2026年09月26日 来源:ACM Transactions on Architecture and Code Optimization 2.9

编辑推荐:

   摘要AI 摘要摘要摘要稀疏线性代数核在图、机器学习和高性能计算等领域的应用中变得越来越重要。对于压缩稀疏数据表示,由于内存访问耗时,索引匹配在这些核函数中至关重要。利用该操作的并行性并非易事。支持基于向量处理单元或通用图形处理器架构的 SIMD/SIMT 通用加速器中的索引匹

  

摘要

摘要

稀疏线性代数核在图、机器学习和高性能计算等领域的应用中变得越来越重要。对于压缩稀疏数据表示,由于内存访问耗时,索引匹配在这些核函数中至关重要。利用该操作的并行性并非易事。支持基于向量处理单元或通用图形处理器架构的 SIMD/SIMT 通用加速器中的索引匹配的最先进硬件表现出有限的可扩展性。此外,替代的基于哈希的方法没有利用所有可用的并行性。
在本工作中,我们提出了 SIMA,一种用于 SIMD/SIMT 通用加速器中稀疏线性代数的可扩展的、基于暂存存储器的索引-匹配硬件加速器。SIMA 遵循基于哈希的索引匹配方法,提供了简单且可扩展的微架构,同时利用了索引和匹配并行性,这与最先进技术形成对比。SIMA 结合了多银行暂存存储器,以较小的面积和功耗开销利用索引并行性,并带有支持匹配并行性的缓存功能。此外,SIMA 还可以通过一种利用索引未命中的新机制来减轻索引冲突的影响。与最先进技术相比,SIMA 在面积和漏电功率上分别实现了至少 94.08% 和 72.65% 的节省。这些改进转化为跨不同评估组的实际矩阵和稀疏核函数的平均加速至少 1.97 倍,平均能效提高至少 6.91 倍。此外,与替代的基于哈希的方法相反,SIMA 可以利用所有可用的并行性,在计算大型矩阵的通用稀疏矩阵 - 稀疏矩阵乘法 (SpGEMM) 时优于所有评估的基线。此外,SIMA 通过容纳对硬件友好的哈希函数,减少索引冲突并提高内存利用率,改进了现有的基于哈希的提案。

AI 摘要

人工智能生成的摘要(实验性)

本摘要使用自动化工具生成,未经文章作者撰写或审阅。它旨在支持发现,帮助读者评估相关性,并协助相邻研究领域的读者理解该工作。旨在补充作者提供的摘要,后者仍然是论文的主要摘要。全文仍然是权威的记录版本。点击此处了解更多信息。

点击此处评论此摘要的准确性、清晰度和有用性。这样做将有助于改进和未来的重新生成版本。

人工智能生成的摘要

由自动系统根据已发表的文章文本生成。

版本创建日期:2026 年 9 月 23 日。

稀疏线性代数通过仅表示非零值来减少存储和计算,但压缩造成了不规则访问和元数据开销。交集和并集操作需要索引匹配来定位对应的值,此操作可能会主导如稀疏矩阵乘法等核函数的执行时间。SIMD 和 SIMT 加速器提供并行性,但硬件支持扩展性较差。基于复制和多端口的暂存存储器设计会产生面积和功耗成本。基于哈希的方法改进了可扩展性,但仅利用传入索引的并行处理或针对存储候选项的并行比较,而非两者兼有。当使用固定哈希函数时,它们可能会遭受冲突和桶不平衡的问题。

提出的架构是一种可扩展的多银行暂存存储器,将稀疏索引值对视为哈希索引存储。向量读操作返回匹配的值或未命中时的零,支持交集。向量写操作更新现有条目或插入新对,支持并集和累加。其接口暴露了跨向量通道的索引并行性和哈希桶内的匹配并行性。索引数据存储器实现为组相联缓存样结构,允许并行比较多个候选索引。银行仲裁器为冲突请求排队,同时设计可以作为没有稀疏数据的应用的暂存存储器运行。

该架构支持基于逻辑运算而非乘法的可编程硬件友好哈希函数。这些函数改进了银行和桶之间的分布,减少了冲突并防止过早溢出。如果桶满了,软件可以更改哈希函数或重新分区并重新运行计算。溢出恢复成本很低,因为失败被早期检测到。对于 64 位数据,复制的索引元数据可以利用未命中。未命中的请求可以返回零而不访问数据银行,允许请求继续并减少冲突延迟。

评估使用了 1201 个现实世界的矩阵和稀疏矩阵 - 向量、加法、乘法和矩阵 - 矩阵乘法核。256 千字节的设计将面积减少了 94.08%,漏电功率减少了 72.65%。性能提高了 1.97 倍,能效提高了 6.91 倍。它在大型稀疏矩阵 - 矩阵乘法方面优于替代方案。自定义哈希函数将最坏情况性能提高了 93.86%,并将利用率从 0.13 提高到 34.35%。基于未命中的冲突处理将读冲突开销减少了 38.52%,并将每指令周期从 1.81 降低到 1.56。总体而言,可扩展的银行、可配置的哈希、并行的桶匹配和溢出恢复为日益增长的稀疏工作负载提供了高效的索引匹配。

相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号