Hazards de Controle e Previsão de Branch em Arquitetura de Computadores Ricardo Pannain 2023

Hazards de Controle branch Se o resultado do desvio é conhecido no MEM Ricardo Pannain 2023 PC Flush estas instruções Set valores de controle para 0 1 Reduzindo o Branch Delay Mover o hardware para calcular o resultado para o estágio ID Somador para o endereço alvo Comparador para os registradores Exemplo branch taken 36 sub 10 4 8 40 beq 1 3 7 44 and 12 2 5 48 or 13 2 6 52 add 14 4 2 56 slt 15 6 7 72 lw 4 507 Ricardo Pannain 2023 2 Exemplo Branch Taken Ricardo Pannain 2023 3 Exemplo Branch Taken Ricardo Pannain 2023 4 Data Hazards para Desvios Se o registrador da comparação é um destino da 2a ou 3a instrução ALU que precede o branch Ricardo Pannain 2023 IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB add 4 5 6 add 1 2 3 beq 1 4 target Podemos resolver utilizando o adiantamento 5 Data Hazards para Desvios Se o registrador a ser comparado é um destino de uma instrução ALU precedente ou um a 2a instrução load precedente Necessita de um ciclo de stall Ricardo Pannain 2023 beq stalled IF ID EX MEM WB IF ID EX MEM WB IF ID ID EX MEM WB add 4 5 6 lw 1 addr beq 1 4 target 6 Data Hazards para Desvios Se o registrador a ser comparado é um destino de uma instrução load imediatamente precedente Necessita de dois ciclos de stall Ricardo Pannain 2023 beq stalled IF ID EX MEM WB IF ID ID ID EX MEM WB beq stalled lw 1 addr beq 1 0 target 7 Previsão Dinâmica de Branch Em pipelines longos e superscalares a penalidade do branch é mais significativa Usar previsão dinâmica Buffer de previsão de Branch branch history table Indexado pela parte menos significativa do endereço das instruções recentes de desvios Resultados armazenados takennot taken one bit predictor Para executar um branch Verificar a tabela assumir o mesmo resultado Iniciar o fetch conforme a tabela indica Se errado dar um flush no pipeline e inverter o bit de previsão Ricardo Pannain 2023 8 1Bit Previsão Previsão 1 loop internos Ricardo Pannain 2023 for YYY beq for XXX 9 Buffer de previsão de Branch branch history table 1Bit Predictor Deficiência Previsão incorreta de loops internos pelo menos 2 vezes se não for tomado Ricardo Pannain 2023 outer inner beq inner beq outer Previsão errada como tomado na última iteração do loop interno Então a previsão errada como não tomado na primeira iteração do próximo loop interno na próxima rodada 10 2Bit Previsão Mudanças na previsão somente em duas previsões sucessivas erradas Ricardo Pannain 2023 11 Exceções e Interrupções Eventos inesperados necessitam mudanças no fluxo de controle Diferentes ISAs usam os termos diferentemente Exceções Geradas dentro da CPU pex opcode indefinido overflow syscall Interrupções Geradas externamente controlador de IO Tratálas sem sacrificar o desempenho é uma tarefa difícil Ricardo Pannain 2023 12 Tratamento de Exceções In MIPS exceções são gerenciadas pelo System Control Coprocessor CP0 Salvar o PC da instrução interrompida No MIPS Exception Program Counter EPC Salvar a indicação do problema No MIPS Registrador Cause 1 bit 0 para opcode indefinido 1 para overflow Saltar para a rotina de tratamento no endereço 8000 00180 Ricardo Pannain 2023 13 Um Mecanismo Alternativo Interrupções Vetoradas Endereço da rotina de tratamento determinada pelo interrupção Exemplo Opcode indefinido C000 0000 Overflow C000 0020 C000 0040 Ricardo Pannain 2023 14 Ações no Tratamento Ler a causa e transferir para a rotina de tratamento específica Determinar a ação necessária Se reiniciável Executar a ação corretiva Usar o EPC para retornar ao programa Caso contrário Terminar o programa Reportar o erro usando EPC cause Ricardo Pannain 2023 15 Exceções no Pipeline Outra forma de hazard de controle Considere um overflow em um add no estágio EX add 1 2 1 Prevenir 1 do overflow Completar as instruções anteriores Flush no add e nas instruções subsequentes Atualizar os valores de Cause e do registrador EPC Transferir o controle para a rotina de tratamento Similar ao erro de previsão do branch Uso do mesmo hardware Ricardo Pannain 2023 16 Pipeline com Exceções Ricardo Pannain 2023 17 Propriedades das Exceções Exceções reiniciáveis Pipeline deve fazer flush na instrução A rotina de tratamento é executada e então retorna à instruções Refetched e executado do zero PC é salvo no registrador EPC Identifica a instrução que causou Na realidade o PC 4 é salvo A rotina de tratamento deve ajustar Ricardo Pannain 2023 18 Exemplo Exceção Exceção no add em 40 sub 11 2 4 44 and 12 2 5 48 or 13 2 6 4C add 1 2 1 50 slt 15 6 7 54 lw 16 507 Rotina de tratamento 80000180 sw 25 10000 80000184 sw 26 10040 Ricardo Pannain 2023 19 Exemplo Exceção Ricardo Pannain 2023 20 Exemplo Exceção Ricardo Pannain 2023 21 Paralelismo em Nível de Instrução ILP Pipeline execução de múltiplas instruções em paralelo Para aumentar o ILP Pipeline mais longos Menos trabalho por estagio menor ciclo de clock Despachos múltiplos Estágios de pipeline replicados pipelines múltiplos Inicia múltiplas instruções por ciclo de clock CPI 1 então utiliza Instruções Por Ciclo IPC Pex 4GHz 4way multipleissue 16 BIPS peak CPI 025 peak IPC 4 Dependências na prática reduz isto Ricardo Pannain 2023 22 Despachos Múltiplos Despachos múltiplos estáticos Grupos de instruções são compilados para serem despachados juntos Packages são despachados em slots O compilador detecta e evita hazards Despachos múltiplos dinâmicos A CPU examina um stream de instruções e escolhe as instruções que serão enviadas em cada ciclo O compilador pode ajudar reordenando as instruções A CPU resolve os hazards usando técnicas avançadas Ricardo Pannain 2023 23 Especulação Adivinhar o que fazer com uma instrução Inicia a operação tão logo como possível Verifica se a adivinhação estava correta Se sim completa a operação Se não volta e executa certo Comum à despacho estático e dinâmico Exemplos Especulação no resultado do branch Reverter se o caminho é diferente Especulação no load Reverter se a localização foi atualizada Ricardo Pannain 2023 24 Especulação CompiladorHardware O compilador pode reordenar as instruções pex mover o load antes do branch Pode incluir instruções fixup para recuperar adivinhações incorretas O hardware pode procurar pro instruções a executar Armazena os resultados em um buffer até eles serem realmente necessários Limpa os buffers em uma especulação incorreta Ricardo Pannain 2023 25 Especulação e Exceções E se ocorrer um exceção em um instruções sendo executada especulativamente pex load especulativo antes da verificação de um nullpointer Especulação estática Pode ser adicionado ao ISA suporte para adiar exceções Especulação dinâmica Pode aramzenar as exceções até a instrução ser completada o que não deve ocorrer Ricardo Pannain 2023 26 Despacho Múltiplo Estático O compilador agrupa instruções em issue packets Grupos de instruções podem ser despachadas em um único ciclo de clock Determinado pelos recursos necessários do pipeline Pense em um issue packet como uma instrução muito longa Especifica múltiplas operações concorrentes Very Long Instruction Word VLIW Ricardo Pannain 2023 27 Escalonamento de Despacho Múltiplo Estático O compilador deve remover algunstodos os hazards Reordenar as instruções em packets para despacho Sem dependências no pacote Possibilidade de alguma depêndencia entre pacotes Varia entre os ISAs o compilador deve saber Preencher com nop se necessário Ricardo Pannain 2023 28 MIPS com Despacho Estático Dual Dois pacotes de despacho Uma de instruções ALUbranch Uma de instruções loadstore 64 bits alinhados ALUbranch e então loadstore Preenche uma instrução não usada com nop Ricardo Pannain 2023 Address Instruction type Pipeline Stages n ALUbranch IF ID EX MEM WB n 4 Loadstore IF ID EX MEM WB n 8 ALUbranch IF ID EX MEM WB n 12 Loadstore IF ID EX MEM WB n 16 ALUbranch IF ID EX MEM WB n 20 Loadstore IF ID EX MEM WB 29 MIPS com Despacho Estático Dual Ricardo Pannain 2023 30 Hazards no MIPS DualIssue Mais instruções sendo executadas em paralelo Hazard de dados em EX add t0 s0 s1 lw s2 0t0 Ricardo Pannain 2023 31 Hazards no MIPS DualIssue Mais instruções sendo executadas em paralelo Hazard de dados em EX Adiantamento evita stalls com singleissue Agora não podemos usar o resultado da ALU no mesmo pacote do loadstore add t0 s0 s1 lw s2 0t0 Dividir em dois pacotes gerar um stall Hazard da utilização do Load Ainda um ciclo de latência mas agora com duas instruções Escalonamento mais agressivo é necessário Ricardo Pannain 2023 32 Exemplo de Escalonamento Escalone o código para o dualissue MIPS Ricardo Pannain 2023 Loop lw t0 0s1 t0array element addu t0 t0 s2 add scalar in s2 sw t0 0s1 store result addi s1 s14 decrement pointer bne s1 zero Loop branch s10 33 MIPS com Despacho Estático Dual Ricardo Pannain 2023 34 Loop lw t0 0s1 t0array element addu t0 t0 s2 add scalar in s2 sw t0 0s1 store result addi s1 s14 decrement pointer bne s1 zero Loop branch s10 Exemplo de Escalonamento Escalone o código para o dualissue MIPS Ricardo Pannain 2023 Loop lw t0 0s1 t0array element addu t0 t0 s2 add scalar in s2 sw t0 0s1 store result addi s1 s14 decrement pointer bne s1 zero Loop branch s10 ALUbranch Loadstore cycle Loop nop lw t0 0s1 1 addi s1 s14 nop 2 addu t0 t0 s2 nop 3 bne s1 zero Loop sw t0 4s1 4 IPC 54 125 cf peak IPC 2 35 Loop Unrolling Replicar o corpo do loop body para permitir maior paralelismo Reduz o trabalho de controle do loop Usar registradores diferentes para replicação Chamado de register renaming Evita realização de loop com antidependência Store seguido por um load do mesmo registrador Conhecido como name dependence Reuso do register name Ricardo Pannain 2023 36 Exemplo de Loop Unrolling IPC 148 175 Perto do 2 mas a um custo relacionado aos registradores ao tamanho do código Ricardo Pannain 2023 ALUbranch Loadstore cycle Loop addi s1 s116 lw t0 0s1 1 nop lw t1 12s1 2 addu t0 t0 s2 lw t2 8s1 3 addu t1 t1 s2 lw t3 4s1 4 addu t2 t2 s2 sw t0 16s1 5 addu t3 t4 s2 sw t1 12s1 6 nop sw t2 8s1 7 bne s1 zero Loop sw t3 4s1 8 37 Exemplo de Loop Unrolling Ricardo Pannain 2023 ALUbranch Loadstore cycle Loop addi s1 s116 lw t0 0s1 1 nop lw t1 12s1 2 addu t0 t0 s2 lw t2 8s1 3 addu t1 t1 s2 lw t3 4s1 4 addu t2 t2 s2 sw t0 16s1 5 addu t3 t4 s2 sw t1 12s1 6 nop sw t2 8s1 7 bne s1 zero Loop sw t3 4s1 8 38 Loop lw t0 0s1 t0array element addu t0 t0 s2 add scalar in s2 sw t0 0s1 store result addi s1 s14 decrement pointer bne s1 zero Loop branch s10 Escalonamento de Despacho Múltiplo Dinâmico Processadores Superscalar A CPU decide se envia 0 1 2 em cada ciclo Evitando hazard de dados e estrutural Evita a necessidade de para escalonamento do compilador Embora ainda ele possa ajudar Semântica do código assegurado pela CPU Ricardo Pannain 2023 39 Pipeline de Escalonamento Dinâmico Permite à CPU executar instruções for a de ordem para evitar stalls Mas entrega o resultado ao registrador em ordem Exemplo lw t0 20s2 addu t1 t0 t2 sub s4 s4 t3 slti t5 s4 20 O sub pode ser iniciado quando o addu estiver esperando o lw Ricardo Pannain 2023 40 CPU Dinamicamente Escalonável Ricardo Pannain 2023 Resultados também enviados para qualquer reservation stations Buffers de reordenação para escrita nos registradores Pode suprir operandos para instruções despachadas Preserva dependências Mantem operando pendentes 41 Register Renaming Reservation stations e reorder buffer efetivamente permitem o register renaming Na instrução despachada para a reservation station Se o operando está disponível no register file ou no reorder buffer Copiado para a reservation station Se não for mais necessário no registrador in the registrador pode ser sobrescrito Se o operando está disponível Ele será providenciado para a reservation station por uma unidade funcional A atualização do registrador não deve ser requerida Ricardo Pannain 2023 42 Especulação Previsão de branch and despacho contínuo Não entrega o resultado até o resultado do bracnh ser determinado Especulação do Load Evita delay de load e de miss de cache Prevê o endereço efetivo Prevê o valor armazenado Carrega depois do completo conhecimento dos stores Valores de stores são passados pela unidade de load Não termina o load até a especulação estar clara Ricardo Pannain 2023 43 Porque Fazer Escalonamento Dinâmico Porque não deixar que o compilador escalone o código Nem todos os stalls são previsíveis pex cache misses Nem sempre podemos escalonar em torno de branches O resultado do branch é determinado dinâmicamente Diferentes implementações deum ISA têm diferentes latências e hazards Ricardo Pannain 2023 44 Múltiplos Despachos Funcionam Sim mas não tanto quanto gostaríamos Programas tem dependências reais que limitam o ILP Some dependências são difíceis de eliminar pex pointer aliasing Alguns paralelismo são difíceis de expor Tamanho limitado da janela durante o despacho das instruções Atrasos de memória e limitação de bandwidth Difícil para manter o pipeline cheio Especulação pode ajudar se bem feito Ricardo Pannain 2023 The BIG Picture 45 Eficiência de Energia Complexidade de especulação e escalonamento requer energia Múltiplos cores simples podem ser melhor Ricardo Pannain 2023 Microprocessor Year Clock Rate Pipeline Stages Issue width Outoforder Speculation Cores Power i486 1989 25MHz 5 1 No 1 5W Pentium 1993 66MHz 5 2 No 1 10W Pentium Pro 1997 200MHz 10 3 Yes 1 29W P4 Willamette 2001 2000MHz 22 3 Yes 1 75W P4 Prescott 2004 3600MHz 31 3 Yes 1 103W Core 2006 2930MHz 14 4 Yes 2 75W UltraSparc III 2003 1950MHz 14 4 No 1 90W UltraSparc T1 2005 1200MHz 6 1 No 8 70W 46 A Microarquitetura do Opteron X4 Ricardo Pannain 2023 411 Realidade O Pipeline do AMD Opteron X4 Barcelona 72 registradores físicos 47 O Fluxo do Pipeline Opteron X4 Para operações inteiras Ricardo Pannain 2023 FP tem 5 estágio Mais de 106 RISCops Gargalo Instruções complexas com dependências longas Previsão errada de branch Atraso de acesso à memória 48 Falácias Pipeline é fácil A idéia básica é fácil O diabo está nos detalhes pex detecção de hazards dados Pipeline é dependente da tecnologia Porque então o pipline não foi sempre utilizado Mais transistores fazem com que técnicas avançadas sejam factíveis Projeto de ISAs para pipeline acompanhar as tendências da tecnologia pex delayed branch Ricardo Pannain 2023 49 Armadilhas Projeto pobre de ISA pode afetar o pipeline de forma adversa pex conjunto complexo de instruções VAX IA 32 Overhead significativo para fazer o pipelining funcionar Abordagem microop IA32 pex complexidade do modos de endereçamento Efeitos colaterais e atualização de registradores indireçao de memória pex delayed branches Pipelines avançados tem um grande delay slots Ricardo Pannain 2023 50 Conclusões ISA influencia o projeto do datapath e do controle O datapath e o controle influenciam o projeto do ISA Pipeline melhora o throughput de instruções usando paralelismo Mais instruções completadas por segundo A latência de cada instrução não reduz Hazards estrutural dados controle Escalonamento e estático dinâmico de despachos múltiplos ILP Dependências limitam o paralelismo Complexidade leva à barreira da energia Ricardo Pannain 2023 51 CPU Overview Ricardo Pannain 2023 52 Multiplexadores Ricardo Pannain 2023 Não podemos ligar dois fios Usar multiplexadores 53 Controle PC Address Instruction Instruction memory Registers Data Register Register Register RegWrite ALU Mux Mux Mux Add Add Branch ALU operation Zero MemWrite Data memory Address Data MemRead Control Ricardo Pannain 2023