Automatic loop interchange
John R. Allen, Ken Kennedy · 1984
Parallel and vector machines are becoming increasingly important to many computation intensive applications. Effectively utilizing such architectures, particularly from sequential languages such as Fortran, has demanded increasingly sophisticated compilers. In general, a compiler needs to significantly reorder a program in order to generate code optimal for a specific architecture.Because DO loops typically control the execution of a number of statements, the order in which loops are executed can dramatically affect the performance of a machine on a particular section of code. In particular, loop interchange can often be used to enhance the performance of code on parallel or vector machines.Determining when loops may be safely and profitably interchanged requires a study of the data dependences in the program. This work discusses specific applications of that theory to loop interchange. This theory is described as it has been implemented in PFC (Parallel Fortran Converter) -- a program which attempts to uncover operations in sequential Fortran code that may be safely rewritten as vector operations.
Cited by 183 works. doi:10.1145/502874.502897 Open-access PDF
Authors
References
- The Art of Computer Programming
- Depth-First Search and Linear Graph Algorithms
- The Art of Computer Programming. Volume 1: Fundamental Algorithms.
- The NYU Ultracomputer—Designing an MIMD Shared Memory Parallel Computer
- Dependence graphs and compiler optimizations
- Squeezing the most out of an algorithm in CRAY FORTRAN
- Conversion of control dependence to data dependence
- The parallel execution of DO loops
- Implementing Linear Algebra Algorithms for Dense Matrices on a Vector Pipeline Machine
- Dependence analysis for subscripted variables and its application to program transformations