Dynamic resource sharing mechanisms for high-performance heterogeneous clusters

Heterogeneous or federated clusters constitute a significant special case of grid computing and offer a prime environment for executing demanding parallel applications. Matching the resource requirements of a parallel application to the available resources of such a cluster is a key requirement in efficiently scheduling the application tasks on the nodes of the cluster.; This dissertation presents a novel method for finding efficient application mappings based on minimizing the required application execution time. CBES (Cost/Benefit Estimating Service), the method's testbed, is an auxiliary run-time system and has as its main goal to facilitate the search for such efficient mappings of application tasks on cluster nodes. CBES relies on its own infrastructure to gather and maintain static and dynamic information profiles for the computing system and the applications of interest. This infrastructure uses a cluster network end-to-end latency model and can generate a current view of CPU and network availability in O(N) time. At the core of CBES is a mapping evaluation module which evaluates mappings by predicting the execution time an application can achieve on each given mapping.; The initial implementation and tests of CBES took place on the Centurion cluster at the University of Virginia. Mapping evaluation tests on a wide range of mappings with synthetic and real applications explored the accuracy and limitations of the mapping evaluation module. For the examined real applications the prediction error was found to be approximately 2% on the average.; A second implementation of CBES was done on an experimental, highly heterogeneous version of the Orange Grove cluster at Syracuse University. Further experiments using a simulated annealing scheduler revealed that exploitation of the observed communication speed differences between nodes of the same architecture can yield speedups of over 10%. The maximum speedup across architectures for the best vs. the worst case scenario was found to be over 36%, while for the average case the speedup was found to be approximately 29%.