Acelerando problemas híbridos de satisfatibilidade booleana XOR–CNF nativamente com computação in‑memory

Por que resolver problemas mais rápido importa

Muitas tarefas que moldam nossa vida cotidiana — desde proteger comunicações online até projetar eletrônicos mais rápidos — se reduzem a uma pergunta de sim-ou-não a um computador: existe uma combinação de chaves que faz essa grande regra lógica ser verdadeira? Esse é o problema de satisfatibilidade booleana, ou SAT. SAT é notoriamente difícil e, à medida que essas tarefas crescem em tamanho e importância, o tempo e a energia necessários para resolvê‑las tornam‑se um gargalo importante. Este artigo explora uma nova forma de turbinar a solução de SAT ao redesenhar tanto a matemática quanto o hardware para que funcionem juntos dentro de um tipo especial de chip de memória.

Transformando regras emaranhadas em blocos mais simples

Solvers SAT tradicionais geralmente descrevem problemas usando um estilo de regra lógica, construído a partir de condições “OU”. Mas muitos problemas industriais reais — como decodificação de sinais sem fio, testes de falhas em chips ou ataques a certos esquemas criptográficos — misturam naturalmente “OU” com “OU exclusivo” (XOR), um tipo de verificação de paridade que muda quando qualquer entrada individual se inverte. As ferramentas atuais frequentemente forçam essas regras XOR a serem reescritas usando apenas OU, o que aumenta o tamanho do problema e desacelera tudo. Os autores, em vez disso, mantêm ambos os tipos de regras, criando uma descrição híbrida que se aproxima mais de como os problemas surgem na prática.

Fazendo mais com menos peças

Os pesquisadores comparam cuidadosamente essa descrição híbrida com a tradicional em várias famílias de benchmarks tiradas da criptografia e de um problema clássico chamado paridade de desacordo mínimo. Ao reconstruir automaticamente estruturas XOR ocultas e aplicar simplificações inteligentes primeiro, eles mostram que a representação mista pode reduzir o número de variáveis em até várias vezes e cortar o número de cláusulas em aproximadamente um fator de quatro a cinco. Em outras palavras, a mesma questão lógica muitas vezes pode ser formulada com muito menos partes móveis quando se permite que XOR e OU coexistam. Problemas menores são mais fáceis não apenas para software, mas também para hardware especializado que tem limites rígidos sobre quantas cláusulas pode armazenar de uma vez.

Deixando os chips de memória fazerem o raciocínio

Para explorar essa descrição mais enxuta, a equipe projeta um acelerador dedicado de “computação in‑memory”. Em vez de trafegar dados entre um processador e a memória, esse dispositivo realiza grande parte do cálculo onde os dados residem, dentro de grades de pequenos elementos eletrônicos chamados memristores. Eles adaptam uma estratégia conhecida de busca local, WalkSAT, para uma nova variante chamada WalkSAT‑XNF que lida nativamente com as regras combinadas XOR–OU. Cada passo do algoritmo — verificar quais cláusulas estão violadas, estimar a influência de cada variável, adicionar um pouco de ruído para escapar de becos sem saída e inverter a melhor candidata — é implementado diretamente em circuitos analógicos nas matrizes crossbar, com circuitos auxiliares simples escolhendo qual variável inverter a seguir.

Comprovando que funciona no laboratório e em simulações

Os autores primeiro constroem um pequeno protótipo usando chips de memristor para demonstrar que o hardware analógico pode avaliar cláusulas fielmente e guiar a busca, mesmo na presença de variações de fabricação e ruído elétrico. Experimentos em uma instância de teste de tamanho modesto mostram que o comportamento do hardware coincide de perto com simulações ideais. Eles então modelam um projeto mais avançado em 28 nanômetros e o avaliam em famílias de problemas criptográficos e de paridade. Como a descrição híbrida embala mais informação em menos cláusulas, o acelerador necessita de muito menos memória no chip e consome muito menos energia por passo do que uma versão restrita a cláusulas só de OU. No geral, o solver híbrido in‑memory alcança cerca de um ganho de velocidade de dez vezes e uma melhoria na eficiência energética na ordem de mil vezes quando comparado a solvers SAT por software líderes rodando em CPUs convencionais.

O que isso significa para futuros computadores

Em termos simples, o trabalho mostra que podemos resolver certos problemas notoriamente difíceis de sim‑ou‑não muito mais rápido e com muito menos energia ao alinhar a forma como escrevemos as regras lógicas com a forma como um novo tipo de hardware baseado em memória computa. Ao suportar nativamente tanto regras XOR quanto OU dentro do chip, o acelerador proposto pode enfrentar tarefas realistas de criptografia, comunicações e projeto de circuitos usando hardware menor, mais frio e mais rápido. À medida que sistemas de computação pressionam cada vez mais contra limites de energia e velocidade, abordagens específicas por problema e in‑memory como essa podem ajudar a manter a infraestrutura digital crítica segura e eficiente.

Citação: 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

Palavras-chave: Satisfatibilidade booleana, computação in‑memory, crossbar de memristores, aceleradores de hardware, criptografia