Performance estimation of heterogeneous distributed computing systems that compute parallel algorithms

Heterogeneous distributed computing systems are an economical and efficient architecture for processing parallel algorithms, but do not normally match the performance of parallel computers with the same number of processors because of higher inherent distribution overhead. In many cases, however, particularly in comparison to the uniprocessor case, faster execution times can be achieved. In order to determine whether the expected levels of performance are obtainable or not, it is necessary to estimate the performance of a heterogeneous distributed system. This dissertation develops a set of performance estimators that are functions of the communication overhead, the relative processing power of the computers that execute the application, and the size of the computer subtask assigned to each machine. These parameters can be easily measured or obtained from the specifications of the underlying system and the characteristics of the distribution scheme used to implement the parallel algorithm