Performance evaluation of fork and join synchronization primitives. (English) Zbl 0625.68025

Duda, Andrzej; Czachórski, Tadeusz

Acta Inf. 24, 525-553 (1987).

Summary: The paper presents a performance model of \(\mathbf{fork}\) and \(\mathbf{join}\) synchronization primitives. The primitives are used in parallel programs executed on distributed systems. Three variants of the execution of parallel programs with \(\mathbf{fork}\) and \(\mathbf{join}\) primitives are considered and queueing models are proposed to evaluate their performance on a finite number of processors. Synchronization delays incurred by the programs are represented by a state-dependent server with service rate depending on a particular synchronization scheme. Closed form results are presented for the two processor case and a numerical method is proposed for many processors. Fork-join queueing networks having more complex structure i.e., processors arranged in series and in parallel, are also analyzed in the same manner. The networks can model the execution of jobs with a general task precedence graph corresponding to a nested structure of the fork-join primitives. Some performance indices of the parallel execution of programs are studied. The results show that the speedup which can be obtained theoretically in a parallel system may be decreased significantly by synchronization constraints.

MSC:

68N25	Theory of operating systems
68M20	Performance evaluation, queueing, and scheduling in the context of computer systems

Keywords:

performance model; parallel programs; distributed systems; queueing models; processors; Synchronization; Fork-join queueing networks; parallel execution