Parallelism in nested loops with unimodular transformation and affine partitioning
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Executing a program in parallel needs not only to find sufficient parallelism in a program, but it is also important that we minimize the synchronization and communication overheads in the parallelized program. Many of loop transformations have been developed to extract the parallelism from nested loops. In this paper, two loop transformations are compared; the unimodular transformation and the affine partitioning. The study shows that unimodular transformation is better than affine partitioning when the nested loops have a one statement and the dependence exists at this statement. While affine partitioning is more effective when the nested loops have a sequence of statements and the dependence exists between these different statements.
Abstract
Executing a program in parallel needs not only to find sufficient parallelism in a program, but it is also important that we minimize the synchronization and communication overheads in the parallelized program. Many of loop transformations have been developed to extract the parallelism from nested loops. In this paper, two loop transformations are compared; the unimodular transformation and the affine partitioning. The study shows that unimodular transformation is better than affine partitioning when the nested loops have a one statement and the dependence exists at this statement. While affine partitioning is more effective when the nested loops have a sequence of statements and the dependence exists between these different statements.
참고문헌 (32)
- A. Schrijver, "Theory of Linear and Integer Programming" (1986), Wiley
- A.W. Lim, "An Affine Partitioning Algorithm to Maximize Parallelism and Minimize Communication", Proceeding of the 13th ACM SIGARCH international Conference on Supercomputing (1999)
- A.W. Lim, "Cache Optimizations with Affine Partitioning", In Proceedings of the Tenth SIAM Conference on Parallel Processing for Scientific Computing (2001)
- A.W. Lim, "Maximizing Parallelism and Minimizing Synchronization with affine partitions", Parallel Computing, 24(3;4), pp.445~475 (1998)
- A.W. Lim, "Maximizing Parallelism and Minimizing Synchronization with Affine Transforms", In Conference Record of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (1997)
- C. Bastoul, "Improving Data Locality in Static Control Programs", pp.2004
- C. Gong, "Loop Transformations for Fault Detection in Regular Loops on Massively Parallel Systems", IEEE Transactions on Parallel and Distributed Systems, 7(12), pp.1238~1249 (1996)
- C.T. Yang, "Run-time Parallelization for Partially Parallel Loops", Proceedings of the 1997 International Conference on Parallel and Distributed Systems, pp.308~313 (1997)
- C. Xu, "Effects of Parallelism Degree on Run-Time Parallelization of Loops", Proceedings of the 31st Hawaii International Conference on System Sciences (HICSS’98)
- D.R. Chesney, "Generalizing the Unimodular Approach", Proceedings of the 1994 International Conference on Parallel and Distributed Systems, pp.398~403 (1994)
- E. D’Hollander, "Partitioning and Labeling of Loops by Unimodular Transformations", IEEE Transactions on Parallel and Distributed Systems, 3(4), pp.465~476 (1992)
- G. Goumas, "An Efficient Code Generation Technique for Tiled Iteration Spaces", IEEE Tran. On Parallel and Distrib. Syst, 14(10), pp.1021~1034 (2003)
- J. Xue, "Unimodular Transformations of Non-Perfectly Nested Loops", Parallel Computing, 22(12), pp.1621~1645 (1997)
- K. Psarris, "The Direction Vector I Test", IEEE Transactions on Parallel and Distributed Systems, 4(11), pp.1280~1290 (1993)
- L.N. Pouchet, "When Iterative Optimization Meets the Polyhedral Model: Onedimensional Date", 석사, pp.2006
- M. Rim, "Valid Transformations: A New Class of Loop Transformations for High-Level Synthesis and Pipelined Scheduling Applications", IEEE Transactions on Parallel and Distributed Systems, 7(4) (1996)
- M. wolf, "A Loop Transformation Theory and an Algorithm to Maximize Parallelism", IEEE Transactions on Parallel and Distributed Systems, 2(4), pp.452~471 (1991)
- M. Wolfe, "High Performance Compilers for Parallel Computing" (1996), Addison-Wesley publishing Company, Inc
- M. wolfe, "The Power Test for Data Dependence", IEEE Transactions on Parallel and Distributed Systems, 3(5), pp.591~601 (1992)
- N.A. Likhoded, "Obtaining Affine Transformations to Improve Locality of Loop Nests", Programming and Computer Software, 31(5), pp.270~281 (2005)
- N. Manjikian, "Fusion of Loops for Parallelism and Locality", IEEE Transactions on Parallel and Distributed Systems, 8(2), pp.193~209 (1997)
- P.M. Petersen, "Static and Dynamic Evaluation of Data Dependence Analysis Techniques", IEEE Transactions on Parallel and Distributed Systems, 7(11), pp.1121~1132 (1996)
- Transforming Complex Loop Nests for Locality, "Q. Yi", ~, pp.Report TR02-386 (2002)
- U. Banerjee, "An Introduction to a Formal Theory of Dependence Analysis", Journal of Supercomputing, 2, pp.133~149 (1988)
- U. Banerjee, "Loop Transformations for Restructuring Compilers: The Foundations", Kluwer Academic Publishers (1993)
- U. Banerjee, "Loop Parallelization" (1994), Kluwer Academic Publishers
- U. Banerjee, "Dependence Analysis" (1997), Kluwer Academic Publishers
- Affine Transformations for Communication Minimal Parallelization and Locality Optimization of Arbitrarily Nested Loop Sequences, "U. Bondhugula", Ohio State Univ., ~, pp.Report OSU-CISRC-5 (2007), 07-TR43
- V. Maslov, "Lazy array data flow dependence analysis", Conference record of the annual ACM symposium on principles of programming languages, pp.311~325 (1994)
- W. Pugh, "A Practical Algorithm for Exact Array Dependence Analysis", Communications of The ACM, 35(8), pp.102~114 (1992)
- X. Kong, "The I Test: An Improved Dependence Test for Automatic Parallelization and Vectorization", IEEE Transactions on Parallel and Distributed Systems, 2(3), pp.342~349 (1991)
- Z. Li, "An Efficient Data Dependence Analysis for Parallelizing Compilers", IEEE Transactions on Parallel and Distributed Systems, 1(1), pp.26~34 (1990)