Branch prediction

Na arquitetura de computadores, um preditor de desvio é um circuito digital que tenta adivinhar para onde um desvio (por exemplo, uma estrutura if–then–else) irá antes que isso seja conhecido definitivamente. O propósito do preditor de desvio é melhorar o fluxo no pipeline de instruções. Os preditores de desvio desempenham um papel crítico para alcançar alto desempenho em muitas arquiteturas de microprocessadores pipelineados modernas.

Figura 1: Exemplo de pipeline de 4 estágios. As caixas coloridas representam instruções independentes entre si.

A ramificação bidirecional é geralmente implementada com uma instrução de salto condicional. Um salto condicional pode ser "tomado" e saltar para um lugar diferente na memória do programa, ou pode ser "não tomado" e continuar a execução imediatamente após o salto condicional. Não se sabe com certeza se um salto condicional será tomado ou não até que a condição seja calculada e o salto condicional tenha passado o estágio de execução no pipeline de instruções (ver fig. 1).

Sem predição de desvio, o processador teria que esperar até que a instrução de salto condicional tivesse passado o estágio de execução antes que a próxima instrução pudesse entrar no estágio de busca no pipeline. O preditor de desvio tenta evitar esse desperdício de tempo tentando adivinhar se o salto condicional é mais provável de ser tomado ou não tomado. O desvio que se supõe ser o mais provável é então buscado e executado especulativamente. Se mais tarde for detectado que a suposição estava errada, então as instruções executadas especulativamente ou parcialmente executadas são descartadas e o pipeline recomeça com o desvio correto, incorrendo em um atraso.

O tempo desperdiçado em caso de predição incorreta de desvio é igual ao número de estágios no pipeline desde o estágio de busca até o estágio de execução. Os microprocessadores modernos tendem a ter pipelines bastante longos, de modo que o atraso de predição incorreta fica entre 10 e 20 ciclos de clock. Como resultado, tornar um pipeline mais longo aumenta a necessidade de um preditor de desvio mais avançado.

A primeira vez que uma instrução de salto condicional é encontrada, não há muita informação para basear uma previsão. No entanto, o preditor de desvio mantém registros de se os desvios são tomados ou não, então, quando encontra um salto condicional que foi visto várias vezes antes, ele pode basear a previsão no histórico registrado. O preditor de desvio pode, por exemplo, reconhecer que o salto condicional é tomado mais vezes do que não, ou que é tomado a cada segunda vez.

A predição de desvio não é o mesmo que predição de alvo de desvio. A predição de desvio tenta adivinhar se um salto condicional será tomado ou não. A predição de alvo de desvio tenta adivinhar o alvo de um salto condicional ou incondicional tomado antes que ele seja computado pela decodificação e execução da própria instrução. A predição de desvio e a predição de alvo de desvio são frequentemente combinadas no mesmo circuito.

Implementação

Predição estática de desvio

A predição estática é a técnica de predição de desvio mais simples, porque não depende de informações sobre o histórico dinâmico do código em execução. Em vez disso, ela prediz o resultado de um desvio baseando-se unicamente na instrução de desvio. As primeiras implementações de SPARC e MIPS (duas das primeiras arquiteturas RISC comerciais) usavam predição estática de direção única: elas sempre predizem que um salto condicional não será tomado, então sempre buscam a próxima instrução sequencial. Somente quando o desvio ou salto é avaliado e considerado tomado, o ponteiro de instrução é definido para um endereço não sequencial.

Ambas as CPUs buscam instruções em um ciclo e avaliam desvios no estágio de decodificação. Como resultado, a recorrência do alvo do desvio tem dois ciclos de duração, e a máquina sempre busca a instrução imediatamente após qualquer desvio tomado. Ambas as arquiteturas definem slots de atraso de desvio para utilizar essas instruções buscadas.

Uma forma mais avançada de predição estática assume que desvios para trás serão tomados e desvios para frente não. (Um desvio para trás é aquele que tem um endereço de destino menor que seu próprio endereço.) Essa regra aumenta a precisão de predição em loops, que podem ser construídos com um desvio para trás no final que é majoritariamente tomado, ou um desvio para frente no início que é majoritariamente não tomado. Com processadores que usam esse método de predição, ordenar as instruções pode maximizar a precisão da predição de desvio. A ISA RISC-V recomenda que o software escrito para harts RISC-V (threads de hardware), ou gerado para rodar em harts RISC-V, seja otimizado com a suposição de que desvios para trás são tomados e desvios para frente não são. (Mesmo quando o processador incorpora um preditor mais avançado que diminui o valor relativo da predição estática.)

Alguns processadores aceitam dicas de predição de desvio que sobrepõem a predição estática. O Intel Pentium 4 e o Pentium 4E aceitam dicas de predição de desvio como prefixos. Na presença de predição dinâmica, a predição estática não oferece quase nenhum benefício, e sobrepor a predição estática ajuda ainda menos. Os processadores Pentium M e Core2 subsequentes da Intel ignoram prefixos de dicas de predição de desvio. Nenhum fabricante de x86 reintroduziu dicas de predição.

Os preditores dinâmicos de desvio naturalmente recorrem à predição estática de desvio quando não têm informação em cache (como na primeira vez que um dado desvio é encontrado). Tanto o Motorola MPC7450 (G4e) quanto o Intel Pentium 4 recorrem à predição estática.

Na predição estática, todas as decisões são tomadas em tempo de compilação, antes da execução do programa.

Predição dinâmica de desvio

A predição dinâmica de desvio usa informações sobre desvios tomados ou não tomados coletadas em tempo de execução para predizer o resultado de um desvio.

Predição aleatória de desvio

Predição aleatória de desvio significa dar um palpite aleatório sobre se um desvio será tomado, a cada vez que ele é executado. O custo de um gerador de números pseudorrandômicos é baixo comparado a outras técnicas. A predição aleatória garante uma taxa de acerto de 50% que não pode ser aumentada ou reduzida por nenhum meio. (E torna o timing ainda mais não determinístico ou imprevisível que outros métodos.) A predição estática de desvio (assumindo que desvios para frente são tomados e desvios para trás não são) prediz cada desvio com uma precisão variando de 0% a 100%, com a taxa de sucesso geral em algum lugar no meio. Código não otimizado tem grande probabilidade de rodar com taxa de sucesso de predição superior a 50%; até 90% é provável. Se o compilador faz alguma reordenação de instruções, ele torna a taxa de predição correta de desvio maior que para código não otimizado. A predição estática de desvio há muito superou a predição aleatória. A predição dinâmica de desvio superou a predição estática de desvio e é comum, apesar da complexidade adicional.

Predição de próxima linha

Alguns processadores superescalares (MIPS R8000, Alpha 21264 e Alpha 21464 (EV8)) buscam cada linha de instruções com um ponteiro para a próxima linha. Esse preditor de próxima linha lida tanto com a predição de alvo de desvio quanto com a predição de direção de desvio.

Quando um preditor de próxima linha aponta para grupos alinhados de 2, 4 ou 8 instruções, o alvo do desvio geralmente não será a primeira instrução buscada, e então as instruções iniciais buscadas são desperdiçadas. Assumindo por simplicidade uma distribuição uniforme de alvos de desvio, 0,5, 1,5 e 3,5 instruções buscadas são descartadas, respectivamente.

Como o próprio desvio geralmente não será a última instrução em um grupo alinhado, as instruções após o desvio tomado (ou seu slot de atraso) serão descartadas. Mais uma vez, assumindo uma distribuição uniforme de posicionamentos de instruções de desvio, 0,5, 1,5 e 3,5 instruções buscadas são descartadas.

As instruções descartadas nas linhas de desvio e destino somam quase um ciclo de busca completo, mesmo para um preditor de próxima linha de ciclo único.

Predição de desvio de um nível

Contador de saturação

Um contador de saturação de 1 bit (essencialmente um flip-flop) registra o último resultado do desvio. Esta é a versão mais simples possível de preditor dinâmico de desvio, embora não seja muito precisa.

Um contador de saturação de 2 bits é uma máquina de estados com quatro estados:

Figura 2: Diagrama de estados do contador de saturação de 2 bits
  • Fortemente não tomado
  • Fracamente não tomado
  • Fracamente tomado
  • Fortemente tomado

Quando um desvio é avaliado, a máquina de estados correspondente é atualizada. Desvios avaliados como não tomados mudam o estado em direção a fortemente não tomado, e desvios avaliados como tomados mudam o estado em direção a fortemente tomado. A vantagem do esquema de contador de dois bits sobre o esquema de um bit é que um salto condicional tem que se desviar duas vezes do que fez mais no passado antes que a predição mude. Por exemplo, um salto condicional de fechamento de loop é predito incorretamente uma vez em vez de duas.

O processador original Intel Pentium, não-MMX, usa um contador de saturação, embora com uma implementação imperfeita.

Nos benchmarks SPEC'89, preditores bimodais muito grandes saturam em 93,5% de acerto, uma vez que cada desvio mapeia para um contador único.:3

A tabela do preditor é indexada com bits do endereço da instrução, para que o processador possa buscar uma predição para cada instrução antes que a instrução seja decodificada.

Preditor de dois níveis

O Preditor de Desvio de Dois Níveis, também referido como Preditor de Desvio Baseado em Correlação, usa uma tabela bidimensional de contadores, também chamada de "Tabela de Histórico de Padrões". As entradas da tabela são contadores de dois bits.

Preditor adaptativo de dois níveis

Figura 3: Preditor de desvio adaptativo de dois níveis. Cada entrada na tabela de histórico de padrões representa um contador de saturação de 2 bits do tipo mostrado na figura 2.

Se uma declaração if é executada três vezes, a decisão tomada na terceira execução pode depender de se as duas anteriores foram tomadas ou não. Em tais cenários, um preditor adaptativo de dois níveis funciona de forma mais eficiente que um contador de saturação. Saltos condicionais que são tomados a cada segunda vez ou que têm algum outro padrão recorrente regular não são bem previstos pelo contador de saturação. Um preditor adaptativo de dois níveis lembra o histórico das últimas n ocorrências do desvio e usa um contador de saturação para cada um dos possíveis 2n padrões de histórico. Esse método é ilustrado na figura 3.

Considere o exemplo de n = 2. Isso significa que as últimas duas ocorrências do desvio são armazenadas em um registrador de deslocamento de dois bits. Esse registrador de histórico de desvio pode ter quatro valores binários diferentes, 00, 01, 10 e 11, onde zero significa "não tomado" e um significa "tomado". Uma tabela de histórico de padrões contém quatro entradas por desvio, uma para cada um dos 22 = 4 históricos de desvio possíveis, e cada entrada na tabela contém um contador de saturação de dois bits do mesmo tipo que na figura 2 para cada desvio. O registrador de histórico de desvio é usado para escolher qual dos quatro contadores de saturação usar. Se o histórico for 00, então o primeiro contador é usado; se o histórico for 11, então o último dos quatro contadores é usado.

Assuma, por exemplo, que um salto condicional é tomado a cada terceira vez. A sequência de desvios é 001001001... Nesse caso, a entrada número 00 na tabela de histórico de padrões irá para o estado "fortemente tomado", indicando que após dois zeros vem um um. A entrada número 01 irá para o estado "fortemente não tomado", indicando que após 01 vem um zero. O mesmo é o caso com a entrada número 10, enquanto a entrada número 11 nunca é usada porque nunca há dois uns consecutivos.

A regra geral para um preditor adaptativo de dois níveis com um histórico de n bits é que ele pode predizer qualquer sequência repetitiva com qualquer período se todas as sub-sequências de n bits forem diferentes.

A vantagem do preditor adaptativo de dois níveis é que ele pode rapidamente aprender a predizer um padrão repetitivo arbitrário. Esse método foi inventado por T.-Y. Yeh e Yale Patt na Universidade de Michigan. Desde a publicação inicial em 1991, esse método se tornou muito popular, sendo usado para processadores Pentium posteriores como o Pentium MMX. Variantes desse método de predição são usadas na maioria dos microprocessadores modernos.[carece de fontes]?

Preditor neural de dois níveis

Um preditor de desvio de dois níveis onde o segundo nível é substituído por uma rede neural foi proposto.

Predição local de desvio

Um preditor local de desvio tem um buffer de histórico separado para cada instrução de salto condicional. Ele pode usar um preditor adaptativo de dois níveis. O buffer de histórico é separado para cada instrução de salto condicional, enquanto a tabela de histórico de padrões pode ser separada também ou pode ser compartilhada entre todos os saltos condicionais.

O Intel Pentium MMX, Pentium II e Pentium III têm preditores locais de desvio com um histórico local de 4 bits e uma tabela de histórico de padrões local com 16 entradas para cada salto condicional.

Nos benchmarks SPEC'89, preditores locais muito grandes saturam em 97,1% de acerto.:6

Predição global de desvio

Um preditor global de desvio não mantém um registro de histórico separado para cada salto condicional. Em vez disso, ele mantém um histórico compartilhado de todos os saltos condicionais. A vantagem de um histórico compartilhado é que qualquer correlação entre diferentes saltos condicionais faz parte da construção das predições. A desvantagem é que o histórico é diluído por informação irrelevante se os diferentes saltos condicionais não são correlacionados, e que o buffer de histórico pode não incluir nenhum bit do mesmo desvio se houver muitos outros desvios no meio. Ele pode usar um preditor adaptativo de dois níveis.

Esse esquema é melhor que o esquema de contador de saturação apenas para tamanhos de tabela grandes, e é raramente tão bom quanto a predição local. O buffer de histórico deve ser mais longo para fazer uma boa predição. O tamanho da tabela de histórico de padrões cresce exponencialmente com o tamanho do buffer de histórico. Portanto, a grande tabela de histórico de padrões deve ser compartilhada entre todos os saltos condicionais.

Um preditor adaptativo de dois níveis com buffer de histórico compartilhado globalmente e tabela de histórico de padrões é chamado de preditor "gshare" se ele faz xor do histórico global e do PC do desvio, e "gselect" se ele os concatena. A predição global de desvio é usada em processadores AMD e nos processadores Intel Pentium M, Core, Core 2 e Atom baseados em Silvermont.

Predição de desvio combinada (alloyed)

Um preditor de desvio combinado combina os princípios de predição local e global concatenando históricos de desvio local e global, possivelmente com alguns bits do contador de programa também. Testes indicam que o processador VIA Nano pode estar usando essa técnica.

Preditor de concordância

Um preditor de concordância é um preditor adaptativo de dois níveis com buffer de histórico compartilhado globalmente e tabela de histórico de padrões, e um contador de saturação local adicional. As saídas dos preditores local e global são combinadas por XOR entre si para dar a predição final. O propósito é reduzir as contenções na tabela de histórico de padrões onde dois desvios com predições opostas acabam compartilhando a mesma entrada na tabela de histórico de padrões.

Preditor híbrido

Um preditor híbrido, também chamado de preditor combinado, implementa mais de um mecanismo de predição. A predição final é baseada ou em um meta-preditor que lembra qual dos preditores fez as melhores predições no passado, ou em uma função de voto majoritário baseada em um número ímpar de preditores diferentes.

Scott McFarling propôs a predição combinada de desvios em seu artigo de 1993.

Nos benchmarks SPEC'89, tal preditor é tão bom quanto o preditor local.[carece de fontes]?

Preditores como o gshare usam múltiplas entradas de tabela para rastrear o comportamento de qualquer desvio particular. Essa multiplicação de entradas torna muito mais provável que dois desvios mapeiem para a mesma entrada da tabela (uma situação chamada de aliasing), o que, por sua vez, torna muito mais provável que a precisão da predição sofra para esses desvios. Uma vez que se tem múltiplos preditores, é benéfico arranjar que cada preditor tenha padrões de aliasing diferentes, para que seja mais provável que ao menos um preditor não tenha aliasing. Preditores combinados com diferentes funções de indexação para os diferentes preditores são chamados de preditores gskew, e são análogos às caches associativas enviesadas usadas para cache de dados e instruções.

Preditor de loop

Um salto condicional que controla um loop é melhor predito com um preditor de loop especial. Um salto condicional na parte inferior de um loop que repete N vezes será tomado N-1 vezes e então não tomado uma vez. Se o salto condicional estiver colocado no topo do loop, ele será não tomado N-1 vezes e então tomado uma vez. Um salto condicional que vai muitas vezes em uma direção e então na outra direção uma vez é detectado como tendo comportamento de loop. Tal salto condicional pode ser predito facilmente com um contador simples. Um preditor de loop faz parte de um preditor híbrido onde um meta-preditor detecta se o salto condicional tem comportamento de loop.

Preditor de desvio indireto

Uma instrução de salto indireto pode escolher entre mais de dois desvios. Alguns processadores têm preditores especializados de desvio indireto. Processadores mais recentes da Intel e AMD podem predizer desvios indiretos usando um preditor adaptativo de dois níveis. Esse tipo de instrução contribui com mais de um bit para o buffer de histórico. O zEC12 e processadores z/Architecture posteriores da IBM suportam uma instrução BRANCH PREDICTION PRELOAD que pode pré-carregar a entrada do preditor de desvio para uma dada instrução com um endereço de destino de desvio construído pela adição do conteúdo de um registrador de propósito geral a um valor de deslocamento imediato.

Processadores sem esse mecanismo simplesmente predizem que um salto indireto irá para o mesmo alvo que foi da última vez.

Predição de retornos de função

Uma função normalmente retornará para onde foi chamada. A instrução de retorno é um salto indireto que lê seu endereço de destino da pilha de chamadas. Muitos microprocessadores têm um mecanismo de predição separado para instruções de retorno. Esse mecanismo é baseado em um chamado return stack buffer, que é um espelho local da pilha de chamadas. O tamanho do return stack buffer é tipicamente de 4 a 16 entradas.

Substituição da predição de desvio

O trade-off entre predição de desvio rápida e boa predição de desvio é às vezes tratado tendo dois preditores de desvio. O primeiro preditor de desvio é rápido e simples. O segundo preditor de desvio, que é mais lento, mais complexo e com tabelas maiores, irá substituir uma predição possivelmente errada feita pelo primeiro preditor.

Os microprocessadores Alpha 21264 e Alpha EV8 usaram um preditor de próxima linha de ciclo único rápido para lidar com a recorrência do alvo de desvio e fornecer uma predição de desvio simples e rápida. Como o preditor de próxima linha é tão impreciso, e a recorrência de resolução do desvio leva tanto tempo, ambos os núcleos têm preditores de desvio secundários de dois ciclos que podem substituir a predição do preditor de próxima linha ao custo de um único ciclo de busca perdido.

O Intel Core i7 tem dois branch target buffers e possivelmente dois ou mais preditores de desvio.

Predição neural de desvio

O aprendizado de máquina para predição de desvio usando LVQ e perceptrons multicamadas, chamado de "predição de desvio neural", foi proposto por Lucian Vintan (Universidade Lucian Blaga de Sibiu). Um ano depois, ele desenvolveu o preditor de desvio por perceptron. A pesquisa sobre preditor neural de desvio foi muito mais desenvolvida por Daniel Jimenez. Em 2001, o primeiro preditor por perceptron que era viável de implementar em hardware foi apresentado. A primeira implementação comercial de um preditor de desvio por perceptron foi na microarquitetura Piledriver da AMD.

A principal vantagem do preditor neural é sua capacidade de explorar históricos longos enquanto exige apenas crescimento linear de recursos. Preditores clássicos exigem crescimento exponencial de recursos. Jimenez relata uma melhoria global de 5,7% sobre um preditor híbrido no estilo McFarling. Ele também usou preditores híbridos de substituição gshare/perceptron.

A principal desvantagem do preditor por perceptron é sua alta latência. Mesmo após tirar vantagem de truques aritméticos de alta velocidade, a latência de computação é relativamente alta comparada ao período de clock de muitas microarquiteturas modernas. A fim de reduzir a latência de predição, Jimenez propôs em 2003 o fast-path neural predictor, onde o preditor por perceptron escolhe seus pesos de acordo com o caminho do desvio atual, em vez de de acordo com o PC do desvio. Muitos outros pesquisadores desenvolveram esse conceito (A. Seznec, M. Monchiero, D. Tarjan & K. Skadron, V. Desmet, Akkary et al., K. Aasaraai, Michael Black, etc.).[carece de fontes]?

A maioria dos preditores de desvio de ponta está usando um preditor por perceptron (ver a "Championship Branch Prediction Competition" da Intel). A Intel já implementa essa ideia em um dos simuladores do IA-64 (2003).

O processador multi-core AMD Ryzen e a Infinity Fabric e os processadores Samsung Exynos incluem preditores de desvio neurais baseados em perceptron.

História

O IBM 7030 Stretch, projetado no final da década de 1950, pré-executa todos os desvios incondicionais e quaisquer desvios condicionais que dependessem dos registradores de índice. Para outros desvios condicionais, os dois primeiros modelos de produção implementaram a previsão de não tomado; modelos subsequentes foram alterados para implementar predições baseadas nos valores atuais dos bits indicadores (correspondendo aos códigos de condição de hoje). Os projetistas do Stretch consideraram bits de dica estáticos nas instruções de desvio no início do projeto, mas decidiram contra eles. A recuperação de predição incorreta era fornecida pela unidade de lookahead no Stretch, e parte da reputação do Stretch de desempenho menos que estelar foi atribuída ao tempo necessário para a recuperação de predição incorreta. Projetos subsequentes de grandes computadores da IBM não usaram predição de desvio com execução especulativa até o IBM 3090 em 1985.

Preditores de dois bits foram introduzidos por Tom McWilliams e Curt Widdoes em 1977 para o supercomputador S-1 do Lawrence Livermore National Lab e, independentemente, por Jim Smith em 1979 na CDC.

Processadores microprogramados, populares de 1960 a 1980 e além, levavam múltiplos ciclos por instrução e geralmente não exigiam predição de desvio. No entanto, além do IBM 3090, há vários outros exemplos de projetos microprogramados que incorporaram predição de desvio.

O Burroughs B4900, uma máquina COBOL microprogramada lançada por volta de 1982, era pipelineada e usava predição de desvio. O estado de histórico de predição de desvio do B4900 é armazenado de volta nas instruções em memória durante a execução do programa. O B4900 implementa predição de desvio de 4 estados usando 4 opcodes de desvio semanticamente equivalentes para representar cada tipo de operador de desvio. O opcode usado indicava o histórico daquela instrução de desvio particular. Se o hardware determina que o estado de predição de desvio de um desvio particular precisa ser atualizado, ele reescreve o opcode com o opcode semanticamente equivalente que indicava o histórico adequado. Esse esquema obtém uma taxa de acerto de 93%. US patent 4,435,756 e outros foram concedidos sobre esse esquema.

O DEC VAX 9000, anunciado em 1989, é tanto microprogramado quanto pipelineado, e realiza predição de desvio.

Os primeiros processadores RISC comerciais, o MIPS R2000 e R3000 e os primeiros processadores SPARC, fazem apenas predição de desvio trivial "não tomado". Como eles usam slots de atraso de desvio, buscavam apenas uma instrução por ciclo e executam em ordem, não há perda de desempenho. O R4000 posterior usa a mesma predição de desvio trivial "não tomado" e perde dois ciclos para cada desvio tomado porque a recorrência de resolução do desvio tem quatro ciclos de duração.

A predição de desvio tornou-se mais importante com a introdução de processadores superescalares pipelineados como o Intel Pentium, DEC Alpha 21064, o MIPS R8000 e a série IBM POWER. Esses processadores todos dependem de preditores de um bit ou bimodais simples.

O DEC Alpha 21264 (EV6) usa um preditor de próxima linha substituído por um preditor local combinado e um preditor global, onde a escolha combinada é feita por um preditor bimodal.

O AMD K8 tem um preditor bimodal e global combinado, onde a escolha combinada é outro preditor bimodal. Esse processador armazena em cache os contadores do preditor bimodal base e de escolha em bits da cache L2, de outra forma usados para ECC. Como resultado, ele tem efetivamente tabelas de preditor base e de escolha muito grandes, e paridade em vez de ECC em instruções na cache L2. O design de paridade é suficiente, uma vez que qualquer instrução que sofra um erro de paridade pode ser invalidada e rebuscada da memória.

O Alpha 21464 (EV8, cancelado tardiamente no projeto) tinha uma penalidade mínima de predição incorreta de desvio de 14 ciclos. Ele deveria usar um preditor de próxima linha complexo, mas rápido, substituído por um preditor bimodal combinado e de voto majoritário. O voto majoritário era entre o bimodal e dois preditores gskew.

Em 2018, uma vulnerabilidade de segurança catastrófica chamada Spectre foi tornada pública pelo Project Zero do Google e outros pesquisadores. Afetando virtualmente todas as CPUs modernas, a vulnerabilidade envolve preparar os preditores de desvio para que outro processo (ou o kernel) prediga incorretamente um desvio e use dados secretos como índice de array, despejando uma das linhas de cache do atacante. O atacante pode cronometrar o acesso ao próprio array para descobrir qual delas, transformando esse estado interno (microarquitetural) da CPU em um valor que o atacante pode salvar e que tem informação sobre valores que ele não poderia ler diretamente.

Ver também

Referências

  1. 1 2 3 «Dynamic Branch Prediction». Consultado em 22 de março de 2017. Arquivado do original em 17 de julho de 2019
  2. 1 2 «The Schemes and Performances of Dynamic Branch predictors» (PDF)
  3. ↑ «Branch Prediction Techniques and Optimizations» (PDF). Consultado em 2 de abril de 2017. Arquivado do original (PDF) em 16 de maio de 2017
  4. ↑ «18-447 Computer Architecture Lecture 11: Branch Prediction» (PDF). 11 de fevereiro de 2013. Arquivado do original (PDF) em 25 de março de 2015
  5. ↑ Skewed branch predictors. HAL (Relatório). Setembro de 1996
  6. ↑ Eyerman, S.; Smith, J.E.; Eeckhout, L. (2006). Characterizing the branch misprediction penalty. 2006 IEEE International Symposium on Performance Analysis of Systems and Software. IEEE. pp. 48–58. ISBN 1-4244-0186-0. doi:10.1109/ispass.2006.1620789
  7. ↑ Modern processor design: fundamentals of superscalar processors. Boston: McGraw-Hill Higher Education. 2005. pp. 455. ISBN 0-07-057064-7
  8. ↑ «The RISC-V Instruction Set Manual Volume I Unprivileged Architecture». Google Docs
  9. 1 2 3 4 5 6 «The microarchitecture of Intel, AMD, and VIA CPUs» (PDF). 1 de dezembro de 2016. pp. 26, 38. Consultado em 22 de março de 2017
  10. ↑ «The Pentium 4 and the G4e: an Architectural Comparison». Ars Technica. 12 de maio de 2001
  11. ↑ «CMSC 611: Advanced Computer Architecture, Chapter 4 (Part V)»
  12. 1 2 3 «Combining Branch Predictors» (PDF). Junho de 1993. Digital Western Research Lab (WRL) Technical Report, TN-36
  13. ↑ «New Algorithm Improves Branch Prediction: 3/27/95» (PDF). Microprocessor Report. 9 (4). 27 de março de 1995. Consultado em 2 de fevereiro de 2016. Arquivado do original (PDF) em 10 de março de 2015
  14. ↑ «Two-Level Adaptive Training Branch Prediction». Proceedings of the 24th annual international symposium on Microarchitecture. Albuquerque, New Mexico, Puerto Rico: ACM. 1991. pp. 51–61. doi:10.1145/123465.123475Acessível livremente
  15. ↑ Fog, Agner. «Branch prediction in the Pentium family». Dr. Dobb's Journal. Arquivado do original em 13 de maio de 2008
  16. ↑ Egan, Colin; Steven, Gordon; Quick, P.; Anguera, R.; Vintan, Lucian (Dezembro de 2003). «Two-Level Branch Prediction using Neural Networks». Journal of Systems Architecture. 49 (12–15): 557–570. doi:10.1016/S1383-7621(03)00095-X
  17. ↑ «A Taxonomy of Branch Mispredictions, and Alloyed Prediction as a Robust Solution to Wrong-History Mispredictions» (PDF). Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques. Philadelphia. Outubro de 2000. pp. 199–206. doi:10.1109/PACT.2000.888344
  18. ↑ «The Agree Predictor: A Mechanism for Reducing Negative Branch History Interference» (PDF). Proceedings of the 24th International Symposium on Computer Architecture. Denver. Junho de 1997. doi:10.1145/264107.264210
  19. ↑ «Cortex-A15 MPCore Technical Reference Manual, section 6.5.3 "Indirect predictor"». ARM Holdings
  20. ↑ «Limits of Indirect Branch Prediction» (PDF). 25 de junho de 1997. Arquivado do original (PDF) em 6 de maio de 2016
  21. ↑ «A Look at Centrino's Core: The Pentium M». 25 de fevereiro de 2004. pp. 2–3
  22. ↑ «Performance Analysis for Core 2 and K8: Part 1». 28 de outubro de 2008. p. 5
  23. ↑ z/Architecture Principles of Operation (PDF) Fourteenth ed. [S.l.]: IBM. Maio de 2022. pp. 7–42 – 7–45. SA22-7832-13
  24. ↑ «IBM zEnterprise BC12 Technical Guide» (PDF). IBM. Fevereiro de 2014. p. 78
  25. ↑
  26. ↑ «Towards a High Performance Neural Branch Predictor» (PDF). Proceedings International Journal Conference on Neural Networks (IJCNN). 1999. doi:10.1109/IJCNN.1999.831066. Consultado em 2 de dezembro de 2010. Arquivado do original (PDF) em 13 de julho de 2019
  27. ↑ «Towards a Powerful Dynamic Branch Predictor» (PDF). Bucharest: Romanian Academy. Romanian Journal of Information Science and Technology. 3 (3): 287–301. 2000. ISSN 1453-8245
  28. 1 2 «Dynamic Branch Prediction with Perceptrons» (PDF). Proceedings of the 7th International Symposium on High Performance Computer Architecture (HPCA-7). Monterrey, NL, Mexico. 2001. pp. 197–296. doi:10.1109/HPCA.2001.903263
  29. ↑ «The AMD Trinity Review (A10-4600M): A New Hope». AnandTech. 15 de maio de 2012. Arquivado do original em 17 de maio de 2012
  30. 1 2 Fast Path-Based Neural Branch Prediction (PDF). San Diego, USA. Dezembro de 2003. pp. 243–252. doi:10.1109/MICRO.2003.1253199. Consultado em 8 de abril de 2018. Arquivado do original (PDF) em 31 de março de 2016
  31. ↑ «Championship Branch Prediction»
  32. ↑ «Hierarchical scheduling windows». Proceedings of the 35th International Symposium on Microarchitecture. Istanbul, Turkey. Dezembro de 2002. doi:10.1109/MICRO.2002.1176236
  33. ↑ «AMD Ryzen reviews, news, performance, pricing, and availability». PCGamesN. 6 de dezembro de 2017
  34. ↑ «AMD Takes Computing to a New Horizon with Ryzen™ Processors» (Nota de imprensa). AMD. Consultado em 14 de dezembro de 2016
  35. ↑ «AMD's Zen CPU is now called Ryzen, and it might actually challenge Intel». Ars Technica UK. Consultado em 14 de dezembro de 2016
  36. ↑ «IBM Stretch (7030) -- Aggressive Uniprocessor Parallelism»
  37. ↑ «S-1 Supercomputer»
  38. ↑ Murray, J.E.; Salett, R.M.; Hetherington, R.C.; McKeen, F.X. (1990). «Micro-architecture of the VAX 9000». Digest of Papers Compcon Spring '90. Thirty-Fifth IEEE Computer Society International Conference on Intellectual Leverage. pp. 44–53. ISBN 0-8186-2028-5. doi:10.1109/CMPCON.1990.63652
  39. 1 2 Seznec, A.; Felix, S.; Krishnan, V.; Sazeides, Y. «Design Tradeoffs for the Alpha EV8 Conditional Branch Predictor». Proceedings 29th Annual International Symposium on Computer Architecture. doi:10.1109/ISCA.2002.1003587
  40. ↑ Gibbs, Samuel (4 de janeiro de 2018). «Meltdown and Spectre: 'worst ever' CPU bugs affect virtually all computers». the Guardian (em inglês). Consultado em 18 de maio de 2018

Ligações externas