On the Compilation of Parallel Programs

Article type: Research Article

Authors: Müldner, Tomasz

Affiliations: Institute of Computing Machines, Warsaw

Abstract: The paper examines the properties of a compilation of sequential and parallel programs with respect to computational semantics, defined in the earlier paper of the present author “On the Semantics of Parallel Programs”. A compilation of sequential programs is defined and proved to be stable, i.e. the sets of results of an arbitrary program and the corresponding compiled program coincide. Next, a natural compilation of parallel programs is defined and shown not to be stable with respect to natural semantics: The compiled program may give the results which are not results of the source program. Other semantics are defined and it is proved that in those semantics the given compilation is stable. The main corollary states that for parallel programs with synchronizing tools, a compilation is stable in natural semantics.

Keywords: Parallel programs, compilation, stable compilation

DOI: 10.3233/FI-1981-4202

Journal: Fundamenta Informaticae, vol. 4, no. 2, pp. 207-243, 1981