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 cells, which enables pulse shaping reminiscent of the A∗ algorithm .
|Original language||English (US)|
|Title of host publication||2019 IEEE International Solid-State Circuits Conference, ISSCC 2019|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|Number of pages||3|
|State||Published - Mar 6 2019|
|Event||2019 IEEE International Solid-State Circuits Conference, ISSCC 2019 - San Francisco, United States|
Duration: Feb 17 2019 → Feb 21 2019
|Name||Digest of Technical Papers - IEEE International Solid-State Circuits Conference|
|Conference||2019 IEEE International Solid-State Circuits Conference, ISSCC 2019|
|Period||2/17/19 → 2/21/19|
Bibliographical noteFunding Information:
This research was supported in part by the National Science Foundation under award number CCF-1763761.