Компактный цифровой вычислитель-память для имитационного отжига по Изингу с вероятностным битом SRAM в 28 нм для задачи Коммивояжера

Почему важны более умные маршруты и микросхемы

Каждый день грузовики, самолёты и сетевые пакеты должны выбирать маршрут так, чтобы всё прибыло вовремя и с минимальными затратами. Такая задача, известная как задача коммивояжера, быстро становится неразрешимой даже для мощных компьютеров по мере роста числа остановок. Работа, лежащая в основе этого обзора, предлагает новый тип специализированной микросхемы, который гораздо эффективнее решает подобные задачи планирования маршрутов, используя идеи, заимствованные у магнитных систем, и реализуя их напрямую в стандартной памяти компьютера.

Классическая задача — посетить каждую точку ровно один раз

Задача коммивояжера задаёт простой вопрос: имея список городов и расстояния между ними, какой коротчайший маршрут, который посетит каждый город ровно один раз и вернётся в исходную точку? Сложность в том, что число возможных туров взрывается с добавлением городов, поэтому проверить все варианты на практике невозможно. Современные подходы вместо этого ищут очень хорошие, если не идеальные, маршруты. Один перспективный метод имитирует поведение сети маленьких «магнитов», называемой моделью Изинга, которая стремится к низкоэнергетическому состоянию, соответствующему хорошему решению. Позволяя этой сети «колебаться» через случайные изменения с постепенным затуханием, система избегает плохих локальных решений и находит лучшие маршруты.

Преобразование микросхемы памяти в решатель задач

Вместо выполнения этого процесса на обычных процессорах авторы реализуют его прямо в аппаратуре памяти — стратегией, называемой вычислениями в памяти. Они проектируют компактную микросхему в 28-нанометровой технологии, где каждая ячейка памяти хранит как информацию о расстояниях, так и участвует напрямую в вычислениях. Умно, микросхема использует естественные производственные отклонения ячеек памяти как встроенный источник случайности, избавляя от необходимости в громоздких генераторах случайных чисел. Коротким контролируемым «толчком» напряжения она временно нарушает сохранённые значения — некоторые биты переворачиваются с некоторой вероятностью, обеспечивая лёгкую стохастичность, необходимую для процесса отжига, без дополнительной логики.

Разбиение больших карт на маленькие округа

Одна из главных проблем применения решателей в стиле Изинга к крупным задачам планирования маршрутов — объём данных: полное представление тура на 96 городов обычно требует огромной сети связей и памяти. Чтобы избежать этого, исследователи группируют близкие города в небольшие кластеры и располагают эти кластеры в несколько уровней иерархии. На верхнем уровне микросхема решает, в каком порядке располагать кластеры; на следующем уровне уточняется порядок городов внутри каждого кластера; и так далее. Поэтапный подход резко сокращает объём требуемой памяти и связей, уменьшая аппаратную сложность с роста пропорционально четвёртой степени числа городов до роста пропорционально квадрату, а затем дополнительно сжимая хранимые расстояния, упаковывая только действительно необходимые значения плотно друг к другу.

Как микросхема одновременно обновляет множество выборов

Внутри микросхемы группы по три города образуют базовые строительные блоки, обрабатываемые параллельно. Массив памяти организован так, что внутри каждого кластера схема может быстро вычислить изменение общей длины тура при перестановке его фрагментов. Поскольку некоторые кластеры не взаимодействуют напрямую, система может обновлять все «нечётные» кластеры за один шаг и все «чётные» — за следующий, ускоряя поиск, при этом поведение остаётся эквивалентным последовательным изменениям. В каждом раунде микросхема использует свои шумные ячейки памяти, чтобы с некоторой вероятностью принять ухудшающий ход — высокая вероятность в начале для исследования и более низкая позже для «остывания» — имитируя охлаждение металла и направляя маршрут к всё более коротким длинам.

От лабораторной микросхемы к маршрутам крупного масштаба

Прототип содержит скромные 6 килобит этой специальной памяти, но уже способен решать экземпляры задачи коммивояжера на 96 городов примерно за 620 микросекунд, потребляя при этом менее микроДж энергии. По сравнению с предыдущими аппаратными решениями для той же задачи он показывает улучшения вплоть до сотен раз по объёму памяти на единицу размера задачи. Моделирования также показывают, что при размещении множества таких блоков памяти бок о бок этот же дизайн может масштабироваться до задач с тысячами городов, при почти линейном росте аппаратуры. Для неспециалиста ключевая мысль такова: превращая знакомую микросхему памяти в активный решатель задач — и делая неизбежные производственные дефекты полезной функцией — эта работа указывает путь к небольшому, быстрому и энергоэффективному оборудованию, которое сможет в реальном времени помогать планировать сложные маршруты и расписания.

Цитирование: Kong, Y., Lu, A., Liu, H. et al. A compact digital compute-in-memory Ising annealer with probabilistic SRAM bit in 28 nm for travelling salesman problem. npj Unconv. Comput. 3, 15 (2026). https://doi.org/10.1038/s44335-026-00060-w

Ключевые слова: задача коммивояжера, отжиг по Изингу, вычисления в памяти, аппаратное обеспечение SRAM, комбинаторная оптимизация