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