Interprocedural Transformations for Parallel Computing

다국어 초록 (Multilingual Abstract)

Since the most program execution time is consumed in a loop structure, extracting parallelism from loop programs is critical for the faster program execution. In this paper, we proposed data dependency removal method for a single loop. The data dependency removal method can be applied to uniform and non-uniform data dependency distance in the single loop. Procedure calls parallelisms with only a single loop structure or procedure call most of other methods are concerned with the uniform code within the uniform data dependency distance. We also propose an algorithm, which can be applied to uniform, non-uniform, and complex data dependency distance among the multiple procedures. We compared our method with conventional methods using CRAY-T3E for the performance evaluation. The results show that the proposed algorithm is effective.

참고문헌 (Reference)

1 D'Hollander. E. H, "Partitioning and Labeling of Loops by Unimodular Transformations" IEEE Trans 3 (3): 1992

2 Hall. M. W, "Managing Interprocedural Optimization" Rice University 1991

3 Banerjee. U, "Loop Transformations for Restructuring Compilers : The Foundations," Kluwer Academic Publishers 1993

4 Hall. M. W, "Interprocedural Transformations for Parallel Code Generation" Rice University 1991

5 Zhang. W, "Interprocedural Optimizations for Improving Data Cache Performance of Array Intensive Embedded Applications" Anaheim California 2003

6 Wolfe. M. J, "High Performance compiler for Parallel Computing" Oregon Graduate Institute of Science Technology 1996

7 Tzen. T. H, "Dependence Uniformization : A Loop Parallelization Technique" IEEE Transactions on Parallel and Distributed Systems

8 Punyamurtula.S, "Compile Time Partitioning of Nested Loop Iteration Spaces with Non uniform Dependences" 1996

9 Allen. F, "An Overview of the PTRAN analysis System for Multiprocessing" 5 (5): 1998

10 Chen Y S, "AParallelizing Compilation Approach to Maximizing Parallelism within Uniform Dependence Nested Loops" National Taiwan University 1993

11 Mckinley. K. S, "A Compiler Optimization Algorithm for Shared Memory Multiprocessors" 9 (9): 769-787, 1998