Performance evaluation of fork and join synchronization primitives

Summary The paper presents a performance model of fork and join synchronization primitives. The primitives are used in parallel programs executed on distributed systems. Three variants of the execution of parallel programs with fork and 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.This research we carried out while the author was visiting ISEM, Université de Paris-Sud, France