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

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

doi: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

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

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Scopus citations

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 language	English (US)
Title of host publication	2019 IEEE International Solid-State Circuits Conference, ISSCC 2019
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	50-52
Number of pages	3
ISBN (Electronic)	9781538685310
DOIs	https://doi.org/10.1109/ISSCC.2019.8662455
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

Publication series

Name	Digest of Technical Papers - IEEE International Solid-State Circuits Conference
Volume	2019-February
ISSN (Print)	0193-6530

Conference

Conference	2019 IEEE International Solid-State Circuits Conference, ISSCC 2019
Country/Territory	United States
City	San Francisco
Period	2/17/19 → 2/21/19

Bibliographical note

Funding Information:
This research was supported in part by the National Science Foundation under award number CCF-1763761.

Publisher Copyright:
© 2019 IEEE.

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Publisher link

10.1109/ISSCC.2019.8662455

Find It

Find It at U of M Libraries

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). Article 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 proceeding › Conference 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). doi: 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.}",

note = "Funding Information: This research was supported in part by the National Science Foundation under award number CCF-1763761. Publisher Copyright: {\textcopyright} 2019 IEEE.; 2019 IEEE International Solid-State Circuits Conference, ISSCC 2019 ; Conference date: 17-02-2019 Through 21-02-2019",

year = "2019",

month = mar,

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.

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

Y2 - 17 February 2019 through 21 February 2019

ER -

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

Abstract

Publication series

Conference

Bibliographical note

UN SDGs

Publisher link

Find It

Other files and links

Fingerprint

Cite this