Matching and scheduling of applications in heterogeneous computing systems with emphasis on high performance, reliability, and QoS

A heterogeneous computing (HC) system is a suite of dissimilar machines interconnected by a high-speed network that enables the high-speed processing of computationally intensive applications with diverse computing needs. A major obstacle to using such a computing environment for harnessing the performance of applications is the matching and scheduling problem. In addition, the advent of networking technologies makes it possible to apply heterogeneous computing to a global scale. With the growing scale of heterogeneous computing, however, machine and network failures will become inevitable and affect applications executing on the system adversely. Furthermore, a number of users with multiple quality of service (QoS) requirements for their applications will be exposed to heterogeneous computing. Finally, several parameters used by many classic scheduling algorithms have a stochastic nature that should be accounted for accordingly in designing new scheduling algorithms. Given these issues, this research has investigated each problem as summarized below.; In the first problem, a static, duplication based matching and scheduling algorithm is developed that can achieve very high performance for an application modeled by a directed acyclic graph (DAG). Next, a reliable scheduling technique is presented that introduces an incremental cost function, which can be incorporated into an existing static or dynamic matching and scheduling heuristic, to improve the reliability of DAG-structured applications executing on a failure-prone HC system. After that, two biobjective matching and scheduling algorithms that can trade off execution time for reliability of a DAG-structured application are devised, where both algorithms depend on a unique mathematical model to compute the reliability of the application. Next, a static QoS-based matching and scheduling algorithm, which can achieve very good success ratio in providing users with the minimum QoS desired and very high net system utilization, is introduced for a set of independent tasks with no data dependencies, where each task can have a distinct number of QoS requirements including timeliness, reliability, security, data accuracy, and priority. Finally, the impact of accounting for the stochastic nature of the execution times of tasks on the performance of a meta-task is both theoretically and experimentally studied.