Semi-systolic Algorithm Synthesis for the Grid
Resumo
The systolic paradigm that appeared in the late seventies has contributed to parallel computing in two ways: the development of the method allowed the parallelization of nested loops algorithms and at the same time several practical applications like cryptography and multimedia using mostly 2-d grids. Unifying these two tendencies we propose a new method for semi-systolic algorithm syntesis, for uniform nested loops. Our solution is better than the tradicional approach if the target architecture is a grid.
Palavras-chave:
grids, systolic, parallel computing, schedule
Referências
Banerjee, U. An introduction to a formal theory of dependence analysis. J. Supercomput. 2(1988) 133–149.
Kung, S. Y. VLSI array processors. Prentice Hill, New Jersey, 1988.
Moldovan, D.; Fortes, J. A. B. Partitioning and mapping algorithms into fixed size systolic array. IEEE Transactions on Computers, vol. C-35, No. 1, January 1986.
Moore, V. Systolic Arrays. Adam Hilger, 1986.
Peir, J. K.; Cytron, R. Minimum distance: a method for partitioning recurrence for multiprocessors. IEEE Trans. Comput. 38(8) (Aug. 1989) 1203–1211.
Polychronopoulos, C. D. Parallel programming and compilers. Kluwer Academic Publishers, 1988.
Quinton, P.; Robert, Y. Systolic Algorithms and Architectures. Prentice Hall, 1989.
Robert, Y.; Darte, A. Scheduling uniform loop nests. Technical Report, Laboratoire de l'Informatique du Parallélisme-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. Revisiting cycle shrinking. Parallel Computing, 18(1992) 481–496.
Schmidt, B.; Schimmler, M.; Schroder, H. Long Operand Arithmetic on Instruction Systolic Computer Architectures and Its Application in RSA Cryptography. Euro-Par'98 Parallel Processing, Lecture Notes in Computer Science Series 1123, Springer-Verlag, 1998, 916–922.
Schmidt, B.; Schimmler, M. A Parallel Accelerator Architecture for multimedia Video compression. Euro-Par'99 Parallel Processing, Lecture Notes in Computer Science Series 1123, Springer-Verlag, 1999, 950–960.
Shang, W.; Fortes, J. A. B. Time optimal linear schedules for algorithms with uniform dependences. 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 architecture II. P. Quinton and Y. Robert (editors), North Holland, 1991.
Song, S. W. Algoritmos Paralelos e Arquitetura VLSI. IV Escola de Computação, IME/USP, 1984.
Wolfe, M. Optimizing supercompilers for supercomputers. MIT Press, Cambridge, MA, 1989.
Wolfe, M. Data dependence and program restructuring. J. Supercomput. 4(1990) 321–344.
Kung, S. Y. VLSI array processors. Prentice Hill, New Jersey, 1988.
Moldovan, D.; Fortes, J. A. B. Partitioning and mapping algorithms into fixed size systolic array. IEEE Transactions on Computers, vol. C-35, No. 1, January 1986.
Moore, V. Systolic Arrays. Adam Hilger, 1986.
Peir, J. K.; Cytron, R. Minimum distance: a method for partitioning recurrence for multiprocessors. IEEE Trans. Comput. 38(8) (Aug. 1989) 1203–1211.
Polychronopoulos, C. D. Parallel programming and compilers. Kluwer Academic Publishers, 1988.
Quinton, P.; Robert, Y. Systolic Algorithms and Architectures. Prentice Hall, 1989.
Robert, Y.; Darte, A. Scheduling uniform loop nests. Technical Report, Laboratoire de l'Informatique du Parallélisme-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. Revisiting cycle shrinking. Parallel Computing, 18(1992) 481–496.
Schmidt, B.; Schimmler, M.; Schroder, H. Long Operand Arithmetic on Instruction Systolic Computer Architectures and Its Application in RSA Cryptography. Euro-Par'98 Parallel Processing, Lecture Notes in Computer Science Series 1123, Springer-Verlag, 1998, 916–922.
Schmidt, B.; Schimmler, M. A Parallel Accelerator Architecture for multimedia Video compression. Euro-Par'99 Parallel Processing, Lecture Notes in Computer Science Series 1123, Springer-Verlag, 1999, 950–960.
Shang, W.; Fortes, J. A. B. Time optimal linear schedules for algorithms with uniform dependences. 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 architecture II. P. Quinton and Y. Robert (editors), North Holland, 1991.
Song, S. W. Algoritmos Paralelos e Arquitetura VLSI. IV Escola de Computação, IME/USP, 1984.
Wolfe, M. Optimizing supercompilers for supercomputers. MIT Press, Cambridge, MA, 1989.
Wolfe, M. Data dependence and program restructuring. J. Supercomput. 4(1990) 321–344.
Publicado
24/10/2000
Como Citar
OKUDA, Kunio; GUBITOSO, Marco Dimas.
Semi-systolic Algorithm Synthesis for the Grid. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 12. , 2000, São Pedro/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2000
.
p. 373-377.
DOI: https://doi.org/10.5753/sbac-pad.2000.41237.
