TAXI: Traveling Salesman Problem Accelerator with X-bar-based Ising Macros Powered by SOT-MRAMs and Hierarchical Clustering

Ising solvers with hierarchical clustering have shown promise for large-scale Traveling Salesman Problems (TSPs), in terms of latency and energy. However, most of these methods still face unacceptable quality degradation as the problem size increases beyond a certain extent. Additionally, their hardwareagnostic adoptions limit their ability to fully exploit available hardware resources. In this work, we introduce TAXI – an inmemory computing-based TSP accelerator with crossbar(Xbar)-based Ising macros. Each macro independently solves a TSP subproblem, obtained by hierarchical clustering, without the need for any off-macro data movement, leading to massive parallelism. Within the macro, Spin-Orbit-Torque (SOT) devices serve as compact energy-efficient random number generators enabling rapid “natural annealing”. By leveraging hardware-algorithm co-design, TAXI offers improvements in solution quality, speed, and energy-efficiency on TSPs up to $\mathbf{8 5, 9 0 0}$ cities (the largest TSPLIB instance). TAXI produces solutions that are only $22 \%$ and $20 \%$ longer than the Concorde solver’s exact solution on $\mathbf{3 3, 8 1 0}$ and $\mathbf{8 5, 9 0 0}$ city TSPs, respectively. TAXI outperforms a current state-of-the-art clustering-based Ising solver, being $8 \times$ faster on average across 20 benchmark problems from TSPLib.