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^*

^*此作品的通信作者

研究成果: Conference contribution › 同行評審

7 引文斯高帕斯（Scopus）

摘要

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.

原文	English
主出版物標題	2021 IEEE International Electron Devices Meeting, IEDM 2021
發行者	Institute of Electrical and Electronics Engineers Inc.
頁面	21.3.1-21.3.4
ISBN（電子）	9781665425728
DOIs	https://doi.org/10.1109/IEDM19574.2021.9720619
出版狀態	Published - 2021
事件	2021 IEEE International Electron Devices Meeting, IEDM 2021 - San Francisco, 美國持續時間: 11 12月 2021 → 16 12月 2021

出版系列

名字	Technical Digest - International Electron Devices Meeting, IEDM
卷	2021-December
ISSN（列印）	0163-1918

Conference

Conference	2021 IEEE International Electron Devices Meeting, IEDM 2021
國家/地區	美國
城市	San Francisco
期間	11/12/21 → 16/12/21

UN SDG

此研究成果有助於以下永續發展目標

存取文件

10.1109/IEDM19574.2021.9720619

其它文件與鏈接

Link to publication in Scopus

引用此

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. 於 2021 IEEE International Electron Devices Meeting, IEDM 2021 (頁 21.3.1-21.3.4). (Technical Digest - International Electron Devices Meeting, IEDM; 卷 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 等. / 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. 頁 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. 於 2021 IEEE International Electron Devices Meeting, IEDM 2021. Technical Digest - International Electron Devices Meeting, IEDM, 卷 2021-December, Institute of Electrical and Electronics Engineers Inc., 頁 21.3.1-21.3.4, 2021 IEEE International Electron Devices Meeting, IEDM 2021, San Francisco, 美國, 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 等.
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; 卷 2021-December).

研究成果: Conference contribution › 同行評審

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 等. 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. 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

摘要

出版系列

Conference

UN SDG

存取文件

其它文件與鏈接

指紋

引用此