AUTOMATIC DETECTION OF PARALLELISM IN COMPUTER PROGRAMS.
Abstract
The object of the first year of this research has been to establish the desirability and feasibility of automatically recognizing parallelism in computer programs written in compiler languages, given suitable machine organizations capable of parallel or concurrent execution. An algorithm for formal analysis of programs is described. This algorithm detects implicit parallelism that exists between parts of a given sequentially ordered program from the input-output set intersections and any initially known essential serial order. The algorithm can be applied to program structures including subroutines, loops, conditionals, recursive subroutines, arrays, and serial input-output calls. To demonstrate that the automatic recognition of parallelism is feasible, a simulation based on the algorithm has been programmed on the Burroughs B5500 for analysis of compiler language programs. The source language for the programs to be analyzed (a subset of ALGOL), a description of the simulation, example programs for analysis, and the results of parallelism detection are given. Desirability is dependent on having machine organizations capable of using the parallelism effectively. The relation between parallelism in programs and the machine organizations will be investigated in future reports. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1967
- Accession Number
- AD0662274
Entities
People
- David A. Fisher
- Earl W. Reigel
- Harvey W. Bingham