Um Gerador Automático de Código para Arquiteturas VLIW com Capacidade de Execução Condicional
Resumo
Nesse artigo apresentamos um gerador automático de código paralelo para o modelo CONDEX, uma arquitetura Superescalar VLIW, que implementa o conceito de execução condicional. A arquitetura é formada por múltiplas unidades funcionais independentes que podem operar concorrentemente, processando diversas instruções procedentes do mesmo programa de aplicação. Além da descrição do modelo de arquitetura, examinamos a implementação do gerador de código paralelo que emprega a compactação condicional, uma técnica de compactação global. Finalmente, avaliamos a qualidade do código paralelo gerado, interpretando um conjunto de programas de teste.
Referências
A. K. Uht, "Hardware Extraction of Low Level Cocurrency from Sequential Instruction Streams," Ph.D. Thesis, Carnegie-Mellon University, December 1985.
R. P. Colwell, R. P. Nix, J. J. O' Donnell, D. B. Papworth and P. K. Rodman, "A VLIW Architecture for a Trace Scheduling Compiler," IEEE Transactions on Computers, Vol. 37, No. 8, August 1988, pp. 967-979.
S. D. Conte, "Elementary Numerical Analysis," McGraw-Hill, NY, USA, 1965.
J. W. Davidson and D. B. Whalley, "Reducing the Cost of Branches by Using Resisters," The 17th Annual ISCA, Washington, 1990, pp. 182-191.
D. R. Ditzel, e H. R. Mclellan, "Branch Folding in the CRISP Microprocessor: Reducing Branch Delay to Zero," Proceedings of the 14th Annual ISCA, 1987, pp. 2-9.
Edil S. T. Fernandes e Anna Dolejsi Santos, "Arquiteturas Super Escalares: Detecção e Exploração do Paralelismo de Baixo Nível," VIII Escola de Computação 1992.
Edil S. T. Fernandes, Anna Dolejsi Santos and Claudio L. de Amorim, "Conditional Execution: an Approach for Eliminating the Basic Block Barriers," Microprocessing and Microprogramming The Euromicro Journal, North Holland Vol. 40 Numbers 10-12, December 1994, pp. 668-692.
J. A. Fisher, "Trace Scheduling: A Technique for Global Microcode Compaction," IEEE Transactions on Computers, Vol. C-30, No. 7, July 1981, pp. 478-490.
S. Gray and R. Adams, "Using Conditional Execution to Exploit Instruction Level Concurrency," Technical Report no. 181, School of Information Sciences, Division of Computer Science University of Hertfordshire, March 1994.
J. K. Lee and A. J. Smith, "Branch Prediction Strategies and Branch Target Buffer Design" IEEE Computer, Vol. 17, No. 1, January 1984 pp. 622.
M. Johnson,"Superscalar Microprocessor Design," Prentice Hall, 1991.
D. Landskov, S. Davidson, B. Shriver, e P. W. Mallet, "Local Microcode Compaction Techniques," Computing Surveys, Vol.21, No.3, Sept.1980, pp.261-294.
David J. Lilja "Reducing the Branch Penalty in Pipelined Processors," IEEE Computer, Vo. 21 No. 7, July 1988; pp. 47-55.
F. H. McMahon, "Fortran Kernels: MFLOPS," Lawrence Livermore National Laboratory,1983.
Leonardo Cardoso Monteiro, "Geração de Código Paralelo para Máquinas Super Escalares," Projeto de Fim de Curso, IM, UFRJ 1993.
João Francisco Pereira Neto, "A Implementação de um Compactador Condicional," Projeto de Fim de Curso, DCC, IM, UFF 1995.
A. Nicolau and R. Potasman, "Realistic Scheduling: Compaction for Pipelined Architectures," Proceedings of the 23rd Annual International Workshop on Microprogramming and Microarchitecture MICRO-23, ACM and IEEE Computer Society, November 1990, pp. 69-79.
D. N. Pnevmatikatos and G. S. Sohi, "Guarded Execution and Branch Prediction in Dynamic ILP Processors," Proceedings of the 21st Annual ISCA, 1994, pp. 120-129.
Anna. Dolejsi Santos, "Efeito da Execução Condicional em Arquiteturas Paralelas" Tese de Doutorado, COPPE/UFRJ, Programa de Engenharia de Sistemas e Computação, 1994.
Anna Dolejsi Santos e Edil S. T. Fernandes, "Extração do Paralelismo em Arquiteturas com Capacidade de Execução Condicional," VII SBAC-PAD, 1995, pp. 77-99.
J. E. Smith, "A Study of Branch Prediction Strategies," The 8th Annual International Symposium on Computer Architecture, 1981, pp. 135-148.
F. L. Stevens G. B. Steven and L. Wang, "An Evaluation of the iHARP Multiple Instruction Issue Processor," Euromicro 94 September 1994.
Daniel Tabak, "Advanced Microprocessors" Mc Graw-Hill, Inc., USA, 1991.
M. Tokoro, T. Takizuka, E. Tamura., and I. Yamamura, "A Technique of Global Optimization of Microprograms," Proceedings of the 11th Annual Microprogramming Workshop, 1978, pp. 41-50.
N. Wirth, "Algorithms+Data Structures=Programs," Prentice-Hall, Inc., 1976.
R. P. Colwell, R. P. Nix, J. J. O' Donnell, D. B. Papworth and P. K. Rodman, "A VLIW Architecture for a Trace Scheduling Compiler," IEEE Transactions on Computers, Vol. 37, No. 8, August 1988, pp. 967-979.
S. D. Conte, "Elementary Numerical Analysis," McGraw-Hill, NY, USA, 1965.
J. W. Davidson and D. B. Whalley, "Reducing the Cost of Branches by Using Resisters," The 17th Annual ISCA, Washington, 1990, pp. 182-191.
D. R. Ditzel, e H. R. Mclellan, "Branch Folding in the CRISP Microprocessor: Reducing Branch Delay to Zero," Proceedings of the 14th Annual ISCA, 1987, pp. 2-9.
Edil S. T. Fernandes e Anna Dolejsi Santos, "Arquiteturas Super Escalares: Detecção e Exploração do Paralelismo de Baixo Nível," VIII Escola de Computação 1992.
Edil S. T. Fernandes, Anna Dolejsi Santos and Claudio L. de Amorim, "Conditional Execution: an Approach for Eliminating the Basic Block Barriers," Microprocessing and Microprogramming The Euromicro Journal, North Holland Vol. 40 Numbers 10-12, December 1994, pp. 668-692.
J. A. Fisher, "Trace Scheduling: A Technique for Global Microcode Compaction," IEEE Transactions on Computers, Vol. C-30, No. 7, July 1981, pp. 478-490.
S. Gray and R. Adams, "Using Conditional Execution to Exploit Instruction Level Concurrency," Technical Report no. 181, School of Information Sciences, Division of Computer Science University of Hertfordshire, March 1994.
J. K. Lee and A. J. Smith, "Branch Prediction Strategies and Branch Target Buffer Design" IEEE Computer, Vol. 17, No. 1, January 1984 pp. 622.
M. Johnson,"Superscalar Microprocessor Design," Prentice Hall, 1991.
D. Landskov, S. Davidson, B. Shriver, e P. W. Mallet, "Local Microcode Compaction Techniques," Computing Surveys, Vol.21, No.3, Sept.1980, pp.261-294.
David J. Lilja "Reducing the Branch Penalty in Pipelined Processors," IEEE Computer, Vo. 21 No. 7, July 1988; pp. 47-55.
F. H. McMahon, "Fortran Kernels: MFLOPS," Lawrence Livermore National Laboratory,1983.
Leonardo Cardoso Monteiro, "Geração de Código Paralelo para Máquinas Super Escalares," Projeto de Fim de Curso, IM, UFRJ 1993.
João Francisco Pereira Neto, "A Implementação de um Compactador Condicional," Projeto de Fim de Curso, DCC, IM, UFF 1995.
A. Nicolau and R. Potasman, "Realistic Scheduling: Compaction for Pipelined Architectures," Proceedings of the 23rd Annual International Workshop on Microprogramming and Microarchitecture MICRO-23, ACM and IEEE Computer Society, November 1990, pp. 69-79.
D. N. Pnevmatikatos and G. S. Sohi, "Guarded Execution and Branch Prediction in Dynamic ILP Processors," Proceedings of the 21st Annual ISCA, 1994, pp. 120-129.
Anna. Dolejsi Santos, "Efeito da Execução Condicional em Arquiteturas Paralelas" Tese de Doutorado, COPPE/UFRJ, Programa de Engenharia de Sistemas e Computação, 1994.
Anna Dolejsi Santos e Edil S. T. Fernandes, "Extração do Paralelismo em Arquiteturas com Capacidade de Execução Condicional," VII SBAC-PAD, 1995, pp. 77-99.
J. E. Smith, "A Study of Branch Prediction Strategies," The 8th Annual International Symposium on Computer Architecture, 1981, pp. 135-148.
F. L. Stevens G. B. Steven and L. Wang, "An Evaluation of the iHARP Multiple Instruction Issue Processor," Euromicro 94 September 1994.
Daniel Tabak, "Advanced Microprocessors" Mc Graw-Hill, Inc., USA, 1991.
M. Tokoro, T. Takizuka, E. Tamura., and I. Yamamura, "A Technique of Global Optimization of Microprograms," Proceedings of the 11th Annual Microprogramming Workshop, 1978, pp. 41-50.
N. Wirth, "Algorithms+Data Structures=Programs," Prentice-Hall, Inc., 1976.
Publicado
04/08/1996
Como Citar
SANTOS, Anna Dolejsi; PEREIRA NETO, João Francisco.
Um Gerador Automático de Código para Arquiteturas VLIW com Capacidade de Execução Condicional. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 8. , 1996, Recife.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1996
.
p. 77-86.
DOI: https://doi.org/10.5753/sbac-pad.1996.19816.
