In-Memory Annealing Unit (IMAU): Energy-Efficient (2000 TOPS/W) Combinatorial Optimizer for Solving Travelling Salesman Problem

Ming Chun Hong; Le Chih Cho; Chih Sheng Lin; Yu Hui Lin; Po An Chen; I. Ting Wang; Pei Jer Tzeng; Shyh Shyuan Sheu; Wei Chung Lo; Chih I. Wu; Tuo Hung Hou

doi:10.1109/IEDM19574.2021.9720619

In-Memory Annealing Unit (IMAU): Energy-Efficient (2000 TOPS/W) Combinatorial Optimizer for Solving Travelling Salesman Problem

Ming Chun Hong, Le Chih Cho, Chih Sheng Lin, Yu Hui Lin, Po An Chen, I. Ting Wang, Pei Jer Tzeng, Shyh Shyuan Sheu, Wei Chung Lo, Chih I. Wu, Tuo Hung Hou^*

^*Corresponding author for this work

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

7 Scopus citations

Abstract

An in-memory annealing unit (IMAU) as an energy-efficient combinatorial optimizer for solving the travelling salesman problem (TSP) has been demonstrated for the first time. A hardware-algorithm co-optimization approach is adopted to overcome the challenges of solving TSP using IMAU, such as large problem size, insufficient weight precision, and inaccurate analog computing. The high-capacity (1152x1024) binary RRAM-based IMAU with an embedded simulated annealing (SA) function achieves an extremely high throughput of 90 TOPS and energy efficiency of 2000 TOPS/W. A new multi-step SA algorithm is proposed to solve the otherwise floating-point TSP using merely 5-level (2.3 bit) weights and achieves the floating point-equivalent shortest route for the 10-city TSP in IMAU.

Original language	English
Title of host publication	2021 IEEE International Electron Devices Meeting, IEDM 2021
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	21.3.1-21.3.4
ISBN (Electronic)	9781665425728
DOIs	https://doi.org/10.1109/IEDM19574.2021.9720619
State	Published - 2021
Event	2021 IEEE International Electron Devices Meeting, IEDM 2021 - San Francisco, United States Duration: 11 Dec 2021 → 16 Dec 2021

Publication series

Name	Technical Digest - International Electron Devices Meeting, IEDM
Volume	2021-December
ISSN (Print)	0163-1918

Conference

Conference	2021 IEEE International Electron Devices Meeting, IEDM 2021
Country/Territory	United States
City	San Francisco
Period	11/12/21 → 16/12/21

UN SDGs

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

Access to Document

10.1109/IEDM19574.2021.9720619

Cite this

Hong, M. C., Cho, L. C., Lin, C. S., Lin, Y. H., Chen, P. A., Wang, I. T., Tzeng, P. J., Sheu, S. S., Lo, W. C., Wu, C. I., & Hou, T. H. (2021). In-Memory Annealing Unit (IMAU): Energy-Efficient (2000 TOPS/W) Combinatorial Optimizer for Solving Travelling Salesman Problem. In 2021 IEEE International Electron Devices Meeting, IEDM 2021 (pp. 21.3.1-21.3.4). (Technical Digest - International Electron Devices Meeting, IEDM; Vol. 2021-December). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IEDM19574.2021.9720619

Hong, Ming Chun ; Cho, Le Chih ; Lin, Chih Sheng et al. / In-Memory Annealing Unit (IMAU) : Energy-Efficient (2000 TOPS/W) Combinatorial Optimizer for Solving Travelling Salesman Problem. 2021 IEEE International Electron Devices Meeting, IEDM 2021. Institute of Electrical and Electronics Engineers Inc., 2021. pp. 21.3.1-21.3.4 (Technical Digest - International Electron Devices Meeting, IEDM).

@inproceedings{2fbd1071624c422887d691677fb9df5c,

title = "In-Memory Annealing Unit (IMAU): Energy-Efficient (2000 TOPS/W) Combinatorial Optimizer for Solving Travelling Salesman Problem",

abstract = "An in-memory annealing unit (IMAU) as an energy-efficient combinatorial optimizer for solving the travelling salesman problem (TSP) has been demonstrated for the first time. A hardware-algorithm co-optimization approach is adopted to overcome the challenges of solving TSP using IMAU, such as large problem size, insufficient weight precision, and inaccurate analog computing. The high-capacity (1152x1024) binary RRAM-based IMAU with an embedded simulated annealing (SA) function achieves an extremely high throughput of 90 TOPS and energy efficiency of 2000 TOPS/W. A new multi-step SA algorithm is proposed to solve the otherwise floating-point TSP using merely 5-level (2.3 bit) weights and achieves the floating point-equivalent shortest route for the 10-city TSP in IMAU.",

author = "Hong, {Ming Chun} and Cho, {Le Chih} and Lin, {Chih Sheng} and Lin, {Yu Hui} and Chen, {Po An} and Wang, {I. Ting} and Tzeng, {Pei Jer} and Sheu, {Shyh Shyuan} and Lo, {Wei Chung} and Wu, {Chih I.} and Hou, {Tuo Hung}",

note = "Publisher Copyright: {\textcopyright} 2021 IEEE.; 2021 IEEE International Electron Devices Meeting, IEDM 2021 ; Conference date: 11-12-2021 Through 16-12-2021",

year = "2021",

doi = "10.1109/IEDM19574.2021.9720619",

language = "English",

series = "Technical Digest - International Electron Devices Meeting, IEDM",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "21.3.1--21.3.4",

booktitle = "2021 IEEE International Electron Devices Meeting, IEDM 2021",

address = "美國",

}

Hong, MC, Cho, LC, Lin, CS, Lin, YH, Chen, PA, Wang, IT, Tzeng, PJ, Sheu, SS, Lo, WC, Wu, CI & Hou, TH 2021, In-Memory Annealing Unit (IMAU): Energy-Efficient (2000 TOPS/W) Combinatorial Optimizer for Solving Travelling Salesman Problem. in 2021 IEEE International Electron Devices Meeting, IEDM 2021. Technical Digest - International Electron Devices Meeting, IEDM, vol. 2021-December, Institute of Electrical and Electronics Engineers Inc., pp. 21.3.1-21.3.4, 2021 IEEE International Electron Devices Meeting, IEDM 2021, San Francisco, United States, 11/12/21. https://doi.org/10.1109/IEDM19574.2021.9720619

In-Memory Annealing Unit (IMAU): Energy-Efficient (2000 TOPS/W) Combinatorial Optimizer for Solving Travelling Salesman Problem. / Hong, Ming Chun; Cho, Le Chih; Lin, Chih Sheng et al.
2021 IEEE International Electron Devices Meeting, IEDM 2021. Institute of Electrical and Electronics Engineers Inc., 2021. p. 21.3.1-21.3.4 (Technical Digest - International Electron Devices Meeting, IEDM; Vol. 2021-December).

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

TY - GEN

T1 - In-Memory Annealing Unit (IMAU)

T2 - 2021 IEEE International Electron Devices Meeting, IEDM 2021

AU - Hong, Ming Chun

AU - Cho, Le Chih

AU - Lin, Chih Sheng

AU - Lin, Yu Hui

AU - Chen, Po An

AU - Wang, I. Ting

AU - Tzeng, Pei Jer

AU - Sheu, Shyh Shyuan

AU - Lo, Wei Chung

AU - Wu, Chih I.

AU - Hou, Tuo Hung

PY - 2021

Y1 - 2021

N2 - An in-memory annealing unit (IMAU) as an energy-efficient combinatorial optimizer for solving the travelling salesman problem (TSP) has been demonstrated for the first time. A hardware-algorithm co-optimization approach is adopted to overcome the challenges of solving TSP using IMAU, such as large problem size, insufficient weight precision, and inaccurate analog computing. The high-capacity (1152x1024) binary RRAM-based IMAU with an embedded simulated annealing (SA) function achieves an extremely high throughput of 90 TOPS and energy efficiency of 2000 TOPS/W. A new multi-step SA algorithm is proposed to solve the otherwise floating-point TSP using merely 5-level (2.3 bit) weights and achieves the floating point-equivalent shortest route for the 10-city TSP in IMAU.

AB - An in-memory annealing unit (IMAU) as an energy-efficient combinatorial optimizer for solving the travelling salesman problem (TSP) has been demonstrated for the first time. A hardware-algorithm co-optimization approach is adopted to overcome the challenges of solving TSP using IMAU, such as large problem size, insufficient weight precision, and inaccurate analog computing. The high-capacity (1152x1024) binary RRAM-based IMAU with an embedded simulated annealing (SA) function achieves an extremely high throughput of 90 TOPS and energy efficiency of 2000 TOPS/W. A new multi-step SA algorithm is proposed to solve the otherwise floating-point TSP using merely 5-level (2.3 bit) weights and achieves the floating point-equivalent shortest route for the 10-city TSP in IMAU.

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

U2 - 10.1109/IEDM19574.2021.9720619

DO - 10.1109/IEDM19574.2021.9720619

M3 - Conference contribution

AN - SCOPUS:85126954323

T3 - Technical Digest - International Electron Devices Meeting, IEDM

SP - 21.3.1-21.3.4

BT - 2021 IEEE International Electron Devices Meeting, IEDM 2021

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 11 December 2021 through 16 December 2021

ER -

Hong MC, Cho LC, Lin CS, Lin YH, Chen PA, Wang IT et al. In-Memory Annealing Unit (IMAU): Energy-Efficient (2000 TOPS/W) Combinatorial Optimizer for Solving Travelling Salesman Problem. In 2021 IEEE International Electron Devices Meeting, IEDM 2021. Institute of Electrical and Electronics Engineers Inc. 2021. p. 21.3.1-21.3.4. (Technical Digest - International Electron Devices Meeting, IEDM). doi: 10.1109/IEDM19574.2021.9720619

In-Memory Annealing Unit (IMAU): Energy-Efficient (2000 TOPS/W) Combinatorial Optimizer for Solving Travelling Salesman Problem

Abstract

Publication series

Conference

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this