On the Semantics of Parallel Programs

Article type: Research Article

Authors: Müldner, Tomasz

Affiliations: Institute of Computing Machines

Abstract: The paper deals with the semantics of parallel programs. It is shown that there exist other semantics besides the well-known one, which reflects multiplexing and is defined as an interleaving of elementary actions. Those semantics are not necessarily equivalent with respect to the input (out-put) relation; moreover, they permit the investigation of the internal behaviour of a computation. A formalized language of parallel programs is defined. Definitions of computational semantics and of a tree of acceptable computations are given. As an example of computational semantics the semantics MULT (for multiplexing) is defined. Next a scheme of computational semantics is introduced. Given the scheme, one can define various computational semantics by means of several strategies. The most natural scheme of computational semantics is then given, followed by examples defined by it. Connections between different classes of computational semantics are examined.

Keywords: Semantics of parallel program, acceptable computation

DOI: 10.3233/FI-1981-4104

Journal: Fundamenta Informaticae, vol. 4, no. 1, pp. 35-81, 1981