The Syntax of Parallelism

Article type: Research Article

Authors: Amir, Amihood^{a; *} | Smith, Carl H.^{b; **}

Affiliations: [a] Department of Computer Science and Institute for Advanced Computer Studies, The University of Maryland, College Park, MD 20742 | [b] Department of Computer Science and The University of Maryland, College Park, MD 20742

Note: [*] Supported in part by National Science Foundation Grant CCR 8803641.

Note: [**] Supported in part by National Science Foundation Grant CCR 8701104. This research was performed while the second author was also affilaited with the National Computer and Telecommunications Laboratory of the National Institute of Standards and Technology.

Abstract: One of the problems associated with the introduction of parallel processors is the so called “dusty deck” problem. A solution entails the development of optimizing compilers that transform programs previously written for a conventional serial processor into functionally equivalent programs that exploit the parallel processing capabilities of the new multiprocessor machines. We introduce a function Composition Model that models parallel architectures as a hierarchy of syntactic function definitions. Position in the hierarchy is equivalent to parallel time complexity in the modelled architecture. Other parallel concepts such as global vs. local communications, concurrency or exclusivity of read and write, and the number of processors used in a computation, are modelled as well. We rigorously prove that a compiler that optimizes a program for parallelism on a CREW PRAM is not effectively computable, even if it is also given an optimal serial program for the same task and a time bounding function. It turns out that the function composition model is similar to some traditional models, such as the Grzegorczyk Hierarchy. Our parallel interpretation of the Grzegorczyk Hierarchy offers new insights and admits a new cleaner and more elegant definition of the hierarchy with a single base class, as opposed to Grzegorczyk’s three.

DOI: 10.3233/FI-1993-193-409

Journal: Fundamenta Informaticae, vol. 19, no. 3-4, pp. 383-402, 1993