Qualquer um que tenha feito um curso básico de ciência da computação sem dúvida gastou tempo projetando um algoritmo de classificação, um código que pegará uma lista não ordenada de itens e os colocará em ordem crescente ou decrescente. É um desafio interessante porque existem muitas maneiras de fazer isso e porque as pessoas passaram muito tempo tentando descobrir como fazer essa classificação da maneira mais eficiente possível.

A classificação é tão básica que os algoritmos são incorporados na maioria das bibliotecas padrão para linguagens de programação. E, no caso da biblioteca C++ usada com o compilador LLVM, o código não é tocado há mais de uma década.

Mas o grupo DeepMind AI do Google agora desenvolveu uma ferramenta de aprendizado por reforço que pode desenvolver algoritmos extremamente otimizados sem primeiro ser treinado em exemplos de código humano. O truque era configurá-lo para tratar a programação como um jogo.

é tudo um jogo

O DeepMind, entre outras coisas, se destaca por ter desenvolvido um software que ensina sozinho a jogar. Essa abordagem provou ser altamente eficaz, conquistando jogos tão variados como xadrez, Ire barco estrela. Embora os detalhes variem dependendo do jogo que você está jogando, o software aprende jogando sozinho e descobre opções que permitem maximizar sua pontuação.

Por não ser treinado em jogos que os humanos jogam, o sistema DeepMind pode descobrir abordagens para jogos que os humanos nunca imaginaram. Claro, como ele está sempre jogando contra si mesmo, há casos em que ele desenvolveu pontos cegos que os humanos podem explorar.

Esta abordagem é muito relevante para a programação. Grandes modelos de linguagem escrevem códigos eficazes porque viram muitos exemplos humanos. Mas por causa disso, é improvável que desenvolvam algo que os humanos não tenham feito antes. Se estivermos procurando otimizar algoritmos bem compreendidos, como funções de classificação, basear algo no código humano existente é, na melhor das hipóteses, obter desempenho equivalente. Mas como você consegue que uma IA identifique um foco verdadeiramente novo?

O pessoal da DeepMind adotou a mesma abordagem que tiveram com o xadrez e Ir: Eles transformaram a otimização de código em um jogo. O sistema AlphaDev desenvolveu algoritmos de montagem x86 que tratavam a latência do código como uma pontuação e tentavam minimizar essa pontuação, garantindo que o código fosse executado sem erros até a conclusão. Por meio do aprendizado por reforço, o AlphaDev desenvolve gradualmente a capacidade de escrever código enxuto e altamente eficiente.

Dentro do AlphaDev

Dizer que o sistema é otimizado para latência é muito diferente de explicar como ele funciona. Como a maioria dos outros sistemas complexos de IA, o AlphaDev consiste em vários componentes diferentes. Uma delas é uma função de renderização, que acompanha o desempenho geral do seu código à medida que ele é desenvolvido. Isso inclui a estrutura geral do algoritmo, bem como o uso de registradores e memória x86.

O sistema adiciona instruções de montagem individualmente, escolhidas por um Pesquisa de árvores de Monte Carlo—novamente, uma abordagem retirada dos sistemas de jogo. O aspecto de “árvore” dessa abordagem permite que o sistema seja rapidamente reduzido a uma área limitada da ampla gama de instruções potenciais, enquanto Monte Carlo adiciona um grau de aleatoriedade à instrução precisa que é escolhida desse ramo. (Observe que “declaração” neste contexto inclui coisas como os registros específicos escolhidos para criar um conjunto válido e completo.)

O sistema então avalia o estado do código assembler em termos de latência e validade, e atribui a ele uma pontuação, comparando-a com a pontuação do anterior. E, por meio do aprendizado por reforço, ele retém informações sobre como os diferentes ramos da árvore funcionam, dado o estado do programa. Com o tempo, ele “aprende” como atingir um estado de jogo vencedor (uma classificação completa) com pontuação máxima, o que significa latência mínima.

O principal benefício desse sistema é que seu treinamento não precisa envolver nenhum exemplo de código. Em vez disso, o sistema gera seus próprios exemplos de código e os avalia. No processo, ele se apega a informações sobre combinações de instruções que são eficazes na classificação.

código útil

A classificação em programas complexos pode lidar com grandes e arbitrárias coleções de elementos. Mas no nível da biblioteca padrão, ele é construído a partir de uma grande coleção de funções altamente específicas que lidam com apenas uma ou algumas situações. Por exemplo, existem algoritmos separados para classificar três itens, quatro itens e cinco itens. E há outro conjunto de funções que pode lidar com um número arbitrário de itens até um limite, o que significa que você pode chamar uma que classifique até quatro itens, mas não mais.

O DeepMind configurou o AlphaDev em cada uma dessas funções, mas elas funcionam de maneira muito diferente. Para funções que lidam com um número específico de elementos, é possível escrever código sem ramificações onde executa código diferente com base no estado de uma variável. Como resultado, o desempenho desse código geralmente aumenta com o número de instruções necessárias. AlphaDev foi capaz de remover uma instrução de sort-3, sort-5 e sort-8, e ainda mais de sort-6 e sort-7. Houve apenas um (sort-4) onde não encontrou uma maneira de melhorar o código humano. Execuções repetidas do código em sistemas reais mostraram que menos instruções levaram a um melhor desempenho.

Classificar um número variável de entradas envolve ramificar o código, e diferentes processadores têm diferentes quantidades de hardware dedicado a lidar com essas ramificações. Portanto, para estes, o código foi testado com base em seu desempenho em 100 máquinas diferentes. Mais uma vez, o AlphaDev encontrou maneiras de obter um desempenho extra, e veremos como eles fizeram isso em uma situação: uma função que classifica até quatro itens.

Na implementação existente na biblioteca C++, o código executa uma série de testes para ver quantos itens precisa classificar e chama a função de classificação dedicada para esses itens. O código revisado faz algo muito mais estranho. Verifica se há dois itens e chama uma função separada para classificá-los, se necessário. Se forem mais de dois itens, o código chama para classificar os três primeiros itens. Se houver três elementos, retorna os resultados desse tipo.

No entanto, se houver quatro itens para classificar, ele executa um código especializado que é extremamente eficiente na inserção de um quarto item no local apropriado dentro de um conjunto de três itens classificados. Isso soa como uma abordagem estranha, mas consistentemente superou o código existente.

Em produção

Como o AlphaDev produzia códigos mais eficientes, a equipe queria trazê-los de volta para a biblioteca C++ padrão LLVM. O problema aqui é que o código estava em assembler em vez de C++. Então, eles tiveram que trabalhar de trás para frente e descobrir o código C++ que produziria o mesmo assembly. Com isso feito, o código foi inserido na cadeia de ferramentas LLVM, a primeira vez que qualquer parte do código foi alterada em mais de uma década.

Como resultado, os pesquisadores estimam que o código do AlphaDev agora é executado trilhões de vezes por dia.

Natureza, 2023. DOI: 10.1038/s41586-023-06004-9 (Sobre DOIs).