Adjustment of Parametric Dynamic Scheduling Heuristics for Heterogeneous Systems to Account for Heterogeneity

Modern computing applications are becoming increasingly data-hungry and computationally expensive. This trend continues even as hardware performance constraints loom with the impending death of Moore\u27s law. Hence, systems have become increasingly heterogeneous in the pursuits of improving performance and reducing power consumption. Such a heterogeneous system relies on a variety of different specialized processors with differing architectures, rather than processing units of a single type. Given their architectural differences, any given computation will not perform equally on all processors. As such, efficient scheduling of computations to processors is an essential design consideration. In this thesis work, a simulation of an existing dynamic scheduling heuristic - Alternative Processor within Threshold (APT) - was used to model the execution of a variety of heterogeneous workloads and heterogeneous systems. An extended version of this scheduler (APTX) was analyzed in a similar way, as was a simplified version of the existing K-Percent Best (KPB) scheduler. Each of these schedulers has a numeric parameter constraining its behavior. In existing analyses, these scheduling heuristics were tested only with a small set of arbitrary values for these parameters. The goal of this research was to use a stochastic method to optimize said parameters for the minimum finishing time of any given set of computations on any given heterogeneous system. An analytical expression to estimate the ideal parameter of each scheduler was developed. Each was based on the statistical analysis of the results of a set of randomly-generated simulations. After these expressions were developed, these optimized APT, APTX, and KPB schedulers were evaluated against three other dynamic schedulers - Minimum Execution Time (MET), Serial Scheduling (SS), and Shortest Process Next (SPN) - by running the randomly-generated simulations on all six. For the most common type of heterogeneous system, APT and APTX were found to have the earliest finish time on average, while MET and KPB generally performed poorly. Ultimately, this research not only demonstrated the advantages of APT and APTX over other dynamic schedulers in a fair comparison, but it also demonstrated a method by which any parametric scheduler can be tuned