Ускорение гибридных задач булевой выполнимости XOR–CNF нативно с помощью вычислений в памяти

Почему важно быстрее решать такие задачи

Многие задачи, определяющие нашу повседневную жизнь — от защиты онлайн‑связи до разработки более быстрых электронных устройств — сводятся к одному двоичному вопросу: существует ли сочетание переключателей, при котором это большое логическое правило оказывается истинным? Это и есть задача булевой выполнимости, или SAT. SAT известно своей вычислительной сложностью, и по мере роста размера и значимости таких задач затраты времени и энергии на их решение становятся узким местом. В статье рассматривается новый способ ускорить SAT‑решение путём совместной переработки как математической модели, так и аппаратуры, чтобы они взаимодействовали внутри специального типа чипа памяти.

Преобразование запутанных правил в более простые блоки

Традиционные SAT‑решатели обычно описывают задачи в одной форме логических условий, построенных из операций «ИЛИ». Но многие реальные промышленные задачи — такие как декодирование беспроводных сигналов, тестирование микросхем на неисправности или атаки на определённые криптографические схемы — естественно сочетают «ИЛИ» с «исключающим ИЛИ» (XOR), видом проверки чётности, который меняет значение при изменении любого одного входа. Современные инструменты часто вынуждают переписывать XOR‑правила только через ИЛИ, что раздувает размер задачи и замедляет работу. Авторы сохраняют оба типа правил, создавая гибридное описание, которое ближе к тому, как эти задачи возникают на практике.

Делать больше с меньшим числом элементов

Исследователи внимательно сравнивают это гибридное описание с традиционным на нескольких наборах эталонных задач из области криптографии и классической задачи минимального несоответствия чётности. Автоматически восстанавливая скрытую XOR‑структуру и применяя умные упрощения на раннем этапе, они показывают, что смешанное представление может сократить число переменных в несколько раз и уменьшить количество правил примерно в 4–5 раз. Иначе говоря, один и тот же логический вопрос часто можно задать с гораздо меньшим количеством составляющих, если допустить сосуществование XOR и ИЛИ. Меньшие задачи проще не только для программного обеспечения, но и для специализированной аппаратуры, у которой строго ограничено, сколько правил она может хранить одновременно.

Дать чипам памяти возможность «думать»

Чтобы использовать это более компактное описание, команда разрабатывает специализированный ускоритель с вычислениями в памяти. Вместо постоянной пересылки данных между процессором и памятью устройство выполняет значительную часть вычислений там, где хранятся данные — внутри сетей крошечных электронных элементов, называемых мемристорами. Они адаптируют известную стратегию локального поиска WalkSAT в новый вариант WalkSAT‑XNF, который нативно обрабатывает комбинированные XOR–ИЛИ‑правила. Каждый шаг алгоритма — проверка нарушённых правил, оценка важности каждой переменной, внесение шума для выхода из тупиковых состояний и инвертирование выбранной переменной — реализуется непосредственно в аналоговой схемотехнике на кроссбар‑массивах, а простые вспомогательные цепи выбирают, какую переменную инвертировать далее.

Доказательства работоспособности в лаборатории и в моделях

Авторы сначала создают небольшой прототип на основе чипов с мемристорами, чтобы показать, что аналоговая аппаратура корректно оценивает дизъюнкции и направляет поиск, даже при наличии технологических вариаций и электрического шума. Эксперименты на умеренном по размеру тестовом примере показывают, что поведение аппаратуры близко к идеальным симуляциям. Затем они моделируют более продвинутый 28‑нанометровый дизайн и проводят бенчмарки на наборах криптографических и чётностных задач. Поскольку гибридное описание упаковывает больше информации в меньшее число дизъюнкций, ускорителю требуется значительно меньше он‑чип памяти и он потребляет гораздо меньше энергии на шаг по сравнению с версией, ограниченной только ИЛИ‑правилами. В целом гибридный in‑memory‑решатель достигает примерно десятикратного ускорения и примерно тысячекратного улучшения энергоэффективности по сравнению с передовыми программными SAT‑решателями, работающими на обычных CPU.

Что это значит для компьютеров будущего

Проще говоря, работа показывает, что определённые издавна трудные двоичные задачи можно решать гораздо быстрее и с меньшими затратами энергии, согласовав способ записи логических правил с тем, как новый класс аппаратуры на базе памяти выполняет вычисления. За счёт нативной поддержки и XOR, и ИЛИ внутри чипа предложенный ускоритель способен решать реалистичные задачи в криптографии, коммуникациях и проектировании схем с использованием более компактного, холодного и быстрого оборудования. По мере того как вычислительные системы всё чаще упираются в пределы энергии и скорости, такие предметно‑ориентированные in‑memory подходы могут помочь сохранять критическую цифровую инфраструктуру безопасной и эффективной.

Цитирование: Im, H., Böhm, F., Pedretti, G. et al. Accelerating hybrid XOR–CNF Boolean satisfiability problems natively with in-memory computing. Nat Commun 17, 2922 (2026). https://doi.org/10.1038/s41467-026-69465-2

Ключевые слова: Булева выполнимость, вычисления в памяти, мемристорная крест-решётка, аппаратные ускорители, криптография