Optimizing for parallelism and data locality

ABSTRACT

Previous research has used program transformation to introduce parallelism and to exploit data locality. Unfortunately, these two objectives have usually been considered independently. This work explores the trade-offs between effectively utilizing parallelism and memory hierarchy on shared-memory multiprocessors. We present a simple, but surprisingly accurate, memory model to determine cache line reuse from both multiple accesses to the same memory location and from consecutive memory access. The model is used in memory optimizing and loop parallelization algorithms that effectively exploit data locality and parallelism in concert. We demonstrate the efficacy of this approach with very encouraging experimental results.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	ACK87	r. Allen , D. Callahan , K. Kennedy, Automatic decomposition of scientific programs for parallel execution, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.63-76, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41631]
	AK84	John R. Allen , Ken Kennedy, Automatic loop interchange, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.233-246, June 17-22, 1984, Montreal, Canada
	AK87	Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
	AS79	Walid Abdul-Karim Abu-Sufah, Improving the performance of virtual memory computers., 1979
	Ban90a	Utpal Banerjee, A theory of loop permutations, Selected papers of the second workshop on Languages and compilers for parallel computing, p.54-74, May 1990, Urbana, Illinois, United States
	Ban90b	U. Banerjee. Unimodular transformations of double loops. In Proceedings of the Third Workshop on Languages and Compilers }or Parallel Computing, Irvine, CA, August 1990.
	BFKK92	Vasanth Balasundaram , Geoffrey Fox , Ken Kennedy , Ulrich Kremer, A static performance estimator in the Fortran D programming system, Languages, compilers and run-time environments for distributed memory machines, Elsevier Science Publishers B. V., Amsterdam, The Netherlands, 1992
	Cal87	C. D. Callahan, II, A global approach to detection of parallelism, Rice University, Houston, TX, 1987
	CCK90	David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.53-65, June 1990, White Plains, New York, United States
	CKPK90	George Cybenko , Lyle Kipp , Lynn Pointer , David Kuck, Supercomputer performance evaluation and the Perfect Benchmarks, Proceedings of the 4th international conference on Supercomputing, p.254-266, June 11-15, 1990, Amsterdam, The Netherlands
	DBMS79	J. Dongarra, J. Bunch, C. Moler, and G. Stewart. LINPACK U~er's Guide. SIAM Fublications, Philadelphia, PA, 1979.
	DCHH88	Jack J. Dongarra , Jeremy Du Croz , Sven Hammarling , Richard J. Hanson, An extended set of FORTRAN basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.1-17, March 1988 [doi>10.1145/42288.42291]
	FST91	Jeanne Ferrante , Vivek Sarkar , W. Thrash, On Estimating and Enhancing Cache Effectiveness, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.328-343, August 07-09, 1991
	GJG88	Dennis Gannon , William Jalby , Kyle Gallivan, Strategies for cache and local memory management by global program transformation, Journal of Parallel and Distributed Computing, v.5 n.5, p.587-616, October 1988 [doi>10.1016/0743-7315(88)90014-7]
	IT88	F. Irigoin , R. Triolet, Supernode partitioning, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.319-329, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73588]
	KKP+ 81	D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
	KMC72	D. Kuck, Y. Muraoka, and S. Chen. On the mlmber of operations simultaneously executable in Fortran-like programs and their resulting speedup. IEEE Transactions on Computers, C-21(12):1293-1310, December 1972.
	KMM91	K. Kennedy, N. McIntosh, and K. S. McKinley. Static performance estimation in a parallelizin& compiler. Technical Report TR91-174, Dept. of Computer Science, Rice University, December 1991.
	KMT92	K. Kennedy, K. S. MCKinley, and C. Tseng. hnproving data locality. Technical Report TR92-179, Dept. of Computer Science, Rice University, March 1992.
	Lam74	Leslie Lamport, The parallel execution of DO loops, Communications of the ACM, v.17 n.2, p.83-93, Feb. 1974 [doi>10.1145/360827.360844]
	LRW91	Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
	McK92	Kathryn Stuart McKinley, Automatic and interactive parallelization, Rice University, Houston, TX, 1992
	McM86	F. McMahon. The Livermore Fortran Kernels: A computer test of the numerical performance range. Technical Report UCRL-53745, Lawrence Livermore National Laboratory, 1986.
	Por89	Allan Kennedy Porterfield , K. W. Kennedy, Software methods for improvement of cache performance on supercomputer applications, 1989
	WB87	Michael Wolfe , Utpal Banerjee, Data dependence and its application to parallel processing, International Journal of Parallel Programming, v.16 n.2, p.137-178, April 1987 [doi>10.1007/BF01379099]
	WL90	M.E. Wolf azld M. Lain. Maximizing parallelism via loop transformations. In Proceedings of the Third Workshop on Languages and Compzlers for Parallel Computsng, Irvine, CA, August 1990.
	WL91	Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
	Wol89a	M. Wolfe, More iteration space tiling, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.655-664, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76337]
	Wol89b	Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990