Browse Prior Art Database

Automatic Translation of Fortran Programs to Vector Form

IP.com Disclosure Number: IPCOM000128276D
Original Publication Date: 1984-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 41 page(s) / 92K

Publishing Venue

Software Patent Institute

Related People

John R. Allen: AUTHOR [+4]

Abstract

The recent success of vector computers such as the Cray- I and array processors such as those manufactured by Floating Point Systems has increased interest in making vector operations available to the Fortran p'rogrammer. The Fortran standards committee is currently considering a successor to Fortran 77, usually called Fortran 8x, that will per-mit the programmer to explicitly specify vector and array operations. Although Fortran 8x will make it convenient to specify explicit vector operations in new prpgrams, it does little for existing code. In order to benefit from the power of vector hardware, existing programs will need to be rewritten in some language (presumably For-tran 8x) that permits the explicit specification of vector operations. One way to avoid a massive manual recoding effort is to provide a translator that discovers the parallelism im-plicit in a Fcrtran program and automatically rewrites that program in Fortran 8x. Such a translation from Fortran to Fortran 8x is not straightfor-ovard because Fortran DO loops are not always semantically equivalent to the corresponding Fortran 8x parallel operation. The semantic difference between these two constructs is precisely captured by the concept of dependence. A translation from Fortran to Fortran 8x preserves the se-mantics of the original program if it preserves the dependences in that program. This paper develops the theoretical background for empioying data dependence to convert Fortran. programs to parallel form. Dependence is defined and characterized in terms of the conditions that give rise to it; accurate tests to determine dependence are presented-, and transformations which use dependence to uncover additional parallelism are dis-cussed.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 6% of the total text.

Page 1 of 41

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Automatic Translation of Fortran Programs to Vector Form.,

John R. Allen Ken Kennedy

Rice COMP TR84-9** July 1984

Department of Computer Science Rice University P.O. Box 1892 Houston, Texas 77251

*43upport. I for this work was provided by IBM Corporatioa. "Previously available as O.ice MASC 476-029-4 (October 1980).

Automatic Translation of Fortran Programs to Vector Form

John R. Allen Ken Kennedy

Abstract

The recent success of vector computers such as the Cray- I and array processors such as those manufactured by Floating Point Systems has increased interest in making vector operations available to the Fortran p'rogrammer. The Fortran standards committee is currently considering a successor to Fortran 77, usually called Fortran 8x, that will per-mit the programmer to explicitly specify vector and array operations.

Although Fortran 8x will make it convenient to specify explicit vector operations in new prpgrams, it does little for existing code. In order to benefit from the power of vector hardware, existing programs will need to be rewritten in some language (presumably For-tran 8x) that permits the explicit specification of vector operations. One way to avoid a massive manual recoding effort is to provide a translator that discovers the parallelism im-plicit in a Fcrtran program and automatically rewrites that program in Fortran 8x.

Such a translation from Fortran to Fortran 8x is not straightfor-ovard because Fortran DO loops are not always semantically equivalent to the corresponding Fortran 8x parallel operation. The semantic difference between these two constructs is precisely captured by the concept of dependence. A translation from Fortran to Fortran 8x preserves the se-mantics of the original program if it preserves the dependences in that program. This paper develops the theoretical background for empioying data dependence to convert Fortran. programs to parallel form. Dependence is defined and characterized in terms of the conditions that give rise to it; accurate tests to determine dependence are presented-, and transformations which use dependence to uncover additional parallelism are dis-cussed.

1. Introduction

With the advent of successful vector computers such as the Cray- I [Cray 76, Russ 78] and the popularity of array processors such as the Floating Point Systems AP-120 [FPS 78,V,ith 78], there has been increased interest in making vector operations available to the Fortran programmer. One common method is to supply a "vectorizing" Fortran compiler [Cray 801 as depicted in Figure 1. Here standard Fortran is accepted as input and, as a part of the

Rice University Page 1 Dec 31, 1984

Page 2 of 41

Automatic Translation of Fortran Programs to Vector Form

optimization phase of the com-piler, a vectorizing stage attempts to convert the innermost loops to vector operations. The code generator can then produce vector machine code for these operations.

This...