Qualquer pessoa que tenha feito um curso básico de ciência da computação sem dúvida passou algum tempo desenvolvendo um algoritmo de classificação – um código que pega uma lista não ordenada de Itens e os organiza 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 fundamental que os algoritmos são incorporados na maioria das bibliotecas de linguagem de programação padrã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 que a programação fosse tratada como um jogo.

é tudo um jogo

Uma das coisas que o DeepMind se destaca é que desenvolveu um software que ensina sozinho a jogar. Esta abordagem provou ser extremamente eficaz, transformando jogos tão diversos como xadrez, IrE nave estelar. Embora os detalhes variem de acordo com o jogo, o software aprende durante o jogo e descobre opções que permitem maximizar as pontuações.

Como o sistema DeepMind não é treinado em jogos que os humanos jogam, ele pode descobrir abordagens para jogos nos quais os humanos ainda não pensaram. Claro, como está sempre jogando contra si mesmo, há casos em que desenvolveu pontos cegos que os humanos podem explorar.

Esta abordagem é muito relevante para a programação. Grandes modelos de linguagem escrevem código eficaz porque viram muitos exemplos humanos. Por causa disso, no entanto, é improvável que desenvolvam algo que os humanos não tenham feito antes. Se quisermos otimizar algoritmos bem compreendidos, como funções de classificação, a base de algo baseado no código humano existente alcançará, na melhor das hipóteses, um desempenho equivalente. Mas como você faz uma IA reconhecer uma abordagem realmente nova?

O pessoal da DeepMind adotou a mesma abordagem do 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 enquanto asseguravam que o código fosse executado sem erros. Por meio do aprendizado por reforço, o AlphaDev desenvolve gradualmente a capacidade de escrever código simplificado e altamente eficiente.

Em AlphaDev

Dizer que o sistema otimiza a 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. Um deles é uma função de gráfico que rastreia o desempenho geral do código à medida que ele evolui. Isso inclui a estrutura geral do algoritmo e o uso de registradores e memória x86.

O sistema adiciona instruções de montagem selecionadas individualmente Pesquisa de árvores de Monte Carlo– novamente, uma abordagem adotada pelos sistemas de videogame. O aspecto de “árvore” dessa abordagem permite que o sistema reduza rapidamente a uma parte limitada da grande variedade de declarações possíveis, enquanto Monte Carlo adiciona um grau de aleatoriedade à declaração exata selecionada desse ramo. (Observe que “instrução” neste contexto inclui coisas como os registradores específicos selecionados para criar um assembly válido e completo.)

O sistema então avalia o estado do código assembly quanto à latência e validade, atribui uma pontuação a ele e a compara com a pontuação do código anterior. E por meio do aprendizado por reforço, ele mantém informações sobre como a descida em diferentes ramos da árvore funciona, dado o status do programa. Com o tempo, ele “aprende” como atingir um estado de jogo bem-sucedido – uma classificação concluída – com pontuação máxima e, portanto, latência mínima.

O principal benefício desse sistema é que nenhuma amostra de código é necessária para o treinamento. Em vez disso, o sistema gera seus próprios exemplos de código e os avalia. Ao fazer isso, ele retém informações sobre combinações de comandos que são eficazes na classificação.

código útil

A classificação em programas complexos pode lidar com coleções grandes e arbitrárias de itens. Mas no nível da biblioteca padrão, ele consiste em 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 qualquer número de elementos até um certo limite – ou seja, você pode chamar uma função que classifica até quatro elementos, mas não mais.

A DeepMind corrigiu o AlphaDev em cada um desses recursos, mas eles funcionam de maneira muito diferente. Para as funções que processam um determinado número de elementos, é possível escrever código sem ramificação, onde você executa código diferente dependendo do estado de uma variável. Portanto, o desempenho desse código geralmente aumenta com o número de instruções necessárias. O AlphaDev foi capaz de truncar uma instrução de cada agrupamento 3, agrupamento 5 e agrupamento 8, e ainda mais do agrupamento 6 e agrupamento 7. Houve apenas um (sort-4) onde não foi encontrada nenhuma maneira de melhorar o código humano. Execuções repetidas do código em sistemas reais mostraram que menos instruções realmente resultaram em melhor desempenho.

Classificar um número variável de entradas requer ramificações no código, e diferentes processadores possuem diferentes quantidades de hardware para lidar com essas ramificações. Portanto, o código foi avaliado com base em seu desempenho em 100 máquinas diferentes. Mais uma vez, o AlphaDev encontrou maneiras de espremer desempenho extra e veremos como ele conseguiu fazer 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 determinar quantos itens classificar e chama a função de classificação dedicada para esse número de itens. O código revisado faz algo muito mais estranho. Ele testa se há dois itens e, se necessário, chama uma função separada para classificá-los. Se houver mais de dois itens, o código solicita a classificação dos três primeiros itens. Se houver três itens, os resultados desse tipo serão retornados.

No entanto, quando quatro elementos precisam ser classificados, é executado um código especial que é extremamente eficiente para inserir um quarto elemento no local apropriado dentro de um conjunto de três elementos classificados. Isso soa como uma abordagem estranha, mas consistentemente superou o código existente.

Em produção

Como o AlphaDev produzia um código mais eficiente, a equipe queria integrá-lo novamente à biblioteca C++ padrão LLVM. O problema aqui é que o código estava em assembly, não em C++. Então você teve que trabalhar de trás para frente e descobrir o código C++ que produziria o mesmo assembly. Feito isso, o código foi integrado à cadeia de ferramentas LLVM – a primeira vez que qualquer parte do código mudou em mais de uma década.

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

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