Performance analysis of concurrent executions in parallel systems has been
recognized as a challenging problem. The aim of this research is to study a
pproximate but efficient solution techniques for this problem. We model the
structure of a parallel machine and the structure of the jobs executing on
such a system. We investigate rich classes of jobs, which can be expressed
by series, parallel-and, parallel-or, and probabilistic-fork. We propose a
n efficient performance prediction method for these classes of jobs running
on a parallel environment which is modeled by a standard queueing network
model. The proposed prediction method is computationally efficient, it has
polynomial complexity in both time and space. The time complexity is O((CNK
)-N-2-K-2) and the space complexity is O((CNK)-N-2-K-2), where C is the num
ber of job classes in the system, the number of tasks in each job class is
O(N), and K is the number of service centers in the queueing model. The acc
uracy of the approximate solution is validated via simulation.