Машина, которая не мешает сама себе экспресс
Оркестр, где каждый музыкант играет свою партию, но слышит только соседа. Стоит одному сбиться — волна ошибок катится по всему залу. Так работают машины Изинга — специальные устройства для решения задач, где нужно найти лучший вариант из множества. Их элементы-«спины» связаны между собой, и если обновлять их одновременно, они начинают мешать друг другу, как музыканты, вступившие не вовремя.
Обычно спины обновляют по очереди, но это медленно. Авторы статьи придумали добавить каждому спину немного инерции — как у маховика, который не даёт резко дёргаться. С инерцией спины перестают реагировать на каждый шорох соседей и могут обновляться все сразу, не портя общий результат. Проверили на задачах раскроя материала (Max-Cut) и модели стекла (Sherrington-Kirkpatrick), а также на детектировании сигналов в беспроводной связи.
Практическая польза видна в 5G: детектирование сигнала в реальном времени требует быстрых решений. Машина Изинга с инерцией уложилась в жёсткие требования по качеству и скорости, заняв при этом разумную площадь на кристалле. Оркестр, где все играют одновременно и слаженно, — вот что получилось.
Оригинальная аннотация
как её написали авторы, на английском arXiv:2604.17109
Ising machines -- special-purpose hardware for heuristically solving Ising optimization problems -- based on probabilistic bits (p-bits) have been established as a promising alternative to heuristic optimization algorithms run on conventional computers. However, it has -- until now -- been thought that Ising spins that are connected in probabilistic Ising machines cannot be updated in parallel without ruining the machine's solving ability. This has been a major challenge for using probabilistic Ising machines as fast solvers for densely connected problems. Here, we circumvent this by introducing a modified Ising spin dynamics with an added inertia term, and verify in algorithm simulations, FPGA hardware emulation, and FPGA experiments that it enables fully parallel, synchronous updates while improving rather than degrading success probability. We evaluated on various types of abstract (Max-Cut and Sherrington-Kirkpatrick-model) and application-derived (MIMO, wireless detection) dense Ising benchmark instances. Performing fully parallel updates results in a speed advantage that grows faster than linearly with the number of spins, giving rise to large time-to-solution increases for practical problem sizes. For both Max-Cut and the SK-1 model at a problem size of 200, our approach achieved an average speedup of $$\approx 35\times$$, with the best single-instance speedup reaching $$150\times$$. As an example of the practical utility of our approach in an application where speed is critical, we further show by co-designing the algorithm dynamics with the hardware implementation -- co-optimizing for solver ability and silicon resource usage -- that probabilistic Ising machines based on our approach satisfy the stringent solution quality and latency/throughput requirements for real-time MIMO detection in modern 5G cellular wireless networks while using a practically reasonable silicon area.
Модель Шеррингтона-Киркпатрика, на которой тестировали машину, описывает спиновое стекло — материал, где магнитные моменты заморожены в случайных направлениях, как люди, застрявшие в толпе и толкающие друг друга в разные стороны.