Parallel program schemata: A mathematical model for parallel computation

Abstract

Many recent design proposals for highperformance computer systems are based on an organization in which many programs, procedures within a program, or instances of the same procedure applied to different data, can simultaneously be in progress. In these systems parallelism becomes a major consideration in problem analysis, the specification of programming languages and the de sign of compiler s and operating systems. Since programming languages currently in use have no explicit provision for representing parallel sequencing, it is necessary to develop new representations of algorithms in order to display various kinds of parallelism and make it easy to take advantage of them. In addition, new questions concerning the analysis and synthesis of a1goriths suggest themselves in connection with parallel computation. Methods will be required for determining the degree of parallelism of given algorithms and for converting algorithms to more highly parallel equivalent forms. Also, the phenomenon of "race s" between computation steps, leading to the possibility of indeterminacy, will have to be studied.