Encolhimento de Ciclo por Redução de Dependência
Resumo
Apresentamos uma nova técnica chamada redução de dependência para encolhimento de ciclo. Eeta técnica consiste em uma transformação do grafo de dependência que permite reduzir o número de passos e o número de comunicações entre processadores. A comparação do novo método com os outros métodos é feita através de exemplos ilustrativos.
Referências
Banerjee, U. An introduction to a formal theory of dependence analysis. J. Supercomput. 2(1988) 133-149.
Liu, L.S., Ho, C.W., Sheu, J.P. On the parallelism of nested for-loops using index shift method. Proc. lntemat. Conf. on Parallel Processing (Aug. 1990) II-119II-123.
Peir, J.K., Cytron, R., Minimum distance: a method for partitioning recurrence for multi processors. IEEE Trans. Comput. 38(8) (Aug. 1989) 1203-1211.
Polychronopoulos, C.D. Compiler optimization for enhancing parallelism and their impact on architecture design. IEEE Trans. Comput. 37(8) (Aug. 1988) 991-1004.
Polychronopoulos, C.D. Parallel programing and compilers. Kluwer Academic Publishers, 1988.
Robert, Y., Darte, A. Scheduling uniforme loop nests. Technical Report, Laboratoire de I' Informatique du Paralllisme-IMAG, Lyon, 1992.
Robert, Y., Darte, A. Mapping Uniform Loop Nests onto Distributed Memory Architectures. Parallel Computing 20( 1994) 679-710.
Robert, Y., Song, S.W. Reviting cycle shrinking. Parallel Computing, 18(1992) 481-496.
Shang, W., Fortes,J.A.B., Time optimal linear schedules for algorithms with uniform dependencies. IEEE Trans. Comput. 40(6) (Jun. 1991) 723-742.
Shang, W., O'Keefe, M.T., Fortes, J.A.B. Generalized cycle shrinking. Parallel algorithms and VLSI archtecture TI. P. Quinton and Y. Robert(editors), North holland, 1991.
Wolfe, M., Optimizing supercompilers for supercopmuters. MIT Press, Cambridge, MA, 1989.
Wolfe, M., Data dependence and program restructuring. J. Supercomput. 4(1990) 321-344.
Liu, L.S., Ho, C.W., Sheu, J.P. On the parallelism of nested for-loops using index shift method. Proc. lntemat. Conf. on Parallel Processing (Aug. 1990) II-119II-123.
Peir, J.K., Cytron, R., Minimum distance: a method for partitioning recurrence for multi processors. IEEE Trans. Comput. 38(8) (Aug. 1989) 1203-1211.
Polychronopoulos, C.D. Compiler optimization for enhancing parallelism and their impact on architecture design. IEEE Trans. Comput. 37(8) (Aug. 1988) 991-1004.
Polychronopoulos, C.D. Parallel programing and compilers. Kluwer Academic Publishers, 1988.
Robert, Y., Darte, A. Scheduling uniforme loop nests. Technical Report, Laboratoire de I' Informatique du Paralllisme-IMAG, Lyon, 1992.
Robert, Y., Darte, A. Mapping Uniform Loop Nests onto Distributed Memory Architectures. Parallel Computing 20( 1994) 679-710.
Robert, Y., Song, S.W. Reviting cycle shrinking. Parallel Computing, 18(1992) 481-496.
Shang, W., Fortes,J.A.B., Time optimal linear schedules for algorithms with uniform dependencies. IEEE Trans. Comput. 40(6) (Jun. 1991) 723-742.
Shang, W., O'Keefe, M.T., Fortes, J.A.B. Generalized cycle shrinking. Parallel algorithms and VLSI archtecture TI. P. Quinton and Y. Robert(editors), North holland, 1991.
Wolfe, M., Optimizing supercompilers for supercopmuters. MIT Press, Cambridge, MA, 1989.
Wolfe, M., Data dependence and program restructuring. J. Supercomput. 4(1990) 321-344.
Publicado
29/07/1995
Como Citar
OKUDA, Kunio.
Encolhimento de Ciclo por Redução de Dependência. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 7. , 1995, Canela.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1995
.
p. 553-567.
DOI: https://doi.org/10.5753/sbac-pad.1995.19887.
