pred desvios

40 %
60 %
Information about pred desvios
Entertainment

Published on December 28, 2007

Author: Carlton

Source: authorstream.com

Slide1:  Universidade Federal do Rio Grande do Sul Instituto de Informática CMP134 – Introdução ao Processamento Paralelo e Distribuído Carlos Frederico Schwochow de Miranda cfsmiranda@inf.ufrgs.br Prof. Philippe Olivier Alexandre Navaux Porto Alegre, junho de 2003. Técnicas de Predição de Desvios Slide2:  1. Introdução 2. Técnicas Implementadas em Hardware 2.1 – Técnicas Estáticas 2.2 – Técnicas Dinâmicas 3. Técnicas Implementadas em Software 3.1 – Delayed Branch 3.2 – Branch Folding 3.3 – In line 3.4 – Desenrolamento de Loops 4. Conclusões 5. Referências Bibliográficas Sumário Slide3:  ▪ Paralelismo no nível de instruções (ILP) - ↑ Desempenho; ▪ Técnica Pipeline → Paralelismo Temporal; ▪ Instruções de Desvio → Provocam queda de desempenho; ▪ Representam cerca de 20% das primitivas interpretadas; ▪ De 65 a 80% dos desvios são condicionais; ▪ Endereços Determinados: ▪ desvio incondicional, chamada de procedimento, desvio condicional; ▪ Endereços Indeterminados: ▪ system call, retorno de procedimento; ▪ Técnicas de Predição de Desvios; ▪ Nível de Implementação: ▪ Técnicas Implementadas em Hardware; ▪ Técnicas Implementadas em Software. 1. Introdução Slide4:  2.1 – Técnicas Estáticas 2.1.1 – Predição Fixada ▪ Assume que os desvios sempre (ou nunca) são tomados; ▪ Instrução alvo do desvio X Instrução adjacente; ▪ Desvios incondicionais e Loops → Desvios sempre tomados. 2. Técnicas Implementadas em Hardware Figura 2.1 – Predição Fixada - Desvios sempre tomados Slide5:  2.1.2 – Predição determinada pelo Código de Operação ▪ Alguns desvios apresentam uma tendência maior por um dos fluxos; ▪ Predição associada ao Código de Operação da instrução. Figura 2.2 – Predição Fixada X Baseada no Código de Operação Slide6:  Figura 2.3 – Predição Fixada X Baseada na História 2.2 – Técnicas Dinâmicas 2.2.1 – Predição determinada pela História do Desvio ▪ Verifica o que ocorreu com as k mais recentes execuções do desvio; ▪ BHT – Branch History Table → Limitações de armazenamento; ▪ Primeira execução da instrução de desvio → Técnica Estática; ▪ Técnicas Dinâmicas são afetadas pela Predição Inicial; Slide7:  Figura 2.4 – Diagrama de estado do Mecanismo de Predição 2.2.1 – Predição determinada pela História do Desvio ▪ Parâmetros importantes: ▪ Número de entradas da BHT; ▪ Número de bits de Histórico (k); ▪ Conflitos de mapeamento → BHT → cache fully/set associative. Slide8:  Figura 2.5 – Percentagens de Acertos para Contadores com 2 e 3 bits 2.2.2 – Predição usando Contadores Saturados ▪ Substituição dos Bits de História por Contadores; ▪ Contador não-negativo → Desvio tomado; ▪ Desvio tomado → Contador é incrementado; ▪ Caso contrário → Contador é decrementado; ▪ Valores extremos → nenhuma operação é realizada. Slide9:  Figura 2.6 – Tabela contendo Informações sobre os Alvos dos Desvios 2.2.3 – Tabela com os Alvos dos Desvios ▪ BTB – Branch Target Buffer; ▪ As taxas de acerto das técnicas de predição baseadas na BHT e na BTB são idênticas; ▪ Informações sobre a sucessora do desvio aceleram a busca da próxima instrução, melhorando o desempenho da máquina. Slide10:  2.2.4 – Predição com Dois Níveis de História ▪ A técnica de predição determinada pela História do Desvio vista anteriormente utiliza somente um nível de história, ou seja, o mecanismo não leva em consideração o que ocorreu com outras instruções de desvio; ▪ ↑ Nível de informação → ↑ Precisão da predição; ▪ Primeiro Nível (BHR – Branch History Register): ▪ resultados dos desvios mais recentemente executados; ▪ história global → diferentes instruções de desvio; ▪ Segundo Nível (PHT – Pattern History Table): ▪ resultados associados a uma instrução de desvio específica; ▪ história local. Slide11:  2.2.4 – Predição com Dois Níveis de História ▪ Parâmetro importante: ▪ Número de bits do registrador BHR → Determina o número de entradas da tabela PHT → Valor rasoável: 11 < k < 14; ▪ História Global X História Local → “Correlação”; ▪ Variações: GAg, GAs, GAp, PAg, PAs, PAp, SAg, SAs, SAp. ▪ GAs → 96,95% → 128 Kbits; ▪ PAs → 96,34% → 8 Kbits. Figura 2.7 – Predição com dois níveis de História Slide12:  2.2.5 – Preditores Híbridos ▪ Predição Inicial → ausência de informação → baixo desempenho; ▪ Trocas de contexto em ambientes multiprogramados → perda das informações de História; ▪ t = tempo requerido para o “treinamento” do preditor (estabilidade); ▪ Preditores com modestas taxas de acerto → baixo t; ▪ Preditores com elevadas taxas de acerto → alto t; ▪ Mecanismos Híbridos de Predição; ▪ Diversas Técnicas operando em paralelo; ▪ Somente a técnica com maior probabilidade de acerto fornece o resultado da predição. Slide13:  3.1 – Delayed Branch ▪ Técnica implementada no processador MIPS (Stanford); ▪ Baseada na reorganização das instruções do programa; ▪ Deve preservar a equivalência semântica; ▪ Em uma máquina Pipeline podemos associar a cada instrução de desvio o número de instruções seguintes que serão executadas independentemente do resultado do desvio. 3. Técnicas Implementadas em Software 1. A := B 2. B := B - 1 3. if A = Q then goto 7 4. Q := Q + 1; 5. D := E; 6. E := F; 7. X := Q; 1. A := B 2. B := B - 1 3. if A = Q then goto 8 4. NOP 5. Q := Q + 1; 6. D := E; 7. E := F; 8. X := Q; 1. A := B 2. if A = Q then goto 7 3. B := B - 1 4. Q := Q + 1; 5. D := E; 6. E := F; 7. X := Q; Slide14:  3.2 – Branch Folding ▪ Técnica implementada nos processadores CRISP (AT&T), PowerPC e IBM RISC System 6000; ▪ Cada instrução inclui o endereço de sua sucessora → cache; ▪ Desvio Condicional → Compilador decide o endereço da instrução sucessora → Técnica de Predição Estática → Esse endereço é armazenado na instrução que precede o desvio; ▪ O endereço do caminho alternativo também é salvo na cache; ▪ O desvio é eliminado (“desvios de zero ciclos”); ▪ Instruções de comparação são movimentadas de modo que sejam executadas o mais cedo possível, excluindo a possibilidade de uma previsão incorreta; ▪ Exige maior complexidade do Hardware e do Compilador; ▪ Difícil implementação. Slide15:  3.3 – In line ▪ Transferência incondicional → Desvios incondicionais e instruções para chamada/retorno de procedimento; ▪ Instruções para troca de contexto e para passagem de parâmetros diminuem o desempenho da arquitetura; ▪ Essa técnica substitui as chamadas a procedimentos dos programas pelo código objeto correspondente; ▪ Maior eficiência: reduções de 75 a 80% no tempo de processamento foram observadas; ▪ Vantagens: ▪ São eliminadas as instruções para passagem de parâmetros; ▪ São eliminadas as instruções CALL e RETN; ▪ Desvantagem: ▪ Aumento significativo do código objeto. Slide16:  3.4 – Desenrolamento de loops ▪ Reduz o custo das instruções de Desvio Condicional existentes nos comandos “for”; ▪ Vantagens: ▪ Reduz o número de instruções condicionais executadas; ▪ Aumenta o tamanho do bloco executado pelo comando “for”; for (i = 0; i < 100; i++) c[i] = a[i] + b[i]; Assumindo: R1 → var. de controle i; R2 → limite superior do for; R3...R5 → end. iniciais de a, b e c; R6...R8 → valores a[i], b[i] e c[i]. Loop: load R6, Base, R1 load R7, Base, R1 add R8, R6, R7 sto R8, Base, R1 add R1, R1, 1 comp R1, R2 bnez Loop Loop: load R6, Base, R1 load R7, Base, R1 add R8, R6, R7 sto R8, Base, R1 load R6, Base, R1+1 load R7, Base, R1+1 add R8, R6, R7 sto R8, Base, R1+1 add R1, R1, 2 comp R1, R2 bnez Loop Slide17:  ▪ Importância das Técnicas de Predição de Desvios; ▪ Precisão dos métodos é bastante afetada pelas características do programa; ▪ Implementação em Hardware X Implementação em Software; ▪ Combinação das abordagens HW e SW; ▪ Tópicos de Pesquisa: ▪ Preditores Híbridos; ▪ Novos Mecanismos de Predição; ▪ Métodos Neurais para Predição Dinâmica de Desvios; ▪ Impacto da complexidade dos mecanismos de predição no desempenho da arquitetura; etc. 4. Conclusões Slide18:  ▪ Fernandes, Edil S. T. “Arquiteturas Super Escalares: Detecção e Exploração do Paralelismo de Baixo Nível”, VIII Escola de Computação, Gramado, 1992. ▪ Fernandes, Edil S. T. “Paralelismo a Nível de Instrução e o Custo de Desvios”, XI Escola de Computação, Rio de Janeiro, 1998. ▪ Hennessy, J.; McFarling, S. “Reducing the cost of Branches”, IEEE Computer Society, 1986. ▪ Hwang, Kai. “Advanced Computer Architecture: Parallelism, Scalability, Programmability”, McGraw-Hill, 1993. ▪ Jiménez, Daniel A.; Lin, Calvin. “Neural Methods for Dynamic Branch Prediction”, University of Texas at Austin, 2001. ▪ Lee, J. K. F.; Smith, J. E. “Branch Prediction Strategies and Branch Target Buffer Design”, Computer, Vol. 17, 1984. ▪ Stallings, Willians. “Arquitetura e Organização de Computadores”, Makron Books, 2002. 5. Referências Bibliográficas

Add a comment

Related presentations

Related pages

BULA PREDIDERM 20MG.pdf - pt.scribd.com

facilita os desvios extracelulares de água e a retenção de sódio. A corticoideterapia frequentemente causa polidipsia, polifagia e poliúria em cães.
Read more

[R-br] gráfico de médias com desvio determinado pelo usuário

Encontrei em livros e na internet como plotar todos os tipos de desvios, ... new$pred <- predict(m0, newdata=new, interval="confidence") str(new)
Read more

A noção de orçamento, hoje lar - OCC

de controlo, dos valores de desempenho prede-terminados com os valores reais, apurando-se, ... Análise dos desvios orçamentais – Calcular um
Read more

Análisis de series temporales: Ajuste de modelos ARIMA en R

rec.mle $ var.pred #estimación del error de varianza. Publicado por rosana Ferrero en 3:59. Etiquetas: ARIMA, R. No hay comentarios:
Read more

PLATAFORMA - Predif | Accesibilidad

PLATAFORMA Abril de 2011 Nº 76 Isabel Martínez Lozano Secretaria general de Política Social y Consumo “A pesar de la crisis, el incremento de
Read more

Rosana Ferrero: Ajuste de modelos ARIMA en R

rec.mle $ var.pred #estimación del error de varianza. Publicado por rosana Ferrero en 3:59. Reacciones: ...
Read more

www.leg.ufpr.br

... conc) { pred - (Vm * conc)/(K + conc) sum ... , start=list(Vm=220, K=0.08)) summary(n0) sum(residuals(n0)) ## Os desvios não se ...
Read more

A PUZZLING MIGRATORY DETOUR: ARE FUELING CONDITIONS IN ...

fuel are likely to be more vulnerable when attacked by pred-ators (Kullberg et al. 1996, Burns and Ydenberg 2002), ...
Read more