Analytic Queueing Network Models for Parallel Processing of Task Systems

This paper is concerned with the performance evaluation of a realistic model of parallel computations. We present an efficient algorithm 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, such that the resulting graph is acyclic. A queueing network (QN) is used to model tasks executing on a single or multicomputer system. In the case of multicomputer systems, we take into account the delay due to interprocess communication. A straight- forward application of a QN solver to the problem is not possible due to variations in the state of the system (composition of tasks in execution). An accurate algorithm based on hierarchical decomposition is presented for solving task systems. At the higher level, the system behavior is specified by a Markov chain whose states correspond to the combination of tasks in execution. The state transition rate matrix for the Markov chain is triangular (since the task system graph was assumed to be acyclic), therefore it can be solved efficiently to compute the state probabilities and the task initiation/completion times. At the lower level, the transition rates among the states of the Markov chain are computed using a QN solver, which determines the throughput of the computer system for each system state. The model and the solution method can be used in performance evaluation of applications exhibiting concurrency in centralized/distributed systems where there are conflicting goals of load balancing and minimizing interprocess communication overhead.