Previsão de Desvios Baseada nos Tipos de Desvios e nas Probabilidades de Transição de Históricos
Resumo
As arquiteturas superescalares possuem a habilidade de explorar o paralelismo em nível de instruções. Para isso, técnicas de previsão de desvios são necessárias para tratar as dependências de controle, agilizando a busca de instruções e aumentando o número de instruções úteis disponíveis para a execução paralela. Atualmente, a maioria dos previsores de desvios usa alguma forma de tabela contendo os históricos dos desvios e os endereços alvos a serem seguidos. Sabe-se que estes históricos geram diferentes padrões que se repetem com probabilidades que dependem do fluxo de execução dos programas. O previsor PPM (Prediction Partial Matching), o qual trabalha sobre as probabilidades dos padrões de desvios, foi analisado e serviu de base para o desenvolvimento de um modelo mais agressivo, denominado PPDT (Previsor com Probabilidade Dependente de Transição). Esse novo modelo foi simulado e avaliado sobre a plataforma SimpleScalar Tool Set. Os resultados obtidos sobre benchmarks do SPEC 2000 alcançaram taxas médias de acerto acima de 95% em muitas situações, atingindo picos de 98% para tamanhos de históricos de 16 bits. O modelo PPDT se mostrou mais eficiente do que o PPM e apropriado para implementação real no futuro breve.
Referências
Gonçalves, R. A. L. e Navaux, P, O. A. Arquiteturas Multi-Tarefas Simultâneas: SEMPRE - Arquitetura SMT com Capacidade de Execução e Escalonamento de Processos - Porto Alegre: PPGC do II/UFRGS, Tese, 2000. 136p.
Fernandes, E. S. T.; Santos, A. D. Arquiteturas Super Escalares: Detecção e Exploração do Paralelismo de Baixo Nível. In: ESCOLA DE COMPUTAÇÃO, 7., 1992, Gramado-RS. Anais... [S. I.:s.n.], 1992.
Smith, J.E.; Sohi, G.S. The Microarchitecture of SuperScalar Processors. Proceedings of the IEEE, [S.I.], v.83, n.12, Dec. 1995.
Gonçalves, R. A. L. et ai. Evaluating the Effects of Branch Prediction Accuracy on the Performance of SMT Architectures, In: EUROMICRO WORKSHOP ON PARALLEL AND DISTRIBUTED PROCESSING, EUROMICRO PDP, 9., 2001, Mantova, Italy. Proceedings... [S.I.:s.n.], 2001.
Moffat, A. Implementing the PPM data Compression Scheme. IEEE Transactions on Communications, November 1990, 38(11): 1917-1921.
Chen, I.C.K; Coffey, J.T.; Mudge, T.N. Analysis of Branch Prediction via Data Compression. In: Proceedings of ASPLOS. October 1995, pages 128-137.
Lee, J. K. L.; Smith, A.J. Branch Prediction Strategies and Branch Target Buffer Design. Computer, 17(1), Jan, 1984.
Bray, B. K.; Flynn, M. J. Strategies For Branch Target Buffers. In: Proceedings of Micro-24, Nov, 1991, p. 42-50.
Perleberg, C. H.; Smith, A.. Branch Target Buffer Design and Optimization. IEEE Transaction on. Computers, April 1993, p. 396-412.
Smith, E. A Study of Branch Prediction Strategies. In Proc. of 8th International Symposium in Computer Architecture, Minneapolis, MN, 1981, p. 135-148.
Yeh, T.; Patt, Y. N. Two-level Adaptive Training Branch Prediction. In Proceedings of the 24th Annual International Symposium on Microarchitecture, Albuquerque, New Mexico, November 1991, p. 51-61.
Yeh, T.; Patt, Y. N. Altemative lmplementation of Two-Level Adaptative Branch prediction. The 19th Annual International Symposium on Computer Architecture, Gold Coast, Australia, May 1992, p. 124-134.
Yeh, T.Y.; Patt, Y. A comparasion of Dynamic Branch. Predictors that use Two Levels of Branch History. In 97 Proceedings of the International Symposium on Computer Architecture, May 1993, pages 257-266.
Jouppi, N. P.; Wall, D. W. Available Instruction-Level Parallelism for Superscalar and Superpipe lined Machines, 3rd International Conference on Architecture Support for Programming Languages and Operating Systems, IEEE and ACM, April, 1989.
Wall, D.W. Limits of Instruction-Level Parallelism. In Proceedings of ASPLOS IV, Santa Clara, 1991. p. 176-188.
Lam, M.S.; Wilson, R. P. Limits of Control Flow on Parallelism. In Proceedings 20th International Symposium on Computer Architecture, May 1993, p.46-57.
Gonzalez, J.; Gonzalez, A. Control-Flow Speculation through Value Prediction for Superscalar Processor. In: Proceedings of PACT, 1999, p. 57-65.
Sherwood, T.; Calder, 8. Loop Termination Prediction. Proceedings of the 3rd International Symposium on High Performance Computing (ISHPC2K), Oct. 2000.
Fem, A.; et ai. Dynamic Feature Selection for Hardware Prediction. Technical Report TR-ECE 00-12, School of Electrical and Computer Engineering, Purdue Univ, 2000.
Aragon, J. L.; et ai. Confidence Estimation for Branch Prediction Reversal. In Proceedings of the 8th International Conference on High Performance Computing, Dec. 2001.
Ribas, V.; Figueiredo, M. e Gonçalves, R. Analyzing Branclt PredJction Unáer Speculative Execution Using Perceptron, XXITI Congresso da SBC - ENIA - Encontro Nacional de Inteligência Artificial, Campinas, Agosto, 2003.
McFarling, S. Combining Branch Predictors. Technical Report TN-36m, Digital Westem Laboratory, Jun. 1993.
Young, C.; Gloy, N.; Smith, M. D. A Comparative Analysis of Schemes for Correlated Branch Prediction.. In: Annual International Symposium on Computer Architecture, ISCA, 22., 1995, Santa Margherita. Ligure, Italy. Proceedings... [S.l.:s.n.], 1995.
Kessler, Richard E. The Alpha 21264 microprocessor. IEEE Micro, [S.l.], v.19, n.2, Mar./Apr. 1999.
Federovsky, E.; Feder, M.; Weiss, S. Branch Prediction based on Universal Data Compression Algorithms. In Proceedings of the International Symposium on Archictcture, June 1998, pages 62-72.
Kalamatianos, J.; Kaeli, D.R..Indirect Branch Prediction using Data Compression. Journal of Instruction Level Parallelism, Vol. 1, 1999.
Burger, D.; Austin, T. M. The SimpleScalar Tool Set, Version 2.0. Technical Report # 1342, Computer Sciences Department, University of Wisconsin-Madison, Jun. 1997.
Henning, J.L. SPEC CPU2000: Measuring CPU Performance in the New Millennium. IEEE, 2000. p. 28-35.
Fernandes, E. S. T.; Santos, A. D. Arquiteturas Super Escalares: Detecção e Exploração do Paralelismo de Baixo Nível. In: ESCOLA DE COMPUTAÇÃO, 7., 1992, Gramado-RS. Anais... [S. I.:s.n.], 1992.
Smith, J.E.; Sohi, G.S. The Microarchitecture of SuperScalar Processors. Proceedings of the IEEE, [S.I.], v.83, n.12, Dec. 1995.
Gonçalves, R. A. L. et ai. Evaluating the Effects of Branch Prediction Accuracy on the Performance of SMT Architectures, In: EUROMICRO WORKSHOP ON PARALLEL AND DISTRIBUTED PROCESSING, EUROMICRO PDP, 9., 2001, Mantova, Italy. Proceedings... [S.I.:s.n.], 2001.
Moffat, A. Implementing the PPM data Compression Scheme. IEEE Transactions on Communications, November 1990, 38(11): 1917-1921.
Chen, I.C.K; Coffey, J.T.; Mudge, T.N. Analysis of Branch Prediction via Data Compression. In: Proceedings of ASPLOS. October 1995, pages 128-137.
Lee, J. K. L.; Smith, A.J. Branch Prediction Strategies and Branch Target Buffer Design. Computer, 17(1), Jan, 1984.
Bray, B. K.; Flynn, M. J. Strategies For Branch Target Buffers. In: Proceedings of Micro-24, Nov, 1991, p. 42-50.
Perleberg, C. H.; Smith, A.. Branch Target Buffer Design and Optimization. IEEE Transaction on. Computers, April 1993, p. 396-412.
Smith, E. A Study of Branch Prediction Strategies. In Proc. of 8th International Symposium in Computer Architecture, Minneapolis, MN, 1981, p. 135-148.
Yeh, T.; Patt, Y. N. Two-level Adaptive Training Branch Prediction. In Proceedings of the 24th Annual International Symposium on Microarchitecture, Albuquerque, New Mexico, November 1991, p. 51-61.
Yeh, T.; Patt, Y. N. Altemative lmplementation of Two-Level Adaptative Branch prediction. The 19th Annual International Symposium on Computer Architecture, Gold Coast, Australia, May 1992, p. 124-134.
Yeh, T.Y.; Patt, Y. A comparasion of Dynamic Branch. Predictors that use Two Levels of Branch History. In 97 Proceedings of the International Symposium on Computer Architecture, May 1993, pages 257-266.
Jouppi, N. P.; Wall, D. W. Available Instruction-Level Parallelism for Superscalar and Superpipe lined Machines, 3rd International Conference on Architecture Support for Programming Languages and Operating Systems, IEEE and ACM, April, 1989.
Wall, D.W. Limits of Instruction-Level Parallelism. In Proceedings of ASPLOS IV, Santa Clara, 1991. p. 176-188.
Lam, M.S.; Wilson, R. P. Limits of Control Flow on Parallelism. In Proceedings 20th International Symposium on Computer Architecture, May 1993, p.46-57.
Gonzalez, J.; Gonzalez, A. Control-Flow Speculation through Value Prediction for Superscalar Processor. In: Proceedings of PACT, 1999, p. 57-65.
Sherwood, T.; Calder, 8. Loop Termination Prediction. Proceedings of the 3rd International Symposium on High Performance Computing (ISHPC2K), Oct. 2000.
Fem, A.; et ai. Dynamic Feature Selection for Hardware Prediction. Technical Report TR-ECE 00-12, School of Electrical and Computer Engineering, Purdue Univ, 2000.
Aragon, J. L.; et ai. Confidence Estimation for Branch Prediction Reversal. In Proceedings of the 8th International Conference on High Performance Computing, Dec. 2001.
Ribas, V.; Figueiredo, M. e Gonçalves, R. Analyzing Branclt PredJction Unáer Speculative Execution Using Perceptron, XXITI Congresso da SBC - ENIA - Encontro Nacional de Inteligência Artificial, Campinas, Agosto, 2003.
McFarling, S. Combining Branch Predictors. Technical Report TN-36m, Digital Westem Laboratory, Jun. 1993.
Young, C.; Gloy, N.; Smith, M. D. A Comparative Analysis of Schemes for Correlated Branch Prediction.. In: Annual International Symposium on Computer Architecture, ISCA, 22., 1995, Santa Margherita. Ligure, Italy. Proceedings... [S.l.:s.n.], 1995.
Kessler, Richard E. The Alpha 21264 microprocessor. IEEE Micro, [S.l.], v.19, n.2, Mar./Apr. 1999.
Federovsky, E.; Feder, M.; Weiss, S. Branch Prediction based on Universal Data Compression Algorithms. In Proceedings of the International Symposium on Archictcture, June 1998, pages 62-72.
Kalamatianos, J.; Kaeli, D.R..Indirect Branch Prediction using Data Compression. Journal of Instruction Level Parallelism, Vol. 1, 1999.
Burger, D.; Austin, T. M. The SimpleScalar Tool Set, Version 2.0. Technical Report # 1342, Computer Sciences Department, University of Wisconsin-Madison, Jun. 1997.
Henning, J.L. SPEC CPU2000: Measuring CPU Performance in the New Millennium. IEEE, 2000. p. 28-35.
Publicado
27/10/2004
Como Citar
SILVA, Zenaide C. da; CAVENAGHI, Marcos A.; MARTINI, João A.; GONÇALVES, Ronaldo A. L..
Previsão de Desvios Baseada nos Tipos de Desvios e nas Probabilidades de Transição de Históricos. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 5. , 2004, Foz do Iguaçu.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2004
.
p. 90-97.
DOI: https://doi.org/10.5753/wscad.2004.19005.
