Answers are grounded in this paper and cite their sources.
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 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 3 3, 8 1 0 and 8 5, 9 0 0 city TSPs, respectively. TAXI outperforms a current state-of-the-art clustering-based Ising solver, being 8 × faster on average across 20 benchmark problems from TSPLib.
No takes yet. Share an insight, caveat, or question.
Yoo et al. (2025) studied this question.