Queueing Network Models for Parallel Processing of Task Systems.

Abstract

The authors deal with a procedure to determine the mean completion time and related performance measures for a task system: a set of tasks with precedence relationships in their execution sequence. The tasks, which are processed by a multiprogrammed multiprocessor system, are specified by their expected total loadings on the units of the computer system. A straightforward application of a queueing network solver to the problem is not possible due to variations in the state of the system. An approximate solution method is presented for this purpose based on the concept of hierarchical decomposition. At the higher level, an efficient procedure generates the Markov chain corresponding to the transitions among the system states and computes state probabilities and other parameters as each state is created. At the lower level, the transition rates among the states are computed using a qn solver which determines the throughput of the computer system for each system state. Numerical results are presented to justify the decomposition method and validated through simulation. The approach is applicable to performance evaluation of programs with internal concurrency. 9 references.