A 40×40 Four-Neighbor Time-Based In-Memory Computing Graph ASIC Chip Featuring Wavefront Expansion and 2D Gradient Control

📋 论文概要

该论文提出了一款基于时间域计算的内存计算图ASIC芯片，用于解决单源最短路径问题。通过波前扩展和二维梯度控制，实现了高效的四邻域图处理，克服了传统顺序遍历算法的速度瓶颈。

💡 主要创新点

• 采用时间域内存计算架构，将图处理映射到时间域，实现并行波前扩展。
• 引入二维梯度控制机制，优化路径搜索效率，减少冗余计算。
• 设计40×40四邻域处理单元阵列，支持大规模图问题的实时处理。

🏷 关键词

📄 原文摘要

Single-source shortest path (SSP) problems have a rich history of algorithm development [1-3]. SSP has many applications including AI decision making, robot navigation, VLSI signal routing, autonomous vehicles and many other classes of problems that can be mapped onto graphs. Conventional algorithms rely on sequentially traversing the search space, which is inherently limited by traditional computer architecture. In graphs which become very large, this slow processing time can become a bottleneck in real world applications. We propose a time-based ASIC to address this issue. Our design leverages a dedicated hardware implementation to solve these problems in linear time complexity with superior energy efficiency. A 40×40 four-neighbor grid implements a wavefront (WF) expansion with a first-in lockout mechanism to enable traceback. Outside the array, a programmable resistive ladder provides bias voltages to the edge

👥 作者与机构

Luke R. Everson, Sachin S. Sapatnekar, Chris H. Kim

University of Minnesota, Minneapolis, MN