DETECTION OF ESSENTIAL ORDERING IMPLICIT IN COMPILER LANGUAGE PROGRAMS
Abstract
An investigation was made to determine how implicit parallelism in programs written in compiler languages can be recognized and exploited by machines with highly parallel organizations. An algorithm is described which identifies the complete serial ordering among parts of a program based on the input-output sets of these parts, the ordering given by the programmer, and any known essential order among the program parts. The algorithm is proved and a demonstration given that a minimum number of comparisons of input-output sets are made. Application of the parallel recognition procedure to subroutines, loops, conditionals, recursive subroutines, and serial input-output device calls is explained. The effect of particular features of several compiler languages on parallelism are discussed. These features include loops, transfers of control, conditionals, and conditional sequences. Requirements for replacing iterative loop control by parallel paths of control are given. Alternative algorithms for recognizing essential ordering are suggested which can be executed more effectively on a highly parallel machine. Application of the given algorithm to the syntactic definition of a context-free language is also considered.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1967
- Accession Number
- AD0650845
Entities
People
- David A. Fisher
- Harvey W. Bingham
- Warren L. Semon