Aula 19: Pipeline Hazards (estruturais e dados)

Até agora, temos o MIPS com pipeline conforme a figura abaixo. Ou seja, com as etapas divididas, conforme a lista abaixo, e os sinais de controle das instruções acompanhando cada instrução através do pipline.

Etapas funcionais do MIPS com pipeline:

1. Instruction Fetch (IF): busca da próxima instrução, na memória de programa, a ser executada;

2. Instruction Decode (ID): decodifica a instrução (UC) e faz a leitura dos registradores utilizados pela instrução;

3. Execute (EX): executa a operação definida pela instrução. É sempre feita na ULA;

4. Memory Acess (MEM): lê a memória ou escreve o resultado da execução na memória RAM;

5. Write Back (WB): escreve o resultado da execução no banco de registradores.

Como temos, potencialmente, 5 instruções executadas ao mesmo tempo, pode ocorrer que alguma dessas instruções não possa ser executada no mesmo clock que as outras.

Esse problema é chamado de pipeline hazard e existem três tipos:

• Estruturais:

  • O mesmo recurso de hardware será utilizado múltiplas vezes no mesmo ciclo de clock, sendo que o recurso não aceita múltiplos acessos concomitantes.

• Dados:

  • A instrução sendo executada depende do resultado de outra instrução que ainda está no pipeline e não terminou a sua execução.

• Controle:

  • Devido a um desvio na sequência do programa, algumas instruções, já carregadas no pipeline, não devem ser executadas.

O conjunto de instruções do MIPS foi pensado para executar em um pipeline, como pode ser visto através de algumas de suas características:

• Todas as instruções possuem o mesmo comprimento, ou seja, uma palavra de 32 bits:

  • Simplificando a busca e a decodificação das instruções (não necessita esperar várias palavras para definir o funcionamento da instrução).

• Possui uma quantidade limitada de formatos (R, I, J) para as instruções e mantém o endereço dos registradores e opcodes na mesma posição, para todas instruções.

  • Permite que a decodificação da instrução e a busca dos registradores usados sejam feitas ao mesmo tempo.

• O acesso à memória RAM só é feito por duas instruções e após o cálculo do endereço.

  • Ajuda a manter o número de etapas do pipeline baixo. Se operasse diretamente na memória, como o x86, teríamos que fazer o cálculo do endereço na etapa 3, o acesso à memória na etapa 4 e em seguida ter a etapa de execução.

• Alinhamento dos dados na memória:

  • Impede que uma única instrução de transferência de dados necessite de dois acessos à memória. Isso permite que o acesso à memória seja executado em um único estágio do pipeline.

O cuidado no projeto do conjunto de instruções permitiu evitar problemas estruturais durante a execução do pipeline. Foram evitadas duas situações:

• Se o MIPS tivesse uma só memória, para instruções e dados juntos, haveria conflito entre a busca de instruções e a escrita/leitura da memória. Por isso, o MIPS separa as memórias para os dados da memória das instruções.

• O banco de registradores foi modificado para permitir a leitura e escrita de dados simultaneamente. Por isso ele pode ser acessado no segundo e quinto estágios do pipeline.

Envolve o retorno do endereço, calculado pela instrução beq e jump, para atualizar program counter. Trateremos dele na próxima aula.

As dependências entre os dados, em um fluxo de execução no pipeline, são divididas em quatro tipos:

1. RAR (Read After Read): Essa dependência não gera problemas pois só ocorrem leituras.

            add  R1, R2, R3
            sub  R5, R2, R4

2. RAW (Read After Write): Chamada de dependência real. A instrução corrente depende do resultado de uma instrução anterior. Dependendo do tamanho do pipeline e da distância entre os dados, pode gerar problemas.

            add  R1, R2, R3
            sub  R5, R1, R4

3. WAR (Write After Read): Chamada de anti-dependência. A instrução corrente depende de um valor que será alterado em seguida, ou seja, a ordem de execução não pode ser mudada.

            add  R1, R2, R3
            sub  R2, R5, R4

4. WAW (Write After Write): Chamada de dependência de saída. O valor final de uma variável depende da ordem das instruções.

            add  R1, R2, R3
            sub  R1, R5, R4

Dependências do Tipo RAW

No caso da dependência do tiplo RAW, a execução de uma instrução depende do resultado de outra instrução que ainda não finalizou sua execução.

Por exemplo, no código abaixo temos a dependência RAW no registrador $s0:

    add $s0, $t0, $t1;

    sub $t2, $s0, $t3;

Que pode ser vista no diagrama de execução do pipeline:

O valor de $s0 ainda não terá seu valor calculado pelo add quando a instrução sub necessitar dele.

Para que o programa obtenha os valores corretos, teríamos que parar ou atrasar a instrução sub:

• Até que o resultado seja escrito no banco de registradores durante a etapa 5 (WB) da execução dessa instrução.

Chamamos esse sistema de parar a execução do pipeline, por alguns ciclos, de criar bolhas na execução.

Como o banco de registradores pode ser escrito e lido no mesmo ciclo de clock, podemos economizar um ciclo de clock.

Essa solução, chamada de stall, desperdiça tempo de processamento.

Outra opção, seria fazer uma análise durante a compilação do programa:

• Procurando por possíveis problemas de dependência de dados;

• E tentar trocar algumas instruções de lugar para resolver a dependência.

Caso essa solução não seja possível, o compilador deve adicionar instruções nop (não executam nenhuma operação) para criar as bolhas no pipeline:

    add $s0, $t0, $t1;
    nop;
    nop;
    sub $t2, $s0, $t3;

Soma Acumulativa

No caso de uma soma acumulativa, como a mostrada abaixo, existe algum problema?

    add $1,$1,$2
    add $1,$1,$3
    add $1,$1,$4

Temos um problema entre:

• O resultado da instrução no estágio WB;

• O resultado da instrução no estágio MEM;

• O operando da instrução na no estágio EX.

A Instrução load word

O caso da instrução lw, que é a mais longa e ocupa todas as etapas do pipeline, se houver uma carga seguida de uma instrução do tipo R, como mostrado abaixo, em qual clock a instrução sub pode iniciar a sua execução? Por que?

    lw $s0, 20($t1);
    sub $t2, $s0, $t3;

Load-Use hazard

Para resolver, é necessário a inserção de duas instruções nop, como mostrado abaixo:

Essa técnica ajuda a mitigar o desperdício de tempo na execução de instruções dependentes.

Ela se baseia no fato de que, para obter dado desejado, não é necessário esperar a instrução atravessar todo o pipeline.

A partir do momento em que o dado foi computado, ele está na saída da ULA e a sua transferência pode ser feita através do próprio pipeline, como se existisse um atalho.

Em resumo, é a criação de um desvio interno ao pipeline.

Porém, como e em quais situações esse desvio deve ser ativado?

Detecção de Problemas com Dados

Para facilitar o entendimento, vamos padronizar a nomenclatura dos sinais. Iremos utilizar a seguinte notação:

        (nome do registrador do pipeline).sinal

Na figura abaixo, está o exemplo dos sinais Rs, Rt e Rd, logo após o registrador de borda entre a etapa ID e a etapa EX.

Agora, precisamos definir em quais estágios do pipeline podem existir dependências. Sabemos que, no caso do MIPS, a produção de dados é feita através do resultado de alguma operação ou do carregamento de um dado da memória.

Dessa forma, a fonte de novos dados está limitada a duas etapas do pipeline:

• Na saída da ULA, na etapa EX.

• Na leitura da memória de dados, na etapa MEM.

Por outro lado, o dado é consumido somente na entrada da ULA.

Como é necessário isolar o consumo da produção, a solução deverá ser parecida com o esquema abaixo:

Como o dado produzido sempre será armazenado em Rd e os dados consumidos sempre serão provenientes de Rs e Rt, podemos verificar a existência do hazard comparando-se os endereços de Rs e Rt:

• Na entrada da ULA.

Com o endereço de Rd, nas etapas seguintes:

• Rd na etapa MEM;

• Rd na etapa WB.

Portanto, no caso de igualdade nos endereços, podemos interligar (usando um MUX) os dados desses pontos:

• Desde que tenhamos um registrador entre eles;

• Impedindo que o circuito oscile.

Como a entrada da ULA pode vir do circuito de extensão de sinal, precisaremos de outro MUX. Ele será controlado pelo sinal ALUSrc.

Os sinais envolvidos no controle do forward são os seguintes:

• RegWrite

• EX/MEM.RegisterRd

• ID/EX.RegisterRs

• ID/EX.RegisterRt

• MEM/WB.RegisterRd

Usaremos a seguinte padronização para a seleção dos MUXES do forward:

De posse das equações, ou circuito, deve ser feita:

• A implementação em VHDL;

• O teste de funcionamento;

• A integração com o Fluxo de Dados e seu teste completo:

  • Para isso, será necessário escrever um programa que utilize o conjunto de instruções implementado (use o simulador SPIM).