Um anelador Ising compacto de cómputo-na-memória digital com bit SRAM probabilístico em 28 nm para o problema do caixeiro-viajante

Por que rotas e chips mais inteligentes importam

Todos os dias, caminhões de entrega, aviões e pacotes de dados precisam escolher qual caminho seguir para que tudo chegue a tempo com custo mínimo. Esse tipo de quebra-cabeça, conhecido como Problema do Caixeiro-Viajante, rapidamente se torna intratável mesmo para computadores potentes à medida que o número de paradas cresce. O artigo por trás deste resumo apresenta um novo tipo de chip especializado que enfrenta problemas de planejamento de rotas com muito mais eficiência, usando ideias emprestadas de materiais magnéticos e incorporadas diretamente na memória padrão do computador.

Um quebra-cabeça clássico de visitar cada parada uma vez

O Problema do Caixeiro-Viajante faz uma pergunta simples: dado uma lista de cidades e as distâncias entre elas, qual é o passeio mais curto que visita cada cidade exatamente uma vez e retorna ao ponto de partida? O problema é que o número de passeios possíveis explode conforme se adicionam cidades, de modo que verificar todas as opções é inviável na prática. Em vez disso, abordagens modernas procuram rotas muito boas, se não perfeitas. Uma abordagem promissora imita como uma rede de pequenos ímãs, chamada modelo Ising, pode se estabilizar em um estado de baixa energia que representa uma boa solução. Ao permitir cuidadosamente que essa rede "oscile" por meio de mudanças aleatórias que gradualmente se acalmam, o sistema escapa de escolhas locais ruins e encontra rotas melhores.

Transformando um chip de memória em um resolvedor de problemas

Em vez de executar esse processo em processadores comuns, os autores o integram ao próprio hardware de memória, uma estratégia chamada cómputo-na-memória. Eles projetam um chip compacto em tecnologia de 28 nanômetros onde cada pequena célula de memória armazena tanto informação de distância quanto participa diretamente dos cálculos. De maneira inteligente, o chip usa as imperfeições naturais de fabricação de suas células de memória como uma fonte embutida de aleatoriedade, eliminando a necessidade de geradores de números aleatórios volumosos. Ao perturbar brevemente os valores armazenados com um "empurrão" de tensão controlado, alguns bits mudam de estado de forma probabilística, fornecendo a aleatoriedade suave necessária para o processo de annealing sem circuitos extras.

Dividindo grandes mapas em pequenas vizinhanças

Um dos principais obstáculos para usar solucionadores estilo Ising em grandes tarefas de planejamento de rotas é a enorme quantidade de dados necessária: uma representação completa de um passeio de 96 cidades normalmente exigiria uma vasta teia de conexões e memória. Para evitar isso, os pesquisadores agrupam cidades próximas em pequenos clusters e então organizam esses clusters em vários níveis hierárquicos. No nível mais alto, o chip resolve em que ordem os clusters devem aparecer; no nível seguinte, refina a ordem das cidades dentro de cada cluster; e assim por diante. Essa abordagem passo a passo reduz drasticamente a quantidade de memória e conexões necessárias, cortando a complexidade de hardware de algo que cresce com a quarta potência do número de cidades para algo que cresce apenas com o quadrado, e em seguida comprimindo ainda mais as distâncias armazenadas ao embalar apenas aquelas realmente necessárias de forma compacta.

Como o chip atualiza muitas escolhas ao mesmo tempo

No interior do chip, grupos de três cidades formam blocos básicos que são tratados em paralelo. A matriz de memória é organizada de modo que, dentro de cada cluster, o circuito possa calcular rapidamente a variação do comprimento total do passeio se trechos do percurso forem trocados. Como alguns clusters não interagem diretamente, o sistema pode atualizar todos os clusters "ímpares" em uma etapa e todos os "pares" na seguinte, acelerando a busca enquanto ainda se comporta como se as mudanças fossem feitas uma de cada vez. Durante cada rodada, o chip usa suas células de memória ruidosas para decidir se aceita um movimento pior com certa probabilidade — alta no início para explorar, e menor depois para se estabilizar — imitando o resfriamento de um metal e direcionando a rota para distâncias cada vez menores.

Do chip de laboratório para rotas em grande escala

O chip protótipo contém modestos 6 kilobits dessa memória especial, mas já consegue resolver instâncias de 96 cidades do Problema do Caixeiro-Viajante em cerca de 620 microssegundos enquanto consome menos de um microjoule de energia. Em comparação com hardware anterior projetado para a mesma tarefa, ele alcança melhorias de até centenas de vezes na quantidade de memória necessária por unidade de tamanho do problema. Simulações também mostram que, ao colocar muitos desses blocos de memória lado a lado, o mesmo projeto poderia escalar para problemas com milhares de cidades mantendo o crescimento do hardware quase linear. Para um leitor leigo, a conclusão-chave é que, ao transformar um chip de memória familiar em um resolvedor de problemas ativo — e ao converter as inevitáveis variações de fabricação em uma característica útil — este trabalho aponta para hardware pequeno, rápido e econômico em energia que pode ajudar a planejar rotas e horários complexos em tempo real.

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

Palavras-chave: problema do caixeiro-viajante, anelador Ising, cómputo-na-memória, hardware SRAM, otimização combinatória