Technical Report CS0351

Title: On Parallel Programming Primitives
Authors: M. Yoeli and A.Ginzburg
Abstract: Structured programing is now widely recognized as an essential tool for the design of correct, easily understood programs. A key issue in structured programming iS the suitable choice of the set of control structures to be used. As far as structured sequential programming is concerned, important theoretical results are available on the "relative power" of various classes of control structures. This paper discusses this "relative power" issue for classes of parallel control structures. It establishes a mathematically precise framework in which all the relevant results are presented.

Only a restricted class or parallel programs is considered in this paper. These programs can be represented by one-in, one-out cycle-free structures containing basic action modules and two types of control moduls: 2-way forks and 2-way jolns. In particular, we demonstrate the limitations of any finite set of controi primitives: there always exists a parallel program not: structurable by means of the given set of primitives.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1985
To the main CS technical reports page

Computer science department, Technion