Integrated analytical models for parallel and distributed computing systems

Abstract

Analytical modelling plays an important role in the design and development of parallel and distributed computing systems. In this context, Product Form Queueing Networks (PFQNs) and Generalized Stochastic Petri Nets (GSPNs) represent two principal modelling tools. These tools have their own advantages and disadvantages in terms of computational complexity and flexibility of modelling. In this thesis, we consider a novel approach called Integrated Analytical Modelling, which combines the computational efficiency of PFQNs and the representational power of GSPNs. We show that integrated analytical models provide realistic and computationally efficient analytic solutions for two important problems in parallel and distributed computing. The first problem is concerned with modelling the effects of time variance of parallelism in dataflow computations. We develop efficient integrated analytical models for the Manchester dataflow machine and its various extended configurations. The numerical results from these models show that the average parallelism is a good characterization of dataflow computations only as long as the time variance of the parallelism is small compared to the average parallelism. However, there would be significant difference in performance estimates when the time variance of parallelism is comparable to or higher than the average parallelism. The second problem focuses on analytical evaluation of two heuristic dynamic load balancing strategies namely shortest queue routing (SQR) and shortest expected delay routing (SEDR). We identify some drawbacks of the existing approximate analyses of these policies and develop an efficient methodology based on integrated analytical models which overcomes these drawbacks. To investigate the efficacy of our methodology, we develop models for the closed central server systems. The numerical results show that for homogeneous distributed systems, SQR performs better than other policies. For heterogeneous systems, SEDR performs worse than SQR at low levels of imbalance in loads. However, when the imbalance in load is high, SEDR outperforms SQR and all other dynamic routing policies. We also carry out an error analysis of this technique and show that the results obtained using integrated analytical models are remarkably accurate.