Aula 10 – Sumário Aritmética Aceleração da adição Multiplicação binária Pipelines Princípio de funcionamento Conflitos de dados, estruturais e de controlo 1 Aritmética Aceleração da adição 2 Adição básica (revisão) Um circuito full adder… A B Cin S Cout Soma os bits A e B com o transporte anterior (Cin), dando o resultado da soma (S) e o transporte que sai (Cout) 3 Adicionador Ripple-carry A0 C0 B0 FA S0 A1 C1 B1 FA S1 A2 C2 B2 FA S2 A3 C3 B3 FA C4 S3 Obtém-se ligando em série tantos full-adders quanto o nº de bits dos números que se querem somar. Desvantagem: Como que cada full adder impõe um atraso, o tempo necessário para ser feita a soma é proporcional ao nº de bits dos números a somar 4 Adicionador Ripple-carry Outra maneira de ver PFA A B Cin S Cout Cout PFA – Partial Full Adder 5 Adicionador Ripple-carry Outra maneira de ver A B PFA Cin P G S Cout Em que: Propagação de carry P AB G AB Geração de carry 6 Adicionador Ripple-carry Para um ripple adder de 4 bits A0 B0 PFA C0 P0 G0 A1 S0 C1 B1 PFA P1 G1 A2 S1 C2 B2 PFA P2 G2 A3 S2 C3 B3 PFA P3 S3 G3 C4 P’s e G’s são todos calculados ao mesmo tempo (em paralelo), pois só dependem dos A’s e dos B’s. Os bits da soma (S’s) têm que esperar que chegue o Cin respectivo. 7 Adicionador Ripple-carry Para um ripple adder de 4 bits A0 B0 PFA C0 P0 G0 A1 S0 C1 B1 PFA P1 G1 A2 S1 C2 B2 PFA P2 A3 S2 G2 C3 B3 PFA P3 S3 G3 C4 Caminho crítico – corresponde ao pior caso na propagação dos sinais. Tipicamente é o que atravessa mais portas lógicas. 8 Acelerar a adição Vamos usar as seguintes equações: C i 1 Gi Pi C i Gi Ai Bi Pi Ai Bi C1 G0 P0C0 C 2 G1 P1C1 G1 P1 G0 P0C 0 G1 P1G0 P1P0C 0 C3 G2 P2C 2 G2 P2 G1 P1C1 G2 P2 G1 P1 G0 P0C0 G2 P2G1 P2 P1G0 P2 P1P0C0 C 4 ... 9 Acelerar a adição A partir das equações anteriores obtém-se: A0 B0 PFA C0 P0 G0 A1 S0 C1 B1 PFA P1 A2 S1 G1 B2 PFA P2 A3 S2 G2 B3 PFA P3 S3 G3 C2 C3 C4 10 Adicionador Carry Lookahead Este tipo de adicionador designa-se por Carry Lookahead Adder (CLA) Repare no atraso associado à propagação do carry até ao último PFA – corresponde ao de 2 portas lógicas E se quisesse construir um CLA de 8 bits ? Problema com o desenho anterior: para calcular carrys de ordem elevada (e.g. C7) precisaria de portas lógicas com muitas entradas... difícil de implementar na prática Uma abordagem mais realista seria fazer um esquema onde apenas se usassem portas lógicas com 2 entradas 11 Adicionador Carry Lookahead A0 C0 B0 A1 S0 PFA P0 G0 P01 B1 A2 S1 PFA C1 P1 G1 G01 B2 A3 S2 PFA P2 P23 G2 B3 S3 PFA C3 P3 G3 G23 C2 P03 G03 C4 12 Adicionador Carry Lookahead A0 C0 B0 A1 S0 PFA P0 G0 P01 B1 A2 S1 PFA C1 P1 G1 G01 B2 A3 S2 PFA P2 P23 G2 B3 S3 PFA C3 P3 G3 G23 C2 P03 G03 C4 O caminho crítico está representado a vermelho 13 Adicionador Carry Lookahead A0 C0 B0 PFA A1 S0 B1 PFA A2 S1 B2 PFA C8 A3 S2 B3 PFA A4 S3 B4 PFA A5 S4 B5 PFA A6 S5 B6 PFA A7 S6 B7 PFA S7 Um CLA de 8 bits 14 Adicionador Carry Lookahead Comparação entre os adicionadores: (supondo que apenas são utilizadas portas lógicas com 2 entradas) Ripple-carry CLA Nº de bits Tempo Nº de portas Tempo Nº de portas 4 9tPD 20 7tPD 29 8 17tPD 40 11tPD 61 16 33tPD 80 15tPD 125 32 65tPD 160 19tPD 253 64 129tPD 320 23tPD 509 128 257tPD 640 27tPD 1021 15 Adicionador Carry Select A0...A3 0 Cin B0...B3 4-bit adder Cout A4...A7 0 Cin B4...B7 4-bit adder 1 Sel Sel . S0...S3 0 Cin 4-bit adder 1 Mux S4...S7 A ideia consiste em ir preparando somas parciais para ambas as hipóteses de carry in. O carry out do bloco anterior irá seleccionar qual dos 2 resultados é válido. 16 Adicionador Carry Skip A0..A3 C0 Ci B0..B3 4-bit Co adder A4..A7 Ci B4..B7 4-bit Co adder P4,7 S0..S3 S4..S7 A8..A11 Ci B8..B11 4-bit Co adder A12..A15 B12..B15 Ci 4-bit Co adder C16 P8,11 S8..S11 S12..S15 Composto por vários blocos onde são calculados os P’s. Estes cálculos permitem propagar o bit de transporte directamente ao bloco seguinte. Poupa-se tempo de propagação nos blocos que ficam no meio. 17 Comparação entre adicionadores Material necessário Tempo de operação 2000 Ripple 250 Tempo (x tPD ) Número de portas lógicas 300 CLA 200 Select 150 Skip 100 50 0 Ripple CLA 1500 Select Skip 1000 500 0 0 32 64 96 Número de bits Adicionador Tempo Ripple O(n) Carry lookahead O(log2 n) Carry skip O(√n) Carry select O(√n) 128 0 32 64 96 128 Número de bits O(x) significa “evolução assimptótica proporcional a x” 18 Aritmética Multiplicação binária 19 Multiplicação binária Multiplicação (sem sinal) 1101 multiplicando (A) × 1010 multiplicador (B) 0000 1101 0000 1101 10000010 produto (P) Quando se multiplicam dois números de n bits (sem sinal), o resultado terá, no máximo, 2n bits. 1101 (13) × 1010 (10) = 10000010 (130) 20 Multiplicação binária Multiplicação (sem sinal) A3 A2 A1 A0 B3 B2 B1 B0 B0A3 B0A2 B0A1 B0A0 B1A3 B1A2 B1A1 B1A0 B2A3 B2A2 B2A1 B2A0 B3A3 B3A2 B3A1 B3A0 P6 P5 P4 P3 × P7 P2 ANDs entre os bits de A e os bits de B P1 P0 21 Multiplicação binária Utilizando vários adicionadores... A3 A2 A1 A0 × B3 B2 B1 B0 0 B0A3 B0A2 B0A1 B0A0 + B1A3 B1A2 B1A1 B1A0 cout1 S13 S12 S11 S10 + B2A3 B2A2 B2A1 B2A0 cout2 S23 S22 S21 S20 + B3A3 B3A2 B3A1 B3A0 cout3 S33 S32 S31 S30 P7 P6 P5 P4 P3 Somadores P2 P1 P0 22 Multiplicação binária A3 A2 A1 A0 B0 Pode-se seguir esta estrutura A3 A2 A1 A0 B1 X A3 A2 A1 A0 Cout B2 Cout B3 ADD Y S X A3 A2 A1 A0 0 ADD Y S X Cout ADD Y S P7 P6 P5 P4 P3 P2 P1 P0 23 Multiplicação binária Utilização de vários adicionadores Se os números a multiplicar são compostos por n bits então são necessários n – 1 adicionadores de n bits cada um Desvantagens: Excesso de material por exemplo, para multiplicar dois números de 32 bits seriam necessários 31 somadores de 32 bits Demasiado consumo de tempo durante um ciclo Num processador, ter um multiplicador deste género pode aumentar de forma significativa a duração de cada ciclo do sinal de relógio, devido aos tempos de propagação dos somadores 24 Multiplicação binária Alternativa: usar um único somador e registos O resultado é calculado em n ciclos Material necessário Um registo para acumular as somas – RP Um registo de deslocamento para a esquerda e outro para a direita – RA e RB RP e RA são registos de 2n bits para RB, um registo de n bits é suficiente 25 Multiplicação binária Algoritmo básico (para inteiros sem sinal) Inicialização: RP ← 0, RA ← A, RB ← B Ciclo (n iterações) se ( RB0 == 1 ) // bit menos significativo em RB RP ← RP + RA RA ← RA << 1, RB ← RB >> 1 No final, o resultado da multiplicação está em RP 26 Multiplicação binária Hardware para o algoritmo básico B A Shift right Shift left RB Serial out RA RB0 ADD Load RP 27 Multiplicação binária Exemplo – multiplicar 1010 por 1001 (i.e. 109) Inicialização: RP: 0000 0000 RA: 0000 1010 RB: 1001 Ciclo 3 (RB0 = 0) RP: 0000 1010 RA: 0101 0000 RB: 0001 Ciclo 1 (RB0 = 1) RP: 0000 1010 RA: 0001 0100 RB: 0100 Ciclo 4 (RB0 = 1) RP: 0101 1010 RA: 1010 0000 RB: 0000 Ciclo 2 (RB0 = 0) RP: 0000 1010 RA: 0010 1000 RB: 0010 O resultado será então: RP: 01011010 = 21+23+24+26 = 2+8+16+64 = 90 28 Pipelines 29 Introdução Arquitectura com unidade de controlo uniciclo Unidade de controlo Load / INC Controlo de saltos PC Memória de programa Memória de dados Descodificador de Endereços Leitura/Escrita Tipo de salto Descodificador de Instruções Palavra de Controlo Datapath Bits de estado (flags) 30 Introdução A mesma ideia, posta de uma forma diferente... Fetch Descodificação M U X Execução Controlo de saltos Const P C Memória de instruções Write back End. salto Tipo salto Inc Acesso à memória Banco de registos M U X ALU Memória de dados M U X 31 Introdução Por cada instrução tem-se a sequência Fetch Descodificação Execução Memória Write-back IF ID EXE MEM WB Fetch (IF) – ler a instrução localizada no endereço dado por PC Descodificação (ID) – obter o opcode e operandos; ler os registos fonte Execução (EXE) – operações na ALU e controlo dos saltos Memória (MEM) – aceder à memória para escrever ou ler dados Write-back (WB) – escrever o resultado no registo de destino 32 Funcionamento em pipeline Estrutura de um pipeline Separam-se as várias etapas por registos (buffers) E sincronizam-se esses registos com um sinal de relógio comum… IF ID EXE MEM WB Clock 33 Funcionamento em pipeline Com mais detalhe... M U X End. salto Controlo de saltos Tipo salto Inc Const Memória de instruções Banco de registos M U X ALU Flags P C Memória de dados M U X 34 Funcionamento em pipeline Ideia semelhante a uma linha de montagem: Por cada impulso de relógio é realizada uma etapa de cada instrução que está dentro do pipeline Se o pipeline tem N etapas, então N instruções podem estar simultaneamente dentro do pipeline Inst. i+4 Inst. i+3 Inst. i+2 Inst. i+1 Inst. i IF ID EXE MEM WB Clock 35 Funcionamento em pipeline Ilustração do funcionamento Inst. 1 Inst. 2 Inst. 3 Inst. 4 Inst. 5 Inst. 6 … IF Programa a correr ID EXE MEM WB Clock 36 Funcionamento em pipeline Ilustração do funcionamento Inst. 1 Inst. 2 Inst. 3 Inst. 4 Inst. 5 Inst. 6 … Programa a correr Inst. 1 IF ID EXE MEM WB Clock 37 Funcionamento em pipeline Ilustração do funcionamento Inst. 1 Inst. 2 Inst. 3 Inst. 4 Inst. 5 Inst. 6 … Programa a correr Inst. 2 Inst. 1 IF ID EXE MEM WB Clock 38 Funcionamento em pipeline Ilustração do funcionamento Inst. 1 Inst. 2 Inst. 3 Inst. 4 Inst. 5 Inst. 6 … Programa a correr Inst. 3 Inst. 2 Inst. 1 IF ID EXE MEM WB Clock 39 Funcionamento em pipeline Ilustração do funcionamento Inst. 1 Inst. 2 Inst. 3 Inst. 4 Inst. 5 Inst. 6 … Programa a correr Inst. 4 Inst. 3 Inst. 2 Inst. 1 IF ID EXE MEM WB Clock 40 Funcionamento em pipeline Ilustração do funcionamento Inst. 1 Inst. 2 Inst. 3 Inst. 4 Inst. 5 Inst. 6 … Programa a correr Inst. 5 Inst. 4 Inst. 3 Inst. 2 Inst. 1 IF ID EXE MEM WB Clock 41 Funcionamento em pipeline Ilustração do funcionamento Inst. 1 Inst. 2 Inst. 3 Inst. 4 Inst. 5 Inst. 6 … Programa a correr Inst. 6 Inst. 5 Inst. 4 Inst. 3 Inst. 2 IF ID EXE MEM WB Clock 42 Funcionamento em pipeline Outra maneira de ver.. Ciclos de relógio inst 1 inst 2 inst 3 inst 4 inst 5 inst 6 ... 1º 2º 3º 4º 5º 6º 7º 8º 9º 10º IF ID EXE MEM WB IF ID EXE MEM WB IF ID EXE MEM WB IF ID EXE MEM WB IF ID EXE MEM WB IF ID EXE MEM WB ... .... .... ... 11º ... Por exemplo, no 5º ciclo de relógio, a instrução 1 está na fase WB, a instrução 2 na fase MEM, a instrução 3 na fase EXE, a inst. 4 está na fase ID e a inst. 5 na fase IF. 43 Desempenho em condições ideais Em condições ideais: O pipeline está bem dividido todas as etapas demoram o mesmo tempo O pipeline encontra-se sempre cheio tem-se sempre uma instrução em cada etapa Tnew Told N etapas CPIideal 1 Ganho (ideal) face a uma versão sem pipeline: Ganhoideal Netapas 44 Conflitos (pipeline hazards) Mas num pipeline nem tudo são rosas... Existem situações em que Instruções em fases diferentes tentam aceder ao mesmo recurso (e.g. à memória) O resultado de uma instrução depende de outra que ainda não terminou a execução Situações deste género designam-se por conflitos (ou pipeline hazards) A existência de conflitos afectam o CPI médio, reduzindo o ganho de um pipeline... 45 Tipos de conflitos Conflitos de dados ocorrem quando existem dependências de dados entre instruções que se encontram dentro do pipeline Conflitos estruturais ocorrem quando duas instruções em fases diferentes tentam aceder ao mesmo recurso Conflitos de controlo ocorrem em instruções de salto, quando o salto depende de um resultado que ainda não foi calculado 46 Conflitos de dados Conflito RAW (Read after Write) Para ilustrar a ocorrência destes conflitos vamos considerar que temos duas instruções: instrução 1 e instrução 2 A instrução 2 vai ser executada depois da instrução 1 Vamos supor que a instrução 2 lê dados que são o resultado da instrução 1 – existe uma dependência entre as instruções O conflito ocorre se a instrução 2 tentar ler os dados antes da instrução 1 os ter escrito A instrução 2 iria ler um valor desactualizado... Exemplo: ... inst. 1: ADD R0, R1, R2 # R0 ← R1 + R2 inst. 2: SUB R5, R0, R4 # R5 ← R0 – R4 ... 47 Conflitos de dados Conflito RAW (cont.) ... ADD R0, R1, R2 SUB R5, R0, R4 ... k k+1 k+2 k+3 k+4 k+5 ... ... ... ... IF ID IF k+6 EXE MEM WB ID EXE MEM WB ... ... ... ... k+7 ... CONFLITO ! A instrução SUB está a utilizar o valor de R0 antes de tempo, pois a instrução ADD ainda não escreveu o resultado... 48 Conflitos de dados Resolução básica de conflitos Detecta-se o conflito Inserem-se bolhas no pipeline Uma bolha é basicamente uma palavra de controlo que manda “não fazer nada” (nop) Cada bolha faz com que seja desperdiçado um ciclo de relógio 49 Conflitos de dados Para o caso anterior, resolve-se o conflito introduzindo 2 bolhas após detectado o conflito O conflito pode ser detectado quando é feita a descodificação do SUB Depois atrasa-se o SUB dois ciclos, de forma a dar tempo para fazer o WB do ADD k k+1 k+2 k+3 ... ... ... ... ... ADD R0, R1, R2 IF ID EXE MEM WB IF ID B ... SUB R5, R0, R4 … Conflito detectado k+4 k+5 k+6 k+7 B EXE MEM WB ... ... ... ... Conflito resolvido 50 Conflitos de dados Outra maneira de ver o problema: SUB R5,R0,R4 IF ADD R0,R1,R2 … ID EXE MEM WB Clock 51 Conflitos de dados Outra maneira de ver o problema: … IF SUB R5,R0,R4 ADD R0,R1,R2 ID EXE … MEM WB Clock 52 Conflitos de dados Outra maneira de ver o problema: … IF SUB R5,R0,R4 B ADD R0,R1,R2 ID EXE MEM … WB Clock 53 Conflitos de dados Outra maneira de ver o problema: … IF SUB R5,R0,R4 B B ID EXE MEM ADD R0,R1,R2 WB Clock 54 Conflitos de dados Outra maneira de ver o problema: … IF … SUB R5,R0,R4 ID EXE B MEM B WB Clock 55 Conflitos de dados Resolução mais eficiente de conflitos RAW Utiliza-se uma técnica chamada forwarding A ideia consiste em disponibilizar resultados nas entradas da unidade funcional (fase EXE)… …ainda antes de ser feito o write-back Quando são detectados conflitos RAW, utilizam-se esses resultados em vez do que foi lido dos registos 56 Conflitos de dados Utilização de forwarding IF ID EXE MEM WB Clock Com mais detalhe: ALU M U X M U X Memória de dados M U X 57 Conflitos de dados Outros conflitos de dados Conflito WAW (Write after Write) Ambas as instruções escrevem dados no mesmo local O conflito ocorre se a instrução 2 tentar escrever antes da instrução 1 escrever Conflito WAR (Write after Read) Uma instrução 1 lê dados do local onde a instrução 2 escreve O conflito ocorre se a instrução 2 tentar escrever antes da instrução 1 ler Só ocorrem em pipelines mais complexos, com várias fases onde são feitas leituras e escritas e nos registos 58 Conflitos estruturais Duas (ou mais) instruções tentam aceder em simultâneo ao mesmo recurso Situação típica Quando se usa uma única memória para dados e programa, não se pode fazer o fetch (IF) ao mesmo tempo que uma instrução acede à memória para ler/escrever dados Outras situações Tentar escrever no mesmo registo em simultâneo (só ocorre em processadores com mais do que uma fase de write-back) Tentar ler ou escrever dados em simultâneo na mesma memória (só ocorre em processadores com mais do que uma fase de acesso à memória) 59 Conflitos estruturais Exemplo de um conflito estrutural k k+1 k+2 k+3 ... ... ... ... ... LOAD R1, a IF ID EXE MEM WB IF ID EXE MEM WB IF ID EXE MEM WB IF ID EXE MEM ADD R3,R4,R5 SUB R6,R6,R7 XOR R1,R4,R5 k+4 k+5 k+6 k+7 WB ... CONFLITO ! Não pode ser feito o fetch ao mesmo tempo que se acede à memória para ler dados (o LOAD)... 60 Conflitos estruturais Resolução do conflito Introdução de uma bolha antes do fetch... k k+1 k+2 k+3 ... ... ... ... ... LOAD R1, a IF ID EXE MEM WB IF ID EXE MEM WB IF ID EXE MEM WB B IF ID ... ADD R3,R4,R5 SUB R6,R6,R7 XOR R1,R4,R5 ... k+4 k+5 k+6 k+7 k+8 EXE MEM WB ... ... ... Conflito resolvido 61 Conflitos estruturais Resoluções mais eficientes Memórias de dados e de instruções separadas Tipicamente este esquema é implementado usando uma memória cache para dados e outra para instruções Instruction pre-fetching É feito antecipadamente o fetch de várias instruções, que ficam guardadas numa memória interna (buffer de instruções) Quando o buffer fica vazio vão-se buscar mais instruções à memória. 62 Conflitos de controlo Ocorrem quando aparecem saltos Saltos incondicionais O processador só fica a saber que é uma instrução de salto na fase ID... ... mas nessa altura, a instrução que está na posição de memória que se segue à de salto já se encontra na fase IF Saltos condicionais Para além do que acontece com os saltos incondicionais, só se sabe vai haver o salto após a verificação da condição de salto (tipicamente associada à fase EXE) 63 Conflitos de controlo Nos saltos condicionais, só depois das flags serem actualizadas é que se sabe se o salto vai ser tomado ou não... Só aqui se sabe que é um salto... M U X End. salto Controlo de saltos Tipo salto Inc Const Memória de instruções Banco de registos M U X ALU Flags P C Memória de dados M U X 64 Conflitos de controlo Exemplo (salto incondicional) ... LBL1: ADD R1, R4, R5 ... STORE a, R1 JUMP LBL1 LBL2: LOAD R1, a ... 65 Conflitos de controlo Ilustração do problema (salto incondicional): k k+1 k+2 k+3 ... ... ... ... ... JUMP LBL1 IF ID EXE MEM WB IF B B B B IF ID EXE MEM WB ... ... ... ... LOAD R1, a ADD R1, R4, R5 ... k+4 k+5 k+6 k+7 k+8 k+9 Perde-se 1 ciclo, pois é feito um fetch inútil da instrução que se segue à de salto (isto assumindo que o controlo está feito de forma a poder actualizar o valor de PC na altura em que a instrução de salto está em ID) 66 Conflitos de controlo Exemplo (salto condicional) ... DEC R1, R1 JZER END Umas vezes há salto, outras não... ADD R0, R1, R2 STORE a, R0 ... END: LOAD R1, a ... 67 Conflitos de controlo Ilustração do problema (salto condicional): k k+1 k+2 k+3 ... ... ... ... ... DEC R1, R1 IF ID EXE MEM WB IF ID EXE MEM WB IF ID B B B IF B B B B IF ID EXE MEM JZER END ADD R0, R1, R2 STORE a, R4 LOAD R1, a k+4 k+5 k+6 k+7 k+8 k+9 WB ... Perdem-se 2 ciclos, pois só se irá actualizar o valor de PC depois do salto entrar na fase EXE (só aí se sabe que o salto se vai verificar ou não)... 68 Conflitos de controlo Minorar a introdução de bolhas: Previsão de saltos (branch prediction) Previsão estática Assume-se que o salto é sempre tomado (predict-taken) Ou se assume que o salto nunca é tomado (predict-not-taken) Previsão dinâmica A previsão depende do que se passou em saltos anteriores O estado da previsão de saltos vai mudando à medida que o programa vai correndo Muito usada em processadores actuais Em caso de previsão errada, perdem-se ciclos de processamento correspondentes às instruções que entretanto entraram no pipeline 69
Download
