Descrever o funcionamento do pipeline e o problemas derivados do controle da execução do programa;
Projetar um circuito que resolva, ou minimize, esses problemas.
Já analisamos os problemas de estrutura e de dados no pipeline do MIPS, agora, iremos ver os problemas relativos ao controle.
Para relembrar, temos a última atualização do projeto do MIPS mostrada abaixo.
Pipeline do MIPS DLX com Stall e Forward
Os problemas de controle, durante execução no pipeline, decorrem de um desvio na sequência do programa. Consequentemente, as instruções já carregadas no pipeline, nos estagios anteriores ao estágio em que o desvio será executado, e que ainda não foram executadas, devem ser descartadas.
De uma forma geral, as instruções que podem gerar um hazard de controle são as de desvio. No caso do MIPS, elas são:
Branch;
Jump;
JAL (jump and link);
Return;
Interrupção:
Provocada tanto por software quanto por hardware.
O nosso foco será no tratamento de duas instruções: BEQ e JUMP.
Esses problemas envolvem o retorno do endereço, calculado pela instrução beq ou jump, para atualizar program counter. A execução do BEQ, no pipeline, é mais complexa que a execução do jump e iniciaremos com ela.
Na figura abaixo, vemos a execução do BEQ em um fluxo de dados com pipeline. Note que a decisão, se haverá ou não o desvio, só é tomada na etapa MEM, ou seja, no quarto ciclo de clock da instrução BEQ.
Execução do Desvio e o Estado do Pipeline
Como o BEQ foi executado, as três instruções seguintes ao BEQ, que já estão nos estágios anteriores do pipeline, não devem ser executadas. Portanto, serão desperdiçados três ciclos de clock - como mostrado na figura abaixo.
Instruções Descartadas
Como visto nos problemas com dependência de dados, o compilador pode resolver adicionando instruções nop, ou o hardware pode fazer com que o pipeline espere (stall) até que o BEQ seja executado. Porém, apesar de serem soluções viáveis, elas possuem impacto no desempenho.
Solução com NOPs
Como melhorar o desempenho do hazard de controle da instrução BEQ?
Previsão de Desvio (branch prediction)
Ao invés de sempre parar o pipeline até que a instrução BEQ seja avaliada, pode-se considerar (“prever”) que o resultado será sempre falso e continuar carregando o pipeline com as instruções seguintes.
Se no momento da avaliação do BEQ, o resultado for a execução do desvio, podemos limpar o pipeline (flush). O flush, além de passar os pontos de controle para inativos (nível ‘0’), também deve incluir as etapas de busca, decodificação e execução.
Para o estágio de busca, como ainda não existe sinal de controle, que é criado no próximo estágio (decode), devemos zerar o campo da instrução no registrador IF/ID.
A previsão estática diminuiu o custo médio do desvio, que só acontece quando o desvio é tomado. Mas, no caso do desvio tomado, ainda temos um custo de três ciclos de clock.
Como poderíamos melhorar essa situção?
Diminuindo a Quantidade de Bolhas no Desvio Tomado
Para melhorar o desempenho do BEQ, quando o desvio é tomado, precisamos diminuir a quantidade de instruções a serem limpas no pipeline.
Uma forma seria tomar a decisão do BEQ em um estágio anterior ao MEM. Para que isso ocorra, precisaremos adiantar o cálculo do destino do BEQ. Felizmente, ele pode ser feito na etapa de decodificação. E, apesar de não utilizado, seria feito para todas instruções.
A avaliação da igualdade do BEQ passa para a etapa de decodificação com a utilização de portas XNOR para a comparação.
A seguir, temos um exemplo da execução de uma instrução BEQ com a decisão adiantada para a etapa de decodificação.
A decisão de executar o desvio, ou não, é tomada no terceiro ciclo de clock na etapa de decodificação (diagrama superior na figura abaixo).
No caso do desvio ser confirmado, teremos:
O endereço de destino, será calculado e transferido para o PC. No caso, o endereço de destino é 72;
O campo da instrução, que seria utilizada no próximo ciclo de clock, será apagado (instrução da linha 44);
Continuando a execução, no quarto ciclo de clock (diagrama inferior na figura abaixo), temos que:
O valor 72 é carregado no PC e inicia a busca da nova instrução, o lw;
A instrução nop é inserida na etapa de decodificação:
Fazendo com que a instrução and seja apagada (instrução da linha 44);
O banco de registadores está desabilitado, impedindo qualquer alteração no estado atual.
A instrução beq está na etapa de execução, e não terá efeito algum.
Adiantando a Decisão do BEQ
A comparação, na etapa de decodificação, cria dois problemas:
O forward dos valores dos registradores usados no BEQ:
Está implementado com destino para a etapa de execução;
E agora, deve ser modificado para a etapa de decodificação.
Além disso, os operandos podem ter origem tanto nos registradores ULA/MEM quanto MEM/WB.
Os valores da comparação do BEQ podem ter dependências nos dados:
Pode ser necessário incluir um stall;
Se a dependência for devida a uma carga (LW) seguida pelo BEQ:
Serão necessários dois ciclos de parada.
A mudança do teste do BEQ para a etapa de decodificação, diminui o custo do desvio tomado para somente um ciclo de clock (uma instrução). Esse custo pode ser minimizado utilizando-se a decisão postergada.
Decisão Postergada
Nesta solução, o pipeline sempre executa a instrução após o BEQ. No caso de laços, pode ser uma instrução do próprio laço ou, eventualmente, um “nop”.
O desvio é avaliado após essa instrução, sem perder um ciclo de execução.
Esse ajuste da instrução após o desvio será feito pelo programa de montagem do código assembly. Ele escolherá uma instrução, antes do desvio, adequada para ser colocada após o desvio.
A seguir, temos três formas para mudar a sequência das instruções e preencher o ciclo após o BEQ.
Decisão Postergada
Para o caso de custos maiores do que um ciclo de clock essa não é uma boa solução. Isso, devido à necessidade de preencher vários ciclos com instruções úteis que possam ser movidas para depois do BEQ e não alterem o resultado do processamento.
Normalmente, se utiliza a previsão do resultado do desvio por hardware, através da previsão dinâmica de desvios.
Considerando que a instrução jump é decodificada e o seu destino calculado no segundo estágio, só há desperdicio de um ciclo de clock. Para amenizar o custo do jump, podemos utilizar a técnica de desvio postergado. Caso não seja possível aplicá-la, deverá ser adicionado uma instrução nop após cada instrução jump.
Responder o quiz de participação, no blackboard, em:
Conteúdos > Participação > Aula_20_Quiz-P1
O diagrama conceitual, faltando alguns detalhes, para o pipeline final do MIPS está na figura abaixo.
Solução:
Neste diagrama é necessário adicionar o MUX referente à entrada do imediato com sinal estendido e outros detalhes.
Diagrama Conceitual do Pipeline Final
De posse do diagrama do 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).
MIPS de Ciclo Único para Instruções dos Grupos A e B
