Shi Tuo, Gao Lili, Zhou Ruixi, Tian Yang, Chen Pei, Ding Yanting, Tang Shuangzhu, Ma Huiqin, Lu Jian, Zhang Hui, Wang Zhanfeng, Lyu Bo, Zhang Xumeng, Yan Xiaobing, Liu Qi
Zhejiang Laboratory, Hangzhou 311100, China.
State Key Laboratory of Integrated Chips and Systems, Frontier Institute of Chip and System, Fudan University, Shanghai 200433, China.
Sci Adv. 2025 May 9;11(19):eadv2312. doi: 10.1126/sciadv.adv2312. Epub 2025 May 7.
Parallel and energy-efficient searching of the shortest paths on a large graph is challenging. Conventional methods commonly used are sequential and computing intensive, rendering them inadequate for addressing large-scale and real-time situations. Here, we propose a highly parallel, computation- and energy-efficient approach to shortest path-based graph learning based on an emerging memristor spiking neural network via algorithm-device codesign. The shortest path is obtained parallelly in nature using simultaneous spike traveling instead of arithmetic calculation, achieving extremely low time and space complexity. A nonlinear weight mapping approach is proposed to counterbalance the neuron intrinsic nonlinearity to guarantee accuracy to support large-scale graphs. The memristor hardware capability is experimentally demonstrated in unsupervised and supervised classification tasks. The estimated energy efficiency of 517.82 giga-traversal edges per second per watt outperforms field programmable gate arrays by three to four orders of magnitude, providing a pathway toward highly energy-efficient graph computing hardware.
在大型图上并行且节能地搜索最短路径具有挑战性。常用的传统方法通常是顺序的且计算量大，这使得它们不足以应对大规模和实时情况。在此，我们基于新兴的忆阻器脉冲神经网络，通过算法 - 器件协同设计，提出一种高度并行、计算高效且节能的基于最短路径的图学习方法。最短路径本质上是通过同时的脉冲传播而非算术计算并行获得的，实现了极低的时间和空间复杂度。提出了一种非线性权重映射方法来平衡神经元固有的非线性，以保证准确性以支持大规模图。忆阻器硬件能力在无监督和有监督分类任务中得到了实验验证。估计的能效为每秒每瓦517.82千兆遍历边，比现场可编程门阵列性能优三到四个数量级，为实现高能效图计算硬件提供了一条途径。
