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 >Q 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 and, in particular, we report on some non-obvious response time behavior that arises as a function of the variance of parallelism found in the workload. Based on exact response time analysis, we propose a simple calculation that can be used as a rule of thumb to predict speedups. This can be viewed as a generalization of Amdahl's law that includes queueing effects. This generalization is reformulated when precise workloads cannot be characterized, but rather when only the fraction of sequential work and the average number of parallel tasks are assumed to be known.