Abstract
A mixed-signal, time-based 65-nm application-specific integrated circuit is developed for solving shortest-path problems. Digital circuits are collocated with the memory as intra-memory computing. The core follows similar principles from wave routing and, additionally, incorporates a gradient on the periphery of the core to implement the A∗ algorithm predicted distance heuristic. A leading pulse is propagated from start nodes and is asynchronously latched in neighboring vertex cells and pushed to its four neighbors. Applications include collision avoidance for self-driving cars, shortest path planning, and scientific computing, and are shown to be scalable across many cores. The chip achieves 559 million traversed edges per second at 105 \times improved energy efficiency compared with existing platforms such as field-programmable gate array and CPU. The processor operates nominally at 1.79 ns per node with peak power consumption of 26.4 mW.
| Original language | English (US) |
|---|---|
| Article number | 9333632 |
| Pages (from-to) | 2281-2290 |
| Number of pages | 10 |
| Journal | IEEE Journal of Solid-State Circuits |
| Volume | 56 |
| Issue number | 7 |
| DOIs | |
| State | Published - Jul 2021 |
Bibliographical note
Funding Information:Manuscript received July 26, 2020; revised October 8, 2020 and December 15, 2020; accepted December 28, 2020. Date of publication January 22, 2021; date of current version June 29, 2021. This article was approved by Associate Editor Edith Beigné. This work was supported by the National Science Foundation under Grant CCF-1763761. (Corresponding author: Chris H. Kim.) The authors are with the Electrical and Computer Engineering Department, University of Minnesota, Minneapolis, MN 55455 USA (e-mail: chriskim@umn.edu).
Publisher Copyright:
© 1966-2012 IEEE.
Keywords
- A
- algorithm
- graph computing
- graphs
- intra-memory computing
- single-source shortest path (SSSP)
- time-domain computing
- time-to-digital converter
