Processador-MIPS-Implementacao-Basica-e-Elementos-Logicos

CHAPTER 4 THE PROCESSOR PATTERSSONHENNESSY Luiz Paulo de Assis Barbosa 1 41 Introdução 2 Uma implementação MIPS básica Instruções de referência à memória lw load word e sw store word Instruções lógicas e aritiméticas add sub AND OR e slt Instruções de salto beq branch equal e j jump 41 Introdução 3 Uma visão geral da implementação 41 Introdução 4 Uma visão geral da implementação Visão simplificada do ciclo de busca e execução de instrução Passo 1 Enviar o valor do contador de programa PC para a memória de programa contém código buscar a instrução e incrementar o PC Passo 2 Ler 1 ou 2 registradores usando os informações presentes nos campos da instrução para selecionar os registradores que serão lidos lw necessita ler apenas um registrador já um add precisa ler dois Demais passos depende da instrução que está sendo executada 41 Introdução 5 Uma visão geral da implementação 42 Convenções do projeto lógico 6 Para discutir sobre o projeto de um computador é necessário Definir como a lógica que implementa o computador irá operar E como o computador utilizará o clock Os elementos no caminho de dados dessa implementação didática do MIPS são formados por dois tipos de elementos lógicos Elementos combinacionais E elementos de estado sequênciais 42 Convenções do projeto lógico 7 Elementos combinacionais1 Elementos que operam sobre os valores dos dados isto é suas saídas dependem apenas do valor corrente de suas entradas O funcionamento de um circuito combinacional pode ser completamente definido por meio de uma tabela da verdade Elementos de estado1 São os elementos que possuem armazenamento interno ou memória e portanto podem guardar um estado Esse tipo de elemento possui pelo menos duas entradas e duas saídas 1 Revisão de BSI1102 Introd à Informatica 42 Convenções do projeto lógico 8 Elementos de estado continuação 42 Convenções do projeto lógico 9 O DLatch em ação 42 Convenções do projeto lógico 10 Elementos de estado continuação 42 Convenções do projeto lógico 11 O D FlipFlop em ação 42 Convenções do projeto lógico 12 Metodologia de clock 43 Construindo um caminho de dados 13 Elemento de caminho de dados Uma unidade que opera sobre dados ou armazena dados dentro do processador No MIPS os elementos do caminhos de dados incluem as memórias de dados e instruções os registradores e ULA e os somadores Contador de programa O registrador que contém o endereço da instrução do programa que está sendo executada 43 Construindo um caminho de dados 14 Elementos utilizados no ciclo de busca 43 Construindo um caminho de dados 15 Elementos utilizados no ciclo de busca Somador usado para computar PC 4 Saída da instrução de máquina Para os demais elementos 43 Construindo um caminho de dados 16 Elementos utilizados para implementar instruções R format da ULA Ex add t1t2t3 Entrada de dados com largura de 32 bits Saída de dados com largura de 32 bits 43 Construindo um caminho de dados 17 Elementos utilizados para implementar instruções I format de acesso à memória em conjunto com os elementos ULA e Registradores Ex lw t1offsetvaluet2 43 Construindo um caminho de dados 18 Considere as instruções lw t1offsetvaluet2 sw t1offsetvaluet2 Essas instruções computam um endereço de memória pela adição do registrador base t2 e do offsetvalue que é um número de 16 bits com sinal Logo para que a ULA possa adicionar o valor de t2 32 bits com offsetvalue 16bits É necessário extender offsetvalue para 32 bits 43 Construindo um caminho de dados 19 Como juntar os elementos estudados nos slides 16 e 17 para formar um caminho dados para as instruções de acesso a memória lógicas e aritméticas As instruções aritméticas usam a ULA com as entradas vindo de dois registradores O valor a ser armazenado no registrador de destino vem da ULA Rformat ou da memória lw As instruções de acesso à memória usam a ULA para cálculo de endereço A segunda entrada dessa operação é o campo de offsetvalue após a extensão para 32bits considerando o sinal 43 Construindo um caminho de dados 20 Observando as considerações do slide 18 temos Escolhe entre a saída dos registradores ou o valor do campo offset da instrução Escolhe entre a saída da memória ou da ULA rs rt rd rtlw offset Resultado ou o dado da memória 43 Construindo um caminho de dados 21 Considere a instrução beq t1t2offset Para implementar essa instrução é necessário Comparar t1 e t2 e verificar se são iguais Adicionar offset 16bits extendido para 32 bits com o valor do PC para achar o endereço alvo do salto Observar os detalhes de implementação no slide posterior 43 Construindo um caminho de dados 22 Dois detalhes devem ser observados O conjunto de instruções do MIPS especifica que a base para o cálculo do endereço do desvio é o endereço da instrução seguinte a instrução de salto beq ou seja PC 4 A arquitetura também especifica que o campo de offset deve ser deslocado 2 bits para esquerda para se transformar em offset de palavra 43 Construindo um caminho de dados 23 Assim Slide 15 Slide 15 43 Construindo um caminho de dados 24 44 Um esquema simples de implementação 25 Antes de falar sobre o controle da ULA vamos dar uma olhada na própria ULA Começaremos por estudar o projeto de uma ULA de 1bit Para a porção de lógica da ULA de 1 bit temos 44 Um esquema simples de implementação 26 Precisamos agora de um somador completo Para a porção de aritmética da ULA de 1 bit temos 44 Um esquema simples de implementação 27 A especificação do somador de 1 bit 44 Um esquema simples de implementação 28 Dentro do módulo somador iremos encontrar Lógica pra gerar o bit de CarryOut Usando os minitermos da coluna CarryOut temos a b CarryIn a b CarryIn a b CarryIn a b CarryIn CarryOut CarryIn CarryIn a b b b a CarryIn a a b CarryIn CarryOut a b a CarryIn b CarryIn CarryOut 44 Um esquema simples de implementação 29 Assim a lógica para gerar o bit CarryOut é 44 Um esquema simples de implementação 30 Continuando Lógica para gerar o bit Sum Usando os minitermos da coluna Sum temos a b CarryIn a b CarryIn a b CarryIn a b CarryIn Sum 44 Um esquema simples de implementação 31 A lógica para gerar sum é 44 Um esquema simples de implementação 32 Assim temos até agora 44 Um esquema simples de implementação 33 Para acrescentar a operação de subtração b a b a c b a b a Sum CarryIn 1 2 1 44 Um esquema simples de implementação 34 Para acrescentar a operação NORusamos De Morgan a b b a 44 Um esquema simples de implementação 35 Para a operação slt temos Essa instrução produz um resultado 1 se rs rt e 0 em caso contrário Desta forma todos os bits do resultado da ULA serão 0 exceto o bit menos significativo que será setado de acordo com a comparação de rs com rt Assim podemos acrescentar uma entrada Less as ULAs 1bit que será usada apenas para a instrução slt 44 Um esquema simples de implementação 36 O resultado é 44 Um esquema simples de implementação 37 Se ligarmos as entradas das ULAs dos bits 311 a zero e setarmos o valor da ULA do bit bit0 de acoordo com a saída do somador da ULA do bit mais significativo bit31 teremos o resultado correto pois Se a b o resultado é negativo e o bit 31MSb ou bit de sinal será 1 Com isso basta ligar a entrada Less da ULA do bit0LSb a saída set da ULA do bit31 que corresponde a saída do somador dessa ULA O somador que gera o bit31 será ligeiramente diferente dos demais somadores já que tem uma saída que indica overflow e a saída set 44 Um esquema simples de implementação 38 ULAs de 1 bit usadas na ULA de 32 Bits do MIPS 44 Um esquema simples de implementação 39 Para a instrução beq precisamos saber se os operandos são iguais para tanto fazemos a subtração ab e testamos o resultado assim Outro detalhe é que para uma subtração Binvert e CarryIn do bit0 são colocados em 1 então podemos ligar Binvert a CarryIn formando Bnegate 44 Um esquema simples de implementação 40 44 Um esquema simples de implementação 41 Tabela de controle da ULA 44 Um esquema simples de implementação 42 44 Um esquema simples de implementação 43 44 Um esquema simples de implementação 44 Nome do sinal Efeito quando em 0 Efeito quando em 1 RegDst O endereço do registrador de destino para escrita vem do campo rt bits 2016 O endereço do registrador de destino para escrita vem do campo rd bits 1511 RegWrite Nada No registrador identificado pela entrada Write register é gravado o valor presente na entrada Write data ALUSrc O segundo operando da ULA virá da segunda saída do banco de registradores Read data 2 O segundo operando da ULA será o valor extendido para 32 bits do campo Immediate 16 bits menos significadtivos da instrução PCSrc O PC é subtituido pela saída do somador que computa PC 4 O PC é subtituido pela saída do somador que computa o endereço alvo do salto MemRead Nada O conteúdo de memória da posição especificada pela entrada Adress é colocado na saída Read data MemWrite Nada O conteúdo de memória da posição especificada pela entrada Adress é substituído pelo valor presente na entrada Write data MemtoReg O valor da entrada Write data do banco de registradores vem da saída result da ULA O valor da entrada Write data do banco de registradores vem da saída Read data da memória de dados 44 Um esquema simples de implementação 45 44 Um esquema simples de implementação 46 A partir do opcode os sinais de controle são determinados de acordo com a instrucão O X presente em alguns sinais indica que o valor desse sinal não interfere na execução da instrução 44 Um esquema simples de implementação 47 A especificação completa do controle do MIPS reduzido e de ciclo único 44 Um esquema simples de implementação 48 Fluxo de informação para add t1t2t3 1 A instrução é buscada e o PC é incrementado 2 Dois registradores t2 e t3 são lidos do banco de registradores além disso a unidade de controle principal determina o valor dos sinais de controle 3 A ULA opera nos dados obtidos do banco de registradores usando a informação do campo funct da instrução para determinar a operaçãoadd nesse caso 4 O resultado produzido pela ULA é escrito no banco de registrador t1 esse registrador é identificado usando os bits 1511 da instrução campo rd 44 Um esquema simples de implementação 49 44 Um esquema simples de implementação 50 Fluxo de informação para lw t1offsett2 1 A instrução é buscada na memória de instruções e o PC é incrementado 2 O registrador t2 é lido do banco de registradores 3 A ULA calcula a soma do valor de t2 com o valor do campo immediateoffset da instrução extendido para 32bits 4 O resultado da soma é usado como endereço para a memória dados 5 O dado oriundo da memória é gravada em t1 identificado pelos bits 2616 campo rt da instrução 44 Um esquema simples de implementação 51 44 Um esquema simples de implementação 52 Fluxo de informação para beq t1t2offset 1 A instrução é buscada na memória de instruções e o PC é incrementado 2 Os registradores t1 e t2 são lidos do banco de registradores 3 A ULA calcula a sutração t1t2 ou rsrt O valor PC 4 é adicionado ao valor offsetextendido 2 O resultado é endereço alvo do salto 4 O resultado da soma realizada na ULA secundária é usado como endereço para a memória de instruções 5 A saída zero da ULA é testada para determinar qual dos resultados dos somadores irá ser gravado no PC PC4 ou o endereço alvo do salto 44 Um esquema simples de implementação 53 44 Um esquema simples de implementação 54 45 Visão geral sobre pipelining 55 Pipelining é uma técnica de implementação na qual múltiplas instruções são sobrepostas durante a execução Vamos utilizar uma analogia com lavagem de roupas Sem pipelining 1 Colocar um lote de roupas sujas na lavadora 2 Quando a lavadora terminar colocar as roupas na secadora 3 Quando a secadora terminar dobrar as roupas 4 Quando terminar de dobrar pedir ao companheiro de quarto para guardar as roupas 45 Visão geral sobre pipelining 56 Com pipelining 1 Colocar um lote de roupas sujas na lavadora 2 Quando a lavadora terminar o 1º lote colocar as roupas na secadora e carregar a lavadora com o 2º lote de roupas 3 Quando a secadora terminar o 1º lote dobrar o 1º lote por o 2º lote para secar e carregar o 3º lote na lavadora 4 Quando terminar de dobrar o 1º lote pedir ao companheiro de quarto para guardar o 1º lote começar a dobrar o 2ºlote por pra secar o 3º lote e colocar o 4º lote na lavadora Nesse ponto todos os passos estão sendo executados concorrentemente 45 Visão geral sobre pipelining 57 Vejamos agora esse processo representado graficamente Tempo total 8h Tempo total 35h Assim Gvel 835 23 45 Visão geral sobre pipelining 58 Observe que o tempo para processar um lote de roupas não é menor para a abordagem com pipelining No entanto as operações ocorrem em paralelo fazendo com que a vazão de lotes aumente Analizando o que vimos temos Se todos os estágios levam o mesmo tempo para completar sua terefa E há uma quantidade razoável de trabalho a ser realizada Então o ganho de velocidade devido ao pipelining é igual ao número de estágios 45 Visão geral sobre pipelining 59 Assim usando pipelining 20 lotes levariam 5 vezes o tempo de 1 lote para concluir já sem pipilining 20 lotes levariam 20 vezes o tempo de um lote para concluir Na figura do slide 57 esse ganho de velocidade é menor 23 apenas pois temos apenas 4 lotes e dessa forma o pipelining não opera completamente cheio por muito tempo Em outras palavras existe o efeito do início até encher o pipeline e do final esvasiamento do pipeline muito significativo quando a carga de trabalho é próxima do número de estágios do pipelining 45 Visão geral sobre pipelining 60 Os mesmos princípios se aplicam aos processadores que utilizam pipeline As instruções MIPS são realizadas em 5 passos 1 Buscar a instrução da memória 2 Ler os registradores e simultaneamente decodificar a instrução 3 Executar a operação ou calcular um endereço 4 Acessar um operando na memória de dados 5 Escrever um operando em um registrador 45 Visão geral sobre pipelining 61 Exemplo ciclo único x performance do pipeline Considere apenas 8 instruções lw sw add sub and or slt e beq Compare o tempo médio entre instruções de implementações de ciclo único com o de uma implementação usando pipeline Os tempos dos estágios mais importantes de são 200ps para acesso à memória 200ps para operação da ULA 100ps para leitura ou gravação em registradores A operação de multiplexadores unidade de contole bem como o acesso ao PC e a extensão considerando o sinal são considerados como tendo atraso zero 45 Visão geral sobre pipelining 62 Considere a execução de 3 instruções lw pior caso Solução Na implementação de ciclo único o ciclo de clock tem que ser extendido para acomodar a instrução mais lenta Vamos calcular os tempos de cada instrução Logo para a implementação de ciclo único teremos que o ciclo de clock deve ser no mínimo 800ps 45 Visão geral sobre pipelining 63 Para a implemantação com pipeline temos Cada estágio leva um ciclo de clock para completar sua tarefa Assim o ciclo de clock deve acomodar o estágio que leva mais tempo no caso 200ps 45 Visão geral sobre pipelining 64 Com essas informações Podemos calcular o tempo entre a 1ª e a 4ª instruções como ps T sem pipeline 800 ps T com pipeline 200 ps ps Tempo entre instruções sem pipeline 2400 3 800 ps ps Tempo entre instruções com pipeline 600 3 200 45 Visão geral sobre pipelining 65 Graficamente 45 Visão geral sobre pipelining 66 Se considerarmos os estágios perfeitamente balanceados em condições ideais Por essa fórmula o pipeline de 5 estágios teria de oferecer um ganho de velocidade de 5 vezes porém de estágios do pipeline número Tempo entre instruções entre instruções Tempo pipeline sem com pipeline ps ps Tempo entre instruções com pipeline 160 5 800 45 Visão geral sobre pipelining 67 Vimos no exemplo no entando que os estágios podem ser desbalanceados já que Esse valor excede o valor mínimo e com isso teremos um ganho de velocidade menor que o esperado Dessa forma teremos No entanto estamos considerando apenas 3 instruções ps T com pipeline 200 1 71 1400 2400 ps ps Ganho de velocidade 45 Visão geral sobre pipelining 68 Se considerarmos a adição de mais 1 milhão de instruções teremos1000003 instruções Para o caso com pipeline Para o caso sem pipeline Assim ps ps ps 200001400 1400 1000000 200 ps ps ps 800002400 2400 1000000 800 3 9999 200001400 800002400 ps ps Ganho de velocidade 45 Visão geral sobre pipelining 69 Pipeline Hazards Existem situações nas quais a próxima instrução não pode executar no próximo ciclo de clock Esses eventos são chamados hazards e podem ser classificados em 3 tipos Harzards estruturais Quando o hardware não suporta a combinação de instruções que queremos executar no mesmo ciclo de clock Hazards de dados Quando o pipeline precisa parar pois um passo deve esperar que o anterior termine para prosseguir Hazards de controle ou hazards de salto Surge da necessidade de tomar uma decisão baseada no resultado de uma instrução enquanto outras estão executando 45 Visão geral sobre pipelining 70 Exemplos de harzards estruturais Referente a anologia da lavagem de roupas Ocorreria um harzard estrutural se fosse utilizada uma única máquina para lavar e secar em lugar de duas máquinas separadas Ou se o o colega de quarto estivesse ocupado e não pudesse guardar as roupas Referente ao MIPS Se no lugar de usar duas memórias uma para instruções e outra para dados o MIPS usasse apenas uma memória teríamos um hazard estrutural Imagine uma quarta instrução na figura do slide 65 teríamos duas instruções concorrendo pela memória uma para acesso aos dados 1ª Instr e outra para busca de instruções 4ª instr 45 Visão geral sobre pipelining 71 Exemplos de Hazards de dados Referente a anologia da lavagem de roupas Seria sair para procurar o par de uma meia que você encontrou enquanto dobrava as roupas Enquanto você procura as roupas secas terão que esperar seu retorno para serem dobradas assim como as que estão lavadas para serem secas Referente ao MIPS Ocorre quando uma instrução depende de uma instrução anterior que ainda está no pipeline add s0t0t1 sub t2s0t3 Sem nenhuma intervenção um hazard de dados pode parar o pipeline Veja que o resultado de add só será escrito nos registradores no 5º estágio o que torna necessário parar o pipeline por 3 ciclos 45 Visão geral sobre pipelining 72 Uma possível solução para esse problema nasce do fato de que não precisamos esperar a conclusão da instrução para tratar o hazard de dados Para o caso mostrado assim que a ULA produzir o resultado do add nós podemos fornecer essa informação para a execução do sub A adição de hardware extra para armazenar o valor do dado que cria a dependência a partir da saída da ULA antes do final da instrução é conhecida como encaminhamento forwarding 45 Visão geral sobre pipelining 73 Encaminhamento forwarding de dados com 2 instruções Como resolver o problema visto usando um encaminhamento de dados Solução 45 Visão geral sobre pipelining 74 Na representação gráfica do slide 73 os caminhos para encaminhamento de dados só são válidos se o estágio de destino está atrasado no tempo em relação ao estágio de origem Não é válido por exemplo um caminho ligando a saída da memória da 1ª Instrução com a entrada do estágio de execução da 2ª Instrução Pois isso implicaria em voltar no tempo 45 Visão geral sobre pipelining 75 Apesar de funcionar bem o encaminhamento de dados não pode solucionar todas as paradas do pepiline por exemplo Suponha a seguinte sequência de instruções Observe que para poder usar o encaminhamento de dados precisamos atrasar por um ciclo a instrução sub lw s020t1 sub t2s0t3 45 Visão geral sobre pipelining 76 Graficamente Observe que estamos fazenddo uma simplificação desde que não poderíamos saber se haveria necessidade de parar o pipeline antes de buscar e decodifcar a instrução sub Vamos ver de forma mais precisa essa bolha do pipeline 45 Visão geral sobre pipelining 77 Reodenando código para evitar paradas do pipeline Considere o seguinte segmento em C Que em assembly do MIPS fica Encontre Hazards no código e reordeneo de forma a evitar paradas do pipeline a b e c b f lw t10t0 lw t24t0 add t3t1t2 sw t312t0 lw t48t0 add t5t1t4 sw t516t0 45 Visão geral sobre pipelining 78 Solução Hazards As duas instruções add provocarão uma parada devido sua dependência em relação a instrução lw imediatamente anterior Reordenando para evitar paradas lw t10t0 lw t24t0 lw t48t0 add t3t1t2 sw t312t0 add t5t1t4 sw t516t0 45 Visão geral sobre pipelining 79