Advances Edge Computing, LIMO Solves Large-Scale Traveling Salesman Problems with Reduced Memory Traffic

Combinatorial optimisation problems, crucial for fields ranging from logistics to electronic design, often demand immense computational resources, particularly when dealing with large datasets, as exemplified by the notorious Travelling Salesman Problem. Amod Holla, Sumedh Chatterjee, Sutanu Sen, and colleagues, from Purdue University, the Indian Institutes of Technology, and imec, present a novel solution in the form of LIMO, a low-power in-memory annealer and matrix-multiplication primitive designed for edge computing. This innovative macro achieves superior performance on complex optimisation tasks by performing computations directly within memory, reducing the energy-intensive data transfer typical of conventional systems. The team’s work significantly improves solution quality and speed for large-scale problems, demonstrated on instances with up to 85,900 cities, and importantly, extends beyond optimisation to efficiently support network inference tasks like image classification and face detection, offering a versatile and energy-efficient platform for a wide range of applications.

RRAM Crossbars Solve Quadratic Optimisation Problems

Scientists are exploring the use of Resistive Random Access Memory (RRAM) crossbars to solve complex combinatorial optimisation problems, such as the Quadratic Unconstrained Binary Optimisation (QUBO) problem, which is prevalent in fields like logistics and electronic design. Current digital solvers struggle with large-scale instances of these problems, motivating the investigation of nanoscale computing paradigms. This work demonstrates a fully integrated QUBO solver based on RRAM, and characterises its performance across various problem sizes and device characteristics. The team developed a programming methodology, termed ‘virtual common source’, which maps QUBO variables to RRAM devices and minimises the impact of device variation, leveraging the symmetry of the RRAM crossbar to improve solution accuracy.

They also implemented an error correction scheme to enhance robustness against device failures and non-idealities. The research includes the design and fabrication of a 1024-device RRAM crossbar, and demonstrates QUBO solving for problems with up to 16 variables. Results show that the ‘virtual common source’ methodology achieves a 30% improvement in solution quality, and the error correction scheme maintains over 95% accuracy even with up to 10% device failures. This work establishes RRAM crossbars as a promising platform for tackling complex optimisation problems, and paves the way for large-scale, energy-efficient QUBO solvers.

LIMO Accelerator For Traveling Salesperson Problem Solutions

Researchers have created LIMO, a custom-designed hardware accelerator for solving the Traveling Salesperson Problem (TSP). This hybrid analog/digital system uses spin-transfer-torque magnetic-tunnel-junctions (STT-MTJ) for random number generation and a CMOS-based processing core. The LIMO employs a combination of techniques, including segment refinement, 2-opt local search, and principal component analysis (PCA)-based clustering, to simplify the search space and improve solution quality. The system’s core innovation is the use of STT-MTJ devices for true random number generation, enabling stochastic optimisation techniques.

Detailed schematics and layouts of the STT-MTJ circuit demonstrate its high speed and low power consumption. The team conducted ablation studies, demonstrating that both 2-opt and segment refinement contribute to better solutions, with the impact varying depending on the problem instance. This work addresses the limitations of traditional computer architectures by implementing an in-memory annealing algorithm, leveraging spin-transfer-torque magnetic-tunnel-junctions (STT-MTJs) to efficiently explore the solution space and avoid becoming trapped in suboptimal solutions. Experiments demonstrate that LIMO, integrated into a spatial architecture, delivers superior solution quality and faster computation times for TSP instances with up to 85,900 cities, surpassing the capabilities of prior hardware annealers. The achievement relies on a reduced-complexity annealing process, aided by an algorithm incorporating weighted stochasticity and iterative insertion techniques. Furthermore, the modular design of LIMO allows it to be repurposed for other computational tasks, including vector-matrix multiplications, enabling support for network inference applications. The team integrated in-memory annealing with a divide-and-conquer algorithm, reducing the computational complexity of exploring vast solution spaces. This co-design approach, leveraging the stochastic switching of magnetic-tunnel-junctions, enables superior solution quality and faster processing times for large-scale instances, outperforming existing hardware annealers when tested on problems with up to 85,900 cities. Beyond optimisation, LIMO’s versatility extends to neural network applications, notably vector-matrix multiplications.

By eliminating the need for dedicated analog-to-digital converters and directly quantizing analog accumulation, the system achieves lower latency and energy consumption compared to conventional compute-in-memory designs while maintaining software-comparable accuracy in tasks like image classification and face detection. Hardware-aware training techniques address the reduced precision of analog accumulation in vector-matrix multiplication. Future work will focus on refining these training algorithms and exploring the application of LIMO to a broader range of computational challenges, capitalising on its modular and adaptable architecture.