DETECTION OF IMPLICIT COMPUTATIONAL PARALLELISM FROM INPUT-OUTPUT SETS.

Abstract

This is the first report of an investigation designed to show how the implicit parallelism in programs written in present programming languages can be recognized and exploited by computers with highly parallel machine organizations. A language-independent recognition algorithm is developed. A program is treated as a partially ordered set of processes. A process is a transformation of an input set into an output set. The algorithm represents a method for converting the given ordering relation among processes in any given program into the essential ordering relation. Unnecessary serial ordering imposed by present programming languages is eliminated. The essential ordering is recognized by comparing inputs to processes with outputs of selected prior processes. The number of comparisons is the minimum necessary to detect the essential ordering. The algorithm is explained in detail and the equivalent graphical operations are described. Program loops and conditionals can be analyzed within the framework of the algorithm. Process inputs and outputs are related to memory and input-output devices. Various levels of partitioning a program into processes are discussed. (Author)

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1966
Accession Number
AD0645120

Entities

People

  • David A. Fisher
  • Harvey W. Bingham
  • Warren L. Semon

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computer Languages
  • Computer Programming
  • Computers
  • Detection
  • Formal Languages
  • Input Output Devices
  • Language
  • Programming Languages
  • Recognition

Fields of Study

  • Computer science

Readers

  • Computational Linguistics
  • Mathematical Modeling and Probability Theory.
  • Systems Analysis and Design