Recognizing and parallelizing bounded recurrences

1. J. R. Allen, D. Callahan, and K. Kennedy. Automatic decomposition of scientific programs for parallel execution. In Conference Record of the Fourteenth ACM Symposium on the Principles of Programming Languages, Munich, West Germany, January 1987.

   Google Scholar 

2. J. R. Allen and K. Kennedy. Automatic translation of FORTRAN programs to vector form. ACM Transactions on Programming Languages and Systems, 9(4):491–542, October 1987.

   Google Scholar 

3. J. R. Allen, K. Kennedy, C. Porterfield, and J. Warren. Conversion of control dependence to data dependence. In Conference Record of the Tenth ACM Symposium on the Principles of Programming Languages, Austin, Tx., January 1983.

   Google Scholar 

4. R. Alverson, D. Callahan, D. Cummings, B. Koblenz, A. Porterfield, and B. Smith. The Tera computer system. In Proceedings of the International Conference on Supercomputing, Amsterdam, 1990.

   Google Scholar 

5. U. Banerjee, S. C. Chen, D. Kuck, and R. Towle. Time and parallel processor bounds for Fortran-like loops. IEEE Transactions on Computers, C-28(9):660–670, September 1979.

   Google Scholar 

6. J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems, 9(3):319–349, July 1987.

   Google Scholar 

7. D. Heller. Some aspects of cyclic reduction algorithm for block tridiagonal systems. SIAM Journal of Numerical Analysis, 13(4):484–496, 1976.

   Google Scholar 

8. P. M. Kogge and H. S. Stone. A parallel algorithm for the efficient solution of a general class of recurrence equations. IEEE Transactions on Computers, C-22(8):786–792, August 1973.

   Google Scholar 

9. C. Kruskal, L. Rudolph, and M. Snir. The power of parallel prefix. In Proceedings of the 1985 International Conference on Parallel Processing, pages 180–183, August 1985.

   Google Scholar 

10. D. J. Kuck, R. H. Kuhn, B. Leasure, D. A. Padua, and M. Wolfe. Compiler transformation of dependence graphs. In Conference Record of the Tenth ACM Symposium on the Principles of Programming Languages, Williamsburg, Va, January 1983.

    Google Scholar 

11. R. E. Ladner and M. J. Fisher. Parallel prefix computation. Journal of the ACM, 27(4):831–839, October 1980.

    Google Scholar 

12. F. H. McMahon. The Livermore Fortran kernels: A computer test of the numerical performance range. Technical Report UCRL-53745, Lawrence Livermore National Laboratory, December 1986.

    Google Scholar 

13. A. Nicolau and H. Wang. Optimal schedules for parallel prefix computation with bounded resources. In Third ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, April 1991.

    Google Scholar 

14. S. S. Pinter and R. Y. Pinter. Program optimization and parallelization using idioms. In Conference Record of the Eighteenth ACM Symposium on the Principles of Programming Languages, January 1991.

    Google Scholar 

15. G. Rodrigue, editor. Parallel Computations. Academic Press, !982.

    Google Scholar 

16. A. Sameh and R. Brent. Solving triangular systems of equations. SIAM Journal of Numerical Analysis, 14(6):1101–1113, 1977.

    Google Scholar 

17. M. Snir. Depth-size trade-offs for parallel prefix computation. Journal of Algorithms, 7:185–201, 1986.

    Google Scholar 

18. Y. Tanaka, K. Iwasawa, Y. Umetani, and S. Gotou. Compiling techniques for first-order linear recurrences on a vector computer. The Journal of Supercomputing, 4(1):63–82, March 1990.

    Google Scholar 

Download references