Computação de recozimento resolve problemas insolúveis com computadores comuns

Com informações da Universidade de Ciências de Tóquio - 04/10/2022

Como os spins conseguem resolver um problema do mundo real implementando uma máquina de Ising.
[Imagem: Kaoru Yamamoto et al. - 10.1016/j.micpro.2022.104674]

Computação de recozimento

Você já se deparou com um problema em que teve que encontrar uma solução ideal entre muitas opções possíveis, como encontrar a rota mais rápida para um determinado local, considerando a distância e o tráfego?

Nesse caso, o problema com o qual você estava lidando é formalmente conhecido como "problema de otimização combinatória".

Esses problemas são comuns no mundo real e surgem em vários campos além da logística, incluindo roteamento de redes de computadores, aprendizado de máquina e ciência dos materiais.

A dificuldade é que problemas de otimização combinatória em larga escala são computacionalmente intensivos demais para serem resolvidos pelos computadores, fazendo com que os pesquisadores se voltem para abordagens alternativas.

Uma dessas abordagens é baseada no "modelo de Ising", que representa matematicamente a orientação magnética dos átomos, ou spins, em um material ferromagnético. A temperatura ambiente, esses spins atômicos apontam para direções aleatórias. Mas, à medida que a temperatura diminui, os spins começam a se alinhar em busca de um estado mínimo de energia, onde a orientação de cada spin depende da de seus vizinhos.

Não é um computador quântico de pleno direito, mas um simulador quântico. E esse princípio de funcionamento, conhecido como "recozimento quântico", pode ser usado para modelar problemas de otimização combinatória de modo que o estado final dos spins produza a solução ótima. O computador quântico D-Wave funciona usando esse princípio, bem como algumas arquiteturas alternativas de processadores ainda em escala de laboratório.

Mas o que os pesquisadores anseiam realmente é criar processadores de recozimento que imitem o comportamento dos spins usando chips semicondutores eletrônicos comuns, como a tecnologia LSI (integração em larga escala). Isso significa evitar mexer com os ainda complicados hardwares dos simuladores e computadores quânticos, o que é uma vantagem nada desprezível.

Implementação da computação de recozimento feita pela equipe, usando dois tipos de chips.
[Imagem: Kaoru Yamamoto et al. - 10.1016/j.micpro.2022.104674]

Processador de recozimento eletrônico

Foi o que fizeram Kaoru Yamamoto e Takayuki Kawahara, da Universidade de Ciências de Tóquio, que construíram um dos primeiros processadores de recozimento LSI totalmente acoplados (isto é, contabilizando todas as possíveis interações spin-spin, em vez de interações apenas com spins vizinhos), compreendendo 512 spins totalmente interconectados.

Mas surgiu um problema: O sistema mostrou-se notoriamente difícil de implementar e ampliar devido ao grande número de conexões entre os spins que precisam ser consideradas. Embora o uso de vários chips totalmente conectados em paralelo fosse uma solução potencial para o problema de escalabilidade, isso tornou o número necessário de interconexões (fios) entre os chips proibitivamente grande.

A dupla então idealizou e construiu uma solução inteligente para esse problema: Eles desenvolveram um novo método no qual o cálculo do estado de energia do sistema é primeiro subdividido entre vários chips totalmente acoplados, formando uma "calculadora matricial". Um segundo tipo de chip, chamado de chip de controle, coleta então os resultados das calculadoras matriciais e calcula a energia total, que é usada para atualizar os valores dos spins simulados.

"A vantagem da nossa abordagem é que a quantidade de dados transmitidos entre os chips é extremamente pequena," explica o professor Kawahara. "Embora seu princípio seja simples, este método nos permite concretizar um sistema LSI escalonável e totalmente conectado para resolver problemas de otimização combinatória por meio do recozimento simulado."

Protótipo do computador de recozimento construído pela equipe.
[Imagem: Kaoru Yamamoto et al. - 10.1016/j.micpro.2022.104674]

Velocidade e eficiência energética

Os pesquisadores implementaram sua abordagem usando chips FPGA comerciais, que são circuitos integrados programáveis depois de estarem prontos. Eles construíram um sistema de recozimento totalmente conectado com 384 spins e o utilizaram para resolver vários problemas de otimização, incluindo um problema de coloração de grafos de 92 nós e um problema de corte máximo de 384 nós.

Mais importante ainda, os testes de prova de conceito mostraram que o método traz benefícios reais de desempenho: Em comparação com uma CPU moderna rodando um programa que modela o mesmo sistema de recozimento, a implementação em FPGA foi 584 vezes mais rápida e consumiu 46 vezes menos energia ao resolver o problema de corte máximo.

Agora, com esta demonstração bem-sucedida do princípio de funcionamento do processador de recozimento em FPGA, os pesquisadores planejam levá-lo para o próximo nível.

"Desejamos produzir um chip LSI personalizado para aumentar a capacidade e melhorar muito o desempenho e a eficiência energética do nosso método," anunciou o professor Kawahara. "Isso nos permitirá obter o desempenho necessário nas áreas de desenvolvimento de materiais e descoberta de medicamentos, que envolvem problemas de otimização muito complexos."

Mais tópicos