A Time-Based Intra-Memory Computing Graph Processor Featuring A∗ Wavefront Expansion and 2-D Gradient Control

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Article number9333632
Pages (from-to)2281-2290
Number of pages10
JournalIEEE Journal of Solid-State Circuits
Volume56
Issue number7
DOIs
StatePublished - Jul 1 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

Fingerprint

Dive into the research topics of 'A Time-Based Intra-Memory Computing Graph Processor Featuring A∗ Wavefront Expansion and 2-D Gradient Control'. Together they form a unique fingerprint.

Cite this