Execução Fora de Ordem

A execução fora de ordem permite que um processador execute instruções assim que seus operandos estejam prontos, em vez de estritamente na ordem do programa, usando renomeação de registradores e bufferização para expor o paralelismo, enquanto ainda produz resultados em ordem.

Definition

A execução fora de ordem é uma técnica microarquitetural na qual um processador reordena dinamicamente a execução de instruções para executar instruções independentes sempre que seus operandos estão disponíveis, enquanto usa bufferização e renomeação para preservar a aparência de conclusão sequencial e em ordem.

Scope

Este tópico abrange o escalonamento dinâmico: estações de reserva, renomeação de registradores para remover dependências falsas, o buffer de reordenação que impõe o commit em ordem e a recuperação de execução especulativa. Ele se baseia diretamente no algoritmo de Tomasulo. Exclui a previsão da direção de desvio (previsão de desvio) e a noção mais ampla de quanto paralelismo existe (paralelismo em nível de instrução), focando na própria maquinaria de reordenação.

Core questions

• Como um processador pode executar instruções fora da ordem do programa e ainda produzir resultados corretos e em ordem?
• Como a renomeação de registradores elimina as dependências de escrita após leitura e escrita após escrita?
• Qual a contribuição das estações de reserva e do buffer de reordenação?
• Como as exceções e previsões incorretas são recuperadas precisamente em um núcleo fora de ordem?

Key concepts

• escalonamento dinâmico
• estações de reserva
• renomeação de registradores
• barramento de dados comum
• buffer de reordenação
• commit em ordem
• exceções precisas
• recuperação de execução especulativa

Key theories

Algoritmo de Tomasulo

O esquema de Tomasulo utiliza estações de reserva e um barramento de dados comum para renomear registradores e despachar instruções para unidades funcionais à medida que seus operandos se tornam disponíveis, permitindo a execução fora de ordem que respeita apenas as verdadeiras dependências de dados.

Exceções precisas via commit em ordem

Um buffer de reordenação armazena os resultados de instruções fora de ordem e os confirma na ordem do programa, de modo que exceções e previsões incorretas possam ser tratadas precisamente como se a execução tivesse sido estritamente sequencial.

Mechanisms

As instruções decodificadas são renomeadas para registradores físicos e colocadas em estações de reserva ou em uma fila de emissão, onde aguardam os operandos transmitidos em um barramento de resultados. Quando prontas, elas são executadas em unidades funcionais disponíveis em qualquer ordem. Um buffer de reordenação rastreia a ordem original do programa e confirma os resultados sequencialmente, descartando resultados especulativos em caso de previsão incorreta ou exceção, de modo que o estado arquitetural seja sempre preciso.

Clinical relevance

A execução fora de ordem é o motor central das CPUs de alto desempenho, ocultando latências de memória e execução ao encontrar trabalho independente a ser feito. Ela também tem implicações de segurança: como o trabalho especulativo e fora de ordem pode acessar dados transitoriamente antes de ser descartado, isso possibilitou as classes de ataques de canal lateral microarquitetural Spectre e Meltdown.

History

Tomasulo introduziu o escalonamento dinâmico no IBM System/360 Modelo 91 em 1967. A combinação com o buffer de reordenação para exceções precisas, desenvolvida na década de 1980, tornou a execução fora de ordem prática para processadores de uso geral, e ela se tornou padrão em projetos de alto desempenho a partir de meados da década de 1990.

Debates

Desempenho versus complexidade, consumo de energia e segurança

A execução fora de ordem oferece forte desempenho de thread único, mas a um custo significativo em complexidade de hardware e consumo de energia, e sua especulação provou ser explorável; isso alimenta o debate sobre quão agressivamente especular versus favorecer designs mais simples, eficientes ou seguros.

Key figures

• Robert Tomasulo
• Yale Patt
• James E. Smith
• John L. Hennessy

Seminal works

• tomasulo1967
• hennessy2019

Frequently asked questions

Se as instruções são executadas fora de ordem, como o programa ainda está correto?

O processador apenas reordena a execução, não os resultados. A renomeação de registradores garante que ele respeite as verdadeiras dependências de dados, e um buffer de reordenação confirma os resultados na ordem original do programa, de modo que o estado arquitetural visível é exatamente o que a execução sequencial produziria.

O que é renomeação de registradores?

A renomeação de registradores mapeia os registradores arquiteturais nomeados nas instruções para um pool maior de registradores físicos. Isso remove dependências falsas (de nome) que surgem do reuso de nomes de registradores, permitindo que mais instruções independentes sejam executadas em paralelo sem conflitar sobre o armazenamento de registradores.