Solucionador matemático impulsiona computadores analógicos

Com informações da Universidade de Notre Dame - 03/01/2019

Existem problemas tipicamente intratáveis pela computação digital - esta ilustração mostra o "problema da festa", ou número de Ramsey R (m, n), que tenta determinar o número mínimo de convidados que devem ser chamados para uma festa para que pelo menos m se conheçam, ou pelo menos n não se conheçam.
[Imagem: Botond Molnár et al. - 10.1038/s41467-018-07327-2]

Computação digital versus computação analógica

Seu computador executa bem a maioria das tarefas - para processamento de texto, certos cálculos, artes gráficas e navegação na web, ele é a melhor ferramenta de trabalho de que você pode dispor na atualidade.

Mas a forma como os computadores digitais funcionam, com o seu estilo de matemática baseado no sistema de código binário - 0s e 1s, ou o "ligado" e "desligado" dos transistores - está longe de ser a ideal para resolver todos os tipos de problemas.

É por isso que várias equipes em todo o mundo estão trabalhando para revitalizar a computação analógica.

Além de haver sinais de que a computação digital atingiu ou está muito próxima do seu potencial máximo, chips analógicos gastam 1.000 vezes menos energia, estão mais próximos de imitar a forma de funcionamento do cérebro e prometem defender a inteligência artificial contra os hackers - há até quem defenda que inteligência artificial prá valer vai exigir um hardware analógico.

Em mais um impulso na área, Botond Molnár e seus colegas da Universidade de Notre Dame, nos EUA, acabam de desenvolver uma nova abordagem matemática que ajudará a avançar a computação para além da estrutura digital, eventualmente viabilizando um processador analógico.

Problemas NP

O avanço está em um novo "solucionador analógico", que pode potencialmente encontrar a melhor solução para alguns dos problemas mais difíceis da computação, os chamados problemas NP - na teoria da complexidade computacional, NP é o acrônimo em inglês para "tempo polinomial não-determinístico" (Non-Deterministic Polynomial Time).

Problemas associados com dobramento de proteínas, bioinformática, tratamento de imagens médicas, agendamentos e muitas outras áreas são quase insolúveis pelos métodos computacionais conhecidos porque lidam com um número grande demais de variáveis - quando esse número é grande o suficiente, esses problemas são conhecidos como NP-Complexos, ou NP-Difíceis.

Depois de testar seu novo método em uma variedade de problemas NP-Difíceis, os pesquisadores concluíram que seu solucionador analógico tem potencial para chegar a soluções melhores e possivelmente mais rápidas do que as que podem ser calculadas digitalmente, mesmo pelos mais poderosos supercomputadores.

Computadores analógicos

Computadores analógicos foram usados para prever marés desde o início até meados do século 20, guiar armas em navios de guerra e lançar os primeiros foguetes da NASA ao espaço. Eles primeiro usaram engrenagens, depois válvulas e mesmo as primeiras versões dos transistores. Esses computadores executavam funções matemáticas diretamente: Por exemplo, para adicionar 5 e 9, os processadores analógicos adicionam tensões elétricas que correspondem a esses números e, em seguida, obtêm instantaneamente a resposta correta medindo a tensão resultante.

Para vencer os inconvenientes dos computadores digitais, há grande confiança nos chamados processadores imprecisos e nos computadores neuromórficos, que tenta imitar o cérebro.
[Imagem: Stanford University]

Como eram grandes e muito afetados por interferências, os computadores analógicos logo foram substituídos pelos menores e mais confiáveis computadores digitais, com seus transistores e circuitos integrados rapidamente miniaturizados. Como todo o seu funcionamento é restrito ao uso de 0s e 1s, sua programação também é muito mais simples, o que ajuda a explicar porque a computação digital é dominante há quase 70 anos.

Mas toda a família de problemas tipo NP com muitas variáveis não apenas continua por aí, como só fez crescer. Basta lembrar do "problema do caixeiro-viajante", em que um vendedor deve começar em uma cidade e retornar a essa cidade depois de viajar para todas as diferentes cidades em uma lista: Qual é o caminho mais eficiente entre todos os pontos? O problema se torna exponencialmente mais difícil conforme cada cidade é adicionada à lista.

"Embora você possa sempre encontrar alguma resposta, você não pode determinar se ela é a ideal. Determinar que não há uma solução melhor é tão difícil quanto o problema em si," explica o professor Zoltán Toroczkai, coordenador da equipe, referindo-se a toda essa classe de problemas de agendamento e otimização.

Algoritmos analógicos

O grande problema para a computação analógica está no desenvolvimento de algoritmos contínuos. Ao contrário da computação digital, que tem uma longa história no desenvolvimento de algoritmos, os algoritmos para computadores analógicos não possuem uma base de conhecimento semelhante, sendo tipicamente muito difíceis de projetar.

É aí que entra o "solucionador analógico" que a equipe acaba de desenvolver, uma solução que é diferente dos algoritmos para computadores digitais em todos os aspectos.

"A ideia baseia-se na observação de que o CTDS [sistema determinístico de tempo contínuo] não faz suposições sobre a satisfabilidade do problema e, portanto, mesmo para problemas SAT [problemas de satisfabilidade] insatisfeitos, a dinâmica ainda minimizará o número de cláusulas insatisfeitas. O que precisamos determinar, no entanto, é a probabilidade da otimização da melhor solução encontrada pelo tempo analógico t, como função de t, o que obtivemos heuristicamente analisando a estatística de uma invariante dinâmica, a taxa de escape," descreveu a equipe, acrescentando que a taxa de escape é uma medida invariante da dinâmica introduzida para caracterizar sistemas transitoriamente caóticos.

Matematicamente tudo funcionou. O próximo passo será projetar e construir hardwares baseados nessa abordagem para rodar o software analógico. Um inconveniente é que esses computadores analógicos terão que ser construídos para tarefas específicas - cada um vai resolver um tipo específico de problema. As vantagens incluem solucionar problemas hoje insolúveis, fazendo isso com uma eficiência imbatível, sendo muito mais rápidos e consumindo menos energia do que os supercomputadores digitais.

"Há principalmente problemas de engenharia que precisam ser resolvidos neste momento, como capacidades espúrias e melhor controle de ruído, mas vamos chegar lá," disse Toroczkai. "Idealmente, eu gostaria de ver você dispondo de uma máquina dessas em sua mesa funcionando como seu agendador. E ele vai fazer um trabalho muito melhor do que o seu computador normal."

• Criado primeiro compilador para computadores analógicos

Mais tópicos