O preditor de desvios 2-Ahead do Zen 5: novas possibilidades para uma ideia de 30 anos
(chipsandcheese.com)- O AMD Zen 5 introduziu um 2-Ahead Branch Predictor dentro de uma reestruturação completa da arquitetura Zen, trazendo de volta para a expansão moderna do front-end x86 pesquisas dos anos 1990 sobre predição antecipada de desvios em múltiplos blocos
- A predição de desvios permite que o front-end da CPU continue buscando instruções mesmo antes de o resultado de um desvio condicional ser conhecido, e erros de previsão levam a flush do pipeline e custo de reinício
- O Zen 5 usa dois fetch pipes de 32 bytes/ciclo a partir de um cache de instruções L1 de 32 KB, cada um ligado a um cluster de decodificação 4-wide, enquanto o Op Cache também tem estrutura dual-ported 6-wide para fornecer até 12 operandos à Op Queue
- A nova estrutura consegue processar 2 taken branches em um ciclo ao longo de blocos de instruções não contíguos e usa um campo de comprimento de 5 bits para localizar o início da terceira janela de predição, reduzindo o uso excessivo de recursos de decode e do Op Cache
- Como o x86 usa instruções de tamanho variável, é difícil paralelizar a identificação dos limites das instruções, então o 2-Ahead Branch Predictor e a estrutura dupla de fetch e decode se tornam a mudança central na expansão do front-end da linha Zen
O que mudou no front-end do Zen 5
- A AMD apresentou o Zen 5 como uma reestruturação completa da arquitetura Zen, e o 2-Ahead Branch Predictor é uma das mudanças que mais chamam atenção
- Essa estrutura reaparece com base em ideias discutidas em artigos de 30 anos atrás, no contexto da busca por mais desempenho por núcleo
- Ao prever vários taken branches de uma vez, o front-end consegue olhar antecipadamente para partes mais distantes do fluxo de instruções
Por que a predição de desvios é necessária no pipeline da CPU
- CPUs modernas usam uma estrutura de pipeline que divide a busca de instruções (fetch), a decodificação e a execução em várias etapas
- Quando há um desvio condicional, o front-end precisa decidir de onde buscar a próxima instrução antes que a avaliação da condição termine
- Há basicamente duas opções possíveis
- parar até que o resultado do desvio esteja pronto
- prever o próximo caminho e, se estiver errado, descartar o trabalho incorreto e recomeçar a partir de um ponto confirmado
- Quando a previsão erra, é necessário um flush para remover do pipeline o trabalho que dependia daquela suposição
- O custo de parar em um desvio é proporcional ao número de estágios do pipeline entre o fetch de instruções e o fim da avaliação da condição de desvio
- No fim, a CPU precisa prever o fluxo de instruções do programa com a maior precisão possível
O contexto em que surgiu a ideia de 2-Ahead
- Entre os métodos simples de previsão havia a estratégia de tratar saltos curtos para trás sempre como taken, o que historicamente trouxe grande vantagem sobre simplesmente buscar sempre o próximo endereço
- Manter um pequeno estado, como histórico recente de desvios ou registro de endereços, permitiu resultados melhores em programas reais
- Mesmo com estruturas de apenas algumas dezenas de KB, já era possível atingir taxas de acerto de predição de desvios na faixa alta dos 90%
- O 2-Ahead Branch Predictor é uma proposta discutida desde o começo dos anos 1990, quando também se estudava como ampliar a largura da arquitetura para 8-wide ou mais
- Depois, com a migração das CPUs comerciais para o multicore, a área de cada núcleo passou a importar mais, e a academia concentrou esforços em melhorias do preditor TAGE, mais eficiente em área
- Com a miniaturização dos processos, tornou-se possível colocar mais transistores em área semelhante, e junto com a expansão para CPUs out-of-order com centenas de estruturas, voltou a crescer o interesse em desempenho por núcleo
Por que o front-end x86 é mais complicado
- ISAs com instruções de tamanho fixo, como o Arm de 64 bits, facilitam a decodificação em paralelo de partes arbitrárias de uma linha de cache de instruções
- basta dividir os dados de entrada em limites de bytes de instrução garantidos e replicar a lógica dos decodificadores
- No x86, como as instruções têm comprimento variável, é necessário analisar os bytes de instrução linearmente para descobrir o próximo limite de cada instrução
- Dá para paralelizar isso até certo ponto com pipeline de pré-decodificação parcial de prefixos, mas o custo no x86 não é baixo
- Esse é um dos motivos pelos quais o decode 4-wide foi comum por muito tempo em núcleos x86 voltados a desempenho
- Projetos como o decode 6-wide do Intel Golden Cove só se tornaram viáveis comercialmente com o aumento da densidade lógica em processos mais recentes, mas o custo de área e energia da decodificação x86 paralela monolítica cresce de forma superlinear com o aumento da largura
- Em aplicações típicas de código inteiro, costuma haver aproximadamente 1 branch a cada 5 ou 6 instruções, o que reduz o incentivo para aumentar muito mais a largura do decoder
- O front-end x86 precisa de uma forma de chegar com segurança ao próximo limite de instrução, pulando uma etapa difícil de paralelizar: a identificação desses limites
A implementação dupla de fetch e decode no Zen 5
- “Multiple-block ahead branch predictors” by Seznec et al. é o artigo central que trata da motivação e da implementação do 2-Ahead Branch Predictor
- Um preditor capaz de lidar com vários taken branches sozinho não basta, e Seznec et al. defendem que, para aproveitar isso sem explodir as exigências de área, é necessário dual-porting do instruction fetch
- O Zen 5 passou a usar estrutura dual-port tanto no instruction fetch quanto no Op Cache
- usa dois fetch pipes de 32 bytes/ciclo a partir do cache de instruções L1 de 32 KB
- cada fetch pipe é ligado ao seu próprio cluster de decode 4-wide
- o Op Cache tem projeto dual-ported 6-wide e pode fornecer até 12 operandos para a Op Queue
- O Branch Target Buffer também entra nesse dual-porting
- a grande escala de 16K entries acessíveis no L1 BTB do Zen 5 pode explicar a possibilidade de um L1 BTB dual-ported
- o L2 BTB tem 8K entries, menor que o L1 BTB
- a AMD usa o L2 BTB de forma parecida com um victim cache, com entradas removidas do L1 BTB sendo movidas para o L2 BTB
Como ele processa 2 taken branches em um ciclo
- O Zen 5 consegue processar 2 taken branches em um único ciclo ao longo de blocos de instruções não contíguos
- Essa mudança reduz a perda de largura de banda de fetch ao encontrar taken branches e permite prever além de dois taken branches
- Isso permite olhar mais adiante no fluxo de instruções depois do segundo taken branch, criando três janelas de predição
- As três janelas de predição podem ser usadas para produzir instruções para o decode
- A segunda janela de predição recebe um campo de comprimento de 5 bits
- isso evita situações de super-reserva de recursos de decode ou do Op Cache
- é menor que um ponteiro, mas ainda fornece o ponto de início da terceira janela de predição
- quando a terceira janela de predição cruza o limite de uma linha de cache, não é necessário guardar estado extra no índice de lookup de predição para o ciclo seguinte
- se a terceira janela de predição estiver na mesma linha de cache que a primeira ou a segunda, essa terceira janela parcial não é tão eficaz quanto uma terceira janela completa
Restrições restantes no SMT
- Quando duas threads estão ativas no Zen 5, o fetch pipe acoplado a cada cluster de decode é particionado estaticamente
- Nessa situação, para funcionar como um núcleo com dual fetch, é preciso fazer fetch tanto do cache de instruções L1 quanto do Op Cache
- O fato de a AMD ter tornado o Op Cache dual-port pode ter como objetivo sustentar melhor o pipeline de dual fetch
Artigos relacionados citados junto
- “Multiple-block ahead branch predictors” by Seznec et al. – ASPLOS 1996: trata da motivação e da direção de implementação do 2-Ahead Branch Predictor
- “Optimization of Instruction Fetch Mechanisms for High Issue Rates” by Conte et al. – ISCA 1995: trata da otimização de mecanismos de instruction fetch para altas taxas de issue
- “Increasing the instruction fetch rate via multiple branch prediction and a branch address cache” by Yeh et al. – ICS 1993: trata do aumento da taxa de fetch por meio de multiple branch prediction e branch address cache
- “Out-of-Order Instruction Fetch using Multiple Sequencers” by Oberoi and Sohi – ICPP’02: trata de instruction fetch out-of-order com uso de multiple sequencers
- “Parallelism in the Front-End” by Oberoi and Sohi – ISCA 2003: trata do paralelismo no front-end da CPU
1 comentários
Opiniões do Hacker News
Para uma boa explicação de previsão de desvios desde as primeiras implementações, https://danluu.com/branch-prediction/ é ótimo
[0]: https://www.youtube.com/watch?v=nhXevKMm3JI&list=PLzH6n4zXuc...
[1]: https://www.youtube.com/watch?v=nczJ58WvtYo&list=PLzH6n4zXuc...
Fico curioso para ver como será o desempenho de SMT, e espero que essa abordagem traga ganhos e seja refinada ainda mais na próxima geração
O Zen5c chega a 192 núcleos ou 384 vCPUs, e no Zen 6c do ano que vem parece que 256 núcleos serão possíveis. Em um servidor 1U de dois soquetes, isso poderia chegar potencialmente a 512 núcleos e 1024 vCPUs
Os problemas de escalabilidade de aplicações web que enfrentávamos em 2014 agora caberiam em um único servidor, desde que dê para resfriá-lo. Mesmo considerando apenas 1 RPS por vCPU, são 1000 RPS sem contar acertos de cache, e nem a primeira página do HN gera 1000 pageviews por segundo no servidor
Fico curioso sobre como será o desempenho em HPC. O resfriamento em si talvez não seja um grande problema, mas a partir de certo ponto pode virar um problema “molhado” que exige resfriamento líquido direto (DLC)
Se considerarmos um rack denso de servidores com GPUs como uma única máquina, já chegamos a centenas de quilonúcleos
Já discuti com alguém que não conseguia entender a ideia de que um serviço na escala da Wikipedia poderia ser fornecido a partir de um único servidor, e foi bem divertido. Isso já é fácil há algum tempo; simplesmente não se faz assim por razões práticas, como disponibilidade ou eficiência de custos
Intuitivamente, quando há mais tarefas processando o mesmo problema à metade da velocidade, parece que deveria haver um custo de uso de memória; fico curioso se são comuns apps que, com SMT ativado, só usam mais memória sem ganho de velocidade
Em muitos benchmarks públicos, a maioria dos apps não parece obter ganhos perceptíveis de velocidade de execução
É sempre interessante ver um artigo de décadas atrás, publicado na época sem muita atenção, de repente se tornar estado da arte quando o hardware fica suficientemente poderoso
Um exemplo é o Z-buffer. Ele é usado em videogames 3D, mas quando apareceu pela primeira vez em um artigo, foi tratado quase como um assunto secundário, não por causa do tema, mas porque exigia memória demais
Algumas décadas depois, megabytes ficaram bem baratos, e no fim todos os renderizadores 3D em tempo real passaram a usá-lo
Parece que houve uma lacuna de uns 38 anos na literatura até David MacKay redescobri-los
O primeiro uso mainstream foi em 2003, e hoje são usados em WiFi, Ethernet e 5G
[1] https://en.wikipedia.org/wiki/Low-density_parity-check_code
[2] https://scholar.google.com/scholar?q=%22low+density+parity+c...
Ir a uma biblioteca e ler o que pesquisadores de ciência da computação publicavam em artigos de papel pode revelar ideias que eram inviáveis na época, mas implementáveis hoje
Nos últimos 20 anos, o desempenho de núcleo único foi contido em favor da escala horizontal, ou seja, mais núcleos, e por isso a complexidade e a área de die de cada núcleo viraram problema. Se essa tendência não existisse e os projetistas de CPU tivessem buscado principalmente desempenho de núcleo único, acho que teríamos visto uma implementação muito antes
O Z-buffer é um conceito simples, então é plausível que parecesse um detalhe secundário no artigo. Um exemplo melhor talvez seja ray tracing. Mesmo sem um histórico em gráficos 3D, o conceito em si é bem claro, mas até recentemente era inviável em termos de desempenho para renderização em tempo real
O interessante é que não encontramos uma abordagem mais simples para aproximar uma renderização parecida com a realidade e acabamos tendo que voltar a uma solução antiga, meio ingênua e cara
Muitos acadêmicos viam os sistemas de tipos subestruturais como algo que, na prática, havia morrido diante da coleta de lixo, mas o Rust os reviveu ao combiná-los com novas ideias do C++ da época
Essa necessidade adicional de largura de banda de memória tornou uma implementação adequada difícil e cara. Implementações avançadas usavam canais de RAM dedicados, mas em hardware de baixo custo isso consumia grande parte da largura de banda da interface de memória compartilhada
Por exemplo, alguns jogos de N64 desativavam o Z-buffer e otimizavam em software o desenho de fundo/primeiro plano para evitar o custo de ler e atualizar informações de profundidade
Preditores especulativos têm sido alvo de vários ataques para extrair dados privados
Se uma boa parte das ISAs comuns for vulnerável, fico curioso se estão tomando medidas para reduzir o impacto desses ataques
Não há como impedir isso, exceto por uma abordagem do nível de ferver o oceano[0]. A execução especulativa é valiosa demais para desempenho; um computador sem ela seria praticamente inutilizável. Se você realmente quer um processador sem execução especulativa, compre um Pentium antigo de primeira geração
Há várias mitigações práticas, mas no mínimo é preciso garantir isolamento de processos entre o processo vítima que contém segredos e o potencial atacante que pode influenciar a execução da vítima
A Intel foi pega fazendo execução especulativa atravessando rings, e por isso era possível ler memória do kernel ou do hipervisor a partir do espaço de usuário. Em uma CPU que não tenha um projeto ruim, a principal preocupação tende a ser iframes HTML
Origens diferentes não podem enviar requisições HTTP livremente[1], mas podem incluir umas às outras sem permissão[2]. Tradicionalmente, essa informação era carregada no processo do atacante e podia vazar por ataque de temporização
A solução inicial da web não foi isolar iframes em processos, mas remover o próprio multithreading com memória compartilhada. Se você tira do atacante a referência de tempo, importa menos o que a vítima executa especulativamente. Mas, para isso, é preciso remover o multithreading. Caso contrário, uma thread pode criar um relógio escrevendo dados conhecidos repetidamente em um loop
[0] https://hackaday.com/2013/08/02/the-mill-cpu-architecture/
[1] Pelo menos não, a menos que a origem de destino permita via CORS
[2] Por exemplo: hotlink de imagens ou embed em iframe
Não é uma vulnerabilidade inerente à previsão em si
Para alguém iniciante nessa área, mesmo depois de ler o texto, não fica claro exatamente o que é um preditor de desvios 2-ahead
Nos anos 90, os processadores ficavam mais próximos de uma coisa ou de outra, mas os modernos parecem ter ambas na maioria dos casos
O resumo de “Multiple-block ahead branch predictors” explica que a ideia é não usar as informações do bloco de instruções atual para prever o endereço do próximo bloco de instruções, e sim prever o bloco seguinte a esse. Isso reduz o gargalo de busca de instruções em processadores “brainiac” com despacho largo e permite prever eficientemente dois endereços de blocos de instruções em um ciclo
Também diz que, em processadores “speed demon”, é possível colocar o processo de previsão de desvios em pipeline para obter clocks mais altos ou melhorar a precisão usando estruturas de previsão maiores. Ao contrário das abordagens existentes com múltiplos preditores, preditores de desvios vários blocos à frente podem usar qualquer método de previsão de desvios
[0] https://dl.acm.org/doi/10.1145/237090.237169
Além disso, parece que eyegor já postou o link, mas a ideia é pelo menos ler o resumo
Deve ser muito mais difícil do que prever o próximo desvio, mas permite buscar muito mais cedo o código para alimentar pipelines mais profundos
Assim, em vez de avaliar antecipadamente apenas n+1 como na previsão de desvios comum, dá para avaliar antecipadamente também o resultado n+2. Não sei bem como isso funciona sem estragar o cache L1
Se a ideia é olhar além de n+1, parece que haveria muito mais expulsões do cache, então acho que estou deixando passar alguma coisa
Dizem que o Zen 5 consegue enxergar mais longe, até o fluxo de instruções além do segundo desvio tomado, e com isso pode ter 3 janelas de previsão úteis para gerar instruções a serem decodificadas
O artigo original está em acesso aberto, mas ainda não li muito: https://dl.acm.org/doi/10.1145/237090.237169
Cada direção de um desvio leva ao início de um novo bloco de instruções, e a última instrução desses blocos normalmente é outro desvio
Ou seja, um preditor de desvios é um dispositivo que acerta o endereço do próximo bloco. Um preditor de desvios 2-ahead faz a mesma coisa, mas para os dois blocos seguintes
Nas palavras do artigo, “as informações do bloco de instruções atual são usadas para prever o endereço do bloco que vem depois do próximo bloco de instruções”
Ao contrário de um preditor de desvios comum, isso é possível sem esperar até que as instruções do próximo bloco sejam decodificadas. Por isso ele consegue alimentar vários decodificadores de instruções ao mesmo tempo
Isso é especialmente útil em CPUs modernas nas quais o decodificador de instruções virou gargalo. Um único decodificador que decodifica apenas 1 instrução por ciclo dificilmente acompanha um front-end largo capaz de executar muitas instruções, como 4 a 6 por ciclo
Talvez sejam necessários mais hints de desvio: https://github.com/ziglang/zig/issues/5177
Fico pensando se daria para ter cold, warm, warmer e omitir hot por ser o padrão. Às vezes também seria possível marcar todos os desvios como cold, exceto um
Provavelmente é uma má ideia, mas queria entender o motivo
Quando há um desvio condicional, fico me perguntando por que não buscar e preparar as instruções dos dois lados possíveis do desvio e depois descartar o lado errado
Queria saber se isso é muito mais difícil, ou se há algum outro motivo que faz não valer a pena
Preditores de desvio TAGE modernos acertam bem mais de 99%. Então as instruções adicionais do outro lado do desvio quase sempre são descartadas
O pior é que o front-end busca instruções dezenas de desvios à frente do ponto em que o back-end consegue confirmar a direção real. O que você faz no próximo desvio? Decodifica 4 desvios possíveis, depois 8, 16, 32? A maioria será descartada
Se você tem hardware para buscar vários fluxos de instruções em paralelo, como no Intel Gracemont/Goldmont/Skymont e no AMD Zen 5, a estratégia melhor é presumir que o preditor de desvio está 100% correto. Siga um lado do desvio, e depois siga o próximo também
O Intel Skymont tem 3 decodificadores, cada um 3-wide, então decodifica em paralelo os próximos 3 alvos de desvio. A Intel até insere desvios falsos para dividir blocos de código grandes, de modo que os três decodificadores estejam sempre decodificando partes diferentes do fluxo de instruções que virá. Depois, os 3 fluxos de micro-operações são mesclados para que o Skymont mantenha uma largura de banda efetiva de decodificação de 9 instruções por ciclo
Executar os dois lados do desvio só reduz um pouco a latência nos raros casos em que a predição de desvio erra. Já ao continuar seguindo as próximas duas ou três predições na mesma direção, Intel e AMD conseguem fazer vários decodificadores trabalharem em paralelo. A Intel consegue formar um 9-wide com três decodificadores 3-wide mais simples, e a AMD consegue formar um 8-wide com dois decodificadores 4-wide mais simples
Compiladores, runtimes, CPUs etc. muitas vezes conseguem acertar qual resultado é mais provável, e normalmente a estratégia melhor é simplesmente não fazer trabalho extra. É melhor do que gastar silício e calor com a resposta errada para o caso de estar equivocado
Acho que muita gente não tem intuição de quão precisa a predição de desvios pode ser. Basta olhar para o próprio código para perceber rapidamente coisas como “a maior parte do fluxo de controle vai por aqui, e este desvio existe para tratar uma situação excepcional”
Compiladores atuais também inferem isso muito bem, e CPUs/JITs/runtimes conseguem criar heurísticas impressionantes. Ainda assim, quando isso falha, é possível inserir dicas explícitas no código para informar ao compilador etc. qual direção é esperada
O buffer de reordenação de instruções de uma CPU moderna tem profundidade de centenas de instruções, e, se houver apenas 8 saltos condicionais entre elas, o programa pode seguir 256 caminhos
Se a probabilidade de o preditor de desvio acertar todos os 8 for maior que 50%, e de fato é, não vale a pena fazer 256 vezes mais trabalho só para se preparar
É preciso silício para armazenar mais estado microarquitetural e mais unidades de execução para aproveitar totalmente a técnica. Mas CPUs superescalares já precisam dessas coisas para explorar paralelismo em nível de instrução em código com poucos desvios, então já as têm
O resto é o trabalho trabalhoso de lidar com coisas complicadas como aliases e interrupções, mas engenheiros de hardware são como magos e conseguem fazer isso também
Só que a execução especulativa abre a possibilidade de explorar canais laterais de temporização de cache para extrair informações de dados tocados por código que foi executado apenas especulativamente e cujos efeitos colaterais arquiteturais não foram commitados. Ou seja, informações podem vazar até de código que não foi executado “de verdade”
Isso inclui código que não teria sido executado explicitamente por causa de verificações condicionais, por exemplo verificações de permissão
Um caso de ataque conhecido é o Spectre: https://en.m.wikipedia.org/wiki/Spectre_(security_vulnerabil...
Então, basicamente, a conta não fecha de jeito nenhum. É muito melhor usar esses recursos do chip em outras threads ou núcleos
Para julgar se é uma boa ideia, eu gostaria de ver primeiro dados de desempenho. Também não há informações sobre a penalidade de predição de desvios dessa abordagem
De todo modo, a intuição dessa abordagem parece estar em buscar e decodificar agressivamente instruções que talvez ainda não estejam no cache de instruções L1 ou no cache de micro-operações
Isso é importante para x86, e talvez também para RISC-V. Ambas têm comprimentos de instrução variáveis, então, olhando apenas para um bloco do cache de instruções, o núcleo não sabe como decodificar as instruções dentro daquele bloco. Em ambas as ISAs, para começar a decodificar um bloco do cache de instruções, é preciso conhecer o PC de pelo menos uma instrução
Portanto, se a aplicação souber para onde pode saltar dois blocos à frente, isso ajuda a buscar e decodificar mais adiante do que a abordagem atual
Essa abordagem se parece com prefetching de instruções, mas o prefetching de instruções não fornece ao núcleo a informação do ponto de partida
Núcleos ARM de alto desempenho provavelmente não sofrem do problema de “encontrar o ponto de partida”, porque todas as instruções têm 32 bits. Portanto, mesmo sem saber o ponto de partida, o procedimento de decodificação pode ser feito em paralelo
Esse método parece beneficiar aplicações com grande peso no front-end, por exemplo cargas de trabalho em nuvem em que blocos de código quentes ficam espalhados pelo binário. Fico curioso para saber se haveria ganhos ou perdas de desempenho em outros tipos de aplicação
Ainda não faço a menor ideia do que é um preditor de desvio 2-ahead
Em geral, artigos de pesquisa antigos presumem que o leitor sabe muito menos sobre temas desse tipo. Na época, esse conhecimento era muito mais de nicho
Agora, o que falta é largura de banda de memória. Os dois canais de memória do soquete AM5 para consumidores são modestos para esse nível de desempenho computacional, especialmente mesmo quando comparados ao Apple Silicon básico
Migrei de uma configuração Zen robusta para um M2 Max, e fiquei novamente surpreso com o quanto o aumento na largura de banda de memória acelera trabalhos intensivos em dados. Mesmo em multitarefa bem pesada, o pipeline estreito de memória da configuração Zen frequentemente ficava congestionado
O motivo pelo qual as pessoas olham para o Apple Silicon, especialmente por causa de LLMs, é que LLMs até são mais adequados para GPU, mas também precisam de muita VRAM, e a NVIDIA cobra preços absurdos por GPUs com muita VRAM
Se a AMD realmente quiser frear o ímpeto da NVIDIA, precisa vender GPUs de consumo com 64~128 GB de VRAM