Pipeline MIPS- Analogia Lavanderia e Otimização de Desempenho

Analogia do Pipeline Lavanderia com pipeline sobreposição de execução Paralelismo melhora o desempenho Ricardo Pannain 2023 Quatro cargas Speedup 835 23 1 Pipeline MIPS Cinco estágio uma etapa por estágio 1 IF Fetch da Instrução da memória 2 ID Decodificação da Instrução leitura dos registradores 3 EX Execução das operações ou cálculo dos endereços 4 MEM Acesso aos operandos da memória 5 WB Escrita do resultado de volta ao registrador Ricardo Pannain 2023 2 Desempenho do Pipeline Assumir que o tempo para cada estágio é 100ps para leitura ou escrita nos registradores 200ps para os outros estágios Comparando o datapath com pipeline com o datapath singlecycle Ricardo Pannain 2023 Instr Instr fetch Register read ALU op Memory access Register write Total time lw 200ps 100 ps 200ps 200ps 100 ps 800ps sw 200ps 100 ps 200ps 200ps 700ps Rformat 200ps 100 ps 200ps 100 ps 600ps beq 200ps 100 ps 200ps 500ps 3 Desempenho do Pipeline Ricardo Pannain 2023 Singlecycle Tc 800ps Pipelined Tc 200ps 4 Pipeline Speedup Se todos os estágios são balanceados ie todos têm o mesmo tempo Tempo de exec entre as instruçõespipelined Tempo de exec entre as instruçõesnonpipelined Número de estágios entre o fim de execução de uma instrução i e o fim de execução de uma instrução i1 Se não forem balanceados o speedup é menor O speedup é decorrente do aumento do throughput quanto maior o número de instruções maior o speeup Latência tempo de execução de cada instrução permanece a mesma Ricardo Pannain 2023 5 Pipeline e o Projeto do ISA O ISA MIPS foi projetado levandose em conta o pipeline Todas as instruções têm 32 bits Facilidade no fetch e na decodificação em um ciclo obs x86 instruções de 1 a 17byte Formatos de instruções são poucos e regulares É possível decodificar e ler os registradores em um só ciclo Endereçamento Loadstore É possível calcular o endereço no 3o estágio acessar a memoria no 4o estágio Alinhamento dos operandos de memória Memoria é acessada em um único ciclo Ricardo Pannain 2023 6 Hazards Situações que impedem iniciar a próxima instrução no próximo ciclo Hazards estruturais Um recurso requerido está ocupado Hazard de dados Necessidade de esperar que instruções prévias completem a operação readwrite de dados reg file Hazard de controle Decisões de controle de execução dependem de instruções previas Ricardo Pannain 2023 7 Hazard estrutural Memória única para instruções e dados Só uma ULA para o beq Hazard de dados add 8 7 9 add 5 4 8 Hazard de controle beq Ricardo Pannain 2023 8 Hazards Exemplos IF Ricardo Pannain 2023 9 ID EXE MEM WB IF ID EXE MEM WB 1 ADD 8 7 9 2 ADD 5 4 8 IF ID EXE MEM WB IF ID EXE MEM WB NOP NOP Hazards Estruturais Conflito para o uso de um recurso No MIPS com pipeline com apenas uma memória Loadstore necessitam de acesso aos dados Fetch da instrução teria que forçar um stall para este ciclo Causaria uma bolha bubble no pipeline Por isso datapaths com pipeline requerem caches separadas de instruções e dados Ricardo Pannain 2023 10 Hazard de Dados Uma instrução depende da finalização do dado tratado por uma instrução anterior add s0 t0 t1 sub t2 s0 t3 and t5 s0 t4 Ricardo Pannain 2023 11 IF Ricardo Pannain 2023 12 ID EXE MEM WB IF ID EXE MEM WB IF ID EXE MEM WB IF ID EXE MEM WB 1 add s0 t0 t1 2 sub t2 s0 t3 3 and t5 s0 t4 IF ID EXE MEM WB 1 3 2 nop nop IF Ricardo Pannain 2023 13 ID EXE MEM WB IF ID EXE MEM WB 1 add s0 t0 t1 2 sub t2 s0 t3 3 and t5 s0 t4 IF ID EXE MEM WB 1 3 2 Forwarding Bypassing Usa o resultado quando for calculado ou lido Não espera ser armazenado no registrador Requerer conexões extras no datapath Ricardo Pannain 2023 14 Hazard de Dados Instrução Load Nem sempre é possível evitar stalls com o forwarding Se o valor não foi definido quando ele for necessário Ricardo Pannain 2023 15 IF Ricardo Pannain 2023 16 ID EXE MEM WB IF ID EXE MEM WB 1 LW 8 107 2 ADD 5 4 8 IF ID EXE MEM WB NOP Escalonamento do Código para Evitar Stalls Reordenar o código para o uso do resulstado do load na próxima instrução Código C A B E C B F Ricardo Pannain 2023 lw t1 0t0 lw t2 4t0 nop add t3 t1 t2 sw t3 12t0 lw t4 8t0 nop add t5 t1 t4 sw t5 16t0 stall stall 13 cycles 17 Escalonamento do Código para Evitar Stalls Reordenar o código para o uso do resulstado do load na próxima instrução Código C A B E C B F Ricardo Pannain 2023 lw t1 0t0 lw t2 4t0 add t3 t1 t2 sw t3 12t0 lw t4 8t0 add t5 t1 t4 sw t5 16t0 stall stall lw t1 0t0 lw t2 4t0 lw t4 8t0 add t3 t1 t2 sw t3 12t0 add t5 t1 t4 sw t5 16t0 11 cycles 13 cycles 18 Hazards de Controle O branch determina o fluxo de controle A próxima instrução a ser buscada depende do resultado do branch O Pipeline pode pegar a instrução errada O branch está ainda no estágio ID No pipeline MIPS Necessidade de antecipar a comparação dos registradores e o cálculo de endereço alvo Adicionar hardware que faça isto no estágio ID Ricardo Pannain 2023 19 Stall no Branch Esperar até o resultado do branch estar pronto antes do fetch para próxima instrução Supor que o pode ser resolvido no 2º estágio Ricardo Pannain 2023 20 Previsão de Branch Pipelines longos não podem antecipar o resultado do branch A penalidade do stall tornase ináceitável Previsão do resultado do branch Stall somente se a previsão estiver errada No pipeline MIPS Podemos prever desvios não tomados not taken Fetch da instrução após o branch sem delay Ricardo Pannain 2023 21 MIPS com Previsão Not Taken Ricardo Pannain 2023 Previsão correta Previsão incorreta 22 Previsão de Branch Mais Realista Previsão estática de branch Baseada no comportamento típico do branch Exemplo desvios de loop e comando if Previsão de desvios tomados para trás Previsão de desvios não tomados para frente Previsão Dinâmica de branch O hardware mede o real comportamento do branch pex armazena o histórico recente de cada branch Assumir que o comportamento futuro acompanhará o histórico Quando errado stall enquanto é feito o novo fetch atualizando o histórico Ricardo Pannain 2023 23 Resumo do Pipeline Pipeline melhora o desempenho pelo aumento do throughput de instrução Executa múltiplas instruções em paralelo Cada instrução tem a mesma latência Tópicos de hazards Estrutural dados controle O projeto do conjunto de instruções afeta a complexidade da implementação do pipeline Ricardo Pannain 2023 The BIG Picture 24 Datapath MIPS com pipeline Ricardo Pannain 2023 WB MEM Da direita para a esquerda o fluxo conduz ao hazard 25 Registradores de Pipeline Necessita registradores entre os estágios Para manter a informação produzida no ciclo anterior Ricardo Pannain 2023 26 Operação de Pipeline Fluxo de instruções ciclo por ciclo através do datapath com pipeline Diagrama Singleclockcycle do pipeline Mostra o uso do pipeline em um ciclo Realces dos recursos usados obs Diagrama multiclockcycle Gráfico da operação ao longo do tempo Vamos ver o diagrama singleclockcycle para o load store Ricardo Pannain 2023 27 IF para Load Store Ricardo Pannain 2023 28 ID para Load Store Ricardo Pannain 2023 29 EX para Load Ricardo Pannain 2023 30 MEM para Load Ricardo Pannain 2023 31 WB para Load Ricardo Pannain 2023 Número do registrador errado 32 Datapath para Load Corrigido Ricardo Pannain 2023 33 EX para Store Ricardo Pannain 2023 34 MEM para Store Ricardo Pannain 2023 35 WB para Store Ricardo Pannain 2023 36 Diagrama MultiCiclo do Pipeline Forma de mostrar o usos dos recursos Ricardo Pannain 2023 37 Diagrama MultiCiclo do Pipeline Forma tradicional Ricardo Pannain 2023 38 Diagrama Ciclo Único do Pipeline Estado do pipeline em um dado ciclo Ricardo Pannain 2023 39 Controle do Pipeline Simplificado Ricardo Pannain 2023 40 Controle do Pipeline Sinais de control são derivados da instrução Uma implementação no singlecycle Ricardo Pannain 2023 41 Controle do Pipeline Ricardo Pannain 2023 42 Hazards de Dados em instruções aritméticalógicas ALU Instructions Considere esta sequencia sub 2 13 and 1225 seta vermelha dependência or 1362 seta azul não dependência add 1422 sw 151002 Podemos resolver hazards com forwarding Como podemos detectar quando adiantar Ricardo Pannain 2023 43 Dependências Forwarding Ricardo Pannain 2023 44 Detecção da Necessidade do Adiantamento Passagem dos números dos registradores através do pipeline pex IDEXRegisterRs número do registrador RS no registrador de pipeline in IDEX pipeline Os números dos registrador usados pela ALU no estágio EX são dados por IDEXRegisterRs IDEXRegisterRt Data hazards quando 1a EXMEMRegisterRd IDEXRegisterRs 1b EXMEMRegisterRd IDEXRegisterRt 2a MEMWBRegisterRd IDEXRegisterRs 2b MEMWBRegisterRd IDEXRegisterRt Ricardo Pannain 2023 Fwd do reg pipeline EXMEM Fwd do reg pipeline MEMWB 45 Detecção da Necessidade do Adiantamento Somente ocorrerá o adiantamento de a instrução for escrever em um registrador EXMEMRegWrite MEMWBRegWrite E somente se Rd da instrução não for o zero EXMEMRegisterRd 0 MEMWBRegisterRd 0 Ricardo Pannain 2023 46 Caminhos do Forwarding Ricardo Pannain 2023 47 Condições do Forwarding EX hazard if EXMEMRegWrite and EXMEMRegisterRd 0 and EXMEMRegisterRd IDEXRegisterRs ForwardA 10 if EXMEMRegWrite and EXMEMRegisterRd 0 and EXMEMRegisterRd IDEXRegisterRt ForwardB 10 MEM hazard if MEMWBRegWrite and MEMWBRegisterRd 0 and MEMWBRegisterRd IDEXRegisterRs ForwardA 01 if MEMWBRegWrite and MEMWBRegisterRd 0 and MEMWBRegisterRd IDEXRegisterRt ForwardB 01 Ricardo Pannain 2023 48 Hazard de Dados Duplo Considere a sequencia add 112 add 113 add 114 Ricardo Pannain 2023 49 Hazard de Dados Duplo Considere a sequencia add 112 add 113 add 114 Ambos hazards ocorrem Queremos usar o mais recente Revisar a condição de hazard no MEM Somente fwd se a condição de hazard em EX for falsa Ricardo Pannain 2023 50 Conditição de Forwarding Revisada MEM hazard if MEMWBRegWrite and MEMWBRegisterRd 0 and not EXMEMRegWrite and EXMEMRegisterRd 0 and EXMEMRegisterRd IDEXRegisterRs and MEMWBRegisterRd IDEXRegisterRs ForwardA 01 if MEMWBRegWrite and MEMWBRegisterRd 0 and not EXMEMRegWrite and EXMEMRegisterRd 0 and EXMEMRegisterRd IDEXRegisterRt and MEMWBRegisterRd IDEXRegisterRt ForwardB 01 Ricardo Pannain 2023 51 Datapath com Forwarding Ricardo Pannain 2023 52 Hazard de com lw Considere a sequencia lw 152 add 314 lw 152 nop add 314 Ricardo Pannain 2023 53 Data Hazard com Load Ricardo Pannain 2023 Necessidade de stall de um ciclo 54 Data Hazard com Load Verificar quando a instrução em uso é decodificada no estágio ID Os números dos registradores usados pela ALU no estágio ID são dados por IFIDRegisterRs IFIDRegisterRt Hazard com Load quando IDEXMemRead and IDEXRegisterRt IFIDRegisterRs or IDEXRegisterRt IFIDRegisterRt Se detectado stall e é inserido uma bolha Ricardo Pannain 2023 55 Como Parar o Pipeline Forçar os valores dos sinais de controle no registrador IDEX a 0 EX MEM e WB executará um nop nooperation Impedir a atualização do PC e do registrador IFID Usando a instrução que está sendo decodificada novamente Fazendo seja feito o fetch da instrução no IF novamente Stall de 1 ciclo permite à MEM ler o dado para o lw Depois é feito o adiantamento para o estágio EX Ricardo Pannain 2023 56 StallBubble no Pipeline Ricardo Pannain 2023 Stall inserido aqui 57 StallBubble no Pipeline Ricardo Pannain 2023 Ou mais precisamente 58 Datapath com Detecção de Hazard Ricardo Pannain 2023 59 Stalls e Desempenho Stalls reduz o desempenho Mas são necessário para resultados corretos Os compiladores podem rearranjar o código evitando hazards e stalls É necessário o conhecimento da estrutura do pipeline Ricardo Pannain 2023 The BIG Picture 60