Pipeline (hardware)

Pipeline básico de cinco estágios
Ciclo de clock
Nº da Instr.
1 2 3 4 5 6 7
1 IF ID EX MEM WB
2 IF ID EX MEM WB
3 IF ID EX MEM WB
4 IF ID EX MEM
5 IF ID EX
(IF = Instruction Fetch, ID = Instruction Decode, EX = Execute, MEM = Memory access, WB = Register write back).

No quarto ciclo de clock (a coluna verde), a instrução mais antiga está no estágio MEM, e a instrução mais recente ainda não entrou no pipeline.

Na engenharia de computadores, o pipeline de instruções é uma técnica para implementar paralelismo em nível de instrução dentro de um único processador. O pipeline tenta manter cada parte do processador ocupada com alguma instrução, dividindo as instruções recebidas em uma série de etapas sequenciais (o homônimo "pipeline") executadas por diferentes unidades do processador, com diferentes partes das instruções processadas em paralelo.

Conceito e motivação

Em um computador com pipeline, as instruções viajam pela unidade central de processamento (CPU) em estágios. Por exemplo, pode haver um estágio para cada passo do ciclo de von Neumann: Buscar a instrução, buscar os operandos, executar a instrução, escrever os resultados. Um computador com pipeline geralmente tem "registradores de pipeline" após cada estágio. Estes armazenam informações da instrução e dos cálculos, para que as portas lógicas do próximo estágio possam executar o passo seguinte.

Esse arranjo permite que a CPU complete uma instrução a cada ciclo de clock. É comum que estágios de número par operem em uma borda do clock de onda quadrada, enquanto estágios de número ímpar operem na outra borda. Isso permite mais vazão de CPU que um computador multiciclo em uma dada frequência de clock, mas pode aumentar a latência devido à sobrecarga adicional do próprio processo de pipeline. Além disso, embora a lógica eletrônica tenha uma velocidade máxima fixa, um computador com pipeline pode ser feito mais rápido ou mais lento variando o número de estágios no pipeline. Com mais estágios, cada estágio faz menos trabalho, e assim o estágio tem menos atrasos das portas lógicas e pode rodar a uma frequência de clock mais alta.

Um modelo de computador com pipeline é frequentemente o mais econômico, quando o custo é medido como portas lógicas por instrução por segundo. Em cada instante, uma instrução está em apenas um estágio do pipeline, e, em média, um estágio do pipeline é menos custoso que um computador multiciclo. Além disso, quando bem feito, a maior parte da lógica do computador com pipeline está em uso na maior parte do tempo. Em contraste, computadores fora de ordem geralmente têm grandes quantidades de lógica ociosa em qualquer instante. Cálculos semelhantes geralmente mostram que um computador com pipeline usa menos energia por instrução.

No entanto, um computador com pipeline geralmente é mais complexo e mais caro que um computador multiciclo comparável. Tipicamente tem mais portas lógicas, registradores e uma unidade de controle mais complexa. De forma semelhante, pode usar mais energia total, enquanto usa menos energia por instrução. CPUs fora de ordem geralmente conseguem fazer mais instruções por segundo porque podem fazer várias instruções ao mesmo tempo.

Em um computador com pipeline, a unidade de controle organiza o fluxo para iniciar, continuar e parar conforme um programa comanda. Os dados das instruções geralmente são passados em registradores de pipeline de um estágio para o próximo, com uma peça um tanto separada de lógica de controle para cada estágio. A unidade de controle também assegura que a instrução em cada estágio não prejudique a operação das instruções em outros estágios. Por exemplo, se dois estágios precisam usar a mesma peça de dados, a lógica de controle assegura que os usos sejam feitos na sequência correta.

Quando operando eficientemente, um computador com pipeline terá uma instrução em cada estágio. Ele então estará trabalhando em todas essas instruções ao mesmo tempo. Ele pode terminar cerca de uma instrução por ciclo de seu clock. Mas quando um programa muda para uma sequência diferente de instruções, o pipeline às vezes precisa descartar os dados em processamento e reiniciar. Isso é chamado de "stall".

Boa parte do projeto de um computador com pipeline evita interferência entre os estágios e reduz stalls.

Número de etapas

O número de etapas dependentes varia com a arquitetura da máquina. Por exemplo:

  • O projeto IBM Stretch de 1956–61 propôs os termos Fetch, Decode e Execute que se tornaram comuns.
  • O pipeline RISC clássico compreende:
    1. Busca da instrução
    2. Decodificação da instrução e busca de registrador
    3. Execução
    4. Acesso à memória
    5. Escrita de volta no registrador
  • O Atmel AVR e o microcontrolador PIC têm cada um um pipeline de dois estágios.
  • Muitos projetos incluem pipelines tão longos quanto 7, 10 e até 20 estágios (como no Intel Pentium 4).
  • Os núcleos NetBurst posteriores "Prescott" e "Cedar Mill" da Intel, usados nos últimos modelos Pentium 4 e seus derivados Pentium D e Xeon, têm um longo pipeline de 31 estágios.
  • O processador de rede Xelerated X10q tem um pipeline com mais de mil estágios, embora, nesse caso, 200 desses estágios representem CPUs independentes com instruções programadas individualmente. Os estágios restantes são usados para coordenar acessos à memória e unidades funcionais no chip.

À medida que o pipeline se torna "mais profundo" (com um número maior de etapas dependentes), uma dada etapa pode ser implementada com circuitos mais simples, o que pode permitir que o clock do processador rode mais rápido. Tais pipelines podem ser chamados de superpipelines.

Diz-se que um processador é totalmente pipelineado se ele pode buscar uma instrução a cada ciclo. Assim, se algumas instruções ou condições exigem atrasos que inibem a busca de novas instruções, o processador não é totalmente pipelineado.

História

Os usos seminais do pipeline foram no projeto ILLIAC II e no projeto IBM Stretch, embora uma versão simples tenha sido usada antes no Z1 em 1939 e no Z3 em 1941.

O pipeline começou em earnest no final da década de 1970 em supercomputadores como processadores vetoriais e processadores de array.[carece de fontes]? Um dos primeiros supercomputadores foi a série Cyber, construída pela Control Data Corporation. Seu principal arquiteto, Seymour Cray, mais tarde chefiou a Cray Research. Cray desenvolveu a linha XMP de supercomputadores, usando pipeline tanto para funções de multiplicação quanto de adição/subtração. Mais tarde, a Star Technologies adicionou paralelismo (várias funções em pipeline trabalhando em paralelo), desenvolvido por Roger Chen. Em 1984, a Star Technologies adicionou o circuito de divisão em pipeline desenvolvido por James Bradley.

O pipeline não se limitou aos supercomputadores. Em 1976, o mainframe de uso geral da série 470 da Amdahl Corporation tinha um pipeline de 7 etapas e um circuito patenteado de predição de desvio.[carece de fontes]? Um elemento central da filosofia de projeto RISC, em meados da década de 1980, o pipeline também estava sendo introduzido nas arquiteturas CISC tradicionais por seus desenvolvedores.

Hazards

O modelo de execução sequencial assume que cada instrução é completada antes que a próxima comece; essa suposição não é verdadeira em um processador com pipeline. Uma situação em que o resultado esperado é problemático é conhecida como um hazard. Imagine as duas instruções de registrador a seguir para um processador hipotético:

1: somar 1 a R5
2: copiar R5 para R6

Se o processador tiver as 5 etapas listadas na ilustração inicial (o 'Pipeline básico de cinco estágios' no início do artigo), a instrução 1 seria buscada em t1 e sua execução seria completada em t5. A instrução 2 seria buscada em t2 e seria completada em t6. A primeira instrução poderia depositar o número incrementado em R5 como sua quinta etapa (escrita de volta no registrador) em t5. Mas a segunda instrução poderia obter o número de R5 (para copiar para R6) em sua segunda etapa (decodificação da instrução e busca de registrador) em t3. Parece que a primeira instrução não teria incrementado o valor até então. O código acima invoca um hazard.

Escrever programas de computador em uma linguagem compilada pode não levantar essas preocupações, pois o compilador poderia ser projetado para gerar código de máquina que evita hazards.

Soluções alternativas

Em alguns primeiros processadores DSP e RISC, a documentação aconselha os programadores a evitar tais dependências em instruções adjacentes e quase adjacentes (chamadas de slots de atraso), ou declara que a segunda instrução usa um valor antigo em vez do valor desejado (no exemplo acima, o processador poderia, contra-intuitivamente, copiar o valor não incrementado), ou declara que o valor que usa é indefinido. O programador pode ter trabalho não relacionado que o processador pode fazer enquanto isso; ou, para garantir resultados corretos, o programador pode inserir NOPs no código, negando parcialmente as vantagens do pipeline.

Soluções

Processadores com pipeline comumente usam três técnicas para funcionar conforme esperado quando o programador assume que cada instrução é completada antes que a próxima comece:

  • O pipeline poderia travar, ou cessar de agendar novas instruções até que os valores necessários estejam disponíveis. Isso resulta em slots vazios no pipeline, ou bolhas, nos quais nenhum trabalho é realizado.
  • Um caminho de dados adicional pode ser adicionado que roteia um valor computado para uma instrução futura em outro lugar no pipeline antes que a instrução que o produziu tenha sido totalmente retirada, um processo chamado encaminhamento de operandos.
  • O processador pode localizar outras instruções que não dependem das atuais e que podem ser imediatamente executadas sem hazards, uma otimização conhecida como execução fora de ordem.

Desvios

Um desvio fora da sequência normal de instruções frequentemente envolve um hazard. A menos que o processador possa dar efeito ao desvio em um único ciclo de tempo, o pipeline continuará buscando instruções sequencialmente. Tais instruções não podem ser permitidas a ter efeito, porque o programador desviou o controle para outra parte do programa.

Um desvio condicional é ainda mais problemático. O processador pode ou não desviar, dependendo de um cálculo que ainda não ocorreu. Vários processadores podem travar, podem tentar a predição de desvio e podem ser capazes de começar a executar duas sequências de programa diferentes (execução ávida), cada uma assumindo que o desvio é ou não tomado, descartando todo o trabalho que pertence à suposição incorreta.

Um processador com uma implementação de predição de desvio que geralmente faz predições corretas pode minimizar a penalidade de desempenho do desvio. No entanto, se os desvios forem previstos pobremente, isso pode criar mais trabalho para o processador, como descartar do pipeline o caminho de código incorreto que começou a ser executado antes de retomar a execução no local correto.

Programas escritos para um processador com pipeline evitam deliberadamente desvios, para minimizar possível perda de velocidade. Por exemplo, o programador pode lidar com o caso usual com execução sequencial e desviar apenas ao detectar casos incomuns. Usar programas como o gcov para analisar a cobertura de código permite ao programador medir com que frequência desvios particulares são realmente executados e obter insight com o qual otimizar o código. Em alguns casos, um programador pode lidar tanto com o caso usual quanto com o caso incomum com código sem desvio.

Situações especiais

Programas automodificáveis
A técnica de código automodificável pode ser problemática em um processador com pipeline. Nesta técnica, um dos efeitos de um programa é modificar suas próprias próximas instruções. Se o processador tiver um cache de instruções, a instrução original pode já ter sido copiada para uma fila de entrada de pré-busca e a modificação não terá efeito. Alguns processadores como o Zilog Z280 podem configurar suas memórias de cache no chip para buscas somente de dados, ou como parte de seu espaço de endereço de memória comum, e evitar tais dificuldades com instruções automodificáveis.
Instruções não interrompíveis
Uma instrução pode ser não interrompível para garantir sua atomicidade, como quando ela troca dois itens. Um processador sequencial permite interrupções entre instruções, mas um processador com pipeline sobrepõe instruções, então executar uma instrução não interrompível torna porções de instruções ordinárias não interrompíveis também. O Cyrix coma bug travaria um sistema de núcleo único usando um loop infinito no qual uma instrução não interrompível estava sempre no pipeline.

Considerações de projeto

Velocidade
O pipeline mantém todas as porções do processador ocupadas e aumenta a quantidade de trabalho útil que o processador pode fazer em um dado tempo. O pipeline tipicamente reduz o tempo de ciclo do processador e aumenta a vazão de instruções. A vantagem de velocidade é diminuída na medida em que a execução encontra hazards que exigem que a execução desacelere abaixo de sua taxa ideal. Um processador sem pipeline executa apenas uma única instrução por vez. O início da próxima instrução é atrasado não com base em hazards, mas incondicionalmente.
A necessidade de um processador com pipeline de organizar todo o seu trabalho em etapas modulares pode exigir a duplicação de registradores, o que aumenta a latência de algumas instruções.
Economia
Ao tornar cada etapa dependente mais simples, o pipeline pode possibilitar operações complexas mais economicamente do que adicionar circuitos complexos, como para cálculos numéricos. No entanto, um processador que recusa buscar aumento de velocidade com pipeline pode ser mais simples e mais barato de fabricar.
Previsibilidade
Comparado a ambientes onde o programador precisa evitar ou contornar hazards, o uso de um processador sem pipeline pode tornar mais fácil programar e treinar programadores. O processador sem pipeline também torna mais fácil prever o timing exato de uma dada sequência de instruções.

Exemplo ilustrado

À direita está um pipeline genérico com quatro estágios: busca, decodificação, execução e escrita de volta. A caixa cinza superior é a lista de instruções esperando para serem executadas, a caixa cinza inferior é a lista de instruções que tiveram sua execução concluída, e a caixa branca do meio é o pipeline.

A execução é a seguinte:

Pipeline genérico de 4 estágios; as caixas coloridas representam instruções independentes entre si
ClockExecução
0
  • Quatro instruções estão esperando para serem executadas
1
  • A instrução verde é buscada da memória
2
  • A instrução verde é decodificada
  • A instrução roxa é buscada da memória
3
  • A instrução verde é executada (a operação real é realizada)
  • A instrução roxa é decodificada
  • A instrução azul é buscada
4
  • Os resultados da instrução verde são escritos de volta no banco de registradores ou na memória
  • A instrução roxa é executada
  • A instrução azul é decodificada
  • A instrução vermelha é buscada
5
  • A execução da instrução verde é concluída
  • A instrução roxa é escrita de volta
  • A instrução azul é executada
  • A instrução vermelha é decodificada
6
  • A execução da instrução roxa é concluída
  • A instrução azul é escrita de volta
  • A instrução vermelha é executada
7
  • A execução da instrução azul é concluída
  • A instrução vermelha é escrita de volta
8
  • A execução da instrução vermelha é concluída
9
  • A execução de todas as quatro instruções é concluída

Bolha de pipeline

Uma bolha no ciclo 3 atrasa a execução.

Um processador com pipeline pode lidar com hazards travando e criando uma bolha no pipeline, resultando em um ou mais ciclos nos quais nada útil acontece.

Na ilustração à direita, no ciclo 3, o processador não pode decodificar a instrução roxa, talvez porque o processador determina que a decodificação depende de resultados produzidos pela execução da instrução verde. A instrução verde pode prosseguir para o estágio Execute e depois para o estágio Write-back conforme agendado, mas a instrução roxa é travada por um ciclo no estágio Fetch. A instrução azul, que deveria ser buscada durante o ciclo 3, é travada por um ciclo, assim como a instrução vermelha depois dela.

Por causa da bolha (as ovais azuis na ilustração), o circuito de Decode do processador fica ocioso durante o ciclo 3. Seu circuito de Execute fica ocioso durante o ciclo 4 e seu circuito de Write-back fica ocioso durante o ciclo 5.

Quando a bolha sai do pipeline (no ciclo 6), a execução normal é retomada. Mas tudo agora está um ciclo atrasado. Levará 8 ciclos (ciclo 1 a 8) em vez de 7 para executar completamente as quatro instruções mostradas em cores.

Meltdown

Em janeiro de 2018, foi publicada uma falha relacionada com a leitura de memória protegida do núcleo (kernel), por meio da exploração da arquitetura de processadores Intel em segmentação de instruções. A falha permite que algoritmos maliciosos tenham acesso à trechos de memória, tais como senhas e outras informações protegidas, por meio da tentativa do acesso explicito a ela devido ao empilhamento e execução das instruções antes de descartá-las. Esse acesso será negado posteriormente pela unidade de controle, contudo sua execução ficará armazenada em cache, tornando-a acessível.

Os updates em softwares para correção desse bug de hardware praticamente desativam a técnica de pipeline nos processadores, comprometendo em até 30% de seu desempenho.

Ver também