Execução fora de ordem (ou, mais formalmente, execução dinâmica) é um paradigma de escalonamento de instruções utilizado em unidades centrais de processamento (CPUs) de alto desempenho para aproveitar ciclos de instrução que, de outro modo, seriam desperdiçados. Sob este paradigma, o processador executa instruções em uma ordem ditada pela disponibilidade de seus dados de entrada e de unidades de execução disponíveis, em vez de seguir estritamente a ordem sequencial original do programa. Dessa forma, o processador evita permanecer ocioso enquanto aguarda a conclusão da instrução anterior, adiantando o processamento de instruções subsequentes que já estejam aptas a serem executadas de forma imediata e independente.
História A execução fora de ordem é uma forma restrita de arquitetura de fluxo de dados, que constituiu uma importante área de pesquisa em arquitetura de computadores durante a década de 1970 e o início da década de 1980.
Uso pioneiro em supercomputadores Considera-se que a primeira máquina a implementar a execução fora de ordem foi o CDC 6600 (1964), que empregava um quadro de pontuação (scoreboard) para resolver conflitos de dados. O 6600, contudo, não realizava o tratamento de conflitos WAW (escrita após escrita), optando por paralisar o pipeline (stall). Essa condição foi denominada "conflito de primeira ordem" por Thornton. Embora dispusesse de resolução tanto para conflitos RAW ("conflito de segunda ordem") quanto para conflitos WAR ("conflito de terceira ordem") — mecanismos suficientes para caracterizá-lo como um sistema plenamente capaz de execução fora de ordem —, o CDC 6600 não oferecia suporte a exceções precisas. Uma variante embrionária e limitada de previsão de saltos era possível, desde que o desvio ocorresse para instruções situadas na chamada "pilha de instruções" (Instruction Stack), restrita a uma profundidade de até sete palavras a partir do contador de programa.
Cerca de dois anos depois, o IBM System/360 Modelo 91 (1966) introduziu a renomeação de registradores com o algoritmo de Tomasulo, que elimina dependências falsas (conflitos WAW e WAR), viabilizando uma execução fora de ordem abrangente. Uma instrução cujo destino seja a escrita no registrador rn pode ser executada antes de uma instrução prévia que leia o mesmo registrador rn, gravando o resultado em um registrador renomeado alternativo alt-rn; este é promovido a registrador arquitetural oficial rn somente após todas as instruções anteriores dependentes de rn terem concluído a leitura, preservando a coerência dos dados para instruções passadas e futuras.
No Modelo 91, a renomeação de registradores foi implementada por meio de um mecanismo de encaminhamento de operandos denominado Common Data Bus (CDB, barramento comum de dados) e de buffers de operandos de memória. Essa abordagem mantinha os registradores arquiteturais físicos ociosos durante vários ciclos, visto que o valor mais atualizado requerido por qualquer instrução pendente encontrava-se em trânsito no CDB. Outra vantagem do Modelo 91 sobre o 6600 residia na capacidade de executar instruções fora de ordem dentro da mesma unidade de execução, e não apenas entre unidades distintas. Isso era viabilizado por meio de estações de reserva, das quais as instruções eram despachadas para a unidade funcional assim que seus operandos estivessem prontos, em contraste com a fila FIFO de cada unidade no 6600. O Modelo 91 também era capaz de reordenar operações de leitura (loads) e escrita (stores) em relação a leituras e escritas precedentes, diferentemente do CDC 6600, cuja flexibilidade se restringia a adiantar leituras diante de leituras e escritas diante de escritas, sem cruzar operações de naturezas distintas. Todavia, apenas os registradores de ponto flutuante do Modelo 91 eram renomeados, sujeitando as operações de ponto fixo (números inteiros) às mesmas limitações de conflitos WAW e WAR do CDC 6600. Além disso, tanto o 91 quanto o 6600 sofriam com exceções imprecisas, um obstáculo que precisou ser solucionado para que a execução fora de ordem se tornasse viável em computadores de uso geral fora do domínio dos supercomputadores.
Exceções precisas Para que um processador ofereça suporte a exceções precisas, o estado arquitetural consistente do programa deve ser integralmente recuperável no momento em que ocorre uma exceção. Em meados de 1985, diversas abordagens foram consolidadas e descritas por James E. Smith e Andrew R. Pleszkun.(Versão expandida publicada em maio de 1988 como Implementing Precise Interrupts in Pipelined Processors.) O CDC Cyber 205 foi um precursor ao salvar todo o estado interno da máquina (incluindo metadados de instruções parcialmente executadas) em um "pacote de troca invisível" (invisible exchange package) diante de interrupções de memória virtual, permitindo que a execução fosse retomada exatamente do mesmo ponto. Contudo, para garantir precisão em qualquer exceção, tornou-se mandatória a capacidade de desfazer ou descartar os efeitos colaterais de instruções executadas especulativamente. O CDC Cyber 990 (1984) implementou interrupções precisas mediante o uso de um buffer de histórico (history buffer), que retinha os valores originais sobrescritos dos registradores, restaurando-os quando uma exceção exigia a anulação de instruções. Por meio de simulações, Smith determinou que a adição de um buffer de reordenamento (ou buffer de histórico equivalente) ao Cray-1S degradaria o desempenho de execução dos primeiros 14 laços de Livermore (sem vetorização) em apenas 3%. Pesquisas acadêmicas fundamentais nessa área foram conduzidas por Yale Patt com o desenvolvimento do simulador HPSm.
Na década de 1980, muitos microprocessadores com arquitetura RISC realizavam a reescrita de resultados nos registradores (writeback) fora de ordem, o que resultava invariavelmente em exceções imprecisas. O Motorola 88100 destacou-se como um dos raros microprocessadores pioneiros a não sofrer de exceções imprecisas em operações inteiras apesar das escritas fora de ordem, embora ainda admitisse exceções de ponto flutuante tanto precisas quanto imprecisas. As instruções iniciavam o processamento em ordem, mas aquelas com maior latência (como operações de ponto flutuante) exigiam mais ciclos para finalizar. Contudo, a execução em ciclo único da maioria das instruções básicas atenuou consideravelmente o impacto do problema em relação ao cenário enfrentado pelo CDC 6600.
Desacoplamento Smith também investigou métodos para desacoplar as unidades de execução entre si e isolá-las do subsistema de memória, do front-end e do fluxo de desvios. Tais conceitos foram implementados no processador Astronautics ZS-1 (1988), da Astronautics Corporation of America, que apresentava um desacoplamento entre o pipeline de inteiros/leitura/escrita e o pipeline de ponto flutuante, permitindo a reordenação entre pipelines distintos. O ZS-1 também viabilizava a execução de operações de leitura à frente de escritas anteriores na memória. Em seu artigo de 1984, Smith sustentou que impor exceções precisas apenas ao pipeline de inteiros e memória seria suficiente para a maior parte dos casos de uso, garantindo inclusive o suporte pleno à memória virtual. Cada pipeline dispunha de um buffer de instruções que o isolava do decodificador, evitando paralisações no front-end. Para mitigar ainda mais o impacto da latência de memória, cada um dos dois pipelines operava com duas filas FIFO endereçáveis que, na prática, atuavam como uma forma elementar de renomeação de registradores. Estrutura desacoplada similar havia sido introduzida pouco antes pelo Culler 7. O conjunto de instruções do ZS-1, a exemplo do posterior POWER da IBM, facilitava o processamento antecipado de desvios condicionais.
Da pesquisa à aplicação prática Com o lançamento do POWER1 (1990), a IBM retomou o uso da execução fora de ordem. O processador foi o primeiro a combinar renomeação de registradores (ainda que restrita ao bloco de ponto flutuante) com exceções precisas. Empregava um arquivo de registradores físicos estendido (com mapeamento dinâmico contendo tanto valores consolidados quanto especulativos) em substituição ao buffer de reordenamento convencional. O cancelamento de instruções especulativas era necessário apenas na unidade de desvios, que utilizava um buffer de histórico (denominado program counter stack pela IBM) para reverter modificações nos registradores de contagem, ligação e condição. A capacidade de reordenação de instruções de ponto flutuante ainda era tímida: devido à incapacidade do POWER1 de reordenar instruções aritméticas de ponto flutuante (cujos resultados ficavam prontos estritamente em ordem), seus registradores de destino não eram renomeados. O processador também carecia de estações de reserva para a utilização fora de ordem dentro da mesma unidade de cálculo.
No ano seguinte, o mainframe IBM ES/9000 Modelo 900 estendeu a renomeação de registradores aos registradores de uso geral. O chip contava com estações de reserva de seis entradas para a unidade inteira dupla (selecionando e despachando até duas instruções por ciclo a partir de seis pendentes) e seis entradas para a FPU. As demais unidades operavam com filas FIFO simples, atingindo uma janela de reordenação de até 32 instruções. O processador A19 da Unisys, desenvolvido para a linha de mainframes da Série A, também foi lançado em 1991 incorporando execução fora de ordem; à época, analistas consideraram a tecnologia do A19 de três a cinco anos mais avançada do que a dos concorrentes diretos.
Ampla adoção comercial Os primeiros microprocessadores superescalares em chip único (como o Intel i960CA, lançado em 1989) utilizavam escalonamento baseado em quadro de pontuação simples, análogo ao do CDC 6600. Entre 1992 e 1996, o rápido avanço nas técnicas de projeto — impulsionado pelo aumento da densidade de transistores previsto pela Lei de Moore — viabilizou a disseminação dessa tecnologia até o segmento de computadores pessoais. O Motorola 88110 (1992) utilizava um buffer de histórico para reverter instruções mal-especuladas. Operações de leitura podiam ser executadas à frente de escritas pendentes; enquanto escritas e desvios aguardavam a inicialização, instruções subsequentes de outros tipos podiam fluir livremente pelos estágios do pipeline, inclusive pela reescrita. A capacidade de 12 entradas do buffer de histórico limitava a profundidade de reordenação.
O PowerPC 601 (1993), derivado do projeto RISC Single Chip, permitia que instruções de desvio e de ponto flutuante ultrapassassem instruções inteiras presentes na fila de busca, cujas quatro entradas inferiores eram analisadas dinamicamente para despacho. Em caso de falha de cache (cache miss), leituras e escritas podiam ser reordenadas; contudo, apenas os registradores de contagem e ligação podiam ser renomeados.Moore, Charles R.; Becker, Michael C. et al. No final de 1994, a NexGen e a aliança IBM-Motorola introduziram a renomeação de registradores de uso geral em microprocessadores integrados. O Nx586 da NexGen foi o primeiro processador da arquitetura x86 a executar instruções fora de ordem, oferecendo uma janela de reordenação de até 14 micro-operações (µops). O PowerPC 603 incorporou a renomeação de registradores tanto inteiros quanto de ponto flutuante; cada uma de suas quatro unidades funcionais podia reter uma instrução em espera sem bloquear as demais. Com um buffer de reordenamento de cinco entradas e um buffer de escrita dedicado, as leituras podiam consultar o cache à frente de escritas pendentes.