Performance evaluation of a general parallel processing model

Abstract

In this paper we analyze a model of a parallel processing system. In our model there is a single queue which is served by K ≥ 1 identical processors. Jobs are assumed to consist of a sequence of barrier synchronizations where, at each step, the number of tasks that must be synchronized is random with a known distribution. An exact analysis of the model is derived. The model leads to a rich set of results characterizing the performance of parallel processing systems. We show that the number of jobs concurrently in execution, as well as the number of synchronization variables, grows linearly with the load of the system and strongly depends on the average number of parallel tasks found in the workload. Properties of expected response time of such systems are extensively analyzed.