Investigation of effect of different run-time distributions on SmartNet performance

Abstract

This thesis investigates, using in-line simulation, the effect of non-deterministic runtime distributions on the performance of SmartNet's schedule execution using the Opportunistic Load Balancing (OLB) Algorithm, the Limited Best Assignment (LBA) Algorithm, an O(mn squared) Greedy Algorithm, and an O(mn) Greedy Algorithm. SmartNet is a framework for scheduling jobs and machines in a heterogeneous computing environment. Its major strength is its use of both current machine loads and predicted job/machine performance when generating schedules. Schedules are built to meet various Quality of Service requirements using the above algorithms among others. We enhanced SmartNet's simulator so that the runtime distributions could be used for experimentation. The distributions were generated using derivations from our study on NAS benchmarks. Experiments were run for various categories of job/machine heterogeneity to compare the algorithms which account for both load and expected performance (the Greedy algorithms) against OLB and LBA. For all categories of heterogeneity, the greedy algorithms outperformed the other two algorithms for both truncated Gaussian and exponential distributions. For these same distributions, the O(mn) Greedy algorithm performed as well as the O(mn2) Greedy algorithm when the heterogeneity of jobs and machines was high