A cost/benefit estimating service for mapping parallel applications on heterogeneous clusters

Matching the resource requirements of a parallel application to the available resources of a large, heterogeneous cluster is a key requirement in effectively scheduling the application tasks on the nodes of the cluster. This paper describes the Cost/Benefit Estimating Service (CBES), a runtime scheduling system targeted at finding highly effective schedules (or mappings) of tasks on 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. At the core of CBES is a mapping evaluation module which evaluates candidate application mappings on the basis of shortest execution times. By default, CBES uses a simulated-annealing based scheduler to select mappings. The paper presents the design, initial implementation, and test results of CBES on the Centurion cluster at the University of Virginia and the Orange Grove cluster at Syracuse University. These tests demonstrated that the exploitation of internode communication speed differences due to network heterogeneity can yield speedups of over 10% between same architecture nodes. The, maximum observed speedup across architectures for the best vs. worst mapping scenarios of the same application was over 36%, while the corresponding average case speedup was approximately 30%.