An Analytical Study of the Time Variance in Parallelism in Dataflow Architectures
C. R. M. Sundaram, Y. Narahari · 2005
Evaluating the performance of parallel computations on parallel machines is an issue of great importance in the design of parallel processing systems. In this paper, we use an integrated modelling framework comprising Product Form Queueing Networks (PFQN’s) and Generalized Stochastic Petri Nets (GSPN’s) to model and evaluate the effect of the variance in parallelism in parallel computations. We focus on dataflow computations and present an integrated PFQN-GSPN model for the execution of dataflow computations on the Manchester dataflow machine. We characterize the parallelism in dataflow computations through a 4-parameter characterization comprising the minimum parallelism, maximum parallelism, average parallelism and the variance in parallelism. This model can be efficiently solved. The numerical results indicate that the average parallelism is a good characterization of the dataflow computations only as long as the variance in parallelism is small. However, siginficant difference in performance measures will result when the variance in parallelism is comparable to or higher than the average parallelism.