On the Number of Operations Simultaneously Executable in Fortran-Like Programs and Their Resulting Speedup

Abstract

This paper is concerned with the problem of analyzing ordinary Fortran-like programs to determine how many of their operations could be performed simultaneously. Algorithms are presented for handling arithmetic assignment statements, DO loops and IF statement trees. The height of the parse trees of arithmetic expressions is reduced by distribution of multiplication over addition as well as the use of associativity and commutativity. DO loops are analyzed in terms of their index sets and subscript forms. Some general underlying assumptions about machine organization are also given. In terms of several measures which are defined, the results of experimental analyses are presented. About 20 Fortran IV programs consisting of nearly 1000 source cards were analyzed. Evidence is given that for very simple Fortran programs 16 processors could be effectively used operating simultaneously in a parallel or pipeline fashion. Thus, for medium or large size Fortran programs, machines consisting of multiples of a basic 16 processor unit could be used.