AOC – Pipeline II

Arquitetura e Organização de Computadores

Pipeline II

Na continuação de Pipeline, vou explicar o que são e como tratar os Hazards de Pipeline.

Hazards

Hazards são, como vimos no fim do post Pipeline I, situações que impedem o pipeline de continuar sua execução natural ou o fazem perder performance por computar incorretamnete. Existem três tipos de Hazards, são eles:

• Hazards Estruturais
• Hazards de Dados
• Hazards de Controle

1. Estruturais

Hazards Estruturais acontecem quando duas ou mais instruções sobrepostas no pipeline tentam usar o mesmo recurso de hardware ao mesmo tempo. Por exemplo se um processador possui memória compartilhada entre dados e instruções, em um momento em que o estágio MEM (referência à memória) e o estágio IF (busca uma instrução) ficam sobrepostos no pipeline, ocorre um hazard estrutural.

Isso pode ser simplesmente resolvido com o uso de bolhas no pipeline. Isso significa dizer que:

# É possível inserir “bolhas” (instruções sem operações) no pipeline e atrasar a execução da instrução atual até que o operando requerido seja computado corretamente e escrito no registrador. Esse método diminui a eficiência do pipeline, que é totalmente o oposto da idéia do próprio pipeline, mas mesmo assim, é uma estratégia válida porque reduz o custo de memória quase que pela metade em uma máquina que suporta acesso à memória e à instruções a cada estágio do pipeline para evitar o hazard, por exemplo.

2. De Dados

Hazards de Dados acontecem quando uma instrução depende no resultado de uma instrução anterior de modo que a primeira instrução ainda não computou esse resultado. Como por exemplo:

ADD R1, R2, R4         ; Instrução 1
SUB R4, R5, R1          ; Instrução 2
AND R6, R1, R7         ; Instrução 3
OR R8, R1, R9            ; Instrução 4
XOR R10, R1, R1  1   ; Instrução 5
(Instruções de processadores da arquitetura RISC, onde Rn são registradores)

Nesse caso, R1 só é escrito no último estágio de execução da instrução 1, mas já é usado no segundo estágio da instrução 2. Veja:

ADD	R1, R2, R3	IF	ID	EX	MEM	WB
SUB	R4, R5, R1		IF	ID	EX	MEM	WB

A tabela acima ilustra bem essa situação no caso RAW. O estágio de Decodificação (ID) da instrução SUB precisa do valor de R1, mas esse valor não vai ser computado até o estágio WB (Writeback), onde a instrução ADD faz escrita no registrador.

Existem três tipos de Hazards de Dados:
– Imaginem duas instruções 1 e 2. 

• RAW (Read After Write – Leitura depois da escrita): Também chamado de Hazard de Dependência, ocorre quando a instrução 2 usa o resultado da instrução 1 que ainda não foi calculado ou buscado.Isso ocorre porque mesmo que a instrução 2 venha depois da instrução 1, no pipeline ela é executada simultaneamente, como no nosso exemplo da tabela acima.Outro exemplo:

   SUB R1, R2, R3  ; Instrução 1
  ADD R4, R1, R3  ; Instrução 2

• WAR (Write After Read – Escrita depois da leitura) : Também chamado de Hazard de Anti Dependência, ocorre em pipelines de tamanho variável, quando a instrução 2 escreve no registrador antesque a instrução 1 o leia. Por exemplo:

  SUB R4, R1, R3  ; Instrução 1
  ADD R1, R2, R3  ; Instrução 2

  SUB	R4, R1, R3	IF	…	…	…	…	…	ID
  ADD	R1, R2, R3		IF	ID	EX	MEM	WB

  A tabela acima ilustra essa situação bem, onde por algum motivo a instrução 1 levou mais ciclos de clock para realizar a leitura para os registradores, mas a instrução 2 realizou escrita nesse registrador antes.

• WAW (Escrita depois de escrita) : Também chamado de Hazard de Output, ocorre apenas em pipelines que escrevem em mais de um estágio ou permitem que uma instrução continue sua execução mesmo quando uma instrução anterior está parada (vamos ver o que são instruções ‘paradas’ logo abaixo).

   SUB R1, R4, R3  ; Instrução 1
  ADD R1, R2, R3  ; Instrução 2

  SUB	R1, R1, R3	IF	ID	…	…	…	…	WB
  ADD	R1, R2, R3		IF	ID	EX	MEM	WB

  A tabela acima mostra como o hazard ocorre. Por algum motivo a instrução 1 levou mais ciclos de clock para terminar, enquanto isso a instrução 2 executou todos seus estágios, incluindo o de escrita. O problema é que a instrução 2 está executando a operação em um registrador que ainda não foi escrito pela instrução 1.

Para resolver os Hazards de Dados, existem algumas opções também:

• Forwarding – Para resolver os problemas de dependência, foi criada uma técnica chamada de Forwarding, onde um novo circuito é adicionado ao pipeline. É como um barramento que corta caminho através do pipeline. Apesar da necessidade de adicionar um novo circuito ao hardware, funciona bem por ser bem mais rápido transferir um dado via hardware do que esperar um estágio do pipeline terminar de executar para então preparar os dados para a próxima instrução que depende deles.
• Reordenação de Código – O problema é evitado usando um compilador ‘inteligente’ que reordena o código em assembly para evitar esses tipos de dependência. Não é muito comum, pois o compilador deve ter informações detalhadas da estrutura e do ‘rítmo’ de execução do pipeline no qual o hazard ocorreria. Esse tipo de compilador é chamado de Compilador Dependente de Hardware.
• Inserção de Bolhas – Como vimos nos Hazards de Estrutura, inserimos uma bolha no pipeline para atrasar a execução da instrução, ganhando tempo para a instrução posterior. Nesse caso é um método de última opção que pode ser usado quando forwarding ou o auxílio de um compilador especial não estiver disponível ou não for suportado pelo hardware.

3. De Controle

Como vimos no último post de AOC (Pipeline I), um dos mais comuns problemas de pipeline são os de desvio de fluxo. Esses problemas são os Hazards de Controle e são causados por desvios e outras instruções que alteram o PC (Program Counter).

Recapitulando um pouco, é comum em Hazards de Controle acontecerem em situações como:

MOV AX, 10h      ; Instrução 1

CMP AX, BX         ; Instrução 2

    JAE  9f                  ; Instrução 3

SUB AX, 5h           ; Instrução 4

…

9: ADD SP, 8          ; Instrução 15

…

Até a instrução 3, o processador não sabe qual instrução deve executar a seguir, por isso, geralmente continua o fluxo normal da instrução 4 e adiante. Porém, caso o jump da instrução 3 seja feito, todas as instruções buscadas entre o primeiro estágio de pipeline da instrução 3 até o fim do estágio de execução são removidas do pipeline e o processador deve então pôr a instrução 15 no pipeline para executa-la, ficando ocioso por um tempo significante. Esse tempo em que fica ocioso é chamado de penalidade de desempenho.

Mostrando de novo a ilustração dessa situação:

Desvio Condicional e Penalidade de Desempenho

Hazards de Controle podem ser tratados dos seguintes modos:

• Inserção de bolha – Insere-se uma bolha no pipeline até que seja computado se o desvio vai ser tomado ou não.
• Nunca tomar o desvio – Como foi mostrado em nosso exemplo, assume-se que o desvio nunca é tomado e a execução sempre ocorre naturalmente. Caso no fim do pipeline da instrução o desvio seja tomado, ocorre a penalidade de desempenho.
• Sempre tomar o desvio – Nessa abodagem, o pipeline sempre assume que o desvio vai ser tomado e já começa a agendar as instruções posteriores ao desvio sem saber se ele na verdade vai ser tomado ou não.

Desses três métodos de tratamento dos Hazards de Controle, o mais comum, assim como pra qualquer outro hazard é o uso de bolhas. Nesse caso o pipeline é parado até que seja computado o estágio de decisão de fluxo, evitando quaisquer tipos de penalidades e perdas maiores de desempenho.

Bom, é isso aí, acabamos então o assunto de hazards de pipeline. Qualquer coisa, só deixar um comentário!

Até!