William Thies
Saman Amarasinghe
ABSTRACT
We present a unified mathematical framework for analyzing the tradeoffs between parallelism and storage allocation within a parallelizing compiler. Using this framework, we show how to find a good storage mapping for a given schedule, a good schedule for a given storage mapping, and a good storage mapping that is valid for all legal schedules. We consider storage mappings that collapse one dimension of a multi-dimensional array, and programs that are in a single assignment form with a one-dimensional schedule. Our technique combines affine scheduling techniques with occupancy vector analysis and incorporates general affine dependences across statements and loop nests. We formulate the constraints imposed by the data dependences and storage mappings as a set of linear inequalities, and apply numerical programming techniques to efficiently solve for the shortest occupancy vector. We consider our method to be a first step towards automating a procedure that finds the optimal tradeoff between parallelism and storage space.
- 1.D. Barthou, A. Cohen, and J. Collard. Maximal static expansion. In Principles of Programming Languages, pages 98-106, San Diego, CA, Jan. 1998. Google Scholar
Digital Library
- 2.A. Cohen. Parallelization via constrained storage mapping optimization. Lecture Notes in Computer Science, 1615:83-94, 1999. Google ScholarDigital Library
- 3.A. Cohen and V. Lefebvre. Optimization of storage mappings for parallel programs. Technical Report 1998/46, PRiSM, U. of Versailles, 1988.Google Scholar
- 4.A. Darte, Y. Robert, and F. Vivien. Scheduling and Automatic Parallelization. Birkh. auser Boston, 2000. Google ScholarDigital Library
- 5.P. Feautrier. Array expansion. In ACM Int. Conf. on Supercomputing, pages 429-441, 1988. Google ScholarDigital Library
- 6.P. Feautrier. Data ow analysis of array and scalar references. Int. J. of Parallel Programming, 20(1):23-51, 1991.Google ScholarCross Ref
- 7.P. Feautrier. Some efficient solutions to the affine scheduling problem. part I. one-dimensional time. Int. J. of Parallel Programming, 21(5):313-347, Oct. 1992. Google ScholarDigital Library
- 8.P. Feautrier. Some efficient solutions to the affine scheduling problem. part II. multidimensional time. Int. J. of Parallel Programming, 21(6):389-420, Dec. 1992. Google ScholarDigital Library
- 9.P. Feautrier, J.-F. Collard, M. Barreteau, D. Barthou, A. Cohen, and V. Lefebvre. The interplay of expansion and scheduling in paf. Technical Report 1998/6, PRiSM, U. of Versailles, 1988.Google Scholar
- 10.F. Irigoin and R. Triolet. Supernode partitioning. In Proc. 15th Annual ACM Symp. Principles of Prog. Languages, pages 319-329, San Diego, CA, Jan. 1988. Google ScholarDigital Library
- 11.V. Lefebvre and P. Feautrier. Automatic storage management for parallel programs. Parallel Computing, 24(3-4):649-671, May 1998. Google ScholarDigital Library
- 12.A. Lim and M. Lam. Maximizing parallelism and minimizing synchronization with affine transforms. In Proceedings of the 24th Annual ACM SIGPLAN-SIGACT Symp. on Principles of Prog. Languages, Jan. 1997. Google ScholarDigital Library
- 13.V. Loechner and D. K. Wilde. Parameterized polyhedra and their vertices. Int. J. of Parallel Programming, 25(6):525-549, Dec. 1997. Google ScholarDigital Library
- 14.S. B. Needleman and C. D. Wunsch. A general method applicable to the search of similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48:443-453, 1970.Google ScholarCross Ref
- 15.W. Pugh. The Omega test: a fast and practical integer programming algorithm for dependence analysis. Communications of the ACM, 8:102-114, Aug. 1992. Google ScholarDigital Library
- 16.A. Schrijver. Theory of Linear and Integer Programming. John Wiley and Sons, New York, 1986. Google ScholarDigital Library
- 17.M. M. Strout, L. Carter, J. Ferrante, and B. Simon. Schedule-independent storage mapping for loops. In Architectural Support for Programming Languages and Operating Systems, pages 24-33, 1998. Google ScholarDigital Library
- 18.D. Wilde and S. Rajopadhye. Memory reuse analysis in the polyhedral model. Parallel Processing Letters, 7(2):203-215, June 1997.Google ScholarCross Ref
Index Terms
- A unified framework for schedule and storage optimization
Recommendations
A unified framework for schedule and storage optimization
We present a unified mathematical framework for analyzing the tradeoffs between parallelism and storage allocation within a parallelizing compiler. Using this framework, we show how to find a good storage mapping for a given schedule, a good schedule ...
A step towards unifying schedule and storage optimization
We present a unified mathematical framework for analyzing the tradeoffs between parallelism and storage allocation within a parallelizing compiler. Using this framework, we show how to find a good storage mapping for a given schedule, a good schedule ...
Schedule-independent storage mapping for loops
This paper studies the relationship between storage requirements and performance. Storage-related dependences inhibit optimizations for locality and parallelism. Techniques such as renaming and array expansion can eliminate all storage-related ...
Comments