面向自旋存内计算架构的图算法优化设计  

Graph Algorithm Optimization for Spintronics-based In-memory Computing Architecture

作　　者：王雪岩 陈序航 贾小涛 杨建磊 屈钢 赵巍胜 WANG Xueyan;CHEN Xuhang;JIA Xiaotao;YANG Jianlei;QU Gang;ZHAO Weisheng(School of Integrated Circuit Science and Engineering,Beihang University,Beijing 100191,China;School of Computer Science and Engineering,Beihang University,Beijing 100191,China;Department of Electrical and Computer Engineering,University of Maryland,College Park,Maryland 20742,USA)

机构地区：[1]北京航空航天大学集成电路科学与工程学院,北京100191 [2]北京航空航天大学计算机学院,北京100191 [3]马里兰大学帕克分校电子与计算机工程系,马里兰州20742

出　　处：《电子与信息学报》2023年第9期3193-3199,共7页Journal of Electronics & Information Technology

基　　金：国家自然科学基金(62004011,62006011,U20A20204,62072019)。

摘　　要：图计算广泛应用于社交网络分析、推荐系统等诸多关键领域,然而,传统的大规模图计算系统面临冯诺依曼架构下访存带来的性能瓶颈。新型存内计算架构成为加速大规模图计算非常有前景的方案,尤其是非易失自旋磁存储器(MRAM)具备超高耐擦写性和超快写入等优点,可使图计算的存内实现更为高效。实现这种潜力的关键挑战之一是如何优化存内计算架构下的图算法设计。该文的前期工作表明,三角形计数算法和图连通分量计算算法可以通过按位运算实现,从而高效地部署在自旋存内处理核中加速。该文探索了更多图算法的优化实现,例如单源最短路径、K-core、链路预测,并提出了面向新型存内计算架构的图算法优化设计模型。该研究对于突破冯诺依曼架构下大规模图计算的内存访问瓶颈具有关键意义。Graph computing has been widely applied to emerging fields such as social network analysis and recommendation systems.However,large-scale graph computing under the traditional Von-Neumann architecture faces the memory access bottleneck.The newly developed in-memory computing architecture becomes a promising alternative for accelerating graph computing.Due to its ultra-high endurance and ultra-fast writing speed,non-volatile Magnetoresistive Random Access Memory(MRAM)has the potential in building efficient in-memory accelerators.One of the key challenges to achieve such potential is how to optimize the graph algorithm design under the in-memory computing architecture.Our previous work shows that the triangle counting algorithms and graph connected component computing algorithms can be implemented with bitwise operations,which enables efficient spintronics in-memory computations.In this paper,the optimized implementation of more graph algorithms is explored such as single-source shortest path,K-core and link prediction,and an optimized design model of graph algorithms for the new in-memory computing architecture based is proposed.This research is of key significance for the breakthrough of solving the memory access bottleneck in large-scale graph computing under the Von Neumann architecture.

关 键 词：图计算 存内计算架构 位逻辑运算 自旋磁存储器 

分 类 号：TN402[电子电信—微电子学与固体电子学]