AOC – Pipeline II

Arquitetura e Organização de Computadores

Pipeline II

Na continuação de Pipeline, vou explicar o que são e como tratar os Hazards de Pipeline.

Hazards

Hazards são, como vimos no fim do post Pipeline I, situações que impedem o pipeline de continuar sua execução natural ou o fazem perder performance por computar incorretamnete. Existem três tipos de Hazards, são eles:

• Hazards Estruturais
• Hazards de Dados
• Hazards de Controle

1. Estruturais

Hazards Estruturais acontecem quando duas ou mais instruções sobrepostas no pipeline tentam usar o mesmo recurso de hardware ao mesmo tempo. Por exemplo se um processador possui memória compartilhada entre dados e instruções, em um momento em que o estágio MEM (referência à memória) e o estágio IF (busca uma instrução) ficam sobrepostos no pipeline, ocorre um hazard estrutural.

Isso pode ser simplesmente resolvido com o uso de bolhas no pipeline. Isso significa dizer que:

# É possível inserir “bolhas” (instruções sem operações) no pipeline e atrasar a execução da instrução atual até que o operando requerido seja computado corretamente e escrito no registrador. Esse método diminui a eficiência do pipeline, que é totalmente o oposto da idéia do próprio pipeline, mas mesmo assim, é uma estratégia válida porque reduz o custo de memória quase que pela metade em uma máquina que suporta acesso à memória e à instruções a cada estágio do pipeline para evitar o hazard, por exemplo.

2. De Dados

Hazards de Dados acontecem quando uma instrução depende no resultado de uma instrução anterior de modo que a primeira instrução ainda não computou esse resultado. Como por exemplo:

ADD R1, R2, R4         ; Instrução 1
SUB R4, R5, R1          ; Instrução 2
AND R6, R1, R7         ; Instrução 3
OR R8, R1, R9            ; Instrução 4
XOR R10, R1, R1  1   ; Instrução 5
(Instruções de processadores da arquitetura RISC, onde Rn são registradores)

Nesse caso, R1 só é escrito no último estágio de execução da instrução 1, mas já é usado no segundo estágio da instrução 2. Veja:

ADD	R1, R2, R3	IF	ID	EX	MEM	WB
SUB	R4, R5, R1		IF	ID	EX	MEM	WB

A tabela acima ilustra bem essa situação no caso RAW. O estágio de Decodificação (ID) da instrução SUB precisa do valor de R1, mas esse valor não vai ser computado até o estágio WB (Writeback), onde a instrução ADD faz escrita no registrador.

Existem três tipos de Hazards de Dados:
– Imaginem duas instruções 1 e 2. 

• RAW (Read After Write – Leitura depois da escrita): Também chamado de Hazard de Dependência, ocorre quando a instrução 2 usa o resultado da instrução 1 que ainda não foi calculado ou buscado.Isso ocorre porque mesmo que a instrução 2 venha depois da instrução 1, no pipeline ela é executada simultaneamente, como no nosso exemplo da tabela acima.Outro exemplo:

   SUB R1, R2, R3  ; Instrução 1
  ADD R4, R1, R3  ; Instrução 2

• WAR (Write After Read – Escrita depois da leitura) : Também chamado de Hazard de Anti Dependência, ocorre em pipelines de tamanho variável, quando a instrução 2 escreve no registrador antesque a instrução 1 o leia. Por exemplo:

  SUB R4, R1, R3  ; Instrução 1
  ADD R1, R2, R3  ; Instrução 2

  SUB	R4, R1, R3	IF	…	…	…	…	…	ID
  ADD	R1, R2, R3		IF	ID	EX	MEM	WB

  A tabela acima ilustra essa situação bem, onde por algum motivo a instrução 1 levou mais ciclos de clock para realizar a leitura para os registradores, mas a instrução 2 realizou escrita nesse registrador antes.

• WAW (Escrita depois de escrita) : Também chamado de Hazard de Output, ocorre apenas em pipelines que escrevem em mais de um estágio ou permitem que uma instrução continue sua execução mesmo quando uma instrução anterior está parada (vamos ver o que são instruções ‘paradas’ logo abaixo).

   SUB R1, R4, R3  ; Instrução 1
  ADD R1, R2, R3  ; Instrução 2

  SUB	R1, R1, R3	IF	ID	…	…	…	…	WB
  ADD	R1, R2, R3		IF	ID	EX	MEM	WB

  A tabela acima mostra como o hazard ocorre. Por algum motivo a instrução 1 levou mais ciclos de clock para terminar, enquanto isso a instrução 2 executou todos seus estágios, incluindo o de escrita. O problema é que a instrução 2 está executando a operação em um registrador que ainda não foi escrito pela instrução 1.

Para resolver os Hazards de Dados, existem algumas opções também:

• Forwarding – Para resolver os problemas de dependência, foi criada uma técnica chamada de Forwarding, onde um novo circuito é adicionado ao pipeline. É como um barramento que corta caminho através do pipeline. Apesar da necessidade de adicionar um novo circuito ao hardware, funciona bem por ser bem mais rápido transferir um dado via hardware do que esperar um estágio do pipeline terminar de executar para então preparar os dados para a próxima instrução que depende deles.
• Reordenação de Código – O problema é evitado usando um compilador ‘inteligente’ que reordena o código em assembly para evitar esses tipos de dependência. Não é muito comum, pois o compilador deve ter informações detalhadas da estrutura e do ‘rítmo’ de execução do pipeline no qual o hazard ocorreria. Esse tipo de compilador é chamado de Compilador Dependente de Hardware.
• Inserção de Bolhas – Como vimos nos Hazards de Estrutura, inserimos uma bolha no pipeline para atrasar a execução da instrução, ganhando tempo para a instrução posterior. Nesse caso é um método de última opção que pode ser usado quando forwarding ou o auxílio de um compilador especial não estiver disponível ou não for suportado pelo hardware.

3. De Controle

Como vimos no último post de AOC (Pipeline I), um dos mais comuns problemas de pipeline são os de desvio de fluxo. Esses problemas são os Hazards de Controle e são causados por desvios e outras instruções que alteram o PC (Program Counter).

Recapitulando um pouco, é comum em Hazards de Controle acontecerem em situações como:

MOV AX, 10h      ; Instrução 1

CMP AX, BX         ; Instrução 2

    JAE  9f                  ; Instrução 3

SUB AX, 5h           ; Instrução 4

…

9: ADD SP, 8          ; Instrução 15

…

Até a instrução 3, o processador não sabe qual instrução deve executar a seguir, por isso, geralmente continua o fluxo normal da instrução 4 e adiante. Porém, caso o jump da instrução 3 seja feito, todas as instruções buscadas entre o primeiro estágio de pipeline da instrução 3 até o fim do estágio de execução são removidas do pipeline e o processador deve então pôr a instrução 15 no pipeline para executa-la, ficando ocioso por um tempo significante. Esse tempo em que fica ocioso é chamado de penalidade de desempenho.

Mostrando de novo a ilustração dessa situação:

Desvio Condicional e Penalidade de Desempenho

Hazards de Controle podem ser tratados dos seguintes modos:

• Inserção de bolha – Insere-se uma bolha no pipeline até que seja computado se o desvio vai ser tomado ou não.
• Nunca tomar o desvio – Como foi mostrado em nosso exemplo, assume-se que o desvio nunca é tomado e a execução sempre ocorre naturalmente. Caso no fim do pipeline da instrução o desvio seja tomado, ocorre a penalidade de desempenho.
• Sempre tomar o desvio – Nessa abodagem, o pipeline sempre assume que o desvio vai ser tomado e já começa a agendar as instruções posteriores ao desvio sem saber se ele na verdade vai ser tomado ou não.

Desses três métodos de tratamento dos Hazards de Controle, o mais comum, assim como pra qualquer outro hazard é o uso de bolhas. Nesse caso o pipeline é parado até que seja computado o estágio de decisão de fluxo, evitando quaisquer tipos de penalidades e perdas maiores de desempenho.

Bom, é isso aí, acabamos então o assunto de hazards de pipeline. Qualquer coisa, só deixar um comentário!

Até!

AOC02 – CISC & RISC

Arquitetura e Organização de Computadores

Arquiteturas CISC e RISC

A aula de hoje foi entrando mais a fundo nos detalhes das arquiteturas CISC e RISC, um assunto muito interessante e cheio de coisas, então vou pular os rodeios e ir direto ao ponto.

CISC – Complex Instruction Set Computer

Ou, traduzindo para o português: Computador de Conjunto Complexo de Instruções “é uma arquitetura de processadores capaz de executar centenas de instruções complexas diferentes sendo assim, extremamente versátil” – trecho da descrição da arquitetura no Wikipédia.

CISC é a arquitetura usada pelos processadores da família Intel x86, presente na maioria (se não, em grande parte) dos computadores pessoais hoje em dia e é bem provável que o seu seja um desses também.

De modo geral, a filosofia da arquitetura é que hardware sendo mais rápido que software, os processadores deveriam ter conjuntos de instruções mais poderosos, permitindo aos programadores fazer bem mais coisas com menos linhas de código, se aproximando mais à linguagens de alto nível.

Uma visão geral da arquitetura CISC:

• Necessidade:
  Os processadores devem ser capazes de executar operações complexas para se aproximar mais das instruções de linguagens de programação de alto nível. Com o crescimento das linguagens de alto nível como C, FORTRAN ou ALGOL no fim da década de 70 e início da década de 80, os desenvolvedores de compiladores começaram a ter muita dificuldade em manter uma boa performance e simplicidade do código gerado em assembly para os programas escritos nessas linguagens de alto nível por causa de suas instruções mais complexas.
• Problema:
  Essa distância entre as instruções de linguagem de máquina existentes na arquitetura de processadores da época e as instruções complexas das linguagens de alto nível gerou uma distância entre as duas que ocasionava em maior necessidade de uso do processador para executar os programas. Esse distância é chamada de gap semântico e é um grande problema da arquitetura CISC existente até nos dias de hoje, pois a capacidade de processamento do processador deve aumentar de acordo com a complexidade das linguagens de alto nível.
• Solução:
  Para diminuir o gap semântico, os arquitetos de processadores tiveram que além de criar instruções mais complexas, utilizar uma micro programação nos processadores CISC, isto é, criar uma camada de microcódigo a nível de hardware na qual as instruções complexas em Assembly serão traduzidas e então executadas. Essas operações em microcódigo, porém, nem sempre tornavam o processador mais rápido, mas pelo contrário, em algumas situações como onde não era necessário o uso de instruções complexas, essa camada de microcódigo poderia gerar mais ciclos de execução para uma instrução simples. Outra situação é que os processadores CISC possuem um número limitado de registradores de propósito geral. Nos x86 da Intel são apenas 4 (AX, BX, CX e DX) e a memória RAM é constantemente usada em operações, o que além de ser mais lento (visto que os registradores estão dentro do próprio processador, diferente da memória RAM) requer vários modos de endereçamento para as instruções fazendo com que seus tamanhos nem sempre sejam iguais e tornando o trabalho do decodificador um bocado mais difícil – e lento.

  Vale notar então que a “solução” de utilizar instruções complexas e uma camada de microcódigo acabou por gerar novos problemas.

• Vantagens:
  Com as instruções complexas, algumas instruções em uma linguagem de alto nível poderia traduzir para exatamente uma instrução em Assembly, reduzindo a dificuldade para escrever compiladores, aumentando a compactação de código, facilitando o processo de debug, aumentando a eficiência de programas escritos em linguagens de alto nível e com isso diminuindo seus custos, tamanhos e complexidades.
• Desvantagens:
  Em alguns casos, o uso de mais instruções simples era mais eficiente do que usar menos instruções complexas, pelo fato de o microcódigo gerar novos ciclos de execução e o decodificador ter mais dificuldade para decodificar as instruções. Sem contar com o uso de operandos de memória, que podem causar hazards estruturais prevenindo a execução de instruções paralelas no pipeline.

É isso aí, amanhã termino o post com um resumo da arquitetura RISC.
Talvez dê alguma editada aqui e adicione mais alguma coisa, também.

Até!

AOC – Pipeline I

AOC?

Para evitar grandes títulos, ao decorrer dos posts, vou procurar utilizar siglas em vez dos nomes completos das disciplinas, mas os escrevendo por extenso no cabeçalho dos posts.

Então, começando:

Arquitetura e Organização de Computadores

Pipeline

Então, se você é da área, provavelmente já ouviu falar em Pipeline. Na aula de hoje aprendi o que é o Pipeline, conheci seus hazards e suas estratégias te otimização.

Em poucas palavras:

• O que é? Pipeline é a implementação de uma técnica para otimizar o processador .
• Como? O Pipeline é baseado em cliclos de clock para processar uma instrução. Cada instrução é quebrada em um número N de passos cada um guardando um valor que será usado como input no próximo passo. No Pipeline, essas instruções são sobrepostas de modo que a cada ciclo do clock, um passo de cada instrução seja executado (Fig. 1), evitando deixar componentes do processador ociosos. A performance do processador é aumentada proporcionalmente ao número de passos em que as instruções são quebradas.

Fig. 1 - Cada instrução possui 6 passos que são sobrepostos no Pipeline e executados a cada ciclo de clock de modo que a partir do 5o ciclo, a cada novo ciclo uma instrução é terminada.

Com mais detalhes:

Antes, vale a pena lembrar que:

Uma instrução em linguagem de montagem (Assembly) é formada por campos que guardam os dados necessários para a execução da instrução, geralmente apresentados como:

• Opcode (Código de Operação) – Código que em Assembly é representado por um mnemônico, ou abreviações como ADD, MOV, STOR, etc. e indica a operação que vai ser executada, tanto quanto o modo de endereçamento de operandos utilizado.
• N Campos de endereço – O número de campos de endereço dos operandos varia de acordo com a necessidade da operação. Geralmente de 0 a 3 operandos sendo eles o operando fonte, operando destino e dependendo da arquitetura do conjunto de instruções, uma referência à próxima instrução.

E que a CPU possui componentes internos como Buscador de Instruções, Decodificador de Instruções, Conjunto de Registradores e ULA(Unidade Lógica e Aritmética) para citar os mais comuns, com isso em mente podemos dizer que quando uma instrução é apresentada ao processador, ele ativa cada um desses componentes internos para realizar uma parte da execução dessa instrução. Esse processo é demonstrado na Fig. 2 abaixo:

Fig. 2 - Diagrama do Ciclo de Instrução

De acordo com a Fig. 2, vemos que para cada passo da execução de uma instrução apenas um componente da CPU é utilizado, deixando todos os outros componentes ociosos, e isso é um grande desperdício de processador. Para resolver esse problema, o Pipeline foi introduzido na organização dos processadores.

Como visto na Fig. 1, o Pipeline é dividido em estágios de acordo com o ciclo de instrução. O número de estágios varia dependendo do tipo de processador, em nosso caso são 6:

• FI (Fetch Instruction) – Busca a próxima instrução e a armazena em um buffer.
• DI (Decodificar Instrução) – Determina o opcode e os operandos que serão usados.
• CO (Calcular Operandos) –  Calcula o endereço dos operandos de origem baseado na forma de endereçamento usada na instrução.
• FO (Fetch Operands) – Busca cada operando da memória, de uma E/S (I/O) ou de um registrador.
• EI – Executa a operação indicada na instrução.
• WO (Write Operand) – Escreve o resultado na memória.

Desse modo, é possível sobrepor as instruções permitindo que a cada ciclo de clock o processador utilize todos seus componentes para executar cada estágio de diversas instruções ao mesmo tempo. Aumentando a performance do processador de modo que:

• No estágio 1, a instrução é buscada e armazenada. Já no estágio 2 o Decodificador é ativado para interpretar a instrução, enquanto o estágio 1 está buscando uma nova instrução. Quando os estágios 1 e 2 terminam, o estágio 2 passa para o estágio 3 e começa a calcular os operandos, o estágio 1 passa para o estágio 2 e começa a decodificar a instrução recém adquirida e o estágio 1 busca uma nova instrução. Mantendo sempre os componentes responsáveis por cada estágio trabalhando. Isso monta a escada de execução mostrada na Fig. 1.

Agora que já entendemos o que é o Pipeline de instruções, algumas perguntas são feitas:

1. Se no pipeline várias instruções são executadas ao mesmo tempo, como o processador sabe quais vão ser essas próximas instruções?

• De modo geral, o pipeline carrega sempre a próxima instrução na sequência. Veja o trecho de código abaixo.

MOV AL, 1h             ; Instrução 1

MOV EAX,  [EBX]  ; Instrução 2

SUB AH, AL             ; Instrução 3

…

Cada instrução é carregada no pipeline na ordem de sequência. A instrução 1, depois a 2, depois a 3. E isso funciona muito bem, se assumirmos que cada instrução sempre vai passar por todos os 6 estágios do pipeline, o que nem sempre acontece. Uma instrução de LOAD, por exemplo, não tem resultado e não precisa do último estágio WO (para escrever um resultado na memória). Além disso, supõe-se que todos estágios podem ser executados em paralelo e que não haverão conflitos de memória. De todos os possíveis problemas que podem aparecer no pipeline, se destaca um: desvios condicionais.

Como o pipeline busca a próxima instrução n+1 antes que a instrução anterior n termine de executar, o que acontece quando a instrução n é um desvio condicional?

MOV AX, 10h      ; Instrução 1

CMP AX, BX         ; Instrução 2

    JAE  9f                  ; Instrução 3

SUB AX, 5h           ; Instrução 4

…

9: ADD SP, 8          ; Instrução 15

…

No trecho de código acima temos um exemplo de desvio condicional, onde se a comparação na instrução 3 for verdadeira, o programa é desviado para a instrução 15, como demonstrado na Fig. 3.

Fig. 3 - Desvio Condicional e Penalidade de Desempenho

Em uma situação como essa, no início na execução da instrução 3, o processador não tem nenhuma maneira de saber se o desvio será tomado ou não, então as instruções da sequência são executadas e ao fim da execução da instrução 3, se o desvio for tomado, todas as instruções entre 3 e 15 são removidas do pipeline e nenhuma instrução é executada entre os tempos t8 e t12. Isso é chamado de penalidade de desempenho.

Outras situações que resultam em perda de desempenho do pipeline ocorrem quando o pipeline ou alguma parte dele, precisa parar porque alguma condição não permite que ele continue. Essas ‘paradas’ são chamadas de bolhas e essas situações que causam de perda de desempenho no pipeline, o impedem de prosseguir ou o fazem computar incorretamente são chamadas de Hazards do Pipeline e são divididos em três tipos que serão detalhados no próximo post de AOC. Os três tipos de hazards são: recurso, dados e controle.

Até a próxima!