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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 [3].

Original languageEnglish (US)
Title of host publication2019 IEEE International Solid-State Circuits Conference, ISSCC 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages50-52
Number of pages3
ISBN (Electronic)9781538685310
DOIs
StatePublished - Mar 6 2019
Event2019 IEEE International Solid-State Circuits Conference, ISSCC 2019 - San Francisco, United States
Duration: Feb 17 2019Feb 21 2019

Publication series

NameDigest of Technical Papers - IEEE International Solid-State Circuits Conference
Volume2019-February
ISSN (Print)0193-6530

Conference

Conference2019 IEEE International Solid-State Circuits Conference, ISSCC 2019
CountryUnited States
CitySan Francisco
Period2/17/192/21/19

Fingerprint

Wavefronts
Application specific integrated circuits
Data storage equipment
Pulse shaping
Computer architecture
Ladders
Bias voltage
Energy efficiency
Navigation
Decision making
Robots
Hardware
Processing

Cite this

Everson, L. R., Sapatnekar, S. S., & Kim, C. H. (2019). 2.5 A 40×40 Four-Neighbor Time-Based In-Memory Computing Graph ASIC Chip Featuring Wavefront Expansion and 2D Gradient Control. In 2019 IEEE International Solid-State Circuits Conference, ISSCC 2019 (pp. 50-52). [8662455] (Digest of Technical Papers - IEEE International Solid-State Circuits Conference; Vol. 2019-February). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISSCC.2019.8662455

2.5 A 40×40 Four-Neighbor Time-Based In-Memory Computing Graph ASIC Chip Featuring Wavefront Expansion and 2D Gradient Control. / Everson, Luke R.; Sapatnekar, Sachin S; Kim, Chris H.

2019 IEEE International Solid-State Circuits Conference, ISSCC 2019. Institute of Electrical and Electronics Engineers Inc., 2019. p. 50-52 8662455 (Digest of Technical Papers - IEEE International Solid-State Circuits Conference; Vol. 2019-February).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Everson, LR, Sapatnekar, SS & Kim, CH 2019, 2.5 A 40×40 Four-Neighbor Time-Based In-Memory Computing Graph ASIC Chip Featuring Wavefront Expansion and 2D Gradient Control. in 2019 IEEE International Solid-State Circuits Conference, ISSCC 2019., 8662455, Digest of Technical Papers - IEEE International Solid-State Circuits Conference, vol. 2019-February, Institute of Electrical and Electronics Engineers Inc., pp. 50-52, 2019 IEEE International Solid-State Circuits Conference, ISSCC 2019, San Francisco, United States, 2/17/19. https://doi.org/10.1109/ISSCC.2019.8662455
Everson LR, Sapatnekar SS, Kim CH. 2.5 A 40×40 Four-Neighbor Time-Based In-Memory Computing Graph ASIC Chip Featuring Wavefront Expansion and 2D Gradient Control. In 2019 IEEE International Solid-State Circuits Conference, ISSCC 2019. Institute of Electrical and Electronics Engineers Inc. 2019. p. 50-52. 8662455. (Digest of Technical Papers - IEEE International Solid-State Circuits Conference). https://doi.org/10.1109/ISSCC.2019.8662455
Everson, Luke R. ; Sapatnekar, Sachin S ; Kim, Chris H. / 2.5 A 40×40 Four-Neighbor Time-Based In-Memory Computing Graph ASIC Chip Featuring Wavefront Expansion and 2D Gradient Control. 2019 IEEE International Solid-State Circuits Conference, ISSCC 2019. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 50-52 (Digest of Technical Papers - IEEE International Solid-State Circuits Conference).
@inproceedings{1b076b116f0842c2b09747a1fe8cde1a,
title = "2.5 A 40×40 Four-Neighbor Time-Based In-Memory Computing Graph ASIC Chip Featuring Wavefront Expansion and 2D Gradient Control",
abstract = "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 [3].",
author = "Everson, {Luke R.} and Sapatnekar, {Sachin S} and Kim, {Chris H.}",
year = "2019",
month = "3",
day = "6",
doi = "10.1109/ISSCC.2019.8662455",
language = "English (US)",
series = "Digest of Technical Papers - IEEE International Solid-State Circuits Conference",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "50--52",
booktitle = "2019 IEEE International Solid-State Circuits Conference, ISSCC 2019",

}

TY - GEN

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

AU - Everson, Luke R.

AU - Sapatnekar, Sachin S

AU - Kim, Chris H.

PY - 2019/3/6

Y1 - 2019/3/6

N2 - 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 [3].

AB - 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 [3].

UR - http://www.scopus.com/inward/record.url?scp=85063537898&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85063537898&partnerID=8YFLogxK

U2 - 10.1109/ISSCC.2019.8662455

DO - 10.1109/ISSCC.2019.8662455

M3 - Conference contribution

AN - SCOPUS:85063537898

T3 - Digest of Technical Papers - IEEE International Solid-State Circuits Conference

SP - 50

EP - 52

BT - 2019 IEEE International Solid-State Circuits Conference, ISSCC 2019

PB - Institute of Electrical and Electronics Engineers Inc.

ER -