pred desvios

Information about pred desvios

Published on December 28, 2007

Author: Carlton

Source: authorstream.com

Content

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 [email protected] 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

Related presentations


Other presentations created by Carlton

Consumer
19. 11. 2007
0 views

Consumer

first06b
02. 10. 2007
0 views

first06b

Nyberg yeast
08. 11. 2007
0 views

Nyberg yeast

udd
10. 12. 2007
0 views

udd

Lab Setup
05. 11. 2007
0 views

Lab Setup

3 MOVE
06. 11. 2007
0 views

3 MOVE

drire
15. 11. 2007
0 views

drire

KRISTAL2006 04
20. 11. 2007
0 views

KRISTAL2006 04

DHCREALV2
22. 11. 2007
0 views

DHCREALV2

modern slow dance
23. 11. 2007
0 views

modern slow dance

Ethnic Geography Part II
23. 11. 2007
0 views

Ethnic Geography Part II

P Naming Elephants Presentation
26. 11. 2007
0 views

P Naming Elephants Presentation

ancientrome
31. 10. 2007
0 views

ancientrome

FarmtoBusiness
27. 12. 2007
0 views

FarmtoBusiness

Polymorphism
31. 12. 2007
0 views

Polymorphism

pruning avon landscape school
03. 01. 2008
0 views

pruning avon landscape school

Clinical
04. 01. 2008
0 views

Clinical

5 Unit 12
04. 01. 2008
0 views

5 Unit 12

WhittakerPaper
07. 01. 2008
0 views

WhittakerPaper

CEROS TechEnterprise 2005
07. 01. 2008
0 views

CEROS TechEnterprise 2005

ISU Trondheim 2006
07. 12. 2007
0 views

ISU Trondheim 2006

Parks Decsion Tree
28. 11. 2007
0 views

Parks Decsion Tree

deussen
02. 01. 2008
0 views

deussen

Onion handout only2006
07. 11. 2007
0 views

Onion handout only2006

SalahuddinAminuzzaman
25. 12. 2007
0 views

SalahuddinAminuzzaman

1 2006 parasitology definitions
24. 10. 2007
0 views

1 2006 parasitology definitions

mktrec
24. 02. 2008
0 views

mktrec

voyager tutorial
27. 02. 2008
0 views

voyager tutorial

MP10SpecialRelativit y2
06. 11. 2007
0 views

MP10SpecialRelativit y2

Maher Creativity 2007 08 14
28. 11. 2007
0 views

Maher Creativity 2007 08 14

Lifeline v4c
31. 10. 2007
0 views

Lifeline v4c

Travel Health
27. 03. 2008
0 views

Travel Health

Musical 1
02. 11. 2007
0 views

Musical 1

Outline2
13. 11. 2007
0 views

Outline2

wac2004ronblum
13. 04. 2008
0 views

wac2004ronblum

Agrofuels Driving Climate Change
26. 11. 2007
0 views

Agrofuels Driving Climate Change

2007 05 09bbh download
26. 10. 2007
0 views

2007 05 09bbh download

Bartenders Karen Palmersheim
11. 12. 2007
0 views

Bartenders Karen Palmersheim

Dynamic Licensing
06. 11. 2007
0 views

Dynamic Licensing

jose nov 04
30. 10. 2007
0 views

jose nov 04

1183379282 IIIA N S results
26. 10. 2007
0 views

1183379282 IIIA N S results

CLS Euro pres
02. 01. 2008
0 views

CLS Euro pres

cours5
01. 11. 2007
0 views

cours5

Homestake DOSSECC 6 2006b
03. 12. 2007
0 views

Homestake DOSSECC 6 2006b

ritt
29. 10. 2007
0 views

ritt

true fri pps2
28. 12. 2007
0 views

true fri pps2

27 Piro ops
30. 10. 2007
0 views

27 Piro ops

KUS5 trebilcock
01. 12. 2007
0 views

KUS5 trebilcock

Subsea experience 1
07. 11. 2007
0 views

Subsea experience 1

Eric Van Heck
12. 12. 2007
0 views

Eric Van Heck