LIMO: низкопотребляющий ин-мемори отжигатель и примитив умножения матриц для периферийных вычислений

Умнее маршруты и экономичнее чипы

Каждый день компании сталкиваются с задачами вроде поиска кратчайшего маршрута для грузовика, посещающего тысячи остановок, или быстрой проверки изображений на предмет лиц с помощью работающей от батареи камеры. Эти задачи перегружают современные компьютеры, которые постоянно перемещают огромные объёмы данных между памятью и процессором. В статье представлен LIMO — новый тип энергоэффективного вычислительного блока, который сохраняет данные на месте при решении сложных задач планирования маршрутов и при выполнении моделей искусственного интеллекта (ИИ), благодаря чему будущие периферийные устройства станут быстрее и экономичнее по энергии.

Почему поиск хороших маршрутов такой тяжёлый

В основе этой работы лежит знаменитая задача коммивояжера: имея множество городов, найти самый короткий тур, посещающий каждый город ровно один раз и возвращающийся в начало. Для небольших карт точные математические методы могут найти оптимальное решение. Но по мере роста числа городов до десятков тысяч количество возможных туров взрывается, и даже мощные компьютеры буксуют. Эвристики, такие как имитация отжига, ищут в этом огромном пространстве хорошие, но не обязательно оптимальные, маршруты, иногда принимая худшие промежуточные варианты, чтобы не застрять в локальном минимуме. Тем не менее стандартные подходы по‑прежнему неэффективно исследуют пространство поиска для очень больших задач и теряют время на перемещения данных между памятью и CPU, сталкиваясь с так называемой «стеной памяти».

Новый способ исследовать варианты

Авторы предлагают новую алгоритмическую схему под названием Significance Weighted Annealed Insertion (SWAI), которая меняет подход к перебору кандидатных туров. Вместо постоянной перестановки пар городов, что плохо масштабируется с ростом числа городов, SWAI строит туры пошагово, вставляя по одному новому городу за раз. На каждом шаге алгоритм иногда выбирает ближайший следующий город (жадный выбор), а иногда опирается на контролируемую случайность, которая отдаёт предпочтение более коротким кандидатным рёбрам, но не исключает полностью более длинные. Эта склонность настраивается со временем: в начале поиск более рискованный, а по мере прогресса становится более консервативным. Поскольку на каждом шаге варианты рассматриваются так, что их число растёт только линейно с числом городов, алгоритм эффективнее находит дальние улучшения по сравнению с традиционной имитацией отжига.

Вычисления внутри памяти с встроенной случайностью

LIMO воплощает этот алгоритм в аппаратуре за счёт тесного совместного проектирования схемотехники и метода поиска. В основе — модифицированный массив памяти, который хранит как текущий тур, так и расстояния между городами, и выполняет ключевые шаги обновления без постоянной связи с отдельным процессором. Случайные выборы, требуемые алгоритмом, получают с помощью крошечных магнитных элементов — магнитно‑туннельных переходов с переносом спина (spin-transfer-torque MTJ), которые естественным образом меняют состояние непредсказуемым образом при подаче подходящего тока. Дизайнеры превращают эту физическую случайность в цифровые биты и используют простые сравнения для реализации вероятностных решений алгоритма. Поскольку большинство операций остаются цифровыми и происходят прямо в памяти, система избегает громоздких преобразователей и уязвимых аналоговых схем, экономя и энергию, и площадь кристалла.

Разбиение больших задач на части

Чтобы решать действительно крупные задачи планирования маршрутов — вплоть до 85 900 городов, система применяет стратегию «разделяй и властвуй». Лёгкий геометрический метод группирует близкие города в кластеры до тех пор, пока каждый кластер не станет достаточно мал, чтобы поместиться в один блок LIMO. Аппарат параллельно решает многие такие подмаршруты, а затем сшивает их в единый тур. Дополнительные шаги уточнения ещё больше улучшают глобальный маршрут: сегменты тура повторно оптимизируются самим оборудованием, а классическая «2-opt» доработка на обычном процессоре устраняет оставшиеся пересечения. В тестах на стандартных бенчмарках этот комбинированный подход дал более качественные туры, чем предыдущие специализированные машины отжига, достигая ответов примерно до пяти раз быстрее на самых больших задачах.

От сложных маршрутов к эффективному ИИ

LIMO не ограничивается планированием маршрутов. Тот же массив памяти может выступать строительным блоком для нейронных сетей, выполняя векторно‑матричные умножения — ключевую операцию для распознавания образов и паттернов. Вместо расходующих много энергии и требующих высокой точности преобразователей для чтения аналоговых сигналов LIMO опирается на очень простые схемы детектирования, фиксирующие только знак суммарного сигнала, и компенсирует эту грубость обучением сетей с учётом особенностей аппаратуры. В задачах классификации изображений и обнаружения лиц эти сети достигали точности, близкой к стандартным программным моделям, при этом снижая энергопотребление и время отклика по сравнению с привычными чипами compute‑in‑memory. Для обычных пользователей это означает, что камеры, дроны и другие периферийные устройства в будущем смогут решать сложные задачи планирования и запускать ИИ‑модели дольше от батареи — всё благодаря более умному поиску и вычислениям прямо там, где хранятся данные.

Цитирование: Holla, A., Chatterjee, S., Sen, S. et al. LIMO: Low-power in-memory-annealer and matrix-multiplication primitive for edge computing. npj Unconv. Comput. 3, 10 (2026). https://doi.org/10.1038/s44335-026-00054-8

Ключевые слова: вычисления в памяти, задача коммивояжера, аппаратный отжиг, энергоэффективный ИИ, периферийные вычисления